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
| Table | Record | Purpose |
|---|---|---|
Selectors | SelectorRecord | Token-arena slice, primary discriminator, packed specificity, compound slice, matchable flag, pseudo-element. |
Rules | Rule | Declaration edges: selector, property, value, condition and layer ids. |
Conditions | Condition | Compiled predicate, parent id and shared executor id. |
Imports, Namespaces, Layers, Scopes | small id records | At-rule metadata preserved for the host and cascade ordering. |
Keyframes, Descriptors, MarginBoxes, Charsets | small id records | Keyframe stops and descriptor blocks without attaching them to normal selectors. |
| Selector / condition token arenas | Token[] | One flat token buffer for all selectors and one for all condition preludes. |
| Compound / filter / pseudo arenas | value records | Selector 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.
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:
- Values, not objects. A rule is a 20-byte struct in one list; there is no object header, no reference field and no per-rule allocation.
- Strings are interned once. Repeated properties and values such as
color,display,0,blockand#fffare one id each, regardless of how many declarations use them. - Selectors share arenas. Tokens live in one buffer. A selector record is an offset/length pair, not a token array.
- Analysis is stored once. Compounds, parsed attribute filters, pseudo records and the An+B values are produced when a selector is interned, not re-derived per match.
- Identical selectors are deduplicated.
.a .bwritten twice is one selector with two rules; whitespace around explicit combinators normalises to the same token sequence. - Executors are shared. The same media query under different parents compiles once; condition records differ only by parent id and delegate reference.
- Adjacent duplicate rules collapse. A flattened selector list that produces the same declaration twice stores it once when it is adjacent in source order.
| Record | Approximate size | What dominates |
|---|---|---|
Rule | 20 B | Five 32-bit ids. |
Token | 12 B | Kind, interned text id, packed 24-bit start + 8-bit length. |
Condition | delegate ref + 8 B | Shared ConditionFunction, parent id, executor id. |
AttributeFilter | ~12 B | Name id, value id, byte operator, bool flag. |
PseudoRecord | ~20 B | Kind, 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.
| Mechanism | Why it is fast |
|---|---|
| Compile once per prelude | The token scan, feature parsing and closure creation happen during stylesheet build, not per node. |
| Shared executors | Conditions 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 condition | bool (in RendererContext) is a direct call with no allocation and no virtual expression walk. |
| Parent-chain short circuit | A nested rule evaluates its innermost condition and stops at the first failure. |
| Version-stamped cache | Results are memoised per table and RendererContext.Version; every rule sharing a query pays for it once per environment change. |
| Fail closed | A 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.
- Specificity is packed into one integer: 10 bits for ids, 10 for classes/attributes/pseudo-classes and 10 for types. It is computed once and read as an integer during sorting.
- The right-most token becomes the
PrimaryDiscriminator, normalised so identifiers, property names and function names share one bucket. IsMatchableis false for unsupported constructs. The selector is still stored for inspection, but matching never returns a wrong positive.::before/::afterare recorded separately, letting the host skip generated-content matching entirely when a sheet never uses it.- Selectors whose subject is an attribute selector are indexed by the attribute name; structural pseudo-class subjects go into a small unkeyed list.
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:
- id, tag name, every class name and the universal bucket;
- attribute-name buckets for selectors whose subject is an attribute;
- 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 measurement | Result |
|---|---|
| Stylesheet | 232,108 characters, 46,438 tokens |
| Selectors / rules / conditions | 2,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 benchmark | 7.46× improvement over the object-per-node baseline |
Trade-offs and sharp edges
| Decision | Cost |
|---|---|
| Ids instead of references | Every 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 arenas | Growing an arena invalidates previously returned spans. Re-read through GetSelectorSpan instead of caching the span. |
| Append-only records | There 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 table | Stable ids for the process, but the table grows with distinct text and is never evicted. |
| Shared scratch buffers | Matching is not re-entrant and the table is not thread-safe while being mutated. |
| Build-time allocation | The 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 conditions | An 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
| File | Read it for… |
|---|---|
Data/Source/DataTable.cs | All tables, arenas, candidate indexes and the condition cache. |
Data/Source/DataTable.Matching.cs | Candidate collection, right-to-left selector verification and cascade ordering. |
Data/Source/Rule.cs | The 20-byte declaration edge. |
Data/Source/SelectorRecord.cs | The selector slice and packed specificity. |
Data/Source/Dom/SelectorAnalysis.cs | One-pass compound splitting, filter parsing, pseudo parsing and specificity. |
Data/Source/Dom/SelectorPlan.cs | Compound, combinator and pseudo records stored in shared arenas. |
Data/Source/Condition.cs | ConditionFunction, shared executors and fail-closed defaults. |
DataEngine/Source/MediaConditionCompiler.cs | The 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.