government / sexpr / reader.go

@ f06eb39c982d1ea91f18e6b8af90fc31f87ae5f0 | history


package sexpr

import (
	"fmt"
	"math"
	"regexp"
	"strconv"
)

// Reader parses source text into values by recursive descent over the
// grammar:
//
//	datum = atom | string | "'" datum | "(" list
//	list  = ")" | datum { datum } [ "." datum ] ")"
//
// The reader also records where each list starts, so errors can point at
// source positions, and keeps the comments it passes, so tests can read
// their annotations.
type Reader struct {
	lex       *Lexer
	peeked    *Token
	positions map[*Pair]Pos
	comments  []Token
}

func NewReader(src string) *Reader {
	return &Reader{lex: NewLexer(src), positions: map[*Pair]Pos{}}
}

// Position returns where a list read by r starts: its "(" or, for 'x, its
// quote mark. Atoms have no recorded position.
func (r *Reader) Position(v Value) (Pos, bool) {
	p, ok := v.(*Pair)
	if !ok {
		return Pos{}, false
	}
	pos, ok := r.positions[p]
	return pos, ok
}

// Comments returns the comments read so far, in source order.
func (r *Reader) Comments() []Token {
	return r.comments
}

// ReadAll returns every top-level form in src.
func ReadAll(src string) ([]Value, error) {
	r := NewReader(src)
	var forms []Value
	for {
		v, err := r.Read()
		if err != nil {
			return nil, err
		}
		if v == nil {
			return forms, nil
		}
		forms = append(forms, v)
	}
}

// Read returns the next top-level form, or nil at end of input.
func (r *Reader) Read() (Value, error) {
	v, _, err := r.ReadWithPos()
	return v, err
}

// ReadWithPos is Read that also returns where the form starts.
func (r *Reader) ReadWithPos() (Value, Pos, error) {
	t, err := r.peek()
	if err != nil {
		return nil, Pos{}, err
	}
	if t.Kind == TokEOF {
		return nil, Pos{}, nil
	}
	v, err := r.datum()
	return v, t.Pos, err
}

func (r *Reader) datum() (Value, error) {
	t, err := r.next()
	if err != nil {
		return nil, err
	}
	switch t.Kind {
	case TokAtom:
		return parseAtom(t)
	case TokString:
		return String(t.Text), nil
	case TokQuote:
		next, err := r.peek()
		if err != nil {
			return nil, err
		}
		if next.Kind == TokEOF || next.Kind == TokRParen {
			return nil, &SyntaxError{Pos: t.Pos, Msg: "' must be followed by a value", Incomplete: next.Kind == TokEOF}
		}
		v, err := r.datum()
		if err != nil {
			return nil, err
		}
		return r.record(List(Symbol("quote"), v), t.Pos), nil
	case TokLParen:
		v, err := r.list(t.Pos)
		if err != nil {
			return nil, err
		}
		return r.record(v, t.Pos), nil
	case TokRParen:
		return nil, &SyntaxError{Pos: t.Pos, Msg: "unexpected )"}
	case TokDot:
		return nil, &SyntaxError{Pos: t.Pos, Msg: "unexpected . outside a list"}
	}
	panic(fmt.Sprintf("sexpr: reader got token %v", t.Kind))
}

// list parses the rest of a list after its "(". Errors about a missing ")"
// point at the "(" that opened the list, which is where the mistake usually
// is.
func (r *Reader) list(open Pos) (Value, error) {
	var items []Value
	for {
		t, err := r.peek()
		if err != nil {
			return nil, err
		}
		switch t.Kind {
		case TokEOF:
			return nil, &SyntaxError{Pos: open, Msg: "unterminated list", Incomplete: true}
		case TokRParen:
			r.next()
			return List(items...), nil
		case TokDot:
			if len(items) == 0 {
				return nil, &SyntaxError{Pos: t.Pos, Msg: "a dotted pair needs a value before ."}
			}
			r.next()
			return r.dottedTail(t.Pos, open, items)
		}
		v, err := r.datum()
		if err != nil {
			return nil, err
		}
		items = append(items, v)
	}
}

// dottedTail parses the single value after "." and the ")" that must follow
// it: a pair has exactly one cdr.
func (r *Reader) dottedTail(dot, open Pos, items []Value) (Value, error) {
	t, err := r.peek()
	if err != nil {
		return nil, err
	}
	switch t.Kind {
	case TokRParen, TokEOF:
		return nil, &SyntaxError{Pos: dot, Msg: "expected a value after .", Incomplete: t.Kind == TokEOF}
	case TokDot:
		return nil, &SyntaxError{Pos: t.Pos, Msg: "only one . is allowed in a list"}
	}
	tail, err := r.datum()
	if err != nil {
		return nil, err
	}
	t, err = r.next()
	if err != nil {
		return nil, err
	}
	switch t.Kind {
	case TokRParen:
		return ListWithTail(tail, items...), nil
	case TokEOF:
		return nil, &SyntaxError{Pos: open, Msg: "unterminated list", Incomplete: true}
	case TokDot:
		return nil, &SyntaxError{Pos: t.Pos, Msg: "only one . is allowed in a list"}
	}
	return nil, &SyntaxError{Pos: t.Pos, Msg: "expected ) after the value following ."}
}

func (r *Reader) record(v Value, pos Pos) Value {
	if p, ok := v.(*Pair); ok {
		r.positions[p] = pos
	}
	return v
}

// next and peek give the reader one token of lookahead, which is all this
// grammar needs (it is LL(1)). Comments are set aside here.
func (r *Reader) next() (Token, error) {
	if r.peeked != nil {
		t := *r.peeked
		r.peeked = nil
		return t, nil
	}
	for {
		t, err := r.lex.Next()
		if err != nil || t.Kind != TokComment {
			return t, err
		}
		r.comments = append(r.comments, t)
	}
}

func (r *Reader) peek() (Token, error) {
	if r.peeked == nil {
		t, err := r.next()
		if err != nil {
			return Token{}, err
		}
		r.peeked = &t
	}
	return *r.peeked, nil
}

var (
	intPattern   = regexp.MustCompile(`^-?(0|[1-9][0-9]*)$`)
	floatPattern = regexp.MustCompile(`^-?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?$`)
	// Anything starting like a number must be a valid one, so "007", "1."
	// and ".5" are errors rather than surprising symbols.
	numberLike = regexp.MustCompile(`^[-+]?\.?[0-9]`)
)

func parseAtom(t Token) (Value, error) {
	s := t.Text
	switch {
	case s == "T":
		return T, nil
	case s == "F":
		return F, nil
	case intPattern.MatchString(s):
		n, err := strconv.ParseInt(s, 10, 64)
		if err != nil {
			return nil, &SyntaxError{Pos: t.Pos, Msg: fmt.Sprintf("integer %s does not fit in 64 bits", s)}
		}
		return Int(n), nil
	case floatPattern.MatchString(s):
		f, err := strconv.ParseFloat(s, 64)
		if err != nil || math.IsInf(f, 0) {
			return nil, &SyntaxError{Pos: t.Pos, Msg: fmt.Sprintf("float %s is out of range", s)}
		}
		return Float(f), nil
	case numberLike.MatchString(s):
		return nil, &SyntaxError{Pos: t.Pos, Msg: fmt.Sprintf("malformed number %s", s)}
	}
	return Symbol(s), nil
}