Canonicalisation

crates/ligase-core/src/canon/ — one module per format, plus the digest they all build. No pyo3: deciding whether two files mean the same thing is correctness-critical logic, and it is tested in Rust.

The job: (DataKind, path) → ContentHash, over a byte stream that depends on what the file says and not on how it was written.

Why this exists at all

M3 keyed a step on its inputs’ bytes, and documented early cutoff as following from it: a step that reruns and writes the same bytes leaves every key below it alone. That is true, and on real tools it almost never happened.

minimap2 writes its whole command line into @PG CL. The command line includes the output path. The output path is .ligase/tmp/<key>.bam. So a step’s output bytes contain that step’s own key, and any change to the step — a parameter, a tool version, a comment — moved its bytes, which moved the key of the step below, whose bytes then moved in turn. The cascade ran to the bottom of the pipeline.

bcftools has the same shape with a timestamp added: ##bcftools_callCommand=call -mv ... -o /tmp/out.vcf.gz; Date=Sat Oct 17 21:14:12 2026.

M4 is therefore less “widen a strict test” than “make the cutoff M3 described actually hold”. The thread-count acceptance criterion in the milestones is one instance of it.

Where it attaches

Exactly where the cache said it would.

pub const INPUT_POLICY: &str = "canonical";   // was "raw"
pub const KEY_VERSION: u32 = 2;               // was 1

Ingredients did not change shape. Runner::key now asks Cache::semantic_hash(kind, path) where it asked Cache::content_hash, and the kind comes from the graph — the input node’s dataset — rather than from the step.

The store still names objects after their bytes. That is deliberate: an object’s name is a claim about its contents that anyone can check with b3sum. The canonical hash is a derived fact held beside it, not a replacement for it.

The digest

canon::Digest is the only thing that writes bytes into the hash, and it offers three ways to do it.

• field(label, value) — written immediately, in order. For anything whose position means something.
• record(parts) — hashed to 32 bytes now, collected, and sorted at the end. For anything whose position does not.
• ordered_record(parts) — hashed to 32 bytes the same way and then written straight in, where its position is fixed. For the one kind whose record order is its result.

The third exists as a method rather than as an argument to the second, and that is deliberate. record and ordered_record take the same arguments and mean opposite things, so a canonicaliser reaching for the wrong one would compile, pass its own tests for every property except the one that matters, and quietly turn a ranking into a set. Naming the choice at the call site is what makes that a visible mistake. It is the same reasoning as D41’s requirement that the module say in a comment why it does not sort: the hazard here is not a hard decision, it is an easy one made by habit.

Everything is length-prefixed, so a field x = yz cannot produce the same stream as xy = z. The domain, the rules’ version, the DataKind and whether this is a canonical form or a fallback all go in first, so no two of those can collide.

Records are sorted as digests, not as text: 32 bytes a record rather than a few hundred, which matters on a BAM with a hundred million of them. A sorted list of digests is still a commitment to the whole multiset — duplicates and absences included, which a commutative combination such as an XOR would lose.

Which formats sort

The split is not a new judgement. It is D14, which already decided that a sequence dictionary’s order is semantic (GATK insists on it) while a BED’s record order is incidental. A reference is a sequence dictionary, so it keeps its order; @SQ is one, so it keeps its order; records are not, so they sort.

Per-format notes

Alignment

Parsed by noodles, BAM and SAM through one code path over the sam::alignment::Record trait. That is what makes a BAM hash the same as the SAM it came from, which D9 requires: re-encoding is not a biological change, so samtools view -b must not cost a cache.

Each record contributes name, flags, reference id, position, mapping quality, CIGAR, mate reference and position, template length, sequence, qualities, and its tags.

Tags are kept, all of them, sorted by tag. They are results — NM, AS, ms are what the aligner concluded — and keeping an unknown tag is the conservative direction. What is normalised away is incidental: the order they were written in, and an integer’s storage width, so a SAM’s NM:i:3 and a BAM’s single byte are the same 3.

@RG keeps ID and SM and nothing else. The rest of a read group is metadata, and one of its standard tags is DT — a date.

Variants

noodles reads and validates the header. The records are then canonicalised as text: tab-split, validated (eight columns or more, a numeric POS), with QUAL quantised and the INFO and FILTER keys sorted.

The alternative was to rebuild each record from the typed accessors, and it was rejected. Doing so means choosing a rendering for every INFO value type, and a rendering that differs from the tool’s own is a fresh chance to call two identical results different. What is being compared here is two outputs of the same tool, and for that the tool’s own text is the most faithful record of what it concluded. What is normalised is only what is genuinely incidental — DP=10;AF=0.5 and AF=0.5;DP=10 are one set of annotations written two ways.

ALT is deliberately left in its order: a genotype’s 1 means the first alternate allele, so sorting them would renumber every call in the file. FORMAT and the sample columns are left alone for the same reason — they line up with each other positionally.

Header keys dropped: fileDate, fileDay, source, reference, bcftoolsVersion, and any key ending Command, CommandLine, Version or Date — which covers bcftools_callCommand, bcftools_viewVersion, GATKCommandLine and whatever the next tool calls its own.

##reference is worth stating separately: it holds a path, and the dimension catalogue is explicit that reference identity never rests on a filename. load::variants already refuses to read identity from it. The ##contig lines carry it, and they are kept.

INFO and FORMAT definitions keep their ID, Number and Type and drop their Description: which fields a record can carry, and how they are shaped, is part of what the file is; the prose describing them is not, and a tool release that rewords a description has not changed a call. Number is spelled out by hand (A, R, G, ., LA…) rather than taken from a derived Debug, so that a rename inside noodles cannot quietly change what every key in every cache is made of.

Reference

Scanned by hand, as load::fasta is, so that a three-gigabase reference is reduced without being held in memory: each contig’s sequence is folded into a hash of its own as it is read. The line breaks arrive as nothing but the points between updates, which is why wrapping cannot reach the result.

Uppercased, because that is the form the SAM specification defines its M5 contig checksum over, and ReferenceId::fingerprint already agrees. Soft masking goes with the case, deliberately: a lowercased repeat region is an annotation applied to a sequence, not a different sequence.

Reads, intervals, report

FASTQ through noodles, which has already split the description off the name. BED by hand, as load::intervals is, because noodles’ BED reader is typed by column count and a BED in the wild has whichever columns its author felt like writing. The resistance report is ours: the header row kept as a row, the rows below it sorted, and a row whose column count disagrees with the header is a parse failure rather than something to hash.

Named lists: the one pair that disagrees on purpose

canon::entity_set and canon::ranked_list do the same work in opposite directions over the same bytes, and they are deliberately two functions.

An EntitySet is a set of entities, so its rows go in as records and sort. A RankedList is a ranking, so its rows go in as ordered_records and do not — because rank is the row position and the position is the output (D41). The DataKind is hashed into the stream before either runs, so reading one file both ways gives two hashes rather than one: a step annotated to return a ranking can never be served the cached output of one annotated to return a set, which would be the same bytes under a weaker promise.

What is shared, and what is not. The loader is shared (load::named_list), because reading a TSV, finding the identifier column, inferring the namespace and noticing a symbol a spreadsheet ate is the same work with the same subtleties for both kinds — including the distinction between “declare identifier_namespace” and “re-export this file”, which are opposite pieces of advice and took M8 a correction to get right. Copying that into a second file would have copied the part that is hard. The canonicaliser is not shared, because it is the one place the two kinds are not the same, and sharing it would mean expressing the difference as a flag somewhere else. The two kinds apply identical dimensions, which a test pins (a_ranked_list_and_a_gene_list_apply_exactly_the_same_dimensions): if the difference ever spreads past canonicalisation, that is where it shows.

The trade-off, stated. Keeping order makes the cache stricter, and a stricter cache costs time it does not have to. A ranking re-emitted by a tool that broke a tie the other way reruns everything below it, even though a scientist would call the two rankings the same. That cost is accepted on the project’s standing bias: a cache that is too cold costs time, and one that is too warm is wrong. There is no tolerance to loosen it with, either — a score column is compared exactly, because no drift has been measured and a guessed tolerance would be baked into every cache key.

Why ligase inspect reads a .tsv as the weaker claim. The command’s LOADERS table maps .tsv to entity_set, and leaves it there. A file cannot say whether its row order is meaningful: that is a fact about what the file is for, which lives in the step annotation that consumes it, and inspect has no pipeline to read one from. Guessing RankedList would have inspect assert something about a user’s data that nothing in the data supports. Everything inspect actually reports — the four dimensions, their sources, the notes — is identical for both kinds, so the weaker reading loses nothing it could have shown.

What mapping a ranking across identifier spaces does to its ranks. map_identifiers is registered for both kinds (convert::Conversion::ALL), because graph::propagate guards the axis override on converts(output) and a ranking left out of that list would carry the input’s namespace onto an output that had crossed. It writes rows in input order, so a mapped ranking is still ranked — but the identifiers that did not cross are left out, so the ranks close up: if the top-ranked identifier had no mapping, the second-ranked one becomes first. That is the honest consequence of D38’s refusal to carry an unmapped name into a space it is not in, and it is visible rather than silent, because every identifier that did not cross is named and counted in the run report, in provenance, in a bundle and in the methods paragraph (D26). The shipped lg.map_identifiers library step is typed for an EntitySet; a ranking crosses through a step of the user’s own declaring conversion="map_identifiers".

Knowledge graphs: sets all the way down

The ordinary rule, reached one level further in than usual. Nodes and edges are records and sort, because the order a graph’s nodes came off whatever assembled them is not a fact about the biology. Inside a node or an edge, the ids and sources lists are also sets, so they are sorted, deduplicated and joined on ASCII unit separator before the record is hashed — a graph re-serialised by a different library must not become a different graph.

Each record leads with a discriminator, node or edge. Both go into one sorted list of record digests, so without it a node and an edge whose parts happened to line up would be one record.

The deduplication inside a node is exact, never folding case, so that the canonical form and SourceSet agree on what two names are. A hash that folded A.json into a.json would make two graphs the dimension checker refuses to join agree on their content, which is the two halves of the engine contradicting each other.

What is not dropped is which sources those are. A source folded in upstream is a different graph, and a cache that served the old answer for it would be serving the wrong one — which is the same reason source_set is a dimension. What is dropped is remote::response’s closed set of keys a serving system writes about itself, from the top level and nowhere else: inside a record a timestamp is what the record says, and recursing would silently delete a time series. Each drop emits a Note::GraphFieldDropped. The reasoning, and the three things the kind deliberately does not do, are on knowledge graphs.

Tolerance

pub struct Tolerance(f64);
impl Tolerance { pub fn bucket(self, value: f64) -> Option<i64>; }
pub fn tolerance(kind: DataKind, field: &str) -> Option<Tolerance>;

One table, one entry: (Variants, "QUAL") at 0.1. Everything else is exact.

A tolerance can only be expressed by quantising, and D20 says why: “within ε” is not transitive, so it is not an equality, and a hash can only express an equality.

0.1 Phred is chosen to absorb last-digit floating-point wobble — 215.376 against 215.375 — while sitting two orders of magnitude below the smallest threshold anyone filters on, so it cannot merge two qualities a user would treat differently. It is one constant in one table.

A value too large to bucket keeps its own text rather than being folded in with every other large value, and a QUAL of . is kept as written: there is nothing to quantise and nothing is gained by pretending otherwise.

The fallback

A file that will not parse hashes as its bytes, tagged Form::Raw (D21). The tag is inside the digest, so a fallback can never collide with a canonical form, nor with the plain ContentHash of the same bytes.

The direction matters: bytes are the stricter test, so a fallback can cost a rerun and can never serve a wrong answer. It is also what keeps the engine working on a .bam holding something that is not a BAM — including the text-file fixtures the execution tests are built on.

Every parser is strict for the same reason. A canonicaliser that read what it could and ignored the rest would be the dangerous kind of lenient: two files that differ only in the part it skipped would agree, which is the one failure a cache must never have. So a FASTA with no > line, a BED row with two columns, a VCF record with seven, and a report row that does not fit its header are all parse failures.

What a canonical form notices

The fallback handles a file that will not parse. The other half of the same problem is a file that parses perfectly and is still wrong in a field the rules cannot drop, and that is what a Note is for (D26).

There is one note in v0.1: a sample identifier that is a file. A VCF’s sample names and a BAM’s read-group samples are what the file is about — a sample set is a dimension — so neither can go the way @PG went, and a tool handed an alignment with no @RG SM writes the input file’s path there. The hash of such an output moves with the cache root.

Note::about_sample decides, and deliberately narrowly: a path separator, or a trailing extension naming a format this engine reads. K03455.1 has a dot and is not a file. The Shape it finds — absolute, relative or a bare name — only chooses the wording, because an absolute path is the one that cannot travel and saying so is more use than “a file”.

for sample in header.sample_names() {
    digest.text("sample", sample);
    if let Some(note) = Note::about_sample(sample) {
        digest.note(note);
    }
}

Three properties hold, and each is a test:

• A note never changes a hash. Digest::note pushes onto a Vec that finish does not read. Two VCFs differing only in a path-shaped sample still have different hashes, because they are claims about different sample sets.
• A note is dropped on the fallback path. canon::hash takes the notes out of the digest on success and discards them on failure. A remark about a file that did not parse would be a remark about the half of it that was read.
• Repeats collapse. Digest::note ignores a note it already holds, so an alignment whose four read groups name the same file has one thing wrong with it rather than four.

Where a note goes

Canonical carries notes beside hash and form, and from there they travel without being recomputed:

They are stored rather than recomputed because a cache hit does not reopen the file, and a warning that appeared on the first run and vanished on the second would be worse than no warning. That is the one cost: the cache’s SCHEMA_VERSION moved to 2 for the new column, which clears its tables. CANON_VERSION did not move, because nothing about what is hashed changed.

Canonicalisation is not the only thing that finds a note. A step’s body says what its own work rested on, which no reading of the output could recover, and those notes travel the same way — stored against the step’s key rather than the output’s hash, since they are not facts about its bytes. The Note type itself, both producers and every surface a note reaches are in Notes.

What it costs, and why it is paid once

Canonicalising a BAM is a full pass over it. Doing that on every run would be the one thing that makes this unaffordable, so it is remembered:

CREATE TABLE canonical (
    raw       TEXT NOT NULL,   -- the hash of the file's bytes
    kind      TEXT NOT NULL,
    canonical TEXT NOT NULL,
    form      TEXT NOT NULL,
    PRIMARY KEY (raw, kind)
)

Keyed on the hash of the bytes, not on the path, because that is what it is a fact about. A file moved, copied, or produced again identically by another step is not parsed twice. Behind it sits the prefilter, so the steady state of a second run is stat → remembered byte hash → remembered canonical hash, and report.hashed and report.canonicalised are both zero.

CANON_VERSION sits in the cache’s meta beside the other two versions. A change to it clears this table and the step entries, which is D19 extended by one line: a canonical hash is a fact about a file given the rules that produced it, so one computed under other rules is a fact about something else. Nothing is migrated because nothing needs to be.

Audit mode

crates/ligase-core/src/audit.rs, which is the user-facing half of the same idea: comparing bytes and meaning separately is what lets an audit tell a tool that signs its work from a tool that cannot repeat itself.

pub enum Verdict { Deterministic, Reproducible, NotReproducible }

audit() runs the pipeline once, normally and through the cache, so that the audited nodes have their inputs; then runs each of them twice more through exec::produce into scratch files, hashes each output both ways, and deletes the scratch. Nothing from the two runs is recorded: an audit observes, and recording either would put a result from a step known to wobble into the cache.

Two pieces were lifted out of exec rather than duplicated — exec::inputs_of, so an audited step is handed exactly what a run would hand it, and exec::produce, which is the part of running a step that is just running it. The audited nodes are taken in turn: a duration is part of what an audit reports, and two runs of an aligner competing for cores would produce timings that describe the machine rather than the step.

AuditReport::verdict() is the worst verdict, not the commonest. One irreproducible sample in a cohort is an irreproducible step, and a summary that averaged them would bury what the user is auditing for — the same reasoning as D15 counting places rather than names.

What is not here

Provenance. Nothing here records why a result is what it is — and dropping the fields that used to say so is what made provenance necessary rather than merely nice (D22).

Notes about inputs. A note is reported for what a run produced. A leaf input the user supplied with path-shaped sample names is their file, described as they gave it, and exec::remember records an InputRecord without notes. Reporting those would mean deciding what a user is to do about a file the pipeline did not write.

BCF and CRAM. Both would fall back to their bytes today. Neither is in the reference pipeline; adding them is a module beside the others and a CANON_VERSION bump.

Sorting under memory pressure. Record digests are held in memory while a file is canonicalised: 32 bytes a record, so a hundred million records is 3.2 GB. That is fine for the amplicon data this is built on and would need an external sort for whole-genome BAMs. The shape that would change is Digest::finish, and nothing above it.

Deciding whether two different tools agree. Everything here is built to compare two outputs of the same tool. A canonical form that could reconcile a GATK VCF with a bcftools one is a much larger claim, and the right place for it is the conversion graph (D5), not the hash.