check

package
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 3, 2026 License: Apache-2.0 Imports: 11 Imported by: 0

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 "warn" only reports.

Index

Constants

This section is empty.

Variables

View Source
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).

View Source
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 and at most 60 characters",
	"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",
	"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 Markers

func Markers(content string) []string

Markers returns the line ids that the @line markers of a file name.

func ParseClaim

func ParseClaim(s string) error

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

func Vars

func Vars(s string) []string

Vars returns the variables of a claim, once each, in order.

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

func PseudoIDs(body string) (map[string][]string, []Finding)

PseudoIDs returns the line ids of the pseudocode blocks of a body, by block id. A block with no id is "main".

func Run

func Run(c *node.Corpus, opt Options) []Finding

Run runs the rules on the corpus and returns the findings, sorted by path and line.

func (Finding) String

func (f Finding) String() string

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
}

Options select what to check.

type Severity

type Severity string

Severity is how much a finding matters.

const (
	Block Severity = "block"
	Warn  Severity = "warn"
)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL