1 files changed, 263 insertions, 0 deletions
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])}
+}