parser.go

package main

import (
	"fmt"
	"math"
	"strconv"
	"strings"
	"unicode"
)

// --- 1. ABSTRACT SYNTAX TREE (AST) DEFINITIONS ---

const (
	QL_UNK = iota
	QL_CMP_GE
	QL_CMP_GT
	QL_CMP_LT
	QL_CMP_LE
	QL_CMP_EQ
	QL_CMP_NE
	QL_AND
	QL_OR
	QL_NOT
	QL_ADD
	QL_SUB
	QL_MUL
	QL_DIV
	QL_NEG
	QL_SYM // Column name or identifier
	QL_STR // String literal
	QL_I64 // Integer literal
	QL_TUP // Tuple / List
)

type QLNode struct {
	Type uint32
	I64  int64
	Str  []byte
	Kids []QLNode
}

type QLScan struct {
	Table  string
	Key1   QLNode // Index By (Start/Range)
	Key2   QLNode // Index By (End)
	Filter QLNode // Filter Condition
	Offset int64
	Limit  int64
}

type QLSelect struct {
	QLScan
	Names  []string
	Output []QLNode
}

type QLUpdate struct {
	QLScan
	Names  []string
	Values []QLNode
}

type QLDelete struct {
	QLScan
}

type QLInsert struct {
	Table  string
	Names  []string
	Values [][]QLNode
}

type QLCreateTable struct {
	Def TableDef
}

// --- 2. LEXER / TOKENIZER ---

type Parser struct {
	sql string
	pos int
}

func (p *Parser) skipWhitespace() {
	for p.pos < len(p.sql) && unicode.IsSpace(rune(p.sql[p.pos])) {
		p.pos++
	}
}

// peek returns the next token string without advancing the cursor
func (p *Parser) peek() string {
	p.skipWhitespace()
	if p.pos >= len(p.sql) {
		return ""
	}

	// Punctuation / Operators
	for _, op := range []string{">=", "<=", "!=", "==", ">", "<", "=", "+", "-", "*", "/", "(", ")", ","} {
		if strings.HasPrefix(p.sql[p.pos:], op) {
			return op
		}
	}

	// String literals
	if p.sql[p.pos] == '\'' {
		end := strings.IndexByte(p.sql[p.pos+1:], '\'')
		if end == -1 {
			panic("unclosed string literal")
		}
		return p.sql[p.pos : p.pos+end+2]
	}

	// Symbols (Keywords, Columns) and Numbers
	start := p.pos
	for p.pos < len(p.sql) {
		ch := rune(p.sql[p.pos])
		if unicode.IsSpace(ch) || strings.ContainsRune(">=<!=+-*/(),", ch) {
			break
		}
		p.pos++
	}
	tok := p.sql[start:p.pos]
	p.pos = start // Reset cursor because this is just a peek
	return tok
}

// consume reads the next token and advances the cursor
func (p *Parser) consume() string {
	tok := p.peek()
	p.pos += len(tok)
	return tok
}

// pKeyword checks if the next tokens match the requested keywords (case-insensitive)
func pKeyword(p *Parser, words ...string) bool {
	savedPos := p.pos
	for _, word := range words {
		tok := p.consume()
		if !strings.EqualFold(tok, word) {
			p.pos = savedPos // Revert if mismatch
			return false
		}
	}
	return true
}

func pMustSym(p *Parser) string {
	tok := p.consume()
	if tok == "" || !unicode.IsLetter(rune(tok[0])) && tok[0] != '@' {
		panic("expected symbol, got: " + tok)
	}
	return tok
}

// --- 3. RECURSIVE DESCENT EXPRESSION PARSER ---

func pExprOr(p *Parser) QLNode {
	node := pExprAnd(p)
	for pKeyword(p, "OR") {
		right := pExprAnd(p)
		node = QLNode{Type: QL_OR, Kids: []QLNode{node, right}}
	}
	return node
}

func pExprAnd(p *Parser) QLNode {
	node := pExprNot(p)
	for pKeyword(p, "AND") {
		right := pExprNot(p)
		node = QLNode{Type: QL_AND, Kids: []QLNode{node, right}}
	}
	return node
}

func pExprNot(p *Parser) QLNode {
	if pKeyword(p, "NOT") {
		right := pExprCmp(p)
		return QLNode{Type: QL_NOT, Kids: []QLNode{right}}
	}
	return pExprCmp(p)
}

func pExprCmp(p *Parser) QLNode {
	node := pExprAdd(p)
	
	opMap := map[string]uint32{
		">=": QL_CMP_GE, ">": QL_CMP_GT,
		"<=": QL_CMP_LE, "<": QL_CMP_LT,
		"=": QL_CMP_EQ, "==": QL_CMP_EQ, "!=": QL_CMP_NE,
	}

	tok := p.peek()
	if opType, exists := opMap[tok]; exists {
		p.consume() // Consume the operator
		right := pExprAdd(p)
		node = QLNode{Type: opType, Kids: []QLNode{node, right}}
	}
	return node
}

func pExprAdd(p *Parser) QLNode {
	node := pExprMul(p)
	for {
		tok := p.peek()
		if tok == "+" {
			p.consume()
			node = QLNode{Type: QL_ADD, Kids: []QLNode{node, pExprMul(p)}}
		} else if tok == "-" {
			p.consume()
			node = QLNode{Type: QL_SUB, Kids: []QLNode{node, pExprMul(p)}}
		} else {
			break
		}
	}
	return node
}

func pExprMul(p *Parser) QLNode {
	node := pExprUnop(p)
	for {
		tok := p.peek()
		if tok == "*" {
			p.consume()
			node = QLNode{Type: QL_MUL, Kids: []QLNode{node, pExprUnop(p)}}
		} else if tok == "/" {
			p.consume()
			node = QLNode{Type: QL_DIV, Kids: []QLNode{node, pExprUnop(p)}}
		} else {
			break
		}
	}
	return node
}

func pExprUnop(p *Parser) QLNode {
	if pKeyword(p, "-") {
		right := pExprAtom(p)
		return QLNode{Type: QL_NEG, Kids: []QLNode{right}}
	}
	return pExprAtom(p)
}

func pExprAtom(p *Parser) QLNode {
	tok := p.consume()
	
	// Tuple (parentheses)
	if tok == "(" {
		node := QLNode{Type: QL_TUP}
		node.Kids = append(node.Kids, pExprOr(p))
		for pKeyword(p, ",") {
			node.Kids = append(node.Kids, pExprOr(p))
		}
		if !pKeyword(p, ")") {
			panic("expected closing parenthesis")
		}
		return node
	}

	// String literal
	if strings.HasPrefix(tok, "'") {
		return QLNode{Type: QL_STR, Str: []byte(tok[1 : len(tok)-1])}
	}

	// Number literal
	if i, err := strconv.ParseInt(tok, 10, 64); err == nil {
		return QLNode{Type: QL_I64, I64: i}
	}

	// Symbol (Column Name)
	return QLNode{Type: QL_SYM, Str: []byte(tok)}
}

// --- 4. STATEMENT PARSERS ---

func pScan(p *Parser, node *QLScan) {
	if pKeyword(p, "INDEX", "BY") {
		node.Key1 = pExprOr(p)
	}
	if pKeyword(p, "FILTER") {
		node.Filter = pExprOr(p)
	}

	node.Offset = 0
	node.Limit = math.MaxInt64
	if pKeyword(p, "LIMIT") {
		node.Limit = pExprAtom(p).I64
	}
}

func pSelect(p *Parser) *QLSelect {
	stmt := QLSelect{}
	
	// Parse Output Expressions (e.g. SELECT a, b+1)
	expr := pExprOr(p)
	stmt.Output = append(stmt.Output, expr)
	if expr.Type == QL_SYM {
		stmt.Names = append(stmt.Names, string(expr.Str))
	} else {
		stmt.Names = append(stmt.Names, fmt.Sprintf("col%d", len(stmt.Output)))
	}

	for pKeyword(p, ",") {
		expr := pExprOr(p)
		stmt.Output = append(stmt.Output, expr)
		if expr.Type == QL_SYM {
			stmt.Names = append(stmt.Names, string(expr.Str))
		} else {
			stmt.Names = append(stmt.Names, fmt.Sprintf("col%d", len(stmt.Output)))
		}
	}

	if !pKeyword(p, "FROM") {
		panic("expected FROM")
	}
	stmt.Table = pMustSym(p)
	
	pScan(p, &stmt.QLScan)
	return &stmt
}

func pCreateTable(p *Parser) *QLCreateTable {
	stmt := QLCreateTable{}
	if !pKeyword(p, "TABLE") {
		panic("expected TABLE")
	}
	stmt.Def.Name = pMustSym(p)
	if !pKeyword(p, "(") {
		panic("expected (")
	}

	for {
		if pKeyword(p, "INDEX") {
			if !pKeyword(p, "(") {
				panic("expected (")
			}
			idxCol := pMustSym(p)
			if !pKeyword(p, ")") {
				panic("expected )")
			}
			stmt.Def.Indexes = append(stmt.Def.Indexes, []string{idxCol})
		} else {
			colName := pMustSym(p)
			colTypeStr := pMustSym(p)
			var colType uint32
			if strings.EqualFold(colTypeStr, "INT64") {
				colType = TYPE_INT64 
			} else if strings.EqualFold(colTypeStr, "BYTES") {
				colType = TYPE_BYTES
			} else {
				panic("unknown type: " + colTypeStr)
			}
			stmt.Def.Cols = append(stmt.Def.Cols, colName)
			stmt.Def.Types = append(stmt.Def.Types, colType)
		}

		if pKeyword(p, ",") {
			continue
		}
		if pKeyword(p, ")") {
			break
		}
		panic("expected , or )")
	}
	return &stmt
}

func pInsert(p *Parser) *QLInsert {
	stmt := QLInsert{}
	if !pKeyword(p, "INTO") {
		panic("expected INTO")
	}
	stmt.Table = pMustSym(p)
	
	if !pKeyword(p, "(") {
		panic("expected (")
	}
	for {
		stmt.Names = append(stmt.Names, pMustSym(p))
		if pKeyword(p, ",") {
			continue
		}
		if pKeyword(p, ")") {
			break
		}
		panic("expected , or )")
	}

	if !pKeyword(p, "VALUES") {
		panic("expected VALUES")
	}
	
	if !pKeyword(p, "(") {
		panic("expected (")
	}
	var row []QLNode
	for {
		row = append(row, pExprOr(p))
		if pKeyword(p, ",") {
			continue
		}
		if pKeyword(p, ")") {
			break
		}
		panic("expected , or )")
	}
	stmt.Values = append(stmt.Values, row)

	return &stmt
}

// ParseSQL is the main entry point to parse a raw SQL string into an AST
func ParseSQL(sql string) (ast interface{}, err error) {
	defer func() {
		if r := recover(); r != nil {
			// Catch panics and return them as clean syntax errors
			err = fmt.Errorf("syntax error: %v", r)
		}
	}()

	p := &Parser{sql: sql, pos: 0}
	
	if pKeyword(p, "SELECT") {
		return pSelect(p), nil
	}
	if pKeyword(p, "CREATE") {
		return pCreateTable(p), nil
	}
	if pKeyword(p, "INSERT") {
		return pInsert(p), nil
	}
	
	return nil, fmt.Errorf("unsupported statement")
}