a hyperdrive inspired data structure for storing FS changes to a log of events.

tree-on-list.js

/*
0 - [foo]         [[0][]]        time      - Add empty folder /foo
1 - [foo,hello]   [[1][1]]       time meta - Add file /foo/hello
2 - [foo,goodbye] [[2][1,2]]     time meta - Add file /foo/goodbye
3 - [foo,man]     [[3][1,2,3][]] time      - Add empty folder /foo/man
4 - [bar,baz]     [[3,4][4]]     time meta - Add file /bar/baz
5 - [bar,bit]     [[3,5][4,5]]   time meta - Add file /bar/bit
6 - [foo,hello]   [[5,6][2,3]]   time      - Delete /foo/hello

To stat /bar/baz

- Read 6, see it's path only overlaps to "/", so start walking root list [5,6],
  but excluding already walked 6
- Read 5, see it overlaps to "/bar/", so start walking "/bar" list [4,5],
  but exclusing already walked 5
- Read 4, see it's an exact match, return meta

To readTree "/foo"

- Read 6, see it has dir entry for "foo", walk list [2,3] to get listing
- Read 2, see it adds file "goodbye" with meta
- Read 3, see it adds empty folder "man"
- return "goodbye" and "man" as listing

To remove "/foo"

- Read 6, see it has entry for "foo"
- Write new entry removing reference to self, but copying other parents.

*/

exports.putFile = putFile
function putFile (log, path, meta) {
  // console.log('putFile', path)
  let parts = splitPath(path)
  let indexes = newIndexes(log, parts)
  log.push([parts, indexes, Date.now(), meta])
}

exports.putTree = putTree
function putTree (log, path) {
  // console.log('putTree', path)
  let parts = splitPath(path)
  let indexes = newIndexes(log, parts)
  indexes.push([])
  log.push([parts, indexes, Date.now()])
}

exports.remove = remove
function remove (log, path) {
  console.log('Remove', path)
  let parts = splitPath(path)
  let indexes = newIndexes(log, parts)
  let last = indexes[parts.length - 1]
  if (last) last.splice(last.indexOf(log.length), 1)
  log.push([parts, indexes, Date.now()])
}

exports.stat = stat
function stat (log, path) {
  console.log('stat', path)
  let parts = splitPath(path)
  let index = find(log, parts)
  if (index < 0) return
  let entry = log[index]
  let time = entry[2]
  let type = entry[1].length > parts.length ? 'tree' : 'file'
  let props = {type, time}
  let meta = entry[3]
  if (type === 'tree') {
    // For trees, we add custom metadata that is number of children as "entries"
    props.entries = entry[1][parts.length].length
  } else {
    // If meta is undefined, this was a deleted file
    if (!meta) return
    // For files, we just mixin the metadata object.
    for (let key in meta) {
      props[key] = meta[key]
    }
  }
  return props
}

exports.readTree = readTree
function readTree (log, path, depth) {
  console.log('readTree', path, depth)
  let parts = splitPath(path)
  let index = find(log, parts)
  if (index < 0) return
  let entry = log[index]
  let list = entry[1][parts.length]
  if (!list) return
  return buildTree(log, list, parts.length, depth)
}

function splitPath (path) {
  return path.split('/').filter(Boolean)
}

// Given a list of path segments, return the index for each segment's data
function indexPath (log, parts) {
  /* eslint no-labels: ["error", { "allowLoop": true }] */
  let indexes = []
  let index = log.length - 1
  let matchIndex = 0
  if (index >= 0) {
    indexes.push(index)
    outer: while (matchIndex < parts.length) {
      let list = log[index][1][matchIndex]
      if (!list) break
      for (let idx of list) {
        if (log[idx][0][matchIndex] === parts[matchIndex]) {
          indexes.push(idx)
          index = idx
          matchIndex++
          continue outer
        }
      }
      break
    }
  }
  return indexes
}

function find (log, parts) {
  let idxs = indexPath(log, parts)
  return (idxs.length === parts.length + 1) ? idxs[idxs.length - 1] : -1
}

function newIndexes (log, parts) {
  let nextIndex = log.length
  let idxs = indexPath(log, parts)

  let indexes = []
  for (let i = 0; i < parts.length; i++) {
    let part = parts[i]
    let idx = idxs[i]
    let list
    let entry = log[idx]
    list = entry && entry[1][i].slice(0) || []
    let found = false
    for (let j = 0; j < list.length; j++) {
      if (log[list[j]][0][i] === part) {
        list[j] = nextIndex
        found = true
      }
    }
    if (!found) {
      list.push(nextIndex)
    }
    indexes[i] = list
  }
  return indexes
}

function buildTree (log, list, matchIndex, depth) {
  let tree = {}
  for (let idx of list) {
    let entry = log[idx]
    let name = entry[0][matchIndex]
    let children = entry[1][matchIndex + 1]
    let type = children ? 'tree' : 'file'
    let time = entry[2]
    let props = {type, time}
    if (type === 'file') {
      let meta = entry[3]
      for (let key in meta) {
        props[key] = meta[key]
      }
    } else {
      props.entries = children.length
      if (depth) {
        props.children = buildTree(log, children, matchIndex + 1, depth - 1)
      }
    }
    tree[name] = props
  }
  return tree
}