Allow using ooo (out-of-order message replication)

5 files changed, 148 insertions, 26 deletions

diff --git a/README.md b/README.md
index 288e229..6d59e18 100644
--- a/README.md
+++ b/README.md
@@ -74,6 +74,7 @@ To make config options persistent, set them in `~/.ssb/config`, e.g.:
     "filter": "all",
     "showPrivates": true,
     "previewVotes": true,
+    "ooo": true,
   }
 }
 ```
@@ -91,6 +92,7 @@ To make config options persistent, set them in `~/.ssb/config`, e.g.:
 - `filter`: Filter setting. `"all"` to show all messages. `"invert"` to show messages that would be hidden by the default setting. Otherwise the default setting applies, which is so to only show messages authored or upvoted by yourself or by a feed that you you follow. Exceptions are that if you navigate to a user feed page, you will see messages authored by that feed, and if you navigate to a message page, you will see that message - regardless of the filter setting. The `filter` setting may also be specified per-request as a query string parameter.
 - `showPrivates`: Whether or not to show private messages. Default is `true`. Overridden by `filter=all`.
 - `previewVotes`: Whether to preview creating votes/likes/digs (`true`) or publish them immediately (`false`). default: `false`
+- `ooo`: if true, use `ssb-ooo` to try to fetch missing messages in threads. also can set per-request with query string `?ooo=1`. default: `false`
 
 ## TODO
 
diff --git a/lib/app.js b/lib/app.js
index 4789e11..81f58f5 100644
--- a/lib/app.js
+++ b/lib/app.js
@@ -32,6 +32,7 @@ function App(sbot, config) {
   this.msgFilter = conf.filter
   this.showPrivates = conf.showPrivates == null ? true : conf.showPrivates
   this.previewVotes = conf.previewVotes == null ? false : conf.previewVotes
+  this.useOoo = conf.ooo == null ? false : conf.ooo
 
   var base = conf.base || '/'
   this.opts = {
@@ -44,7 +45,11 @@ function App(sbot, config) {
 
   sbot.get = memo({cache: lru(100)}, sbot.get)
   this.about = new About(this, sbot.id)
-  this.getMsg = memo({cache: lru(100)}, getMsgWithValue, sbot)
+  this.msgCache = lru(100)
+  this.getMsg = memo({cache: this.msgCache}, getMsgWithValue, sbot)
+  this.getMsgOoo = sbot.ooo
+    ? memo({cache: this.msgCache}, sbot.ooo.get)
+    : function (id, cb) { cb(new Error('missing ssb-ooo plugin')) }
   this.getAbout = memo({cache: this.aboutCache = lru(500)},
     this._getAbout.bind(this))
   this.unboxContent = memo({cache: lru(100)}, sbot.private.unbox)
@@ -179,6 +184,14 @@ App.prototype.getMsgDecrypted = function (key, cb) {
   })
 }
 
+App.prototype.getMsgDecryptedOoo = function (key, cb) {
+  var self = this
+  this.getMsgOoo(key, function (err, msg) {
+    if (err) return cb(err)
+    self.unboxMsg(msg, cb)
+  })
+}
+
 App.prototype.publish = function (content, cb) {
   var self = this
   function tryPublish(triesLeft) {
@@ -333,6 +346,16 @@ function getMsgWithValue(sbot, id, cb) {
   })
 }
 
+function getMsgOooWithValueCreate(sbot) {
+  if (!sbot.ooo) {
+    var err = new Error('missing ssb-ooo plugin')
+    return function (id, cb) {
+      cb(null, err)
+    }
+  }
+  return sbot.ooo.get
+}
+
 App.prototype._getAbout = function (id, cb) {
   var self = this
   if (!u.isRef(id)) return cb(null, {})
@@ -805,3 +828,85 @@ App.prototype.getIdeaTitle = function (id, cb) {
     })
   )
 }
+
+function traverse(obj, emit) {
+  emit(obj)
+  if (obj !== null && typeof obj === 'object') {
+    for (var k in obj) {
+      traverse(obj[k], emit)
+    }
+  }
+}
+
+App.prototype.expandOoo = function (opts, cb) {
+  var self = this
+  var dest = opts.dest
+  var msgs = opts.msgs
+  if (!Array.isArray(msgs)) return cb(new TypeError('msgs should be array'))
+
+  // algorithm:
+  // traverse all links in the initial message set.
+  // find linked-to messages not in the set.
+  // fetch those messages.
+  // if one links to the dest, add it to the set
+  // and look for more missing links to fetch.
+  // done when no more links to fetch
+
+  var msgsO = {}
+  var getting = {}
+  var waiting = 0
+
+  function checkDone() {
+    if (waiting) return
+    var msgs = Object.keys(msgsO).map(function (key) {
+      return msgsO[key]
+    })
+    cb(null, msgs)
+  }
+
+  function getMsg(id) {
+    if (msgsO[id] || getting[id]) return
+    getting[id] = true
+    waiting++
+    self.getMsgDecryptedOoo(id, function (err, msg) {
+      waiting--
+      if (err) console.trace(err)
+      else gotMsg(msg)
+      checkDone()
+    })
+  }
+
+  var links = {}
+  function addLink(id) {
+    if (typeof id === 'string' && id[0] === '%' && u.isRef(id)) {
+      links[id] = true
+    }
+  }
+
+  msgs.forEach(function (msg) {
+    if (msgs[msg.key]) return
+    if (msg.value.content === false) return // missing root
+    msgsO[msg.key] = msg
+    traverse(msg, addLink)
+  })
+  waiting++
+  for (var id in links) {
+    getMsg(id)
+  }
+  waiting--
+  checkDone()
+
+  function gotMsg(msg) {
+    if (msgsO[msg.key]) return
+    var links = []
+    var linkedToDest = msg.key === dest
+    traverse(msg, function (id) {
+      if (id === dest) linkedToDest = true
+      links.push(id)
+    })
+    if (linkedToDest) {
+      msgsO[msg.key] = msg
+      links.forEach(addLink)
+    }
+  }
+}
diff --git a/lib/render-msg.js b/lib/render-msg.js
index 92ad260..3b498e0 100644
--- a/lib/render-msg.js
+++ b/lib/render-msg.js
@@ -811,7 +811,10 @@ RenderMsg.prototype.valueTable = function (val, depth, cb) {
 }
 
 RenderMsg.prototype.missing = function (cb) {
-  this.wrapMini(h('code', 'MISSING'), cb)
+  this.wrapMini([
+    h('code', 'MISSING'), ' ',
+    h('a', {href: '?ooo=1'}, 'fetch')
+  ], cb)
 }
 
 RenderMsg.prototype.issues = function (cb) {
diff --git a/lib/serve.js b/lib/serve.js
index 73e209c..b688f72 100644
--- a/lib/serve.js
+++ b/lib/serve.js
@@ -259,6 +259,8 @@ Serve.prototype.publish = function (content, cb) {
 Serve.prototype.handle = function () {
   var m = urlIdRegex.exec(this.req.url)
   this.query = m[5] ? qs.parse(m[5]) : {}
+  this.useOoo = this.query.ooo != null ?
+    Boolean(this.query.ooo) : this.app.useOoo
   switch (m[2]) {
     case '%25': m[2] = '%'; m[1] = decodeURIComponent(m[1])
     case '%': return this.id(m[1], m[3])
@@ -955,7 +957,7 @@ Serve.prototype.links = function (path) {
 Serve.prototype.rawId = function (id) {
   var self = this
 
-  self.app.getMsgDecrypted(id, function (err, msg) {
+  self.getMsgDecryptedMaybeOoo(id, function (err, msg) {
     if (err) return pull(
       pull.once(u.renderError(err).outerHTML),
       self.respondSink(400, {'Content-Type': ctype('html')})
@@ -1003,12 +1005,11 @@ function threadHeads(msgs, rootId) {
   }))
 }
 
-
 Serve.prototype.id = function (id, path) {
   var self = this
   if (self.query.raw != null) return self.rawId(id)
 
-  this.app.getMsgDecrypted(id, function (err, rootMsg) {
+  this.getMsgDecryptedMaybeOoo(id, function (err, rootMsg) {
     if (err && err.name === 'NotFoundError') err = null, rootMsg = {
       key: id, value: {content: false}}
     if (err) return self.respond(500, err.stack || err)
@@ -1029,26 +1030,31 @@ Serve.prototype.id = function (id, path) {
         if (!channel && c.channel) channel = c.channel
       }),
       pull.collect(function (err, links) {
-        if (err) return self.respond(500, err.stack || err)
-        pull(
-          pull.values(sort(links)),
-          self.renderThread({
-	    msgId: id,
-	  }),
-          self.wrapMessages(),
-          self.wrapThread({
-            recps: recps,
-            root: threadRootId,
-            post: id,
-            branches: threadHeads(links, threadRootId),
-            postBranches: threadRootId !== id && threadHeads(links, id),
-            channel: channel,
-          }),
-          self.wrapPage(id),
-          self.respondSink(200)
-        )
+        if (err) return gotLinks(err)
+        if (!self.useOoo) return gotLinks(null, links)
+        self.app.expandOoo({msgs: links, dest: id}, gotLinks)
       })
     )
+    function gotLinks(err, links) {
+      if (err) return self.respond(500, err.stack || err)
+      pull(
+        pull.values(sort(links)),
+        self.renderThread({
+          msgId: id,
+        }),
+        self.wrapMessages(),
+        self.wrapThread({
+          recps: recps,
+          root: threadRootId,
+          post: id,
+          branches: threadHeads(links, threadRootId),
+          postBranches: threadRootId !== id && threadHeads(links, id),
+          channel: channel,
+        }),
+        self.wrapPage(id),
+        self.respondSink(200)
+      )
+    }
   })
 }
 
@@ -1955,7 +1961,7 @@ Serve.prototype.gitBlob = function (rev) {
     self.respondSink(400)
   )
 
-  self.app.getMsgDecrypted(self.query.msg, function (err, msg) {
+  self.getMsgDecryptedMaybeOoo(self.query.msg, function (err, msg) {
     if (err) return pull(
       pull.once(u.renderError(err).outerHTML),
       self.wrapPage('git object ' + rev),
@@ -2769,6 +2775,11 @@ Serve.prototype.getBuiltinEmojiLink = function (name) {
   }
 }
 
+Serve.prototype.getMsgDecryptedMaybeOoo = function (key, cb) {
+  if (this.useOoo) this.app.getMsgDecryptedOoo(key, cb)
+  else this.app.getMsgDecrypted(key, cb)
+}
+
 Serve.prototype.emojis = function (path) {
   var self = this
   var seen = {}
diff --git a/lib/util.js b/lib/util.js
index fb0b13f..7425513 100644
--- a/lib/util.js
+++ b/lib/util.js
@@ -5,12 +5,13 @@ var b64url = require('base64-url')
 var u = exports
 
 u.ssbRefRegex = /((?:@|%|&|ssb:\/\/%)[A-Za-z0-9\/+]{43}=\.[\w\d]+)/g
+u.ssbRefRegexOnly = /^(?:@|%|&|ssb:\/\/%)[A-Za-z0-9\/+]{43}=\.[\w\d]+$/
 u.ssbRefEncRegex = /((?:ssb:\/\/)?(?:[@%&]|%26|%40|%25)(?:[A-Za-z0-9\/+]|%2[fF]|%2[bB]){43}(?:=|%3[dD])\.[\w\d]+)/g
 
 u.isRef = function (str) {
   if (!str) return false
-  u.ssbRefRegex.lastIndex = 0
-  return u.ssbRefRegex.test(str)
+  u.ssbRefRegexOnly.lastIndex = 0
+  return u.ssbRefRegexOnly.test(str)
 }
 
 u.readNext = function (fn) {