path: root/internal/sexp/sexp.go

// 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])}
}