government / sexpr / token.go

@ 3608a1b3f346ed04e58a598e4f092b09f515c3fd | history


package sexpr

import (
	"fmt"
	"strconv"
	"strings"
	"unicode"
	"unicode/utf8"
)

type TokenKind int

const (
	TokEOF TokenKind = iota
	TokLParen
	TokRParen
	TokQuote
	TokDot
	TokAtom
	TokString
	TokComment
)

func (k TokenKind) String() string {
	switch k {
	case TokEOF:
		return "EOF"
	case TokLParen:
		return "("
	case TokRParen:
		return ")"
	case TokQuote:
		return "'"
	case TokDot:
		return "."
	case TokAtom:
		return "atom"
	case TokString:
		return "string"
	case TokComment:
		return "comment"
	}
	return fmt.Sprintf("TokenKind(%d)", int(k))
}

// Pos is a 1-based source position. Col counts runes, not bytes, so it
// matches what an editor shows.
type Pos struct {
	Line, Col int
}

func (p Pos) String() string { return fmt.Sprintf("%d:%d", p.Line, p.Col) }

// Token.Text depends on Kind:
//   - TokAtom: the raw atom text. Whether it is an integer, float or symbol
//     is the reader's decision, not the lexer's.
//   - TokString: the decoded value, escapes already applied.
//   - TokComment: everything after the first ';' up to the end of the line,
//     untrimmed, so ";=> 3" has Text "=> 3".
type Token struct {
	Kind TokenKind
	Text string
	Pos  Pos
}

type SyntaxError struct {
	Pos Pos
	Msg string
	// Incomplete means the input ended in the middle of a form, so more
	// input could make it valid. A REPL uses this to ask for another line.
	Incomplete bool
}

func (e *SyntaxError) Error() string { return e.Pos.String() + ": " + e.Msg }

// Lexer splits source text into tokens. Comments are tokens rather than
// skipped, because later steps keep them as notes in the certificates.
type Lexer struct {
	src string
	off int // byte offset of the next unread rune
	pos Pos // position of the next unread rune
	err error
}

func NewLexer(src string) *Lexer {
	l := &Lexer{src: src, pos: Pos{Line: 1, Col: 1}}
	if i := invalidUTF8(src); i >= 0 {
		l.err = &SyntaxError{Pos: positionAt(src, i), Msg: "invalid UTF-8"}
	}
	return l
}

// Tokenize returns every token in src, without the final TokEOF.
func Tokenize(src string) ([]Token, error) {
	l := NewLexer(src)
	var toks []Token
	for {
		t, err := l.Next()
		if err != nil {
			return nil, err
		}
		if t.Kind == TokEOF {
			return toks, nil
		}
		toks = append(toks, t)
	}
}

// Next returns the next token, or TokEOF at the end of input. After an
// error, every call returns the same error.
func (l *Lexer) Next() (Token, error) {
	if l.err != nil {
		return Token{}, l.err
	}
	t, err := l.next()
	if err != nil {
		l.err = err
	}
	return t, err
}

func (l *Lexer) next() (Token, error) {
	for l.off < len(l.src) && unicode.IsSpace(l.peek()) {
		l.advance()
	}
	start := l.pos
	if l.off >= len(l.src) {
		return Token{Kind: TokEOF, Pos: start}, nil
	}

	switch r := l.peek(); r {
	case '(':
		l.advance()
		return Token{Kind: TokLParen, Text: "(", Pos: start}, nil
	case ')':
		l.advance()
		return Token{Kind: TokRParen, Text: ")", Pos: start}, nil
	case '\'':
		l.advance()
		return Token{Kind: TokQuote, Text: "'", Pos: start}, nil
	case '"':
		return l.lexString(start)
	case ';':
		l.advance()
		begin := l.off
		for l.off < len(l.src) && l.peek() != '\n' {
			l.advance()
		}
		return Token{Kind: TokComment, Text: l.src[begin:l.off], Pos: start}, nil
	}

	begin := l.off
	for l.off < len(l.src) && !isDelimiter(l.peek()) {
		l.advance()
	}
	text := l.src[begin:l.off]
	// A lone dot is the dotted-pair marker; "3.14" and "a.b" are atoms.
	if text == "." {
		return Token{Kind: TokDot, Text: ".", Pos: start}, nil
	}
	return Token{Kind: TokAtom, Text: text, Pos: start}, nil
}

func isDelimiter(r rune) bool {
	switch r {
	case '(', ')', '\'', '"', ';':
		return true
	}
	return unicode.IsSpace(r)
}

// lexString reads a string literal starting at its opening quote. Strings
// may span lines. Errors point at the offending escape, or at the opening
// quote when the string never ends.
func (l *Lexer) lexString(start Pos) (Token, error) {
	l.advance()
	var b strings.Builder
	for {
		if l.off >= len(l.src) {
			return Token{}, &SyntaxError{Pos: start, Msg: "unterminated string", Incomplete: true}
		}
		escPos := l.pos
		r := l.advance()
		switch r {
		case '"':
			return Token{Kind: TokString, Text: b.String(), Pos: start}, nil
		case '\\':
			decoded, err := l.lexEscape(escPos)
			if err != nil {
				return Token{}, err
			}
			b.WriteRune(decoded)
		default:
			b.WriteRune(r)
		}
	}
}

func (l *Lexer) lexEscape(escPos Pos) (rune, error) {
	if l.off >= len(l.src) {
		return 0, &SyntaxError{Pos: escPos, Msg: "unterminated escape", Incomplete: true}
	}
	switch r := l.advance(); r {
	case '"', '\\':
		return r, nil
	case 'n':
		return '\n', nil
	case 't':
		return '\t', nil
	case 'u':
		return l.lexUnicodeEscape(escPos)
	default:
		return 0, &SyntaxError{Pos: escPos, Msg: fmt.Sprintf("unknown escape \\%c", r)}
	}
}

// lexUnicodeEscape reads the {hex} part of \u{hex}: 1 to 6 hex digits naming
// a Unicode scalar value (a code point that is not a surrogate).
func (l *Lexer) lexUnicodeEscape(escPos Pos) (rune, error) {
	bad := func(msg string) (rune, error) {
		return 0, &SyntaxError{Pos: escPos, Msg: msg, Incomplete: l.off >= len(l.src)}
	}
	if l.off >= len(l.src) || l.peek() != '{' {
		return bad(`\u must be followed by {hex}`)
	}
	l.advance()
	begin := l.off
	for l.off < len(l.src) && l.peek() != '}' && l.peek() != '"' {
		l.advance()
	}
	if l.off >= len(l.src) || l.peek() != '}' {
		return bad(`unterminated \u{...} escape`)
	}
	digits := l.src[begin:l.off]
	l.advance()
	if len(digits) == 0 || len(digits) > 6 {
		return bad(`\u{...} needs 1 to 6 hex digits`)
	}
	n, err := strconv.ParseUint(digits, 16, 32)
	if err != nil {
		return bad(fmt.Sprintf(`invalid hex digits in \u{%s}`, digits))
	}
	r := rune(n)
	if r > unicode.MaxRune || (r >= 0xD800 && r <= 0xDFFF) {
		return bad(fmt.Sprintf(`\u{%s} is not a Unicode scalar value`, digits))
	}
	return r, nil
}

func (l *Lexer) peek() rune {
	r, _ := utf8.DecodeRuneInString(l.src[l.off:])
	return r
}

func (l *Lexer) advance() rune {
	r, size := utf8.DecodeRuneInString(l.src[l.off:])
	l.off += size
	if r == '\n' {
		l.pos.Line++
		l.pos.Col = 1
	} else {
		l.pos.Col++
	}
	return r
}

// invalidUTF8 returns the byte offset of the first invalid UTF-8 sequence
// in s, or -1. Checking up front keeps the lexer free of RuneError cases.
func invalidUTF8(s string) int {
	for i, r := range s {
		if r == utf8.RuneError {
			if _, size := utf8.DecodeRuneInString(s[i:]); size == 1 {
				return i
			}
		}
	}
	return -1
}

func positionAt(s string, off int) Pos {
	p := Pos{Line: 1, Col: 1}
	for _, r := range s[:off] {
		if r == '\n' {
			p.Line++
			p.Col = 1
		} else {
			p.Col++
		}
	}
	return p
}