checkbox-tree/docs/tree-state-serialization.md

Tree UI State Serialization Design

Implementation amendment: adaptive fields

The implemented version 1 format retains the manifest, URL parameters, stable slots, and default-state behavior described below, but adaptively encodes each c and x field. This amendment supersedes the document's later recommendation that fields always use dense bitsets.

Each decoded field still represents one Boolean per manifest slot. Before Base64URL encoding, its first byte selects the shortest representation:

• 0: dense, least-significant-bit-first bitset
• 1: delta-encoded variable-length indexes of enabled slots
• 2: manifest coverage followed by delta-encoded indexes of disabled slots

Mode 2's coverage value preserves forward compatibility: slots appended beyond the encoded coverage remain false rather than inheriting the enabled state. Empty all-false fields remain omitted. The encoder compares all three valid representations independently for checked and expanded state and emits the shortest. Sparse indexes are ascending, delta encoded, and stored as unsigned base-128 variable-length integers.

This adaptive layout was adopted before deployment, so it uses serialization version 1; no dense-only version 1 URLs need backward compatibility.

Selectable field encodings

Websites select their encoding with the CheckboxTree stateEncoding option. The value is intentionally not stored in the fragment, so it forms part of the website's URL-format contract. Version 1 supports:

• adaptive (default): adaptive c and x fields described above
• dense: trimmed dense c and x bitsets
• tiered: hierarchical checked fields and depth-grouped expanded fields

In tiered encoding, c1 stores actual root checked state. Each deeper cN stores whether a node differs from its direct parent's checked state; restoration uses XOR. Expansion does not inherit from a parent: each xN stores actual expanded state for branches at depth N, with collapsed as the baseline. Every tier independently uses the adaptive representation. Non-selectable parents provide a false checked baseline. An n field records the manifest slot coverage at serialization time; slots appended beyond that value restore false.

1. Purpose

Implement a compact, shareable, client-side serialization format for storing tree widget state in a URL.

Each tree node has two Boolean UI states:

• Checked or unchecked
• Expanded or collapsed

The serialized state must:

• Fit comfortably in a URL for ordinary tree sizes.
• Require no server-side token or state storage.
• Remain reasonably compatible when nodes are added, removed, renamed, moved, or reordered.
• Be deterministic and easy to restore.
• Allow future format changes.
• Avoid embedding explicit numeric IDs in the primary tree data.

The recommended design uses a separate append-only node manifest. A node’s stable identity is its permanent slot number in that manifest.

---

2. High-Level Design

Maintain a separate manifest file containing one node path per line.

Example:

panos
panos>12.1
panos>11.1
panos>12.1>12.1.2
panos>12.1>12.1.3
gp>6.0>6.1

The zero-based line number is the node’s permanent slot:

slot 0 = panos
slot 1 = panos>12.1
slot 2 = panos>11.1
slot 3 = panos>12.1>12.1.2
slot 4 = panos>12.1>12.1.3
slot 5 = gp>6.0>6.1

Each node consumes two state bits:

• One bit in the checked-state bitset
• One bit in the expanded-state bitset

The state is encoded using Base64URL and stored in the URL fragment or query string.

Recommended URL format:

https://example.com/tree#v=1&c=<checked>&x=<expanded>

Example:

https://example.com/tree#v=1&c=GkA&x=AQM

The URL fragment is preferred because it is available to client-side JavaScript but is not sent to the web server.

---

3. Terminology

Node path

A human-readable path identifying a node in the current tree data.

Example:

panos>12.1>12.1.2

Slot

The permanent numeric position assigned to a logical node in the manifest.

The slot is the actual stable identity used by serialized state.

Manifest

The append-only registry mapping stable slots to current node paths.

Tombstone

A manifest slot whose original node no longer exists.

Tombstoned slots remain reserved and must not be reused.

Checked bitset

A dense bitset in which bit N represents whether manifest slot N is checked.

Expanded bitset

A dense bitset in which bit N represents whether manifest slot N is expanded.

---

4. Manifest Requirements

The manifest is a persistent identity registry, not a generated list that may be freely reordered.

The following rules are mandatory.

4.1 Existing slots must never be reordered

Once a node has been assigned slot 12, it must remain slot 12.

The visual order of nodes in the tree may change independently.

4.2 New nodes must be appended

When a new logical node is introduced, add it to the end of the manifest.

Do not insert it between existing entries.

4.3 Removed nodes must become tombstones

When a node is removed, preserve its slot.

Example:

panos
panos>12.1
# removed: panos>11.1
panos>12.1>12.1.2

A structured manifest format may represent tombstones more explicitly, but the slot must remain occupied.

4.4 Tombstoned slots must never be reused

A slot formerly assigned to one logical node must never later identify another logical node.

Reusing slots would cause old shared URLs to apply state to the wrong node.

4.5 Renamed or moved nodes should retain their slots

When a logical node is renamed or moved, edit the path stored in its existing manifest slot.

Example:

Before:

slot 3 = panos>12.1>12.1.2

After:

slot 3 = archive>12.1>12.1.2

The node retains slot 3, so existing shared URLs continue to apply its prior state.

4.6 Paths must be unique among active entries

Two active manifest entries must not resolve to the same current node path.

The loader should detect and report duplicates.

---

5. Recommended Manifest Format

A plain-text line-based file is acceptable.

Example:

# tree-state-manifest
# schema=1

panos
panos>12.1
!deleted
panos>12.1>12.1.2
panos>12.1>12.1.3
gp>6.0>6.1

Recommended conventions:

• Blank lines and comment lines beginning with # do not consume slots.
• Every non-comment record consumes exactly one slot.
• !deleted represents a tombstone.
• Active records contain a node path.
• Paths are UTF-8 strings.
• Leading and trailing whitespace is either forbidden or trimmed consistently.
• The delimiter used inside paths must be escaped or prohibited in node names.

An alternative JSON manifest is also acceptable:

{
  "schema": 1,
  "nodes": [
    "panos",
    "panos>12.1",
    null,
    "panos>12.1>12.1.2",
    "panos>12.1>12.1.3",
    "gp>6.0>6.1"
  ]
}

The JSON form is easier to validate and avoids ambiguity around comments and tombstones. The line-based form is easier to review and edit manually.

The implementation may choose either format, but slot stability rules must remain identical.

---

6. URL Format

Use these fragment parameters:

v=<serialization-version>
c=<checked-bitset>
x=<expanded-bitset>

Example:

#v=1&c=GkA&x=AQM

6.1 v

The serialization schema version.

This version describes the binary and URL encoding format, not ordinary additions to the manifest.

Appending nodes, tombstoning nodes, or updating a path in place should not require incrementing v.

Increment v only when the meaning or layout of the serialized state changes incompatibly.

6.2 c

Base64URL-encoded checked-state bitset.

The parameter may be omitted when every node uses the default unchecked state.

6.3 x

Base64URL-encoded expanded-state bitset.

The parameter may be omitted when every node uses the default collapsed state.

6.4 Optional manifest fingerprint

The format may optionally include:

m=<manifest-fingerprint>

Example:

#v=1&m=a81f32c9&c=GkA&x=AQM

A fingerprint can detect whether the URL was generated from a different manifest.

A 32-bit or 48-bit truncated hash is sufficient for accidental mismatch detection.

An 8-bit fingerprint is not recommended because collisions would be too common.

The fingerprint should not automatically invalidate URLs when the manifest only grew by appending nodes. If used, it should support a compatibility policy described later in this document.

---

7. Bitset Layout

Use two independent bitsets.

For slot N:

checked bit N  = node N checked state
expanded bit N = node N expanded state

Within each byte, use least-significant-bit-first ordering:

bit index 0 -> byte 0, bit 0
bit index 1 -> byte 0, bit 1
...
bit index 7 -> byte 0, bit 7
bit index 8 -> byte 1, bit 0

The calculation is:

byteIndex = Math.floor(slot / 8);
bitMask = 1 << (slot % 8);

This ordering must be explicitly documented and covered by tests.

---

8. Default States

The default states are:

checked = false
expanded = false

When a URL does not contain enough bits for a node, the missing state defaults to false.

This is important for forward compatibility.

An old URL generated before new nodes were appended will contain a shorter bitset. Newly appended nodes will therefore be unchecked and collapsed.

---

9. Encoding Algorithm

9.1 Build the path-to-slot map

Load the manifest and create:

Map<string, number>

Example:

{
  "panos" => 0,
  "panos>12.1" => 1,
  "panos>12.1>12.1.2" => 3
}

Tombstoned slots are omitted from the map but still count toward slot positions.

9.2 Allocate bitsets

Let:

byteLength = Math.ceil(manifestSlotCount / 8);

Create:

const checked = new Uint8Array(byteLength);
const expanded = new Uint8Array(byteLength);

9.3 Set bits

For every active tree node:

1. Calculate its canonical path.
2. Look up the path in the manifest.
3. If no slot exists, report or collect it as an unregistered node.
4. Set the checked bit when the node is checked.
5. Set the expanded bit when the node is expanded.

Example helper:

function setBit(bytes, bitIndex, value) {
  const byteIndex = Math.floor(bitIndex / 8);
  const mask = 1 << (bitIndex % 8);

  if (value) {
    bytes[byteIndex] |= mask;
  } else {
    bytes[byteIndex] &= ~mask;
  }
}

9.4 Trim trailing zero bytes

Remove zero bytes from the end of each bitset before encoding.

Example:

function trimTrailingZeroBytes(bytes) {
  let end = bytes.length;

  while (end > 0 && bytes[end - 1] === 0) {
    end--;
  }

  return bytes.slice(0, end);
}

This makes URLs much smaller when active state is concentrated in low-numbered slots.

An entirely zero bitset becomes an empty byte array, and its URL parameter may be omitted.

9.5 Base64URL encode

Encode bytes with URL-safe Base64:

• Replace + with -
• Replace / with _
• Remove trailing =

Example implementation:

function bytesToBase64Url(bytes) {
  let binary = "";

  for (let i = 0; i < bytes.length; i++) {
    binary += String.fromCharCode(bytes[i]);
  }

  return btoa(binary)
    .replace(/\+/g, "-")
    .replace(/\//g, "_")
    .replace(/=+$/g, "");
}

For very large arrays, use chunking to avoid argument or string limits.

---

10. Decoding Algorithm

10.1 Parse URL state

Read the URL fragment:

const params = new URLSearchParams(location.hash.slice(1));

Read:

const version = params.get("v");
const checkedEncoded = params.get("c");
const expandedEncoded = params.get("x");

10.2 Validate version

If v is absent, malformed, or unsupported:

• Do not apply serialized state.
• Restore the tree using normal defaults.
• Do not throw an uncaught exception.

10.3 Decode Base64URL fields

Convert Base64URL back to bytes.

function base64UrlToBytes(value) {
  if (!value) {
    return new Uint8Array();
  }

  const base64 = value
    .replace(/-/g, "+")
    .replace(/_/g, "/");

  const padded = base64 + "=".repeat((4 - base64.length % 4) % 4);
  const binary = atob(padded);

  return Uint8Array.from(binary, character => character.charCodeAt(0));
}

Malformed data should be caught and handled by falling back to defaults.

10.4 Read bits

Example helper:

function getBit(bytes, bitIndex) {
  const byteIndex = Math.floor(bitIndex / 8);

  if (byteIndex >= bytes.length) {
    return false;
  }

  const mask = 1 << (bitIndex % 8);
  return (bytes[byteIndex] & mask) !== 0;
}

For each active tree node:

1. Find its manifest slot.
2. Read its checked bit.
3. Read its expanded bit.
4. Apply those states.

Bits belonging to tombstoned or missing nodes are ignored.

Bits beyond the current manifest length are ignored.

---

11. Compatibility with Tree Changes

11.1 New node appended

Behavior:

• Existing node slots remain unchanged.
• Old URLs do not contain bits for the new slot.
• The new node defaults to unchecked and collapsed.

This is fully compatible.

11.2 Existing node removed

Behavior:

• Its manifest slot becomes a tombstone.
• State bits for that slot are ignored.
• All other slots remain aligned.

This is fully compatible.

11.3 Node renamed

Behavior:

• Update the path in its existing manifest slot.
• The node retains its prior serialized state.

This is compatible as long as the existing slot is preserved.

11.4 Node moved to another parent

Behavior:

• Update its path in its existing manifest slot.
• The node retains its prior serialized state.

This is compatible as long as the move represents the same logical node.

11.5 Tree display order changed

Behavior:

• No manifest changes are required.
• State remains attached to stable slots rather than presentation order.

This is fully compatible.

11.6 Manifest accidentally reordered

Behavior:

• Old state may be applied to the wrong nodes.

This is a breaking and dangerous change.

The implementation should include validation or tooling to prevent accidental reordering.

11.7 Manifest rebuilt from scratch

Behavior:

• Existing URLs are no longer trustworthy unless an explicit migration map exists.

This requires either:

• A new serialization version that resets old state, or
• A slot migration table.

---

12. Versioning Policy

Use separate concepts for serialization format changes and manifest evolution.

Serialization version

Stored in:

v=1

Increment when:

• Bit ordering changes.
• Fields change meaning.
• Encoding changes.
• Defaults change.
• Multiple states are packed differently.
• The URL schema changes incompatibly.

Do not increment when:

• Nodes are appended.
• Nodes are tombstoned.
• Existing paths are updated in place.
• Display order changes.

Manifest revision

The application may maintain a human-readable manifest revision internally, but it need not appear in every URL.

Example:

{
  "schema": 1,
  "revision": 23,
  "nodes": []
}

A manifest revision is useful for development and diagnostics but should not automatically cause old shared URLs to be rejected.

Manifest fingerprint

An optional fingerprint may be added to detect unexpected manifest differences.

Recommended behavior:

• Matching fingerprint: restore normally.
• Mismatched fingerprint with a supported serialization version: restore known overlapping slots and ignore missing data.
• Known breaking manifest generation: reset or migrate.
• Unknown or malformed state: use defaults.

A fingerprint should be diagnostic rather than the primary identity mechanism.

---

13. Manifest Maintenance Workflow

Provide a maintenance tool or build step that compares current tree paths with the manifest.

The tool should:

1. Load the existing manifest.
2. Enumerate all current tree node paths.
3. Match current paths to existing active manifest entries.
4. Report duplicate paths.
5. Report nodes present in the tree but missing from the manifest.
6. Append new nodes when explicitly requested.
7. Report manifest entries that no longer exist in the tree.
8. Tombstone removed entries when explicitly requested.
9. Never reorder existing records.
10. Never reuse tombstoned slots.

Renames and moves cannot always be inferred safely. The tool should allow a deliberate operation such as:

move slot 37 from:
panos>12.1>old-name

to:
panos>12.1>new-name

This preserves identity.

---

14. Error Handling

The state loader must fail safely.

The following conditions must not break the page:

• Missing fragment
• Missing parameters
• Unknown serialization version
• Invalid Base64URL
• Truncated or malformed data
• Bitsets shorter than the manifest
• Bitsets longer than the manifest
• Missing tree paths
• Tombstoned slots
• Duplicate or invalid manifest entries

Recommended fallback:

checked = false
expanded = false

Invalid serialized state should be ignored as a whole unless partial restoration is intentionally supported and tested.

Errors may be logged to the developer console but should not normally be shown to end users.

---

15. Security Considerations

Serialized URL state is untrusted input.

The decoder must:

• Impose a maximum accepted encoded length.
• Reject malformed Base64URL.
• Avoid allocating memory based solely on untrusted declared sizes.
• Ignore state beyond the current manifest length.
• Never interpret decoded bytes as executable content.
• Avoid inserting URL values into HTML without escaping.

A reasonable maximum URL-state size should be selected based on expected tree size.

Example:

maximum decoded state per bitset =
ceil(manifestSlotCount / 8)

Decoded data longer than that may be truncated or rejected.

---

16. Size Characteristics

The dense representation uses:

2 bits per manifest slot

For 1,000 slots:

checked bitset  = 125 bytes
expanded bitset = 125 bytes
total raw state = 250 bytes

Base64URL adds approximately one-third overhead:

approximately 334 characters

The actual URL may be shorter because trailing zero bytes are removed independently from each bitset.

Tombstones cost only two bits each, so preserving deleted slots is inexpensive.

---

17. Suggested JavaScript API

The implementation should expose functions similar to:

loadManifest(source): Manifest

validateManifest(manifest, tree): ValidationResult

encodeTreeState(tree, manifest): {
  version: number,
  checked: string | null,
  expanded: string | null
}

decodeTreeState(fragment, manifest): DecodedTreeState

applyTreeState(tree, manifest, decodedState): void

serializeStateToFragment(tree, manifest): string

restoreStateFromLocation(tree, manifest, location): RestoreResult

Suggested manifest structure:

{
  schema: 1,
  slots: [
    { path: "panos", deleted: false },
    { path: "panos>12.1", deleted: false },
    { path: null, deleted: true }
  ],
  pathToSlot: new Map()
}

Suggested restore result:

{
  applied: true,
  version: 1,
  warnings: []
}

---

18. Reference Encoding Example

Given this manifest:

slot 0 = panos
slot 1 = panos>12.1
slot 2 = panos>11.1
slot 3 = panos>12.1>12.1.2
slot 4 = panos>12.1>12.1.3
slot 5 = gp>6.0>6.1

Suppose the states are:

slot 0: checked=true,  expanded=true
slot 1: checked=false, expanded=true
slot 2: checked=true,  expanded=false
slot 3: checked=true,  expanded=false
slot 4: checked=false, expanded=false
slot 5: checked=true,  expanded=false

The checked bits are:

slot:  5 4 3 2 1 0
value: 1 0 1 1 0 1

Using least-significant-bit-first layout, the first byte is:

00101101 binary
45 decimal
0x2d

The expanded bits are:

slot:  5 4 3 2 1 0
value: 0 0 0 0 1 1

The first byte is:

00000011 binary
3 decimal
0x03

Those byte arrays are Base64URL-encoded and placed into c and x.

The exact Base64URL output should be captured in unit tests rather than calculated manually throughout the application.

---

19. Testing Requirements

Bit operations

Test:

• Setting and reading bit 0
• Setting and reading bit 7
• Setting and reading bit 8
• Multiple bits in one byte
• Missing bytes returning false
• Clearing previously set bits

Base64URL encoding

Test:

• Empty byte array
• One byte
• Multiple bytes
• Values that normally produce +, /, or =
• Round-trip encode and decode
• Invalid input rejection

Manifest handling

Test:

• Active entries
• Tombstones
• Duplicate active paths
• Comments and blank lines, if using text format
• Appended nodes
• Renamed nodes retaining slots
• Removed nodes retaining tombstones

State restoration

Test:

• Empty URL
• Fully populated state
• Checked-only state
• Expanded-only state
• Old shorter URL against a longer manifest
• URL containing bits for tombstoned slots
• URL longer than the current manifest
• Unsupported version
• Malformed fields

Compatibility

Create an initial manifest and URL, then verify state after:

• Appending a node
• Tombstoning a node
• Renaming a node in place
• Moving a node in place
• Reordering the visual tree
• Adding unrelated nodes

---

20. Acceptance Criteria

The implementation is complete when:

1. Tree state can be serialized into a URL fragment.
2. Opening the URL restores checked and expanded states.
3. No server-side state or token is required.
4. Each node uses exactly one checked bit and one expanded bit.
5. New manifest entries are appended without changing existing slots.
6. Deleted entries become permanent tombstones.
7. Renamed and moved nodes can retain their existing slots.
8. Old URLs continue working after compatible manifest changes.
9. Unsupported or malformed state falls back safely to defaults.
10. The implementation has unit tests for encoding, decoding, manifest behavior, and compatibility.
11. The manifest validation process prevents accidental slot reordering or reuse.
12. URL output uses Base64URL without padding.
13. Trailing zero bytes are omitted.
14. Empty default-state fields are omitted from the URL.
15. The serialization version is included.

---

21. Future Enhancements

The initial implementation should use two dense bitsets because it is simple, deterministic, and compact.

Possible later enhancements include:

• Sparse encoding for expanded nodes when expansion is extremely sparse.
• Checked-state inheritance encoding for trees with strong parent-child checkbox semantics.
• Compression for exceptionally large manifests.
• Migration maps between deliberately rebuilt manifests.
• A generated manifest management CLI.
• Human-readable debug output for serialized state.
• Optional CRC or checksum for detecting corrupted URL state.
• Additional per-node Boolean state fields.

These enhancements should not be included in the first implementation unless real-world URL sizes demonstrate a need.

---

22. Final Recommendation

Use a separate append-only manifest whose stable line or array index acts as the node ID.

Store checked and expanded state as two independently trimmed, Base64URL-encoded bitsets in the URL fragment.

The manifest must preserve slot identity permanently:

• Append new nodes.
• Tombstone deleted nodes.
• Never reorder slots.
• Never reuse slots.
• Retain slots across logical renames and moves.

Use a serialization version for encoding-format changes. Treat normal manifest growth as backward-compatible so old shared URLs continue to work.