v23/syncbase/nosql/internal/query/query_parser/query_parser.go

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package query_parser

import (
	"fmt"
	"math/big"
	"regexp"
	"strconv"
	"strings"
	"text/scanner"
	"time"
	"unicode/utf8"

	"v.io/syncbase/v23/syncbase/nosql/query_db"
	"v.io/syncbase/v23/syncbase/nosql/syncql"
	"v.io/v23/vdl"
)

type TokenType int

const (
	TokCHAR TokenType = 1 + iota
	TokCOMMA
	TokEOF
	TokEQUAL
	TokFLOAT
	TokIDENT
	TokINT
	TokLEFTANGLEBRACKET
	TokLEFTBRACKET
	TokLEFTPAREN
	TokMINUS
	TokPERIOD
	TokRIGHTANGLEBRACKET
	TokRIGHTBRACKET
	TokRIGHTPAREN
	TokSTRING
)

type Token struct {
	Tok   TokenType
	Value string
	Off   int64
}

type Node struct {
	Off int64
}

type Statement interface {
	Offset() int64
	String() string
}

type Segment struct {
	Value string
	Keys  []*Operand // Used as key(s) or index(es) to dereference map/set/array/list.
	Node
}

type Field struct {
	Segments []Segment
	Node
}

type BinaryOperatorType int

const (
	And BinaryOperatorType = 1 + iota
	Equal
	GreaterThan
	GreaterThanOrEqual
	Is
	IsNot
	LessThan
	LessThanOrEqual
	Like
	NotEqual
	NotLike
	Or
)

type BinaryOperator struct {
	Type BinaryOperatorType
	Node
}

type OperandType int

const (
	TypBigInt OperandType = 1 + iota // Only as a result of Resolve/Coerce Operand
	TypBigRat                        // Only as a result of Resolve/Coerce Operand
	TypBool
	TypComplex
	TypExpr
	TypField
	TypFloat
	TypFunction
	TypInt
	TypNil
	TypStr
	TypTime
	TypObject // Only as the result of a ResolveOperand.
	TypUint   // Only as a result of a ResolveOperand
)

type Operand struct {
	Type      OperandType
	BigInt    *big.Int
	BigRat    *big.Rat
	Bool      bool
	Complex   complex128
	Column    *Field
	Float     float64
	Function  *Function
	Int       int64
	Str       string
	Time      time.Time
	Prefix    string // Computed by checker for Like expressions
	Regex     string // Computed by checker for Like expressions
	Uint      uint64
	CompRegex *regexp.Regexp
	Expr      *Expression
	Object    *vdl.Value
	Node
}

type Function struct {
	Name     string
	Args     []*Operand
	ArgTypes []OperandType // Filled in by checker.
	RetType  OperandType   // Filled in by checker.
	Computed bool          // Checker sets to true and sets RetValue if function takes no args
	RetValue *Operand
	Node
}

type Expression struct {
	Operand1 *Operand
	Operator *BinaryOperator
	Operand2 *Operand
	Node
}

type SelectorType int

const (
	TypSelField SelectorType = 1 + iota
	TypSelFunc
)

// Selector: entries in the select clause.
// Entries can be functions for fields.
// The AS name, if present, will ONLY be used in the
// returned column header.
type Selector struct {
	Type     SelectorType
	Field    *Field
	Function *Function
	As       *AsClause // If not nil, used in returned column header.
	Node
}

type AsClause struct {
	AltName Name
	Node
}

type Name struct {
	Value string
	Node
}

type SelectClause struct {
	Selectors []Selector
	Node
}

type FromClause struct {
	Table TableEntry
	Node
}

type TableEntry struct {
	Name    string
	DBTable query_db.Table // Checker gets table from db and sets this.
	Node
}

type WhereClause struct {
	Expr *Expression
	Node
}

type Int64Value struct {
	Value int64
	Node
}

type LimitClause struct {
	Limit *Int64Value
	Node
}

type ResultsOffsetClause struct {
	ResultsOffset *Int64Value
	Node
}

type SelectStatement struct {
	Select        *SelectClause
	From          *FromClause
	Where         *WhereClause
	Limit         *LimitClause
	ResultsOffset *ResultsOffsetClause
	Node
}

func scanToken(s *scanner.Scanner) *Token {
	// TODO(jkline): Replace golang text/scanner.
	var token Token
	tok := s.Scan()
	token.Value = s.TokenText()
	token.Off = int64(s.Position.Offset)

	switch tok {
	case '.':
		token.Tok = TokPERIOD
	case ',':
		token.Tok = TokCOMMA
	case '-':
		token.Tok = TokMINUS
	case '(':
		token.Tok = TokLEFTPAREN
	case ')':
		token.Tok = TokRIGHTPAREN
	case '=':
		token.Tok = TokEQUAL
	case '<':
		token.Tok = TokLEFTANGLEBRACKET
	case '>':
		token.Tok = TokRIGHTANGLEBRACKET
	case '[':
		token.Tok = TokLEFTBRACKET
	case ']':
		token.Tok = TokRIGHTBRACKET
	case scanner.EOF:
		token.Tok = TokEOF
	case scanner.Ident:
		token.Tok = TokIDENT
	case scanner.Int:
		token.Tok = TokINT
	case scanner.Float:
		token.Tok = TokFLOAT
	case scanner.Char:
		token.Tok = TokCHAR
		token.Value = token.Value[1 : len(token.Value)-1]
	case scanner.String:
		token.Tok = TokSTRING
		token.Value = token.Value[1 : len(token.Value)-1]
	}
	return &token
}

// Text/scanner reports errors to stderr that are not errors in the query language.
// For example, to get the value where the key is "\",
// One would write the string:
// "select v where k = \"\\\""
// This will result in the scanner spewing "literal not terminated" to stderr if we don't
// set the Error field in Scanner.  As such, Error is set to the following function which
// eats errors.  In the longer term, there is still a TODO to replace text/scanner with
// our own scanner.
func scannerError(s *scanner.Scanner, msg string) {
	// Do nothing.
}

// Parse a statement.  Return it or an error.
func Parse(db query_db.Database, src string) (*Statement, error) {
	r := strings.NewReader(src)
	var s scanner.Scanner
	s.Init(r)
	s.Error = scannerError

	token := scanToken(&s) // eat the select
	if token.Tok == TokEOF {
		return nil, syncql.NewErrNoStatementFound(db.GetContext(), token.Off)
	}
	if token.Tok != TokIDENT {
		return nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
	}
	switch strings.ToLower(token.Value) {
	case "select":
		var st Statement
		var err error
		st, token, err = selectStatement(db, &s, token)
		return &st, err
	default:
		return nil, syncql.NewErrUnknownIdentifier(db.GetContext(), token.Off, token.Value)
	}
}

// Parse the [currently] one and only supported statement: select.
func selectStatement(db query_db.Database, s *scanner.Scanner, token *Token) (Statement, *Token, error) {
	// TODO(jkline): keep a count of recursions and limit it to some arbitrary number.
	var st SelectStatement
	st.Off = token.Off

	// parse SelectClause
	var err error
	st.Select, token, err = parseSelectClause(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	st.From, token, err = parseFromClause(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	st.Where, token, err = parseWhereClause(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	st.Limit, st.ResultsOffset, token, err = parseLimitResultsOffsetClauses(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	// There can be nothing remaining for the current statement
	if token.Tok != TokEOF {
		return nil, nil, syncql.NewErrUnexpected(db.GetContext(), token.Off, token.Value)
	}

	return st, token, nil
}

// Parse the select clause (fields). Return *SelectClause, next token (or error).
func parseSelectClause(db query_db.Database, s *scanner.Scanner, token *Token) (*SelectClause, *Token, error) {
	// must be at least one selector or it is an error
	// field seclectors may be in dot notation
	// selectors are separated by commas
	var selectClause SelectClause
	selectClause.Off = token.Off
	token = scanToken(s) // eat the select
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	var err error
	// scan first selector
	if token, err = parseSelector(db, s, &selectClause, token); err != nil {
		return nil, nil, err
	}

	// More selectors?
	for token.Tok == TokCOMMA {
		token = scanToken(s)
		if token, err = parseSelector(db, s, &selectClause, token); err != nil {
			return nil, nil, err
		}
	}

	return &selectClause, token, nil
}

// Parse a selector. Return next token (or error).
func parseSelector(db query_db.Database, s *scanner.Scanner, selectClause *SelectClause, token *Token) (*Token, error) {
	if token.Tok != TokIDENT {
		return nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
	}

	var selector Selector
	selector.Off = token.Off
	selector.Type = TypSelField
	var field Field
	selector.Field = &field
	selector.Field.Off = token.Off
	selector.Field = &field

	var segment *Segment
	var err error
	if segment, token, err = parseSegment(db, s, token); err != nil {
		return nil, err
	}
	selector.Field.Segments = append(selector.Field.Segments, *segment)

	// It might be a function.
	if token.Tok == TokLEFTPAREN {
		// Segments with a key(s) specified cannot be function calls.
		if len(segment.Keys) != 0 {
			return nil, syncql.NewErrUnexpected(db.GetContext(), token.Off, token.Value)
		}
		// switch selector to a function
		selector.Type = TypSelFunc
		var err error
		if selector.Function, token, err = parseFunction(db, s, segment.Value, segment.Off, token); err != nil {
			return nil, err
		}
		selector.Field = nil

	} else {
		for token.Tok != TokEOF && token.Tok == TokPERIOD {
			token = scanToken(s)
			if token.Tok != TokIDENT {
				return nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
			}
			if segment, token, err = parseSegment(db, s, token); err != nil {
				return nil, err
			}
			selector.Field.Segments = append(selector.Field.Segments, *segment)
		}
	}

	// Check for AS
	if token.Tok == TokIDENT && strings.ToLower(token.Value) == "as" {
		var asClause AsClause
		asClause.Off = token.Off
		token = scanToken(s)
		if token.Tok != TokIDENT {
			return nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
		}
		asClause.AltName.Value = token.Value
		asClause.AltName.Off = token.Off
		selector.As = &asClause
		token = scanToken(s)
	}

	selectClause.Selectors = append(selectClause.Selectors, selector)
	return token, nil
}

// Parse a segment. Return the segment and the next token (or error).
// Check for a key (i.e., [<key>] following the segment).
func parseSegment(db query_db.Database, s *scanner.Scanner, token *Token) (*Segment, *Token, error) {
	var segment Segment
	segment.Value = token.Value
	segment.Off = token.Off
	token = scanToken(s)

	for token.Tok == TokLEFTBRACKET {
		// A key to the segment is specified.
		token = scanToken(s)
		var key *Operand
		var err error
		key, token, err = parseOperand(db, s, token)
		if err != nil {
			return nil, nil, err
		}
		segment.Keys = append(segment.Keys, key)
		if token.Tok != TokRIGHTBRACKET {
			return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, "]")
		}
		token = scanToken(s)
	}
	return &segment, token, nil
}

// Parse the from clause, Return FromClause and next Token or error.
func parseFromClause(db query_db.Database, s *scanner.Scanner, token *Token) (*FromClause, *Token, error) {
	if strings.ToLower(token.Value) != "from" {
		return nil, nil, syncql.NewErrExpectedFrom(db.GetContext(), token.Off, token.Value)
	}
	var fromClause FromClause
	fromClause.Off = token.Off
	token = scanToken(s) // eat from
	// must be a table specified
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	if token.Tok != TokIDENT {
		return nil, nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
	}
	fromClause.Table.Off = token.Off
	fromClause.Table.Name = token.Value
	token = scanToken(s)
	return &fromClause, token, nil
}

// Parse the where clause (if any).  Return WhereClause (could be nil) and and next Token or error.
func parseWhereClause(db query_db.Database, s *scanner.Scanner, token *Token) (*WhereClause, *Token, error) {
	// parse Optional where clause
	if token.Tok != TokEOF {
		if strings.ToLower(token.Value) != "where" {
			return nil, token, nil
		}
		var where WhereClause
		where.Off = token.Off
		token = scanToken(s)
		// parse expression
		var err error
		where.Expr, token, err = parseExpression(db, s, token)
		if err != nil {
			return nil, nil, err
		}
		return &where, token, nil
	} else {
		return nil, token, nil
	}
}

// Parse a parenthesized expression.  Return expression and next token (or error)
func parseParenthesizedExpression(db query_db.Database, s *scanner.Scanner, token *Token) (*Expression, *Token, error) {
	// Only called when token == TokLEFTPAREN
	token = scanToken(s) // eat '('
	var expr *Expression
	var err error
	expr, token, err = parseExpression(db, s, token)
	if err != nil {
		return nil, nil, err
	}
	// Expect right paren
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	if token.Tok != TokRIGHTPAREN {
		return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, ")")
	}
	token = scanToken(s) // eat ')'
	return expr, token, nil
}

// Parse an expression.  Return expression and next token (or error)
func parseExpression(db query_db.Database, s *scanner.Scanner, token *Token) (*Expression, *Token, error) {
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}

	var err error
	var expr *Expression

	if token.Tok == TokLEFTPAREN {
		expr, token, err = parseParenthesizedExpression(db, s, token)
	} else {
		// We expect a like/equal expression
		expr, token, err = parseLikeEqualExpression(db, s, token)
	}
	if err != nil {
		return nil, nil, err
	}

	for token.Tok != TokEOF && token.Tok != TokRIGHTPAREN {
		// There is more.  If not 'and', 'or' or ')', the where is over.
		if strings.ToLower(token.Value) != "and" && strings.ToLower(token.Value) != "or" {
			return expr, token, nil
		}
		var newExpression Expression
		var operand1 Operand
		operand1.Type = TypExpr
		operand1.Expr = expr
		operand1.Off = operand1.Expr.Off
		newExpression.Operand1 = &operand1
		newExpression.Off = operand1.Off

		newExpression.Operator, token, err = parseLogicalOperator(db, s, token)
		if err != nil {
			return nil, nil, err
		}

		expr = &newExpression
		// Need to set operand2.
		var operand2 Operand
		expr.Operand2 = &operand2
		if token.Tok == TokLEFTPAREN {
			expr.Operand2.Type = TypExpr
			expr.Operand2.Expr, token, err = parseParenthesizedExpression(db, s, token)
		} else {
			expr.Operand2.Type = TypExpr
			expr.Operand2.Expr, token, err = parseLikeEqualExpression(db, s, token)
		}
		if err != nil {
			return nil, nil, err
		}
		expr.Operand2.Off = expr.Operand2.Expr.Off
	}

	return expr, token, nil
}

// Parse a binary expression.  Return expression and next token (or error)
func parseLikeEqualExpression(db query_db.Database, s *scanner.Scanner, token *Token) (*Expression, *Token, error) {
	var expression Expression
	expression.Off = token.Off

	// operand 1
	var operand1 *Operand
	var err error
	operand1, token, err = parseOperand(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	// operator
	var operator *BinaryOperator
	operator, token, err = parseBinaryOperator(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	// operand 2
	var operand2 *Operand
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	operand2, token, err = parseOperand(db, s, token)
	if err != nil {
		return nil, nil, err
	}

	expression.Operand1 = operand1
	expression.Operator = operator
	expression.Operand2 = operand2

	return &expression, token, nil
}

func parseFunction(db query_db.Database, s *scanner.Scanner, funcName string, funcOffset int64, token *Token) (*Function, *Token, error) {
	var function Function
	function.Name = funcName
	function.Off = funcOffset
	token = scanToken(s) // eat left paren
	for token.Tok != TokRIGHTPAREN {
		if token.Tok == TokEOF {
			return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, ")")
		}
		var arg *Operand
		var err error
		arg, token, err = parseOperand(db, s, token)
		if err != nil {
			return nil, nil, err
		}
		function.Args = append(function.Args, arg)
		// A comma or right paren is expected, but a right paren cannot come after a comma.
		if token.Tok == TokCOMMA {
			token = scanToken(s)
			if token.Tok == TokRIGHTPAREN {
				// right paren cannot come after a comma
				return nil, nil, syncql.NewErrExpectedOperand(db.GetContext(), token.Off, token.Value)
			}
		} else if token.Tok != TokRIGHTPAREN {
			return nil, nil, syncql.NewErrUnexpected(db.GetContext(), token.Off, token.Value)
		}
	}
	token = scanToken(s) // eat right paren
	return &function, token, nil
}

// Parse an operand (field or literal) and return it and the next Token (or error)
func parseOperand(db query_db.Database, s *scanner.Scanner, token *Token) (*Operand, *Token, error) {
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	var operand Operand
	operand.Off = token.Off
	switch token.Tok {
	case TokIDENT:
		operand.Type = TypField
		var field Field
		field.Off = token.Off
		var segment *Segment
		var err error
		if segment, token, err = parseSegment(db, s, token); err != nil {
			return nil, nil, err
		}
		field.Segments = append(field.Segments, *segment)

		// If the next token is not a period, check for true/false/nil.
		// If true/false or nil, change this operand to a bool or nil, respectively.
		// Also, check for function call.  If so, change to a function operand.
		if token.Tok != TokPERIOD && (strings.ToLower(segment.Value) == "true" || strings.ToLower(segment.Value) == "false") {
			operand.Type = TypBool
			operand.Bool = strings.ToLower(segment.Value) == "true"
		} else if token.Tok != TokPERIOD && strings.ToLower(segment.Value) == "nil" {
			operand.Type = TypNil
		} else if token.Tok == TokLEFTPAREN {
			// Segments with a key specified cannot be function calls.
			if len(segment.Keys) != 0 {
				return nil, nil, syncql.NewErrUnexpected(db.GetContext(), token.Off, token.Value)
			}
			operand.Type = TypFunction
			var err error
			if operand.Function, token, err = parseFunction(db, s, segment.Value, segment.Off, token); err != nil {
				return nil, nil, err
			}
		} else { // This is a field (column) operand.
			// If the next token is a period, collect the rest of the segments in the column.
			for token.Tok != TokEOF && token.Tok == TokPERIOD {
				token = scanToken(s)
				if token.Tok != TokIDENT {
					return nil, nil, syncql.NewErrExpectedIdentifier(db.GetContext(), token.Off, token.Value)
				}
				if segment, token, err = parseSegment(db, s, token); err != nil {
					return nil, nil, err
				}
				field.Segments = append(field.Segments, *segment)
			}
			operand.Column = &field
		}
	case TokINT:
		operand.Type = TypInt
		i, err := strconv.ParseInt(token.Value, 0, 64)
		if err != nil {
			return nil, nil, syncql.NewErrCouldNotConvert(db.GetContext(), token.Off, token.Value, "int64")
		}
		operand.Int = i
		token = scanToken(s)
	case TokFLOAT:
		operand.Type = TypFloat
		f, err := strconv.ParseFloat(token.Value, 64)
		if err != nil {
			return nil, nil, syncql.NewErrCouldNotConvert(db.GetContext(), token.Off, token.Value, "float64")
		}
		operand.Float = f
		token = scanToken(s)
	case TokCHAR:
		operand.Type = TypInt
		ch, _ := utf8.DecodeRuneInString(token.Value)
		operand.Int = int64(ch)
		token = scanToken(s)
	case TokSTRING:
		operand.Type = TypStr
		operand.Str = token.Value
		token = scanToken(s)
	case TokMINUS:
		// Could be negative int or negative float
		off := token.Off
		token = scanToken(s)
		switch token.Tok {
		case TokINT:
			operand.Type = TypInt
			i, err := strconv.ParseInt("-"+token.Value, 0, 64)
			if err != nil {
				return nil, nil, syncql.NewErrCouldNotConvert(db.GetContext(), off, "-"+token.Value, "int64")
			}
			operand.Int = i
		case TokFLOAT:
			operand.Type = TypFloat
			f, err := strconv.ParseFloat("-"+token.Value, 64)
			if err != nil {
				return nil, nil, syncql.NewErrCouldNotConvert(db.GetContext(), off, "-"+token.Value, "float64")
			}
			operand.Float = f
		default:
			return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, "int or float")
		}
		token = scanToken(s)
	default:
		return nil, nil, syncql.NewErrExpectedOperand(db.GetContext(), token.Off, token.Value)
	}
	return &operand, token, nil
}

// Parse binary operator and return it and the next Token (or error)
func parseBinaryOperator(db query_db.Database, s *scanner.Scanner, token *Token) (*BinaryOperator, *Token, error) {
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	var operator BinaryOperator
	operator.Off = token.Off
	if token.Tok == TokIDENT {
		switch strings.ToLower(token.Value) {
		case "equal":
			operator.Type = Equal
			token = scanToken(s)
		case "is":
			operator.Type = Is
			token = scanToken(s)
			// if the next token is "not", change to IsNot
			if token.Tok != TokEOF && strings.ToLower(token.Value) == "not" {
				operator.Type = IsNot
				token = scanToken(s)
			}
		case "like":
			operator.Type = Like
			token = scanToken(s)
		case "not":
			token = scanToken(s)
			if token.Tok == TokEOF || (strings.ToLower(token.Value) != "equal" && strings.ToLower(token.Value) != "like") {
				return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, "'equal' or 'like'")
			}
			switch strings.ToLower(token.Value) {
			case "equal":
				operator.Type = NotEqual
			default: //case "like":
				operator.Type = NotLike
			}
			token = scanToken(s)
		default:
			return nil, nil, syncql.NewErrExpectedOperator(db.GetContext(), token.Off, token.Value)
		}
	} else {
		switch token.Tok {
		case TokEQUAL:
			operator.Type = Equal
			token = scanToken(s)
		case TokLEFTANGLEBRACKET:
			// Can be '<', '<=', '<>'.
			token = scanToken(s)
			switch token.Tok {
			case TokRIGHTANGLEBRACKET:
				operator.Type = NotEqual
				token = scanToken(s)
			case TokEQUAL:
				operator.Type = LessThanOrEqual
				token = scanToken(s)
			default:
				operator.Type = LessThan
			}
		case TokRIGHTANGLEBRACKET:
			// Can be '>', '>='
			token = scanToken(s)
			switch token.Tok {
			case TokEQUAL:
				operator.Type = GreaterThanOrEqual
				token = scanToken(s)
			default:
				operator.Type = GreaterThan
			}
		default:
			return nil, nil, syncql.NewErrExpectedOperator(db.GetContext(), token.Off, token.Value)
		}
	}

	return &operator, token, nil
}

// Parse logical operator and return it and the next Token (or error)
func parseLogicalOperator(db query_db.Database, s *scanner.Scanner, token *Token) (*BinaryOperator, *Token, error) {
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	var operator BinaryOperator
	operator.Off = token.Off
	switch strings.ToLower(token.Value) {
	case "and":
		operator.Type = And
	case "or":
		operator.Type = Or
	default:
		return nil, nil, syncql.NewErrExpectedOperator(db.GetContext(), token.Off, token.Value)
	}

	token = scanToken(s)
	return &operator, token, nil
}

// Parse and return LimitClause and ResultsOffsetClause (one or both can be nil) and next token (or error)
func parseLimitResultsOffsetClauses(db query_db.Database, s *scanner.Scanner, token *Token) (*LimitClause, *ResultsOffsetClause, *Token, error) {
	var err error
	var lc *LimitClause
	var oc *ResultsOffsetClause
	for token.Tok != TokEOF {
		// Note: Can be in any order.  If more than one limit or offset clause, the last one wins
		if token.Tok == TokIDENT && strings.ToLower(token.Value) == "limit" {
			lc, token, err = parseLimitClause(db, s, token)
		} else if token.Tok == TokIDENT && strings.ToLower(token.Value) == "offset" {
			oc, token, err = parseResultsOffsetClause(db, s, token)
		} else {
			return lc, oc, token, nil
		}
		if err != nil {
			return nil, nil, nil, err
		}
	}
	return lc, oc, token, nil
}

// Parse the limit clause.  Return the LimitClause and the next Token (or error).
func parseLimitClause(db query_db.Database, s *scanner.Scanner, token *Token) (*LimitClause, *Token, error) {
	var lc LimitClause
	lc.Off = token.Off
	token = scanToken(s)
	var err error
	lc.Limit, token, err = parseNonNegInt64(db, s, token)
	if err != nil {
		return nil, nil, err
	}
	return &lc, token, nil
}

// Parse the results offset clause.  Return the ResultsOffsetClause and the next Token (or error).
func parseResultsOffsetClause(db query_db.Database, s *scanner.Scanner, token *Token) (*ResultsOffsetClause, *Token, error) {
	var oc ResultsOffsetClause
	oc.Off = token.Off
	token = scanToken(s)
	var err error
	oc.ResultsOffset, token, err = parseNonNegInt64(db, s, token)
	if err != nil {
		return nil, nil, err
	}
	return &oc, token, nil
}

// Parse and return an Int64Value and next token (or error).
// This function is called by parseLimitClause and parseResultsOffsetClause.  The integer
// values for both of these clauses cannot be negative.
func parseNonNegInt64(db query_db.Database, s *scanner.Scanner, token *Token) (*Int64Value, *Token, error) {
	// We expect an integer literal
	// Since we're looking for integers >= 0, don't allow TokMINUS.
	if token.Tok == TokEOF {
		return nil, nil, syncql.NewErrUnexpectedEndOfStatement(db.GetContext(), token.Off)
	}
	if token.Tok != TokINT {
		return nil, nil, syncql.NewErrExpected(db.GetContext(), token.Off, "positive integer literal")
	}
	var v Int64Value
	v.Off = token.Off
	var err error
	v.Value, err = strconv.ParseInt(token.Value, 0, 64)
	if err != nil {
		// The token value has already been checked, so this can't happen.
		return nil, nil, syncql.NewErrCouldNotConvert(db.GetContext(), token.Off, token.Value, "int64")
	}
	token = scanToken(s)
	return &v, token, nil
}

func (st SelectStatement) Offset() int64 {
	return st.Off
}

// Pretty string of select statement.
func (st SelectStatement) String() string {
	val := fmt.Sprintf("Off(%d):", st.Off)
	if st.Select != nil {
		val += st.Select.String()
	}
	if st.From != nil {
		val += " " + st.From.String()
	}
	if st.Where != nil {
		val += " " + st.Where.String()
	}
	if st.Limit != nil {
		val += " " + st.Limit.String()
	}
	if st.ResultsOffset != nil {
		val += " " + st.ResultsOffset.String()
	}
	return val
}

func (sel SelectClause) String() string {
	val := fmt.Sprintf(" Off(%d):SELECT Columns(", sel.Off)
	sep := ""
	for _, selector := range sel.Selectors {
		val += sep + selector.String()
		sep = ","
	}
	val += ")"
	return val
}

func (s Selector) String() string {
	val := fmt.Sprintf(" Off(%d):", s.Off)
	switch s.Type {
	case TypSelField:
		val += s.Field.String()
	case TypSelFunc:
		val += s.Function.String()
	}
	if s.As != nil {
		val += s.As.String()
	}
	return val
}

func (a AsClause) String() string {
	val := fmt.Sprintf(" Off(%d):", a.Off)
	val += a.AltName.String()
	return val
}

func (n Name) String() string {
	val := fmt.Sprintf(" Off(%d):", n.Off)
	val += n.Value
	return val
}

func (f Field) String() string {
	val := fmt.Sprintf(" Off(%d):", f.Off)
	for i := range f.Segments {
		if i != 0 {
			val += "."
		}
		val += f.Segments[i].String()
	}
	return val
}

func (f Function) String() string {
	val := fmt.Sprintf("Off(%d):", f.Off)
	val += f.Name
	val += "("
	sep := ""
	for _, a := range f.Args {
		val += sep + a.String()
		sep = ","
	}
	val += ")"
	return val
}

func (s Segment) String() string {
	val := fmt.Sprintf(" Off(%d):%s", s.Off, s.Value)
	for _, k := range s.Keys {
		val += "[" + k.String() + "]"
	}
	return val
}

func (f FromClause) String() string {
	return fmt.Sprintf("Off(%d):FROM %s", f.Off, f.Table.String())
}

func (t TableEntry) String() string {
	return fmt.Sprintf("Off(%d):%s", t.Off, t.Name)
}

func (w WhereClause) String() string {
	return fmt.Sprintf(" Off(%d):WHERE %s", w.Off, w.Expr.String())
}

func (l LimitClause) String() string {
	return fmt.Sprintf(" Off(%d):LIMIT %d", l.Off, l.Limit)
}

func (l ResultsOffsetClause) String() string {
	return fmt.Sprintf(" Off(%d):OFFSET %d", l.Off, l.ResultsOffset)
}

func (o Operand) String() string {
	val := fmt.Sprintf("Off(%d):", o.Off)
	switch o.Type {
	case TypBigInt:
		val += "(BigInt)"
		val += o.BigInt.String()
	case TypBigRat:
		val += "(BigRat)"
		val += o.BigRat.String()
	case TypComplex:
		val += "(Complex)"
		val += fmt.Sprintf("%g", o.Complex)
	case TypField:
		val += "(field)"
		val += o.Column.String()
	case TypBool:
		val += "(bool)"
		val += strconv.FormatBool(o.Bool)
	case TypInt:
		val += "(int)"
		val += strconv.FormatInt(o.Int, 10)
	case TypFloat:
		val += "(float)"
		val += strconv.FormatFloat(o.Float, 'f', -1, 64)
	case TypFunction:
		val += "(function)"
		val += o.Function.String()
	case TypStr:
		val += "(string)"
		val += o.Str
	case TypExpr:
		val += "(expr)"
		val += o.Expr.String()
	case TypTime:
		val += "(time)"
		val += o.Time.Format("Mon Jan 2 15:04:05 -0700 MST 2006")
	case TypNil:
		val += "<nil>"
	case TypObject:
		val += "(object)"
		val += fmt.Sprintf("%v", o.Object)
	default:
		val += "<operand-type-undefined>"

	}
	return val
}

func (o BinaryOperator) String() string {
	val := fmt.Sprintf("Off(%d):", o.Off)
	switch o.Type {
	case And:
		val += "AND"
	case Equal:
		val += "="
	case GreaterThan:
		val += ">"
	case GreaterThanOrEqual:
		val += ">="
	case Is:
		val += "IS"
	case IsNot:
		val += "IS NOT"
	case LessThan:
		val += "<"
	case LessThanOrEqual:
		val += "<="
	case Like:
		val += "LIKE"
	case NotEqual:
		val += "<>"
	case NotLike:
		val += "NOT LIKE"
	case Or:
		val += "OR"
	default:
		val += "<operator-undefined>"
	}
	return val
}

func (e Expression) String() string {
	return fmt.Sprintf("(Off(%d):%s %s %s)", e.Off, e.Operand1.String(), e.Operator.String(), e.Operand2.String())
}