gish

Gish
====

Gish is a library and command-line utility for hashing files and directories. It
will provide you with a consistent hash that will not change unless the
underlying files change.

Gish is designed to produce identical output to git's object system. That is,
git hash-object myfile and gish myfile should produce identical output. And
gish mydirectory should produce an identical object to the git tree of the
same directory. (There is no git command to do this for arbitrary directories,
but you can do something like git show -s --format=%T HEAD to show a directory
that's already been checked in).

To install as a command-line tool, just npm install -g gish. You can also
require() it from nodejs.

Libraries and helper functions
------------------------------

Bluebird is optional, but it's faster than node core Promises.

crypto = require 'crypto'
fs = require 'fs'
path = require 'path'
Promise = require 'bluebird'

We promisify all our fs calls. These functions assume only one argument because
that's true for our purposes and it's faster than using varargs.

promisify = (fn) -> (arg) ->
new Promise (resolve, reject) ->
fn arg, (err, result) ->
if err then reject err else resolve result

stat = promisify fs.lstat
readdir = promisify fs.readdir
readlink = promisify fs.readlink

Standard Promisey memoise function. setInterval isn't such a great cache expiry
function but it works well enough.

memo = (f) ->
cache = {}
setInterval((-> cache = {}), 1000).unref()
(arg) -> if result = cache[arg] then result else cache[arg] = f(arg)

We call stat a lot, so it makes sense to memoise it and save on syscalls.

stat = memo stat

Limit a function to max simultaneous pending Promises. If we don't do this we
run out of file descriptors.

limit = (max, f) ->
n = 0
queue = []
dec = (x) -> n--; queue.pop()?(); x

(arg) ->
n++
if n <= max
f(arg).then(dec)
else
(new Promise (resolve, reject) -> queue.push resolve)
.then -> f(arg).then(dec)

Basic hashing functions
-----------------------

hashFile just performs a standard sha1 on the file contents, but it has to
write the git blob header first.

hashFile = limit 100, (file) ->
stat(file).then (stats) ->
readStream = fs.createReadStream file
readStream.on 'error', (e) -> throw e
hash = crypto.createHash 'sha1'
hash.on 'error', (e) -> throw e

hash.write "blob #{stats.size}\0"
readStream.pipe hash

new Promise (resolve, reject) ->
hash.on 'finish', -> resolve hash.read()

hashLink works basically the same as hashFile. Because symlinks are small we
can just read it into memory.

hashLink = limit 100, (file) ->
readlink(file).then (link) ->
buf = new Buffer link
hash = crypto.createHash 'sha1'
hash.write "blob #{buf.length}\0"
hash.write buf
hash.end()
hash.read()

Tree hashing
------------

Hashing a tree is somewhat complex. Git trees are a list of tree entries that
look like this:

100644 foo.txt\0HASH

The first part is the file mode + some extra git bits indicating whether it's a
file, directory or symlink. Then comes the filename terminated with a NUL, then
the hash as binary data.

Git only supports mode 644 or 755, so we only support mode 644 or 655.

MODES =
file: 0b1000 << 12 | 0o644
file_x: 0b1000 << 12 | 0o755
dir: 0b0100 << 12
link: 0b1010 << 12

EXECUTABLE = 0o100

treeEntry generates one line of the git tree.

treeEntry = (dir, name) ->
file = path.join dir, name
hash = hashAnything file
fmt = stat(file)
.then (stats) ->
if stats.isDirectory() then 'dir'
else if stats.isSymbolicLink() then 'link'
else if stats.isFile()
if stats.mode & EXECUTABLE then 'file_x' else 'file'
else
throw new Error "unhashable file: #{file}"

.then (mode) ->
buf = new Buffer "#{MODES[mode].toString(8)} #{name}\0", 'utf8'

Promise.all([fmt, hash]).then Buffer.concat

git doesn't sort like other people sort. It basically adds a slash to the end of
every directory before sorting. I think it does this so that the sorting stays
stable when files and directories with the same name are present (not possible
for us, but it could happen when comparing different trees).

watSort = (dir) -> (files) ->
Promise.all files.map (file) ->
stat(path.join(dir, file)).then (stats) ->
if stats.isDirectory()
file + '/'
else
file
.then (files) ->
files.sort().map (x) -> x.replace /\/$/, ''

git ignores empty directories, so we make a special exception that we can send
up the Promise chain and filter out when we're building subdirectories.

class EmptyDirectoryError extends Error
name: 'EmptyDirectoryError'
constructor: ->

hashTree is the holy grail: it gives us the (recursive) hash of a directory
tree by joining together and hashing all the tree entries.

We ignore .git directories because who wants to hash their git directory?

hashTree = limit 100, (dir) ->
readdir dir
.then watSort(dir)
.then (files) ->
files = files.filter((x) -> x isnt '.git')
if files.length is 0
throw new EmptyDirectoryError "can't hash an empty directory"

files.map (name) ->
treeEntry dir, name
.catch (e) ->
throw e unless e instanceof EmptyDirectoryError
null

.then Promise.all.bind(Promise)

.then (entries) ->
size = 0
size += e.length for e in entries when e
hash = crypto.createHash 'sha1'
hash.write "tree #{size}\0"
hash.write entry for entry in entries when entry
hash.end()
hash.read()

hashAnything is a convenience function that stats the file and delegates to the
appropriate specialised hashing function.

hashAnything = (file) ->
stat(file).then (stats) ->
if stats.isDirectory() then hashTree file
else if stats.isSymbolicLink() then hashLink file
else if stats.isFile() then hashFile file
else throw new Error "unhashable file: #{file}"

It's also our main export. But we provide the others too under gish.hashTree
etc.

module.exports = hashAnything
hashAnything[k] = v for k, v of {hashTree, hashLink, hashFile, treeEntry}