Wednesday, April 30, 2014

Antislacker

Last weekend I wrote a small Chrome extension that helps me to avoid facebook & livejournal. I mean I allow myself to stare at them for 10 minutes max & then Antislaker (the extension) kicks in & blocks those 2 domains for the rest of the day.

The idea is this:

  1. In background.coffee we look for a domain name match. If the match was successfully, we inject a chunk of JS code.
  2. The injected peace of the code contains a counter that every 5 seconds updates a record in localStore.
  3. When a time limit comes, we move user to our internal page withing Chrome extension that shows a random Dilbert comics.

The most tricky part was making a 'mutex' for localStore records. Because the user can open several facebook pages & the counter (in the worst case) will count 2 times faster. It's actually a pity that we don't have any concurrency primitives in JS & so we have to invert poor man's busy waiting when using timers.

Thursday, October 24, 2013

Multi-Lingual Interface With Jekyll

Imagine you have a site in N languages, for example, in English & Ukrainian. The content of articles is different & cannot be auto-translated, but we can ensure that the GUI on each part of the site is localized. All menus, buttons, tooltips, etc can be edited or localized without modifying the app source code.

Let's start with the example.

$ jekyll --version
jekyll 1.2.1

$ jekyll new blog && cd blog && mkdir _plugins

$ for i in en uk
  do
  (mkdir $i \
  && cd $i && ln -s ../css ../_l* ../_plugins . \
  && cp -r ../*yml ../_posts ../*html .); \
  done

$ rm -rf _config.yml _posts index.html

For each section we copied _posts, _config.yml & index.html, because for each site they all are different, and we symlinked css & _layouts directories because for each site they will be the same.

The site's structure looks like this:

_layouts/
|__ ..
|__ default.html
|__ post.html
_plugins/
|__ ..
css/
|__ ..
|__ main.css
|__ syntax.css
en/
|__ ..
|__ _layouts@ -> ../_layouts/
|__ _plugins@ -> ../_plugins/
|__ _posts/
|__ css@ -> ../css/
|__ _config.yml
|__ index.html
uk/
|__ ..
|__ _layouts@ -> ../_layouts/
|__ _plugins@ -> ../_plugins/
|__ _posts/
|__ css@ -> ../css/
|__ _config.yml
|__ index.html
.gitignore

Now, install jekyll-msgcat:

$ gem install jekyll-msgcat

Create _plugins/req.rb file & add to it 1 line:

require 'jekyll/msgcat'

Add to uk/_config.yml:

msgcat:
  locale: uk
  # may be 'domain' or 'nearby'
  deploy: nearby

Then open _layouts/default.html, find the line

<a class="extra" href="/">home</a>

& replace it with:

<a class="extra" href="/">{{ 'Return to Home' | mc }}</a>

(Quotes are essential.)

As you see, we are using some unknown Liquid filter 'mc'. If you check the uk site

$ (cd uk; jekyll serve)

& go to http://127.0.0.1:4000/, nothing will change, everything would be in English as before. To automatically substitute 'Return to Home' string with something else we need to create a message catalog.

In our case, the message catalog is just a .yaml file:

$ cat uk/_msgcat.yaml
uk:
  'Return to Home': На головну сторiнку

What is handy about this is that if the string in the message catalog isn't provided or if there is no _msgcat.yaml file at all, the default English string would be used. Kill jekyll's server & start it again to test.

Links to Localized Versions

The other problem you may have is how to generate a link from a current page to the same page in other language.

If you choose to host each site on a separate subdomain, e.g. en.example.com & uk.example.com, set the value of``msgcat.deploy`` key in site's _config.yml to domain. If you like a scheme without subdomains & prefer example.com/blog/en && example.com/blog/uk, set the key's value to nearby.

Make sure you have url & baseurl in _config.yml. In Liquid templates use cur_page_in_another_locale filter. For example, in _layouts/default.html:

{{ 'en' | cur_page_in_another_locale }}
{{ 'uk' | cur_page_in_another_locale }}

will generate in en site (msgcat.deploy == domain):

<a href='#' class='btn btn-primary btn-xs disabled'>en</a>
<a href='http://uk.example.com/index.html' class='btn btn-primary btn-xs '>uk</a>

or for msgcat.deploy == nearby:

<a href='#' class='btn btn-primary btn-xs disabled'>en</a>
<a href='/blog/uk/index.html' class='btn btn-primary btn-xs '>uk</a>

If you don't like injected names of Bootstrap's CSS classes, use the filter with an empty parameter:

{{ 'en' | cur_page_in_another_locale: "" }}
{{ 'uk' | cur_page_in_another_locale: "" }}

Or provide your own class name(s) instead of the empty string.

Friday, March 1, 2013

Creating Emacs Multi-file Packages

(This text assumes your familiarity with the difference between simple vs. multi-file packages in Emacs, how to create them, etc.)

After writing NAME-pkg.el, creating tar file & successfully installing a package from your local test archive, you may notice a small problem: the package meta information (its version, name, etc) appears in 2 or 3 places. Take, for example, a version number:

  • it's sitting somewhere in the code as a variable value;
  • it exists in NAME-pkg.el;
  • it's stored in Makefile because your target must be aware of the output file name (which must contain the version number).

Some even prefer to include it in README.

In other package systems like npm, this is a non-issue, because their package.json file that contains all the meta can be a first class citizen in the libraries that npm delivers. It's trivial to parse it & there are nive CLI tools like jsontool that can be used in Makefiles to extract any data from package.json.

Of course we can 'parse' our NAME-pkg.el file too. This snippet will read foobar-pkg.el file and return the version string from it:

(nth 2 (package-read-from-string
      (with-temp-buffer
        (insert-file-contents
         "foobar-pkg.el")
        (buffer-string))))

But it won't solve the problem with Makefile. For instance, you'll need to write a custom CLI util only to grab package's name & version from NAME-pkg.el.

meta.json

Instead we'll take another path & store all information about our package in a .json file. JSON can be easily parsed in elisp & with jsontool's help we can extract all data within Makefile.

meta.json may look like this:

{
    "name" : "foobar",
    "version" : "0.0.1",
    "docstring" : "Free variables and bound variables",
    "reqs" : {
        "emacs" : "24.3"
    },
    "repo" : {
        "type": "git",
        "url" : "git://example.com/foobar.git"
    },
    "homepage" : "http://example.com",
    "files" : [
        "*.el",
        "README",
        "meta.json"
    ]
}

If you're not familiar with jsontool, install it via npm -g jsontool & play:

$ json name < meta.json
foobar
$ json files < meta.json | json -a
*.el
README
meta.json
$ json -a -d- name version < meta.json
foobar-0.0.1

It's very handy.

Getting Meta Into Elisp

That .json file can be parsed once while our package is loading into Emacs. We can wrap that in a library, for example, foo-metadata.el:

(require 'json)

(defvar foo-meta (json-read-file
                 (concat (file-name-directory load-file-name) "/meta.json")))

(defconst foo-meta-version (cdr (assoc 'version foo-meta)))
(defconst foo-meta-name (cdr (assoc 'name foo-meta)))

(provide 'foo-metadata)

Then you just write (require 'foo-metadata) in your code.

Package Generation

Consider the minimal multi-file structure of some Foobar project:

foobar/
|__ ..
|__ bin/
|   |__ ..
|   |__ foo-make-pkg
|__ Makefile
|__ fb-bar.el
|__ fb-foo.el
|__ fb-foobar.el
|__ meta.json

Notice that file foobar-pkg.el is missing. Instead we have strange bin/foo-make-pkg utility that generates it. If we write it properly enough we can reuse it in another emacs project:

:; exec emacs -Q --script "$0" -- "$@" # -*- mode: emacs-lisp; lexical-binding: t -*-

(setq
 debug-on-error t                     ; show stack stace
 argv (cdr argv))                     ; remove '--' from CL arguments

(require 'json)

(when (not (= 2 (length argv)))
  (message "Usage: %s meta.json some-pkg.el" (file-name-base load-file-name))
  (kill-emacs 1))

(setq data (json-read-file (car argv)))

(setq reqs (cdr (assoc 'reqs data)))
(when reqs
  (let (rlist)
    (dolist (idx reqs)
      (push (list (car idx) (cdr idx)) rlist))
    (setq reqs `(quote ,rlist))
    ))

(with-temp-file
    (nth 1 argv)
  (insert (prin1-to-string
           (list 'define-package
                 (cdr (assoc 'name data))
                 (cdr (assoc 'version data))
                 (cdr (assoc 'docstring data))
                 reqs))))

Test it by running:

$ bin/foo-make-pkg meta.json foobar-pkg.el && cat !#:1
(define-package "foobar" "0.0.1" \
    "Free variables and bound variables" (quote ((emacs "24.3"))))

To bring all together we need 2 targets in Makefile: foobar-pkg.el that generates that file & a phony target package that creates elpa-compatible tar.

.PHONY: clean package

JSON := json
METADATA := meta.json
PKG_NAME := $(shell $(JSON) -a -d- name version < $(METADATA))

foobar-pkg.el: meta.json
    bin/foo-make-pkg $@

package: foobar-pkg.el
    $(TAR) --transform='s,^,$(PKG_NAME)/,S' -cf $(PKG_NAME).tar \
        `$(JSON) files < $(METADATA) | $(JSON) -a`

clean:
    rm foobar-pkg.el $(PKG_NAME).tar

Recall that with meta.json we have 1 definitive source of all project metadata, so when you'll need to update the version number or the project dependencies or the contents of the tar or whatever--you'll edit only 1 file.

There is, of course, another route--even without any file generation. For example, you can gently parse foobar-pkg.el in elisp & have an utility that from static foobar-pkg.el produces JSON, which goes to jsontool input.

Thursday, February 28, 2013

Emacs, ERT & Structuring Unit Tests

ERT framework, that everyone is using this days in Emacs, provide very little guidance on how to organize & structure unit tests.

Running tests in the Emacs you are working in is quote idiotic. Not only you can easily pollute editor's global namespace in case of mistyping, but unit tests in such mode cannot be reliable at all, because it's possible to create unwanted dependencies on a data structures that weren't properly destroyed in previous tests invocations.

Emacs batch mode

The only one right way to execute tests is to use emacs batch mode. The idea is: your Makefile contains test target which goes to test directory, which contains several test_*.el files. Each test_*.el file can be run independently & has a test selector (a regexp) that you may optionally provide as a command line parameter.

For example, consider some Foobar project:

foobar/
|__ ..
|__ test/
|   |__ ..
|   |__ test_bar.el
|   |__ test_foo.el
|   |__ test_utils.el
|__ Makefile
|__ foo-bar.el
|__ foo-foo.el
|__ foo-foobar.el
|__ foo-utils.el

To make this work, each test_* file must know where to find foo-*.el libraries & how to run its tests. Ideally it should not depend on a current directory from which user actually runs it.

test_utils.el script then looks like:

:; exec emacs -Q --script "$0" -- "$@"

(setq tdd-lib-dir (concat (file-name-directory load-file-name) "/.."))
(push tdd-lib-dir load-path)
(push (file-name-directory load-file-name) load-path)

(setq argv (cdr argv))

(require 'foo-utils)

(ert-deftest ignorance-is-strength()
  (should (equal (foo-utils-agenda) "war is peace")))

(ert-run-tests-batch-and-exit (car argv))

Here is quite a header before the ert-deftest definition.

1st line is a way to tell your kernel & bash to run emacs with current file as an argument. -Q option forces Emacs not to read your ~/.emacs file, not to process X resource, etc. This helps (a) to start Emacs as quickly as possible & (b) to force your code not to depend on your local customizations.

Next 3 lines modify load-path list which is used by Emacs to search for files when you 'require' or 'load' something. We add to that list a parent directory, where our *.el files are. Note that load-file-name contains an absolute path to the current test_utils.el file.

Next line removes '--' cell from argv list, so that (car argv) will give you 1st command line parameter passed to the script.

(require 'foo-utils) line loads ../foo-utils.el file (if you have provided 'foo-utils in it, of course).

Next 2 lines are usual ERT test definition with 1 assertion in this example.

The last line is a ERT command that runs your unit tests. Notice its argument--it allows you to optionally run the script as:

$ ./test_utils.el regexp

to filter out unmatched ert-deftest definitions.

Makefile

You can add to it 2 useful targets: test & compile. The last one transforms .el files to .elc & sometimes produces useful info about unused variables, etc:

.PHONY: test compile clean

ELC := $(patsubst %.el,%.elc,$(wildcard *.el))

%.elc: %.el
    emacs -Q -batch -L `pwd` -f batch-byte-compile $<

test:
    @for idx in test/test_*; do \
        printf '* %s\n' $$idx ; \
        ./$$idx ; \
        [ $$? -ne 0 ] && exit 1 ; \
    done; :

compile: $(ELC)

clean:
    rm $(ELC)

Hints

Try to make every test non-interactive. For example, if your command ask user for confirmation via (y-or-n-p), Emacs even in batch mode stops and waits for input from the terminal. If you need to answer "yes", just monkey patch the function:

(setq tdd-y-or-n nil) ;; by default say "no"
(defun y-or-n-p (prompt)
  tdd-y-or-n)

and then write an assert as:

(let ((tdd-y-or-n t))
  (should (freedom-is-slavery)))

You can monkey patch any elisp function except those which are compiled in (e.g. come from .c files & are 'primitive' in Emacs terminology).

Unfortunately, famous (message) function is built-in & cannot be monkey patched. If you use it heavily in the code, your non-interactive tests will fill the stderr with garbage that will distract you. It's better to use a global (to your project namespace) flag & a wrapper for (message):

(defconst foo-meta-name "foobar")
(defvar foo-verbose 1)

(defun foo-warn (level str &rest args)
"Print a message via (message) according to LEVEL."
(when (<= level foo-verbose)
  (if (/= 0 level) (setq str (concat foo-meta-name ": " str)))
  (message (apply 'format str args))
  ))

Then use (foo-warn 1 "hi, mom") in the code instead of (message). In .el libraries foo-verbose variable can be equal to 1, but in your tests set it to -1 to prevent printing to stderr.

Friday, January 25, 2013

ssh command quoting hell

When you type

$ ssh user@host 'cat /tmp/foo.txt'

cat /tmp/foo.txt part of that string is evaluated twice: 1) by your current shell as a single quoted string, 2) by a shell on a remote host.

Lets assume you want to write a script that backups some directory from a remote machine. A naive version:

$ cat mybackup.sh
#!/bin/sh

[ -z "$1" -o -z "$2" ] && exit 1

tcd=$1
tdir=$2
ssh user@host "tar cvf - -C $tcd $tdir | gzip" > foo.tar.gz

and if you run it like this:

$ ./mybackup.sh /home joe

And if everything goes ok, you'll get foo.tar.gz which will contain joe's home directory files. But what if $1 or $2 arguments contain spaces and/or quotes? I'll tell you:

$ ./mybackup.sh /home/joe 'tmp/foo "bar'
bash: -c: line 0: unexpected EOF while looking for matching `"'
bash: -c: line 1: syntax error: unexpected end of file

This is a bash error from a remote host because it tries to run

tar czv -C /home/joe tmp/foo "bar | gzip

and "bar contains an unmached quote. Obvously this is not the command you had in mind.

How can we fix that? Another naive approach would be to single-quote some variables in the script:

ssh user@host "tar cvf - -C '$tcd' '$tdir' | gzip" > foo.tar.gz

And this will work for our example but will fail if tmp/foo "bar directory would have a name tmp/foo 'bar (with a single quote instead of a double).

To make it work regardless of such shades we need somehow to transform $1 and $2 script arguments to quoted strings. Such transformed strings shall be a safe choice for substrings that represent to-be-executed commands on the remote host.

One nuance: transforming must be done not by the rules of /bin/sh or your current local shell, but by the rules of user's shell on a remote host. (See do_child() function in session.c of openssh source: it extracts user's shell name from users db on a remote machine & constructs arguments for execve(2) as "/path/to/shell_name", "shell_name", "-c", "foo", "bar".)

If the remote shell is a sh-derived one, the trasformation function can look like:

sq() {
    printf '%s\n' "$*" | sed -e "s/'/'\\\\''/g" -e 1s/^/\'/ -e \$s/\$/\'/
}

(Taken from of http://unix.stackexchange.com/a/4774.)

Then, a final version of the 'backup' script would be:

#!/bin/sh

sq() {
    printf '%s\n' "$*" | sed -e "s/'/'\\\\''/g" -e 1s/^/\'/ -e \$s/\$/\'/
}

[ -z "$1" -o -z "$2" ] && exit 1

tcd=$1
tdir=$2
out=`basename "$tdir"`.tar.gz

cmd="tar cvf - -C `sq $tcd` `sq $tdir` | gzip"
echo "$cmd"
ssh user@host "$cmd" > "$out"

Hint: when in doubt, run (openssh) ssh with -v option and search for 'debug1: Sending command' string in the output.

Monday, July 30, 2012

Gmake Acrobatics

Lets start with obvious. Suppose you have in your Makefile several variables:

DB_HOST := 127.0.0.1
DB_PORT := 5432
DB_USER := joe
DB_NAME := test

Variable values come from some configuration file outside of this Makefile. There is no point of replication such information & holding it in 2 places (config & Makefile). So you start thinking like this: "I'll just read my config file from my Makefile and assign variables dynamically. That's easy."

Suppose the config is in json format. Using handy jsontool we can write:

  DB_HOST := $(shell json db.host < myconfig.json)  

Okay. But with this approach we need to execute jsontool every time for each variable. For n variable this will be exactly n forks. Suddenly every task in your Makefile becomes a little (or not a little) sluggish.

It is possible, of course, to execute jsontool only once and get a newline separated 'list' of all values:

$ json db.host db.port db.user db.name < myconfig.json
127.0.0.1
5432
joe
test

But how do you map those into Makefile variables?

In every other language this would be very simple: iterate over a list of variable names; for each name, construct a string var := value and feed it to eval function. Fot example, in lovely CoffeeScript:

values = ['a', 'b']
MyEval "#{v} := #{values[count++]}" for v,count in ['DB_HOST', 'DB_PORT']  

Try to translate this into gmake code & you will struggle badly. gmake can iterate on a string, splitting it with spaces. It has eval function which can parse & evaluate its makefile language. It even has some simple helper functions for manipulating strings, for example $(word 2,this is nice) would return the word 'is'.

What is doesn't have is basic arithmetic support. You can't add 1 + 1 in it without executing a shell script or whatever.

Googling may bring up this link to you, which is hilarious in its very own way but has a great idea: if we need a simple counter, we can start it with an empty string (yes, string), call gmake function $(words $(string)) which will return 0. Then we concatenate the string with another string containing a space & a char (for example, ' x'), call function $(words $(string)) again & it will return 1. And so on.

This is what I ended with:

# Create a batch of variables on-the-fly.
# _left contains variable names, _right--their corresponding values.
_left := DB_NAME DB_USER DB_HOST DB_PORT
_right := $(shell json db_name db.user db.host db.port < myconfig.json)
_n := 1
define _dvars
$(i) := $$(word $$(words $$(_n)),$$(_right))
_n := $$(_n) x
endef
$(foreach i,$(_left),$(eval $(_dvars)))

It works but looks ugly. Those define...endif construction is just a way to define a variable that contains newlines. eval function evaluates it twice for every iteration. This is why we need $$ in front of every dynamic construction except of $(i) parameter.

Hint: user Rake & don't waste your time.

Monday, June 18, 2012

On-the-fly Generator of Preferences Pages for Opera Extensions

If you've ever tried to write an Opera extension, then you probably have stumbled upon a process of handling preferences for your extensions.

When a user clinks 'Preferences' in an extension menu button, Opera reads options.html file from the installed extension. What goes to that options.html is up to the developer. Nothing prevents him to display a lolcat video instead of html forms.

The process of writing options.html if everything except creative--it's the same boring crap over & over again for every new extension. I don't get why you even have to do this--Opera could have an API to help automatically generate preferences pages like it have it internally for the browser (opera:config). But there isn't API for this & nobody pushes for it.

So image you're writing in a declarative way what preferences your extension needs & the browser is drawing GUI elements according to your specification. Not code, just a declaration.

If you agree to this approach & don't want to waste your time on a dumb & repetitive staff, see weakspec on-the fly generator. You'll probably like it.

Friday, April 13, 2012

How To Disable Rack Logging in Sinatra

To completely & finally turn the annoying Rack logging off, simple 'set :logging, nil' doesn't help. Instead, insert this monkey patch at the beginning of your Sinatra application:

# Disable useless rack logger completely! Yay, yay!
module Rack
  class CommonLogger
    def call(env)
      # do nothing
      @app.call(env)
    end
  end
end

Custom RDoc's Darkfish Templates

RDoc 3.12 allows us to specify a template for a formatter. Formatter can be 'ri' or such that emits html. The later is called 'darkfish' in RDoc.

The problem with darkfish is that albeit it contains a quite nice navigation, it hurts my eyes:

https://lh5.googleusercontent.com/-g62JInQnNmc/T4dJdslbgQI/AAAAAAAAAXE/jZY55_VNhoo/s800/rdoc-template.png

Dark grey on light grey! Very artistic choice, of course. I believe it's very possible to invent even worse combination, like red on green, but I still don't get how anybody can like the absence of a contrast.

Anyway, here is a solution: another template for darkfish. (Not another formatter.)

RDoc allows that if you install another template as a gem, because it looks for templates only in rdoc/generator/template directory in Ruby's $LOAD_PATH.

What if you want to generate alternate looking html from a particular Rakefile without messing up with system gems?

  1. Copy the original template to some editable place, for example:

    % cp /usr/[...]/1.9/gems/rdoc-3.12/lib/rdoc/generator/template/darkfish \
    /home/alex/Desktop/lightfish
    

    'lightfish' is out new template in this example.

  2. Edit lightfish/rdoc.css to remove ugly colors, fonts, etc.

  3. Add a small monkey patch to your project's Rakefile:

    class RDoc::Options
      def template_dir_for template
        '/home/alex/Desktop/' + template
      end
    end
    
    RDoc::Task.new('html') do |i|
      i.template = 'lightfish'
      i.main = 'README.rdoc'
      i.rdoc_files = FileList['doc/*', 'lib/**/*.rb', '*.rb']
    end
    

    template_dir_for() function is a key to succsess.

  4. Run rake html. RDoc must not complain about 'could not find template lightfish'.

But there is even simpler method with $LOAD_PATH. Make rdoc/generator/template directory somewhere, for example in the project's root directory. Move in it a modified template from steps 1-2 above and just run (assuming rake's target for generating documentation is still called 'html'):

% rake -I . html

Friday, January 27, 2012

Rubygems rdoc spec exclude & rdoc task exclude

One more or less popular error in gemspec:

spec = Gem::Specification.new {|i|
  [...]

  i.rdoc_options << '-m' << 'doc/README.rdoc' << '-x' << 'lib/**/templates/**/*'
  i.extra_rdoc_files = FileList['doc/*']

  [...]
}

In this example a pattern after -x option is invalid. rdoc internally constructs an Regexp object from argument to -x option:

  • If you supply a string 'foo' it will end up as /foo/ argument to a Regexp.new.
  • If you have several -x options like -x foo -x bar, the argument will be /foo|bar/.

(At first rdoc constructs an array from all -x options and then converts it into 1 regexp.)

Now, 'lib/**/templates/**/*' is obviously a bogus regexp and rdoc will loudly complain about it during gem installation. [1] How did it appear in the spec in the first place?

A developer just copied a string from RDoc task which might look like:

RDoc::Task.new('html') do |i|
      i.main = "doc/README.rdoc"
      i.rdoc_files = FileList['doc/*', 'lib/**/*.rb']
      i.rdoc_files.exclude 'lib/**/templates/**/*'
end

This rake task works as intended: 'lib/**/templates/**/*' parameter is a valid one because i.rdoc_files is a Rake::FileList object and exclude method of that object expects such kind of patterns and doesn't understand regexps.

So, don't mix up those patterns it the spec and in the RDoc task itself.

[1]The right one would be something like 'lib/.+/templates/'.

Friday, December 23, 2011

Molloy Problem

Molloy problem is a quest of figuring out a way to 'consume' 16 stones from 4 pockets. Each step must take a unique stone, so that all 16 stones will be processed. An example of valid sequences (stones are numbered from 1 to 16):

[5, 12, 16, 15, 8, 4, 10, 2, 1, 9, 6, 13, 14, 11, 7, 3]
[16, 8, 1, 15, 13, 9, 2, 5, 11, 7, 10, 14, 4, 3, 6, 12]

Invalid sequences:

[11, 3, 8, 13, 9, 9, 8, 11, 2, 10, 12, 4, 4, 2, 2, 15]
[4, 7, 2, 6, 5, 7, 5, 16, 13, 8, 1, 16, 14, 9, 11, 2]

Using any type of external memory such as keeping a list of already 'consumed' stones is forbidden.

Some background. The quest came from 'Molloy' novel by Samuel Beckett. The scene of Molloy on a seaside is considered as a classic one in some quite boring and useless art circles. You can read the English translation of the relevant part of the novel online. Go read, it's just several pages.

At the beginning, Molloy divided 16 stones in 4 groups (by the number of undamaged pockets he had), where each group contained exactly 4 stones:

http://gromnitsky.users.sourceforge.net/articles/molloy-problem/p1.svg

While he was sucking a stone from pocket say #1, he was moving 1 stone from pocket say #2 to pocket #1, then 1 stone from pocket #3 to pocket #2, then 1 stone from pocket #4 to pocket #3. After finishing with the stone in his mouth, Molloy would put it to pocket #4 so that all pockets would contain exactly 4 stones before the next iteration.

Such arrangement caused a problem for him: there was no guarantee that every time he took the different stone:

'... by an extraordinary hazard, the 4 stones circulating thus might always be the same 4. In which case, far from sucking the 16 turn and turn about, I was really only sucking 4, always the same, turn and turn about.'

At this point I thought that the quest can be used as an interview question.

It took some time for Molloy to solve the problem, so any decent non-poser developer can achieve the same result. If the interviewee behaves arrogant, force him to write the solution in the code, for example, give him a ready abstract class which he would extend and override 1 method of reshuffling the stones.

(The example in Ruby is here. If the interviewee still behaves arrogant, ask him why (& if) the story with abstract class looks foreign in Ruby.)

Later on Molloy realized that 4 stones in 4 pockets is a red herring that kept him from the solution. So he redistributes 16 stones in 3 groups by 6, 5, 5 stones correspondingly, leaving 1 pocket empty, and finally constructs the algorithm:

http://gromnitsky.users.sourceforge.net/articles/molloy-problem/p2.svg
  1. Take a stone from pocket #1, suck it and place in pocket #4.
  2. Do it until pocket #1 becomes empty.
  3. Take a stone from pocket #2, suck it and place in pocket #1.
  4. Do it until pocket #2 becomes empty.
  5. Take a stone from pocket #3, suck it and place in pocket #2.
  6. Do it until pocket #3 becomes empty.
  7. Take a stone from pocket #4, suck it and place in pocket #3.
  8. Do it until pocket #4 becomes empty.

Which, of course, doesn't guarantee unique sequences but does guarantee that in every iteration each stone would not be left behind.

Thursday, September 1, 2011

FreeBSD 8.2, open-vm-tools and VMware Workstation

(A note for russian-speaking dudes: поцаны, прежде чем писать мне письма мелким почерком "у меня ни работаит шарные папки" или храбро скачивать х.з. какую версию порта откуда, откройте для себя 'vmware' тэг в левой колонке. Я верю что вы можете. На русский этот потс мне переводить лень, звиняйте панове.)

A custom port of open-vm-tools-2011.08.21-471295 for FreeBSD 8.2 can be obtained by typing:

% git clone https://github.com/gromnitsky/open-vm-tools-minimum.git

The port contains only a minimum version of VMware guest tools. It doesn't include kernel modules, hgfs client and wrappers for vmtoolsd.

Why?

  • The 'shared folders' option needs a guest support for vmblock file system and a hgfs kernel module. If one tries to say

    # mount -t vmhgfs .host:/shared-folder /mnt/hgfs
    

    He may get a kernel panic in FreeBSD 8.2. So, no shared folders for Jakucha.

  • vmblock is also required by drag&drop function provided by a vmusr/libdndcp.so plugin for vmtoolsd. Despite my attempts to repeat the struggle in 7.2, I couldn't achieve the same results with this version of open-vm-tools. So, no drag&drop and vmblock (fuse or .ko version) is useless.

  • I don't see a point of having external vmxnet driver instead of working em(4). And vmmemctl is like a furniture in the loft.

What have we in the so called minimum version?

  • Time sync.
  • Copy/paste under X.
  • VIX support.

The difference from previous versions:

  • vmware-user was removed and completely replaced by plugins for vmtoolsd utility.
  • GTK program vmware-toolbox was removed in favor of console version vmware-toolbox-cmd.
  • Unity plugin was excluded. It is too boring to explain why.

Installation

Delete all previous installations of open-vm-tools-minumum or open-vm-tools. This is mandatory, not optional.

After gitclonning cd to the open-vm-tools-minumum directory and decide: do you need X support for your virtual machine or it is just a console server? If the second variant is true, type:

# make WITHOUT_X11=1 install clean

otherwise

# make install clean

Then add to /etc/rc.conf line:

vmware_vmtoolsd_vmsvc_enable=YES

and type:

# /usr/local/etc/rc.d/vmware_vmtoolsd_vmsvc start

OK, now you have time sync and VIX.

If you've installed full variant with X support add this line to your ~/.xinitrc:

vmtoolsd -n vmusr &

(Don't miss the ampersand.)

Now if you start X (if X is already running type previous command in a xterm) you'll get copy/paste function between host and FreeBSD guest.

VIX Tests

The good news is: VIX works with FreeBSD guests and doens't require those kernel modules that were cutted.

To test VIX, we will use vmrun program (it comes with modern versions of Workstation). In Windows hosts it usually sit in C:\Program Files\VMware\VMware VIX directory.

Get a list of all running virtual machines:

>vmrun list
Total running VMs: 2
D:\vm\FreeBSD Stable\FreeBSD Stable.vmx
D:\vm\FreeBSD test\FreeBSD test.vmx

Get a list of all running processed in a virtual machine (it requires a name & a password of a particular user in the guest):

>vmrun -T ws -gu bob -gp asecretpass listProcessesInGuest \
 "D:\vm\FreeBSD test\FreeBSD test.vmx"
Process list: 50
pid=77251, owner=bob, cmd=/usr/local/bin/vmtoolsd -n vmsvc
pid=60007, owner=bob, cmd=/bin/csh
[...]

If vmrun hands for a long time there is a problem with vmtoolsd and its plugins in the guest. Check if vmtoolsd is running:

% ps -ax | grep vmtoolsd
  823  ??  S      1:02.33 /usr/local/bin/vmtoolsd -n vmsvc

And note the '-n vmsvc' option. Look into /var/log/messages file.

Something more interesting: copy a file from the host to the guest. This doesn't require any 'shared folders' or hgfs kernel modules. It works even if a network in the guest is down:

>vmrun -T ws -gu bob -gp asecretpass CopyFileFromHostToGuest \
      "D:\vm\FreeBSD test\FreeBSD test.vmx" d:\1.jpg "/tmp/1.jpg"

Cool, eh?

Cooking FreeBSD & Xorg under VMware Workstation 7.1

(The text below is for users who are new to configuring FreeBSD under VMware Workstation.)

Modern versions of Workstation automatically turn on emulation of Intel PRO/1000 network card if you choose 'FreeBSD' as an operating system while creating a new virtual machine. FreeBSD recognizes that device as em0. If it doesn't, turn off the virtual machine, close Workstation and insert ethernet0.virtualDev = "e1000" line into your .vmx file.

A long time ago mouse and video drivers were distributed only with a proprietry version of vmvare-tools. Today (it's like 4 years now) they are included with xorg and exist in FreeBSD ports collection. Install x11-drivers/xf86-video-vmware and x11-drivers/xf86-input-vmmouse ports.

The mouse configuring may be tricky. By default VMware Workstation emulates your mouse a ps/2 one with 5 buttons, disregarding if it a usual USB mouse on the host or a touchpad. You can force Workstation to exclusively grab the HID device (USB mouse) but then it will dissapear from the host. (VMware guest tools for MS Windows ship a special ps/2 driver which supports 6 & 7 mouse buttons (binded to back & forward in browsers) but I don't know any for FreeBSD.)

If you need mouse in syscons & X simultaneously, do not use moused option '-3' to emulate middle button for 2-buttons touchpad because you'll have problems with double click in X.

Xorg vmmouse driver (12.6.9) supports only 2 options (after Protocol & Device): Buttons and ZAxisMapping. Setting Buttons option to '7' won't bring you working 6 & 7 mouse buttons, though. (xev just ignores them.)

To turn on sound, type:

# kldload snd_es137x

and add to /boot/loader.conf file:

snd_es137x_load="YES"

If your laptop has the screen resolution 1280x800, add to xorg.conf section Monitor the line:

Modeline "1280x800" 70.00 1280 1312 1344 1376 800 801 804 850

Tuesday, August 30, 2011

FreeBSD 9 newfs block size and fragment size

In FreeBSD 9.0 beta1 2 new defaults for newfs(8) were introduced:

#define DFL_FRAGSIZE    4096
#define DFL_BLKSIZE     32768

Previous values (FreeBSD ≤ 8.2) were 2 times smaller. This means that by default new UFS filesystems will have 2 times less inodes.

This can be an unpleasant surprise if you want to quick install FreeBSD into a virtual machine with a small virtual hdd. For example, a quite modest setup with 4GB virtual hdd may bring you a /usr partition ~ 2.7GB. How many inodes is that?

The rough formula is:

10242s / 4f

where s is a partition size in MB and f is a magic number called fragment size. The new default is 4096 bytes (controlled by -f newfs(8) option).

So, for our example, the /usr partition will contain max 172,800 inodes. [1] Isn't that enough? (And why should I care?)

For a partitions larger than, say 6GB, you'll rarely ever bother with the word inode. But for smaller ones and such as /usr which usually holds full ports tree directory, you can put yourself into a strange situation when after a fresh FreeBSD install your /usr has ~ plenty of a free space but almost no free inodes.

Returning to our 2.7GB partition example, just after the installation and csup'ing of the ports tree, the number of files is:

# find /usr | wc -l
163114 

Or 94.4% of max possible files.

To make things worse, a new installer in FreeBSD 9.0 beta1 doesn't allow you to specify the fragment size & block size (b) values at all. The last one is important too, because the condition b/8 ≤ f ≤ b must be satisfied.

[1]After that number you'll get a dismal message from the kernel: /usr: create/symlink failed, no inodes free.

Monday, August 8, 2011

Emacs, xkb & xxkb

The song that never ends.

Every kid has its own scheme. Through the years I've picked out mine.

The prerequisites:

  1. You have tuned up xkb and know what key is your X layout switcher. (In the past I've used left Ctrl to toggle en/ru, but recently switched to capslock.)
  2. You're using xxkb as your X Window indicator of the current layout. Not from Gnome, not from KDE, etc.

We want: use capslock for emacs toggle-input-method too. We don't want to modify xorg system files or hack part of emacs written in C.

The problem is that emacs (under xorg-7.5.1, for example) ignores ISO_Next_Group completely. You cannot bind anything to the key that emits that event.

But there is a clever trick I've googled. You translate ISO_Next_Group to some unused key in emacs, for example Super-A. (Super == left win key on my machine.):

 (setf (gethash #xfe08 x-keysym-table) (aref (kbd "s-a") 0)) 

#xfe08 is ISO_Next_Group code. Then bind Super-A to toggle emacs keyboard layout:

 (global-set-key (kbd "s-a") '(lambda () (toggle-input-method))) 

OK. Next we need somehow disable system X switcher for all emacs windows. For xxkb this is done by adding this to its configuration file:

 XXkb.app_list.wm_class_class.alt_group1: Emacs 

And that's all.

As a bonus, I've added another very handy indicator of the current input method in emacs: cursor color.

;; default cursor color for all X frames
(add-to-list 'default-frame-alist '(cursor-color . "black"))

;; toggle the input method and the cursor color in one place
(global-set-key (kbd "s-a") '(lambda ()
                             (interactive)
                             (toggle-input-method)
                             (if window-system
                                 (set-cursor-color
                                  (if current-input-method
                                      "red3"
                                    "black")))
                             ))

Friday, August 5, 2011

Why pkg_version or portmaster -L Are Slow

Long time no see.

If you ever wondered why (in FreeBSD) any program that prints installed packages vs. available updates from the Ports is so freaking slow, then I have an answer for you and a maybe even a solution.

tl;dr: install pkg_noisrev gem. [1]

Why it is So Freaking Slow?

Just grabbing the installed list is simple: you read /var/db/pkg directory and you are done. The interesting part is how to check this data with the Ports tree.

Every correctly installed package records its origin in /var/db/pkg/package-name-1.2.3/+CONTENTS file. An origin is a relative path to the /usr/ports directory, for example for zip-3.0 package, the origin is archivers/zip.

Having that we can theoretically read corresponding Makefile (/usr/ports/archivers/zip/Makefile in our example) and compute the version number of the particular port. The problem is that 'the version' is a string that can containg 3 components (3 different Makefile varibles): port version, revision and epoch. Somethimes there is no port version but exists so called vedor version. Sometimes Makefile doesn't containt any version information at all but include (via a bsd make .include directive) another Makefile that can include another and so on.

So, to extract that information you need either:

  • Properly parse Makefile and recursively expand all its variables, read all includes, etc, i.e. write your own mini make utility.
  • Run "make -V PKGVERSION" command in the port directory.

You can guess what path was chosen by authors of the system pkg_version program or famous portmaster manager.

Think: run make for every package name; if you have 2,000 packages installed, make will run exactly 2,000 times.

To make thing worse, this is not the end of The Problem. Next quiz after obtaining the version number is how to compare 2 versions: the installed one and one from the Ports tree. They are not just simple numbers as in lovery rubygems. For example, what is newer: 4.13a or 4.13.20110529_1? Is there is a difference between 0.3.9.p1.20080208_7 and 0.3.9-pre1.20080208_7?

The system pkg_version utility contains a tedious comparation aloritm (/usr/src/usr.sbin/pkg_install/lib/version.c), reproduction of which is very boring. [2] So boring, that portmaster just calls "pkg_version -t v1 v2" to compare a pair of version number strings. Yes, if you have 2,000 packages installed, portmaster will execute make program 2,000 times + 2,000 times pkg_version program.

The last bit of slowness of such applications as pkg_version or portmaster is an iterative model. They read the whole packages list and process items one after another with 0 attempts to do things in parallel.

Can we do all that faster?

Yes, we can. A simple pkg_noisrev utility does that 4-5 times faster.

It tries to do a primitive parsing of Makefiles and if that fails only then executes make. It ships with the comparator extracted from pkg_version as a shared library that can be loaded once via Ruby dllopen method. It creates several threads and does things in parallel.

So, if you were running "portmaster -L" in the past, run "pkg_noisrev --likeportmaster" now.

[1]It requires Ruby 1.9.2.
[2]And, I dare to say, unsafe, because pkg_version doesn't have any tests you can reuse, so you can easily come up with some nasty bugs in your implementation.

Thursday, May 26, 2011

The Best of edw519

The famous book from one HN user can be read in 1-2 days (you can safely skip first 2 chapters.)

I've counted the number of interesting (to me) posts in the book: 57 of 256, or ~22.27%. Not bad.

The most hilarious chapter was #9.