#◐ moonmask

#一眼看懂

#工作原理

flowchart TB
    subgraph C["① 约束 → 自动机"]
        direction TB
        S["JSON Schema"] -- "schema::to_regex" --> AST["语法树"]
        R["Regex"] --> AST
        G["GBNF"] -- "规则展开" --> AST
        AST -- "Thompson 构造" --> NFA["NFA"]
        NFA -- "子集构造 · 剪枝 · 距离" --> DFA[("字节 DFA")]
    end
    subgraph V["② 词表 → 前缀树"]
        direction TB
        TJ["tokenizer.json"] -- "tokenizers-moonbit" --> VO["token → 字节串"]
        VO --> TR["字节前缀树"]
    end
    DFA --> GD{{"③ Guide：每个状态的 token 掩码（带缓存）"}}
    TR --> GD
    GD -- "allowed(state)" --> SP["④ 采样器：非法 token 的 logit 置 −∞"]
    SP -- "advance(state, token)" --> GD

1. 约束 → DFA。 三种约束都先变成同一种语法树，再经 Thompson NFA、子集构造得到按字节转移的 DFA。到不了接受状态的状态被剪掉，所以“走到死状态”在任何时候都能立刻发现；每个状态还记下离接受状态最少还差几个字节。
2. 词表 → 前缀树。 用 tokenizers-moonbit 读取 GPT-2 的 tokenizer.json，把 50,257 个 token 还原成字节串并建成前缀树。
3. DFA × 前缀树 → 掩码。 从当前状态出发沿前缀树走，相同前缀只走一次，走不通就剪掉整棵子树。结果按状态缓存。
4. 解码循环。 采样器只在掩码内选 token，然后用 advance 推进状态，直到在接受状态选出 eos。

sequenceDiagram
    autonumber
    participant M as LLM
    participant G as Guide (moonmask)
    participant S as 采样器
    loop 直到输出 eos
        M->>S: 这一步的 logits（50,257 维）
        G->>S: allowed(state)：当前合法的 token
        S->>S: 其余 token 置 −∞，再采样
        S->>G: advance(state, token)
        G-->>G: state ← 下一状态
    end
    Note over G,S: eos 只在接受状态放行，所以结束时输出一定完整且合法

#实验结果

./scripts/fetch-gpt2.sh     # 按固定版本下载 GPT-2 tokenizer.json 并校验 SHA-256
moon run cmd/main --target native -- assets/gpt2/tokenizer.json \
  examples/schemas/user.json examples/schemas/order.json examples/schemas/tool_call.json
# 可选空白模式：同样三组 schema、种子和词表
moon run cmd/main --target native -- --whitespace assets/gpt2/tokenizer.json \
  examples/schemas/user.json examples/schemas/order.json examples/schemas/tool_call.json

#快速开始

git clone https://github.com/FidollarinLA/moonmask.git
cd moonmask
# macOS / Linux:
export PATH="$HOME/.moon/bin:$PATH"
moon update
moon run cmd/quickstart

moon add FidollarinLA/moonmask@0.1.0

import {
  "FidollarinLA/moonmask/schema",
  "FidollarinLA/moonmask/vocab",
  "FidollarinLA/moonmask/mask",
}

///|
fn main raise {
  let dfa = @schema.compile({ "enum": ["ok"] })
  let vocab = @vocab.Vocab::new([b"\"ok\"", b"\"no\"", b""], eos=2)
  let guide = @mask.Guide::new(dfa, vocab)
  // 非法 token 的分数更高，仍会被排除。
  assert_eq(guide.greedy(guide.start(), [0.0, 100.0, 0.0]), Some(0))
  println("PASS")
}

let tok = @tokenizer.from_file("assets/gpt2/tokenizer.json")
let vocab = @vocab.from_tokenizer(tok, eos_token="<|endoftext|>")
let guide = @mask.Guide::new(@schema.compile(schema), vocab)
let mut state = guide.start()
// 每一步：只保留 guide.allowed(state)，其余 logit 置为 -inf，采样得到 token，然后：
if token == vocab.eos {
  assert_true(guide.is_accept(state)) // 仅在接受状态允许结束
} else {
  match guide.advance(state, token) {
    Some(next) => state = next
    None => panic() // 非法 token；不能把 None 一律当作合法 eos
  }
}

#支持什么

#项目结构

moonmask/
├── regex/        正则解析 → Thompson NFA → 子集构造 DFA（剪枝、距离、采样）
├── schema/       JSON Schema 子集 → 字节级正则
├── gbnf/         GBNF 文法 → 同一种 DFA
├── vocab/        GPT-2 tokenizer.json → token 字节串（基于 tokenizers-moonbit）
├── mask/         Guide：前缀树 + 每状态掩码缓存；monkey / monkey_step 采样器
├── cmd/main/     猴子打字机实验 CLI（native 后端）
├── playground/   浏览器 Playground（MoonBit + rabbita，独立模块，不进发布包）
├── examples/     实验用的三个 schema
├── docs/         规格细则、设计说明、截图
└── scripts/      fetch-gpt2.sh：下载并校验 GPT-2 词表

#Playground

• 在 JSON Schema / 正则 / GBNF 之间切换，边改边重新编译，看 DFA 状态数和 schema 生成的正则；
• 播放或单步解码，对比加掩码和不加掩码：不加掩码时通常第一个 token 就掉进死状态；
• 看当前状态有多少 token 合法，点击某个 token 自己充当模型；
• 看自动机的局部结构和刚走过的轨迹；
• 一键跑 30 + 30 次随机采样实验；
• 把玩具词表换成真实的 GPT-2 词表（浏览器里下载并解析 50,257 个 token）。

#文档

• docs/acceptance.md：九项验收证据、复现命令与演示步骤
• docs/dependencies.md：依赖、参考项目与许可证来源

• docs/schema-subset.md：支持的 JSON Schema 关键字和边界情况
• docs/gbnf.md：GBNF 子集
• docs/design.md：算法细节、终止性、测试方法
• examples/logits/README.md：真实模型 logits 接入、协议与运行方法
• docs/logits-demo.md：固定版本真实模型的逐步证据与限制
• CHANGELOG.md

#测试

moon test --deny-warn

#限制

• 推理时每一步都要能拿到 logits。只返回整段文本的云端 API 只能事后校验。
• 只生成紧凑 JSON（不含空白），object 属性按声明顺序输出。
• 不支持递归结构：递归 schema、递归 GBNF 规则都会报错。
• 词表只支持 GPT-2 字节级 BPE；SentencePiece 会在加载时拒绝。

#参考与许可证