Documentation
¶
Overview ¶
Package chronicle is the extracted cascade engine of the chronicle substrate (docs/proposals/chronicle-substrate.md, @C03/@C04): a generic rollup cascade parameterised by a monoid, over a time-grain hierarchy.
The theorem (@C03): the rollup cascade in ts, cal, and bal is one construction — a monoid homomorphism over a grain hierarchy. ts folds (number, +, 0) and (min/max with identities); cal's dayparts fold (bitset, OR, ∅); bal folds (int64, +, 0). This package implements the construction once, parameterised: an associative combine with an identity, cascading upward on append, invalidating on correction.
Sequencing (@C §5): incumbents do not migrate onto this engine merely because it exists — cal's rollups are stress-verified on real hardware and migrate opportunistically or never; ts likewise when next touched for its own reasons. New consumers (bal, wave 4) ride the engine natively. The instantiation tests in this package prove the incumbent monoids are expressible, which is the extraction's correctness bar.
Index ¶
- Variables
- func AssertRebuildOracle(t TestingT, ctx context.Context, o RebuildOracle)
- func CanTransition(from, to TemporalPolicy) bool
- func MonthWindows(t time.Time) (time.Time, time.Time)
- func RunBucketStoreContract(t *testing.T, newStore func() BucketStore[int64])
- type BitsetOR
- type BucketKey
- type BucketStore
- type Engine
- func (e *Engine[T]) Append(v T, t time.Time)
- func (e *Engine[T]) AsOf(epoch, t time.Time) T
- func (e *Engine[T]) Bucket(level int, t time.Time) T
- func (e *Engine[T]) FoldRange(from, to time.Time) T
- func (e *Engine[T]) Invalidate(t time.Time)
- func (e *Engine[T]) Recompute(t time.Time, replay func(from, to time.Time, emit func(v T, at time.Time)))
- type Grain
- type Hierarchy
- type MaxFloat64
- type MemStore
- type MinFloat64
- type MinValue
- type Monoid
- type OracleResult
- type RebuildOracle
- type SealedError
- type Sealer
- type SumFloat64
- type SumInt64
- type TemporalPolicy
- type TestingT
- type TreeSpec
- type WindowFn
Constants ¶
This section is empty.
Variables ¶
var ErrBackdatedRefused = errors.New(
"entry predates the timeline's latest entry (policy append_only)")
ErrBackdatedRefused is the sentinel a guard's refusal wraps when an append_only timeline receives a strictly-backdated entry. Primitives wrap it in their own error types and codes (bal: XOLU-BAL006).
Functions ¶
func AssertRebuildOracle ¶ added in v0.16.13
func AssertRebuildOracle(t TestingT, ctx context.Context, o RebuildOracle)
AssertRebuildOracle runs the oracle and fails the test on divergence — the test-side consumption form.
func CanTransition ¶ added in v0.26.0
func CanTransition(from, to TemporalPolicy) bool
CanTransition reports whether a timeline's policy may change from one value to another. Widening (append_only → backdated) is always legal: it only admits more. Narrowing is refused in v1 — it asserts the recorded past is monotonic, which is a verification-bearing operation deferred by T-55's scope.
func MonthWindows ¶ added in v0.16.13
MonthWindows tiles time into UTC calendar months — bal's period shape.
func RunBucketStoreContract ¶ added in v0.16.13
func RunBucketStoreContract(t *testing.T, newStore func() BucketStore[int64])
RunBucketStoreContract exercises any BucketStore[int64] implementation against the behaviour the engine depends on. New stores (bal's SQL-plane store at wave 4; any Pebble-plane store) must pass this harness before the engine is trusted on them — the same contract-harness discipline as pkg/graph's store contract.
The int64 carrier is deliberate: the contract is about storage behaviour (presence, overwrite, deletion, ordered ranging, level isolation), not the monoid, and a comparable carrier keeps the assertions exact.
Types ¶
type BitsetOR ¶
type BitsetOR struct{}
BitsetOR is cal's daypart occupancy fold: (uint8 bitset, OR, 0). One byte summarises a day at 3-hour-daypart granularity (@cal codec §4).
type BucketKey ¶
BucketKey addresses one bucket: a hierarchy level and its grain-aligned start instant (UTC).
type BucketStore ¶
type BucketStore[T any] interface { Get(k BucketKey) (T, bool) Put(k BucketKey, v T) Delete(k BucketKey) // RangeLevel visits every existing bucket at the given level with // Start in the half-open window [from, to), in ascending Start // order. Returning false from fn stops the iteration. Required by // the prefix-fold read path (AsOf); implementations back it with an // ordered scan (SQL: ORDER BY start; Pebble: key iteration). RangeLevel(level int, from, to time.Time, fn func(k BucketKey, v T) bool) }
BucketStore is the storage seam. The engine is storage-agnostic: an in-memory store ships here for tests and small consumers; bal brings a SQL-plane store (wave 4, guard-locality obliged — @C04a), and any Pebble-plane store arrives with its consumer.
Get returns the bucket's folded value and whether it exists. Put overwrites. Delete removes (used by invalidation). Implementations must be safe for the engine's single-writer discipline; concurrent writers are the consumer's concern (bal serialises under its own transaction; @C04a).
type Engine ¶
type Engine[T any] struct { // contains filtered or unexported fields }
Engine is the monoid-parameterised cascade over one hierarchy and one store. Append folds a value into the finest bucket and cascades the combine upward through every coarser grain. Invalidate removes every bucket covering an instant so a later Recompute (or the consumer's re-fold) rebuilds them — corrections must not silently keep stale coarse folds (the ts correction rule, generalised).
func (*Engine[T]) Append ¶
Append folds v into the bucket containing t at every level of the hierarchy — the upward cascade. Because Combine is associative and every coarse bucket is an exact multiple of the fine grain, combining the increment directly into each level equals re-folding that level from its children: the homomorphism property, asserted by the engine's tests rather than trusted.
func (*Engine[T]) AsOf ¶ added in v0.16.13
AsOf folds everything from `epoch` up to (excluding) the finest bucket containing t plus that bucket itself — i.e. the cumulative value as of the end of t's finest bucket. Callers wanting strict "before t" semantics pass to=t truncated to grain 0 via FoldRange directly; AsOf is the common inclusive read (bal: balance as of a posting instant includes the instant's bucket).
func (*Engine[T]) Bucket ¶
Bucket returns the folded value for the bucket containing t at the given level, or the identity if the bucket does not exist.
func (*Engine[T]) FoldRange ¶ added in v0.16.13
FoldRange folds the half-open window [from, to) using the coarsest buckets that fit entirely inside it, descending to finer grains only at the ragged edges — the classic prefix/segment walk. This is @C03's cumulative read ("the fold of a prefix: the same monoid, chained across sealed checkpoints"): bal's balance-as-of is FoldRange from the epoch (or the last sealed checkpoint) to the as-of instant.
Correctness rests on the homomorphism: a coarse bucket equals the fold of its children, so substituting it for them changes nothing. The engine's tests assert FoldRange == the naive finest-grain fold.
Cost: O(levels × buckets-touched); for a hierarchy like 5m/hour/day an as-of over a year touches ~365 day buckets + edge partials rather than ~105k five-minute buckets.
func (*Engine[T]) Invalidate ¶
Invalidate removes every bucket, at every level, that covers t. A correction to underlying data makes every covering fold stale; the safe response is absence (forcing recompute), never a silently wrong value. Recompute rebuilds from a replay callback.
func (*Engine[T]) Recompute ¶
func (e *Engine[T]) Recompute(t time.Time, replay func(from, to time.Time, emit func(v T, at time.Time)))
Recompute rebuilds every bucket, at every level, inside the coarsest bucket containing t, by re-folding source values supplied by replay. replay must yield every (value, instant) pair within the half-open window [from, to) — the consumer owns the authoritative record (the journal, the event store) and therefore owns replay; the engine owns only the fold.
The whole coarsest window is cleared, not just the chain covering t: replay refills every fine bucket in the window via Append, so any bucket left standing would double-count its replayed values.
type Grain ¶
type Grain struct {
Name string // e.g. "hour", "day", "month" — diagnostic only
// Width is the fixed bucket width, or 0 for calendar grains. Kept
// for diagnostics and for the fixed-width fast paths; never assume
// it is non-zero.
Width time.Duration
// contains filtered or unexported fields
}
Grain is one level of the time hierarchy: a tiling of the timeline into buckets. Instants truncate onto grain-aligned bucket starts in UTC.
A grain is defined by two operations rather than a width, because calendar periods (months, quarters, years) have no fixed duration yet tile time perfectly:
- truncate(t): the start of the bucket containing t
- next(s): the start of the bucket following the one at s
Fixed-width grains are built with FixedGrain; calendar grains with MonthGrain / MonthsGrain. This mirrors seal.go's WindowFn, which already carried both shapes.
func FixedGrain ¶ added in v0.26.0
FixedGrain builds a fixed-width grain (hour, day, week, 5m…).
func MonthGrain ¶ added in v0.26.0
MonthGrain is MonthsGrain(name, 1).
func MonthsGrain ¶ added in v0.26.0
MonthsGrain builds a calendar grain spanning n whole months, aligned to the start of the year: n=1 months, n=3 quarters, n=6 halves, n=12 years. Alignment to January keeps quarters at Jan/Apr/Jul/Oct and makes every coarser multiple nest exactly.
type Hierarchy ¶
type Hierarchy struct {
// contains filtered or unexported fields
}
Hierarchy is a single-parent TREE of grains, finest at the leaves. Each grain has at most one parent, and a grain may have several children — the shape ts rollups have always had (one source may feed several destinations; a destination has exactly one source). A linear chain is the degenerate case of one child per node.
Nesting requirement, which is what makes the homomorphism exact: every parent bucket must begin on a child bucket boundary and span a whole number of child buckets, so a parent equals the fold of its children and cascading combine loses nothing. This is checked structurally (by probing boundaries) rather than by duration modulus, so calendar grains qualify: months nest in quarters 3:1, quarters in years 4:1, days in months (28–31):1.
func NewHierarchy ¶
NewHierarchy builds a LINEAR hierarchy: grains ordered finest→coarsest, each the parent of the previous. Retained as the common case and for back-compatibility; NewTreeHierarchy expresses fan-out.
func NewTreeHierarchy ¶ added in v0.26.0
NewTreeHierarchy builds a single-parent tree of grains — the shape ts rollups use. Exactly one grain may be the root; every other grain names its parent. Fan-out is permitted (day may parent BOTH week and month); fan-in is not (a grain has one parent), and cycles are rejected.
Grains are stored finest-first by tree depth so that level indices remain stable and BucketKey needs no change.
func (*Hierarchy) Children ¶ added in v0.26.0
Children returns the levels whose parent is i, ascending.
func (*Hierarchy) CoarsestLeafFor ¶ added in v0.26.0
CoarsestLeafFor returns the leaf whose buckets are coarsest among those that still fit inside [from, to) — the best starting point for a fold. Falls back to the root when no leaf bucket fits.
func (*Hierarchy) Leaves ¶ added in v0.26.0
Leaves returns the levels with no children — the COARSEST grain on each branch (year on the month branch, week on the week branch). A fold starts at whichever leaf best tiles the requested window and descends toward the root.
type MaxFloat64 ¶
type MaxFloat64 struct{}
MaxFloat64 is ts's maximum fold, same identity treatment.
func (MaxFloat64) Combine ¶
func (MaxFloat64) Combine(a, b MinValue) MinValue
func (MaxFloat64) Identity ¶
func (MaxFloat64) Identity() MinValue
type MemStore ¶
type MemStore[T any] struct { // contains filtered or unexported fields }
MemStore is the in-memory BucketStore: the test vehicle and the small-consumer default. Not safe for concurrent use — the engine's single-writer discipline is the consumer's to enforce (@C04a).
func NewMemStore ¶
NewMemStore constructs an empty in-memory store.
func (*MemStore[T]) RangeLevel ¶ added in v0.16.13
RangeLevel visits existing buckets at level with Start in [from, to), ascending. The map is unordered, so keys are collected and sorted — fine for the test/small-consumer role; durable stores use an ordered scan natively.
type MinFloat64 ¶
type MinFloat64 struct{}
func (MinFloat64) Combine ¶
func (MinFloat64) Combine(a, b MinValue) MinValue
func (MinFloat64) Identity ¶
func (MinFloat64) Identity() MinValue
type MinValue ¶
MinFloat64 is ts's minimum fold, with +Inf-free identity handling via a validity flag: the identity is "no value yet".
type Monoid ¶
type Monoid[T any] interface { // Identity returns the neutral element: Combine(Identity(), x) == x. Identity() T // Combine folds two values. Must be associative: // Combine(a, Combine(b, c)) == Combine(Combine(a, b), c). Combine(a, b T) T }
Monoid is the algebraic parameter of the cascade: an associative Combine with an Identity element. Associativity and identity are laws the implementation must satisfy — they are property-tested per instantiation in this package, not assumed.
type OracleResult ¶ added in v0.16.13
type OracleResult struct {
Name string
Equal bool
// FirstDivergence describes the first differing line when not equal:
// "line N: derived=... current=..." — enough to localise, not a full
// diff (fingerprints are available to the caller for that).
FirstDivergence string
Derived string
Current string
}
OracleResult reports one oracle's outcome.
func CheckAll ¶ added in v0.16.13
func CheckAll(ctx context.Context, oracles []RebuildOracle) ([]*OracleResult, error)
CheckAll runs a set of oracles, failing fast only on execution errors — divergences are results, not errors, so one broken invariant does not hide another's report.
type RebuildOracle ¶ added in v0.16.13
type RebuildOracle struct {
// Name identifies the oracle in reports, e.g. "cal.index",
// "graph.edges", "ts.rollups".
Name string
// Derive replays the authoritative record (journal, source table)
// into the canonical fingerprint of the state it implies.
Derive func(ctx context.Context) (string, error)
// Current serialises the live derived state into the same canonical
// form.
Current func(ctx context.Context) (string, error)
}
RebuildOracle names one derived-state invariant for one primitive.
func (RebuildOracle) Check ¶ added in v0.16.13
func (o RebuildOracle) Check(ctx context.Context) (*OracleResult, error)
Check runs one oracle.
type SealedError ¶ added in v0.16.13
SealedError reports a mutation refused because its span touches the sealed (immutable) past.
func (*SealedError) Error ¶ added in v0.16.13
func (e *SealedError) Error() string
type Sealer ¶ added in v0.16.13
type Sealer struct {
// contains filtered or unexported fields
}
Sealer manages a monotone seal frontier over a window tiling, and serialises frontier advance against guarded mutations. The zero frontier means nothing is sealed.
func (*Sealer) AdvanceTo ¶ added in v0.16.13
AdvanceTo advances the frontier to now (monotone: moving backward is a no-op). Sealing is a logical freeze — the frontier IS the seal; no per-window rewrite happens here (cal's model, kept: a physical cold move is a consumer/store concern).
func (*Sealer) Frontier ¶ added in v0.16.13
Frontier returns the current seal frontier. Windows ending at or before it are immutable.
func (*Sealer) Guard ¶ added in v0.16.13
Guard runs fn under the seal lock iff the span [from, to) touches no sealed window; otherwise it returns *SealedError and fn never runs. This is the lifted serialisation discipline: Guard and AdvanceTo are mutually exclusive, so the seal observes only fully-applied states and mutations never land in the immutable past.
fn runs WITH the lock held — it must be the consumer's short critical section (the index write, the bucket update), not long I/O. cal's hazard analysis applies verbatim: the one operation touching two planes must sit entirely inside the guard or the interleaving returns.
type SumFloat64 ¶
type SumFloat64 struct{}
SumFloat64 is ts's additive fold: (float64, +, 0).
func (SumFloat64) Combine ¶
func (SumFloat64) Combine(a, b float64) float64
func (SumFloat64) Identity ¶
func (SumFloat64) Identity() float64
type SumInt64 ¶
type SumInt64 struct{}
SumInt64 is bal's conservation fold: (int64, +, 0). Balance-as-of is this monoid chained across sealed checkpoints (@C03).
type TemporalPolicy ¶ added in v0.26.0
type TemporalPolicy string
TemporalPolicy is a chronicle-based timeline's declared arrival-order contract (T-55). One vocabulary across every primitive that keeps a chronicle timeline (/bal accounts, /ts timelines, /cal calendars); each primitive stores the value in its OWN guard plane — a column on the timeline's authoritative row, read inside the transaction of the write it governs — never in /meta (@C04c: guards do not read meta).
const ( // AppendOnly is the default: accounting-style. An entry dated // strictly before the timeline's latest recorded entry is refused // by the primitive's guard with the primitive's own error. // Same-instant entries are admitted — batches and multi-leg writes // legitimately share a timestamp, and refusing them would make the // policy unusable at second granularity. (Deviation from T-55's // filed "at-or-before" wording, recorded there.) AppendOnly TemporalPolicy = "append_only" // Backdated admits entries in any arrival order — museum records, // wikipedia-style timelines, facts of the past arriving as found. // Under this policy the primitive's checkpoint-invalidation // machinery is active: a write dated at-or-before an existing // checkpoint marks that checkpoint and every later one stale // (lazy; recomputed on the next Checkpoint call, skipped by // as-of reads meanwhile). Backdated TemporalPolicy = "backdated" )
func ParsePolicy ¶ added in v0.26.0
func ParsePolicy(s string) (TemporalPolicy, error)
ParsePolicy validates a stored or supplied policy string. The empty string is the default (AppendOnly) so that pre-policy rows and zero-value definitions get accounting semantics without migration.
func (TemporalPolicy) CheckAdmission ¶ added in v0.26.0
func (p TemporalPolicy) CheckAdmission(at, latest time.Time) error
CheckAdmission applies the policy to a candidate entry instant given the timeline's latest recorded instant (zero time when the timeline is empty). Returns nil to admit, ErrBackdatedRefused (wrapped with both instants) to refuse. Pure function: primitives that fold the predicate into SQL for write-first transactions must implement the SAME rule — strictly-earlier refused, same-instant admitted — and their conformance tests should assert agreement with this function.
type TestingT ¶ added in v0.16.13
type TestingT interface {
Helper()
Fatalf(format string, args ...interface{})
Logf(format string, args ...interface{})
}
TestingT is the subset of *testing.T the assertion helper needs; an interface so the harness does not import testing (tooling links this package too).
type TreeSpec ¶ added in v0.26.0
type TreeSpec struct {
Grain Grain
Parent string // parent grain's Name, or "" if this is the root
}
TreeSpec declares one grain and the name of its parent ("" for the root). Order is free; the constructor resolves names.
type WindowFn ¶ added in v0.16.13
WindowFn maps an instant to the half-open window [start, end) containing it, in UTC. Windows must tile time: contiguous, non-overlapping, end(t) == start of the next window. cal instantiates UTC days; bal instantiates calendar months; fixed-width consumers use GrainWindows.
func GrainWindows ¶ added in v0.16.13
GrainWindows adapts a fixed-width Grain to a WindowFn.
Source Files