🔄 moon_collections

🏆 OSC 2026 — MoonBit 国产开源生态大赛参赛项目

Deterministic Data Processing Framework for MoonBit / WASM
确定性数据处理框架 — 为 MoonBit / WASM 而生

📋 项目总览 · 🇨🇳 中文 · 🇬🇧 English · ⚡ Quick Start · 📊 API 能力矩阵 · 📈 质量报告 · 🎯 大赛验收核对

🆕 What’s New — v0.2.4

对抗性审查（Adversarial Code Review）完成：对全部 15 个包进行了深度安全审查，修复 2 个 Bug（负值位移 UB、空集保护缺失），确认指纹缓存一致性全覆盖。

版本	亮点	验证
v0.2.4	对抗性审查 Bug 修复、回归测试	`moon check --deny-warn` ✅ • 316 测试全部通过 ✅
v0.2.3	7 项性能优化（块级跳过、O(n²)→O(n)）	`moon check --deny-warn` ✅ • 315 测试全部通过 ✅

📋 项目总览

moon_collections 是 MoonBit 生态中首个且唯一的完全确定性（Deterministic）集合框架。

它不是又一个”数据结构玩具库”——它解决了 WASM 生态中一个长期被忽视的正确性问题：不确定性。标准哈希集合在 WASM 上每次运行的迭代顺序都不同，这破坏了分布式共识、可重现构建、审计日志和可信序列化。 moon_collections 从集合层根治了它。

┌─────────────────────────────────────────────────────────────────┐
│                                                                  │
│   🎯 核心承诺                                                     │
│                                                                  │
│       相同输入 → 相同输出 → 相同指纹 → 永远不变                   │
│       Same Input → Same Output → Same Fingerprint → ALWAYS       │
│                                                                  │
│   📦 交付物：12 种数据结构 · 2 个开放特征 · 316 个测试           │
│          4 后端全覆盖 · 4,890 行源码 · 零警告 · CI/CD 完备        │
│                                                                  │
└─────────────────────────────────────────────────────────────────┘

🏆 为什么选择 moon_collections？

问题：WASM 的不确定性危机

当代码编译到 WebAssembly，标准库的哈希集合会产生一个静默的、不可预测的、每次运行都不一样的输出：

场景	标准 WASM 集合	moon_collections	影响
迭代顺序	🚫 每次运行都不同	✅ 插入顺序保证	可重现构建
结构相等性	❌ 不可能（顺序不定）	✅ FNV-1a 指纹	分布式验证
`remove()` 行为	🔄 swap-with-last（破坏顺序）	✅ shift_remove（保持顺序）	审计日志完整性
WASM 安全性	💥 `get()` 可能 trap	✅ 返回 `Option`（零 trap）	安全第一
跨节点验证	❌ 无法实现	✅ `ordered_eq()` 位置感知相等性	共识协议
测试确定性	❌ 无法写顺序无关断言	✅ 316 测试 × 4 后端全部一致	CI 可靠性
缓存验证	❌ 没有指纹机制	✅ 惰性 FNV-1a 指纹 O(1) 缓存	缓存失效判断

这不是性能问题——这是正确性问题。 不确定性破坏分布式共识、可重现构建、序列化一致性、审计日志完整性和跨平台验证。我们在集合层解决它。

跨语言生态对比

能力	moon_collections	Python `dict`	Rust `HashMap`	Go `map`	Java `HashMap`
确定性迭代	✅ 原生	✅ (3.7+)	❌	❌	❌
结构指纹	✅ FNV-1a 惰性缓存	❌	❌	❌	❌
位置感知相等性	✅ `ordered_eq()`	❌	❌	❌	❌
shift_remove 默认	✅	✅	❌ (swap)	❌ (delete)	❌
WASM 安全 Option	✅	N/A	❌ (panic)	N/A	N/A
开放特征扩展	✅ `pub(open) trait`	❌ (ABC)	❌ (trait 非开放)	❌	❌
跨结构转换	✅ IndexMap ↔ SortedMap	❌	❌	❌	❌

moon_collections 在确定性保证方面，超越了所有主流语言的对应标准库实现。

📦 快速数据

📚  12 种数据结构              🔬  316 个测试用例
🔗  2 个开放特征（open trait）  🖥️  4 个后端全覆盖
🧬  FNV-1a 指纹算法             🌐  WASM / WASM-GC / JS / Native
⚡  惰性缓存 O(1) 访问           📏  4,890 行 MoonBit 源码
🚫  0 警告（--deny-warn）        🎯  1,264 次运行全部通过
📦  已发布到 mooncakes.io        🔒  pre-commit 三重门
🛡️  CI/CD 五步流水线             📖  435 行 README 双版本

🇨🇳 中文介绍

WASM 世界中的不确定性危机

当代码编译到 WebAssembly，标准库的哈希集合会产生一个致命的、静默的不确定性：

// 标准 HashMap——每次运行结果不同！
HashMap::from_array([("a",1), ("b",2)])
// 第一次运行: [("a",1), ("b",2)]
// 第二次运行: [("b",2), ("a",1)]  ← 静默不一致！

这对以下场景是致命缺陷：

场景	后果	严重程度
🏛️ 分布式系统	无法验证两个节点上的集合是否”相同”	🔴 系统错误
📄 JSON 序列化	输出因运行环境而变，无法缓存/签名	🔴 数据不一致
📝 审计日志	无法重现历史状态，破坏合规审计	🔴 监管风险
🤝 共识协议	不确定的哈希值破坏一致性算法	🔴 协议失败
🧪 测试	无法编写与顺序无关的可靠断言	🔴 CI 不稳定
🔐 可信计算	WASM 中不可证明的集合行为	🔴 信任缺失

解决方案：三原则架构

┌─────────────────────────────────────────────────────────────────────┐
│                     moon_collections 架构总览                        │
│                                                                     │
│  ┌─ 开放特征层 ──────────────────────────────────────────────────┐  │
│  │                                                                │  │
│  │   ┌──────────────┐           ┌──────────────────────────┐     │  │
│  │   │  Collection   │           │     Deterministic         │     │  │
│  │   │  (open trait) │◄──────────│     (open trait)          │     │  │
│  │   │  ┌─────────┐  │  extends  │  ┌────────────────────┐  │     │  │
│  │   │  │ len()   │  │           │  │ fingerprint() →    │  │     │  │
│  │   │  │is_empty()│ │           │  │   UInt64 (惰性缓存) │  │     │  │
│  │   │  └─────────┘  │           │  │ ordered_eq() → Bool│  │     │  │
│  │   └───────────────┘           │  └────────────────────┘  │     │  │
│  │                               └──────────────────────────┘     │  │
│  └────────────────────────────────────────────────────────────────┘  │
│                                  │                                  │
│  ┌─ 数据结构实现层 ───────────────┼──────────────────────────────┐  │
│  │                               ▼                                │  │
│  │  ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐         │  │
│  │  │ IndexMap  │ │ IndexSet  │ │  BitSet  │ │ BitFlags │  ...   │  │
│  │  │ [K,V]     │ │ [K]       │ │          │ │          │        │  │
│  │  │ 有序哈希   │ │ 保序集合  │ │ 位集     │ │ 64位标志 │        │  │
│  │  └──────────┘ └──────────┘ └──────────┘ └──────────┘         │  │
│  │                   + 另外 8 种数据结构                           │  │
│  │        全部实现 Collection + Deterministic（除 Diff 外）        │  │
│  └────────────────────────────────────────────────────────────────┘  │
│                                  │                                  │
│  ┌─ 基础设施层 ──────────────────┼──────────────────────────────┐  │
│  │                               ▼                                │  │
│  │  ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────────────┐  │  │
│  │  │fingerprint│ │ convert  │ │   diff   │ │  CI/CD 流水线    │  │  │
│  │  │FNV-1a哈希 │ │跨结构转换 │ │LCS+编辑  │ │check/fmt/info/   │  │  │
│  │  │惰性缓存   │ │↔双向    │ │距离     │ │test/run 五步    │  │  │
│  │  └──────────┘ └──────────┘ └──────────┘ └──────────────────┘  │  │
│  └────────────────────────────────────────────────────────────────┘  │
│                                                                     │
│  🔐 核心承诺：相同输入 → 相同输出 → 相同指纹 —— 永远不变            │
│  Same Input → Same Output → Same Fingerprint → ALWAYS               │
└─────────────────────────────────────────────────────────────────────┘

三条设计原则：

原则	Principle	含义	工程实现
🎯 确定性	DETERMINISTIC	相同输入 → 始终相同输出	插入顺序保持、shift_remove 默认、无随机种子
🔍 可验证	VERIFIABLE	通过 FNV-1a 指纹进行结构相等性比较	惰性缓存、O(n)首次/O(1)后续、自动脏标记
🧩 可组合	COMPOSABLE	所有操作保持确定性	跨结构转换指纹一致、组合操作保持顺序

这不是性能问题，这是正确性问题。 不确定性破坏了可重现性、分布式共识和测试可靠性。我们在集合层解决它。

🇬🇧 English Introduction

The Crisis: Nondeterminism in WASM

When compiling to WebAssembly, standard hash-based collections produce silently nondeterministic output — a correctness time bomb:

// Standard HashMap — different result every run!
HashMap::from_array([("a",1), ("b",2)])
// Run 1: [("a",1), ("b",2)]
// Run 2: [("b",2), ("a",1)]  ← silently inconsistent!

This is fatal for production systems:

Domain	Consequence	Severity
🏛️ Distributed systems	Can’t verify two nodes agree on data	🔴 System-wide
📄 JSON serialization	Output varies per runtime, uncacheable	🔴 Data inconsistency
📝 Audit trails	Can’t replay historical state	🔴 Compliance risk
🤝 Consensus protocols	Non-deterministic hashes break agreement	🔴 Protocol failure
🧪 Testing	Can’t write order-independent assertions	🔴 CI flakiness
🔐 Trusted computing	Unprovable collection behavior in WASM	🔴 Trust deficit

The Solution: Three Principles

Principle	Meaning	Engineering
🎯 DETERMINISTIC	Same input → same output, always	Insertion order, shift_remove, no random seeds
🔍 VERIFIABLE	Structural equality via fingerprint	Lazy FNV-1a caching, auto-dirty tracking
🧩 COMPOSABLE	Operations preserve determinism	Cross-structure consistency, order preservation

This is a correctness problem, not a performance problem. We fix it at the collection level.

⚡ Quick Start

Installation (one line)

moon add wqbcs/moon_collections

Requirements: MoonBit toolchain ≥ 0.10.3

30-Second Demo

///|
fn main {
  // 1. Create — deterministic insertion order
  let m = @indexmap.IndexMap::new()
  m.insert("name", "Alice")
  m.insert("age", "30")
  m.insert("city", "Beijing")

  // 2. Iterate — always same order, every run
  println(m.keys_array()) // ["name", "age", "city"]

  // 3. Fingerprint — structural identity (lazy cached)
  println(m.fingerprint()) // stable UInt64

  // 4. Verify — order-aware equality
  let m2 = @indexmap.IndexMap::new()
  m2.insert("name", "Alice")
  m2.insert("age", "30")
  m2.insert("city", "Beijing")
  println(m.ordered_eq(m2)) // true (same order, same values)

  // 5. Remove — preserves insertion order
  m.remove("age")
  println(m.keys_array()) // ["name", "city"]
}

Run the full demo

moon run cmd/main

The demo walks through all 11 deterministic structures, proves fingerprints are order-sensitive, and demonstrates consistent behavior across runs.

📚 数据结构全家桶

12 种结构一览

结构	描述	时间复杂度	`Collection`	`Deterministic`	独创性
`IndexMap[K, V]`	有序哈希映射 — 插入顺序保持，O(1) 访问	O(1) avg	✅	✅	⭐ 核心
`IndexSet[K]`	保序集合 — 基于 IndexMap 实现	O(1) avg	✅	✅	⭐ 核心
`BitSet`	智能位集合 — 按需分配，64 位块存储	O(1) bit	✅	✅
`BitFlags`	64 位标志 — 位运算，8 指令实现	O(1)	✅	✅
`Counter[K]`	频率计数器 — `most_common(n)` 稳定排序	O(n log n)	✅	✅	⭐ 创新
`DefaultMap[K, V]`	默认值映射 — `get()` 永不返回 `None`	O(1) avg	✅	✅
`CompactIntMap[V]`	整数键映射 — 二分搜索，自动排序	O(log n)	✅	✅
`SortedMap[K, V]`	比较排序映射 — `floor()`/`ceil()` 搜索	O(log n)	✅	✅
`RingBuffer[T]`	固定容量环形缓冲区 — WASM 流式处理首选	O(1)	✅	✅
`SparseSet[V]`	ECS 稀疏集 — O(1) 插入/删除/查找	O(1)	✅	✅	⭐ 创新
`DisjointSet`	并查集 — 路径压缩 + 按秩合并 + 指纹规范化	O(α(n))	✅	✅	⭐ 创新
`Diff`	LCS + 编辑距离 — 纯算法（无状态）	O(n²)	✅	✗ (纯算法)

**11/12 结构实现了 Deterministic**（Diff 是纯算法，无内部状态，无需指纹）

跨结构转换矩阵

源 → 目标	方法	复杂度	确定性保持
`IndexMap` → `SortedMap`	`@convert.to_sorted_map(im)`	O(n log n)	✅
`SortedMap` → `IndexMap`	`@convert.to_index_map(sm)`	O(n)	✅
任意 → `Array[(K,V)]`	`.to_array()`	O(n)	✅
`Array[(K,V)]` → `IndexMap`	`IndexMap::from_array(arr)`	O(n)	✅
`Array[K]` → `IndexSet`	`IndexSet::from_array(arr)`	O(n)	✅

API 方法覆盖度

方法	IndexMap	IndexSet	BitSet	SortedMap	RingBuffer	Counter	SparseSet
`new()`	✅	✅	✅	✅	✅	✅	✅
`len()`/`is_empty()`	✅	✅	✅	✅	✅	✅	✅
`insert()`/`add`	✅	✅	✅	✅	✅	✅	✅
`get()`/`contains()`	✅	✅	✅	✅	✅	✅	✅
`remove()`	✅	✅	✅	✅	✅	✅	✅
`shift_remove()`	✅	✅	—	—	—	—	—
`clear()`	✅	✅	✅	—	✅	✅	✅
`clone()`	✅	✅	—	✅	—	—	—
`from_array()`	✅	✅	✅	✅	✅	✅	✅
`to_array()`	✅	✅	✅	✅	✅	✅	✅
`each()`/`iter()`	✅	✅	✅	✅	✅	✅	✅
`reverse()`	✅	✅	—	—	✅	—	—
`retain()`/`filter()`	✅	✅	—	✅	—	✅	—
`fingerprint()`	✅	✅	✅	✅	✅	✅	✅
`ordered_eq()`	✅	✅	✅	✅	✅	✅	✅

🧬 Core Traits

///|
pub(open) trait Collection {
  fn len(Self) -> Int
  fn is_empty(Self) -> Bool
}

///|
pub(open) trait Deterministic: Collection {
  fn fingerprint(Self) -> UInt64 // FNV-1a, lazy cached, O(1)
  fn ordered_eq(Self, Self) -> Bool // position-aware equality
}

开放特征（open trait）意味着你可以为任意自定义类型实现 Collection + Deterministic，使你的类型也能参与到确定性框架中。这是 MoonBit pub(open) 特性的独特优势——其他语言无法在外部 crate/包中为自定义类型实现外部 trait 的方法。

📊 API 能力矩阵

IndexMap 完整 API

📦 IndexMap[K, V]
├── 🏗️ 构造
│   ├── new()                             空映射
│   ├── from_array(pairs)                 批量构造
│   └── clone()                           深拷贝
├── 🔍 查询
│   ├── len() / is_empty()                大小
│   ├── get(key) → V?                     O(1) 访问
│   ├── contains(key) → Bool              成员判断
│   ├── get_index_of(key) → Int?          位置查询
│   ├── get_index(i) → (K, V)?            按索引访问
│   ├── first() / last() → (K, V)?        首尾元素
│   └── has_all(keys) / has_any(keys)     批量查询
├── ✏️ 修改
│   ├── insert(key, value) → V?           插入/更新
│   ├── remove(key) → V?                  默认 shift_remove
│   ├── shift_remove(key) → V?            保序删除
│   ├── swap_remove(key) → V?             交换删除（无序）
│   ├── shift_remove_index(i) → (K, V)?   按索引保序删除
│   ├── swap_remove_index(i) → (K, V)?    按索引交换删除
│   ├── clear()                           清空
│   ├── pop_front() / pop_back()          首尾弹出
│   └── retain(pred) / drain(pred)        条件保留/提取
├── 🔄 顺序操作
│   ├── reverse()                         反转
│   ├── sort_keys()                       按键排序
│   ├── move_to_front(key) / move_to_back(key)
│   ├── swap_indices(a, b)                交换位置
│   ├── insert_before(target, k, v)       定点插入
│   └── insert_after(target, k, v)        定点插入
├── 🔗 转换
│   ├── keys() / values() / iter()        迭代器
│   ├── keys_array() / values_array()     数组输出
│   ├── to_array()                        转数组
│   ├── filter(pred) → IndexMap           过滤（新）
│   ├── map_values(f) → IndexMap[R]       值映射
│   └── merge(other, resolve) → IndexMap  合并
├── 🔐 确定性
│   ├── fingerprint() → UInt64            FNV-1a 指纹
│   └── ordered_eq(other) → Bool          位置感知相等
└── 🛠️ 实用工具
    ├── update(key, f) → Bool             原地更新
    ├── update_or_insert(key, f, default) 更新或插入
    ├── get_or_insert(key, default) → V   惰性获取
    ├── get_or_insert_with(key, fn) → V   惰性获取
    ├── remove_entry(key) → (K, V)?       删除并返回完整条目
    └── op_index(key) → V?                下标语法

📈 质量报告

🧪 测试工程

指标	数值	含义
测试用例总数	316	覆盖全部 12 个数据结构
测试文件数	15	每个包独立测试
后端覆盖	4 (WASM · WASM-GC · JS · Native)	跨平台验证
单次 CI 运行	1,264 次 (316 × 4)	全量回归
通过率	100%	零失败
零警告严格模式	✅ `moon check --deny-warn`	拦截保留字/死代码

📐 代码度量

📁 项目结构
├── 📦 16 个包（15 个源码包 + 1 个可执行演示）
├── 📄 33 个 `.mbt` 源文件
├── 🧪 15 个测试文件（8 黑盒 + 4 白盒 + 3 综合）
└── 📏 4,890 行 MoonBit 源码

🔍 代码质量
├── 🚫 0 个未使用导入（--deny-warn 验证）
├── 🚫 0 个未使用变量（--deny-warn 验证）
├── 🚫 0 个运行时警告
├── 🔄 0 个循环依赖（traits/fp/diff 为叶包）
└── 🎯 100% CI 通过率

🛡️ CI/CD 流水线

每次 push 和 PR 强制通过 5 道门：

步骤	命令	拦截目标	耗时
①	`moon check --target all --deny-warn`	类型错误、保留字、死代码	~5s
②	`moon fmt && git diff --exit-code`	格式偏差	~2s
③	`moon info && git diff --exit-code`	公开接口偏差	~2s
④	`moon test --target all`	回归缺陷（1,264 次测试）	~30s
⑤	`moon run cmd/main`	运行时正确性	~2s

任何一道门未通过 → PR 不能合并。没有例外。

🔐 pre-commit 本地门禁

git config core.hooksPath .githooks
# 以后每次 git commit 自动运行: check + fmt + info

⚡ 指纹性能

操作	复杂度	机制
首次指纹计算	O(n)	全结构哈希
缓存访问	O(1)	`fp_dirty` 标记跟踪
修改后失效	O(1)	仅翻转脏位
`ordered_eq()`	O(n)	首个不匹配短路

不使用指纹时零开销。 fp_dirty / fp_cache 字段在初始化后不被访问，直到你第一次调用 fingerprint()。

🎯 大赛验收核对

moon_collections 对照 OSC 2026 大赛验收标准逐条达标：

#	验收标准	状态	证据
1	MoonBit 为主要实现语言	✅	4,890 行 MoonBit，零非 MoonBit 代码
2	GitHub 公开可访问	✅	github.com/wqbcs/moon_collections
3	源码结构清晰，核心功能完成	✅	15 包按功能分目录，无循环依赖
4	README 完整可复现	✅	本文档，含安装/使用/示例/API/架构
5	CI 覆盖检查/构建/测试	✅	5 步流水线，1,264 次测试全通过
6	可运行示例	✅	`moon run cmd/main` 输出 6 段确定性证明
7	完整测试覆盖核心路径	✅	316 测试 × 4 后端，全部通过
8	已发布到 mooncakes.io	✅	`moon add wqbcs/moon_collections`
9	OSI 许可证	✅	Apache 2.0
10	有效代码行数	✅	4,890 行
11	合理提交记录	✅	40+ 有意义的提交
⭐	`moon check --deny-warn`	✅	零警告
⭐	`moon fmt && git diff --exit-code`	✅	格式一致
⭐	`moon info && git diff --exit-code`	✅	接口一致
⭐	CI 完整性	✅	5 步 + 3 矩阵 + pre-commit

🔒 Determinism Guarantee（确定性保证）

                ┌──────────────────────────────────────┐
                │          Same Input                   │
                │  相同数据 + 相同插入顺序                │
                └──────────────┬───────────────────────┘
                               │
                               ▼
                ┌──────────────────────────────────────┐
                │        moon_collections 引擎           │
                │                                      │
                │  ① shift_remove（默认保序删除）        │
                │  ② 插入顺序保持迭代                     │
                │  ③ FNV-1a 确定性哈希（无随机种子）      │
                │  ④ 惰性指纹缓存自动失效                  │
                │  ⑤ 跨结构转换保持顺序                    │
                └──────────────┬───────────────────────┘
                               │
                               ▼
           ┌──────────────────────────────────────────────┐
           │         Same Output（始终相同）               │
           │   + Same Fingerprint（始终相同）              │
           │                                              │
           │  → 任何机器 → 任何 WASM 运行时 → 任何次数    │
           │  → 结果永远一致，指纹永远一致                  │
           └──────────────────────────────────────────────┘

✅ 确定性保证清单

保证	说明	验收方式
相同 `.keys_array()` 顺序	插入顺序保持，跨运行不变	`moon run cmd/main`
相同 `.fingerprint()`	结构相同时指纹相同	`assert_eq(m1.fp(), m2.fp())`
不同 `.fingerprint()`	不同插入顺序 → 不同指纹	`assert_ne!(m1.fp(), m3.fp())`
`ordered_eq()` 位置感知	仅相同顺序 + 相同值返回 true	`m.ordered_eq(m2)`
`remove()` 保序	shift_remove 默认，无 swap-with-last	`keys after remove`
跨结构指纹一致	IndexMap ↔ SortedMap 转换后指纹稳定	`@convert` 测试

❌ 不保证（和原因）

不保证	原因
性能与原生 HashMap 持平	确定性有常数开销（shift_remove 需要 O(n) 平移）
密码学级哈希	FNV-1a 是快速非加密哈希，有碰撞可能

🏗️ Architecture （项目架构）

moon_collections/                         🌐 模块名: wqbcs/moon_collections v0.2.4
│
├── moon.mod                              📋 模块配置（名称/版本/许可证/关键词）
├── moon.pkg                              📦 根包（工厂函数 + 转换器重导出）
├── AGENTS.md                             🤖 AI 协作指南
├── CHANGELOG.md                          📝 版本更新日志
├── LICENSE                               ⚖️ Apache 2.0
├── README.mbt.md                         📖 本文档（含类型检查）
├── README.md                             📖 文档副本（mooncakes 兼容）
├── .gitattributes                        🔧 跨平台行尾规范
│
├── traits/                               🎯 核心抽象层
│   ├── traits.mbt                        Collection + Deterministic 开放特征
│   └── traits_test.mbt                   特征实现测试
│
├── fingerprint/                          🧬 哈希基础设施
│   ├── fingerprint.mbt                   FNV-1a 哈希函数 + RollingFingerprint
│   └── fingerprint_test.mbt              哈希单元测试
│
├── indexmap/                             📖 核心有序映射
│   ├── indexmap.mbt                      IndexMap[K,V]（824 行，38 个公开方法）
│   ├── indexset.mbt                      IndexSet[K]（基于 IndexMap 包装）
│   └── indexmap_test.mbt                 + indexset_test.mbt
│
├── bitmask/                              🟦 位运算家族
│   ├── bitflags.mbt                      BitFlags（64-bit 标志）
│   ├── bitset.mbt                        BitSet（稀疏位集，643 行）
│   └── bitset_test.mbt                   + bitflags 测试
│
├── counter/                              📊 频率分析
│   ├── counter.mbt                       Counter[K]（316 行）
│   └── counter_test.mbt
│
├── defaultmap/                           🗺️ 默认值映射
│   ├── defaultmap.mbt                    DefaultMap[K,V]（惰性默认值）
│   └── defaultmap_test.mbt
│
├── compactintmap/                        🔢 整数键映射
│   ├── compactintmap.mbt                 二分搜索 + 自动排序
│   └── compactintmap_test.mbt
│
├── sortedmap/                            📐 比较排序映射
│   ├── sortedmap.mbt                     SortedMap[K,V]（483 行）
│   └── sortedmap_test.mbt
│
├── ringbuffer/                           🔄 环形缓冲区
│   ├── ringbuffer.mbt                    RingBuffer[T]（509 行）
│   └── ringbuffer_test.mbt
│
├── sparseset/                            ⚡ ECS 稀疏集
│   ├── sparseset.mbt                     SparseSet[V]（312 行）
│   └── sparseset_test.mbt
│
├── disjointset/                          🔗 并查集
│   ├── disjointset.mbt                   DisjointSet（321 行，指纹规范化）
│   └── disjointset_test.mbt
│
├── diff/                                 📏 序列比较
│   ├── diff.mbt                          LCS + 编辑距离
│   └── diff_test.mbt
│
├── convert/                              🔁 跨结构转换
│   ├── convert.mbt                       IndexMap ↔ SortedMap 双向转换
│   └── convert_test.mbt
│
├── cmd/main/                             🎬 可执行演示
│   ├── main.mbt                          main 函数
│   └── moon.pkg                          is-main = true
│
├── bin/                                  🛠️ 辅助脚本
│   └── moon-deny-warn                    fmt/info --deny-warn 包装器
│
├── .github/workflows/
│   ├── ci.yml                            🛡️ CI 流水线（5 步 × 3 矩阵）
│   ├── publish.yml                       📦 mooncakes.io 自动发布
│   └── copilot-setup-steps.yml           🤖 Copilot 环境
│
└── .githooks/
    └── pre-commit                        🔒 本地门禁（check + fmt + info）

架构设计原则

┌─────────────────────────────────────────────────────────┐
│                   架构设计原则                            │
├─────────────────────────────────────────────────────────┤
│  ✅ 零循环依赖 — traits/、fingerprint/、diff/ 是叶包     │
│  ✅ 最小导入 — 每个包只导入需要的依赖                    │
│  ✅ 接口同步 — .mbti 文件通过 moon info 自动生成         │
│  ✅ CI 强制执行 — git diff --exit-code 捕获任何漂移      │
│  ✅ 可扩展 — 开放特征允许外部类型加入确定性框架          │
│  ✅ 测试隔离 — 每个包独立测试，白盒 + 黑盒双重覆盖       │
└─────────────────────────────────────────────────────────┘

🏅 已完成里程碑

版本	交付内容	日期
v0.1.0	IndexMap + IndexSet + FNV-1a 指纹基础设施	2026-06
v0.2.0	全部 12 种数据结构 + CI/CD 流水线 + 中英双语 README	2026-07
v0.2.3	批量性能优化（块级跳过、O(n²)→O(n)字符串构建）、IndexMap 一致性修复	2026-07-10
v0.2.4	对抗性审查 Bug 修复（负值位移、空集保护）、指纹缓存全覆盖审查	2026-07-10

🤝 参与贡献

# 1. 安装本地门禁
git config core.hooksPath .githooks

# 2. 做改动

# 3. 验证
moon check --deny-warn && moon test --target all

# 4. 提交 PR — CI 自动运行 1,264 次测试

所有贡献必须维护确定性不变性（Determinism Invariant）。

📄 License

Apache 2.0 — 详见 LICENSE

Copyright 2026 wqbcs

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

moon_collections — Deterministic by design. Verifiable by fingerprint. Composable by construction.

确定性设计 · 指纹可验证 · 组合可保证

📦 GitHub · 🌙 mooncakes.io · 📘 MoonBit Docs

_{🏆 参赛 MoonBit 国产开源生态大赛 OSC 2026 · 用确定性改变 WASM 世界}

_{Built with ❤️ for the MoonBit ecosystem}