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