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 /**
 24  * @class Stores state vectors.
 25  * @param [value] Pre-initialize the vector with existing values. This can be
 26  * a Vector object, a generic Object with numeric properties, or a string of
 27  * the form "1:2;3:4;5:6".
 28  */
 29 function Vector(value) {
 30 	if(typeof(value) == "object")
 31 	{
 32 		for(var user in value) {
 33 			if(user.match(Vector.user_regex) && value[user] > 0)
 34 				this[user] = value[user];
 35 		}
 36 	} else if (typeof(value) == "string") {
 37 		var match = Vector.timestring_regex.exec(value);
 38 		while (match != null) {
 39 			this[match[1]] = parseInt(match[2]);
 40 			match = Vector.timestring_regex.exec(value);
 41 		}
 42 	}
 43 }
 44 
 45 /** @ignore
 46  *  @static */
 47 Vector.user_regex = /\d+/;
 48 /** @ignore
 49  *  @static */
 50 Vector.timestring_regex = /(\d+):(\d+)/g;
 51 
 52 /** Helper function to easily iterate over all users in this vector.
 53  *  @param {function} callback Callback function which is called with the user
 54  *  and the value of each component. If this callback function returns false,
 55  *  iteration is stopped at that point and false is returned.
 56  *  @type Boolean
 57  *  @returns True if the callback function has never returned false; returns
 58  *  False otherwise.
 59  */
 60 Vector.prototype.eachUser = function(callback) {
 61 	for(var user in this) {
 62 		if(user.match(Vector.user_regex)) {
 63 			if(callback(parseInt(user), this[user]) == false)
 64 				return false;
 65 		}
 66 	}
 67 	
 68 	return true;
 69 };
 70 
 71 /** Returns this vector as a string of the form "1:2;3:4;5:6"
 72  *  @type String
 73  */
 74 Vector.prototype.toString = function() {
 75 	var components = new Array();
 76 	
 77 	this.eachUser(function(u, v) {
 78 		if(v > 0)
 79 			components.push(u + ":" + v);
 80 	});
 81 	
 82 	components.sort();
 83 	
 84 	return components.join(";");
 85 };
 86 
 87 Vector.prototype.toHTML = Vector.prototype.toString;
 88 
 89 /** Returns the sum of two vectors.
 90  *  @param {Vector} other
 91  */ 
 92 Vector.prototype.add = function(other) {
 93 	var result = new Vector(this);
 94 	
 95 	other.eachUser(function(u, v) {
 96 		result[u] = result.get(u) + v;
 97 	});
 98 	
 99 	return result;
100 };
101 
102 /** Returns a copy of this vector. */
103 Vector.prototype.copy = function() {
104 	return new Vector(this);
105 };
106 
107 /** Returns a specific component of this vector, or 0 if it is not defined.
108  *  @param {Number} user Index of the component to be returned
109  */
110 Vector.prototype.get = function(user) {
111 	if(this[user] != undefined)
112 		return this[user];
113 	else
114 		return 0;
115 };
116 
117 /** Calculates whether this vector is smaller than or equal to another vector.
118  *  This means that all components of this vector are less than or equal to
119  *  their corresponding components in the other vector.
120  *  @param {Vector} other The vector to compare to
121  *  @type Boolean
122  */
123 Vector.prototype.causallyBefore = function(other) {
124 	return this.eachUser(function(u, v) {
125 		return v <= other.get(u);
126 	});
127 };
128 
129 /** Determines whether this vector is equal to another vector. This is true if
130  *  all components of this vector are present in the other vector and match
131  *  their values, and vice-versa.
132  *  @param {Vector} other The vector to compare to
133  *  @type Boolean
134  */
135 Vector.prototype.equals = function(other) {
136 	var eq1 = this.eachUser(function(u, v) {
137 		return other.get(u) == v;
138 	});
139 	
140 	var self = this;
141 	var eq2 = other.eachUser(function(u, v) {
142 		return self.get(u) == v;
143 	});
144 	
145 	return eq1 && eq2;
146 };
147 
148 /** Returns a new vector with a specific component increased by a given
149  *  amount.
150  *  @param {Number} user Component to increase
151  *  @param {Number} [by] Amount by which to increase the component (default 1)
152  *  @type Vector
153  */
154 Vector.prototype.incr = function(user, by) {
155 	var result = new Vector(this);
156 	
157 	if(by == undefined)
158 		by = 1;
159 	
160 	result[user] = result.get(user) + by;
161 	
162 	return result;
163 }
164 
165 /** Calculates the least common successor of two vectors.
166  *  @param {Vector} v1
167  *  @param {Vector} v2
168  *  @type Vector
169  */
170 Vector.leastCommonSuccessor = function(v1, v2) {
171 	var result = v1.copy();
172 	
173 	v2.eachUser(function(u, v) {
174 		var val1 = v1.get(u);
175 		var val2 = v2.get(u);
176 		
177 		if(val1 < val2)
178 			result[u] = val2;
179 		//else
180 		//	result[u] = val1; // This is already the case since we copied v1
181 	});
182 	
183 	return result;
184 };
185 
186 /** Instantiates a new state object.
187  *  @class Stores and manipulates the state of a document by keeping track of
188  *  its state vector, content and history of executed requests.
189  *  @param {Buffer} [buffer] Pre-initialize the buffer
190  *  @param {Vector} [vector] Set the initial state vector
191  */
192 function State(buffer, vector) {
193 	if(buffer instanceof Buffer)
194 		this.buffer = buffer.copy();
195 	else
196 		this.buffer = new Buffer();
197 	
198 	this.vector = new Vector(vector);
199 	this.request_queue = new Array();
200 	this.log = new Array();
201 	this.cache = {};
202 }
203 
204 /** Translates a request to the given state vector.
205  *  @param {Request} request The request to translate
206  *  @param {Vector} targetVector The target state vector
207  *  @param {Boolean} [nocache] Set to true to bypass the translation cache.
208  */
209 State.prototype.translate = function(request, targetVector, noCache) {	
210 	if(request instanceof DoRequest && request.vector.equals(targetVector)) {
211 		// If the request vector is not an undo/redo request and is already
212 		// at the desired state, simply return the original request since
213 		// there is nothing to do.
214 		return request.copy();
215 	}
216 	
217 	// Before we attempt to translate the request, we check whether it is
218 	// cached already.
219 	var cache_key = [request, targetVector].toString();
220 	if(this.cache != undefined && !noCache) {
221 		if(!this.cache[cache_key])
222 			this.cache[cache_key] = this.translate(request, targetVector, true);
223 		
224 		// FIXME: translated requests are not cleared from the cache, so this
225 		// might fill up considerably.
226 		return this.cache[cache_key];
227 	}
228 	
229 	if(request instanceof UndoRequest || request instanceof RedoRequest)
230 	{
231 		// If we're dealing with an undo or redo request, we first try to see
232 		// whether a late mirror is possible. For this, we retrieve the
233 		// associated request to this undo/redo and see whether it can be
234 		// translated and then mirrored to the desired state.
235 		var assocReq = request.associatedRequest(this.log);
236 		
237 		// The state we're trying to mirror at corresponds to the target
238 		// vector, except the component of the issuing user is changed to
239 		// match the one from the associated request.
240 		var mirrorAt = targetVector.copy();
241 		mirrorAt[request.user] = assocReq.vector.get(request.user);
242 		
243 		if(this.reachable(mirrorAt))
244 		{			
245 			var translated = this.translate(assocReq, mirrorAt);
246 			var mirrorBy = targetVector.get(request.user) -
247 				mirrorAt.get(request.user);
248 			
249 			var mirrored = translated.mirror(mirrorBy);
250 			return mirrored;
251 		}
252 		
253 		// If mirrorAt is not reachable, we need to mirror earlier and then
254 		// perform a translation afterwards, which is attempted next.
255 	}
256 	
257 	for(var _user in this.vector)
258 	{
259 		// We now iterate through all users to see how we can translate
260 		// the request to the desired state.
261 		
262 		if(!_user.match(Vector.user_regex))
263 			continue;
264 		
265 		var user = parseInt(_user);
266 		
267 		// The request's issuing user is left out since it is not possible
268 		// to transform or fold a request along its own user.
269 		if(user == request.user)
270 			continue;
271 		
272 		// We can only transform against requests that have been issued
273 		// between the translated request's vector and the target vector.
274 		if(targetVector.get(user) <= request.vector.get(user))
275 			continue;
276 		
277 		// Fetch the last request by this user that contributed to the
278 		// current state vector.
279 		var lastRequest = this.requestByUser(user, targetVector.get(user) - 1);
280 		
281 		if(lastRequest instanceof UndoRequest || lastRequest instanceof RedoRequest)
282 		{
283 			// When the last request was an undo/redo request, we can try to
284 			// "fold" over it. By just skipping the do/undo or undo/redo pair,
285 			// we pretend that nothing has changed and increase the state
286 			// vector.
287 			
288 			var foldBy = targetVector.get(user) -
289 				lastRequest.associatedRequest(this.log).vector.get(user);
290 			
291 			if(targetVector.get(user) >= foldBy)
292 			{
293 				var foldAt = targetVector.incr(user, -foldBy);
294 				
295 				// We need to make sure that the state we're trying to
296 				// fold at is reachable and that the request we're translating
297 				// was issued before it.
298 				
299 				if(this.reachable(foldAt) && request.vector.causallyBefore(foldAt))
300 				{
301 					var translated = this.translate(request, foldAt);
302 					var folded = translated.fold(user, foldBy);
303 					
304 					return folded;
305 				}
306 			}
307 		}
308 		
309 		// If folding and mirroring is not possible, we can transform this
310 		// request against other users' requests that have contributed to
311 		// the current state vector.
312 		
313 		var transformAt = targetVector.incr(user, -1);
314 		if(transformAt.get(user) >= 0 && this.reachable(transformAt))
315 		{
316 			var lastRequest = this.requestByUser(user, transformAt.get(user));
317 			
318 			var r1 = this.translate(request, transformAt);
319 			var r2 = this.translate(lastRequest, transformAt);
320 			
321 			var cid_req;
322 			
323 			if(r1.operation.requiresCID)
324 			{
325 				// For the Insert operation, we need to check whether it is
326 				// possible to determine which operation is to be transformed.
327 				var cid = r1.operation.cid(r2.operation);
328 			
329 				if(!cid)
330 				{
331 					// When two requests insert text at the same position,
332 					// the transformation result is undefined. We therefore
333 					// need to perform some tricks to decide which request
334 					// has to be transformed against which.
335 					
336 					// The first try is to transform both requests to a
337 					// common successor before the transformation vector.
338 					var lcs = Vector.leastCommonSuccessor(request.vector,
339 						lastRequest.vector);
340 					
341 					if(this.reachable(lcs))
342 					{
343 						var r1t = this.translate(request, lcs);
344 						var r2t = this.translate(lastRequest, lcs);
345 						
346 						// We try to determine the CID at this vector, which
347 						// hopefully yields a result.
348 						var cidt = r1t.operation.cid(r2t.operation);
349 						
350 						if(cidt == r1t.operation)
351 							cid = r1.operation;
352 						else if(cidt == r2t.operation)
353 							cid = r2.operation;
354 					}
355 					
356 					if(!cid) {
357 						// If we arrived here, we couldn't decide for a CID,
358 						// so we take the last resort: use the user ID of the
359 						// requests to decide which request is to be
360 						// transformed. This behavior is specified in the
361 						// Infinote protocol.
362 						
363 						if(r1.user < r2.user)
364 							cid = r1.operation;
365 						if(r1.user > r2.user)
366 							cid = r2.operation;
367 					}
368 				}
369 				
370 				if(cid == r1.operation)
371 					cid_req = r1;
372 				if(cid == r2.operation)
373 					cid_req = r2;
374 			}
375 			
376 			return r1.transform(r2, cid_req);
377 		}
378 	}
379 	
380 	throw "Could not find a translation path";
381 };
382 
383 /** Adds a request to the request queue.
384  *  @param {Request} request The request to be queued.
385  */
386 State.prototype.queue = function(request) {
387 	this.request_queue.push(request);
388 };
389 
390 /** Checks whether a given request can be executed in the current state.
391  *  @type Boolean
392  */
393 State.prototype.canExecute = function(request) {
394 	if(request == undefined)
395 		return false;
396 	
397 	return request.vector.causallyBefore(this.vector);
398 };
399 
400 /** Executes a request that is executable.
401  *  @param {Request} [request] The request to be executed. If omitted, an
402  *  executable request is picked from the request queue instead.
403  *  @returns The request that has been executed, or undefined if no request
404  *  has been executed.
405  */
406 State.prototype.execute = function(request) {
407 	if(request == undefined)
408 	{
409 		// Pick an executable request from the queue.
410 		for(var index = 0; index < this.request_queue.length; index ++)
411 		{
412 			request = request_queue[index];
413 			if(this.canExecute(request))
414 			{
415 				this.request_queue.splice(index, 1);
416 				break;
417 			}
418 		}
419 	}
420 	
421 	if(!this.canExecute(request))
422 	{
423 		// Not executable yet - put it (back) in the queue.
424 		if(request != undefined)
425 			this.queue(request);
426 		
427 		return;
428 	}
429 	
430 	request = request.copy();
431 	
432 	if(request instanceof UndoRequest || request instanceof RedoRequest) {
433 		// For undo and redo requests, we change their vector to the vector
434 		// of the original request, but leave the issuing user's component
435 		// untouched.
436 		var assocReq = request.associatedRequest(this.log);
437 		var newVector = new Vector(assocReq.vector);
438 		newVector[request.user] = request.vector.get(request.user);
439 		request.vector = newVector;
440 	}
441 	
442 	var translated = this.translate(request, this.vector);
443 	
444 	if(request instanceof DoRequest && request.operation instanceof Operations.Delete) {
445 		// Since each request might have to be mirrored at some point, it
446 		// needs to be reversible. Delete requests are not reversible by
447 		// default, but we can make them reversible.
448 		this.log.push(request.makeReversible(translated, this));
449 	} else {
450 		this.log.push(request);
451 	}
452 	
453 	translated.execute(this);
454 	
455 	if(this.onexecute)
456 		this.onexecute(translated);
457 	
458 	return translated;
459 };
460 
461 /** Executes all queued requests that are ready for execution. */
462 State.prototype.executeAll = function() {
463 	do {
464 		var executed = this.execute();
465 	} while(executed);
466 };
467 
468 /** Determines whether a given state is reachable by translation.
469  *  @param {Vector} vector
470  *  @type Boolean
471  */
472 State.prototype.reachable = function(vector) {
473 	var self = this;
474 	return this.vector.eachUser(function(u, v) {
475 		return self.reachableUser(vector, u);
476 	});
477 };
478 
479 State.prototype.reachableUser = function(vector, user) {
480 	var n = vector.get(user);
481 	
482 	while(true) {
483 		if(n == 0)
484 			return true;
485 		
486 		var r = this.requestByUser(user, n - 1);
487 		
488 		if(r == undefined)
489 		{
490 			return false;
491 		}
492 
493 		if(r instanceof DoRequest)
494 		{
495 			var w = r.vector;
496 			return w.causallyBefore(vector);
497 		} else {
498 			var assocReq = r.associatedRequest(this.log);
499 			n = assocReq.vector.get(user);
500 		}
501 	}
502 };
503 
504 /** Retrieve an user's request by its index.
505  *  @param {Number} user
506  *  @param {Number} index The number of the request to be returned
507  */
508 State.prototype.requestByUser = function(user, getIndex) {
509 	var userReqCount = 0;
510 	for(var reqIndex in this.log)
511 	{
512 		if(this.log[reqIndex].user == user)
513 		{
514 			if(userReqCount == getIndex)
515 				return this.log[reqIndex];
516 			else
517 				userReqCount += 1;
518 		}
519 	}
520 }
521