Repository: peggyjs/peggy
Pull request #606 (2025-04-23 22:17:22)

Unreachable code now causes a warning.
Adds a "semantic" pass to the compiler, right before code generation, for rules that need to rely on
node.match being in place, and depend on all
other transformations having already run.

Most of a fix for #576, without full static analysis.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index f382e10..dcae5cf 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -87,6 +87,15 @@ Released: TBD (Not before 2025-05-01)
   using a plugin, this may be somewhat challenging for the plugin author.
   Please file an issue on Peggy for help.
   [#602](https://github.com/peggyjs/peggy/pull/602)
+- A new "semantic" pass has been added to the compiler, which occurs after all
+  transformations, but before code generation.  Plugins in this pass can rely
+  on annotations from previous passes to reason about the code.
+  [#606](https://github.com/peggyjs/peggy/pull/606)
+- Unreachable code in rules like `'b'* / 'c'`, `![]`, `&[]`, `!('f'*)`, and
+  `&('f'*)` now cause a semantic warning.  This warning may be escalated to an
+  error in a future release, once experience in the field has shown that the
+  approach does not catch code that is valid.
+  [#606](https://github.com/peggyjs/peggy/pull/606)
 
 ### Bug fixes
 
diff --git a/lib/compiler/index.js b/lib/compiler/index.js
index 6eb5ee1..b28c355 100644
--- a/lib/compiler/index.js
+++ b/lib/compiler/index.js
@@ -15,6 +15,7 @@ const reportInfiniteRecursion = require("./passes/report-infinite-recursion");
 const reportInfiniteRepetition = require("./passes/report-infinite-repetition");
 const reportUndefinedRules = require("./passes/report-undefined-rules");
 const reportIncorrectPlucking = require("./passes/report-incorrect-plucking");
+const reportUnreachable = require("./passes/report-unreachable");
 const Session = require("./session");
 const visitor = require("./visitor");
 const { base64 } = require("./utils");
@@ -72,6 +73,9 @@ const compiler = {
       removeUnusedRules,
       inferenceMatchResult,
     ],
+    semantic: [
+      reportUnreachable, // Not a transform, but has to be after inferenceMatchResult
+    ],
     generate: [
       generateBytecode,
       generateJS,
diff --git a/lib/compiler/passes/report-unreachable.js b/lib/compiler/passes/report-unreachable.js
new file mode 100644
index 0000000..6f2cd62
--- /dev/null
+++ b/lib/compiler/passes/report-unreachable.js
@@ -0,0 +1,63 @@
+// @ts-check
+"use strict";
+
+const visitor = require("../visitor");
+const { ALWAYS_MATCH, NEVER_MATCH } = require("./inference-match-result");
+
+/** @type {PEG.Pass} */
+function reportUnreachable(ast, options, session) {
+  const visit = visitor.build({
+    /**
+     * @param {PEG.ast.Choice} node
+     */
+    choice(node) {
+      node.alternatives.forEach(a => visit(a));
+      for (let i = 0; i < node.alternatives.length - 1; i++) {
+        const alt = node.alternatives[i];
+        if (alt.match === ALWAYS_MATCH) {
+          session.warning(
+            "Always matches.  Following alternatives may not be reachable.",
+            alt.location
+          );
+        }
+      }
+    },
+    /**
+     * @param {PEG.ast.Prefixed} node
+     */
+    simple_and(node) {
+      visit(node.expression);
+      if (node.expression.match === ALWAYS_MATCH) {
+        session.warning(
+          "Always matches, making the & predicate redundant.",
+          node.expression.location
+        );
+      } else if (node.expression.match === NEVER_MATCH) {
+        session.warning(
+          "Never matches, making the & predicate always fail.",
+          node.expression.location
+        );
+      }
+    },
+    /**
+     * @param {PEG.ast.Prefixed} node
+     */
+    simple_not(node) {
+      visit(node.expression);
+      if (node.expression.match === ALWAYS_MATCH) {
+        session.warning(
+          "Always matches, making the ! predicate always fail.",
+          node.expression.location
+        );
+      } else if (node.expression.match === NEVER_MATCH) {
+        session.warning(
+          "Never matches, making the ! predicate redundant.",
+          node.expression.location
+        );
+      }
+    },
+  });
+  visit(ast);
+}
+
+module.exports = reportUnreachable;


Test patch:
diff --git a/test/unit/compiler.spec.js b/test/unit/compiler.spec.js
index 9483985..f1c001a 100644
--- a/test/unit/compiler.spec.js
+++ b/test/unit/compiler.spec.js
@@ -86,7 +86,11 @@ describe("Peggy compiler", () => {
     // This is here, in the wrong place, because it needs both
     // inference-match-result and generate-bytecode to be in the plugin chain.
     const ast = parser.parse("start = 'a'? / 'b'");
-    compiler.compile(ast, compiler.passes, { output: "ast" });
+    const warnings = [];
+    compiler.compile(ast, compiler.passes, {
+      output: "ast",
+      warning(...args) { warnings.push(args); },
+    });
 
     // Note there is no attempt to match string 1 ('b') here.
     expect(ast.rules[0].bytecode).to.eql([
@@ -97,5 +101,101 @@ describe("Peggy compiler", () => {
       6,            //   POP
       2,            //   PUSH_NULL
     ]);
+
+    expect(warnings).to.eql([
+      [
+        "semantic",
+        "Always matches.  Following alternatives may not be reachable.",
+        {
+          "start": { "column": 9, "line": 1, "offset": 8 },
+          "end": { "column": 13, "line": 1, "offset": 12 },
+          "source": undefined,
+        },
+      ],
+    ]);
+  });
+
+  it("detects unreachable code", () => {
+    const ast = parser.parse("start = &('f'*) &[] !('f'*) ![] 'b'");
+    const warnings = [];
+    compiler.compile(ast, compiler.passes, {
+      output: "ast",
+      warning(...args) { warnings.push(args); },
+    });
+    expect(warnings).to.eql([
+      [
+        "semantic",
+        "Always matches, making the & predicate redundant.",
+        {
+          "start": { "column": 11, "line": 1, "offset": 10 },
+          "end": { "column": 15, "line": 1, "offset": 14 },
+          "source": undefined,
+        },
+      ],
+      [
+        "semantic",
+        "Never matches, making the & predicate always fail.",
+        {
+          "start": { "column": 18, "line": 1, "offset": 17 },
+          "end": { "column": 20, "line": 1, "offset": 19 },
+          "source": undefined,
+        },
+      ],
+      [
+        "semantic",
+        "Always matches, making the ! predicate always fail.",
+        {
+          "start": { "column": 23, "line": 1, "offset": 22 },
+          "end": { "column": 27, "line": 1, "offset": 26 },
+          "source": undefined,
+        },
+      ],
+      [
+        "semantic",
+        "Never matches, making the ! predicate redundant.",
+        {
+          "start": { "column": 30, "line": 1, "offset": 29 },
+          "end": { "column": 32, "line": 1, "offset": 31 },
+          "source": undefined,
+        },
+      ],
+    ]);
+  });
+
+  it("detects deeper unreachable code", () => {
+    const ast = parser.parse("start = &('a'? / 'b') !('a'? / 'b') &('a'? / 'b')");
+    const warnings = [];
+    compiler.compile(ast, compiler.passes, {
+      output: "ast",
+      warning(...args) { warnings.push(args); },
+    });
+    expect(warnings).to.eql([
+      [
+        "semantic",
+        "Always matches.  Following alternatives may not be reachable.",
+        {
+          "start": { "column": 11, "line": 1, "offset": 10 },
+          "end": { "column": 15, "line": 1, "offset": 14 },
+          "source": undefined,
+        },
+      ],
+      [
+        "semantic",
+        "Always matches.  Following alternatives may not be reachable.",
+        {
+          "start": { "column": 25, "line": 1, "offset": 24 },
+          "end": { "column": 29, "line": 1, "offset": 28 },
+          "source": undefined,
+        },
+      ], [
+        "semantic",
+        "Always matches.  Following alternatives may not be reachable.",
+        {
+          "start": { "column": 39, "line": 1, "offset": 38 },
+          "end": { "column": 43, "line": 1, "offset": 42 },
+          "source": undefined,
+        },
+      ],
+    ]);
   });
 });