@ 675167640370859e58d24a1f76126760c2e61968 | 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
// End is the position just after the token's last character.
End 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
}
t.End = l.pos
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
}
// IsDelimiter reports whether r ends an atom: whitespace, a paren, a
// quote, a string's opening quote or a comment's semicolon.
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
}