# Contributing to moonbit-indexmap

## Getting Started

```bash
# Prerequisites
# Install MoonBit: https://www.moonbitlang.com/download/

git clone https://github.com/aurasuisui/moonbit-indexmap
cd moonbit-indexmap
moon check   # Type check (0 warnings, 0 errors; --deny-warn clean)
moon test    # Run in-package tests (white-box + library-specific)
moon fmt     # Format code
```

## Project Layout

```
.
├── src/
│   ├── lib.mbt           # Public API entry points + VERSION + from_json aliases
│   ├── map.mbt           # IndexMap[K, V] core (all logic + from_json)
│   ├── set.mbt           # IndexSet[K] — thin wrapper over IndexMap[K, Unit]
│   ├── hash.mbt          # Shared load-factor constants
│   ├── map_test.mbt      # Black-box API tests for IndexMap (131 tests)
│   ├── set_test.mbt      # Black-box API tests for IndexSet (52 tests)
│   ├── arbitrary_test.mbt # QuickCheck property tests (11 tests)
│   ├── cmp_builtin_test.mbt # IndexMap-vs-builtin-Map parity + probe bound (7)
│   ├── model_wbtest.mbt  # WHITE-BOX model/oracle property test + 8 invariants
│   ├── fuzz_wbtest.mbt   # WHITE-BOX op-stream/int-stream fuzz
│   ├── moon.pkg          # Package config (test/quickcheck/debug/json/bench imports)
│   └── pkg.generated.mbti # Public interface (regenerated by `moon info`, CI-tracked)
├── cmd/                  # Example packages (use pkgtype; CI `examples` job compiles+runs)
│   ├── lru_cache/        #   LRU eviction demo
│   ├── config_parse/     #   Order-preserving config parser
│   └── json_order/       #   ToJson key-order demo
├── docs/
│   ├── RELEASE_CHECKLIST.md  # Per-tier release-test status (the release gate)
│   └── BUG-insert-duplicate-key.md  # Duplicate-key defect report and regression evidence
├── .github/workflows/ci.yml  # check + target×mode matrix + examples + bench
├── moon.work             # Workspace members: `.` + cmd/* (examples resolve local lib)
├── README.md
├── CHANGELOG.md
├── IMPROVEMENT.md        # Historical sprint checklist (competition acceptance)
└── LICENSE
```

> **Library vs `indexmap-test-suite` split:** this repo keeps **white-box +
> library-specific** tests (model + fuzz + API + QC + cmp-vs-builtin). The
> **black-box robustness battery** (HashDoS, fail-fast aborts, perf benchmarks +
> gate, `from_json` round-trip, Rust `indexmap` differential) lives in the
> separate [`indexmap-test-suite`](https://github.com/aurasuisui/indexmap-test-suite)
> repo, resolved as a local sibling via its `moon.work`.

## Style Guide

| Rule | Example |
|------|---------|
| Functions | `snake_case`: `locate`, `get_index_of` |
| Types | `PascalCase`: `IndexMap`, `OccupiedEntry` |
| Constants | `UPPER_CASE`: `MIN_CAPACITY`, `LOAD_FACTOR_NUMERATOR` |
| Public API docs | `///|` doc comment block |
| Internal docs | `///|` on internal helpers too |
| Section separators | `// ---` with label |
| Tests | `@aurasuisui/indexmap.` prefix for black-box access |

---

## Architecture Deep Dive

### Data Layout

IndexMap uses two parallel arrays:

```
IndexMap[K, V]
├── buckets:   Array[Entry[K, V]?]  ← Robin Hood hash table
├── order:     Array[K]             ← Insertion-order log
└── positions: Map[K, Int]          ← Key → index lookup (O(1) get_index_of)
```

**Buckets** is the hash table. Each slot is `Entry[K, V]?`: `None` means empty and every `Some(entry)` is live. Deletion uses backward-shift compaction, moving later displaced entries back one bucket until it reaches an empty bucket or an entry at its home bucket.

**Order** is a flat array of keys in insertion order. Iteration walks this array and looks up every key in the hash table.

### Key Constants

| Constant | Location | Value | Meaning |
|----------|----------|-------|---------|
| `MIN_CAPACITY` | map.mbt | 16 | Minimum bucket count (power of 2) |
| `LOAD_FACTOR_NUMERATOR` | hash.mbt | 3 | 3/4 = 0.75 load factor |
| `LOAD_FACTOR_DENOMINATOR` | hash.mbt | 4 | |

### Robin Hood Hashing

Standard open-addressing places each key at `hash(key) % capacity`. If occupied, it probes linearly. This causes **clustering**: some keys probe much farther than others.

Robin Hood improves this: when inserting, if the incoming key has probed **farther** than the key currently in the slot, the incoming key **steals** the slot and the displaced key continues probing. This equalizes probe distances across all entries.

In our implementation:

- `Entry.distance` records how far from its ideal bucket this entry has been displaced
- `locate(key, hash)` — searches through the next empty bucket before reporting a miss, and remembers the first valid Robin Hood insertion point
- `robin_hood_insert_into(...)` — shared insertion primitive for normal insertion and rehashing; if the current slot's entry has shorter distance, the incoming entry steals the slot
- `backshift_remove(index)` — restores contiguous probe paths after removal

### Internal Function Map

```
                    ┌──────────────────┐
                    │   Public API     │
                    └──────┬───────────┘
           ┌───────────────┼───────────────┐
           │               │               │
    ┌──────▼──────┐ ┌─────▼─────┐ ┌───────▼──────┐
    │ probe_find  │ │robin_hood │ │robin_hood    │
    │ (get/remove │ │ _find     │ │_insert_at    │
    │  /contains) │ │ (insert/  │ │ (insertion)  │
    └─────────────┘ │  entry)   │ └──────────────┘
                    └───────────┘
```

**`locate(key, hash) -> (index, found)`**
Single lookup path for `get`, `remove`, `contains`, `get_mut`, `insert`, `entry`,
stale Entry handles and `rehash`. It always probes through the next empty bucket
before reporting a miss, so key existence never depends on a distance-ordering shortcut.

**`robin_hood_insert_into(buckets, mask, entry, start_idx, max_probe) -> Int`**
Shared insertion primitive. It returns the updated maximum probe distance and is used by both
regular insertion and rehashing.

**`backshift_remove(index) -> Unit`**
Compacts a deletion hole. Every following entry with `distance > 0` moves back one bucket and
has its distance decremented; the operation stops at an empty bucket or a home-bucket entry.

**`remove_from_order(key) -> Unit`**
O(n) shift-remove using `positions: Map[K, Int]`. Shifts elements after the target one slot
left (fixing their positions), then pops the last slot. This preserves the insertion order of
remaining elements — the core ordering guarantee of IndexMap. Called by: `remove`, `get_mut`,
`retain`. (`swap_remove_index(i)` delegates to `remove(order[index])`, so it is **also O(n)
and order-preserving** despite its Rust-indexmap-style name — see README Gotcha #3.)

**`recalc_max_probe() -> Unit`**
O(capacity) scan of `buckets[]` recomputing `self.max_probe_distance` from live
`entry.distance` values. Called after `sort_by_key` / `sort_by`, which
rebuild `order`/`positions` in place — keeps the "this field always reflects the live buckets"
invariant explicit rather than relying on the fact that sorting does not move entries.

**`rehash(new_cap) -> Unit`**
Rebuild buckets from scratch using entries in insertion order and the shared
`robin_hood_insert_into` primitive.

**`should_resize_impl(len, capacity) -> Bool`**
Returns true when `len / capacity >= 0.75`.

### Deletion: Single Coherent Path

All deletion goes through `remove(key)` and compacts the affected bucket cluster:

- `remove(key)`: calls `backshift_remove`, then `remove_from_order`
- `get_mut` with `None` callback: delegates to `remove(key)`
- `OccupiedEntry::remove()`: delegates to `self.map.remove(self.key)`

Backward-shift compaction leaves no dead bucket entries and preserves a contiguous probe path from each live entry's home bucket.

### Iteration: How Order Is Preserved

`iter()`, `keys()`, and `values()` each return a lazy built-in `Iter[T]` built via
`Iter::new(fn() -> T? { ... }, size_hint=len)`. The closure captures a mutable `pos` cursor
into `self.order` and, on each `next()`, walks forward looking up the key in the hash table:

```
iter().next():
  advance pos through self.order:
    let val = self.get(key)   // lookup in hash table
    if val is Some → yield (key, val)   // key still exists
    else → skip                          // key was deleted, skip silently
  when pos reaches the end → yield None
```

This supports `for (k, v) in map { ... }` syntax. A consuming `IntoMapIter` (returned by
`into_iter()`) owns the drained entries and does not need table lookups.

### Memory Layout Invariants

These must ALWAYS hold true. Breaking any of them will cause bugs:

| Invariant | Enforced By |
|-----------|-------------|
| `self.len == count of occupied buckets` | All insert/remove paths |
| `self.order.length() == self.len` | remove_from_order (shift-remove), sort rebuilds |
| `self.positions.size() == self.len` | All insert/remove paths that touch order |
| `self.positions[key] == index` for each `order[index] == key` | insert, remove_from_order, sort rebuilds |
| `self.mask == self.buckets.length() - 1` | Constructor, resize |
| `self.buckets.length()` is a power of 2 | `next_power_of_two_impl` |
| `entry.distance == (bucket_index - home_bucket) & mask` | insertion, rehash, backshift removal |
| Every live entry has an occupied probe path from home to its bucket | insertion, rehash, backshift removal |
| A key appears in at most one bucket | unified lookup and insertion paths |
| `self.max_probe_distance >= max(entry.distance for all entries)` | insert, rehash, `recalc_max_probe` (after sort) |

---

## Adding a New Feature

### Pattern: Adding a new method to IndexMap

1. Add the implementation in `map.mbt` under the appropriate section
2. Add `///|` doc comment explaining params and return value
3. Add black-box tests in `map_test.mbt` using `@aurasuisui/indexmap.` prefix
4. Add a white-box model/property test in `model_wbtest.mbt` if there's an
   invariant to verify (random op-stream vs a naive-array oracle + internal
   invariants after every step); black-box robustness coverage (HashDoS, etc.)
   goes in `indexmap-test-suite` instead
5. Update the API table in `README.md`
6. Add a CHANGELOG entry

### Pattern: Adding a new trait implementation

Example from the codebase (adding `Debug`):
```moonbit
impl[K : Debug + Hash + Eq, V : Debug] Debug for IndexMap[K, V] with to_repr(self) {
  // collect entries → Repr array
  // return Repr::opaque_("IndexMap", Repr::map(entries))
}
```

Trait bounds must include `Hash + Eq` when the implementation iterates (which requires looking up keys).

---

## Testing Guide

### Test Categories

| File | Type | Count | What It Tests |
|------|------|-------|---------------|
| `map_test.mbt` | Unit | 131 | Per-method correctness, edge cases, order |
| `set_test.mbt` | Unit | 52 | IndexSet methods, set operations |
| `arbitrary_test.mbt` | QuickCheck | 11 | QuickCheck property tests for IndexMap + IndexSet |
| `cmp_builtin_test.mbt` | Load/cmp | 7 | IndexMap-vs-builtin-Map parity + benign-key probe bound |
| `model_wbtest.mbt` | White-box | 15 | Model/oracle (op-stream vs naive array) + 8 internal invariants |
| `fuzz_wbtest.mbt` | White-box | 2 | Op-stream + decoded-stream fuzz (shares model oracle) |

Black-box robustness tests (HashDoS, fail-fast, perf, Rust differential, JSON
round-trip) live in `indexmap-test-suite`, not here. ("Total" fluctuates as the
model/fuzz harnesses are parameterized; run `moon test` for the current count.)

### Test Convention

```moonbit
test "descriptive name in english" {
  let map = @aurasuisui/indexmap.new()
  // Arrange
  map.insert("key", 42) |> ignore
  // Act & Assert (expect-test snapshot)
  debug_inspect(map.get("key"), content="Some(42)")
}
```

All tests use `@aurasuisui/indexmap.` prefix (black-box testing). The `moon.pkg` imports
`moonbitlang/core/test` for `@test.fail` / `@test.assert_eq` and `moonbitlang/core/debug` for
`debug_inspect` (which binds the `Debug` trait — `inspect`, which bound `Show`, was deprecated
by `moonbitlang/core`). For assertions inside loops with many distinct values, prefer
`@test.assert_eq` / `@test.fail` over `debug_inspect` snapshots, since `moon test -u` generates
unstable snapshots when one `debug_inspect` runs N times with N different values.

### Running Tests

```bash
moon test                    # All in-package tests (currently 221)
moon test -f "model*"        # Model/oracle and white-box invariants
moon test -f "fuzz*"         # Deterministic op-stream fuzz
```

---

## Known Issues & Gotchas

> **Note:** Items below are historical records from earlier development cycles.
> The implementation now shares its Robin Hood insertion primitive between normal
> insertion and rehashing; item 5's O(1) swap-remove "fix" was reverted to O(n)
> shift-remove to preserve insertion order (see README Gotcha #3).
> For current known limitations, see the
> [README Gotchas section](README.md#gotchas).

### 1. ~~VERSION mismatch~~ ✅ Fixed
`lib.mbt`, `moon.mod`, and test now all read "0.2.0".

### 2. ~~Dead code in hash.mbt~~ ✅ Fixed
Unused constants and functions removed. Only `LOAD_FACTOR_NUMERATOR` and `LOAD_FACTOR_DENOMINATOR` remain (used by `map.mbt`).

### 3. ~~Duplicate function alias~~ ✅ Fixed
The earlier split lookup helpers were removed. `entry()` now shares the single
exhaustive `locate` path with all other key-based operations.

### 4. ~~get_mut deletion path was inconsistent~~ ✅ Fixed and redesigned
`get_mut` now re-applies its callback result through a fresh `insert` or `remove`, so stale
bucket indices cannot corrupt the table. `remove` uses backward-shift compaction to preserve
probe reachability.

### 5. remove_from_order — O(1) swap-remove attempted, then reverted
Briefly replaced the O(n) shift-remove with an O(1) swap-remove using a
`positions: Map[K, Int]` for key→index lookup. **Reverted to O(n) shift-remove**
because swap-remove broke the insertion order of remaining elements, which
contradicts IndexMap's core guarantee (see README Gotcha #3). The `positions` map
is kept for O(1) `get_index_of`; deletion is order-preserving shift-remove.

### 6. ~~sort_entries / sort_entries_by were unused~~ ✅ Fixed
Removed. Sorting is done inline in `sort_by_key` and `sort_by`.

### 7. ~~rehash duplicated Robin Hood insertion~~ ✅ Fixed
Both normal insertion and `rehash` now call `robin_hood_insert_into`.

---

## Roadmap

### v0.1.0 — Core Data Structures ✅
- IndexMap, IndexSet, Entry API, iterators, bulk ops, `Show`/`Hash`/`Eq`

### v0.2.0 — Standard Library Integration ✅
- `Debug`, `Default`, `ToJson`, `copy()`, `get_mut()`, `into_iter()`, `into_array()`, native sort

### v0.2.1 — Re-publish to mooncakes.io ✅
- Docs-only release re-published to mooncakes.io (no code changes)

### v0.3.0 — Competition Acceptance ✅
- [x] Runnable `cmd/*` example packages (lru_cache, config_parse, json_order)
- [x] `extend` → `extend_from_array` ([0035] reserved keyword)
- [x] CI updated to the 5-step pipeline (`moon fmt --check` / `moon check` / `moon info && git diff --exit-code` / `moon test` / `moon build`); `pkg.generated.mbti` CI-tracked
- [x] Migrated to TOML `moon.mod` / `moon.pkg`

### v0.3.1 — Warning Cleanup ✅
- [x] `inspect` → `debug_inspect` across source, tests, examples (binds `Debug`, not `Show`)
- [x] `Show::to_string` → `@debug.to_string` in ToJson impl and `cmd/json_order`
- [x] `moon check --deny-warn` passes (was 110 warnings)
- [x] Independent black-box test suite ([indexmap-test-suite](https://github.com/aurasuisui/indexmap-test-suite)) — 485 tests, all green; 1 bug + 4 design warnings documented as README Gotchas

### v0.3.2 — Test-Suite Recommendations ✅
- [x] BUG-001 fixed: `get_mut` re-insert-same-key-then-`None` no longer loses data (`contains` guard)
- [x] WARN-003 fixed: `max_probe_distance` recalculated after `sort_by` / `sort_by_key` (`recalc_max_probe()`)
- [x] WARN-002 clarified: README Gotcha #3 self-contradiction resolved
- [x] `cmd/*` excluded from `moon.work` so the library CI pipeline stays green on the CI `latest` toolchain (example main-declaration syntax is toolchain-version-sensitive); sources remain for reference
- [x] Publish v0.3.2 to mooncakes.io

### v0.3.3 — Post-Verdict Correctness Pass ✅
- [x] Entry API resize/stale-index fixed (no more infinite loop when filling via `entry()`; `OccupiedEntry` re-probes by key; `robin_hood_insert_at` termination guard; dropped the `bucket_index` field)
- [x] `get_mut` reworked to an authoritative contract (return value re-applied via a fresh `insert`/`remove`); fixes broken plain deletion, double-decrement, ghost entries, and resize mis-writes
- [x] `ToJson` keys fixed (`k.to_string()`, canonical for String keys); bound `K : ToJson` → `K : Show`
- [x] Iterators made truly fail-fast (mutation `version` counter + clear abort)
- [x] Regression tests for all four fixes; vacuous/misleading tests corrected; reproduced edge cases ported (255 → 277 tests at the v0.3.3 milestone)

### v0.4.0 — RELEASE_TEST_CHECKLIST Tier 1/2/3 coverage + test reorganization + duplicate-key fix ✅
- [x] **`from_json` / `from_json_with`** deserialization (new public API — the minor-version bump to `0.4.0`)
- [x] `[0083]` deprecation warnings fixed via qualified trait calls; `moon check --deny-warn` clean (was 14 warnings); `to_repr` → `Repr` cleanup (was 3 `[0020]` errors under `--deny-warn`)
- [x] Model/stateful property test + white-box invariants (`model_wbtest.mbt`); op-stream/int-stream fuzz (`fuzz_wbtest.mbt`)
- [x] HashDoS / adversarial collision tests; fail-fast iterator panic tests; real `moon bench` benchmarks + scaling-ratio regression gate ( THESE live in `indexmap-test-suite` now)
- [x] `from_json` round-trip + golden; Rust `indexmap` differential (replay + generator) — in `indexmap-test-suite`
- [x] CI hardened: `moon check --deny-warn` + `target × mode` matrix + `examples` job (statistical `bench` job moved to the suite CI, since `perf_bench_test.mbt` now lives there)
- [x] `cmd/*` migrated to `pkgtype(kind: "executable")` **and re-added to `moon.work`** (the old `options("is-main")` / `version: latest` conflict is resolved by `pkgtype`); examples now resolve the **local** library (registry-independent) and run in the `examples` CI job — fixes the CI failure where `cmd/*` couldn't resolve the unpublished package from mooncakes
- [x] Test reorganization (走向 1: library minimal + suite strong): dropped `property_test.mbt`/`bench_test.mbt` from the library; moved black-box robustness tests to `indexmap-test-suite`
- [x] Duplicate-key corruption repaired: tombstones were replaced by backward-shift deletion, and all key-based operations now share exhaustive `locate`; see [`docs/BUG-insert-duplicate-key.md`](docs/BUG-insert-duplicate-key.md)
- [x] Released as `0.4.0`: VERSION/moon.mod bumped, VERSION assertions updated, `pkg.generated.mbti` regenerated, `docs/RELEASE_CHECKLIST.md` re-run green (`moon publish` to mooncakes.io is the final manual step)

See [CHANGELOG.md](CHANGELOG.md) `[0.4.0]` for the full list.

## License

Apache 2.0 — see [LICENSE](LICENSE).