Crate sheng 

sheng — register-resident refutation sieves for regex.

A sieve answers one question, in one direction: can this document be proven to hold no match? When the answer is yes it is conclusive and the document never needs to be scanned. When the answer is no it means nothing at all, and a real engine has to run. Nothing here ever reports a match, or a position, or a capture — the asymmetry is the design, not a limitation of it.

let sieve = sheng::Sieve::new(r"(?-u)WalletService")?;
for doc in std::iter::empty::<&[u8]>() {
    if sieve.refutes(doc) {
        continue; // proven match-free; no engine runs
    }
    // ... hand `doc` to a real matcher ...
}

Why it is sound

Sieve::new builds regex-automata’s own dense::DFA, projects it onto its reachable core (projection), and climbs the lattice of substitution-property partitions past the point where language is preserved (lattice) — a partition closed under the transition function (p ≡ q ⟹ δ(p,b) ≡ δ(q,b) for every byte), per Hartmanis & Stearns, Algebraic Structure Theory of Sequential Machines (Prentice-Hall, 1966), ch. 2. A closed partition induces a quotient automaton; marking a block accepting whenever any member state accepts makes that quotient recognize a superset of the pattern’s language. A superset that rejects therefore proves the original rejects. The quotient’s own arithmetic is re-derived and re-checked before it is trusted, so a partition that is not actually closed is discarded rather than shipped.

Why it is fast

A quotient is capped at 16 blocks, which is one SIMD register, so the transition step is a single byte shuffle with no gather and the accept test is a running max (shuffle). That kernel is Langdale’s Sheng (2018, shipped in Hyperscan; see https://branchfree.org/2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/), pointed at an over-approximating quotient rather than at the real automaton — which is what lets a machine that must fit in a register front a pattern far too large to fit in one.

Prior art

The contract — over-approximate, reject early, verify survivors exactly — is not novel. Luchaup, De Carli, Jha & Bach’s DFA-trees (INFOCOM 2014, doi:10.1109/INFOCOM.2014.6847977) is the same idea, and their paper calls its shrunk DFAs “a special case of quotient automaton”; Češka et al. (arXiv:1904.10786) cascade crude over-approximating NFAs chosen by a traffic model; Hyperscan’s HS_FLAG_PREFILTER has shipped the superset-plus-confirmation contract for years. What is narrow here is the SP-lattice harvest as the source of the approximation, the register-resident conjunction selection, and the training-free gate below. Notably, DFA-trees also measured +26% in the case where nothing is rejected — the hazard that gate exists to refuse.

Why it sometimes refuses

Most patterns get no sieve, and that is the intended behavior. A sieve arms only when the lattice yields a partition small enough to hold in a register, coarse enough to be a real abstraction, and cheaper than the engine it would front (price). That last test is a comparison of two measured per-byte costs, not a threshold on selectivity — because the decisive question is often not how much the filter rejects but how little the rival costs. When regex-automata can memchr its way through a document, nothing that inspects every byte can front it profitably, however selective. Such a pattern gets BuildError::NotWorthIt carrying the arithmetic instead of a slow sieve.

Selectivity itself is predicted from the quotient’s own Markov chain with no calibration haystack (selectivity), under a first-order model of byte-class persistence (prior) — because an independent-draw model prices a k-byte run as p^k and is wrong by orders of magnitude on real text.

What is measured, and where measurements stop applying

Everything above is arithmetic and instructions; it holds on any machine. The decision rests on two empirical facts that are nobody’s constants — how fast a machine runs three loops, and what the bytes being searched look like — and Policy is the single place both live.

Absolute speed is provably irrelevant: scaling every coefficient of a price::Calibration by any positive factor leaves every decision unchanged, so clock, load and thermal state cancel. What does not cancel is three dimensionless ratios, and those turn out to differ about twofold between arm64 and x86_64 — in opposite directions — so price::MINTED keeps one row per (architecture, kernel) pair that has actually been measured, and a machine absent from it gets BuildError::Uncalibrated rather than another machine’s optimism. The shipped prior describes a polyglot source tree; a caller whose corpus is prose, logs or DNA mints their own and passes it in.

Modules

price

What each kernel costs, and the one inequality that decides whether a sieve arms.

prior

What a byte is likely to be, given the byte before it.

shuffle

The register-resident kernel: one shuffle per byte, no gather, no branch.

Structs

Policy

Every empirical fact the arming decision rests on, in one replaceable place.

Projection

A dense::DFA projected onto its reachable core: compact state ids, one transition table over derived byte classes, and the accept set.

Quotient

A ≤16-state quotient, byte-expanded into exactly the form the shuffle kernel consumes: rows[b] is the 16-lane transition row for byte b, indexed by the current block.

Sieve

A conjunction of over-approximating quotients, run as one refutation pass.

Skip

How to find the next byte that leaves a block, and which block that is.

Enums

BuildError

Why a pattern got no sieve. None of these are failures of the caller’s pattern — they mean a per-byte filter would not have paid, or could not have been proven sound, so the caller should simply run its matcher unfiltered.

Decline

Why a pattern gets no sieve. Every variant is a precondition of soundness or of the cost model — never a taste call — and each is checked against the finished automaton rather than inferred from the pattern’s syntax.

Gate

Whether to enforce the worth test.

Instrument

Which searcher a skip runs, and therefore what its excursions cost.

Constants

MAX_CONJUNCTS

How many quotients may be conjoined. Two independent shuffle chains issue in parallel and their per-position conjunction costs a handful of throughput ops, so the second is nearly free; a third adds a register chain to a filter that is already at its selectivity floor.

Functions

harvest

Harvest the lattice and return the chosen conjunction, most selective first. An empty result means no closed partition small enough to hold in a register carried any discriminating power.

worst_case

The pessimistic fallthrough rate over every chain in chains — what the gate decides on. A conjunction is scored on its best member, because a document only has to be refuted once.