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}