// 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