canonical_encoding.hpp File Reference

The canonical exact text encoding of expression trees (ADR-0042). More...

#include <map>
#include <memory>
#include <ostream>
#include <string>
#include "bertini2/function_tree/node.hpp"

Include dependency graph for canonical_encoding.hpp:

Go to the source code of this file.

Classes
struct	bertini::node::EncodingContext
	Traversal state for one canonical-encoding pass: the back-reference table. More...

Namespaces
namespace	bertini
namespace	bertini::node

Functions
void	bertini::node::EncodeCanonical (std::shared_ptr< Node > const &root, std::ostream &out, EncodingContext &ctx)
	Append the canonical encoding of the DAG rooted at root to out.
std::string	bertini::node::CanonicalEncoding (std::shared_ptr< Node > const &root)
	The canonical encoding of a single tree as a string (fresh context).

Detailed Description

The canonical exact text encoding of expression trees (ADR-0042).

This is the identity substrate for persistent content digests: a deterministic, bit-exact, S-expression-like encoding of a node DAG, stable across runs, compilers, and library versions. It deliberately does NOT reuse:

• Node::Hash() / typeid – per-process only;
• the classic printer (ADR-0012) – a cosmetic, test-pinned surface whose tweaks must not rotate persistent digests;
• Boost.Serialization archives – their bytes embed boost-version-dependent framing.

Format sketch (kind tags are fixed strings, never typeid):

• leaves: (var 1:x), (diff 1:x), (int -7), (rat 1/3 0), (cplx 30 <re> <im>) (a Complex literal carries its stored precision – value-equal literals at different precisions are distinct identities), (pi), (e);
• operators: (sum +<child> -<child> ...) / (mul *<child> /<child> ...) in the order the session canonicalization produced, (neg <c>), (pow <base> <exp>), (ipow <n> <c>), (sqrt <c>), (exp <c>), (log <c>), (sin <c>) etc., (named 1:f <c>);
• names are netstrings (<byte-length>:<utf8-bytes>), so any name – emoji included – encodes unambiguously;
• back-references: every node gets an index in traversal order at its first encounter; a revisit emits #<index>. On interned (hash-consed) DAGs equal subtrees ARE the same object, so the encoding is canonical for equal content and stays linear-size under heavy sharing.

Any change to this format is a digest-breaking change: bump the system-encoding version header (b2sysenc/<n>, see system content identity) and the golden-digest fixture in the same commit.