[gi-docgen: 1/10] feat: add fzy.js

[Emmanuele Bassi <ebassi src gnome org>]

commit e93b512ec887281271224f82df8c8577f0d60afd
Author: Rom Grk <romgrk cc gmail com>
Date:   Thu Apr 1 00:07:24 2021 -0400

    feat: add fzy.js

 gidocgen/templates/basic/base.html  |   1 +
 gidocgen/templates/basic/basic.toml |   1 +
 gidocgen/templates/basic/fzy.js     | 241 ++++++++++++++++++++++++++++++++++++
 3 files changed, 243 insertions(+)
---
diff --git a/gidocgen/templates/basic/base.html b/gidocgen/templates/basic/base.html
index 4861059..ca3d3cb 100644
--- a/gidocgen/templates/basic/base.html
+++ b/gidocgen/templates/basic/base.html
@@ -83,6 +83,7 @@ SPDX-License-Identifier: Apache-2.0 OR GPL-3.0-or-later
     <section id="search" class="content hidden"></section>
 
     {% if CONFIG.search_index %}
+    <script src="fzy.js"></script>
     <script src="search.js"></script>
     {% endif %}
 
diff --git a/gidocgen/templates/basic/basic.toml b/gidocgen/templates/basic/basic.toml
index 0937194..35bf168 100644
--- a/gidocgen/templates/basic/basic.toml
+++ b/gidocgen/templates/basic/basic.toml
@@ -36,6 +36,7 @@ style = "style.css"
 [extra_files]
 files = [
   "main.js",
+  "fzy.js",
   "search.js",
   "stemmer.js",
   "pygment.css",
diff --git a/gidocgen/templates/basic/fzy.js b/gidocgen/templates/basic/fzy.js
new file mode 100644
index 0000000..c7dd78f
--- /dev/null
+++ b/gidocgen/templates/basic/fzy.js
@@ -0,0 +1,241 @@
+/* The MIT License (MIT)
+ *
+ * Copyright (c) 2014 John Hawthorn
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+window.fzy = (function() {
+    var SCORE_MIN = -Infinity;
+    var SCORE_MAX = Infinity;
+
+    var SCORE_GAP_LEADING = -0.005
+    var SCORE_GAP_TRAILING = -0.005
+    var SCORE_GAP_INNER = -0.01
+    var SCORE_MATCH_CONSECUTIVE = 1.0
+    var SCORE_MATCH_SLASH = 0.9
+    var SCORE_MATCH_WORD = 0.8
+    var SCORE_MATCH_CAPITAL = 0.7
+    var SCORE_MATCH_DOT = 0.6
+
+    function islower(s) {
+        return s.toLowerCase() === s;
+    }
+
+    function isupper(s) {
+        return s.toUpperCase() === s;
+    }
+
+    function precompute_bonus(haystack) {
+        /* Which positions are beginning of words */
+        var m = haystack.length;
+        var match_bonus = new Array(m);
+
+        var last_ch = '/';
+        for (var i = 0; i < m; i++) {
+            var ch = haystack[i];
+
+            if (last_ch === '/') {
+                match_bonus[i] = SCORE_MATCH_SLASH;
+            } else if (last_ch === '-' || last_ch === '_' || last_ch === ' ') {
+                match_bonus[i] = SCORE_MATCH_WORD;
+            } else if (last_ch === '.') {
+                match_bonus[i] = SCORE_MATCH_DOT;
+            } else if (islower(last_ch) && isupper(ch)) {
+                match_bonus[i] = SCORE_MATCH_CAPITAL;
+            } else {
+                match_bonus[i] = 0;
+            }
+
+            last_ch = ch;
+        }
+
+        return match_bonus;
+    }
+
+    function compute(needle, haystack, D, M) {
+        var n = needle.length;
+        var m = haystack.length;
+
+        var match_bonus = precompute_bonus(haystack, match_bonus);
+
+        /*
+        * D[][] Stores the best score for this position ending with a match.
+        * M[][] Stores the best possible score at this position.
+        */
+
+        for (var i = 0; i < n; i++) {
+            D[i] = new Array(m);
+            M[i] = new Array(m);
+
+            var prev_score = SCORE_MIN;
+            var gap_score = i === n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER;
+
+            for (var j = 0; j < m; j++) {
+                if (needle[i] === haystack[j]) {
+                    var score = SCORE_MIN;
+                    if (!i) {
+                        score = (j * SCORE_GAP_LEADING) + match_bonus[j];
+                    } else if (j) { /* i > 0 && j > 0*/
+                        score = Math.max(
+                            M[i - 1][j - 1] + match_bonus[j],
+
+                            /* consecutive match, doesn't stack with match_bonus */
+                            D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE);
+                    }
+                    D[i][j] = score;
+                    M[i][j] = prev_score = Math.max(score, prev_score + gap_score);
+                } else {
+                    D[i][j] = SCORE_MIN;
+                    M[i][j] = prev_score = prev_score + gap_score;
+                }
+            }
+        }
+    }
+
+    function score(needle, haystack) {
+        var n = needle.length;
+        var m = haystack.length;
+
+        if (!n || !m)
+            return SCORE_MIN;
+
+        if (n === m) {
+            /* Since this method can only be called with a haystack which
+            * matches needle. If the lengths of the strings are equal the
+            * strings themselves must also be equal (ignoring case).
+            */
+            return SCORE_MAX;
+        }
+
+        if (m > 1024) {
+            /*
+            * Unreasonably large candidate: return no score
+            * If it is a valid match it will still be returned, it will
+            * just be ranked below any reasonably sized candidates
+            */
+            return SCORE_MIN;
+        }
+
+        var D = new Array(n);
+        var M = new Array(n);
+
+        compute(needle, haystack, D, M)
+
+        return M[n - 1][m - 1];
+    }
+
+    function positions(needle, haystack) {
+        var n = needle.length;
+        var m = haystack.length;
+
+        var positions = new Array(n);
+
+        if (!n || !m)
+            return positions;
+
+        if (n === m) {
+            for (var i = 0; i < n; i++)
+                positions[i] = i;
+            return positions;
+        }
+
+        if (m > 1024) {
+            return positions;
+        }
+
+        var D = new Array(n);
+        var M = new Array(n);
+
+        compute(needle, haystack, D, M)
+
+        /* backtrack to find the positions of optimal matching */
+        var match_required = false;
+
+        for (var i = n - 1, j = m - 1; i >= 0; i--) {
+            for (; j >= 0; j--) {
+                /*
+                * There may be multiple paths which result in
+                * the optimal weight.
+                *
+                * For simplicity, we will pick the first one
+                * we encounter, the latest in the candidate
+                * string.
+                */
+                if (D[i][j] !== SCORE_MIN &&
+                    (match_required || D[i][j] === M[i][j])) {
+                    /* If this score was determined using
+                    * SCORE_MATCH_CONSECUTIVE, the
+                    * previous character MUST be a match
+                    */
+                    match_required =
+                        i && j &&
+                        M[i][j] === D[i - 1][j - 1] + SCORE_MATCH_CONSECUTIVE;
+                    positions[i] = j--;
+                    break;
+                }
+            }
+        }
+
+        return positions;
+    }
+
+    function hasMatch(needle, haystack) {
+        var l = needle.length
+        for (var i = 0, j = 0; i < l; i += 1) {
+            j = haystack.indexOf(needle[i], j) + 1
+            if (j === 0) return false
+        }
+        return true
+    }
+
+    function filter(needle, items, selector) {
+        const isCaseSensitive = needle.toLowerCase() !== needle;
+        const actualNeedle = isCaseSensitive ? needle : needle.toLowerCase();
+        const filteredItems = items.reduce((results, item) => {
+            const haystack = isCaseSensitive ? selector(item) : selector(item).toLowerCase();
+            if (hasMatch(actualNeedle, haystack))
+                results.push({ item, score: score(needle, haystack) })
+            return results;
+        }, [])
+        filteredItems.sort((a, b) => b.score - a.score)
+        return filteredItems;
+    }
+
+    return {
+        /* constants */
+        SCORE_MIN,
+        SCORE_MAX,
+
+        SCORE_GAP_LEADING,
+        SCORE_GAP_TRAILING,
+        SCORE_GAP_INNER,
+        SCORE_MATCH_CONSECUTIVE,
+        SCORE_MATCH_SLASH,
+        SCORE_MATCH_WORD,
+        SCORE_MATCH_CAPITAL,
+        SCORE_MATCH_DOT,
+
+        /* functions */
+        score,
+        positions,
+        hasMatch,
+        filter,
+    }
+})();