docs/IMPLEMENTATION.md

# Implementation plan

This is the build order. Each phase is independently shippable; later phases assume the artifacts of earlier ones.

## Phase 0 — repository skeleton

Create:

```
README.md
requirements.txt
.python-version                # 3.12
.gitignore                     # data/index, data/raw, node_modules, dist, __pycache__
pyproject.toml                 # pytest config, optional later
pipeline/download.py
pipeline/build_index.py
backend/app.py
backend/graph.py
backend/filters.py
backend/search.py
backend/models.py
backend/load.py
frontend/                      # Vite + React + TypeScript
tests/test_filters.py
tests/test_graph.py
tests/test_search.py
scripts/run.sh
docs/DESIGN.md                 # already written
docs/IMPLEMENTATION.md         # this file
```

Runtime stack:

- Python 3.12, FastAPI, uvicorn, numpy, pandas, pyarrow, orjson
- SQLite 3 (stdlib) with FTS5
- Node 22, Vite, React 18/19, TypeScript, d3-hierarchy
- Leaflet + a tiny QR library for the phone dialog

No Docker required. `scripts/run.sh` downloads (if needed), builds the index (if needed), builds the SPA (if needed), and serves everything on `:8000`.

## Phase 1 — download

`pipeline/download.py` fetches into `data/raw/`:

1. Hugging Face parquet files from `https://huggingface.co/datasets/lukeslp/etymology-atlas/resolve/main/{file}`:
   - etymologies.parquet
   - languages.parquet
   - cognate_sets.parquet
   - phonemes.parquet
   - linguistic_features.parquet
2. `https://raw.githubusercontent.com/glottolog/glottolog-cldf/master/cldf/languages.csv`
3. `https://raw.githubusercontent.com/cldf-datasets/wals/master/cldf/languages.csv`
4. `https://raw.githubusercontent.com/cldf-datasets/wals/master/cldf/codes.csv`

Idempotent: skip files whose size matches a recorded `.meta.json`. Retry with exponential backoff. Fail with a clear message if Hugging Face is unreachable.

## Phase 2 — language catalog

Inside `build_index.py`, build a `languages` table that actually has families and ISO codes (the published `languages.parquet` leaves `family_name`, `iso_639_3`, and `speakers_count` entirely null).

Algorithm:

1. Load Glottolog CLDF. Rows with `Level == "family"` give `Family_ID -> family name`. Rows with `Level in {language, dialect}` give glottocode, ISO, coords, macroarea, isolate flag.
2. Load atlas `languages.parquet` for vitality (`status`), atlas coordinates (fill if Glottolog coords missing), and `phoneme_count`.
3. Collect every distinct `lang` string from etymology `lang1` and `lang2`.
4. Resolve each atlas lang key to a glottocode:
   - If the key is a 3-letter ISO 639-3 code (Lexibank), map via Glottolog `ISO639P3code`.
   - Else lowercase-name match against Glottolog `Name`.
   - Else lowercase-name match against atlas `languages.name`.
   - Else try stripping a parenthetical dialect (`persian: tehran` -> `persian`) and retry.
   - Else leave unresolved; still store the atlas key as a first-class language so proto-languages work.
5. Family name: Glottolog family lookup. Fallback: if the key starts with `proto-`, use the remainder title-cased as a pseudo-family (so `proto-germanic` groups with Germanic when the family row exists, otherwise "Proto-Germanic").
6. Macroarea: Glottolog, then atlas parquet.
7. WALS join: `wals_languages.Glottocode` -> atlas glottocode. Store `wals_id`.
8. Phoneme join: PHOIBLE `glottocode`. Union inventories when multiple PHOIBLE sources exist for one language.
9. Assign dense integer codes for `lang`, `family`, `macroarea`, `status` used later as numpy columns.

Write `languages` SQLite table:

```
lang_key TEXT PK,
display TEXT,
glottocode TEXT,
iso_639_3 TEXT,
family_id TEXT,
family_name TEXT,
macroarea TEXT,
status TEXT,
latitude REAL,
longitude REAL,
wals_id TEXT,
phoneme_count INTEGER,
resolved INTEGER
```

Write auxiliary tables:

```
wals_values(glottocode, feature_id, feature_name, value INT, value_label TEXT)
phoneme_inv(glottocode, phoneme, segment_class, tone INT)
cognate_set(id, words_json, language_count)
cognate_member(set_id, term, lang, glottocode)
```

WALS `value_label` comes from `codes.csv` (`81A-2` -> `SOV` etc.), not the atlas `value_name` which is only the code id.

## Phase 3 — node internment and CSR graph

1. Read etymologies in one pandas load (58 MB parquet; ~1–2 GB peak is acceptable).
2. Drop rows with null/empty `term1` or `term2`.
3. Intern `(term, lang)` -> dense `node_id` starting at 0. Process both sides. Preserve original term spelling as `term`; store `term_norm` for FTS (NFKC, casefold, strip leading `*`, map `₂`/`₃` -> `2`/`3`).
4. Map `relationship_type` to uint8 via a fixed table (order stable, stored in `meta.json`).
5. Quantize confidence to uint8 as `round(conf * 100)`.
6. Source to uint8: 0 = etymology-db, 1 = lexibank:iecor.

Reverse CSR (the walk direction):

```
offsets: int32[n_nodes + 1]
targets: int32[n_edges]      # descendant node ids
rel:     uint8[n_edges]
conf:    uint8[n_edges]
src:     uint8[n_edges]
```

Edge `term2 -> term1` is appended in input order, then each adjacency list is sorted by `(rel, -conf, target)` so inherited high-confidence children appear first.

Also build a forward CSR (`term1 -> term2`) for the inspector. Same arrays, `fwd_` prefix.

Per-node numpy (saved in the same npz or a second one):

```
lang_code:     int32[n_nodes]
family_code:   int32[n_nodes]
macro_code:    int8[n_nodes]
status_code:   int8[n_nodes]
glotto_code:   int32[n_nodes]   # -1 if unresolved
child_count:   int32[n_nodes]   # reverse out-degree
```

SQLite `nodes`:

```
id INTEGER PK,
term TEXT,
term_norm TEXT,
lang TEXT,
child_count INTEGER
```

FTS5:

```
CREATE VIRTUAL TABLE nodes_fts USING fts5(
  term, term_norm, lang,
  content='nodes', content_rowid='id',
  tokenize = 'unicode61 remove_diacritics 2'
);
```

`meta.json`: relation names, language/family/macroarea vocabularies with counts, example roots, cluster/depth defaults, dataset citation.

Build is a single command, prints timings, refuses to overwrite unless `--force`.

## Phase 4 — filter engine

`backend/filters.py` is pure and unit-tested with a synthetic graph. No FastAPI imports.

Dataclasses (mirrors the JSON body):

```python
class EdgeFilter:
    relations: frozenset[str]   # empty = default set
    min_confidence: float
    max_depth: int
    max_visit: int

class NodePredicate:
    languages: frozenset[str]
    families: frozenset[str]
    macroareas: frozenset[str]
    statuses: frozenset[str]
    term_contains: str
    term_regex: str | None
    bbox: tuple[float, float, float, float] | None  # minlat, minlon, maxlat, maxlon
    require_coords: bool
    wals: tuple[WalsClause, ...]   # feature_id + allowed int values
    phonemes_have: frozenset[str]
    phonemes_lack: frozenset[str]
    require_tone: bool | None
    keep_unknown: bool

class PathFilter:
    node: NodePredicate
    quantifier: Literal["any", "all", "none", "exactly"]
    exactly_k: int
    relations_any: frozenset[str]
    relations_none: frozenset[str]
    apply_to_root: bool

class TreeQuery:
    term: str
    lang: str
    edges: EdgeFilter
    leaf: NodePredicate
    path: PathFilter
    expand: tuple[str, ...]     # cluster keys to unpack
    cluster_threshold: int
    max_payload: int
    color_by: str
```

`node_ok(node_id, pred, ctx) -> bool`:

- Empty predicate fields are no-ops (vacuously true).
- WALS/phoneme lookups go through `glotto_code[node_id]`; if `-1` and pred uses those fields, return `pred.keep_unknown`.
- Term regex compiled once per query.

`path_ok(node_ids, edge_rels, path_filter) -> bool`:

- Slice intermediates.
- Quantifier over `node_ok` on that slice.
- Then AND the relation-any / relation-none checks on `edge_rels`.

`walk(query) -> TreeResult`:

1. Resolve root id or return 404-equivalent empty result.
2. BFS using reverse CSR. Skip edges failing Layer A. Store `parent[child] = node`, `parent_edge[child] = edge_index`, `depth[child]`.
3. Identify candidate leaves: visited nodes with no kept child in the BFS tree, or depth == max_depth.
4. For each candidate, reconstruct path by parent pointers, test leaf + path filters.
5. Mark surviving nodes.
6. Cluster unmarked-as-expanded high fan-out sibling groups.
7. Hydrate payload rows from SQLite in one `WHERE id IN (...)` query.
8. Return stats: visited, kept_leaves, clustered, elapsed_ms, truncated flag.

Do not recurse in Python objects; use arrays and deques. This is the hot path.

## Phase 5 — FastAPI

`backend/load.py` on startup:

- mmap `graph.npz`
- open SQLite with `pragma journal_mode=wal; mmap_size=268435456; cache_size=-80000`
- load `meta.json`
- load WALS/phoneme dicts keyed by glotto_code (built once from SQLite into Python dicts; 2k inventories is tiny)
- expose a process-global `Atlas` object

`backend/app.py`:

- `/api/*` routes
- `/` and assets from `frontend/dist` if present
- gzip via Starlette GZipMiddleware
- CORS `*`
- orjson response class
- request timing header `X-Query-Ms`

Validation: pydantic models matching `TreeQuery`. Unknown relation names 422. Empty suggest query returns the curated examples.

## Phase 6 — frontend

Vite React TS. Single page.

### State

URL is the source of truth. `useQueryState` (hand-rolled) serializes:

```
q, lang, depth, conf,
rels (comma),
view (tree|radial|map|table|stats),
color,
leafLang, leafFam, leafArea, leafWals, leafPh,
pathLang, pathFam, pathArea, pathMatch, pathRelAny,
expand
```

Changing any of these (except camera) refetches `/api/tree`. Camera is session-only.

### Components

| File | Responsibility |
| --- | --- |
| `App.tsx` | Shell, URL state, data fetching, layout mode (desktop vs mobile) |
| `SearchBar.tsx` | Combobox suggest, language disambiguation, `/` shortcut |
| `FilterPanel.tsx` | Three tabs: Graph / Leaves / Path. Multi-selects, sliders, quantifier, keep-unknown |
| `FilterChips.tsx` | Compact removable chips; the mobile summary of the query |
| `TreeCanvas.tsx` | Canvas camera + pointer/touch + hover path |
| `layout.ts` | d3-hierarchy tidy / radial, cluster stub sizing |
| `render.ts` | Draw edges, nodes, labels, LOD, minimap, DPR |
| `MapView.tsx` | Leaflet markers from hydrated coords |
| `TableView.tsx` | Sort, filter-in-view, pagination, CSV button |
| `StatsView.tsx` | Small-multiple bars for the current payload |
| `Inspector.tsx` | Desktop drawer / mobile sheet |
| `Legend.tsx` | Color encoding |
| `Examples.tsx` | First-run cards |
| `PhoneQR.tsx` | LAN origin QR |
| `api.ts` | fetch wrappers |
| `types.ts` | shared TS types matching pydantic |
| `colors.ts` | relation + family palettes |
| `pwa.ts` | service worker registration |

### Canvas details

- Offscreen node array `{x,y,r,id,kind,color,label}`.
- `devicePixelRatio` cap at 2 for mobile GPUs.
- Hit test: `grid[(gx<<16)^gy]` lists of node indices.
- Path highlight: walk `parent` from hovered id, draw those edges last.
- Cluster stubs drawn as rounded rects with count.
- Empty state when the query yields only the root: explain which layer dropped the descendants.

### Mobile chrome

```
[ search ................. ] [filters n]
[ tree | radial | map | table ]
<canvas flex>
[ inspector sheet handle ]
```

Bottom sheet uses a drag handle, 40% default height, snap to 90% for filter editing.

### PWA

`manifest.webmanifest`: name "Reverse Etymology Atlas", standalone, theme color ink navy, 192/512 icons (simple SVG-generated PNGs checked in or generated at build).

Service worker: cache-first for `/assets/*` and `/`, network-first for `/api/*`.

## Phase 7 — tests

Synthetic graph in `tests/conftest.py`:

```
PIE *kaput -> Latin caput (inherited)
Latin caput -> Old French chef (inherited)
Old French chef -> English chief (borrowed)
Latin caput -> English capital (derived)   # no French hop
Latin caput -> French chef (inherited)
French chef -> English chef (borrowed)
```

Cases:

- No filters: all descendants present.
- Leaf language English: *chief*, *capital*, *chef* (English); French *chef* excluded; Latin kept as ancestor.
- Leaf English AND path any French/Old French: *chief* and English *chef* kept; *capital* dropped.
- Path none French: *capital* kept; *chief* dropped.
- Path all Romance family: depends on assigned families in the fixture.
- Relation construction without `borrowed`: English *chef* and *chief* disappear.
- Quantifier exactly 1.
- Cluster threshold unpack.
- Cycle: A->B->A does not infinite loop.
- Suggest ranks exact over prefix.
- API 404 on unknown root.

Run with `pytest -q`. The synthetic atlas is built in-memory; no parquet required.

Optional smoke: if `data/index/graph.npz` exists, one test queries Latin `mater` and asserts at least one inherited Romance daughter.

## Phase 8 — run, measure, polish

1. `python pipeline/download.py && python pipeline/build_index.py`
2. `cd frontend && npm install && npm run build`
3. `uvicorn backend.app:app --host 0.0.0.0 --port 8000`
4. Hit `/api/suggest?q=mater`, `/api/tree` for Latin mater, depth 3.
5. Confirm elapsed_ms in the budget.
6. Resize to 390px and check sheets, pinch, chips.
7. README: citation, how to run, filter semantics, license.

## File-level backend notes

`backend/graph.py`

- `class CSR: offsets, targets, rel, conf, src`
- `class Atlas: n, reverse, forward, node_traits, sqlite, meta, wals, phonemes, lang_index`
- `children(node, edge_filter) -> iterator of edge indices`

`backend/search.py`

- Parameterized FTS: `nodes_fts MATCH ?` with prefix `q*`, fallback LIKE for 1-character queries (FTS5 is weak there).
- Limit 20.

## Frontend performance notes

- Debounce suggest at 80 ms, tree refetch at 150 ms for slider drags.
- AbortController cancels in-flight tree requests when the query changes.
- Do not React-render every canvas frame; canvas is an imperative module.
- Table view windows 100 rows; full payload stays in memory (max 2500).

## Risks and mitigations

| Risk | Mitigation |
| --- | --- |
| `other` + compounds + cognates can turn affix queries into large bushy trees | Cluster stubs; max_visit; users can uncheck noisy relation types per query |
| Empty atlas family column | Glottolog enrichment |
| Lexibank ISO keys vs Wiktionary names | Dual resolver; show both in suggest |
| Cognate cliques | Cognates excluded from reverse walk by default; inspector only |
| Mobile canvas jank | DPR cap, LOD, cluster, 2500 node cap |
| Hugging Face download flaky | Retry, documented mirror paths, skip if files exist |
| WALS sparse coverage | `keep_unknown` toggle, fail-closed default |

## Acceptance criteria

- [ ] Design and this plan committed.
- [ ] Index builds from the published parquet files without manual cleanup.
- [ ] Searching `mater` + language Latin shows Romance inherited daughters.
- [ ] Leaf filter English + path filter French keeps only English descendants whose path includes French.
- [ ] Toggling cognates/compounds/other changes the tree.
- [ ] Map, table, stats, radial all consume the same filtered payload.
- [ ] Layout is usable at 390px width with touch pan/zoom.
- [ ] Filter unit tests pass without the full dataset.
- [ ] README documents run steps and CC BY-SA citation.