Pattern labeling creates unnecessary nested contexts

(originally posted by @gibson042 in https://github.com/endojs/endo/issues/1795#issuecomment-1756093032)

Have we considered instead creating a call-specific stack of labels at the matches/mustMatch entry points and passing it down such that there are no redundant calls to checkMatches or even nested try..catch contexts?

   const mustMatch = (specimen, patt, label = undefined) => {
-    let innerError;
+    const labels = label === undefined ? [] : [label];
+    const labelCount = labels.length;
     try {
-      if (checkMatches(specimen, patt, identChecker, undefined)) {
-        return;
-      }
+      const result = checkMatches(specimen, patt, assertChecker, labels);
+      labels.length === labelCount && (labelCount === 0 || labels[0] === label) ||
+        Fail`internal: unexpected final label stack ${labels}`;
+      return result;
     } catch (er) {
-      innerError = er;
+      // const wrapError = (err, labels) => {
+      //   let lastMessage = err.message;
+      //   for (let i = labels.length - 1; i >= 0; i -= 1) {
+      //     const label = labels[i];
+      //     // cf. `bestEffortStringify`
+      //     const message = typeof label === 'number' || typeof label === 'string' && label[0] === '['
+      //       ? `[${label}]: ${lastMessage}`
+      //       : `${label}: ${lastMessage}`;
+      //     const outerErr = assert.error(message);
+      //     assert.note(outerErr, X`Caused by ${err}`);
+      //     err = outerErr;
+      //     lastMessage = message;
+      //   }
+      //   return err;
+      // };
+      throw wrapError(er, labels);
     }
-    // should only throw
-    checkMatches(specimen, patt, assertChecker, label);
-    const outerError = assert.error(
-      X`internal: ${label}: inconsistent pattern match: ${q(patt)}`,
-    );
-    if (innerError !== undefined) {
-      assert.note(outerError, X`caused by ${innerError}`);
-    }
-    throw outerError;
   };

Update checkMatches to extend/contract a shared stack of labels rather than being called with new labels in nested try..catch contexts

```diff /** * @param {Passable} specimen - * @param {Pattern} pattern + * @param {Pattern} patt * @param {Checker} check - * @param {string|number} [label] + * @param {Array} labels * @returns {boolean} */ - const checkMatches = (specimen, pattern, check, label = undefined) => + const checkMatches = (specimen, patt, check, labels) => - // eslint-disable-next-line no-use-before-define - applyLabelingError(checkMatchesInternal, [specimen, pattern, check], label); - - /** - * @param {Passable} specimen - * @param {Pattern} patt - * @param {Checker} check - * @returns {boolean} - */ - const checkMatchesInternal = (specimen, patt, check) => { // Worth being a bit verbose and repetitive in order to optimize const patternKind = kindOf(patt, check); const specimenKind = kindOf(specimen); // may be undefined switch (patternKind) { case undefined: { return Fail`pattern expected: ${patt}`; } case 'promise': { return Fail`promises cannot be patterns: ${patt}`; } case 'error': { return Fail`errors cannot be patterns: ${patt}`; } case 'undefined': case 'null': case 'boolean': case 'number': case 'bigint': case 'string': case 'symbol': case 'copySet': case 'copyBag': case 'remotable': { // These kinds are necessarily keys - return checkAsKeyPatt(specimen, patt, check); + return checkAsKeyPatt(specimen, patt, check, labels); } case 'copyArray': { if (isKey(patt)) { // Takes care of patterns which are keys, so the rest of this // logic can assume patterns that are not keys. - return checkAsKeyPatt(specimen, patt, check); + return checkAsKeyPatt(specimen, patt, check, labels); } if (specimenKind !== 'copyArray') { return check( false, X`${specimen} - Must be a copyArray to match a copyArray pattern: ${q( patt, )}`, ); } const { length } = patt; if (specimen.length !== length) { return check( false, X`Array ${specimen} - Must be as long as copyArray pattern: ${q( patt, )}`, ); } - return patt.every((p, i) => checkMatches(specimen[i], p, check, i)); + return patt.every((p, i) => { + labels.push(i); + const result = checkMatches(specimen[i], p, check, labels); + labels.pop(); + return result; + }); } - … + … default: { const matchHelper = maybeMatchHelper(patternKind); - if (matchHelper) { - return matchHelper.checkMatches(specimen, patt.payload, check); - } - throw Fail`internal: should have recognized ${q(patternKind)} `; + if (!matchHelper) { + throw Fail`internal: should have recognized ${q(patternKind)}`; + } + return matchHelper.checkMatches(specimen, patt.payload, check, labels); } } }; ```

stack frame comparison

```js mustMatch( harden({arr: ["foo", ["bar", "BAR"], ["qux", "quux"]]}), harden({arr: ["foo", ["bar", "BAR"], [M.string(), "qux"]]}), ); ``` ```diff --- before +++ after @@ -1,14 +1,6 @@ (Error#1) Error#1: arr: [2]: [1]: (a string) - Must be: (a string) - at throwLabeled (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at mustMatch (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/[eval1] @@ -16,19 +8,6 @@ Error#1 ERROR_NOTE: Caused by (Error#2) Nested error under Error#1 Error#2: [2]: [1]: (a string) - Must be: (a string) - at throwLabeled (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at mustMatch (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/[eval1] @@ -36,24 +15,6 @@ Nested error under Error#1 Nested error under Error#2 Error#3: [1]: (a string) - Must be: (a string) - at throwLabeled (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js - at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) - at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at mustMatch (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/[eval1] @@ -61,25 +22,15 @@ Nested error under Error#1 Nested error under Error#3 Error#4: quux - Must be: qux at assertChecker (file:///home/rgibson/HD.VAULT/Projects/endo/packages/pass-style/src/passStyle-helpers.js) at checkAsKeyPatt (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js at Array.every () - at checkMatchesInternal (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) - at applyLabelingError (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/utils.js) at checkMatches (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at mustMatch (file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/src/patterns/patternMatchers.js) at file:///home/rgibson/HD.VAULT/Projects/endo/packages/patterns/[eval1] ```

The improvement appears to be small but real.

esbench -n 100 --repetitions 20 --tmp --eshost-option '-h V8,*XS*' \
  --init-file <(printf '
    import "@endo/init";
    import { M, matches, mustMatch } from "@endo/patterns";
    Object.assign(globalThis, { M, matches, mustMatch });
  ' | npx rollup -p @rollup/plugin-node-resolve -f iife) \
  '
    const { M, matches, mustMatch } = globalThis;
    const patt = harden({arr: ["foo", ["bar", "BAR"], [M.string(), "qux"]]});
  ' '{
    "pass": `result = matches(harden({arr: ["foo", ["bar", "BAR"], ["qux", "qux"]]}), patt);`,
    "fail": `result = matches(harden({arr: ["foo", ["bar", "BAR"], ["qux", "quux"]]}), patt);`,
  }'

Before:

#### Moddable XS
pass: 0.13 ops/ms
fail: 0.13 ops/ms

#### V8
console.warn: Removing intrinsics.Promise.withResolvers
pass: 0.95 ops/ms
fail: 1.05 ops/ms

After:

#### Moddable XS
pass: 0.15 ops/ms
fail: 0.15 ops/ms

#### V8
console.warn: Removing intrinsics.Promise.withResolvers
pass: 1.02 ops/ms
fail: 1.08 ops/ms

endojs / endo

Pattern labeling creates unnecessary nested contexts #1848