# Contributing to moonbit-multiindex

## Getting Started

```bash
# Prerequisites: install MoonBit from https://www.moonbitlang.com/download/
git clone https://github.com/aurasuisui/moonbit-multiindex
cd moonbit-multiindex
moon check   # type check
moon test    # run all tests
moon fmt     # format
```

## Branch model

| Branch | Role |
|---|---|
| **`dev`** | The working branch. **Every commit lands here first** — the full, granular history (one commit per node, message says what it did and why). |
| **`main`** | The **milestone view**. A stage is squash-merged here once its exit criteria are met, so `main` reads as one commit per milestone instead of hundreds of nodes. |

```bash
# land a finished stage on main (main is a generated milestone *view*)
git checkout main
git read-tree --reset -u dev      # make main's tree exactly dev's, in one step
git commit -m "feat: M<n> <stage> —— <one-line summary>"
git push origin main
git checkout dev
```

> **Why not `git merge`** — all three variants fail or backfire, which is why the recipe above
> uses plumbing instead:
>
> | Attempt | Result |
> |---|---|
> | `git merge dev` | `fatal: refusing to merge unrelated histories` (`main` was squashed at project start and shares no ancestor with `dev`) |
> | `git merge --squash --allow-unrelated-histories dev` | git treats **every file as add/add** and conflicts on each one that differs |
> | `git merge dev` (no `--squash`) | drags all of `dev`'s node commits onto `main`, destroying the milestone view |
>
> `git read-tree --reset -u dev` sidesteps all three: it sets `main`'s index **and** worktree to
> `dev`'s tree, so the next commit has exactly the end state a squash-merge would have produced.
>
> Consequence to be aware of: **`main` is a view, not an ancestry.** `git log --graph` will never
> show `dev` merging into `main`, and that is intended — the evidence lives in `dev`.

> **Why both branches are public**: `main` is the readable overview, `dev` is the evidence.
> Squashing for `main` must never be used to hide work — the detailed record stays in `dev`,
> and **commit dates are never rewritten**: a milestone is merged on the day it actually finished.

## Project Layout

```
.
├── src/
│   ├── lib.mbt             # Public types: VERSION, RowId, Conflict/Rejected/RegisterError/UpdateRejected, IndexStats, IndexKind
│   ├── table.mbt           # Table core: rows/gens/free/order/positions + chokepoints + fail-fast iterators
│   ├── index.mbt           # Index[K,V] four-quadrant enum + bucket add/remove/slots/cursors
│   ├── table_api.mbt       # register_* / unregister_index / get_by / iter_by / range family / diagnostics
│   ├── extends.mbt         # Official-style `pub extend` promotions (keeps [0079] at zero)
│   ├── json.mbt            # JSON round-trip + decode errors
│   ├── table_test.mbt      # Black-box unit tests
│   ├── table_wbtest.mbt    # White-box invariants + "the guard is not vacuous" negative tests
│   ├── property_test.mbt   # check_invariants (I1-I8) - observable projection
│   ├── property_wbtest.mbt # Same invariants read off private fields, after every step
│   ├── model_test.mbt      # Differential vs naive Array[V] oracle
│   ├── differential_test.mbt + differential_fixture_test.mbt  # vs Rust reference (Tier 1)
│   ├── json_test.mbt       # JSON round-trip, re-registration, malformed input
│   ├── bench_test.mbt      # Stress tests
│   ├── moon.pkg            # imports test / quickcheck / debug / json / sorted_map
│   └── pkg.generated.mbti  # generated by `moon info` (CI-tracked)
├── cmd/                    # Example packages (imports the PUBLISHED package)
├── bench/                  # Timing benchmarks (@bench; standalone)
├── tools/diffgen/          # Dev tooling: Rust fixture generator (standalone)
├── docs/                   # Full map in docs/README.md
├── .github/workflows/ci.yml
└── README.md / CONTRIBUTING.md / CHANGELOG.md / AGENTS.md / LICENSE
    (AGENTS.md 是面向所有编码 agent 的唯一会话入口,不再维护 CLAUDE.md 镜像)
```

## Style Guide

> **通用约定的唯一真源是 [`docs/STYLE.md`](docs/STYLE.md)** —— 命名、代码组织、文档注释、测试风格、
> CI、license header 的官方依据都在那里(实测自 `moonbitlang/core` 仓库与官方 CI)。**本节只列本项目需要强调的几条**,
> 不重复其内容。

| Rule | Example |
|---|---|
| 黑盒测试前缀 | `@aurasuisui/multiindex.` —— **本库硬性约定**(见 §H.6:`+unnecessary_annotation` 会与它冲突,故不启用该 lint) |
| 限定 trait 调用 | `Hash::hash(x)`, `Show::to_string(x)` —— 避免多约束类型参数上的点调用(`[0083]`) |
| 长度与效果 | `array.length()` 而非 `.size()`;效果标 `raise` 而非已废弃的 `!` |
| **MoonBit 语法坑** | 结构体/枚举泛型**不能**带 trait 约束(`struct T[K : Hash + Eq]` 是语法错误),约束写在方法上 |

---

## Architecture Deep Dive

### Data Layout

```
Table[K, V]
├── rows    : Array[V?]                  ← slot storage; None = free slot
├── gens    : Array[Int]                 ← per-slot generation, +1 on recycle
├── free    : Array[Int]                 ← free-slot stack (LIFO); retired slots NEVER re-enter (I9)
├── order   : Array[Int]                 ← live slots in insertion order
├── indexes : Map[String, Index[K, V]]   ← the 2x2 index registry
├── mut len : Int
└── mut version : Int                    ← mutation counter (fail-fast iterators)

Index quadrants (matches the reference's hashed/ordered x unique/non-unique):
   unique + hashed   -> Map[K, Int]
   unique + ordered  -> SortedMap[K, Int]
   non-unique + hashed  -> Map[K, SortedSet[Int]]
   non-unique + ordered -> SortedMap[K, SortedSet[Int]]

Index entries store **slot numbers only, never RowId** — generations exist only to
validate caller-supplied handles; bucket entries are maintained inside the chokepoints
and always point at the current live record.
```

**Indexes never store values** — they store slot numbers only. Values live in exactly one
place (`rows`), which is what makes "one update touches all indexes and stays consistent"
tractable. Buckets are **sorted sets** (`SortedSet[Int]`), so removing one entry is O(log k)
rather than the O(k) a plain array would cost on large buckets. The trade-off: **bucket
iteration order is slot-number ascending, not insertion order.**

### The invariants (must ALWAYS hold — see docs/DEVPLAN.md §3)

```
(asserted in `property_wbtest.mbt`, since `Table`'s fields are private and `*_test.mbt` is an external package)

I1  every slot in `order` is live, and appears once
I2  live record count == len == order.length()
I3  no duplicate slots inside any bucket (structural for SortedSet; cross-checked anyway)
I4  for every bucket entry s: (idx.project)(rows[s]) == bucket key
I5  every UNIQUE index bucket has length <= 1
I6  `free` has no duplicates and is disjoint from live slots
I7  every live record appears in exactly the right bucket of every index
I8  version only increments on a real change
I9  retired slots never re-enter free (exhausted generation -> slot permanently removed)
```

**I5 and I7 must be checked as a pair**: I7 catches "missing", I5 catches "extra". Skipping I5
is how the `update`-conflict bug (below) stayed invisible — `verify` returned true while a
unique bucket held two holders.

### Chokepoint discipline (the #1 source of bugs)

Every mutation funnels through exactly four private helpers; **no other code may touch
`rows` + `order` + `indexes` + `gens` + `free` together**:

| Helper | Steps |
|---|---|
| `insert_impl` | conflict check **before any mutation** → allocate slot → write row → bucket-add in every index → `order.push` |
| `remove_impl` | bucket-del in every index → `rows[slot]=None` → `gens[slot]+=1` → `free.push` → compact `order` |
| `modify_impl` | conflict check **excluding self** → bucket-del old in every index → write row → bucket-add new in every index |
| `clear_impl` | bulk retire: every live slot gets `gen += 1` then returns to `free` (exhausted generations retire for good) → clear `rows`/`order`/`indexes`; `version` bumps only if the table was non-empty |

### Four high-risk paths (probe- and source-validated)

1. **`update` must conflict-check *excluding itself*.** The probe showed that omitting this lets
   a record take a unique key already held by another record, silently breaking I5.
2. **Conflict checks happen before any mutation.** On `Err`, the table must be byte-for-byte
   equivalent to before the call for **value records** (mirrors bimap's `insert_no_overwrite`).
   A `modify` closure that already mutated a shared container cannot be rolled back — see
   [`docs/SPEC.md`](docs/SPEC.md) §3.7 「拒绝路径的边界」.
3. **No observable intermediate state between old-bucket-removal and new-bucket-insertion.**
   When the key is unchanged, take a fast path instead of delete-then-add.
4. **`modify` must finish all uniqueness pre-checks before committing any index change.**
   The Rust reference removes the old key first and only then tries the new one, **panicking
   mid-way and leaving dirty indexes** (`generators.rs:322-332`). Our order is fixed:
   compute new projections → pre-check every unique index (excluding self) → commit together.

---

## Adding a Feature

1. Implement in the right `src` file (through a chokepoint if it mutates).
2. Add a `///|` doc comment.
3. Add black-box tests in `table_test.mbt`.
4. Add/extend an invariant in `property_test.mbt` (and I5/I7 if the feature touches indexes).
5. Update the API table in `README.md` **and** the contract in `docs/SPEC.md`.
6. Add a CHANGELOG entry.
7. Run the eight-check CI locally (the block in `AGENTS.md`). The example job is run through the
   verified `moon.work` recipe recorded in [`.gitignore`](.gitignore) — `cmd/leaderboard` is a
   standalone module, so without it you are running the published copy, not your changes.
8. **Version bump follows the change's nature** — see the 版本策略 section in
   [`docs/RELEASE_CHECKLIST.md`](docs/RELEASE_CHECKLIST.md). A backwards-compatible addition is a
   **MINOR** bump, a compatible fix is **PATCH**, and an incompatible change is **MAJOR**
   (the `0.x` exemption is **not** used in this project). Decide it from the diff, not by habit.

---

## Doc Sync Convention(文档同步约定 · 防漂移防死文件)

单一真源(SSOT):每条事实只住一个文件,别处只链接不复制(完整 SSOT 表见 [`docs/README.md`](docs/README.md))。

| 你改了 | 必须同步更新 |
|---|---|
| 公开 API(签名/返回类型/语义) | `docs/SPEC.md` + `README.md` 的 API 表 |
| 任何行为变化 / 关键决策 | `CHANGELOG.md`(Notes / Deviations) |
| 架构 / 不变量 / 开发流程 | `CONTRIBUTING.md` |
| 命令 / 工具链 / 高层架构速览 | `AGENTS.md`(唯一会话入口) |
| 新增或删除任何文档 | `docs/README.md` 枢纽的地图表 |
| bump 版本 / `moon publish` 前 | `docs/RELEASE_CHECKLIST.md` 逐项全绿,并在 `CHANGELOG.md` 记一行勾选结果 |

**收尾自检**:① 按上表联动更新;② `docs/README.md` 无孤儿条目;③ 全文 grep 不残留指向已删文件的链接;
④ 八项 CI(两个 job,含示例冒烟)全绿。

---

## Testing Guide

| File | Type | What it tests |
|---|---|---|
| `table_test.mbt` | Unit (black-box) | insert / get / remove / clear matrix, slot reuse, stale-handle rejection |
| `property_wbtest.mbt` | Invariant (white-box) | `check_invariants` (I1/I2/I6 + observable I9) read straight off private fields, after **every step** of random sequences — plus **"the guard is not vacuous" meta-tests** that corrupt `free`/`order` and assert the checker throws |
| `property_test.mbt` | Invariant (black-box) | the observable projection of the same invariants (len / iter / get / insertion order / stale handles rejected) |
| `model_test.mbt` | Differential | Same op stream vs a naive `Array[V]` linear-scan oracle |
| `differential_test.mbt` | Differential (Tier 1) | Op-stream observations vs the **real Rust reference**; fixture generated by `tools/diffgen`, checked in — `moon test` needs no Rust |
| `table_wbtest.mbt` | White-box | `free`/live disjointness (I6), generation monotonicity, slot inverse, the `update`-conflict regression, and **negative tests** that corrupt `order` / `free` / index buckets to prove each `verify_*` check actually fires |
| `abort_guard_wbtest.mbt` | White-box (`test "panic …"` + companions) | Every reachable `abort` guard, one trigger per test, each fixture re-run by an ordinary-named companion test; plus the three defensive branches that are reachable (`record_at` out of range / removed, `iter` over a dangling `order` entry) |
| `json_test.mbt` | Unit (black-box) | JSON round-trip, re-registration after load, malformed input |
| `differential_fixture_test.mbt` | Fixture loader | Parses the checked-in golden fixture consumed by `differential_test.mbt` |
| `bench_test.mbt` | Stress | 10k+ op mixes, slot-reuse storms, long buckets |

Conventions:

```moonbit
test "descriptive english name" {
  let t : @aurasuisui/multiindex.Table[String, (String, String)] = @aurasuisui/multiindex.Table::new()
  t.register_unique("name", fn(p) { p.0 })
  debug_inspect(t.len(), content="0")
}
```

- Avoid `debug_inspect` inside loops with varying values (unstable `moon test -u` snapshots);
  use `@test.assert_eq` / `@test.fail` there.
- Helper functions that call `@test.assert_eq` must be declared `-> Unit raise`.
- Invariant helpers are black-box: assert through the public API, not private fields
  (private-field assertions belong in `*_wbtest.mbt`).
- **Asserting an `abort` / panic**: name the test `test "panic …"` — the `panic ` prefix is the
  *only* mechanism (`try/catch` cannot see a panic: `[0023] unused_try`; there is no `#panic`
  attribute: `[4132]`). Such a test passes on **any** panic, so make the guard the *only* thing
  that can panic: assert every precondition (fixtures, `verify_invariants`, index existence)
  first, and leave the offending call as the final statement. Delete the guard and the test fails
  with `panic is expected` — that is the built-in negative control. See `docs/MOONBIT_REF.md` §7.1.
- **Coverage** is a checkable gate, not decoration:

  ```bash
  moon test --enable-coverage
  moon coverage analyze -p aurasuisui/multiindex -- -f summary   # totals
  moon coverage analyze -p aurasuisui/multiindex -- -f caret     # per-line gaps
  moon coverage clean
  ```

  Current: **847/868**. `-f caret` flags 21 lines, most of which are *failure branches* rather than
  code that never ran — the reporter groups a condition line with its failure branch, so read the
  table in [`docs/SPEC.md` §7.3](docs/SPEC.md) rather than the raw line numbers. A new uncovered
  line must either get a test or a row in that table: **no silent drift**.