Friday, July 25, 2014

Nix pill 3: enter the environment

Welcome to the third Nix pill. In the previous second pill we have installed Nix on our running system. Now we can finally play with it a little, things also apply to NixOS users.

Enter the environment


In the previous pill we created a nix user, so let's start by switching user with su - nix. If your ~/.profile got evaluated, then you should now be able to run commands like nix-env and nix-store.
If that's not the case:
$ source ~/.nix-profile/etc/profile.d/nix.sh


I remind you, ~/.nix-profile/etc points to the nix-1.7 derivation. At this point, we are in our nix user profile.


Install something


Finally something practical! Installation in the nix environment is an interesting process. Let's install nix-repl, a simple command line tool for playing with the Nix language. Yes, Nix is a pure, lazy, functional language, not only a set of tools to manage derivations.

Back to the installation:
$ nix-env -i nix-repl

installing `nix-repl-1.7-1734e8a'
these paths will be fetched (18.61 MiB download, 69.53 MiB unpacked):
[...]
building path(s) `/nix/store/f01lfzbw7n0yzhsjd33xfj77li9raljv-user-environment'
created 24 symlinks in user environment
Now you can run nix-repl. Things to notice:
  • We did install software as user, only for the nix user.
  • It created a new user environment. That's a new generation of our nix user profile.
  • The nix-env tool manages environments, profiles and their generations.
  • We installed nix-repl by derivation name minus the version. I repeat: we did specify the derivation name (minus the version) to install.
We can list generations without walking through the /nix hierarchy:
$ nix-env --list-generations
   1   2014-07-24 09:23:30   
   2   2014-07-25 08:45:01   (current)
List installed derivations:
$ nix-env -q
nix-1.7
nix-repl-1.7-1734e8a
So, where did nix-repl really got installed? which nix-repl is ~/.nix-profile/bin/nix-repl which points to the store.
We can also list the derivation paths with nix-env -q --out-path . So that's how those derivation paths are called: the output of a build.

Path merging


At this point you sure have the necessity to run "man". Even if you already have man system-wide outside of the nix environment, you can install and use it within nix with nix-env -i man. As usual, a new generation will be created, and ~/.nix-profile will point to it.
Let's inspect the profile a bit:
$ ls -l ~/.nix-profile/
dr-xr-xr-x 2 nix nix 4096 Jan  1  1970 bin
lrwxrwxrwx 1 nix nix   55 Jan  1  1970 etc -> /nix/store/clnpynyac3hx3a6z5lsy893p7b4rwnyf-nix-1.7/etc
[...]
Now that's interesting. When only nix-1.7 was installed, bin/ was a symlink to nix-1.7. Now it's a real directory, no symlink.
$ ls -l ~/.nix-profile/bin/
[...]
man -> /nix/store/83cn9ing5sc6644h50dqzzfxcs07r2jn-man-1.6g/bin/man
[...]
nix-env -> /nix/store/clnpynyac3hx3a6z5lsy893p7b4rwnyf-nix-1.7/bin/nix-env
[...]
nix-repl -> /nix/store/0fcl92chxbbs8axb994rg12vxddg1ivs-nix-repl-1.7-1734e8a/bin/nix-repl
[...]
All clear. nix-env merged the paths from the installed derivations. which man points to the nix profile, rather than the system man, because ~/.nix-profile/bin is at the head of $PATH.

Rollback / switch generation


The last command installed "man". We should be at generation #3, unless you changed something in the middle. Let's say we want to rollback to the old generation:
$ nix-env --rollback
switching from generation 3 to 2
Now nix-env -q does not list "man" anymore. ls -l `which man` should now be your system installed one.
Enough with the joke, let's go back to the last generation:
$ nix-env -G 3
switching from generation 2 to 3
I invite you to read the manpage of nix-env. nix-env requires an operation to perform, then there are common options for all operations, and there are options specific to an operation.

You can of course also delete and upgrade packages.

Querying the store


So far we learned how to query and manipulate the environment. But all of the environment components point to the store.
To query and manipulate the store, there's the nix-store command. We can do neat things, but we'll only see some queries for now.

Show direct runtime dependencies of nix-repl:
$ nix-store -q --references `which nix-repl`
/nix/store/94n64qy99ja0vgbkf675nyk39g9b978n-glibc-2.19
/nix/store/8jm0wksask7cpf85miyakihyfch1y21q-gcc-4.8.3
/nix/store/25lg5iqy68k25hdv17yac72kcnwlh4lm-boehm-gc-7.2d
/nix/store/g21di262aql6xskx15z3qiw3zh3wmjlb-nix-1.7
/nix/store/jxs2k83npdin18ysnd104xm4sy29m8xp-readline-6.2
The argument to nix-store can be anything as long as it points to the nix store. It will follow symlinks.
It may not make sense for you right now, but let's print reverse dependencies of nix-repl:
$ nix-store -q --referrers `which nix-repl`
/nix/store/8rj57vahlndqwg4q095x5qvfa1g4rmvr-env-manifest.nix
/nix/store/9c8ak2h7c6vbr9kqk8i2n96bwg55br7y-env-manifest.nix
/nix/store/dr1y2saask2k4y2wrmxw443302pp02z2-user-environment
/nix/store/f01lfzbw7n0yzhsjd33xfj77li9raljv-user-environment
Did you expect it? Our environments depend upon nix-repl. Yes, the environments are in the store, and since there are symlinks to nix-repl, therefore the environment depends upon nix-repl.
It lists two environments, generation 2 and generation 3.

The manifest.nix file contains metadata about the environment, such as which derivations are installed. So that nix-env can list them, upgrade or remove them. Guess what, the current manifest.nix can be found in ~/.nix-profile/manifest.nix.

Closures


The closure of a derivation is the list of all dependencies, recursively, down to the bare minimum necessary to use that derivation.
$ nix-store -qR `which man`
[...]

Copying all those derivations to the nix store of another machine makes you able to run "man" out of the box on that other machine. That's the base of nix deployment, you can already foresee the potential when deploying software in the cloud (hint: nix-copy-closure and nix-store --export).

A nicer view of the closure:
$ nix-store -qR --tree `which man`
[...]

With the above command, you can know exactly why a runtime dependency, being it direct or indirect, has been picked for a given derivation.

Same applies to environments of course. As an exercise run nix-store -qR --tree ~/.nix-profile , see that the first children are direct dependencies of the user environment: the installed derivations, and the manifest.nix.

Dependency resolution


There isn't anything like apt which solves a SAT problem in order to satisfy dependencies with lower and upper bounds on versions. Because there's no need. A derivation X depends on derivation Y, always.

Fancy disrupt


$ nix-env -e '*'
uninstalling `man-1.6g'
uninstalling `nix-repl-1.7-1734e8a'
uninstalling `nix-1.7'
[...]

Ops, that uninstalled all derivations from the environment, including nix. We are not able to run nix-env, what now?
Environments are a convenience for the user, but Nix is still there, in the store!

First pick one nix-1.7 derivation: ls /nix/store/*nix-1.7, say /nix/store/g21di262aql6xskx15z3qiw3zh3wmjlb-nix-1.7.

The first possibility is to rollback:
$ /nix/store/g21di262aql6xskx15z3qiw3zh3wmjlb-nix-1.7/bin/nix-env --rollback

The second possibility is to install nix, thus creating a new generation:
$ /nix/store/g21di262aql6xskx15z3qiw3zh3wmjlb-nix-1.7/bin/nix-env -i /nix/store/g21di262aql6xskx15z3qiw3zh3wmjlb-nix-1.7

Channels


So where are we getting packages from? We said something already in pill 2. There's a list of channels from which we get packages, usually we use a single channel. The tool to manage channels is nix-channel.
$ nix-channel --list
nixpkgs http://nixos.org/channels/nixpkgs-unstable

That's basically the contents of ~/.nix-channels. Note: ~/.nix-channels is not a symlink to the nix store!

To update the channel run nix-channel --update . It will download the new nix expressions (descriptions of the packages), create a new generation of the channels profile and unpack under ~/.nix-defexpr/channels .
That's much similar to apt-get update.

Conclusion


We learned how to query the user environment and to manipulate it by installing and uninstalling software. Upgrading software is as straight as it gets by reading the manual (nix-env -u '*' will upgrade all packages in the environment).
Everytime we change the environment, a new generation gets created. Switching between generations is easy and immediate.

Then we queried the store. We inspected the dependencies and reverse dependencies of store paths.
We still see symlinks to compose paths from the nix store, our lovely trick.

Quick analogy with programming languages. You have the heap with all the objects, that's the nix store. You have objects that point to other objects, those are the derivations. Will be this the right path?

Next pill


...we will learn the basics of the Nix language. The Nix language is used to describe how to build derivations, and it's the base for everything else including NixOS. Therefore it's very important to understand the syntax and the semantics.

To be notified about the new pill, stay tuned on #NixPills, follow @lethalman or subscribe to the nixpills rss.

Thursday, July 24, 2014

Nix pill 2: install on your running system

Welcome to the second Nix pill. In the first pill we briefly described Nix.
Now we'll install Nix on our running system and understand what changed in our system after the installation.

Nix installation is as easy as installing any other package. It will not revolutionize our system, it will stay in its own place out of our way.

Download


You can grab the last stable tarball (nix 1.7 during this writing) or the package for your distro here: http://hydra.nixos.org/release/nix/nix-1.7 .
At the time you are reading, there may be nix 1.8. You can see a list of releases here: http://hydra.nixos.org/project/nix#tabs-releases .

I prefer using the precompiled binaries, because it's a nice self-contained environment, just works and it's a little less invasive (in that it does not install anything under /etc or /usr). So in this series I will use the nix bootstrap distribution.
In the download page above you can find binaries for linux i686, x86_64 and darwin.

Note: if you are using a rolling distribution however, I suggest not to install the package (for example on Debian sid) because you will experience broken perl dependencies when running nix tools.

Installation


To ensure we don't mess with the system, you could create a custom user to let him own the Nix store, let's call it "nix".

As root:
# adduser nix
# mkdir -m 0755 /nix && chown nix /nix
From now on, all the operations we do on the shell are done from this nix user:
# su - nix
$ tar -xf nix-1.7-x86_64-linux.tar.bz2
$ cd nix-1.7-x86_64-linux
$ ./install

My pills are not a simple tutorial, there's are several articles out there to learn the basics of nix and unix. We'll instead walk through the nix system to understand the fundamentals.

First thing to note: those stuff in nix store refer to software in nix store itself. It doesn't use libc from our system or whatelse. It's a self-contained nix bootstrap.

Quick note: in a normal installation, the store is owned by root and multiple users can install and build software through a nix daemon.

So small nix store


Start inspecting the output of the install command:
copying Nix to /nix/store..........................

Effectively, that's right the /nix/store we were talking in the first pill. The contents is the strictly necessary software to bootstrap a Nix system. You can see bash, core utils, the toolchain, perl libraries, sqlite and nix itself with its own tools and libnix.
You surely noticed that in /nix/store not only directories are allowed, but also files, always in the form hash-name.

The holy database


Right after copying the store, the installation process initializes the database with the current information:
initialising Nix database...

Oh Nix also has a database. It's under /nix/var/nix/db. It is an sqlite database that keeps track of the dependencies between derivations.
The schema is very simple: there's a table of valid paths, mapping from auto increment integer to store path.
Then there's a dependency relation from one path to other paths.
Inspect it running /nix/store/*sqlite*/bin/sqlite3 /nix/var/nix/db/db.sqlite

Important rule: never change /nix/store manually because that wouldn't be in sync with the sqlite db, unless you know what you are doing.

The first profile


Then we discover the profile concept during the installation:
creating /home/nix/.nix-profile
installing `nix-1.7'
building path(s) `/nix/store/xxhdgml3rshn8mkaqxb86gp4r276sp9d-user-environment'
created 6 symlinks in user environment
A profile in nix is a general and very convenient concept for realizing rollbacks. Profiles are used to compose more components that are spread among multiple paths, under a new unified path. Not only, profiles are made up of multiple generations: they are versioned. Whenever you change a profile, a new generation is created.
Generations thus can be switched and rollback-ed atomatically.

Let's take a closer look at our profile:

$ ls -l ~/.nix-profile/
bin -> /nix/store/clnpynyac3hx3a6z5lsy893p7b4rwnyf-nix-1.7/bin
[...]
manifest.nix -> /nix/store/82dg18wz250vvcxjbclgyy5yg2kfz1gw-env-manifest.nix
[...]
share -> /nix/store/clnpynyac3hx3a6z5lsy893p7b4rwnyf-nix-1.7/share
That nix-1.7 derivation in the nix store is nix itself, with binaries and libraries. The installation basically reproduced the hierarchy of the nix-1.7 derivation in the profile by means of symbolic links.
The contents of this profile are special, because only one program has been installed in our profile, therefore e.g. the bin directory fully points to the only program being installed.

But that's only the contents of the latest generation of our profile. In fact, ~/.nix-profile itself is a symbolic link to /nix/var/nix/profiles/default .
In turn, that's a symlink to default-1-link in the same directory. Yes, that means it's the generation #1 of the default profile.
Finally that's a symlink to the nix store "user-environment" derivation that you saw printed during the installation process.

The manifest.nix will be meat for the next pill.

Meet nixpkgs expressions


More wild output from the installer:
downloading Nix expressions from `http://releases.nixos.org/nixpkgs/nixpkgs-14.10pre46060.a1a2851/nixexprs.tar.xz'...
unpacking channels...
created 2 symlinks in user environment
modifying /home/nix/.profile...

Nix expressions are used to describe packages and how to build them. Nixpkgs is the repository containing all these expressions: https://github.com/NixOS/nixpkgs .
The installer downloaded the package descriptions from commit a1a2851.

The second profile we meet is the channels profile. ~/.nix-defexpr/channels points to /nix/var/nix/profiles/per-user/nix/channels which points to channels-1-link which points to a nix store directory containing the downloaded nix expressions.

Channels are a set of packages and expressions available for download. Similar to debian stable and unstable, there's a stable and unstable channel. In this installation, we're tracking nixpkgs unstable.

Don't bother yet with nix expressions.

Finally, for your own convenience, it modified ~/.profile to automatically enter the nix environment. What ~/.nix-profile/etc/profile.d/nix.sh really does is simply adding ~/.nix-profile/bin to PATH and ~/.nix-defexpr/channels/nixpkgs to NIX_PATH. We'll discuss about NIX_PATH in another pill.
Read nix.sh, it's short.

FAQ: Can I change /nix to something else?


You can, but there's a strong reason to keep using /nix instead of a different directory. All the derivations depend on other derivations by absolute path. I remind you in pill 1 that bash pointed to a glibc under /nix/store.
You can see now by yourself, don't worry if you see multiple bash derivations:
$ ldd /nix/store/*bash*/bin/bash
[...]
Keeping the store in /nix means we can grab the binary cache from nixos.org (just like you grab packages from debian mirrors) otherwise:

  1. glibc would be installed under /foo/store
  2. thus bash needs to point to glibc under /foo/store
  3. the binary cache won't help, and we'd have to recompile all the stuff by ourselves
After all /nix is a cool place.

Conclusion


We've installed nix on our system, fully isolated and owned by the "nix" user as we're still diffident with this new system.
We learned some new concepts like profiles and channels. In particular, with profiles we're able to manage multiple generations of a composition of packages, while with channels we're able to download binaries from nixos.org .
The installation put everything under /nix, and some symlinks in the nix user home. That's because every user is able to install and use software in her own environment.

I hope I left nothing uncovered in a way that you think there's some kind of magic behind. It's all about putting components in the store and symlinking these components together.

Also I hope the commands in this pill were consistent with your fresh nix installation.

Next pill... 


...we will enter the nix environment and learn how to interact with the store.
Pill 3 is available for reading here.

To be notified about the new pill, stay tuned on #NixPills, follow @lethalman or subscribe to the nixpills rss.

Wednesday, July 23, 2014

Nix pill 1: why you should give it a try

Introduction

Welcome to the first post of the Nix in pills series. Nix is a purely functional package manager and deployment system for POSIX. There's a lot of documentation that describes what Nix, NixOS and related projects are.
The purpose of this post is to convince you to give Nix a try. Installing NixOS is not required, but sometimes I may refer to NixOS as a real world example of Nix usage for building a whole operating system.

Rationale of pills

The Nix manualrelated papersarticles and wiki are excellent in explaining how Nix/NixOS works, how you can use it and the amount of cools thing being done with it, however sometimes you may feel some magic happening behind the scenes hard to grasp in the beginning.
This series aims to complement the missing explanations from the more formal documents.

Follows a description of Nix. Just as pills, I'll try to be as short as possible.

Not being pure functional

Most, if not all, widely used package managers (dpkg, rpm, ...) mutate the global state of the system. If a package foo-1.0 installs a program to /usr/bin/foo, you cannot install foo-1.1 as well, unless you change the installation paths or the binary name.
Changing the installation paths means breaking the assumptions about the file system hierarchy.
Changing the binary names means breaking possible users of that binary.

Debian for example partially solves the problem with the alternatives.

So in theory it's possible with the current systems to install multiple versions of the same package, in practice it's very painful.
Let's say you need an nginx service and also an nginx-openresty service. You have to create a new package that changes all the paths with e.g. an -openresty suffix.
Or you want to run two different instances of mysql, 5.2 and 5.5. Same thing applies plus you have to also make sure the two mysqlclient libraries do not collide.

This is not impossible but very inconvenient. If you want to install two whole stack of software like GNOME 3.10 and GNOME 3.12, you can imagine the amount of work.

From an administrator view point: containers to the rescue. The solution nowadays is to create a container per service, especially when different versions are needed. That somehow solves the problem, but at a different level and with other drawbacks. Needing orchestration tools, setting up a shared cache of packages, and new wild machines to monitor rather than simple services.

From a developer view point: virtualenv for python or jhbuild for gnome or whatelse. But then, how do you mix the two stacks? How do you avoid recompiling the same thing when it could be instead be shared? Also you need to setup your development tools to point to the different directories where libraries are installed. Not only, there's the risk that some of the software incorrectly uses system libraries.

And so on. Nix solves all this at the packaging level and solves it well. A single tool to rule them all.

Being pure functional

Nix does no assumption about the global state of the system. This has many advantages, but also some drawbacks of course. The core of a Nix based system is the Nix store, usually installed under /nix/store, and some tools to manipulate the store. In Nix there's the notion of derivation rather than package. The difference might be subtle at the beginning, so I will often mix both of the words, ignore that.

Derivations/packages are stored in the nix store as follows: /nix/store/hash-name, where the hash uniquely identifies the derivation (not true, it's a little more complex than this), and name is the name of the derivation.

Let's take the bash derivation as example: /nix/store/s4zia7hhqkin1di0f187b79sa2srhv6k-bash-4.2-p45/ . It is a directory that contains bin/bash.
You get it, there's no /bin/bash, there's only that self-contained build output in the store. Same goes for coreutils and everything else. To make their usage convenient from the shell, nix will put those paths in PATH.
What we have is basically a store of all packages and different versions of them, and things in the nix store are immutable.

There's no ldconfig cache either. So where does bash find libc?
$ ldd  `which bash`
libc.so.6 => /nix/store/94n64qy99ja0vgbkf675nyk39g9b978n-glibc-2.19/lib/libc.so.6 (0x00007f0248cce000)

Turns out that when bash was built, it used that specific version of glibc and at runtime it will require exactly that glibc version.
Don't be doubtful about the version in the derivation name: it's only a name for us humans. You may end up having a different hash given the same derivation name.

What does it all mean? You could run mysql 5.2 with glibc-2.18, and mysql 5.5 with glibc-2.19. You could use your python module with python 2.7 compiled with gcc 4.6 and the same python module with python 3 compiled with gcc 4.8, all in the same system.
In other words, no dependency hell, not even a dependency resolution algorithm. Straight dependencies from derivations to other derivations.

From an administrator view point: need an old PHP version from lenny and want to upgrade to wheezy, not painful.

From a developer view point: want to develop webkit with llvm 3.4 and 3.3, not painful.

Mutable vs immutable

When upgrading a library, package managers replace it in-place. All new applications run afterwards with the new library without being recompiled. After all, they all refer dynamically to libc6.so.
While being immutable with Nix, upgrading a library like glibc means recompiling all applications, because the glibc path to the nix store is being hardcoded.

So how do we deal with security updates? In Nix we have some tricks (yet pure) to solve this problem, but that's another story.

Another problem is that unless software has in mind a pure functional model, or it can be adapted to, it's hard to compose applications at runtime.
Let's take for example firefox. You install flash, and you get it working because firefox looks in a global path for plugins.
In Nix, there's no such global path for plugins. Firefox therefore must know explicitly about the path to flash. We wrap the firefox binary to setup the necessary environment to make it find flash in the nix store. That will produce a new firefox derivation: be aware it takes a few seconds, but it made composition harder at runtime.

No upgrade/downgrade scripts for your data. It doesn't make sense with this approach, because there's no real derivation to be upgraded. With nix you switch to using another software with its own stack of dependencies, but there's no formal notion of upgrade or downgrade when doing so.
Migrating to the new data format is your own responsibility.

Conclusion

Nix lets you compose software at build time with maximum flexibility and with builds being as reproducible as possible. Not only, due to its nature deploying systems in the cloud is so easy, consistent and reliable that in the Nix world all existing self-containment and orchestration tools are deprecated by NixOps. Talking about this, no comparison with other tools is fair, nix rocks.
It however currently falls off when speaking about dynamic composition at runtime or replacing low level libraries due to massive rebuilds.

That may sound scary, however after running NixOS on both a server and a laptop desktop, I'm very satisfied so far. Some of the architectural problems just need some man power, other design problems are to be solved as a community yet.

Considering Nixpkgs (github link) is a completely new repository of all the existing software, with a completely fresh concept, and with few core developers but overall year-over-year increasing contributions, the current state is way more than acceptable and beyond the experimental stage. In other words, it's worth your investment.

Next pill...

...we will install Nix on top of your current system (I assume GNU/Linux, but we also have OSX users) and start inspecting the installed stuff.
Pill 2 is available for reading here.

To be notified about the new pill, stay tuned on #NixPills, follow @lethalman or subscribe to the nixpills rss.

Wednesday, July 09, 2014

Debugging and fixing a wmctrl bug in NixOS

Without wmctrl I'm lost. I use it together with xbindkeys so that pressing a combination of keys will raise a window of the desktop (editor, shell, browser, chat, ...).

It turns out however that in NixOS wmctrl didn't work well. I had 3 windows opened, and wmctrl -l only showed one. Since gnome3 is still young in nixos, the first thought was that mutter did something wrong when returning the list of clients, due to some possible packaging mistake.

However, xprop -root correctly listed 3 window ids for the _NET_CLIENT_LIST atom, so mutter did its job.

Therefore it might be a problem of wmctrl. I'm always sure in these cases Debian has a patch, however I wanted to find out by myself.

Let's prepare an environment for hacking wmctrl:

$ nix-shell ~/nixpkgs -A wmctrl
$ unpackPhase
$ cd $sourceRoot
$ configurePhase
$ buildPhase
$ ./wmctrl -l

Ok it runs. Now let's dive into the code.
  1. Open main.c
  2. Search for _NET_CLIENT_LIST
  3. Note the for loop in list_windows function right below, it uses client_list_size / sizeof(Window) in the condition. That may be the culprit. 
  4. We make use of the most advanced debugging technique: before the for loop add a printf("%lu\n%lu\n", client_list_size, sizeof(Window));
Now let's rebuild and run wmctrl:

$ buildPhase
$ ./wmctrl -l

Bingo! client_list_size is 12 (3 windows x 4 byte) while sizeof(Window) is 8 instead of 4. Definitely a bug for 64-bit systems.
Of course Debian has the patch: http://ftp.de.debian.org/debian/pool/main/w/wmctrl/wmctrl_1.07-7.debian.tar.gz

  1. Exit the nix-shell and delete the wmctrl source directory.
  2. Copy debian/patches/01_64-bit-data.patch under ~/nixpkgs/pkgs/tools/X11/wmctrl/64-bit-data.patch.
  3. Edit ~/nixpkgs/pkgs/tools/X11/wmctrl/default and add patches = [ ./64-bit-data.patch ]; in the derivation.
  4. Finally install the patched wmctrl with nix-env ~/nixpkgs -iA wmctrl and see that wmctrl -l now works.
  5. Commit, push to nixpkgs master, profit.

Wednesday, May 21, 2014

Grep in git with emacs

I'm sure you're aware of vc-git-grep command in Emacs, but it has a downside: you must specify the file extension every time, and it's case-sensitive.
I propose you an alternative vc-git-grep2 that is case-insensitive and only requires the directory in which to start the search.

(defun vc-git-grep2 (regexp dir)
  (interactive
   (progn
     (grep-compute-defaults)
     (cond
      ((equal current-prefix-arg '(16))
       (list (read-from-minibuffer "Run: " "git grep" nil nil 'grep-history)
    nil))
      (t (let* ((regexp (grep-read-regexp))
    (dir (read-directory-name "In directory: " nil default-directory t)))
     (list regexp dir))))))
  (require 'grep)
  (when (and (stringp regexp) (> (length regexp) 0))
    (let ((command regexp))
      (if (> 4 5)
    (if (string= command "git grep")
     (setq command nil))
  (setq dir (file-name-as-directory (expand-file-name dir)))
  (setq command
     (grep-expand-template "git grep -n -i -e <R>" regexp))
  (when command
    (if (equal current-prefix-arg '(4))
     (setq command
     (read-from-minibuffer "Confirm: " command nil nil 'grep-history))
   (add-to-history 'grep-history command))))
      (when command
  (let ((default-directory dir)
     (compilation-environment '("PAGER=")))
    ;; Setting process-setup-function makes exit-message-function work
    ;; even when async processes aren't supported.
    (compilation-start command 'grep-mode))
  (if (eq next-error-last-buffer (current-buffer))
   (setq default-directory dir))))))
 
Plus I suggest you to add the following to your .emacs. Install find-file-in-git-repo and add the following: (require 'find-file-in-git-repo) (global-set-key (kbd "C-x f") 'find-file-in-git-repo) Then bind our new vc-git-grep2: (global-set-key (kbd "C-x s") 'vc-git-grep2) Finally, because some modes don't use the common C-c C-c to comment/uncomment regions: (global-set-key (kbd "C-c C-") 'comment-or-uncomment-region)

Sunday, March 23, 2014

Gtk3 hit-a-hint: mouseless navigation module

I present gtkhah, a gtk module for hit-a-hint mouseless navigation of gtk3 applications.
It's been inspired by the various hit-a-hint browser extensions.
Usage at the project homepage. Here's a quick screenshot of Gedit:


Monday, January 20, 2014

Intersection test and optimal allocation of 2D axis-aligned boxes using linear programming

Either-or trick
In this solution, we will make use of the either-or trick. The constraints in a program are all in and, but we want some of them to be in or.
Consider the following logic formula: \(a\ge b\vee c\ge d\). It can be written with the following and constraints: \[ \begin{alignedat}{2}\, & M\cdot x\; & +a\; & \ge b\\ \, & M\cdot\left(1-x\right)\; & +c\; & \ge d\\ \, & \, & x\; & \in\left\{ 0,1\right\} \end{alignedat} \] where \(M \gt 0\) is big (depending on the specific context as we'll see later).
When \(x=0\), then \(a \ge b\) must hold, while the second constraint is always satisfied. When \(x=1\), then \(c \ge d\) must hold, while the first constraint is always satisfied.
In other words, either one of the two constraint must hold for a given value of \(x\). If neither do, then the original or formula is not satisfied.

Empty intersection test
Given two AABB boxes \(i,j\) at position \(x_i,y_i\) and \(x_j,y_j\) with size \(w_i,h_i\) and \(w_j,h_j\) respectively, we want to constraint our program such that their intersection is empty.
This can be expressed with the following logic formula:
\[ \left(x_{i}\ge x_{j}+w_{j}\vee x_{j}\ge x_{i}+w_{i}\right)\vee\left(y_{i}\ge y_{j}+h_{j}\vee y_{j}\ge y_{i}+h_{i}\right) \]
We can encode the above expression with 3 either-or tricks using 3 binary variables:
\[ \begin{alignedat}{3}\; & M\cdot b_{1}\; & \, & +M\cdot b_{3} & +x_{i}\; & \ge x_{j}+w_{j}\\ \; & M\cdot\left(1-b_{1}\right)\; & \, & +M\cdot b_{3} & +x_{j}\; & \ge x_{i}+w_{i}\\ \; & M\cdot b_{2}\; & \, & +M\cdot\left(1-b_{3}\right) & +y_{i}\; & \ge y_{j}+w_{j}\\ \; & M\cdot\left(1-b_{2}\right)\; & \, & +M\cdot\left(1-b_{3}\right) & +y_{j}\; & \ge y_{i}+w_{i}\\ \, & \, & \, & \; & b_{1},b_{2},b_{3}\; & \in\left\{ 0,1\right\} \end{alignedat} \] Real problem
Given a fixed area of size \((cols)\times(rows)\) and a set of boxes with fixed width \(w_i\) for each \(i=1..n\) (where \(n\) is the number of boxes), find the optimal allocation \(x_i, y_i, h_i\) for each box \(i=1..n\) such that we cover all the area and maximize the size of the boxes fairly.
To achieve fair allocation we choose to maximize the minimum height of the boxes. For example, if we had an area of size \(5\times100\), and two boxes of width \(5\) each, we prefer them to have height \(50\) and \(50\) respectively, rather than \(1\) and \(99\).

This problem can be encoded as follows: \[ max\; minh+C\cdot{\displaystyle \sum_{i=1}^{n}h_{i}} \] \[ subject\;to: \] \begin{equation} \forall i=1..n:\; minh\leq h_{i} \end{equation}
\[ \forall i=1..n-1,\, j=i+1..n: \] \begin{equation} \begin{alignedat}{3}\; & M\cdot b_{1}^{\left(ij\right)}\; & \, & +M\cdot b_{3}^{\left(ij\right)} & +x_{i}\; & \ge x_{j}+w_{j}\\ \; & M\cdot\left(1-b_{1}^{\left(ij\right)}\right)\; & \, & +M\cdot b_{3}^{\left(ij\right)} & +x_{j}\; & \ge x_{i}+w_{i}\\ \; & M\cdot b_{2}^{\left(ij\right)}\; & \, & +M\cdot\left(1-b_{3}^{\left(ij\right)}\right) & +y_{i}\; & \ge y_{j}+w_{j}\\ \; & M\cdot\left(1-b_{2}^{\left(ij\right)}\right)\; & \, & +M\cdot\left(1-b_{3}^{\left(ij\right)}\right) & +y_{j}\; & \ge y_{i}+w_{i}\\ \, & \, & \, & \; & b_{1}^{\left(ij\right)},b_{2}^{\left(ij\right)},b_{3}^{\left(ij\right)}\; & \in\left\{ 0,1\right\} \end{alignedat} \end{equation}
\[ \forall i=1..n: \] \begin{equation} \begin{alignedat}{1}x_{i}+w_{i}\; & \le cols\\ y_{i}+h_{i}\; & \leq rows\\ 0\leq x_{i}\; & \leq cols-1\\ 0\leq y_{i}\; & \leq rows-1\\ 1\leq h_{i}\; & \leq rows \end{alignedat} \end{equation} Equation \((1)\) is used to get the minimum height of the boxes together with the objective function. Equations \((2)\) ensure that the boxes do not overlap. Equations \((3)\) ensure that the boxes don't lie outside of the allocation area.
In the objective function we also add a second component, which ensures that on equal \(minh\) we chose the allocation that fills the remaining space. This component must thus be \(< 1\) to not bias the \(minh\) component.

Now, what are the values of \(M\) and \(C\)? The constant \(M\) must be big enough to make an inequality always true, so:
\begin{gather*} \forall i,j:\; M\ge x_{j}+w_{j}-x_{i}\\ M\ge\max\left\{ x_{j}+w_{j}-x_{i}\right\} \\ M\ge\max\left\{ x_{j}+w_{j}\right\} -\min\left\{ x_{i}\right\} \\ M\ge cols \end{gather*} Since it must hold also for rows, \(M\ge\max\left\{ cols,rows\right\}\). The result is very intuitive if you look at the original inequalities. We can choose a value of \(M=cols+rows\).
The constant \(C\) instead must be such that: \begin{gather*} C\cdot{\displaystyle \sum_{i=1}^{n}h_{i}}<1\\ C\cdot n\cdot\max\left\{ h_{i}\right\} <1\\ C\cdot n\cdot rows<1\\ C<\frac{1}{n\cdot rows} \end{gather*} This result is also very intuitive. We can choose \(C=\frac{1}{2\cdot n\cdot rows}\) to avoid numerical instability.

Demonstration
I've prepared a GMPL program to allocate \(10\) boxes with width \(3,4,10,7,4,8,2,9,8,5\) in an area of \(10\,cols\times100\, rows\). GLPK does not converge, so you can limit the time to 1 second (or more) in order to get a feasible but suboptimal solution.
You can visualize the result in the screenshot below of the two solutions while running for 1 second and 5 second respectively. After 60 seconds the solution didn't improve.
Please note that there is no relationship between the colors of the two tests.

image/svg+xml 1s 5s

Relaxing the integer constraint on \(x,y,h,minh\) might also give you better solutions in less time.
You can download the gist below and run it as: glpsol --tmlim 5 -m aabb_alloc.mod: