Part III FlexBuffers

Book contents · Previous: Part II FlatBuffers · Next: Part IV Quality and Performance

Chapters 10–18 of FlatBuffers & FlexBuffers: From Bytes to Mutable Memory. The trailer, width solver, strings, vector families, maps, views, builders, mutation, and verification.

This is the supplied first edition, pinned to its September 2026 source baseline. The laboratories and LiveFlex capstone are educational implementations and design proposals. The book overview explains the evidence limits; Reaktor’s performance review documents the current framework.

In this part

• Chapter 10: FlexBuffers starts at the end
• Chapter 11: Widths are a small layout solver
• Chapter 12: Keys, strings, and blobs are different objects
• Chapter 13: Every vector family, one at a time
• Chapter 14: A map is two coordinated vectors
• Chapter 15: Building a reader as a set of views
• Chapter 16: Building the writer from first principles
• Chapter 17: Mutation, sharing, and why one outlier matters
• Chapter 18: Verification is a small security boundary

Chapter 10: FlexBuffers starts at the end

A three-byte document

The smallest useful way to understand FlexBuffers is to decode a whole document containing the signed integer 13:

position:  0   1   2
byte:     0d  04  01
meaning:  13  tag width

The last byte is the actual byte width of the root slot. Here it is 1. The preceding byte is the packed type. The root slot occupies one byte immediately before those two trailer bytes. There is no separate front root pointer in this example. [1,4]

For a buffer of length N:

root_parent_width = bytes[N - 1]
root_packed_type  = bytes[N - 2]
root_slot        = N - 2 - root_parent_width

Validate the length and width before performing the final subtraction. An input shorter than three bytes cannot contain even the smallest root. A last byte of 3 is not a three-byte width; it is invalid as a root width.

Split the packed type

A packed type stores a six-bit type code in the high bits and a two-bit width code in the low bits:

type_code  = packed >> 2
width_code = packed & 3
child_width = 1 << width_code

Thus 0x04 is type 1 with width code 0. Type 1 is a signed integer, and width code 0 corresponds to one byte. The last byte of the document was also 1, but these are different encodings in different places: the tag stores the logarithmic width code; the trailer stores the actual width. [1]

For a true boolean, the complete buffer is 01 68 01. The packed type 0x68 is decimal 104, and 104 >> 2 is 26, the boolean type. Boolean is an inline type even though its numeric type code is well above the indirect types. Do not decide inline versus indirect with an oversimplified “type code below some threshold” rule. [1]

Inline values and indirect values

An inline root stores its scalar payload in the root slot. An indirect root stores an unsigned backward distance there. For an indirect slot at position P, the destination is:

target = P - unsigned_value_at(P, parent_width)

The distance is measured from the offset slot itself. It is not measured from the beginning of the buffer, the trailer, or the beginning of the enclosing vector. The source must be checked before subtraction so a malicious distance cannot underflow the position.

The normal builder writes referenced children before their parents and appends the root at the end. Backward references fit that construction order. Like the backward-growing FlatBuffers builder, this avoids unresolved ordinary child references, but the two formats choose opposite wire directions. [1,3,4]

Why the trailer contains two widths in disguise

The root's final byte tells us how many bytes to read for the root's own slot. The packed tag's low bits tell us the width relevant to the object being described. When the root references a vector, that is the vector's element width. When it references a string, that is the string's length-prefix width.

These widths can differ. A large vector may have eight-byte elements but lie only a short distance before the root slot, allowing a one-byte root offset. A tiny string may use a one-byte length prefix but be referenced from an eight-byte slot in a wide parent vector.

A reliable internal reference object therefore carries at least the buffer, the slot position, the parent slot width, the child width, and the type. Collapsing the two widths into one field is the source of many plausible but incorrect reimplementations. The official Reference stores them separately. [1]

A string root

The complete buffer for "Ada" produced by the companion is:

03 41 64 61 00 04 14 01

The final width is 1. The packed type is 0x14: type 5, string, with a one-byte child width. The root slot is at position 5 and contains 4. Its target is 5 - 4 = 1, the A byte. The one-byte length prefix is immediately before the target, at position 0, and contains 3. The zero terminator follows the three content bytes.

This example is eight bytes long. No step required an application schema. The tag, the trailer, the relative reference, and the prefix provided the structural information. The reader still needs to decide whether it accepts a string as its application root and whether "Ada" is a meaningful value for that application.

What the trailer does not provide

The trailer does not tell a stream receiver where the document ends until the receiver already knows which bytes belong to it. An external frame or containing object must supply the extent. Nor does the trailer contain a checksum, authentication tag, schema version, or application type identifier. Those belong in an envelope or a deliberate root convention when required.

A root map with a version field can be an application convention, but it is not a built-in FlexBuffers protocol version field. Keep transport framing, application versioning, and the core byte format separate.

Checkpoint

Exercise 11. Decode 01 68 01 without consulting an API. Then explain why a packed width code of 3 is valid while a final root-width byte of 3 is invalid.

Chapter 11: Widths are a small layout solver

The four storage widths

FlexBuffers uses widths of 1, 2, 4, or 8 bytes for scalar slots, offsets, and relevant length fields. These are fixed-width values once the layout has been chosen; they are not variable-length integers decoded byte by byte until a continuation bit ends. Width metadata tells the reader how much to load. [1]

For an unsigned integer, choose the smallest width whose range contains the value. For a signed integer, choose the smallest width whose signed range contains it. The transitions differ: unsigned 255 fits in one byte, but signed 255 does not. Signed -128 fits; signed -129 does not.

The official signed-width helper uses bit operations resembling a signed-to-unsigned range transformation. That does not mean signed values are stored with zigzag encoding. The payload remains a width-selected two's-complement integer. [1]

A parent gives all its slots one stride

A heterogeneous vector uses a common element width. It may contain a one-byte-sized integer, a string reference, and a double, but the slots themselves all occupy the chosen vector width. The values have different meanings and type bytes, not different slot strides.

This makes index calculation simple: V + i * W. It also means a single wide inline value can widen every slot. The writer has to choose W large enough for the count, every inline scalar, and every relative offset stored in those slots. The referenced children's own widths are separate. [1]

The count participates because a variable-length vector stores its count in the same width as its elements. A typed vector of 256 tiny integers therefore cannot use one-byte slots: its count does not fit. This can surprise someone who considers only the element values.

A full example with different widths

Here is the companion's encoding of the untyped vector ["hi", 300]:

02 68 69 00 02 00 05 00 2c 01 14 05 06 29 01

Read that table from the bottom first. The root offset occupies one byte, yet its destination vector has two-byte elements. Then read the string element: its offset occupies two bytes, yet the destination string has a one-byte length prefix. Both differences occur in one fifteen-byte document.

Why distance depends on the candidate width

Suppose a child is already at position 0, the current buffer length is 254, and a two-element vector will be written next. With one-byte elements, its count is at 254 and its element slots are at 255 and 256. An offset from the first slot back to position 0 fits in one byte; the offset from the second does not.

Trying two-byte elements changes the layout. Alignment rounds 254 to 254 because it is already even. The two-byte count occupies positions 254–255. The element slots are now at 256 and 258. Their distances are larger, but two bytes can hold them.

It is incorrect to compute distances once using one-byte slots, discover that some need two bytes, and then write the wider layout without recomputing positions. The earlier slots and padding have moved the later slots. Width choice is a small constraint-solving problem, not just a maximum over already known distances.

A simple global candidate algorithm

The companion deliberately tries the four widths in ascending order. For each candidate it calculates the aligned prefix position, the actual position of every future slot, and whether every value fits. The first candidate that satisfies all constraints is selected.

for W in {1, 2, 4, 8}:
    B = align(current_size, W)
    check count fits W, when a count exists
    check map prefix references, when present
    for element i:
        P = B + (prefix_slots + i) * W
        if element is inline:
            check its required width <= W
        else:
            check target <= P
            check P - target fits W
    if all checks pass:
        choose W

The official builder factors the computation into per-value width helpers and vector construction. The global trial formulation is easier to explain and independently implement. Both must honor the final slot positions, alignment, and parent/child width distinction. Exact output bytes can differ while remaining valid. [1]

Floats and indirect numeric values

An inline float has to be written at the parent's slot width, which must be four or eight bytes. A numeric value can also be stored out of line using an indirect numeric type. Its payload then has its own width, and the parent stores only an offset. This can prevent one large value from widening an otherwise narrow heterogeneous vector.

Do not assume indirection always helps. The out-of-line scalar requires payload bytes and alignment. Its offset can itself require a wider parent slot if the distance is large. Chapter 17 calculates a concrete case and explains how to decide rather than applying indirection everywhere.

Checkpoint

Exercise 12. In ["hi", 300], identify the width used for each of these operations: reading the root offset, reading the vector count, reading the string offset, and reading the string length.

Exercise 13. Explain why a vector of 256 booleans may occupy substantially more than 256 payload bytes in the wire representation even though each logical value needs only one bit.

Chapter 12: Keys, strings, and blobs are different objects

A key has no length prefix

A key is a zero-terminated sequence used for map keys and the standalone key type. The offset points at its first content byte. Its end is found by scanning for the terminator. There is no independent stored byte count before that target. Map lookup in the pinned C++ reader compares keys with C-string-style lexical comparison. [1]

An embedded zero would end the key, so an application-facing key constructor should reject it rather than silently creating two different interpretations of the same supplied string. The companion also requires valid UTF-8 for newly written keys. Its byte ordering is lexical ordering of the encoded bytes, not locale-aware collation or Unicode normalization.

The keys "A" and "a" are different. Canonically equivalent Unicode strings with different byte sequences are different unless the application normalizes them before insertion. The format does not make those policy decisions for you.

A string has a length and a terminator

A FlexBuffers string is laid out as:

[length in W bytes][content bytes][zero]
                    ^ target

The reference's child width tells the reader how wide the length prefix is. The prefix is immediately before the target. The offset slot that reaches this string may use a different width. The length counts content bytes and excludes the terminator. [1]

Because the length exists, a string can contain embedded zero bytes while retaining its full length. A reader using the length can return "a\0b" as three bytes; one using strlen sees only "a". This distinction is especially important when importing legacy typed string vectors, where the necessary per-string prefix-width information was lost.

The string prefix widens at length boundaries, but the content remains a byte sequence. A 256-byte string has a two-byte length prefix; it does not store every character in two bytes. The vector count/stride coupling discussed in Chapter 11 does not apply to string content.

A blob is not a typed byte vector

A blob uses a length prefix followed by raw bytes, with no required string terminator. Its content is not interpreted as UTF-8. The child width describes the length prefix, not a stride larger than one for the payload. [1] This makes a blob the natural representation for arbitrary binary data. A typed unsigned vector can instead communicate a sequence of unsigned numeric values, but its element width must also hold the vector length. Using a blob for a large byte payload avoids widening every byte merely to represent a larger count.

The distinction survives even if both happen to contain the same byte values. A blob is one binary object. A typed vector exposes numeric elements. A semantic compatibility layer should not silently convert between them unless its contract explicitly treats those forms as equivalent.

Empty values reveal useful edge cases

The companion emits these complete documents:

For the empty blob, the first byte is its zero length. Its content target is position 1, which is also where the root offset slot is written. The backward distance is therefore zero. This is valid because the blob has no content bytes to consume. A blanket rule that every indirect offset must be strictly positive would reject this ordinary empty representation.

A zero offset is not a blanket permission for arbitrary self-reference either. The target type, prefix, extent, and traversal rules still matter. A verifier must judge the actual object, not replace all that reasoning with one overbroad distance rule.

Pooling changes aliasing

A builder can reuse the same serialized key or string for multiple references. The pinned C++ builder pools keys by default and offers optional string pooling. It can also reuse previously built values explicitly. These choices reduce duplicate bytes at the cost of construction bookkeeping. [1]

Now suppose two fields reference one pooled string. A same-length in-place edit changes the shared payload. Both fields observe the new text. A caller expecting value-copy semantics would be surprised, even though the mutation preserved the wire layout perfectly.

Pooling therefore belongs in the ownership and mutation story. “Immutable strings are shared” and “mutable strings behave like independently owned values” are compatible only with a rule such as copy-on-write or replacement of references. They are not compatible merely because the API uses the word string.

Boundaries and text validation

A safe reader checks the length prefix before reading it, the content extent before exposing it, and the terminator according to the contract it promises. UTF-8 validation is an additional scan. A structural verifier's success should not be assumed to imply Unicode validity or application-specific text rules.

For very large payloads, repeated validation can dominate a workload. A verified immutable owner can cache the result for a particular range and interpretation. A writable buffer cannot retain that conclusion after arbitrary mutation. Cache invalidation here is a correctness issue, not just a performance detail.

Checkpoint

Exercise 14. Why does a 300-byte blob avoid the width inflation of a 300-element typed byte vector? Draw the two layouts and identify which quantities use the container width.

Chapter 13: Every vector family, one at a time

Untyped vectors carry a separate type table

An untyped vector has a count before its data, uniformly sized slots, and one packed type byte per element after the slot array:

[count: W][slot 0: W] ... [slot N-1: W][tag 0] ... [tag N-1]
           ^ V

Its element slot is at V + i * W. Its type byte is at V + N * W + i. The type table is byte-dense; its entries are not spaced W bytes apart. This is one of the most important indexing formulas in a reimplementation. [1]

The complete untyped vector [1, 2, 3] is:

03 01 02 03 04 04 04 06 28 01

The count is at position 0. Slots begin at 1. Their tags begin at 4. The root slot is at 7, stores distance 6, and therefore points to position 1. The root tag is 0x28, an untyped vector with one-byte elements. The total is ten bytes.

Typed vectors remove the per-element tags

If all elements have one supported type, the vector's own type identifies it. The count and slot array remain, but the type table disappears. The active variable-length typed families discussed here are signed integers, unsigned integers, floats, keys, and booleans. [1]

For [1, 2, 3] as a typed signed vector, the companion emits:

03 01 02 03 03 2c 01

The root is now at position 4 and stores distance 3. 0x2c is the packed code for a typed signed vector with one-byte elements. The result is seven bytes: the three element tags have disappeared.

Typed does not mean that an application had to declare a schema before creating the document. A builder can observe the element types at runtime and choose a typed representation. This is an early example of a theme used in the capstone: schemaless interfaces can still exploit homogeneous data.

Fixed typed vectors remove the count too

Numeric tuples of length two, three, or four have dedicated type codes. Their length is encoded in the vector type, so no length prefix or element type table is stored. The three supported numeric element kinds are signed integer, unsigned integer, and float. [1]

For fixed typed [1, 2, 3], the complete document is:

01 02 03 03 4c 01

The three element bytes begin at position 0. The root slot at position 3 stores distance 3. The tag 0x4c identifies a fixed signed triple with one-byte elements. The total is six bytes.

For a fixed-vector type code T between 16 and 24:

length = 2 + (T - 16) / 3
element_type = 1 + (T - 16) % 3

The divisions are integer divisions. There is no corresponding fixed boolean tuple family in these type codes. A writer must reject unsupported combinations rather than manufacture a plausible-looking arithmetic tag.

The deprecated typed-string family

The historical typed string-vector type removed the per-element tags. That also removed the per-string width information needed to locate each string's length prefix. Strings of different lengths can require different prefix widths, so one vector-level type is insufficient to recover that information reliably.

The pinned reader treats this legacy family using key-like access as a compatibility workaround: it can find a terminating zero but does not recover the full length-prefix semantics of arbitrary strings. Embedded zeros make the loss especially visible. New writers should use an untyped vector of strings, retaining each child's width in its tag, or a key vector when key semantics are actually intended. [1]

Do not interpret the continued presence of an enum value as a recommendation to emit it. Compatibility readers often retain old forms precisely so writers can stop producing them without making old data wholly unreadable.

Count width can dominate element width

A variable-length typed vector still uses one width for its count and its elements. The companion tests the transitions at 255/256 and 65,535/65,536 elements. Even a vector filled entirely with the integer 1 widens at these transitions.

The pinned C++ source also has a direct scalar-vector construction path based on the C++ element size. It checks that the count fits that width rather than promising to widen every such input automatically. API selection can therefore matter at these boundaries. A blob is often the better model for a large uninterpreted byte sequence. [1]

A fixed tuple does not have a count prefix, so this particular count-width issue disappears. Its element values still need to fit the chosen common width, and its float elements still need an implemented floating width.

Typed scans and heterogeneous discovery

A typed numeric vector supports a regular scan: one type and one width can be selected before entering the loop. An untyped vector requires consulting tags unless the consumer has separately proved a stronger invariant. The absence of per-element dispatch can matter more than a few bytes of metadata for a long numerical operation.

Conversely, a heterogeneous vector can mix records, blobs, strings, and numbers without an application schema. Its generality is real, and so is its execution cost. A good system preserves this flexibility at its boundaries while offering typed paths for hot homogeneous regions.

Checkpoint

Exercise 15. Starting from the three encodings of [1, 2, 3], account for every byte removed by the typed and fixed typed forms. Then explain why a typed vector of arbitrary maps is not created by simply adding a new element-type number to the existing arithmetic.

Chapter 14: A map is two coordinated vectors

Begin with sorted keys

A FlexBuffers map associates string keys with values. Its wire representation is not a hash table. It stores a sorted typed vector of key references and a corresponding heterogeneous vector of values. Position i in the key vector corresponds to position i in the value vector. Sorting must therefore move key/value pairs together. [1]

For the logical map {"foo": 13, "bar": 14}, the wire order is bar, then foo. The order is bytewise lexical key order, not insertion order. A reader can binary-search the key vector, then index the value vector using the resulting position.

The cost of a lookup includes key comparison. Saying only “logarithmic” hides the work needed to compare long strings or strings with a common prefix. Later, the capstone will use interned key IDs and a hash index for repeated mutable lookups, then restore lexical order when exporting.

The map prefix

Let V be the start of the value slots and W their width. Three fields precede the value slots:

V - 3W : backward offset to the key-vector data
V - 2W : actual byte width K of key-vector elements
V -  W : number of values N
V       : value slots, followed by N type bytes

The key-vector data has its own count immediately before it, using width K. The key-vector reference in the map prefix is read using W, because that prefix belongs to the value-side layout. Individual key offsets are read using K. The prefix stores the actual width—1, 2, 4, or 8—not the logarithmic packed-type width code. [1]

This creates a third width relationship to remember: root width, map value width, and key-vector width can all be independently relevant. The strings used as keys are still terminated byte strings with no length prefix.

Decode a complete map

The companion emits this twenty-one-byte document:

62 61 72 00 66 6f 6f 00 02 09 06 02 01 02 0e 0d 04 04 04 24 01

Start at the trailer. The root slot is at 18, and the map data begins at 14. The map tag gives W = 1. The prefix is therefore at positions 11, 12, and 13. Position 11 points to the key-vector data at

9. Position 12 tells us to read its elements and count with width 1. Position 8 supplies its count.

Only after those steps do we compare a requested key. Finding foo gives index 1, so its value is at 14 + 1 * 1 = 15, with its tag at 14 + 2 * 1 + 1 = 17.

Key width and value width need not match

Long keys placed early in a buffer can require two-byte key offsets even when a map has few enough entries, narrow enough values, and a nearby enough key vector for one-byte value slots. Conversely, a large inline numeric value can widen the value vector without widening each key offset.

This is why the key-vector width is stored explicitly in the map prefix. Inferring it from the map value width would work on many small examples and fail on exactly the documents where width compression is doing useful work.

A good test corpus must deliberately produce such different-width maps. Small maps with short keys often exercise only the W = K = 1 case and can hide a broken implementation for a long time.

Duplicate keys and absent values

A map must have a well-defined lookup policy. The pinned builder sorts entries and exposes a duplicate-key indication rather than silently making all duplicates retrievable. A new strict writer should reject duplicates or apply a clearly documented replacement policy before serialization. The companion rejects duplicate keys. [1]

A missing key is different from a present key whose value is null. The companion's find returns std::optional<Ref>, preserving that distinction. A convenience API that returns a null-like reference for missing data can be useful, but it should not be used where presence itself matters.

Likewise, structural verification alone should not be assumed to establish ordering, uniqueness, and equal key/value counts. The companion's strict profile checks those explicitly. Chapter 18 compares that policy with the pinned upstream structural verifier.

Sharing key vectors

The wire layout permits multiple maps to reference the same key vector when their field population and order agree. That can amortize repeated field names and key-offset arrays. Sharing keys individually and sharing an entire key vector are different optimizations.

The pinned C++ source exposes a key-vector-sharing flag, but its EndMap implementation still contains a TODO at the point where that sharing would be performed. Do not infer implemented behavior from the enum name alone. The format permits the optimization; this particular inspected code path does not establish that it performs it. [1]

Checkpoint

Exercise 16. Starting from the map's root at position 18, list every load required to obtain the value for foo. Identify the base used by every offset and the width used by every load.

Chapter 15: Building a reader as a set of views

The reference object is not the wire object

The companion represents a reference with these logical fields:

struct Ref {
    ByteSpan bytes;
    std::size_t slot;
    unsigned parent_width;
    unsigned child_width;
    Type type;
};

This C++ structure is a navigation aid. It is not serialized. Its size is not the size of a FlexBuffers value. Its span borrows an allocation; its position and widths tell the reader how to interpret that allocation. A production library can use more compact fields or specialized views when measurement justifies them.

The important invariant is semantic: slot identifies the location from which the parent stores this value. If the value is inline, load it at slot with parent_width. If it is indirect, read its offset with parent_width, compute the target, and interpret the destination using child_width and type.

Scalar accessors should make conversion policy explicit

The teaching reader's as_int() accepts signed direct or indirect integer types. It rejects an unsigned integer rather than silently narrowing it. as_uint() and as_float() similarly have explicit accepted families. This strictness prevents a malformed or unexpected application shape from quietly becoming a plausible default value.

The official C++ convenience API has broader conversion behavior and default-like results for some mismatches and missing accesses. That can be useful for dynamic data exploration, but it is not a substitute for validation. Applications that depend on exact type and presence should check those conditions explicitly. [1]

A separate conversion API can offer checked conversions: an unsigned value may convert to signed only when it fits; a floating value may convert to integer only under a specified rounding and range policy. Keeping that operation separate makes both correctness and performance easier to reason about.

Container access is mostly arithmetic

For an untyped vector, at(i) first checks that i < count. It computes the slot using the container width and reads the packed type from the byte-dense type table. The resulting child Ref gets the container width as its parent_width and the tag's width as its child_width.

For a typed vector, the element type is obtained from the vector type rather than a type table. Inline numeric elements use the vector width as their parent width. A key element follows an offset of that width and scans its target for a terminator. For a fixed numeric tuple, the length comes from the type code rather than a prefix.

This is why separate Vector, TypedVector, and fixed-vector views can be useful: the view can establish the representation once and provide a simpler loop. The companion keeps the main logic in one Ref for readability; the official implementation uses several specialized wrapper classes. [1]

Map lookup is an indexed relationship

A map view first recovers its key-vector view. Binary search compares the requested key with keys at selected indices. Once a match is found, the same index is applied to the value vector. The keys and values must agree in count and order.

A successful bounds check does not establish sortedness. Calling binary search on unsorted keys can return “missing” for a key that is physically present. This is not an out-of-bounds crash; it is a semantic failure. Verification and application API design need to account for both kinds of error.

A useful optimization for repeated lookups is to cache a validated key position or a compiled access path. Such a cache belongs to a particular immutable buffer or a particular mutable version. Reusing it after a structural edit without a version check changes a performance optimization into a correctness bug.

Do not let convenience hide ownership

Consider this incorrect conceptual function:

Ref make_root() {
    Writer writer;
    auto bytes = writer.finish(Writer::integer(13));
    return verify(bytes); // Wrong: bytes dies on return.
}

auto bytes copies the returned vector in this example, but that copy is still local. Returning a view into it does not extend its lifetime. Using const auto& would instead borrow the writer's storage, which also dies on return. Neither spelling fixes the ownership problem.

Return the owning bytes, or return an owning verified-buffer object whose root view is tied to that owner. A reader library should make its common correct use easier than its common dangling-view mistake.

A trusted fast path is a different contract

After a buffer is verified and immutable, a specialized internal accessor can omit checks that are already established. This is a reasonable optimization. It must not be accidentally exposed as the untrusted-input API.

One design uses a token or owner type produced only by successful verification. Another keeps unchecked accessors private to generated or validated traversal code. The exact technique matters less than making the trust transition visible and preventing later mutation from invalidating it silently.

The companion does not claim to implement this optimized typestate boundary. It leaves many checks in place and exposes plain structs for study. A production API should make representation descriptors opaque enough that callers cannot forge inconsistent type, width, and payload combinations.

Checkpoint

Exercise 17. Design separate get_signed() and convert_to_signed() APIs. Specify how each handles a null, an unsigned value larger than INT64_MAX, a non-integral float, and a missing map key.

Chapter 16: Building the writer from first principles

Store construction descriptors, not unstable pointers

The companion's Encoded descriptor contains a type, a required width, a payload, and an owner identity. For an inline scalar, the payload holds its bits. For an indirect object, it holds an absolute position in the writer's current byte sequence. Those positions remain valid when the vector backing the writer reallocates, because the bytes retain their logical positions.

The owner identity rejects accidentally using a child from one writer in another writer. The writer itself is non-copyable and non-movable in this teaching implementation so that its identity stays simple. A more elaborate movable builder could use an independent stable state object instead.

Public descriptors are convenient in a laboratory but are not a hardened application boundary. A production implementation should keep constructors controlled so callers cannot claim that a wide payload requires only one byte or forge a child position that was never emitted.

Emit children eagerly

Strings, keys, blobs, and indirect scalars can be written when they are created. The writer records their payload positions and widths in descriptors. A vector or map can then be constructed from descriptors for already-existing children and inline scalar values.

For a string, choose the width of its length, align, write the length, remember the content start, write the bytes, and write the terminator. For a blob, omit the terminator. For an indirect scalar, align to the scalar's width, write its payload, and remember that position.

Nothing in this process requires final buffer addresses. Only the current logical length and the fixed format rules matter. This is the benefit of position-based construction state.

Close a vector in two phases

The first phase solves its width using the candidate algorithm in Chapter 11. The second phase writes the chosen representation. For an ordinary heterogeneous vector, that means padding, count, slots, and type bytes. For a typed vector, omit the type bytes. For a fixed numeric tuple, omit the count as well.

When writing an inline scalar's type byte in a heterogeneous vector, the stored width reflects the actual parent slot width. When writing an indirect value's type byte, it preserves the child's width. This is the writer-side counterpart of the reader's two-width rule. [1]

A useful invariant is: after width selection succeeds, the emission phase should not discover a new representability problem. Keep the arithmetic used by the solver and the arithmetic used by emission visibly equivalent. The companion still checks offset fit during writing so a defect fails loudly rather than silently truncating bytes.

Close a map without losing associations

The map builder accepts pairs. It sorts those pairs by encoded key bytes, rejects duplicates, writes or reuses keys, constructs the typed key vector, and then constructs the value vector with its three-field map prefix.

Avoid sorting a raw interleaved array through an unrelated aggregate pointer in a new implementation merely because it looks compact. A vector of actual pairs makes the object model and association invariant explicit. Only replace that representation after profiling and a careful aliasing review.

The companion does not pool keys or strings. That keeps the initial implementation small and makes fixture layouts easy to inspect. Pooling is a separate optimization that must preserve ownership, offset validity, and mutation semantics. The official builder's flags and pools provide useful source material once the basic writer is correct. [1]

Finish the document

The root has no parent container to tell the reader its slot width. The writer therefore selects and aligns the root slot, writes the root value or backward offset, writes its packed type, and finally writes the actual root slot width. After finishing, the writer is sealed.

There must be exactly one chosen root. A stack-based public builder enforces matching start/end calls and a single remaining root value. The companion uses explicit returned descriptors instead, so its finish(root) names the root directly. Both are API choices over the same trailer representation.

Sealing prevents ordinary writes from appending bytes after the trailer and changing which value GetRoot would discover. Reusing a builder requires resetting all relevant construction state, not just clearing the byte vector. Pools, duplicate tracking, pending values, and finished state deserve tests of their own.

Exception and allocation behavior

The educational writer does not promise transactional rollback after every allocation failure. An operation may have appended some unreachable construction bytes before throwing. No completed output is returned from the failing operation, but the caller should not assume the builder remains suitable for arbitrary continued use.

A production builder can provide a strong guarantee by recording a checkpoint of byte length and scratch state, then rolling back on failure. Pools complicate rollback because they may have published references to newly written positions. A temporary operation arena or staged pool insertion can keep those updates atomic at the API level.

Do not call a builder “allocation-free” merely because it appends to one vector. Capacity growth, temporary descriptors, sorting storage, and pooling indexes all count. Reserve intelligently, measure allocation count, and distinguish the final buffer size from peak construction memory.

Checkpoint

Exercise 18. Add a builder checkpoint/rollback operation. List every state component that must be restored when an attempted map construction fails after writing some keys but before writing its value vector.

Chapter 17: Mutation, sharing, and why one outlier matters

What the official mutation methods can do

The pinned C++ Reference exposes experimental mutation methods for numeric values, booleans, and strings. Numeric updates can succeed when the replacement fits the existing representation. The string mutation path requires exactly the existing byte length. These operations do not turn the buffer into a general growable object store. [1]

The companion's mutate_int is deliberately narrower: it accepts signed direct or indirect integers, verifies that the supplied mutable owner is the allocation the reference borrows, and returns false when the new value needs a larger width. Failure leaves the value unchanged. Its same-length string mutation also requires valid UTF-8 according to the teaching profile.

A same-width byte update still requires writable storage. A const view does not prove the allocation was originally mutable. A buffer backed by read-only memory or a truly const object must not be written through a cast. Nor is a multi-byte update automatically safe against concurrent readers.

The scalar outlier example

Consider an untyped vector of 100 signed integers. Ninety-nine values are 1, and one is INT64_MAX. If all are inline, every slot needs eight bytes. The type table needs another 100 bytes. The count occupies eight bytes, and the root needs enough offset width to reach back over the vector.

The companion emits 912 bytes for this layout. When the wide value is stored as an indirect integer before the vector, the other 99 inline values and the offset to the outlier all fit in one-byte slots. The complete document becomes 212 bytes.

These are generated fixture sizes, not estimated benchmark speedups. The reduction is exactly 700 bytes for these particular layouts. Reading the exceptional value now includes an extra indirection. Building it required an additional out-of-line object. The smaller working set may help many operations, but size reduction alone does not establish lower latency for every access pattern.

Derive the approximate trade-off

Ignoring padding and root differences for a moment, widening an N-element heterogeneous vector from w to W adds approximately N * (W - w) slot bytes, plus any count-width difference. Moving one scalar out of line adds its payload and replaces it with an offset that must fit the narrow parent.

The potential saving is therefore large when N is large and the exceptional values are few. It is small or negative for tiny vectors, many exceptional values, or large offset distances that widen the parent anyway. A real optimizer must solve the resulting layout, not use the approximation as a guarantee.

This is an example of a broader design principle: local compression decisions can have nonlocal effects when containers use a shared stride. The cheapest representation of one value in isolation may not minimize the size of the containing document.

Reserving width is not reserving arbitrary capacity

The official builder has ForceMinimumBitWidth, which influences vector/map slot width in the inspected implementation. This can provide room for later numeric changes in those slots. Its use in vector construction should not be generalized into a promise that every standalone root scalar or separately emitted indirect scalar is automatically widened by that setting. [1]

Even a deliberately wide slot does not provide room to append elements. A vector's type table begins immediately after its current slot array, and its count is part of the layout. A string's length and terminator describe its current content. Reserving native allocation capacity in the backing std::vector does not create a standard capacity field in the wire format.

Choose the reservation policy according to the expected edits. A few counters can be given wide slots. A frequently growing collection is a different problem and usually deserves a different live representation.

Moving bytes changes some offsets, not all

Let an old relative distance be D = P - T, where P is the offset slot and T its target. If an edit moves them by different amounts, the new distance is:

D_new = D + movement_of_slot - movement_of_target

Moving the entire buffer as one unit leaves every internal distance unchanged. Inserting bytes between a target and its referencing slot changes that distance. Moving a subtree as a block can preserve internal references while changing references that cross the subtree boundary.

This is why “relative offsets make relocation easy” needs a scope. Whole-buffer relocation is easy. Arbitrary internal insertion is not automatically easy. Every crossing reference, every width threshold, and every affected container boundary must still be accounted for.

Aliases make mutation observable elsewhere

The companion test writes one string object and places two references to it in a vector. Replacing "Ada" with "Bob" through the first reference makes the second reference read "Bob" too. No bytes moved, no widths changed, and the effect is still broader than one field.

A mutable API must choose whether shared objects have identity semantics or value semantics. Identity semantics make aliases intentionally observe mutations. Value semantics require replacement or copy-on-write before a shared payload is changed. The capstone uses stable identity for containers and treats text values as replacement values in its baseline, avoiding an accidental mixture.

Checkpoint

Exercise 19. Reproduce the 912-byte and 212-byte fixtures. Explain the root width in each, not just the vector payload. Then construct a case where indirection increases total size.

Chapter 18: Verification is a small security boundary

Begin with the threat model

A buffer from a file, network, plugin, or another language must be treated as an arbitrary byte sequence until validated. It may be truncated, contain invalid widths, describe enormous lengths, point outside itself, repeat the same expensive object many times, or encode a shape that is structurally readable but semantically invalid for your API.

A verifier should state which of these problems it handles. Bounds safety, canonical encoding, UTF-8 validity, sorted map keys, duplicate policy, recursion limits, and application rules are not interchangeable. A function named VerifyBuffer is only as strong as its actual checks.

The order of checks matters

Start with the trailer length and root width. Construct a bounded root descriptor. Validate the type code. For an inline value, validate the slot extent and any profile rules for its type. For an indirect value, read the offset using the parent width, check that subtraction is permitted, and only then resolve the target.

Next validate any prefix before reading it. A string needs a length prefix and a content range. A vector needs a count, a checked multiplication by stride, and possibly a type table. A map needs both vectors and the relation between them. A fixed tuple has no count prefix, so its type determines the extent.

The safe arithmetic patterns from Chapter 2 should appear repeatedly. Large unsigned fields are not inherently suspicious; unbounded arithmetic using them is. A verifier must be correct at the maximum representable values, not merely at typical application sizes.

Structural verification versus a strict application profile

The pinned upstream FlexBuffers verifier checks many structural properties and supports depth limits and an optional reuse tracker. Its inspected implementation does not establish every property a strict map/text API might expect. In particular, its map verification does not compare key and value counts or enforce sorted unique keys; its string terminator helper checks that the terminator position is in range rather than checking the byte's value; it does not perform UTF-8 validation. [1]

Those are observations about the pinned code, not a claim that all upstream versions have the same behavior or that the verifier is intended to enforce every possible application convention. The engineering lesson is to read the checks you depend on and add a profile layer where necessary.

The companion's default profile additionally requires valid UTF-8 for text, an actual zero string terminator, equal map counts, strictly increasing unique keys, canonical boolean/null payloads, and implemented float widths. It rejects reserved type tags. It can allow or reject the deprecated typed-string family, with its documented key-like interpretation.

Budgets are correctness features

A recursive implementation needs a depth budget to prevent stack exhaustion. A work budget prevents a small-looking root from causing unbounded repeated traversal. A byte-scan budget is also valuable because a million references to one very long key can repeatedly trigger expensive scans even when the number of visited nodes is bounded.

The teaching verifier has depth and visit budgets; it does not implement a separate total byte-scan budget or reuse memoization. Its malformed-input tests use bounded input sizes. A production verifier should add those resource controls and report budget exhaustion separately from structural corruption.

A fully iterative traversal can replace recursion with an explicit work stack. That removes reliance on the machine call stack, but it does not remove the need to bound total work and temporary memory. An attacker can exhaust an unbounded heap worklist too.

Sharing and memoization

When the same immutable object is referenced many times, a verifier can remember that it has already validated that interpretation. A cache key must include the buffer identity and enough information to distinguish different interpretations, such as target position, type, and child width. Reusing a result for the same address under a different type is not automatically valid.

A traversal should distinguish an object currently being explored from one whose validation is complete. That distinction detects cycles or overlapping pathological interpretations rather than treating an incomplete result as a proof. Normal builders produce children-before-parents structures, but a verifier must cope with arbitrary bytes, not just normal builders.

Memoization consumes memory. The pinned implementation offers an optional byte-indexed reuse tracker with a memory cost proportional to buffer size. Other designs can use sparse tables or bounded caches. The correct choice depends on sharing density and the allowed validation memory budget. [1]

Verification has a lifetime

A successful result applies to the bytes that were checked. If a caller then changes a length, tag, or offset, later unchecked navigation may be unsafe. If another thread changes payload while it is read, C++ synchronization rules apply regardless of whether metadata stays valid. [13]

An immutable owned snapshot is the simplest durable verification contract. A mutable buffer can support verified access only with explicit mutation rules, versioning, and synchronization.

Do not cache “verified” as a permanent property of an allocation that remains arbitrarily writable.

Checkpoint

Exercise 20. Design an iterative verifier work item and a memoization key. Explain how your design distinguishes a completed shared child from a cycle, and how it limits both visited nodes and scanned text bytes.

Book contents · Previous: Part II FlatBuffers · Next: Part IV Quality and Performance