~mna/snow unlisted

snow/pkg/semantic/semantic.go -rw-r--r-- 11.1 KiB
424066c5Martin Angers doc: v0.0.5 1 year, 6 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
package semantic

import (
	"fmt"
	"sort"

	"git.sr.ht/~mna/snow/pkg/token"
)

// List of symbols with special meaning in Snow.
const (
	SelfVarName    = "self"
	MainFnName     = "main"
	ExternAttrName = "extern"
	TrueLitName    = "true"
	FalseLitName   = "false"
)

// Node is the common interface for the abstract semantic graph. Unlike the
// AST, the semantic graph doesn't care about staying close to the source
// code, it cares about making static, semantic analysis as easy as
// possible, recording as many facts as possible to reason about the
// semantics of the program. As such, things like comments have no
// place here.
//
// Once transformed to this graph, the AST isn't used anymore for the rest
// of the compilation. The only thing kept from the AST (other than the
// details of the program, of course) is the starting position of each
// node for error reporting.
type Node interface {
	Pos() token.Pos
	Scope() *Scope
}

type commonNode struct {
	pos   token.Pos
	scope *Scope
}

func (c commonNode) Pos() token.Pos { return c.pos }
func (c commonNode) Scope() *Scope  { return c.scope }

type Stmt interface {
	Node
	stmt()
}

type commonStmt struct {
	commonNode
}

func (c commonStmt) stmt() {}

type Typed interface {
	Node
	Type() Type
	TypeContext() TypeContext
	setType(T Type)
}

type Expr interface {
	Typed
	expr()
}

type commonExpr struct {
	commonNode
	typ Type
	ctx TypeContext
}

func (c commonExpr) Type() Type               { return c.typ }
func (c commonExpr) TypeContext() TypeContext { return c.ctx }
func (c commonExpr) expr()                    {}
func (c *commonExpr) setType(T Type)          { c.typ = T }

type Decl interface {
	Typed

	Ident() string
	IsGeneric() bool
	decl()
}

type GenericDecl interface {
	Decl

	// GenClause returns the GenericClause - that is, the generic parameters -
	// of the generic declaration.
	GenClause() *GenericClause

	// GenInsts returns the generic instantiations of the generic declaration.
	// It returns a slice of all generic instantiations sorted by position,
	// and a map keyed by generic instantiations with the actual types slice as
	// values. This is so that the caller can loop over the sorted slice and
	// process the map in deterministic order.
	GenInsts() ([]*GenericInst, map[*GenericInst][]Type)

	// Instantiate returns the type of the GenericDecl on which it is called once
	// instantiated by the GenericInst, with the specified Types and the map of
	// generic type to resolved type.
	Instantiate(*GenericInst, []Type, map[*GenericType]Type) Type
}

type commonDecl struct {
	commonStmt
	ident string
	typ   Type
}

func (c commonDecl) Ident() string   { return c.ident }
func (c commonDecl) Type() Type      { return c.typ }
func (c commonDecl) IsGeneric() bool { return false }
func (c commonDecl) decl()           {}
func (c *commonDecl) setType(T Type) { c.typ = T }

func AsFnDecl(n Node) *Fn {
	if fn, ok := n.(*Fn); ok {
		return fn
	}
	return nil
}

func AsVarDecl(n Node) *Var {
	if v, ok := n.(*Var); ok {
		return v
	}
	return nil
}

type Unit struct {
	Files     []*File
	FileSet   *token.FileSet  // set by Run after the translation pass
	Main      *Fn             // set during typecheck pass, only one main fn per compilation unit is allowed
	ValueUses map[*Ident]Decl // set during analysis pass, RHS uses of declarations
	commonNode
}

type File struct {
	Vars       []*Var
	Fns        []*Fn
	Structs    []*Struct
	Interfaces []*Interface
	commonNode
}

// ************** DECLARATIONS *****************

type Fn struct {
	Attrs         []*Call                 // set during translation pass
	GenericParams *GenericClause          // set during translation pass
	GenericInsts  map[*GenericInst][]Type // set during type-assign pass, each distinct instantiation is recorded here

	Params     []*Var // for Fn, Var.Ctx == immutable and Var.Value == nil
	ReturnExpr Expr   // possibly nil, not a resolved Type, but the Expr of the return
	Body       *Block // possibly nil

	MethodOf         *Struct    // set during translation pass
	AbstractMethodOf *Interface // set during translation pass
	IsRef            bool       // set during translation pass
	commonDecl
}

func (fn *Fn) TypeContext() TypeContext  { return Immutable }
func (fn *Fn) IsGeneric() bool           { return fn.GenericParams != nil }
func (fn *Fn) GenClause() *GenericClause { return fn.GenericParams }

func (fn *Fn) GenInsts() ([]*GenericInst, map[*GenericInst][]Type) {
	gis := make([]*GenericInst, 0, len(fn.GenericInsts))
	for gi := range fn.GenericInsts {
		gis = append(gis, gi)
	}
	sort.Slice(gis, func(i, j int) bool {
		l, r := gis[i], gis[j]
		return l.Pos() < r.Pos()
	})
	return gis, fn.GenericInsts
}

func (fn *Fn) Instantiate(gi *GenericInst, types []Type, resolve map[*GenericType]Type) Type {
	if fn.GenericInsts == nil {
		fn.GenericInsts = make(map[*GenericInst][]Type)
	}
	fn.GenericInsts[gi] = types
	return fn.Type().ResolveGeneric(resolve)
}

type Var struct {
	Ctx      TypeContext // only mutable or immutable for Var, set during translation pass
	TypeExpr Expr        // possibly nil, not a resolved Type, but the Expr assigned to var in `var x: int`
	Value    Expr        // possibly nil
	PropOf   *Struct     // set during translation pass if the Var is a Struct property
	ParamOf  *Fn         // set during translation pass if the Var is a function parameter
	commonDecl
}

func (v *Var) TypeContext() TypeContext { return v.Ctx }

// Struct is also used to declare the pre-defined attributes (currently just
// @extern), even though just Vars can be declared on those. This is TBD if
// it stays this way, but the current thinking is that attributes will be
// structs with some compiler magic.
type Struct struct {
	GenericParams *GenericClause          // set during translation pass
	GenericInsts  map[*GenericInst][]Type // set during type-assign pass, each distinct instantiation is recorded here

	Vars       []*Var
	Fns        []*Fn
	Structs    []*Struct
	Interfaces []*Interface

	// BodyScope is the scope for the content of the struct (unlike Struct.Scope
	// which is the scope where the struct is defined).
	BodyScope *Scope
	commonDecl
}

func (s *Struct) TypeContext() TypeContext  { return Typ }
func (s *Struct) IsGeneric() bool           { return s.GenericParams != nil }
func (s *Struct) GenClause() *GenericClause { return s.GenericParams }

func (s *Struct) GenInsts() ([]*GenericInst, map[*GenericInst][]Type) {
	gis := make([]*GenericInst, 0, len(s.GenericInsts))
	for gi := range s.GenericInsts {
		gis = append(gis, gi)
	}
	sort.Slice(gis, func(i, j int) bool {
		l, r := gis[i], gis[j]
		return l.Pos() < r.Pos()
	})
	return gis, s.GenericInsts
}

func (s *Struct) Instantiate(gi *GenericInst, types []Type, resolve map[*GenericType]Type) Type {
	if s.GenericInsts == nil {
		s.GenericInsts = make(map[*GenericInst][]Type)
	}
	s.GenericInsts[gi] = types
	return &StructType{Decl: s, Inst: types}
}

type Interface struct {
	GenericParams *GenericClause          // set during translation pass
	GenericInsts  map[*GenericInst][]Type // set during type-assign pass, each distinct instantiation is recorded here

	Methods []*Fn
	commonDecl
}

func (i *Interface) TypeContext() TypeContext  { return Typ }
func (i *Interface) IsGeneric() bool           { return i.GenericParams != nil }
func (i *Interface) GenClause() *GenericClause { return i.GenericParams }

func (i *Interface) GenInsts() ([]*GenericInst, map[*GenericInst][]Type) {
	gis := make([]*GenericInst, 0, len(i.GenericInsts))
	for gi := range i.GenericInsts {
		gis = append(gis, gi)
	}
	sort.Slice(gis, func(i, j int) bool {
		l, r := gis[i], gis[j]
		return l.Pos() < r.Pos()
	})
	return gis, i.GenericInsts
}

func (i *Interface) Instantiate(gi *GenericInst, types []Type, resolve map[*GenericType]Type) Type {
	if i.GenericInsts == nil {
		i.GenericInsts = make(map[*GenericInst][]Type)
	}
	i.GenericInsts[gi] = types
	return &InterfaceType{Decl: i, Inst: types}
}

type GenericElem struct {
	commonDecl
}

func (g *GenericElem) TypeContext() TypeContext { return Typ }

// ************** STATEMENTS *****************

type Block struct {
	Stmts []Stmt
	commonStmt
}

type Return struct {
	Value Expr
	commonStmt
}

type Assign struct {
	Left  Expr
	Op    token.Token
	Right Expr
	commonStmt
}

type ExprStmt struct {
	Value Expr
	commonStmt
}

type If struct {
	Conds []Expr
	Body  *Block
	Else  Stmt // *If or *Block
	commonStmt
}

type Guard struct {
	Conds []Expr
	Else  *Block
	commonStmt
}

// ************** EXPRESSIONS *****************

type FnTypeExpr struct {
	Params []Expr
	Return Expr
	commonExpr
}

type TupleTypeExpr struct {
	Fields []Expr
	commonExpr
}

type TupleVal struct {
	Values []Expr
	commonExpr
}

type Binary struct {
	Left  Expr
	Op    token.Token
	Right Expr
	commonExpr
}

type Unary struct {
	Op    token.Token
	Right Expr
	commonExpr
}

type Paren struct {
	Value Expr
	commonExpr
}

// Call represents any call-like expression: function call (Fun is an
// expression of function type), struct initializer (Fun is the struct
// identifier) and attribute (Fun is the attribute identifier).
type Call struct {
	Fun    Expr
	Labels []string
	Args   []Expr

	InitOf *Struct // set during typeassign pass if this is a struct init call (including attributes)
	AttrOf *Fn     // set during translation pass if attribute on a function
	commonExpr
}

type Selector struct {
	Left Expr
	Sel  Expr // can be *Ident or *GenericInst
	commonExpr
}

type LitString struct {
	Repr  string
	Value string // filled in the translation pass, the actual string value
	commonExpr
}

type LitInt struct {
	Repr  string
	Value int // filled in the translation pass, the actual integer value
	commonExpr
}

type GenericInst struct {
	GenericDecl *Ident
	TypeExprs   []Expr
	commonExpr
}

type Ident struct {
	Name  string
	Index int  // filled in the translation pass, -1 for non-tuple identifiers
	Ref   Decl // filled in the typeassign pass, can still be nil for Tuple fields
	commonExpr
}

// added in the typecheck pass where implicit conversions take place, the Value
// is the expression being converted, and the Type of this node is the target
// type.
type ImplicitConv struct {
	Value Expr
	commonExpr
}

// ************** SUPPORTING TYPES *****************

type GenericClause struct {
	Explicit bool
	Elems    []*GenericElem
}

// TypeIdentString returns a string representation of n where the type is
// printed as well as the identifier if it is a Decl or an *Ident.
func TypeIdentString(n Node) string {
	var lbl string
	switch n := n.(type) {
	case Decl:
		lbl = n.Ident()
	case *Ident:
		lbl = n.Name
	case *Selector:
		return "_." + TypeIdentString(n.Sel)
	case *GenericInst:
		lbl = n.GenericDecl.Name + "[...]"
	}
	if lbl == "" {
		return fmt.Sprintf("%T", n)
	}
	return fmt.Sprintf("%T %s", n, lbl)
}

// Values returns the argument values of a Call keyed by their label.
// It should only be called for attributes (Call with AttrOf!=nil),
// as those have compile-time values as arguments and require labels.
func (c *Call) Values() map[string]interface{} {
	vals := make(map[string]interface{}, len(c.Args))
	for i, arg := range c.Args {
		lbl := c.Labels[i]

		var val interface{}
		switch arg := arg.(type) {
		case *LitInt:
			val = arg.Value
		case *LitString:
			val = arg.Value
		}
		vals[lbl] = val
	}
	return vals
}