new type/pathfinding algorithm

6 files changed, 244 insertions, 28 deletions

diff --git a/mmm/mmmfs/browser.moon b/mmm/mmmfs/browser.moon
index cdeba30..f872ed9 100644
--- a/mmm/mmmfs/browser.moon
+++ b/mmm/mmmfs/browser.moon
@@ -1,9 +1,10 @@
 require = relative ..., 1
 import Key from require '.fileder'
-import converts, get_conversions, apply_conversions from require '.conversion'
+import get_conversions, apply_conversions from require '.conversion'
 import ReactiveVar, get_or_create, text, elements, tohtml from require 'mmm.component'
 import pre, div, nav, span, button, a, code, select, option from elements
 import languages from require 'mmm.highlighting'
+converts = require '.converts'
 
 keep = (var) ->
   last = var\get!
@@ -15,6 +16,7 @@ code_cast = (lang) ->
   {
     inp: "text/#{lang}.*",
     out: 'mmm/dom',
+    cost: 0
     transform: (val) => languages[lang] val
   }
 
@@ -28,6 +30,7 @@ casts = {
   {
     inp: 'URL.*'
     out: 'mmm/dom'
+    cost: 0
     transform: (href) => span a (code href), :href
   }
 }
diff --git a/mmm/mmmfs/conversion.moon b/mmm/mmmfs/conversion.moon
index 31cbf5e..4b47bba 100644
--- a/mmm/mmmfs/conversion.moon
+++ b/mmm/mmmfs/conversion.moon
@@ -1,16 +1,19 @@
 require = relative ..., 1
-converts = require '.converts'
+base_converts = require '.converts'
+import Queue from require '.queue'
 
 count = (base, pattern='->') -> select 2, base\gsub pattern, ''
 escape_pattern = (inp) -> "^#{inp\gsub '([^%w])', '%%%1'}$"
 escape_inp = (inp) -> "^#{inp\gsub '([-/])', '%%%1'}$"
 
+local print_conversions
+
 -- attempt to find a conversion path from 'have' to 'want'
 -- * have - start type string or list of type strings
 -- * want - stop type pattern
 -- * limit - limit conversion amount
 -- returns a list of conversion steps
-get_conversions = (want, have, _converts=converts, limit=5) ->
+get_conversions = (want, have, converts=base_converts, limit=5) ->
   assert have, 'need starting type(s)'
 
   if 'string' == type have
@@ -19,29 +22,55 @@ get_conversions = (want, have, _converts=converts, limit=5) ->
   assert #have > 0, 'need starting type(s) (list was empty)'
 
   want = escape_pattern want
-  iterations = limit + math.max table.unpack [count type for type in *have]
-  have = [{ :start, rest: start, conversions: {} } for start in *have]
-
-  for i=1, iterations
-    next_have, c = {}, 1
-    for { :start, :rest, :conversions } in *have
-      if rest\match want
-        return conversions, start
+  limit = limit + 3 * math.max table.unpack [count type for type in *have]
+
+  had = {}
+  queue = Queue!
+  for start in *have
+    return {}, start if want\match start
+    queue\add { :start, rest: start, conversions: {} }, 0, start
+
+  best = Queue!
+
+  while true
+    entry, cost = queue\pop!
+    if not entry or cost > limit
+      break
+
+    { :start, :rest, :conversions } = entry
+    had[rest] = true
+    for convert in *converts
+      inp = escape_inp convert.inp
+      continue unless rest\match inp
+      result = rest\gsub inp, convert.out
+      continue unless result
+      continue if had[result]
+
+      next_entry = {
+        :start
+        rest: result
+        cost: cost + convert.cost
+        conversions: { { :convert, from: rest, to: result }, table.unpack conversions }
+      }
+
+      if result\match want
+        best\add next_entry, next_entry.cost
       else
-        for convert in *_converts
-          inp = escape_inp convert.inp
-          continue unless rest\match inp
-          result = rest\gsub inp, convert.out
-          if result
-            next_have[c] = {
-              :start,
-              rest: result,
-              conversions: { { :convert, from: rest, to: result }, table.unpack conversions }
-            }
-            c += 1
-
-    have = next_have
-    return unless #have > 0
+        queue\add next_entry, next_entry.cost, result
+
+
+  if solution = best\pop!
+    -- print "BEST: (#{solution.cost})"
+    -- print_conversions solution.conversions
+    solution.conversions, solution.start if solution
+
+-- stringify conversions for debugging
+-- * conversions - conversions from get_conversions
+print_conversions = (conversions) ->
+  print "converting:"
+  for i=#conversions,1,-1
+    step = conversions[i]
+    print "- #{step.from} -> #{step.to} (#{step.convert.cost})"
 
 -- apply transforms for conversion path sequentially
 -- * conversions - conversions from get_conversions
@@ -73,7 +102,6 @@ convert = (have, want, value, ...) ->
   apply_conversions conversions, value, ...
 
 {
-  :converts
   :get_conversions
   :apply_conversions
   :convert
diff --git a/mmm/mmmfs/converts.moon b/mmm/mmmfs/converts.moon
index 9276c33..e4a6ddf 100644
--- a/mmm/mmmfs/converts.moon
+++ b/mmm/mmmfs/converts.moon
@@ -30,6 +30,7 @@ code_hl = (lang) ->
   {
     inp: "text/#{lang}",
     out: 'mmm/dom',
+    cost: 5
     transform: (val) => pre languages[lang] val
   }
 
@@ -42,16 +43,19 @@ converts = {
   {
     inp: 'fn -> (.+)',
     out: '%1',
+    cost: 1
     transform: (val, fileder) => val fileder
   }
   {
     inp: 'mmm/component',
     out: 'mmm/dom',
+    const: 3
     transform: single tohtml
   }
   {
     inp: 'mmm/dom',
     out: 'text/html+frag',
+    cost: 3
     transform: (node) => if MODE == 'SERVER' then node else node.outerHTML
   }
   {
@@ -59,11 +63,13 @@ converts = {
     -- @TODO: this doesn't feel right... maybe mmm/dom has to go?
     inp: 'mmm/dom',
     out: 'text/html',
+    cost: 3
     transform: (html, fileder) => render html, fileder
   }
   {
     inp: 'text/html%+frag',
     out: 'mmm/dom',
+    cost: 1
     transform: if MODE == 'SERVER'
       (html, fileder) =>
         html = html\gsub '<mmm%-link%s+(.-)>(.-)</mmm%-link>', (attrs, text) ->
@@ -138,11 +144,13 @@ converts = {
   {
     inp: 'text/lua -> (.+)',
     out: '%1',
+    cost: 0.5
     transform: loadwith load or loadstring
   }
   {
     inp: 'mmm/tpl -> (.+)',
     out: '%1',
+    cost: 1
     transform: (source, fileder) =>
       source\gsub '{{(.-)}}', (expr) ->
         path, facet = expr\match '^([%w%-_%./]*)%+(.*)'
@@ -153,6 +161,7 @@ converts = {
   {
     inp: 'time/iso8601-date',
     out: 'time/unix',
+    cost: 0.5
     transform: (val) =>
       year, _, month, day = val\match '^%s*(%d%d%d%d)(%-?)([01]%d)%2([0-3]%d)%s*$'
       assert year, "failed to parse ISO 8601 date: '#{val}'"
@@ -161,6 +170,7 @@ converts = {
   {
     inp: 'URL -> twitter/tweet',
     out: 'mmm/dom',
+    cost: 1
     transform: (href) =>
       id = assert (href\match 'twitter.com/[^/]-/status/(%d*)'), "couldn't parse twitter/tweet URL: '#{href}'"
       if MODE == 'CLIENT'
@@ -176,6 +186,7 @@ converts = {
   {
     inp: 'URL -> youtube/video',
     out: 'mmm/dom',
+    cost: 1
     transform: (link) =>
       id = link\match 'youtu%.be/([^/]+)'
       id or= link\match 'youtube.com/watch.*[?&]v=([^&]+)'
@@ -196,11 +207,13 @@ converts = {
   {
     inp: 'URL -> image/.+',
     out: 'mmm/dom',
+    cost: 1
     transform: (src, fileder) => img :src
   }
   {
     inp: 'URL -> video/.+',
     out: 'mmm/dom',
+    cost: 1
     transform: (src) =>
       -- @TODO: add parsed MIME type
       video (source :src), controls: true, loop: true
@@ -208,11 +221,13 @@ converts = {
   {
     inp: 'text/plain',
     out: 'mmm/dom',
+    cost: 2
     transform: (val) => span val
   }
   {
     inp: 'alpha',
     out: 'mmm/dom',
+    cost: 2
     transform: single code
   }
   -- this one needs a higher cost
@@ -224,11 +239,13 @@ converts = {
   {
     inp: '(.+)',
     out: 'URL -> %1',
+    cost: 10
     transform: (_, fileder, key) => "#{fileder.path}/#{key.name}:#{@from}"
   }
   {
     inp: 'table',
     out: 'text/json',
+    cost: 2
     transform: do
       tojson = (obj) ->
         switch type obj
@@ -253,6 +270,7 @@ converts = {
   {
     inp: 'table',
     out: 'mmm/dom',
+    cost: 5
     transform: do
       deep_tostring = (tbl, space='') ->
         buf = space .. tostring tbl
@@ -281,18 +299,21 @@ if MODE == 'SERVER'
     table.insert converts, {
       inp: 'text/moonscript -> (.+)',
       out: '%1',
+      cost: 1
       transform: loadwith moon.load or moon.loadstring
     }
 
     table.insert converts, {
       inp: 'text/moonscript -> (.+)',
       out: 'text/lua -> %1',
+      cost: 2
       transform: single moon.to_lua
     }
 else
   table.insert converts, {
     inp: 'text/javascript -> (.+)',
     out: '%1',
+    cost: 1
     transform: (source) =>
       f = js.new window.Function, source
       f!
@@ -315,12 +336,14 @@ do
     table.insert converts, {
       inp: 'text/markdown',
       out: 'text/html+frag',
+      cost: 1
       transform: (md) => "<div class=\"markdown\">#{markdown md}</div>"
     }
 
     table.insert converts, {
       inp: 'text/markdown%+span',
       out: 'mmm/dom',
+      cost: 1
       transform: if MODE == 'SERVER'
         (source) =>
           html = markdown source
diff --git a/mmm/mmmfs/fileder.moon b/mmm/mmmfs/fileder.moon
index cf517a1..cdfc649 100644
--- a/mmm/mmmfs/fileder.moon
+++ b/mmm/mmmfs/fileder.moon
@@ -96,7 +96,7 @@ class Fileder
 
       __index: (t, k) ->
         canonical = rawget t, tostring k
-        canonical or= Key k
+        -- canonical or= Key k
         canonical
 
       __newindex: (t, k, v) ->
@@ -109,6 +109,7 @@ class Fileder
 
         -- get canonical Key instance
         k = @facet_keys[k]
+        return unless k
 
         -- if cached, return
         if v = rawget t, k
@@ -129,6 +130,7 @@ class Fileder
       __newindex: (t, k, v) ->
         -- get canonical Key instance
         k = @facet_keys[k]
+        return unless k
 
         rawset t, k, v
 
@@ -167,7 +169,9 @@ class Fileder
         @facet_keys[copy] = copy
 
     _, name = dir_base @path
-    @facets['name: alpha'] = name
+    name_key = Key 'name: alpha'
+    @facet_keys[name_key] = name_key
+    @facets[name_key] = name
 
   -- recursively walk to and return the fileder with @path == path
   -- * path - the path to walk to
@@ -255,6 +259,10 @@ class Fileder
   get: (...) =>
     want = Key ...
 
+    -- return directly if present
+    if val = @facets[want]
+      return val, want
+
     -- find matching key and shortest conversion path
     key, conversions = @find want
 
diff --git a/mmm/mmmfs/queue.moon b/mmm/mmmfs/queue.moon
new file mode 100644
index 0000000..f90d41b
--- /dev/null
+++ b/mmm/mmmfs/queue.moon
@@ -0,0 +1,66 @@
+-- a priority queue with an index
+-- only one element with a given key may exist at a time
+-- when an element with an existing key is added,
+-- the element with lower priority survives.
+class Queue
+  new: =>
+    @values = {}
+    @index = {}
+
+  -- add a value with a given priority to the queue
+  -- if no key is specified, assume the element is uniq
+  add: (value, priority, key) =>
+    entry = { :value, :key, :priority }
+
+    if key
+      if old_entry = @index[key]
+        -- already have an entry for this key
+        -- if it is lower priority, we leave it there and do nothing
+        if old_entry.priority < priority
+          return
+
+        -- otherwise we remove the old one and continue as normal
+        -- find the index of the old entry
+        local i
+        for ii, entry in ipairs @values
+          if entry == old_entry
+            i = ii
+            break
+
+        -- remove it
+        table.remove @values, i
+
+      -- store this entry in the index
+      @index[key] = entry
+
+    -- store lowest priority last
+    for i, v in ipairs @values
+      if v.priority < priority
+        -- i is the first key that is lower,
+        -- we want to insert right before it
+        table.insert @values, i, entry
+        return
+
+    -- couldn't find a key with a lower priority,
+    -- so insert at the end
+    table.insert @values, entry
+
+  peek: =>
+    entry = @values[#@values]
+    if entry
+      { :value, :priority, :key } = entry
+      @index[key] = nil if key
+      value, priority
+
+  pop: =>
+    entry = table.remove @values
+    if entry
+      { :value, :priority, :key } = entry
+      @index[key] = nil if key
+      value, priority
+
+  -- iterator, yields (value, priority), low priority first
+  poll: => @.pop, @
+{
+  :Queue
+}
diff --git a/spec/queue_spec.moon b/spec/queue_spec.moon
new file mode 100644
index 0000000..d095398
--- /dev/null
+++ b/spec/queue_spec.moon
@@ -0,0 +1,88 @@
+import Queue from require 'mmm.mmmfs.queue'
+
+describe "Queue", ->
+  it "stores things", ->
+    queue = Queue!
+    queue\add "test", 1
+    queue\add "toast", 2
+    queue\add "spice", 3
+
+    assert.is.equal "test", queue\pop!
+    assert.is.equal "toast", queue\pop!
+    assert.is.equal "spice", queue\pop!
+    assert.is.nil queue\pop!
+
+  it "doesnt care about the order", ->
+    queue = Queue!
+    queue\add "spice", 3
+    queue\add "test", 1
+    queue\add "toast", 2
+
+    assert.is.equal "test", queue\pop!
+    assert.is.equal "toast", queue\pop!
+
+    queue\add "pepper", 5
+    queue\add "salt", .5
+    assert.is.equal "salt", queue\pop!
+    assert.is.equal "spice", queue\pop!
+    assert.is.equal "pepper", queue\pop!
+
+  it "can be peeked", ->
+    queue = Queue!
+    queue\add "spice", 3
+    queue\add "test", 1
+    queue\add "toast", 2
+
+    assert.is.equal "test", queue\peek!
+    assert.is.equal "test", queue\pop!
+    queue\pop!
+
+    queue\add "pepper", 5
+    queue\add "salt", .5
+
+    assert.is.equal "salt", queue\peek!
+    queue\pop!
+    queue\pop!
+
+    assert.is.equal "pepper", queue\peek!
+    queue\pop!
+
+    assert.is.nil queue\peek!
+
+  it "keeps keys in an index", ->
+    queue = Queue!
+    queue\add "test", 1, 'test'
+    queue\add "toast", 2, 'toast'
+    queue\add "spice", 3, 'spice'
+
+    assert.is.equal "test", queue\peek!
+    queue\add "spice2", .5, 'spice'
+    assert.is.equal "spice2", queue\pop!
+    assert.is.equal "test", queue\pop!
+
+    queue\add "bad toast", 5, 'toast'
+    assert.is.equal "toast", queue\pop!
+    assert.is.nil queue\pop!
+
+  it "provides an iterator", ->
+    queue = Queue!
+    queue\add "test", 1
+    queue\add "spice", 3
+    queue\add "toast", 2
+
+    expect = {'test', 'toast', 'late', 'spice'}
+    expect_next = 1
+    report = spy.new (v, i) ->
+      assert.is.equal expect[expect_next], v
+      expect_next += 1
+
+    for value, prio in queue\poll!
+      report value, prio
+
+      if value == 'toast'
+        queue\add "late", 0.5
+
+    assert.stub(report).was.called_with('test', 1)
+    assert.stub(report).was.called_with('toast', 2)
+    assert.stub(report).was.called_with('spice', 3)
+    assert.stub(report).was.called_with('late', 0.5)