package main

import (
	"encoding/xml"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

// Node retains XML order and source locations, including expressions. Resolution
// turns this syntax tree into the flat, typed emission IR; parsing makes no Go
// naming or layout choices.
type Node struct {
	Kind     string
	Attr     map[string]string
	Text     string
	Children []*Node
	File     string
	Line     int
}

func (n *Node) fail(format string, args ...any) error {
	return fmt.Errorf("%s:%d: %s", n.File, n.Line, fmt.Sprintf(format, args...))
}

// Attribute and child whitelists are per element, not global: a known attribute
// or element used in the wrong place is also an error. Documentation is ignored.
var attributes = map[string]string{
	"xcb":    "header extension-name extension-xname extension-multiword major-version minor-version",
	"import": "", "typedef": "oldname newname", "xidtype": "name", "xidunion": "name", "type": "",
	"enum": "name", "item": "name", "value": "", "bit": "", "struct": "name", "union": "name",
	"request": "name opcode combine-adjacent", "reply": "", "event": "name number no-sequence-number xge",
	"eventcopy": "name number ref", "error": "name number type", "errorcopy": "name number ref",
	"field": "name type enum altenum mask", "pad": "bytes align", "list": "name type enum",
	"exprfield": "name type", "switch": "name", "bitcase": "", "fieldref": "", "enumref": "ref",
	"op": "op", "unop": "op", "popcount": "", "doc": "",
}
var children = map[string]string{
	"xcb":      "import typedef xidtype xidunion enum struct union request event eventcopy error errorcopy doc",
	"xidunion": "type", "enum": "item doc", "item": "value bit doc",
	"struct": "field pad list doc", "union": "field pad list doc",
	"request": "field pad list exprfield switch reply doc", "reply": "field pad list exprfield doc",
	"event": "field pad list exprfield doc", "error": "field pad doc",
	"list": "value fieldref op unop popcount enumref", "exprfield": "value fieldref op unop popcount enumref",
	"switch": "fieldref op unop popcount enumref bitcase", "bitcase": "enumref value field pad doc",
	"op": "value fieldref op unop popcount enumref", "unop": "value fieldref op unop popcount enumref",
	"popcount": "value fieldref op unop popcount enumref",
}

func contains(words, word string) bool {
	for _, s := range strings.Fields(words) {
		if s == word {
			return true
		}
	}
	return false
}

func parseFile(path string) (*Node, error) {
	f, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer f.Close()
	return parseXML(path, f)
}
func parseXML(file string, r io.Reader) (*Node, error) {
	d := xml.NewDecoder(r)
	var root *Node
	var stack []*Node
	for {
		token, err := d.Token()
		if err == io.EOF {
			break
		}
		if err != nil {
			line, _ := d.InputPos()
			return nil, fmt.Errorf("%s:%d: %w", file, line, err)
		}
		switch t := token.(type) {
		case xml.StartElement:
			line, _ := d.InputPos()
			n := &Node{Kind: t.Name.Local, Attr: make(map[string]string), File: file, Line: line}
			allowed, ok := attributes[n.Kind]
			if !ok || t.Name.Space != "" {
				return nil, n.fail("unsupported element <%s>", t.Name.Local)
			}
			if len(stack) == 0 {
				if root != nil || n.Kind != "xcb" {
					return nil, n.fail("expected a single <xcb> root")
				}
				root = n
			} else {
				parent := stack[len(stack)-1]
				if !contains(children[parent.Kind], n.Kind) {
					return nil, n.fail("unsupported <%s> in <%s>", n.Kind, parent.Kind)
				}
				parent.Children = append(parent.Children, n)
			}
			if n.Kind == "doc" {
				if err := d.Skip(); err != nil {
					return nil, n.fail("invalid doc: %v", err)
				}
				continue
			}
			for _, a := range t.Attr {
				if a.Name.Space != "" || !contains(allowed, a.Name.Local) {
					return nil, n.fail("unknown attribute %q on <%s>", a.Name.Local, n.Kind)
				}
				if _, ok := n.Attr[a.Name.Local]; ok {
					return nil, n.fail("duplicate attribute %q", a.Name.Local)
				}
				n.Attr[a.Name.Local] = a.Value
			}
			stack = append(stack, n)
		case xml.EndElement:
			if len(stack) == 0 {
				return nil, fmt.Errorf("%s: unexpected closing element", file)
			}
			n := stack[len(stack)-1]
			n.Text = strings.TrimSpace(n.Text)
			if err := validateNode(n); err != nil {
				return nil, err
			}
			stack = stack[:len(stack)-1]
		case xml.CharData:
			if len(stack) > 0 {
				stack[len(stack)-1].Text += string(t)
			} else if strings.TrimSpace(string(t)) != "" {
				return nil, fmt.Errorf("%s: text outside root", file)
			}
		case xml.Directive:
			return nil, fmt.Errorf("%s: XML directives are unsupported", file)
		}
	}
	if root == nil {
		return nil, fmt.Errorf("%s:1: missing <xcb> root", file)
	}
	return root, nil
}
func require(n *Node, names string) error {
	for _, name := range strings.Fields(names) {
		if n.Attr[name] == "" {
			return n.fail("missing %s on <%s>", name, n.Kind)
		}
	}
	return nil
}
func number(n *Node, attr string, bits int) error {
	_, err := strconv.ParseUint(n.Attr[attr], 0, bits)
	if err != nil {
		return n.fail("invalid %s %q", attr, n.Attr[attr])
	}
	return nil
}
func exprCount(n *Node) int {
	count := 0
	for _, c := range n.Children {
		if c.Kind != "doc" {
			count++
		}
	}
	return count
}
func validateNode(n *Node) error {
	required := map[string]string{
		"xcb": "header", "typedef": "oldname newname", "xidtype": "name", "xidunion": "name",
		"enum": "name", "item": "name", "struct": "name", "union": "name", "request": "name opcode",
		"event": "name number", "eventcopy": "name number ref", "error": "name number", "errorcopy": "name number ref",
		"field": "name type", "list": "name type", "exprfield": "name type", "switch": "name", "enumref": "ref", "op": "op", "unop": "op",
	}
	if err := require(n, required[n.Kind]); err != nil {
		return err
	}
	switch n.Kind {
	case "import", "type", "fieldref", "enumref":
		if n.Text == "" {
			return n.fail("empty <%s>", n.Kind)
		}
	case "value", "bit":
		if _, err := strconv.ParseInt(n.Text, 0, 64); err != nil {
			return n.fail("invalid <%s> integer %q", n.Kind, n.Text)
		}
	case "pad":
		_, b := n.Attr["bytes"]
		_, a := n.Attr["align"]
		if b == a {
			return n.fail("pad requires exactly one of bytes or align")
		}
		key := "bytes"
		if a {
			key = "align"
		}
		if err := number(n, key, 31); err != nil {
			return err
		}
		if a {
			v, _ := strconv.Atoi(n.Attr[key])
			if v == 0 || v&(v-1) != 0 {
				return n.fail("pad alignment must be a positive power of two")
			}
		}
	case "request":
		if err := number(n, "opcode", 8); err != nil {
			return err
		}
	case "event", "eventcopy", "error", "errorcopy":
		if err := number(n, "number", 8); err != nil {
			return err
		}
		if n.Attr["xge"] == "true" {
			v, _ := strconv.Atoi(n.Attr["number"])
			if v >= 128 {
				return n.fail("xge evtype must be < 128")
			}
		}
	case "op":
		if !contains("+ - * / & | << >>", n.Attr["op"]) {
			return n.fail("unsupported operator %q", n.Attr["op"])
		}
		if exprCount(n) != 2 {
			return n.fail("op requires two operands")
		}
	case "unop":
		if n.Attr["op"] != "~" {
			return n.fail("unsupported unary operator %q", n.Attr["op"])
		}
		if exprCount(n) != 1 {
			return n.fail("unop requires one operand")
		}
	case "popcount", "exprfield", "item":
		if exprCount(n) != 1 {
			return n.fail("<%s> requires one expression", n.Kind)
		}
	case "list":
		if exprCount(n) > 1 {
			return n.fail("list has multiple length expressions")
		}
	case "bitcase":
		fields := 0
		for _, c := range n.Children {
			if c.Kind == "field" {
				fields++
				if contains("CARD8 CARD16 INT8 INT16 BOOL char BYTE void", c.Attr["type"]) {
					return c.fail("value-list bitcase requires a 4-byte field")
				}
			}
		}
		if fields != 1 {
			return n.fail("value-list bitcase requires exactly one field")
		}
	}
	for _, key := range []string{"xge", "no-sequence-number", "combine-adjacent", "extension-multiword"} {
		if v, ok := n.Attr[key]; ok && v != "true" && v != "false" {
			return n.fail("invalid boolean %s=%q", key, v)
		}
	}
	// Forward references cannot be laid out in one pass. Reject at the length
	// expression's location rather than failing later while emitting Go.
	declared := map[string]bool{}
	for _, c := range n.Children {
		if c.Kind == "field" || c.Kind == "exprfield" {
			declared[c.Attr["name"]] = true
		}
	}
	seen := map[string]bool{}
	for _, c := range n.Children {
		if c.Kind == "list" {
			var visit func(*Node) error
			visit = func(e *Node) error {
				if e.Kind == "fieldref" && declared[e.Text] && !seen[e.Text] {
					return e.fail("list length references later field %q", e.Text)
				}
				for _, child := range e.Children {
					if err := visit(child); err != nil {
						return err
					}
				}
				return nil
			}
			if err := visit(c); err != nil {
				return err
			}
		}
		if c.Kind == "field" || c.Kind == "exprfield" {
			seen[c.Attr["name"]] = true
		}
	}
	return nil
}