1047 lines
23 KiB
Markdown
1047 lines
23 KiB
Markdown
# 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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
https://example.com/tree#v=1&c=<checked>&x=<expanded>
|
||
```
|
||
|
||
Example:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
# 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:
|
||
|
||
```json
|
||
{
|
||
"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:
|
||
|
||
```text
|
||
v=<serialization-version>
|
||
c=<checked-bitset>
|
||
x=<expanded-bitset>
|
||
```
|
||
|
||
Example:
|
||
|
||
```text
|
||
#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:
|
||
|
||
```text
|
||
m=<manifest-fingerprint>
|
||
```
|
||
|
||
Example:
|
||
|
||
```text
|
||
#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`:
|
||
|
||
```text
|
||
checked bit N = node N checked state
|
||
expanded bit N = node N expanded state
|
||
```
|
||
|
||
Within each byte, use least-significant-bit-first ordering:
|
||
|
||
```text
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```js
|
||
Map<string, number>
|
||
```
|
||
|
||
Example:
|
||
|
||
```js
|
||
{
|
||
"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:
|
||
|
||
```js
|
||
byteLength = Math.ceil(manifestSlotCount / 8);
|
||
```
|
||
|
||
Create:
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
const params = new URLSearchParams(location.hash.slice(1));
|
||
```
|
||
|
||
Read:
|
||
|
||
```js
|
||
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.
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```json
|
||
{
|
||
"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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
2 bits per manifest slot
|
||
```
|
||
|
||
For 1,000 slots:
|
||
|
||
```text
|
||
checked bitset = 125 bytes
|
||
expanded bitset = 125 bytes
|
||
total raw state = 250 bytes
|
||
```
|
||
|
||
Base64URL adds approximately one-third overhead:
|
||
|
||
```text
|
||
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:
|
||
|
||
```js
|
||
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:
|
||
|
||
```js
|
||
{
|
||
schema: 1,
|
||
slots: [
|
||
{ path: "panos", deleted: false },
|
||
{ path: "panos>12.1", deleted: false },
|
||
{ path: null, deleted: true }
|
||
],
|
||
pathToSlot: new Map()
|
||
}
|
||
```
|
||
|
||
Suggested restore result:
|
||
|
||
```js
|
||
{
|
||
applied: true,
|
||
version: 1,
|
||
warnings: []
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 18. Reference Encoding Example
|
||
|
||
Given this manifest:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
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:
|
||
|
||
```text
|
||
slot: 5 4 3 2 1 0
|
||
value: 1 0 1 1 0 1
|
||
```
|
||
|
||
Using least-significant-bit-first layout, the first byte is:
|
||
|
||
```text
|
||
00101101 binary
|
||
45 decimal
|
||
0x2d
|
||
```
|
||
|
||
The expanded bits are:
|
||
|
||
```text
|
||
slot: 5 4 3 2 1 0
|
||
value: 0 0 0 0 1 1
|
||
```
|
||
|
||
The first byte is:
|
||
|
||
```text
|
||
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.
|