tiny.ui.style.generation

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const css = @import("css");4const abi = @import("../abi/root.zig");5const tree = @import("../tree/root.zig");6const asset = @import("../asset/root.zig");7const computed = @import("computed.zig");8const element = @import("element.zig");9const share = @import("share.zig");1011const Allocator = std.mem.Allocator;1213pub const Limits = struct {14    nodes: u32 = 16_384,15    distinct_styles: u32 = 224,16    selectors: u32 = 512,17    font_faces: u32 = 32,18    bytes: usize = 2_097_152,19};2021pub const Capacity = struct {22    required_bytes: usize,23    total_bytes: usize,24    storage_bytes: usize,2526    pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {27        const nodes = std.math.mul(usize, limits.nodes, 2 * @sizeOf(NodeState)) catch return error.CapacityOverflow;28        const records = std.math.mul(usize, limits.distinct_styles, 2 * @sizeOf(computed.Record)) catch return error.CapacityOverflow;29        const chain_slots = std.math.mul(usize, limits.distinct_styles, limits.font_faces) catch return error.CapacityOverflow;30        if (chain_slots > std.math.maxInt(u32)) return error.CapacityOverflow;31        const chains = std.math.mul(usize, chain_slots, 2 * @sizeOf(asset.AssetHandle)) catch return error.CapacityOverflow;32        const slots = std.math.mul(usize, std.math.ceilPowerOfTwo(usize, @as(usize, limits.distinct_styles) * 2) catch return error.CapacityOverflow, 2 * @sizeOf(u32)) catch return error.CapacityOverflow;33        const key_slots = std.math.mul(usize, std.math.ceilPowerOfTwo(usize, limits.distinct_styles) catch return error.CapacityOverflow, 2 * @sizeOf(share.KeySlot)) catch return error.CapacityOverflow;34        const entries = std.math.mul(usize, limits.selectors, @sizeOf(css.bucket.Entry) + @sizeOf(css.match.Match)) catch return error.CapacityOverflow;35        const flags = @as(usize, limits.nodes) + @as(usize, limits.distinct_styles) * @sizeOf(u32);36        const word_count = std.math.divCeil(usize, limits.nodes, 64) catch return error.CapacityOverflow;37        const key_words = std.math.mul(usize, word_count, (2 * key_columns + 1) * @sizeOf(u64)) catch return error.CapacityOverflow;38        const node_keys = std.math.mul(usize, limits.nodes, 2 * @sizeOf(u16)) catch return error.CapacityOverflow;39        const sum = nodes;40        const sum2 = std.math.add(usize, sum, records) catch return error.CapacityOverflow;41        const sum3 = std.math.add(usize, sum2, slots) catch return error.CapacityOverflow;42        const sum4 = std.math.add(usize, sum3, entries) catch return error.CapacityOverflow;43        const sum5 = std.math.add(usize, sum4, key_slots) catch return error.CapacityOverflow;44        const tail = std.math.add(usize, flags, key_words) catch return error.CapacityOverflow;45        const tail_with_keys = std.math.add(usize, tail, node_keys) catch return error.CapacityOverflow;46        const tail_with_chains = std.math.add(usize, tail_with_keys, chains) catch return error.CapacityOverflow;47        const tail_with_alignment = std.math.add(usize, tail_with_chains, 80) catch return error.CapacityOverflow;48        const required = std.math.add(usize, sum5, tail_with_alignment) catch return error.CapacityOverflow;49        if (required > limits.bytes) return error.CapacityOverflow;50        return .{ .required_bytes = required, .total_bytes = limits.bytes, .storage_bytes = limits.bytes };51    }52};5354const NodeState = extern struct {55    id: u64 = 0,56    ancestor_classes: u64 = 0,57    style: u32 = 0,58    computed_generation: u32 = 0,59};6061const hover_sensitive: u32 = 0x8000_0000;62const style_mask: u32 = ~hover_sensitive;63const key_columns: usize = 14;6465const ChainSet = struct {66    ids: [128]u64 = undefined,67    occupied: [128]bool = @splat(false),6869    fn position(id: u64) usize {70        const mixed = id *% 0x9e3779b97f4a7c15;71        return @intCast((mixed >> 57) & 127);72    }7374    fn insert(self: *ChainSet, id: u64) void {75        var at = position(id);76        for (0..self.ids.len) |_| {77            if (!self.occupied[at]) {78                self.ids[at] = id;79                self.occupied[at] = true;80                return;81            }82            if (self.ids[at] == id) return;83            at = (at + 1) & 127;84        }85        unreachable;86    }8788    fn contains(self: *const ChainSet, id: u64) bool {89        var at = position(id);90        for (0..self.ids.len) |_| {91            if (!self.occupied[at]) return false;92            if (self.ids[at] == id) return true;93            at = (at + 1) & 127;94        }95        return false;96    }97};9899fn bucketBit(space: css.bucket.Space, name: []const u8) u16 {100    const digest = css.atom.hash(name) ^ (@as(u32, @backingInt(space)) *% 0x9e3779b9);101    return @as(u16, 1) << @intCast(digest % key_columns);102}103104const SelectorKeys = struct { bits: u16, universal: bool };105106fn selectorKeys(index: css.bucket.Index) SelectorKeys {107    var bits: u16 = 0;108    var universal = false;109    for (index.entries) |entry| {110        const space: css.bucket.Space = @fromBackingInt(@intCast(entry.space));111        if (space == .universal) {112            universal = true;113        } else {114            bits |= bucketBit(space, index.source.name(entry.key));115        }116    }117    return .{ .bits = bits, .universal = universal };118}119120pub const Error = error{ DistinctStyleQuota, MatchedRuleQuota, SelectorQuota, CapacityOverflow } || Allocator.Error;121pub const Exhaustion = error{ DistinctStyleQuota, MatchedRuleQuota, SelectorQuota, CapacityOverflow };122const LimitsType = Limits;123const CapacityType = Capacity;124const ExhaustionType = Exhaustion;125126pub const Result = struct {127    restyled: u32 = 0,128    visited: u32 = 0,129    carried: u32 = 0,130    carried_bytes: u64 = 0,131    shared: u32 = 0,132    candidates: u64 = 0,133    ancestor_walks: u64 = 0,134    combinator_candidates: u64 = 0,135};136137pub const Engine = struct {138    pub const Limits = LimitsType;139    pub const Capacity = CapacityType;140    pub const Storage = []align(8) u8;141    pub const storage_alignment: usize = 8;142    pub const InitError = error{CapacityOverflow} || Allocator.Error;143    pub const Exhaustion = ExhaustionType;144    pub const work_limits: alloc_phase.capacity.WorkLimits = .{145        .transition_steps_max = 1,146        .cleanup_steps_per_call_max = 0,147        .cleanup_calls_at_capacity_max = 0,148    };149    pub const claim: alloc_phase.capacity.Declaration = .{150        .source = .{151            .id = "ui.style_engine",152            .kind = .phase_static,153            .limit_source = .caller,154            .storage = .{155                .covered = &.{156                    .{ .id = "computed_style_pools", .lifetime = .steady, .detail = "two bounded record pools, value hash slots, and sixteen-byte sharing keys" },157                    .{ .id = "node_style_generations", .lifetime = .steady, .detail = "two node-state arrays and invalidation occupancy words" },158                    .{ .id = "rule_buckets_and_invalidation", .lifetime = .steady, .detail = "rule entries, match scratch, flags, and style remap" },159                    .{ .id = "authored_font_chains", .lifetime = .steady, .detail = "two bounded chains with one font slot per configured face and distinct style" },160                },161                .excluded = &.{162                    "the caller-owned stylesheet source and parsed sheet placement",163                    "the retained publish envelope owned by ui.publish_store",164                },165            },166            .capacity = .{167                .inputs = &.{alloc_phase.capacity.bindInput(LimitsType, "bytes", "bytes")},168                .type_selectors = &.{},169                .nodes = &.{.{ .input = 0 }},170                .assertions = &.{.{171                    .scope = .closure_total,172                    .measure = .retained,173                    .relation = .exact,174                    .expression = 0,175                }},176            },177            .overload = .{178                .kind = .reject_before_seal,179                .detail = "Capacity.derive rejects an undersized byte budget, font binding rejects a face quota above the chain slots, and a cascade above the distinct style quota leaves the live pool sealed",180            },181            .risks = .{182                .transitive = .{ .status = .open, .detail = "the matcher and resolver accept no allocator, while a machine certificate of their call graphs remains open" },183                .foreign = .{ .status = .excluded, .detail = "cascade and lowering call no foreign runtime" },184            },185            .obligations = &.{186                .{ .key = "ui_style_capacity", .role = .capacity_model },187                .{ .key = "ui_style_acquisition", .role = .acquisition },188                .{ .key = "ui_style_sharing_quota", .role = .overload },189                .{ .key = "ui_style_font_chain", .role = .overload },190                .{ .key = "ui_style_oom", .role = .initialization_failure },191                .{ .key = "ui_style_teardown", .role = .teardown },192            },193        },194        .bindings = .{195            .owner = @This(),196            .seal = .{197                .family = alloc_phase.capacity.selector(@This().activate),198                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },199            },200            .teardown = .{201                .family = alloc_phase.capacity.selector(@This().deinit),202                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },203            },204        },205    };206207    phase: alloc_phase.capacity.Phase,208    capacity: CapacityType,209    bytes: []align(8) u8,210    limits: LimitsType,211    states: [2][]NodeState,212    key_index: [2][]u64,213    key_bits: [2][]u16,214    touched: []u64,215    flags: []u8,216    entries: []css.bucket.Entry,217    matches: []css.match.Match,218    pools: [2]share.Pool,219    remap: []u32,220    live: u1 = 0,221    pool_live: u1 = 0,222    style_epoch: u64 = 0,223    count: u32 = 0,224    node_buffer_addr: usize = 0,225    view_revision: u64 = 0,226    last_view: tree.View = .{},227    selector_count: u32 = 0,228    stylesheet_generation: u32 = 0,229    sheet: ?*const css.StyleSheet = null,230    summary: css.bucket.Summary = .{},231    selector_key_bits: u16 = 0,232    universal_selector: bool = false,233    custom_sheet: bool = false,234    direct_hover: bool = false,235    hover_filter_enabled: bool = true,236    interaction: element.Interaction = .{},237    metrics: computed.Metrics = .{},238    fonts: ?*const asset.Registry = null,239    font_revision: u64 = 0,240    applied_font_revision: u64 = 0,241    applied_font_epoch: u64 = 0,242243    pub fn init(allocator: Allocator, limits: LimitsType) InitError!Engine {244        const capacity = try CapacityType.derive(limits);245        const bytes = try allocator.alignedAlloc(u8, .of(u64), capacity.total_bytes);246        errdefer allocator.free(bytes);247        var arena = std.heap.FixedBufferAllocator.init(bytes);248        const a = arena.allocator();249        const states_a = a.alloc(NodeState, limits.nodes) catch unreachable;250        const states_b = a.alloc(NodeState, limits.nodes) catch unreachable;251        const word_count = std.math.divCeil(usize, limits.nodes, 64) catch unreachable;252        const key_index_a = a.alloc(u64, key_columns * word_count) catch unreachable;253        const key_index_b = a.alloc(u64, key_columns * word_count) catch unreachable;254        const key_bits_a = a.alloc(u16, limits.nodes) catch unreachable;255        const key_bits_b = a.alloc(u16, limits.nodes) catch unreachable;256        const touched = a.alloc(u64, word_count) catch unreachable;257        const flags = a.alloc(u8, limits.nodes) catch unreachable;258        const entries = a.alloc(css.bucket.Entry, limits.selectors) catch unreachable;259        const matches = a.alloc(css.match.Match, limits.selectors) catch unreachable;260        const records_a = a.alloc(computed.Record, limits.distinct_styles) catch unreachable;261        const records_b = a.alloc(computed.Record, limits.distinct_styles) catch unreachable;262        const chain_slots = @as(usize, limits.distinct_styles) * limits.font_faces;263        const chains_a = a.alloc(asset.AssetHandle, chain_slots) catch unreachable;264        const chains_b = a.alloc(asset.AssetHandle, chain_slots) catch unreachable;265        const slot_count = std.math.ceilPowerOfTwo(usize, @as(usize, limits.distinct_styles) * 2) catch unreachable;266        const slots_a = a.alloc(u32, slot_count) catch unreachable;267        const slots_b = a.alloc(u32, slot_count) catch unreachable;268        const key_count = std.math.ceilPowerOfTwo(usize, limits.distinct_styles) catch unreachable;269        const keys_a = a.alloc(share.KeySlot, key_count) catch unreachable;270        const keys_b = a.alloc(share.KeySlot, key_count) catch unreachable;271        const remap = a.alloc(u32, limits.distinct_styles) catch unreachable;272        @memset(slots_a, 0);273        @memset(slots_b, 0);274        return .{275            .phase = .initialization,276            .capacity = capacity,277            .bytes = bytes,278            .limits = limits,279            .states = .{ states_a, states_b },280            .key_index = .{ key_index_a, key_index_b },281            .key_bits = .{ key_bits_a, key_bits_b },282            .touched = touched,283            .flags = flags,284            .entries = entries,285            .matches = matches,286            .pools = .{287                .{ .records = records_a, .slots = slots_a, .keys = keys_a, .chains = chains_a, .font_faces = limits.font_faces },288                .{ .records = records_b, .slots = slots_b, .keys = keys_b, .chains = chains_b, .font_faces = limits.font_faces },289            },290            .remap = remap,291        };292    }293294    pub fn activate(self: *Engine) void {295        std.debug.assert(self.phase == .initialization);296        std.debug.assert(self.bytes.len == self.capacity.storage_bytes);297        self.phase = .steady;298    }299300    /// The registry outlives the engine. A changed registry epoch recomputes301    /// every style that may hold a resolved face handle.302    pub fn setFonts(self: *Engine, registry: ?*const asset.Registry) error{FontChainQuota}!void {303        if (registry) |value| {304            if (value.limits.fonts > self.limits.font_faces) return error.FontChainQuota;305        }306        self.fonts = registry;307        self.font_revision +%= 1;308    }309310    pub fn authoredFallbacks(self: *const Engine, node: u32) []const asset.AssetHandle {311        const text = self.record(node).text;312        return self.pools[self.pool_live].chains[text.fallback_first..][0..text.fallback_count];313    }314315    pub fn deinit(self: *Engine, allocator: Allocator) void {316        std.debug.assert(self.phase != .teardown);317        self.phase = .teardown;318        allocator.free(self.bytes);319        self.bytes = &.{};320    }321322    pub fn record(self: *const Engine, node: u32) *const computed.Record {323        std.debug.assert(node < self.count);324        return self.pools[self.pool_live].get(self.states[self.live][node].style & style_mask);325    }326327    /// Returns the interned computed Record ID for an admitted node.328    /// Two nodes sharing the same computed style have the same ID within one style epoch.329    pub fn styleId(self: *const Engine, node: u32) u32 {330        std.debug.assert(node < self.count);331        return self.states[self.live][node].style & style_mask;332    }333334    /// Returns a u64 counter that advances only when a full cascade flips the335    /// computed-style pool and may renumber IDs: a fast cascade that appends in336    /// the current pool keeps the epoch. A cache retained across cascades keys337    /// by both epoch and ID, while a script fallback used only within one layout338    /// pass can key by ID alone.339    pub fn styleEpoch(self: *const Engine) u64 {340        std.debug.assert(self.phase == .steady);341        return self.style_epoch;342    }343344    fn oldAt(self: *const Engine, id: u64) ?NodeState {345        for (self.states[self.live][0..self.count]) |state| {346            if (state.id == id) return state;347        }348        return null;349    }350351    fn oldAtIndex(self: *const Engine, view: tree.View, at: u32) ?NodeState {352        if (self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and353            self.view_revision == view.header.revision and self.states[self.live][at].id == view.nodes[at].id)354        {355            return self.states[self.live][at];356        }357        if (view.prior.len == view.nodes.len) {358            const prior = view.prior[at] & ~tree.prior_dirty;359            if (prior != tree.prior_absent and prior < self.count) return self.states[self.live][prior];360            return null;361        }362        if (at < self.count and self.states[self.live][at].id == view.nodes[at].id) {363            return self.states[self.live][at];364        }365        return self.oldAt(view.nodes[at].id);366    }367368    fn classBloom(adapter: *const element.Adapter, index: u32) u64 {369        var result: u64 = 0;370        for (adapter.view.classesOf(index)) |atom| {371            const token = adapter.sheet.token(adapter.view.text(atom));372            result |= @as(u64, 1) << @truncate(token);373        }374        return result;375    }376377    fn sameMatchInputs(before: tree.View, old: u32, after: tree.View, at: u32) bool {378        const left = before.nodes[old];379        const right = after.nodes[at];380        if (left.kind != right.kind or left.role != right.role or left.state != right.state or381            left.flags != right.flags or (old == 0) != (at == 0) or382            (left.subtree_count == 0 and left.text == abi.text_absent) !=383                (right.subtree_count == 0 and right.text == abi.text_absent)) return false;384        if (old != 0 and before.nodes[left.parent].id != after.nodes[right.parent].id) return false;385        if (!std.mem.eql(u8, before.text(left.identifier), after.text(right.identifier))) return false;386        const old_classes = before.classesOf(old);387        const new_classes = after.classesOf(at);388        if (old_classes.len != new_classes.len) return false;389        for (old_classes, new_classes) |left_class, right_class| {390            if (!std.mem.eql(u8, before.text(left_class), after.text(right_class))) return false;391        }392        return std.mem.eql(u8, std.mem.sliceAsBytes(before.declarationsOf(old)), std.mem.sliceAsBytes(after.declarationsOf(at)));393    }394395    fn tokenHit(word: u64, token: u32) bool {396        return token != 0 and word & (@as(u64, 1) << @truncate(token)) != 0;397    }398399    fn hoverAncestorKeyHit(self: *const Engine, callbacks: css.match.Element, index: u32, classes: u64) bool {400        const summary = self.summary;401        if (summary.ancestor_kinds == 0 and summary.ancestor_roles == 0 and402            summary.ancestor_classes == 0 and summary.ancestor_ids == 0) return true;403        return classes & summary.ancestor_classes != 0 or404            tokenHit(summary.ancestor_kinds, callbacks.kind(callbacks.context, index)) or405            tokenHit(summary.ancestor_roles, callbacks.role(callbacks.context, index)) or406            tokenHit(summary.ancestor_ids, callbacks.identifier(callbacks.context, index));407    }408409    fn nodeKeys(view: tree.View, at: u32) u16 {410        const node = view.nodes[at];411        const kind: abi.Kind = @fromBackingInt(@intCast(node.kind));412        const role: abi.Role = @fromBackingInt(@intCast(node.role));413        var bits = bucketBit(.kind, @tagName(kind)) | bucketBit(.role, @tagName(role));414        if (node.identifier != 0) bits |= bucketBit(.identifier, view.text(node.identifier));415        for (view.classesOf(at)) |class| bits |= bucketBit(.class, view.text(class));416        return bits;417    }418419    fn putKeyBits(self: *Engine, target: u1, at: u32, bits: u16) void {420        const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;421        self.key_bits[target][at] = bits;422        for (0..key_columns) |column| {423            if (bits & (@as(u16, 1) << @intCast(column)) != 0) {424                self.key_index[target][column * stride + at / 64] |= @as(u64, 1) << @intCast(at % 64);425            }426        }427    }428429    fn updateKeyBits(self: *Engine, view: tree.View, at: u32) void {430        const bits = nodeKeys(view, at);431        const old = self.key_bits[self.live][at];432        if (bits == old) return;433        const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;434        for (0..key_columns) |column| {435            const key = @as(u16, 1) << @intCast(column);436            if ((old ^ bits) & key == 0) continue;437            const word = &self.key_index[self.live][column * stride + at / 64];438            const member = @as(u64, 1) << @intCast(at % 64);439            if (bits & key != 0) word.* |= member else word.* &= ~member;440        }441        self.key_bits[self.live][at] = bits;442    }443444    fn markBucketKeys(self: *Engine, count: usize, bits: u16) void {445        const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;446        for (0..key_columns) |column| {447            if (bits & (@as(u16, 1) << @intCast(column)) == 0) continue;448            for (0..std.math.divCeil(usize, count, 64) catch unreachable) |word| {449                var members = self.key_index[self.live][column * stride + word];450                while (members != 0) {451                    const bit: usize = @intCast(@ctz(members));452                    self.flags[word * 64 + bit] = 1;453                    members &= members - 1;454                }455            }456        }457    }458459    fn markFastBucketKeys(self: *Engine, target: u1, count: usize, bits: u16, universal: bool) void {460        if (universal) {461            for (0..count) |at| self.markFast(@intCast(at));462            return;463        }464        const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;465        for (0..key_columns) |column| {466            if (bits & (@as(u16, 1) << @intCast(column)) == 0) continue;467            for (0..std.math.divCeil(usize, count, 64) catch unreachable) |word| {468                var members = self.key_index[target][column * stride + word];469                while (members != 0) {470                    self.markFast(@intCast(word * 64 + @ctz(members)));471                    members &= members - 1;472                }473            }474        }475    }476477    fn markSubtree(self: *Engine, view: tree.View, index: u32) void {478        const end = index + view.nodes[index].subtree_count + 1;479        @memset(self.flags[index..end], 1);480    }481482    fn countGroup(index: css.bucket.Index, group: []const css.bucket.Entry, result: *Result) void {483        result.candidates += group.len;484        for (group) |entry| {485            const selector = index.source.rules[entry.rule].selectors[entry.selector];486            result.combinator_candidates += @intFromBool(selector.combinators.len != 0);487        }488    }489490    fn countCandidates(index: css.bucket.Index, callbacks: css.match.Element, node: u32, result: *Result) void {491        countGroup(index, index.group(.universal, 0), result);492        const kind = callbacks.kind(callbacks.context, node);493        if (kind != 0) countGroup(index, index.group(.kind, kind), result);494        const role = callbacks.role(callbacks.context, node);495        if (role != 0) countGroup(index, index.group(.role, role), result);496        const identifier = callbacks.identifier(callbacks.context, node);497        if (identifier != 0) countGroup(index, index.group(.identifier, identifier), result);498        var held: [css.match.max_element_classes]u32 = undefined;499        const count = callbacks.classes(callbacks.context, node, &held, css.match.max_element_classes);500        for (held[0..count]) |class| {501            if (class != 0) countGroup(index, index.group(.class, class), result);502        }503    }504505    fn markInteraction(self: *Engine, adapter: *const element.Adapter, id: u64, class: css.selector.PseudoClass) void {506        if (id == 0) return;507        const found = adapter.find(id) orelse return;508        var at = found;509        while (true) {510            const old = self.oldAt(adapter.view.nodes[at].id);511            const sensitive = if (class == .hover and self.hover_filter_enabled) if (old) |state| state.style & hover_sensitive != 0 else true else true;512            if (sensitive) {513                self.flags[at] = 1;514                if (self.summary.ancestorPseudoSensitive(class) or515                    (class == .focus and self.summary.ancestorPseudoSensitive(.focus_within)))516                {517                    self.markSubtree(adapter.view, at);518                }519            }520            if (at == 0) break;521            at = adapter.view.nodes[at].parent;522        }523    }524525    fn markFast(self: *Engine, at: u32) void {526        const word = at / 64;527        const bit = @as(u64, 1) << @intCast(at % 64);528        if (self.touched[word] & bit == 0) self.flags[at] = 1;529        self.touched[word] |= bit;530    }531532    fn markFastSubtree(self: *Engine, view: tree.View, at: u32) void {533        const end = at + view.nodes[at].subtree_count + 1;534        var index = at;535        while (index < end) : (index += 1) self.markFast(index);536    }537538    fn markFastDescendants(self: *Engine, view: tree.View, at: u32) void {539        const end = at + view.nodes[at].subtree_count + 1;540        var index = at + 1;541        while (index < end) : (index += 1) self.markFast(index);542    }543544    fn markFastChildren(self: *Engine, view: tree.View, at: u32) void {545        const end = at + view.nodes[at].subtree_count + 1;546        var index = at + 1;547        while (index < end) : (index += view.nodes[index].subtree_count + 1) self.markFast(index);548    }549550    fn findInView(view: tree.View, id: u64) ?u32 {551        if (id == 0) return null;552        if (view.identity) |identity| return identity.lookup(view.nodes, id);553        for (view.nodes, 0..) |node, at| if (node.id == id) return @intCast(at);554        return null;555    }556557    fn chain(view: tree.View, id: u64, held: *[65]u32) []const u32 {558        var at = findInView(view, id) orelse return held[0..0];559        var used: usize = 0;560        while (true) {561            std.debug.assert(used < held.len);562            held[used] = at;563            used += 1;564            if (at == 0) break;565            at = view.nodes[at].parent;566        }567        return held[0..used];568    }569570    fn markFastPseudoNode(self: *Engine, adapter: *element.Adapter, at: u32, class: css.selector.PseudoClass) void {571        const sensitive = class != .hover or !self.hover_filter_enabled or self.direct_hover or572            (self.summary.ancestorPseudoSensitive(.hover) and573                self.hoverAncestorKeyHit(adapter.element(), at, classBloom(adapter, at)));574        if (!sensitive) return;575        self.markFast(at);576        if (self.summary.ancestorPseudoSensitive(class) or577            (class == .focus and self.summary.ancestorPseudoSensitive(.focus_within)))578        {579            self.markFastSubtree(adapter.view, at);580        }581    }582583    fn markFastTransition(self: *Engine, adapter: *element.Adapter, old_id: u64, new_id: u64, class: css.selector.PseudoClass) void {584        var old_buffer: [65]u32 = undefined;585        var new_buffer: [65]u32 = undefined;586        const old_chain = chain(self.last_view, old_id, &old_buffer);587        const new_chain = chain(adapter.view, new_id, &new_buffer);588        if (class == .hover and !self.hover_filter_enabled) {589            for (old_chain) |at| {590                const current = adapter.find(self.last_view.nodes[at].id) orelse continue;591                self.markFastPseudoNode(adapter, current, class);592            }593            for (new_chain) |at| self.markFastPseudoNode(adapter, at, class);594            return;595        }596        var old_set = ChainSet{};597        var new_set = ChainSet{};598        for (old_chain) |at| old_set.insert(self.last_view.nodes[at].id);599        for (new_chain) |at| new_set.insert(adapter.view.nodes[at].id);600        for (old_chain) |at| {601            const id = self.last_view.nodes[at].id;602            if (new_set.contains(id)) continue;603            const current = adapter.find(id) orelse continue;604            self.markFastPseudoNode(adapter, current, class);605        }606        for (new_chain) |at| {607            if (old_set.contains(adapter.view.nodes[at].id)) continue;608            self.markFastPseudoNode(adapter, at, class);609        }610    }611612    fn fastCascade(613        self: *Engine,614        view: tree.View,615        dirty: []const u32,616        sheet: *const css.StyleSheet,617        generation: u32,618        interaction: element.Interaction,619        index: css.bucket.Index,620        metrics: computed.Metrics,621        font_environment: ?computed.FontSource,622        carry: bool,623        carried_count: u32,624        changed_selector_bits: u16,625        changed_universal: bool,626        ancestor_classes: u64,627    ) Error!Result {628        const words = std.math.divCeil(usize, view.nodes.len, 64) catch unreachable;629        if (!carry) @memset(self.touched[0..words], 0);630        if (changed_selector_bits != 0 or changed_universal) {631            self.markFastBucketKeys(if (carry) self.live ^ 1 else self.live, view.nodes.len, changed_selector_bits, changed_universal);632        }633        var adapter = element.Adapter{ .view = view, .sheet = sheet, .interaction = interaction };634        for (dirty) |at| {635            const old_index = if (carry) view.prior[at] & ~tree.prior_dirty else tree.prior_absent;636            if (!carry or old_index == tree.prior_absent or637                !sameMatchInputs(self.last_view, old_index, view, at)) self.markFast(at);638            const bloom = classBloom(&adapter, at);639            const old = self.states[if (carry) self.live ^ 1 else self.live][at];640            if ((old.ancestor_classes ^ bloom) & ancestor_classes != 0) {641                self.markFastSubtree(view, at);642            }643            if (self.summary.sibling_sensitive or self.summary.positional) {644                self.markFastChildren(view, at);645                if (at != 0) self.markFastChildren(view, view.nodes[at].parent);646            }647        }648        if (carry or interaction.hovered != self.interaction.hovered) {649            self.markFastTransition(&adapter, self.interaction.hovered, interaction.hovered, .hover);650        }651        if (carry or interaction.focused != self.interaction.focused) {652            self.markFastTransition(&adapter, self.interaction.focused, interaction.focused, .focus);653        }654        if (interaction.focused != self.interaction.focused) {655            if (adapter.find(self.interaction.focused)) |old| self.markFastPseudoNode(&adapter, old, .focus);656            if (adapter.find(interaction.focused)) |new| self.markFastPseudoNode(&adapter, new, .focus);657        }658        if (interaction.keyboard_focus != self.interaction.keyboard_focus) {659            if (adapter.find(interaction.focused)) |focused| self.markFastPseudoNode(&adapter, focused, .focus_visible);660        }661        if (carry or interaction.active != self.interaction.active) {662            self.markFastTransition(&adapter, self.interaction.active, interaction.active, .active);663        }664        const stage: u1 = self.live ^ 1;665        const pool = &self.pools[self.pool_live];666        var result = Result{ .carried = carried_count, .carried_bytes = @as(u64, carried_count) * @sizeOf(NodeState) };667        var resolver = css.cascade.Resolver{};668        for (0..words) |word| {669            var processed: u64 = 0;670            while (self.touched[word] & ~processed != 0) {671                const bit: u6 = @intCast(@ctz(self.touched[word] & ~processed));672                const at: u32 = @intCast(word * 64 + bit);673                processed |= @as(u64, 1) << bit;674                self.flags[at] = 0;675                result.visited += 1;676                const node = view.nodes[at];677                const prior = self.states[if (carry) stage else self.live][at];678                const bloom = classBloom(&adapter, at);679                const parent_style: u32 = if (at == 0) 0 else blk: {680                    const parent = node.parent;681                    if (carry) break :blk self.states[stage][parent].style & style_mask;682                    const parent_bit = @as(u64, 1) << @intCast(parent % 64);683                    const staged = self.touched[parent / 64] & parent_bit != 0 and self.flags[parent] == 0;684                    break :blk (if (staged) self.states[stage][parent].style else self.states[self.live][parent].style) & style_mask;685                };686                const callbacks = adapter.element();687                countCandidates(index, callbacks, at, &result);688                const before_steps = adapter.ancestor_steps;689                const matched = css.bucket.matchElement(index, callbacks, at, self.matches);690                if (matched.rejected != 0) return error.MatchedRuleQuota;691                result.ancestor_walks += adapter.ancestor_steps - before_steps;692                var rule_hash: u32 = 2166136261;693                for (self.matches[0..matched.count]) |item| {694                    rule_hash = (rule_hash ^ item.rule) *% 16777619;695                    rule_hash = (rule_hash ^ item.selector) *% 16777619;696                }697                const key = share.Key{698                    .matched_rules = rule_hash,699                    .inline_first = node.declaration_first,700                    .inline_count = node.declaration_count,701                    .parent_style = parent_style,702                };703                const sensitive = self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and704                    self.hoverAncestorKeyHit(callbacks, at, bloom));705                resolver.begin(sheet.source, &sheet.atoms, null);706                for (self.matches[0..matched.count]) |item| {707                    const rule = sheet.rules[item.rule];708                    for (rule.lowered) |declaration| resolver.add(declaration, .author, item.specificity, item.order);709                }710                for (view.declarationsOf(at)) |declaration| resolver.add(declaration, .author, css.Specificity.inlineStyle(), std.math.maxInt(u32));711                const inherited = if (parent_style == 0) null else &pool.get(parent_style).computed;712                var style: css.cascade.Computed = undefined;713                resolver.finish(inherited, &style);714                const style_id = try pool.intern(key, self.matches[0..matched.count], style, metrics, font_environment);715                self.states[stage][at] = .{716                    .id = node.id,717                    .ancestor_classes = bloom,718                    .style = style_id | (if (sensitive) hover_sensitive else 0),719                    .computed_generation = generation,720                };721                result.restyled += 1;722                if (prior.style & style_mask == 0 or !std.mem.eql(u8, std.mem.asBytes(&pool.get(prior.style & style_mask).computed), std.mem.asBytes(&pool.get(style_id).computed))) {723                    self.markFastDescendants(view, at);724                }725            }726        }727        if (carry) {728            self.live = stage;729            self.count = @intCast(view.nodes.len);730            self.node_buffer_addr = @intFromPtr(view.nodes.ptr);731            self.view_revision = view.header.revision;732        } else {733            for (self.touched[0..words], 0..) |held, word| {734                var members = held;735                while (members != 0) {736                    const bit: u6 = @intCast(@ctz(members));737                    const at = word * 64 + bit;738                    self.states[self.live][at] = self.states[stage][at];739                    self.updateKeyBits(view, @intCast(at));740                    members &= members - 1;741                }742            }743        }744        self.interaction = interaction;745        self.last_view = view;746        return result;747    }748749    pub fn cascade(750        self: *Engine,751        store: *const tree.Store,752        sheet: *const css.StyleSheet,753        generation: u32,754        interaction: element.Interaction,755    ) Error!Result {756        std.debug.assert(self.phase == .steady);757        return self.cascadeView(store.retained(), store.dirty(), sheet, generation, interaction);758    }759760    pub fn cascadeView(761        self: *Engine,762        view: tree.View,763        dirty: []const u32,764        sheet: *const css.StyleSheet,765        generation: u32,766        interaction: element.Interaction,767    ) Error!Result {768        std.debug.assert(self.phase == .steady);769        if (view.nodes.len > self.limits.nodes) return error.CapacityOverflow;770        const selector_count = css.bucket.Limits.inspect(sheet).entries;771        if (selector_count > self.entries.len) return error.SelectorQuota;772        var adapter = element.Adapter{ .view = view, .sheet = sheet, .interaction = interaction };773        const metrics = computed.Metrics{774            .root_font_size = view.header.root_font_size,775            .viewport_width = view.header.viewport.width,776            .viewport_height = view.header.viewport.height,777        };778        const changed_sheet = self.sheet != sheet or self.stylesheet_generation != generation;779        const changed_fonts = self.applied_font_revision != self.font_revision or780            (if (self.fonts) |registry| self.applied_font_epoch != registry.epoch else false);781        const changed_inputs = !std.meta.eql(self.metrics, metrics) or changed_fonts or (changed_sheet and self.fonts != null);782        const font_environment: ?computed.FontSource = if (self.fonts) |registry|783            .{ .registry = registry, .source = sheet.source }784        else785            null;786        const previous_summary = self.summary;787        const previous_hover = self.direct_hover;788        const previous_custom = self.custom_sheet;789        errdefer if (changed_sheet) {790            self.summary = previous_summary;791            self.direct_hover = previous_hover;792            self.custom_sheet = previous_custom;793            if (self.sheet) |retained_sheet| _ = css.bucket.build(self.entries, retained_sheet);794        };795        const index: css.bucket.Index = if (changed_sheet) css.bucket.build(self.entries, sheet) else .{ .entries = self.entries[0..self.selector_count], .source = sheet };796        const keys: SelectorKeys = if (changed_sheet) selectorKeys(index) else .{ .bits = self.selector_key_bits, .universal = self.universal_selector };797        if (changed_sheet) {798            self.summary = css.bucket.summarize(sheet);799            self.direct_hover = false;800            self.custom_sheet = false;801            for (sheet.rules) |rule| {802                if (rule.customs.len != 0) self.custom_sheet = true;803                for (rule.selectors) |selector| {804                    if (selector.rightmost().pseudo & css.selector.bit(.hover) != 0) self.direct_hover = true;805                }806            }807        }808        const changed_selector_bits = if (changed_sheet) self.selector_key_bits | keys.bits else @as(u16, 0);809        const changed_universal = changed_sheet and (self.universal_selector or keys.universal);810        const ancestor_classes = previous_summary.ancestor_classes | self.summary.ancestor_classes;811        const complete_refresh = blk: {812            if (dirty.len != view.nodes.len) break :blk false;813            for (dirty, 0..) |at, index_at| if (at != index_at) break :blk false;814            break :blk true;815        };816        if (!complete_refresh and self.count != 0 and !changed_inputs and !self.custom_sheet and !previous_custom and817            self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and818            self.view_revision == view.header.revision)819        {820            var stable_ids = true;821            for (dirty) |at| {822                if (at >= self.count or self.states[self.live][at].id != view.nodes[at].id) {823                    stable_ids = false;824                    break;825                }826            }827            if (stable_ids) {828                const retained_styles = self.pools[self.pool_live].used;829                if (self.fastCascade(view, dirty, sheet, generation, interaction, index, metrics, font_environment, false, 0, changed_selector_bits, changed_universal, ancestor_classes)) |fast| {830                    self.sheet = sheet;831                    self.stylesheet_generation = generation;832                    self.selector_key_bits = keys.bits;833                    self.universal_selector = keys.universal;834                    self.selector_count = @intCast(index.entries.len);835                    return fast;836                } else |err| {837                    self.pools[self.pool_live].truncate(retained_styles);838                    @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);839                    switch (err) {840                        error.DistinctStyleQuota => {},841                        else => return err,842                    }843                }844            }845        }846        if (!complete_refresh and self.count != 0 and !changed_inputs and !self.custom_sheet and !previous_custom and847            view.prior.len == view.nodes.len and self.last_view.nodes.len == self.count and848            (view.header.base_revision == 0 or view.header.base_revision == self.view_revision) and849            (self.node_buffer_addr != @intFromPtr(view.nodes.ptr) or self.view_revision != view.header.revision))850        {851            const stage: u1 = self.live ^ 1;852            @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);853            @memset(self.key_index[stage], 0);854            var carried: u32 = 0;855            var valid = true;856            for (view.nodes, 0..) |node, at| {857                const old = view.prior[at] & ~tree.prior_dirty;858                if (old == tree.prior_absent) {859                    self.states[stage][at] = .{ .id = node.id };860                    self.putKeyBits(stage, @intCast(at), nodeKeys(view, @intCast(at)));861                    continue;862                }863                if (old >= self.count or self.states[self.live][old].id != node.id) {864                    valid = false;865                    break;866                }867                self.states[stage][at] = self.states[self.live][old];868                const bits = if (view.prior[at] & tree.prior_dirty != 0)869                    nodeKeys(view, @intCast(at))870                else871                    self.key_bits[self.live][old];872                self.putKeyBits(stage, @intCast(at), bits);873                carried += 1;874                if (at != 0 and self.last_view.nodes[old].parent < self.last_view.nodes.len and875                    self.last_view.nodes[self.last_view.nodes[old].parent].id != view.nodes[node.parent].id)876                {877                    self.markFastSubtree(view, @intCast(at));878                    if (self.summary.sibling_sensitive or self.summary.positional) {879                        self.markFastChildren(view, node.parent);880                        const old_parent_id = self.last_view.nodes[self.last_view.nodes[old].parent].id;881                        if (view.identity) |identity| {882                            if (identity.lookup(view.nodes, old_parent_id)) |old_parent| {883                                self.markFastChildren(view, old_parent);884                            }885                        }886                    }887                }888            }889            if (valid) {890                const retained_styles = self.pools[self.pool_live].used;891                if (self.fastCascade(view, dirty, sheet, generation, interaction, index, metrics, font_environment, true, carried, changed_selector_bits, changed_universal, ancestor_classes)) |fast| {892                    self.sheet = sheet;893                    self.stylesheet_generation = generation;894                    self.selector_key_bits = keys.bits;895                    self.universal_selector = keys.universal;896                    self.selector_count = @intCast(index.entries.len);897                    return fast;898                } else |err| {899                    self.pools[self.pool_live].truncate(retained_styles);900                    @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);901                    switch (err) {902                        error.DistinctStyleQuota => {},903                        else => return err,904                    }905                }906            }907        }908        @memset(self.flags[0..view.nodes.len], if (self.count == 0 or changed_inputs or909            self.custom_sheet or (changed_sheet and (self.universal_selector or keys.universal or910            self.node_buffer_addr != @intFromPtr(view.nodes.ptr) or self.view_revision != view.header.revision))) 1 else 0);911        if (changed_sheet and self.count != 0 and !changed_inputs and !self.universal_selector and !keys.universal and912            self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and self.view_revision == view.header.revision)913        {914            self.markBucketKeys(view.nodes.len, self.selector_key_bits | keys.bits);915        }916        for (dirty) |at| self.flags[at] = 1;917        if (self.summary.sibling_sensitive or self.summary.positional) {918            for (dirty) |at| {919                const parent = view.nodes[at].parent;920                self.markSubtree(view, parent);921            }922        }923        if (interaction.hovered != self.interaction.hovered) {924            self.markInteraction(&adapter, self.interaction.hovered, .hover);925            self.markInteraction(&adapter, interaction.hovered, .hover);926        }927        if (interaction.focused != self.interaction.focused or interaction.keyboard_focus != self.interaction.keyboard_focus) {928            self.markInteraction(&adapter, self.interaction.focused, .focus);929            self.markInteraction(&adapter, interaction.focused, .focus);930        }931        if (interaction.active != self.interaction.active) {932            self.markInteraction(&adapter, self.interaction.active, .active);933            self.markInteraction(&adapter, interaction.active, .active);934        }935        const next: u1 = self.live ^ 1;936        const next_pool = &self.pools[self.pool_live ^ 1];937        next_pool.reset();938        @memset(self.key_index[next], 0);939        @memset(self.remap, 0);940        var result = Result{};941        var resolver = css.cascade.Resolver{};942        var custom_stack: [65]css.cascade.CustomTable = undefined;943        var custom_nodes: [65]u32 = undefined;944        var custom_depth: usize = 0;945        for (view.nodes, 0..) |node, i| {946            result.visited += 1;947            const at: u32 = @intCast(i);948            self.putKeyBits(next, at, nodeKeys(view, at));949            const prior = self.oldAtIndex(view, at);950            const bloom = classBloom(&adapter, at);951            const parent_style: u32 = if (at == 0) 0 else self.states[next][node.parent].style & style_mask;952            const ancestor_change = if (prior) |state| (state.ancestor_classes ^ bloom) & self.summary.ancestor_classes != 0 else false;953            if (ancestor_change) self.markSubtree(view, at);954            const same_view = self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and955                self.view_revision == view.header.revision;956            const shifted = prior == null or if (same_view)957                self.states[self.live][at].id != node.id958            else if (view.prior.len == view.nodes.len)959                (view.prior[at] & ~tree.prior_dirty) != at960            else961                at >= self.count or self.states[self.live][at].id != node.id;962            const should_compute = changed_inputs or self.flags[at] != 0 or prior == null or shifted;963            if (!should_compute) {964                var same = prior.?;965                const old_id = same.style & style_mask;966                var new_id = self.remap[old_id - 1];967                if (new_id == 0) {968                    const inherited = self.pools[self.pool_live].get(old_id);969                    new_id = try next_pool.intern(.{970                        .matched_rules = 0,971                        .inline_first = 0,972                        .inline_count = 0,973                        .parent_style = parent_style,974                    }, &.{}, inherited.computed, metrics, font_environment);975                    self.remap[old_id - 1] = new_id;976                }977                const old_hover = same.style & hover_sensitive;978                const next_hover = if (changed_sheet)979                    if (self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and980                        self.hoverAncestorKeyHit(adapter.element(), at, bloom))) hover_sensitive else @as(u32, 0)981                else982                    old_hover;983                same.style = new_id | next_hover;984                same.ancestor_classes = bloom;985                same.computed_generation = generation;986                self.states[next][at] = same;987                result.shared += 1;988                continue;989            }990            const callbacks = adapter.element();991            countCandidates(index, callbacks, at, &result);992            const before_steps = adapter.ancestor_steps;993            const matched = css.bucket.matchElement(index, callbacks, at, self.matches);994            if (matched.rejected != 0) return error.MatchedRuleQuota;995            result.ancestor_walks += adapter.ancestor_steps - before_steps;996            var rule_hash: u32 = 2166136261;997            for (self.matches[0..matched.count]) |item| {998                rule_hash = (rule_hash ^ item.rule) *% 16777619;999                rule_hash = (rule_hash ^ item.selector) *% 16777619;1000            }1001            const key = share.Key{1002                .matched_rules = rule_hash,1003                .inline_first = node.declaration_first,1004                .inline_count = node.declaration_count,1005                .parent_style = parent_style,1006            };1007            const sensitive = self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and1008                self.hoverAncestorKeyHit(callbacks, at, bloom));1009            if (if (self.custom_sheet) null else next_pool.lookup(key, self.matches[0..matched.count])) |style_id| {1010                self.states[next][at] = .{1011                    .id = node.id,1012                    .ancestor_classes = bloom,1013                    .style = style_id | (if (sensitive) hover_sensitive else 0),1014                    .computed_generation = generation,1015                };1016                result.restyled += 1;1017                result.shared += 1;1018                if (prior) |old| {1019                    const old_style = self.pools[self.pool_live].get(old.style & style_mask);1020                    const new_style = next_pool.get(style_id);1021                    if (!std.mem.eql(u8, std.mem.asBytes(&old_style.computed), std.mem.asBytes(&new_style.computed))) {1022                        self.markSubtree(view, at);1023                    }1024                }1025                continue;1026            }1027            var parent_customs: ?*const css.cascade.CustomTable = null;1028            if (self.custom_sheet and at != 0) {1029                while (custom_depth > 0 and custom_nodes[custom_depth - 1] != node.parent) custom_depth -= 1;1030                std.debug.assert(custom_depth > 0);1031                parent_customs = &custom_stack[custom_depth - 1];1032            }1033            resolver.begin(sheet.source, &sheet.atoms, parent_customs);1034            for (self.matches[0..matched.count]) |item| {1035                const rule = sheet.rules[item.rule];1036                for (rule.lowered) |declaration| resolver.add(declaration, .author, item.specificity, item.order);1037                for (rule.customs) |custom| resolver.addCustom(custom, .author, item.specificity, item.order);1038            }1039            for (view.declarationsOf(at)) |declaration| resolver.add(declaration, .author, css.Specificity.inlineStyle(), std.math.maxInt(u32));1040            const inherited = if (parent_style == 0) null else &next_pool.get(parent_style).computed;1041            var style: css.cascade.Computed = undefined;1042            resolver.finish(inherited, &style);1043            if (self.custom_sheet) {1044                if (custom_depth == custom_stack.len) return error.CapacityOverflow;1045                custom_stack[custom_depth] = resolver.customs;1046                custom_nodes[custom_depth] = at;1047                custom_depth += 1;1048            }1049            const style_id = try next_pool.intern(key, self.matches[0..matched.count], style, metrics, font_environment);1050            self.states[next][at] = .{1051                .id = node.id,1052                .ancestor_classes = bloom,1053                .style = style_id | (if (sensitive) hover_sensitive else 0),1054                .computed_generation = generation,1055            };1056            result.restyled += 1;1057            if (prior) |old| {1058                const old_style = self.pools[self.pool_live].get(old.style & style_mask);1059                if (!std.mem.eql(u8, std.mem.asBytes(&old_style.computed), std.mem.asBytes(&style))) {1060                    self.markSubtree(view, at);1061                }1062            }1063        }1064        self.live = next;1065        self.pool_live ^= 1;1066        std.debug.assert(self.style_epoch < std.math.maxInt(u64));1067        self.style_epoch += 1;1068        self.count = @intCast(view.nodes.len);1069        self.node_buffer_addr = @intFromPtr(view.nodes.ptr);1070        self.view_revision = view.header.revision;1071        self.last_view = view;1072        self.selector_count = @intCast(index.entries.len);1073        self.sheet = sheet;1074        self.stylesheet_generation = generation;1075        self.selector_key_bits = keys.bits;1076        self.universal_selector = keys.universal;1077        self.interaction = interaction;1078        self.metrics = metrics;1079        self.applied_font_revision = self.font_revision;1080        self.applied_font_epoch = if (self.fonts) |registry| registry.epoch else 0;1081        return result;1082    }1083};10841085comptime {1086    alloc_phase.capacity.requireAllocatorExactOwnerShape(Engine);1087}10881089test "incremental cascade agrees with a cold cascade after one dirty node" {1090    const allocator = std.testing.allocator;1091    var workspace = css.Workspace.init(allocator);1092    defer workspace.deinit();1093    const sheet = try workspace.parse("box { color: #ff0000; } text { color: #0000ff; }", .default());1094    const nodes = [_]@import("../abi/root.zig").Node{1095        .{ .id = 1, .revision = 1, .kind = @backingInt(@import("../abi/root.zig").Kind.box), .subtree_count = 1 },1096        .{ .id = 2, .revision = 1, .kind = @backingInt(@import("../abi/root.zig").Kind.text), .parent = 0 },1097    };1098    const view = tree.View{ .header = .{ .root_font_size = 16 }, .nodes = &nodes };1099    const limits = Limits{ .nodes = 2, .distinct_styles = 4, .selectors = 4, .bytes = 16 * 1024 };1100    var incremental = try Engine.init(allocator, limits);1101    defer incremental.deinit(allocator);1102    incremental.activate();1103    const first = try incremental.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{});1104    try std.testing.expectEqual(@as(u32, 2), first.restyled);1105    const next = try incremental.cascadeView(view, &.{1}, &sheet, 1, .{});1106    try std.testing.expectEqual(@as(u32, 1), next.restyled);1107    var cold = try Engine.init(allocator, limits);1108    defer cold.deinit(allocator);1109    cold.activate();1110    _ = try cold.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{});1111    for (nodes, 0..) |_, at| {1112        try std.testing.expect(std.meta.eql(incremental.record(@intCast(at)).computed, cold.record(@intCast(at)).computed));1113    }1114}11151116test "stylesheet generation visits only indexed bucket keys" {1117    const allocator = std.testing.allocator;1118    var first_workspace = css.Workspace.init(allocator);1119    defer first_workspace.deinit();1120    var second_workspace = css.Workspace.init(allocator);1121    defer second_workspace.deinit();1122    const first = try first_workspace.parse(".alpha { color: red; }", .default());1123    const second = try second_workspace.parse(".beta { color: blue; }", .default());1124    var nodes: [128]abi.Node = undefined;1125    nodes[0] = .{ .id = 1, .subtree_count = 127 };1126    for (1..nodes.len) |at| nodes[at] = .{ .id = @intCast(at + 1), .parent = 0 };1127    nodes[1].class_first = 0;1128    nodes[1].class_count = 1;1129    nodes[2].class_first = 1;1130    nodes[2].class_count = 1;1131    const classes = [_]u32{ 1, 2 };1132    const atoms = [_]abi.Atom{ .{}, .{ .offset = 0, .len = 5 }, .{ .offset = 5, .len = 4 } };1133    const view = tree.View{ .nodes = &nodes, .classes = &classes, .atoms = &atoms, .strings = "alphabeta" };1134    var incremental = try Engine.init(allocator, .{ .nodes = 128, .distinct_styles = 8, .selectors = 4, .bytes = 64 * 1024 });1135    defer incremental.deinit(allocator);1136    incremental.activate();1137    _ = try incremental.cascadeView(view, &.{}, &first, 1, .{});1138    const changed = try incremental.cascadeView(view, &.{}, &second, 2, .{});1139    try std.testing.expectEqual(@as(u32, 2), changed.visited);1140    try std.testing.expectEqual(@as(u32, 2), changed.restyled);1141    var cold = try Engine.init(allocator, .{ .nodes = 128, .distinct_styles = 8, .selectors = 4, .bytes = 64 * 1024 });1142    defer cold.deinit(allocator);1143    cold.activate();1144    _ = try cold.cascadeView(view, &.{}, &second, 2, .{});1145    for (nodes, 0..) |_, at| {1146        try std.testing.expect(std.meta.eql(incremental.record(@intCast(at)).computed, cold.record(@intCast(at)).computed));1147    }1148}11491150test "ui_style_capacity derives the caller bound" {1151    comptime {1152        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_capacity"), null, null, null, null, null, null);1153    }1154    const capacity = try Capacity.derive(.{});1155    try std.testing.expectEqual(@as(usize, 2_097_152), capacity.total_bytes);1156    try std.testing.expect(capacity.required_bytes <= capacity.total_bytes);1157}11581159test "ui_style_acquisition and ui_style_teardown own one block" {1160    comptime {1161        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_acquisition"), null, null, null, null, null, null);1162        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_teardown"), null, null, null, null, null, null);1163    }1164    var engine = try Engine.init(std.testing.allocator, .{});1165    try std.testing.expectEqual(@as(usize, 2_097_152), engine.bytes.len);1166    engine.activate();1167    engine.deinit(std.testing.allocator);1168    try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, engine.phase);1169}11701171fn openAndClose(allocator: Allocator, limits: LimitsType) !void {1172    var engine = try Engine.init(allocator, limits);1173    engine.activate();1174    engine.deinit(allocator);1175}11761177test "ui_style_oom refuses acquisition without a partial block" {1178    comptime {1179        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_oom"), null, null, null, null, null, null);1180    }1181    var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });1182    try std.testing.expectError(error.OutOfMemory, Engine.init(failing.allocator(), .{}));1183    try std.testing.expectEqual(@as(usize, 0), failing.allocated_bytes - failing.freed_bytes);1184    try std.testing.checkAllAllocationFailures(std.testing.allocator, openAndClose, .{LimitsType{}});1185}11861187test "ui_style_sharing_quota rejects before changing the live generation" {1188    comptime {1189        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_sharing_quota"), null, null, null, null, null, null);1190    }1191    const allocator = std.testing.allocator;1192    var workspace = css.Workspace.init(allocator);1193    defer workspace.deinit();1194    const sheet = try workspace.parse("box { color: red; } text { color: blue; }", .default());1195    const nodes = [_]abi.Node{1196        .{ .id = 1, .subtree_count = 1, .kind = @backingInt(abi.Kind.box) },1197        .{ .id = 2, .parent = 0, .kind = @backingInt(abi.Kind.text) },1198    };1199    var engine = try Engine.init(allocator, .{ .nodes = 2, .distinct_styles = 1, .selectors = 2, .bytes = 8 * 1024 });1200    defer engine.deinit(allocator);1201    engine.activate();1202    const view = tree.View{ .header = .{ .root_font_size = 16 }, .nodes = &nodes };1203    try std.testing.expectError(error.DistinctStyleQuota, engine.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{}));1204    try std.testing.expectEqual(@as(u32, 0), engine.count);1205    try std.testing.expectEqual(@as(u32, 0), engine.stylesheet_generation);1206}12071208test "ui_style_font_chain rejects a face quota before binding" {1209    comptime {1210        @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_font_chain"), null, null, null, null, null, null);1211    }1212    const allocator = std.testing.allocator;1213    var registry = try asset.Registry.init(allocator, .{ .fonts = 2, .images = 0, .owned_bytes = 0 });1214    defer registry.deinit(allocator);1215    registry.activate();1216    var engine = try Engine.init(allocator, .{ .nodes = 1, .distinct_styles = 1, .selectors = 1, .font_faces = 1, .bytes = 8 * 1024 });1217    defer engine.deinit(allocator);1218    engine.activate();1219    try std.testing.expectError(error.FontChainQuota, engine.setFonts(&registry));1220    try std.testing.expect(engine.fonts == null);1221}12221223test "sparse quota failure preserves the live pool and node states" {1224    const allocator = std.testing.allocator;1225    var workspace = css.Workspace.init(allocator);1226    defer workspace.deinit();1227    const sheet = try workspace.parse(".red { color: red; } .blue { color: blue; }", .default());1228    const nodes = [_]abi.Node{1229        .{ .id = 1, .subtree_count = 2 },1230        .{ .id = 2, .parent = 0, .class_first = 0, .class_count = 1 },1231        .{ .id = 3, .parent = 0, .class_first = 1, .class_count = 1 },1232    };1233    var classes = [_]u32{ 1, 1 };1234    const atoms = [_]abi.Atom{ .{}, .{ .offset = 0, .len = 3 }, .{ .offset = 3, .len = 4 } };1235    const view = tree.View{ .nodes = &nodes, .classes = &classes, .atoms = &atoms, .strings = "redblue" };1236    var engine = try Engine.init(allocator, .{ .nodes = 3, .distinct_styles = 2, .selectors = 4, .bytes = 64 * 1024 });1237    defer engine.deinit(allocator);1238    engine.activate();1239    _ = try engine.cascadeView(view, &.{ 0, 1, 2 }, &sheet, 1, .{});1240    const original = engine.record(2).computed;1241    const original_epoch = engine.styleEpoch();1242    const retained_styles = engine.pools[engine.pool_live].used;1243    classes[1] = 2;1244    try std.testing.expectError(error.DistinctStyleQuota, engine.cascadeView(view, &.{2}, &sheet, 1, .{}));1245    try std.testing.expectEqual(retained_styles, engine.pools[engine.pool_live].used);1246    try std.testing.expectEqual(original_epoch, engine.styleEpoch());1247    try std.testing.expect(std.meta.eql(original, engine.record(2).computed));1248    classes[1] = 1;1249    const restored = try engine.cascadeView(view, &.{2}, &sheet, 1, .{});1250    try std.testing.expectEqual(@as(u32, 1), restored.visited);1251    try std.testing.expect(std.meta.eql(original, engine.record(2).computed));1252}12531254test "style ids share within an epoch and a full cascade advances it" {1255    const allocator = std.testing.allocator;1256    var workspace = css.Workspace.init(allocator);1257    defer workspace.deinit();1258    const red = try workspace.parse("box { color: red; }", .default());1259    const blue = try workspace.parse("box { color: blue; }", .default());1260    const nodes = [_]abi.Node{1261        .{ .id = 1, .subtree_count = 1, .kind = @backingInt(abi.Kind.box) },1262        .{ .id = 2, .parent = 0, .kind = @backingInt(abi.Kind.box) },1263    };1264    const view = tree.View{1265        .header = .{ .root_font_size = 16 },1266        .nodes = &nodes,1267    };1268    var engine = try Engine.init(allocator, .{1269        .nodes = 2,1270        .distinct_styles = 4,1271        .selectors = 2,1272        .bytes = 16 * 1024,1273    });1274    defer engine.deinit(allocator);1275    engine.activate();1276    try std.testing.expectEqual(@as(u64, 0), engine.styleEpoch());1277    _ = try engine.cascadeView(view, &.{ 0, 1 }, &red, 1, .{});1278    const first_epoch = engine.styleEpoch();1279    const first_id = engine.styleId(0);1280    try std.testing.expectEqual(@as(u64, 1), first_epoch);1281    try std.testing.expectEqual(first_id, engine.styleId(1));1282    _ = try engine.cascadeView(view, &.{1}, &red, 1, .{});1283    try std.testing.expectEqual(first_epoch, engine.styleEpoch());1284    try std.testing.expectEqual(first_id, engine.styleId(0));1285    _ = try engine.cascadeView(view, &.{ 0, 1 }, &blue, 2, .{});1286    try std.testing.expectEqual(first_epoch + 1, engine.styleEpoch());1287}

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