|
(function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){ |
|
var bindEditor = require('gulf-contenteditable') |
|
var domOT = require('dom-ot') |
|
var gulf = require('gulf') |
|
|
|
document.addEventListener('DOMContentLoaded', function () { |
|
var editable = document.querySelector('#doc[contenteditable]') |
|
var editableReplica = document.querySelector('#replica') |
|
var docB = bindEditor(editable) |
|
var docBReplica = bindEditor(editableReplica) |
|
|
|
gulf.Document.create( |
|
new gulf.MemoryAdapter, |
|
domOT, |
|
document.createElement('div'), |
|
function (er, docA) { |
|
|
|
var linkB = docB.masterLink() |
|
var linkBReplica = docBReplica.masterLink() |
|
|
|
linkB.pipe(docA.slaveLink()).pipe(linkB) |
|
linkBReplica.pipe(docA.slaveLink()).pipe(linkBReplica) |
|
|
|
}) |
|
}) |
|
},{"dom-ot":12,"gulf":22,"gulf-contenteditable":21}],2:[function(require,module,exports){ |
|
var Changeset = require('./Changeset') |
|
, Retain = require('./operations/Retain') |
|
, Skip = require('./operations/Skip') |
|
, Insert = require('./operations/Insert') |
|
|
|
function Builder() { |
|
this.ops = [] |
|
this.addendum = '' |
|
this.removendum = '' |
|
} |
|
|
|
module.exports = Builder |
|
|
|
Builder.prototype.keep = |
|
Builder.prototype.retain = function(len) { |
|
this.ops.push(new Retain(len)) |
|
return this |
|
} |
|
|
|
Builder.prototype.delete = |
|
Builder.prototype.skip = function(str) { |
|
this.removendum += str |
|
this.ops.push(new Skip(str.length)) |
|
return this |
|
} |
|
|
|
Builder.prototype.add = |
|
Builder.prototype.insert = function(str) { |
|
this.addendum += str |
|
this.ops.push(new Insert(str.length)) |
|
return this |
|
} |
|
|
|
Builder.prototype.end = function() { |
|
var cs = new Changeset(this.ops) |
|
cs.addendum = this.addendum |
|
cs.removendum = this.removendum |
|
return cs |
|
} |
|
},{"./Changeset":3,"./operations/Insert":8,"./operations/Retain":9,"./operations/Skip":10}],3:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational transformation (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 sequence of consecutive operations |
|
* |
|
* @param ops.. <Operation> all passed operations will be added to the changeset |
|
*/ |
|
function Changeset(ops/*or ops..*/) { |
|
this.addendum = "" |
|
this.removendum = "" |
|
this.inputLength = 0 |
|
this.outputLength = 0 |
|
|
|
if(!Array.isArray(ops)) ops = arguments |
|
for(var i=0; i<ops.length; i++) { |
|
this.push(ops[i]) |
|
this.inputLength += ops[i].input |
|
this.outputLength += ops[i].output |
|
} |
|
} |
|
|
|
// True inheritance |
|
Changeset.prototype = Object.create(Array.prototype, { |
|
constructor: { |
|
value: Changeset, |
|
enumerable: false, |
|
writable: true, |
|
configurable: true |
|
} |
|
}); |
|
module.exports = Changeset |
|
|
|
var TextTransform = require('./TextTransform') |
|
, ChangesetTransform = require('./ChangesetTransform') |
|
|
|
var Retain = require('./operations/Retain') |
|
, Skip = require('./operations/Skip') |
|
, Insert = require('./operations/Insert') |
|
|
|
var Builder = require('./Builder') |
|
|
|
/** |
|
* Returns an array containing the ops that are within the passed range |
|
* (only op.input is counted; thus not counting inserts to the range length, yet they are part of the range) |
|
*/ |
|
Changeset.prototype.subrange = function(start, len) { |
|
var range = [] |
|
, op, oplen |
|
, l=0 |
|
for(var i=0, pos=0; i<this.length && l < len; i++) { |
|
op = this[i] |
|
if(op.length+pos > start) { |
|
if(op.input) { |
|
if(op.length != Infinity) oplen = op.length -Math.max(0, start-pos) -Math.max(0, (op.length+pos)-(start+len)) |
|
else oplen = len |
|
range.push( op.derive(oplen) ) // (Don't copy over more than len param allows) |
|
} |
|
else { |
|
range.push( op.derive(op.length) ) |
|
oplen = 0 |
|
} |
|
l += oplen |
|
} |
|
pos += op.input |
|
} |
|
return range |
|
} |
|
|
|
/** |
|
* Merge two changesets (that are based on the same state!) so that the resulting changseset |
|
* has the same effect as both orignal ones applied one after the other |
|
* |
|
* @param otherCs <Changeset> |
|
* @param left <boolean> Which op to choose if there's an insert tie (If you use this function in a distributed, synchronous environment, be sure to invert this param on the other site, otherwise it can be omitted safely)) |
|
* @returns <Changeset> |
|
*/ |
|
Changeset.prototype.merge = function(otherCs, left) { |
|
if(!(otherCs instanceof Changeset)) { |
|
throw new Error('Argument must be a #<Changeset>, but received '+otherCs.__proto__.constructor.name) |
|
} |
|
|
|
var newops = [] |
|
, addPtr1 = 0 |
|
, remPtr1 = 0 |
|
, addPtr2 = 0 |
|
, remPtr2 = 0 |
|
, newaddendum = '' |
|
, newremovendum = '' |
|
|
|
zip(this, otherCs, function(op1, op2) { |
|
// console.log(newops) |
|
// console.log(op1, op2) |
|
|
|
if(op1 && !op1.input && (!op2 || op2.input || left)) { // if it's a tie -- "left" breaks it. |
|
newops.push(op1.merge().clone()) |
|
newaddendum += this.addendum.substr(addPtr1, op1.length) // overtake added chars |
|
addPtr1 += op1.length |
|
op1.length = 0 // don't gimme that one again. |
|
return |
|
} |
|
|
|
if(op2 && !op2.input && (!op1 || op1.input || !left)) {// if it's a tie -- "left" breaks it. |
|
newops.push(op2.merge().clone()) |
|
newaddendum += otherCs.addendum.substr(addPtr2, op2.length) // overtake added chars |
|
addPtr2 += op2.length |
|
op2.length = 0 // don't gimme that one again. |
|
return |
|
} |
|
|
|
// XXX Move addendum and removendum stuff to indiv. ops |
|
// XXX Move everything below this to op1.merge(op2) |
|
|
|
if(op2 && !op2.output) { |
|
newops.push(op2.merge(op1).clone()) |
|
newremovendum += otherCs.removendum.substr(remPtr2, op2.length) // overtake removed chars |
|
remPtr2 += op2.length |
|
if(op1) op1.length = 0 // don't gimme these again. |
|
op2.length = 0 |
|
return |
|
} |
|
|
|
if(op1 && !op1.output) { |
|
newops.push(op1.merge(op2).clone()) |
|
newremovendum += this.removendum.substr(remPtr1, op1.length) // overtake removed chars |
|
remPtr1 += op1.length |
|
op1.length = 0 // don't gimme that one again. |
|
if(op2) op2.length = 0 |
|
return |
|
} |
|
|
|
if((op1 && op1.input == op1.output)) { |
|
newops.push(op1.merge(op2).clone()) |
|
op1.length = 0 // don't gimme these again. |
|
if(op2) op2.length = 0 |
|
return |
|
} |
|
|
|
console.log('oops', arguments) |
|
throw new Error('oops. This case hasn\'t been considered by the developer (error code: PBCAC)') |
|
}.bind(this)) |
|
|
|
var newCs = new Changeset(newops) |
|
newCs.addendum = newaddendum |
|
newCs.removendum = newremovendum |
|
|
|
return newCs |
|
} |
|
|
|
/** |
|
* A private and quite handy function that slices ops into equally long pieces and applies them on a mapping function |
|
* that can determine the iteration steps by setting op.length to 0 on an op (equals using .next() in a usual iterator) |
|
*/ |
|
function zip(cs1, cs2, func) { |
|
var opstack1 = cs1.map(function(op) {return op.clone()}) // copy ops |
|
, opstack2 = cs2.map(function(op) {return op.clone()}) |
|
|
|
var op2, op1 |
|
while(opstack1.length || opstack2.length) {// iterate through all outstanding ops of this cs |
|
op1 = opstack1[0]? opstack1[0].clone() : null |
|
op2 = opstack2[0]? opstack2[0].clone() : null |
|
|
|
if(op1) { |
|
if(op2) op1 = op1.derive(Math.min(op1.length, op2.length)) // slice 'em into equally long pieces |
|
if(opstack1[0].length > op1.length) opstack1[0] = opstack1[0].derive(opstack1[0].length-op1.length) |
|
else opstack1.shift() |
|
} |
|
|
|
if(op2) { |
|
if(op1) op2 = op2.derive(Math.min(op1.length, op2.length)) // slice 'em into equally long pieces |
|
if(opstack2[0].length > op2.length) opstack2[0] = opstack2[0].derive(opstack2[0].length-op2.length) |
|
else opstack2.shift() |
|
} |
|
|
|
func(op1, op2) |
|
|
|
if(op1 && op1.length) opstack1.unshift(op1) |
|
if(op2 && op2.length) opstack2.unshift(op2) |
|
} |
|
} |
|
|
|
/** |
|
* 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 |
|
* effects of the latter are effectively included. |
|
* This is basically like a applying the other cs on this one. |
|
* |
|
* @param otherCs <Changeset> |
|
* @param left <boolean> Which op to choose if there's an insert tie (If you use this function in a distributed, synchronous environment, be sure to invert this param on the other site, otherwise it can be omitted safely) |
|
* |
|
* @returns <Changeset> |
|
*/ |
|
Changeset.prototype.transformAgainst = function(otherCs, left) { |
|
if(!(otherCs instanceof Changeset)) { |
|
throw new Error('Argument to Changeset#transformAgainst must be a #<Changeset>, but received '+otherCs.__proto__.constructor.name) |
|
} |
|
|
|
if(this.inputLength != otherCs.inputLength) { |
|
throw new Error('Can\'t transform changesets with differing inputLength: '+this.inputLength+' and '+otherCs.inputLength) |
|
} |
|
|
|
var transformation = new ChangesetTransform(this, [new Retain(Infinity)]) |
|
otherCs.forEach(function(op) { |
|
var nextOp = this.subrange(transformation.pos, Infinity)[0] // next op of this cs |
|
if(nextOp && !nextOp.input && !op.input && left) { // two inserts tied; left breaks it |
|
transformation.writeOutput(transformation.readInput(nextOp.length)) |
|
} |
|
op.apply(transformation) |
|
}.bind(this)) |
|
|
|
return transformation.result() |
|
} |
|
|
|
/** |
|
* 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 |
|
* |
|
* @param changeset <Changeset> the changeset to substract from this one |
|
* @param left <boolean> Which op to choose if there's an insert tie (If you use this function in a distributed, synchronous environment, be sure to invert this param on the other site, otherwise it can be omitted safely) |
|
* @returns <Changeset> |
|
*/ |
|
Changeset.prototype.substract = function(changeset, left) { |
|
// 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 |
|
return this.transformAgainst(changeset.invert(), left) |
|
} |
|
|
|
/** |
|
* Returns the inverse Changeset of the current one |
|
* |
|
* Changeset.invert().apply(Changeset.apply(document)) == document |
|
*/ |
|
Changeset.prototype.invert = function() { |
|
// invert all ops |
|
var newCs = new Changeset(this.map(function(op) { |
|
return op.invert() |
|
})) |
|
|
|
// removendum becomes addendum and vice versa |
|
newCs.addendum = this.removendum |
|
newCs.removendum = this.addendum |
|
|
|
return newCs |
|
} |
|
|
|
/** |
|
* Applies this changeset on a text |
|
*/ |
|
Changeset.prototype.apply = function(input) { |
|
// pre-requisites |
|
if(input.length != this.inputLength) throw new Error('Input length doesn\'t match expected length. expected: '+this.inputLength+'; actual: '+input.length) |
|
|
|
var operation = new TextTransform(input, this.addendum, this.removendum) |
|
|
|
this.forEach(function(op) { |
|
// each Operation has access to all pointers as well as the input, addendum and removendum (the latter are immutable) |
|
op.apply(operation) |
|
}.bind(this)) |
|
|
|
return operation.result() |
|
} |
|
|
|
/** |
|
* Returns an array of strings describing this changeset's operations |
|
*/ |
|
Changeset.prototype.inspect = function() { |
|
var j = 0 |
|
return this.map(function(op) { |
|
var string = '' |
|
|
|
if(!op.input) { // if Insert |
|
string = this.addendum.substr(j,op.length) |
|
j += op.length |
|
return string |
|
} |
|
|
|
for(var i=0; i<op.length; i++) string += op.symbol |
|
return string |
|
}.bind(this)).join('') |
|
} |
|
|
|
/** |
|
* Serializes the given changeset in order to return a (hopefully) more compact representation |
|
* than json that can be sent through a network or stored in a database |
|
* |
|
* Numbers are converted to the base 36, unsafe chars in the text are urlencoded |
|
* |
|
* @param cs <Changeset> The changeset to be serialized |
|
* @returns <String> The serialized changeset |
|
*/ |
|
Changeset.prototype.pack = function() { |
|
var packed = this.map(function(op) { |
|
return op.pack() |
|
}).join('') |
|
|
|
var addendum = this.addendum.replace(/%/g, '%25').replace(/\|/g, '%7C') |
|
, removendum = this.removendum.replace(/%/g, '%25').replace(/\|/g, '%7C') |
|
return packed+'|'+addendum+'|'+removendum |
|
} |
|
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) { |
|
if(packed == '') throw new Error('Cannot unpack from empty string') |
|
var components = packed.split('|') |
|
, opstring = components[0] |
|
, addendum = components[1].replace(/%7c/gi, '|').replace(/%25/g, '%') |
|
, removendum = components[2].replace(/%7c/gi, '|').replace(/%25/g, '%') |
|
|
|
var matches = opstring.match(/[=+-]([^=+-])+/g) |
|
if(!matches) throw new Error('Cannot unpack invalidly serialized op string') |
|
|
|
var ops = [] |
|
matches.forEach(function(s) { |
|
var symbol = s.substr(0,1) |
|
, data = s.substr(1) |
|
if(Skip.prototype.symbol == symbol) return ops.push(Skip.unpack(data)) |
|
if(Insert.prototype.symbol == symbol) return ops.push(Insert.unpack(data)) |
|
if(Retain.prototype.symbol == symbol) return ops.push(Retain.unpack(data)) |
|
throw new Error('Invalid changeset representation passed to Changeset.unpack') |
|
}) |
|
|
|
var cs = new Changeset(ops) |
|
cs.addendum = addendum |
|
cs.removendum = removendum |
|
|
|
return cs |
|
} |
|
|
|
Changeset.create = function() { |
|
return new Builder |
|
} |
|
|
|
/** |
|
* Returns a Changeset containing the operations needed to transform text1 into text2 |
|
* |
|
* @param text1 <String> |
|
* @param text2 <String> |
|
*/ |
|
Changeset.fromDiff = function(diff) { |
|
/** |
|
* The data structure representing a diff is an array of tuples: |
|
* [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']] |
|
* which means: delete 'Hello', add 'Goodbye' and keep ' world.' |
|
*/ |
|
var DIFF_DELETE = -1; |
|
var DIFF_INSERT = 1; |
|
var DIFF_EQUAL = 0; |
|
|
|
var ops = [] |
|
, removendum = '' |
|
, addendum = '' |
|
|
|
diff.forEach(function(d) { |
|
if (DIFF_DELETE == d[0]) { |
|
ops.push(new Skip(d[1].length)) |
|
removendum += d[1] |
|
} |
|
|
|
if (DIFF_INSERT == d[0]) { |
|
ops.push(new Insert(d[1].length)) |
|
addendum += d[1] |
|
} |
|
|
|
if(DIFF_EQUAL == d[0]) { |
|
ops.push(new Retain(d[1].length)) |
|
} |
|
}) |
|
|
|
var cs = new Changeset(ops) |
|
cs.addendum = addendum |
|
cs.removendum = removendum |
|
return cs |
|
} |
|
},{"./Builder":2,"./ChangesetTransform":4,"./TextTransform":6,"./operations/Insert":8,"./operations/Retain":9,"./operations/Skip":10}],4:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational ChangesetTransform (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Retain = require('./operations/Retain') |
|
, Skip = require('./operations/Skip') |
|
, Insert = require('./operations/Insert') |
|
, Changeset = require('./Changeset') |
|
|
|
|
|
function ChangesetTransform(inputCs, addendum) { |
|
this.output = [] |
|
this.addendum = addendum |
|
this.newRemovendum = '' |
|
this.newAddendum = '' |
|
|
|
this.cs = inputCs |
|
this.pos = 0 |
|
this.addendumPointer = 0 |
|
this.removendumPointer = 0 |
|
} |
|
module.exports = ChangesetTransform |
|
|
|
ChangesetTransform.prototype.readInput = function (len) { |
|
var ret = this.cs.subrange(this.pos, len) |
|
this.pos += len |
|
return ret |
|
} |
|
|
|
ChangesetTransform.prototype.readAddendum = function (len) { |
|
//return [new Retain(len)] |
|
var ret = this.subrange(this.addendum, this.addendumPointer, len) |
|
this.addendumPointer += len |
|
return ret |
|
} |
|
|
|
ChangesetTransform.prototype.writeRemovendum = function (range) { |
|
range |
|
.filter(function(op) {return !op.output}) |
|
.forEach(function(op) { |
|
this.removendumPointer += op.length |
|
}.bind(this)) |
|
} |
|
|
|
ChangesetTransform.prototype.writeOutput = function (range) { |
|
this.output = this.output.concat(range) |
|
range |
|
.filter(function(op) {return !op.output}) |
|
.forEach(function(op) { |
|
this.newRemovendum += this.cs.removendum.substr(this.removendumPointer, op.length) |
|
this.removendumPointer += op.length |
|
}.bind(this)) |
|
} |
|
|
|
ChangesetTransform.prototype.subrange = function (range, start, len) { |
|
if(len) return this.cs.subrange.call(range, start, len) |
|
else return range.filter(function(op){ return !op.input}) |
|
} |
|
|
|
ChangesetTransform.prototype.result = function() { |
|
this.writeOutput(this.readInput(Infinity)) |
|
var newCs = new Changeset(this.output) |
|
newCs.addendum = this.cs.addendum |
|
newCs.removendum = this.newRemovendum |
|
return newCs |
|
} |
|
},{"./Changeset":3,"./operations/Insert":8,"./operations/Retain":9,"./operations/Skip":10}],5:[function(require,module,exports){ |
|
function Operator() { |
|
} |
|
|
|
module.exports = Operator |
|
|
|
Operator.prototype.clone = function() { |
|
return this.derive(this.length) |
|
} |
|
|
|
Operator.prototype.derive = function(len) { |
|
return new (this.constructor)(len) |
|
} |
|
|
|
Operator.prototype.pack = function() { |
|
return this.symbol + (this.length).toString(36) |
|
} |
|
},{}],6:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational Apply (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Retain = require('./operations/Retain') |
|
, Skip = require('./operations/Skip') |
|
, Insert = require('./operations/Insert') |
|
, Insert = require('./Changeset') |
|
|
|
|
|
function TextTransform(input, addendum, removendum) { |
|
this.output = '' |
|
|
|
this.input = input |
|
this.addendum = addendum |
|
this.removendum = removendum |
|
this.pos = 0 |
|
this.addPos = 0 |
|
this.remPos = 0 |
|
} |
|
module.exports = TextTransform |
|
|
|
TextTransform.prototype.readInput = function (len) { |
|
var ret = this.input.substr(this.pos, len) |
|
this.pos += len |
|
return ret |
|
} |
|
|
|
TextTransform.prototype.readAddendum = function (len) { |
|
var ret = this.addendum.substr(this.addPos, len) |
|
this.addPos += len |
|
return ret |
|
} |
|
|
|
TextTransform.prototype.writeRemovendum = function (range) { |
|
//var expected = this.removendum.substr(this.remPos, range.length) |
|
//if(range != expected) throw new Error('Removed chars don\'t match removendum. expected: '+expected+'; actual: '+range) |
|
this.remPos += range.length |
|
} |
|
|
|
TextTransform.prototype.writeOutput = function (range) { |
|
this.output += range |
|
} |
|
|
|
TextTransform.prototype.subrange = function (range, start, len) { |
|
return range.substr(start, len) |
|
} |
|
|
|
TextTransform.prototype.result = function() { |
|
this.writeOutput(this.readInput(Infinity)) |
|
return this.output |
|
} |
|
},{"./Changeset":3,"./operations/Insert":8,"./operations/Retain":9,"./operations/Skip":10}],7:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational transformation (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Changeset = require('./Changeset') |
|
, Retain = require('./operations/Retain') |
|
, Skip = require('./operations/Skip') |
|
, Insert = require('./operations/Insert') |
|
|
|
exports.Operator = require('./Operator') |
|
exports.Changeset = Changeset |
|
exports.Insert = Insert |
|
exports.Retain = Retain |
|
exports.Skip = Skip |
|
|
|
if('undefined' != typeof window) window.changesets = exports |
|
|
|
/** |
|
* 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) |
|
} |
|
|
|
|
|
|
|
|
|
/** |
|
* shareJS ot type API sepc support |
|
*/ |
|
|
|
exports.name = 'changesets' |
|
exports.url = 'https://github.com/marcelklehr/changesets' |
|
|
|
/** |
|
* create([initialText]) |
|
* |
|
* creates a snapshot (optionally with supplied intial text) |
|
*/ |
|
exports.create = function(initText) { |
|
return initText || '' |
|
} |
|
|
|
/** |
|
* Apply a changeset on a snapshot creating a new one |
|
* |
|
* The old snapshot object mustn't be used after calling apply on it |
|
* returns the resulting |
|
*/ |
|
exports.apply = function(snapshot, op) { |
|
op = exports.unpack(op) |
|
return op.apply(snapshot) |
|
} |
|
|
|
/** |
|
* Transform changeset1 against changeset2 |
|
*/ |
|
exports.transform = function (op1, op2, side) { |
|
op1 = exports.unpack(op1) |
|
op2 = exports.unpack(op2) |
|
return exports.pack(op1.transformAgainst(op2, ('left'==side))) |
|
} |
|
|
|
/** |
|
* Merge two changesets into one |
|
*/ |
|
exports.compose = function (op1, op2) { |
|
op1 = exports.unpack(op1) |
|
op2 = exports.unpack(op2) |
|
return exports.pack(op1.merge(op2)) |
|
} |
|
|
|
/** |
|
* Invert a changeset |
|
*/ |
|
exports.invert = function(op) { |
|
return op.invert() |
|
} |
|
},{"./Changeset":3,"./Operator":5,"./operations/Insert":8,"./operations/Retain":9,"./operations/Skip":10}],8:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational transformation (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Operator = require('../Operator') |
|
|
|
/** |
|
* Insert Operator |
|
* Defined by: |
|
* - length |
|
* - input=0 |
|
* - output=length |
|
* |
|
* @param length <Number> How many chars to be inserted |
|
*/ |
|
function Insert(length) { |
|
this.length = length |
|
this.input = 0 |
|
this.output = length |
|
} |
|
|
|
// True inheritance |
|
Insert.prototype = Object.create(Operator.prototype, { |
|
constructor: { |
|
value: Insert, |
|
enumerable: false, |
|
writable: true, |
|
configurable: true |
|
} |
|
}); |
|
module.exports = Insert |
|
Insert.prototype.symbol = '+' |
|
|
|
var Skip = require('./Skip') |
|
, Retain = require('./Retain') |
|
|
|
Insert.prototype.apply = function(t) { |
|
t.writeOutput(t.readAddendum(this.output)) |
|
} |
|
|
|
Insert.prototype.merge = function() { |
|
return this |
|
} |
|
|
|
Insert.prototype.invert = function() { |
|
return new Skip(this.length) |
|
} |
|
|
|
Insert.unpack = function(data) { |
|
return new Insert(parseInt(data, 36)) |
|
} |
|
},{"../Operator":5,"./Retain":9,"./Skip":10}],9:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational transformation (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Operator = require('../Operator') |
|
|
|
/** |
|
* Retain Operator |
|
* Defined by: |
|
* - length |
|
* - input=output=length |
|
* |
|
* @param length <Number> How many chars to retain |
|
*/ |
|
function Retain(length) { |
|
this.length = length |
|
this.input = length |
|
this.output = length |
|
} |
|
|
|
// True inheritance |
|
Retain.prototype = Object.create(Operator.prototype, { |
|
constructor: { |
|
value: Retain, |
|
enumerable: false, |
|
writable: true, |
|
configurable: true |
|
} |
|
}); |
|
module.exports = Retain |
|
Retain.prototype.symbol = '=' |
|
|
|
Retain.prototype.apply = function(t) { |
|
t.writeOutput(t.readInput(this.input)) |
|
} |
|
|
|
Retain.prototype.invert = function() { |
|
return this |
|
} |
|
|
|
Retain.prototype.merge = function(op2) { |
|
return this |
|
} |
|
|
|
Retain.unpack = function(data) { |
|
return new Retain(parseInt(data, 36)) |
|
} |
|
},{"../Operator":5}],10:[function(require,module,exports){ |
|
/*! |
|
* changesets |
|
* A Changeset library incorporating operational transformation (OT) |
|
* Copyright 2012 by Marcel Klehr <mklehr@gmx.net> |
|
* |
|
* (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 Operator = require('../Operator') |
|
|
|
/** |
|
* Skip Operator |
|
* Defined by: |
|
* - length |
|
* - input=length |
|
* - output=0 |
|
* |
|
* @param length <Number> How many chars to be Skip |
|
*/ |
|
function Skip(length) { |
|
this.length = length |
|
this.input = length |
|
this.output = 0 |
|
} |
|
|
|
// True inheritance |
|
Skip.prototype = Object.create(Operator.prototype, { |
|
constructor: { |
|
value: Skip, |
|
enumerable: false, |
|
writable: true, |
|
configurable: true |
|
} |
|
}); |
|
module.exports = Skip |
|
Skip.prototype.symbol = '-' |
|
|
|
var Insert = require('./Insert') |
|
, Retain = require('./Retain') |
|
, Changeset = require('../Changeset') |
|
|
|
Skip.prototype.apply = function(t) { |
|
var input = t.readInput(this.input) |
|
t.writeRemovendum(input) |
|
t.writeOutput(t.subrange(input, 0, this.output)) // retain Inserts in my range |
|
} |
|
|
|
Skip.prototype.merge = function(op2) { |
|
return this |
|
} |
|
|
|
Skip.prototype.invert = function() { |
|
return new Insert(this.length) |
|
} |
|
|
|
Skip.unpack = function(data) { |
|
return new Skip(parseInt(data, 36)) |
|
} |
|
},{"../Changeset":3,"../Operator":5,"./Insert":8,"./Retain":9}],11:[function(require,module,exports){ |
|
/** |
|
* Diff Match and Patch |
|
* |
|
* Copyright 2006 Google Inc. |
|
* http://code.google.com/p/google-diff-match-patch/ |
|
* |
|
* Licensed under the Apache License, Version 2.0 (the "License"); |
|
* you may not use this file except in compliance with the License. |
|
* You may obtain a copy of the License at |
|
* |
|
* http://www.apache.org/licenses/LICENSE-2.0 |
|
* |
|
* Unless required by applicable law or agreed to in writing, software |
|
* distributed under the License is distributed on an "AS IS" BASIS, |
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
* See the License for the specific language governing permissions and |
|
* limitations under the License. |
|
*/ |
|
|
|
/** |
|
* @fileoverview Computes the difference between two texts to create a patch. |
|
* Applies the patch onto another text, allowing for errors. |
|
* @author fraser@google.com (Neil Fraser) |
|
*/ |
|
|
|
/** |
|
* Class containing the diff, match and patch methods. |
|
* @constructor |
|
*/ |
|
function diff_match_patch() { |
|
|
|
// Defaults. |
|
// Redefine these in your program to override the defaults. |
|
|
|
// Number of seconds to map a diff before giving up (0 for infinity). |
|
this.Diff_Timeout = 1.0; |
|
// Cost of an empty edit operation in terms of edit characters. |
|
this.Diff_EditCost = 4; |
|
// The size beyond which the double-ended diff activates. |
|
// Double-ending is twice as fast, but less accurate. |
|
this.Diff_DualThreshold = 32; |
|
// At what point is no match declared (0.0 = perfection, 1.0 = very loose). |
|
this.Match_Threshold = 0.5; |
|
// How far to search for a match (0 = exact location, 1000+ = broad match). |
|
// A match this many characters away from the expected location will add |
|
// 1.0 to the score (0.0 is a perfect match). |
|
this.Match_Distance = 1000; |
|
// When deleting a large block of text (over ~64 characters), how close does |
|
// the contents have to match the expected contents. (0.0 = perfection, |
|
// 1.0 = very loose). Note that Match_Threshold controls how closely the |
|
// end points of a delete need to match. |
|
this.Patch_DeleteThreshold = 0.5; |
|
// Chunk size for context length. |
|
this.Patch_Margin = 4; |
|
|
|
/** |
|
* Compute the number of bits in an int. |
|
* The normal answer for JavaScript is 32. |
|
* @return {number} Max bits |
|
*/ |
|
function getMaxBits() { |
|
var maxbits = 0; |
|
var oldi = 1; |
|
var newi = 2; |
|
while (oldi != newi) { |
|
maxbits++; |
|
oldi = newi; |
|
newi = newi << 1; |
|
} |
|
return maxbits; |
|
} |
|
// How many bits in a number? |
|
this.Match_MaxBits = getMaxBits(); |
|
} |
|
|
|
|
|
// DIFF FUNCTIONS |
|
|
|
|
|
/** |
|
* The data structure representing a diff is an array of tuples: |
|
* [[DIFF_DELETE, 'Hello'], [DIFF_INSERT, 'Goodbye'], [DIFF_EQUAL, ' world.']] |
|
* which means: delete 'Hello', add 'Goodbye' and keep ' world.' |
|
*/ |
|
var DIFF_DELETE = -1; |
|
var DIFF_INSERT = 1; |
|
var DIFF_EQUAL = 0; |
|
|
|
|
|
/** |
|
* Find the differences between two texts. Simplifies the problem by stripping |
|
* any common prefix or suffix off the texts before diffing. |
|
* @param {string} text1 Old string to be diffed. |
|
* @param {string} text2 New string to be diffed. |
|
* @param {boolean} opt_checklines Optional speedup flag. If present and false, |
|
* then don't run a line-level diff first to identify the changed areas. |
|
* Defaults to true, which does a faster, slightly less optimal diff |
|
* @return {Array.<Array.<number|string>>} Array of diff tuples. |
|
*/ |
|
diff_match_patch.prototype.diff_main = function(text1, text2, opt_checklines) { |
|
// Check for null inputs. |
|
if (text1 == null || text2 == null) { |
|
throw new Error('Null input. (diff_main)'); |
|
} |
|
|
|
// Check for equality (speedup). |
|
if (text1 == text2) { |
|
return [[DIFF_EQUAL, text1]]; |
|
} |
|
|
|
if (typeof opt_checklines == 'undefined') { |
|
opt_checklines = true; |
|
} |
|
var checklines = opt_checklines; |
|
|
|
// Trim off common prefix (speedup). |
|
var commonlength = this.diff_commonPrefix(text1, text2); |
|
var commonprefix = text1.substring(0, commonlength); |
|
text1 = text1.substring(commonlength); |
|
text2 = text2.substring(commonlength); |
|
|
|
// Trim off common suffix (speedup). |
|
commonlength = this.diff_commonSuffix(text1, text2); |
|
var commonsuffix = text1.substring(text1.length - commonlength); |
|
text1 = text1.substring(0, text1.length - commonlength); |
|
text2 = text2.substring(0, text2.length - commonlength); |
|
|
|
// Compute the diff on the middle block. |
|
var diffs = this.diff_compute(text1, text2, checklines); |
|
|
|
// Restore the prefix and suffix. |
|
if (commonprefix) { |
|
diffs.unshift([DIFF_EQUAL, commonprefix]); |
|
} |
|
if (commonsuffix) { |
|
diffs.push([DIFF_EQUAL, commonsuffix]); |
|
} |
|
this.diff_cleanupMerge(diffs); |
|
return diffs; |
|
}; |
|
|
|
|
|
/** |
|
* Find the differences between two texts. Assumes that the texts do not |
|
* have any common prefix or suffix. |
|
* @param {string} text1 Old string to be diffed. |
|
* @param {string} text2 New string to be diffed. |
|
* @param {boolean} checklines Speedup flag. If false, then don't run a |
|
* line-level diff first to identify the changed areas. |
|
* If true, then run a faster, slightly less optimal diff |
|
* @return {Array.<Array.<number|string>>} Array of diff tuples. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_compute = function(text1, text2, checklines) { |
|
var diffs; |
|
|
|
if (!text1) { |
|
// Just add some text (speedup). |
|
return [[DIFF_INSERT, text2]]; |
|
} |
|
|
|
if (!text2) { |
|
// Just delete some text (speedup). |
|
return [[DIFF_DELETE, text1]]; |
|
} |
|
|
|
var longtext = text1.length > text2.length ? text1 : text2; |
|
var shorttext = text1.length > text2.length ? text2 : text1; |
|
var i = longtext.indexOf(shorttext); |
|
if (i != -1) { |
|
// Shorter text is inside the longer text (speedup). |
|
diffs = [[DIFF_INSERT, longtext.substring(0, i)], |
|
[DIFF_EQUAL, shorttext], |
|
[DIFF_INSERT, longtext.substring(i + shorttext.length)]]; |
|
// Swap insertions for deletions if diff is reversed. |
|
if (text1.length > text2.length) { |
|
diffs[0][0] = diffs[2][0] = DIFF_DELETE; |
|
} |
|
return diffs; |
|
} |
|
longtext = shorttext = null; // Garbage collect. |
|
|
|
// Check to see if the problem can be split in two. |
|
var hm = this.diff_halfMatch(text1, text2); |
|
if (hm) { |
|
// A half-match was found, sort out the return data. |
|
var text1_a = hm[0]; |
|
var text1_b = hm[1]; |
|
var text2_a = hm[2]; |
|
var text2_b = hm[3]; |
|
var mid_common = hm[4]; |
|
// Send both pairs off for separate processing. |
|
var diffs_a = this.diff_main(text1_a, text2_a, checklines); |
|
var diffs_b = this.diff_main(text1_b, text2_b, checklines); |
|
// Merge the results. |
|
return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b); |
|
} |
|
|
|
// Perform a real diff. |
|
if (checklines && (text1.length < 100 || text2.length < 100)) { |
|
// Too trivial for the overhead. |
|
checklines = false; |
|
} |
|
var linearray; |
|
if (checklines) { |
|
// Scan the text on a line-by-line basis first. |
|
var a = this.diff_linesToChars(text1, text2); |
|
text1 = a[0]; |
|
text2 = a[1]; |
|
linearray = a[2]; |
|
} |
|
diffs = this.diff_map(text1, text2); |
|
if (!diffs) { |
|
// No acceptable result. |
|
diffs = [[DIFF_DELETE, text1], [DIFF_INSERT, text2]]; |
|
} |
|
if (checklines) { |
|
// Convert the diff back to original text. |
|
this.diff_charsToLines(diffs, linearray); |
|
// Eliminate freak matches (e.g. blank lines) |
|
this.diff_cleanupSemantic(diffs); |
|
|
|
// Rediff any replacement blocks, this time character-by-character. |
|
// Add a dummy entry at the end. |
|
diffs.push([DIFF_EQUAL, '']); |
|
var pointer = 0; |
|
var count_delete = 0; |
|
var count_insert = 0; |
|
var text_delete = ''; |
|
var text_insert = ''; |
|
while (pointer < diffs.length) { |
|
switch (diffs[pointer][0]) { |
|
case DIFF_INSERT: |
|
count_insert++; |
|
text_insert += diffs[pointer][1]; |
|
break; |
|
case DIFF_DELETE: |
|
count_delete++; |
|
text_delete += diffs[pointer][1]; |
|
break; |
|
case DIFF_EQUAL: |
|
// Upon reaching an equality, check for prior redundancies. |
|
if (count_delete >= 1 && count_insert >= 1) { |
|
// Delete the offending records and add the merged ones. |
|
var a = this.diff_main(text_delete, text_insert, false); |
|
diffs.splice(pointer - count_delete - count_insert, |
|
count_delete + count_insert); |
|
pointer = pointer - count_delete - count_insert; |
|
for (var j = a.length - 1; j >= 0; j--) { |
|
diffs.splice(pointer, 0, a[j]); |
|
} |
|
pointer = pointer + a.length; |
|
} |
|
count_insert = 0; |
|
count_delete = 0; |
|
text_delete = ''; |
|
text_insert = ''; |
|
break; |
|
} |
|
pointer++; |
|
} |
|
diffs.pop(); // Remove the dummy entry at the end. |
|
} |
|
return diffs; |
|
}; |
|
|
|
|
|
/** |
|
* Split two texts into an array of strings. Reduce the texts to a string of |
|
* hashes where each Unicode character represents one line. |
|
* @param {string} text1 First string. |
|
* @param {string} text2 Second string. |
|
* @return {Array.<string|Array.<string>>} Three element Array, containing the |
|
* encoded text1, the encoded text2 and the array of unique strings. The |
|
* zeroth element of the array of unique strings is intentionally blank. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_linesToChars = function(text1, text2) { |
|
var lineArray = []; // e.g. lineArray[4] == 'Hello\n' |
|
var lineHash = {}; // e.g. lineHash['Hello\n'] == 4 |
|
|
|
// '\x00' is a valid character, but various debuggers don't like it. |
|
// So we'll insert a junk entry to avoid generating a null character. |
|
lineArray[0] = ''; |
|
|
|
/** |
|
* Split a text into an array of strings. Reduce the texts to a string of |
|
* hashes where each Unicode character represents one line. |
|
* Modifies linearray and linehash through being a closure. |
|
* @param {string} text String to encode. |
|
* @return {string} Encoded string. |
|
* @private |
|
*/ |
|
function diff_linesToCharsMunge(text) { |
|
var chars = ''; |
|
// Walk the text, pulling out a substring for each line. |
|
// text.split('\n') would would temporarily double our memory footprint. |
|
// Modifying text would create many large strings to garbage collect. |
|
var lineStart = 0; |
|
var lineEnd = -1; |
|
// Keeping our own length variable is faster than looking it up. |
|
var lineArrayLength = lineArray.length; |
|
while (lineEnd < text.length - 1) { |
|
lineEnd = text.indexOf('\n', lineStart); |
|
if (lineEnd == -1) { |
|
lineEnd = text.length - 1; |
|
} |
|
var line = text.substring(lineStart, lineEnd + 1); |
|
lineStart = lineEnd + 1; |
|
|
|
if (lineHash.hasOwnProperty ? lineHash.hasOwnProperty(line) : |
|
(lineHash[line] !== undefined)) { |
|
chars += String.fromCharCode(lineHash[line]); |
|
} else { |
|
chars += String.fromCharCode(lineArrayLength); |
|
lineHash[line] = lineArrayLength; |
|
lineArray[lineArrayLength++] = line; |
|
} |
|
} |
|
return chars; |
|
} |
|
|
|
var chars1 = diff_linesToCharsMunge(text1); |
|
var chars2 = diff_linesToCharsMunge(text2); |
|
return [chars1, chars2, lineArray]; |
|
}; |
|
|
|
|
|
/** |
|
* Rehydrate the text in a diff from a string of line hashes to real lines of |
|
* text. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @param {Array.<string>} lineArray Array of unique strings. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_charsToLines = function(diffs, lineArray) { |
|
for (var x = 0; x < diffs.length; x++) { |
|
var chars = diffs[x][1]; |
|
var text = []; |
|
for (var y = 0; y < chars.length; y++) { |
|
text[y] = lineArray[chars.charCodeAt(y)]; |
|
} |
|
diffs[x][1] = text.join(''); |
|
} |
|
}; |
|
|
|
|
|
/** |
|
* Explore the intersection points between the two texts. |
|
* @param {string} text1 Old string to be diffed. |
|
* @param {string} text2 New string to be diffed. |
|
* @return {?Array.<Array.<number|string>>} Array of diff tuples or null if no |
|
* diff available. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_map = function(text1, text2) { |
|
// Don't run for too long. |
|
var ms_end = (new Date()).getTime() + this.Diff_Timeout * 1000; |
|
// Cache the text lengths to prevent multiple calls. |
|
var text1_length = text1.length; |
|
var text2_length = text2.length; |
|
var max_d = text1_length + text2_length - 1; |
|
var doubleEnd = this.Diff_DualThreshold * 2 < max_d; |
|
// JavaScript efficiency note: (x << 32) + y doesn't work since numbers are |
|
// only 32 bit. Use x + ',' + y to create a hash instead. |
|
var v_map1 = []; |
|
var v_map2 = []; |
|
var v1 = {}; |
|
var v2 = {}; |
|
v1[1] = 0; |
|
v2[1] = 0; |
|
var x, y; |
|
var footstep; // Used to track overlapping paths. |
|
var footsteps = {}; |
|
var done = false; |
|
// If the total number of characters is odd, then the front path will collide |
|
// with the reverse path. |
|
var front = (text1_length + text2_length) % 2; |
|
for (var d = 0; d < max_d; d++) { |
|
// Bail out if timeout reached. |
|
if (this.Diff_Timeout > 0 && (new Date()).getTime() > ms_end) { |
|
return null; |
|
} |
|
|
|
// Walk the front path one step. |
|
v_map1[d] = {}; |
|
for (var k = -d; k <= d; k += 2) { |
|
if (k == -d || k != d && v1[k - 1] < v1[k + 1]) { |
|
x = v1[k + 1]; |
|
} else { |
|
x = v1[k - 1] + 1; |
|
} |
|
y = x - k; |
|
if (doubleEnd) { |
|
footstep = x + ',' + y; |
|
if (front && footsteps[footstep] !== undefined) { |
|
done = true; |
|
} |
|
if (!front) { |
|
footsteps[footstep] = d; |
|
} |
|
} |
|
while (!done && x < text1_length && y < text2_length && |
|
text1.charAt(x) == text2.charAt(y)) { |
|
x++; |
|
y++; |
|
if (doubleEnd) { |
|
footstep = x + ',' + y; |
|
if (front && footsteps[footstep] !== undefined) { |
|
done = true; |
|
} |
|
if (!front) { |
|
footsteps[footstep] = d; |
|
} |
|
} |
|
} |
|
v1[k] = x; |
|
v_map1[d][x + ',' + y] = true; |
|
if (x == text1_length && y == text2_length) { |
|
// Reached the end in single-path mode. |
|
return this.diff_path1(v_map1, text1, text2); |
|
} else if (done) { |
|
// Front path ran over reverse path. |
|
v_map2 = v_map2.slice(0, footsteps[footstep] + 1); |
|
var a = this.diff_path1(v_map1, text1.substring(0, x), |
|
text2.substring(0, y)); |
|
return a.concat(this.diff_path2(v_map2, text1.substring(x), |
|
text2.substring(y))); |
|
} |
|
} |
|
|
|
if (doubleEnd) { |
|
// Walk the reverse path one step. |
|
v_map2[d] = {}; |
|
for (var k = -d; k <= d; k += 2) { |
|
if (k == -d || k != d && v2[k - 1] < v2[k + 1]) { |
|
x = v2[k + 1]; |
|
} else { |
|
x = v2[k - 1] + 1; |
|
} |
|
y = x - k; |
|
footstep = (text1_length - x) + ',' + (text2_length - y); |
|
if (!front && footsteps[footstep] !== undefined) { |
|
done = true; |
|
} |
|
if (front) { |
|
footsteps[footstep] = d; |
|
} |
|
while (!done && x < text1_length && y < text2_length && |
|
text1.charAt(text1_length - x - 1) == |
|
text2.charAt(text2_length - y - 1)) { |
|
x++; |
|
y++; |
|
footstep = (text1_length - x) + ',' + (text2_length - y); |
|
if (!front && footsteps[footstep] !== undefined) { |
|
done = true; |
|
} |
|
if (front) { |
|
footsteps[footstep] = d; |
|
} |
|
} |
|
v2[k] = x; |
|
v_map2[d][x + ',' + y] = true; |
|
if (done) { |
|
// Reverse path ran over front path. |
|
v_map1 = v_map1.slice(0, footsteps[footstep] + 1); |
|
var a = this.diff_path1(v_map1, text1.substring(0, text1_length - x), |
|
text2.substring(0, text2_length - y)); |
|
return a.concat(this.diff_path2(v_map2, |
|
text1.substring(text1_length - x), |
|
text2.substring(text2_length - y))); |
|
} |
|
} |
|
} |
|
} |
|
// Number of diffs equals number of characters, no commonality at all. |
|
return null; |
|
}; |
|
|
|
|
|
/** |
|
* Work from the middle back to the start to determine the path. |
|
* @param {Array.<Object>} v_map Array of paths. |
|
* @param {string} text1 Old string fragment to be diffed. |
|
* @param {string} text2 New string fragment to be diffed. |
|
* @return {Array.<Array.<number|string>>} Array of diff tuples. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_path1 = function(v_map, text1, text2) { |
|
var path = []; |
|
var x = text1.length; |
|
var y = text2.length; |
|
/** @type {?number} */ |
|
var last_op = null; |
|
for (var d = v_map.length - 2; d >= 0; d--) { |
|
while (1) { |
|
if (v_map[d][(x - 1) + ',' + y] !== undefined) { |
|
x--; |
|
if (last_op === DIFF_DELETE) { |
|
path[0][1] = text1.charAt(x) + path[0][1]; |
|
} else { |
|
path.unshift([DIFF_DELETE, text1.charAt(x)]); |
|
} |
|
last_op = DIFF_DELETE; |
|
break; |
|
} else if (v_map[d][x + ',' + (y - 1)] !== undefined) { |
|
y--; |
|
if (last_op === DIFF_INSERT) { |
|
path[0][1] = text2.charAt(y) + path[0][1]; |
|
} else { |
|
path.unshift([DIFF_INSERT, text2.charAt(y)]); |
|
} |
|
last_op = DIFF_INSERT; |
|
break; |
|
} else { |
|
x--; |
|
y--; |
|
if (text1.charAt(x) != text2.charAt(y)) { |
|
throw new Error('No diagonal. Can\'t happen. (diff_path1)'); |
|
} |
|
if (last_op === DIFF_EQUAL) { |
|
path[0][1] = text1.charAt(x) + path[0][1]; |
|
} else { |
|
path.unshift([DIFF_EQUAL, text1.charAt(x)]); |
|
} |
|
last_op = DIFF_EQUAL; |
|
} |
|
} |
|
} |
|
return path; |
|
}; |
|
|
|
|
|
/** |
|
* Work from the middle back to the end to determine the path. |
|
* @param {Array.<Object>} v_map Array of paths. |
|
* @param {string} text1 Old string fragment to be diffed. |
|
* @param {string} text2 New string fragment to be diffed. |
|
* @return {Array.<Array.<number|string>>} Array of diff tuples. |
|
* @private |
|
*/ |
|
diff_match_patch.prototype.diff_path2 = function(v_map, text1, text2) { |
|
var path = []; |
|
var pathLength = 0; |
|
var x = text1.length; |
|
var y = text2.length; |
|
/** @type {?number} */ |
|
var last_op = null; |
|
for (var d = v_map.length - 2; d >= 0; d--) { |
|
while (1) { |
|
if (v_map[d][(x - 1) + ',' + y] !== undefined) { |
|
x--; |
|
if (last_op === DIFF_DELETE) { |
|
path[pathLength - 1][1] += text1.charAt(text1.length - x - 1); |
|
} else { |
|
path[pathLength++] = |
|
[DIFF_DELETE, text1.charAt(text1.length - x - 1)]; |
|
} |
|
last_op = DIFF_DELETE; |
|
break; |
|
} else if (v_map[d][x + ',' + (y - 1)] !== undefined) { |
|
y--; |
|
if (last_op === DIFF_INSERT) { |
|
path[pathLength - 1][1] += text2.charAt(text2.length - y - 1); |
|
} else { |
|
path[pathLength++] = |
|
[DIFF_INSERT, text2.charAt(text2.length - y - 1)]; |
|
} |
|
last_op = DIFF_INSERT; |
|
break; |
|
} else { |
|
x--; |
|
y--; |
|
if (text1.charAt(text1.length - x - 1) != |
|
text2.charAt(text2.length - y - 1)) { |
|
throw new Error('No diagonal. Can\'t happen. (diff_path2)'); |
|
} |
|
if (last_op === DIFF_EQUAL) { |
|
path[pathLength - 1][1] += text1.charAt(text1.length - x - 1); |
|
} else { |
|
path[pathLength++] = |
|
[DIFF_EQUAL, text1.charAt(text1.length - x - 1)]; |
|
} |
|
last_op = DIFF_EQUAL; |
|
} |
|
} |
|
} |
|
return path; |
|
}; |
|
|
|
|
|
/** |
|
* Determine the common prefix of two strings |
|
* @param {string} text1 First string. |
|
* @param {string} text2 Second string. |
|
* @return {number} The number of characters common to the start of each |
|
* string. |
|
*/ |
|
diff_match_patch.prototype.diff_commonPrefix = function(text1, text2) { |
|
// Quick check for common null cases. |
|
if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) { |
|
return 0; |
|
} |
|
// Binary search. |
|
// Performance analysis: http://neil.fraser.name/news/2007/10/09/ |
|
var pointermin = 0; |
|
var pointermax = Math.min(text1.length, text2.length); |
|
var pointermid = pointermax; |
|
var pointerstart = 0; |
|
while (pointermin < pointermid) { |
|
if (text1.substring(pointerstart, pointermid) == |
|
text2.substring(pointerstart, pointermid)) { |
|
pointermin = pointermid; |
|
pointerstart = pointermin; |
|
} else { |
|
pointermax = pointermid; |
|
} |
|
pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin); |
|
} |
|
return pointermid; |
|
}; |
|
|
|
|
|
/** |
|
* Determine the common suffix of two strings |
|
* @param {string} text1 First string. |
|
* @param {string} text2 Second string. |
|
* @return {number} The number of characters common to the end of each string. |
|
*/ |
|
diff_match_patch.prototype.diff_commonSuffix = function(text1, text2) { |
|
// Quick check for common null cases. |
|
if (!text1 || !text2 || text1.charAt(text1.length - 1) != |
|
text2.charAt(text2.length - 1)) { |
|
return 0; |
|
} |
|
// Binary search. |
|
// Performance analysis: http://neil.fraser.name/news/2007/10/09/ |
|
var pointermin = 0; |
|
var pointermax = Math.min(text1.length, text2.length); |
|
var pointermid = pointermax; |
|
var pointerend = 0; |
|
while (pointermin < pointermid) { |
|
if (text1.substring(text1.length - pointermid, text1.length - pointerend) == |
|
text2.substring(text2.length - pointermid, text2.length - pointerend)) { |
|
pointermin = pointermid; |
|
pointerend = pointermin; |
|
} else { |
|
pointermax = pointermid; |
|
} |
|
pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin); |
|
} |
|
return pointermid; |
|
}; |
|
|
|
|
|
/** |
|
* Do the two texts share a substring which is at least half the length of the |
|
* longer text? |
|
* @param {string} text1 First string. |
|
* @param {string} text2 Second string. |
|
* @return {?Array.<string>} Five element Array, containing the prefix of |
|
* text1, the suffix of text1, the prefix of text2, the suffix of |
|
* text2 and the common middle. Or null if there was no match. |
|
*/ |
|
diff_match_patch.prototype.diff_halfMatch = function(text1, text2) { |
|
var longtext = text1.length > text2.length ? text1 : text2; |
|
var shorttext = text1.length > text2.length ? text2 : text1; |
|
if (longtext.length < 10 || shorttext.length < 1) { |
|
return null; // Pointless. |
|
} |
|
var dmp = this; // 'this' becomes 'window' in a closure. |
|
|
|
/** |
|
* Does a substring of shorttext exist within longtext such that the substring |
|
* is at least half the length of longtext? |
|
* Closure, but does not reference any external variables. |
|
* @param {string} longtext Longer string. |
|
* @param {string} shorttext Shorter string. |
|
* @param {number} i Start index of quarter length substring within longtext |
|
* @return {?Array.<string>} Five element Array, containing the prefix of |
|
* longtext, the suffix of longtext, the prefix of shorttext, the suffix |
|
* of shorttext and the common middle. Or null if there was no match. |
|
* @private |
|
*/ |
|
function diff_halfMatchI(longtext, shorttext, i) { |
|
// Start with a 1/4 length substring at position i as a seed. |
|
var seed = longtext.substring(i, i + Math.floor(longtext.length / 4)); |
|
var j = -1; |
|
var best_common = ''; |
|
var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b; |
|
while ((j = shorttext.indexOf(seed, j + 1)) != -1) { |
|
var prefixLength = dmp.diff_commonPrefix(longtext.substring(i), |
|
shorttext.substring(j)); |
|
var suffixLength = dmp.diff_commonSuffix(longtext.substring(0, i), |
|
shorttext.substring(0, j)); |
|
if (best_common.length < suffixLength + prefixLength) { |
|
best_common = shorttext.substring(j - suffixLength, j) + |
|
shorttext.substring(j, j + prefixLength); |
|
best_longtext_a = longtext.substring(0, i - suffixLength); |
|
best_longtext_b = longtext.substring(i + prefixLength); |
|
best_shorttext_a = shorttext.substring(0, j - suffixLength); |
|
best_shorttext_b = shorttext.substring(j + prefixLength); |
|
} |
|
} |
|
if (best_common.length >= longtext.length / 2) { |
|
return [best_longtext_a, best_longtext_b, |
|
best_shorttext_a, best_shorttext_b, best_common]; |
|
} else { |
|
return null; |
|
} |
|
} |
|
|
|
// First check if the second quarter is the seed for a half-match. |
|
var hm1 = diff_halfMatchI(longtext, shorttext, |
|
Math.ceil(longtext.length / 4)); |
|
// Check again based on the third quarter. |
|
var hm2 = diff_halfMatchI(longtext, shorttext, |
|
Math.ceil(longtext.length / 2)); |
|
var hm; |
|
if (!hm1 && !hm2) { |
|
return null; |
|
} else if (!hm2) { |
|
hm = hm1; |
|
} else if (!hm1) { |
|
hm = hm2; |
|
} else { |
|
// Both matched. Select the longest. |
|
hm = hm1[4].length > hm2[4].length ? hm1 : hm2; |
|
} |
|
|
|
// A half-match was found, sort out the return data. |
|
var text1_a, text1_b, text2_a, text2_b; |
|
if (text1.length > text2.length) { |
|
text1_a = hm[0]; |
|
text1_b = hm[1]; |
|
text2_a = hm[2]; |
|
text2_b = hm[3]; |
|
} else { |
|
text2_a = hm[0]; |
|
text2_b = hm[1]; |
|
text1_a = hm[2]; |
|
text1_b = hm[3]; |
|
} |
|
var mid_common = hm[4]; |
|
return [text1_a, text1_b, text2_a, text2_b, mid_common]; |
|
}; |
|
|
|
|
|
/** |
|
* Reduce the number of edits by eliminating semantically trivial equalities. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
*/ |
|
diff_match_patch.prototype.diff_cleanupSemantic = function(diffs) { |
|
var changes = false; |
|
var equalities = []; // Stack of indices where equalities are found. |
|
var equalitiesLength = 0; // Keeping our own length var is faster in JS. |
|
var lastequality = null; // Always equal to equalities[equalitiesLength-1][1] |
|
var pointer = 0; // Index of current position. |
|
// Number of characters that changed prior to the equality. |
|
var length_changes1 = 0; |
|
// Number of characters that changed after the equality. |
|
var length_changes2 = 0; |
|
while (pointer < diffs.length) { |
|
if (diffs[pointer][0] == DIFF_EQUAL) { // equality found |
|
equalities[equalitiesLength++] = pointer; |
|
length_changes1 = length_changes2; |
|
length_changes2 = 0; |
|
lastequality = diffs[pointer][1]; |
|
} else { // an insertion or deletion |
|
length_changes2 += diffs[pointer][1].length; |
|
if (lastequality !== null && (lastequality.length <= length_changes1) && |
|
(lastequality.length <= length_changes2)) { |
|
// Duplicate record |
|
diffs.splice(equalities[equalitiesLength - 1], 0, |
|
[DIFF_DELETE, lastequality]); |
|
// Change second copy to insert. |
|
diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT; |
|
// Throw away the equality we just deleted. |
|
equalitiesLength--; |
|
// Throw away the previous equality (it needs to be reevaluated). |
|
equalitiesLength--; |
|
pointer = equalitiesLength > 0 ? equalities[equalitiesLength - 1] : -1; |
|
length_changes1 = 0; // Reset the counters. |
|
length_changes2 = 0; |
|
lastequality = null; |
|
changes = true; |
|
} |
|
} |
|
pointer++; |
|
} |
|
if (changes) { |
|
this.diff_cleanupMerge(diffs); |
|
} |
|
this.diff_cleanupSemanticLossless(diffs); |
|
}; |
|
|
|
|
|
/** |
|
* Look for single edits surrounded on both sides by equalities |
|
* which can be shifted sideways to align the edit to a word boundary. |
|
* e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
*/ |
|
diff_match_patch.prototype.diff_cleanupSemanticLossless = function(diffs) { |
|
// Define some regex patterns for matching boundaries. |
|
var punctuation = /[^a-zA-Z0-9]/; |
|
var whitespace = /\s/; |
|
var linebreak = /[\r\n]/; |
|
var blanklineEnd = /\n\r?\n$/; |
|
var blanklineStart = /^\r?\n\r?\n/; |
|
|
|
/** |
|
* Given two strings, compute a score representing whether the internal |
|
* boundary falls on logical boundaries. |
|
* Scores range from 5 (best) to 0 (worst). |
|
* Closure, makes reference to regex patterns defined above. |
|
* @param {string} one First string. |
|
* @param {string} two Second string. |
|
* @return {number} The score. |
|
*/ |
|
function diff_cleanupSemanticScore(one, two) { |
|
if (!one || !two) { |
|
// Edges are the best. |
|
return 5; |
|
} |
|
|
|
// Each port of this function behaves slightly differently due to |
|
// subtle differences in each language's definition of things like |
|
// 'whitespace'. Since this function's purpose is largely cosmetic, |
|
// the choice has been made to use each language's native features |
|
// rather than force total conformity. |
|
var score = 0; |
|
// One point for non-alphanumeric. |
|
if (one.charAt(one.length - 1).match(punctuation) || |
|
two.charAt(0).match(punctuation)) { |
|
score++; |
|
// Two points for whitespace. |
|
if (one.charAt(one.length - 1).match(whitespace) || |
|
two.charAt(0).match(whitespace)) { |
|
score++; |
|
// Three points for line breaks. |
|
if (one.charAt(one.length - 1).match(linebreak) || |
|
two.charAt(0).match(linebreak)) { |
|
score++; |
|
// Four points for blank lines. |
|
if (one.match(blanklineEnd) || two.match(blanklineStart)) { |
|
score++; |
|
} |
|
} |
|
} |
|
} |
|
return score; |
|
} |
|
|
|
var pointer = 1; |
|
// Intentionally ignore the first and last element (don't need checking). |
|
while (pointer < diffs.length - 1) { |
|
if (diffs[pointer - 1][0] == DIFF_EQUAL && |
|
diffs[pointer + 1][0] == DIFF_EQUAL) { |
|
// This is a single edit surrounded by equalities. |
|
var equality1 = diffs[pointer - 1][1]; |
|
var edit = diffs[pointer][1]; |
|
var equality2 = diffs[pointer + 1][1]; |
|
|
|
// First, shift the edit as far left as possible. |
|
var commonOffset = this.diff_commonSuffix(equality1, edit); |
|
if (commonOffset) { |
|
var commonString = edit.substring(edit.length - commonOffset); |
|
equality1 = equality1.substring(0, equality1.length - commonOffset); |
|
edit = commonString + edit.substring(0, edit.length - commonOffset); |
|
equality2 = commonString + equality2; |
|
} |
|
|
|
// Second, step character by character right, looking for the best fit. |
|
var bestEquality1 = equality1; |
|
var bestEdit = edit; |
|
var bestEquality2 = equality2; |
|
var bestScore = diff_cleanupSemanticScore(equality1, edit) + |
|
diff_cleanupSemanticScore(edit, equality2); |
|
while (edit.charAt(0) === equality2.charAt(0)) { |
|
equality1 += edit.charAt(0); |
|
edit = edit.substring(1) + equality2.charAt(0); |
|
equality2 = equality2.substring(1); |
|
var score = diff_cleanupSemanticScore(equality1, edit) + |
|
diff_cleanupSemanticScore(edit, equality2); |
|
// The >= encourages trailing rather than leading whitespace on edits. |
|
if (score >= bestScore) { |
|
bestScore = score; |
|
bestEquality1 = equality1; |
|
bestEdit = edit; |
|
bestEquality2 = equality2; |
|
} |
|
} |
|
|
|
if (diffs[pointer - 1][1] != bestEquality1) { |
|
// We have an improvement, save it back to the diff. |
|
if (bestEquality1) { |
|
diffs[pointer - 1][1] = bestEquality1; |
|
} else { |
|
diffs.splice(pointer - 1, 1); |
|
pointer--; |
|
} |
|
diffs[pointer][1] = bestEdit; |
|
if (bestEquality2) { |
|
diffs[pointer + 1][1] = bestEquality2; |
|
} else { |
|
diffs.splice(pointer + 1, 1); |
|
pointer--; |
|
} |
|
} |
|
} |
|
pointer++; |
|
} |
|
}; |
|
|
|
|
|
/** |
|
* Reduce the number of edits by eliminating operationally trivial equalities. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
*/ |
|
diff_match_patch.prototype.diff_cleanupEfficiency = function(diffs) { |
|
var changes = false; |
|
var equalities = []; // Stack of indices where equalities are found. |
|
var equalitiesLength = 0; // Keeping our own length var is faster in JS. |
|
var lastequality = ''; // Always equal to equalities[equalitiesLength-1][1] |
|
var pointer = 0; // Index of current position. |
|
// Is there an insertion operation before the last equality. |
|
var pre_ins = false; |
|
// Is there a deletion operation before the last equality. |
|
var pre_del = false; |
|
// Is there an insertion operation after the last equality. |
|
var post_ins = false; |
|
// Is there a deletion operation after the last equality. |
|
var post_del = false; |
|
while (pointer < diffs.length) { |
|
if (diffs[pointer][0] == DIFF_EQUAL) { // equality found |
|
if (diffs[pointer][1].length < this.Diff_EditCost && |
|
(post_ins || post_del)) { |
|
// Candidate found. |
|
equalities[equalitiesLength++] = pointer; |
|
pre_ins = post_ins; |
|
pre_del = post_del; |
|
lastequality = diffs[pointer][1]; |
|
} else { |
|
// Not a candidate, and can never become one. |
|
equalitiesLength = 0; |
|
lastequality = ''; |
|
} |
|
post_ins = post_del = false; |
|
} else { // an insertion or deletion |
|
if (diffs[pointer][0] == DIFF_DELETE) { |
|
post_del = true; |
|
} else { |
|
post_ins = true; |
|
} |
|
/* |
|
* Five types to be split: |
|
* <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del> |
|
* <ins>A</ins>X<ins>C</ins><del>D</del> |
|
* <ins>A</ins><del>B</del>X<ins>C</ins> |
|
* <ins>A</del>X<ins>C</ins><del>D</del> |
|
* <ins>A</ins><del>B</del>X<del>C</del> |
|
*/ |
|
if (lastequality && ((pre_ins && pre_del && post_ins && post_del) || |
|
((lastequality.length < this.Diff_EditCost / 2) && |
|
(pre_ins + pre_del + post_ins + post_del) == 3))) { |
|
// Duplicate record |
|
diffs.splice(equalities[equalitiesLength - 1], 0, |
|
[DIFF_DELETE, lastequality]); |
|
// Change second copy to insert. |
|
diffs[equalities[equalitiesLength - 1] + 1][0] = DIFF_INSERT; |
|
equalitiesLength--; // Throw away the equality we just deleted; |
|
lastequality = ''; |
|
if (pre_ins && pre_del) { |
|
// No changes made which could affect previous entry, keep going. |
|
post_ins = post_del = true; |
|
equalitiesLength = 0; |
|
} else { |
|
equalitiesLength--; // Throw away the previous equality; |
|
pointer = equalitiesLength > 0 ? |
|
equalities[equalitiesLength - 1] : -1; |
|
post_ins = post_del = false; |
|
} |
|
changes = true; |
|
} |
|
} |
|
pointer++; |
|
} |
|
|
|
if (changes) { |
|
this.diff_cleanupMerge(diffs); |
|
} |
|
}; |
|
|
|
|
|
/** |
|
* Reorder and merge like edit sections. Merge equalities. |
|
* Any edit section can move as long as it doesn't cross an equality. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
*/ |
|
diff_match_patch.prototype.diff_cleanupMerge = function(diffs) { |
|
diffs.push([DIFF_EQUAL, '']); // Add a dummy entry at the end. |
|
var pointer = 0; |
|
var count_delete = 0; |
|
var count_insert = 0; |
|
var text_delete = ''; |
|
var text_insert = ''; |
|
var commonlength; |
|
while (pointer < diffs.length) { |
|
switch (diffs[pointer][0]) { |
|
case DIFF_INSERT: |
|
count_insert++; |
|
text_insert += diffs[pointer][1]; |
|
pointer++; |
|
break; |
|
case DIFF_DELETE: |
|
count_delete++; |
|
text_delete += diffs[pointer][1]; |
|
pointer++; |
|
break; |
|
case DIFF_EQUAL: |
|
// Upon reaching an equality, check for prior redundancies. |
|
if (count_delete !== 0 || count_insert !== 0) { |
|
if (count_delete !== 0 && count_insert !== 0) { |
|
// Factor out any common prefixies. |
|
commonlength = this.diff_commonPrefix(text_insert, text_delete); |
|
if (commonlength !== 0) { |
|
if ((pointer - count_delete - count_insert) > 0 && |
|
diffs[pointer - count_delete - count_insert - 1][0] == |
|
DIFF_EQUAL) { |
|
diffs[pointer - count_delete - count_insert - 1][1] += |
|
text_insert.substring(0, commonlength); |
|
} else { |
|
diffs.splice(0, 0, [DIFF_EQUAL, |
|
text_insert.substring(0, commonlength)]); |
|
pointer++; |
|
} |
|
text_insert = text_insert.substring(commonlength); |
|
text_delete = text_delete.substring(commonlength); |
|
} |
|
// Factor out any common suffixies. |
|
commonlength = this.diff_commonSuffix(text_insert, text_delete); |
|
if (commonlength !== 0) { |
|
diffs[pointer][1] = text_insert.substring(text_insert.length - |
|
commonlength) + diffs[pointer][1]; |
|
text_insert = text_insert.substring(0, text_insert.length - |
|
commonlength); |
|
text_delete = text_delete.substring(0, text_delete.length - |
|
commonlength); |
|
} |
|
} |
|
// Delete the offending records and add the merged ones. |
|
if (count_delete === 0) { |
|
diffs.splice(pointer - count_delete - count_insert, |
|
count_delete + count_insert, [DIFF_INSERT, text_insert]); |
|
} else if (count_insert === 0) { |
|
diffs.splice(pointer - count_delete - count_insert, |
|
count_delete + count_insert, [DIFF_DELETE, text_delete]); |
|
} else { |
|
diffs.splice(pointer - count_delete - count_insert, |
|
count_delete + count_insert, [DIFF_DELETE, text_delete], |
|
[DIFF_INSERT, text_insert]); |
|
} |
|
pointer = pointer - count_delete - count_insert + |
|
(count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1; |
|
} else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) { |
|
// Merge this equality with the previous one. |
|
diffs[pointer - 1][1] += diffs[pointer][1]; |
|
diffs.splice(pointer, 1); |
|
} else { |
|
pointer++; |
|
} |
|
count_insert = 0; |
|
count_delete = 0; |
|
text_delete = ''; |
|
text_insert = ''; |
|
break; |
|
} |
|
} |
|
if (diffs[diffs.length - 1][1] === '') { |
|
diffs.pop(); // Remove the dummy entry at the end. |
|
} |
|
|
|
// Second pass: look for single edits surrounded on both sides by equalities |
|
// which can be shifted sideways to eliminate an equality. |
|
// e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC |
|
var changes = false; |
|
pointer = 1; |
|
// Intentionally ignore the first and last element (don't need checking). |
|
while (pointer < diffs.length - 1) { |
|
if (diffs[pointer - 1][0] == DIFF_EQUAL && |
|
diffs[pointer + 1][0] == DIFF_EQUAL) { |
|
// This is a single edit surrounded by equalities. |
|
if (diffs[pointer][1].substring(diffs[pointer][1].length - |
|
diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) { |
|
// Shift the edit over the previous equality. |
|
diffs[pointer][1] = diffs[pointer - 1][1] + |
|
diffs[pointer][1].substring(0, diffs[pointer][1].length - |
|
diffs[pointer - 1][1].length); |
|
diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1]; |
|
diffs.splice(pointer - 1, 1); |
|
changes = true; |
|
} else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) == |
|
diffs[pointer + 1][1]) { |
|
// Shift the edit over the next equality. |
|
diffs[pointer - 1][1] += diffs[pointer + 1][1]; |
|
diffs[pointer][1] = |
|
diffs[pointer][1].substring(diffs[pointer + 1][1].length) + |
|
diffs[pointer + 1][1]; |
|
diffs.splice(pointer + 1, 1); |
|
changes = true; |
|
} |
|
} |
|
pointer++; |
|
} |
|
// If shifts were made, the diff needs reordering and another shift sweep. |
|
if (changes) { |
|
this.diff_cleanupMerge(diffs); |
|
} |
|
}; |
|
|
|
|
|
/** |
|
* loc is a location in text1, compute and return the equivalent location in |
|
* text2. |
|
* e.g. 'The cat' vs 'The big cat', 1->1, 5->8 |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @param {number} loc Location within text1. |
|
* @return {number} Location within text2. |
|
*/ |
|
diff_match_patch.prototype.diff_xIndex = function(diffs, loc) { |
|
var chars1 = 0; |
|
var chars2 = 0; |
|
var last_chars1 = 0; |
|
var last_chars2 = 0; |
|
var x; |
|
for (x = 0; x < diffs.length; x++) { |
|
if (diffs[x][0] !== DIFF_INSERT) { // Equality or deletion. |
|
chars1 += diffs[x][1].length; |
|
} |
|
if (diffs[x][0] !== DIFF_DELETE) { // Equality or insertion. |
|
chars2 += diffs[x][1].length; |
|
} |
|
if (chars1 > loc) { // Overshot the location. |
|
break; |
|
} |
|
last_chars1 = chars1; |
|
last_chars2 = chars2; |
|
} |
|
// Was the location was deleted? |
|
if (diffs.length != x && diffs[x][0] === DIFF_DELETE) { |
|
return last_chars2; |
|
} |
|
// Add the remaining character length. |
|
return last_chars2 + (loc - last_chars1); |
|
}; |
|
|
|
|
|
/** |
|
* Convert a diff array into a pretty HTML report. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @return {string} HTML representation. |
|
*/ |
|
diff_match_patch.prototype.diff_prettyHtml = function(diffs) { |
|
var html = []; |
|
var i = 0; |
|
for (var x = 0; x < diffs.length; x++) { |
|
var op = diffs[x][0]; // Operation (insert, delete, equal) |
|
var data = diffs[x][1]; // Text of change. |
|
var text = data.replace(/&/g, '&').replace(/</g, '<') |
|
.replace(/>/g, '>').replace(/\n/g, '¶<BR>'); |
|
switch (op) { |
|
case DIFF_INSERT: |
|
html[x] = '<INS STYLE="background:#E6FFE6;" TITLE="i=' + i + '">' + |
|
text + '</INS>'; |
|
break; |
|
case DIFF_DELETE: |
|
html[x] = '<DEL STYLE="background:#FFE6E6;" TITLE="i=' + i + '">' + |
|
text + '</DEL>'; |
|
break; |
|
case DIFF_EQUAL: |
|
html[x] = '<SPAN TITLE="i=' + i + '">' + text + '</SPAN>'; |
|
break; |
|
} |
|
if (op !== DIFF_DELETE) { |
|
i += data.length; |
|
} |
|
} |
|
return html.join(''); |
|
}; |
|
|
|
|
|
/** |
|
* Compute and return the source text (all equalities and deletions). |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @return {string} Source text. |
|
*/ |
|
diff_match_patch.prototype.diff_text1 = function(diffs) { |
|
var text = []; |
|
for (var x = 0; x < diffs.length; x++) { |
|
if (diffs[x][0] !== DIFF_INSERT) { |
|
text[x] = diffs[x][1]; |
|
} |
|
} |
|
return text.join(''); |
|
}; |
|
|
|
|
|
/** |
|
* Compute and return the destination text (all equalities and insertions). |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @return {string} Destination text. |
|
*/ |
|
diff_match_patch.prototype.diff_text2 = function(diffs) { |
|
var text = []; |
|
for (var x = 0; x < diffs.length; x++) { |
|
if (diffs[x][0] !== DIFF_DELETE) { |
|
text[x] = diffs[x][1]; |
|
} |
|
} |
|
return text.join(''); |
|
}; |
|
|
|
|
|
/** |
|
* Compute the Levenshtein distance; the number of inserted, deleted or |
|
* substituted characters. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @return {number} Number of changes. |
|
*/ |
|
diff_match_patch.prototype.diff_levenshtein = function(diffs) { |
|
var levenshtein = 0; |
|
var insertions = 0; |
|
var deletions = 0; |
|
for (var x = 0; x < diffs.length; x++) { |
|
var op = diffs[x][0]; |
|
var data = diffs[x][1]; |
|
switch (op) { |
|
case DIFF_INSERT: |
|
insertions += data.length; |
|
break; |
|
case DIFF_DELETE: |
|
deletions += data.length; |
|
break; |
|
case DIFF_EQUAL: |
|
// A deletion and an insertion is one substitution. |
|
levenshtein += Math.max(insertions, deletions); |
|
insertions = 0; |
|
deletions = 0; |
|
break; |
|
} |
|
} |
|
levenshtein += Math.max(insertions, deletions); |
|
return levenshtein; |
|
}; |
|
|
|
|
|
/** |
|
* Crush the diff into an encoded string which describes the operations |
|
* required to transform text1 into text2. |
|
* E.g. =3\t-2\t+ing -> Keep 3 chars, delete 2 chars, insert 'ing'. |
|
* Operations are tab-separated. Inserted text is escaped using %xx notation. |
|
* @param {Array.<Array.<number|string>>} diffs Array of diff tuples. |
|
* @return {string} Delta text. |
|
*/ |
|
diff_match_patch.prototype.diff_toDelta = function(diffs) { |
|
var text = []; |
|
for (var x = 0; x < diffs.length; x++) { |
|
switch (diffs[x][0]) { |
|
case DIFF_INSERT: |
|
text[x] = '+' + encodeURI(diffs[x][1]); |
|
break; |
|
case DIFF_DELETE: |
|
text[x] = '-' + diffs[x][1].length; |
|
break; |
|
case DIFF_EQUAL: |
|
text[x] = '=' + diffs[x][1].length; |
|
break; |
|
} |
|
} |
|
// Opera doesn't know how to encode char 0. |
|
return text.join('\t').replace(/\x00/g, '%00').replace(/%20/g, ' '); |
|
}; |
|
|
|
|
|
/** |
|
* Given the original text1, and an encoded string which describes the |
|
* operations required to transform text1 into text2, compute the full diff. |
|
* @param {string} text1 Source string for the diff. |
|
* @param {string} delta Delta text. |
|
* @return {Array.<Array.<number|string>>} Array of diff tuples. |
|
* @throws {Error} If invalid input. |
|
*/ |
|
diff_match_patch.prototype.diff_fromDelta = function(text1, delta) { |
|
var diffs = []; |
|
var diffsLength = 0; // Keeping our own length var is faster in JS. |
|
var pointer = 0; // Cursor in text1 |
|
// Opera doesn't know how to decode char 0. |
|
delta = delta.replace(/%00/g, '\0'); |
|
var tokens = delta.split(/\t/g); |
|
for (var x = 0; x < tokens.length; x++) { |
|
// Each token begins with a one character parameter which specifies the |
|
// operation of this token (delete, insert, equality). |
|
var param = tokens[x].substring(1); |
|
switch (tokens[x].charAt(0)) { |
|
case '+': |
|
try { |
|
diffs[diffsLength++] = [DIFF_INSERT, decodeURI(param)]; |
|
} catch (ex) { |
|
// Malformed URI sequence. |
|
throw new Error('Illegal escape in diff_fromDelta: ' + param); |
|
} |
|
break; |
|
case '-': |
|
// Fall through. |
|
case '=': |
|
var n = parseInt(param, 10); |
|
if (isNaN(n) || n < 0) { |
|
throw new Error('Invalid number in diff_fromDelta: ' + param); |
|
} |
|
var text = text1.substring(pointer, pointer += n); |
|
if (tokens[x].charAt(0) == '=') { |
|
diffs[diffsLength++] = [DIFF_EQUAL, text]; |
|
} else { |
|
diffs[diffsLength++] = [DIFF_DELETE, text]; |
|
} |
|
break; |
|
default: |
|
// Blank tokens are ok (from a trailing \t). |
|
// Anything else is an error. |
|
if (tokens[x]) { |
|
throw new Error('Invalid diff operation in diff_fromDelta: ' + |
|
tokens[x]); |
|
} |
|
} |
|
} |
|
if (pointer != text1.length) { |
|
throw new Error('Delta length (' + pointer + |
|
') does not equal source text length (' + text1.length + ').'); |
|
} |
|
return diffs; |
|
}; |
|
|
|
|
|
// MATCH FUNCTIONS |
|
|
|
|
|
/** |
|
* Locate the best instance of 'pattern' in 'text' near 'loc'. |
|
* @param {string} text The text to search. |
|
* @param {string} pattern The pattern to search for. |
|
* @param {number} loc The location to search around. |
|
* @return {number} Best match index or -1. |
|
*/ |
|
diff_match_patch.prototype.match_main = function(text, pattern, loc) { |
|
// Check for null inputs. |
|
if (text == null || pattern == null || loc == null) { |
|
throw new Error('Null input. (match_main)'); |
|
} |
|
|
|
loc = Math.max(0, Math.min(loc, text.length)); |
|
if (text == pattern) { |
|
// Shortcut (potentially not guaranteed by the algorithm) |
|
return 0; |
|
} else if (!text.length) { |
|
// Nothing to match. |
|
return -1; |
|
} else if (text.substring(loc, loc + pattern.length) == |