| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * This is part of jsdifflib v1.0. <http://snowtide.com/jsdifflib> | |
| 3 * | |
| 4 * Copyright (c) 2007, Snowtide Informatics Systems, Inc. | |
| 5 * All rights reserved. | |
| 6 * | |
| 7 * Redistribution and use in source and binary forms, with or without modificati
on, | |
| 8 * are permitted provided that the following conditions are met: | |
| 9 * | |
| 10 * * Redistributions of source code must retain the above copyright notice, t
his | |
| 11 * list of conditions and the following disclaimer. | |
| 12 * * Redistributions in binary form must reproduce the above copyright notice
, | |
| 13 * this list of conditions and the following disclaimer in the documentation | |
| 14 * and/or other materials provided with the distribution. | |
| 15 * * Neither the name of the Snowtide Informatics Systems nor the names of it
s | |
| 16 * contributors may be used to endorse or promote products derived from this | |
| 17 * software without specific prior written permission. | |
| 18 * | |
| 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" A
ND ANY | |
| 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WAR
RANTIES | |
| 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT | |
| 22 * SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | |
| 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED | |
| 24 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFIT
S; OR | |
| 25 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
IN | |
| 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
NG IN | |
| 27 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY O
F SUCH | |
| 28 * DAMAGE. | |
| 29 **/ | |
| 30 /* Author: Chas Emerick <cemerick@snowtide.com> */ | |
| 31 /* taken from https://github.com/cemerick/jsdifflib */ | |
| 32 | |
| 33 __whitespace = {" ":true, "\t":true, "\n":true, "\f":true, "\r":true}; | |
| 34 | |
| 35 difflib = { | |
| 36 defaultJunkFunction: function (c) { | |
| 37 return __whitespace.hasOwnProperty(c); | |
| 38 }, | |
| 39 | |
| 40 stripLinebreaks: function (str) { return str.replace(/^[\n\r]*|[\n\r]*$/g, "
"); }, | |
| 41 | |
| 42 stringAsLines: function (str) { | |
| 43 var lfpos = str.indexOf("\n"); | |
| 44 var crpos = str.indexOf("\r"); | |
| 45 var linebreak = ((lfpos > -1 && crpos > -1) || crpos < 0) ? "\n" : "\r"; | |
| 46 | |
| 47 var lines = str.split(linebreak); | |
| 48 for (var i = 0; i < lines.length; i++) { | |
| 49 lines[i] = difflib.stripLinebreaks(lines[i]); | |
| 50 } | |
| 51 | |
| 52 return lines; | |
| 53 }, | |
| 54 | |
| 55 // iteration-based reduce implementation | |
| 56 __reduce: function (func, list, initial) { | |
| 57 if (initial != null) { | |
| 58 var value = initial; | |
| 59 var idx = 0; | |
| 60 } else if (list) { | |
| 61 var value = list[0]; | |
| 62 var idx = 1; | |
| 63 } else { | |
| 64 return null; | |
| 65 } | |
| 66 | |
| 67 for (; idx < list.length; idx++) { | |
| 68 value = func(value, list[idx]); | |
| 69 } | |
| 70 | |
| 71 return value; | |
| 72 }, | |
| 73 | |
| 74 // comparison function for sorting lists of numeric tuples | |
| 75 __ntuplecomp: function (a, b) { | |
| 76 var mlen = Math.max(a.length, b.length); | |
| 77 for (var i = 0; i < mlen; i++) { | |
| 78 if (a[i] < b[i]) return -1; | |
| 79 if (a[i] > b[i]) return 1; | |
| 80 } | |
| 81 | |
| 82 return a.length == b.length ? 0 : (a.length < b.length ? -1 : 1); | |
| 83 }, | |
| 84 | |
| 85 __calculate_ratio: function (matches, length) { | |
| 86 return length ? 2.0 * matches / length : 1.0; | |
| 87 }, | |
| 88 | |
| 89 // returns a function that returns true if a key passed to the returned func
tion | |
| 90 // is in the dict (js object) provided to this function; replaces being able
to | |
| 91 // carry around dict.has_key in python... | |
| 92 __isindict: function (dict) { | |
| 93 return function (key) { return dict.hasOwnProperty(key); }; | |
| 94 }, | |
| 95 | |
| 96 // replacement for python's dict.get function -- need easy default values | |
| 97 __dictget: function (dict, key, defaultValue) { | |
| 98 return dict.hasOwnProperty(key) ? dict[key] : defaultValue; | |
| 99 }, | |
| 100 | |
| 101 SequenceMatcher: function (a, b, isjunk) { | |
| 102 this.set_seqs = function (a, b) { | |
| 103 this.set_seq1(a); | |
| 104 this.set_seq2(b); | |
| 105 } | |
| 106 | |
| 107 this.set_seq1 = function (a) { | |
| 108 if (a == this.a) return; | |
| 109 this.a = a; | |
| 110 this.matching_blocks = this.opcodes = null; | |
| 111 } | |
| 112 | |
| 113 this.set_seq2 = function (b) { | |
| 114 if (b == this.b) return; | |
| 115 this.b = b; | |
| 116 this.matching_blocks = this.opcodes = this.fullbcount = null; | |
| 117 this.__chain_b(); | |
| 118 } | |
| 119 | |
| 120 this.__chain_b = function () { | |
| 121 var b = this.b; | |
| 122 var n = b.length; | |
| 123 var b2j = this.b2j = {}; | |
| 124 var populardict = {}; | |
| 125 for (var i = 0; i < b.length; i++) { | |
| 126 var elt = b[i]; | |
| 127 if (b2j.hasOwnProperty(elt)) { | |
| 128 var indices = b2j[elt]; | |
| 129 if (n >= 200 && indices.length * 100 > n) { | |
| 130 populardict[elt] = 1; | |
| 131 delete b2j[elt]; | |
| 132 } else { | |
| 133 indices.push(i); | |
| 134 } | |
| 135 } else { | |
| 136 b2j[elt] = [i]; | |
| 137 } | |
| 138 } | |
| 139 | |
| 140 for (var elt in populardict) { | |
| 141 if (populardict.hasOwnProperty(elt)) { | |
| 142 delete b2j[elt]; | |
| 143 } | |
| 144 } | |
| 145 | |
| 146 var isjunk = this.isjunk; | |
| 147 var junkdict = {}; | |
| 148 if (isjunk) { | |
| 149 for (var elt in populardict) { | |
| 150 if (populardict.hasOwnProperty(elt) && isjunk(elt)) { | |
| 151 junkdict[elt] = 1; | |
| 152 delete populardict[elt]; | |
| 153 } | |
| 154 } | |
| 155 for (var elt in b2j) { | |
| 156 if (b2j.hasOwnProperty(elt) && isjunk(elt)) { | |
| 157 junkdict[elt] = 1; | |
| 158 delete b2j[elt]; | |
| 159 } | |
| 160 } | |
| 161 } | |
| 162 | |
| 163 this.isbjunk = difflib.__isindict(junkdict); | |
| 164 this.isbpopular = difflib.__isindict(populardict); | |
| 165 } | |
| 166 | |
| 167 this.find_longest_match = function (alo, ahi, blo, bhi) { | |
| 168 var a = this.a; | |
| 169 var b = this.b; | |
| 170 var b2j = this.b2j; | |
| 171 var isbjunk = this.isbjunk; | |
| 172 var besti = alo; | |
| 173 var bestj = blo; | |
| 174 var bestsize = 0; | |
| 175 var j = null; | |
| 176 | |
| 177 var j2len = {}; | |
| 178 var nothing = []; | |
| 179 for (var i = alo; i < ahi; i++) { | |
| 180 var newj2len = {}; | |
| 181 var jdict = difflib.__dictget(b2j, a[i], nothing); | |
| 182 for (var jkey in jdict) { | |
| 183 if (jdict.hasOwnProperty(jkey)) { | |
| 184 j = jdict[jkey]; | |
| 185 if (j < blo) continue; | |
| 186 if (j >= bhi) break; | |
| 187 newj2len[j] = k = difflib.__dictget(j2len, j - 1, 0) + 1
; | |
| 188 if (k > bestsize) { | |
| 189 besti = i - k + 1; | |
| 190 bestj = j - k + 1; | |
| 191 bestsize = k; | |
| 192 } | |
| 193 } | |
| 194 } | |
| 195 j2len = newj2len; | |
| 196 } | |
| 197 | |
| 198 while (besti > alo && bestj > blo && !isbjunk(b[bestj - 1]) && a[bes
ti - 1] == b[bestj - 1]) { | |
| 199 besti--; | |
| 200 bestj--; | |
| 201 bestsize++; | |
| 202 } | |
| 203 | |
| 204 while (besti + bestsize < ahi && bestj + bestsize < bhi && | |
| 205 !isbjunk(b[bestj + bestsize]) && | |
| 206 a[besti + bestsize] == b[bestj + bestsize]) { | |
| 207 bestsize++; | |
| 208 } | |
| 209 | |
| 210 while (besti > alo && bestj > blo && isbjunk(b[bestj - 1]) && a[best
i - 1] == b[bestj - 1]) { | |
| 211 besti--; | |
| 212 bestj--; | |
| 213 bestsize++; | |
| 214 } | |
| 215 | |
| 216 while (besti + bestsize < ahi && bestj + bestsize < bhi && isbjunk(b
[bestj + bestsize]) && | |
| 217 a[besti + bestsize] == b[bestj + bestsize]) { | |
| 218 bestsize++; | |
| 219 } | |
| 220 | |
| 221 return [besti, bestj, bestsize]; | |
| 222 } | |
| 223 | |
| 224 this.get_matching_blocks = function () { | |
| 225 if (this.matching_blocks != null) return this.matching_blocks; | |
| 226 var la = this.a.length; | |
| 227 var lb = this.b.length; | |
| 228 | |
| 229 var queue = [[0, la, 0, lb]]; | |
| 230 var matching_blocks = []; | |
| 231 var alo, ahi, blo, bhi, qi, i, j, k, x; | |
| 232 while (queue.length) { | |
| 233 qi = queue.pop(); | |
| 234 alo = qi[0]; | |
| 235 ahi = qi[1]; | |
| 236 blo = qi[2]; | |
| 237 bhi = qi[3]; | |
| 238 x = this.find_longest_match(alo, ahi, blo, bhi); | |
| 239 i = x[0]; | |
| 240 j = x[1]; | |
| 241 k = x[2]; | |
| 242 | |
| 243 if (k) { | |
| 244 matching_blocks.push(x); | |
| 245 if (alo < i && blo < j) | |
| 246 queue.push([alo, i, blo, j]); | |
| 247 if (i+k < ahi && j+k < bhi) | |
| 248 queue.push([i + k, ahi, j + k, bhi]); | |
| 249 } | |
| 250 } | |
| 251 | |
| 252 matching_blocks.sort(difflib.__ntuplecomp); | |
| 253 | |
| 254 var i1 = j1 = k1 = block = 0; | |
| 255 var non_adjacent = []; | |
| 256 for (var idx in matching_blocks) { | |
| 257 if (matching_blocks.hasOwnProperty(idx)) { | |
| 258 block = matching_blocks[idx]; | |
| 259 i2 = block[0]; | |
| 260 j2 = block[1]; | |
| 261 k2 = block[2]; | |
| 262 if (i1 + k1 == i2 && j1 + k1 == j2) { | |
| 263 k1 += k2; | |
| 264 } else { | |
| 265 if (k1) non_adjacent.push([i1, j1, k1]); | |
| 266 i1 = i2; | |
| 267 j1 = j2; | |
| 268 k1 = k2; | |
| 269 } | |
| 270 } | |
| 271 } | |
| 272 | |
| 273 if (k1) non_adjacent.push([i1, j1, k1]); | |
| 274 | |
| 275 non_adjacent.push([la, lb, 0]); | |
| 276 this.matching_blocks = non_adjacent; | |
| 277 return this.matching_blocks; | |
| 278 } | |
| 279 | |
| 280 this.get_opcodes = function () { | |
| 281 if (this.opcodes != null) return this.opcodes; | |
| 282 var i = 0; | |
| 283 var j = 0; | |
| 284 var answer = []; | |
| 285 this.opcodes = answer; | |
| 286 var block, ai, bj, size, tag; | |
| 287 var blocks = this.get_matching_blocks(); | |
| 288 for (var idx in blocks) { | |
| 289 if (blocks.hasOwnProperty(idx)) { | |
| 290 block = blocks[idx]; | |
| 291 ai = block[0]; | |
| 292 bj = block[1]; | |
| 293 size = block[2]; | |
| 294 tag = ''; | |
| 295 if (i < ai && j < bj) { | |
| 296 tag = 'replace'; | |
| 297 } else if (i < ai) { | |
| 298 tag = 'delete'; | |
| 299 } else if (j < bj) { | |
| 300 tag = 'insert'; | |
| 301 } | |
| 302 if (tag) answer.push([tag, i, ai, j, bj]); | |
| 303 i = ai + size; | |
| 304 j = bj + size; | |
| 305 | |
| 306 if (size) answer.push(['equal', ai, i, bj, j]); | |
| 307 } | |
| 308 } | |
| 309 | |
| 310 return answer; | |
| 311 } | |
| 312 | |
| 313 // this is a generator function in the python lib, which of course is no
t supported in javascript | |
| 314 // the reimplementation builds up the grouped opcodes into a list in the
ir entirety and returns that. | |
| 315 this.get_grouped_opcodes = function (n) { | |
| 316 if (!n) n = 3; | |
| 317 var codes = this.get_opcodes(); | |
| 318 if (!codes) codes = [["equal", 0, 1, 0, 1]]; | |
| 319 var code, tag, i1, i2, j1, j2; | |
| 320 if (codes[0][0] == 'equal') { | |
| 321 code = codes[0]; | |
| 322 tag = code[0]; | |
| 323 i1 = code[1]; | |
| 324 i2 = code[2]; | |
| 325 j1 = code[3]; | |
| 326 j2 = code[4]; | |
| 327 codes[0] = [tag, Math.max(i1, i2 - n), i2, Math.max(j1, j2 - n),
j2]; | |
| 328 } | |
| 329 if (codes[codes.length - 1][0] == 'equal') { | |
| 330 code = codes[codes.length - 1]; | |
| 331 tag = code[0]; | |
| 332 i1 = code[1]; | |
| 333 i2 = code[2]; | |
| 334 j1 = code[3]; | |
| 335 j2 = code[4]; | |
| 336 codes[codes.length - 1] = [tag, i1, Math.min(i2, i1 + n), j1, Ma
th.min(j2, j1 + n)]; | |
| 337 } | |
| 338 | |
| 339 var nn = n + n; | |
| 340 var groups = []; | |
| 341 for (var idx in codes) { | |
| 342 if (codes.hasOwnProperty(idx)) { | |
| 343 code = codes[idx]; | |
| 344 tag = code[0]; | |
| 345 i1 = code[1]; | |
| 346 i2 = code[2]; | |
| 347 j1 = code[3]; | |
| 348 j2 = code[4]; | |
| 349 if (tag == 'equal' && i2 - i1 > nn) { | |
| 350 groups.push([tag, i1, Math.min(i2, i1 + n), j1, Math.min
(j2, j1 + n)]); | |
| 351 i1 = Math.max(i1, i2-n); | |
| 352 j1 = Math.max(j1, j2-n); | |
| 353 } | |
| 354 | |
| 355 groups.push([tag, i1, i2, j1, j2]); | |
| 356 } | |
| 357 } | |
| 358 | |
| 359 if (groups && groups[groups.length - 1][0] == 'equal') groups.pop(); | |
| 360 | |
| 361 return groups; | |
| 362 } | |
| 363 | |
| 364 this.ratio = function () { | |
| 365 matches = difflib.__reduce( | |
| 366 function (sum, triple) { return sum + triple[triple.
length - 1]; }, | |
| 367 this.get_matching_blocks(), 0); | |
| 368 return difflib.__calculate_ratio(matches, this.a.length + this.b.len
gth); | |
| 369 } | |
| 370 | |
| 371 this.quick_ratio = function () { | |
| 372 var fullbcount, elt; | |
| 373 if (this.fullbcount == null) { | |
| 374 this.fullbcount = fullbcount = {}; | |
| 375 for (var i = 0; i < this.b.length; i++) { | |
| 376 elt = this.b[i]; | |
| 377 fullbcount[elt] = difflib.__dictget(fullbcount, elt, 0) + 1; | |
| 378 } | |
| 379 } | |
| 380 fullbcount = this.fullbcount; | |
| 381 | |
| 382 var avail = {}; | |
| 383 var availhas = difflib.__isindict(avail); | |
| 384 var matches = numb = 0; | |
| 385 for (var i = 0; i < this.a.length; i++) { | |
| 386 elt = this.a[i]; | |
| 387 if (availhas(elt)) { | |
| 388 numb = avail[elt]; | |
| 389 } else { | |
| 390 numb = difflib.__dictget(fullbcount, elt, 0); | |
| 391 } | |
| 392 avail[elt] = numb - 1; | |
| 393 if (numb > 0) matches++; | |
| 394 } | |
| 395 | |
| 396 return difflib.__calculate_ratio(matches, this.a.length + this.b.len
gth); | |
| 397 } | |
| 398 | |
| 399 this.real_quick_ratio = function () { | |
| 400 var la = this.a.length; | |
| 401 var lb = this.b.length; | |
| 402 return _calculate_ratio(Math.min(la, lb), la + lb); | |
| 403 } | |
| 404 | |
| 405 this.isjunk = isjunk ? isjunk : difflib.defaultJunkFunction; | |
| 406 this.a = this.b = null; | |
| 407 this.set_seqs(a, b); | |
| 408 } | |
| 409 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1336803005:
DevTools: use diff_match_patch instead of jsdifflib for text diffing. (Closed)
Base URL: svn://svn.chromium.org/blink/trunk