changesets - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

.travis.yml

+language: node_js
+node_js:
+  - 0.8

lib/text/Changeset.js

+/*!
+ * changesets
+ * A Changeset library incorporating operational transformation (OT)
+ * Copyright 2012 by Marcel Klehr <[e-mail]>
+ *
+ * (MIT LICENSE)
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+/**
+ * A list (in no particular order) of context-equivalent operations
+ * (use Changeset#sequencify() to get an array of transformed
+ * ops that can be applied on a document in sequence)
+ *
+ * @param ops.. <Operation> all passed operations will be added to the changeset
+ */
+function Changeset() {
+  for(var i=0; i<arguments.length; i++) {
+    this.push(arguments[i])
+  }
+}
+
+Changeset.prototype = new Array
+Changeset.prototype.constructor = Changeset
+module.exports = Changeset
+
+var Equal = require('./operations/Equal')
+  , Delete = require('./operations/Delete')
+  , Insert = require('./operations/Insert')
+
+/**
+ * Inclusion Transformation (IT) or Forward Transformation
+ *
+ * transforms the operations of the current changeset against the
+ * all operations in another changeset in such a way that the
+ * impact of the latter are effectively included
+ * 
+ * @returns <Changeset>
+ */
+Changeset.prototype.transformAgainst = function(changeset) {
+  if(!(changeset instanceof Changeset)) {
+    throw new Error('Argument must be a #<Changeset>, but received '+changeset.__proto__.constructor.name)
+  }
+  
+  var newCs = new Changeset
+    , changes = changeset.sequencify()
+    
+  this.forEach(function(op) {
+    changes.forEach(function(o) {
+      op = op.transformAgainst(o)
+    })
+    newCs.push(op)
+  })
+  
+  return newCs
+}
+
+/**
+ * Exclusion Transformation (ET) or Backwards Transformation
+ * 
+ * transforms all operations in the current changeset against the operations
+ * in another changeset in such a way that the impact of the latter are effectively excluded
+ * 
+ * @returns <Changeset>
+ */
+Changeset.prototype.substract = function(changeset) {
+  // The current operations assume that the changes in
+  // `changeset` happened before, so for each of those ops
+  // we create an operation that undoes its effect and
+  // transform all our operations on top of the inverse changes
+  var changes = Changeset.prototype.invert.apply(changeset.sequencify())
+  return this.transformAgainst(changes)
+}
+
+/**
+ * Transforms all contained operations against each
+ * other in sequence and returns an array of those new operations
+ *
+ * @returns <Array>
+ * Used internally
+ */
+Changeset.prototype.sequencify = function() {
+  var result = []
+  this.forEach(function(op) {
+    if(op instanceof Equal) return
+    
+    // transform against all previous ops
+    result.forEach(function(o) {
+      //console.log(op.__proto__.constructor.name+' '+op.pos+':'+op.text, '->',o.__proto__.constructor.name+' '+o.pos+':'+o.text)
+      op = op.transformAgainst(o)
+    })
+    //console.log('=',op.__proto__.constructor.name+' '+op.pos+':'+op.text)
+    //  console.log()
+    // ... and add it on top of them
+    result.push(op)
+  })
+  return result
+}
+
+/**
+ * Returns the inverse Changeset of the current one
+ * 
+ * Changeset.invert().apply(Changeset.apply(document)) == document
+ */
+Changeset.prototype.invert = function() {
+  var newCs = new Changeset
+  this.forEach(function(op) {
+    newCs.push(op.invert())
+  })
+  return newCs
+}
+
+/**
+ * Returns the inverse Operation of the current one
+ * 
+ * Operation.invert().apply(Operation.apply(state)) == state
+ */
+Changeset.prototype.apply = function(resource) {
+  var changes = this.sequencify()
+  changes.forEach(function(op) {
+    resource = op.apply(resource)
+  })
+  
+  return resource
+}
+
+/**
+ * Returns an array of strings describing this changeset's operations
+ */
+Changeset.prototype.inspect = function() {
+  return this.map(function(op) {
+    return op.__proto__.constructor.name+' '+op.pos+':'+op.text
+  })
+}
+
+// Hack that sorts out no-ops as well as changesets
+Changeset.prototype.push = function() {
+  var that = this
+  for(var i=0; i < arguments.length; i++) {
+    if(arguments[i] instanceof Equal) continue;
+    if(arguments[i] instanceof Changeset) {
+      arguments[i].forEach(function(op) {
+        that.push(op)
+      })
+      continue;
+    }
+    Array.prototype.push.call(this, arguments[i])
+  }
+  return this
+}
+
+/**
+ * Serializes the given changeset in order to return a (hopefully) more compact representation
+ * that can be sent through a network or stored in a database
+ *
+ * Numbers are converted to the base 36, text is converted to base64 (this is inefficient, I know..)
+ *
+ * @param cs <Changeset> The changeset to be serialized
+ * @returns <String> The serialized changeset
+ */
+Changeset.prototype.pack = function() {
+  var packed = this.map(function(op) {
+    var text = base64_encode(op.text)
+      , pos = (op.pos).toString(36)
+      , accessory = (op.accessory).toString(36)
+
+    if(op instanceof Delete) {
+      return '-'+pos+':'+text+':'+accessory
+    }
+    if(op instanceof Insert) {
+      return '+'+pos+':'+text+':'+accessory
+    }
+  }).join('')
+  return packed
+}
+Changeset.prototype.toString = function() {
+  return this.pack()
+}
+
+/**
+ * Unserializes the output of cs.text.Changeset#toString()
+ * 
+ * @param packed <String> The serialized changeset
+ * @param <cs.Changeset>
+ */
+Changeset.unpack = function(packed) {
+  var matches = packed.match(/(\+|-)\w+?:[^:\+-]+?:\w+?/g)
+  if(!matches) throw new Error('Cannot unpack invalid serialized changeset string')
+  
+  var cs = new Changeset
+  matches.forEach(function(s) {
+    var type = s.substr(0,1)
+      , props = s.substr(1).split(':')
+    var pos = parseInt(props[0], 36)
+      , text = base64_decode(props[1])
+      , accessory = parseInt(props[2], 36)
+    if(type == '-') return cs.push(new Delete(props[0], text, props[2]))
+    if(type == '+') return cs.push(new Insert(pos, text, accessory))
+  })
+  return cs
+}
+
+
+function base64_encode(text) {
+  if('undefined' != typeof window) return btoa(text)
+  if('undefined' != typeof process) return (new Buffer(text)).toString('base64').replace(/=+/, '')
+  throw new Error('No base64 implementation available!')
+}
+
+function base64_decode(base64) {
+  if('undefined' != typeof window) return atob(base64)
+  if('undefined' != typeof process) return (new Buffer(base64, 'base64')).toString()
+  throw new Error('No base64 implementation available!')
+}

lib/index.js

 exports.text = require('./text/index')
-exports.Changeset = require('./Changeset')
-exports.Operation = require('./Changeset')
+exports.Operation = require('./Operation')

lib/text/index.js

@@ -26,3 +26,3 @@ /*!
 
-var Changeset = require('../Changeset')
+var Changeset = require('./Changeset')
   , Delete = require('./operations/Delete')
@@ -36,2 +36,3 @@ , Insert = require('./operations/Insert')
 
+exports.Changeset = Changeset
   
@@ -68,1 +69,18 @@ /**
 }
+
+/**
+ * Serializes the given changeset in order to return a (hopefully) more compact representation
+ * that can be sent through a network or stored in a database
+ * @alias cs.text.Changeset#pack
+ */
+exports.pack = function(cs) {
+  return cs.pack()
+}
+
+/**
+ * Unserializes the output of cs.text.pack
+ * @alias cs.text.Changeset.unpack
+ */
+exports.unpack = function(packed) {
+  return Changeset.unpack(packed)
+}

lib/text/operations/Delete.js

@@ -49,3 +49,3 @@ /*!
   , Equal = require('./Equal')
-  , Changeset = require('../../Changeset')
+  , Changeset = require('../Changeset')
 
@@ -52,0 +52,0 @@

package.json

 {
   "name": "changesets",
-  "version": "0.1.2",
+  "version": "0.1.3",
   "description": "A Changeset library incorporating an operational transformation (OT) algorithm.",
@@ -23,3 +23,5 @@ "repository": {
   "main": "./lib/index",
-  "test": "vows ./test/*",
+  "scripts": {
+    "test": "vows ./test/*"
+  },
   "dependencies": {
@@ -26,0 +28,0 @@ "diff_match_patch": "*"

README.md

 
 # changesets
-This is library allows you to build text-based concurrent multi-user applications.
+build text-based concurrent multi-user applications using operational transformation!
 
-It was built with the following requirements in mind:
-* intention preservation
-* reversibility/invertibility (undo effect)
-* convergence
+*changesets* allows you to easily create changesets and apply them on all sites of a distributed system using Operational Transformation. It was built with the following requirements in mind:
 
-Easily create changesets and apply them on all sites of a distributed system using Operational Transformation.
+* intention preservation (no content corruption; your edits always have the same effect)
+* reversibility/invertibility (undo any edit without corrupting the content or the state)
+* convergence (everybody sees the same state)
 
 Note: While, at the current stage of development, this library only implements a text-based changeset solution, I intend to add functionality for tree-based data and at some point in the future maybe even images. If you would like to help, feel free to contact me.
 
+### Oppositional what?!
+In case the above question just came to your mind, you better start with [Wikipedia's entry on Operational Transformation](https://en.wikipedia.org/wiki/Operational_transformation) and a comprehensive [FAQ concerning OT](http://www3.ntu.edu.sg/home/czsun/projects/otfaq); I particularly recommend reading the latter.
+
 ## Install
@@ -29,3 +31,3 @@ `npm install changesets`
 ```
-You get a `cs.Changeset` object containing multiple `cs.Operation`s. The changeset can be applied to a text as follows:
+You get a `cs.text.Changeset` object containing multiple `cs.Operation`s. The changeset can be applied to a text as follows:
 ```js
@@ -37,4 +39,23 @@ var finalText = changes.apply(text1)
 
+### Serializing changesets
+In many cases you will find the need to serialize your changesets in order to efficiently transfer them through the network or store them on disk.
+
+`Changeset#pack()` takes a changeset object and returns the string representation of that changeset.
+```js
+var serialized = changeset.pack() // '+1:YWI:0+2:Yw:0-3:NA:0+9:YWthYmw:0+b:cmFkYQ:0'
+```
+
+`Changeset.unpack()` takes the output of `Changeset#pack()` and returns a changeset object.
+```js
+cs.text.Changeset.unpack(serialized) // {"0":{"accessory":0,"pos":1,"len":2,"text":"ab"},"1":{"accessory":0,"pos":2,"len":1,"text":"c"},"2":{"accessory":0,"pos":3,"len":1,"text" ...
+```
+
+If you'd like to display a changeset in a humanly readable form, use `Changeset#inspect`:
+
+```js
+changeset.inspect() // [ 'Insert 1:ab', 'Insert 2:c', 'Delete 3:4', 'Insert 9:akabl', 'Insert 11:rada' ]
+```
+
 ### Operational transformation
-*Inclusion Transformation* as well as *Exclusion Transformation* are supported.
+*Inclusion Transformation* as well as *Exclusion Transformation* is supported.
 
@@ -58,3 +79,5 @@ #### Inclusion Transformation
 ```
-Since we can at least safely apply one of them, we'll apply changeset A first on the original text. Now, in order to be able to apply changeset B, which still assumes the original context, we need to adjust it, based on the changes of changeset A, so that it still has the same effect on the text that was originally intended.
+Doesn't look that good.
+
+But since we can at least safely apply one of them, let's apply changeset A first on the original text. Now, in order to be able to apply changeset B, which still assumes the original context, we need to adjust it, based on the changes of changeset A, so that it still has the same effect on the text.
 ```js
@@ -70,3 +93,3 @@ var csB_new = csB.transformAgainst(csA)
 #### Exclusion Transformation
-Imagine a text editor, where users that allows users to undo any edit they've ever done to a document. Naturally, one will choose to store all edits as a list of changesets, where each applied on top of the other results in the currently visible document.
+Imagine a text editor, that allows users to undo any edit they've ever done to a document. Naturally, one will choose to store all edits as a list of changesets, where each applied on top of the other results in the currently visible document.
 ```js
@@ -89,5 +112,5 @@ var versions =
 ```
-Now we need to transform all following edits against this inverse changeset and in turn transform it against the previously iterated edits.
+Now we transform all following edits against this inverse changeset and in turn transform it against the previously iterated edits.
 ```
-var newEdits = [""]
+var newEdits = []
 for (var i=1; i < edits.length; i++) {
@@ -100,6 +123,2 @@ newEdits[i] = edits[i].transformAgainst(inverse)
 
-# More information
-Anyone interested in OT may want to start with [Wikipedia's entry on Operational Transformation](https://en.wikipedia.org/wiki/Operational_transformation) and a comprehensive [FAQ concerning OT](http://www3.ntu.edu.sg/home/czsun/projects/otfaq), I particularly recommend reading the latter.
-
-
 # Under the hood
@@ -114,3 +133,2 @@ *Changesets* makes use of Neil Fraser's [*diff-match-patch* library](https://code.google.com/p/google-diff-match-patch/) for generating the diff between two texts -- an amazing library!
 * Perhaps add text length diff to `Operation`s in order to be able validate them
-* Add a `pack()`/`unpack()`method to changesets
 * Simplify anyundo (large numbers of changesets have to be transformed against each other and an undo changseset)
@@ -117,0 +135,0 @@

test/text.js

@@ -73,7 +73,7 @@ /*!
         console.log("\n\n", test[0])        
-        console.dir(cs1.dump())
-        console.dir(cs2.dump())
+        console.dir(cs1.inspect())
+        console.dir(cs2.inspect())
 
         cs1 = cs1.transformAgainst(cs2)
-        console.log('=>', cs1.dump())
+        console.log('=>', cs1.inspect())
 
@@ -121,7 +121,7 @@ return cs1.apply(cs2.apply(test[0]))
         console.log("\n\n "+test[0][0]+":", test[0][2], '-', test[0][1])
-        console.dir(cs1.dump())
-        console.dir(cs2.dump())
+        console.dir(cs1.inspect())
+        console.dir(cs2.inspect())
 
         cs2 = cs2.substract(cs1)
-        console.log('=>', cs2.dump())
+        console.log('=>', cs2.inspect())
 
@@ -138,2 +138,18 @@ return cs2.apply(test[0][0])
 
+suite.addBatch({
+'pack/unpack':
+  { topic: function() {
+      return engine.constructChangeset("1234blabliblu", "1ab2c3blablakablibradalu")
+    }
+  , 'should be packed and unpacked correctly': function(er, cs) {
+      var packed = cs.pack()
+      console.log()
+      console.log(cs.inspect())
+      console.log(packed)
+      var unpacked = engine.Changeset.unpack(packed)
+      assert.deepEqual(unpacked, cs)
+    }
+  }
+})
+
 suite.export(module)

lib/Changeset.js

-/*!
- * changesets
- * A Changeset library incorporating operational transformation (OT)
- * Copyright 2012 by Marcel Klehr <[e-mail]>
- *
- * (MIT LICENSE)
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- * 
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- * 
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
- * THE SOFTWARE.
- */
-
-var Equal = require('./text/operations/Equal')
-
-/**
- * A list (in no particular order) of context-equivalent operations
- * (use Changeset#sequencify() to get an array of transformed
- * ops that can be applied on a document in sequence)
- *
- * @param ops.. <Operation> all passed operations will be added to the changeset
- */
-function Changeset() {
-  for(var i=0; i<arguments.length; i++) {
-    this.push(arguments[i])
-  }
-}
-
-Changeset.prototype = new Array
-Changeset.prototype.constructor = Changeset
-module.exports = Changeset
-
-/**
- * Inclusion Transformation (IT) or Forward Transformation
- *
- * transforms the operations of the current changeset against the
- * all operations in another changeset in such a way that the
- * impact of the latter are effectively included
- * 
- * @returns <Changeset>
- */
-Changeset.prototype.transformAgainst = function(changeset) {
-  if(!(changeset instanceof Changeset)) {
-    throw new Error('Argument must be a #<Changeset>, but received '+changeset.__proto__.constructor.name)
-  }
-  
-  var newCs = new Changeset
-    , changes = changeset.sequencify()
-    
-  this.forEach(function(op) {
-    changes.forEach(function(o) {
-      op = op.transformAgainst(o)
-    })
-    newCs.push(op)
-  })
-  
-  return newCs
-}
-
-/**
- * Exclusion Transformation (ET) or Backwards Transformation
- * 
- * transforms all operations in the current changeset against the operations
- * in another changeset in such a way that the impact of the latter are effectively excluded
- * 
- * @returns <Changeset>
- */
-Changeset.prototype.substract = function(changeset) {
-  // The current operations assume that the changes in
-  // `changeset` happened before, so for each of those ops
-  // we create an operation that undoes its effect and
-  // transform all our operations on top of the inverse changes
-  var changes = Changeset.prototype.invert.apply(changeset.sequencify())
-  return this.transformAgainst(changes)
-}
-
-/**
- * Transforms all contained operations against each
- * other in sequence and returns an array of those new operations
- *
- * @returns <Array>
- * Used internally
- */
-Changeset.prototype.sequencify = function() {
-  var result = []
-  this.forEach(function(op) {
-    if(op instanceof Equal) return
-    
-    // transform against all previous ops
-    result.forEach(function(o) {
-      //console.log(op.__proto__.constructor.name+' '+op.pos+':'+op.text, '->',o.__proto__.constructor.name+' '+o.pos+':'+o.text)
-      op = op.transformAgainst(o)
-    })
-    //console.log('=',op.__proto__.constructor.name+' '+op.pos+':'+op.text)
-    //  console.log()
-    // ... and add it on top of them
-    result.push(op)
-  })
-  return result
-}
-
-/**
- * Returns the inverse Changeset of the current one
- * 
- * Changeset.invert().apply(Changeset.apply(document)) == document
- */
-Changeset.prototype.invert = function() {
-  var newCs = new Changeset
-  this.forEach(function(op) {
-    newCs.push(op.invert())
-  })
-  return newCs
-}
-
-/**
- * Returns the inverse Operation of the current one
- * 
- * Operation.invert().apply(Operation.apply(state)) == state
- */
-Changeset.prototype.apply = function(resource) {
-  var changes = this.sequencify()
-  changes.forEach(function(op) {
-    resource = op.apply(resource)
-  })
-  
-  return resource
-}
-
-/**
- * Returns an array of strings describing this changeset's operations
- */
-Changeset.prototype.dump = function() {
-  return this.map(function(op) {
-    return op.__proto__.constructor.name+' '+op.pos+':'+op.text
-  })
-}
-
-// Hack that sorts out no-ops as well as changesets
-Changeset.prototype.push = function() {
-  var that = this
-  for(var i=0; i < arguments.length; i++) {
-    if(arguments[i] instanceof Equal) continue;
-    if(arguments[i] instanceof Changeset) {
-      arguments[i].forEach(function(op) {
-        that.push(op)
-      })
-      continue;
-    }
-    Array.prototype.push.call(this, arguments[i])
-  }
-  return this
-}

New alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

37633

12.36%

Number of package files

13

8.33%

Lines of code

724

13.66%

Number of lines in readme file

130

16.07%

Worsened metrics

Number of low supply chain risk alerts

1

Infinity%

No dependency changes