nelsonduarte/capa-language

# Capa [](https://github.com/nelsonduarte/capa-language/actions/workflows/tests.yml) [](https://github.com/nelsonduarte/capa-language/releases) [](LICENSE) [](pyproject.toml) [](https://slsa.dev/spec/v1.0/levels#build-l1) [](https://github.com/nelsonduarte/capa-language/discussions) [](CONTRIBUTING.md) **网站：** **Capa** 编程语言的完整前端：词法分析器、语法分析器、语义分析器、Python 转译器和运行时，全部用 Python 手写。 **Capa 程序首次可以运行了。** ``` $ capa --run examples/grades.capa === Roster === Ana: 17.5 (Excellent) Bruno: 13.0 (Pass) Carla: 8.5 (Fail) Diogo: 15.5 (Good) Eva: 11.0 (Pass) Filipe: 19.0 (Excellent) Statistics: Average: 14.083333333333334 Passed: 5 Failed: 1 ``` ## 项目布局 ``` Capa/ ├── capa/ # Python package implementing the compiler │ ├── __init__.py # public package exports │ ├── __main__.py # enables `python -m capa ...` │ ├── cli.py # command-line utility │ ├── tokens.py # TokenKind, Token, Pos, KEYWORDS │ ├── errors.py # LexerError with pedagogical formatting │ ├── typesys.py # internal type representation │ ├── builtins.py # declarative table of built-in types + methods │ ├── _suggest.py # Levenshtein matcher for "did you mean" hints │ ├── formatter.py # canonical-style formatter (capa-fmt) │ ├── init_project.py # `capa init` project scaffolding │ ├── lexer/ # mixin-composed lexer (significant-indentation) │ ├── parser/ # recursive-descent parser, split by item kind │ ├── capa_ast/ # AST node definitions, split by category │ ├── analyzer/ # name resolution + type check + capability disc. │ ├── transpiler/ # codegen for Python 3.10+, split by AST kind │ ├── manifest/ # capability manifest + CycloneDX SBOM emitter │ ├── docgen/ # HTML doc generator from /// doc-comments │ ├── lsp/ # Language Server Protocol implementation │ └── runtime/ # Result, Option, Stdio, Fs, ..., Unsafe, py_import ├── tests/ # 792 unit, end-to-end, and property tests │ ├── test_lexer.py │ ├── test_parser.py │ ├── test_analyzer.py │ ├── test_transpiler.py # transpile and execute Capa programs │ ├── test_lsp.py # language-server features │ ├── test_formatter.py │ ├── test_attributes.py │ ├── test_docs.py │ └── test_properties.py # Hypothesis-based property tests ├── examples/ # .capa files demonstrating the language │ ├── hello.capa # hello world │ ├── basics.capa # several constructs │ ├── tasks.capa, grades.capa # non-trivial programs │ ├── io.capa # Result and the ? operator │ ├── net_attenuation.capa # capability attenuation │ ├── fs_env_attenuation.capa # Fs / Env narrowing │ ├── clock_attenuation.capa # Clock not-before │ ├── user_capabilities.capa # user-defined capabilities │ ├── python_interop.capa # Python boundary under Unsafe │ ├── demo_event_stream.capa # CVE case study: event-stream 2018 │ ├── cve_eslint_scope.capa # CVE case study: eslint-scope 2018 │ ├── cve_ua_parser_js.capa # CVE case study: ua-parser-js 2021 │ ├── cve_torchtriton.capa # CVE case study: torchtriton 2022 │ ├── cve_node_ipc.capa # CVE partial-loss: node-ipc 2022 │ ├── cve_xz_utils.capa # CVE partial-loss: xz-utils 2024 │ ├── cve_pyyaml.capa # CVE design-pattern: PyYAML yaml.load() (2017) │ ├── cve_jinja2_ssti.capa # CVE design-pattern: Jinja2 SSTI │ ├── cve_lxml_xxe.capa # CVE design-pattern: XML external entity │ ├── cve_pickle.capa # CVE design-pattern: pickle gadget chains │ ├── empirical_config.capa # SBOM diff micro-validation (Capa side) │ ├── empirical_config_naive.py # SBOM diff micro-validation (Python side) │ ├── llm_tool_sandbox.capa # LLM tool-use sandboxing via capability discipline │ ├── llm_agent_runner.capa # Mock LLM + Capa-typed tool dispatch loop │ ├── llm_anthropic_real.capa # Real Anthropic Messages API round-trip │ ├── llm_anthropic_agent.capa # Real LLM + Capa-typed tool dispatch loop │ ├── llm_anthropic_helper.py # Python bridge for the real-API HTTP dance │ ├── vex_demo.capa # @vex per-function exploitability claims │ ├── spdx_parser.capa # SPDX 2.3 JSON parser, in Capa │ ├── cyclonedx_parser.capa # CycloneDX 1.5 JSON parser, in Capa │ ├── spdx_license_expr.capa # SPDX Annex D license-expression parser │ ├── sbom_capability_audit.capa # SBOM ↔ policy audit pipeline │ ├── sbom_diff.capa # SBOM v1 ↔ v2 capability-change report │ └── data/ # sample SBOM + policy for the audit demo ├── docs/ # public website + design writeups │ ├── index.html, tour.html, start.html, why.html │ ├── manifest.html, reference.html, stdlib.html, roadmap.html │ ├── positioning.md # honest comparison vs Pony, Koka, Roc, Wasm-CM │ ├── semantics.md # λ_cap calculus sketch + soundness theorems │ ├── cra.md # Cyber Resilience Act article-by-article mapping │ ├── regulatory.md # Multi-jurisdiction comparative (CRA+NIS2+DORA+SSDF+SCVS) │ ├── provenance-signing.md # Capa SLSA L1 -> L2 via cosign / Sigstore │ ├── empirical_micro.md # SBOM diff Python vs Capa, fully reproducible │ ├── llm-tool-sandbox.md # LLM tool-use sandboxing via capabilities │ ├── demo-event-stream.md # case study walkthrough │ ├── cve_eslint_scope.md # case study walkthrough │ ├── cve_ua_parser_js.md # case study walkthrough │ ├── cve_torchtriton.md # case study walkthrough │ ├── cve_node_ipc.md # case study walkthrough (partial loss) │ └── cve_xz_utils.md # case study walkthrough (partial loss) ├── proofs/ # Agda mechanisation skeleton (lambda_cap) │ ├── README.md # status, plan, how to typecheck │ ├── CapaSyntax.agda # syntax + typing + reduction │ └── CapaSoundness.agda # theorem statements as postulates ├── benchmarks/ # runtime-overhead suite: Capa vs hand-Python │ ├── runner.py # in-process timeit-based runner │ ├── *.capa + *_baseline.py # paired workloads (fib, scope, ua_parse) │ └── README.md # methodology + headline numbers ├── Capa-EBNF.md # formal grammar of the language ├── pyproject.toml # package metadata + optional [test] / [lsp] extras ├── LICENSE # MIT └── README.md ``` **关于模块名称的说明：** `capa_ast/`（而非 `ast/`）和 `typesys.py`（而非 `types.py`）避免了与 Python 标准库模块冲突，这些冲突会在通过 `python -m capa` 调用包时导致微妙的循环导入错误。 ## 完整流水线 ``` .capa ↓ Lexer tokens with significant indentation ↓ Parser AST ↓ Analyzer name resolution + types ↓ Transpiler Python 3.10+ code ↓ Runtime imports Result, Stdio, Fs, ... ↓ python execute Capa program running ``` ## 安装 ### 一键安装（推荐） 安装程序下载预构建的二进制文件，将其放置在 `~/.local/bin/capa`（在 Windows 上为 `%LOCALAPPDATA%\capa\capa.exe`），并该目录添加到用户 `PATH`。无需 Python 安装；二进制文件捆绑了自己的解释器。 ``` # Linux / macOS Apple Silicon curl -fsSL https://raw.githubusercontent.com/nelsonduarte/capa-language/main/deploy/install.sh | bash ``` ``` # Windows (PowerShell) irm https://raw.githubusercontent.com/nelsonduarte/capa-language/main/deploy/install.ps1 | iex ``` 打开一个新终端，运行 `capa --version` 应会打印安装版本。之后，在任何目录下都可以使用 `capa init my-project`。 可通过 `INSTALL_DIR`（bash）或 `CAPA_INSTALL_DIR`（PowerShell）环境变量覆盖安装位置。 ### 手动下载二进制文件 如果您更喜欢手动安装，请从[最新版本](https://github.com/nelsonduarte/capa-language/releases/latest)下载对应平台的文件： | 平台 | 文件 | |---|---| | Linux x86_64 | `capa-linux-x86_64` | | macOS Apple Silicon (M1 及更新) | `capa-macos-arm64` | | Windows x86_64 | `capa-windows-x86_64.exe` | Intel Mac 未提供预构建二进制文件；请从源码安装（见下文）。 每个版本还附带一个 `.sha256` 校验和文件；在运行前请验证下载： ``` sha256sum -c capa-linux-x86_64.sha256 ``` ### 从源码安装 在项目根目录（`Capa/`）： ``` pip install -e . ``` 这是推荐的源码安装方式。它将 `capa` 命令添加到您的 `PATH` *并* 注册该包到 Python 导入系统，因此 `capa ` 和 `python -m capa ` 可以在**任何目录**下工作。 要自行构建二进制文件： ``` pip install pyinstaller>=6.0 pyinstaller deploy/capa.spec ./dist/capa --run examples/hello.capa ``` ### 编辑器支持 VSCode 扩展（提供语法高亮）位于 [`vscode/`](vscode/)。它尚未上架应用商店；请手动安装，使用符号链接（macOS/Linux：`ln -s "$(pwd)/vscode" ~/.vscode/extensions/capa-language`；Windows：`New-Item -ItemType Junction ...`）并重新加载 VSCode。 ### 语言服务器 (LSP) 编译器附带一个语言服务器。安装可选依赖并启动： ``` pip install -e '.[lsp]' # adds pygls>=2.0 capa lsp # speaks LSP over stdio ``` v1 版服务器提供： - **诊断**：每次更改时运行完整的词法分析器 + 语法分析器 + 分析器流水线，因此编辑器会显示与 `capa --check` 相同的错误，包括 `; did you mean 'X'?` 提示。 - **悬停**：将光标放在函数上会显示 Capa 风格的签名；放在参数或绑定上会显示 `name: T` 以及类型标签；放在结构体字段 / 和类型变体 / 能力 / 常量上会显示相应细节。在引用和声明处都会触发。 - **跳转到定义**：从任何引用（或声明本身）跳转到名称声明的精确列。内置符号（`Stdio`, `Net`, `Result`, …）被干净地过滤，因此不会跳转到 "line 0"。 - **查找引用**：列出文件中解析为相同符号的每个标识符；遵循 LSP 请求中的 `includeDeclaration` 标志。 - **文档符号**（大纲）：模块的层次视图。常量、结构体（嵌套字段）、和类型（嵌套变体，细节中包含负载类型）、trait 和能力（嵌套方法签名）、顶级函数和 impl 块（嵌套方法）按源代码顺序显示。 - **代码操作**（快速修复）：每个 `; did you mean 'X'?` 提示都会产生一个单击 "Replace with 'X'" 操作，标记为首选，因此编辑器的默认键盘快捷键会应用它。 对于大多数客户端，编辑器配置是一行设置。对于 Helix (`languages.toml`)： ``` [[language]] name = "capa" language-servers = ["capa"] file-types = ["capa"] [language-server.capa] command = "capa" args = ["lsp"] ``` 对于使用 `nvim-lspconfig` 的 Neovim： ``` require("lspconfig").configs.capa = { default_config = { cmd = { "capa", "lsp" }, filetypes = { "capa" }, root_dir = require("lspconfig.util").root_pattern(".git", "."), }, } require("lspconfig").capa.setup({}) ``` （如果 `capa` 不在您的 `PATH` 上，请使用 `python -m capa` 替换。） 补全和语义标记已排入 v2 版本计划。 ### 网站 一个五页的静态网站位于 [`docs/`](docs/)： - [`docs/index.html`](docs/index.html)，主页 - [`docs/why.html`](docs/why.html)，该语言的优势 - [`docs/tour.html`](docs/tour.html)，语言导览 - [`docs/start.html`](docs/start.html)，安装 + 第一个程序 + CLI 参考 - [`docs/roadmap.html`](docs/roadmap.html)，现状与路线图 无 JavaScript、无框架、无外部字体；一个样式表 (`docs/style.css`)。 本地预览：`cd docs && python -m http.server` 并打开 `http://localhost:8000/`。为 `docs/` 目录启用 GitHub Pages 后，它将作为项目的公共网站。 ## CLI ``` # Tokenize capa examples/hello.capa # 解析 (AST) capa --parse examples/tasks.capa # 分析 (lex + parse + semantic check) capa --check examples/io.capa # 转译为 Python (输出到标准输出) capa --transpile examples/grades.capa # 运行 Capa 程序 (转译 + 执行) capa --run examples/grades.capa # 创建新项目脚手架 capa init my-project # 就地格式化文件 (行级, 幂等) capa --fmt main.capa # 生成 JSON 能力清单 (每函数能力 + 属性) capa --manifest examples/manifest_demo.capa # 生成包含能力元数据属性的 CycloneDX 1.5 SBOM capa --cyclonedx examples/manifest_demo.capa # 从 /// 文档注释生成独立的 HTML 文档页面 capa --doc examples/documented_demo.capa > demo.html # 启动语言服务器 (stdio) capa lsp ``` `capa` 命令通过 `pip install -e .` 和 PyInstaller 二进制发行版安装。如果两者都不可用，请将上述所有调用替换为 `python -m capa`。 ## 编程使用 ``` from capa import Lexer, Parser, analyze, transpile source = open("program.capa", encoding="utf-8").read() tokens = Lexer(source, filename="program.capa").lex() module = Parser(tokens, source=source, filename="program.capa").parse_module() result = analyze(module, source=source, filename="program.capa") if not result.ok: for e in result.errors: print(e.format()) else: code = transpile(module, filename="program.capa") print(code) ``` ## 测试 ``` python -m unittest discover tests ``` **769 项测试**，涵盖词法分析器、语法分析器、分析器、转译器、LSP、格式化器、属性模式验证和 Hypothesis 驱动的属性测试。转译器套件实际上*执行*了生成的 Python 代码并检查标准输出，这是测试转译器的唯一诚实方式。属性套件 (`tests/test_properties.py`) 使用任意文本输入、语法感知的 Capa 程序以及 `runtime_capability_set ⊆ manifest_declared_set` 的健全性不变式对完整流水线进行模糊测试，这些程序通过 `main` 线程化 `Fs` / `Net` / `Env` / `Clock` / `Random`。使用 `pip install -e .[test]` 安装 Hypothesis。 ## Capa → Python 映射 | Capa | 生成的 Python | |-------------------------------------|-----------------------------------| | `fun f(x: T) -> R` | `def f(x):` (无类型注解) | | `let x = e` / `var x = e` | `x = e` | | `if/while/for` | 相同 | | `match` | `match/case` (Python 3.10+) | | `type T { ... }` (结构体) | `@dataclass class T:` | | `type T = A \| B(P)` (和类型) | 类 + 别名 `T = A \| B` | | `trait T` | `class _Trait_T:` (信息性) | | `impl T` | 方法附加到 `T` | | `obj.meth(x)` | `obj.meth(x)` | | `Some(x)` / `Ok(x)` / `Err(e)` | 相同（运行时类） | | `e?` (try) | `_capa_try(e)` + `@_capa_wrap` 装饰器 | | `"hi ${name}"` | `f"hi {name}"` | ## 已知限制 (v1) ### 语言 - **`if`/`while`/`for` 是语句**。三元 `if cond then a else b` 是 `if` 唯一的表达式形式。 ### 词法分析器 / 语法分析器 - 字符串插值被识别但在词法分析器中未递归标记化；转译器稍后处理它。它适用于简单情况 (`${ident}`, `${a.b}`, `${a + b}`)，但 `${...}` 之间的内容被解释为直接的 Python 代码，而非纯 Capa。 - 不支持原始字符串 (`r"..."`)。 ### 分析器 - **能力规范**（三层）： *结构层 (v1)：* 能力（`Stdio`, `Fs`, `Net`, `Env`, `Proc`, `Clock`, `Random`, `Db`, `Unsafe`）只能出现在函数参数中。分析器拒绝： * 能力作为结构体字段 * 能力作为变体负载 * 能力作为函数返回类型 * 能力作为常量类型 * 能力绑定在局部 `let`/`var` 中 * 能力在泛型类型（`List`, `Option`...）或元组内部 *流层 (v2)：* * **调用中无别名**：同一能力不能作为同一调用的多个参数出现，也不能同时作为接收者和参数。`f(stdio, stdio)` 是错误。 * **必须使用**：声明为参数的能力必须在函数体中至少使用一次。惯例：在名称前加 `_` 以消除警告（Rust 和 Haskell 中的惯用法）。 *线性层 (v3)，`consume` 关键字：* * **可选移动语义**：将参数标记为 `consume cap: Cap` 表示函数消耗（获取所有权）传递的能力。调用后，调用者不能再使用该能力。 * **带分叉/合并的流分析**：在 `if/elif/else` 和 `match` 中，我们在每个分支之前快照消耗集，并在之后取保守并集，如果*任何*分支消耗了能力，则该能力从该点起被视为已消耗。这是 Rust 使用的规则，防止潜在消耗后的使用。 * **循环的预运行 + 重做**：对于 `while` 和 `for`，我们对主体执行一次静默扫描以发现哪些能力将被消耗；然后我们将这些能力预先标记为已消耗并执行真正的扫描。这可以捕获“在迭代 1 中消耗，在迭代 2 中使用”这种我们以前在循环中遗漏的线性失败。 * 默认情况下，参数是*借用*：调用者可以继续使用该能力。典型模式：多次借用，最后进行一次消耗。 三层一起为常见用法提供完整的线性性：能力在结构上不能被复制，每次调用无别名，必须使用，并且消耗通过包括分支和循环的流分析进行严格验证。 - **局部泛型推断**。检查器在三种上下文中推断类型参数： * **带负载的变体构造器**：`Ok(42)` 产生 `Result`，`Some("hi")` 产生 `Option`。无法从负载推断的类型参数（如 `Result` 中的 `E`）保持为 `TyUnknown`。 * **泛型函数的函数调用**：给定 `fun first(xs: List) -> T`，调用 `first([1, 2, 3])` 推断 `T = Int` 并返回 `Int`。 * **泛型结构体字面量**：`Pair { first: 1, second: "x" }` 产生 `Pair`（如果 `Pair` 已声明）。 推断是局部的（每个调用都是独立问题，无 let-多态泛化）。它通过简单的带替换的统一实现，无约束集求解。对常见情况足够好；推断失败时返回 `TyUnknown`，与任何类型兼容。 - **闭包 (lambda) v2**。语法：`fun (params) -> Ret => body`，其中 `body` 是单个表达式*或*缩进块： ``` // 单表达式 let double = fun (x: Int) -> Int => x * 2 // 块体，显式返回 let log = fun (x: Int) -> Int => stdio.println("got ${x}") return x * 10 ``` 函数类型作为注解：`Fun(Int, Int) -> Int`。支持高阶函数： ``` fun apply(f: Fun(Int) -> Int, x: Int) -> Int return f(x) fun compose(f: Fun(Int) -> Int, g: Fun(Int) -> Int) -> Fun(Int) -> Int return fun (x: Int) -> Int => g(f(x)) ``` *闭包中的线性性*： * **捕获是借用**：闭包可以从外围作用域捕获能力并用于借用（不消耗的调用）。 * **捕获不能被消耗**：尝试消耗被捕获的能力会被拒绝，因为闭包可以被多次调用，但能力只能被消耗一次。这是 Rust 中 `Fn` 和 `FnOnce` 的区别，通过捕获分析解决。该规则也适用于块体 lambda。 * **闭包本身作为参数的能力可以被消耗**：每次调用接收自己的能力，不共享。 *当前限制*： * **块体 lambda 不能直接出现在 `(...)` 内。** Capa 依赖 NEWLINE/INDENT/DEDENT 来定界块，并且词法分析器在括号内抑制这些标记以实现隐式行续接。因此编写 `f(fun (x) => , 5)` 会被拒绝，并提供针对性的解析器错误，指向推荐的解决方法：先将 lambda 绑定到 `let`，然后传递绑定（`let body = fun (x) => ; f(body, 5)`），或使用单表达式体。这是有意限制，非 bug；同样的根本原因适用于括号内的缩进形式 `match`。 * 无 let-多态泛化。 - **标准库：`List` 的内置方法**。`length`, `push`, `contains`, `map`, `filter`, `fold`，全部由检查器验证。 多态类型：`map(Fun(T) -> U) -> List` (T 来自接收者)，`filter(Fun(T) -> Bool) -> List`，`fold(U, Fun(U,T) -> U) -> U`。 ``` let xs = [1, 2, 3, 4, 5] let evens = xs.filter(fun (x: Int) -> Bool => x % 2 == 0) let doubled = xs.map(fun (x: Int) -> Int => x * 2) let total = xs.fold(0, fun (acc: Int, x: Int) -> Int => acc + x) ``` - **多行方法链**。当一行以 `.` 开头时，词法分析器抑制 NEWLINE/INDENT，允许惯用链式调用： ``` let total = xs .filter(fun (x: Int) -> Bool => x > 0) .map(fun (x: Int) -> Int => x * x) .fold(0, fun (acc: Int, x: Int) -> Int => acc + x) ``` 链步骤之间的 `//` 注释是允许的。它也适用于多行字段访问。列表字面量被转译为 `CapaList(...)`，是 Python `list` 的子类。 - **标准库：`String` 的内置方法**。`length`, `trim`, `to_upper`, `to_lower`, `contains`, `starts_with`, `ends_with`, `split`, `replace`，全部由检查器验证。类型： * `length() -> Int`, `to_upper() -> String`, `trim() -> String` * `contains(s: String) -> Bool`, `starts_with(s: String) -> Bool` * `split(sep: String) -> List`, `replace(old: String, new: String) -> String` ``` let normalised = " Hello World ".trim().to_lower() let parts = "one,two,three".split(",") ``` 实现：转译器执行**类型感知分发**，它从分析器接收类型映射，对于 `String` 类型的接收者，将 Capa 方法（`length`, `to_upper` 等）映射到其 Python 等价物（`len`, `.upper()` 等）。对于用户定义类型和 `List`（其方法同名），它直接发出 Python 方法调用。 - **插值字符串作为真正的表达式**。`"${expr}"` 被解析为 `InterpolatedString(parts: list[str | Expr])`，每个 `${...}` 都是一个完整的 Capa 表达式。类型检查在插值内有效；插值中的方法调用正确分发：`"${s.length()}"` 发出 `f"{len(s)}"`。`$$` 是 `$` 的转义。 - **标准库：`Map` 和 `Set`**。具有内置方法并由检查器验证的数据结构。 *Map*：`length`, `get` (返回 `Option`)，`set`, `contains_key`, `keys` (返回 `List`)，`values` (返回 `List`)。 *Set*：`length`, `add`, `remove`, `contains`, `to_list`。 构造：内置函数 `new_map()` 和 `new_set()` 返回空实例。要固定类型参数，请注解 `let`： ``` let counts: Map = new_map() counts.set("ana", 30) match counts.get("ana") Some(n) -> stdio.println("age = ${n}") None -> stdio.println("not found") let unique: Set = new_set() unique.add("a") unique.add("b") unique.add("a") // 忽略，集合元素唯一 ``` 实现：Map 使用 Python `dict`，Set 使用 Python `set`。转译器执行类型感知分发：`m.get(k)` → 三元表达式 `Some(m[k]) if k in m else None_`。 - **类型化的能力 (`Stdio`, `Fs`, `Env`, `Clock`, `Random`, `Net`)**：检查器中所有方法都有精确类型，而不是旧的宽松 `TyUnknown` 后备。 | 能力 | 方法 | 返回值 | |----------|-------------------------------------------|---------------------------| | `Stdio` | `print`, `println`, `eprintln(s: String)` | `()` | | `Stdio` | `read_line()` | `Result` | | `Fs` | `read(p: String)` | `Result` | | `Fs` | `write(p: String, c: String)` | `Result<(), IoError>` | | `Fs` | `exists(p: String)` | `Bool` | | `Fs` | `restrict_to(prefix: String)` | `Fs` (衰减后) | | `Fs` | `allows(path: String)` | `Bool` | | `Env` | `get(name: String)` | `Option` | | `Env` | `args()` | `List` | | `Env` | `restrict_to_keys(keys: List)` | `Env` (衰减后) | | `Env` | `allows(name: String)` | `Bool` | | `Clock` | `now_secs()`, `now_monotonic()` | `Float` | | `Clock` | `sleep(seconds: Float)` | `()` | | `Clock` | `restrict_to_after(t: Float)` | `Clock` (衰减后) | | `Clock` | `allows()` | `Bool` | | `Random` | `int_range(low: Int, high: Int)` | `Int` | | `Random` | `float_unit()` | `Float` | | `Random` | `with_seed(seed: Int)` | `Random` (确定性) | | `Net` | `restrict_to(host: String)` | `Net` (衰减后) | | `Net` | `allows(host: String)` | `Bool` | | `Net` | `get(url: String)` | `Result` | 结果：`clock.sleep(1)` 现在是错误（期望 Float）。`fs.read(42)` 是错误（期望 String）。并且 `match fs.exists(p) Ok(_) -> ...` 是错误，因为 `exists` 返回 `Bool`，不是 `Result`。 - **一等能力衰减** (`Net.restrict_to`)。衰减的结果是一个新的、可绑定到 `let` 的能力（结构上“局部变量中无能力”的规则特意放宽，因为方法调用结果不能是别名）。限制是单调的：链式两个 `restrict_to` 调用会取它们允许的主机集合的交集，绝不扩宽。运行时检查在*任何*系统调用*之前*触发，因此被阻止的主机永远不会接触网络。参见 `examples/net_attenuation.capa`。 - **用户定义的能力** (`capability X { ... }`)。 库可以声明自己的能力，`SendEmail`, `QueryDB`, `PublishMessage`，实现它们的类型在规范中被视为能力（无别名，不存储在普通局部变量中，不通过泛型参数泄露）。结构规则在两个方面被放宽：实现用户定义能力的类型*可以*将内置能力作为结构体字段（封装），普通函数*可以*返回用户定义的能力（工厂模式）。内置能力仍然不能返回，因此权限链在每个环节都保持明确。参见 `examples/user_capabilities.capa`。 `JsonValue` 的提取辅助函数：`is_null() -> Bool`, `as_bool() -> Option`, `as_num() -> Option`, `as_string() -> Option`, `as_array() -> Option>`, `as_object() -> Option>`。如果变体不匹配，每个都返回 `None`，消除样板匹配。 `Option` 的方法：`is_some() -> Bool`, `is_none() -> Bool`, `unwrap_or(default: T) -> T`, `map(Fun(T) -> U) -> Option`, `and_then(Fun(T) -> Option) -> Option`, `ok_or(err: E) -> Result`。 `Result` 上的相同方法：`is_ok`, `is_err`, `unwrap_or`, `map(Fun(T) -> U) -> Result`, `and_then(Fun(T) -> Result) -> Result`, `map_err(Fun(E) -> F) -> Result`。 一起实现了惯用的功能性代码，无需链式匹配： ``` let n = parse_int(s).map(fun (x: Int) -> Int => x * 2).unwrap_or(0) // ok_or 将 Option 转换为 Result let r: Result = parse_int(s).ok_or("invalid input") // map_err 转换错误类型 let r2 = fs.read(p).map_err(fun (e: IoError) -> Int => 1) ``` - **`if`-表达式（三元）**：`if cond then e1 else e2` 作为内联表达式。在此形式中需要 `then` 关键字，没有 `then`，`if` 在适当的上下文中被解释为语句。 ``` let cat = if n > 0 then "+" else if n < 0 then "-" else "0" // 在单行闭包中有用 let abs_xs = xs.map(fun (x: Int) -> Int => if x < 0 then 0 - x else x) // 在单子管线中 let par = parse_int(s).and_then(fun (x: Int) -> Option => if x > 0 then Some(x * 2) else None ) ``` 条件必须是 `Bool`，分支必须具有兼容的类型。精确错误：`if 42 then "a" else "b"` → `condition must be Bool, got Int`。 - **集合辅助函数**： - `List`: `is_empty() -> Bool`, `first() -> Option`, `last() -> Option`, `get(i: Int) -> Option` (安全访问) - `String`: `is_empty() -> Bool` - `Map`: `is_empty() -> Bool` - `Set`: `is_empty() -> Bool` - **标准库中的 JSON**。内置 `JsonValue` 类型，有 6 个递归变体：`JNull`, `JBool(Bool)`, `JNum(Float)`, `JStr(String)`, `JArr(List)`, `JObj(Map)`。函数 `parse_json(s: String) -> Result` 和 `to_json(v: JsonValue) -> String`。 ``` match parse_json(input) Err(msg) -> stdio.eprintln("error: ${msg}") Ok(config) -> match config JObj(m) -> match m.get("name") Some(JStr(name)) -> stdio.println("name: ${name}") _ -> stdio.println("name missing") _ -> stdio.println("not an object") // 构建并序列化 let resp: Map = new_map() resp.set("status", JStr("ok")) resp.set("count", JNum(42.0)) let s = to_json(JObj(resp)) ``` 穷尽性自然生效，`match j: JsonValue` 要求覆盖所有 6 个变体或一个通配符 `_`。 - **内置转换函数**： - `parse_int(s: String) -> Option`，输入无效时返回 `None` - `parse_float(s: String) -> Option`，对浮点数同理 惯用的交互式程序： ``` fun ask(stdio: Stdio, prompt: String) -> Option stdio.print(prompt) return match stdio.read_line() Ok(line) -> Some(line.trim()) Err(_) -> None fun main(stdio: Stdio) match ask(stdio, "Age: ") Some(s) -> match parse_int(s) Some(n) -> stdio.println("You are ${n}.") None -> stdio.println("Invalid age.") None -> stdio.println("EOF.") ``` - **带类型参数替换的模式匹配**。`match m.get(k)` 其中 `m: Map` 推断 `Some(n)` 为 `n: Int`，而非 `n: T`。所有者类型参数被审查表达式的具体类型参数自动替换。 - **高级模式匹配**： *元组*：在 `let`, `var`, `for`, 和 `match` 中解构： ``` let (name, age) = person() match pair (1, s) -> stdio.println(s) (n, _) -> stdio.println("${n}") ``` 嵌套模式：`(Some(n), label)` 匹配第一个元素是 `Some(...)` 的元组。检查模式的元数与审查表达式的类型是否匹配。 *match 中的字符串字面量*：`"help" -> ...`, `"quit" -> ...` - 对于命令分派器很有用。 *或模式*：`A | B -> ...` 如果*任何*替代匹配则匹配。对于共享主体的分支很有用： ``` match cmd "h" | "help" | "?" -> stdio.println("...") "q" | "quit" | "exit" -> stdio.println("goodbye") _ -> stdio.println("unknown") match c Red | Yellow -> "warm" Blue | Green -> "cold" ``` 或模式中的每个替代都计入穷尽性检查。 *带绑定的或模式*：每个替代都可以绑定变量，只要所有替代绑定的名称集和类型兼容： ``` type Op = Add(Int) Sub(Int) Mul(Int) fun value(o: Op) -> Int return match o Add(n) | Sub(n) | Mul(n) -> n // n 在所有中都是 Int ``` 不一致会被捕获：`Add(n) | NoOp` → 错误，因为 `NoOp` 不绑定 `n`。`AsInt(x) | AsStr(x)` → 错误，因为 `x` 在一个中是 `Int`，另一个中是 `String`。 - **跨语句推断**：类型通过共享的 TyVar 由后续使用细化。`let xs = []` 产生 `List`。第一次 `xs.push(42)` 固定 `_t = Int`，后续使用按 `List` 检查： ``` let xs = [] xs.push(42) // OK，推断为 Int xs.push("oops") // 错误：期望 Int，得到 String let ys = xs // 共享相同的 TyVar ys.push("oops") // 也是错误：它已经是 List ``` 传递 `xs` 到期望 `List` 的函数也有效，无需中间注解。 - **`List[i]` 的索引**返回其他可索引类型（Map 等）仍返回 `TyUnknown`。 - **真正的方法分发**。`impl` 块中定义的方法注册在目标类型的 Symbol 上。调用 `obj.method(args)` 被检查： * 方法必须存在于接收者的类型上 * 元数必须匹配 * 参数类型必须兼容（带有来自类型的类型参数替换：`c.put(x)` 在 `Box` 上期望 `x: Int`） * 返回类型中的 `Self` 解析为接收者的类型 * 附加推断适用于方法的类型参数 内置能力（`Stdio`, `Fs`, `Env`, `Net`, `Clock`, `Random`, `Unsafe`）在 Capa 源代码中没有 `impl` 块。它们的方法表面在 `capa/builtins.py` 中声明为一个封闭的表，分析器在分发期间查询该表。内置能力上的未知方法会被拒绝，并提供 "did you mean" 提示，而不是静默类型化为 `TyUnknown`；运行时根据 `capa/runtime/_capabilities.py` 中的 Python 实现解析注册的名称。 - **和类型和 `Bool` 的匹配穷尽性**： * **和类型**：每个变体必须被某个无守卫的分支覆盖。通配符 (`_`) 或无守卫的简单绑定 (`other`) 作为默认捕获。有守卫的分支不计入覆盖，因为守卫可能失败。 * **Bool**：需要覆盖 `true` 和 `false`（或 `_`）。消息如 `non-exhaustive match on Bool: missing false`。 * 对于具有高基数的非和类型（Int、具有异构字段的结构体），检查器尚未要求穷尽性，对 Int (2^64 值) 不可行，对结构体无关。 ### 转译器 - 输出是可读的 Python，但不是惯用的，它紧密映射 Capa 结构。 - `?` 运算符使用内部异常进行传播。它工作且正确，但不如展开的命令式版本高效。 ## 系统本身捕获的真实 bug 在开发过程中，**转译器 + 运行时捕获了设计和规范示例中的 bug**，这些是检查器未能捕获的： 1. `match` 作为语句，带有表达式分支时，会静默丢弃值，`tasks.capa` 产生了 `None` 而非字符串。通过运行程序检测到。 2. 内置变体 (`Ok`, `Err`, `Some`) 在分析器中未标记为有负载，`Ok(n)` 给出检查错误。已修复。 3. 内置泛型类型没有 `type_params`，`Result` 出现时无参数，与 `Result` 不兼容。已修复。 4. 使用 `?` 的函数需要一个捕获内部异常的装饰器；没有它，`Err` 会传播到程序顶部。我们添加了一个 AST 检测器来自动应用装饰器。这正是在实现线性性之前构建转译器的原因——运行真实代码是对设计最严苛的测试。 - **完全 trait 验证**。当您声明 `impl Trait for Type` 时，检查器验证： * **trait 中声明的每个方法的存在** * **签名兼容性**：每个实现的方法必须具有相同的元数、参数类型和返回类型。trait 签名中的 `Self` 解析为具体的 impl 类型。 * **额外的方法**（辅助函数）是允许的。 ## 下一步 Capa 是一种能力类型的语言：每个函数声明它持有的权限，分析器静态执行，并且衰减在设计上是单调的。除了其他能力语言（Pony, Koka, WebAssembly 组件模型）提供的功能外，编译器还可以直接从能力签名发出标准的供应链工件，无需外部扫描仪近似相同的信息。下一个里程碑继续在两个方面构建： **第一层，技术工件（进行中）：** 1. **SBOM diff 工具**（完成，[`examples/sbom_diff.capa`](examples/sbom_diff.capa)）。 比较两个 CycloneDX SBOM，并报告每个函数的能力拓宽、缩窄、添加、移除。 2. **SPDX 2.3 发射**（完成，`capa --spdx file.capa`）。Capa 现在除了 CycloneDX 1.5 还发射 SPDX 2.3；每个函数的能力元数据通过 SPDX `annotations[]` 传输。与 Linux Foundation 对齐，兼容 OpenChain。 3. **VEX 集成**（完成，`capa --vex file.capa`）。 通过函数上的 `@vex(cve, status, justification, detail)` 属性，实现每个函数的可利用性声明。没有其他语言在函数粒度发射 VEX；这是真正新颖的部分。嵌入在 `--cyclonedx` 中，并可通过 `--vex` 单独使用。 4. **SLSA Build L1 来源**（完成，`capa --provenance file.capa`）。in-toto Statement v1，带有 SLSA Provenance v1.0 谓词，主题 = 源代码的 SHA-256。用行业标准格式解决了 "这个 SBOM 从哪里来？" 的问题。**第一层完成。** **第二层，法规映射：** 5. **合并的 `docs/regulatory.md`**（完成，[`docs/regulatory.md`](docs/regulatory.md)）。多司法管辖区比较表，涵盖 CRA、NIS2、DORA（仅网络安全条款）、NIST SSDF 和 OWASP SCVS。扩展了 [`docs/cra.md`](docs/cra.md) 中现有的 CRA 逐条映射。**第二层完成。** **也许，未承诺：** 6. **在 Agda 中形式化 `λ_cap` 的可靠性定理。** 微积分草图和证明大纲位于 [`docs/semantics.md`](docs/semantics.md)；阶段 0 骨架（语法 + 定理陈述作为公理）位于 [`proofs/`](proofs/)。填充阶段 1-4（进展性、保持性、能力可靠性、清单完整性）是工作坊论文大小的延续。 7. **原生后端（LLVM 或 Cranelift）。** 长期目标，不在 v1 预算内。