krino: foundation — sexp reader, config language, init/new/check

3 files changed, 473 insertions, 0 deletions

diff --git a/internal/sexp/fuzz_test.go b/internal/sexp/fuzz_test.go
new file mode 100644
index 0000000..01d436b
--- /dev/null
+++ b/internal/sexp/fuzz_test.go
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package sexp
+
+import "testing"
+
+// FuzzParse checks that Parse never panics and that every node it returns
+// spans valid bytes, with lists pointing at their own parentheses.
+func FuzzParse(f *testing.F) {
+	for _, s := range []string{`(a "b" (c))`, `"\"`, `(((`, `)`, "; x\n(y)", `("ł" x)`, "\xff", `"\\"`} {
+		f.Add([]byte(s))
+	}
+	f.Fuzz(func(t *testing.T, src []byte) {
+		nodes, err := Parse("f", src)
+		if err != nil {
+			return
+		}
+		walk(nodes, func(n *Node) {
+			if n.Pos.Offset < 0 || n.End.Offset > len(src) || n.Pos.Offset >= n.End.Offset {
+				t.Fatalf("bad span %d..%d in %q", n.Pos.Offset, n.End.Offset, src)
+			}
+			if n.Kind == List && (src[n.Pos.Offset] != '(' || src[n.End.Offset-1] != ')') {
+				t.Fatalf("list %d..%d does not span its parens in %q", n.Pos.Offset, n.End.Offset, src)
+			}
+		})
+	})
+}
diff --git a/internal/sexp/sexp.go b/internal/sexp/sexp.go
new file mode 100644
index 0000000..6e14a1f
--- /dev/null
+++ b/internal/sexp/sexp.go
@@ -0,0 +1,263 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// Package sexp reads the s-expression syntax of krino's config files: lists,
+// symbols, strings and ; comments. Nodes record positions and byte offsets,
+// so callers can report errors precisely and splice edits into the text.
+package sexp
+
+import (
+	"fmt"
+	"strings"
+	"unicode"
+	"unicode/utf8"
+)
+
+// Kind is the kind of a Node.
+type Kind int
+
+const (
+	List Kind = iota
+	Symbol
+	String
+)
+
+func (k Kind) String() string {
+	switch k {
+	case List:
+		return "list"
+	case Symbol:
+		return "symbol"
+	case String:
+		return "string"
+	}
+	return fmt.Sprintf("Kind(%d)", int(k))
+}
+
+// Pos is a position in a source file. Line and Col count from 1, and Col
+// counts characters; Offset counts bytes from 0.
+type Pos struct {
+	Offset, Line, Col int
+}
+
+// Node is a list, a symbol or a string.
+type Node struct {
+	Kind     Kind
+	Pos      Pos     // the "(" of a list, the first character of an atom
+	End      Pos     // just past the node's last byte
+	Text     string  // a symbol's name or a string's decoded value
+	Children []*Node // a list's elements
+}
+
+// Head is the name of the symbol a list starts with, or "".
+func (n *Node) Head() string {
+	if n.Kind == List && len(n.Children) > 0 && n.Children[0].Kind == Symbol {
+		return n.Children[0].Text
+	}
+	return ""
+}
+
+// Args are a list's elements after the first.
+func (n *Node) Args() []*Node {
+	if n.Kind != List || len(n.Children) == 0 {
+		return nil
+	}
+	return n.Children[1:]
+}
+
+// String renders n briefly for messages: atoms in full, a list by at most its
+// first two atoms, as in (rule "acme" ...).
+func (n *Node) String() string {
+	switch n.Kind {
+	case Symbol:
+		return n.Text
+	case String:
+		return Quote(n.Text)
+	}
+	var b strings.Builder
+	b.WriteByte('(')
+	shown := 0
+	for _, c := range n.Children {
+		if c.Kind == List || shown == 2 {
+			break
+		}
+		if shown > 0 {
+			b.WriteByte(' ')
+		}
+		b.WriteString(c.String())
+		shown++
+	}
+	if shown < len(n.Children) {
+		if shown > 0 {
+			b.WriteByte(' ')
+		}
+		b.WriteString("...")
+	}
+	b.WriteByte(')')
+	return b.String()
+}
+
+var quoter = strings.NewReplacer(`\`, `\\`, `"`, `\"`)
+
+// Quote encodes s as a config string, escaping only " and \.
+func Quote(s string) string {
+	return `"` + quoter.Replace(s) + `"`
+}
+
+// Error is a syntax error.
+type Error struct {
+	File string
+	Pos  Pos
+	Msg  string
+}
+
+func (e *Error) Error() string {
+	return fmt.Sprintf("%s:%d:%d: %s", e.File, e.Pos.Line, e.Pos.Col, e.Msg)
+}
+
+// Parse reads every top-level form in src. file names the source in errors,
+// and every error is an *Error.
+func Parse(file string, src []byte) ([]*Node, error) {
+	p := &parser{file: file, src: src, pos: Pos{Line: 1, Col: 1}}
+	if err := p.checkUTF8(); err != nil {
+		return nil, err
+	}
+	if len(src) >= 3 && src[0] == 0xEF && src[1] == 0xBB && src[2] == 0xBF {
+		p.pos.Offset = 3 // a leading BOM is invisible: skip it, offsets stay into src
+	}
+	var top, stack []*Node
+	add := func(n *Node) {
+		if len(stack) == 0 {
+			top = append(top, n)
+			return
+		}
+		parent := stack[len(stack)-1]
+		parent.Children = append(parent.Children, n)
+	}
+	for {
+		p.skipSpace()
+		if p.eof() {
+			break
+		}
+		start := p.pos
+		switch p.src[p.pos.Offset] {
+		case '(':
+			p.next()
+			n := &Node{Kind: List, Pos: start}
+			add(n)
+			stack = append(stack, n)
+		case ')':
+			if len(stack) == 0 {
+				return nil, p.errorf(start, `unexpected ")"`)
+			}
+			p.next()
+			stack[len(stack)-1].End = p.pos
+			stack = stack[:len(stack)-1]
+		case '"':
+			n, err := p.str()
+			if err != nil {
+				return nil, err
+			}
+			add(n)
+		default:
+			add(p.symbol())
+		}
+	}
+	if len(stack) > 0 {
+		return nil, p.errorf(stack[0].Pos, `"(" never closed: %s`, stack[0])
+	}
+	return top, nil
+}
+
+type parser struct {
+	file string
+	src  []byte
+	pos  Pos
+}
+
+func (p *parser) eof() bool { return p.pos.Offset >= len(p.src) }
+
+func (p *parser) peek() rune {
+	r, _ := utf8.DecodeRune(p.src[p.pos.Offset:])
+	return r
+}
+
+// next moves past one character and returns it.
+func (p *parser) next() rune {
+	r, size := utf8.DecodeRune(p.src[p.pos.Offset:])
+	p.pos.Offset += size
+	if r == '\n' {
+		p.pos.Line++
+		p.pos.Col = 1
+	} else {
+		p.pos.Col++
+	}
+	return r
+}
+
+func (p *parser) errorf(at Pos, format string, args ...any) *Error {
+	return &Error{File: p.file, Pos: at, Msg: fmt.Sprintf(format, args...)}
+}
+
+// checkUTF8 rejects invalid UTF-8 up front, so the parser can assume it.
+func (p *parser) checkUTF8() error {
+	for !p.eof() {
+		if r, size := utf8.DecodeRune(p.src[p.pos.Offset:]); r == utf8.RuneError && size == 1 {
+			return p.errorf(p.pos, "invalid UTF-8")
+		}
+		p.next()
+	}
+	p.pos = Pos{Line: 1, Col: 1}
+	return nil
+}
+
+// skipSpace moves past whitespace and comments.
+func (p *parser) skipSpace() {
+	for !p.eof() {
+		switch r := p.peek(); {
+		case r == ';':
+			for !p.eof() && p.peek() != '\n' {
+				p.next()
+			}
+		case unicode.IsSpace(r):
+			p.next()
+		default:
+			return
+		}
+	}
+}
+
+// str reads a string. A backslash escapes only " and \; any other backslash
+// is kept, so regular expressions need no doubling.
+func (p *parser) str() (*Node, error) {
+	start := p.pos
+	p.next() // the opening quote
+	var b strings.Builder
+	for {
+		if p.eof() {
+			return nil, p.errorf(start, "string never closed")
+		}
+		r := p.next()
+		switch r {
+		case '"':
+			return &Node{Kind: String, Pos: start, End: p.pos, Text: b.String()}, nil
+		case '\\':
+			if !p.eof() && (p.peek() == '"' || p.peek() == '\\') {
+				r = p.next()
+			}
+		}
+		b.WriteRune(r)
+	}
+}
+
+// symbol reads everything up to whitespace, a parenthesis, a quote or a
+// comment.
+func (p *parser) symbol() *Node {
+	start := p.pos
+	for !p.eof() {
+		if r := p.peek(); unicode.IsSpace(r) || r == '(' || r == ')' || r == '"' || r == ';' {
+			break
+		}
+		p.next()
+	}
+	return &Node{Kind: Symbol, Pos: start, End: p.pos, Text: string(p.src[start.Offset:p.pos.Offset])}
+}
diff --git a/internal/sexp/sexp_test.go b/internal/sexp/sexp_test.go
new file mode 100644
index 0000000..b0e0e4e
--- /dev/null
+++ b/internal/sexp/sexp_test.go
@@ -0,0 +1,183 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package sexp
+
+import "testing"
+
+func mustParse(t *testing.T, src string) []*Node {
+	t.Helper()
+	nodes, err := Parse("t.conf", []byte(src))
+	if err != nil {
+		t.Fatalf("Parse(%q): %v", src, err)
+	}
+	return nodes
+}
+
+// walk calls fn for every node, depth first.
+func walk(nodes []*Node, fn func(*Node)) {
+	for _, n := range nodes {
+		fn(n)
+		walk(n.Children, fn)
+	}
+}
+
+func TestAtoms(t *testing.T) {
+	tests := []struct {
+		src  string
+		kind Kind
+		text string
+	}{
+		{`pdf`, Symbol, "pdf"},
+		{`30d`, Symbol, "30d"},
+		{`>=`, Symbol, ">="},
+		{`"acme ltd"`, String, "acme ltd"},
+		{`"say \"hi\""`, String, `say "hi"`},
+		{`"\bacme\b"`, String, `\bacme\b`},
+		{`"a\\b"`, String, `a\b`},
+		{`"a\\\\b"`, String, `a\\b`},
+		{"\"two\nlines\"", String, "two\nlines"},
+		{`"spółka"`, String, "spółka"},
+		{`""`, String, ""},
+	}
+	for _, tt := range tests {
+		nodes := mustParse(t, tt.src)
+		if len(nodes) != 1 || nodes[0].Kind != tt.kind || nodes[0].Text != tt.text {
+			t.Errorf("Parse(%q) = %+v, want one %v %q", tt.src, nodes, tt.kind, tt.text)
+		}
+	}
+}
+
+func TestListStructure(t *testing.T) {
+	nodes := mustParse(t, `(when (type pdf) (content "x" "y"))`)
+	if len(nodes) != 1 {
+		t.Fatalf("got %d nodes", len(nodes))
+	}
+	w := nodes[0]
+	if w.Kind != List || w.Head() != "when" || len(w.Args()) != 2 {
+		t.Fatalf("when = %+v", w)
+	}
+	c := w.Args()[1]
+	if c.Head() != "content" || len(c.Args()) != 2 || c.Args()[1].Text != "y" {
+		t.Fatalf("content = %+v", c)
+	}
+	if got := mustParse(t, `("x" y)`)[0].Head(); got != "" {
+		t.Errorf("Head of a list starting with a string = %q, want empty", got)
+	}
+}
+
+func TestPositions(t *testing.T) {
+	src := "; comment\n(path \"~/d\")\n  (ignore \"*.part\")\n"
+	nodes := mustParse(t, src)
+	if len(nodes) != 2 {
+		t.Fatalf("got %d nodes", len(nodes))
+	}
+	checks := []struct {
+		name      string
+		got, want Pos
+	}{
+		{"path start", nodes[0].Pos, Pos{Offset: 10, Line: 2, Col: 1}},
+		{"path end", nodes[0].End, Pos{Offset: 22, Line: 2, Col: 13}},
+		{"string start", nodes[0].Args()[0].Pos, Pos{Offset: 16, Line: 2, Col: 7}},
+		{"string end", nodes[0].Args()[0].End, Pos{Offset: 21, Line: 2, Col: 12}},
+		{"ignore start", nodes[1].Pos, Pos{Offset: 25, Line: 3, Col: 3}},
+	}
+	for _, c := range checks {
+		if c.got != c.want {
+			t.Errorf("%s = %+v, want %+v", c.name, c.got, c.want)
+		}
+	}
+}
+
+func TestColumnsCountCharacters(t *testing.T) {
+	x := mustParse(t, `("ł" x)`)[0].Children[1]
+	if want := (Pos{Offset: 6, Line: 1, Col: 6}); x.Pos != want {
+		t.Fatalf("x at %+v, want %+v", x.Pos, want)
+	}
+}
+
+// TestBOMIsSkipped is item G: a leading UTF-8 byte-order mark must not
+// become a visible symbol, and byte offsets after it must stay offsets into
+// the original source.
+func TestBOMIsSkipped(t *testing.T) {
+	src := "\xEF\xBB\xBF(a)"
+	nodes := mustParse(t, src)
+	if len(nodes) != 1 {
+		t.Fatalf("got %d nodes, want 1", len(nodes))
+	}
+	n := nodes[0]
+	want := Pos{Offset: 3, Line: 1, Col: 1}
+	if n.Pos != want {
+		t.Errorf("Pos = %+v, want %+v", n.Pos, want)
+	}
+	if n.End.Offset != 6 {
+		t.Errorf("End.Offset = %d, want 6", n.End.Offset)
+	}
+}
+
+func TestListOffsetsPointAtParens(t *testing.T) {
+	src := "(rule \"a\"\n  (when (or (type pdf) (name \"x\")))\n  (stop)) (b)"
+	walk(mustParse(t, src), func(n *Node) {
+		if n.Kind == List && (src[n.Pos.Offset] != '(' || src[n.End.Offset-1] != ')') {
+			t.Errorf("list %s spans %d..%d", n, n.Pos.Offset, n.End.Offset)
+		}
+	})
+}
+
+func TestComments(t *testing.T) {
+	nodes := mustParse(t, "(a ; x ) y\n b) ; c")
+	if len(nodes) != 1 || len(nodes[0].Children) != 2 || nodes[0].Children[1].Text != "b" {
+		t.Fatalf("got %+v, want (a b)", nodes)
+	}
+	if n := mustParse(t, ""); n != nil {
+		t.Errorf("empty source gave %+v", n)
+	}
+	if n := mustParse(t, "; only a comment\n"); n != nil {
+		t.Errorf("comment-only source gave %+v", n)
+	}
+}
+
+func TestNodeString(t *testing.T) {
+	tests := map[string]string{
+		`(rule "acme" (when x) (stop))`: `(rule "acme" ...)`,
+		`(stop)`:                        `(stop)`,
+		`(type pdf docx odt)`:           `(type pdf ...)`,
+		`(a b)`:                         `(a b)`,
+		`()`:                            `()`,
+		`((a) b)`:                       `(...)`,
+		`sym`:                           `sym`,
+		`"a\"b"`:                        `"a\"b"`,
+	}
+	for src, want := range tests {
+		if got := mustParse(t, src)[0].String(); got != want {
+			t.Errorf("String of %s = %s, want %s", src, got, want)
+		}
+	}
+}
+
+func TestQuoteRoundTrip(t *testing.T) {
+	for _, v := range []string{"plain", `a"b`, `a\b`, `\bacme\b`, `x\"y`, "~/My Files"} {
+		n := mustParse(t, Quote(v))
+		if len(n) != 1 || n[0].Kind != String || n[0].Text != v {
+			t.Errorf("Quote(%q) = %s does not read back", v, Quote(v))
+		}
+	}
+}
+
+func TestErrors(t *testing.T) {
+	tests := []struct{ src, want string }{
+		{`(a (b)`, `t.conf:1:1: "(" never closed: (a ...)`},
+		{"(rule \"acme\"\n  (when (type pdf)", `t.conf:1:1: "(" never closed: (rule "acme" ...)`},
+		{`a)`, `t.conf:1:2: unexpected ")"`},
+		{"(a\n  \"abc", `t.conf:2:3: string never closed`},
+		{"ok \xff", `t.conf:1:4: invalid UTF-8`},
+	}
+	for _, tt := range tests {
+		_, err := Parse("t.conf", []byte(tt.src))
+		if err == nil || err.Error() != tt.want {
+			t.Errorf("Parse(%q) error = %v, want %s", tt.src, err, tt.want)
+		}
+		if _, ok := err.(*Error); err != nil && !ok {
+			t.Errorf("Parse(%q) error is %T, want *Error", tt.src, err)
+		}
+	}
+}