src/redakcja/static/js/lib/diff.js

   1 $.wiki.diff = function(a, b) {
   2     MAXD = 500;
   3
   4     let VV = new Array(),
   5         N = a.length,
   6         M = b.length,
   7         V, Vp, D, x, y, k;
   8     V = VV[-1] = Array();
   9     V[1] = 0;
  10     let endD = null;
  11     for (D = 0; D < MAXD && endD === null; D++) {
  12         Vp = V;
  13         V = VV[D] = Array();
  14         for (k = -D; k <= D; k += 2) {
  15             if (k == -D || (k != D && Vp[k-1] < Vp[k + 1])) {
  16                 x = Vp[k + 1];
  17             } else {
  18                 x = Vp[k - 1] + 1;
  19             }
  20             y = x - k;
  21
  22             while (x < N && y < M && a[x] == b[y]) {
  23                 x ++;
  24                 y ++;
  25
  26                 // Avoid comparing long text character by character.
  27                 let step = 1;
  28                 while (true) {
  29                     step = Math.min(step * 2, N - x, M - y);
  30                     if (!step) break;
  31                     if (a.substr(x, step) == b.substr(y, step)) {
  32                         x += step;
  33                         y += step;
  34                     } else {
  35                         break;
  36                     }
  37                 }
  38             }
  39
  40             V[k] = x;
  41             if (x == N && y == M) {
  42                 endD = D;
  43                 break;
  44             }
  45         }
  46     }
  47     if (endD === null) {
  48         // Max D limit reached, diff too big. Bail and just return the whole target text.
  49         return b;
  50     }
  51
  52     // Now go back.
  53     result = []
  54     let px, py;
  55     for (D = endD; D; --D) {
  56         k = x - y;
  57         V = VV[D - 1];
  58         if (V[k - 1] === undefined || V[k + 1] > V[k - 1]) {
  59             // move up
  60             k ++;
  61             px = V[k];
  62             py = px - k;
  63             if (result.length && result[0][0] && result[0][1] == px) {
  64                 result[0][2] = b[py] + result[0][2];
  65             } else {
  66                 result.unshift(
  67                     [true, px, b[py]]
  68                 )
  69             }
  70         } else {
  71             // move down
  72             k --;
  73             px = V[k];
  74             py = px - k;
  75             if (result.length && !result[0][0] && result[0][1] == px + 1) {
  76                 result[0][1]--;
  77                 result[0][2]++;
  78             } else {
  79                 result.unshift(
  80                     [false, px, 1]
  81                 )
  82             }
  83         }
  84         x = px;
  85         y = py;
  86     }
  87     return result
  88 }
  89
  90
  91 $.wiki.patch = function(a, p) {
  92     for (i = p.length - 1; i >= 0; -- i) {
  93         let c = p[i];
  94         if (c[0]) {
  95             a = a.substr(0, c[1]) + c[2] + a.substr(c[1]);
  96         } else {
  97             a = a.substr(0, c[1]) + a.substr(c[1] + c[2]);
  98         }
  99     }
 100     return a;
 101 }