Adding upstream version 1.55.0+dfsg.upstream/1.55.0+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 306 insertions, 0 deletions

diff --git a/src/lib/diff/README.md b/src/lib/diff/README.md
new file mode 100644
index 0000000..e1a90b0
--- /dev/null
+++ b/src/lib/diff/README.md
@@ -0,0 +1,34 @@
+# diff
+
+implementation of myers diff algorithm
+
+[![Build Status](https://travis-ci.org/Swatinem/diff.png?branch=master)](https://travis-ci.org/Swatinem/diff)
+[![Coverage Status](https://coveralls.io/repos/Swatinem/diff/badge.png?branch=master)](https://coveralls.io/r/Swatinem/diff)
+[![Dependency Status](https://gemnasium.com/Swatinem/diff.png)](https://gemnasium.com/Swatinem/diff)
+
+
+This uses the [*An O(ND) Difference Algorithm and Its Variations*](http://www.xmailserver.org/diff2.pdf)
+Also see http://simplygenius.net/Article/DiffTutorial2 and
+http://www.mathertel.de/Diff/ViewSrc.aspx for more inspiration
+
+## Installation
+
+    $ npm install diff
+    $ component install Swatinem/diff
+
+## Usage
+
+### diff(a, b, [eql(a, b)])
+
+Given two arrays (or array-likes, such as strings) `a` and `b` and an optional
+equal function `eql`, this will return an array with the following operations:
+* *nop* the element is in both arrays
+* *ins* the element is only in array `b` and will be inserted
+* *del* the element in only in array `a` and will be removed
+* *rep* the element from `a` will be replaced by the element from `b`.
+This is essentially the same as a del+ins
+
+## License
+
+  LGPLv3
+
diff --git a/src/lib/diff/swatinem_diff.js b/src/lib/diff/swatinem_diff.js
new file mode 100644
index 0000000..d986b2f
--- /dev/null
+++ b/src/lib/diff/swatinem_diff.js
@@ -0,0 +1,272 @@
+/*******************************************************************************
+
+  Key portions of code below was borrowed from:
+    https://github.com/Swatinem/diff
+
+  License is LGPL3 (thanks!) as per:
+    https://github.com/Swatinem/diff/blob/b58391504759/README.md
+
+  I chose to pick this implementation over
+  https://github.com/google/diff-match-patch as suggested by CodeMirror
+  because:
+
+  - Code is clean and simple to read -- useful when unfamiliar with the diff
+    algorithm, this makes changing the code easier if/when needed.
+
+  - Smaller -- diff_match_patch comes with an extended API most of which is
+    of no use to the current project.
+    - diff_match_patch uncompressed: 74.7 KB
+    - Swatinem's diff uncompressed: 3.66 KB
+
+  - I can easily adapt Swatinem's diff to deal with arrays of strings, which
+    is best suited for the current project -- it natively work with arrays.
+
+  I removed portions of code which are of no use for the current project.
+
+  I modified the diff script generator (Diff.prototype.editscript) since I
+  need to generate a script which is compatible with the output of the
+  diff_match_patch, as expected by CodeMirror.
+
+  2018-12-20 gorhill:
+  ===================
+  There was an issue causing the wrong diff data to be issued, for instance
+  when diff-ing these two URLs on a character granularity basis (failure
+  point is marked):
+                                                                                                                          |
+  /articles/5c1a7aae1854f30006cb26f7/lede/1545239527833-shutterstock_726   01757 2-copy.jpeg?crop=0.8889xw%3A0.9988xh%3B0.1089xw%2C0xh&resize=650%3A*&output-quality=55
+  /articles/5c1a*   1854f30006cb2*  /lede/15452*       -shutterstock_*     017*  2-copy.jpeg?crop=0.*   xw%3A*      h%3B0.0*  xw%2C0xh&resize=650%3A*&output-quality=55
+  /articles/5c1aaea91854f30006cb2f1e/lede/1545253629235-shutterstock_106399017   2-copy.jpeg?crop=0.7749xw%3A1     xh%3B0.0391xw%2C0xh&resize=650%3A*&output-quality=55
+                                                                                                                          |
+
+  Investigating, I found what appears to be the original source on which the
+  code below is based:
+  - "An O(ND) Difference Algorithm for C#" by Matthias Hertel
+  - http://www.mathertel.de/Diff/ViewSrc.aspx
+  - https://github.com/mathertel
+
+  There was a difference; code had been commented out in the original source:
+  http://www.mathertel.de/Diff/DiffTest.aspx?oldfile=Diff.cs.v1&newfile=Diff.cs.v2
+
+  The developer noted:
+  > There have been overlapping boxes; that where analyzed partial differently.
+  > One return-point is enough.
+
+  After applying the changes to the code below, the problematic diff-ing went
+  away:
+                                                                                                                          |
+  /articles/5c1a7aae1854f30006cb26f7/lede/1545239527833-shutterstock_726   01757 2-copy.jpeg?crop=0.8889xw%3A0.9988xh%3B0.1089xw%2C0xh&resize=650%3A*&output-quality=55
+  /articles/5c1a*   1854f30006cb2*  /lede/15452*       -shutterstock_*     017*  2-copy.jpeg?crop=0.*  9xw%3A*     xh%3B0.*   xw%2C0xh&resize=650%3A*&output-quality=55
+  /articles/5c1aaea91854f30006cb2f1e/lede/1545253629235-shutterstock_106399017   2-copy.jpeg?crop=0.7749xw%3A1     xh%3B0.0391xw%2C0xh&resize=650%3A*&output-quality=55
+                                                                                                                          |
+
+  So I will assume this was the issue.
+
+  2021-07-17 gorhill:
+  ===================
+  Added pure diff() method which natively deals with arrays and other minor
+  changes related to ES6.
+  
+**/
+
+'use strict';
+
+(function(context) {
+
+    // CodeMirror expect these globals:
+    context.DIFF_INSERT = 1;
+    context.DIFF_DELETE = -1;
+    context.DIFF_EQUAL = 0;
+    context.diff_match_patch = function(){};
+
+    context.diff_match_patch.prototype.diff_main = function(a, b) {
+        if ( a === b ) { return [ [ 0, a ] ]; }
+        const aa = a.match(/\n|[^\n]+\n?/g) || [];
+        const bb = b.match(/\n|[^\n]+\n?/g) || [];
+        const d = new Diff(aa, bb);
+        return d.editscript();
+    };
+
+    context.diff_match_patch.prototype.diff = function(a, b) {
+        const d = new Diff(a, b);
+        return d.editscript();
+    };
+
+    const eqlDefault = (a, b) => a === b;
+
+    function Diff(a, b, eql = eqlDefault) {
+        this.a = a;
+        this.b = b;
+        this.eql = eql;
+
+        this.moda = Array.apply(null, new Array(a.length)).map(true.valueOf, false);
+        this.modb = Array.apply(null, new Array(b.length)).map(true.valueOf, false);
+
+        // just to save some allocations:
+        this.down = {};
+        this.up = {};
+
+        this.lcs(0, a.length, 0, b.length);
+    }
+
+    Diff.prototype.editscript = function Diff_editscript() {
+        const moda = this.moda, modb = this.modb;
+        var astart = 0, aend = moda.length;
+        var bstart = 0, bend = modb.length;
+        const result = [];
+        while (astart < aend || bstart < bend) {
+            if (astart < aend && bstart < bend) {
+                if (!moda[astart] && !modb[bstart]) {
+                    result.push([ 0, this.a[astart] ]);
+                    astart++; bstart++;
+                    continue;
+                } else if (moda[astart] && modb[bstart]) {
+                    result.push([ -1, this.a[astart] ]);
+                    result.push([ 1, this.b[bstart] ]);
+                    astart++; bstart++;
+                    continue;
+                }
+            }
+            if (astart < aend && (bstart >= bend || moda[astart])) {
+                result.push([ -1, this.a[astart] ]);
+                astart++;
+            }
+            if (bstart < bend && (astart >= aend || modb[bstart])) {
+                result.push([ 1, this.b[bstart] ]);
+                bstart++;
+            }
+        }
+        return result;
+    };
+
+    Diff.prototype.lcs = function Diff_lcs(astart, aend, bstart, bend) {
+        const a = this.a, b = this.b, eql = this.eql;
+        // separate common head
+        while (astart < aend && bstart < bend && eql(a[astart], b[bstart])) {
+            astart++; bstart++;
+        }
+        // separate common tail
+        while (astart < aend && bstart < bend && eql(a[aend - 1], b[bend - 1])) {
+            aend--; bend--;
+        }
+
+        if (astart === aend) {
+            // only insertions
+            while (bstart < bend) {
+                this.modb[bstart] = true;
+                bstart++;
+            }
+        } else if (bend === bstart) {
+            // only deletions
+            while (astart < aend) {
+                this.moda[astart] = true;
+                astart++;
+            }
+        } else {
+            const snake = this.snake(astart, aend, bstart, bend);
+
+            this.lcs(astart, snake.x, bstart, snake.y);
+            this.lcs(snake.x, aend, snake.y, bend);
+        }
+    };
+
+    Diff.prototype.snake = function Diff_snake(astart, aend, bstart, bend) {
+        const a = this.a, b = this.b, eql = this.eql;
+
+        const N = aend - astart;
+        const M = bend - bstart;
+
+        const kdown = astart - bstart;
+        const kup   = aend   - bend;
+
+        const delta = N - M;
+        const deltaOdd = delta & 1;
+
+        const down = this.down;
+        down[kdown + 1] = astart;
+        const up = this.up;
+        up[kup - 1] = aend;
+
+        const Dmax = (N + M + 1) / 2;
+        for (let D = 0; D <= Dmax; D++) {
+            // forward path
+            for (let k = kdown - D; k <= kdown + D; k += 2) {
+                let x;
+                if (k === kdown - D) {
+                    x = down[k + 1]; // down
+                } else {
+                    x = down[k - 1] + 1; // right
+                    if ((k < kdown + D) && (down[k + 1] >= x)) {
+                        x = down[k + 1]; // down
+                    }
+                }
+                let y = x - k;
+
+                while (x < aend && y < bend && eql(a[x], b[y])) {
+                    x++; y++; // diagonal
+                }
+                down[k] = x;
+
+                if (deltaOdd && (kup - D < k) && (k < kup + D) &&
+                    up[k] <= down[k]) {
+                    return {
+                        x: down[k],
+                        y: down[k] - k,
+                    //    u: up[k],
+                    //    v: up[k] - k,
+                    };
+                }
+            }
+
+            // reverse path
+            for (let k = kup - D; k <= kup + D; k += 2) {
+                let x;
+                if (k === kup + D) {
+                    x = up[k - 1]; // up
+                } else {
+                    x = up[k + 1] - 1; // left
+                    if ((k > kup - D) && (up[k - 1] < x)) {
+                        x = up[k - 1]; // up
+                    }
+                }
+                let y = x - k;
+
+                while (x > astart && y > bstart && eql(a[x - 1], b[y - 1])) {
+                    x--; y--; // diagonal
+                }
+                up[k] = x;
+
+                if (!deltaOdd && (kdown - D <= k) && (k <= kdown + D) &&
+                    up[k] <= down[k]) {
+                    return {
+                        x: down[k],
+                        y: down[k] - k,
+                    //    u: up[k],
+                    //    v: up[k] - k,
+                    };
+                }
+            }
+        }
+    };
+
+    return Diff;
+})(self);
+
+
+
+
+
+
+
+
+/*******************************************************************************
+
+    DO NOT:
+    - Remove the following code
+    - Add code beyond the following code
+    Reason:
+    - https://github.com/gorhill/uBlock/pull/3721
+    - uBO never uses the return value from injected content scripts
+
+**/
+
+void 0;