@ 21ba553f2ac9aed7435e6a7744c2a33c37c9dec8 | 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) {
switch t.Text {
case "T":
return T, nil
case "F":
return F, nil
}
v, ok, err := ParseNumber(t.Text)
if err != nil {
return nil, &SyntaxError{Pos: t.Pos, Msg: err.Error()}
}
if ok {
return v, nil
}
return Symbol(t.Text), nil
}
// ParseNumber reads s as a number literal. ok is false when s does not start
// like a number, so it is a symbol. The OID decoder uses this too, so a
// payload is a valid integer, float or symbol exactly when the same text is
// in source.
func ParseNumber(s string) (v Value, ok bool, err error) {
switch {
case intPattern.MatchString(s):
n, err := strconv.ParseInt(s, 10, 64)
if err != nil {
return nil, true, fmt.Errorf("integer %s does not fit in 64 bits", s)
}
return Int(n), true, nil
case floatPattern.MatchString(s):
f, err := strconv.ParseFloat(s, 64)
if err != nil || math.IsInf(f, 0) {
return nil, true, fmt.Errorf("float %s is out of range", s)
}
return Float(f), true, nil
case numberLike.MatchString(s):
return nil, true, fmt.Errorf("malformed number %s", s)
}
return nil, false, nil
}