Source

depresso / depresso.coffee

Full commit
_ = require 'underscore'
_s = require 'underscore.string'
assert = require 'assert'
spahql = require 'spahql'
clone = require 'clone'
InternalDepGraph = require 'dep-graph'

# Concepts:
#  - path: A unique string
#  - expression: A string that can be resolved to one or more paths
#  - path resolution: Generation of paths from an expression
#  - dependency: A description how a path can be given a value
#    (resolution), and what paths it needs as a prerequisite.

repeat = (n, obj) ->
  result = []
  if n > 0
    _(n).times -> result.push obj
  result

assoc = (dict, key, value) ->
  result = if _.isEmpty dict then dict else _.clone dict
  result[key] = value
  result

# Hide spahql internals and issues
class Db
  constructor: (objOrDb) ->
    if objOrDb
      if objOrDb.data
        @_db = objOrDb
      else
        @_data = objOrDb
    else
      @empty = yes

  db: ->
    unless @_db
      @_db = spahql.db @_data
    @_db

  data: ->
    if @empty
      null
    else
      unless @_data
        @_data @_db.data
      @_data

  uniquePaths: (absPath) ->
    paths = @db().select absPath.asString()
    # fix spahql weirdness
    _(paths).map (p) ->
      new UniquePath(if _.isString p then p else p.path)

  update: (paths, defValue=null) ->
    db = @
    for p in paths
      loc = p.asString().indexOf '*'
      if loc isnt -1
        leading = p.asString()[..loc]
        restPath = new Path p.asString()[loc+2..]
        for up in new Path(leading).uniquePaths db
          db = up.join(restPath).toUnique().updateObject db, defValue
      else
        db = p.toUnique().updateObject db, defValue
    db

  singleValue: (up) ->
    parentValue = @db().select(up.parent().asString()).value()
    last = _.last up.asArray()
    parentValue[last]

  value: (path) ->
    s = path.asString()
    result = @db().select(s)
    if _.isEmpty result
      undefined
    else
      # Fix that falsey values are all returned as undefined
      result = _(result).map (x) =>
        if _.isString x
          @singleValue new UniquePath x
        else
          x.value
      if s.indexOf('//') is -1 and s.indexOf('*') is -1
        result = result[0]
      result

  setValue: (up, value) ->
    arr = up.asArray()
    if arr.length is 1
      result = new Db assoc(@data(), arr[0], value)
    else if arr.length > 1
      data = @data()[arr[0]]
      child = new Db(data).setValue new UniquePath(arr[1..]), value
      result = new Db assoc(@data(), arr[0], child.data())
    else
      throw new Error "Cannot set '#{value}' at root"
    result
    
class DepGraph
  constructor: (map, parent=null) ->
    @map = if parent then parent.map else {}
    @map = _(@map).defaults map

  resolutionOrder: (uniquePaths) ->
    unless @_dg
      @_dg = new InternalDepGraph
      @_dg.map = @map
    result = []
    for up in uniquePaths
      pathStr = up.asString()
      for required in @_dg.getChain pathStr
        unless required in result
          result.push required
      unless pathStr in result
        result.push pathStr
    _(result).map (s) -> new UniquePath s

class Dependency
  constructor: (dict) ->
    @target = new Path dict.target
    @depends = {}
    for name, str of dict.depends
      @depends[name] = new Path str
    @context = dict.context
    @calculate = dict.calculate

  depGraph: (db) ->
    result = {}
    for targetUPath in @target.uniquePaths db
      dependPathStrings = {}
      for dependPath in _.values @depends
        absDependPath = targetUPath.join dependPath
        for uniqueDependPath in absDependPath.uniquePaths db
          dependPathStrings[uniqueDependPath.asString()] = yes
      result[targetUPath.asString()] = dependPathStrings
    for k,v of result
      result[k] = _.keys v
    new DepGraph result

  @fullDepGraph: (db, deps) ->
    fun = (depGraph, dep) ->
      new DepGraph dep.depGraph(db).map, depGraph
    _(deps).reduce fun, new DepGraph {} 

  calculateValue: (db, upTarget) ->
    context = {}
    for name,depends of @depends
      context[name] = db.value upTarget.join(depends)
    if @context
      _.extend context, @context
    @calculate.call context

class Path
  constructor: (@pathStr) ->

  asString: ->
    @pathStr

  toUnique: ->
    if @asString().indexOf('//') isnt -1 or @asString().indexOf('*') isnt -1
      throw new TypeError "Path #{@asString()} is not unique"
    else
      new UniquePath @asString()

  uniquePaths: (db, refPath=null) ->
    refPath or= new UniquePath []
    absPath = refPath.join @
    db.uniquePaths absPath

  @distinctUniquePaths: (db, paths) ->
    result = {}
    for p in paths
      for up in p.uniquePaths db
        result[up.asString()] = yes
    _(result).keys().map (s) -> new UniquePath s

class UniquePath
  constructor: (strOrArray) ->
    if _.isString strOrArray
      @pathStr = strOrArray
    else if _.isArray strOrArray
      @pathArr = strOrArray
    else throw new TypeError strOrArray

  asString: ->
    unless @pathStr
      @pathStr = '/' + @pathArr.join '/'
    @pathStr

  asArray: ->
    unless @pathArr
      @pathArr = _(@pathStr.split('/')[1..]).map (x) ->
        num = parseInt x
        if _.isFinite num then num else x
    @pathArr

  isRoot: ->
    _.isEmpty @asArray()

  @PATH_PREFIXES =
    '/': (uniqPath, otherPath) ->
      new UniquePath([]).join otherPath
    '../': (uniqPath, otherPath) ->
      new UniquePath(uniqPath.asArray()[..-2]).join otherPath
    './': (uniqPath, otherPath) ->
      uniqPath.join otherPath
    '</': (uniqPath, otherPath) ->
      idx = _.last uniqPath.asArray()
      if _.isFinite idx
        new UniquePath(uniqPath.asArray()[..-2].concat([idx - 1])).join otherPath
      else
        throw new TypeError "Expected number as index, got #{uniqPath}"

  parent: ->
    new UniquePath(@asArray()[..-2])

  join: (otherPath) ->
    result = null
    exp = otherPath.asString()
    if @isRoot()
      result = new Path "/#{exp}"
    else
      for start, fun of UniquePath.PATH_PREFIXES
        if _s.startsWith exp, start
          result = fun @, new Path exp[start.length..]
      unless result
        result = new Path "#{@asString()}/#{exp}"
    result

  makeObject: (defValue=null) ->
    if @isRoot()
      new Db defValue
    else
      children = new UniquePath(@asArray()[1..]).makeObject(defValue).data()
      current = @asArray()[0]
      if _.isFinite current
        # An index of n requires at least n+1 elements
        new Db(repeat current + 1, children)
      else
        new Db(assoc {}, current, children)

  updateObject: (db, defValue=null) ->
    obj = db.data()
    result = null
    if @isRoot()
      result = db 
    else
      current = @asArray()[0]
      rest = @asArray()[1..]
      if _.isFinite current
        assert.ok _.isArray(obj), "Expected array at #{@asString()}, got #{obj}"
        missing = current - obj.length + 1
        if missing > 0
          child = new UniquePath(rest).makeObject(defValue).data()
          result = new Db(obj.concat repeat missing, child)
        else
          child = new UniquePath(rest).updateObject(new Db(obj[current]), defValue)
          result = new Db(assoc obj, current, child.data())
      else if current is '*'
        keys = if _.isArray obj then [0..obj.length-1] else _.keys obj
        fun = (db, idx) ->
          up = new UniquePath [idx].concat(rest)
          up.updateObject db, defValue
        _([0..obj.length-1]).reduce fun, db
        result = keys.reduce fun, db
      else
        assert.ok _.isObject(obj), "Expected object at #{@asString()}, got #{obj}"
        child = null
        if _.isUndefined obj[current]
          child = new UniquePath(rest).makeObject defValue
        else
          child = new UniquePath(rest).updateObject new Db(obj[current]), defValue
        result = new Db(assoc obj, current, child.data())
    #console.log 'updateObject', @asString(), '\n\t', obj, '\n\t', result.data()
    result

@resolve = (data, depDicts, wantedExpressions) ->
  db = new Db data
  wantedPaths = _(wantedExpressions).map (x) -> new Path x
  db = db.update wantedPaths # add placeholders
  wantedUPs = Path.distinctUniquePaths db, wantedPaths
  deps = _(depDicts).map (x) -> new Dependency x
  depGraph = Dependency.fullDepGraph db, deps
  pathStrToDep = {}
  for dep in deps
    for up in dep.target.uniquePaths db
      unless pathStrToDep[up.asString()]
        pathStrToDep[up.asString()] = dep
  sortedUPs = depGraph.resolutionOrder wantedUPs
  fun = (db, up) ->
    current = db.value up
    #console.log 'current', up, current
    if _.isNull(current) or _.isUndefined(current)
      dep = pathStrToDep[up.asString()]
      value = dep.calculateValue db, up
      result = db.setValue up, value
      #console.log 'value', value
      result
    else
      db
  db = _(sortedUPs).reduce fun, db
  db.data()

@testing =
  Db: Db
  Dependency: Dependency
  DepGraph: DepGraph
  Path: Path
  UniquePath: UniquePath
  repeat: repeat
  assoc: assoc
  withData: (assert, fun, data) ->
    for d in data
      msg = d.msg or "#{d.in}"
      input = d.in
      unless _.isArray input
        input = [input]
      got = null
      try
        got = fun.apply @, input
      catch e
        #throw e
        got = e.toString()
      assert.deepEqual d.out, got, msg
    assert.done()