Cavil-Matcher

 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

docs/Architecture.md  view on Meta::CPAN

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

docs/Architecture.md  view on Meta::CPAN

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

src/SpookyV2.cpp  view on Meta::CPAN

// init spooky state
void SpookyHash::Init(uint64 seed1, uint64 seed2)
{
    m_length = 0;
    m_remainder = 0;
    m_state[0] = seed1;
    m_state[1] = seed2;
}

// add a message fragment to the state
void SpookyHash::Update(const void* message, size_t length)
{
    uint64 h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11;
    size_t newLength = length + m_remainder;
    uint8 remainder;
    union {
        const uint8* p8;
        uint64* p64;
        size_t i;
    } u;
    const uint64* end;

    // Is this message fragment too short?  If it is, stuff it away.
    if (newLength < sc_bufSize) {
        memcpy(&((uint8*)m_data)[m_remainder], message, length);
        m_length = length + m_length;
        m_remainder = (uint8)newLength;
        return;
    }

    // init the variables
    if (m_length < sc_bufSize) {
        h0 = h3 = h6 = h9 = m_state[0];

src/SpookyV2.cpp  view on Meta::CPAN

    m_state[4] = h4;
    m_state[5] = h5;
    m_state[6] = h6;
    m_state[7] = h7;
    m_state[8] = h8;
    m_state[9] = h9;
    m_state[10] = h10;
    m_state[11] = h11;
}

// report the hash for the concatenation of all message fragments so far
void SpookyHash::Final(uint64* hash1, uint64* hash2)
{
    // init the variables
    if (m_length < sc_bufSize) {
        *hash1 = m_state[0];
        *hash2 = m_state[1];
        Short(m_data, m_length, hash1, hash2);
        return;
    }

src/SpookyV2.h  view on Meta::CPAN

    // Init: initialize the context of a SpookyHash
    //
    void Init(
        uint64 seed1,       // any 64-bit value will do, including 0
        uint64 seed2);      // different seeds produce independent hashes
    
    //
    // Update: add a piece of a message to a SpookyHash state
    //
    void Update(
        const void *message,  // message fragment
        size_t length);       // length of message fragment in bytes


    //
    // Final: compute the hash for the current SpookyHash state
    //
    // This does not modify the state; you can keep updating it afterward
    //
    // The result is the same as if SpookyHash() had been called with
    // all the pieces concatenated into one message.
    //