hyper-string

conflict-free p2p string data structure powered by a hyperlog of operations

STATUS: very mad science-y work-in-progres

TODO: write some background / context on this. talk about the implications of representing a textual string as an append-only log of operations, with a materialized view as a DAG of character sequences.

Usage

Let's start writing "Helo", but have a fork where some other user wants to fix the spelling error by inserting another "l".

var hstring = require('hyper-string')
var memdb = require('memdb')
 
var str = hstring(memdb())
 
str.insert(null, null, 'Hola', function (err, ops) {
  // ops is an array of four unique IDs
  str.insert(null, ops[0], '¡')
  str.insert(ops[ops.length-1], null, '!')
})
 
str.text(function (err, text) {
  console.log(text)
})

This will output

¡Hola!

API

var hstring = require('hyper-string')

var str = hstring(db, opts={})

Creates a new hyper-string, backed by the LevelUP instance db.

str.insert(beforePos, afterPos, string, [cb])

Inserts all characters of string after position beforePos and before position afterPos, which are unique IDs of other characters previously inserted. If 'beforePosisnull, the given string is inserted at the beginning of the hyper-string. IfafterPosisnull`, it is inserted at the end.

Remember, since the hyper-string is represented by a directed acyclic graph, it can have many different "beginnings" and "ends". hyper-string ensures that the ordering of these are deterministic.

The callback cb is called with the signature function (err, chars), where chars is an array of the inserted characters of the form

{
  chr: 'P',
  pos: '...'
}

str.delete(from, to, [cb])

Deletes the characters between positions from and to, inclusive. cb is called with the signature function (err).

{
  op: 'delete',
  from: '...',
  to: '...'
}

str.text(cb)

Asynchronously returns a string, in the order they would be displayed for a human to read.

str.chars(cb)

Asynchronously returns all characters in the string, in the order they would be displayed for a human to read. Each object is of the form

{
  chr: 'P',
  pos: '...'
}

Install

With npm installed, run

$ npm install hyper-string

Acknowledgments

Based on the Logroot CRDT paper by Stephane Weiss, Pascal Urso, and Pascal Molli.

License

ISC