Remove duplicated results in the search

1 files changed, 88 insertions, 47 deletions

diff --git a/src/librustdoc/html/static/main.js b/src/librustdoc/html/static/main.js
index 0323c083b9b..b1120e0af38 100644
--- a/src/librustdoc/html/static/main.js
+++ b/src/librustdoc/html/static/main.js
@@ -349,7 +349,7 @@
             var valLower = query.query.toLowerCase(),
                 val = valLower,
                 typeFilter = itemTypeFromName(query.type),
-                results = [],
+                results = {},
                 split = valLower.split("::");
 
             // remove empty keywords
@@ -360,6 +360,23 @@
                 }
             }
 
+            function min(a, b) {
+                if (a < b) {
+                    return a;
+                }
+                return b;
+            }
+
+            function nbElements(obj) {
+                var size = 0, key;
+                for (key in obj) {
+                    if (obj.hasOwnProperty(key)) {
+                        size += 1;
+                    }
+                }
+                return size;
+            }
+
             function findArg(obj, val) {
                 var lev_distance = MAX_LEV_DISTANCE + 1;
                 if (obj && obj.type && obj.type.inputs.length > 0) {
@@ -368,9 +385,9 @@
                             // No need to check anything else: we found it. Let's just move on.
                             return 0;
                         }
-                        var tmp = levenshtein(obj.type.inputs[i].name, val);
-                        if (tmp < lev_distance) {
-                            lev_distance = tmp;
+                        lev_distance = min(levenshtein(obj.type.inputs[i].name, val), lev_distance);
+                        if (lev_distance === 0) {
+                            return 0;
                         }
                     }
                 }
@@ -378,13 +395,17 @@
             }
 
             function checkReturned(obj, val) {
+                var lev_distance = MAX_LEV_DISTANCE + 1;
                 if (obj && obj.type && obj.type.output) {
                     if (obj.type.output.name.toLowerCase() === val) {
                         return 0;
                     }
-                    return levenshtein(obj.type.output.name.toLowerCase(), val);
+                    lev_distance = min(levenshtein(obj.type.output.name, val));
+                    if (lev_distance === 0) {
+                        return 0;
+                    }
                 }
-                return MAX_LEV_DISTANCE + 1;
+                return lev_distance;
             }
 
             function typePassesFilter(filter, type) {
@@ -414,22 +435,27 @@
             if ((val.charAt(0) === "\"" || val.charAt(0) === "'") &&
                 val.charAt(val.length - 1) === val.charAt(0))
             {
-                val = val.substr(1, val.length - 2);
+                val = val.substr(1, val.length - 2).toLowerCase();
                 for (var i = 0; i < nSearchWords; ++i) {
+                    var ty = searchIndex[i];
                     if (searchWords[i] === val) {
                         // filter type: ... queries
                         if (typePassesFilter(typeFilter, searchIndex[i].ty)) {
-                            results.push({id: i, index: -1});
+                            results[ty.path + ty.name] = {id: i, index: -1};
                         }
-                    } else if (findArg(searchIndex[i], val.toLowerCase()) ||
-                               (searchIndex[i].type &&
-                                searchIndex[i].type.output &&
-                                searchIndex[i].type.output.name === val.toLowerCase())) {
+                    } else if (findArg(searchIndex[i], val) ||
+                               (ty.type &&
+                                ty.type.output &&
+                                ty.type.output.name === val)) {
                         if (typePassesFilter(typeFilter, searchIndex[i].ty)) {
-                            results.push({id: i, index: -1, dontValidate: true});
+                            results[ty.path + ty.name] = {
+                                id: i,
+                                index: -1,
+                                dontValidate: true,
+                            };
                         }
                     }
-                    if (results.length === max) {
+                    if (nbElements(results) === max) {
                         break;
                     }
                 }
@@ -447,6 +473,7 @@
 
                 for (var i = 0; i < nSearchWords; ++i) {
                     var type = searchIndex[i].type;
+                    var ty = searchIndex[i];
                     if (!type) {
                         continue;
                     }
@@ -460,7 +487,7 @@
                     var typeOutput = type.output ? type.output.name : "";
                     if (output === "*" || output == typeOutput) {
                         if (input === "*") {
-                            results.push({id: i, index: -1, dontValidate: true});
+                            results[ty.path + ty.name] = {id: i, index: -1, dontValidate: true};
                         } else {
                             var allFound = true;
                             for (var it = 0; allFound === true && it < inputs.length; it++) {
@@ -471,7 +498,11 @@
                                 allFound = found;
                             }
                             if (allFound === true) {
-                                results.push({id: i, index: -1, dontValidate: true});
+                                results[ty.path + ty.name] = {
+                                    id: i,
+                                    index: -1,
+                                    dontValidate: true,
+                                };
                             }
                         }
                     }
@@ -487,57 +518,77 @@
                 for (var i = 0; i < split.length; ++i) {
                     for (var j = 0; j < nSearchWords; ++j) {
                         var lev_distance;
+                        var ty = searchIndex[j];
+                        if (!ty) {
+                            continue;
+                        }
                         if (searchWords[j].indexOf(split[i]) > -1 ||
                             searchWords[j].indexOf(val) > -1 ||
                             searchWords[j].replace(/_/g, "").indexOf(val) > -1)
                         {
                             // filter type: ... queries
                             if (typePassesFilter(typeFilter, searchIndex[j].ty)) {
-                                results.push({
+                                results[ty.path + ty.name] = {
                                     id: j,
                                     index: searchWords[j].replace(/_/g, "").indexOf(val),
                                     lev: 0,
-                                });
+                                };
                             }
                         } else if (
                             (lev_distance = levenshtein(searchWords[j], val)) <= MAX_LEV_DISTANCE) {
                             if (typePassesFilter(typeFilter, searchIndex[j].ty)) {
-                                results.push({
-                                    id: j,
-                                    index: 0,
-                                    // we want lev results to go lower than others
-                                    lev: lev_distance,
-                                });
+                                if (results[ty.path + ty.name] === undefined ||
+                                    results[ty.path + ty.name].lev > lev_distance) {
+                                    results[ty.path + ty.name] = {
+                                        id: j,
+                                        index: 0,
+                                        // we want lev results to go lower than others
+                                        lev: lev_distance,
+                                    };
+                                }
                             }
                         } else if (
                             (lev_distance = findArg(searchIndex[j], val)) <= MAX_LEV_DISTANCE) {
                             if (typePassesFilter(typeFilter, searchIndex[j].ty)) {
-                                results.push({
-                                    id: j,
-                                    index: 0,
-                                    // we want lev results to go lower than others
-                                    lev: lev_distance,
-                                });
+                                if (results[ty.path + ty.name] === undefined ||
+                                    results[ty.path + ty.name].lev > lev_distance) {
+                                    results[ty.path + ty.name] = {
+                                        id: j,
+                                        index: 0,
+                                        // we want lev results to go lower than others
+                                        lev: lev_distance,
+                                    };
+                                }
                             }
                         } else if (
                             (lev_distance = checkReturned(searchIndex[j], val)) <=
                             MAX_LEV_DISTANCE) {
                             if (typePassesFilter(typeFilter, searchIndex[j].ty)) {
-                                results.push({
-                                    id: j,
-                                    index: 0,
-                                    // we want lev results to go lower than others
-                                    lev: lev_distance,
-                                });
+                                if (results[ty.path + ty.name] === undefined ||
+                                    results[ty.path + ty.name].lev > lev_distance) {
+                                    results[ty.path + ty.name] = {
+                                        id: j,
+                                        index: 0,
+                                        // we want lev results to go lower than others
+                                        lev: lev_distance,
+                                    };
+                                }
                             }
                         }
-                        if (results.length === max) {
+                        if (nbElements(results) === max) {
                             break;
                         }
                     }
                 }
             }
 
+            var ar = [];
+            for (var entry in results) {
+                if (results.hasOwnProperty(entry)) {
+                    ar.push(results[entry]);
+                }
+            }
+            results = ar;
             var nresults = results.length;
             for (var i = 0; i < nresults; ++i) {
                 results[i].word = searchWords[results[i].id];
@@ -613,16 +664,6 @@
                 return 0;
             });
 
-            // remove duplicates, according to the data provided
-            for (var i = results.length - 1; i > 0; i -= 1) {
-                if (results[i].word === results[i - 1].word &&
-                    results[i].item.ty === results[i - 1].item.ty &&
-                    results[i].item.path === results[i - 1].item.path &&
-                    (results[i].item.parent || {}).name === (results[i - 1].item.parent || {}).name)
-                {
-                    results[i].id = -1;
-                }
-            }
             for (var i = 0; i < results.length; ++i) {
                 var result = results[i],
                     name = result.item.name.toLowerCase(),