scd - smart change directory

[Pavol Juhas <pj2192@xxxxxxxxxxxx>]

Well, I just read the thread on the "cdr" function - seems
that it is indeed hard to come up with anything new.  :)

Anyway, here is the scd code.  A directory ranking is
calculated from the frequency and time of its visits,
which are recorded in the ~/.scdhistory file.
The scd function accepts one or more patterns arguments,
where all patterns must be present in the full path.
Directories that match with their tail name are preferred.
If scd argument is an existing directory or a directory
alias, scd would jump to that path.

scd can be used as autoloadable zsh function

    autoload scd
    scd p1 p2 ...

or as a zsh executable, which writes a "cd" command to a
file given by the $SCD_SCRIPT environment variable.  The later
mode should support the use of scd from other shells or from the
vim editor.

Cheers,

Pavol

PS: The .scdhistory file is loaded with awk to avoid the
    issues with truncated alternate history.

#!/bin/zsh
# $Id: scd 127 2010-07-15 16:48:32Z juhas $

emulate -L zsh

local DOC='scd -- smart change to a recently used directory
usage: scd [options] [pattern1 pattern2 ...]
Go to a directory path that contains all fixed string patterns.  Prefer
recently visited directories and directories with patterns in their tail
component.  Display a selection menu in case of multiple matches.

Options:
  -a, --add         add specified directories to the directory index
  -r, --recursive   add directoriese recursively for option --add
  -v, --verbose     display directory rank in the selection menu
  -h, --help        display this message and exit

This function adds a chpwd hook that records all visited directories.
'

local SCD_HISTFILE=~/.scdhistory
local SCD_HISTSIZE=${SCD_HISTSIZE:-5000}
local SCD_MENUSIZE=${SCD_MENUSIZE:-25}
local SCD_MEANLIFE=${SCD_MEANLIFE:-86400}
local SCD_THRESHOLD=${SCD_THRESHOLD:-0.005}
local SCD_SCRIPT=${SCD_SCRIPT:-}

local ICASE a d m p i tnow tdir maxrank threshold
local opt_help opt_recursive opt_verbose opt_add
local -A drank dalias
local dmatching

setopt nohistsavebycopy extendedhistory extendedglob warncreateglobal

# self destructive action command
scd_action() {
    if [[ $# == 1 ]]; then
        [[ -n $SCD_SCRIPT ]] && (umask 077;
            print -r "cd ${(q)1}" >| $SCD_SCRIPT)
        cd $1
    fi
    unfunction scd_action
}

# define chpwd hook
if [[ -o interactive && ${+functions[scd_chpwd_hook]} == 0 ]]; then
    scd_chpwd_hook()  { scd --add -- $PWD }
    autoload add-zsh-hook
    add-zsh-hook chpwd scd_chpwd_hook
fi

# process command line options
zmodload -i zsh/zutil
zparseopts -D -- h=opt_help -help=opt_help \
    a=opt_add -add=opt_add \
    r=opt_recursive -recursive=opt_recursive \
    v=opt_verbose -verbose=opt_verbose || return $?

if [[ -n $opt_help ]]; then
    print $DOC
    return
fi

# define custom history file
fc -a -p $SCD_HISTFILE $SCD_HISTSIZE

if [[ -n $opt_add || -n $opt_recursive ]]; then
    for a in ${*:-.}; do
	if [[ ! -d $a ]]; then
	    print -u 2 "Directory $a does not exist"
	    return 2
	fi
	d=$(unfunction -m scd_chpwd_hook; cd $a; pwd)
	print -rs -- $d
	if [[ -n $opt_recursive ]]; then
	    print -n "scanning ${d} ... "
	    m=( ${d}/**/*(/N) )
	    [[ ${#m} == 0 ]] || print -rsl -- $m
	    print "[done]"
	fi
    done
    return
fi

# wipe out the script file
[[ -n $SCD_SCRIPT ]] && /bin/rm -f -- $SCD_SCRIPT

# take care of existing directories
if  [[ $# == 1 && -d $1 ]]; then
    scd_action $1
    return $?
# take care of exact aliases
elif  [[ $# == 1 ]] && d=${$(hash -d -m "(#s)$1")#${1}=} && [[ -d $d ]]; then
    scd_action $d
    return $?
fi

[[ "$*" == *[[:upper:]]* ]] || ICASE='(#i)'

# calculate rank for all directories in the history
tnow=${(%):-"%D{%s}"}
drank=( ${(f)"$(
    tail -${SCD_HISTSIZE} $SCD_HISTFILE |
    awk -v tnow=$tnow -v meanlife=$SCD_MEANLIFE '
        BEGIN { FS = "[:;]"; }
        {   pi = 0.01 + exp(1.0 * ($2 - tnow) / meanlife);
            sub(/^[^;]*;/, "");
            p[$0] += pi;
        }
        END { for (di in p)  { print di; print p[di]; } }'
    )"}
)

for a; do
    p=${ICASE}"*${a}*"
    drank=( ${(kv)drank[(I)${~p}]} )
done

# build matching directories sorted by rank
dmatching=( ${(f)"$( for d p in ${(kv)drank}; do print -r -- "$p $d"; done |
    sort -grk1 | cut -d ' ' -f 2- )"} )

# reduce to exact matches
# patterns follow each other
p=${ICASE}"*${(j:*:)argv}*"
m=( ${(M)dmatching:#${~p}} )
[[ -d ${m[1]} ]] && dmatching=( $m )
# last pattern is in the path tail
p=${ICASE}"*${(j:*:)argv}[^/]#"
m=( ${(M)dmatching:#${~p}} )
[[ -d ${m[1]} ]] && dmatching=( $m )
# all patterns are present in the path tail
m=( $dmatching )
for a; do
    p=${ICASE}"*/[^/]#${a}[^/]#"
    m=( ${(M)m:#${~p}} )
done
[[ -d ${m[1]} ]] && dmatching=( $m )
# all patterns are in the path tail
p=${ICASE}"/*${(j:[^/]#:)argv}[^/]#"
m=( ${(M)dmatching:#${~p}} )
[[ -d ${m[1]} ]] && dmatching=( $m )

# do not match $HOME or $PWD when run without arguments
if [[ $# == 0 ]]; then
    dmatching=( ${dmatching:#(${HOME}|${PWD})} )
fi

# cut dmatching to $SCD_MENUSIZE existing directories
m=( )
for d in $dmatching; do
    [[ ${#m} == $SCD_MENUSIZE ]] && break
    [[ -d $d ]] && m+=$d
done
dmatching=( $m )

# find out maximum rank
maxrank=0.0
for d in $dmatching; do
    [[ ${drank[$d]} -lt maxrank ]] || maxrank=${drank[$d]}
done

# cut out directories below rank threshold
threshold=$(( maxrank * SCD_THRESHOLD ))
dmatching=( ${(f)"$(
    for d in ${dmatching}; do
        (( ${drank[$d]} > threshold )) && print -r -- $d
    done)"}
)
dmatching=( $dmatching )

case ${#dmatching} in
(0)
    print -u2 "no matching directory"
    return 1
    ;;
(1)
    scd_action $dmatching
    return $?
    ;;
(*)
    m=( ${(f)"$(unfunction -m scd_chpwd_hook;
            for d in ${dmatching}; do
                cd $d
                [[ -n $opt_verbose ]] && printf "%.3g " ${drank[$d]}
                print -P "%~"
            done)"} )
    for i in {1..${#m}}; dalias[${m[i]}]=$dmatching[i]
    select d in ${m}; do
        scd_action ${dalias[$d]}
        return $?
    done
esac