# TagTree -- Architecture

## Purpose

TagTree is a shared Rust library crate that provides a hierarchical dot-notation tag standard. Tags are lowercase strings with dot-separated segments representing a hierarchy (e.g., `genre.electronic.house`, `work.meeting.standup`). The crate handles validation, parsing, tree operations, SQL helpers, prefix renaming, and keystroke-speed autocomplete -- with zero runtime dependencies.

## Tag Format

- Segments: lowercase alphanumeric and hyphens (`[a-z0-9-]`)
- Separator: `.` (dot)
- No empty segments, no leading/trailing dots, no consecutive dots

## Per-App TagConfig

Each consumer defines a `TagConfig` constant controlling depth, length, and semantic prefix rules.

| App | max_depth | max_length | semantic_depth | Notes |
|-----|-----------|------------|----------------|-------|
| AF  | 5         | 100        | 1              | Deep hierarchy, namespace-driven (`genre.electronic.house`) |
| GO  | 3         | 60         | 0              | Shallow free-form tags |
| BB  | 3         | 80         | 0              | Shallow free-form tags |
| MT  | 3         | 64         | 0              | Community-scoped thread tags |
| MNW | 5         | 100        | 0              | Content/project tags |

- `max_depth` -- maximum number of segments allowed
- `max_length` -- maximum character length of the entire tag string
- `semantic_depth` -- number of leading segments that carry dispatch meaning (0 = all free-form; 1 = first segment is a namespace like `genre`, `mood`)

## Core Types

| Type | Role |
|------|------|
| `TagConfig` | Per-app validation rules (depth, length, semantic prefix) |
| `TagError` | Error type returned on validation failure |
| `TagIndex` | In-memory sorted index for autocomplete suggestions |
| `SEPARATOR` | The `.` constant |

## API Surface

### Validation

- `validate_with(tag, config)` -- validate against a `TagConfig`
- `validate(tag)` -- validate with defaults (depth 5, length 100, no semantic prefix)

### Hierarchy Parsing

- `parent(tag)` -- parent path (`"a.b.c"` -> `Some("a.b")`)
- `leaf(tag)` -- last segment (`"a.b.c"` -> `"c"`)
- `depth(tag)` -- segment count (`"a.b.c"` -> `3`)
- `segment(tag, i)` -- extract segment by 0-based index
- `prefix_at_depth(tag, n)` -- first `n` segments as a path
- `ancestors(tag)` -- all ancestor paths, root to parent

### Tree Relationships

- `is_ancestor_of(a, b)` -- true if `a` is an ancestor of `b` at a segment boundary
- `common_ancestor(a, b)` -- longest shared prefix

### Set Operations (in-memory)

- `children_at_prefix(prefix, tags)` -- immediate children one level below prefix
- `subtree(prefix, tags)` -- all descendants of prefix (including prefix if present)
- `rename_prefix(old, new, tag)` -- swap a tag's prefix, returning new tag

### Semantic Splitting

- `semantic_prefix(tag, depth)` -- namespace portion
- `free_suffix(tag, depth)` -- value portion after semantic prefix

### SQL Helpers

- `escape_like(s)` -- escape `%`, `_`, `\` for safe LIKE embedding
- `like_descendant_pattern(prefix)` -- build `prefix.%` for hierarchy queries (works on both SQLite and PostgreSQL)

### TagIndex (Autocomplete)

Sorted `Vec<String>` with binary-search lookup. Two-tier suggestion strategy:

1. **Path prefix** (tier 1) -- binary search for tags whose full path starts with input. O(log n + k).
2. **Segment prefix** (tier 2) -- linear scan for tags where any non-first segment starts with input. Only runs if tier 1 didn't fill the limit and input has no dots. A segment index gates entry: if no known segment starts with input, scan is skipped in O(log m).

Key methods: `new()`, `empty()`, `insert()`, `remove()`, `rebuild()`, `contains()`, `suggest(input, limit)`, `suggest_with_status(input, limit)`.

## Integration Patterns

Apps integrate TagTree as a path dependency and define a `TagConfig` constant:

```rust
use tagtree::{TagConfig, validate_with};

const TAGS: TagConfig = TagConfig { max_depth: 5, max_length: 100, semantic_depth: 1 };

// Validate on create/update
validate_with(&user_input, &TAGS)?;

// SQL hierarchy queries
let pattern = tagtree::like_descendant_pattern("genre");
// WHERE tag LIKE ?1 ESCAPE '\' -> finds all genre.* tags
```

- **AF, GO, BB** -- SQLite repositories use `like_descendant_pattern` for hierarchy queries; `TagIndex` powers autocomplete in the UI
- **MT** -- community-scoped tags validated per-thread; migration 014 added `path` column using TagTree conventions
- **MNW** -- server-side validation on content/project tags; migration 038 added `path` column

## Performance Characteristics

Criterion benchmarks cover six groups at multiple scales (1K, 10K, 50K tags):

| Benchmark Group | What it measures |
|----------------|------------------|
| `validate` | Tag validation (simple, deep, max-depth, invalid, long) |
| `hierarchy` | parent, leaf, depth, ancestors, is_ancestor_of, common_ancestor |
| `sql` | escape_like, like_descendant_pattern |
| `tree_ops` | children_at_prefix, subtree, rename_prefix |
| `tag_index` | Build time, suggest (prefix/path/exact/no-match) at 1K/10K/50K |
| `deep_tree` | Validation and traversal at depth 5/10/20, deep-wide trees (~19K nodes) |

At typical corpus sizes (hundreds to low thousands), `suggest` completes in single-digit microseconds. Path-prefix lookups are O(log n); segment-prefix scans are gated by a segment index to avoid unnecessary work.

## Key Paths

| What | Path |
|------|------|
| Library source | `Shared/tagtree/src/lib.rs` |
| Cargo manifest | `Shared/tagtree/Cargo.toml` |
| Benchmarks | `Shared/tagtree/benches/tagtree_bench.rs` |
| Audit review | `docs/shared/tagtree/audit_review.md` |

## Metrics

- 1,441 LOC (single file, ~500 lines tests + ~940 library)
- 99 tests (68.7 tests/KLOC)
- Zero runtime dependencies (std-only)
- Zero unsafe, zero unwrap in production code
- Rust 2024 edition