Modified: trunk/Source/WebCore/inspector/front-end/RevisionHistoryView.js (120084 => 120085)
--- trunk/Source/WebCore/inspector/front-end/RevisionHistoryView.js 2012-06-12 16:32:58 UTC (rev 120084)
+++ trunk/Source/WebCore/inspector/front-end/RevisionHistoryView.js 2012-06-12 16:44:28 UTC (rev 120085)
@@ -161,104 +161,79 @@
this._revision.requestContent(step2.bind(this, baseContent));
}
- function step2(baseContent, revisionContent)
+ function step2(baseContent, newContent)
{
- var oldLines = baseContent.split(/\r?\n/);
- var newLines = revisionContent.split(/\r?\n/);
- var diffData = this._diff(oldLines, newLines);
+ var baseLines = difflib.stringAsLines(baseContent);
+ var newLines = difflib.stringAsLines(newContent);
+ var sm = new difflib.SequenceMatcher(baseLines, newLines);
+ var opcodes = sm.get_opcodes();
+ var lastWasSeparator = false;
- for (var i = 0; i < diffData.added.length; ++i) {
- var lineNumber = diffData.added[i];
- this._createLine(lineNumber, newLines[lineNumber], "added");
- }
+ for (var idx = 0; idx < opcodes.length; idx++) {
+ var code = opcodes[idx];
+ var change = code[0];
+ var b = code[1];
+ var be = code[2];
+ var n = code[3];
+ var ne = code[4];
+ var rowCount = Math.max(be - b, ne - n);
+ var topRows = [];
+ var bottomRows = [];
+ for (var i = 0; i < rowCount; i++) {
+ if (change === "delete" || (change === "replace" && b < be)) {
+ var lineNumber = b++;
+ this._createLine(lineNumber, null, baseLines[lineNumber], "removed");
+ lastWasSeparator = false;
+ }
- for (var i = 0; i < diffData.removed.length; ++i) {
- var lineNumber = diffData.removed[i];
- this._createLine(lineNumber, oldLines[lineNumber], "removed");
+ if (change === "insert" || (change === "replace" && n < ne)) {
+ var lineNumber = n++;
+ this._createLine(null, lineNumber, newLines[lineNumber], "added");
+ lastWasSeparator = false;
+ }
+
+ if (change === "equal") {
+ b++;
+ n++;
+ if (!lastWasSeparator)
+ this._createLine(null, null, " \u2026", "separator");
+ lastWasSeparator = true;
+ }
+ }
}
}
},
/**
- * @param {number} lineNumber
+ * @param {?number} baseLineNumber
+ * @param {?number} newLineNumber
* @param {string} lineContent
* @param {string} changeType
*/
- _createLine: function(lineNumber, lineContent, changeType)
+ _createLine: function(baseLineNumber, newLineNumber, lineContent, changeType)
{
var child = new TreeElement("", null, false);
child.selectable = false;
this.appendChild(child);
var lineElement = document.createElement("span");
- var numberString = numberToStringWithSpacesPadding(lineNumber + 1, 4);
- var lineNumberSpan = document.createElement("span");
- lineNumberSpan.addStyleClass("webkit-line-number");
- lineNumberSpan.textContent = numberString;
- child.listItemElement.appendChild(lineNumberSpan);
+ function appendLineNumber(lineNumber)
+ {
+ var numberString = lineNumber !== null ? numberToStringWithSpacesPadding(lineNumber + 1, 4) : " ";
+ var lineNumberSpan = document.createElement("span");
+ lineNumberSpan.addStyleClass("webkit-line-number");
+ lineNumberSpan.textContent = numberString;
+ child.listItemElement.appendChild(lineNumberSpan);
+ }
+
+ appendLineNumber(baseLineNumber);
+ appendLineNumber(newLineNumber);
+
var contentSpan = document.createElement("span");
contentSpan.textContent = lineContent;
child.listItemElement.appendChild(contentSpan);
child.listItemElement.addStyleClass("revision-history-line");
child.listItemElement.addStyleClass("revision-history-line-" + changeType);
- },
-
- _diff: function(x, y)
- {
- var symbols = {};
- var r = 0, p = 0;
- var result = [];
-
- var p1 = popsym(0);
- for (var i = 0; i < x.length; i++) {
- p = r === p ? p1 : popsym(i);
- p1 = popsym(i + 1);
-
- var idx;
- if (p > p1) {
- i++;
- idx = p1;
- delete symbols[y[p]];
- } else
- idx = p;
-
- if (idx === y.length)
- p = popsym(i);
- else {
- r = idx;
- result.push([i, r]);
- }
- }
-
- var removed = [];
- var added = [];
- var ix = 0;
- var iy = 0;
- for (var i = 0; i < result.length; ++i) {
- for (var j = ix; j < result[i][0]; ++j)
- removed.push(j);
- ix = result[i][0] + 1;
- for (var j = iy; j < result[i][1]; ++j)
- added.push(j);
- iy = result[i][1] + 1;
- }
- for (var j = ix + 1; j < x.length; ++j)
- removed.push(j);
- for (var j = iy + 1; j < y.length; ++j)
- added.push(j);
-
- return { removed: removed, added: added };
-
- function popsym(index)
- {
- var s = x[index];
- var pos = symbols[s] + 1;
- pos = y.indexOf(s, pos > r ? pos : r);
- if (pos === -1)
- pos = y.length;
- symbols[s] = pos;
- return pos;
- }
}
}
Added: trunk/Source/WebCore/inspector/front-end/jsdifflib.js (0 => 120085)
--- trunk/Source/WebCore/inspector/front-end/jsdifflib.js (rev 0)
+++ trunk/Source/WebCore/inspector/front-end/jsdifflib.js 2012-06-12 16:44:28 UTC (rev 120085)
@@ -0,0 +1,409 @@
+/*
+ * This is part of jsdifflib v1.0. <http://snowtide.com/jsdifflib>
+ *
+ * Copyright (c) 2007, Snowtide Informatics Systems, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice, this
+ * list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of the Snowtide Informatics Systems nor the names of its
+ * contributors may be used to endorse or promote products derived from this
+ * software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
+ * SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ **/
+/* Author: Chas Emerick <cemer...@snowtide.com> */
+/* taken from https://github.com/cemerick/jsdifflib */
+
+__whitespace = {" ":true, "\t":true, "\n":true, "\f":true, "\r":true};
+
+difflib = {
+ defaultJunkFunction: function (c) {
+ return __whitespace.hasOwnProperty(c);
+ },
+
+ stripLinebreaks: function (str) { return str.replace(/^[\n\r]*|[\n\r]*$/g, ""); },
+
+ stringAsLines: function (str) {
+ var lfpos = str.indexOf("\n");
+ var crpos = str.indexOf("\r");
+ var linebreak = ((lfpos > -1 && crpos > -1) || crpos < 0) ? "\n" : "\r";
+
+ var lines = str.split(linebreak);
+ for (var i = 0; i < lines.length; i++) {
+ lines[i] = difflib.stripLinebreaks(lines[i]);
+ }
+
+ return lines;
+ },
+
+ // iteration-based reduce implementation
+ __reduce: function (func, list, initial) {
+ if (initial != null) {
+ var value = initial;
+ var idx = 0;
+ } else if (list) {
+ var value = list[0];
+ var idx = 1;
+ } else {
+ return null;
+ }
+
+ for (; idx < list.length; idx++) {
+ value = func(value, list[idx]);
+ }
+
+ return value;
+ },
+
+ // comparison function for sorting lists of numeric tuples
+ __ntuplecomp: function (a, b) {
+ var mlen = Math.max(a.length, b.length);
+ for (var i = 0; i < mlen; i++) {
+ if (a[i] < b[i]) return -1;
+ if (a[i] > b[i]) return 1;
+ }
+
+ return a.length == b.length ? 0 : (a.length < b.length ? -1 : 1);
+ },
+
+ __calculate_ratio: function (matches, length) {
+ return length ? 2.0 * matches / length : 1.0;
+ },
+
+ // returns a function that returns true if a key passed to the returned function
+ // is in the dict (js object) provided to this function; replaces being able to
+ // carry around dict.has_key in python...
+ __isindict: function (dict) {
+ return function (key) { return dict.hasOwnProperty(key); };
+ },
+
+ // replacement for python's dict.get function -- need easy default values
+ __dictget: function (dict, key, defaultValue) {
+ return dict.hasOwnProperty(key) ? dict[key] : defaultValue;
+ },
+
+ SequenceMatcher: function (a, b, isjunk) {
+ this.set_seqs = function (a, b) {
+ this.set_seq1(a);
+ this.set_seq2(b);
+ }
+
+ this.set_seq1 = function (a) {
+ if (a == this.a) return;
+ this.a = a;
+ this.matching_blocks = this.opcodes = null;
+ }
+
+ this.set_seq2 = function (b) {
+ if (b == this.b) return;
+ this.b = b;
+ this.matching_blocks = this.opcodes = this.fullbcount = null;
+ this.__chain_b();
+ }
+
+ this.__chain_b = function () {
+ var b = this.b;
+ var n = b.length;
+ var b2j = this.b2j = {};
+ var populardict = {};
+ for (var i = 0; i < b.length; i++) {
+ var elt = b[i];
+ if (b2j.hasOwnProperty(elt)) {
+ var indices = b2j[elt];
+ if (n >= 200 && indices.length * 100 > n) {
+ populardict[elt] = 1;
+ delete b2j[elt];
+ } else {
+ indices.push(i);
+ }
+ } else {
+ b2j[elt] = [i];
+ }
+ }
+
+ for (var elt in populardict) {
+ if (populardict.hasOwnProperty(elt)) {
+ delete b2j[elt];
+ }
+ }
+
+ var isjunk = this.isjunk;
+ var junkdict = {};
+ if (isjunk) {
+ for (var elt in populardict) {
+ if (populardict.hasOwnProperty(elt) && isjunk(elt)) {
+ junkdict[elt] = 1;
+ delete populardict[elt];
+ }
+ }
+ for (var elt in b2j) {
+ if (b2j.hasOwnProperty(elt) && isjunk(elt)) {
+ junkdict[elt] = 1;
+ delete b2j[elt];
+ }
+ }
+ }
+
+ this.isbjunk = difflib.__isindict(junkdict);
+ this.isbpopular = difflib.__isindict(populardict);
+ }
+
+ this.find_longest_match = function (alo, ahi, blo, bhi) {
+ var a = this.a;
+ var b = this.b;
+ var b2j = this.b2j;
+ var isbjunk = this.isbjunk;
+ var besti = alo;
+ var bestj = blo;
+ var bestsize = 0;
+ var j = null;
+
+ var j2len = {};
+ var nothing = [];
+ for (var i = alo; i < ahi; i++) {
+ var newj2len = {};
+ var jdict = difflib.__dictget(b2j, a[i], nothing);
+ for (var jkey in jdict) {
+ if (jdict.hasOwnProperty(jkey)) {
+ j = jdict[jkey];
+ if (j < blo) continue;
+ if (j >= bhi) break;
+ newj2len[j] = k = difflib.__dictget(j2len, j - 1, 0) + 1;
+ if (k > bestsize) {
+ besti = i - k + 1;
+ bestj = j - k + 1;
+ bestsize = k;
+ }
+ }
+ }
+ j2len = newj2len;
+ }
+
+ while (besti > alo && bestj > blo && !isbjunk(b[bestj - 1]) && a[besti - 1] == b[bestj - 1]) {
+ besti--;
+ bestj--;
+ bestsize++;
+ }
+
+ while (besti + bestsize < ahi && bestj + bestsize < bhi &&
+ !isbjunk(b[bestj + bestsize]) &&
+ a[besti + bestsize] == b[bestj + bestsize]) {
+ bestsize++;
+ }
+
+ while (besti > alo && bestj > blo && isbjunk(b[bestj - 1]) && a[besti - 1] == b[bestj - 1]) {
+ besti--;
+ bestj--;
+ bestsize++;
+ }
+
+ while (besti + bestsize < ahi && bestj + bestsize < bhi && isbjunk(b[bestj + bestsize]) &&
+ a[besti + bestsize] == b[bestj + bestsize]) {
+ bestsize++;
+ }
+
+ return [besti, bestj, bestsize];
+ }
+
+ this.get_matching_blocks = function () {
+ if (this.matching_blocks != null) return this.matching_blocks;
+ var la = this.a.length;
+ var lb = this.b.length;
+
+ var queue = [[0, la, 0, lb]];
+ var matching_blocks = [];
+ var alo, ahi, blo, bhi, qi, i, j, k, x;
+ while (queue.length) {
+ qi = queue.pop();
+ alo = qi[0];
+ ahi = qi[1];
+ blo = qi[2];
+ bhi = qi[3];
+ x = this.find_longest_match(alo, ahi, blo, bhi);
+ i = x[0];
+ j = x[1];
+ k = x[2];
+
+ if (k) {
+ matching_blocks.push(x);
+ if (alo < i && blo < j)
+ queue.push([alo, i, blo, j]);
+ if (i+k < ahi && j+k < bhi)
+ queue.push([i + k, ahi, j + k, bhi]);
+ }
+ }
+
+ matching_blocks.sort(difflib.__ntuplecomp);
+
+ var i1 = j1 = k1 = block = 0;
+ var non_adjacent = [];
+ for (var idx in matching_blocks) {
+ if (matching_blocks.hasOwnProperty(idx)) {
+ block = matching_blocks[idx];
+ i2 = block[0];
+ j2 = block[1];
+ k2 = block[2];
+ if (i1 + k1 == i2 && j1 + k1 == j2) {
+ k1 += k2;
+ } else {
+ if (k1) non_adjacent.push([i1, j1, k1]);
+ i1 = i2;
+ j1 = j2;
+ k1 = k2;
+ }
+ }
+ }
+
+ if (k1) non_adjacent.push([i1, j1, k1]);
+
+ non_adjacent.push([la, lb, 0]);
+ this.matching_blocks = non_adjacent;
+ return this.matching_blocks;
+ }
+
+ this.get_opcodes = function () {
+ if (this.opcodes != null) return this.opcodes;
+ var i = 0;
+ var j = 0;
+ var answer = [];
+ this.opcodes = answer;
+ var block, ai, bj, size, tag;
+ var blocks = this.get_matching_blocks();
+ for (var idx in blocks) {
+ if (blocks.hasOwnProperty(idx)) {
+ block = blocks[idx];
+ ai = block[0];
+ bj = block[1];
+ size = block[2];
+ tag = '';
+ if (i < ai && j < bj) {
+ tag = 'replace';
+ } else if (i < ai) {
+ tag = 'delete';
+ } else if (j < bj) {
+ tag = 'insert';
+ }
+ if (tag) answer.push([tag, i, ai, j, bj]);
+ i = ai + size;
+ j = bj + size;
+
+ if (size) answer.push(['equal', ai, i, bj, j]);
+ }
+ }
+
+ return answer;
+ }
+
+ // this is a generator function in the python lib, which of course is not supported in _javascript_
+ // the reimplementation builds up the grouped opcodes into a list in their entirety and returns that.
+ this.get_grouped_opcodes = function (n) {
+ if (!n) n = 3;
+ var codes = this.get_opcodes();
+ if (!codes) codes = [["equal", 0, 1, 0, 1]];
+ var code, tag, i1, i2, j1, j2;
+ if (codes[0][0] == 'equal') {
+ code = codes[0];
+ tag = code[0];
+ i1 = code[1];
+ i2 = code[2];
+ j1 = code[3];
+ j2 = code[4];
+ codes[0] = [tag, Math.max(i1, i2 - n), i2, Math.max(j1, j2 - n), j2];
+ }
+ if (codes[codes.length - 1][0] == 'equal') {
+ code = codes[codes.length - 1];
+ tag = code[0];
+ i1 = code[1];
+ i2 = code[2];
+ j1 = code[3];
+ j2 = code[4];
+ codes[codes.length - 1] = [tag, i1, Math.min(i2, i1 + n), j1, Math.min(j2, j1 + n)];
+ }
+
+ var nn = n + n;
+ var groups = [];
+ for (var idx in codes) {
+ if (codes.hasOwnProperty(idx)) {
+ code = codes[idx];
+ tag = code[0];
+ i1 = code[1];
+ i2 = code[2];
+ j1 = code[3];
+ j2 = code[4];
+ if (tag == 'equal' && i2 - i1 > nn) {
+ groups.push([tag, i1, Math.min(i2, i1 + n), j1, Math.min(j2, j1 + n)]);
+ i1 = Math.max(i1, i2-n);
+ j1 = Math.max(j1, j2-n);
+ }
+
+ groups.push([tag, i1, i2, j1, j2]);
+ }
+ }
+
+ if (groups && groups[groups.length - 1][0] == 'equal') groups.pop();
+
+ return groups;
+ }
+
+ this.ratio = function () {
+ matches = difflib.__reduce(
+ function (sum, triple) { return sum + triple[triple.length - 1]; },
+ this.get_matching_blocks(), 0);
+ return difflib.__calculate_ratio(matches, this.a.length + this.b.length);
+ }
+
+ this.quick_ratio = function () {
+ var fullbcount, elt;
+ if (this.fullbcount == null) {
+ this.fullbcount = fullbcount = {};
+ for (var i = 0; i < this.b.length; i++) {
+ elt = this.b[i];
+ fullbcount[elt] = difflib.__dictget(fullbcount, elt, 0) + 1;
+ }
+ }
+ fullbcount = this.fullbcount;
+
+ var avail = {};
+ var availhas = difflib.__isindict(avail);
+ var matches = numb = 0;
+ for (var i = 0; i < this.a.length; i++) {
+ elt = this.a[i];
+ if (availhas(elt)) {
+ numb = avail[elt];
+ } else {
+ numb = difflib.__dictget(fullbcount, elt, 0);
+ }
+ avail[elt] = numb - 1;
+ if (numb > 0) matches++;
+ }
+
+ return difflib.__calculate_ratio(matches, this.a.length + this.b.length);
+ }
+
+ this.real_quick_ratio = function () {
+ var la = this.a.length;
+ var lb = this.b.length;
+ return _calculate_ratio(Math.min(la, lb), la + lb);
+ }
+
+ this.isjunk = isjunk ? isjunk : difflib.defaultJunkFunction;
+ this.a = this.b = null;
+ this.set_seqs(a, b);
+ }
+}
Property changes on: trunk/Source/WebCore/inspector/front-end/jsdifflib.js
___________________________________________________________________
