lib/machine/src/explore/query/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! Once a run fails, the next questions are which choice, message, or fault led
  2 //! there, and where the failing run first parted from one that passed. This
  3 //! namespace records one run in order and answers such questions within bounds
  4 //! fixed in advance.
  5 //!
  6 //! The record holds each step's choice, the position the run reached, and what
  7 //! the step produced: entries added to the run's ordered log of inputs and
  8 //! faults, event messages from the guest kernel, and the events recorded for
  9 //! checking rules. A caller asks for the entries that match one question: a
 10 //! kind of entry, a kind of choice, a rule event, a packet, a fault, an outside
 11 //! effect, or terminal input and output. A caller compares two runs from the
 12 //! same start and learns where they first differ.
 13 //!
 14 //! An answer has to point at entries in a way that still names the same entry
 15 //! after the record is stored and read back in another process, and that cannot
 16 //! be resolved against a different record. Answers and comparisons have to fit
 17 //! fixed storage and bounded work, so a scan cut short has to say so and be
 18 //! resumable. A question asked of a run that was itself cut short cannot claim
 19 //! a complete answer. A record has to agree with itself: log entries follow one
 20 //! another from each position to the next, and rule events move forward in
 21 //! number and in time.
 22 //!
 23 //! Each run becomes an append-only record, a *causal history*: the start
 24 //! position, then for each step the choice, the position reached, and the
 25 //! entries that step produced. `finish` checks the record, marks it exhausted
 26 //! or incomplete, writes its one canonical byte encoding, and records its
 27 //! SHA-256 identity, and after that the record changes no more.
 28 //!
 29 //! Queries (`Query`) and comparisons answer with references into the record,
 30 //! each an *evidence reference* made of the record's identity, a target (a
 31 //! choice, a reached position, or an entry), and an index, so an answer holds
 32 //! no copies of the entries. A reference also travels as an 80-byte encoding
 33 //! with its own SHA-256 check. A query reads the record in one fixed order: the
 34 //! start, then for each step its choice, its entries, and the position reached.
 35 //! A query scans forward or backward, over the whole record or before or after
 36 //! a reference, and optionally only inside a window of simulated time. A query
 37 //! stops when its result storage fills or its work budget runs out, returns a
 38 //! cursor to resume from, and marks the answer incomplete with the reason. A
 39 //! query over an incomplete record that could still grow past the scanned range
 40 //! reports its answer incomplete as well.
 41 //!
 42 //! A comparison (`Diff`) walks two sealed records with the same start step by
 43 //! step and collects the common prefix of steps equal in choice, entries, and
 44 //! reached position. It reports the first step that differs (the *first
 45 //! divergence*), with the reason and which fields of the two positions differ.
 46 //! A comparison stays inside its prefix capacity, its suffix capacity, and a
 47 //! work budget, and it marks the result incomplete when any of them runs out or
 48 //! when either record is incomplete. Records, queries, and comparisons hold no
 49 //! pointers.
 50 //!
 51 //! - *moment*: a position in one world's history, pairing the world root the
 52 //!   world grew from with the ledger root it has reached since.
 53 //! - *frame*: one step of a causal history: its decision, the moment it
 54 //!   reached, and the range of its evidence records.
 55 //! - *transition*: one ledger entry together with the ledger root it produces.
 56 //! - *semantic event*: one numbered, timestamped entry in the event list a run
 57 //!   is checked over.
 58 //! - *canonical wire*: the one fixed-size byte encoding of a sealed history for
 59 //!   a given capacity, ending in its SHA-256 identity. Decoding rejects any
 60 //!   input that does not encode back to the same bytes.
 61 
 62 const canon = @import("canon.zig");
 63 const engine = @import("engine.zig");
 64 const history_owner = @import("history.zig");
 65 const types = @import("types.zig");
 66 
 67 pub const Capacity = types.Capacity;
 68 pub const ChoicePattern = types.ChoicePattern;
 69 pub const Cursor = types.Cursor;
 70 pub const Diff = engine.Diff;
 71 pub const DiffCapacity = types.DiffCapacity;
 72 pub const DiffCompletion = types.DiffCompletion;
 73 pub const DiffIncompleteReason = types.DiffIncompleteReason;
 74 pub const DiffResult = types.DiffResult;
 75 pub const Divergence = types.Divergence;
 76 pub const DivergenceReason = types.DivergenceReason;
 77 pub const EffectPattern = types.EffectPattern;
 78 pub const EffectPhase = types.EffectPhase;
 79 pub const Error = types.Error;
 80 pub const Evidence = types.Evidence;
 81 pub const EvidenceRange = types.EvidenceRange;
 82 pub const EvidenceRef = types.EvidenceRef;
 83 pub const FaultPattern = types.FaultPattern;
 84 pub const Frame = types.Frame;
 85 pub const FramePair = types.FramePair;
 86 pub const FrameRefs = types.FrameRefs;
 87 pub const History = history_owner.History;
 88 pub const Identity = types.Identity;
 89 pub const IncompleteReason = types.IncompleteReason;
 90 pub const Kind = types.Kind;
 91 pub const Located = types.Located;
 92 pub const PacketAction = types.PacketAction;
 93 pub const PacketPattern = types.PacketPattern;
 94 pub const Pattern = types.Pattern;
 95 pub const Query = engine.Query;
 96 pub const QueryCapacity = types.QueryCapacity;
 97 pub const QueryCompletion = types.QueryCompletion;
 98 pub const QueryPlan = types.QueryPlan;
 99 pub const QueryOrder = types.QueryOrder;
100 pub const QueryResult = types.QueryResult;
101 pub const QueryScope = types.QueryScope;
102 pub const RefWire = canon.RefWire;
103 pub const RootDifference = types.RootDifference;
104 pub const Target = types.Target;
105 pub const TerminalDirection = types.TerminalDirection;
106 pub const TerminalPattern = types.TerminalPattern;
107 pub const View = types.View;
108 pub const VirtualTimeRange = types.VirtualTimeRange;
109 pub const decodeRef = canon.decodeRef;
110 pub const encodeRef = canon.encodeRef;