moon_collections

#📋 项目总览

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

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

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

#🏆 为什么选择 moon_collections？

#问题：WASM 的不确定性危机

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

#跨语言生态对比

#📦 快速数据

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

#🇨🇳 中文介绍

#WASM 世界中的不确定性危机

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

#解决方案：三原则架构

┌─────────────────────────────────────────────────────────────────────┐
│                     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               │
└─────────────────────────────────────────────────────────────────────┘

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

#🇬🇧 English Introduction

#The Crisis: Nondeterminism in WASM

// 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!

#The Solution: Three Principles

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 种结构一览

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

#跨结构转换矩阵

#API 方法覆盖度

#🧬 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?                下标语法

#📈 质量报告

#🧪 测试工程

#📐 代码度量

📁 项目结构
├── 📦 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 流水线

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

#🔐 pre-commit 本地门禁

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

#⚡ 指纹性能

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

#🎯 大赛验收核对

#🔒 Determinism Guarantee（确定性保证）

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

#✅ 确定性保证清单

#❌ 不保证（和原因）

#🏗️ Architecture （项目架构）

moon_collections/                         🌐 模块名: wqbcs/moon_collections v0.2.2
│
├── 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]（311 行）
│   └── 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 捕获任何漂移      │
│  ✅ 可扩展 — 开放特征允许外部类型加入确定性框架          │
│  ✅ 测试隔离 — 每个包独立测试，白盒 + 黑盒双重覆盖       │
└─────────────────────────────────────────────────────────┘

#🏅 已完成里程碑

#🤝 参与贡献

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

# 2. 做改动

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

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

#📄 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.