Cavil::Matcher Architecture

This document explains how the matcher works and, more importantly, why it is built the way it is. It is meant to be read start to finish by someone new to the project, before they open the source. It talks about concepts, not functions or line numbers.

Why this exists

Cavil reviews the licensing of software by scanning source code for the text of known licenses. The scanning is done by matching every file against a large, ever-growing collection of patterns - normalized fragments of license text. The previous engine did this well and fast, and this one keeps its core idea unchanged. What it changes is everything around that core, because the old design had three operational problems that grow worse over time:

• Every change rebuilt the world. Adding or editing a single pattern threw away the entire compiled collection, and the next scan had to recompile all of it from scratch. Patterns are added every day, so this cost was paid constantly.
• Every worker kept its own copy. Cavil scans in parallel with many worker processes, and each one loaded its own full copy of the compiled patterns into private memory. The more patterns, the more this multiplied.
• The on-disk form was fragile. The compiled file had no header, version, or checksum; it was trusted blindly. A format change or a truncated file could be silently misread.

The goal of this engine is to fix those three things - cheap incremental updates, one shared copy per machine, and a safe, versioned on-disk format - while keeping matching itself bit-for-bit identical, so switching to it requires no re-processing of existing data.

The Perl/native split, and why

Only one thing in a license scan is genuinely performance-critical: walking every word of every file through the pattern collection. That inner loop, and the hashing that feeds it, is where nearly all the time goes, and it is written in a small, carefully-frozen C++ core.

Everything else - deciding which patterns are active, recording that a pattern was removed, choosing when to compact, reading and writing the little file that describes the collection - happens rarely and on small data. All of that is plain Perl, because that is where the team is strongest, because it is where a newcomer can follow the logic without a debugger, and because none of it is on the hot path, so nothing is lost by keeping it in Perl. The native side is deliberately dumb: it is handed a list of things to search and simply searches them. Every decision is made in Perl.

The native core is C++ rather than a rewrite in another language for a simple reason: the matching algorithm and its hashing are already proven on a legal tool, where a subtle behavioural change is the worst kind of bug. Reusing that code unchanged is the safest possible choice, so the core stays in the language it is already written in. The genuinely new native code - the reader for the on-disk format - is small and only ever reads files this same software wrote, and it validates everything it reads, which removes the one real weakness the old format had.

How matching works

A pattern is neither a regular expression nor a literal string. Before anything is compared, both the patterns and the files being scanned are put through the same normalization: text is lower-cased and split into words, punctuation and common comment or markup noise is discarded, and each surviving word is reduced to a number. Only those numbers are ever compared. This is what lets a match survive reformatting, rewrapping, and different comment styles - the layout simply disappears during normalization.

One wildcard exists. A pattern may say "skip one to N words here" (at least one word, at most N - it does not match a zero-word gap), which lets a single pattern absorb the parts of a license that legitimately vary, such as a copyright holder or a year. A pattern must begin and end on real words, never on a skip, so that every match is anchored at both ends.

All of a collection's patterns are arranged into a shared prefix tree keyed on those word-numbers. Patterns that start with the same words share the same branch and only diverge where the words diverge. Scanning a file means walking its words down this tree and noting wherever a complete pattern is reached. The important consequence is that scanning speed barely depends on how many patterns there are: shared beginnings are walked once, and only branches that actually occur in the file are ever explored.

When several patterns match overlapping parts of a file, the longest match wins; an exact tie is resolved in favour of the higher pattern identifier, on the assumption that newer patterns are the more specific ones. This "higher id means newer" rule holds because identifiers are assigned monotonically as patterns are created (Cavil uses a database sequence), which is a required invariant of any caller: the resolver only ever sees identifiers, not creation timestamps or segment order, so if identifiers were reused or assigned non-monotonically the tie-break would no longer prefer the genuinely newer pattern. This resolution is a pure function of the set of raw matches, which is what makes the segmented design below safe: it does not matter how the raw matches were gathered, only what they are.

Segments, tombstones, and the manifest

Instead of one monolithic compiled file, a collection is stored as a set of segments. A segment is a compiled prefix tree for one batch of patterns, and once written it is never modified. Alongside the segments lives a small, human-readable manifest: it lists the active segments, the pattern identifiers that have been removed (tombstones), and a generation number that increases on every change.

This is the whole point of the design, and it follows the model search engines have used for decades:

• Adding patterns compiles one small new segment and appends it to the manifest. The existing segments are not touched. Absorbing a new pattern is therefore cheap and local, no matter how large the collection has grown.
• Removing a pattern writes a tombstone in the manifest and nothing else. At scan time, matches belonging to a tombstoned pattern are dropped before overlap resolution - so removing a pattern correctly reveals any smaller matches it had been hiding, exactly as if it had never existed. No segment is recompiled.
• A query searches all active segments at once, gathers their matches, discards the tombstoned ones, and then applies the ordinary overlap resolution to the combined set. The result is identical to what a single combined collection would have produced.

Because deltas and tombstones accumulate, an occasional compaction folds the current pattern set back into a single fresh base segment and clears the tombstones. This is the one operation that reads the full pattern set from the database - Cavil's source of truth - and it is rare and runs in the background, off the scanning path. It exists only to keep the number of segments and the length of the tombstone list bounded over time.

Shared memory and reproducibility

Segments are mapped into memory read-only and searched in place, rather than being read and rebuilt in each worker's private memory. When many workers on the same machine use the same collection, the operating system keeps a single physical copy of each segment and shares it across all of them. The practical effect is dramatic: attaching a large index to dozens of workers costs kilobytes of private memory per worker instead of a full duplicate each. This is what lifts the memory ceiling that limited the previous design.

The generation number in the manifest gives reproducibility. A scan pins the generation it ran against, and a report can record it, so re-running an old report can use exactly the same patterns it originally saw. Updates are published atomically - a new segment and an updated manifest are written to the side and swapped into place in one step - so a reader never observes a half-written collection.

The on-disk format

Each segment file begins with a header identifying it, stating its format version, and carrying a checksum of everything that follows. Opening a segment always validates its structure - the header fields, the size, and every internal reference - so a file that is truncated, of the wrong version, structurally impossible, or simply not a segment at all is rejected cleanly; it is never partially trusted and never able to send the scanner off the end of the data. This structural validation is cheap and always on, so memory safety never depends on the checksum.

The whole-payload checksum is a separate, corruption-detection concern, and it is deliberately not recomputed on the hot scan path. A segment is Cavil's own derived cache: it is checksummed when compiled, published atomically (written to the side and renamed into place), and thereafter immutable and regenerable from the database. Re-checksumming a multi-hundred-megabyte payload on every one of the thousands of indexing opens - where the mmap already shares one physical copy - is almost the entire cost of a load (measured at ~97%), and it guards against a corruption that atomic publishing already prevents. So the CRC is verified where it is meaningful: once when the segment is written, and on demand through the engine's verify entry point (an fsck for operators). The manifest additionally records a checksum for each segment for that on-demand check. This validated, versioned format is the deliberate replacement for the old engine's headerless, unchecked file.

Robustness

Scanning a whole distribution means feeding the matcher every kind of file that exists, including binaries, deliberately malformed samples that security tools ship as test data, files full of null bytes, and enormous single-line files with no structure at all. The matcher treats all of this as ordinary input: it reads files in bounded chunks, stops cleanly at the end of usable data, and bounds the amount of a file it holds in memory at once. Unreadable paths and missing files produce empty results rather than errors. The guiding rule is simple and absolute - no input, however hostile or malformed, may crash the scan.

The fingerprint index (snippet provenance)

The pattern engine answers "which known licenses does this file contain". A second, closely related question is "which known open source code does this snippet resemble", and it is what powers a service where someone submits a fragment (for example AI-generated code) and asks how much of it already exists in the open source Cavil has seen. This is a different lookup from license matching and it is kept deliberately separate, but it reuses almost everything above: the same frozen tokenizer and hashing, and the same on-disk discipline of a versioned, checksummed, structure-validated, memory-mapped segment published atomically.

The idea is the one plagiarism detectors have used for decades, called winnowing. A file's tokens are grouped into overlapping runs (k tokens each), every run is hashed, and a stable subset of those hashes is selected by taking the smallest hash in each sliding window of the runs. The selection is deterministic and shift-stable, so the same code always yields the same fingerprints no matter how it is chopped up while reading, and it survives reformatting and renaming because the layout has already disappeared during tokenization. The window width is the one knob: a wider window keeps fewer fingerprints (cheaper) and a narrower window keeps more (more robust), with the fingerprint count landing near two divided by the window-plus-one, times the number of runs.

Where a pattern segment is a prefix tree walked by a file, a fingerprint segment is simply a sorted array of 16-byte records, each a fingerprint value paired with a reference to the content it came from and the exact line range it covers. The content reference points into a small per-segment table of 128-bit content hashes, not file names: the content hash is the stable, deduplication-native key that the Cavil database maps to every path, package, version and piece of metadata. Keeping the record minimal and content-keyed is deliberate, because this is the huge, expensive-to-rebuild part of the system; anything richer that a future feature needs lives in the database keyed by that hash and never forces the index to be re-emitted. A query winnows the submitted snippet the same way and binary-searches each of its fingerprints into the array. The score reported for a candidate is containment: the fraction of the snippet's distinct fingerprints found in it (and, because each content also records its own fingerprint count, the reverse fraction too, so a caller can tell "your snippet is inside this file" from "this file is your snippet"). That is the same "match percentage" commercial tools show, and a risk indicator is built from it by weighting containment with the license risk Cavil already knows for the matched code, so that resembling copyleft code reads louder than resembling permissive code. The result is advisory and probabilistic, never an automated verdict.

Two properties matter for correctness. First, the index never collapses a fingerprint: every occurrence is a separate record, so a fingerprint present in fifty files returns all fifty. Nothing that was indexed becomes unfindable. Second, the index is content-addressed by a package version's checksum and lives under its own manifest and generation, completely independent of the pattern generation. Editing a license pattern and re-scanning a package changes its license conclusions but not its source bytes, so it must not touch the fingerprint index at all. A package version is fingerprinted once and reused on every later re-scan of that same version. The one-time full build is therefore the only time the whole corpus is fingerprinted; from then on the cost tracks churn, which is what makes a weekly full re-scan and constant pattern-driven re-scans cost the fingerprint index almost nothing.

The care point is document-frequency. Boilerplate that appears across genuinely unrelated code is noise and is worth pruning, but the same good function repeated across many versions of one package must not be mistaken for boilerplate and dropped. The obvious grouping, "count once per package", does not work here, because package names carry their version (rust1.23, go-1.23) and are not reliably parseable back to a project, and because every Cavil deployment uses its own naming scheme, so any name-based grouping would be an unportable guess. So identity is taken from content, not names: fingerprints are deduplicated and document frequency is counted per distinct file content (the checksum Cavil already computes). Fifty versions shipping a byte-identical file collapse to one stored copy and contribute one to document frequency, while a line that truly appears across thousands of unrelated file contents is still high-frequency and prunes. A matched fingerprint resolves through its content checksum back to every package, version and path that carries it, so nothing becomes unfindable and the version list is recovered from the database rather than guessed from a name. Verbatim vendored copies fall out of the same rule: one content, kept and detectable, not mistaken for noise.

Measured on a few hundred megabytes of real C, Python and JavaScript source, each fingerprint costs about sixteen bytes on disk (the sorted record alone; filenames map back through the database in production), the index holds roughly three fingerprints per kilobyte of source at the wide window, a snippet scores in well under a millisecond against a cached segment, and detection quality is essentially unchanged across window widths even though storage falls several-fold at the wide window. So the cheap large window is the right default, and the storage of a very large corpus is dominated by that sixteen-bytes-per-fingerprint record cost times the corpus size, before per-content document-frequency pruning trims the boilerplate tail.

Because each record already carries the exact matched line range, the same index also answers "which files contain code like this snippet, and where", so it doubles as a snippet code-search engine over the whole corpus, not just a provenance check. The point that keeps this cheap is that it needs no change to the index: results are ranked by containment straight from the records, and any richer convenience a consumer wants (filtering, expanding a match to every copy, language or license facets) is a lookup keyed by the content hash, never a wider record or a scan of the whole corpus.

What deliberately stays the same

Some things are intentionally unchanged from the previous engine, because they were already right:

• The database remains the source of truth for patterns. The compiled segments are a derived cache that can always be rebuilt from it.
• The prefix tree remains the authoritative matcher. Similarity scoring and closest-match are useful for suggestions, never for the authoritative yes/no of whether a license is present.
• The tokenizer and the hashing are frozen and produce exactly the same numbers as before. Because the stored checksums of patterns and text fragments depend on those numbers, keeping them identical means the new engine can replace the old one without recomputing or migrating any stored data.

Scaling characteristics and limits

The two costs that grew worst in the old design are gone: a change no longer recompiles the whole collection, and workers no longer each hold a private copy of it. Matching speed was already largely independent of the number of patterns, and remains so.

The new costs to watch are different and milder. Every active segment adds a little fixed overhead to each scan, so a collection that accumulates a great many un-compacted delta segments will slow down gradually; compaction is the remedy, and how often to run it is the main tuning knob. A single pathologically long pattern still widens the scanning window for every file, and patterns built from many skips still make the tree branch more, so the shape of new patterns is worth watching, not only their number.

How to work on it

The behaviour of the matcher is pinned by a self-contained test suite that needs no external engine: it asserts exact matches on a set of curated license fixtures, exercises the segment lifecycle (incremental add, tombstone, compaction, atomic update), checks that a damaged segment or manifest is handled gracefully, and throws a barrage of hostile inputs at the scanner to confirm it never crashes. That suite is the contract; if you change behaviour, it should tell you.

While this engine and its predecessor coexist, a separate developer-only set of tests cross-checks that the two produce byte-for-byte identical results across the whole real pattern corpus and a large sample of real snippets. Those tests are how equivalence is proven during the transition; once the old engine is retired they can simply be deleted, and the self-contained suite stands on its own.

A change to the pattern set flows through the system in the obvious way: adding patterns writes a new segment, removing one writes a tombstone, and compaction periodically rewrites a single clean base - none of which disturbs the data an in-flight scan is already using.