chris blogs

January 2017

02jan2017 · zz: a smart and efficient directory changer

A nice feature I’ve become used to in the last year is a so-called “smart directory changer” that keeps track of the directories you change into, and then lets you jump to popular ones quickly, using fragments of the path to find the right location.

There is quite some prior art in this, such as autojump, fasd or z, but I could not resist building my own implementation of it, optimized for zsh.

As far as I can see, my zz directory changer is the only one with a “pay-as-you-go” performance impact, i.e., not every directory change is slowed down, but only every use of the smart matching functonality.

The idea is pretty easy: we add a chpwd hook to zsh to keep track of directory changes, and log for each change a line looking like “0 $epochtime 1 $path” into a file ~/.zz. This is an operation with effectively constant cost on a Unix system.

chpwd_zz() {
  print -P '0\t%D{%s}\t1\t%~' >>~/.zz
chpwd_functions=( ${(kM)functions:#chpwd?*} )

The actual jumping function is called zz:

zz() {

How does the matching work? It’s an adaption of the z algorithm: The lines of ~/.zz are tallied by directory and last-used time stamp, so for example the lines

0 1483225200 1 ~/src
0 1483225201 1 ~/tmp
0 1483225202 1 ~/src
0 1483225203 1 ~/tmp
0 1483225204 1 ~/src

would turn into

6 1483225204 3 ~/src
4 1483225203 2 ~/tmp

Also, the initial number, the effective score of the directory, is computed: We take the relative age of the directory (that is, seconds since we went there), and boost or dampen the results: the frequency is multiplied by 4 for directories not older than 1 hour, doubled for directories we went into today, halved for directories we went into this week, and divided by 4 else.

  awk -v ${(%):-now=%D{%s}} <~/.zz '
    function r(t,f) {
      age = now - t
      return (age<3600) ? f*4 : (age<86400) ? f*2 : (age<604800) ? f/2 : f/4
    { f[$4]+=$3; if ($2>l[$4]) l[$4]=$2 }
    END { for(i in f) printf("%d\t%d\t%d\t%s\n",r(l[i],f[i]),l[i],f[i],i) }' |

By design, this tallied file can be appended again with new lines originating from chpwd, and recomputed whenever needed.

The output of this tally is then sorted by age, truncated to 9000 lines, then sorted by score. (My ~/.zz is only 350 lines, however.)

      sort -k2 -n -r | sed 9000q | sort -n -r -o ~/.zz

With this precomputed tally (which is generated in linear time), finding the best match is easy. It is the first string that matches all arguments:

  if (( $# )); then
    local p=$(awk 'NR != FNR { exit }  # exit after first file argument
                   { for (i = 3; i < ARGC; i++) if ($4 !~ ARGV[i]) next
                     print $4; exit }' ~/.zz ~/.zz "$@")

If nothing was found, we bail with exit code 1. If zz is used interactively, it changes into the best match, else the best match is just printed. This allows using things like cp foo.mkv $(zz mov).

    [[ $p ]] || return 1
    local op=print
    [[ -t 1 ]] && op=cd
    if [[ -d ${~p} ]]; then
      $op ${~p}

If we found a directory that doesn’t exist anymore, we clean up the ~/.zz file, and try it all over.

      # clean nonexisting paths and retry
      while read -r line; do
        [[ -d ${~${line#*$'\t'*$'\t'*$'\t'}} ]] && print -r $line
      done <~/.zz | sort -n -r -o ~/.zz
      zz "$@"

With no arguments, zz simply prints the top ten directories.

    sed 10q ~/.zz

I actually shortcut zz to z and add a leading space to not store z calls into history:

alias z=' zz'

The full code (possibly updated) can be found as usual in my .zshrc.

I use lots of shell hacks, but zz definitely is among my most successful ones.

NP: Leonard Cohen—Leaving The Table

Copyright © 2004–2016