tiny.css.bucket

1/// The most classes one element may report to a compound test.2pub const max_element_classes: u32 = 64;

1//! The rule bucket index: one sorted entry per selector, keyed by the strongest2//! key its rightmost compound carries.3//!4//! Matching an element against a whole sheet is a walk over every selector only5//! if nothing narrows the candidates first. A selector whose rightmost compound6//! names an id, a class, a role, or an element type can only match an element7//! carrying that key, so the index groups selectors by key and an element tests8//! its own keys plus the universal group. The groups are one sorted array with9//! a binary search, so the index is a flat block with no pointers.10//!11//! The index also answers the question a style sharing cache asks before it12//! reuses a computed style: whether a mutation somewhere above or beside an13//! element can change what matches. `Summary` holds conservative Bloom words14//! over the atoms that appear left of a combinator, plus the two bits that15//! say a sheet uses sibling combinators or positional pseudo-classes at all.16//! `Summary` also holds `ancestor_pseudo`, an exact `u32` bitset over the17//! thirty `PseudoClass` values rather than a Bloom word. A set bit names a18//! pseudo-class some selector puts left of a combinator, and a clear bit19//! rules that pseudo-class out.2021const std = @import("std");22const alloc_phase = @import("alloc_phase");2324const atom = @import("atom.zig");25const match = @import("match/root.zig");26const selector = @import("selector/root.zig");27const sheet = @import("sheet.zig");2829const Allocator = std.mem.Allocator;3031/// The key spaces a bucket entry lives in, in the order the index sorts them.32pub const Space = enum(u8) {33    universal = 0,34    kind = 1,35    role = 2,36    class = 3,37    identifier = 4,38};3940/// One selector's place in the index.41pub const Entry = extern struct {42    key: u32 = 0,43    rule: u32 = 0,44    selector: u32 = 0,45    space: u8 = @backingInt(Space.universal),4647    fn before(left: Entry, right: Entry) bool {48        if (left.space != right.space) return left.space < right.space;49        if (left.key != right.key) return left.key < right.key;50        if (left.rule != right.rule) return left.rule < right.rule;51        return left.selector < right.selector;52    }53};5455/// The bound one sheet produces, which is its selector count.56pub const Limits = struct {57    entries: usize = 0,5859    /// Counts the entries `parsed` needs without writing one.60    pub fn inspect(parsed: *const sheet.StyleSheet) Limits {61        var total: usize = 0;62        for (parsed.rules) |rule| total += rule.selectors.len;63        return .{ .entries = total };64    }6566    pub fn grow(left: Limits, right: Limits) Limits {67        return .{ .entries = @max(left.entries, right.entries) };68    }69};7071/// The byte layout one `Limits` produces.72pub const Capacity = struct {73    entries: usize = 0,74    total_bytes: usize = 0,7576    pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {77        const bytes = std.math.mul(usize, limits.entries, @sizeOf(Entry)) catch78            return error.CapacityOverflow;79        return .{ .entries = limits.entries, .total_bytes = bytes };80    }81};8283const LimitsType = Limits;84const CapacityType = Capacity;8586/// The alignment the index block is acquired at.87pub const storage_alignment: usize = @alignOf(Entry);8889/// The sorted entries plus the sheet arrays a match walk reads.90pub const Index = struct {91    entries: []const Entry = &.{},92    source: *const sheet.StyleSheet,9394    /// The entries in one key space, or an empty slice when the sheet has none.95    pub fn group(self: Index, space: Space, key: u32) []const Entry {96        const wanted = Entry{ .space = @backingInt(space), .key = key };97        var low: usize = 0;98        var high: usize = self.entries.len;99        while (low < high) {100            const middle = low + (high - low) / 2;101            if (Entry.before(self.entries[middle], wanted)) low = middle + 1 else high = middle;102        }103        var end = low;104        while (end < self.entries.len and105            self.entries[end].space == wanted.space and106            self.entries[end].key == key) : (end += 1)107        {}108        return self.entries[low..end];109    }110111    fn selectorAt(self: Index, entry: Entry) selector.Selector {112        const rule = self.source.rules[entry.rule];113        return rule.selectors[entry.selector];114    }115};116117/// The outcome of one element's candidate walk.118pub const Gather = struct {119    count: u32 = 0,120    rejected: u32 = 0,121};122123/// The most classes one element carries into a candidate walk.124pub const max_element_classes: u32 = match.max_element_classes;125126/// Writes every selector in `index` that matches `node` into `out`, ordered by127/// source order and then specificity. Candidates past `out` are rejected and128/// counted rather than dropped silently.129pub fn matchElement(130    index: Index,131    element: match.Element,132    node: u32,133    out: []match.Match,134) Gather {135    var found = Gather{};136    const context = index.source.context();137    collect(index, context, element, node, out, &found, .universal, 0);138    const kind = element.kind(element.context, node);139    if (kind != 0) collect(index, context, element, node, out, &found, .kind, kind);140    const role = element.role(element.context, node);141    if (role != 0) collect(index, context, element, node, out, &found, .role, role);142    const identifier = element.identifier(element.context, node);143    if (identifier != atom.none) collect(index, context, element, node, out, &found, .identifier, identifier);144    var held: [max_element_classes]u32 = undefined;145    const classes = element.classes(element.context, node, &held, max_element_classes);146    std.debug.assert(classes <= max_element_classes);147    for (held[0..classes]) |class| {148        collect(index, context, element, node, out, &found, .class, class);149    }150    std.mem.sort(match.Match, out[0..found.count], {}, earlier);151    return found;152}153154fn collect(155    index: Index,156    context: match.Context,157    element: match.Element,158    node: u32,159    out: []match.Match,160    found: *Gather,161    space: Space,162    key: u32,163) void {164    for (index.group(space, key)) |entry| {165        const item = index.selectorAt(entry);166        if (!match.matches(context, item, element, node)) continue;167        if (found.count == out.len) {168            found.rejected += 1;169            continue;170        }171        out[found.count] = .{172            .rule = entry.rule,173            .selector = entry.selector,174            .specificity = item.specificity,175            .order = @intCast(index.source.rules[entry.rule].source_order),176        };177        found.count += 1;178    }179}180181fn earlier(_: void, left: match.Match, right: match.Match) bool {182    if (left.order != right.order) return left.order < right.order;183    return left.specificity.compare(right.specificity) == .lt;184}185186fn keyOf(item: selector.Selector) Entry {187    return switch (item.bucket) {188        .universal => .{ .space = @backingInt(Space.universal), .key = 0 },189        .kind => |key| .{ .space = @backingInt(Space.kind), .key = key },190        .role => |key| .{ .space = @backingInt(Space.role), .key = key },191        .class => |key| .{ .space = @backingInt(Space.class), .key = key },192        .id => |key| .{ .space = @backingInt(Space.identifier), .key = key },193    };194}195196/// Fills `entries` from `parsed` and returns the sorted index.197pub fn build(entries: []Entry, parsed: *const sheet.StyleSheet) Index {198    var used: usize = 0;199    for (parsed.rules, 0..) |rule, rule_index| {200        for (rule.selectors, 0..) |item, selector_index| {201            std.debug.assert(used < entries.len);202            var entry = keyOf(item);203            entry.rule = @intCast(rule_index);204            entry.selector = @intCast(selector_index);205            entries[used] = entry;206            used += 1;207        }208    }209    std.mem.sort(Entry, entries[0..used], {}, lessThan);210    return .{ .entries = entries[0..used], .source = parsed };211}212213fn lessThan(_: void, left: Entry, right: Entry) bool {214    return Entry.before(left, right);215}216217/// What a mutation must carry before it can change what a sheet matches.218///219/// The Bloom words are conservative: a set bit means some selector names an220/// atom that folds onto that bit left of a combinator, so a consumer that sees221/// a clear bit knows no ancestor change with that atom can matter.222pub const Summary = struct {223    ancestor_kinds: u64 = 0,224    ancestor_roles: u64 = 0,225    ancestor_classes: u64 = 0,226    ancestor_ids: u64 = 0,227    /// A set bit means some selector names that pseudo-class left of a228    /// combinator, and a clear bit means no selector does. The word is an exact229    /// set rather than a conservative Bloom word, unlike the Bloom words above230    /// this field.231    ancestor_pseudo: u32 = 0,232    sibling_sensitive: bool = false,233    positional: bool = false,234235    /// Whether an ancestor carrying `id` in `space` can change matching.236    pub fn ancestorSensitive(self: Summary, space: Space, id: u32) bool {237        const word = switch (space) {238            .universal => return true,239            .kind => self.ancestor_kinds,240            .role => self.ancestor_roles,241            .class => self.ancestor_classes,242            .identifier => self.ancestor_ids,243        };244        return word & bit(id) != 0;245    }246247    /// This predicate returns whether ancestor_pseudo carries248    /// selector.bit(class). The check answers whether any rule in the sheet249    /// puts the given pseudo-class above a subject, such as :hover in250    /// .row:hover .cell. The alternative is rescanning every selector in the251    /// stylesheet.252    pub fn ancestorPseudoSensitive(self: Summary, class: selector.PseudoClass) bool {253        const word = selector.bit(class);254        std.debug.assert(word != 0);255        return self.ancestor_pseudo & word != 0;256    }257};258259fn bit(id: u32) u64 {260    return @as(u64, 1) << @truncate(id);261}262263/// Folds every selector in `parsed` into one conservative summary.264pub fn summarize(parsed: *const sheet.StyleSheet) Summary {265    var out = Summary{};266    for (parsed.rules) |rule| {267        for (rule.selectors) |item| {268            for (item.combinators) |joint| {269                if (joint == .next_sibling or joint == .subsequent_sibling) out.sibling_sensitive = true;270            }271            for (item.compounds, 0..) |compound, position| {272                if (compound.nth != 0) out.positional = true;273                if (position + 1 == item.compounds.len) continue;274                absorb(&out, parsed, compound);275            }276        }277    }278    return out;279}280281fn absorb(out: *Summary, parsed: *const sheet.StyleSheet, compound: selector.Compound) void {282    out.ancestor_pseudo |= compound.pseudo;283    if (compound.kind != 0) out.ancestor_kinds |= bit(compound.kind);284    if (compound.role != 0) out.ancestor_roles |= bit(compound.role);285    if (compound.id != atom.none) out.ancestor_ids |= bit(compound.id);286    var index: u32 = 0;287    while (index < compound.class_count) : (index += 1) {288        out.ancestor_classes |= bit(parsed.classes[compound.class_first + index]);289    }290}291292/// The single aligned block one bucket index owns.293pub const Storage = struct {294    pub const Limits = LimitsType;295    pub const Capacity = CapacityType;296297    pub const claim: alloc_phase.capacity.Declaration = .{298        .source = .{299            .id = "css.bucket_index",300            .kind = .phase_static,301            .limit_source = .caller,302            .storage = .{303                .covered = &.{304                    .{305                        .id = "flat_sorted_bucket_entry_output",306                        .lifetime = .steady,307                        .detail = "flat sorted rule bucket entry output, one entry per sheet selector",308                    },309                },310                .excluded = &.{311                    "stylesheet placement holding the rules and selectors the entries address",312                    "caller-owned matched rule output buffer",313                },314            },315            .capacity = .{316                .inputs = &.{317                    alloc_phase.capacity.bindInput(LimitsType, "entries", "entries"),318                },319                .type_selectors = &.{320                    alloc_phase.capacity.bindType(Entry, "entry"),321                },322                .nodes = &.{323                    .{ .input = 0 },324                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },325                    .{ .constant = 0 },326                    .{ .alignment = .{ .node = 2, .alignment = .{ .concrete_type = 0 } } },327                    .{ .add = .{ .left = 3, .right = 1 } },328                    .{ .alignment = .{ .node = 4, .alignment = .{ .literal = 16 } } },329                },330                .assertions = &.{.{331                    .scope = .closure_total,332                    .measure = .retained,333                    .relation = .exact,334                    .expression = 5,335                }},336            },337            .overload = .{338                .kind = .reject_before_seal,339                .detail = "the entry count is the sheet selector count, which is known before acquisition; filling and sorting the admitted block performs no allocation",340            },341            .risks = .{342                .transitive = .{343                    .status = .open,344                    .detail = "the sort and the match walk are allocation-free and witnessed but lack a machine-checked call-graph closure certificate",345                },346                .foreign = .{347                    .status = .excluded,348                    .detail = "indexing and matching are process-local transformations with no operating-system edge",349                },350            },351            .obligations = &.{352                .{ .key = "css_bucket_capacity_model", .role = .capacity_model },353                .{ .key = "css_bucket_overload", .role = .overload },354                .{ .key = "css_bucket_acquisition", .role = .custom },355                .{ .key = "css_bucket_steady_overload", .role = .overload },356                .{ .key = "css_bucket_steady_foreign_risk", .role = .foreign_risk },357            },358        },359        .bindings = .{360            .owner = @This(),361            .seal = .{362                .family = alloc_phase.capacity.selector(@This().activate),363                .premise = .{364                    .class = .checked_semantic_fact,365                    .authority = .checker,366                },367            },368            .teardown = .{369                .family = alloc_phase.capacity.selector(@This().deinit),370                .premise = .{371                    .class = .checked_semantic_fact,372                    .authority = .checker,373                },374            },375        },376    };377378    phase: alloc_phase.capacity.Phase,379    limits: LimitsType,380    capacity: CapacityType,381    bytes: []align(storage_alignment) u8,382    entries: []Entry,383384    pub fn init(allocator: Allocator, limits: LimitsType) !Storage {385        const capacity = try CapacityType.derive(limits);386        const bytes = try allocator.alignedAlloc(u8, .fromByteUnits(storage_alignment), capacity.total_bytes);387        return .{388            .phase = .initialization,389            .limits = limits,390            .capacity = capacity,391            .bytes = bytes,392            .entries = entrySlice(bytes, capacity.entries),393        };394    }395396    pub fn activate(self: *Storage) void {397        std.debug.assert(self.phase == .initialization);398        self.assertStorage();399        self.phase = .steady;400    }401402    pub fn admits(self: *const Storage, limits: LimitsType) bool {403        std.debug.assert(self.phase == .steady);404        return limits.entries <= self.capacity.entries;405    }406407    /// Indexes `parsed`, asserting admission rather than growing.408    pub fn index(self: *Storage, parsed: *const sheet.StyleSheet) Index {409        std.debug.assert(self.phase == .steady);410        std.debug.assert(self.admits(LimitsType.inspect(parsed)));411        return build(self.entries, parsed);412    }413414    pub fn deinit(self: *Storage, allocator: Allocator) void {415        std.debug.assert(self.phase != .teardown);416        self.assertStorage();417        self.phase = .teardown;418        allocator.free(self.bytes);419        self.bytes = &.{};420        self.entries = &.{};421    }422423    fn assertStorage(self: *const Storage) void {424        const expected = CapacityType.derive(self.limits) catch unreachable;425        std.debug.assert(std.meta.eql(expected, self.capacity));426        std.debug.assert(self.bytes.len == self.capacity.total_bytes);427        std.debug.assert(self.entries.len == self.capacity.entries);428    }429};430431comptime {432    alloc_phase.capacity.requireAllocatorExactOwnerShape(Storage);433}434435fn entrySlice(bytes: []u8, count: usize) []Entry {436    if (count == 0) return &.{};437    const region: []align(@alignOf(Entry)) u8 = @alignCast(bytes[0..][0 .. count * @sizeOf(Entry)]);438    return std.mem.bytesAsSlice(Entry, region);439}440441const fixture = @import("match/fixture/tree.zig");442443const Indexed = struct {444    workspace: sheet.Workspace,445    storage: Storage,446    parsed: sheet.StyleSheet = .{},447448    fn init(source: []const u8) !Indexed {449        var workspace = sheet.Workspace.init(std.testing.allocator);450        errdefer workspace.deinit();451        const parsed = try workspace.parse(source, .default());452        var storage = try Storage.init(std.testing.allocator, Limits.inspect(&parsed));453        storage.activate();454        return .{ .workspace = workspace, .storage = storage, .parsed = parsed };455    }456457    fn deinit(self: *Indexed) void {458        self.storage.deinit(std.testing.allocator);459        self.workspace.deinit();460    }461462    fn index(self: *Indexed) Index {463        return self.storage.index(&self.parsed);464    }465};466467fn modelBucketCapacity(limits: Limits) error{CapacityOverflow}!Capacity {468    const total = @as(u128, limits.entries) * @sizeOf(Entry);469    if (total > std.math.maxInt(usize)) return error.CapacityOverflow;470    return .{ .entries = limits.entries, .total_bytes = @intCast(total) };471}472473fn checkBucketStorageInit(allocator: Allocator, limits: Limits) !void {474    var storage = try Storage.init(allocator, limits);475    defer storage.deinit(allocator);476    try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, storage.phase);477}478479test "bucket index capacity matches an independent model" {480    comptime {481        alloc_phase.capacity.record(482            alloc_phase.capacity.witness(Storage, "css_bucket_capacity_model"),483        );484    }485    comptime {486        alloc_phase.capacity.record(alloc_phase.capacity.witness(Storage, "css_bucket_overload"));487    }488489    for ([_]Limits{ .{}, .{ .entries = 1 }, .{ .entries = 4097 } }) |limits| {490        try std.testing.expectEqual(try modelBucketCapacity(limits), try Capacity.derive(limits));491    }492    try std.testing.expectError(error.CapacityOverflow, Capacity.derive(.{ .entries = std.math.maxInt(usize) }));493}494495test "bucket index acquisition retries after every allocation failure" {496    comptime {497        alloc_phase.capacity.record(498            alloc_phase.capacity.witness(Storage, "css_bucket_acquisition"),499        );500    }501502    try std.testing.checkAllAllocationFailures(503        std.testing.allocator,504        checkBucketStorageInit,505        .{Limits{ .entries = 64 }},506    );507}508509test "the bucket index groups selectors by their strongest rightmost key" {510    comptime {511        alloc_phase.capacity.record(512            alloc_phase.capacity.witness(Storage, "css_bucket_steady_overload"),513        );514    }515    comptime {516        alloc_phase.capacity.record(517            alloc_phase.capacity.witness(Storage, "css_bucket_steady_foreign_risk"),518        );519    }520521    var indexed = try Indexed.init(522        \\#main { color: red }523        \\.card { color: red }524        \\article { color: red }525        \\* { color: red }526        \\[role=button] { color: red }527    );528    defer indexed.deinit();529    var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});530    failing.fail_index = failing.alloc_index;531    const built = indexed.index();532    try std.testing.expectEqual(@as(usize, 5), built.entries.len);533    try std.testing.expectEqual(@as(usize, 1), built.group(.universal, 0).len);534    try std.testing.expectEqual(@as(usize, 1), built.group(.kind, indexed.parsed.token("article")).len);535    try std.testing.expectEqual(@as(usize, 1), built.group(.class, indexed.parsed.token("card")).len);536    try std.testing.expectEqual(@as(usize, 1), built.group(.identifier, indexed.parsed.token("main")).len);537    try std.testing.expectEqual(@as(usize, 1), built.group(.role, indexed.parsed.token("button")).len);538    try std.testing.expectEqual(@as(usize, 0), built.group(.kind, indexed.parsed.token("card")).len);539    try std.testing.expect(!failing.has_induced_failure);540}541542test "an element gathers only the candidates its own keys reach" {543    var indexed = try Indexed.init(544        \\article .card { color: red }545        \\#main { color: blue }546        \\span { color: green }547        \\* { color: black }548    );549    defer indexed.deinit();550    const built = indexed.index();551    var tree = fixture.Tree{};552    _ = try tree.add(&indexed.parsed.atoms, 0, "article#main");553    _ = try tree.add(&indexed.parsed.atoms, 1, "span.card");554    tree.finish();555556    var out: [8]match.Match = undefined;557    const leaf = matchElement(built, tree.element(), 1, &out);558    try std.testing.expectEqual(@as(u32, 3), leaf.count);559    try std.testing.expectEqual(@as(u32, 0), leaf.rejected);560    try std.testing.expectEqual(@as(u32, 0), out[0].rule);561    try std.testing.expectEqual(@as(u32, 2), out[1].rule);562    try std.testing.expectEqual(@as(u32, 3), out[2].rule);563564    const root = matchElement(built, tree.element(), 0, &out);565    try std.testing.expectEqual(@as(u32, 2), root.count);566    try std.testing.expectEqual(@as(u32, 1), out[0].rule);567    try std.testing.expectEqual(@as(u32, 3), out[1].rule);568569    var narrow: [1]match.Match = undefined;570    const bounded = matchElement(built, tree.element(), 1, &narrow);571    try std.testing.expectEqual(@as(u32, 1), bounded.count);572    try std.testing.expectEqual(@as(u32, 2), bounded.rejected);573}574575test "the summary records the pseudo classes a sheet raises above a subject" {576    var raised = try Indexed.init(577        \\.row:hover .cell { color: red }578        \\.panel:focus-within .field { color: red }579    );580    defer raised.deinit();581    const above = summarize(&raised.parsed);582    try std.testing.expect(above.ancestorPseudoSensitive(.hover));583    try std.testing.expect(above.ancestorPseudoSensitive(.focus_within));584    try std.testing.expect(!above.ancestorPseudoSensitive(.focus));585    try std.testing.expect(!above.ancestorPseudoSensitive(.active));586587    var subject = try Indexed.init(588        \\.cell:hover { color: red }589        \\.field:focus-within { color: red }590    );591    defer subject.deinit();592    const rightmost = summarize(&subject.parsed);593    try std.testing.expectEqual(@as(u32, 0), rightmost.ancestor_pseudo);594    try std.testing.expect(!rightmost.ancestorPseudoSensitive(.hover));595    try std.testing.expect(!rightmost.ancestorPseudoSensitive(.focus_within));596}597598test "the summary marks ancestor atoms sibling combinators and positions" {599    var indexed = try Indexed.init(600        \\article .card { color: red }601        \\li:nth-child(2) { color: red }602        \\h1 + p { color: red }603    );604    defer indexed.deinit();605    const summary = summarize(&indexed.parsed);606    try std.testing.expect(summary.sibling_sensitive);607    try std.testing.expect(summary.positional);608    try std.testing.expect(summary.ancestorSensitive(.kind, indexed.parsed.token("article")));609    try std.testing.expect(summary.ancestorSensitive(.kind, indexed.parsed.token("h1")));610    try std.testing.expect(!summary.ancestorSensitive(.class, indexed.parsed.token("card")));611    try std.testing.expect(!summary.ancestorSensitive(.kind, indexed.parsed.token("p")));612}

1pub const bucket = @import("bucket.zig");