Appendix D Checked FlexBuffers Laboratory
Book contents · Previous: Appendix C Reading the Official Implementation · Next: Appendix E Mutable Semantic Laboratory
Appendix D of FlatBuffers & FlexBuffers: From Bytes to Mutable Memory. Checked FlexBuffers Laboratory from the complete supplied first edition.
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.
Appendix D: Complete checked FlexBuffers laboratory
File: include/flex_wire.hpp. This is original educational C++20 code, not a copy of the official header. It supplies the byte primitives, writer, borrowed reader, strict-profile verifier, copy operation, and constrained mutation helpers discussed in the book.
Source file: include/flex_wire.hpp.
// Original educational implementation for the accompanying book.
// SPDX-License-Identifier: MIT
// C++20. No FlatBuffers runtime dependency. Not production-certified.
#pragma once
#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <optional>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace flexlab {
using Bytes = std::vector<std::uint8_t>;
using ByteSpan = std::span<const std::uint8_t>;
struct Error : std::runtime_error { using std::runtime_error::runtime_error; };
inline void require(bool ok, const char* what) { if (!ok) throw Error(what); }
static_assert(sizeof(double) == 8 && sizeof(float) == 4);
static_assert(std::numeric_limits<double>::is_iec559);
static_assert(std::numeric_limits<float>::is_iec559);
enum class Type : std::uint8_t {
Null=0, Int=1, UInt=2, Float=3, Key=4, String=5,
IndirectInt=6, IndirectUInt=7, IndirectFloat=8, Map=9, Vector=10,
VectorInt=11, VectorUInt=12, VectorFloat=13, VectorKey=14,
VectorStringDeprecated=15,
Int2=16, UInt2=17, Float2=18, Int3=19, UInt3=20, Float3=21,
Int4=22, UInt4=23, Float4=24, Blob=25, Bool=26, VectorBool=36
};
inline unsigned id(Type t) { return static_cast<unsigned>(t); }
inline bool inline_type(Type t) { return id(t) <= 3 || t == Type::Bool; }
inline bool typed(Type t) { return (id(t)>=11 && id(t)<=15) || t==Type::VectorBool; }
inline bool fixed(Type t) { return id(t)>=16 && id(t)<=24; }
inline bool valid_type(Type t) { return id(t)<=26 || t==Type::VectorBool; }
inline bool width_ok(unsigned w) { return w==1 || w==2 || w==4 || w==8; }
inline unsigned width_code(unsigned w) {
require(width_ok(w), "invalid byte width");
return w==1 ? 0 : w==2 ? 1 : w==4 ? 2 : 3;
}
inline std::uint8_t packed(Type t, unsigned w) {
return static_cast<std::uint8_t>((id(t)<<2) | width_code(w));
}
inline unsigned uint_width(std::uint64_t x) {
return x<=0xff ? 1 : x<=0xffff ? 2 : x<=0xffffffffULL ? 4 : 8;
}
inline unsigned int_width(std::int64_t x) {
if (x>=-128 && x<=127) return 1;
if (x>=-32768 && x<=32767) return 2;
if (x>=INT32_MIN && x<=INT32_MAX) return 4;
return 8;
}
inline bool fits_unsigned(std::uint64_t x, unsigned w) {
return w==8 || x < (std::uint64_t{1} << (8*w));
}
inline std::size_t add(std::size_t a, std::size_t b) {
require(b<=SIZE_MAX-a, "size addition overflow"); return a+b;
}
inline std::size_t mul(std::size_t a, std::size_t b) {
require(a==0 || b<=SIZE_MAX/a, "size multiplication overflow"); return a*b;
}
inline std::size_t align_up(std::size_t n, unsigned w) {
require(width_ok(w), "invalid alignment");
return add(n, (w-(n & (w-1))) & (w-1));
}
inline void range(ByteSpan b, std::size_t p, std::size_t n) {
require(p<=b.size() && n<=b.size()-p, "byte range out of bounds");
}
// This slow, explicit baseline never creates an unaligned typed pointer.
inline std::uint64_t load_u(ByteSpan b, std::size_t p, unsigned w) {
require(width_ok(w), "invalid load width"); range(b,p,w);
std::uint64_t u=0;
for (unsigned j=0; j<w; ++j) u |= std::uint64_t{b[p+j]} << (8*j);
return u;
}
inline std::int64_t load_i(ByteSpan b, std::size_t p, unsigned w) {
auto u=load_u(b,p,w);
if (w==8) return std::bit_cast<std::int64_t>(u);
const unsigned bits=8*w;
if (u & (std::uint64_t{1} << (bits-1)))
return static_cast<std::int64_t>(u) - static_cast<std::int64_t>(std::uint64_t{1}<<bits);
return static_cast<std::int64_t>(u);
}
inline double load_f(ByteSpan b, std::size_t p, unsigned w) {
require(w==4 || w==8, "float must be binary32 or binary64");
if (w==4) return std::bit_cast<float>(static_cast<std::uint32_t>(load_u(b,p,4)));
return std::bit_cast<double>(load_u(b,p,8));
}
inline void store_u(Bytes& b, std::uint64_t u, unsigned w) {
require(width_ok(w), "invalid store width");
for (unsigned j=0; j<w; ++j) b.push_back(static_cast<std::uint8_t>(u>>(8*j)));
}
inline bool utf8(std::string_view s) {
for (std::size_t i=0; i<s.size();) {
const auto a=static_cast<unsigned char>(s[i++]);
if (a<0x80) continue;
unsigned more=0; std::uint32_t cp=0, minimum=0;
if (a>=0xc2 && a<=0xdf) { more=1; cp=a&31; minimum=0x80; }
else if (a>=0xe0 && a<=0xef) { more=2; cp=a&15; minimum=0x800; }
else if (a>=0xf0 && a<=0xf4) { more=3; cp=a&7; minimum=0x10000; }
else return false;
if (more>s.size()-i) return false;
while (more--) {
auto q=static_cast<unsigned char>(s[i++]);
if ((q&0xc0)!=0x80) return false;
cp=(cp<<6)|(q&63);
}
if (cp<minimum || cp>0x10ffff || (cp>=0xd800 && cp<=0xdfff)) return false;
}
return true;
}
inline int byte_compare(std::string_view a, std::string_view b) {
const auto n=std::min(a.size(),b.size());
const auto c=n ? std::memcmp(a.data(),b.data(),n) : 0;
if (c) return c;
return a.size()<b.size() ? -1 : a.size()>b.size() ? 1 : 0;
}
struct Encoded {
Type type=Type::Null;
unsigned width=1; // scalar minimum or child storage width
std::uint64_t payload=0; // scalar bits, or absolute child position
const void* owner=nullptr; // referenced children belong to one writer
};
class Writer {
Bytes b_;
bool sealed_=false;
void writable() const { require(!sealed_, "writer already finished"); }
void owned(const Encoded& e) const {
require(inline_type(e.type) || e.owner==this, "cross-writer child reference");
require(valid_type(e.type) && width_ok(e.width), "invalid encoded value");
}
void pad(unsigned w) { b_.resize(align_up(b_.size(),w),0); }
void write_value(const Encoded& e, unsigned w) {
owned(e);
if (!inline_type(e.type)) {
require(e.payload<=b_.size(), "forward FlexBuffers offset");
const auto d=static_cast<std::uint64_t>(b_.size())-e.payload;
require(fits_unsigned(d,w), "offset does not fit"); store_u(b_,d,w);
} else if (e.type==Type::Float) {
const auto d=std::bit_cast<double>(e.payload);
require(w==4 || w==8, "invalid float slot width");
store_u(b_, w==4 ? std::bit_cast<std::uint32_t>(static_cast<float>(d)) : e.payload,w);
} else store_u(b_,e.payload,w);
}
unsigned vector_width(std::span<const Encoded> v, unsigned prefix,
bool has_length, const Encoded* keys) const {
for (unsigned w : {1U,2U,4U,8U}) {
if (has_length && !fits_unsigned(v.size(),w)) continue;
bool ok=true;
const auto base=align_up(b_.size(),w);
if (keys) {
owned(*keys);
ok=keys->payload<=base && fits_unsigned(base-keys->payload,w)
&& fits_unsigned(keys->width,w);
}
for (std::size_t i=0; ok && i<v.size(); ++i) {
const auto& e=v[i]; owned(e);
if (inline_type(e.type)) ok=e.width<=w;
else {
const auto p=add(base,mul(add(prefix,i),w));
ok=e.payload<=p && fits_unsigned(p-e.payload,w);
}
}
if (ok) return w;
}
throw Error("no representable vector width");
}
Encoded sequence(std::span<const Encoded> v, Type output,
bool has_types, bool has_length, const Encoded* keys=nullptr) {
writable();
const unsigned prefix=keys ? 3 : has_length ? 1 : 0;
const auto w=vector_width(v,prefix,has_length,keys);
pad(w);
if (keys) { write_value(*keys,w); store_u(b_,keys->width,w); }
if (has_length) store_u(b_,v.size(),w);
const auto p=b_.size();
for (const auto& e:v) write_value(e,w);
if (has_types) for (const auto& e:v)
b_.push_back(packed(e.type,inline_type(e.type) ? w : e.width));
return {output,w,p,this};
}
public:
explicit Writer(std::size_t reserve=256) { b_.reserve(reserve); }
Writer(const Writer&)=delete;
Writer& operator=(const Writer&)=delete;
Writer(Writer&&)=delete;
Writer& operator=(Writer&&)=delete;
static Encoded null() { return {}; }
static Encoded boolean(bool b) { return {Type::Bool,1,b ? 1ULL : 0ULL,nullptr}; }
static Encoded integer(std::int64_t x) {
return {Type::Int,int_width(x),std::bit_cast<std::uint64_t>(x),nullptr};
}
static Encoded uint(std::uint64_t x) { return {Type::UInt,uint_width(x),x,nullptr}; }
static Encoded real(double x, bool force64=false) {
const auto f=static_cast<float>(x);
const bool exact=!std::isnan(x) && static_cast<double>(f)==x;
return {Type::Float,(!force64 && exact) ? 4U : 8U,std::bit_cast<std::uint64_t>(x),nullptr};
}
Encoded indirect(Encoded scalar) {
writable(); owned(scalar);
require(scalar.type==Type::Int || scalar.type==Type::UInt || scalar.type==Type::Float,
"only numeric scalars can be indirect");
pad(scalar.width); const auto p=b_.size(); write_value(scalar,scalar.width);
return {static_cast<Type>(id(scalar.type)+5),scalar.width,p,this};
}
Encoded key(std::string_view s) {
writable(); require(s.find('\0')==s.npos, "key contains NUL");
require(utf8(s), "key is not UTF-8"); const auto p=b_.size();
b_.insert(b_.end(),s.begin(),s.end()); b_.push_back(0);
return {Type::Key,1,p,this};
}
Encoded string(std::string_view s) {
writable(); require(utf8(s), "string is not UTF-8");
const auto w=uint_width(s.size()); pad(w); store_u(b_,s.size(),w);
const auto p=b_.size(); b_.insert(b_.end(),s.begin(),s.end()); b_.push_back(0);
return {Type::String,w,p,this};
}
Encoded blob(ByteSpan data) {
writable(); const auto w=uint_width(data.size()); pad(w); store_u(b_,data.size(),w);
const auto p=b_.size(); b_.insert(b_.end(),data.begin(),data.end());
return {Type::Blob,w,p,this};
}
Encoded vector(std::span<const Encoded> v) { return sequence(v,Type::Vector,true,true); }
Encoded typed_vector(std::span<const Encoded> v, Type element, unsigned fixed_n=0) {
require(element==Type::Int || element==Type::UInt || element==Type::Float ||
element==Type::Key || element==Type::Bool, "unsupported typed vector element");
for (const auto& e:v) require(e.type==element, "heterogeneous typed vector");
Type result;
if (fixed_n) {
require(fixed_n>=2 && fixed_n<=4 && v.size()==fixed_n, "bad fixed vector length");
require(id(element)>=1 && id(element)<=3, "bad fixed vector element type");
result=static_cast<Type>(16+3*(fixed_n-2)+id(element)-1);
} else result=element==Type::Bool ? Type::VectorBool : static_cast<Type>(id(element)+10);
return sequence(v,result,false,fixed_n==0);
}
Encoded map(std::vector<std::pair<std::string,Encoded>> fields) {
writable();
std::sort(fields.begin(),fields.end(),[](const auto& a,const auto& b) {
return byte_compare(a.first,b.first)<0;
});
std::vector<Encoded> keys, vals; keys.reserve(fields.size()); vals.reserve(fields.size());
for (std::size_t i=0; i<fields.size(); ++i) {
if (i) require(fields[i-1].first!=fields[i].first, "duplicate map key");
owned(fields[i].second); keys.push_back(key(fields[i].first)); vals.push_back(fields[i].second);
}
const auto kv=typed_vector(keys,Type::Key);
return sequence(vals,Type::Map,true,true,&kv);
}
const Bytes& finish(const Encoded& root) {
writable(); owned(root);
unsigned w=1;
for (w=1; w<=8; w*=2) {
const auto p=align_up(b_.size(),w);
if (inline_type(root.type) ? root.width<=w :
root.payload<=p && fits_unsigned(p-root.payload,w)) break;
}
require(w<=8,"root offset overflow"); pad(w); write_value(root,w);
b_.push_back(packed(root.type,inline_type(root.type) ? w : root.width));
b_.push_back(static_cast<std::uint8_t>(w)); sealed_=true; return b_;
}
const Bytes& buffer() const { require(sealed_,"unfinished buffer"); return b_; }
};
struct Ref {
ByteSpan bytes;
std::size_t slot=0;
unsigned parent_width=1;
unsigned child_width=1;
Type type=Type::Null;
static Ref root(ByteSpan b) {
require(b.size()>=3,"truncated root trailer");
const auto w=b.back(); require(width_ok(w),"invalid root width");
require(w<=b.size()-2,"truncated root slot");
const auto t=b[b.size()-2];
return {b,b.size()-2-w,w,1U<<(t&3),static_cast<Type>(t>>2)};
}
std::size_t target() const {
require(!inline_type(type),"inline value has no target");
const auto d=load_u(bytes,slot,parent_width);
require(d<=slot,"backward offset underflow"); return slot-static_cast<std::size_t>(d);
}
std::int64_t as_int() const {
require(type==Type::Int || type==Type::IndirectInt,"not a signed integer");
return type==Type::Int ? load_i(bytes,slot,parent_width) : load_i(bytes,target(),child_width);
}
std::uint64_t as_uint() const {
require(type==Type::UInt || type==Type::IndirectUInt,"not an unsigned integer");
return type==Type::UInt ? load_u(bytes,slot,parent_width) : load_u(bytes,target(),child_width);
}
double as_float() const {
require(type==Type::Float || type==Type::IndirectFloat,"not a floating-point value");
return type==Type::Float ? load_f(bytes,slot,parent_width) : load_f(bytes,target(),child_width);
}
bool as_bool() const {
require(type==Type::Bool,"not a boolean"); return load_u(bytes,slot,parent_width)!=0;
}
std::size_t length() const {
if (fixed(type)) return 2+(id(type)-16)/3;
require(type==Type::Vector || type==Type::Map || typed(type) ||
type==Type::String || type==Type::Blob,"type has no length prefix");
const auto p=target(); require(child_width<=p,"missing length prefix");
const auto n=load_u(bytes,p-child_width,child_width);
require(n<=SIZE_MAX,"length does not fit size_t"); return static_cast<std::size_t>(n);
}
std::string_view text() const {
require(type==Type::String || type==Type::Key,"not text");
const auto p=target();
if (type==Type::String) {
const auto n=length(); range(bytes,p,add(n,1));
require(bytes[p+n]==0,"missing string terminator");
return {reinterpret_cast<const char*>(bytes.data()+p),n};
}
std::size_t end=p;
while (end<bytes.size() && bytes[end]!=0) ++end;
require(end<bytes.size(),"unterminated key");
return {reinterpret_cast<const char*>(bytes.data()+p),end-p};
}
ByteSpan blob() const {
require(type==Type::Blob,"not a blob");
const auto p=target(), n=length(); range(bytes,p,n); return bytes.subspan(p,n);
}
Ref at(std::size_t index) const {
require(type==Type::Vector || type==Type::Map || typed(type) || fixed(type),"not a vector");
const auto n=length(); require(index<n,"vector index out of range");
const auto p=target(), extent=mul(n,child_width);
range(bytes,p,extent);
const auto loc=add(p,mul(index,child_width));
if (type==Type::Vector || type==Type::Map) {
const auto tags=add(p,extent); range(bytes,tags,n);
const auto t=bytes[tags+index];
return {bytes,loc,child_width,1U<<(t&3),static_cast<Type>(t>>2)};
}
Type element;
if (fixed(type)) element=static_cast<Type>(1+(id(type)-16)%3);
else if (type==Type::VectorBool) element=Type::Bool;
else if (type==Type::VectorStringDeprecated) element=Type::Key;
else element=static_cast<Type>(id(type)-10);
return {bytes,loc,child_width,1,element};
}
Ref keys() const {
require(type==Type::Map,"not a map"); const auto p=target();
const auto pref=mul(child_width,3); require(pref<=p,"missing map prefix");
const auto q=p-pref;
const auto kw=load_u(bytes,q+child_width,child_width);
require(width_ok(static_cast<unsigned>(kw)) && kw<=8,"invalid key-vector width");
return {bytes,q,child_width,static_cast<unsigned>(kw),Type::VectorKey};
}
std::optional<Ref> find(std::string_view key) const {
const auto k=keys(); require(k.length()==length(),"key/value length mismatch");
std::size_t lo=0, hi=length();
while (lo<hi) {
const auto m=lo+(hi-lo)/2; const auto cmp=byte_compare(k.at(m).text(),key);
if (cmp<0) lo=m+1; else hi=m;
}
if (lo<length() && byte_compare(k.at(lo).text(),key)==0) return at(lo);
return std::nullopt;
}
};
struct VerifyOptions {
std::size_t max_depth=64;
std::size_t max_visits=1'000'000;
bool check_utf8=true;
bool canonical_bool_and_null=true;
bool allow_deprecated=true;
};
// A bounded recursive teaching verifier. Deliberately no reuse memoization.
// Semantic checks are stronger than the upstream structural verifier.
inline void verify_ref(const Ref& r, const VerifyOptions& o,
std::size_t depth, std::size_t& visits) {
require(depth<=o.max_depth,"nesting limit exceeded");
require(visits<o.max_visits,"verification work limit exceeded"); ++visits;
require(width_ok(r.parent_width) && width_ok(r.child_width),"invalid width");
require(valid_type(r.type),"unknown or reserved type tag");
range(r.bytes,r.slot,r.parent_width);
if (inline_type(r.type)) {
if (r.type==Type::Float) require(r.parent_width==4 || r.parent_width==8,"invalid inline float width");
if (o.canonical_bool_and_null && r.type==Type::Bool)
require(load_u(r.bytes,r.slot,r.parent_width)<=1,"noncanonical boolean");
if (o.canonical_bool_and_null && r.type==Type::Null)
require(load_u(r.bytes,r.slot,r.parent_width)==0,"noncanonical null");
return;
}
const auto p=r.target();
require((p & (r.child_width-1))==0,"misaligned child position");
switch (r.type) {
case Type::IndirectInt: case Type::IndirectUInt:
range(r.bytes,p,r.child_width); return;
case Type::IndirectFloat:
require(r.child_width==4 || r.child_width==8,"invalid indirect float width");
range(r.bytes,p,r.child_width); return;
case Type::String: case Type::Key: {
const auto s=r.text(); require(!o.check_utf8 || utf8(s),"invalid UTF-8"); return;
}
case Type::Blob: (void)r.blob(); return;
default: break;
}
require(r.type==Type::Map || r.type==Type::Vector || typed(r.type) || fixed(r.type),"not a supported container");
require(o.allow_deprecated || r.type!=Type::VectorStringDeprecated,"deprecated vector disabled");
const auto n=r.length(); range(r.bytes,p,mul(n,r.child_width));
if (r.type==Type::Vector || r.type==Type::Map)
range(r.bytes,add(p,mul(n,r.child_width)),n);
// Charge every scalar too: inputs cannot hide unbounded work in a typed array.
require(n<=o.max_visits-visits,"verification work limit exceeded");
for (std::size_t i=0; i<n; ++i) verify_ref(r.at(i),o,depth+1,visits);
if (r.type==Type::Map) {
const auto k=r.keys(); require(k.length()==n,"map key/value count mismatch");
verify_ref(k,o,depth+1,visits);
for (std::size_t i=1; i<n; ++i)
require(byte_compare(k.at(i-1).text(),k.at(i).text())<0,"map keys unsorted or duplicate");
}
}
inline Ref verify(ByteSpan b, VerifyOptions options={}) {
auto r=Ref::root(b); std::size_t visits=0; verify_ref(r,options,0,visits); return r;
}
// Re-encode supported values. Sharing and representation widths are not retained.
inline Encoded copy_to(Writer& w, const Ref& r, std::size_t depth=0) {
require(depth<=64,"copy nesting limit exceeded");
switch (r.type) {
case Type::Null: return Writer::null();
case Type::Bool: return Writer::boolean(r.as_bool());
case Type::Int: return Writer::integer(r.as_int());
case Type::UInt: return Writer::uint(r.as_uint());
case Type::Float: return Writer::real(r.as_float());
case Type::IndirectInt: return w.indirect(Writer::integer(r.as_int()));
case Type::IndirectUInt: return w.indirect(Writer::uint(r.as_uint()));
case Type::IndirectFloat: return w.indirect(Writer::real(r.as_float()));
case Type::String: return w.string(r.text());
case Type::Key: return w.key(r.text());
case Type::Blob: return w.blob(r.blob());
case Type::Map: {
std::vector<std::pair<std::string,Encoded>> fields; const auto k=r.keys();
for (std::size_t i=0; i<r.length(); ++i)
fields.emplace_back(std::string(k.at(i).text()),copy_to(w,r.at(i),depth+1));
return w.map(std::move(fields));
}
default: {
require(r.type==Type::Vector || typed(r.type) || fixed(r.type),"unsupported copy type");
std::vector<Encoded> values; values.reserve(r.length());
for (std::size_t i=0; i<r.length(); ++i) values.push_back(copy_to(w,r.at(i),depth+1));
if (r.type==Type::Vector) return w.vector(values);
Type element=Type::Key;
if (fixed(r.type)) element=static_cast<Type>(1+(id(r.type)-16)%3);
else if (r.type==Type::VectorBool) element=Type::Bool;
else if (r.type!=Type::VectorStringDeprecated) element=static_cast<Type>(id(r.type)-10);
return w.typed_vector(values,element,fixed(r.type) ? static_cast<unsigned>(r.length()) : 0);
}
}
}
// Same-layout mutation only. Aliases observe the same changed bytes.
inline bool mutate_int(Bytes& owner, const Ref& r, std::int64_t value) {
require(r.bytes.data()==owner.data() && r.bytes.size()==owner.size(),"wrong mutable owner");
require(r.type==Type::Int || r.type==Type::IndirectInt,"not a signed integer");
const auto w=r.type==Type::Int ? r.parent_width : r.child_width;
const auto p=r.type==Type::Int ? r.slot : r.target();
if (int_width(value)>w) return false;
range(owner,p,w); const auto bits=std::bit_cast<std::uint64_t>(value);
for (unsigned j=0; j<w; ++j) owner[p+j]=static_cast<std::uint8_t>(bits>>(8*j));
return true;
}
inline bool mutate_same_length_string(Bytes& owner, const Ref& r, std::string_view value) {
require(r.bytes.data()==owner.data() && r.bytes.size()==owner.size(),"wrong mutable owner");
require(r.type==Type::String && utf8(value),"not a valid UTF-8 string mutation");
if (r.length()!=value.size()) return false;
const auto p=r.target(); range(owner,p,value.size());
if (!value.empty()) std::memmove(owner.data()+p,value.data(),value.size());
return true;
}
} // namespace flexlab
REFERENCE & COMPLETE SOURCE
Book contents · Previous: Appendix C Reading the Official Implementation · Next: Appendix E Mutable Semantic Laboratory