node

package
v0.1.11 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: 13 Imported by: 0

Documentation

Overview

Package node reads the node directories of tamnd/algorithm (spec 04.3 and 04.4).

Index

Constants

This section is empty.

Variables

View Source
var BuildFiles = []string{
	"go.mod", "go.sum", "go.work", "Cargo.toml", "Cargo.lock", "package.json", "package-lock.json", "tsconfig.json",
	"pyproject.toml", "setup.py", "setup.cfg", "conftest.py", "pom.xml", "build.gradle", "build.gradle.kts",
	"settings.gradle", "settings.gradle.kts", "CMakeLists.txt", "Makefile", "Directory.Build.props",
}

BuildFiles are the names of the files that the generator writes (spec 08.5). Rule I15 refuses them in the content repo.

View Source
var EdgeKeys = []string{
	"solves", "implements", "techniques", "uses", "variant_of", "generalizes",
	"model", "complexity_in", "prereqs", "see_also", "exercises",
}

EdgeKeys are the front matter keys whose values name other nodes by slug (spec 04.6).

View Source
var KeyOrder = []string{
	"tag", "kind", "slug", "name", "aliases", "area", "areas", "level", "summary",
	"solves", "implements", "techniques", "uses", "variant_of", "generalizes",
	"model", "complexity", "complexity_in", "properties", "constraints", "history",
	"prereqs", "see_also", "same_as", "lean", "sources", "exercises", "people",
}

KeyOrder is the order of the front matter keys (spec 04.4). Keys that are not in the list go after it, in the order of the file.

View Source
var Kinds = []string{
	"area", "concept", "definition", "model", "problem", "abstract-type",
	"algorithm", "data-structure", "technique", "theorem", "exercise", "person",
}

Kinds are the 12 node kinds of spec 04.1.

View Source
var Levels = []string{"intro", "core", "advanced", "research"}

Levels are the editorial levels of spec 05.5.

Functions

func FormatNode added in v0.1.1

func FormatNode(b []byte) ([]byte, error)

FormatNode returns node.md in canonical form: LF line ends, no trailing spaces, the front matter keys in the order of KeyOrder, at most one blank line in a row outside code blocks, and one newline at the end. It returns an error when the new front matter does not parse to the same value as the old one, so it never changes what a node says.

func FormatText added in v0.1.1

func FormatText(b []byte) []byte

FormatText returns a text file with LF line ends, no trailing spaces and one newline at the end. algo fmt uses it for YAML, registers and proofs.

func IsBuildFile added in v0.1.3

func IsBuildFile(name string) bool

IsBuildFile tells if a file name is a build file of a language, such as go.mod or a .csproj file.

func IsKind

func IsKind(k string) bool

IsKind tells if k is one of the 12 kinds.

func IsTestFile

func IsTestFile(name string) bool

IsTestFile tells if a file name is a native test, by the conventions of spec 08.3. Examples: test_binary_search.py, binary_search_test.go, binarySearch.test.js, BinarySearchTest.java, binary_search_tests.rs.

func ReadAliases added in v0.1.2

func ReadAliases(path string) (map[string]string, error)

readTags reads registers/tags.reg. Each line is "TAG slug". A line that starts with # is a comment. ReadAliases reads registers/aliases.reg. Each line is an old slug and the slug it moved to.

func RenameRefs added in v0.1.2

func RenameRefs(b []byte, old, new string) []byte

RenameRefs changes each reference to the slug old into new: the values of the edge keys in the front matter, and the links "](/old/" and "](/old#" in the text. It changes nothing else, so a word in a summary or a URL in a source stays as it is.

func SetSlugArea added in v0.1.2

func SetSlugArea(b []byte, slug, area string) []byte

SetSlugArea sets the slug line and, when area is not empty, the area line of the front matter.

func SplitFront

func SplitFront(b []byte) (front, body []byte, bodyLine int, err error)

SplitFront splits a Markdown file into its YAML front matter and its body. It returns the line number where the body starts.

Types

type Area

type Area struct {
	ID       string `yaml:"id" json:"id"`
	Name     string `yaml:"name" json:"name"`
	Summary  string `yaml:"summary,omitempty" json:"summary,omitempty"`
	Children []Area `yaml:"children,omitempty" json:"children,omitempty"`
	Parent   string `yaml:"-" json:"parent,omitempty"`
}

Area is one entry of topics/areas.yaml (spec 05.2).

func (Area) Path

func (a Area) Path() string

Path is "top/sub" for a sub-area and "top" for a top area.

type Complexity

type Complexity struct {
	Vars  map[string]string            `yaml:"vars,omitempty" json:"vars,omitempty"`
	Time  map[string]string            `yaml:"time,omitempty" json:"time,omitempty"`
	Space map[string]string            `yaml:"space,omitempty" json:"space,omitempty"`
	Other map[string]map[string]string `yaml:",inline" json:"other,omitempty"`
}

Complexity holds the claims of a node (spec 04.4 and 06.6).

type Corpus

type Corpus struct {
	Root     string
	Nodes    []*Node
	BySlug   map[string]*Node
	ByTag    map[string]*Node
	Areas    []Area
	AreaByID map[string]*Area // keyed by Area.Path()
	Langs    []Lang
	LangByID map[string]*Lang
	Reserved map[string]bool
	Tags     []Tag
	// OldSlugs maps each old slug of registers/aliases.reg to the slug it moved to.
	OldSlugs map[string]string
	// Errors are the node directories that could not be read. Package check reports them as T01.
	Errors []error
}

Corpus is the content tree.

func Load

func Load(root string) (*Corpus, error)

Load reads the whole content tree at root.

func (*Corpus) InArea

func (c *Corpus) InArea(path string) []*Node

InArea returns the nodes whose primary area is path or is under path.

func (*Corpus) Kind

func (c *Corpus) Kind(kind string) []*Node

Kind returns the nodes of one kind.

func (*Corpus) Leads

func (c *Corpus) Leads(slug string) []*Node

Leads returns the nodes that list slug in prereqs or uses.

func (*Corpus) Solvers

func (c *Corpus) Solvers(problem string) []*Node

Solvers returns the nodes with a `solves` edge to the problem.

type File

type File struct {
	Name    string `json:"name"`
	Path    string `json:"path"`
	Content string `json:"-"`
	Test    bool   `json:"test"`
}

File is one file of an implementation.

type Front

type Front struct {
	Tag         string            `yaml:"tag" json:"tag"`
	Kind        string            `yaml:"kind" json:"kind"`
	Slug        string            `yaml:"slug" json:"slug"`
	Name        string            `yaml:"name" json:"name"`
	Aliases     []string          `yaml:"aliases,omitempty" json:"aliases,omitempty"`
	Area        string            `yaml:"area" json:"area"`
	Areas       []string          `yaml:"areas,omitempty" json:"areas,omitempty"`
	Level       string            `yaml:"level" json:"level"`
	Summary     string            `yaml:"summary" json:"summary"`
	Solves      []Solve           `yaml:"solves,omitempty" json:"solves,omitempty"`
	Implements  []string          `yaml:"implements,omitempty" json:"implements,omitempty"`
	Techniques  []string          `yaml:"techniques,omitempty" json:"techniques,omitempty"`
	Uses        []string          `yaml:"uses,omitempty" json:"uses,omitempty"`
	VariantOf   string            `yaml:"variant_of,omitempty" json:"variant_of,omitempty"`
	Generalizes []string          `yaml:"generalizes,omitempty" json:"generalizes,omitempty"`
	Model       string            `yaml:"model,omitempty" json:"model,omitempty"`
	Complexity  *Complexity       `yaml:"complexity,omitempty" json:"complexity,omitempty"`
	Properties  map[string]any    `yaml:"properties,omitempty" json:"properties,omitempty"`
	Constraints map[string]any    `yaml:"constraints,omitempty" json:"constraints,omitempty"`
	History     *History          `yaml:"history,omitempty" json:"history,omitempty"`
	Prereqs     []string          `yaml:"prereqs,omitempty" json:"prereqs,omitempty"`
	SameAs      map[string]any    `yaml:"same_as,omitempty" json:"same_as,omitempty"`
	Lean        map[string]string `yaml:"lean,omitempty" json:"lean,omitempty"`
	Sources     []Source          `yaml:"sources,omitempty" json:"sources,omitempty"`
	Exercises   []string          `yaml:"exercises,omitempty" json:"exercises,omitempty"`
	People      []string          `yaml:"people,omitempty" json:"people,omitempty"`
	SeeAlso     []string          `yaml:"see_also,omitempty" json:"see_also,omitempty"`
}

Front is the front matter of node.md. The schema is schema/node.v1.json in tamnd/algorithm.

type History

type History struct {
	Year   int      `yaml:"year,omitempty" json:"year,omitempty"`
	People []string `yaml:"people,omitempty" json:"people,omitempty"`
	Note   string   `yaml:"note,omitempty" json:"note,omitempty"`
}

History says where a node comes from.

type Impl

type Impl struct {
	Lang  string `json:"lang"`
	Files []File `json:"files"`
}

Impl is the implementation of a node in one language (spec 08.1).

func (Impl) HasTests

func (im Impl) HasTests() bool

HasTests tells if the implementation has native tests.

func (Impl) Main

func (im Impl) Main() *File

Main is the first file that is not a test.

type Lang

type Lang struct {
	ID        string   `yaml:"id" json:"id"`
	Name      string   `yaml:"name" json:"name"`
	Tier      int      `yaml:"tier" json:"tier"`
	Ext       []string `yaml:"ext" json:"ext"`
	FileCase  string   `yaml:"file_case" json:"file_case,omitempty"`
	Test      LangTool `yaml:"test" json:"test"`
	Format    LangTool `yaml:"format" json:"format"`
	Lint      LangTool `yaml:"lint" json:"lint"`
	Toolchain string   `yaml:"toolchain" json:"toolchain,omitempty"` // the pinned version, for the language page
	Run       string   `yaml:"run" json:"run,omitempty"`             // how a reader runs the tests without algo
	Comment   string   `yaml:"comment" json:"comment,omitempty"`
	Highlight string   `yaml:"highlight" json:"highlight"` // the Chroma lexer
	Int       string   `yaml:"int" json:"int,omitempty"`
	List      string   `yaml:"list" json:"list,omitempty"`
	Since     string   `yaml:"since" json:"since,omitempty"`
}

Lang is one entry of registers/languages.yaml (spec 08.2).

type LangTool

type LangTool struct {
	Tool      string   `yaml:"tool,omitempty" json:"tool,omitempty"`
	Framework string   `yaml:"framework,omitempty" json:"framework,omitempty"`
	File      string   `yaml:"file,omitempty" json:"file,omitempty"`
	Args      []string `yaml:"args,omitempty" json:"args,omitempty"`
}

LangTool is a tool of a language: the test framework, the formatter or the linter.

type Node

type Node struct {
	Front
	Body      string   `json:"-"`
	BodyLine  int      `json:"-"` // the line of node.md where the body starts
	Dir       string   `json:"-"`
	Rel       string   `json:"path"` // the directory, relative to the root
	RawFront  []byte   `json:"-"`
	Forbidden []string `json:"-"` // front matter keys that rule T05 rejects
	Impls     []Impl   `json:"impls,omitempty"`
	Proofs    []Proof  `json:"proofs,omitempty"`
	Scene     string   `json:"scene,omitempty"` // path of viz/scene.ts, relative to the root
	Presets   []Preset `json:"presets,omitempty"`
}

Node is one node directory.

func Read

func Read(root, dir string) (*Node, error)

Read reads one node directory. It does not check the node; package check does that.

func (*Node) Lang

func (n *Node) Lang(id string) *Impl

Lang returns the implementation in a language, or nil.

type Preset

type Preset struct {
	Name  string         `yaml:"name" json:"name"`
	Input map[string]any `yaml:"input" json:"input"`
	Note  string         `yaml:"note,omitempty" json:"note,omitempty"`
}

Preset is a named input of a scene (spec 10.4).

type Proof

type Proof struct {
	ID    string     `json:"id"`
	Path  string     `json:"path"`
	Front ProofFront `json:"front"`
	Body  string     `json:"-"`
}

Proof is one file of proofs/.

type ProofFront

type ProofFront struct {
	Title  string   `yaml:"title" json:"title"`
	Proves []string `yaml:"proves" json:"proves"`
	Status string   `yaml:"status" json:"status"` // full or sketch
	Lean   string   `yaml:"lean,omitempty" json:"lean,omitempty"`
}

ProofFront is the front matter of a proof file (spec 06.5).

type Solve

type Solve struct {
	Problem  string         `yaml:"problem" json:"problem"`
	Requires map[string]any `yaml:"requires,omitempty" json:"requires,omitempty"`
	Time     string         `yaml:"time,omitempty" json:"time,omitempty"`
	Note     string         `yaml:"note,omitempty" json:"note,omitempty"`
}

Solve is one `solves` edge. The short form is a problem slug. The long form has conditions (spec 04.4).

func (*Solve) UnmarshalYAML

func (s *Solve) UnmarshalYAML(n *yaml.Node) error

UnmarshalYAML accepts a slug or a mapping.

type Source

type Source struct {
	Book    string `yaml:"book,omitempty" json:"book,omitempty"`
	URL     string `yaml:"url,omitempty" json:"url,omitempty"`
	Paper   string `yaml:"paper,omitempty" json:"paper,omitempty"`
	Title   string `yaml:"title,omitempty" json:"title,omitempty"`
	Locator string `yaml:"locator,omitempty" json:"locator,omitempty"`
	Note    string `yaml:"note,omitempty" json:"note,omitempty"`
}

Source is one entry of `sources`.

type Tag

type Tag struct {
	Tag  string
	Slug string
	Line int
}

Tag is one line of registers/tags.reg.

Jump to

Keyboard shortcuts

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