1 /*
  2 Copyright (c) 2009 Simon Veith <simon@jinfinote.com>
  3 
  4 Permission is hereby granted, free of charge, to any person obtaining a copy
  5 of this software and associated documentation files (the "Software"), to deal
  6 in the Software without restriction, including without limitation the rights
  7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  8 copies of the Software, and to permit persons to whom the Software is
  9 furnished to do so, subject to the following conditions:
 10 
 11 The above copyright notice and this permission notice shall be included in
 12 all copies or substantial portions of the Software.
 13 
 14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 20 THE SOFTWARE.
 21 */
 22 
 23 /** @namespace
 24  */
 25 Operations = {};
 26 
 27 /** Instantiates a new NoOp operation object.
 28  *  @class An operation that does nothing.
 29  */
 30 Operations.NoOp = function() {};
 31 
 32 Operations.NoOp.prototype.requiresCID = false;
 33 
 34 Operations.NoOp.prototype.toString = function() { return "NoOp()"; };
 35 
 36 Operations.NoOp.prototype.toHTML = Operations.NoOp.prototype.toString;
 37 
 38 /** Applies this NoOp operation to a buffer. This does nothing, per
 39  *  definition. */
 40 Operations.NoOp.prototype.apply = function(buffer) {};
 41 
 42 /** Transforms this NoOp operation against another operation. This returns a
 43  *  new NoOp operation.
 44  *  @type Operations.NoOp
 45  */
 46 Operations.NoOp.prototype.transform = function(other) { 
 47 	return new Operations.NoOp();
 48 };
 49 
 50 /** Mirrors this NoOp operation. This returns a new NoOp operation.
 51  *  @type Operations.NoOp
 52  */
 53 Operations.NoOp.prototype.mirror = function() {
 54 	return new Operations.NoOp();
 55 };
 56 
 57 /** Instantiates a new Insert operation object.
 58  *  @class An operation that inserts a Buffer at a certain offset.
 59  *  @param {Number} position The offset at which the text is to be inserted.
 60  *  @param {Buffer} text The Buffer to insert.
 61  */
 62 Operations.Insert = function(position, text) {
 63 	this.position = position;
 64 	this.text = text.copy();
 65 };
 66 
 67 Operations.Insert.prototype.requiresCID = true;
 68 
 69 Operations.Insert.prototype.toString = function() {
 70 	return "Insert(" + this.position + ", " + this.text + ")";
 71 };
 72 
 73 Operations.Insert.prototype.toHTML = function() {
 74 	return "Insert(" + this.position + ", " + this.text.toHTML() + ")";
 75 };
 76 
 77 /** Applies the insert operation to the given Buffer.
 78  *  @param {Buffer} buffer The buffer in which the insert operation is to be
 79  *  performed.
 80  */
 81 Operations.Insert.prototype.apply = function(buffer) {
 82 	buffer.splice(this.position, 0, this.text);
 83 };
 84 
 85 /** Computes the concurrency ID against another Insert operation.
 86  *  @param {Operations.Insert} other
 87  *  @returns The operation that is to be transformed.
 88  *  @type Operations.Insert
 89  */
 90 Operations.Insert.prototype.cid = function(other) {
 91 	if(this.position < other.position)
 92 		return other;
 93 	if(this.position > other.position)
 94 		return this;
 95 };
 96 
 97 /** Returns the total length of data to be inserted by this insert operation,
 98  *  in characters.
 99  *  @type Number
100  */
101 Operations.Insert.prototype.getLength = function() {
102 	return this.text.getLength();
103 };
104 
105 /** Transforms this Insert operation against another operation, returning the
106  *  resulting operation as a new object.
107  *  @param {Operation} other The operation to transform against.
108  *  @param {Operation} [cid] The cid to take into account in the case of
109  *  conflicts.
110  *  @type Operation
111  */
112 Operations.Insert.prototype.transform = function(other, cid) {
113 	if(other instanceof Operations.NoOp)
114 		return new Operations.Insert(this.position, this.text);
115 	
116 	if(other instanceof Operations.Split) {
117 		// We transform against the first component of the split operation
118 		// first.
119 		var transformFirst = this.transform(other.first,
120 			(cid == this ? this : other.first));
121 		
122 		// The second part of the split operation is transformed against its
123 		// first part.
124 		var newSecond = other.second.transform(other.first);
125 		
126 		var transformSecond = transformFirst.transform(newSecond,
127 			(cid == this ? transformFirst : newSecond));
128 		
129 		return transformSecond;
130 	}
131 	
132 	var pos1 = this.position;
133 	var str1 = this.text;
134 	var pos2 = other.position;
135 	
136 	if(other instanceof Operations.Insert) {
137 		var str2 = other.text;
138 		
139 		if(pos1 < pos2 || (pos1 == pos2 && cid == other))
140 			return new Operations.Insert(pos1, str1);
141 		if(pos1 > pos2 || (pos1 == pos2 && cid == this))
142 			return new Operations.Insert(pos1 + str2.getLength(), str1);
143 	} else if(other instanceof Operations.Delete) {
144 		var len2 = other.getLength();
145 		
146 		if(pos1 >= pos2 + len2)
147 			return new Operations.Insert(pos1 - len2, str1);
148 		if(pos1 < pos2)
149 			return new Operations.Insert(pos1, str1);
150 		if(pos1 >= pos2 && pos1 < pos2 + len2)
151 			return new Operations.Insert(pos2, str1);
152 	}
153 };
154 
155 /** Returns the inversion of this Insert operation.
156  *  @type Operations.Delete
157  */
158 Operations.Insert.prototype.mirror = function() {
159 	return new Operations.Delete(this.position, this.text.copy());
160 };
161 
162 /** Instantiates a new Delete operation object.
163  *  Delete operations can be reversible or not, depending on how they are
164  *  constructed. Delete operations constructed with a Buffer object know which
165  *  text they are removing from the buffer and can therefore be mirrored,
166  *  whereas Delete operations knowing only the amount of characters to be
167  *  removed are non-reversible.
168  *  @class An operation that removes a range of characters in the target
169  *  buffer.
170  *  @param {Number} position The offset of the first character to remove.
171  *  @param what The data to be removed. This can be either a numeric value
172  *  or a Buffer object.
173  */
174 Operations.Delete = function(position, what, recon) {
175 	this.position = position;
176 	
177 	if(what instanceof Buffer)
178 		this.what = what.copy();
179 	else
180 		this.what = what;
181 	
182 	if(recon)
183 		this.recon = recon;
184 	else
185 		this.recon = new Recon();
186 };
187 
188 Operations.Delete.prototype.requiresCID = false;
189 
190 Operations.Delete.prototype.toString = function() {
191 	return "Delete(" + this.position + ", " + this.what + ")";
192 };
193 
194 Operations.Delete.prototype.toHTML = function() {
195 	return "Delete(" + this.position + ", " + 
196 		(this.what instanceof Buffer ? this.what.toHTML() : this.what) + ")";
197 };
198 
199 /** Determines whether this Delete operation is reversible.
200  *  @type Boolean
201  */
202 Operations.Delete.prototype.isReversible = function() {
203 	return (this.what instanceof Buffer);
204 };
205 
206 /** Applies this Delete operation to a buffer.
207  *  @param {Buffer} buffer The buffer to which the operation is to be applied.
208  */
209 Operations.Delete.prototype.apply = function(buffer) {
210 	buffer.splice(this.position, this.getLength());
211 };
212 
213 Operations.Delete.prototype.cid = function(other) {};
214 
215 /** Returns the number of characters that this Delete operation removes.
216  *  @type Number
217  */
218 Operations.Delete.prototype.getLength = function() {
219 	if(this.isReversible())
220 		return this.what.getLength();
221 	else
222 		return this.what;
223 };
224 
225 /** Splits this Delete operation into two Delete operations at the given
226  *  offset. The resulting Split operation will consist of two Delete
227  *  operations which, when combined, affect the same range of text as the
228  *  original Delete operation.
229  *  @param {Number} at Offset at which to split the Delete operation.
230  *  @type Operations.Split
231  */
232 Operations.Delete.prototype.split = function(at) {
233 	if(this.isReversible())
234 	{
235 		// This is a reversible Delete operation. No need to to any
236 		// processing for recon data.
237 		return new Operations.Split(
238 			new Operations.Delete(this.position, this.what.slice(0, at)),
239 			new Operations.Delete(this.position + at, this.what.slice(at))
240 		);
241 	} else {
242 		// This is a non-reversible Delete operation that might carry recon
243 		// data. We need to split that data accordingly between the two new
244 		// components.
245 		var recon1 = new Recon();
246 		var recon2 = new Recon();
247 		
248 		for(index in this.recon.segments)
249 		{
250 			if(this.recon.segments[index].offset < at)
251 				recon1.segments.push(this.recon.segments[index]);
252 			else
253 				recon2.segments.push(
254 					new ReconSegment(this.recon.segments[index].offset - at,
255 						this.recon.segments[index].buffer)
256 				);
257 		}
258 		
259 		return new Operations.Split(
260 			new Operations.Delete(this.position, at, recon1),
261 			new Operations.Delete(this.position + at, this.what - at, recon2)
262 		);
263 	}
264 };
265 
266 /** Returns the range of text in a buffer that this Delete or Split-Delete
267  *  operation removes.
268  *  @param operation A Split-Delete or Delete operation
269  *  @param {Buffer} buffer
270  *  @type Buffer
271  */
272 Operations.Delete.getAffectedString = function(operation, buffer) {
273 	if(operation instanceof Operations.Split)
274 	{
275 		// The other operation is a Split operation. We call this function
276 		// again recursively for each component.
277 		var part1 = Operations.Delete.getAffectedString(operation.first,
278 			buffer);
279 		var part2 = Operations.Delete.getAffectedString(operation.second,
280 			buffer);
281 		
282 		part2.splice(0, 0, part1);
283 		return part2;
284 	} else if (operation instanceof Operations.Delete) {
285 		// In the process of determining the affected string, we also
286 		// have to take into account the data that has been "transformed away"
287 		// from the Delete operation and which is stored in the Recon object.
288 		
289 		var reconBuffer = buffer.slice(operation.position, operation.position
290 			+ operation.getLength());
291 		
292 		operation.recon.restore(reconBuffer);
293 
294 		return reconBuffer;
295 	}
296 };
297 
298 /** Makes this Delete operation reversible, given a transformed version of 
299  *  this operation in a buffer matching its state. If this Delete operation is
300  *  already reversible, this function simply returns a copy of it.
301  *  @param {Operations.Delete} transformed A transformed version of this
302  *  operation.
303  *  @param {State} state The state in which the transformed operation could be
304  *  applied.
305  */
306 Operations.Delete.prototype.makeReversible = function(transformed, state) {
307 	if(this.what instanceof Buffer)
308 		return new Operations.Delete(this.position, this.what);
309 	else {
310 		return new Operations.Delete(this.position, 
311 			Operations.Delete.getAffectedString(transformed, state.buffer)
312 		);
313 	}
314 };
315 
316 /** Merges a Delete operation with another one. The resulting Delete operation
317  *  removes the same range of text as the two separate Delete operations would
318  *  when executed sequentially.
319  *  @param {Operations.Delete} other
320  *  @type Operations.Delete
321  */
322 Operations.Delete.prototype.merge = function(other) {
323 	if(this.isReversible()) {
324 		if(!other.isReversible())
325 			throw "Cannot merge reversible operations with non-reversible ones";
326 		
327 		var newBuffer = this.what.copy();
328 		newBuffer.splice(newBuffer.getLength(), 0, other.what);
329 		return new Operations.Delete(this.position, newBuffer);
330 	} else {
331 		var newLength = this.getLength() + other.getLength();
332 		return new Operations.Delete(this.position, newLength);
333 	}
334 };
335 
336 /** Transforms this Delete operation against another operation.
337  *  @param {Operation} other
338  *  @param {Operation} [cid]
339  */
340 Operations.Delete.prototype.transform = function(other, cid) {
341 	if(other instanceof Operations.NoOp)
342 		return new Operations.Delete(this.position, this.what, this.recon);
343 	
344 	if(other instanceof Operations.Split) {
345 		// We transform against the first component of the split operation
346 		// first.
347 		var transformFirst = this.transform(other.first,
348 			(cid == this ? this : other.first));
349 		
350 		// The second part of the split operation is transformed against its
351 		// first part.
352 		var newSecond = other.second.transform(other.first);
353 		
354 		var transformSecond = transformFirst.transform(newSecond,
355 			(cid == this ? transformFirst : newSecond));
356 		
357 		return transformSecond;
358 	}
359 	
360 	var pos1 = this.position;
361 	var len1 = this.getLength();
362 	
363 	var pos2 = other.position;
364 	var len2 = other.getLength();
365 	
366 	if(other instanceof Operations.Insert)
367 	{
368 		if(pos2 >= pos1 + len1)
369 			return new Operations.Delete(pos1, this.what, this.recon);
370 		if(pos2 <= pos1)
371 			return new Operations.Delete(pos1 + len2, this.what, this.recon);
372 		if(pos2 > pos1 && pos2 < pos1 + len1)
373 		{
374 			var result = this.split(pos2 - pos1);
375 			result.second.position += len2;
376 			return result;
377 		}
378 	} else if(other instanceof Operations.Delete) {
379 		if(pos1 + len1 <= pos2)
380 			return new Operations.Delete(pos1, this.what, this.recon);
381 		if(pos1 >= pos2 + len2)
382 			return new Operations.Delete(pos1 - len2, this.what, this.recon);
383 		if(pos2 <= pos1 && pos2 + len2 >= pos1 + len1) {
384 			/*     1XXXXX|
385 			 * 2-------------|
386 			 *
387 			 * This operation falls completely within the range of another,
388 			 * i.e. all data has already been removed. The resulting
389 			 * operation removes nothing.
390 			 */
391 			var newData = (this.isReversible() ? new Buffer() : 0);
392 			var newRecon = this.recon.update(0,
393 				other.what.slice(pos1 - pos2, pos1 - pos2 + len1) );
394 			return new Operations.Delete(pos2, newData, newRecon);
395 		}
396 		if(pos2 <= pos1 && pos2 + len2 < pos1 + len1)
397 		{
398 			/*     1XXXX----|
399 			 * 2--------|
400 			 * 
401 			 * The first part of this operation falls within the range of
402 			 * another.
403 			 */
404 			var result = this.split(pos2 + len2 - pos1);
405 			result.second.position = pos2;
406 			result.second.recon = this.recon.update(0,
407 				other.what.slice(pos1 - pos2) );
408 			return result.second;
409 		}
410 		if(pos2 > pos1 && pos2 + len2 >= pos1 + len1)
411 		{
412 			/* 1----XXXXX|
413 			 *     2--------|
414 			 *
415 			 * The second part of this operation falls within the range of
416 			 * another.
417 			 */
418 			var result = this.split(pos2 - pos1);
419 			result.first.recon = this.recon.update(result.first.getLength(), other.what.slice(0, pos1 + len1 - pos2) );
420 			return result.first;
421 		}
422 		if(pos2 > pos1 && pos2 + len2 < pos1 + len1)
423 		{
424 			/* 1-----XXXXXX---|
425 			 *      2------|
426 			 *
427 			 * Another operation falls completely within the range of this
428 			 * operation. We remove that part.
429 			 */
430 			
431 			// We split this operation two times: first at the beginning of
432 			// the second operation, then at the end of the second operation.
433 			var r1 = this.split(pos2 - pos1);
434 			var r2 = r1.second.split(len2);
435 			
436 			// The resulting Delete operation consists of the first and the
437 			// last part, which are merged back into a single operation.
438 			var result = r1.first.merge(r2.second);
439 			result.recon = this.recon.update(pos2 - pos1, other.what);
440 			return result;
441 		}
442 	}
443 };
444 
445 /** Mirrors this Delete operation. Returns an operation which inserts the text
446  *  that this Delete operation would remove. If this Delete operation is not
447  *  reversible, the return value is undefined.
448  *  @type Operations.Insert
449  */
450 Operations.Delete.prototype.mirror = function() {
451 	if(this.isReversible())
452 		return new Operations.Insert(this.position, this.what.copy());
453 };
454 
455 /** Instantiates a new Split operation object.
456  *  @class An operation which wraps two different operations into a single
457  *  object. This is necessary for example in order to transform a Delete
458  *  operation against an Insert operation which falls into the range that is
459  *  to be deleted.
460  *  @param {Operation} first
461  *  @param {Operation} second
462  */
463 Operations.Split = function(first, second) {
464 	this.first = first;
465 	this.second = second;
466 };
467 
468 Operations.Split.prototype.requiresCID = true;
469 
470 Operations.Split.prototype.toString = function() {
471 	return "Split(" + this.first + ", " + this.second + ")";
472 };
473 
474 Operations.Split.prototype.toHTML = function() {
475 	return "Split(" + this.first.toHTML() + ", " + this.second.toHTML() + ")";
476 };
477 
478 /** Applies the two components of this split operation to the given buffer
479  *  sequentially. The second component is implicitly transformed against the 
480  *  first one in order to do so.
481  *  @param {Buffer} buffer The buffer to which this operation is to be applied.
482  */
483 Operations.Split.prototype.apply = function(buffer) {
484 	this.first.apply(buffer);
485 	var transformedSecond = this.second.transform(this.first);
486 	transformedSecond.apply(buffer);
487 };
488 
489 Operations.Split.prototype.cid = function() {};
490 
491 /** Transforms this Split operation against another operation. This is done
492  *  by transforming both components individually.
493  *  @param {Operation} other
494  *  @param {Operation} [cid]
495  */
496 Operations.Split.prototype.transform = function(other, cid) {
497 	if(cid == this || cid == other)
498 		return new Operations.Split(
499 			this.first.transform(other, (cid == this ? this.first : other)),
500 			this.second.transform(other, (cid == this ? this.second : other))
501 		);
502 	else
503 		return new Operations.Split(
504 			this.first.transform(other),
505 			this.second.transform(other)
506 		);
507 };
508 
509 /** Mirrors this Split operation. This is done by transforming the second
510  *  component against the first one, then mirroring both components
511  *  individually.
512  *  @type Operations.Split
513  */
514 Operations.Split.prototype.mirror = function() {
515 	var newSecond = this.second.transform(this.first);
516 	return new Operations.Split(this.first.mirror(), newSecond.mirror());
517 };
518 
519 /** Creates a new Recon object.
520  *  @class The Recon class is a helper class which collects the parts of a
521  *  Delete operation that are lost during transformation. This is used to
522  *  reconstruct the text of a remote Delete operation that was issued in a
523  *  previous state, and thus to make such a Delete operation reversible.
524  *  @param {Recon} [recon] Pre-initialize the Recon object with data from
525  *  another object.
526  */
527 function Recon(recon) {
528 	if(recon)
529 		this.segments = recon.segments.slice(0);
530 	else
531 		this.segments = new Array();
532 }
533 
534 Recon.prototype.toString = function() {
535 	return "Recon(" + this.segments + ")";
536 };
537 
538 /** Creates a new Recon object with an additional piece of text to be restored
539  *  later.
540  *  @param {Number} offset
541  *  @param {Buffer} buffer
542  *  @type {Recon}
543  */
544 Recon.prototype.update = function(offset, buffer) {
545 	var newRecon = new Recon(this);
546 	if(buffer instanceof Buffer)
547 		newRecon.segments.push(new ReconSegment(offset, buffer));
548 	return newRecon;
549 };
550 
551 /** Restores the recon data in the given buffer.
552  *  @param {Buffer} buffer
553  */
554 Recon.prototype.restore = function(buffer) {
555 	for(var index in this.segments)
556 	{
557 		var segment = this.segments[index];
558 		buffer.splice(segment.offset, 0, segment.buffer);
559 	}
560 };
561 
562 /** Instantiates a new ReconSegment object.
563  *  @class ReconSegments store a range of text combined with the offset at
564  *  which they are to be inserted upon restoration.
565  *  @param {Number} offset
566  *  @param {Buffer} buffer
567  */
568 function ReconSegment(offset, buffer) {
569 	this.offset = offset;
570 	this.buffer = buffer.copy();
571 }
572 
573 ReconSegment.prototype.toString = function() {
574 	return "(" + this.offset + ", " + this.buffer + ")";
575 };
576