diff options
Diffstat (limited to 'trunk/etherpad/src/etherpad/collab')
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/contentcollector.js | 527 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/domline.js | 210 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/easysync1.js | 923 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/easysync2.js | 1968 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/easysync2_tests.js | 877 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/ace/linestylefilter.js | 253 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/collab_server.js | 778 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/collabroom_server.js | 359 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/genimg.js | 55 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/json_sans_eval.js | 178 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/readonly_server.js | 174 | ||||
| -rw-r--r-- | trunk/etherpad/src/etherpad/collab/server_utils.js | 204 |
12 files changed, 6506 insertions, 0 deletions
diff --git a/trunk/etherpad/src/etherpad/collab/ace/contentcollector.js b/trunk/etherpad/src/etherpad/collab/ace/contentcollector.js new file mode 100644 index 0000000..5dd4f9c --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/contentcollector.js @@ -0,0 +1,527 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/contentcollector.js +import("etherpad.collab.ace.easysync2.Changeset") + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +var _MAX_LIST_LEVEL = 8; + +function sanitizeUnicode(s) { + return s.replace(/[\uffff\ufffe\ufeff\ufdd0-\ufdef\ud800-\udfff]/g, '?'); +} + +function makeContentCollector(collectStyles, browser, apool, domInterface, + className2Author) { + browser = browser || {}; + + var dom = domInterface || { + isNodeText: function(n) { + return (n.nodeType == 3); + }, + nodeTagName: function(n) { + return n.tagName; + }, + nodeValue: function(n) { + return n.nodeValue; + }, + nodeNumChildren: function(n) { + return n.childNodes.length; + }, + nodeChild: function(n, i) { + return n.childNodes.item(i); + }, + nodeProp: function(n, p) { + return n[p]; + }, + nodeAttr: function(n, a) { + return n.getAttribute(a); + }, + optNodeInnerHTML: function(n) { + return n.innerHTML; + } + }; + + var _blockElems = { "div":1, "p":1, "pre":1, "li":1 }; + function isBlockElement(n) { + return !!_blockElems[(dom.nodeTagName(n) || "").toLowerCase()]; + } + function textify(str) { + return sanitizeUnicode( + str.replace(/[\n\r ]/g, ' ').replace(/\xa0/g, ' ').replace(/\t/g, ' ')); + } + function getAssoc(node, name) { + return dom.nodeProp(node, "_magicdom_"+name); + } + + var lines = (function() { + var textArray = []; + var attribsArray = []; + var attribsBuilder = null; + var op = Changeset.newOp('+'); + var self = { + length: function() { return textArray.length; }, + atColumnZero: function() { + return textArray[textArray.length-1] === ""; + }, + startNew: function() { + textArray.push(""); + self.flush(true); + attribsBuilder = Changeset.smartOpAssembler(); + }, + textOfLine: function(i) { return textArray[i]; }, + appendText: function(txt, attrString) { + textArray[textArray.length-1] += txt; + //dmesg(txt+" / "+attrString); + op.attribs = attrString; + op.chars = txt.length; + attribsBuilder.append(op); + }, + textLines: function() { return textArray.slice(); }, + attribLines: function() { return attribsArray; }, + // call flush only when you're done + flush: function(withNewline) { + if (attribsBuilder) { + attribsArray.push(attribsBuilder.toString()); + attribsBuilder = null; + } + } + }; + self.startNew(); + return self; + }()); + var cc = {}; + function _ensureColumnZero(state) { + if (! lines.atColumnZero()) { + _startNewLine(state); + } + } + var selection, startPoint, endPoint; + var selStart = [-1,-1], selEnd = [-1,-1]; + var blockElems = { "div":1, "p":1, "pre":1 }; + function _isEmpty(node, state) { + // consider clean blank lines pasted in IE to be empty + if (dom.nodeNumChildren(node) == 0) return true; + if (dom.nodeNumChildren(node) == 1 && + getAssoc(node, "shouldBeEmpty") && dom.optNodeInnerHTML(node) == " " + && ! getAssoc(node, "unpasted")) { + if (state) { + var child = dom.nodeChild(node, 0); + _reachPoint(child, 0, state); + _reachPoint(child, 1, state); + } + return true; + } + return false; + } + function _pointHere(charsAfter, state) { + var ln = lines.length()-1; + var chr = lines.textOfLine(ln).length; + if (chr == 0 && state.listType && state.listType != 'none') { + chr += 1; // listMarker + } + chr += charsAfter; + return [ln, chr]; + } + function _reachBlockPoint(nd, idx, state) { + if (! dom.isNodeText(nd)) _reachPoint(nd, idx, state); + } + function _reachPoint(nd, idx, state) { + if (startPoint && nd == startPoint.node && startPoint.index == idx) { + selStart = _pointHere(0, state); + } + if (endPoint && nd == endPoint.node && endPoint.index == idx) { + selEnd = _pointHere(0, state); + } + } + function _incrementFlag(state, flagName) { + state.flags[flagName] = (state.flags[flagName] || 0)+1; + } + function _decrementFlag(state, flagName) { + state.flags[flagName]--; + } + function _incrementAttrib(state, attribName) { + if (! state.attribs[attribName]) { + state.attribs[attribName] = 1; + } + else { + state.attribs[attribName]++; + } + _recalcAttribString(state); + } + function _decrementAttrib(state, attribName) { + state.attribs[attribName]--; + _recalcAttribString(state); + } + function _enterList(state, listType) { + var oldListType = state.listType; + state.listLevel = (state.listLevel || 0)+1; + if (listType != 'none') { + state.listNesting = (state.listNesting || 0)+1; + } + state.listType = listType; + _recalcAttribString(state); + return oldListType; + } + function _exitList(state, oldListType) { + state.listLevel--; + if (state.listType != 'none') { + state.listNesting--; + } + state.listType = oldListType; + _recalcAttribString(state); + } + function _enterAuthor(state, author) { + var oldAuthor = state.author; + state.authorLevel = (state.authorLevel || 0)+1; + state.author = author; + _recalcAttribString(state); + return oldAuthor; + } + function _exitAuthor(state, oldAuthor) { + state.authorLevel--; + state.author = oldAuthor; + _recalcAttribString(state); + } + function _recalcAttribString(state) { + var lst = []; + for(var a in state.attribs) { + if (state.attribs[a]) { + lst.push([a,'true']); + } + } + if (state.authorLevel > 0) { + var authorAttrib = ['author', state.author]; + if (apool.putAttrib(authorAttrib, true) >= 0) { + // require that author already be in pool + // (don't add authors from other documents, etc.) + lst.push(authorAttrib); + } + } + state.attribString = Changeset.makeAttribsString('+', lst, apool); + } + function _produceListMarker(state) { + lines.appendText('*', Changeset.makeAttribsString( + '+', [['list', state.listType], + ['insertorder', 'first']], + apool)); + } + function _startNewLine(state) { + if (state) { + var atBeginningOfLine = lines.textOfLine(lines.length()-1).length == 0; + if (atBeginningOfLine && state.listType && state.listType != 'none') { + _produceListMarker(state); + } + } + lines.startNew(); + } + cc.notifySelection = function (sel) { + if (sel) { + selection = sel; + startPoint = selection.startPoint; + endPoint = selection.endPoint; + } + }; + cc.collectContent = function (node, state) { + if (! state) { + state = {flags: {/*name -> nesting counter*/}, + attribs: {/*name -> nesting counter*/}, + attribString: ''}; + } + var isBlock = isBlockElement(node); + var isEmpty = _isEmpty(node, state); + if (isBlock) _ensureColumnZero(state); + var startLine = lines.length()-1; + _reachBlockPoint(node, 0, state); + if (dom.isNodeText(node)) { + var txt = dom.nodeValue(node); + var rest = ''; + var x = 0; // offset into original text + if (txt.length == 0) { + if (startPoint && node == startPoint.node) { + selStart = _pointHere(0, state); + } + if (endPoint && node == endPoint.node) { + selEnd = _pointHere(0, state); + } + } + while (txt.length > 0) { + var consumed = 0; + if (state.flags.preMode) { + var firstLine = txt.split('\n',1)[0]; + consumed = firstLine.length+1; + rest = txt.substring(consumed); + txt = firstLine; + } + else { /* will only run this loop body once */ } + if (startPoint && node == startPoint.node && + startPoint.index-x <= txt.length) { + selStart = _pointHere(startPoint.index-x, state); + } + if (endPoint && node == endPoint.node && + endPoint.index-x <= txt.length) { + selEnd = _pointHere(endPoint.index-x, state); + } + var txt2 = txt; + if ((! state.flags.preMode) && /^[\r\n]*$/.exec(txt)) { + // prevents textnodes containing just "\n" from being significant + // in safari when pasting text, now that we convert them to + // spaces instead of removing them, because in other cases + // removing "\n" from pasted HTML will collapse words together. + txt2 = ""; + } + var atBeginningOfLine = lines.textOfLine(lines.length()-1).length == 0; + if (atBeginningOfLine) { + // newlines in the source mustn't become spaces at beginning of line box + txt2 = txt2.replace(/^\n*/, ''); + } + if (atBeginningOfLine && state.listType && state.listType != 'none') { + _produceListMarker(state); + } + lines.appendText(textify(txt2), state.attribString); + x += consumed; + txt = rest; + if (txt.length > 0) { + _startNewLine(state); + } + } + } + else { + var tname = (dom.nodeTagName(node) || "").toLowerCase(); + if (tname == "br") { + _startNewLine(state); + } + else if (tname == "script" || tname == "style") { + // ignore + } + else if (! isEmpty) { + var styl = dom.nodeAttr(node, "style"); + var cls = dom.nodeProp(node, "className"); + + var isPre = (tname == "pre"); + if ((! isPre) && browser.safari) { + isPre = (styl && /\bwhite-space:\s*pre\b/i.exec(styl)); + } + if (isPre) _incrementFlag(state, 'preMode'); + var attribs = null; + var oldListTypeOrNull = null; + var oldAuthorOrNull = null; + if (collectStyles) { + function doAttrib(na) { + attribs = (attribs || []); + attribs.push(na); + _incrementAttrib(state, na); + } + if (tname == "b" || (styl && /\bfont-weight:\s*bold\b/i.exec(styl)) || + tname == "strong") { + doAttrib("bold"); + } + if (tname == "i" || (styl && /\bfont-style:\s*italic\b/i.exec(styl)) || + tname == "em") { + doAttrib("italic"); + } + if (tname == "u" || (styl && /\btext-decoration:\s*underline\b/i.exec(styl)) || + tname == "ins") { + doAttrib("underline"); + } + if (tname == "s" || (styl && /\btext-decoration:\s*line-through\b/i.exec(styl)) || + tname == "del") { + doAttrib("strikethrough"); + } + if (tname == "h1") { + doAttrib("h1"); + } + if (tname == "h2") { + doAttrib("h2"); + } + if (tname == "h3") { + doAttrib("h3"); + } + if (tname == "h4") { + doAttrib("h4"); + } + if (tname == "h5") { + doAttrib("h5"); + } + if (tname == "h6") { + doAttrib("h6"); + } + if (tname == "ul") { + var type; + var rr = cls && /(?:^| )list-(bullet[12345678])\b/.exec(cls); + type = rr && rr[1] || "bullet"+ + String(Math.min(_MAX_LIST_LEVEL, (state.listNesting||0)+1)); + oldListTypeOrNull = (_enterList(state, type) || 'none'); + } + else if ((tname == "div" || tname == "p") && cls && + cls.match(/(?:^| )ace-line\b/)) { + oldListTypeOrNull = (_enterList(state, type) || 'none'); + } + if (className2Author && cls) { + var classes = cls.match(/\S+/g); + if (classes && classes.length > 0) { + for(var i=0;i<classes.length;i++) { + var c = classes[i]; + var a = className2Author(c); + if (a) { + oldAuthorOrNull = (_enterAuthor(state, a) || 'none'); + break; + } + } + } + } + } + + var nc = dom.nodeNumChildren(node); + for(var i=0;i<nc;i++) { + var c = dom.nodeChild(node, i); + cc.collectContent(c, state); + } + + if (isPre) _decrementFlag(state, 'preMode'); + if (attribs) { + for(var i=0;i<attribs.length;i++) { + _decrementAttrib(state, attribs[i]); + } + } + if (oldListTypeOrNull) { + _exitList(state, oldListTypeOrNull); + } + if (oldAuthorOrNull) { + _exitAuthor(state, oldAuthorOrNull); + } + } + } + if (! browser.msie) { + _reachBlockPoint(node, 1, state); + } + if (isBlock) { + if (lines.length()-1 == startLine) { + _startNewLine(state); + } + else { + _ensureColumnZero(state); + } + } + + if (browser.msie) { + // in IE, a point immediately after a DIV appears on the next line + _reachBlockPoint(node, 1, state); + } + }; + // can pass a falsy value for end of doc + cc.notifyNextNode = function (node) { + // an "empty block" won't end a line; this addresses an issue in IE with + // typing into a blank line at the end of the document. typed text + // goes into the body, and the empty line div still looks clean. + // it is incorporated as dirty by the rule that a dirty region has + // to end a line. + if ((!node) || (isBlockElement(node) && !_isEmpty(node))) { + _ensureColumnZero(null); + } + }; + // each returns [line, char] or [-1,-1] + var getSelectionStart = function() { return selStart; }; + var getSelectionEnd = function() { return selEnd; }; + + // returns array of strings for lines found, last entry will be "" if + // last line is complete (i.e. if a following span should be on a new line). + // can be called at any point + cc.getLines = function() { return lines.textLines(); }; + + //cc.applyHints = function(hints) { + //if (hints.pastedLines) { + // + //} + //} + + cc.finish = function() { + lines.flush(); + var lineAttribs = lines.attribLines(); + var lineStrings = cc.getLines(); + + lineStrings.length--; + lineAttribs.length--; + + var ss = getSelectionStart(); + var se = getSelectionEnd(); + + function fixLongLines() { + // design mode does not deal with with really long lines! + var lineLimit = 2000; // chars + var buffer = 10; // chars allowed over before wrapping + var linesWrapped = 0; + var numLinesAfter = 0; + for(var i=lineStrings.length-1; i>=0; i--) { + var oldString = lineStrings[i]; + var oldAttribString = lineAttribs[i]; + if (oldString.length > lineLimit+buffer) { + var newStrings = []; + var newAttribStrings = []; + while (oldString.length > lineLimit) { + //var semiloc = oldString.lastIndexOf(';', lineLimit-1); + //var lengthToTake = (semiloc >= 0 ? (semiloc+1) : lineLimit); + lengthToTake = lineLimit; + newStrings.push(oldString.substring(0, lengthToTake)); + oldString = oldString.substring(lengthToTake); + newAttribStrings.push(Changeset.subattribution(oldAttribString, + 0, lengthToTake)); + oldAttribString = Changeset.subattribution(oldAttribString, + lengthToTake); + } + if (oldString.length > 0) { + newStrings.push(oldString); + newAttribStrings.push(oldAttribString); + } + function fixLineNumber(lineChar) { + if (lineChar[0] < 0) return; + var n = lineChar[0]; + var c = lineChar[1]; + if (n > i) { + n += (newStrings.length-1); + } + else if (n == i) { + var a = 0; + while (c > newStrings[a].length) { + c -= newStrings[a].length; + a++; + } + n += a; + } + lineChar[0] = n; + lineChar[1] = c; + } + fixLineNumber(ss); + fixLineNumber(se); + linesWrapped++; + numLinesAfter += newStrings.length; + + newStrings.unshift(i, 1); + lineStrings.splice.apply(lineStrings, newStrings); + newAttribStrings.unshift(i, 1); + lineAttribs.splice.apply(lineAttribs, newAttribStrings); + } + } + return {linesWrapped:linesWrapped, numLinesAfter:numLinesAfter}; + } + var wrapData = fixLongLines(); + + return { selStart: ss, selEnd: se, linesWrapped: wrapData.linesWrapped, + numLinesAfter: wrapData.numLinesAfter, + lines: lineStrings, lineAttribs: lineAttribs }; + } + + return cc; +} diff --git a/trunk/etherpad/src/etherpad/collab/ace/domline.js b/trunk/etherpad/src/etherpad/collab/ace/domline.js new file mode 100644 index 0000000..de2e7d3 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/domline.js @@ -0,0 +1,210 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/domline.js + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +var domline = {}; +domline.noop = function() {}; +domline.identity = function(x) { return x; }; + +domline.addToLineClass = function(lineClass, cls) { + // an "empty span" at any point can be used to add classes to + // the line, using line:className. otherwise, we ignore + // the span. + cls.replace(/\S+/g, function (c) { + if (c.indexOf("line:") == 0) { + // add class to line + lineClass = (lineClass ? lineClass+' ' : '')+c.substring(5); + } + }); + return lineClass; +} + +// if "document" is falsy we don't create a DOM node, just +// an object with innerHTML and className +domline.createDomLine = function(nonEmpty, doesWrap, optBrowser, optDocument) { + var result = { node: null, + appendSpan: domline.noop, + prepareForAdd: domline.noop, + notifyAdded: domline.noop, + clearSpans: domline.noop, + finishUpdate: domline.noop, + lineMarker: 0 }; + + var browser = (optBrowser || {}); + var document = optDocument; + + if (document) { + result.node = document.createElement("div"); + } + else { + result.node = {innerHTML: '', className: ''}; + } + + var html = []; + var preHtml, postHtml; + var curHTML = null; + function processSpaces(s) { + return domline.processSpaces(s, doesWrap); + } + var identity = domline.identity; + var perTextNodeProcess = (doesWrap ? identity : processSpaces); + var perHtmlLineProcess = (doesWrap ? processSpaces : identity); + var lineClass = 'ace-line'; + result.appendSpan = function(txt, cls) { + if (cls.indexOf('list') >= 0) { + var listType = /(?:^| )list:(\S+)/.exec(cls); + if (listType) { + listType = listType[1]; + if (listType) { + preHtml = '<ul class="list-'+listType+'"><li>'; + postHtml = '</li></ul>'; + } + result.lineMarker += txt.length; + return; // don't append any text + } + } + var href = null; + var simpleTags = null; + if (cls.indexOf('url') >= 0) { + cls = cls.replace(/(^| )url:(\S+)/g, function(x0, space, url) { + href = url; + return space+"url"; + }); + } + if (cls.indexOf('tag') >= 0) { + cls = cls.replace(/(^| )tag:(\S+)/g, function(x0, space, tag) { + if (! simpleTags) simpleTags = []; + simpleTags.push(tag.toLowerCase()); + return space+tag; + }); + } + if ((! txt) && cls) { + lineClass = domline.addToLineClass(lineClass, cls); + } + else if (txt) { + var extraOpenTags = ""; + var extraCloseTags = ""; + if (href) { + extraOpenTags = extraOpenTags+'<a href="'+ + href.replace(/\"/g, '"')+'">'; + extraCloseTags = '</a>'+extraCloseTags; + } + if (simpleTags) { + simpleTags.sort(); + extraOpenTags = extraOpenTags+'<'+simpleTags.join('><')+'>'; + simpleTags.reverse(); + extraCloseTags = '</'+simpleTags.join('></')+'>'+extraCloseTags; + } + html.push('<span class="',cls||'','">',extraOpenTags, + perTextNodeProcess(domline.escapeHTML(txt)), + extraCloseTags,'</span>'); + } + }; + result.clearSpans = function() { + html = []; + lineClass = ''; // non-null to cause update + result.lineMarker = 0; + }; + function writeHTML() { + var newHTML = perHtmlLineProcess(html.join('')); + if (! newHTML) { + if ((! document) || (! optBrowser)) { + newHTML += ' '; + } + else if (! browser.msie) { + newHTML += '<br/>'; + } + } + if (nonEmpty) { + newHTML = (preHtml||'')+newHTML+(postHtml||''); + } + html = preHtml = postHtml = null; // free memory + if (newHTML !== curHTML) { + curHTML = newHTML; + result.node.innerHTML = curHTML; + } + if (lineClass !== null) result.node.className = lineClass; + } + result.prepareForAdd = writeHTML; + result.finishUpdate = writeHTML; + result.getInnerHTML = function() { return curHTML || ''; }; + + return result; +}; + +domline.escapeHTML = function(s) { + var re = /[&<>'"]/g; /']/; // stupid indentation thing + if (! re.MAP) { + // persisted across function calls! + re.MAP = { + '&': '&', + '<': '<', + '>': '>', + '"': '"', + "'": ''' + }; + } + return s.replace(re, function(c) { return re.MAP[c]; }); +}; + +domline.processSpaces = function(s, doesWrap) { + if (s.indexOf("<") < 0 && ! doesWrap) { + // short-cut + return s.replace(/ /g, ' '); + } + var parts = []; + s.replace(/<[^>]*>?| |[^ <]+/g, function(m) { parts.push(m); }); + if (doesWrap) { + var endOfLine = true; + var beforeSpace = false; + // last space in a run is normal, others are nbsp, + // end of line is nbsp + for(var i=parts.length-1;i>=0;i--) { + var p = parts[i]; + if (p == " ") { + if (endOfLine || beforeSpace) + parts[i] = ' '; + endOfLine = false; + beforeSpace = true; + } + else if (p.charAt(0) != "<") { + endOfLine = false; + beforeSpace = false; + } + } + // beginning of line is nbsp + for(var i=0;i<parts.length;i++) { + var p = parts[i]; + if (p == " ") { + parts[i] = ' '; + break; + } + else if (p.charAt(0) != "<") { + break; + } + } + } + else { + for(var i=0;i<parts.length;i++) { + var p = parts[i]; + if (p == " ") { + parts[i] = ' '; + } + } + } + return parts.join(''); +}; diff --git a/trunk/etherpad/src/etherpad/collab/ace/easysync1.js b/trunk/etherpad/src/etherpad/collab/ace/easysync1.js new file mode 100644 index 0000000..4f40aa0 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/easysync1.js @@ -0,0 +1,923 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/easy_sync.js + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +function Changeset(arg) { + + var array; + if ((typeof arg) == "string") { + // constant + array = [Changeset.MAGIC, 0, arg.length, 0, 0, arg]; + } + else if ((typeof arg) == "number") { + var n = Math.round(arg); + // delete-all on n-length text (useful for making a "builder") + array = [Changeset.MAGIC, n, 0, 0, 0, ""]; + } + else if (! arg) { + // identity on 0-length text + array = [Changeset.MAGIC, 0, 0, 0, 0, ""]; + } + else if (arg.isChangeset) { + return arg; + } + else array = arg; + + array.isChangeset = true; + + // OOP style: attach generic methods to array object, hold no state in environment + + //function error(msg) { top.console.error(msg); top.console.trace(); } + function error(msg) { var e = new Error(msg); e.easysync = true; throw e; } + function assert(b, msg) { if (! b) error("Changeset: "+String(msg)); } + function min(x, y) { return (x < y) ? x : y; } + Changeset._assert = assert; + + array.isIdentity = function() { + return this.length == 6 && this[1] == this[2] && this[3] == 0 && + this[4] == this[1] && this[5] == ""; + } + + array.eachStrip = function(func, thisObj) { + // inside "func", the method receiver will be "this" by default, + // or you can pass an object. + for(var i=0;i<this.numStrips();i++) { + var ptr = 3 + i*3; + if (func.call(thisObj || this, this[ptr], this[ptr+1], this[ptr+2], i)) + return true; + } + return false; + } + + array.numStrips = function() { return (this.length-3)/3; }; + array.oldLen = function() { return this[1]; }; + array.newLen = function() { return this[2]; }; + + array.checkRep = function() { + assert(this[0] == Changeset.MAGIC, "bad magic"); + assert(this[1] >= 0, "bad old text length"); + assert(this[2] >= 0, "bad new text length"); + assert((this.length % 3) == 0, "bad array length"); + assert(this.length >= 6, "must be at least one strip"); + var numStrips = this.numStrips(); + var oldLen = this[1]; + var newLen = this[2]; + // iterate over the "text strips" + var actualNewLen = 0; + this.eachStrip(function(startIndex, numTaken, newText, i) { + var s = startIndex, t = numTaken, n = newText; + var isFirst = (i == 0); + var isLast = (i == numStrips-1); + assert(t >= 0, "can't take negative number of chars"); + assert(isFirst || t > 0, "all strips but first must take"); + assert((t > 0) || (s == 0), "if first strip doesn't take, must have 0 startIndex"); + assert(s >= 0 && s + t <= oldLen, "bad index: "+this.toString()); + assert(t > 0 || n.length > 0 || (isFirst && isLast), "empty strip must be first and only"); + if (! isLast) { + var s2 = this[3 + i*3 + 3]; // startIndex of following strip + var gap = s2 - (s + t); + assert(gap >= 0, "overlapping or out-of-order strips: "+this.toString()); + assert(gap > 0 || n.length > 0, "touching strips with no added text"); + } + actualNewLen += t + n.length; + }); + assert(newLen == actualNewLen, "calculated new text length doesn't match"); + } + + array.applyToText = function(text) { + assert(text.length == this.oldLen(), "mismatched apply: "+text.length+" / "+this.oldLen()); + var buf = []; + this.eachStrip(function (s, t, n) { + buf.push(text.substr(s, t), n); + }); + return buf.join(''); + } + + function _makeBuilder(oldLen, supportAuthors) { + var C = Changeset(oldLen); + if (supportAuthors) { + _ensureAuthors(C); + } + return C.builder(); + } + + function _getNumInserted(C) { + var numChars = 0; + C.eachStrip(function(s,t,n) { + numChars += n.length; + }); + return numChars; + } + + function _ensureAuthors(C) { + if (! C.authors) { + C.setAuthor(); + } + return C; + } + + array.setAuthor = function(author) { + var C = this; + // authors array has even length >= 2; + // alternates [numChars1, author1, numChars2, author2]; + // all numChars > 0 unless there is exactly one, in which + // case it can be == 0. + C.authors = [_getNumInserted(C), author || '']; + return C; + } + + array.builder = function() { + // normal pattern is Changeset(oldLength).builder().appendOldText(...). ... + // builder methods mutate this! + var C = this; + // OOP style: state in environment + var self; + return self = { + appendNewText: function(str, author) { + C[C.length-1] += str; + C[2] += str.length; + + if (C.authors) { + var a = (author || ''); + var lastAuthorPtr = C.authors.length-1; + var lastAuthorLengthPtr = C.authors.length-2; + if ((!a) || a == C.authors[lastAuthorPtr]) { + C.authors[lastAuthorLengthPtr] += str.length; + } + else if (0 == C.authors[lastAuthorLengthPtr]) { + C.authors[lastAuthorLengthPtr] = str.length; + C.authors[lastAuthorPtr] = (a || C.authors[lastAuthorPtr]); + } + else { + C.authors.push(str.length, a); + } + } + + return self; + }, + appendOldText: function(startIndex, numTaken) { + if (numTaken == 0) return self; + // properties of last strip... + var s = C[C.length-3], t = C[C.length-2], n = C[C.length-1]; + if (t == 0 && n == "") { + // must be empty changeset, one strip that doesn't take old chars or add new ones + C[C.length-3] = startIndex; + C[C.length-2] = numTaken; + } + else if (n == "" && (s+t == startIndex)) { + C[C.length-2] += numTaken; // take more + } + else C.push(startIndex, numTaken, ""); // add a strip + C[2] += numTaken; + C.checkRep(); + return self; + }, + toChangeset: function() { return C; } + }; + } + + array.authorSlicer = function(outputBuilder) { + return _makeAuthorSlicer(this, outputBuilder); + } + + function _makeAuthorSlicer(changesetOrAuthorsIn, builderOut) { + // "builderOut" only needs to support appendNewText + var authors; // considered immutable + if (changesetOrAuthorsIn.isChangeset) { + authors = changesetOrAuthorsIn.authors; + } + else { + authors = changesetOrAuthorsIn; + } + + // OOP style: state in environment + var authorPtr = 0; + var charIndex = 0; + var charWithinAuthor = 0; // 0 <= charWithinAuthor <= authors[authorPtr]; max value iff atEnd + var atEnd = false; + function curAuthor() { return authors[authorPtr+1]; } + function curAuthorWidth() { return authors[authorPtr]; } + function assertNotAtEnd() { assert(! atEnd, "_authorSlicer: can't move past end"); } + function forwardInAuthor(numChars) { + charWithinAuthor += numChars; + charIndex += numChars; + } + function nextAuthor() { + assertNotAtEnd(); + assert(charWithinAuthor == curAuthorWidth(), "_authorSlicer: not at author end"); + charWithinAuthor = 0; + authorPtr += 2; + if (authorPtr == authors.length) { + atEnd = true; + } + } + + var self; + return self = { + skipChars: function(n) { + assert(n >= 0, "_authorSlicer: can't skip negative n"); + if (n == 0) return; + assertNotAtEnd(); + + var leftToSkip = n; + while (leftToSkip > 0) { + var leftInAuthor = curAuthorWidth() - charWithinAuthor; + if (leftToSkip >= leftInAuthor) { + forwardInAuthor(leftInAuthor); + leftToSkip -= leftInAuthor; + nextAuthor(); + } + else { + forwardInAuthor(leftToSkip); + leftToSkip = 0; + } + } + }, + takeChars: function(n, text) { + assert(n >= 0, "_authorSlicer: can't take negative n"); + if (n == 0) return; + assertNotAtEnd(); + assert(n == text.length, "_authorSlicer: bad text length"); + + var textLeft = text; + var leftToTake = n; + while (leftToTake > 0) { + if (curAuthorWidth() > 0 && charWithinAuthor < curAuthorWidth()) { + // at least one char to take from current author + var leftInAuthor = (curAuthorWidth() - charWithinAuthor); + assert(leftInAuthor > 0, "_authorSlicer: should have leftInAuthor > 0"); + var toTake = min(leftInAuthor, leftToTake); + assert(toTake > 0, "_authorSlicer: should have toTake > 0"); + builderOut.appendNewText(textLeft.substring(0, toTake), curAuthor()); + forwardInAuthor(toTake); + leftToTake -= toTake; + textLeft = textLeft.substring(toTake); + } + assert(charWithinAuthor <= curAuthorWidth(), "_authorSlicer: past end of author"); + if (charWithinAuthor == curAuthorWidth()) { + nextAuthor(); + } + } + }, + setBuilder: function(builder) { + builderOut = builder; + } + }; + } + + function _makeSlicer(C, output) { + // C: Changeset, output: builder from _makeBuilder + // C is considered immutable, won't change or be changed + + // OOP style: state in environment + var charIndex = 0; // 0 <= charIndex <= C.newLen(); maximum value iff atEnd + var stripIndex = 0; // 0 <= stripIndex <= C.numStrips(); maximum value iff atEnd + var charWithinStrip = 0; // 0 <= charWithinStrip < curStripWidth() + var atEnd = false; + + var authorSlicer; + if (C.authors) { + authorSlicer = _makeAuthorSlicer(C.authors, output); + } + + var ptr = 3; + function curStartIndex() { return C[ptr]; } + function curNumTaken() { return C[ptr+1]; } + function curNewText() { return C[ptr+2]; } + function curStripWidth() { return curNumTaken() + curNewText().length; } + function assertNotAtEnd() { assert(! atEnd, "_slicer: can't move past changeset end"); } + function forwardInStrip(numChars) { + charWithinStrip += numChars; + charIndex += numChars; + } + function nextStrip() { + assertNotAtEnd(); + assert(charWithinStrip == curStripWidth(), "_slicer: not at strip end"); + charWithinStrip = 0; + stripIndex++; + ptr += 3; + if (stripIndex == C.numStrips()) { + atEnd = true; + } + } + function curNumNewCharsInRange(start, end) { + // takes two indices into the current strip's combined "taken" and "new" + // chars, and returns how many "new" chars are included in the range + assert(start <= end, "_slicer: curNumNewCharsInRange given out-of-order indices"); + var nt = curNumTaken(); + var nn = curNewText().length; + var s = nt; + var e = nt+nn; + if (s < start) s = start; + if (e > end) e = end; + if (e < s) return 0; + return e-s; + } + + var self; + return self = { + skipChars: function (n) { + assert(n >= 0, "_slicer: can't skip negative n"); + if (n == 0) return; + assertNotAtEnd(); + + var leftToSkip = n; + while (leftToSkip > 0) { + var leftInStrip = curStripWidth() - charWithinStrip; + if (leftToSkip >= leftInStrip) { + forwardInStrip(leftInStrip); + + if (authorSlicer) + authorSlicer.skipChars(curNumNewCharsInRange(charWithinStrip, + charWithinStrip + leftInStrip)); + + leftToSkip -= leftInStrip; + nextStrip(); + } + else { + if (authorSlicer) + authorSlicer.skipChars(curNumNewCharsInRange(charWithinStrip, + charWithinStrip + leftToSkip)); + + forwardInStrip(leftToSkip); + leftToSkip = 0; + } + } + }, + takeChars: function (n) { + assert(n >= 0, "_slicer: can't take negative n"); + if (n == 0) return; + assertNotAtEnd(); + + var leftToTake = n; + while (leftToTake > 0) { + if (curNumTaken() > 0 && charWithinStrip < curNumTaken()) { + // at least one char to take from current strip's numTaken + var leftInTaken = (curNumTaken() - charWithinStrip); + assert(leftInTaken > 0, "_slicer: should have leftInTaken > 0"); + var toTake = min(leftInTaken, leftToTake); + assert(toTake > 0, "_slicer: should have toTake > 0"); + output.appendOldText(curStartIndex() + charWithinStrip, toTake); + forwardInStrip(toTake); + leftToTake -= toTake; + } + if (leftToTake > 0 && curNewText().length > 0 && charWithinStrip >= curNumTaken() && + charWithinStrip < curStripWidth()) { + // at least one char to take from current strip's newText + var leftInNewText = (curStripWidth() - charWithinStrip); + assert(leftInNewText > 0, "_slicer: should have leftInNewText > 0"); + var toTake = min(leftInNewText, leftToTake); + assert(toTake > 0, "_slicer: should have toTake > 0"); + var newText = curNewText().substr(charWithinStrip - curNumTaken(), toTake); + if (authorSlicer) { + authorSlicer.takeChars(newText.length, newText); + } + else { + output.appendNewText(newText); + } + forwardInStrip(toTake); + leftToTake -= toTake; + } + assert(charWithinStrip <= curStripWidth(), "_slicer: past end of strip"); + if (charWithinStrip == curStripWidth()) { + nextStrip(); + } + } + }, + skipTo: function(n) { + self.skipChars(n - charIndex); + } + }; + } + + array.slicer = function(outputBuilder) { + return _makeSlicer(this, outputBuilder); + } + + array.compose = function(next) { + assert(next.oldLen() == this.newLen(), "mismatched composition"); + + var builder = _makeBuilder(this.oldLen(), !!(this.authors || next.authors)); + var slicer = _makeSlicer(this, builder); + + var authorSlicer; + if (next.authors) { + authorSlicer = _makeAuthorSlicer(next.authors, builder); + } + + next.eachStrip(function(s, t, n) { + slicer.skipTo(s); + slicer.takeChars(t); + if (authorSlicer) { + authorSlicer.takeChars(n.length, n); + } + else { + builder.appendNewText(n); + } + }, this); + + return builder.toChangeset(); + }; + + array.traverser = function() { + return _makeTraverser(this); + } + + function _makeTraverser(C) { + var s = C[3], t = C[4], n = C[5]; + var nextIndex = 6; + var indexIntoNewText = 0; + + var authorSlicer; + if (C.authors) { + authorSlicer = _makeAuthorSlicer(C.authors, null); + } + + function advanceIfPossible() { + if (t == 0 && n == "" && nextIndex < C.length) { + s = C[nextIndex]; + t = C[nextIndex+1]; + n = C[nextIndex+2]; + nextIndex += 3; + } + } + + var self; + return self = { + numTakenChars: function() { + // if starts with taken characters, then how many, else 0 + return (t > 0) ? t : 0; + }, + numNewChars: function() { + // if starts with new characters, then how many, else 0 + return (t == 0 && n.length > 0) ? n.length : 0; + }, + takenCharsStart: function() { + return (self.numTakenChars() > 0) ? s : 0; + }, + hasMore: function() { + return self.numTakenChars() > 0 || self.numNewChars() > 0; + }, + curIndex: function() { + return indexIntoNewText; + }, + consumeTakenChars: function (x) { + assert(self.numTakenChars() > 0, "_traverser: no taken chars"); + assert(x >= 0 && x <= self.numTakenChars(), "_traverser: bad number of taken chars"); + if (x == 0) return; + if (t == x) { s = 0; t = 0; } + else { s += x; t -= x; } + indexIntoNewText += x; + advanceIfPossible(); + }, + consumeNewChars: function(x) { + return self.appendNewChars(x, null); + }, + appendNewChars: function(x, builder) { + assert(self.numNewChars() > 0, "_traverser: no new chars"); + assert(x >= 0 && x <= self.numNewChars(), "_traverser: bad number of new chars"); + if (x == 0) return ""; + var str = n.substring(0, x); + n = n.substring(x); + indexIntoNewText += x; + advanceIfPossible(); + + if (builder) { + if (authorSlicer) { + authorSlicer.setBuilder(builder); + authorSlicer.takeChars(x, str); + } + else { + builder.appendNewText(str); + } + } + else { + if (authorSlicer) authorSlicer.skipChars(x); + return str; + } + }, + consumeAvailableTakenChars: function() { + return self.consumeTakenChars(self.numTakenChars()); + }, + consumeAvailableNewChars: function() { + return self.consumeNewChars(self.numNewChars()); + }, + appendAvailableNewChars: function(builder) { + return self.appendNewChars(self.numNewChars(), builder); + } + }; + } + + array.follow = function(prev, reverseInsertOrder) { + // prev: Changeset, reverseInsertOrder: boolean + + // A.compose(B.follow(A)) is the merging of Changesets A and B, which operate on the same old text. + // It is always the same as B.compose(A.follow(B, true)). + + assert(prev.oldLen() == this.oldLen(), "mismatched follow: "+prev.oldLen()+"/"+this.oldLen()); + var builder = _makeBuilder(prev.newLen(), !! this.authors); + var a = _makeTraverser(prev); + var b = _makeTraverser(this); + while (a.hasMore() || b.hasMore()) { + if (a.numNewChars() > 0 && ! reverseInsertOrder) { + builder.appendOldText(a.curIndex(), a.numNewChars()); + a.consumeAvailableNewChars(); + } + else if (b.numNewChars() > 0) { + b.appendAvailableNewChars(builder); + } + else if (a.numNewChars() > 0 && reverseInsertOrder) { + builder.appendOldText(a.curIndex(), a.numNewChars()); + a.consumeAvailableNewChars(); + } + else if (! b.hasMore()) a.consumeAvailableTakenChars(); + else if (! a.hasMore()) b.consumeAvailableTakenChars(); + else { + var x = a.takenCharsStart(); + var y = b.takenCharsStart(); + if (x < y) a.consumeTakenChars(min(a.numTakenChars(), y-x)); + else if (y < x) b.consumeTakenChars(min(b.numTakenChars(), x-y)); + else { + var takenByBoth = min(a.numTakenChars(), b.numTakenChars()); + builder.appendOldText(a.curIndex(), takenByBoth); + a.consumeTakenChars(takenByBoth); + b.consumeTakenChars(takenByBoth); + } + } + } + return builder.toChangeset(); + } + + array.encodeToString = function(asBinary) { + var stringDataArray = []; + var numsArray = []; + if (! asBinary) numsArray.push(this[0]); + numsArray.push(this[1], this[2]); + this.eachStrip(function(s, t, n) { + numsArray.push(s, t, n.length); + stringDataArray.push(n); + }, this); + if (! asBinary) { + return numsArray.join(',')+'|'+stringDataArray.join(''); + } + else { + return "A" + Changeset.numberArrayToString(numsArray) + +escapeCrazyUnicode(stringDataArray.join('')); + } + } + + function escapeCrazyUnicode(str) { + return str.replace(/\\/g, '\\\\').replace(/[\ud800-\udfff]/g, function (c) { + return "\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4); + }); + } + + array.applyToAttributedText = Changeset.applyToAttributedText; + + function splicesFromChanges(c) { + var splices = []; + // get a list of splices, [startChar, endChar, newText] + var traverser = c.traverser(); + var oldTextLength = c.oldLen(); + var indexIntoOldText = 0; + while (traverser.hasMore() || indexIntoOldText < oldTextLength) { + var newText = ""; + var startChar = indexIntoOldText; + var endChar = indexIntoOldText; + if (traverser.numNewChars() > 0) { + newText = traverser.consumeAvailableNewChars(); + } + if (traverser.hasMore()) { + endChar = traverser.takenCharsStart(); + indexIntoOldText = endChar + traverser.numTakenChars(); + traverser.consumeAvailableTakenChars(); + } + else { + endChar = oldTextLength; + indexIntoOldText = endChar; + } + if (endChar != startChar || newText.length > 0) { + splices.push([startChar, endChar, newText]); + } + } + return splices; + } + + array.toSplices = function() { + return splicesFromChanges(this); + } + + array.characterRangeFollowThis = function(selStartChar, selEndChar, insertionsAfter) { + var changeset = this; + // represent the selection as a changeset that replaces the selection with some finite string. + // Because insertions indicate intention, it doesn't matter what this string is, and even + // if the selectionChangeset is made to "follow" other changes it will still be the only + // insertion. + var selectionChangeset = + Changeset(changeset.oldLen()).builder().appendOldText(0, selStartChar).appendNewText( + "X").appendOldText(selEndChar, changeset.oldLen() - selEndChar).toChangeset(); + var newSelectionChangeset = selectionChangeset.follow(changeset, insertionsAfter); + var selectionSplices = newSelectionChangeset.toSplices(); + function includeChar(i) { + if (! includeChar.calledYet) { + selStartChar = i; + selEndChar = i; + includeChar.calledYet = true; + } + else { + if (i < selStartChar) selStartChar = i; + if (i > selEndChar) selEndChar = i; + } + } + for(var i=0; i<selectionSplices.length; i++) { + var s = selectionSplices[i]; + includeChar(s[0]); + includeChar(s[1]); + } + return [selStartChar, selEndChar]; + } + + return array; +} + +Changeset.MAGIC = "Changeset"; +Changeset.makeSplice = function(oldLength, spliceStart, numRemoved, stringInserted) { + oldLength = (oldLength || 0); + spliceStart = (spliceStart || 0); + numRemoved = (numRemoved || 0); + stringInserted = String(stringInserted || ""); + + var builder = Changeset(oldLength).builder(); + builder.appendOldText(0, spliceStart); + builder.appendNewText(stringInserted); + builder.appendOldText(spliceStart + numRemoved, oldLength - numRemoved - spliceStart); + return builder.toChangeset(); +}; +Changeset.identity = function(len) { + return Changeset(len).builder().appendOldText(0, len).toChangeset(); +}; +Changeset.decodeFromString = function(str) { + function error(msg) { var e = new Error(msg); e.easysync = true; throw e; } + function toHex(str) { + var a = []; + a.push("length["+str.length+"]:"); + var TRUNC=20; + for(var i=0;i<str.substring(0,TRUNC).length;i++) { + a.push(("000"+str.charCodeAt(i).toString(16)).slice(-4)); + } + if (str.length > TRUNC) a.push("..."); + return a.join(' '); + } + function unescapeCrazyUnicode(str) { + return str.replace(/\\(u....|\\)/g, function(seq) { + if (seq == "\\\\") return "\\"; + return String.fromCharCode(Number("0x"+seq.substring(2))); + }); + } + + var numData, stringData; + var binary = false; + var typ = str.charAt(0); + if (typ == "B" || typ == "A") { + var result = Changeset.numberArrayFromString(str, 1); + numData = result[0]; + stringData = result[1]; + if (typ == "A") { + stringData = unescapeCrazyUnicode(stringData); + } + binary = true; + } + else if (typ == "C") { + var barPosition = str.indexOf('|'); + numData = str.substring(0, barPosition).split(','); + stringData = str.substring(barPosition+1); + } + else { + error("Not a changeset: "+toHex(str)); + } + var stringDataOffset = 0; + var array = []; + var ptr; + if (binary) { + array.push("Changeset", numData[0], numData[1]); + var ptr = 2; + } + else { + array.push(numData[0], Number(numData[1]), Number(numData[2])); + var ptr = 3; + } + while (ptr < numData.length) { + array.push(Number(numData[ptr++]), Number(numData[ptr++])); + var newTextLength = Number(numData[ptr++]); + array.push(stringData.substr(stringDataOffset, newTextLength)); + stringDataOffset += newTextLength; + } + if (stringDataOffset != stringData.length) { + error("Extra character data beyond end of encoded string ("+toHex(str)+")"); + } + return Changeset(array); +}; + +Changeset.numberArrayToString = function(nums) { + var array = []; + function writeNum(n) { + // does not support negative numbers + var twentyEightBit = (n & 0xfffffff); + if (twentyEightBit <= 0x7fff) { + array.push(String.fromCharCode(twentyEightBit)); + } + else { + array.push(String.fromCharCode(0xa000 | (twentyEightBit >> 15), + twentyEightBit & 0x7fff)); + } + } + writeNum(nums.length); + var len = nums.length; + for(var i=0;i<len;i++) { + writeNum(nums[i]); + } + return array.join(''); +}; + +Changeset.numberArrayFromString = function(str, startIndex) { + // returns [numberArray, remainingString] + var nums = []; + var strIndex = (startIndex || 0); + function readNum() { + var n = str.charCodeAt(strIndex++); + if (n > 0x7fff) { + if (n >= 0xa000) { + n = (((n & 0x1fff) << 15) | str.charCodeAt(strIndex++)); + } + else { + // legacy format + n = (((n & 0x1fff) << 16) | str.charCodeAt(strIndex++)); + } + } + return n; + } + var len = readNum(); + for(var i=0;i<len;i++) { + nums.push(readNum()); + } + return [nums, str.substring(strIndex)]; +}; + +(function() { + function repeatString(str, times) { + if (times <= 0) return ""; + var s = repeatString(str, times >> 1); + s += s; + if (times & 1) s += str; + return s; + } + function chr(n) { return String.fromCharCode(n+48); } + function ord(c) { return c.charCodeAt(0)-48; } + function runMatcher(c) { + // Takes "A" and returns /\u0041+/g . + // Avoid creating new objects unnecessarily by caching matchers + // as properties of this function. + var re = runMatcher[c]; + if (re) return re; + re = runMatcher[c] = new RegExp("\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4)+"+", 'g'); + return re; + } + function runLength(str, idx, c) { + var re = runMatcher(c); + re.lastIndex = idx; + var result = re.exec(str); + if (result && result[0]) { + return result[0].length; + } + return 0; + } + + // emptyObj may be a StorableObject + Changeset.initAttributedText = function(emptyObj, initialString, initialAuthor) { + var obj = emptyObj; + obj.authorMap = { 1: (initialAuthor || '') }; + obj.text = (initialString || ''); + obj.attribs = repeatString(chr(1), obj.text.length); + return obj; + }; + Changeset.gcAttributedText = function(atObj) { + // "garbage collect" the list of authors + var removedAuthors = []; + for(var a in atObj.authorMap) { + if (atObj.attribs.indexOf(chr(Number(a))) < 0) { + removedAuthors.push(atObj.authorMap[a]); + delete atObj.authorMap[a]; + } + } + return removedAuthors; + }; + Changeset.cloneAttributedText = function(emptyObj, atObj) { + var obj = emptyObj; + obj.text = atObj.text; // string + if (atObj.attribs) obj.attribs = atObj.attribs; // string + if (atObj.attribs_c) obj.attribs_c = atObj.attribs_c; // string + obj.authorMap = {}; + for(var a in atObj.authorMap) { + obj.authorMap[a] = atObj.authorMap[a]; + } + return obj; + }; + Changeset.applyToAttributedText = function(atObj, C) { + C = (C || this); + var oldText = atObj.text; + var oldAttribs = atObj.attribs; + Changeset._assert(C.isChangeset, "applyToAttributedText: 'this' is not a changeset"); + Changeset._assert(oldText.length == C.oldLen(), + "applyToAttributedText: mismatch "+oldText.length+" / "+C.oldLen()); + var textBuf = []; + var attribsBuf = []; + var authorMap = atObj.authorMap; + function authorId(author) { + for(var a in authorMap) { + if (authorMap[Number(a)] === author) { + return Number(a); + } + } + for(var i=1;i<=60000;i++) { + // don't use "in" because it's currently broken on StorableObjects + if (authorMap[i] === undefined) { + authorMap[i] = author; + return i; + } + } + } + var myBuilder = { appendNewText: function(txt, author) { + // object that acts as a "builder" in that it receives requests from + // authorSlicer to append text attributed to different authors + attribsBuf.push(repeatString(chr(authorId(author)), txt.length)); + } }; + var authorSlicer; + if (C.authors) { + authorSlicer = C.authorSlicer(myBuilder); + } + C.eachStrip(function (s, t, n) { + textBuf.push(oldText.substr(s, t), n); + attribsBuf.push(oldAttribs.substr(s, t)); + if (authorSlicer) { + authorSlicer.takeChars(n.length, n); + } + else { + myBuilder.appendNewText(n, ''); + } + }); + atObj.text = textBuf.join(''); + atObj.attribs = attribsBuf.join(''); + return atObj; + }; + Changeset.getAttributedTextCharAuthor = function(atObj, idx) { + return atObj.authorMap[ord(atObj.attribs.charAt(idx))]; + }; + Changeset.getAttributedTextCharRunLength = function(atObj, idx) { + var c = atObj.attribs.charAt(idx); + return runLength(atObj.attribs, idx, c); + }; + Changeset.eachAuthorInAttributedText = function(atObj, func) { + // call func(author, authorNum) + for(var a in atObj.authorMap) { + if (func(atObj.authorMap[a], Number(a))) break; + } + }; + Changeset.getAttributedTextAuthorByNum = function(atObj, n) { + return atObj.authorMap[n]; + }; + // Compressed attributed text can be cloned, but nothing else until uncompressed!! + Changeset.compressAttributedText = function(atObj) { + // idempotent, mutates the object, returns it + if (atObj.attribs) { + atObj.attribs_c = atObj.attribs.replace(/([\s\S])\1{0,63}/g, function(run) { + return run.charAt(0)+chr(run.length);; + }); + delete atObj.attribs; + } + return atObj; + }; + Changeset.decompressAttributedText = function(atObj) { + // idempotent, mutates the object, returns it + if (atObj.attribs_c) { + atObj.attribs = atObj.attribs_c.replace(/[\s\S][\s\S]/g, function(run) { + return repeatString(run.charAt(0), ord(run.charAt(1))); + }); + delete atObj.attribs_c; + } + return atObj; + }; +})(); diff --git a/trunk/etherpad/src/etherpad/collab/ace/easysync2.js b/trunk/etherpad/src/etherpad/collab/ace/easysync2.js new file mode 100644 index 0000000..0fa1ec4 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/easysync2.js @@ -0,0 +1,1968 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/easysync2.js +jimport("com.etherpad.Easysync2Support"); + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +//var _opt = (this.Easysync2Support || null); +var _opt = null; // disable optimization for now + +function AttribPool() { + var p = {}; + p.numToAttrib = {}; // e.g. {0: ['foo','bar']} + p.attribToNum = {}; // e.g. {'foo,bar': 0} + p.nextNum = 0; + + p.putAttrib = function(attrib, dontAddIfAbsent) { + var str = String(attrib); + if (str in p.attribToNum) { + return p.attribToNum[str]; + } + if (dontAddIfAbsent) { + return -1; + } + var num = p.nextNum++; + p.attribToNum[str] = num; + p.numToAttrib[num] = [String(attrib[0]||''), + String(attrib[1]||'')]; + return num; + }; + + p.getAttrib = function(num) { + var pair = p.numToAttrib[num]; + if (! pair) return pair; + return [pair[0], pair[1]]; // return a mutable copy + }; + + p.getAttribKey = function(num) { + var pair = p.numToAttrib[num]; + if (! pair) return ''; + return pair[0]; + }; + + p.getAttribValue = function(num) { + var pair = p.numToAttrib[num]; + if (! pair) return ''; + return pair[1]; + }; + + p.eachAttrib = function(func) { + for(var n in p.numToAttrib) { + var pair = p.numToAttrib[n]; + func(pair[0], pair[1]); + } + }; + + p.toJsonable = function() { + return {numToAttrib: p.numToAttrib, nextNum: p.nextNum}; + }; + + p.fromJsonable = function(obj) { + p.numToAttrib = obj.numToAttrib; + p.nextNum = obj.nextNum; + p.attribToNum = {}; + for(var n in p.numToAttrib) { + p.attribToNum[String(p.numToAttrib[n])] = Number(n); + } + return p; + }; + + return p; +} + +var Changeset = {}; + +Changeset.error = function error(msg) { var e = new Error(msg); e.easysync = true; throw e; }; +Changeset.assert = function assert(b, msgParts) { + if (! b) { + var msg = Array.prototype.slice.call(arguments, 1).join(''); + Changeset.error("Changeset: "+msg); + } +}; + +Changeset.parseNum = function(str) { return parseInt(str, 36); }; +Changeset.numToString = function(num) { return num.toString(36).toLowerCase(); }; +Changeset.toBaseTen = function(cs) { + var dollarIndex = cs.indexOf('$'); + var beforeDollar = cs.substring(0, dollarIndex); + var fromDollar = cs.substring(dollarIndex); + return beforeDollar.replace(/[0-9a-z]+/g, function(s) { + return String(Changeset.parseNum(s)); }) + fromDollar; +}; + +Changeset.oldLen = function(cs) { + return Changeset.unpack(cs).oldLen; +}; +Changeset.newLen = function(cs) { + return Changeset.unpack(cs).newLen; +}; + +Changeset.opIterator = function(opsStr, optStartIndex) { + //print(opsStr); + var regex = /((?:\*[0-9a-z]+)*)(?:\|([0-9a-z]+))?([-+=])([0-9a-z]+)|\?|/g; + var startIndex = (optStartIndex || 0); + var curIndex = startIndex; + var prevIndex = curIndex; + function nextRegexMatch() { + prevIndex = curIndex; + var result; + if (_opt) { + result = _opt.nextOpInString(opsStr, curIndex); + if (result) { + if (result.opcode() == '?') { + Changeset.error("Hit error opcode in op stream"); + } + curIndex = result.lastIndex(); + } + } + else { + regex.lastIndex = curIndex; + result = regex.exec(opsStr); + curIndex = regex.lastIndex; + if (result[0] == '?') { + Changeset.error("Hit error opcode in op stream"); + } + } + return result; + } + var regexResult = nextRegexMatch(); + var obj = Changeset.newOp(); + function next(optObj) { + var op = (optObj || obj); + if (_opt && regexResult) { + op.attribs = regexResult.attribs(); + op.lines = regexResult.lines(); + op.chars = regexResult.chars(); + op.opcode = regexResult.opcode(); + regexResult = nextRegexMatch(); + } + else if ((! _opt) && regexResult[0]) { + op.attribs = regexResult[1]; + op.lines = Changeset.parseNum(regexResult[2] || 0); + op.opcode = regexResult[3]; + op.chars = Changeset.parseNum(regexResult[4]); + regexResult = nextRegexMatch(); + } + else { + Changeset.clearOp(op); + } + return op; + } + function hasNext() { return !! (_opt ? regexResult : regexResult[0]); } + function lastIndex() { return prevIndex; } + return {next: next, hasNext: hasNext, lastIndex: lastIndex}; +}; + +Changeset.clearOp = function(op) { + op.opcode = ''; + op.chars = 0; + op.lines = 0; + op.attribs = ''; +}; +Changeset.newOp = function(optOpcode) { + return {opcode:(optOpcode || ''), chars:0, lines:0, attribs:''}; +}; +Changeset.cloneOp = function(op) { + return {opcode: op.opcode, chars: op.chars, lines: op.lines, attribs: op.attribs}; +}; +Changeset.copyOp = function(op1, op2) { + op2.opcode = op1.opcode; + op2.chars = op1.chars; + op2.lines = op1.lines; + op2.attribs = op1.attribs; +}; +Changeset.opString = function(op) { + // just for debugging + if (! op.opcode) return 'null'; + var assem = Changeset.opAssembler(); + assem.append(op); + return assem.toString(); +}; +Changeset.stringOp = function(str) { + // just for debugging + return Changeset.opIterator(str).next(); +}; + +Changeset.checkRep = function(cs) { + // doesn't check things that require access to attrib pool (e.g. attribute order) + // or original string (e.g. newline positions) + var unpacked = Changeset.unpack(cs); + var oldLen = unpacked.oldLen; + var newLen = unpacked.newLen; + var ops = unpacked.ops; + var charBank = unpacked.charBank; + + var assem = Changeset.smartOpAssembler(); + var oldPos = 0; + var calcNewLen = 0; + var numInserted = 0; + var iter = Changeset.opIterator(ops); + while (iter.hasNext()) { + var o = iter.next(); + switch (o.opcode) { + case '=': oldPos += o.chars; calcNewLen += o.chars; break; + case '-': oldPos += o.chars; Changeset.assert(oldPos < oldLen, oldPos," >= ",oldLen," in ",cs); break; + case '+': { + calcNewLen += o.chars; numInserted += o.chars; + Changeset.assert(calcNewLen < newLen, calcNewLen," >= ",newLen," in ",cs); + break; + } + } + assem.append(o); + } + + calcNewLen += oldLen - oldPos; + charBank = charBank.substring(0, numInserted); + while (charBank.length < numInserted) { + charBank += "?"; + } + + assem.endDocument(); + var normalized = Changeset.pack(oldLen, calcNewLen, assem.toString(), charBank); + Changeset.assert(normalized == cs, normalized,' != ',cs); + + return cs; +} + +Changeset.smartOpAssembler = function() { + // Like opAssembler but able to produce conforming changesets + // from slightly looser input, at the cost of speed. + // Specifically: + // - merges consecutive operations that can be merged + // - strips final "=" + // - ignores 0-length changes + // - reorders consecutive + and - (which margingOpAssembler doesn't do) + + var minusAssem = Changeset.mergingOpAssembler(); + var plusAssem = Changeset.mergingOpAssembler(); + var keepAssem = Changeset.mergingOpAssembler(); + var assem = Changeset.stringAssembler(); + var lastOpcode = ''; + var lengthChange = 0; + + function flushKeeps() { + assem.append(keepAssem.toString()); + keepAssem.clear(); + } + + function flushPlusMinus() { + assem.append(minusAssem.toString()); + minusAssem.clear(); + assem.append(plusAssem.toString()); + plusAssem.clear(); + } + + function append(op) { + if (! op.opcode) return; + if (! op.chars) return; + + if (op.opcode == '-') { + if (lastOpcode == '=') { + flushKeeps(); + } + minusAssem.append(op); + lengthChange -= op.chars; + } + else if (op.opcode == '+') { + if (lastOpcode == '=') { + flushKeeps(); + } + plusAssem.append(op); + lengthChange += op.chars; + } + else if (op.opcode == '=') { + if (lastOpcode != '=') { + flushPlusMinus(); + } + keepAssem.append(op); + } + lastOpcode = op.opcode; + } + + function appendOpWithText(opcode, text, attribs, pool) { + var op = Changeset.newOp(opcode); + op.attribs = Changeset.makeAttribsString(opcode, attribs, pool); + var lastNewlinePos = text.lastIndexOf('\n'); + if (lastNewlinePos < 0) { + op.chars = text.length; + op.lines = 0; + append(op); + } + else { + op.chars = lastNewlinePos+1; + op.lines = text.match(/\n/g).length; + append(op); + op.chars = text.length - (lastNewlinePos+1); + op.lines = 0; + append(op); + } + } + + function toString() { + flushPlusMinus(); + flushKeeps(); + return assem.toString(); + } + + function clear() { + minusAssem.clear(); + plusAssem.clear(); + keepAssem.clear(); + assem.clear(); + lengthChange = 0; + } + + function endDocument() { + keepAssem.endDocument(); + } + + function getLengthChange() { + return lengthChange; + } + + return {append: append, toString: toString, clear: clear, endDocument: endDocument, + appendOpWithText: appendOpWithText, getLengthChange: getLengthChange }; +}; + +if (_opt) { + Changeset.mergingOpAssembler = function() { + var assem = _opt.mergingOpAssembler(); + + function append(op) { + assem.append(op.opcode, op.chars, op.lines, op.attribs); + } + function toString() { + return assem.toString(); + } + function clear() { + assem.clear(); + } + function endDocument() { + assem.endDocument(); + } + + return {append: append, toString: toString, clear: clear, endDocument: endDocument}; + }; +} +else { + Changeset.mergingOpAssembler = function() { + // This assembler can be used in production; it efficiently + // merges consecutive operations that are mergeable, ignores + // no-ops, and drops final pure "keeps". It does not re-order + // operations. + var assem = Changeset.opAssembler(); + var bufOp = Changeset.newOp(); + + // If we get, for example, insertions [xxx\n,yyy], those don't merge, + // but if we get [xxx\n,yyy,zzz\n], that merges to [xxx\nyyyzzz\n]. + // This variable stores the length of yyy and any other newline-less + // ops immediately after it. + var bufOpAdditionalCharsAfterNewline = 0; + + function flush(isEndDocument) { + if (bufOp.opcode) { + if (isEndDocument && bufOp.opcode == '=' && ! bufOp.attribs) { + // final merged keep, leave it implicit + } + else { + assem.append(bufOp); + if (bufOpAdditionalCharsAfterNewline) { + bufOp.chars = bufOpAdditionalCharsAfterNewline; + bufOp.lines = 0; + assem.append(bufOp); + bufOpAdditionalCharsAfterNewline = 0; + } + } + bufOp.opcode = ''; + } + } + function append(op) { + if (op.chars > 0) { + if (bufOp.opcode == op.opcode && bufOp.attribs == op.attribs) { + if (op.lines > 0) { + // bufOp and additional chars are all mergeable into a multi-line op + bufOp.chars += bufOpAdditionalCharsAfterNewline + op.chars; + bufOp.lines += op.lines; + bufOpAdditionalCharsAfterNewline = 0; + } + else if (bufOp.lines == 0) { + // both bufOp and op are in-line + bufOp.chars += op.chars; + } + else { + // append in-line text to multi-line bufOp + bufOpAdditionalCharsAfterNewline += op.chars; + } + } + else { + flush(); + Changeset.copyOp(op, bufOp); + } + } + } + function endDocument() { + flush(true); + } + function toString() { + flush(); + return assem.toString(); + } + function clear() { + assem.clear(); + Changeset.clearOp(bufOp); + } + return {append: append, toString: toString, clear: clear, endDocument: endDocument}; + }; +} + +if (_opt) { + Changeset.opAssembler = function() { + var assem = _opt.opAssembler(); + // this function allows op to be mutated later (doesn't keep a ref) + function append(op) { + assem.append(op.opcode, op.chars, op.lines, op.attribs); + } + function toString() { + return assem.toString(); + } + function clear() { + assem.clear(); + } + return {append: append, toString: toString, clear: clear}; + }; +} +else { + Changeset.opAssembler = function() { + var pieces = []; + // this function allows op to be mutated later (doesn't keep a ref) + function append(op) { + pieces.push(op.attribs); + if (op.lines) { + pieces.push('|', Changeset.numToString(op.lines)); + } + pieces.push(op.opcode); + pieces.push(Changeset.numToString(op.chars)); + } + function toString() { + return pieces.join(''); + } + function clear() { + pieces.length = 0; + } + return {append: append, toString: toString, clear: clear}; + }; +} + +Changeset.stringIterator = function(str) { + var curIndex = 0; + function assertRemaining(n) { + Changeset.assert(n <= remaining(), "!(",n," <= ",remaining(),")"); + } + function take(n) { + assertRemaining(n); + var s = str.substr(curIndex, n); + curIndex += n; + return s; + } + function peek(n) { + assertRemaining(n); + var s = str.substr(curIndex, n); + return s; + } + function skip(n) { + assertRemaining(n); + curIndex += n; + } + function remaining() { + return str.length - curIndex; + } + return {take:take, skip:skip, remaining:remaining, peek:peek}; +}; + +Changeset.stringAssembler = function() { + var pieces = []; + function append(x) { + pieces.push(String(x)); + } + function toString() { + return pieces.join(''); + } + return {append: append, toString: toString}; +}; + +// "lines" need not be an array as long as it supports certain calls (lines_foo inside). +Changeset.textLinesMutator = function(lines) { + // Mutates lines, an array of strings, in place. + // Mutation operations have the same constraints as changeset operations + // with respect to newlines, but not the other additional constraints + // (i.e. ins/del ordering, forbidden no-ops, non-mergeability, final newline). + // Can be used to mutate lists of strings where the last char of each string + // is not actually a newline, but for the purposes of N and L values, + // the caller should pretend it is, and for things to work right in that case, the input + // to insert() should be a single line with no newlines. + + var curSplice = [0,0]; + var inSplice = false; + // position in document after curSplice is applied: + var curLine = 0, curCol = 0; + // invariant: if (inSplice) then (curLine is in curSplice[0] + curSplice.length - {2,3}) && + // curLine >= curSplice[0] + // invariant: if (inSplice && (curLine >= curSplice[0] + curSplice.length - 2)) then + // curCol == 0 + + function lines_applySplice(s) { + lines.splice.apply(lines, s); + } + function lines_toSource() { + return lines.toSource(); + } + function lines_get(idx) { + if (lines.get) { + return lines.get(idx); + } + else { + return lines[idx]; + } + } + // can be unimplemented if removeLines's return value not needed + function lines_slice(start, end) { + if (lines.slice) { + return lines.slice(start, end); + } + else { + return []; + } + } + function lines_length() { + if ((typeof lines.length) == "number") { + return lines.length; + } + else { + return lines.length(); + } + } + + function enterSplice() { + curSplice[0] = curLine; + curSplice[1] = 0; + if (curCol > 0) { + putCurLineInSplice(); + } + inSplice = true; + } + function leaveSplice() { + lines_applySplice(curSplice); + curSplice.length = 2; + curSplice[0] = curSplice[1] = 0; + inSplice = false; + } + function isCurLineInSplice() { + return (curLine - curSplice[0] < (curSplice.length - 2)); + } + function debugPrint(typ) { + print(typ+": "+curSplice.toSource()+" / "+curLine+","+curCol+" / "+lines_toSource()); + } + function putCurLineInSplice() { + if (! isCurLineInSplice()) { + curSplice.push(lines_get(curSplice[0] + curSplice[1])); + curSplice[1]++; + } + return 2 + curLine - curSplice[0]; + } + + function skipLines(L, includeInSplice) { + if (L) { + if (includeInSplice) { + if (! inSplice) { + enterSplice(); + } + for(var i=0;i<L;i++) { + curCol = 0; + putCurLineInSplice(); + curLine++; + } + } + else { + if (inSplice) { + if (L > 1) { + leaveSplice(); + } + else { + putCurLineInSplice(); + } + } + curLine += L; + curCol = 0; + } + //print(inSplice+" / "+isCurLineInSplice()+" / "+curSplice[0]+" / "+curSplice[1]+" / "+lines.length); + /*if (inSplice && (! isCurLineInSplice()) && (curSplice[0] + curSplice[1] < lines.length)) { + print("BLAH"); + putCurLineInSplice(); + }*/ // tests case foo in remove(), which isn't otherwise covered in current impl + } + //debugPrint("skip"); + } + + function skip(N, L, includeInSplice) { + if (N) { + if (L) { + skipLines(L, includeInSplice); + } + else { + if (includeInSplice && ! inSplice) { + enterSplice(); + } + if (inSplice) { + putCurLineInSplice(); + } + curCol += N; + //debugPrint("skip"); + } + } + } + + function removeLines(L) { + var removed = ''; + if (L) { + if (! inSplice) { + enterSplice(); + } + function nextKLinesText(k) { + var m = curSplice[0] + curSplice[1]; + return lines_slice(m, m+k).join(''); + } + if (isCurLineInSplice()) { + //print(curCol); + if (curCol == 0) { + removed = curSplice[curSplice.length-1]; + // print("FOO"); // case foo + curSplice.length--; + removed += nextKLinesText(L-1); + curSplice[1] += L-1; + } + else { + removed = nextKLinesText(L-1); + curSplice[1] += L-1; + var sline = curSplice.length - 1; + removed = curSplice[sline].substring(curCol) + removed; + curSplice[sline] = curSplice[sline].substring(0, curCol) + + lines_get(curSplice[0] + curSplice[1]); + curSplice[1] += 1; + } + } + else { + removed = nextKLinesText(L); + curSplice[1] += L; + } + //debugPrint("remove"); + } + return removed; + } + + function remove(N, L) { + var removed = ''; + if (N) { + if (L) { + return removeLines(L); + } + else { + if (! inSplice) { + enterSplice(); + } + var sline = putCurLineInSplice(); + removed = curSplice[sline].substring(curCol, curCol+N); + curSplice[sline] = curSplice[sline].substring(0, curCol) + + curSplice[sline].substring(curCol+N); + //debugPrint("remove"); + } + } + return removed; + } + + function insert(text, L) { + if (text) { + if (! inSplice) { + enterSplice(); + } + if (L) { + var newLines = Changeset.splitTextLines(text); + if (isCurLineInSplice()) { + //if (curCol == 0) { + //curSplice.length--; + //curSplice[1]--; + //Array.prototype.push.apply(curSplice, newLines); + //curLine += newLines.length; + //} + //else { + var sline = curSplice.length - 1; + var theLine = curSplice[sline]; + var lineCol = curCol; + curSplice[sline] = theLine.substring(0, lineCol) + newLines[0]; + curLine++; + newLines.splice(0, 1); + Array.prototype.push.apply(curSplice, newLines); + curLine += newLines.length; + curSplice.push(theLine.substring(lineCol)); + curCol = 0; + //} + } + else { + Array.prototype.push.apply(curSplice, newLines); + curLine += newLines.length; + } + } + else { + var sline = putCurLineInSplice(); + curSplice[sline] = curSplice[sline].substring(0, curCol) + + text + curSplice[sline].substring(curCol); + curCol += text.length; + } + //debugPrint("insert"); + } + } + + function hasMore() { + //print(lines.length+" / "+inSplice+" / "+(curSplice.length - 2)+" / "+curSplice[1]); + var docLines = lines_length(); + if (inSplice) { + docLines += curSplice.length - 2 - curSplice[1]; + } + return curLine < docLines; + } + + function close() { + if (inSplice) { + leaveSplice(); + } + //debugPrint("close"); + } + + var self = {skip:skip, remove:remove, insert:insert, close:close, hasMore:hasMore, + removeLines:removeLines, skipLines: skipLines}; + return self; +}; + +Changeset.applyZip = function(in1, idx1, in2, idx2, func) { + var iter1 = Changeset.opIterator(in1, idx1); + var iter2 = Changeset.opIterator(in2, idx2); + var assem = Changeset.smartOpAssembler(); + var op1 = Changeset.newOp(); + var op2 = Changeset.newOp(); + var opOut = Changeset.newOp(); + while (op1.opcode || iter1.hasNext() || op2.opcode || iter2.hasNext()) { + if ((! op1.opcode) && iter1.hasNext()) iter1.next(op1); + if ((! op2.opcode) && iter2.hasNext()) iter2.next(op2); + func(op1, op2, opOut); + if (opOut.opcode) { + //print(opOut.toSource()); + assem.append(opOut); + opOut.opcode = ''; + } + } + assem.endDocument(); + return assem.toString(); +}; + +Changeset.unpack = function(cs) { + var headerRegex = /Z:([0-9a-z]+)([><])([0-9a-z]+)|/; + var headerMatch = headerRegex.exec(cs); + if ((! headerMatch) || (! headerMatch[0])) { + Changeset.error("Not a changeset: "+cs); + } + var oldLen = Changeset.parseNum(headerMatch[1]); + var changeSign = (headerMatch[2] == '>') ? 1 : -1; + var changeMag = Changeset.parseNum(headerMatch[3]); + var newLen = oldLen + changeSign*changeMag; + var opsStart = headerMatch[0].length; + var opsEnd = cs.indexOf("$"); + if (opsEnd < 0) opsEnd = cs.length; + return {oldLen: oldLen, newLen: newLen, ops: cs.substring(opsStart, opsEnd), + charBank: cs.substring(opsEnd+1)}; +}; + +Changeset.pack = function(oldLen, newLen, opsStr, bank) { + var lenDiff = newLen - oldLen; + var lenDiffStr = (lenDiff >= 0 ? + '>'+Changeset.numToString(lenDiff) : + '<'+Changeset.numToString(-lenDiff)); + var a = []; + a.push('Z:', Changeset.numToString(oldLen), lenDiffStr, opsStr, '$', bank); + return a.join(''); +}; + +Changeset.applyToText = function(cs, str) { + var unpacked = Changeset.unpack(cs); + Changeset.assert(str.length == unpacked.oldLen, + "mismatched apply: ",str.length," / ",unpacked.oldLen); + var csIter = Changeset.opIterator(unpacked.ops); + var bankIter = Changeset.stringIterator(unpacked.charBank); + var strIter = Changeset.stringIterator(str); + var assem = Changeset.stringAssembler(); + while (csIter.hasNext()) { + var op = csIter.next(); + switch(op.opcode) { + case '+': assem.append(bankIter.take(op.chars)); break; + case '-': strIter.skip(op.chars); break; + case '=': assem.append(strIter.take(op.chars)); break; + } + } + assem.append(strIter.take(strIter.remaining())); + return assem.toString(); +}; + +Changeset.mutateTextLines = function(cs, lines) { + var unpacked = Changeset.unpack(cs); + var csIter = Changeset.opIterator(unpacked.ops); + var bankIter = Changeset.stringIterator(unpacked.charBank); + var mut = Changeset.textLinesMutator(lines); + while (csIter.hasNext()) { + var op = csIter.next(); + switch(op.opcode) { + case '+': mut.insert(bankIter.take(op.chars), op.lines); break; + case '-': mut.remove(op.chars, op.lines); break; + case '=': mut.skip(op.chars, op.lines, (!! op.attribs)); break; + } + } + mut.close(); +}; + +Changeset.composeAttributes = function(att1, att2, resultIsMutation, pool) { + // att1 and att2 are strings like "*3*f*1c", asMutation is a boolean. + + // Sometimes attribute (key,value) pairs are treated as attribute presence + // information, while other times they are treated as operations that + // mutate a set of attributes, and this affects whether an empty value + // is a deletion or a change. + // Examples, of the form (att1Items, att2Items, resultIsMutation) -> result + // ([], [(bold, )], true) -> [(bold, )] + // ([], [(bold, )], false) -> [] + // ([], [(bold, true)], true) -> [(bold, true)] + // ([], [(bold, true)], false) -> [(bold, true)] + // ([(bold, true)], [(bold, )], true) -> [(bold, )] + // ([(bold, true)], [(bold, )], false) -> [] + + // pool can be null if att2 has no attributes. + + if ((! att1) && resultIsMutation) { + // In the case of a mutation (i.e. composing two changesets), + // an att2 composed with an empy att1 is just att2. If att1 + // is part of an attribution string, then att2 may remove + // attributes that are already gone, so don't do this optimization. + return att2; + } + if (! att2) return att1; + var atts = []; + att1.replace(/\*([0-9a-z]+)/g, function(_, a) { + atts.push(pool.getAttrib(Changeset.parseNum(a))); + return ''; + }); + att2.replace(/\*([0-9a-z]+)/g, function(_, a) { + var pair = pool.getAttrib(Changeset.parseNum(a)); + var found = false; + for(var i=0;i<atts.length;i++) { + var oldPair = atts[i]; + if (oldPair[0] == pair[0]) { + if (pair[1] || resultIsMutation) { + oldPair[1] = pair[1]; + } + else { + atts.splice(i, 1); + } + found = true; + break; + } + } + if ((! found) && (pair[1] || resultIsMutation)) { + atts.push(pair); + } + return ''; + }); + atts.sort(); + var buf = Changeset.stringAssembler(); + for(var i=0;i<atts.length;i++) { + buf.append('*'); + buf.append(Changeset.numToString(pool.putAttrib(atts[i]))); + } + //print(att1+" / "+att2+" / "+buf.toString()); + return buf.toString(); +}; + +Changeset._slicerZipperFunc = function(attOp, csOp, opOut, pool) { + // attOp is the op from the sequence that is being operated on, either an + // attribution string or the earlier of two changesets being composed. + // pool can be null if definitely not needed. + + //print(csOp.toSource()+" "+attOp.toSource()+" "+opOut.toSource()); + if (attOp.opcode == '-') { + Changeset.copyOp(attOp, opOut); + attOp.opcode = ''; + } + else if (! attOp.opcode) { + Changeset.copyOp(csOp, opOut); + csOp.opcode = ''; + } + else { + switch (csOp.opcode) { + case '-': { + if (csOp.chars <= attOp.chars) { + // delete or delete part + if (attOp.opcode == '=') { + opOut.opcode = '-'; + opOut.chars = csOp.chars; + opOut.lines = csOp.lines; + opOut.attribs = ''; + } + attOp.chars -= csOp.chars; + attOp.lines -= csOp.lines; + csOp.opcode = ''; + if (! attOp.chars) { + attOp.opcode = ''; + } + } + else { + // delete and keep going + if (attOp.opcode == '=') { + opOut.opcode = '-'; + opOut.chars = attOp.chars; + opOut.lines = attOp.lines; + opOut.attribs = ''; + } + csOp.chars -= attOp.chars; + csOp.lines -= attOp.lines; + attOp.opcode = ''; + } + break; + } + case '+': { + // insert + Changeset.copyOp(csOp, opOut); + csOp.opcode = ''; + break; + } + case '=': { + if (csOp.chars <= attOp.chars) { + // keep or keep part + opOut.opcode = attOp.opcode; + opOut.chars = csOp.chars; + opOut.lines = csOp.lines; + opOut.attribs = Changeset.composeAttributes(attOp.attribs, csOp.attribs, + attOp.opcode == '=', pool); + csOp.opcode = ''; + attOp.chars -= csOp.chars; + attOp.lines -= csOp.lines; + if (! attOp.chars) { + attOp.opcode = ''; + } + } + else { + // keep and keep going + opOut.opcode = attOp.opcode; + opOut.chars = attOp.chars; + opOut.lines = attOp.lines; + opOut.attribs = Changeset.composeAttributes(attOp.attribs, csOp.attribs, + attOp.opcode == '=', pool); + attOp.opcode = ''; + csOp.chars -= attOp.chars; + csOp.lines -= attOp.lines; + } + break; + } + case '': { + Changeset.copyOp(attOp, opOut); + attOp.opcode = ''; + break; + } + } + } +}; + +Changeset.applyToAttribution = function(cs, astr, pool) { + var unpacked = Changeset.unpack(cs); + + return Changeset.applyZip(astr, 0, unpacked.ops, 0, function(op1, op2, opOut) { + return Changeset._slicerZipperFunc(op1, op2, opOut, pool); + }); +}; + +/*Changeset.oneInsertedLineAtATimeOpIterator = function(opsStr, optStartIndex, charBank) { + var iter = Changeset.opIterator(opsStr, optStartIndex); + var bankIndex = 0; + +};*/ + +Changeset.mutateAttributionLines = function(cs, lines, pool) { + //dmesg(cs); + //dmesg(lines.toSource()+" ->"); + + var unpacked = Changeset.unpack(cs); + var csIter = Changeset.opIterator(unpacked.ops); + var csBank = unpacked.charBank; + var csBankIndex = 0; + // treat the attribution lines as text lines, mutating a line at a time + var mut = Changeset.textLinesMutator(lines); + + var lineIter = null; + function isNextMutOp() { + return (lineIter && lineIter.hasNext()) || mut.hasMore(); + } + function nextMutOp(destOp) { + if ((!(lineIter && lineIter.hasNext())) && mut.hasMore()) { + var line = mut.removeLines(1); + lineIter = Changeset.opIterator(line); + } + if (lineIter && lineIter.hasNext()) { + lineIter.next(destOp); + } + else { + destOp.opcode = ''; + } + } + var lineAssem = null; + function outputMutOp(op) { + //print("outputMutOp: "+op.toSource()); + if (! lineAssem) { + lineAssem = Changeset.mergingOpAssembler(); + } + lineAssem.append(op); + if (op.lines > 0) { + Changeset.assert(op.lines == 1, "Can't have op.lines of ",op.lines," in attribution lines"); + // ship it to the mut + mut.insert(lineAssem.toString(), 1); + lineAssem = null; + } + } + + var csOp = Changeset.newOp(); + var attOp = Changeset.newOp(); + var opOut = Changeset.newOp(); + while (csOp.opcode || csIter.hasNext() || attOp.opcode || isNextMutOp()) { + if ((! csOp.opcode) && csIter.hasNext()) { + csIter.next(csOp); + } + //print(csOp.toSource()+" "+attOp.toSource()+" "+opOut.toSource()); + //print(csOp.opcode+"/"+csOp.lines+"/"+csOp.attribs+"/"+lineAssem+"/"+lineIter+"/"+(lineIter?lineIter.hasNext():null)); + //print("csOp: "+csOp.toSource()); + if ((! csOp.opcode) && (! attOp.opcode) && + (! lineAssem) && (! (lineIter && lineIter.hasNext()))) { + break; // done + } + else if (csOp.opcode == '=' && csOp.lines > 0 && (! csOp.attribs) && (! attOp.opcode) && + (! lineAssem) && (! (lineIter && lineIter.hasNext()))) { + // skip multiple lines; this is what makes small changes not order of the document size + mut.skipLines(csOp.lines); + //print("skipped: "+csOp.lines); + csOp.opcode = ''; + } + else if (csOp.opcode == '+') { + if (csOp.lines > 1) { + var firstLineLen = csBank.indexOf('\n', csBankIndex) + 1 - csBankIndex; + Changeset.copyOp(csOp, opOut); + csOp.chars -= firstLineLen; + csOp.lines--; + opOut.lines = 1; + opOut.chars = firstLineLen; + } + else { + Changeset.copyOp(csOp, opOut); + csOp.opcode = ''; + } + outputMutOp(opOut); + csBankIndex += opOut.chars; + opOut.opcode = ''; + } + else { + if ((! attOp.opcode) && isNextMutOp()) { + nextMutOp(attOp); + } + //print("attOp: "+attOp.toSource()); + Changeset._slicerZipperFunc(attOp, csOp, opOut, pool); + if (opOut.opcode) { + outputMutOp(opOut); + opOut.opcode = ''; + } + } + } + + Changeset.assert(! lineAssem, "line assembler not finished"); + mut.close(); + + //dmesg("-> "+lines.toSource()); +}; + +Changeset.joinAttributionLines = function(theAlines) { + var assem = Changeset.mergingOpAssembler(); + for(var i=0;i<theAlines.length;i++) { + var aline = theAlines[i]; + var iter = Changeset.opIterator(aline); + while (iter.hasNext()) { + assem.append(iter.next()); + } + } + return assem.toString(); +}; + +Changeset.splitAttributionLines = function(attrOps, text) { + var iter = Changeset.opIterator(attrOps); + var assem = Changeset.mergingOpAssembler(); + var lines = []; + var pos = 0; + + function appendOp(op) { + assem.append(op); + if (op.lines > 0) { + lines.push(assem.toString()); + assem.clear(); + } + pos += op.chars; + } + + while (iter.hasNext()) { + var op = iter.next(); + var numChars = op.chars; + var numLines = op.lines; + while (numLines > 1) { + var newlineEnd = text.indexOf('\n', pos)+1; + Changeset.assert(newlineEnd > 0, "newlineEnd <= 0 in splitAttributionLines"); + op.chars = newlineEnd - pos; + op.lines = 1; + appendOp(op); + numChars -= op.chars; + numLines -= op.lines; + } + if (numLines == 1) { + op.chars = numChars; + op.lines = 1; + } + appendOp(op); + } + + return lines; +}; + +Changeset.splitTextLines = function(text) { + return text.match(/[^\n]*(?:\n|[^\n]$)/g); +}; + +Changeset.compose = function(cs1, cs2, pool) { + var unpacked1 = Changeset.unpack(cs1); + var unpacked2 = Changeset.unpack(cs2); + var len1 = unpacked1.oldLen; + var len2 = unpacked1.newLen; + Changeset.assert(len2 == unpacked2.oldLen, "mismatched composition"); + var len3 = unpacked2.newLen; + var bankIter1 = Changeset.stringIterator(unpacked1.charBank); + var bankIter2 = Changeset.stringIterator(unpacked2.charBank); + var bankAssem = Changeset.stringAssembler(); + + var newOps = Changeset.applyZip(unpacked1.ops, 0, unpacked2.ops, 0, function(op1, op2, opOut) { + //var debugBuilder = Changeset.stringAssembler(); + //debugBuilder.append(Changeset.opString(op1)); + //debugBuilder.append(','); + //debugBuilder.append(Changeset.opString(op2)); + //debugBuilder.append(' / '); + + var op1code = op1.opcode; + var op2code = op2.opcode; + if (op1code == '+' && op2code == '-') { + bankIter1.skip(Math.min(op1.chars, op2.chars)); + } + Changeset._slicerZipperFunc(op1, op2, opOut, pool); + if (opOut.opcode == '+') { + if (op2code == '+') { + bankAssem.append(bankIter2.take(opOut.chars)); + } + else { + bankAssem.append(bankIter1.take(opOut.chars)); + } + } + + //debugBuilder.append(Changeset.opString(op1)); + //debugBuilder.append(','); + //debugBuilder.append(Changeset.opString(op2)); + //debugBuilder.append(' -> '); + //debugBuilder.append(Changeset.opString(opOut)); + //print(debugBuilder.toString()); + }); + + return Changeset.pack(len1, len3, newOps, bankAssem.toString()); +}; + +Changeset.attributeTester = function(attribPair, pool) { + // returns a function that tests if a string of attributes + // (e.g. *3*4) contains a given attribute key,value that + // is already present in the pool. + if (! pool) { + return never; + } + var attribNum = pool.putAttrib(attribPair, true); + if (attribNum < 0) { + return never; + } + else { + var re = new RegExp('\\*'+Changeset.numToString(attribNum)+ + '(?!\\w)'); + return function(attribs) { + return re.test(attribs); + }; + } + function never(attribs) { return false; } +}; + +Changeset.identity = function(N) { + return Changeset.pack(N, N, "", ""); +}; + +Changeset.makeSplice = function(oldFullText, spliceStart, numRemoved, newText, optNewTextAPairs, pool) { + var oldLen = oldFullText.length; + + if (spliceStart >= oldLen) { + spliceStart = oldLen - 1; + } + if (numRemoved > oldFullText.length - spliceStart - 1) { + numRemoved = oldFullText.length - spliceStart - 1; + } + var oldText = oldFullText.substring(spliceStart, spliceStart+numRemoved); + var newLen = oldLen + newText.length - oldText.length; + + var assem = Changeset.smartOpAssembler(); + assem.appendOpWithText('=', oldFullText.substring(0, spliceStart)); + assem.appendOpWithText('-', oldText); + assem.appendOpWithText('+', newText, optNewTextAPairs, pool); + assem.endDocument(); + return Changeset.pack(oldLen, newLen, assem.toString(), newText); +}; + +Changeset.toSplices = function(cs) { + // get a list of splices, [startChar, endChar, newText] + + var unpacked = Changeset.unpack(cs); + var splices = []; + + var oldPos = 0; + var iter = Changeset.opIterator(unpacked.ops); + var charIter = Changeset.stringIterator(unpacked.charBank); + var inSplice = false; + while (iter.hasNext()) { + var op = iter.next(); + if (op.opcode == '=') { + oldPos += op.chars; + inSplice = false; + } + else { + if (! inSplice) { + splices.push([oldPos, oldPos, ""]); + inSplice = true; + } + if (op.opcode == '-') { + oldPos += op.chars; + splices[splices.length-1][1] += op.chars; + } + else if (op.opcode == '+') { + splices[splices.length-1][2] += charIter.take(op.chars); + } + } + } + + return splices; +}; + +Changeset.characterRangeFollow = function(cs, startChar, endChar, insertionsAfter) { + var newStartChar = startChar; + var newEndChar = endChar; + var splices = Changeset.toSplices(cs); + var lengthChangeSoFar = 0; + for(var i=0;i<splices.length;i++) { + var splice = splices[i]; + var spliceStart = splice[0] + lengthChangeSoFar; + var spliceEnd = splice[1] + lengthChangeSoFar; + var newTextLength = splice[2].length; + var thisLengthChange = newTextLength - (spliceEnd - spliceStart); + + if (spliceStart <= newStartChar && spliceEnd >= newEndChar) { + // splice fully replaces/deletes range + // (also case that handles insertion at a collapsed selection) + if (insertionsAfter) { + newStartChar = newEndChar = spliceStart; + } + else { + newStartChar = newEndChar = spliceStart + newTextLength; + } + } + else if (spliceEnd <= newStartChar) { + // splice is before range + newStartChar += thisLengthChange; + newEndChar += thisLengthChange; + } + else if (spliceStart >= newEndChar) { + // splice is after range + } + else if (spliceStart >= newStartChar && spliceEnd <= newEndChar) { + // splice is inside range + newEndChar += thisLengthChange; + } + else if (spliceEnd < newEndChar) { + // splice overlaps beginning of range + newStartChar = spliceStart + newTextLength; + newEndChar += thisLengthChange; + } + else { + // splice overlaps end of range + newEndChar = spliceStart; + } + + lengthChangeSoFar += thisLengthChange; + } + + return [newStartChar, newEndChar]; +}; + +Changeset.moveOpsToNewPool = function(cs, oldPool, newPool) { + // works on changeset or attribution string + var dollarPos = cs.indexOf('$'); + if (dollarPos < 0) { + dollarPos = cs.length; + } + var upToDollar = cs.substring(0, dollarPos); + var fromDollar = cs.substring(dollarPos); + // order of attribs stays the same + return upToDollar.replace(/\*([0-9a-z]+)/g, function(_, a) { + var oldNum = Changeset.parseNum(a); + var pair = oldPool.getAttrib(oldNum); + var newNum = newPool.putAttrib(pair); + return '*'+Changeset.numToString(newNum); + }) + fromDollar; +}; + +Changeset.makeAttribution = function(text) { + var assem = Changeset.smartOpAssembler(); + assem.appendOpWithText('+', text); + return assem.toString(); +}; + +// callable on a changeset, attribution string, or attribs property of an op +Changeset.eachAttribNumber = function(cs, func) { + var dollarPos = cs.indexOf('$'); + if (dollarPos < 0) { + dollarPos = cs.length; + } + var upToDollar = cs.substring(0, dollarPos); + + upToDollar.replace(/\*([0-9a-z]+)/g, function(_, a) { + func(Changeset.parseNum(a)); + return ''; + }); +}; + +// callable on a changeset, attribution string, or attribs property of an op, +// though it may easily create adjacent ops that can be merged. +Changeset.filterAttribNumbers = function(cs, filter) { + return Changeset.mapAttribNumbers(cs, filter); +}; + +Changeset.mapAttribNumbers = function(cs, func) { + var dollarPos = cs.indexOf('$'); + if (dollarPos < 0) { + dollarPos = cs.length; + } + var upToDollar = cs.substring(0, dollarPos); + + var newUpToDollar = upToDollar.replace(/\*([0-9a-z]+)/g, function(s, a) { + var n = func(Changeset.parseNum(a)); + if (n === true) { + return s; + } + else if ((typeof n) === "number") { + return '*'+Changeset.numToString(n); + } + else { + return ''; + } + }); + + return newUpToDollar + cs.substring(dollarPos); +}; + +Changeset.makeAText = function(text, attribs) { + return { text: text, attribs: (attribs || Changeset.makeAttribution(text)) }; +}; + +Changeset.applyToAText = function(cs, atext, pool) { + return { text: Changeset.applyToText(cs, atext.text), + attribs: Changeset.applyToAttribution(cs, atext.attribs, pool) }; +}; + +Changeset.cloneAText = function(atext) { + return { text: atext.text, attribs: atext.attribs }; +}; + +Changeset.copyAText = function(atext1, atext2) { + atext2.text = atext1.text; + atext2.attribs = atext1.attribs; +}; + +Changeset.appendATextToAssembler = function(atext, assem) { + // intentionally skips last newline char of atext + var iter = Changeset.opIterator(atext.attribs); + var op = Changeset.newOp(); + while (iter.hasNext()) { + iter.next(op); + if (! iter.hasNext()) { + // last op, exclude final newline + if (op.lines <= 1) { + op.lines = 0; + op.chars--; + if (op.chars) { + assem.append(op); + } + } + else { + var nextToLastNewlineEnd = + atext.text.lastIndexOf('\n', atext.text.length-2) + 1; + var lastLineLength = atext.text.length - nextToLastNewlineEnd - 1; + op.lines--; + op.chars -= (lastLineLength + 1); + assem.append(op); + op.lines = 0; + op.chars = lastLineLength; + if (op.chars) { + assem.append(op); + } + } + } + else { + assem.append(op); + } + } +}; + +Changeset.prepareForWire = function(cs, pool) { + var newPool = new AttribPool(); + var newCs = Changeset.moveOpsToNewPool(cs, pool, newPool); + return {translated: newCs, pool: newPool}; +}; + +Changeset.isIdentity = function(cs) { + var unpacked = Changeset.unpack(cs); + return unpacked.ops == "" && unpacked.oldLen == unpacked.newLen; +}; + +Changeset.opAttributeValue = function(op, key, pool) { + return Changeset.attribsAttributeValue(op.attribs, key, pool); +}; + +Changeset.attribsAttributeValue = function(attribs, key, pool) { + var value = ''; + if (attribs) { + Changeset.eachAttribNumber(attribs, function(n) { + if (pool.getAttribKey(n) == key) { + value = pool.getAttribValue(n); + } + }); + } + return value; +}; + +Changeset.builder = function(oldLen) { + var assem = Changeset.smartOpAssembler(); + var o = Changeset.newOp(); + var charBank = Changeset.stringAssembler(); + + var self = { + // attribs are [[key1,value1],[key2,value2],...] or '*0*1...' (no pool needed in latter case) + keep: function(N, L, attribs, pool) { + o.opcode = '='; + o.attribs = (attribs && + Changeset.makeAttribsString('=', attribs, pool)) || ''; + o.chars = N; + o.lines = (L || 0); + assem.append(o); + return self; + }, + keepText: function(text, attribs, pool) { + assem.appendOpWithText('=', text, attribs, pool); + return self; + }, + insert: function(text, attribs, pool) { + assem.appendOpWithText('+', text, attribs, pool); + charBank.append(text); + return self; + }, + remove: function(N, L) { + o.opcode = '-'; + o.attribs = ''; + o.chars = N; + o.lines = (L || 0); + assem.append(o); + return self; + }, + toString: function() { + assem.endDocument(); + var newLen = oldLen + assem.getLengthChange(); + return Changeset.pack(oldLen, newLen, assem.toString(), + charBank.toString()); + } + }; + + return self; +}; + +Changeset.makeAttribsString = function(opcode, attribs, pool) { + // makeAttribsString(opcode, '*3') or makeAttribsString(opcode, [['foo','bar']], myPool) work + if (! attribs) { + return ''; + } + else if ((typeof attribs) == "string") { + return attribs; + } + else if (pool && attribs && attribs.length) { + if (attribs.length > 1) { + attribs = attribs.slice(); + attribs.sort(); + } + var result = []; + for(var i=0;i<attribs.length;i++) { + var pair = attribs[i]; + if (opcode == '=' || (opcode == '+' && pair[1])) { + result.push('*'+Changeset.numToString(pool.putAttrib(pair))); + } + } + return result.join(''); + } +}; + +// like "substring" but on a single-line attribution string +Changeset.subattribution = function(astr, start, optEnd) { + var iter = Changeset.opIterator(astr, 0); + var assem = Changeset.smartOpAssembler(); + var attOp = Changeset.newOp(); + var csOp = Changeset.newOp(); + var opOut = Changeset.newOp(); + + function doCsOp() { + if (csOp.chars) { + while (csOp.opcode && (attOp.opcode || iter.hasNext())) { + if (! attOp.opcode) iter.next(attOp); + + if (csOp.opcode && attOp.opcode && csOp.chars >= attOp.chars && + attOp.lines > 0 && csOp.lines <= 0) { + csOp.lines++; + } + + Changeset._slicerZipperFunc(attOp, csOp, opOut, null); + if (opOut.opcode) { + assem.append(opOut); + opOut.opcode = ''; + } + } + } + } + + csOp.opcode = '-'; + csOp.chars = start; + + doCsOp(); + + if (optEnd === undefined) { + if (attOp.opcode) { + assem.append(attOp); + } + while (iter.hasNext()) { + iter.next(attOp); + assem.append(attOp); + } + } + else { + csOp.opcode = '='; + csOp.chars = optEnd - start; + doCsOp(); + } + + return assem.toString(); +}; + +Changeset.inverse = function(cs, lines, alines, pool) { + // lines and alines are what the changeset is meant to apply to. + // They may be arrays or objects with .get(i) and .length methods. + // They include final newlines on lines. + function lines_get(idx) { + if (lines.get) { + return lines.get(idx); + } + else { + return lines[idx]; + } + } + function lines_length() { + if ((typeof lines.length) == "number") { + return lines.length; + } + else { + return lines.length(); + } + } + function alines_get(idx) { + if (alines.get) { + return alines.get(idx); + } + else { + return alines[idx]; + } + } + function alines_length() { + if ((typeof alines.length) == "number") { + return alines.length; + } + else { + return alines.length(); + } + } + + var curLine = 0; + var curChar = 0; + var curLineOpIter = null; + var curLineOpIterLine; + var curLineNextOp = Changeset.newOp('+'); + + var unpacked = Changeset.unpack(cs); + var csIter = Changeset.opIterator(unpacked.ops); + var builder = Changeset.builder(unpacked.newLen); + + function consumeAttribRuns(numChars, func/*(len, attribs, endsLine)*/) { + + if ((! curLineOpIter) || (curLineOpIterLine != curLine)) { + // create curLineOpIter and advance it to curChar + curLineOpIter = Changeset.opIterator(alines_get(curLine)); + curLineOpIterLine = curLine; + var indexIntoLine = 0; + var done = false; + while (! done) { + curLineOpIter.next(curLineNextOp); + if (indexIntoLine + curLineNextOp.chars >= curChar) { + curLineNextOp.chars -= (curChar - indexIntoLine); + done = true; + } + else { + indexIntoLine += curLineNextOp.chars; + } + } + } + + while (numChars > 0) { + if ((! curLineNextOp.chars) && (! curLineOpIter.hasNext())) { + curLine++; + curChar = 0; + curLineOpIterLine = curLine; + curLineNextOp.chars = 0; + curLineOpIter = Changeset.opIterator(alines_get(curLine)); + } + if (! curLineNextOp.chars) { + curLineOpIter.next(curLineNextOp); + } + var charsToUse = Math.min(numChars, curLineNextOp.chars); + func(charsToUse, curLineNextOp.attribs, + charsToUse == curLineNextOp.chars && curLineNextOp.lines > 0); + numChars -= charsToUse; + curLineNextOp.chars -= charsToUse; + curChar += charsToUse; + } + + if ((! curLineNextOp.chars) && (! curLineOpIter.hasNext())) { + curLine++; + curChar = 0; + } + } + + function skip(N, L) { + if (L) { + curLine += L; + curChar = 0; + } + else { + if (curLineOpIter && curLineOpIterLine == curLine) { + consumeAttribRuns(N, function() {}); + } + else { + curChar += N; + } + } + } + + function nextText(numChars) { + var len = 0; + var assem = Changeset.stringAssembler(); + var firstString = lines_get(curLine).substring(curChar); + len += firstString.length; + assem.append(firstString); + + var lineNum = curLine+1; + while (len < numChars) { + var nextString = lines_get(lineNum); + len += nextString.length; + assem.append(nextString); + lineNum++; + } + + return assem.toString().substring(0, numChars); + } + + function cachedStrFunc(func) { + var cache = {}; + return function(s) { + if (! cache[s]) { + cache[s] = func(s); + } + return cache[s]; + }; + } + + var attribKeys = []; + var attribValues = []; + while (csIter.hasNext()) { + var csOp = csIter.next(); + if (csOp.opcode == '=') { + if (csOp.attribs) { + attribKeys.length = 0; + attribValues.length = 0; + Changeset.eachAttribNumber(csOp.attribs, function(n) { + attribKeys.push(pool.getAttribKey(n)); + attribValues.push(pool.getAttribValue(n)); + }); + var undoBackToAttribs = cachedStrFunc(function(attribs) { + var backAttribs = []; + for(var i=0;i<attribKeys.length;i++) { + var appliedKey = attribKeys[i]; + var appliedValue = attribValues[i]; + var oldValue = Changeset.attribsAttributeValue(attribs, appliedKey, pool); + if (appliedValue != oldValue) { + backAttribs.push([appliedKey, oldValue]); + } + } + return Changeset.makeAttribsString('=', backAttribs, pool); + }); + consumeAttribRuns(csOp.chars, function(len, attribs, endsLine) { + builder.keep(len, endsLine ? 1 : 0, undoBackToAttribs(attribs)); + }); + } + else { + skip(csOp.chars, csOp.lines); + builder.keep(csOp.chars, csOp.lines); + } + } + else if (csOp.opcode == '+') { + builder.remove(csOp.chars, csOp.lines); + } + else if (csOp.opcode == '-') { + var textBank = nextText(csOp.chars); + var textBankIndex = 0; + consumeAttribRuns(csOp.chars, function(len, attribs, endsLine) { + builder.insert(textBank.substr(textBankIndex, len), attribs); + textBankIndex += len; + }); + } + } + + return Changeset.checkRep(builder.toString()); +}; + +// %CLIENT FILE ENDS HERE% + +Changeset.follow = function(cs1, cs2, reverseInsertOrder, pool) { + var unpacked1 = Changeset.unpack(cs1); + var unpacked2 = Changeset.unpack(cs2); + var len1 = unpacked1.oldLen; + var len2 = unpacked2.oldLen; + Changeset.assert(len1 == len2, "mismatched follow"); + var chars1 = Changeset.stringIterator(unpacked1.charBank); + var chars2 = Changeset.stringIterator(unpacked2.charBank); + + var oldLen = unpacked1.newLen; + var oldPos = 0; + var newLen = 0; + + var hasInsertFirst = Changeset.attributeTester(['insertorder','first'], + pool); + + var newOps = Changeset.applyZip(unpacked1.ops, 0, unpacked2.ops, 0, function(op1, op2, opOut) { + if (op1.opcode == '+' || op2.opcode == '+') { + var whichToDo; + if (op2.opcode != '+') { + whichToDo = 1; + } + else if (op1.opcode != '+') { + whichToDo = 2; + } + else { + // both + + var firstChar1 = chars1.peek(1); + var firstChar2 = chars2.peek(1); + var insertFirst1 = hasInsertFirst(op1.attribs); + var insertFirst2 = hasInsertFirst(op2.attribs); + if (insertFirst1 && ! insertFirst2) { + whichToDo = 1; + } + else if (insertFirst2 && ! insertFirst1) { + whichToDo = 2; + } + // insert string that doesn't start with a newline first so as not to break up lines + else if (firstChar1 == '\n' && firstChar2 != '\n') { + whichToDo = 2; + } + else if (firstChar1 != '\n' && firstChar2 == '\n') { + whichToDo = 1; + } + // break symmetry: + else if (reverseInsertOrder) { + whichToDo = 2; + } + else { + whichToDo = 1; + } + } + if (whichToDo == 1) { + chars1.skip(op1.chars); + opOut.opcode = '='; + opOut.lines = op1.lines; + opOut.chars = op1.chars; + opOut.attribs = ''; + op1.opcode = ''; + } + else { + // whichToDo == 2 + chars2.skip(op2.chars); + Changeset.copyOp(op2, opOut); + op2.opcode = ''; + } + } + else if (op1.opcode == '-') { + if (! op2.opcode) { + op1.opcode = ''; + } + else { + if (op1.chars <= op2.chars) { + op2.chars -= op1.chars; + op2.lines -= op1.lines; + op1.opcode = ''; + if (! op2.chars) { + op2.opcode = ''; + } + } + else { + op1.chars -= op2.chars; + op1.lines -= op2.lines; + op2.opcode = ''; + } + } + } + else if (op2.opcode == '-') { + Changeset.copyOp(op2, opOut); + if (! op1.opcode) { + op2.opcode = ''; + } + else if (op2.chars <= op1.chars) { + // delete part or all of a keep + op1.chars -= op2.chars; + op1.lines -= op2.lines; + op2.opcode = ''; + if (! op1.chars) { + op1.opcode = ''; + } + } + else { + // delete all of a keep, and keep going + opOut.lines = op1.lines; + opOut.chars = op1.chars; + op2.lines -= op1.lines; + op2.chars -= op1.chars; + op1.opcode = ''; + } + } + else if (! op1.opcode) { + Changeset.copyOp(op2, opOut); + op2.opcode = ''; + } + else if (! op2.opcode) { + Changeset.copyOp(op1, opOut); + op1.opcode = ''; + } + else { + // both keeps + opOut.opcode = '='; + opOut.attribs = Changeset.followAttributes(op1.attribs, op2.attribs, pool); + if (op1.chars <= op2.chars) { + opOut.chars = op1.chars; + opOut.lines = op1.lines; + op2.chars -= op1.chars; + op2.lines -= op1.lines; + op1.opcode = ''; + if (! op2.chars) { + op2.opcode = ''; + } + } + else { + opOut.chars = op2.chars; + opOut.lines = op2.lines; + op1.chars -= op2.chars; + op1.lines -= op2.lines; + op2.opcode = ''; + } + } + switch (opOut.opcode) { + case '=': oldPos += opOut.chars; newLen += opOut.chars; break; + case '-': oldPos += opOut.chars; break; + case '+': newLen += opOut.chars; break; + } + }); + newLen += oldLen - oldPos; + + return Changeset.pack(oldLen, newLen, newOps, unpacked2.charBank); +}; + +Changeset.followAttributes = function(att1, att2, pool) { + // The merge of two sets of attribute changes to the same text + // takes the lexically-earlier value if there are two values + // for the same key. Otherwise, all key/value changes from + // both attribute sets are taken. This operation is the "follow", + // so a set of changes is produced that can be applied to att1 + // to produce the merged set. + if ((! att2) || (! pool)) return ''; + if (! att1) return att2; + var atts = []; + att2.replace(/\*([0-9a-z]+)/g, function(_, a) { + atts.push(pool.getAttrib(Changeset.parseNum(a))); + return ''; + }); + att1.replace(/\*([0-9a-z]+)/g, function(_, a) { + var pair1 = pool.getAttrib(Changeset.parseNum(a)); + for(var i=0;i<atts.length;i++) { + var pair2 = atts[i]; + if (pair1[0] == pair2[0]) { + if (pair1[1] <= pair2[1]) { + // winner of merge is pair1, delete this attribute + atts.splice(i, 1); + } + break; + } + } + return ''; + }); + // we've only removed attributes, so they're already sorted + var buf = Changeset.stringAssembler(); + for(var i=0;i<atts.length;i++) { + buf.append('*'); + buf.append(Changeset.numToString(pool.putAttrib(atts[i]))); + } + return buf.toString(); +}; diff --git a/trunk/etherpad/src/etherpad/collab/ace/easysync2_tests.js b/trunk/etherpad/src/etherpad/collab/ace/easysync2_tests.js new file mode 100644 index 0000000..7a23dc0 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/easysync2_tests.js @@ -0,0 +1,877 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/easysync2_tests.js +import("etherpad.collab.ace.easysync2.*") + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +function runTests() { + + function print(str) { + java.lang.System.out.println(str); + } + + function assert(code, optMsg) { + if (! eval(code)) throw new Error("FALSE: "+(optMsg || code)); + } + function literal(v) { + if ((typeof v) == "string") { + return '"'+v.replace(/[\\\"]/g, '\\$1').replace(/\n/g, '\\n')+'"'; + } + else return v.toSource(); + } + function assertEqualArrays(a, b) { + assert(literal(a)+".toSource() == "+literal(b)+".toSource()"); + } + function assertEqualStrings(a, b) { + assert(literal(a)+" == "+literal(b)); + } + + function throughIterator(opsStr) { + var iter = Changeset.opIterator(opsStr); + var assem = Changeset.opAssembler(); + while (iter.hasNext()) { + assem.append(iter.next()); + } + return assem.toString(); + } + + function throughSmartAssembler(opsStr) { + var iter = Changeset.opIterator(opsStr); + var assem = Changeset.smartOpAssembler(); + while (iter.hasNext()) { + assem.append(iter.next()); + } + assem.endDocument(); + return assem.toString(); + } + + (function() { + print("> throughIterator"); + var x = '-c*3*4+6|3=az*asdf0*1*2*3+1=1-1+1*0+1=1-1+1|c=c-1'; + assert("throughIterator("+literal(x)+") == "+literal(x)); + })(); + + (function() { + print("> throughSmartAssembler"); + var x = '-c*3*4+6|3=az*asdf0*1*2*3+1=1-1+1*0+1=1-1+1|c=c-1'; + assert("throughSmartAssembler("+literal(x)+") == "+literal(x)); + })(); + + function applyMutations(mu, arrayOfArrays) { + arrayOfArrays.forEach(function (a) { + var result = mu[a[0]].apply(mu, a.slice(1)); + if (a[0] == 'remove' && a[3]) { + assertEqualStrings(a[3], result); + } + }); + } + + function mutationsToChangeset(oldLen, arrayOfArrays) { + var assem = Changeset.smartOpAssembler(); + var op = Changeset.newOp(); + var bank = Changeset.stringAssembler(); + var oldPos = 0; + var newLen = 0; + arrayOfArrays.forEach(function (a) { + if (a[0] == 'skip') { + op.opcode = '='; + op.chars = a[1]; + op.lines = (a[2] || 0); + assem.append(op); + oldPos += op.chars; + newLen += op.chars; + } + else if (a[0] == 'remove') { + op.opcode = '-'; + op.chars = a[1]; + op.lines = (a[2] || 0); + assem.append(op); + oldPos += op.chars; + } + else if (a[0] == 'insert') { + op.opcode = '+'; + bank.append(a[1]); + op.chars = a[1].length; + op.lines = (a[2] || 0); + assem.append(op); + newLen += op.chars; + } + }); + newLen += oldLen - oldPos; + assem.endDocument(); + return Changeset.pack(oldLen, newLen, assem.toString(), + bank.toString()); + } + + function runMutationTest(testId, origLines, muts, correct) { + print("> runMutationTest#"+testId); + var lines = origLines.slice(); + var mu = Changeset.textLinesMutator(lines); + applyMutations(mu, muts); + mu.close(); + assertEqualArrays(correct, lines); + + var inText = origLines.join(''); + var cs = mutationsToChangeset(inText.length, muts); + lines = origLines.slice(); + Changeset.mutateTextLines(cs, lines); + assertEqualArrays(correct, lines); + + var correctText = correct.join(''); + //print(literal(cs)); + var outText = Changeset.applyToText(cs, inText); + assertEqualStrings(correctText, outText); + } + + runMutationTest(1, ["apple\n", "banana\n", "cabbage\n", "duffle\n", "eggplant\n"], + [['remove',1,0,"a"],['insert',"tu"],['remove',1,0,"p"],['skip',4,1],['skip',7,1], + ['insert',"cream\npie\n",2],['skip',2],['insert',"bot"],['insert',"\n",1], + ['insert',"bu"],['skip',3],['remove',3,1,"ge\n"],['remove',6,0,"duffle"]], + ["tuple\n","banana\n","cream\n","pie\n", "cabot\n","bubba\n","eggplant\n"]); + + runMutationTest(2, ["apple\n", "banana\n", "cabbage\n", "duffle\n", "eggplant\n"], + [['remove',1,0,"a"],['remove',1,0,"p"],['insert',"tu"],['skip',11,2], + ['insert',"cream\npie\n",2],['skip',2],['insert',"bot"],['insert',"\n",1], + ['insert',"bu"],['skip',3],['remove',3,1,"ge\n"],['remove',6,0,"duffle"]], + ["tuple\n","banana\n","cream\n","pie\n", "cabot\n","bubba\n","eggplant\n"]); + + runMutationTest(3, ["apple\n", "banana\n", "cabbage\n", "duffle\n", "eggplant\n"], + [['remove',6,1,"apple\n"],['skip',15,2],['skip',6],['remove',1,1,"\n"], + ['remove',8,0,"eggplant"],['skip',1,1]], + ["banana\n","cabbage\n","duffle\n"]); + + runMutationTest(4, ["15\n"], + [['skip',1],['insert',"\n2\n3\n4\n",4],['skip',2,1]], + ["1\n","2\n","3\n","4\n","5\n"]); + + runMutationTest(5, ["1\n","2\n","3\n","4\n","5\n"], + [['skip',1],['remove',7,4,"\n2\n3\n4\n"],['skip',2,1]], + ["15\n"]); + + runMutationTest(6, ["123\n","abc\n","def\n","ghi\n","xyz\n"], + [['insert',"0"],['skip',4,1],['skip',4,1],['remove',8,2,"def\nghi\n"],['skip',4,1]], + ["0123\n", "abc\n", "xyz\n"]); + + runMutationTest(7, ["apple\n", "banana\n", "cabbage\n", "duffle\n", "eggplant\n"], + [['remove',6,1,"apple\n"],['skip',15,2,true],['skip',6,0,true],['remove',1,1,"\n"], + ['remove',8,0,"eggplant"],['skip',1,1,true]], + ["banana\n","cabbage\n","duffle\n"]); + + function poolOrArray(attribs) { + if (attribs.getAttrib) { + return attribs; // it's already an attrib pool + } + else { + // assume it's an array of attrib strings to be split and added + var p = new AttribPool(); + attribs.forEach(function (kv) { p.putAttrib(kv.split(',')); }); + return p; + } + } + + function runApplyToAttributionTest(testId, attribs, cs, inAttr, outCorrect) { + print("> applyToAttribution#"+testId); + var p = poolOrArray(attribs); + var result = Changeset.applyToAttribution( + Changeset.checkRep(cs), inAttr, p); + assertEqualStrings(outCorrect, result); + } + + // turn c<b>a</b>ctus\n into a<b>c</b>tusabcd\n + runApplyToAttributionTest(1, ['bold,', 'bold,true'], + "Z:7>3-1*0=1*1=1=3+4$abcd", + "+1*1+1|1+5", "+1*1+1|1+8"); + + // turn "david\ngreenspan\n" into "<b>david\ngreen</b>\n" + runApplyToAttributionTest(2, ['bold,', 'bold,true'], + "Z:g<4*1|1=6*1=5-4$", + "|2+g", "*1|1+6*1+5|1+1"); + + (function() { + print("> mutatorHasMore"); + var lines = ["1\n", "2\n", "3\n", "4\n"]; + var mu; + + mu = Changeset.textLinesMutator(lines); + assert(mu.hasMore()+' == true'); + mu.skip(8,4); + assert(mu.hasMore()+' == false'); + mu.close(); + assert(mu.hasMore()+' == false'); + + // still 1,2,3,4 + mu = Changeset.textLinesMutator(lines); + assert(mu.hasMore()+' == true'); + mu.remove(2,1); + assert(mu.hasMore()+' == true'); + mu.skip(2,1); + assert(mu.hasMore()+' == true'); + mu.skip(2,1); + assert(mu.hasMore()+' == true'); + mu.skip(2,1); + assert(mu.hasMore()+' == false'); + mu.insert("5\n", 1); + assert(mu.hasMore()+' == false'); + mu.close(); + assert(mu.hasMore()+' == false'); + + // 2,3,4,5 now + mu = Changeset.textLinesMutator(lines); + assert(mu.hasMore()+' == true'); + mu.remove(6,3); + assert(mu.hasMore()+' == true'); + mu.remove(2,1); + assert(mu.hasMore()+' == false'); + mu.insert("hello\n", 1); + assert(mu.hasMore()+' == false'); + mu.close(); + assert(mu.hasMore()+' == false'); + + })(); + + function runMutateAttributionTest(testId, attribs, cs, alines, outCorrect) { + print("> runMutateAttributionTest#"+testId); + var p = poolOrArray(attribs); + var alines2 = Array.prototype.slice.call(alines); + var result = Changeset.mutateAttributionLines( + Changeset.checkRep(cs), alines2, p); + assertEqualArrays(outCorrect, alines2); + + print("> runMutateAttributionTest#"+testId+".applyToAttribution"); + function removeQuestionMarks(a) { return a.replace(/\?/g, ''); } + var inMerged = Changeset.joinAttributionLines(alines.map(removeQuestionMarks)); + var correctMerged = Changeset.joinAttributionLines(outCorrect.map(removeQuestionMarks)); + var mergedResult = Changeset.applyToAttribution(cs, inMerged, p); + assertEqualStrings(correctMerged, mergedResult); + } + + // turn 123\n 456\n 789\n into 123\n 4<b>5</b>6\n 789\n + runMutateAttributionTest(1, ["bold,true"], "Z:c>0|1=4=1*0=1$", ["|1+4", "|1+4", "|1+4"], + ["|1+4", "+1*0+1|1+2", "|1+4"]); + + // make a document bold + runMutateAttributionTest(2, ["bold,true"], "Z:c>0*0|3=c$", ["|1+4", "|1+4", "|1+4"], + ["*0|1+4", "*0|1+4", "*0|1+4"]); + + // clear bold on document + runMutateAttributionTest(3, ["bold,","bold,true"], "Z:c>0*0|3=c$", + ["*1+1+1*1+1|1+1", "+1*1+1|1+2", "*1+1+1*1+1|1+1"], + ["|1+4", "|1+4", "|1+4"]); + + // add a character on line 3 of a document with 5 blank lines, and make sure + // the optimization that skips purely-kept lines is working; if any attribution string + // with a '?' is parsed it will cause an error. + runMutateAttributionTest(4, ['foo,bar','line,1','line,2','line,3','line,4','line,5'], + "Z:5>1|2=2+1$x", + ["?*1|1+1", "?*2|1+1", "*3|1+1", "?*4|1+1", "?*5|1+1"], + ["?*1|1+1", "?*2|1+1", "+1*3|1+1", "?*4|1+1", "?*5|1+1"]); + + var testPoolWithChars = (function() { + var p = new AttribPool(); + p.putAttrib(['char','newline']); + for(var i=1;i<36;i++) { + p.putAttrib(['char',Changeset.numToString(i)]); + } + p.putAttrib(['char','']); + return p; + })(); + + // based on runMutationTest#1 + runMutateAttributionTest(5, testPoolWithChars, + "Z:11>7-2*t+1*u+1|2=b|2+a=2*b+1*o+1*t+1*0|1+1*b+1*u+1=3|1-3-6$"+ + "tucream\npie\nbot\nbu", + ["*a+1*p+2*l+1*e+1*0|1+1", + "*b+1*a+1*n+1*a+1*n+1*a+1*0|1+1", + "*c+1*a+1*b+2*a+1*g+1*e+1*0|1+1", + "*d+1*u+1*f+2*l+1*e+1*0|1+1", + "*e+1*g+2*p+1*l+1*a+1*n+1*t+1*0|1+1"], + ["*t+1*u+1*p+1*l+1*e+1*0|1+1", + "*b+1*a+1*n+1*a+1*n+1*a+1*0|1+1", + "|1+6", + "|1+4", + "*c+1*a+1*b+1*o+1*t+1*0|1+1", + "*b+1*u+1*b+2*a+1*0|1+1", + "*e+1*g+2*p+1*l+1*a+1*n+1*t+1*0|1+1"]); + + // based on runMutationTest#3 + runMutateAttributionTest(6, testPoolWithChars, + "Z:11<f|1-6|2=f=6|1-1-8$", + ["*a|1+6", "*b|1+7", "*c|1+8", "*d|1+7", "*e|1+9"], + ["*b|1+7", "*c|1+8", "*d+6*e|1+1"]); + + // based on runMutationTest#4 + runMutateAttributionTest(7, testPoolWithChars, + "Z:3>7=1|4+7$\n2\n3\n4\n", + ["*1+1*5|1+2"], + ["*1+1|1+1","|1+2","|1+2","|1+2","*5|1+2"]); + + // based on runMutationTest#5 + runMutateAttributionTest(8, testPoolWithChars, + "Z:a<7=1|4-7$", + ["*1|1+2","*2|1+2","*3|1+2","*4|1+2","*5|1+2"], + ["*1+1*5|1+2"]); + + // based on runMutationTest#6 + runMutateAttributionTest(9, testPoolWithChars, + "Z:k<7*0+1*10|2=8|2-8$0", + ["*1+1*2+1*3+1|1+1","*a+1*b+1*c+1|1+1", + "*d+1*e+1*f+1|1+1","*g+1*h+1*i+1|1+1","?*x+1*y+1*z+1|1+1"], + ["*0+1|1+4", "|1+4", "?*x+1*y+1*z+1|1+1"]); + + runMutateAttributionTest(10, testPoolWithChars, + "Z:6>4=1+1=1+1|1=1+1=1*0+1$abcd", + ["|1+3", "|1+3"], + ["|1+5", "+2*0+1|1+2"]); + + + runMutateAttributionTest(11, testPoolWithChars, + "Z:s>1|1=4=6|1+1$\n", + ["*0|1+4", "*0|1+8", "*0+5|1+1", "*0|1+1", "*0|1+5", "*0|1+1", "*0|1+1", "*0|1+1", "|1+1"], + ["*0|1+4", "*0+6|1+1", "*0|1+2", "*0+5|1+1", "*0|1+1", "*0|1+5", "*0|1+1", "*0|1+1", "*0|1+1", "|1+1"]); + + function randomInlineString(len, rand) { + var assem = Changeset.stringAssembler(); + for(var i=0;i<len;i++) { + assem.append(String.fromCharCode(rand.nextInt(26) + 97)); + } + return assem.toString(); + } + + function randomMultiline(approxMaxLines, approxMaxCols, rand) { + var numParts = rand.nextInt(approxMaxLines*2)+1; + var txt = Changeset.stringAssembler(); + txt.append(rand.nextInt(2) ? '\n' : ''); + for(var i=0;i<numParts;i++) { + if ((i % 2) == 0) { + if (rand.nextInt(10)) { + txt.append(randomInlineString(rand.nextInt(approxMaxCols)+1, rand)); + } + else { + txt.append('\n'); + } + } + else { + txt.append('\n'); + } + } + return txt.toString(); + } + + function randomStringOperation(numCharsLeft, rand) { + var result; + switch(rand.nextInt(9)) { + case 0: { + // insert char + result = {insert: randomInlineString(1, rand)}; + break; + } + case 1: { + // delete char + result = {remove: 1}; + break; + } + case 2: { + // skip char + result = {skip: 1}; + break; + } + case 3: { + // insert small + result = {insert: randomInlineString(rand.nextInt(4)+1, rand)}; + break; + } + case 4: { + // delete small + result = {remove: rand.nextInt(4)+1}; + break; + } + case 5: { + // skip small + result = {skip: rand.nextInt(4)+1}; + break; + } + case 6: { + // insert multiline; + result = {insert: randomMultiline(5, 20, rand)}; + break; + } + case 7: { + // delete multiline + result = {remove: Math.round(numCharsLeft * rand.nextDouble() * rand.nextDouble()) }; + break; + } + case 8: { + // skip multiline + result = {skip: Math.round(numCharsLeft * rand.nextDouble() * rand.nextDouble()) }; + break; + } + case 9: { + // delete to end + result = {remove: numCharsLeft}; + break; + } + case 10: { + // skip to end + result = {skip: numCharsLeft}; + break; + } + } + var maxOrig = numCharsLeft - 1; + if ('remove' in result) { + result.remove = Math.min(result.remove, maxOrig); + } + else if ('skip' in result) { + result.skip = Math.min(result.skip, maxOrig); + } + return result; + } + + function randomTwoPropAttribs(opcode, rand) { + // assumes attrib pool like ['apple,','apple,true','banana,','banana,true'] + if (opcode == '-' || rand.nextInt(3)) { + return ''; + } + else if (rand.nextInt(3)) { + if (opcode == '+' || rand.nextInt(2)) { + return '*'+Changeset.numToString(rand.nextInt(2)*2+1); + } + else { + return '*'+Changeset.numToString(rand.nextInt(2)*2); + } + } + else { + if (opcode == '+' || rand.nextInt(4) == 0) { + return '*1*3'; + } + else { + return ['*0*2', '*0*3', '*1*2'][rand.nextInt(3)]; + } + } + } + + function randomTestChangeset(origText, rand, withAttribs) { + var charBank = Changeset.stringAssembler(); + var textLeft = origText; // always keep final newline + var outTextAssem = Changeset.stringAssembler(); + var opAssem = Changeset.smartOpAssembler(); + var oldLen = origText.length; + + var nextOp = Changeset.newOp(); + function appendMultilineOp(opcode, txt) { + nextOp.opcode = opcode; + if (withAttribs) { + nextOp.attribs = randomTwoPropAttribs(opcode, rand); + } + txt.replace(/\n|[^\n]+/g, function (t) { + if (t == '\n') { + nextOp.chars = 1; + nextOp.lines = 1; + opAssem.append(nextOp); + } + else { + nextOp.chars = t.length; + nextOp.lines = 0; + opAssem.append(nextOp); + } + return ''; + }); + } + + function doOp() { + var o = randomStringOperation(textLeft.length, rand); + if (o.insert) { + var txt = o.insert; + charBank.append(txt); + outTextAssem.append(txt); + appendMultilineOp('+', txt); + } + else if (o.skip) { + var txt = textLeft.substring(0, o.skip); + textLeft = textLeft.substring(o.skip); + outTextAssem.append(txt); + appendMultilineOp('=', txt); + } + else if (o.remove) { + var txt = textLeft.substring(0, o.remove); + textLeft = textLeft.substring(o.remove); + appendMultilineOp('-', txt); + } + } + + while (textLeft.length > 1) doOp(); + for(var i=0;i<5;i++) doOp(); // do some more (only insertions will happen) + + var outText = outTextAssem.toString()+'\n'; + opAssem.endDocument(); + var cs = Changeset.pack(oldLen, outText.length, opAssem.toString(), charBank.toString()); + Changeset.checkRep(cs); + return [cs, outText]; + } + + function testCompose(randomSeed) { + var rand = new java.util.Random(randomSeed); + print("> testCompose#"+randomSeed); + + var p = new AttribPool(); + + var startText = randomMultiline(10, 20, rand)+'\n'; + + var x1 = randomTestChangeset(startText, rand); + var change1 = x1[0]; + var text1 = x1[1]; + + var x2 = randomTestChangeset(text1, rand); + var change2 = x2[0]; + var text2 = x2[1]; + + var x3 = randomTestChangeset(text2, rand); + var change3 = x3[0]; + var text3 = x3[1]; + + //print(literal(Changeset.toBaseTen(startText))); + //print(literal(Changeset.toBaseTen(change1))); + //print(literal(Changeset.toBaseTen(change2))); + var change12 = Changeset.checkRep(Changeset.compose(change1, change2, p)); + var change23 = Changeset.checkRep(Changeset.compose(change2, change3, p)); + var change123 = Changeset.checkRep(Changeset.compose(change12, change3, p)); + var change123a = Changeset.checkRep(Changeset.compose(change1, change23, p)); + assertEqualStrings(change123, change123a); + + assertEqualStrings(text2, Changeset.applyToText(change12, startText)); + assertEqualStrings(text3, Changeset.applyToText(change23, text1)); + assertEqualStrings(text3, Changeset.applyToText(change123, startText)); + } + + for(var i=0;i<30;i++) testCompose(i); + + (function simpleComposeAttributesTest() { + print("> simpleComposeAttributesTest"); + var p = new AttribPool(); + p.putAttrib(['bold','']); + p.putAttrib(['bold','true']); + var cs1 = Changeset.checkRep("Z:2>1*1+1*1=1$x"); + var cs2 = Changeset.checkRep("Z:3>0*0|1=3$"); + var cs12 = Changeset.checkRep(Changeset.compose(cs1, cs2, p)); + assertEqualStrings("Z:2>1+1*0|1=2$x", cs12); + })(); + + (function followAttributesTest() { + var p = new AttribPool(); + p.putAttrib(['x','']); + p.putAttrib(['x','abc']); + p.putAttrib(['x','def']); + p.putAttrib(['y','']); + p.putAttrib(['y','abc']); + p.putAttrib(['y','def']); + + function testFollow(a, b, afb, bfa, merge) { + assertEqualStrings(afb, Changeset.followAttributes(a, b, p)); + assertEqualStrings(bfa, Changeset.followAttributes(b, a, p)); + assertEqualStrings(merge, Changeset.composeAttributes(a, afb, true, p)); + assertEqualStrings(merge, Changeset.composeAttributes(b, bfa, true, p)); + } + + testFollow('', '', '', '', ''); + testFollow('*0', '', '', '*0', '*0'); + testFollow('*0', '*0', '', '', '*0'); + testFollow('*0', '*1', '', '*0', '*0'); + testFollow('*1', '*2', '', '*1', '*1'); + testFollow('*0*1', '', '', '*0*1', '*0*1'); + testFollow('*0*4', '*2*3', '*3', '*0', '*0*3'); + testFollow('*0*4', '*2', '', '*0*4', '*0*4'); + })(); + + function testFollow(randomSeed) { + var rand = new java.util.Random(randomSeed + 1000); + print("> testFollow#"+randomSeed); + + var p = new AttribPool(); + + var startText = randomMultiline(10, 20, rand)+'\n'; + + var cs1 = randomTestChangeset(startText, rand)[0]; + var cs2 = randomTestChangeset(startText, rand)[0]; + + var afb = Changeset.checkRep(Changeset.follow(cs1, cs2, false, p)); + var bfa = Changeset.checkRep(Changeset.follow(cs2, cs1, true, p)); + + var merge1 = Changeset.checkRep(Changeset.compose(cs1, afb)); + var merge2 = Changeset.checkRep(Changeset.compose(cs2, bfa)); + + assertEqualStrings(merge1, merge2); + } + + for(var i=0;i<30;i++) testFollow(i); + + function testSplitJoinAttributionLines(randomSeed) { + var rand = new java.util.Random(randomSeed + 2000); + print("> testSplitJoinAttributionLines#"+randomSeed); + + var doc = randomMultiline(10, 20, rand)+'\n'; + + function stringToOps(str) { + var assem = Changeset.mergingOpAssembler(); + var o = Changeset.newOp('+'); + o.chars = 1; + for(var i=0;i<str.length;i++) { + var c = str.charAt(i); + o.lines = (c == '\n' ? 1 : 0); + o.attribs = (c == 'a' || c == 'b' ? '*'+c : ''); + assem.append(o); + } + return assem.toString(); + } + + var theJoined = stringToOps(doc); + var theSplit = doc.match(/[^\n]*\n/g).map(stringToOps); + + assertEqualArrays(theSplit, Changeset.splitAttributionLines(theJoined, doc)); + assertEqualStrings(theJoined, Changeset.joinAttributionLines(theSplit)); + } + + for(var i=0;i<10;i++) testSplitJoinAttributionLines(i); + + (function testMoveOpsToNewPool() { + print("> testMoveOpsToNewPool"); + + var pool1 = new AttribPool(); + var pool2 = new AttribPool(); + + pool1.putAttrib(['baz','qux']); + pool1.putAttrib(['foo','bar']); + + pool2.putAttrib(['foo','bar']); + + assertEqualStrings(Changeset.moveOpsToNewPool('Z:1>2*1+1*0+1$ab', pool1, pool2), 'Z:1>2*0+1*1+1$ab'); + assertEqualStrings(Changeset.moveOpsToNewPool('*1+1*0+1', pool1, pool2), '*0+1*1+1'); + })(); + + + (function testMakeSplice() { + print("> testMakeSplice"); + + var t = "a\nb\nc\n"; + var t2 = Changeset.applyToText(Changeset.makeSplice(t, 5, 0, "def"), t); + assertEqualStrings("a\nb\ncdef\n", t2); + + })(); + + (function testToSplices() { + print("> testToSplices"); + + var cs = Changeset.checkRep('Z:z>9*0=1=4-3+9=1|1-4-4+1*0+a$123456789abcdefghijk'); + var correctSplices = [[5, 8, "123456789"], [9, 17, "abcdefghijk"]]; + assertEqualArrays(correctSplices, Changeset.toSplices(cs)); + })(); + + function testCharacterRangeFollow(testId, cs, oldRange, insertionsAfter, correctNewRange) { + print("> testCharacterRangeFollow#"+testId); + + var cs = Changeset.checkRep(cs); + assertEqualArrays(correctNewRange, Changeset.characterRangeFollow(cs, oldRange[0], oldRange[1], + insertionsAfter)); + + } + + testCharacterRangeFollow(1, 'Z:z>9*0=1=4-3+9=1|1-4-4+1*0+a$123456789abcdefghijk', + [7, 10], false, [14, 15]); + testCharacterRangeFollow(2, "Z:bc<6|x=b4|2-6$", [400, 407], false, [400, 401]); + testCharacterRangeFollow(3, "Z:4>0-3+3$abc", [0,3], false, [3,3]); + testCharacterRangeFollow(4, "Z:4>0-3+3$abc", [0,3], true, [0,0]); + testCharacterRangeFollow(5, "Z:5>1+1=1-3+3$abcd", [1,4], false, [5,5]); + testCharacterRangeFollow(6, "Z:5>1+1=1-3+3$abcd", [1,4], true, [2,2]); + testCharacterRangeFollow(7, "Z:5>1+1=1-3+3$abcd", [0,6], false, [1,7]); + testCharacterRangeFollow(8, "Z:5>1+1=1-3+3$abcd", [0,3], false, [1,2]); + testCharacterRangeFollow(9, "Z:5>1+1=1-3+3$abcd", [2,5], false, [5,6]); + testCharacterRangeFollow(10, "Z:2>1+1$a", [0,0], false, [1,1]); + testCharacterRangeFollow(11, "Z:2>1+1$a", [0,0], true, [0,0]); + + (function testOpAttributeValue() { + print("> testOpAttributeValue"); + + var p = new AttribPool(); + p.putAttrib(['name','david']); + p.putAttrib(['color','green']); + + assertEqualStrings("david", Changeset.opAttributeValue(Changeset.stringOp('*0*1+1'), 'name', p)); + assertEqualStrings("david", Changeset.opAttributeValue(Changeset.stringOp('*0+1'), 'name', p)); + assertEqualStrings("", Changeset.opAttributeValue(Changeset.stringOp('*1+1'), 'name', p)); + assertEqualStrings("", Changeset.opAttributeValue(Changeset.stringOp('+1'), 'name', p)); + assertEqualStrings("green", Changeset.opAttributeValue(Changeset.stringOp('*0*1+1'), 'color', p)); + assertEqualStrings("green", Changeset.opAttributeValue(Changeset.stringOp('*1+1'), 'color', p)); + assertEqualStrings("", Changeset.opAttributeValue(Changeset.stringOp('*0+1'), 'color', p)); + assertEqualStrings("", Changeset.opAttributeValue(Changeset.stringOp('+1'), 'color', p)); + })(); + + function testAppendATextToAssembler(testId, atext, correctOps) { + print("> testAppendATextToAssembler#"+testId); + + var assem = Changeset.smartOpAssembler(); + Changeset.appendATextToAssembler(atext, assem); + assertEqualStrings(correctOps, assem.toString()); + } + + testAppendATextToAssembler(1, {text:"\n", attribs:"|1+1"}, ""); + testAppendATextToAssembler(2, {text:"\n\n", attribs:"|2+2"}, "|1+1"); + testAppendATextToAssembler(3, {text:"\n\n", attribs:"*x|2+2"}, "*x|1+1"); + testAppendATextToAssembler(4, {text:"\n\n", attribs:"*x|1+1|1+1"}, "*x|1+1"); + testAppendATextToAssembler(5, {text:"foo\n", attribs:"|1+4"}, "+3"); + testAppendATextToAssembler(6, {text:"\nfoo\n", attribs:"|2+5"}, "|1+1+3"); + testAppendATextToAssembler(7, {text:"\nfoo\n", attribs:"*x|2+5"}, "*x|1+1*x+3"); + testAppendATextToAssembler(8, {text:"\n\n\nfoo\n", attribs:"|2+2*x|2+5"}, "|2+2*x|1+1*x+3"); + + function testMakeAttribsString(testId, pool, opcode, attribs, correctString) { + print("> testMakeAttribsString#"+testId); + + var p = poolOrArray(pool); + var str = Changeset.makeAttribsString(opcode, attribs, p); + assertEqualStrings(correctString, str); + } + + testMakeAttribsString(1, ['bold,'], '+', [['bold','']], ''); + testMakeAttribsString(2, ['abc,def','bold,'], '=', [['bold','']], '*1'); + testMakeAttribsString(3, ['abc,def','bold,true'], '+', [['abc','def'],['bold','true']], '*0*1'); + testMakeAttribsString(4, ['abc,def','bold,true'], '+', [['bold','true'],['abc','def']], '*0*1'); + + function testSubattribution(testId, astr, start, end, correctOutput) { + print("> testSubattribution#"+testId); + + var str = Changeset.subattribution(astr, start, end); + assertEqualStrings(correctOutput, str); + } + + testSubattribution(1, "+1", 0, 0, ""); + testSubattribution(2, "+1", 0, 1, "+1"); + testSubattribution(3, "+1", 0, undefined, "+1"); + testSubattribution(4, "|1+1", 0, 0, ""); + testSubattribution(5, "|1+1", 0, 1, "|1+1"); + testSubattribution(6, "|1+1", 0, undefined, "|1+1"); + testSubattribution(7, "*0+1", 0, 0, ""); + testSubattribution(8, "*0+1", 0, 1, "*0+1"); + testSubattribution(9, "*0+1", 0, undefined, "*0+1"); + testSubattribution(10, "*0|1+1", 0, 0, ""); + testSubattribution(11, "*0|1+1", 0, 1, "*0|1+1"); + testSubattribution(12, "*0|1+1", 0, undefined, "*0|1+1"); + testSubattribution(13, "*0+2+1*1+3", 0, 1, "*0+1"); + testSubattribution(14, "*0+2+1*1+3", 0, 2, "*0+2"); + testSubattribution(15, "*0+2+1*1+3", 0, 3, "*0+2+1"); + testSubattribution(16, "*0+2+1*1+3", 0, 4, "*0+2+1*1+1"); + testSubattribution(17, "*0+2+1*1+3", 0, 5, "*0+2+1*1+2"); + testSubattribution(18, "*0+2+1*1+3", 0, 6, "*0+2+1*1+3"); + testSubattribution(19, "*0+2+1*1+3", 0, 7, "*0+2+1*1+3"); + testSubattribution(20, "*0+2+1*1+3", 0, undefined, "*0+2+1*1+3"); + testSubattribution(21, "*0+2+1*1+3", 1, undefined, "*0+1+1*1+3"); + testSubattribution(22, "*0+2+1*1+3", 2, undefined, "+1*1+3"); + testSubattribution(23, "*0+2+1*1+3", 3, undefined, "*1+3"); + testSubattribution(24, "*0+2+1*1+3", 4, undefined, "*1+2"); + testSubattribution(25, "*0+2+1*1+3", 5, undefined, "*1+1"); + testSubattribution(26, "*0+2+1*1+3", 6, undefined, ""); + testSubattribution(27, "*0+2+1*1|1+3", 0, 1, "*0+1"); + testSubattribution(28, "*0+2+1*1|1+3", 0, 2, "*0+2"); + testSubattribution(29, "*0+2+1*1|1+3", 0, 3, "*0+2+1"); + testSubattribution(30, "*0+2+1*1|1+3", 0, 4, "*0+2+1*1+1"); + testSubattribution(31, "*0+2+1*1|1+3", 0, 5, "*0+2+1*1+2"); + testSubattribution(32, "*0+2+1*1|1+3", 0, 6, "*0+2+1*1|1+3"); + testSubattribution(33, "*0+2+1*1|1+3", 0, 7, "*0+2+1*1|1+3"); + testSubattribution(34, "*0+2+1*1|1+3", 0, undefined, "*0+2+1*1|1+3"); + testSubattribution(35, "*0+2+1*1|1+3", 1, undefined, "*0+1+1*1|1+3"); + testSubattribution(36, "*0+2+1*1|1+3", 2, undefined, "+1*1|1+3"); + testSubattribution(37, "*0+2+1*1|1+3", 3, undefined, "*1|1+3"); + testSubattribution(38, "*0+2+1*1|1+3", 4, undefined, "*1|1+2"); + testSubattribution(39, "*0+2+1*1|1+3", 5, undefined, "*1|1+1"); + testSubattribution(40, "*0+2+1*1|1+3", 1, 5, "*0+1+1*1+2"); + testSubattribution(41, "*0+2+1*1|1+3", 2, 6, "+1*1|1+3"); + testSubattribution(42, "*0+2+1*1+3", 2, 6, "+1*1+3"); + + function testFilterAttribNumbers(testId, cs, filter, correctOutput) { + print("> testFilterAttribNumbers#"+testId); + + var str = Changeset.filterAttribNumbers(cs, filter); + assertEqualStrings(correctOutput, str); + } + + testFilterAttribNumbers(1, "*0*1+1+2+3*1+4*2+5*0*2*1*b*c+6", + function(n) { return (n%2) == 0; }, + "*0+1+2+3+4*2+5*0*2*c+6"); + testFilterAttribNumbers(2, "*0*1+1+2+3*1+4*2+5*0*2*1*b*c+6", + function(n) { return (n%2) == 1; }, + "*1+1+2+3*1+4+5*1*b+6"); + + function testInverse(testId, cs, lines, alines, pool, correctOutput) { + print("> testInverse#"+testId); + + pool = poolOrArray(pool); + var str = Changeset.inverse(Changeset.checkRep(cs), lines, alines, pool); + assertEqualStrings(correctOutput, str); + } + + // take "FFFFTTTTT" and apply "-FT--FFTT", the inverse of which is "--F--TT--" + testInverse(1, "Z:9>0=1*0=1*1=1=2*0=2*1|1=2$", null, ["+4*1+5"], ['bold,','bold,true'], + "Z:9>0=2*0=1=2*1=2$"); + + function testMutateTextLines(testId, cs, lines, correctLines) { + print("> testMutateTextLines#"+testId); + + var a = lines.slice(); + Changeset.mutateTextLines(cs, a); + assertEqualArrays(correctLines, a); + } + + testMutateTextLines(1, "Z:4<1|1-2-1|1+1+1$\nc", ["a\n", "b\n"], ["\n", "c\n"]); + testMutateTextLines(2, "Z:4>0|1-2-1|2+3$\nc\n", ["a\n", "b\n"], ["\n", "c\n", "\n"]); + + function testInverseRandom(randomSeed) { + var rand = new java.util.Random(randomSeed + 3000); + print("> testInverseRandom#"+randomSeed); + + var p = poolOrArray(['apple,','apple,true','banana,','banana,true']); + + var startText = randomMultiline(10, 20, rand)+'\n'; + var alines = Changeset.splitAttributionLines(Changeset.makeAttribution(startText), startText); + var lines = startText.slice(0,-1).split('\n').map(function(s) { return s+'\n'; }); + + var stylifier = randomTestChangeset(startText, rand, true)[0]; + + //print(alines.join('\n')); + Changeset.mutateAttributionLines(stylifier, alines, p); + //print(stylifier); + //print(alines.join('\n')); + Changeset.mutateTextLines(stylifier, lines); + + var changeset = randomTestChangeset(lines.join(''), rand, true)[0]; + var inverseChangeset = Changeset.inverse(changeset, lines, alines, p); + + var origLines = lines.slice(); + var origALines = alines.slice(); + + Changeset.mutateTextLines(changeset, lines); + Changeset.mutateAttributionLines(changeset, alines, p); + //print(origALines.join('\n')); + //print(changeset); + //print(inverseChangeset); + //print(origLines.map(function(s) { return '1: '+s.slice(0,-1); }).join('\n')); + //print(lines.map(function(s) { return '2: '+s.slice(0,-1); }).join('\n')); + //print(alines.join('\n')); + Changeset.mutateTextLines(inverseChangeset, lines); + Changeset.mutateAttributionLines(inverseChangeset, alines, p); + //print(lines.map(function(s) { return '3: '+s.slice(0,-1); }).join('\n')); + + assertEqualArrays(origLines, lines); + assertEqualArrays(origALines, alines); + } + + for(var i=0;i<30;i++) testInverseRandom(i); +}
\ No newline at end of file diff --git a/trunk/etherpad/src/etherpad/collab/ace/linestylefilter.js b/trunk/etherpad/src/etherpad/collab/ace/linestylefilter.js new file mode 100644 index 0000000..c7f79a5 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/ace/linestylefilter.js @@ -0,0 +1,253 @@ +// DO NOT EDIT THIS FILE, edit infrastructure/ace/www/linestylefilter.js +import("etherpad.collab.ace.easysync2.Changeset"); + +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +// requires: easysync2.Changeset + +var linestylefilter = {}; + +linestylefilter.ATTRIB_CLASSES = { + 'bold':'tag:b', + 'italic':'tag:i', + 'underline':'tag:u', + 'strikethrough':'tag:s', + 'h1':'tag:h1', + 'h2':'tag:h2', + 'h3':'tag:h3', + 'h4':'tag:h4', + 'h5':'tag:h5', + 'h6':'tag:h6' +}; + +linestylefilter.getAuthorClassName = function(author) { + return "author-"+author.replace(/[^a-y0-9]/g, function(c) { + if (c == ".") return "-"; + return 'z'+c.charCodeAt(0)+'z'; + }); +}; + +// lineLength is without newline; aline includes newline, +// but may be falsy if lineLength == 0 +linestylefilter.getLineStyleFilter = function(lineLength, aline, + textAndClassFunc, apool) { + + if (lineLength == 0) return textAndClassFunc; + + var nextAfterAuthorColors = textAndClassFunc; + + var authorColorFunc = (function() { + var lineEnd = lineLength; + var curIndex = 0; + var extraClasses; + var leftInAuthor; + + function attribsToClasses(attribs) { + var classes = ''; + Changeset.eachAttribNumber(attribs, function(n) { + var key = apool.getAttribKey(n); + if (key) { + var value = apool.getAttribValue(n); + if (value) { + if (key == 'author') { + classes += ' '+linestylefilter.getAuthorClassName(value); + } + else if (key == 'list') { + classes += ' list:'+value; + } + else if (linestylefilter.ATTRIB_CLASSES[key]) { + classes += ' '+linestylefilter.ATTRIB_CLASSES[key]; + } + } + } + }); + return classes.substring(1); + } + + var attributionIter = Changeset.opIterator(aline); + var nextOp, nextOpClasses; + function goNextOp() { + nextOp = attributionIter.next(); + nextOpClasses = (nextOp.opcode && attribsToClasses(nextOp.attribs)); + } + goNextOp(); + function nextClasses() { + if (curIndex < lineEnd) { + extraClasses = nextOpClasses; + leftInAuthor = nextOp.chars; + goNextOp(); + while (nextOp.opcode && nextOpClasses == extraClasses) { + leftInAuthor += nextOp.chars; + goNextOp(); + } + } + } + nextClasses(); + + return function(txt, cls) { + while (txt.length > 0) { + if (leftInAuthor <= 0) { + // prevent infinite loop if something funny's going on + return nextAfterAuthorColors(txt, cls); + } + var spanSize = txt.length; + if (spanSize > leftInAuthor) { + spanSize = leftInAuthor; + } + var curTxt = txt.substring(0, spanSize); + txt = txt.substring(spanSize); + nextAfterAuthorColors(curTxt, (cls&&cls+" ")+extraClasses); + curIndex += spanSize; + leftInAuthor -= spanSize; + if (leftInAuthor == 0) { + nextClasses(); + } + } + }; + })(); + return authorColorFunc; +}; + +linestylefilter.getAtSignSplitterFilter = function(lineText, + textAndClassFunc) { + var at = /@/g; + at.lastIndex = 0; + var splitPoints = null; + var execResult; + while ((execResult = at.exec(lineText))) { + if (! splitPoints) { + splitPoints = []; + } + splitPoints.push(execResult.index); + } + + if (! splitPoints) return textAndClassFunc; + + return linestylefilter.textAndClassFuncSplitter(textAndClassFunc, + splitPoints); +}; + +linestylefilter.REGEX_WORDCHAR = /[\u0030-\u0039\u0041-\u005A\u0061-\u007A\u00C0-\u00D6\u00D8-\u00F6\u00F8-\u00FF\u0100-\u1FFF\u3040-\u9FFF\uF900-\uFDFF\uFE70-\uFEFE\uFF10-\uFF19\uFF21-\uFF3A\uFF41-\uFF5A\uFF66-\uFFDC]/; +linestylefilter.REGEX_URLCHAR = new RegExp('('+/[-:@a-zA-Z0-9_.,~%+\/\\?=&#;()$]/.source+'|'+linestylefilter.REGEX_WORDCHAR.source+')'); +linestylefilter.REGEX_URL = new RegExp(/(?:(?:https?|s?ftp|ftps|file|smb|afp|nfs|(x-)?man|gopher|txmt):\/\/|mailto:)/.source+linestylefilter.REGEX_URLCHAR.source+'*(?![:.,;])'+linestylefilter.REGEX_URLCHAR.source, 'g'); + +linestylefilter.getURLFilter = function(lineText, textAndClassFunc) { + linestylefilter.REGEX_URL.lastIndex = 0; + var urls = null; + var splitPoints = null; + var execResult; + while ((execResult = linestylefilter.REGEX_URL.exec(lineText))) { + if (! urls) { + urls = []; + splitPoints = []; + } + var startIndex = execResult.index; + var url = execResult[0]; + urls.push([startIndex, url]); + splitPoints.push(startIndex, startIndex + url.length); + } + + if (! urls) return textAndClassFunc; + + function urlForIndex(idx) { + for(var k=0; k<urls.length; k++) { + var u = urls[k]; + if (idx >= u[0] && idx < u[0]+u[1].length) { + return u[1]; + } + } + return false; + } + + var handleUrlsAfterSplit = (function() { + var curIndex = 0; + return function(txt, cls) { + var txtlen = txt.length; + var newCls = cls; + var url = urlForIndex(curIndex); + if (url) { + newCls += " url:"+url; + } + textAndClassFunc(txt, newCls); + curIndex += txtlen; + }; + })(); + + return linestylefilter.textAndClassFuncSplitter(handleUrlsAfterSplit, + splitPoints); +}; + +linestylefilter.textAndClassFuncSplitter = function(func, splitPointsOpt) { + var nextPointIndex = 0; + var idx = 0; + + // don't split at 0 + while (splitPointsOpt && + nextPointIndex < splitPointsOpt.length && + splitPointsOpt[nextPointIndex] == 0) { + nextPointIndex++; + } + + function spanHandler(txt, cls) { + if ((! splitPointsOpt) || nextPointIndex >= splitPointsOpt.length) { + func(txt, cls); + idx += txt.length; + } + else { + var splitPoints = splitPointsOpt; + var pointLocInSpan = splitPoints[nextPointIndex] - idx; + var txtlen = txt.length; + if (pointLocInSpan >= txtlen) { + func(txt, cls); + idx += txt.length; + if (pointLocInSpan == txtlen) { + nextPointIndex++; + } + } + else { + if (pointLocInSpan > 0) { + func(txt.substring(0, pointLocInSpan), cls); + idx += pointLocInSpan; + } + nextPointIndex++; + // recurse + spanHandler(txt.substring(pointLocInSpan), cls); + } + } + } + return spanHandler; +}; + +// domLineObj is like that returned by domline.createDomLine +linestylefilter.populateDomLine = function(textLine, aline, apool, + domLineObj) { + // remove final newline from text if any + var text = textLine; + if (text.slice(-1) == '\n') { + text = text.substring(0, text.length-1); + } + + function textAndClassFunc(tokenText, tokenClass) { + domLineObj.appendSpan(tokenText, tokenClass); + } + + var func = textAndClassFunc; + func = linestylefilter.getURLFilter(text, func); + func = linestylefilter.getLineStyleFilter(text.length, aline, + func, apool); + func(text, ''); +}; diff --git a/trunk/etherpad/src/etherpad/collab/collab_server.js b/trunk/etherpad/src/etherpad/collab/collab_server.js new file mode 100644 index 0000000..78c9921 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/collab_server.js @@ -0,0 +1,778 @@ +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +import("comet"); +import("ejs"); +import("etherpad.collab.ace.easysync2.{AttribPool,Changeset}"); +import("etherpad.log"); +import("etherpad.pad.activepads"); +import("etherpad.pad.model"); +import("etherpad.pad.padutils"); +import("etherpad.pad.padusers"); +import("etherpad.pad.padevents"); +import("etherpad.pad.pad_security"); +import("etherpad.pro.pro_padmeta"); +import("fastJSON"); +import("fileutils.readFile"); +import("jsutils.{eachProperty,keys}"); +import("etherpad.collab.collabroom_server.*"); +import("etherpad.collab.readonly_server"); +jimport("java.util.concurrent.ConcurrentHashMap"); + +var PADPAGE_ROOMTYPE = "padpage"; + +function onStartup() { + +} + +function _padIdToRoom(padId) { + return "padpage/"+padId; +} + +function _roomToPadId(roomName) { + return roomName.substring(roomName.indexOf("/")+1); +} + +function removeFromMemory(pad) { + // notification so we can free stuff + if (getNumConnections(pad) == 0) { + var tempObj = pad.tempObj(); + tempObj.revisionSockets = {}; + } +} + +function _getPadConnections(pad) { + return getRoomConnections(_padIdToRoom(pad.getId())); +} + +function guestKnock(globalPadId, guestId, displayName) { + var askedSomeone = false; + + // requires that we somehow have permission on this pad + model.accessPadGlobal(globalPadId, function(pad) { + var connections = _getPadConnections(pad); + connections.forEach(function(connection) { + // only send to pro users + if (! padusers.isGuest(connection.data.userInfo.userId)) { + askedSomeone = true; + var msg = { type: "SERVER_MESSAGE", + payload: { type: 'GUEST_PROMPT', + userId: guestId, + displayName: displayName } }; + sendMessage(connection.connectionId, msg); + } + }); + }); + + if (! askedSomeone) { + pad_security.answerKnock(guestId, globalPadId, "denied"); + } +} + +function _verifyUserId(userId) { + var result; + if (padusers.isGuest(userId)) { + // allow cookie-verified guest even if user has signed in + result = (userId == padusers.getGuestUserId()); + } + else { + result = (userId == padusers.getUserId()); + } + return result; +} + +function _checkChangesetAndPool(cs, pool) { + Changeset.checkRep(cs); + Changeset.eachAttribNumber(cs, function(n) { + if (! pool.getAttrib(n)) { + throw new Error("Attribute pool is missing attribute "+n+" for changeset "+cs); + } + }); +} + +function _doWarn(str) { + log.warn(appjet.executionId+": "+str); +} + +function _doInfo(str) { + log.info(appjet.executionId+": "+str); +} + +function _getPadRevisionSockets(pad) { + var revisionSockets = pad.tempObj().revisionSockets; + if (! revisionSockets) { + revisionSockets = {}; // rev# -> socket id + pad.tempObj().revisionSockets = revisionSockets; + } + return revisionSockets; +} + +function applyUserChanges(pad, baseRev, changeset, optSocketId, optAuthor) { + // changeset must be already adapted to the server's apool + + var apool = pad.pool(); + var r = baseRev; + while (r < pad.getHeadRevisionNumber()) { + r++; + var c = pad.getRevisionChangeset(r); + changeset = Changeset.follow(c, changeset, false, apool); + } + + var prevText = pad.text(); + if (Changeset.oldLen(changeset) != prevText.length) { + _doWarn("Can't apply USER_CHANGES "+changeset+" to document of length "+ + prevText.length); + return; + } + + var thisAuthor = ''; + if (optSocketId) { + var connectionId = getSocketConnectionId(optSocketId); + if (connectionId) { + var connection = getConnection(connectionId); + if (connection) { + thisAuthor = connection.data.userInfo.userId; + } + } + } + if (optAuthor) { + thisAuthor = optAuthor; + } + + pad.appendRevision(changeset, thisAuthor); + var newRev = pad.getHeadRevisionNumber(); + if (optSocketId) { + _getPadRevisionSockets(pad)[newRev] = optSocketId; + } + + var correctionChangeset = _correctMarkersInPad(pad.atext(), pad.pool()); + if (correctionChangeset) { + pad.appendRevision(correctionChangeset); + } + + ///// make document end in blank line if it doesn't: + if (pad.text().lastIndexOf("\n\n") != pad.text().length-2) { + var nlChangeset = Changeset.makeSplice( + pad.text(), pad.text().length-1, 0, "\n"); + pad.appendRevision(nlChangeset); + } + + updatePadClients(pad); + + activepads.touch(pad.getId()); + padevents.onEditPad(pad, thisAuthor); +} + +function updateClient(pad, connectionId) { + var conn = getConnection(connectionId); + if (! conn) { + return; + } + var lastRev = conn.data.lastRev; + var userId = conn.data.userInfo.userId; + var socketId = conn.socketId; + while (lastRev < pad.getHeadRevisionNumber()) { + var r = ++lastRev; + var author = pad.getRevisionAuthor(r); + var revisionSockets = _getPadRevisionSockets(pad); + if (revisionSockets[r] === socketId) { + sendMessage(connectionId, {type:"ACCEPT_COMMIT", newRev:r}); + } + else { + var forWire = Changeset.prepareForWire(pad.getRevisionChangeset(r), pad.pool()); + var msg = {type:"NEW_CHANGES", newRev:r, + changeset: forWire.translated, + apool: forWire.pool, + author: author}; + sendMessage(connectionId, msg); + } + } + conn.data.lastRev = pad.getHeadRevisionNumber(); + updateRoomConnectionData(connectionId, conn.data); +} + +function updatePadClients(pad) { + _getPadConnections(pad).forEach(function(connection) { + updateClient(pad, connection.connectionId); + }); + + readonly_server.updatePadClients(pad); +} + +function applyMissedChanges(pad, missedChanges) { + var userInfo = missedChanges.userInfo; + var baseRev = missedChanges.baseRev; + var committedChangeset = missedChanges.committedChangeset; // may be falsy + var furtherChangeset = missedChanges.furtherChangeset; // may be falsy + var apool = pad.pool(); + + if (! _verifyUserId(userInfo.userId)) { + return; + } + + if (committedChangeset) { + var wireApool1 = (new AttribPool()).fromJsonable(missedChanges.committedChangesetAPool); + _checkChangesetAndPool(committedChangeset, wireApool1); + committedChangeset = pad.adoptChangesetAttribs(committedChangeset, wireApool1); + } + if (furtherChangeset) { + var wireApool2 = (new AttribPool()).fromJsonable(missedChanges.furtherChangesetAPool); + _checkChangesetAndPool(furtherChangeset, wireApool2); + furtherChangeset = pad.adoptChangesetAttribs(furtherChangeset, wireApool2); + } + + var commitWasMissed = !! committedChangeset; + if (commitWasMissed) { + var commitSocketId = missedChanges.committedChangesetSocketId; + var revisionSockets = _getPadRevisionSockets(pad); + // was the commit really missed, or did the client just not hear back? + // look for later changeset by this socket + var r = baseRev; + while (r < pad.getHeadRevisionNumber()) { + r++; + var s = revisionSockets[r]; + if (! s) { + // changes are too old, have to drop them. + return; + } + if (s == commitSocketId) { + commitWasMissed = false; + break; + } + } + } + if (! commitWasMissed) { + // commit already incorporated by the server + committedChangeset = null; + } + + var changeset; + if (committedChangeset && furtherChangeset) { + changeset = Changeset.compose(committedChangeset, furtherChangeset, apool); + } + else { + changeset = (committedChangeset || furtherChangeset); + } + + if (changeset) { + var author = userInfo.userId; + + applyUserChanges(pad, baseRev, changeset, null, author); + } +} + +function getAllPadsWithConnections() { + // returns array of global pad id strings + return getAllRoomsOfType(PADPAGE_ROOMTYPE).map(_roomToPadId); +} + +function broadcastServerMessage(msgObj) { + var msg = {type: "SERVER_MESSAGE", payload: msgObj}; + getAllRoomsOfType(PADPAGE_ROOMTYPE).forEach(function(roomName) { + getRoomConnections(roomName).forEach(function(connection) { + sendMessage(connection.connectionId, msg); + }); + }); +} + +function appendPadText(pad, txt) { + txt = model.cleanText(txt); + var oldFullText = pad.text(); + _applyChangesetToPad(pad, Changeset.makeSplice(oldFullText, + oldFullText.length-1, 0, txt)); +} + +function setPadText(pad, txt) { + txt = model.cleanText(txt); + var oldFullText = pad.text(); + // replace text except for the existing final (virtual) newline + _applyChangesetToPad(pad, Changeset.makeSplice(oldFullText, 0, + oldFullText.length-1, txt)); +} + +function setPadAText(pad, atext) { + var oldFullText = pad.text(); + var deletion = Changeset.makeSplice(oldFullText, 0, oldFullText.length-1, ""); + + var assem = Changeset.smartOpAssembler(); + Changeset.appendATextToAssembler(atext, assem); + var charBank = atext.text.slice(0, -1); + var insertion = Changeset.checkRep(Changeset.pack(1, atext.text.length, + assem.toString(), charBank)); + + var cs = Changeset.compose(deletion, insertion, pad.pool()); + Changeset.checkRep(cs); + + _applyChangesetToPad(pad, cs); +} + +function applyChangesetToPad(pad, changeset) { + Changeset.checkRep(changeset); + + _applyChangesetToPad(pad, changeset); +} + +function _applyChangesetToPad(pad, changeset) { + pad.appendRevision(changeset); + updatePadClients(pad); +} + +function getHistoricalAuthorData(pad, author) { + var authorData = pad.getAuthorData(author); + if (authorData) { + var data = {}; + if ((typeof authorData.colorId) == "number") { + data.colorId = authorData.colorId; + } + if (authorData.name) { + data.name = authorData.name; + } + else { + var uname = padusers.getNameForUserId(author); + if (uname) { + data.name = uname; + } + } + return data; + } + return null; +} + +function buildHistoricalAuthorDataMapFromAText(pad, atext) { + var map = {}; + pad.eachATextAuthor(atext, function(author, authorNum) { + var data = getHistoricalAuthorData(pad, author); + if (data) { + map[author] = data; + } + }); + return map; +} + +function buildHistoricalAuthorDataMapForPadHistory(pad) { + var map = {}; + pad.pool().eachAttrib(function(key, value) { + if (key == 'author') { + var author = value; + var data = getHistoricalAuthorData(pad, author); + if (data) { + map[author] = data; + } + } + }); + return map; +} + +function getATextForWire(pad, optRev) { + var atext; + if ((optRev && ! isNaN(Number(optRev))) || (typeof optRev) == "number") { + atext = pad.getInternalRevisionAText(Number(optRev)); + } + else { + atext = pad.atext(); + } + + var historicalAuthorData = buildHistoricalAuthorDataMapFromAText(pad, atext); + + var attribsForWire = Changeset.prepareForWire(atext.attribs, pad.pool()); + var apool = attribsForWire.pool; + // mutate atext (translate attribs for wire): + atext.attribs = attribsForWire.translated; + + return {atext:atext, apool:apool.toJsonable(), + historicalAuthorData:historicalAuthorData }; +} + +function getCollabClientVars(pad) { + // construct object that is made available on the client + // as collab_client_vars + + var forWire = getATextForWire(pad); + + return { + initialAttributedText: forWire.atext, + rev: pad.getHeadRevisionNumber(), + padId: pad.getLocalId(), + globalPadId: pad.getId(), + historicalAuthorData: forWire.historicalAuthorData, + apool: forWire.apool, + clientIp: request.clientAddr, + clientAgent: request.headers["User-Agent"] + }; +} + +function getNumConnections(pad) { + return _getPadConnections(pad).length; +} + +function getConnectedUsers(pad) { + var users = []; + _getPadConnections(pad).forEach(function(connection) { + users.push(connection.data.userInfo); + }); + return users; +} + + +function bootAllUsersFromPad(pad, reason) { + return bootUsersFromPad(pad, reason); +} + +function bootUsersFromPad(pad, reason, userInfoFilter) { + var connections = _getPadConnections(pad); + var bootedUserInfos = []; + connections.forEach(function(connection) { + if ((! userInfoFilter) || userInfoFilter(connection.data.userInfo)) { + bootedUserInfos.push(connection.data.userInfo); + bootConnection(connection.connectionId); + } + }); + return bootedUserInfos; +} + +function dumpStorageToString(pad) { + var lines = []; + var errors = []; + var head = pad.getHeadRevisionNumber(); + try { + for(var i=0;i<=head;i++) { + lines.push("changeset "+i+" "+Changeset.toBaseTen(pad.getRevisionChangeset(i))); + } + } + catch (e) { + errors.push("!!!!! Error in changeset "+i+": "+e.message); + } + for(var i=0;i<=head;i++) { + lines.push("author "+i+" "+pad.getRevisionAuthor(i)); + } + for(var i=0;i<=head;i++) { + lines.push("time "+i+" "+pad.getRevisionDate(i)); + } + var revisionSockets = _getPadRevisionSockets(pad); + for(var k in revisionSockets) lines.push("socket "+k+" "+revisionSockets[k]); + return errors.concat(lines).join('\n'); +} + +function _getPadIdForSocket(socketId) { + var connectionId = getSocketConnectionId(socketId); + if (connectionId) { + var connection = getConnection(connectionId); + if (connection) { + return _roomToPadId(connection.roomName); + } + } + return null; +} + +function _getUserIdForSocket(socketId) { + var connectionId = getSocketConnectionId(socketId); + if (connectionId) { + var connection = getConnection(connectionId); + if (connection) { + return connection.data.userInfo.userId; + } + } + return null; +} + +function _serverDebug(msg) { /* nothing */ } + +function _accessSocketPad(socketId, accessType, padFunc, dontRequirePad) { + return _accessCollabPad(_getPadIdForSocket(socketId), accessType, + padFunc, dontRequirePad); +} + +function _accessConnectionPad(connection, accessType, padFunc, dontRequirePad) { + return _accessCollabPad(_roomToPadId(connection.roomName), accessType, + padFunc, dontRequirePad); +} + +function _accessCollabPad(padId, accessType, padFunc, dontRequirePad) { + if (! padId) { + if (! dontRequirePad) { + _doWarn("Collab operation \""+accessType+"\" aborted because socket "+socketId+" has no pad."); + } + return; + } + else { + return _accessExistingPad(padId, accessType, function(pad) { + return padFunc(pad); + }, dontRequirePad); + } +} + +function _accessExistingPad(padId, accessType, padFunc, dontRequireExist) { + return model.accessPadGlobal(padId, function(pad) { + if (! pad.exists()) { + if (! dontRequireExist) { + _doWarn("Collab operation \""+accessType+"\" aborted because pad "+padId+" doesn't exist."); + } + return; + } + else { + return padFunc(pad); + } + }); +} + +function _handlePadUserInfo(pad, userInfo) { + var author = userInfo.userId; + var colorId = Number(userInfo.colorId); + var name = userInfo.name; + + if (! author) return; + + // update map from author to that author's last known color and name + var data = {colorId: colorId}; + if (name) data.name = name; + pad.setAuthorData(author, data); + padusers.notifyUserData(data); +} + +function _sendUserInfoMessage(connectionId, type, userInfo) { + if (translateSpecialKey(userInfo.specialKey) != 'invisible') { + sendMessage(connectionId, {type: type, userInfo: userInfo }); + } +} + + +function getRoomCallbacks(roomName) { + var callbacks = {}; + callbacks.introduceUsers = + function (joiningConnection, existingConnection) { + // notify users of each other + _sendUserInfoMessage(existingConnection.connectionId, + "USER_NEWINFO", + joiningConnection.data.userInfo); + _sendUserInfoMessage(joiningConnection.connectionId, + "USER_NEWINFO", + existingConnection.data.userInfo); + }; + callbacks.extroduceUsers = + function (leavingConnection, existingConnection) { + _sendUserInfoMessage(existingConnection.connectionId, "USER_LEAVE", + leavingConnection.data.userInfo); + }; + callbacks.onAddConnection = + function (data) { + model.accessPadGlobal(_roomToPadId(roomName), function(pad) { + _handlePadUserInfo(pad, data.userInfo); + padevents.onUserJoin(pad, data.userInfo); + readonly_server.updateUserInfo(pad, data.userInfo); + }); + }; + callbacks.onRemoveConnection = + function (data) { + model.accessPadGlobal(_roomToPadId(roomName), function(pad) { + padevents.onUserLeave(pad, data.userInfo); + }); + }; + callbacks.handleConnect = + function (data) { + if (roomName.indexOf("padpage/") != 0) { + return null; + } + if (! (data.userInfo && data.userInfo.userId && + _verifyUserId(data.userInfo.userId))) { + return null; + } + return data.userInfo; + }; + callbacks.clientReady = + function(newConnection, data) { + var padId = _roomToPadId(newConnection.roomName); + + if (data.stats) { + log.custom("padclientstats", {padId:padId, stats:data.stats}); + } + + var lastRev = data.lastRev; + var isReconnectOf = data.isReconnectOf; + var isCommitPending = !! data.isCommitPending; + var connectionId = newConnection.connectionId; + + newConnection.data.lastRev = lastRev; + updateRoomConnectionData(connectionId, newConnection.data); + + if (padutils.isProPadId(padId)) { + pro_padmeta.accessProPad(padId, function(propad) { + // tell client about pad title + sendMessage(connectionId, {type: "CLIENT_MESSAGE", payload: { + type: "padtitle", title: propad.getDisplayTitle() } }); + sendMessage(connectionId, {type: "CLIENT_MESSAGE", payload: { + type: "padpassword", password: propad.getPassword() } }); + }); + } + + _accessExistingPad(padId, "CLIENT_READY", function(pad) { + sendMessage(connectionId, {type: "CLIENT_MESSAGE", payload: { + type: "padoptions", options: pad.getPadOptionsObj() } }); + + updateClient(pad, connectionId); + + }); + + if (isCommitPending) { + // tell client that if it hasn't received an ACCEPT_COMMIT by now, it isn't coming. + sendMessage(connectionId, {type:"NO_COMMIT_PENDING"}); + } + }; + callbacks.handleMessage = function(connection, msg) { + _handleCometMessage(connection, msg); + }; + return callbacks; +} + +var _specialKeys = [['x375b', 'invisible']]; + +function translateSpecialKey(specialKey) { + // code -> name + for(var i=0;i<_specialKeys.length;i++) { + if (_specialKeys[i][0] == specialKey) { + return _specialKeys[i][1]; + } + } + return null; +} + +function getSpecialKey(name) { + // name -> code + for(var i=0;i<_specialKeys.length;i++) { + if (_specialKeys[i][1] == name) { + return _specialKeys[i][0]; + } + } + return null; +} + +function _updateDocumentConnectionUserInfo(pad, socketId, userInfo) { + var connectionId = getSocketConnectionId(socketId); + if (connectionId) { + var updatingConnection = getConnection(connectionId); + updatingConnection.data.userInfo = userInfo; + updateRoomConnectionData(connectionId, updatingConnection.data); + _getPadConnections(pad).forEach(function(connection) { + if (connection.socketId != updatingConnection.socketId) { + _sendUserInfoMessage(connection.connectionId, + "USER_NEWINFO", userInfo); + } + }); + + _handlePadUserInfo(pad, userInfo); + padevents.onUserInfoChange(pad, userInfo); + readonly_server.updateUserInfo(pad, userInfo); + } +} + +function _handleCometMessage(connection, msg) { + + var socketUserId = connection.data.userInfo.userId; + if (! (socketUserId && _verifyUserId(socketUserId))) { + // user has signed out or cleared cookies, no longer auth'ed + bootConnection(connection.connectionId, "unauth"); + } + + if (msg.type == "USER_CHANGES") { + try { + _accessConnectionPad(connection, "USER_CHANGES", function(pad) { + var baseRev = msg.baseRev; + var wireApool = (new AttribPool()).fromJsonable(msg.apool); + var changeset = msg.changeset; + if (changeset) { + _checkChangesetAndPool(changeset, wireApool); + changeset = pad.adoptChangesetAttribs(changeset, wireApool); + applyUserChanges(pad, baseRev, changeset, connection.socketId); + } + }); + } + catch (e if e.easysync) { + _doWarn("Changeset error handling USER_CHANGES: "+e); + } + } + else if (msg.type == "USERINFO_UPDATE") { + _accessConnectionPad(connection, "USERINFO_UPDATE", function(pad) { + var userInfo = msg.userInfo; + // security check + if (userInfo.userId == connection.data.userInfo.userId) { + _updateDocumentConnectionUserInfo(pad, + connection.socketId, userInfo); + } + else { + // drop on the floor + } + }); + } + else if (msg.type == "CLIENT_MESSAGE") { + _accessConnectionPad(connection, "CLIENT_MESSAGE", function(pad) { + var payload = msg.payload; + if (payload.authId && + payload.authId != connection.data.userInfo.userId) { + // authId, if present, must actually be the sender's userId; + // here it wasn't + } + else { + getRoomConnections(connection.roomName).forEach( + function(conn) { + if (conn.socketId != connection.socketId) { + sendMessage(conn.connectionId, + {type: "CLIENT_MESSAGE", payload: payload}); + } + }); + padevents.onClientMessage(pad, connection.data.userInfo, + payload); + } + }); + } +} + +function _correctMarkersInPad(atext, apool) { + var text = atext.text; + + // collect char positions of line markers (e.g. bullets) in new atext + // that aren't at the start of a line + var badMarkers = []; + var iter = Changeset.opIterator(atext.attribs); + var offset = 0; + while (iter.hasNext()) { + var op = iter.next(); + var listValue = Changeset.opAttributeValue(op, 'list', apool); + if (listValue) { + for(var i=0;i<op.chars;i++) { + if (offset > 0 && text.charAt(offset-1) != '\n') { + badMarkers.push(offset); + } + offset++; + } + } + else { + offset += op.chars; + } + } + + if (badMarkers.length == 0) { + return null; + } + + // create changeset that removes these bad markers + offset = 0; + var builder = Changeset.builder(text.length); + badMarkers.forEach(function(pos) { + builder.keepText(text.substring(offset, pos)); + builder.remove(1); + offset = pos+1; + }); + return builder.toString(); +} diff --git a/trunk/etherpad/src/etherpad/collab/collabroom_server.js b/trunk/etherpad/src/etherpad/collab/collabroom_server.js new file mode 100644 index 0000000..ab1f844 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/collabroom_server.js @@ -0,0 +1,359 @@ +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +import("execution"); +import("comet"); +import("fastJSON"); +import("cache_utils.syncedWithCache"); +import("etherpad.collab.collab_server"); +import("etherpad.collab.readonly_server"); +import("etherpad.log"); +jimport("java.util.concurrent.ConcurrentSkipListMap"); +jimport("java.util.concurrent.CopyOnWriteArraySet"); + +function onStartup() { + execution.initTaskThreadPool("collabroom_async", 1); +} + +function _doWarn(str) { + log.warn(appjet.executionId+": "+str); +} + +// deep-copies (recursively clones) an object (or value) +function _deepCopy(obj) { + if ((typeof obj) != 'object' || !obj) { + return obj; + } + var o = {}; + for(var k in obj) { + if (obj.hasOwnProperty(k)) { + var v = obj[k]; + if ((typeof v) == 'object' && v) { + o[k] = _deepCopy(v); + } + else { + o[k] = v; + } + } + } + return o; +} + +// calls func inside a global lock on the cache +function _withCache(func) { + return syncedWithCache("collabroom_server", function(cache) { + if (! cache.rooms) { + // roomName -> { connections: CopyOnWriteArraySet<connectionId>, + // type: <immutable type string> } + cache.rooms = new ConcurrentSkipListMap(); + } + if (! cache.allConnections) { + // connectionId -> connection object + cache.allConnections = new ConcurrentSkipListMap(); + } + return func(cache); + }); +} + +// accesses cache without lock +function _getCache() { + return _withCache(function(cache) { return cache; }); +} + +// if roomType is null, will only update an existing connection +// (otherwise will insert or update as appropriate) +function _putConnection(connection, roomType) { + var roomName = connection.roomName; + var connectionId = connection.connectionId; + var socketId = connection.socketId; + var data = connection.data; + + _withCache(function(cache) { + var rooms = cache.rooms; + if (! rooms.containsKey(roomName)) { + // connection refers to room that doesn't exist / is empty + if (roomType) { + rooms.put(roomName, {connections: new CopyOnWriteArraySet(), + type: roomType}); + } + else { + return; + } + } + if (roomType) { + rooms.get(roomName).connections.add(connectionId); + cache.allConnections.put(connectionId, connection); + } + else { + cache.allConnections.replace(connectionId, connection); + } + }); +} + +function _removeConnection(connection) { + _withCache(function(cache) { + var rooms = cache.rooms; + var thisRoom = connection.roomName; + var thisConnectionId = connection.connectionId; + if (rooms.containsKey(thisRoom)) { + var roomConnections = rooms.get(thisRoom).connections; + roomConnections.remove(thisConnectionId); + if (roomConnections.isEmpty()) { + rooms.remove(thisRoom); + } + } + cache.allConnections.remove(thisConnectionId); + }); +} + +function _getConnection(connectionId) { + // return a copy of the connection object + return _deepCopy(_getCache().allConnections.get(connectionId) || null); +} + +function _getConnections(roomName) { + var array = []; + + var roomObj = _getCache().rooms.get(roomName); + if (roomObj) { + var roomConnections = roomObj.connections; + var iter = roomConnections.iterator(); + while (iter.hasNext()) { + var cid = iter.next(); + var conn = _getConnection(cid); + if (conn) { + array.push(conn); + } + } + } + return array; +} + +function sendMessage(connectionId, msg) { + var connection = _getConnection(connectionId); + if (connection) { + _sendMessageToSocket(connection.socketId, msg); + if (! comet.isConnected(connection.socketId)) { + // defunct socket, disconnect (later) + execution.scheduleTask("collabroom_async", + "collabRoomDisconnectSocket", + 0, [connection.connectionId, + connection.socketId]); + } + } +} + +function _sendMessageToSocket(socketId, msg) { + var msgString = fastJSON.stringify({type: "COLLABROOM", data: msg}); + comet.sendMessage(socketId, msgString); +} + +function disconnectDefunctSocket(connectionId, socketId) { + var connection = _getConnection(connectionId); + if (connection && connection.socketId == socketId) { + removeRoomConnection(connectionId); + } +} + +function _bootSocket(socketId, reason) { + if (reason) { + _sendMessageToSocket(socketId, + {type: "DISCONNECT_REASON", reason: reason}); + } + comet.disconnect(socketId); +} + +function bootConnection(connectionId, reason) { + var connection = _getConnection(connectionId); + if (connection) { + _bootSocket(connection.socketId, reason); + removeRoomConnection(connectionId); + } +} + +function getCallbacksForRoom(roomName, roomType) { + if (! roomType) { + var room = _getCache().rooms.get(roomName); + if (room) { + roomType = room.type; + } + } + + var emptyCallbacks = {}; + emptyCallbacks.introduceUsers = + function (joiningConnection, existingConnection) {}; + emptyCallbacks.extroduceUsers = + function extroduceUsers(leavingConnection, existingConnection) {}; + emptyCallbacks.onAddConnection = function (joiningData) {}; + emptyCallbacks.onRemoveConnection = function (leavingData) {}; + emptyCallbacks.handleConnect = + function(data) { return /*userInfo or */null; }; + emptyCallbacks.clientReady = function(newConnection, data) {}; + emptyCallbacks.handleMessage = function(connection, msg) {}; + + if (roomType == collab_server.PADPAGE_ROOMTYPE) { + return collab_server.getRoomCallbacks(roomName, emptyCallbacks); + } + else if (roomType == readonly_server.PADVIEW_ROOMTYPE) { + return readonly_server.getRoomCallbacks(roomName, emptyCallbacks); + } + else { + //java.lang.System.out.println("UNKNOWN ROOMTYPE: "+roomType); + return emptyCallbacks; + } +} + +// roomName must be globally unique, just within roomType; +// data must have a userInfo.userId +function addRoomConnection(roomName, roomType, + connectionId, socketId, data) { + var callbacks = getCallbacksForRoom(roomName, roomType); + + comet.setAttribute(socketId, "connectionId", connectionId); + + bootConnection(connectionId, "userdup"); + var joiningConnection = {roomName:roomName, + connectionId:connectionId, socketId:socketId, + data:data}; + _putConnection(joiningConnection, roomType); + var connections = _getConnections(roomName); + var joiningUser = data.userInfo.userId; + + connections.forEach(function(connection) { + if (connection.socketId != socketId) { + var user = connection.data.userInfo.userId; + if (user == joiningUser) { + bootConnection(connection.connectionId, "userdup"); + } + else { + callbacks.introduceUsers(joiningConnection, connection); + } + } + }); + + callbacks.onAddConnection(data); + + return joiningConnection; +} + +function removeRoomConnection(connectionId) { + var leavingConnection = _getConnection(connectionId); + if (leavingConnection) { + var roomName = leavingConnection.roomName; + var callbacks = getCallbacksForRoom(roomName); + + _removeConnection(leavingConnection); + + _getConnections(roomName).forEach(function (connection) { + callbacks.extroduceUsers(leavingConnection, connection); + }); + + callbacks.onRemoveConnection(leavingConnection.data); + } +} + +function getConnection(connectionId) { + return _getConnection(connectionId); +} + +function updateRoomConnectionData(connectionId, data) { + var connection = _getConnection(connectionId); + if (connection) { + connection.data = data; + _putConnection(connection); + } +} + +function getRoomConnections(roomName) { + return _getConnections(roomName); +} + +function getAllRoomsOfType(roomType) { + var rooms = _getCache().rooms; + var roomsIter = rooms.entrySet().iterator(); + var array = []; + while (roomsIter.hasNext()) { + var entry = roomsIter.next(); + var roomName = entry.getKey(); + var roomStruct = entry.getValue(); + if (roomStruct.type == roomType) { + array.push(roomName); + } + } + return array; +} + +function getSocketConnectionId(socketId) { + var result = comet.getAttribute(socketId, "connectionId"); + return result && String(result); +} + +function handleComet(cometOp, cometId, msg) { + var cometEvent = cometOp; + + function requireTruthy(x, id) { + if (!x) { + _doWarn("Collab operation rejected due to missing value, case "+id); + if (messageSocketId) { + comet.disconnect(messageSocketId); + } + response.stop(); + } + return x; + } + + if (cometEvent != "disconnect" && cometEvent != "message") { + response.stop(); + } + + var messageSocketId = requireTruthy(cometId, 2); + var messageConnectionId = getSocketConnectionId(messageSocketId); + + if (cometEvent == "disconnect") { + if (messageConnectionId) { + removeRoomConnection(messageConnectionId); + } + } + else if (cometEvent == "message") { + if (msg.type == "CLIENT_READY") { + var roomType = requireTruthy(msg.roomType, 4); + var roomName = requireTruthy(msg.roomName, 11); + + var socketId = messageSocketId; + var connectionId = messageSocketId; + var clientReadyData = requireTruthy(msg.data, 12); + + var callbacks = getCallbacksForRoom(roomName, roomType); + var userInfo = + requireTruthy(callbacks.handleConnect(clientReadyData), 13); + + var newConnection = addRoomConnection(roomName, roomType, + connectionId, socketId, + {userInfo: userInfo}); + + callbacks.clientReady(newConnection, clientReadyData); + } + else { + if (messageConnectionId) { + var connection = getConnection(messageConnectionId); + if (connection) { + var callbacks = getCallbacksForRoom(connection.roomName); + callbacks.handleMessage(connection, msg); + } + } + } + } +}
\ No newline at end of file diff --git a/trunk/etherpad/src/etherpad/collab/genimg.js b/trunk/etherpad/src/etherpad/collab/genimg.js new file mode 100644 index 0000000..04d1b3b --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/genimg.js @@ -0,0 +1,55 @@ +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +import("sync"); +import("image"); +import("blob"); + +//jimport("java.lang.System.out.println"); + +function _cache() { + sync.callsyncIfTrue(appjet.cache, + function() { return ! appjet.cache["etherpad-genimg"]; }, + function() { appjet.cache["etherpad-genimg"] = { paths: {}}; }); + return appjet.cache["etherpad-genimg"]; +} + +function renderPath(path) { + if (_cache().paths[path]) { + //println("CACHE HIT"); + } + else { + //println("CACHE MISS"); + var regexResult = null; + var img = null; + if ((regexResult = + /solid\/([0-9]+)x([0-9]+)\/([0-9a-fA-F]{6})\.gif/.exec(path))) { + var width = Number(regexResult[1]); + var height = Number(regexResult[2]); + var color = regexResult[3]; + img = image.solidColorImageBlob(width, height, color); + } + else { + // our "broken image" image, red and partly transparent + img = image.pixelsToImageBlob(2, 2, [0x00000000, 0xffff0000, + 0xffff0000, 0x00000000], true, "gif"); + } + _cache().paths[path] = img; + } + + blob.serveBlob(_cache().paths[path]); + return true; +} diff --git a/trunk/etherpad/src/etherpad/collab/json_sans_eval.js b/trunk/etherpad/src/etherpad/collab/json_sans_eval.js new file mode 100644 index 0000000..6cbd497 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/json_sans_eval.js @@ -0,0 +1,178 @@ +// Copyright (C) 2008 Google Inc. +// +// 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. + +/** + * Parses a string of well-formed JSON text. + * + * If the input is not well-formed, then behavior is undefined, but it is + * deterministic and is guaranteed not to modify any object other than its + * return value. + * + * This does not use `eval` so is less likely to have obscure security bugs than + * json2.js. + * It is optimized for speed, so is much faster than json_parse.js. + * + * This library should be used whenever security is a concern (when JSON may + * come from an untrusted source), speed is a concern, and erroring on malformed + * JSON is *not* a concern. + * + * Pros Cons + * +-----------------------+-----------------------+ + * json_sans_eval.js | Fast, secure | Not validating | + * +-----------------------+-----------------------+ + * json_parse.js | Validating, secure | Slow | + * +-----------------------+-----------------------+ + * json2.js | Fast, some validation | Potentially insecure | + * +-----------------------+-----------------------+ + * + * json2.js is very fast, but potentially insecure since it calls `eval` to + * parse JSON data, so an attacker might be able to supply strange JS that + * looks like JSON, but that executes arbitrary javascript. + * If you do have to use json2.js with untrusted data, make sure you keep + * your version of json2.js up to date so that you get patches as they're + * released. + * + * @param {string} json per RFC 4627 + * @return {Object|Array} + * @author Mike Samuel <mikesamuel@gmail.com> + */ +var jsonParse = (function () { + var number + = '(?:-?\\b(?:0|[1-9][0-9]*)(?:\\.[0-9]+)?(?:[eE][+-]?[0-9]+)?\\b)'; + var oneChar = '(?:[^\\0-\\x08\\x0a-\\x1f\"\\\\]' + + '|\\\\(?:[\"/\\\\bfnrt]|u[0-9A-Fa-f]{4}|x7c))'; + var string = '(?:\"' + oneChar + '*\")'; + + // Will match a value in a well-formed JSON file. + // If the input is not well-formed, may match strangely, but not in an unsafe + // way. + // Since this only matches value tokens, it does not match whitespace, colons, + // or commas. + var jsonToken = new RegExp( + '(?:false|true|null|[\\{\\}\\[\\]]' + + '|' + number + + '|' + string + + ')', 'g'); + + // Matches escape sequences in a string literal + var escapeSequence = new RegExp('\\\\(?:([^ux]|x7c)|u(.{4}))', 'g'); + + // Decodes escape sequences in object literals + var escapes = { + '"': '"', + '/': '/', + '\\': '\\', + 'b': '\b', + 'f': '\f', + 'n': '\n', + 'r': '\r', + 't': '\t', + 'x7c': '|' + }; + function unescapeOne(_, ch, hex) { + return ch ? escapes[ch] : String.fromCharCode(parseInt(hex, 16)); + } + + // A non-falsy value that coerces to the empty string when used as a key. + var EMPTY_STRING = new String(''); + var SLASH = '\\'; + + // Constructor to use based on an open token. + var firstTokenCtors = { '{': Object, '[': Array }; + + return function (json) { + // Split into tokens + var toks = json.match(jsonToken); + // Construct the object to return + var result; + var tok = toks[0]; + if ('{' === tok) { + result = {}; + } else if ('[' === tok) { + result = []; + } else { + throw new Error(tok); + } + + // If undefined, the key in an object key/value record to use for the next + // value parsed. + var key; + // Loop over remaining tokens maintaining a stack of uncompleted objects and + // arrays. + var stack = [result]; + for (var i = 1, n = toks.length; i < n; ++i) { + tok = toks[i]; + + var cont; + switch (tok.charCodeAt(0)) { + default: // sign or digit + cont = stack[0]; + cont[key || cont.length] = +(tok); + key = void 0; + break; + case 0x22: // '"' + tok = tok.substring(1, tok.length - 1); + if (tok.indexOf(SLASH) !== -1) { + tok = tok.replace(escapeSequence, unescapeOne); + } + cont = stack[0]; + if (!key) { + if (cont instanceof Array) { + key = cont.length; + } else { + key = tok || EMPTY_STRING; // Use as key for next value seen. + break; + } + } + cont[key] = tok; + key = void 0; + break; + case 0x5b: // '[' + cont = stack[0]; + stack.unshift(cont[key || cont.length] = []); + key = void 0; + break; + case 0x5d: // ']' + stack.shift(); + break; + case 0x66: // 'f' + cont = stack[0]; + cont[key || cont.length] = false; + key = void 0; + break; + case 0x6e: // 'n' + cont = stack[0]; + cont[key || cont.length] = null; + key = void 0; + break; + case 0x74: // 't' + cont = stack[0]; + cont[key || cont.length] = true; + key = void 0; + break; + case 0x7b: // '{' + cont = stack[0]; + stack.unshift(cont[key || cont.length] = {}); + key = void 0; + break; + case 0x7d: // '}' + stack.shift(); + break; + } + } + // Fail if we've got an uncompleted object. + if (stack.length) { throw new Error(); } + return result; + }; +})(); diff --git a/trunk/etherpad/src/etherpad/collab/readonly_server.js b/trunk/etherpad/src/etherpad/collab/readonly_server.js new file mode 100644 index 0000000..e367f04 --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/readonly_server.js @@ -0,0 +1,174 @@ +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +import("comet"); +import("ejs"); +import("etherpad.collab.ace.easysync2.{AttribPool,Changeset}"); +import("etherpad.log"); +import("etherpad.pad.activepads"); +import("etherpad.pad.model"); +import("etherpad.pad.padutils"); +import("etherpad.pad.padevents"); +import("etherpad.pro.pro_padmeta"); +import("fastJSON"); +import("fileutils.readFile"); +import("jsutils.eachProperty"); +import("etherpad.collab.server_utils.*"); +import("etherpad.collab.collabroom_server"); + +jimport("java.util.concurrent.ConcurrentHashMap"); + +jimport("java.lang.System.out.println"); + +var PADVIEW_ROOMTYPE = 'padview'; + +var _serverDebug = println;//function(x) {}; + +// "view id" is either a padId or an ro.id +function _viewIdToRoom(padId) { + return "padview/"+padId; +} + +function _roomToViewId(roomName) { + return roomName.substring(roomName.indexOf("/")+1); +} + +function getRoomCallbacks(roomName, emptyCallbacks) { + var callbacks = emptyCallbacks; + + var viewId = _roomToViewId(roomName); + + callbacks.handleConnect = function(data) { + if (data.userInfo && data.userInfo.userId) { + return data.userInfo; + } + return null; + }; + callbacks.clientReady = + function(newConnection, data) { + newConnection.data.lastRev = data.lastRev; + collabroom_server.updateRoomConnectionData(newConnection.connectionId, + newConnection.data); + }; + + return callbacks; +} + +function updatePadClients(pad) { + var padId = pad.getId(); + var roId = padIdToReadonly(padId); + + function update(connection) { + updateClient(pad, connection.connectionId); + } + + collabroom_server.getRoomConnections(_viewIdToRoom(padId)).forEach(update); + collabroom_server.getRoomConnections(_viewIdToRoom(roId)).forEach(update); +} + +// Get arrays of text lines and attribute lines for a revision +// of a pad. +function _getPadLines(pad, revNum) { + var atext; + if (revNum >= 0) { + atext = pad.getInternalRevisionAText(revNum); + } else { + atext = Changeset.makeAText("\n"); + } + + var result = {}; + result.textlines = Changeset.splitTextLines(atext.text); + result.alines = Changeset.splitAttributionLines(atext.attribs, + atext.text); + return result; +} + +function updateClient(pad, connectionId) { + var conn = collabroom_server.getConnection(connectionId); + if (! conn) { + return; + } + var lastRev = conn.data.lastRev; + while (lastRev < pad.getHeadRevisionNumber()) { + var r = ++lastRev; + var author = pad.getRevisionAuthor(r); + var lines = _getPadLines(pad, r-1); + var wirePool = new AttribPool(); + var forwards = pad.getRevisionChangeset(r); + var backwards = Changeset.inverse(forwards, lines.textlines, + lines.alines, pad.pool()); + var forwards2 = Changeset.moveOpsToNewPool(forwards, pad.pool(), + wirePool); + var backwards2 = Changeset.moveOpsToNewPool(backwards, pad.pool(), + wirePool); + + function revTime(r) { + var date = pad.getRevisionDate(r); + var s = Math.floor((+date)/1000); + //java.lang.System.out.println("time "+r+": "+s); + return s; + } + + var msg = {type:"NEW_CHANGES", newRev:r, + changeset: forwards2, + changesetBack: backwards2, + apool: wirePool.toJsonable(), + author: author, + timeDelta: revTime(r) - revTime(r-1) }; + collabroom_server.sendMessage(connectionId, msg); + } + conn.data.lastRev = pad.getHeadRevisionNumber(); + collabroom_server.updateRoomConnectionData(connectionId, conn.data); +} + +function sendMessageToPadConnections(pad, msg) { + var padId = pad.getId(); + var roId = padIdToReadonly(padId); + + function update(connection) { + collabroom_server.sendMessage(connection.connectionId, msg); + } + + collabroom_server.getRoomConnections(_viewIdToRoom(padId)).forEach(update); + collabroom_server.getRoomConnections(_viewIdToRoom(roId)).forEach(update); +} + +function updateUserInfo(pad, userInfo) { + var msg = { type:"NEW_AUTHORDATA", + author: userInfo.userId, + data: {} }; + var hasData = false; + if ((typeof (userInfo.colorId)) == "number") { + msg.data.colorId = userInfo.colorId; + hasData = true; + } + if (userInfo.name) { + msg.data.name = userInfo.name; + hasData = true; + } + if (hasData) { + sendMessageToPadConnections(pad, msg); + } +} + +function broadcastNewRevision(pad, revObj) { + var msg = { type:"NEW_SAVEDREV", + savedRev: revObj }; + + delete revObj.ip; // we try not to share info like IP addresses on slider + + sendMessageToPadConnections(pad, msg); +} diff --git a/trunk/etherpad/src/etherpad/collab/server_utils.js b/trunk/etherpad/src/etherpad/collab/server_utils.js new file mode 100644 index 0000000..ece3aea --- /dev/null +++ b/trunk/etherpad/src/etherpad/collab/server_utils.js @@ -0,0 +1,204 @@ +/** + * Copyright 2009 Google Inc. + * + * 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. + */ + +import("comet"); +import("ejs"); +import("etherpad.collab.ace.easysync2.{AttribPool,Changeset}"); +import("etherpad.log"); +import("etherpad.pad.activepads"); +import("etherpad.pad.model"); +import("etherpad.pad.padutils"); +import("etherpad.pad.padevents"); +import("etherpad.pro.pro_padmeta"); +import("fastJSON"); +import("fileutils.readFile"); +import("jsutils.eachProperty"); + +jimport("java.util.Random"); +jimport("java.lang.System"); + +import("etherpad.collab.collab_server"); +// importClass(java.util.Random); +// importClass(java.lang.System); + +var _serverDebug = function() {}; +var _dmesg = function() { System.out.println(arguments[0]+""); }; + +/// Begin readonly/padId conversion code +/// TODO: refactor into new file? +var _baseRandomNumber = 0x123123; // keep this number seekrit + +function _map(array, func) { + for(var i=0; i<array.length; i++) { + array[i] = func(array[i]); + } + return array; +} + +function parseUrlId(readOnlyIdOrLocalPadId) { + var localPadId; + var viewId; + var isReadOnly; + var roPadId; + var globalPadId; + if(isReadOnlyId(readOnlyIdOrLocalPadId)) { + isReadOnly = true; + globalPadId = readonlyToPadId(readOnlyIdOrLocalPadId); + localPadId = padutils.globalToLocalId(globalPadId); + var globalPadIdCheck = padutils.getGlobalPadId(localPadId); + if (globalPadId != globalPadIdCheck) { + // domain doesn't match + response.forbid(); + } + roPadId = readOnlyIdOrLocalPadId; + viewId = roPadId; + } + else { + isReadOnly = false; + localPadId = readOnlyIdOrLocalPadId; + globalPadId = padutils.getGlobalPadId(localPadId); + viewId = globalPadId; + roPadId = padIdToReadonly(globalPadId); + } + + return {localPadId:localPadId, viewId:viewId, isReadOnly:isReadOnly, + roPadId:roPadId, globalPadId:globalPadId}; +} + +function isReadOnlyId(str) { + return str.indexOf("ro.") == 0; +} + +/* + for now, we just make it 'hard to guess' + TODO: make it impossible to find read/write page through hash +*/ +function readonlyToPadId (readOnlyHash) { + + // readOnly hashes must start with 'ro-' + if(!isReadOnlyId(readOnlyHash)) return null; + else { + readOnlyHash = readOnlyHash.substring(3, readOnlyHash.length); + } + + // convert string to series of numbers between 1 and 64 + var result = _strToArray(readOnlyHash); + + var sum = result.pop(); + // using a secret seed to util.random, transform each number using + and % + var seed = _baseRandomNumber + sum; + var rand = new Random(seed); + + _map(result, function(elem) { + return ((64 + elem - rand.nextInt(64)) % 64); + }); + + // convert array of numbers back to a string + return _arrayToStr(result); +} + +/* + Temporary code. see comment at readonlyToPadId. +*/ +function padIdToReadonly (padid) { + var result = _strToArray(padid); + var sum = 0; + + if(padid.length > 1) { + for(var i=0; i<result.length; i++) { + sum = (sum + result[i] + 1) % 64; + } + } else { + sum = 64; + } + + var seed = _baseRandomNumber + sum; + var rand = new Random(seed); + + _map(result, function(elem) { + var randnum = rand.nextInt(64); + return ((elem + randnum) % 64); + }); + + result.push(sum); + return "ro." + _arrayToStr(result); +} + +// little reversable string encoding function +// 0-9 are the numbers 0-9 +// 10-35 are the uppercase letters A-Z +// 36-61 are the lowercase letters a-z +// 62 are all other characters +function _strToArray(str) { + var result = new Array(str.length); + for(var i=0; i<str.length; i++) { + result[i] = str.charCodeAt(i); + + if (_between(result[i], '0'.charCodeAt(0), '9'.charCodeAt(0))) { + result[i] -= '0'.charCodeAt(0); + } + else if(_between(result[i], 'A'.charCodeAt(0), 'Z'.charCodeAt(0))) { + result[i] -= 'A'.charCodeAt(0); // A becomes 0 + result[i] += 10; // A becomes 10 + } + else if(_between(result[i], 'a'.charCodeAt(0), 'z'.charCodeAt(0))) { + result[i] -= 'a'.charCodeAt(0); // a becomes 0 + result[i] += 36; // a becomes 36 + } else if(result[i] == '$'.charCodeAt(0)) { + result[i] = 62; + } else { + result[i] = 63; // if not alphanumeric or $, we default to 63 + } + } + return result; +} + +function _arrayToStr(array) { + var result = ""; + for(var i=0; i<array.length; i++) { + if(_between(array[i], 0, 9)) { + result += String.fromCharCode(array[i] + '0'.charCodeAt(0)); + } + else if(_between(array[i], 10, 35)) { + result += String.fromCharCode(array[i] - 10 + 'A'.charCodeAt(0)); + } + else if(_between(array[i], 36, 61)) { + result += String.fromCharCode(array[i] - 36 + 'a'.charCodeAt(0)); + } + else if(array[i] == 62) { + result += "$"; + } else { + result += "-"; + } + } + return result; +} + +function _between(charcode, start, end) { + return charcode >= start && charcode <= end; +} + +/* a short little testing function, converts back and forth */ +// function _testEncrypt(str) { +// var encrypted = padIdToReadonly(str); +// var decrypted = readonlyToPadId(encrypted); +// _dmesg(str + " " + encrypted + " " + decrypted); +// if(decrypted != str) { +// _dmesg("ERROR: " + str + " and " + decrypted + " do not match"); +// } +// } + +// _testEncrypt("testing$"); |