Documentation
¶
Overview ¶
Package check runs the audit rules of spec 13.3 that `algo check` needs.
Each rule has an id, such as T01. A rule with the severity "block" stops a merge. A rule with the severity "level" keeps a part below the level that needs it. A rule with the severity "warn" only reports.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var Order = map[string][]string{
"algorithm": {"In plain words", "The problem", "The algorithm", "Example", "Correctness", "Complexity", "Properties", "Variants and improvements", "When to use it", "Pitfalls", "Implementations", "Formal proof", "History", "Exercises", "References"},
"data-structure": {"In plain words", "The abstract type", "Representation", "Operations", "Example", "Correctness", "Complexity", "Variants", "When to use it", "Pitfalls", "Implementations", "Formal proof", "History", "Exercises", "References"},
"problem": {"In plain words", "Definition", "Variants", "Examples", "Known algorithms", "Bounds", "Reductions", "Applications", "References"},
"abstract-type": {"In plain words", "Operations", "Laws", "Implementations", "Lower bounds", "References"},
"technique": {"In plain words", "When it applies", "The template", "Classic examples", "Variations", "Pitfalls", "Exercises", "References"},
"concept": {"In plain words", "The idea", "Examples", "Where it is used", "References"},
"definition": {"Definition", "Examples and non-examples", "Related definitions", "References"},
"model": {"The machine", "What it counts", "Relation to other models", "Known results in the model", "References"},
"theorem": {"Statement", "In plain words", "Proof", "Consequences", "Tightness", "History", "References"},
}
Order lists the headings of each kind in their order (spec 06.3).
var Rules = map[string]string{
"T01": "node.md front matter is valid for its kind",
"T02": "each tag is in registers/tags.reg, once, with its slug",
"T03": "each slug is unique, lowercase kebab-case, at most 60 characters, and not an old slug in aliases.reg",
"T04": "the path of the node matches its area",
"T05": "no status, level or badge is written in front matter",
"T06": "no provisional id is left on main",
"G01": "prereqs edges form a DAG",
"G02": "variant_of and generalizes edges have no cycle",
"G03": "each solves target is a problem node",
"G04": "each implements target is an abstract type",
"G05": "each edge target exists",
"G07": "no edge points to its own node; see_also has at most 8 targets",
"E01": "each complexity string parses",
"E04": "each variable of a claim is defined in vars, and the model exists",
"W01": "the section headings of the kind are in order",
"W03": "pseudocode line ids are unique, and each @line marker names an existing id",
"I10": "each implementation and test file starts with the SPDX header",
"I11": "each line id of the main pseudocode has a marker in each tier-1 implementation",
"I12": "each implementation language is in the register",
"I15": "no generated file under build/ is committed, and no implementation has a build file; algo gen writes them",
"S01": "contract.yaml is valid; each complexity variable of each solving algorithm is a size parameter or is defined",
"S02": "each case validates against the contract",
"S03": "a custom checker has checker cases, valid and invalid, with a note for each invalid output",
"S04": "edge.jsonl has at least one case for each class of edge_classes",
"S05": "each generator is a Python file under generators/ that uses only the rng it gets",
"S06": "the contract of each core problem is reviewed by a person, bound to its hash",
"S09": "a flaky case names its open issue",
"L01": "each Lean name in the front matter exists in decls.jsonl with the expected kind",
"L02": "the correctness theorem mentions the spec and the model",
"L03": "each declaration uses only propext, Classical.choice and Quot.sound",
"L04": "the fidelity review of the spec of a core node is current",
"L05": "each time claim of a node with lean.cost has a class lemma of the same class",
"L07": "the model is total and computable",
"L09": "the module path mirrors the node path",
"X01": "each link in a node to /<slug>/ names a node, an area or a site page",
"X06": "no node slug is a reserved word, a language id or an area id",
}
Rules lists the rules that this package runs, with their text.
Functions ¶
func ParseClaim ¶
ParseClaim checks one complexity string in the small grammar of spec 04.4.
A claim is a bound, Θ(e), O(e), Ω(e), o(e) or ω(e), or an exact expression e. Words such as "amortized", "expected" and "w.h.p." may follow. An expression uses numbers, variables, the functions log, lg, ln, sqrt, min, max, the operators + − - * · × / ^, brackets ( ) ⌊ ⌋ ⌈ ⌉ and |x|.
Types ¶
type Finding ¶
type Finding struct {
Rule string `json:"rule"`
Severity Severity `json:"severity"`
Path string `json:"path"`
Line int `json:"line,omitempty"`
Msg string `json:"msg"`
}
Finding is one result of a rule.
func PseudoIDs ¶
PseudoIDs returns the line ids of the pseudocode blocks of a body, by block id. A block with no id is "main".
type Options ¶
type Options struct {
// Only, when not empty, limits the run to these slugs.
Only map[string]bool
// Rule, when not empty, runs only this rule.
Rule string
// Main is true on the main branch, where provisional ids are an error (T06).
Main bool
// Decls are the declarations that algo lean build wrote. When it is nil, the rules L01 to L09 that need them do not run.
Decls formal.Decls
}
Options select what to check.