Nothing left that nobody reads

Nothing left that nobody reads

The release before this one said the first sector was the one piece of code
here that is written and never read back, that reading it meant a decoder for a
width nothing else here uses, and that it deserved a release of its own. This
is that release, and with it there is nothing this file writes that nothing
here reads.

Fifty instructions over a hundred and eighty octets. Forty-three of them are
sixteen bits wide and seven are sixty-four, the far jump counting as the last
narrow one, because the sector changes width halfway through by jumping into
itself with a new selector. The operand-size prefix is the whole of the
difference between the two halves and it means opposite things in them: narrow,
it widens an operand to thirty-two bits, and wide, it narrows one to sixteen.
The same three octets on either side of that jump are two different
instructions, which is exactly the sort of thing a decoder is for and a search
is not.

Because that is what this replaces. The three numbers the sector states about
the disk around it - how many sectors to ask the drive for, where the
descriptor table is, where to go to become sixty-four bits wide - were found by
searching the sector for the octets of the instruction that carries each. That
works until an immediate happens to look like the instruction being searched
for, and nothing stopped that but the sector staying the shape it was in when
the search was written. They are read off the decoding now.

Decoding it is only worth the lines if the decoding is asked something the
octets could not be, and every number in that sector is one instruction telling
another where to look. The drive is asked for a read, and for the sectors that
were actually written. Where the drive is told to put them is the address the
last instruction jumps to. The descriptor is loaded from where the
instructions stop. Long mode is entered at the instruction after the one that
enters it. Paging is turned on with a table the sector wrote, the tables it
wrote are inside the span it cleared first, and both selectors it uses are
whole entries of the table it loaded. None of those were checked before and
all of them are now.

And the claim the three machines and the module have always made about their
texts, which the disk could not: every octet of it is spent on something. A
hundred and eighty of instructions, six of the descriptor that names the table,
forty of the table, two hundred and eighty-four of nothing, two of the
signature. Five hundred and twelve.

One thing found on the way, and it is the same thing the last release found
wearing different clothes. Once the disk reader was reading the sector, two
rules existed in two places - whether the drive is asked for a sensible number
of sectors, and whether long mode is entered inside the sector. A rule checked
twice cannot be deleted from either place without the other covering for it,
and deleting all forty-five rules in turn is how that was found: eight came
back green, six of them for that reason. The fix is not more bends. It is
deleting the duplicate. Forty-two rules now, sixty-seven bends, and every rule
fails the battery on its own.

Two of those bends are a sector built rather than bent. The written sector
stops decoding at its own jump into the payload, a long way before the end, so
no change to one octet of it will ever be an instruction wanting more of the
sector than is left, and none will ever be a sector with no jump in it at all.
These readers get pointed at images off a disk as well as at ones just written,
so what they do with a sector that is neither is worth stating.

python3 ouroboros.py --explain container

Full Changelog: v0.61.0...v0.62.0

LOC: 27759

The outermost thing, read back

The outermost thing, read back

Everything this file writes is read back by something inside it, except the
thing on the outside. The three texts are decoded instruction by instruction.
The module is decoded and run by a reader that shares nothing with the encoder.
The IR, since last release, is read and run here too. And every one of them
sits inside a container that nothing here ever looked at again: an ELF64, a
PE32+, or a disk whose first sector is a machine walking up to its own width.

The first thing to say is what the gap was not, because the obvious answer is
wrong. The machine readers do take an image apart properly - the entry, the
program header table, a walk over the segments, mapping what they say to map.
They are not slicing at a constant. What they do not do is disbelieve any of
it. No field is checked against any other, the permission bits are not read at
all, and a header naming a segment that runs off the end of the file would be
mapped as cheerfully as a correct one. The only thing in the world that would
refuse it is the loader: the kernel on a host that has one, the firmware on a
machine that has that. Which is the same standing tier 2 had before the last
release, and the same answer: a second opinion that lives here.

So a reader for each container, answering every complaint rather than the first,
because the reason to ask is to be told what to fix. Nine of them in one
inventory, walked by the battery and printed by --explain container. They share
no constant with the writers: where the text begins is found by asking which
segment holds the entry, not by adding up the header sizes the way the writer
does, and two round-trip comparisons that had been doing exactly that now ask
the headers as well.

Three things in it are worth pulling out.

The third board is in that inventory with no container at all, and that is the
check. Its reset vector goes to the first octet of memory whatever is there, so
an executable in front of the text is jumped into as though the header were an
instruction. That happened, once, and the letter printed at each stage is how
it was found. Wrapping it again is now a failure rather than a morning.

The first sector is not decoded and this does not pretend to. It is sixteen
bits wide, hand-written, and switches to sixty-four at its own far jump, so
reading its instructions means a real-mode decoder that nothing else here would
use. What is read instead is the three numbers it states about the disk it is
the front of: how many sectors it asks a drive for, which must be sectors the
disk has and, for a boot disk, exactly the ones that were written; where the
descriptor table is and how long it claims to be, which must be whole entries
starting with a null one and must fit in front of the signature; and where it
goes to become sixty-four bits wide, which must be inside the sector it is
already in. Each found by looking for the instruction that carries it. The
decoder is the next piece of this and deserves its own release.

And the part worth the most, which is not the readers. A reader that answers
nothing about every container it is given is either looking at correct
containers or not looking. Fifty-three bends, one field at a time, are how
those are told apart - and the first version of that check was nearly useless.
It asked only whether a complaint appeared, and under that test fourteen of the
thirty-three rules could be deleted with the battery still green, because a bend
that trips two rules leaves the second covering for the first: a segment reading
past the end of the file also holds more on disk than in memory, and a section
reading past the end also reaches past what the image says it maps. Making each
bend name the words it expects back pins every rule to exactly one bend, and
that was verified the only way it can be, by deleting all thirty-three in turn
and watching each one fail.

That change also took the layer from 75 per cent covered to 96, which is the
same fact from the other side: the quarter nothing reached was the part that
says what is wrong, and nothing had ever been wrong.

python3 ouroboros.py --explain container

Full Changelog: v0.60.0...v0.61.0

LOC: 27336

Tier 2 reads its own writing

Tier 2 reads its own writing

Every tier in this file has a second opinion inside the file. The three
machines are read back instruction by instruction. The module is read back and
executed by a decoder that shares nothing with the encoder. The interpreter
reads everything. Tier 2 had none: the IR was handed to llvmlite, which
verified it and ran it, and agreeing with the tool that consumes you is not a
check. On a host with nothing installed it was not checked at all, which is
four of the six interpreters CI runs.

Layer 16b reads back exactly what layer 16 writes. The list of shapes was
counted rather than guessed at - the catalogue at three orders, thirty generated
programs and the one that divides - and it came to about twenty forms, with one
absence that decides the whole design: there is no phi. Layer 7 already turned
the operand stack into memory, so every value that outlives a block is in an
alloca, no block takes arguments, and a register is written once and read from a
dictionary. A reader for SSA without phi is an afternoon. With it, it is a
dominator tree.

Two details in it are load-bearing and do not look it. sdiv truncates towards
zero and srem takes the sign of its left operand; layer 16 emits the pair and
then corrects the quotient back to the flooring the interpreter does, so a
reader that floored would undo the correction and still agree on every positive
operand. And getelementptr multiplies by the element width, which matters for
every array that is not i8.

Which is how the program that divides came to divide a negative. It existed to
reach the division emitters and reached them with two positive operands - the
one case where truncating and flooring give the same answer. Every tier
corrects for that divergence and nothing had ever asked one of them to. All
nine got it right, which is the answer you want and not the one you can assume.

The check was validated by breaking the reader five ways. Four are caught on
two programs. The fifth is not, and cannot be: masking a zext as though it
were a sext is unobservable when the only zext the backend writes widens an i1
that is already zero or one. That is an equivalent mutant rather than a missing
check, and the difference was settled by listing every conversion layer 16
emits instead of arguing about it.

In the fuzzer it is read-ir, needing no toolchain, so it runs precisely where
the jit tier is skipped: four seconds over two hundred programs on the oldest
interpreter this supports. On the command line it is --run-llvm, taking a path
or - for a pipe, beside --run-wasm.

python3 ouroboros.py --emit-llvm | python3 ouroboros.py --run-llvm -

Full Changelog: v0.59.0...v0.60.0

LOC: 26518

v0.59.0

A floor under each layer

The coverage walk landed eight releases ago and asserted nothing at all. It
printed a number and a list, and a number nobody is accountable to is a number
that drifts.

It has floors now, and the shape of them is the decision worth explaining:
they are per layer, not one for the whole file. A single figure for 12478
lines lets a machine backend go quietly dark behind a hundred lines of
something easy to run somewhere else, and the average would never move. Seven
layers carry one, and they are the ones where being wrong is silent: the LLVM
lowering, the three machine backends, the wasm encoder, the module read back,
the machines read back, and the tier that asks for nothing underneath it. Each
floor is the number that layer reaches today, less a little.

The rest carry none, on purpose. The scenery does not need one, because being
wrong there is loud. And the coverage layer has none because it does not
measure itself, which was written down when it landed and is still true.

One thing the floors turned up before they were even set. The other language's
compilers had a layer sitting at 23 per cent, and the reason was not that they
went unchecked: it was that nothing in the exercise list called the thing that
checks them. Adding it took that layer to 86, and the file overall to 87.8.

python3 ouroboros.py --coverage

Full Changelog: v0.58.0...v0.59.0

LOC: 26060

v0.58.0

Breaking it on purpose

This file says what it checked at every turn, and the release before last
added how much of itself those checks touch. Neither of those says whether
any of it would catch anything. A check that cannot fail is a check that is
not there, and nothing here had ever been asked to fail.

So now it breaks itself, one small change at a time, in the encoders, the
readers and the narrators - the places where being wrong is quiet. Each
change gets its own interpreter and is put to the battery, then the tier
differential, then the fuzzer. Cheapest first, and the fuzzer last, because a
mistake the fuzzer notices sends it off to shrink the program that showed it,
which costs more than both the checks in front of it put together.

python3 ouroboros.py --fuzz-mutants

It reports. It does not pass or fail, and that is the design rather than a
shortcut: a change nothing noticed is one of two things, and telling them
apart wants a reader. Loosen the bound on the second machine's shifted
immediate and the encoder writes a different encoding that is exactly as
correct; no amount of running will ever call that wrong. Making this a gate
would have meant either pretending it was a bug or quietly dropping it.

The first thing it found was a flaw in itself, which is the right order to
find things in: the first version changed words inside docstrings, which
survive for no interesting reason at all and read as gaps. It masks the
strings and the comments now, through the tokeniser rather than by guessing.

Sixteen of twenty-four caught. One survivor is worth the trip: the x86
narrator's guard on group five can be loosened and nothing minds, because
nothing the battery narrates contains a decrement. The emitter is reached -
the check two releases ago says so - but only into the disk and the firmware,
which are the two texts the narrator is never pointed at.

Full Changelog: v0.57.0...v0.58.0

LOC: 25996

v0.57.0

Watching the module go

Layer 20 knows what an instruction means. The narrator knows what it is
called. One tier down those two were joined into something that shows a
program going, and up here they never were, which left the module as the last
thing in this file that could be read and run and not watched.

What is worth showing is not the same. A machine has registers, so a step
there says which one it wrote. A wasm function has a stack, so a step here
says what it left on top, and names the locals that moved beside it. A step
is reported once the following step has begun, because that is the first
moment its effect can be read; the last one has nothing after it and is said
with what the function answered.

The interpreter takes a watcher rather than being copied for this. One branch
per instruction, and no second implementation of the same semantics to keep in
step with the first, which is the mistake this file would have made a year ago.

The claim that every step it runs is a step it can name now covers the module
as well as the three texts: 17969 of them.

python3 ouroboros.py --trace-wasm

Full Changelog: v0.56.0...v0.57.0

LOC: 25793

v0.56.0

The module writes itself again

When the narration learned to hand its fields back to the encoder, the three
machines got a claim they had never had: that what this file says its octets
are will write those octets again. The module did not get it, which left one
tier where the naming was checked for its length and not for its content. A
branch depth read one structure too shallow would have passed every walk
there is, in silence.

It has it now. Every instruction comes back with the way to write it again,
and the awkward part is exactly the part worth checking: wasm says how many
structures to leave, and the encoder wants to be told which one. So the walk
keeps the stack of what is open, looks the name up, and hands the encoder the
name rather than the number, leaving it to count the depth again for itself.
Take a depth apart wrongly and the octets come back different.

One thing had to be true first and was worth confirming rather than assuming:
the encoding has to be canonical, because LEB128 will hold the same number
several ways and a round-trip means nothing if the encoder is free to pick a
different spelling. Every immediate layer 19 writes comes back the octets it
went in as.

Identical at seven orders and over the whole catalogue on the first run.
Reading a branch one structure too shallow is reported.

Full Changelog: v0.55.0...v0.56.0

LOC: 25702

v0.55.0

Four compilers, and whether they are one compiler

There is a generator for the language of tier 1 and there has never been one
for the language of tier 3. So the four compilers for that language had
compiled, between them, the nine programs written in it by hand, and those
nine do not change.

What a fixpoint says is that a compiler reproduces itself. A compiler can do
that while getting wrong anything it does not itself use: the miscompilation
is stable, so the three generations still agree, and the closure still
passes, and nothing anywhere says a word. The only thing that finds it is a
program none of them is.

So one is generated, handed to the seed and to all three tails, and every
answer compared. A refusal counts as an answer, because four compilers
refusing together is four compilers agreeing. The programs terminate, read
nothing and print three digits, since a program that hangs compares nothing,
and the loop counters are readable inside their own bodies and never
assignable there, which is the whole of why they stop.

It found something on the first serious run, and it is the same shape as the
last two releases. There were three limits on how many values a function may
have where there should have been one: eight thousand in the seed and in the
tail for this machine, three thousand in the other two. A function with four
thousand compiled twice and was refused twice. They all stop at three
thousand now, and the number is not this machine's to pick - a displacement
here is thirty-two bits and would hold any of them, but the one that reaches
least far decides, and that is the second machine, whose scaled offset stops
at four thousand and thirty-one.

The check was checked by putting the old limit back: five disagreements inside
fifty programs, naming the seed's answer and the three refusals beside it.

python3 ouroboros.py --fuzz-gsl2 40

Full Changelog: v0.54.0...v0.55.0

LOC: 25560

v0.54.0

Two compilers, one language

The bootstrap fixpoint says that the seed and the compiler written in itself
emit the same bytes for any accepted input. It was quietly assuming
something else: that the two of them accept the same inputs at all.

They did not. The seed is written in a language whose stack it does not
choose, and a GSL-2 expression a hundred and nine parentheses deep ended the
process with a traceback instead of a refusal. The self-hosted compiler,
being a program, would have gone thousands deep and accepted it happily. The
crash was the visible half; the divergence was the half that mattered, since
two compilers that accept different languages cannot be compared at all.

Both stop at the same stated number now. Sixty-four, chosen from two
measurements rather than from taste: the deepest expression in any GSL-2
source in this file is seven, and the seed gives way at a hundred and nine.
Verified from both sides, the seed and a built gslcelf refusing together at
sixty-four and accepting together at sixty-three.

The same asymmetry had been left one language up and unnoticed. Layer 5
learned to refuse at four hundred levels of descent two releases ago; the GSL
front end written in GSL-2 did not, and would have gone on accepting what
this file refuses. Both draw that edge in the same place now, which is what
the refusal fuzzer exists to check and would not have caught, since nothing
it generates nests four hundred deep.

All three compilers still settle in three generations, the seed still writes
the compiler the compiler writes, and both front ends still refuse the same
broken programs.

Full Changelog: v0.53.0...v0.54.0

LOC: 25192

v0.53.0

The node you were handed is the node you get

The parser answered with the abstract node, and every reader reached for an
attribute that only one kind of node has. It worked, because a table pairs
each code with the shape of node it applies to. Nothing but the table said
so: get that pairing wrong and the first news of it is an AttributeError
somewhere down inside the analyser, a long way from the table that was wrong.

Every node carries where it came from. That was true of all of them except
the root, and it is written on the base class now rather than repeated
thirteen times and assumed; the root carries the position of the lattice
declaration it opens with. The parser answers the two declarations it names
instead of two base nodes. And the branches of the analyser and the lowering
now ask for the shape their code implies, through one helper that refuses by
naming both what it wanted and what it found - so the table's pairing is
checked at the place it is used instead of being discovered later by an
attribute that is not there.

That is the whole of it worth having. The remainder is saying out loud what
was already the case: the registry hands back a way to make an instruction
and how many operands that takes is the opcode's business rather than the
signature's, two tables keyed by a class admit to being keyed by a class, and
an interned marker declares the name it keeps rather than carrying a
suppression for it.

When ty was first pointed at this file it had sixty-one things to say. Three
releases ago that went to forty-one and three of its rules were set aside in
the workflow, with a note that narrowing the front end was the real fix and
was its own piece of work. This is that piece of work. It has nothing to
say now, and the workflow runs it with no rules set aside at all.

Full Changelog: v0.52.1...v0.53.0

LOC: 25150