Repository: chaijs/chai
Pull request #1098 (2017-12-02 22:52:56)

perf: Optimize proxify and stringDistance
- Fill 2D array with ints upfront to reduce property access cost
- Change from recursive to simpler iterative (DP) solution
- Add cap parameter to stringDistanceCapped to limit computation
- Make candidate generation use a simple loop to avoid allocating unnecessary arrays and to call stringDistance only once on each pair of strings instead of every time in the sort callback

This improves chai perf by about 13% on @bmeurer's https://github.com/v8/web-tooling-benchmark.

codecov[bot]: # [Codecov](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=h1) Report
> Merging [#1098](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=desc) into [master](https://codecov.io/gh/chaijs/chai/commit/eae99d1502b8f5ec242a0ca1f650168c6da7988b?src=pr&el=desc) will **decrease** coverage by `0.02%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/chaijs/chai/pull/1098/graphs/tree.svg?width=650&height=150&src=pr&token=J8Fz3KwOQq)](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #1098      +/-   ##
==========================================
- Coverage   93.61%   93.58%   -0.03%     
==========================================
  Files          32       32              
  Lines        1628     1637       +9     
  Branches      393      393              
==========================================
+ Hits         1524     1532       +8     
- Misses        104      105       +1
```


| [Impacted Files](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [lib/chai/utils/proxify.js](https://codecov.io/gh/chaijs/chai/pull/1098/diff?src=pr&el=tree#diff-bGliL2NoYWkvdXRpbHMvcHJveGlmeS5qcw==) | `100% <100%> (ø)` | :arrow_up: |
| [lib/chai/utils/overwriteProperty.js](https://codecov.io/gh/chaijs/chai/pull/1098/diff?src=pr&el=tree#diff-bGliL2NoYWkvdXRpbHMvb3ZlcndyaXRlUHJvcGVydHkuanM=) | `90.9% <0%> (-4.55%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=footer). Last update [eae99d1...5467f07](https://codecov.io/gh/chaijs/chai/pull/1098?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

sophiebits: I didn't try that but it makes sense. I did try hoisting the 2D array as a static 41x41 array (and bailing out on names longer than 40 chars) and it didn't seem to help much. Not sure where the bottleneck is now.
bmeurer: In this case it doesn't matter, since the arrays contain only small integers.

Patch:
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index 78e2ce4..88072d4 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -154,7 +154,7 @@ Simply run `make release-major`, `make release-minor`, or `make-release-patch`
 and it will automatically do the following:
 
  - Build chai.js
- - Bump the version numbers accross the project
+ - Bump the version numbers across the project
  - Make a commit within git
 
 All you need to do is push the commit up and make a pull request, one of the core contributors will merge it and publish a release.
@@ -163,7 +163,7 @@ All you need to do is push the commit up and make a pull request, one of the cor
 
 Anyone who is a core contributor (see the [Core Contributors Heading in the Readme](https://github.com/chaijs/chai#core-contributors)) can publish a release:
 
-1. Go to te [Releases page on Github](https://github.com/chaijs/chai/releases)
+1. Go to the [Releases page on Github](https://github.com/chaijs/chai/releases)
 2. Hit "Draft a new release" (if you can't see this, you're not a core contributor!)
 3. Write human-friendly Release Notes based on changelog.
   - The release title is "x.x.x / YYYY-MM-DD" (where x.x.x is the version number)
diff --git a/lib/chai/config.js b/lib/chai/config.js
index ca1e30a..412a0c8 100644
--- a/lib/chai/config.js
+++ b/lib/chai/config.js
@@ -90,5 +90,5 @@ module.exports = {
    * @api public
    */
 
-  proxyExcludedKeys: ['then', 'inspect', 'toJSON']
+  proxyExcludedKeys: ['then', 'catch', 'inspect', 'toJSON']
 };
diff --git a/lib/chai/interface/assert.js b/lib/chai/interface/assert.js
index 03dfd10..7772e2c 100644
--- a/lib/chai/interface/assert.js
+++ b/lib/chai/interface/assert.js
@@ -1940,8 +1940,8 @@ module.exports = function (chai, util) {
    * If `errMsgMatcher` is provided, it also asserts that the error thrown will have a
    * message matching `errMsgMatcher`.
    *
-   *     assert.throws(fn, 'function throws a reference error');
-   *     assert.throws(fn, /function throws a reference error/);
+   *     assert.throws(fn, 'Error thrown must have this msg');
+   *     assert.throws(fn, /Error thrown must have a msg that matches this/);
    *     assert.throws(fn, ReferenceError);
    *     assert.throws(fn, errorInstance);
    *     assert.throws(fn, ReferenceError, 'Error thrown must be a ReferenceError and have this msg');
diff --git a/lib/chai/utils/proxify.js b/lib/chai/utils/proxify.js
index 51e0e63..4bbbee3 100644
--- a/lib/chai/utils/proxify.js
+++ b/lib/chai/utils/proxify.js
@@ -49,19 +49,31 @@ module.exports = function proxify(obj, nonChainableMethodName) {
             nonChainableMethodName + '".');
         }
 
-        var orderedProperties = getProperties(target).filter(function(property) {
-          return !Object.prototype.hasOwnProperty(property) &&
-            builtins.indexOf(property) === -1;
-        }).sort(function(a, b) {
-          return stringDistance(property, a) - stringDistance(property, b);
+        // If the property is reasonably close to an existing Chai property,
+        // suggest that property to the user. Only suggest properties with a
+        // distance less than 4.
+        var suggestion = null;
+        var suggestionDistance = 4;
+        getProperties(target).forEach(function(prop) {
+          if (
+            !Object.prototype.hasOwnProperty(prop) &&
+            builtins.indexOf(prop) === -1
+          ) {
+            var dist = stringDistanceCapped(
+              property,
+              prop,
+              suggestionDistance
+            );
+            if (dist < suggestionDistance) {
+              suggestion = prop;
+              suggestionDistance = dist;
+            }
+          }
         });
 
-        if (orderedProperties.length &&
-            stringDistance(orderedProperties[0], property) < 4) {
-          // If the property is reasonably close to an existing Chai property,
-          // suggest that property to the user.
+        if (suggestion !== null) {
           throw Error('Invalid Chai property: ' + property +
-            '. Did you mean "' + orderedProperties[0] + '"?');
+            '. Did you mean "' + suggestion + '"?');
         } else {
           throw Error('Invalid Chai property: ' + property);
         }
@@ -89,36 +101,44 @@ module.exports = function proxify(obj, nonChainableMethodName) {
 };
 
 /**
- * # stringDistance(strA, strB)
- * Return the Levenshtein distance between two strings.
+ * # stringDistanceCapped(strA, strB, cap)
+ * Return the Levenshtein distance between two strings, but no more than cap.
  * @param {string} strA
  * @param {string} strB
- * @return {number} the string distance between strA and strB
+ * @param {number} number
+ * @return {number} min(string distance between strA and strB, cap)
  * @api private
  */
 
-function stringDistance(strA, strB, memo) {
-  if (!memo) {
-    // `memo` is a two-dimensional array containing a cache of distances
-    // memo[i][j] is the distance between strA.slice(0, i) and
-    // strB.slice(0, j).
-    memo = [];
-    for (var i = 0; i <= strA.length; i++) {
-      memo[i] = [];
-    }
+function stringDistanceCapped(strA, strB, cap) {
+  if (Math.abs(strA.length - strB.length) >= cap) {
+    return cap;
   }
 
-  if (!memo[strA.length] || !memo[strA.length][strB.length]) {
-    if (strA.length === 0 || strB.length === 0) {
-      memo[strA.length][strB.length] = Math.max(strA.length, strB.length);
-    } else {
-      var sliceA = strA.slice(0, -1);
-      var sliceB = strB.slice(0, -1);
-      memo[strA.length][strB.length] = Math.min(
-        stringDistance(sliceA, strB, memo) + 1,
-        stringDistance(strA, sliceB, memo) + 1,
-        stringDistance(sliceA, sliceB, memo) +
-          (strA.slice(-1) === strB.slice(-1) ? 0 : 1)
+  var memo = [];
+  // `memo` is a two-dimensional array containing distances.
+  // memo[i][j] is the distance between strA.slice(0, i) and
+  // strB.slice(0, j).
+  for (var i = 0; i <= strA.length; i++) {
+    memo[i] = Array(strB.length + 1).fill(0);
+    memo[i][0] = i;
+  }
+  for (var j = 0; j < strB.length; j++) {
+    memo[0][j] = j;
+  }
+
+  for (var i = 1; i <= strA.length; i++) {
+    var ch = strA.charCodeAt(i - 1);
+    for (var j = 1; j <= strB.length; j++) {
+      if (Math.abs(i - j) >= cap) {
+        memo[i][j] = cap;
+        continue;
+      }
+      memo[i][j] = Math.min(
+        memo[i - 1][j] + 1,
+        memo[i][j - 1] + 1,
+        memo[i - 1][j - 1] +
+          (ch === strB.charCodeAt(j - 1) ? 0 : 1)
       );
     }
   }


Test patch:
diff --git a/test/configuration.js b/test/configuration.js
index 1f929d1..7127314 100644
--- a/test/configuration.js
+++ b/test/configuration.js
@@ -788,8 +788,8 @@ describe('configuration', function () {
       }
     };
 
-    it('should have default value equal to `[\'then\', \'inspect\', \'toJSON\']`', function() {
-      expect(chai.config.proxyExcludedKeys).to.be.deep.equal(['then', 'inspect', 'toJSON']);
+    it('should have default value equal to `[\'then\', \'catch\', \'inspect\', \'toJSON\']`', function() {
+      expect(chai.config.proxyExcludedKeys).to.be.deep.equal(['then', 'catch', 'inspect', 'toJSON']);
     });
 
     it('should not throw when accessing non-existing `then` and `inspect` in an environment with proxy support', function() {