Skip to content

Decide how far to take regex-satisfiability analysis in the exception bridgeΒ #2910

Description

@devantler

πŸ€– Generated by the Agentic Engineer

Evidence

The Kubescape backlog bridge (#2876) needs to know whether an exception's regex pattern can match
anything at all β€” an always-unmatchable pattern is a silently dead exception. That check is currently
a hand-written walk over regexp/syntax, and it has been the single largest source of review churn on
that branch: 14 review rounds, 9 of the 13 completed ones found a defect in the round immediately
before
, and the last three rounds were all this one class β€” an empty expression, an impossible
character class, an unmatchable concatenation element, a positional contradiction. Three of the
defects were introduced while fixing the previous round.

Regular-language emptiness is decidable, but not by an ad-hoc structural walk, and Go exposes no
oracle for it. There is no evidence the well is dry: a fifth hole is expected.

The problem, and who has it

Whoever operates the exception artifact. A pattern that cannot match is a rule that looks active and
does nothing β€” the same "broken and compliant read identically" failure mode the bridge exists to
prevent, one level up.

What the measurement says about priority

Against the real 21-policy artifact: 318 patterns, 0 interior anchors, 0 empty-only.

Case Reachable from the generator?
^$ from an empty CR value yes β€” anchor() wraps the raw value
Impossible character class no
Unmatchable concatenation element no
Positional contradiction no β€” anchor() runs QuoteMeta, so no interior anchor can be emitted

So the one generator-reachable case is already covered on #2876. Every remaining case requires
someone to hand-edit generated output. The artifact is operator-supplied, so that is real but
lower-tier risk β€” which is exactly why this is worth deciding rather than grinding.

Why a Spike

The honest options include "do not build a complete oracle". Possible outcomes:

  1. Accept the current partial check plus a documented boundary on what it does not decide.
  2. Replace the structural walk with a decision procedure over a proper automaton construction.
  3. Constrain the input instead β€” validate/normalise operator-supplied patterns so unmatchable
    shapes cannot enter, making the analysis unnecessary.

Acceptance criteria

  • A recorded decision on this issue: evidence β†’ options β†’ chosen path β†’ why.
  • Follow-up issues filed for whatever the decision implies (or an explicit "no further work" with
    the reasoning).
  • If option 1: the documented boundary lands, stating precisely which unmatchable shapes are not
    detected.

Size: timeboxed investigation. Do not open a delivery PR for this issue β€” a Spike's
definition-of-done is the decision plus follow-ups.

Split out of #2876 so that branch can merge on its independently-valuable work.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    Projects

    Status
    πŸ“₯ Backlog

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions