// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! The two tables an HPACK index can name: the static one from RFC 7541 //! Appendix A, and the dynamic one of §2.3.2. //! //! They share one index space (§2.3.3): 1 through 61 are the static table, //! and 62 upwards are the dynamic table with the *most recently added* entry //! first. That ordering is the thing to keep in mind while reading this file //! — a dynamic entry's index changes every time another is inserted, which is //! why nothing here hands out indices that are meant to be kept. const std = @import("std"); const Allocator = std.mem.Allocator; const protocol = @import("../../protocol.zig"); const Field = protocol.Field; const token = protocol.token; /// RFC 7541 Appendix A, transcribed. An empty value means the entry names a /// field whose value is always given as a literal. pub const static: [61]Field = .{ .{ .name = ":authority", .value = "" }, // 1 .{ .name = ":method", .value = "GET" }, // 2 .{ .name = ":method", .value = "POST" }, // 3 .{ .name = ":path", .value = "/" }, // 4 .{ .name = ":path", .value = "/index.html" }, // 5 .{ .name = ":scheme", .value = "http" }, // 6 .{ .name = ":scheme", .value = "https" }, // 7 .{ .name = ":status", .value = "200" }, // 8 .{ .name = ":status", .value = "204" }, // 9 .{ .name = ":status", .value = "206" }, // 10 .{ .name = ":status", .value = "304" }, // 11 .{ .name = ":status", .value = "400" }, // 12 .{ .name = ":status", .value = "404" }, // 13 .{ .name = ":status", .value = "500" }, // 14 .{ .name = "accept-charset", .value = "" }, // 15 .{ .name = "accept-encoding", .value = "gzip, deflate" }, // 16 .{ .name = "accept-language", .value = "" }, // 17 .{ .name = "accept-ranges", .value = "" }, // 18 .{ .name = "accept", .value = "" }, // 19 .{ .name = "access-control-allow-origin", .value = "" }, // 20 .{ .name = "age", .value = "" }, // 21 .{ .name = "allow", .value = "" }, // 22 .{ .name = "authorization", .value = "" }, // 23 .{ .name = "cache-control", .value = "" }, // 24 .{ .name = "content-disposition", .value = "" }, // 25 .{ .name = "content-encoding", .value = "" }, // 26 .{ .name = "content-language", .value = "" }, // 27 .{ .name = "content-length", .value = "" }, // 28 .{ .name = "content-location", .value = "" }, // 29 .{ .name = "content-range", .value = "" }, // 30 .{ .name = "content-type", .value = "" }, // 31 .{ .name = "cookie", .value = "" }, // 32 .{ .name = "date", .value = "" }, // 33 .{ .name = "etag", .value = "" }, // 34 .{ .name = "expect", .value = "" }, // 35 .{ .name = "expires", .value = "" }, // 36 .{ .name = "from", .value = "" }, // 37 .{ .name = "host", .value = "" }, // 38 .{ .name = "if-match", .value = "" }, // 39 .{ .name = "if-modified-since", .value = "" }, // 40 .{ .name = "if-none-match", .value = "" }, // 41 .{ .name = "if-range", .value = "" }, // 42 .{ .name = "if-unmodified-since", .value = "" }, // 43 .{ .name = "last-modified", .value = "" }, // 44 .{ .name = "link", .value = "" }, // 45 .{ .name = "location", .value = "" }, // 46 .{ .name = "max-forwards", .value = "" }, // 47 .{ .name = "proxy-authenticate", .value = "" }, // 48 .{ .name = "proxy-authorization", .value = "" }, // 49 .{ .name = "range", .value = "" }, // 50 .{ .name = "referer", .value = "" }, // 51 .{ .name = "refresh", .value = "" }, // 52 .{ .name = "retry-after", .value = "" }, // 53 .{ .name = "server", .value = "" }, // 54 .{ .name = "set-cookie", .value = "" }, // 55 .{ .name = "strict-transport-security", .value = "" }, // 56 .{ .name = "transfer-encoding", .value = "" }, // 57 .{ .name = "user-agent", .value = "" }, // 58 .{ .name = "vary", .value = "" }, // 59 .{ .name = "via", .value = "" }, // 60 .{ .name = "www-authenticate", .value = "" }, // 61 }; /// Where each name's run begins and ends in `static`, as zero-based offsets. /// Entries sharing a name are contiguous in Appendix A — asserted below — so /// one hash gets the run and a short scan finds the value. const Run = struct { first: u8, last: u8 }; const by_name = blk: { @setEvalBranchQuota(20_000); var pairs: [static.len]struct { []const u8, Run } = undefined; var count: usize = 0; var i: usize = 0; while (i < static.len) { var j = i; while (j + 1 < static.len and std.mem.eql(u8, static[j + 1].name, static[i].name)) : (j += 1) {} // The property the run representation depends on: a name may not // reappear later in the table. A transcription that scrambled the // order would fail here rather than silently making some entries // unfindable. for (static[j + 1 ..]) |later| { if (std.mem.eql(u8, later.name, static[i].name)) { @compileError("static table entries for " ++ static[i].name ++ " are not contiguous"); } } pairs[count] = .{ static[i].name, .{ .first = i, .last = j } }; count += 1; i = j + 1; } break :blk std.StaticStringMap(Run).initComptime(pairs[0..count].*); }; /// The index of the static entry with this name and value, or null. /// /// Names are compared without regard to case because the encoder is fed them /// as the handler wrote them, and `Headers` deliberately keeps that spelling. /// Values are compared exactly — `GET` and `get` are different methods. pub fn findStatic(name: []const u8, value: []const u8) ?u8 { const run = by_name.get(name) orelse return findStaticSlow(name, value); var i = run.first; while (i <= run.last) : (i += 1) { if (std.mem.eql(u8, static[i].value, value)) return i + 1; } return null; } test findStatic { try testing.expectEqual(@as(?u8, 2), findStatic(":method", "GET")); // The name is matched without regard to case, the value exactly. try testing.expectEqual(@as(?u8, 31), findStatic("Content-Type", "")); try testing.expectEqual(@as(?u8, null), findStatic(":method", "get")); // A name in the table with a value that is not. try testing.expectEqual(@as(?u8, null), findStatic(":method", "PATCH")); } /// The lowest index of any static entry with this name, which is what a /// literal with an indexed name wants. Names are compared without regard to /// case, as in `findStatic`. pub fn findStaticName(name: []const u8) ?u8 { if (by_name.get(name)) |run| return run.first + 1; return findStaticNameSlow(name); } test findStaticName { // `:status` has seven entries, 8 through 14; the first is the one named. try testing.expectEqual(@as(?u8, 8), findStaticName(":status")); try testing.expectEqual(@as(?u8, 58), findStaticName("User-Agent")); try testing.expectEqual(@as(?u8, null), findStaticName("x-request-id")); } /// The case-insensitive fallback. `StaticStringMap` hashes exactly, so a name /// that is not already lower case misses it and lands here — which is the /// common path for a response, since the library's own `sendStatus` sets /// `Content-Type`. fn findStaticSlow(name: []const u8, value: []const u8) ?u8 { for (static, 0..) |entry, i| { if (token.eqlIgnoreCase(entry.name, name) and std.mem.eql(u8, entry.value, value)) { return @intCast(i + 1); } } return null; } fn findStaticNameSlow(name: []const u8) ?u8 { for (static, 0..) |entry, i| { if (token.eqlIgnoreCase(entry.name, name)) return @intCast(i + 1); } return null; } /// The overhead RFC 7541 §4.1 charges each entry, on top of its name and /// value. /// /// It is not the real cost of this data structure and is not meant to be. It /// is a fixed estimate so that two endpoints with entirely different /// representations agree about the exact moment an eviction happens — and /// they must agree, because an eviction one end makes and the other does not /// shifts every index after it. pub const entry_overhead = 32; pub const Dynamic = struct { /// Newest first, so that the HPACK index and the slot index differ by a /// constant and the code reads the way §2.3.3 draws it. Insertion is /// therefore an insert at zero — a move of at most a few hundred slots, /// since the capacity divided by `entry_overhead` bounds the count — and /// eviction is a pop from the end, which is the operation that must not /// be got wrong. entries: std.ArrayList(Entry) = .empty, /// The running total. A field rather than a computation because eviction /// compares against it on every insertion, and recomputing it is how the /// two drift apart. size: u32 = 0, /// The capacity in force, which a dynamic table size update sets. capacity: u32, /// The ceiling such an update may not exceed: `SETTINGS_HEADER_TABLE_SIZE` /// as this endpoint advertised it. max_capacity: u32, pub const Entry = struct { /// Owned. The field section these came from is gone by the time this /// entry is indexed; see the note at the top of `hpack.zig`. name: []const u8, value: []const u8, /// What this entry counts for against the table's capacity: its name /// and value plus `entry_overhead`, as RFC 7541 §4.1 defines it. pub fn size(e: Entry) u32 { return @intCast(e.name.len + e.value.len + entry_overhead); } test size { const e: Entry = .{ .name = "custom-key", .value = "custom-header" }; // RFC 7541 C.3.1 reports the table at 55 after inserting exactly this. try testing.expectEqual(@as(u32, 55), e.size()); } }; /// An empty table whose capacity starts at its ceiling, since no dynamic /// table size update has lowered it yet. pub fn init(max_capacity: u32) Dynamic { return .{ .capacity = max_capacity, .max_capacity = max_capacity }; } test init { var d: Dynamic = .init(4096); defer d.deinit(testing.allocator); try testing.expectEqual(@as(u32, 4096), d.capacity); try testing.expectEqual(@as(u32, 0), d.size); } /// Frees every entry, and the list that held them. `gpa` must be the /// allocator every `insert` was given. pub fn deinit(d: *Dynamic, gpa: Allocator) void { for (d.entries.items) |e| { gpa.free(e.name); gpa.free(e.value); } d.entries.deinit(gpa); d.* = undefined; } test deinit { var d: Dynamic = .init(4096); try d.insert(testing.allocator, "custom-key", "custom-value"); d.deinit(testing.allocator); } /// The entry at an HPACK index, which for the dynamic table starts at 62. /// Null for an index in the static table's range or past the newest /// live entry. /// /// The entry's strings are the table's and are freed when it is evicted, /// which an `insert` may do at any time. pub fn get(d: *const Dynamic, index: u32) ?Entry { if (index <= static.len) return null; const slot = index - static.len - 1; if (slot >= d.entries.items.len) return null; return d.entries.items[slot]; } test get { const gpa = testing.allocator; var d: Dynamic = .init(4096); defer d.deinit(gpa); try d.insert(gpa, "custom-key", "custom-value"); try testing.expectEqualStrings("custom-value", d.get(62).?.value); try testing.expect(d.get(63) == null); // An index in the static table is not this table's to answer. try testing.expect(d.get(2) == null); } pub const InsertError = Allocator.Error; /// Adds an entry, evicting from the end until it fits. /// /// RFC 7541 §4.4: "It is not an error to attempt to add an entry that is /// larger than the maximum size; an attempt to add an entry larger than /// the maximum size causes the table to be emptied of all existing /// entries and results in an empty table." That sentence is the whole /// reason this is not three lines, and it has a test of its own. pub fn insert(d: *Dynamic, gpa: Allocator, name: []const u8, value: []const u8) InsertError!void { const wanted: u32 = @intCast(name.len + value.len + entry_overhead); d.evictTo(gpa, if (wanted > d.capacity) 0 else d.capacity - wanted); if (wanted > d.capacity) return; const owned_name = try gpa.dupe(u8, name); errdefer gpa.free(owned_name); const owned_value = try gpa.dupe(u8, value); errdefer gpa.free(owned_value); try d.entries.insert(gpa, 0, .{ .name = owned_name, .value = owned_value }); d.size += wanted; } test insert { const gpa = testing.allocator; // Room for one 54-octet entry and not two. var d: Dynamic = .init(100); defer d.deinit(gpa); try d.insert(gpa, "custom-key", "custom-value"); try d.insert(gpa, "custom-key", "other-value"); // The newer is at 62, and the older was evicted to make room for it. try testing.expectEqualStrings("other-value", d.get(62).?.value); try testing.expect(d.get(63) == null); } pub const CapacityError = error{ /// A dynamic table size update above `SETTINGS_HEADER_TABLE_SIZE` /// (RFC 7541 §6.3). TableSizeTooLarge, }; /// A dynamic table size update: sets the capacity to `n`, evicting the /// oldest entries until what is left fits, or refuses an `n` above /// `max_capacity`. pub fn setCapacity(d: *Dynamic, gpa: Allocator, n: u32) CapacityError!void { if (n > d.max_capacity) return error.TableSizeTooLarge; d.capacity = n; d.evictTo(gpa, n); } test setCapacity { const gpa = testing.allocator; var d: Dynamic = .init(4096); defer d.deinit(gpa); try d.insert(gpa, "custom-key", "custom-value"); // Zero empties the table, which is how a peer says it may be freed. try d.setCapacity(gpa, 0); try testing.expect(d.get(62) == null); try testing.expectError(error.TableSizeTooLarge, d.setCapacity(gpa, 8192)); } /// Called when the peer acknowledges a SETTINGS frame of ours that /// changed `SETTINGS_HEADER_TABLE_SIZE` — **not** when that frame is /// sent. /// /// Until the acknowledgement arrives the peer is entitled to go on using /// the old size, so lowering this early makes a conformant peer look like /// it is breaking the rules. A real interoperability bug rather than a /// theoretical one. /// /// A capacity above the new ceiling is lowered to it, evicting as it goes; /// one below it is left alone, since raising it is the peer's to do with a /// size update. pub fn setMaxCapacity(d: *Dynamic, gpa: Allocator, n: u32) void { d.max_capacity = n; if (d.capacity > n) { d.capacity = n; d.evictTo(gpa, n); } } test setMaxCapacity { const gpa = testing.allocator; var d: Dynamic = .init(4096); defer d.deinit(gpa); d.setMaxCapacity(gpa, 1024); try testing.expectEqual(@as(u32, 1024), d.capacity); // And a size update may no longer go above it. try testing.expectError(error.TableSizeTooLarge, d.setCapacity(gpa, 2048)); } fn evictTo(d: *Dynamic, gpa: Allocator, limit: u32) void { while (d.size > limit) { const last = d.entries.pop() orelse break; d.size -= last.size(); gpa.free(last.name); gpa.free(last.value); } } }; const testing = std.testing; test "the static table is the one in Appendix A" { try testing.expectEqual(@as(usize, 61), static.len); try testing.expectEqualStrings(":authority", static[0].name); try testing.expectEqualStrings("", static[0].value); try testing.expectEqualStrings("www-authenticate", static[60].name); // The worked lookups RFC 7541 uses in Appendix C. try testing.expectEqual(@as(u8, 2), findStatic(":method", "GET").?); try testing.expectEqual(@as(u8, 6), findStatic(":scheme", "http").?); try testing.expectEqual(@as(u8, 4), findStatic(":path", "/").?); try testing.expectEqual(@as(u8, 8), findStatic(":status", "200").?); try testing.expectEqual(@as(u8, 1), findStaticName(":authority").?); try testing.expectEqual(@as(u8, 8), findStaticName(":status").?); try testing.expect(findStatic(":method", "PROPFIND") == null); try testing.expect(findStaticName("x-made-up") == null); } test "names are matched without regard to case, values exactly" { // Which is the path the library's own `sendStatus` takes, since it sets // `Content-Type` rather than `content-type`. try testing.expectEqual(@as(u8, 31), findStaticName("Content-Type").?); try testing.expectEqual(@as(u8, 31), findStaticName("content-type").?); // A method is case-sensitive and `get` is not `GET`. try testing.expect(findStatic(":method", "get") == null); } test "insertion, indexing and eviction" { const gpa = testing.allocator; var d: Dynamic = .init(256); defer d.deinit(gpa); try d.insert(gpa, "custom-key", "custom-value"); try testing.expectEqual(@as(u32, 10 + 12 + 32), d.size); // The newest entry is 62, immediately after the static table. try testing.expectEqualStrings("custom-key", d.get(62).?.name); try testing.expect(d.get(63) == null); // An index inside the static table is not this table's business. try testing.expect(d.get(61) == null); try d.insert(gpa, "second", "entry"); // And now the newest is 62 and the first has moved down. try testing.expectEqualStrings("second", d.get(62).?.name); try testing.expectEqualStrings("custom-key", d.get(63).?.name); } test "an entry larger than the capacity empties the table and is not added" { // RFC 7541 §4.4, quoted in `insert`. It is deliberately not an error. const gpa = testing.allocator; var d: Dynamic = .init(100); defer d.deinit(gpa); try d.insert(gpa, "small", "one"); try testing.expectEqual(@as(usize, 1), d.entries.items.len); try d.insert(gpa, &@as([40]u8, @splat('x')), &@as([40]u8, @splat('y'))); try testing.expectEqual(@as(usize, 0), d.entries.items.len); try testing.expectEqual(@as(u32, 0), d.size); } test "a size update evicts, and one above the ceiling is refused" { const gpa = testing.allocator; var d: Dynamic = .init(4096); defer d.deinit(gpa); try d.insert(gpa, "aaaa", "bbbb"); try d.insert(gpa, "cccc", "dddd"); try testing.expectEqual(@as(u32, 80), d.size); // Down to one entry's worth. try d.setCapacity(gpa, 40); try testing.expectEqual(@as(usize, 1), d.entries.items.len); // The one kept is the newest. try testing.expectEqualStrings("cccc", d.get(62).?.name); try d.setCapacity(gpa, 0); try testing.expectEqual(@as(usize, 0), d.entries.items.len); try testing.expectError(error.TableSizeTooLarge, d.setCapacity(gpa, 4097)); } test "the recorded size is always the sum of the entries" { const gpa = testing.allocator; var d: Dynamic = .init(300); defer d.deinit(gpa); const names = [_][]const u8{ "a", "bb", "ccc", "dddd", "eeeee" }; for (0..40) |i| { const n = names[i % names.len]; try d.insert(gpa, n, n); var total: u32 = 0; for (d.entries.items) |e| total += e.size(); try testing.expectEqual(total, d.size); try testing.expect(d.size <= d.capacity); } }