view release on metacpan or  search on metacpan

docs/Architecture.md  view on Meta::CPAN

# 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.

docs/Architecture.md  view on Meta::CPAN

- **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.

## Fingerprinting for snippet provenance

The pattern engine answers "which known licenses does this file contain". A closely related question is
"which known open source code does this snippet resemble", used by 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 distribution provides the *primitives* for that question. The searchable index that turns
fingerprints back into packages and paths lives in the consuming application - Cavil keeps it in Postgres -
not here.

Two calls make up the surface. `content_hash` returns the 128-bit hash of a file's raw bytes as 32 hex
characters, produced by the same frozen hasher the pattern side uses, so identical content always yields
the same key and the database can join on it. `fingerprint_file` winnows a file into a set of fingerprints,
each carrying the exact line range it covers so a match can be highlighted.

Winnowing is the idea plagiarism detectors have used for decades. 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 where it sits in a file or how
it was 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 count landing near two divided by the
window-plus-one, times the number of runs.

Everything downstream is the consumer's: storing the fingerprints, looking a query's fingerprints up,
ranking candidates by containment, pruning boilerplate, and resolving a content hash back to packages and
paths. Cavil does all of that in the database. Keeping only the primitives here means the expensive,
corpus-sized index is owned where it is queried, and this distribution stays a deterministic fingerprint
source with nothing on disk of its own to maintain.

## 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.