D Donkeh docs
GitHub

Data

Donkeh.Data is deliberately generic. It does not know how to parse CSS and it does not know how to paint; it describes the relationships between tokens, selectors, declarations and conditions. The representation is a set of flat tables whose columns are almost entirely integer ids into interned values or other tables.

The core idea: relationships as ids

A stylesheet is a graph: a selector owns declarations, a declaration references a property and a value, a rule may be gated by a condition, and a condition may be nested inside another. The obvious object model gives every node a class and every edge a reference. That is pleasant to debug and expensive to hold in memory.

Donkeh stores the graph as parallel lists. A rule is a Rule value with five integers: selector id, property id, value id, condition id and layer id. A selector record points into a shared token arena. A condition is a compiled delegate plus a parent id. There are no per-rule objects, no per-selector token arrays and no string fields in the hot structures.

public readonly struct Rule
{
    public required int SelectorId { get; init; }  // -> DataTable.Selectors
    public required int PropertyId { get; init; }  // -> interned "background-color"
    public required int ValueId    { get; init; }  // -> interned "#fff"
    public int ConditionId { get; init; } = -1;    // -> DataTable.Conditions
    public int LayerId     { get; init; } = -1;    // -> DataTable.Layers
}

A rule is 20 bytes. Every negative id is an absent optional edge. Resolving a rule to text is a lookup in InternTable, not a pointer chase through a tree of small heap objects. The table itself is append-only while parsing, so ids are dense, stable and safe to use as array indices.

What lives in the table

TableRecordPurpose
SelectorsSelectorRecordToken-arena slice, primary discriminator, packed specificity, compound slice, matchable flag, pseudo-element.
RulesRuleDeclaration edges: selector, property, value, condition and layer ids.
ConditionsConditionCompiled predicate, parent id and shared executor id.
Imports, Namespaces, Layers, Scopessmall id recordsAt-rule metadata preserved for the host and cascade ordering.
Keyframes, Descriptors, MarginBoxes, Charsetssmall id recordsKeyframe stops and descriptor blocks without attaching them to normal selectors.
Selector / condition token arenasToken[]One flat token buffer for all selectors and one for all condition preludes.
Compound / filter / pseudo arenasvalue recordsSelector analysis stored once, so matching never re-parses selector tokens.

The SelectorRecord is the best example of the pattern. It does not own its tokens or compounds. It stores TokenOffset and TokenLength into the table's selector-token arena, plus CompoundOffset and CompoundCount into the compound arena. Attribute filters and pseudo classes are similarly sliced out of table-wide arenas. A table with thousands of selectors has a handful of large arrays instead of thousands of small ones.

Arenas and intrusive lists

Collision chains are not List<int> per hash bucket. The table keeps a dictionary from key to head id and a parallel _next list; the head is the newest entry and every record points at the previous one. Selector hash buckets, condition buckets, executor buckets, discriminator buckets, attribute-name buckets and per-selector rule chains all use the same trick. That removes one allocation per bucket and keeps traversal inside two contiguous arrays.

_discriminatorHeads: { key → newest selector id } │ ├── selector 42 → selector 17 → selector 9 → -1 │ _discriminatorNext[42] = 17 │ _discriminatorNext[17] = 9 │ _discriminatorNext[9] = -1 └── key = (TokenKind.Identifier, interned "btn")

Why it is small

The memory benchmark reports a 7.46× improvement over the object-per-node representation. The saving is structural, not a micro optimisation:

RecordApproximate sizeWhat dominates
Rule20 BFive 32-bit ids.
Token12 BKind, interned text id, packed 24-bit start + 8-bit length.
Conditiondelegate ref + 8 BShared ConditionFunction, parent id, executor id.
AttributeFilter~12 BName id, value id, byte operator, bool flag.
PseudoRecord~20 BKind, An+B terms and :not() argument slice.

On Bootstrap 5.3.8 the pipeline sees 232,108 characters, 46,438 tokens, 2,762 unique selectors, 6,496 rules and 18 conditions. Build time is roughly 13 ms in the debugger’s release run, with 2.4 MB of transient allocation for tokens and parsing. Those allocations are the build cost; the flattened table is what survives.

Conditions are delegates

Condition is where the design becomes unusually direct. A condition does not store an expression tree, an operator enum or a list of feature values to interpret later. It stores a compiled ConditionFunction:

public delegate bool ConditionFunction(in RendererContext context);

public readonly struct Condition
{
    public required ConditionFunction Executor { get; init; }
    public int ParentId { get; init; } = -1;
    public int ExecutorId { get; init; }
}

The compiler is called once per distinct prelude. Media queries become a small immutable closure that compares fields on RendererContext; @supports and @container can be supplied by a different compiler. The rule builder stores the resulting delegate reference and a condition id. At match time the engine calls the delegate — there is no re-parsing and no interpretation of the query text.

MechanismWhy it is fast
Compile once per preludeThe token scan, feature parsing and closure creation happen during stylesheet build, not per node.
Shared executorsConditions are interned by (tokens, parent); executors are interned by tokens alone, so a responsive query compiles once even when nested in many scopes.
Delegate call per conditionbool (in RendererContext) is a direct call with no allocation and no virtual expression walk.
Parent-chain short circuitA nested rule evaluates its innermost condition and stops at the first failure.
Version-stamped cacheResults are memoised per table and RendererContext.Version; every rule sharing a query pays for it once per environment change.
Fail closedA missing compiler, a null result or a thrown exception becomes AlwaysFalse, never an accidental match.

Condition.AlwaysTrue and AlwaysFalse are static delegates, and AlwaysTrueCompiler is useful for tests and for builds that do not need media-query filtering. The cache is deliberately conservative: a new context instance or a changed version invalidates it, so results are never shared across environments.

Selector analysis at intern time

Interning a selector is the expensive moment, and it happens once. A single pass splits the token sequence into compounds on combinators and descendant gaps, tracks bracket/parenthesis depth so operators inside [attr^=v] and :nth-child() are not mistaken for combinators, parses attribute filters and pseudo classes, and computes specificity.

This is why matching does not have to re-tokenize or re-analyze anything. The selector record already contains the plan: compounds, filters, pseudo records, combinator links and specificity.

Matching as a table lookup

MatchRules does not scan every selector. It collects candidate ids from the node's own interned keys:

  1. id, tag name, every class name and the universal bucket;
  2. attribute-name buckets for selectors whose subject is an attribute;
  3. the small list of structural pseudo-class subjects.

Every probe is an integer dictionary lookup and an intrusive-list walk. The subject compound is verified first, then the selector is walked right to left through the compound plan. Only after a selector matches are its rules walked through the per-selector rule chain. Conditions are filtered last, so a rule gated by a media query does not pay for the condition until its selector has already matched.

The result is sorted weakest first: layer order, then specificity, then source order. Applying rules in that order lets later declarations win exactly as the cascade requires. The span overload writes into a caller-provided buffer and reuses table scratch lists, which is the allocation-free path used by the renderer.

Bootstrap 5.3.8 measurementResult
Stylesheet232,108 characters, 46,438 tokens
Selectors / rules / conditions2,762 / 6,496 / 18
Build time~13 ms, ~17.7 MB/s, 2.4 MB transient allocation
Matching a 4,512-element page~4.25 µs/node, ~56,500 matches per pass
Hot leaf / cold leaf~8.25 µs (53 matches) / ~3.54 µs (1 match)
Retained-memory benchmark7.46× improvement over the object-per-node baseline

Trade-offs and sharp edges

DecisionCost
Ids instead of referencesEvery debugging session needs the intern table to turn an id back into text. Id 0 is a valid token; -1 is the absent sentinel.
Flat arenasGrowing an arena invalidates previously returned spans. Re-read through GetSelectorSpan instead of caching the span.
Append-only recordsThere is no general deletion. The inspector can edit a rule value or property in place; removing a selector would invalidate ids and is not supported.
Global intern tableStable ids for the process, but the table grows with distinct text and is never evicted.
Shared scratch buffersMatching is not re-entrant and the table is not thread-safe while being mutated.
Build-time allocationThe flattened result is compact, but parsing and interning still allocate tokens, lists and distinct strings. The 2.4 MB Bootstrap number is transient build cost.
Fail-closed conditionsAn unsupported query silently disables its rules. That is safer than applying styles the engine cannot verify, but it can look like a missing rule.

Code tour

FileRead it for…
Data/Source/DataTable.csAll tables, arenas, candidate indexes and the condition cache.
Data/Source/DataTable.Matching.csCandidate collection, right-to-left selector verification and cascade ordering.
Data/Source/Rule.csThe 20-byte declaration edge.
Data/Source/SelectorRecord.csThe selector slice and packed specificity.
Data/Source/Dom/SelectorAnalysis.csOne-pass compound splitting, filter parsing, pseudo parsing and specificity.
Data/Source/Dom/SelectorPlan.csCompound, combinator and pseudo records stored in shared arenas.
Data/Source/Condition.csConditionFunction, shared executors and fail-closed defaults.
DataEngine/Source/MediaConditionCompiler.csThe media-query compiler that produces the delegate.

The short version: the parser gives Data a stream of interned tokens; Data turns those tokens into a compact relationship graph of integer edges. Matching then works almost entirely by indexing, filtering and calling already-compiled predicates, rather than by interpreting a stylesheet-shaped object graph.