repos / gbc

GBC - Go B Compiler
git clone https://github.com/xplshn/gbc.git

gbc / pkg / ast
xplshn  ·  2025-08-16

ast.go

Go
  1package ast
  2
  3import (
  4	"github.com/xplshn/gbc/pkg/token"
  5	"github.com/xplshn/gbc/pkg/util"
  6)
  7
  8type NodeType int
  9
 10const (
 11	// Expressions
 12	Number NodeType = iota
 13	String
 14	Ident
 15	Assign
 16	BinaryOp
 17	UnaryOp
 18	PostfixOp
 19	FuncCall
 20	Indirection
 21	AddressOf
 22	Ternary
 23	Subscript
 24	AutoAlloc
 25	MemberAccess
 26	TypeCast
 27
 28	// Statements
 29	FuncDecl
 30	VarDecl
 31	MultiVarDecl
 32	TypeDecl
 33	ExtrnDecl
 34	If
 35	While
 36	Return
 37	Block
 38	Goto
 39	Switch
 40	Case
 41	Default
 42	Break
 43	Continue
 44	Label
 45	AsmStmt
 46	Directive
 47)
 48
 49// Node represents a node in the Abstract Syntax Tree.
 50type Node struct {
 51	Type   NodeType
 52	Tok    token.Token
 53	Parent *Node
 54	Data   interface{}
 55	Typ    *BxType // Set by the type checker.
 56}
 57
 58type BxTypeKind int
 59
 60const (
 61	TYPE_PRIMITIVE BxTypeKind = iota
 62	TYPE_POINTER
 63	TYPE_VOID
 64	TYPE_ARRAY
 65	TYPE_STRUCT
 66	TYPE_BOOL
 67	TYPE_FLOAT
 68	TYPE_UNTYPED
 69)
 70
 71// BxType represents a type in the Bx type system.
 72type BxType struct {
 73	Kind      BxTypeKind
 74	Base      *BxType // Base type for pointers or arrays.
 75	Name      string  // Name for primitive types or the typedef name.
 76	ArraySize *Node
 77	IsConst   bool
 78	StructTag string  // The name immediately following the 'struct' keyword.
 79	Fields    []*Node // List of *VarDecl nodes for struct members.
 80}
 81
 82// Pre-defined types.
 83var (
 84	TypeInt     = &BxType{Kind: TYPE_PRIMITIVE, Name: "int"}
 85	TypeUint    = &BxType{Kind: TYPE_PRIMITIVE, Name: "uint"}
 86	TypeInt8    = &BxType{Kind: TYPE_PRIMITIVE, Name: "int8"}
 87	TypeUint8   = &BxType{Kind: TYPE_PRIMITIVE, Name: "uint8"}
 88	TypeInt16   = &BxType{Kind: TYPE_PRIMITIVE, Name: "int16"}
 89	TypeUint16  = &BxType{Kind: TYPE_PRIMITIVE, Name: "uint16"}
 90	TypeInt32   = &BxType{Kind: TYPE_PRIMITIVE, Name: "int32"}
 91	TypeUint32  = &BxType{Kind: TYPE_PRIMITIVE, Name: "uint32"}
 92	TypeInt64   = &BxType{Kind: TYPE_PRIMITIVE, Name: "int64"}
 93	TypeUint64  = &BxType{Kind: TYPE_PRIMITIVE, Name: "uint64"}
 94	TypeFloat   = &BxType{Kind: TYPE_FLOAT, Name: "float"}
 95	TypeFloat32 = &BxType{Kind: TYPE_FLOAT, Name: "float32"}
 96	TypeFloat64 = &BxType{Kind: TYPE_FLOAT, Name: "float64"}
 97	TypeByte    = &BxType{Kind: TYPE_PRIMITIVE, Name: "byte"}
 98	TypeVoid    = &BxType{Kind: TYPE_VOID, Name: "void"}
 99	TypeBool    = &BxType{Kind: TYPE_BOOL, Name: "bool"}
100	TypeUntyped = &BxType{Kind: TYPE_UNTYPED, Name: "untyped"}
101	TypeString  = &BxType{Kind: TYPE_POINTER, Base: TypeByte, Name: "string"}
102)
103
104type NumberNode struct{ Value int64 }
105type StringNode struct{ Value string }
106type IdentNode struct{ Name string }
107type AssignNode struct{ Op token.Type; Lhs, Rhs *Node }
108type BinaryOpNode struct{ Op token.Type; Left, Right *Node }
109type UnaryOpNode struct{ Op token.Type; Expr *Node }
110type PostfixOpNode struct{ Op token.Type; Expr *Node }
111type IndirectionNode struct{ Expr *Node }
112type AddressOfNode struct{ LValue *Node }
113type TernaryNode struct{ Cond, ThenExpr, ElseExpr *Node }
114type SubscriptNode struct{ Array, Index *Node }
115type MemberAccessNode struct{ Expr, Member *Node }
116type TypeCastNode struct{ Expr *Node; TargetType *BxType }
117type FuncCallNode struct{ FuncExpr *Node; Args []*Node }
118type AutoAllocNode struct{ Size *Node }
119type FuncDeclNode struct {
120	Name       string
121	Params     []*Node
122	Body       *Node
123	HasVarargs bool
124	IsTyped    bool
125	ReturnType *BxType
126}
127type VarDeclNode struct {
128	Name        string
129	Type        *BxType
130	InitList    []*Node
131	SizeExpr    *Node
132	IsVector    bool
133	IsBracketed bool
134	IsDefine    bool
135}
136type MultiVarDeclNode struct{ Decls []*Node }
137type TypeDeclNode struct{ Name string; Type *BxType }
138type ExtrnDeclNode struct{ Names []*Node }
139type IfNode struct{ Cond, ThenBody, ElseBody *Node }
140type WhileNode struct{ Cond, Body *Node }
141type ReturnNode struct{ Expr *Node }
142type BlockNode struct{ Stmts []*Node; IsSynthetic bool }
143type GotoNode struct{ Label string }
144type CaseLabelNode struct{ Value int64; LabelName string }
145type SwitchNode struct{ Expr, Body *Node; CaseLabels []CaseLabelNode; DefaultLabelName string }
146type CaseNode struct{ Value, Body *Node; QbeLabel string }
147type DefaultNode struct{ Body *Node; QbeLabel string }
148type BreakNode struct{}
149type ContinueNode struct{}
150type LabelNode struct{ Name string; Stmt *Node }
151type AsmStmtNode struct{ Code string }
152type DirectiveNode struct{ Name string }
153
154func newNode(tok token.Token, nodeType NodeType, data interface{}, children ...*Node) *Node {
155	node := &Node{Type: nodeType, Tok: tok, Data: data}
156	for _, child := range children {
157		if child != nil {
158			child.Parent = node
159		}
160	}
161	return node
162}
163
164func NewNumber(tok token.Token, value int64) *Node {
165	return newNode(tok, Number, NumberNode{Value: value})
166}
167func NewString(tok token.Token, value string) *Node {
168	return newNode(tok, String, StringNode{Value: value})
169}
170func NewIdent(tok token.Token, name string) *Node {
171	return newNode(tok, Ident, IdentNode{Name: name})
172}
173func NewAssign(tok token.Token, op token.Type, lhs, rhs *Node) *Node {
174	return newNode(tok, Assign, AssignNode{Op: op, Lhs: lhs, Rhs: rhs}, lhs, rhs)
175}
176func NewBinaryOp(tok token.Token, op token.Type, left, right *Node) *Node {
177	return newNode(tok, BinaryOp, BinaryOpNode{Op: op, Left: left, Right: right}, left, right)
178}
179func NewUnaryOp(tok token.Token, op token.Type, expr *Node) *Node {
180	return newNode(tok, UnaryOp, UnaryOpNode{Op: op, Expr: expr}, expr)
181}
182func NewPostfixOp(tok token.Token, op token.Type, expr *Node) *Node {
183	return newNode(tok, PostfixOp, PostfixOpNode{Op: op, Expr: expr}, expr)
184}
185func NewIndirection(tok token.Token, expr *Node) *Node {
186	return newNode(tok, Indirection, IndirectionNode{Expr: expr}, expr)
187}
188func NewAddressOf(tok token.Token, lvalue *Node) *Node {
189	return newNode(tok, AddressOf, AddressOfNode{LValue: lvalue}, lvalue)
190}
191func NewTernary(tok token.Token, cond, thenExpr, elseExpr *Node) *Node {
192	return newNode(tok, Ternary, TernaryNode{Cond: cond, ThenExpr: thenExpr, ElseExpr: elseExpr}, cond, thenExpr, elseExpr)
193}
194func NewSubscript(tok token.Token, array, index *Node) *Node {
195	return newNode(tok, Subscript, SubscriptNode{Array: array, Index: index}, array, index)
196}
197func NewMemberAccess(tok token.Token, expr, member *Node) *Node {
198	return newNode(tok, MemberAccess, MemberAccessNode{Expr: expr, Member: member}, expr, member)
199}
200func NewTypeCast(tok token.Token, expr *Node, targetType *BxType) *Node {
201	return newNode(tok, TypeCast, TypeCastNode{Expr: expr, TargetType: targetType}, expr)
202}
203func NewFuncCall(tok token.Token, funcExpr *Node, args []*Node) *Node {
204	node := newNode(tok, FuncCall, FuncCallNode{FuncExpr: funcExpr, Args: args}, funcExpr)
205	for _, arg := range args {
206		arg.Parent = node
207	}
208	return node
209}
210func NewAutoAlloc(tok token.Token, size *Node) *Node {
211	return newNode(tok, AutoAlloc, AutoAllocNode{Size: size}, size)
212}
213func NewFuncDecl(tok token.Token, name string, params []*Node, body *Node, hasVarargs bool, isTyped bool, returnType *BxType) *Node {
214	node := newNode(tok, FuncDecl, FuncDeclNode{
215		Name: name, Params: params, Body: body, HasVarargs: hasVarargs, IsTyped: isTyped, ReturnType: returnType,
216	}, body)
217	for _, p := range params {
218		p.Parent = node
219	}
220	return node
221}
222func NewVarDecl(tok token.Token, name string, varType *BxType, initList []*Node, sizeExpr *Node, isVector bool, isBracketed bool, isDefine bool) *Node {
223	node := newNode(tok, VarDecl, VarDeclNode{
224		Name: name, Type: varType, InitList: initList, SizeExpr: sizeExpr, IsVector: isVector, IsBracketed: isBracketed, IsDefine: isDefine,
225	}, sizeExpr)
226	for _, init := range initList {
227		init.Parent = node
228	}
229	return node
230}
231func NewMultiVarDecl(tok token.Token, decls []*Node) *Node {
232	node := newNode(tok, MultiVarDecl, MultiVarDeclNode{Decls: decls})
233	for _, d := range decls {
234		d.Parent = node
235	}
236	return node
237}
238func NewTypeDecl(tok token.Token, name string, typ *BxType) *Node {
239	return newNode(tok, TypeDecl, TypeDeclNode{Name: name, Type: typ})
240}
241func NewExtrnDecl(tok token.Token, names []*Node) *Node {
242	node := newNode(tok, ExtrnDecl, ExtrnDeclNode{Names: names})
243	for _, n := range names {
244		n.Parent = node
245	}
246	return node
247}
248func NewIf(tok token.Token, cond, thenBody, elseBody *Node) *Node {
249	return newNode(tok, If, IfNode{Cond: cond, ThenBody: thenBody, ElseBody: elseBody}, cond, thenBody, elseBody)
250}
251func NewWhile(tok token.Token, cond, body *Node) *Node {
252	return newNode(tok, While, WhileNode{Cond: cond, Body: body}, cond, body)
253}
254func NewReturn(tok token.Token, expr *Node) *Node {
255	return newNode(tok, Return, ReturnNode{Expr: expr}, expr)
256}
257func NewBlock(tok token.Token, stmts []*Node, isSynthetic bool) *Node {
258	node := newNode(tok, Block, BlockNode{Stmts: stmts, IsSynthetic: isSynthetic})
259	for _, s := range stmts {
260		if s != nil {
261			s.Parent = node
262		}
263	}
264	return node
265}
266func NewGoto(tok token.Token, label string) *Node {
267	return newNode(tok, Goto, GotoNode{Label: label})
268}
269func NewSwitch(tok token.Token, expr, body *Node) *Node {
270	return newNode(tok, Switch, SwitchNode{Expr: expr, Body: body}, expr, body)
271}
272func NewCase(tok token.Token, value, body *Node) *Node {
273	return newNode(tok, Case, CaseNode{Value: value, Body: body}, value, body)
274}
275func NewDefault(tok token.Token, body *Node) *Node {
276	return newNode(tok, Default, DefaultNode{Body: body}, body)
277}
278func NewBreak(tok token.Token) *Node {
279	return newNode(tok, Break, BreakNode{})
280}
281func NewContinue(tok token.Token) *Node {
282	return newNode(tok, Continue, ContinueNode{})
283}
284func NewLabel(tok token.Token, name string, stmt *Node) *Node {
285	return newNode(tok, Label, LabelNode{Name: name, Stmt: stmt}, stmt)
286}
287func NewAsmStmt(tok token.Token, code string) *Node {
288	return newNode(tok, AsmStmt, AsmStmtNode{Code: code})
289}
290func NewDirective(tok token.Token, name string) *Node {
291	return newNode(tok, Directive, DirectiveNode{Name: name})
292}
293
294// FoldConstants performs compile-time constant evaluation on the AST.
295func FoldConstants(node *Node) *Node {
296	if node == nil {
297		return nil
298	}
299
300	switch d := node.Data.(type) {
301	case AssignNode:
302		d.Rhs = FoldConstants(d.Rhs)
303		node.Data = d
304	case BinaryOpNode:
305		d.Left = FoldConstants(d.Left)
306		d.Right = FoldConstants(d.Right)
307		node.Data = d
308	case UnaryOpNode:
309		d.Expr = FoldConstants(d.Expr)
310		node.Data = d
311	case TernaryNode:
312		d.Cond = FoldConstants(d.Cond)
313		if d.Cond.Type == Number {
314			if d.Cond.Data.(NumberNode).Value != 0 {
315				return FoldConstants(d.ThenExpr)
316			}
317			return FoldConstants(d.ElseExpr)
318		}
319		d.ThenExpr = FoldConstants(d.ThenExpr)
320		d.ElseExpr = FoldConstants(d.ElseExpr)
321		node.Data = d
322	}
323
324	switch node.Type {
325	case BinaryOp:
326		d := node.Data.(BinaryOpNode)
327		if d.Left.Type == Number && d.Right.Type == Number {
328			l, r := d.Left.Data.(NumberNode).Value, d.Right.Data.(NumberNode).Value
329			var res int64
330			folded := true
331			switch d.Op {
332			case token.Plus:
333				res = l + r
334			case token.Minus:
335				res = l - r
336			case token.Star:
337				res = l * r
338			case token.And:
339				res = l & r
340			case token.Or:
341				res = l | r
342			case token.Xor:
343				res = l ^ r
344			case token.Shl:
345				res = l << uint64(r)
346			case token.Shr:
347				res = l >> uint64(r)
348			case token.EqEq:
349				if l == r {
350					res = 1
351				}
352			case token.Neq:
353				if l != r {
354					res = 1
355				}
356			case token.Lt:
357				if l < r {
358					res = 1
359				}
360			case token.Gt:
361				if l > r {
362					res = 1
363				}
364			case token.Lte:
365				if l <= r {
366					res = 1
367				}
368			case token.Gte:
369				if l >= r {
370					res = 1
371				}
372			case token.Slash:
373				if r == 0 {
374					util.Error(node.Tok, "Compile-time division by zero.")
375				}
376				res = l / r
377			case token.Rem:
378				if r == 0 {
379					util.Error(node.Tok, "Compile-time modulo by zero.")
380				}
381				res = l % r
382			default:
383				folded = false
384			}
385			if folded {
386				return NewNumber(node.Tok, res)
387			}
388		}
389	case UnaryOp:
390		d := node.Data.(UnaryOpNode)
391		if d.Expr.Type == Number {
392			val := d.Expr.Data.(NumberNode).Value
393			var res int64
394			folded := true
395			switch d.Op {
396			case token.Minus:
397				res = -val
398			case token.Complement:
399				res = ^val
400			case token.Not:
401				if val == 0 {
402					res = 1
403				}
404			default:
405				folded = false
406			}
407			if folded {
408				return NewNumber(node.Tok, res)
409			}
410		}
411	}
412
413	return node
414}