# Contributing to moonbit-bimap

## Getting Started

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

## Project Layout

```
.
├── src/
│   ├── lib.mbt            # Public re-exports (new/with_capacity), VERSION, Overwritten enum
│   ├── hashtable.mbt      # Private pure Robin Hood engine (adapted from indexmap, no ordering)
│   ├── bimap.mbt          # BiMap core: two inverse tables + order + positions + put_pair
│   ├── bimap_api.mbt      # insert_no_overwrite, index access, from_array/copy/to_inverse
│   ├── bimap_iter.mbt     # Fail-fast iter/lefts/rights
│   ├── bimap_traits.mbt   # Debug/Default/Show/Eq/Hash/ToJson/Arbitrary
│   ├── bimap_test.mbt     # Black-box unit tests (C0-C4 matrix, lookup, removal)
│   ├── property_test.mbt  # QuickCheck invariant tests (the bijection guard)
│   ├── bench_test.mbt     # Stress tests (10k ops, resize cascade, tombstones, fuzz)
│   ├── arbitrary_test.mbt # QuickCheck generation tests
│   ├── traits_test.mbt    # Trait + iteration tests
│   ├── edge_test.mbt      # Per-API edge cases
│   ├── types_test.mbt     # Boundary key/value type coverage
│   ├── coverage_test.mbt  # Additional API coverage + QuickCheck shapes
│   ├── more_test.mbt      # Final coverage batch
│   ├── model_test.mbt     # Differential tests vs a naive Array[(L,R)] oracle
│   ├── bimap_wbtest.mbt   # White-box invariant + HashDoS tests (reads private fields)
│   ├── iter_test.mbt      # Iterator independence + size_hint effect
│   ├── generics_test.mbt  # Custom-struct keys, Int boundaries, capacity stability
│   ├── moon.pkg           # imports test / quickcheck / debug
│   └── pkg.generated.mbti # generated by `moon info` (CI-tracked)
├── cmd/                   # Example packages (username_email, country_code)
├── docs/                  # Living: README(hub) / SPEC / MOONBIT_REF / SESSION_PLAYBOOK / RELEASE_CHECKLIST;
│                          # archived: DEVPLAN / 申报书  — full map in docs/README.md
├── .github/workflows/ci.yml
├── README.md / CONTRIBUTING.md / CHANGELOG.md / CLAUDE.md / LICENSE
```

## Style Guide

| Rule | Example |
|---|---|
| Functions | `snake_case`: `get_by_left`, `put_pair` |
| Types | `PascalCase`: `BiMap`, `Overwritten` |
| Constants | `UPPER_CASE`: `MIN_CAPACITY`, `TOMBSTONE_HASH` |
| Public API docs | `///|` doc comment block |
| Internal docs | `///|` on internal helpers too |
| Section separators | `// ---` with label |
| Tests | `@aurasuisui/bimap.` prefix for black-box access |
| Qualified trait calls | `Hash::hash(x)`, `Show::to_string(x)` (avoid the deprecated dot form on type params) |

---

## Architecture Deep Dive

### Data Layout

```
BiMap[L, R]
├── forward  : HashTab[L, R]   ← left→right Robin Hood table
├── backward : HashTab[R, L]   ← right→left Robin Hood table (reverse lookup only; NO order)
├── order    : Array[L]        ← left keys in insertion order (single source of order)
├── positions: Map[L, Int]     ← left key → index in `order` (O(1) get_index_of_left)
├── len      : Int             (mut)
└── version  : Int             (mut) ← mutation counter for fail-fast iterators
```

`HashTab[K, V]` is a **pure** open-addressing Robin Hood table: `buckets: Array[Entry?]`,
`len`, `mask`, `tombstone_count`, `max_probe_distance`. It has **no ordering** — ordering
is the `BiMap` layer's job. This separation (pure table vs. ordering) is what makes `BiMap`
more cohesive than `indexmap` (which couples the table and order in one struct). Only `len`
and `version` are `mut` fields on `BiMap`; the table/array/map fields are mutated in place
through their own methods, never reassigned.

### The Bijection Invariants (must ALWAYS hold)

```
∀ (l, r) ∈ forward  ⟺  backward[r] == l        // two sides strictly inverse
forward.len == backward.len == order.length()
            == positions.length() == self.len  // five consistent counters
positions[order[i]] == i                         // position map self-consistent
order has no duplicate left keys
forward.buckets.length() is a power of 2
```

**Discipline:** every mutation goes through the private helpers `put_pair` (insert path) and
`remove_by_left` / `remove_by_right` (removal path). Public methods never sync the two tables
themselves — that is the #1 source of BiMap bugs. The `check_bijection` helper in
`property_test.mbt` asserts the black-box observable form of these invariants.

### Insertion: the five cases (C0–C4)

`insert(l, r)` first short-circuits **C1** (exact pair already present → `Pair(l, r)`,
no mutation). This short-circuit is essential: without it, `(Some(r), Some(l))` would be
mis-handled as a C4 collapse. Otherwise `put_pair` handles:

- **C0** (both free): add fresh pair, append `l` to `order`, `len + 1`.
- **C2** (`l→r'`, `r` free): rebind `l` to `r`; drop `r'` from `backward`. `l` **keeps its
  order position** (rebinding does not change insertion order — an intentional extension).
- **C3** (`l'→r`, `l` free): drop `l'` from `forward` + `order` + `positions`; bind `(l, r)`;
  append `l` to `order`. Net length unchanged.
- **C4** (`l→r'` AND `l'→r`): collapse two pairs into one — remove both `(l,r')` and `(l',r)`,
  then bind `(l,r)`. `l` keeps its position; `l'` is removed. **`len` decreases by 1.**

The return `(old_right?, old_left?)` from `put_pair` maps to the `Overwritten` enum.

### Deletion: symmetric two-sided cleanup

`remove_by_left(l)` looks up `r = forward[l]`, removes `l` from `forward` and `r` from
`backward`, and shrinks `order`/`positions`, bumping `version`. `remove_by_right` is
symmetric. Missing one side breaks the bijection — the property tests catch this.

### Eq/Hash are order-independent (unlike indexmap)

A `BiMap` is a *set of pairs*. `Eq` compares pair sets (ignoring insertion order); `Hash`
combines per-pair fingerprints with a **commutative** operation (sum) so reordering doesn't
change the hash. The per-pair fingerprint is `Hash::hash(l) * 0x9E3779B9 + Hash::hash(r)`
(order-sensitive within a pair, so `(l,r)` differs from `(r,l)`). This is the opposite of
`indexmap` (order-sensitive) and is documented as a Gotcha.

---

## Adding a Feature

1. Implement in the right `src` file (`bimap*.mbt`, or `hashtable.mbt` for engine work).
2. Add a `///|` doc comment.
3. Add black-box tests (`@aurasuisui/bimap.` prefix) in the appropriate `*_test.mbt`.
4. Add a property test in `property_test.mbt` if an invariant is involved.
5. Update the API table in `README.md`.
6. Add a CHANGELOG entry.
7. Run the five-step CI locally: `moon fmt --check && moon check && moon info &&
   git diff --exit-code && moon test && moon build`.

---

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

文档漂移的根因是**同一信息存了两份**。本仓库实行**单一真源(SSOT)**:每条事实只住一个
文件,别处只链接不复制(完整 SSOT 表见 [`docs/README.md`](docs/README.md))。

**改动联动清单**——动了左边,必须同步右边:

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

**收尾自检**(每个 PR / 会话结束前):
1. 按上表联动更新,没有"只改代码不改文档"。
2. `docs/README.md` 地图里每份文档都真实存在、没有孤儿条目。
3. 全文 grep 不残留指向已删文件的链接。
4. 五步 CI 全绿。

> 这套约定替代了 CI 脚本——靠每个会话自觉执行。`docs/SESSION_PLAYBOOK.md §5` 把"知识回写"
> 列为每个任务会话的收尾必做项,与本文互锁。

---

## Testing Guide

| File | Type | What it tests |
|---|---|---|
| `bimap_test.mbt` | Unit | C0–C4 matrix, bidirectional lookup, removal, index access |
| `property_test.mbt` | Invariant | Bijection + five-counter invariants across random op sequences |
| `bench_test.mbt` | Stress | 10k insert/remove, resize cascade, tombstone buildup, 20k-op fuzz |
| `arbitrary_test.mbt` | QuickCheck | Generated BiMaps satisfy invariants, order-independent Eq/Hash |
| `traits_test.mbt` | Unit | Order-independent Eq/Hash, Debug/Show/ToJson/Default, iteration |
| `model_test.mbt` | Differential | Same op stream vs a naive `Array[(L,R)]` oracle; exact content+order match each step |
| `bimap_wbtest.mbt` | White-box | Strong invariants on private fields (five counters, `positions`, mask, bucket inverse, tombstones); HashDoS flood correctness + probe distance |
| `iter_test.mbt` | Unit | Simultaneous-iterator independence; `collect()` / `size_hint` effect |
| `generics_test.mbt` | Unit | User-defined struct keys (both sides), portable Int boundary keys, capacity stability |
| `edge_test.mbt` / `types_test.mbt` / `coverage_test.mbt` / `more_test.mbt` | Unit | Edge cases, boundary key/value types, extra coverage |

Conventions:
```moonbit
test "descriptive english name" {
  let m = @aurasuisui/bimap.new()
  m.insert("a", 1) |> ignore
  debug_inspect(m.get_by_left("a"), content="Some(1)")
}
```
- For assertions inside loops with varying values, use `@test.assert_eq` / `@test.fail`
  (not `debug_inspect`, which makes `moon test -u` generate unstable snapshots).
- `Overwritten` results are checked via a `classify` helper that pattern-matches the value
  into a `String` (MoonBit cannot construct a cross-package nullary enum variant in value
  position, but matching works fine and also captures the payload).
- Helper functions that call `@test.assert_eq` must be declared `-> Unit raise` (assertions
  raise on failure).

---

## Roadmap

### v0.1.0 — Core
- `BiMap`, two insert semantics, bidirectional lookup/removal, index access, order
  preservation, `to_inverse`, standard traits, fail-fast iterators, examples, tests, CI.

### v0.1.1 — Hardening
- Test suite 203 → 229 (differential model, white-box invariants, iterator contract,
  generics, HashDoS). Zero compiler warnings: dead code removed, deprecated API uses
  replaced, trait bounds minimized to the per-side minimum (`moon check/test --deny-warn`
  clean). See CHANGELOG `[0.1.1]` for details.

### v0.2.0 — Planned (not in scope for the hackathon)
- `BiBTreeMap` (sorted variant), `retain`, set-view adapters, richer entry-style helpers.

---

## License

Apache 2.0. Robin Hood engine adapted from `aurasuisui/indexmap` (Apache-2.0);
BiMap semantics ported from Rust `bimap` (MIT/Apache-2.0) and Guava `BiMap` (Apache-2.0).