1 // Copyright 2014 Wouter van Oortmerssen. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 namespace lobster {
16
17 struct LValContext {
18 // For now, only: ident ( . field )*.
19 const SpecIdent *sid;
20 vector<SharedField *> derefs;
LValContextLValContext21 LValContext(const Node &n) {
22 auto t = &n;
23 while (auto dot = Is<Dot>(t)) {
24 derefs.insert(derefs.begin(), dot->fld);
25 t = dot->children[0];
26 }
27 auto idr = Is<IdentRef>(t);
28 sid = idr ? idr->sid : nullptr;
29 }
IsValidLValContext30 bool IsValid() { return sid; }
DerefsEqualLValContext31 bool DerefsEqual(const LValContext &o) {
32 if (derefs.size() != o.derefs.size()) return false;
33 for (auto &shf : derefs) if (shf != o.derefs[&shf - &derefs[0]]) return false;
34 return true;
35 }
IsPrefixLValContext36 bool IsPrefix(const LValContext &o) {
37 if (sid != o.sid || derefs.size() < o.derefs.size()) return false;
38 for (auto &shf : o.derefs) if (shf != derefs[&shf - &o.derefs[0]]) return false;
39 return true;
40 }
NameLValContext41 string Name() {
42 auto s = sid ? sid->id->name : "<invalid>";
43 for (auto &shf : derefs) {
44 s += ".";
45 s += shf->name;
46 }
47 return s;
48 }
49 };
50
51 struct FlowItem : LValContext {
52 TypeRef old, now;
FlowItemFlowItem53 FlowItem(const Node &n, TypeRef type) : LValContext(n), old(n.exptype), now(type) {}
54 };
55
56 struct Borrow : LValContext {
57 int refc = 1; // Number of outstanding borrowed values. While >0 can't assign.
BorrowBorrow58 Borrow(const Node &n) : LValContext(n) {}
59 };
60
61 struct TypeChecker {
62 Parser &parser;
63 SymbolTable &st;
64 struct Scope { SubFunction *sf; const Node *call_context; };
65 vector<Scope> scopes, named_scopes;
66 vector<FlowItem> flowstack;
67 vector<Borrow> borrowstack;
68
TypeCheckerTypeChecker69 TypeChecker(Parser &_p, SymbolTable &_st, size_t retreq) : parser(_p), st(_st) {
70 // FIXME: this is unfriendly.
71 if (!st.RegisterDefaultTypes())
72 TypeError("cannot find standard types (from stdtype.lobster)", *parser.root);
73 for (auto &udt : st.udttable) {
74 if (udt->generics.empty()) {
75 // NOTE: all users of sametype will only act on it if it is numeric, since
76 // otherwise it would a scalar field to become any without boxing.
77 // Much of the implementation relies on these being 2-4 component vectors, so
78 // deny this functionality to any other structs.
79 if (udt->fields.size() >= 2 && udt->fields.size() <= 4) {
80 udt->sametype = udt->fields.v[0].type;
81 for (size_t i = 1; i < udt->fields.size(); i++) {
82 // Can't use Union here since it will bind variables, use simplified alternative:
83 if (!ExactType(udt->fields.v[i].type, udt->sametype)) {
84 udt->sametype = type_undefined;
85 break;
86 }
87 }
88 }
89 // Update the type to the correct struct type.
90 if (udt->is_struct) {
91 for (auto &field : udt->fields.v) {
92 if (IsRefNil(field.type->t)) {
93 udt->hasref = true;
94 break;
95 }
96 }
97 const_cast<ValueType &>(udt->thistype.t) =
98 udt->hasref ? V_STRUCT_R : V_STRUCT_S;
99 }
100 }
101 if (udt->superclass) {
102 // If this type has fields inherited from the superclass that refer to the
103 // superclass, make it refer to this type instead. There may be corner cases where
104 // this is not what you want, but generally you do.
105 for (auto &field : make_span(udt->fields.v.data(),
106 udt->superclass->fields.v.size())) {
107 PromoteStructIdx(field.type, udt->superclass, udt);
108 }
109 }
110 for (auto u = udt; u; u = u->superclass) u->subudts.push_back(udt);
111 }
112 AssertIs<Call>(parser.root)->sf->reqret = retreq;
113 TT(parser.root, retreq, LT_KEEP);
114 AssertIs<Call>(parser.root);
115 CleanUpFlow(0);
116 assert(borrowstack.empty());
117 assert(scopes.empty());
118 assert(named_scopes.empty());
119 Stats();
120 }
121
122 // Needed for any sids in cloned code.
UpdateCurrentSidTypeChecker123 void UpdateCurrentSid(SpecIdent *&sid) { sid = sid->Current(); }
RevertCurrentSidTypeChecker124 void RevertCurrentSid(SpecIdent *&sid) { sid->Current() = sid; }
125
PromoteStructIdxTypeChecker126 void PromoteStructIdx(TypeRef &type, const UDT *olds, const UDT *news) {
127 auto u = type;
128 while (u->Wrapped()) u = u->Element();
129 if (IsUDT(u->t) && u->udt == olds) type = PromoteStructIdxRec(type, news);
130 }
131
PromoteStructIdxRecTypeChecker132 TypeRef PromoteStructIdxRec(TypeRef type, const UDT *news) {
133 return type->Wrapped()
134 ? st.Wrap(PromoteStructIdxRec(type->sub, news), type->t)
135 : &news->thistype;
136 }
137
138 string TypedArg(const GenericArgs &args, size_t i, bool withtype = true) {
139 string s;
140 s += args.GetName(i);
141 if (args.GetType(i)->t != V_ANY && withtype)
142 s += ":" + TypeName(args.GetType(i));
143 return s;
144 }
145
146 string Signature(const GenericArgs &args, bool withtype = true) {
147 string s = "(";
148 for (size_t i = 0; i < args.size(); i++) {
149 if (i) s += ", ";
150 s += TypedArg(args, i, withtype);
151 }
152 return s + ")";
153 }
154
SignatureTypeChecker155 string Signature(const UDT &udt) {
156 return udt.name + Signature(udt.fields);
157 }
158 string Signature(const SubFunction &sf, bool withtype = true) {
159 return sf.parent->name + Signature(sf.args, withtype);
160 }
SignatureTypeChecker161 string Signature(const NativeFun &nf) {
162 return nf.name + Signature(nf.args);
163 }
164
165 string SignatureWithFreeVars(const SubFunction &sf, set<Ident *> *already_seen,
166 bool withtype = true) {
167 string s = Signature(sf, withtype) + " { ";
168 for (auto [i, freevar] : enumerate(sf.freevars.v)) {
169 if (freevar.type->t != V_FUNCTION &&
170 !freevar.sid->id->static_constant &&
171 (!already_seen || already_seen->find(freevar.sid->id) == already_seen->end())) {
172 s += TypedArg(sf.freevars, i) + " ";
173 if (already_seen) already_seen->insert(freevar.sid->id);
174 }
175 }
176 s += "}";
177 return s;
178 }
179
ArgNameTypeChecker180 string ArgName(size_t i) {
181 switch (i) {
182 case 0: return "1st";
183 case 1: return "2nd";
184 case 2: return "3rd";
185 default: return cat(i + 1, "th");
186 }
187 }
188
NiceNameTypeChecker189 string_view NiceName(const Node &n) {
190 if (auto call = Is<Call>(n))
191 if (!call->sf->parent->anonymous)
192 return call->sf->parent->name;
193 if (auto idr = Is<IdentRef>(n))
194 return idr->sid->id->name;
195 return n.Name();
196 }
197
198 void TypeError(string_view required, TypeRef got, const Node &n, string_view argname = "",
199 string_view context = "") {
200 TypeError(cat("\"", (context.size() ? context : NiceName(n)), "\" ",
201 (argname.size() ? "(" + argname + " argument) " : ""),
202 "requires type: ", required, ", got: ", TypeName(got)), n);
203 }
204
TypeErrorTypeChecker205 void TypeError(string err, const Node &n) {
206 set<Ident *> already_seen;
207 if (!scopes.empty())
208 for (auto scope : reverse(scopes)) {
209 if (scope.sf == st.toplevel) continue;
210 err += "\n in " + parser.lex.Location(scope.call_context->line) + ": ";
211 err += SignatureWithFreeVars(*scope.sf, &already_seen);
212 for (auto dl : scope.sf->body->children) {
213 if (auto def = Is<Define>(dl)) {
214 for (auto p : def->sids) {
215 err += ", " + p.first->id->name + ":" + TypeName(p.first->type);
216 }
217 }
218 }
219 }
220 parser.Error(err, &n);
221 }
222
NoStructTypeChecker223 void NoStruct(const Node &n, string_view context) {
224 if (IsStruct(n.exptype->t)) TypeError("struct value cannot be used in: " + context, n);
225 }
226
NatCallErrorTypeChecker227 void NatCallError(string_view errstr, const NativeFun *nf, const NativeCall &callnode) {
228 auto err = errstr + nf->name;
229 err += "\n got:";
230 for (auto c : callnode.children) {
231 err += " " + TypeName(c->exptype);
232 }
233 for (auto cnf = nf->first; cnf; cnf = cnf->overloads) {
234 err += "\n overload: " + Signature(*cnf);
235 }
236 TypeError(err, callnode);
237 }
238
NewTypeVarTypeChecker239 TypeRef NewTypeVar() {
240 auto var = st.NewType();
241 *var = Type(V_VAR);
242 // Vars store a cycle of all vars its been unified with, starting with itself.
243 var->sub = var;
244 return var;
245 }
246
NewNilTypeVarTypeChecker247 TypeRef NewNilTypeVar() {
248 auto nil = st.NewType();
249 *nil = Type(V_NIL);
250 nil->sub = &*NewTypeVar();
251 return nil;
252 }
253
NewTupleTypeChecker254 TypeRef NewTuple(size_t sz) {
255 auto type = st.NewType();
256 *type = Type(V_TUPLE);
257 type->tup = new vector<Type::TupleElem>(sz);
258 st.tuplelist.push_back(type->tup);
259 return type;
260 }
261
UnifyVarTypeChecker262 void UnifyVar(TypeRef type, TypeRef hasvar) {
263 // Typically Type is const, but this is the one place we overwrite them.
264 // Type objects that are V_VAR are seperate heap instances, so overwriting them has no
265 // side-effects on non-V_VAR Type instances.
266 assert(hasvar->t == V_VAR);
267 if (type->t == V_VAR) {
268 // Combine two cyclic linked lists.. elegant!
269 swap((Type *&)hasvar->sub, (Type *&)type->sub);
270 } else {
271 auto v = hasvar;
272 do { // Loop thru all vars in unification cycle.
273 auto next = v->sub;
274 *(Type *)&*v = *type; // Overwrite Type struct!
275 v = next;
276 } while (&*v != &*hasvar); // Force TypeRef pointer comparison.
277 }
278 }
279
280 bool ConvertsTo(TypeRef type, TypeRef sub, bool coercions, bool unifications = true) {
281 if (sub == type) return true;
282 if (type->t == V_VAR) {
283 if (unifications) UnifyVar(sub, type);
284 return true;
285 }
286 switch (sub->t) {
287 case V_VOID: return coercions;
288 case V_VAR: UnifyVar(type, sub); return true;
289 case V_FLOAT: return type->t == V_INT && coercions;
290 case V_INT: return (type->t == V_TYPEID && coercions) ||
291 (type->t == V_INT && !sub->e);
292 case V_STRING: return coercions && IsRuntimePrintable(type->t);
293 case V_FUNCTION: return type->t == V_FUNCTION && !sub->sf;
294 case V_NIL: return (type->t == V_NIL &&
295 ConvertsTo(type->Element(), sub->Element(), false,
296 unifications)) ||
297 (!type->Numeric() && type->t != V_VOID && !IsStruct(type->t) &&
298 ConvertsTo(type, sub->Element(), false, unifications)) ||
299 (type->Numeric() && // For builtins.
300 ConvertsTo(type, sub->Element(), false, unifications));
301 case V_VECTOR: return (type->t == V_VECTOR &&
302 ConvertsTo(type->Element(), sub->Element(), false,
303 unifications));
304 case V_CLASS: return type->t == V_CLASS &&
305 st.SuperDistance(sub->udt, type->udt) >= 0;
306 case V_STRUCT_R:
307 case V_STRUCT_S: return type->t == sub->t && type->udt == sub->udt;
308 case V_COROUTINE: return type->t == V_COROUTINE &&
309 (sub->sf == type->sf ||
310 (!sub->sf && type->sf && ConvertsTo(type->sf->coresumetype,
311 NewNilTypeVar(), false)));
312 case V_TUPLE: return type->t == V_TUPLE && ConvertsToTuple(*type->tup, *sub->tup);
313 default: return false;
314 }
315 }
316
ConvertsToTupleTypeChecker317 bool ConvertsToTuple(const vector<Type::TupleElem> &ttup, const vector<Type::TupleElem> &stup) {
318 if (ttup.size() != stup.size()) return false;
319 for (auto [i, te] : enumerate(ttup))
320 if (!ConvertsTo(te.type, stup[i].type, false))
321 return false;
322 return true;
323 }
324
UnionTypeChecker325 TypeRef Union(TypeRef at, TypeRef bt, bool coercions, const Node *err) {
326 if (ConvertsTo(at, bt, coercions)) return bt;
327 if (ConvertsTo(bt, at, coercions)) return at;
328 if (at->t == V_VECTOR && bt->t == V_VECTOR) {
329 auto et = Union(at->Element(), bt->Element(), false, err);
330 return st.Wrap(et, V_VECTOR);
331 }
332 if (at->t == V_CLASS && bt->t == V_CLASS) {
333 auto sstruc = st.CommonSuperType(at->udt, bt->udt);
334 if (sstruc) return &sstruc->thistype;
335 }
336 if (err)
337 TypeError(cat(TypeName(at), " and ", TypeName(bt), " have no common supertype"), *err);
338 return type_undefined;
339 }
340
ExactTypeTypeChecker341 bool ExactType(TypeRef a, TypeRef b) {
342 return a == b; // Not inlined for documentation purposes.
343 }
344
MakeStringTypeChecker345 void MakeString(Node *&a, Lifetime orig_recip) {
346 assert(a->exptype->t != V_STRING);
347 DecBorrowers(a->lt, *a);
348 a = new ToString(a->line, a);
349 a->exptype = type_string;
350 a->lt = LT_KEEP;
351 // Make sure whatever lifetime a was typechecked at is preserved.
352 AdjustLifetime(a, orig_recip);
353 }
354
MakeBoolTypeChecker355 void MakeBool(Node *&a) {
356 DecBorrowers(a->lt, *a);
357 if (a->exptype->t == V_INT) return;
358 a = new ToBool(a->line, a);
359 a->exptype = &st.default_bool_type->thistype;
360 a->lt = LT_ANY;
361 }
362
MakeIntTypeChecker363 void MakeInt(Node *&a) {
364 auto ti = new ToInt(a->line, a);
365 ti->exptype = type_int;
366 ti->lt = a->lt;
367 a = ti;
368 }
369
MakeFloatTypeChecker370 void MakeFloat(Node *&a) {
371 auto tf = new ToFloat(a->line, a);
372 tf->exptype = type_float;
373 tf->lt = a->lt;
374 a = tf;
375 }
376
MakeLifetimeTypeChecker377 void MakeLifetime(Node *&n, Lifetime lt, uint64_t incref, uint64_t decref) {
378 auto tlt = new ToLifetime(n->line, n, incref, decref);
379 tlt->exptype = n->exptype;
380 tlt->lt = lt;
381 n = tlt;
382 }
383
StorageTypeTypeChecker384 void StorageType(TypeRef type, const Node &context) {
385 if (type->HasValueType(V_VOID)) TypeError("cannot store value of type void", context);
386 }
387
SubTypeLRTypeChecker388 void SubTypeLR(TypeRef sub, BinOp &n) {
389 SubType(n.left, sub, "left", n);
390 SubType(n.right, sub, "right", n);
391 }
392
SubTypeTypeChecker393 void SubType(Node *&a, TypeRef sub, string_view argname, const Node &context) {
394 SubType(a, sub, argname, NiceName(context));
395 }
SubTypeTypeChecker396 void SubType(Node *&a, TypeRef sub, string_view argname, string_view context) {
397 if (ConvertsTo(a->exptype, sub, false)) return;
398 switch (sub->t) {
399 case V_FLOAT:
400 if (a->exptype->t == V_INT) {
401 MakeFloat(a);
402 return;
403 }
404 break;
405 case V_INT:
406 if (a->exptype->t == V_TYPEID) {
407 MakeInt(a);
408 return;
409 }
410 break;
411 case V_FUNCTION:
412 if (a->exptype->IsFunction() && sub->sf) {
413 // See if these functions can be made compatible. Specialize and typecheck if
414 // needed.
415 auto sf = a->exptype->sf;
416 auto ss = sub->sf;
417 if (!ss->parent->istype)
418 TypeError("dynamic function value can only be passed to declared "
419 "function type", *a);
420 if (sf->args.v.size() != ss->args.v.size()) break;
421 for (auto [i, arg] : enumerate(sf->args.v)) {
422 // Specialize to the function type, if requested.
423 if (!sf->typechecked && arg.flags & AF_GENERIC) {
424 arg.type = ss->args.v[i].type;
425 }
426 // Note this has the args in reverse: function args are contravariant.
427 if (!ConvertsTo(ss->args.v[i].type, arg.type, false))
428 goto error;
429 // This function must be compatible with all other function values that
430 // match this type, so we fix lifetimes to LT_BORROW.
431 // See typechecking of istype calls.
432 arg.sid->lt = LT_BORROW;
433 }
434 if (sf->typechecked) {
435 if (sf->reqret != ss->reqret) goto error;
436 } else {
437 sf->reqret = ss->reqret;
438 }
439 sf->isdynamicfunctionvalue = true;
440 TypeCheckFunctionDef(*sf, *sf->body);
441 // Covariant again.
442 if (sf->returntype->NumValues() != ss->returntype->NumValues() ||
443 !ConvertsTo(sf->returntype, ss->returntype, false))
444 break;
445 // Parser only parses one ret type for function types.
446 assert(ss->returntype->NumValues() <= 1);
447 return;
448 }
449 break;
450 default:
451 ;
452 }
453 error:
454 TypeError(TypeName(sub), a->exptype, *a, argname, context);
455 }
456
457 void SubTypeT(TypeRef type, TypeRef sub, const Node &n, string_view argname,
458 string_view context = {}) {
459 if (!ConvertsTo(type, sub, false))
460 TypeError(TypeName(sub), type, n, argname, context);
461 }
462
MathCheckVectorTypeChecker463 bool MathCheckVector(TypeRef &type, Node *&left, Node *&right) {
464 TypeRef ltype = left->exptype;
465 TypeRef rtype = right->exptype;
466 // Special purpose check for vector * scalar etc.
467 if (ltype->t == V_STRUCT_S && rtype->Numeric()) {
468 auto etype = ltype->udt->sametype;
469 if (etype->Numeric()) {
470 if (etype->t == V_INT) {
471 // Don't implicitly convert int vectors to float.
472 if (rtype->t == V_FLOAT) return false;
473 } else {
474 if (rtype->t == V_INT) SubType(right, type_float, "right", *right);
475 }
476 type = <ype->udt->thistype;
477 return true;
478 }
479 }
480 return false;
481 }
482
MathCheckTypeChecker483 const char *MathCheck(TypeRef &type, BinOp &n, bool &unionchecked,
484 bool typechangeallowed) {
485 if (Is<Mod>(&n) || Is<ModEq>(&n)) {
486 if (type->t != V_INT) return "int";
487 } else {
488 if (!type->Numeric() && type->t != V_VECTOR && !IsUDT(type->t)) {
489 if (MathCheckVector(type, n.left, n.right)) {
490 unionchecked = true;
491 return nullptr;
492 }
493 if (Is<Plus>(&n) || Is<PlusEq>(&n)) {
494 auto ltype = n.left->exptype;
495 auto rtype = n.right->exptype;
496 if (ltype->t == V_STRING) {
497 if (rtype->t != V_STRING) {
498 // Anything can be added to a string on the right (because of +=).
499 MakeString(n.right, LT_BORROW);
500 // Make sure the overal type is string.
501 type = type_string;
502 unionchecked = true;
503 }
504 } else if (rtype->t == V_STRING && ltype->t != V_STRING && typechangeallowed) {
505 // Only if not in a +=
506 MakeString(n.left, LT_BORROW);
507 type = type_string;
508 unionchecked = true;
509 } else {
510 return "numeric/string/vector/struct";
511 }
512 } else {
513 return "numeric/vector/struct";
514 }
515 }
516 }
517 return nullptr;
518 }
519
MathErrorTypeChecker520 void MathError(TypeRef &type, BinOp &n, bool &unionchecked, bool typechangeallowed) {
521 auto err = MathCheck(type, n, unionchecked, typechangeallowed);
522 if (err) {
523 if (MathCheck(n.left->exptype, n, unionchecked, typechangeallowed))
524 TypeError(err, n.left->exptype, n, "left");
525 if (MathCheck(n.right->exptype, n, unionchecked, typechangeallowed))
526 TypeError(err, n.right->exptype, n, "right");
527 TypeError("can\'t use \"" +
528 NiceName(n) +
529 "\" on " +
530 TypeName(n.left->exptype) +
531 " and " +
532 TypeName(n.right->exptype), n);
533 }
534 }
535
TypeCheckMathOpTypeChecker536 void TypeCheckMathOp(BinOp &n) {
537 TT(n.left, 1, LT_BORROW);
538 TT(n.right, 1, LT_BORROW);
539 n.exptype = Union(n.left->exptype, n.right->exptype, true, nullptr);
540 bool unionchecked = false;
541 MathError(n.exptype, n, unionchecked, true);
542 if (!unionchecked) SubTypeLR(n.exptype, n);
543 DecBorrowers(n.left->lt, n);
544 DecBorrowers(n.right->lt, n);
545 n.lt = LT_KEEP;
546 }
547
TypeCheckMathOpEqTypeChecker548 void TypeCheckMathOpEq(BinOp &n) {
549 TT(n.left, 1, LT_BORROW);
550 DecBorrowers(n.left->lt, n);
551 TT(n.right, 1, LT_BORROW);
552 CheckLval(n.left);
553 n.exptype = n.left->exptype;
554 if (!MathCheckVector(n.exptype, n.left, n.right)) {
555 bool unionchecked = false;
556 MathError(n.exptype, n, unionchecked, false);
557 if (!unionchecked) SubType(n.right, n.exptype, "right", n);
558 }
559 // This really does: "left = left op right" the result of op is LT_KEEP, which is
560 // implicit, so the left var must be LT_KEEP as well. This is ensured elsewhere because
561 // all !single_assignment vars are LT_KEEP.
562 assert(!Is<IdentRef>(n.left) || LifetimeType(Is<IdentRef>(n.left)->sid->lt) != LT_BORROW);
563 DecBorrowers(n.right->lt, n);
564 n.lt = PushBorrow(n.left);
565 }
566
TypeCheckCompTypeChecker567 void TypeCheckComp(BinOp &n) {
568 TT(n.left, 1, LT_BORROW);
569 TT(n.right, 1, LT_BORROW);
570 n.exptype = &st.default_bool_type->thistype;
571 auto u = Union(n.left->exptype, n.right->exptype, true, nullptr);
572 if (!u->Numeric() && u->t != V_STRING) {
573 if (Is<Equal>(&n) || Is<NotEqual>(&n)) {
574 // Comparison with one result, but still by value for structs.
575 if (u->t != V_VECTOR && !IsUDT(u->t) && u->t != V_NIL && u->t != V_FUNCTION)
576 TypeError(TypeName(n.left->exptype), n.right->exptype, n, "right-hand side");
577 } else {
578 // Comparison vector op: vector inputs, vector out.
579 if (u->t == V_STRUCT_S && u->udt->sametype->Numeric()) {
580 n.exptype = st.default_int_vector_types[0][u->udt->fields.size()];
581 } else if (MathCheckVector(n.exptype, n.left, n.right)) {
582 n.exptype = st.default_int_vector_types[0][n.exptype->udt->fields.size()];
583 // Don't do SubTypeLR since type already verified and `u` not
584 // appropriate anyway.
585 goto out;
586 } else {
587 TypeError(n.Name() + " doesn\'t work on " + TypeName(n.left->exptype) +
588 " and " + TypeName(n.right->exptype), n);
589 }
590 }
591 }
592 SubTypeLR(u, n);
593 out:
594 DecBorrowers(n.left->lt, n);
595 DecBorrowers(n.right->lt, n);
596 n.lt = LT_KEEP;
597 }
598
TypeCheckBitOpTypeChecker599 void TypeCheckBitOp(BinOp &n) {
600 TT(n.left, 1, LT_BORROW);
601 TT(n.right, 1, LT_BORROW);
602 auto u = Union(n.left->exptype, n.right->exptype, true, nullptr);
603 if (u->t != V_INT) u = type_int;
604 SubTypeLR(u, n);
605 n.exptype = u;
606 DecBorrowers(n.left->lt, n);
607 DecBorrowers(n.right->lt, n);
608 n.lt = LT_ANY;
609 }
610
TypeCheckPlusPlusTypeChecker611 void TypeCheckPlusPlus(Unary &n) {
612 TT(n.child, 1, LT_BORROW);
613 CheckLval(n.child);
614 n.exptype = n.child->exptype;
615 if (!n.exptype->Numeric())
616 TypeError("numeric", n.exptype, n);
617 n.lt = n.child->lt;
618 }
619
TopScopeTypeChecker620 SubFunction *TopScope(vector<Scope> &_scopes) {
621 return _scopes.empty() ? nullptr : _scopes.back().sf;
622 }
623
624 void RetVal(TypeRef type, SubFunction *sf, const Node &err, bool register_return = true) {
625 if (register_return) {
626 for (auto isc : reverse(scopes)) {
627 if (isc.sf->parent == sf->parent) break;
628 // isc.sf is a function in the call chain between the return statement and the
629 // function it is returning from. Since we're affecting the return type of the
630 // function we're returning from, if it gets specialized but a function along the
631 // call chain (isc.sf) does not, we must ensure that return type affects the second
632 // specialization.
633 // We do this by tracking return types, and replaying them when a function gets
634 // reused.
635 // A simple test case is in return_from unit test, and recursive_exception is also
636 // affected.
637 isc.sf->reuse_return_events.push_back({ sf, type });
638 }
639 }
640 sf->num_returns++;
641 if (sf->fixedreturntype.Null()) {
642 if (sf->reqret) {
643 // If this is a recursive call we must be conservative because there may already
644 // be callers dependent on the return type so far, so any others must be subtypes.
645 if (!sf->isrecursivelycalled) {
646 // We can safely generalize the type if needed, though not with coercions.
647 sf->returntype = Union(type, sf->returntype, false, &err);
648 }
649 } else {
650 // The caller doesn't want return values.
651 sf->returntype = type_void;
652 }
653 }
654 }
655
TypeCheckFunctionDefTypeChecker656 void TypeCheckFunctionDef(SubFunction &sf, const Node &call_context) {
657 if (sf.typechecked) return;
658 LOG_DEBUG("function start: ", SignatureWithFreeVars(sf, nullptr));
659 Scope scope;
660 scope.sf = &sf;
661 scope.call_context = &call_context;
662 scopes.push_back(scope);
663 //for (auto &ns : named_scopes) LOG_DEBUG("named scope: ", ns.sf->parent->name);
664 if (!sf.parent->anonymous) named_scopes.push_back(scope);
665 sf.typechecked = true;
666 for (auto &arg : sf.args.v) StorageType(arg.type, call_context);
667 for (auto &fv : sf.freevars.v) UpdateCurrentSid(fv.sid);
668 auto backup_vars = [&](ArgVector &in, ArgVector &backup) {
669 for (auto [i, arg] : enumerate(in.v)) {
670 // Need to not overwrite nested/recursive calls. e.g. map(): map(): ..
671 backup.v[i].sid = arg.sid->Current();
672 arg.sid->type = arg.type;
673 RevertCurrentSid(arg.sid);
674 }
675 };
676 auto backup_args = sf.args; backup_vars(sf.args, backup_args);
677 auto backup_locals = sf.locals; backup_vars(sf.locals, backup_locals);
678 auto enter_scope = [&](const Arg &var) {
679 IncBorrowers(var.sid->lt, call_context);
680 };
681 for (auto &arg : sf.args.v) enter_scope(arg);
682 for (auto &local : sf.locals.v) enter_scope(local);
683 sf.coresumetype = sf.iscoroutine ? NewNilTypeVar() : type_undefined;
684 sf.returntype = sf.reqret
685 ? (!sf.fixedreturntype.Null() ? sf.fixedreturntype : NewTypeVar())
686 : type_void;
687 auto start_borrowed_vars = borrowstack.size();
688 auto start_promoted_vars = flowstack.size();
689 TypeCheckList(sf.body, true, 0, LT_ANY);
690 CleanUpFlow(start_promoted_vars);
691 if (!sf.num_returns) {
692 if (!sf.fixedreturntype.Null() && sf.fixedreturntype->t != V_VOID)
693 TypeError("missing return statement", *sf.body->children.back());
694 sf.returntype = type_void;
695 }
696 // Let variables go out of scope in reverse order of declaration.
697 auto exit_scope = [&](const Arg &var) {
698 DecBorrowers(var.sid->lt, call_context);
699 };
700 for (auto &local : reverse(sf.locals.v)) exit_scope(local);
701 for (auto &arg : sf.args.v) exit_scope(arg); // No order.
702 while (borrowstack.size() > start_borrowed_vars) {
703 auto &b = borrowstack.back();
704 if (b.refc) {
705 TypeError(cat("variable ", b.Name(), " still has ", b.refc,
706 " borrowers"), *sf.body->children.back());
707 }
708 borrowstack.pop_back();
709 }
710 for (auto &back : backup_args.v) RevertCurrentSid(back.sid);
711 for (auto &back : backup_locals.v) RevertCurrentSid(back.sid);
712 if (sf.returntype->HasValueType(V_VAR)) {
713 // If this function return something with a variable in it, then it likely will get
714 // bound by the caller. If the function then gets reused without specialization, it will
715 // get the wrong return type, so we force specialization for subsequent calls of this
716 // function. FIXME: check in which cases this is typically true, since its expensive
717 // if done without reason.
718 sf.mustspecialize = true;
719 }
720 if (!sf.parent->anonymous) named_scopes.pop_back();
721 scopes.pop_back();
722 LOG_DEBUG("function end ", Signature(sf), " returns ",
723 TypeName(sf.returntype));
724 }
725
FindStructSpecializationTypeChecker726 UDT *FindStructSpecialization(UDT *given, const Constructor *cons) {
727 // This code is somewhat similar to function specialization, but not similar enough to
728 // share. If they're all typed, we bail out early:
729 if (given->generics.empty()) return given;
730 auto head = given->first;
731 assert(cons->Arity() == head->fields.size());
732 // Now find a match:
733 UDT *best = nullptr;
734 int bestmatch = 0;
735 for (auto udt = head->next; udt; udt = udt->next) {
736 int nmatches = 0;
737 for (auto [i, arg] : enumerate(cons->children)) {
738 auto &field = udt->fields.v[i];
739 if (field.genericref >= 0) {
740 if (ExactType(arg->exptype, field.type)) nmatches++;
741 else break;
742 }
743 }
744 if (nmatches > bestmatch) {
745 bestmatch = nmatches;
746 best = udt;
747 }
748 }
749 if (best) return best;
750 string s;
751 for (auto &arg : cons->children) s += " " + TypeName(arg->exptype);
752 TypeError("no specialization of " + given->first->name + " matches these types:" + s,
753 *cons);
754 return nullptr;
755 }
756
757 void CheckIfSpecialization(UDT *spec_struc, TypeRef given, const Node &n,
758 string_view argname, string_view req = {},
759 bool subtypeok = false, string_view context = {}) {
760 auto givenu = given->UnWrapped();
761 if (!IsUDT(given->t) ||
762 (!spec_struc->IsSpecialization(givenu->udt) &&
763 (!subtypeok || st.SuperDistance(spec_struc, givenu->udt) < 0))) {
764 TypeError(req.data() ? req : spec_struc->name, given, n, argname, context);
765 }
766 }
767
CheckGenericArgTypeChecker768 void CheckGenericArg(TypeRef otype, TypeRef argtype, string_view argname, const Node &n,
769 string_view context) {
770 // Check if argument is a generic struct type, or wrapped in vector/nilable.
771 if (otype->t != V_ANY) {
772 auto u = otype->UnWrapped();
773 assert(IsUDT(u->t));
774 if (otype->EqNoIndex(*argtype)) {
775 CheckIfSpecialization(u->udt, argtype, n, argname, TypeName(otype), true,
776 context);
777 } else {
778 // This likely generates either an error, or contains an unbound var that will get
779 // bound.
780 SubTypeT(argtype, otype, n, argname, context);
781 //TypeError(TypeName(otype), argtype, n, argname, context);
782 }
783 }
784 }
785
FreeVarsSameAsCurrentTypeChecker786 bool FreeVarsSameAsCurrent(const SubFunction &sf, bool prespecialize) {
787 for (auto &freevar : sf.freevars.v) {
788 //auto atype = Promote(freevar.id->type);
789 if (freevar.sid != freevar.sid->Current() ||
790 !ExactType(freevar.type, freevar.sid->Current()->type)) {
791 (void)prespecialize;
792 assert(prespecialize ||
793 freevar.sid == freevar.sid->Current() ||
794 (freevar.sid && freevar.sid->Current()));
795 return false;
796 }
797 //if (atype->t == V_FUNCTION) return false;
798 }
799 return true;
800 }
801
CloneFunctionTypeChecker802 SubFunction *CloneFunction(SubFunction *csf, int i) {
803 LOG_DEBUG("cloning: ", csf->parent->name);
804 auto sf = st.CreateSubFunction();
805 sf->SetParent(*csf->parent, csf->parent->overloads[i]);
806 // Any changes here make sure this corresponds what happens in Inline() in the optimizer.
807 st.CloneIds(*sf, *csf);
808 sf->body = (List *)csf->body->Clone();
809 sf->freevarchecked = true;
810 sf->fixedreturntype = csf->fixedreturntype;
811 sf->returntype = csf->returntype;
812 sf->logvarcallgraph = csf->logvarcallgraph;
813 sf->method_of = csf->method_of;
814 return sf;
815 }
816
817 // See if returns produced by an existing specialization are compatible with our current
818 // context of functions.
CompatibleReturnsTypeChecker819 bool CompatibleReturns(const SubFunction &ssf) {
820 for (auto re : ssf.reuse_return_events) {
821 auto sf = re.first;
822 for (auto isc : reverse(scopes)) {
823 if (isc.sf->parent == sf->parent) {
824 if (isc.sf->reqret != sf->reqret) return false;
825 goto found;
826 }
827 }
828 return false; // Function not in context.
829 found:;
830 }
831 return true;
832 }
833
CheckReturnPastTypeChecker834 void CheckReturnPast(const SubFunction *sf, const SubFunction *sf_to, const Node &context) {
835 // Special case for returning out of top level, which is always allowed.
836 if (sf_to == st.toplevel) return;
837 if (sf->iscoroutine) {
838 TypeError("cannot return out of coroutine", context);
839 }
840 if (sf->isdynamicfunctionvalue) {
841 // This is because the function has been typechecked against one context, but
842 // can be called again in a different context that does not have the same callers.
843 TypeError("cannot return out of dynamic function value", context);
844 }
845 }
846
TypeCheckCallTypeChecker847 TypeRef TypeCheckCall(SubFunction *csf, List *call_args, SubFunction *&chosen,
848 const Node &call_context, size_t reqret, int &vtable_idx) {
849 Function &f = *csf->parent;
850 UDT *dispatch_udt = nullptr;
851 vtable_idx = -1;
852
853 auto TypeCheckMatchingCall = [&](SubFunction *sf, bool static_dispatch, bool first_dynamic) {
854 // Here we have a SubFunction witch matching specialized types.
855 sf->numcallers++;
856 Function &f = *sf->parent;
857 if (!f.istype) TypeCheckFunctionDef(*sf, call_context);
858 // Finally check all the manually typed args. We do this after checking the function
859 // definition, since SubType below can cause specializations of the current function
860 // to be typechecked with strongly typed function value arguments.
861 for (auto [i, c] : enumerate(call_args->children)) {
862 if (i < f.nargs()) /* see below */ {
863 auto &arg = sf->args.v[i];
864 if (static_dispatch || first_dynamic) {
865 // Check a dynamic dispatch only for the first case, and then skip
866 // checking the first arg.
867 if (!(arg.flags & AF_GENERIC) && (static_dispatch || i))
868 SubType(c, arg.type, ArgName(i), f.name);
869 AdjustLifetime(c, arg.sid->lt);
870 }
871 }
872 // This has to happen even to dead args:
873 if (static_dispatch || first_dynamic) DecBorrowers(c->lt, call_context);
874 }
875 chosen = sf;
876 for (auto &freevar : sf->freevars.v) {
877 // New freevars may have been added during the function def typecheck above.
878 // In case their types differ from the flow-sensitive value at the callsite (here),
879 // we want to override them.
880 freevar.type = freevar.sid->Current()->type;
881 }
882 // See if this call is recursive:
883 for (auto &sc : scopes) if (sc.sf == sf) { sf->isrecursivelycalled = true; break; }
884 return sf->returntype;
885 };
886
887 auto SpecializationIsCompatible = [&](const SubFunction &sf) {
888 return reqret == sf.reqret &&
889 FreeVarsSameAsCurrent(sf, false) &&
890 CompatibleReturns(sf);
891 };
892
893 auto ReplayReturns = [&](const SubFunction *sf) {
894 // Apply effects of return statements for functions being reused, see
895 // RetVal above.
896 for (auto [isf, type] : sf->reuse_return_events) {
897 for (auto isc : reverse(scopes)) {
898 if (isc.sf->parent == isf->parent) {
899 // NOTE: will have to re-apply lifetimes as well if we change
900 // from default of LT_KEEP.
901 RetVal(type, isc.sf, call_context, false);
902 // This should in theory not cause an error, since the previous
903 // specialization was also ok with this set of return types.
904 // It could happen though if this specialization has an
905 // additional return statement that was optimized
906 // out in the previous one.
907 SubTypeT(type, isc.sf->returntype, call_context, "",
908 "reused return value");
909 break;
910 }
911 CheckReturnPast(isc.sf, isf, call_context);
912 }
913 }
914 };
915
916 auto TypeCheckCallStatic = [&](int overload_idx, bool static_dispatch, bool first_dynamic) {
917 Function &f = *csf->parent;
918 SubFunction *sf = f.overloads[overload_idx];
919 if (sf->logvarcallgraph) {
920 // Mark call-graph up to here as using logvars, if it hasn't been already.
921 for (auto sc : reverse(scopes)) {
922 if (sc.sf->logvarcallgraph) break;
923 sc.sf->logvarcallgraph = true;
924 }
925 }
926 // Check if we need to specialize: generic args, free vars and need of retval
927 // must match previous calls.
928 auto AllowAnyLifetime = [&](const Arg & arg) {
929 return arg.sid->id->single_assignment && !sf->iscoroutine;
930 };
931 // Check if any existing specializations match.
932 for (sf = f.overloads[overload_idx]; sf; sf = sf->next) {
933 if (sf->typechecked && !sf->mustspecialize && !sf->logvarcallgraph) {
934 // We check against f.nargs because HOFs are allowed to call a function
935 // value with more arguments than it needs (if we're called from
936 // TypeCheckDynCall). Optimizer always removes these.
937 // Note: we compare only lt, since calling with other borrowed sid
938 // should be ok to reuse.
939 for (auto [i, c] : enumerate(call_args->children)) if (i < f.nargs()) {
940 auto &arg = sf->args.v[i];
941 if ((arg.flags & AF_GENERIC && !ExactType(c->exptype, arg.type)) ||
942 (IsBorrow(c->lt) != IsBorrow(arg.sid->lt) &&
943 AllowAnyLifetime(arg))) goto fail;
944 }
945 if (SpecializationIsCompatible(*sf)) {
946 // This function can be reused.
947 // Make sure to add any freevars this call caused to be
948 // added to its parents also to the current parents, just in case
949 // they're different.
950 LOG_DEBUG("re-using: ", Signature(*sf));
951 for (auto &fv : sf->freevars.v) CheckFreeVariable(*fv.sid);
952 ReplayReturns(sf);
953 return TypeCheckMatchingCall(sf, static_dispatch, first_dynamic);
954 }
955 fail:;
956 }
957 }
958 // No match.
959 sf = f.overloads[overload_idx];
960 // Specialize existing function, or its clone.
961 if (sf->typechecked) sf = CloneFunction(sf, overload_idx);
962 // Now specialize.
963 sf->reqret = reqret;
964 // See if this is going to be a coroutine.
965 for (auto [i, c] : enumerate(call_args->children)) if (i < f.nargs()) /* see above */ {
966 if (Is<CoClosure>(c))
967 sf->iscoroutine = true;
968 }
969 for (auto [i, c] : enumerate(call_args->children)) if (i < f.nargs()) /* see above */ {
970 auto &arg = sf->args.v[i];
971 arg.sid->lt = AllowAnyLifetime(arg) ? c->lt : LT_KEEP;
972 if (arg.flags & AF_GENERIC) {
973 arg.type = c->exptype; // Specialized to arg.
974 CheckGenericArg(f.orig_args.v[i].type, arg.type, arg.sid->id->name,
975 *c, f.name);
976 LOG_DEBUG("arg: ", arg.sid->id->name, ":", TypeName(arg.type));
977 }
978 }
979 // This must be the correct freevar specialization.
980 assert(!f.anonymous || sf->freevarchecked);
981 assert(!sf->freevars.v.size());
982 LOG_DEBUG("specialization: ", Signature(*sf));
983 return TypeCheckMatchingCall(sf, static_dispatch, first_dynamic);
984 };
985
986 auto TypeCheckCallDispatch = [&]() {
987 // We must assume the instance may dynamically be different, so go thru vtable.
988 // See if we already have a vtable entry for this type of call.
989 for (auto [i, disp] : enumerate(dispatch_udt->dispatch)) {
990 // FIXME: does this guarantee it find it in the recursive case?
991 // TODO: we chould check for a superclass vtable entry also, but chances
992 // two levels will be present are low.
993 if (disp.sf && disp.sf->method_of == dispatch_udt && disp.is_dispatch_root &&
994 &f == disp.sf->parent && SpecializationIsCompatible(*disp.sf)) {
995 for (auto [i, c] : enumerate(call_args->children)) if (i < f.nargs()) {
996 auto &arg = disp.sf->args.v[i];
997 if (i && !ConvertsTo(c->exptype, arg.type, false, false))
998 goto fail;
999 }
1000 for (auto udt : dispatch_udt->subudts) {
1001 // Since all functions were specialized with the same args, they should
1002 // all be compatible if the root is.
1003 auto sf = udt->dispatch[i].sf;
1004 LOG_DEBUG("re-using dyndispatch: ", Signature(*sf));
1005 assert(SpecializationIsCompatible(*sf));
1006 for (auto &fv : sf->freevars.v) CheckFreeVariable(*fv.sid);
1007 ReplayReturns(sf);
1008 }
1009 // Type check this as if it is a static dispatch to just the root function.
1010 TypeCheckMatchingCall(disp.sf, true, false);
1011 vtable_idx = (int)i;
1012 return dispatch_udt->dispatch[i].returntype;
1013 }
1014 fail:;
1015 }
1016 // Must create a new vtable entry.
1017 // TODO: would be good to search superclass if it has this method also.
1018 // Probably not super important since dispatching on the "middle" type in a
1019 // hierarchy will be rare.
1020 // Find subclasses and max vtable size.
1021 {
1022 vector<int> overload_idxs;
1023 for (auto sub : dispatch_udt->subudts) {
1024 int best = -1;
1025 int bestdist = 0;
1026 for (auto [i, sf] : enumerate(csf->parent->overloads)) {
1027 if (sf->method_of) {
1028 auto sdist = st.SuperDistance(sf->method_of, sub);
1029 if (sdist >= 0 && (best < 0 || bestdist > sdist)) {
1030 best = (int)i;
1031 bestdist = sdist;
1032 }
1033 }
1034 }
1035 if (best < 0) {
1036 if (sub->constructed) {
1037 TypeError("no implementation for " + sub->name + "." + csf->parent->name,
1038 call_context);
1039 } else {
1040 // This UDT is unused, so we're ok there not being an implementation
1041 // for it.. like e.g. an abstract base class.
1042 }
1043 }
1044 overload_idxs.push_back(best);
1045 vtable_idx = max(vtable_idx, (int)sub->dispatch.size());
1046 }
1047 // Add functions to all vtables.
1048 for (auto [i, udt] : enumerate(dispatch_udt->subudts)) {
1049 auto &dt = udt->dispatch;
1050 assert((int)dt.size() <= vtable_idx); // Double entry.
1051 // FIXME: this is not great, wasting space, but only way to do this
1052 // on the fly without tracking lots of things.
1053 while ((int)dt.size() < vtable_idx) dt.push_back({});
1054 dt.push_back({ overload_idxs[i] < 0
1055 ? nullptr
1056 : csf->parent->overloads[overload_idxs[i]] });
1057 }
1058 // FIXME: if any of the overloads below contain recursive calls, it may run into
1059 // issues finding an existing dispatch above? would be good to guarantee..
1060 // The fact that in subudts the superclass comes first will help avoid problems
1061 // in many cases.
1062 auto de = &dispatch_udt->dispatch[vtable_idx];
1063 de->is_dispatch_root = true;
1064 de->returntype = NewTypeVar();
1065 // Typecheck all the individual functions.
1066 SubFunction *last_sf = nullptr;
1067 for (auto [i, udt] : enumerate(dispatch_udt->subudts)) {
1068 auto sf = udt->dispatch[vtable_idx].sf;
1069 if (!sf) continue; // Missing implementation for unused UDT.
1070 // FIXME: this possible runs the code below multiple times for the same sf,
1071 // we rely on it finding the same specialization.
1072 if (last_sf) {
1073 // FIXME: good to have this check here so it only occurs for functions
1074 // participating in the dispatch, but error now appears at the call site!
1075 for (auto [j, arg] : enumerate(sf->args.v)) {
1076 if (j && arg.type != last_sf->args.v[j].type &&
1077 !(arg.flags & AF_GENERIC))
1078 TypeError("argument " + to_string(j + 1) + " of " + f.name +
1079 " overload type mismatch", call_context);
1080 }
1081 }
1082 call_args->children[0]->exptype = &udt->thistype;
1083 // FIXME: return value?
1084 /*auto rtype =*/ TypeCheckCallStatic(overload_idxs[i], false, !last_sf);
1085 de = &dispatch_udt->dispatch[vtable_idx]; // May have realloced.
1086 sf = chosen;
1087 sf->method_of->dispatch[vtable_idx].sf = sf;
1088 // FIXME: Lift these limits?
1089 if (sf->returntype->NumValues() > 1)
1090 TypeError("dynamic dispatch can currently return only 1 value.",
1091 call_context);
1092 auto u = sf->returntype;
1093 if (de->returntype->IsBoundVar()) {
1094 // Typically in recursive calls, but can happen otherwise also?
1095 if (!ConvertsTo(u, de->returntype, false))
1096 // FIXME: not a great error, but should be rare.
1097 TypeError("dynamic dispatch for " + f.name +
1098 " return value type " +
1099 TypeName(sf->returntype) +
1100 " doesn\'t match other case returning " +
1101 TypeName(de->returntype), *sf->body);
1102 } else {
1103 if (i) {
1104 // We have to be able to take the union of all retvals without
1105 // coercion, since we're not fixing up any previously typechecked
1106 // functions.
1107 u = Union(u, de->returntype, false, &call_context);
1108 // Ensure we didn't accidentally widen the type from a scalar.
1109 assert(IsRef(de->returntype->t) || !IsRef(u->t));
1110 }
1111 de->returntype = u;
1112 }
1113 last_sf = sf;
1114 }
1115 call_args->children[0]->exptype = &dispatch_udt->thistype;
1116 }
1117 return dispatch_udt->dispatch[vtable_idx].returntype;
1118 };
1119
1120 if (f.istype) {
1121 // Function types are always fully typed.
1122 // All calls thru this type must have same lifetimes, so we fix it to LT_BORROW.
1123 return TypeCheckMatchingCall(csf, true, false);
1124 }
1125 // Check if we need to do dynamic dispatch. We only do this for functions that have a
1126 // explicit first arg type of a class (not structs, since they can never dynamically be
1127 // different from their static type), and only when there is a sub-class that has a
1128 // method that can be called also.
1129 if (f.nargs()) {
1130 auto type = call_args->children[0]->exptype;
1131 if (type->t == V_CLASS) dispatch_udt = type->udt;
1132 }
1133 if (dispatch_udt) {
1134 size_t num_methods = 0;
1135 for (auto isf : csf->parent->overloads) if (isf->method_of) num_methods++;
1136 if (num_methods > 1) {
1137 // Go thru all other overloads, and see if any of them have this one as superclass.
1138 for (auto isf : csf->parent->overloads) {
1139 if (isf->method_of && st.SuperDistance(dispatch_udt, isf->method_of) > 0) {
1140 LOG_DEBUG("dynamic dispatch: ", Signature(*isf));
1141 return TypeCheckCallDispatch();
1142 }
1143 }
1144 // Yay there are no sub-class implementations, we can just statically dispatch.
1145 }
1146 // Yay only one method, we can statically dispatch.
1147 }
1148 // Do a static dispatch, if there are overloads, figure out from first arg which to pick,
1149 // much like dynamic dispatch. Unlike dynamic dispatch, we also include non-class types.
1150 // TODO: also involve the other arguments for more complex static overloads?
1151 int overload_idx = 0;
1152 if (f.nargs() && f.overloads.size() > 1) {
1153 overload_idx = -1;
1154 auto type0 = call_args->children[0]->exptype;
1155 // First see if there is an exact match.
1156 for (auto [i, isf] : enumerate(f.overloads)) {
1157 if (ExactType(type0, isf->args.v[0].type)) {
1158 if (overload_idx >= 0)
1159 TypeError("multiple overloads have the same type: " + f.name +
1160 ", first arg: " + TypeName(type0), call_context);
1161 overload_idx = (int)i;
1162 }
1163 }
1164 // Then see if there's a match by subtyping.
1165 if (overload_idx < 0) {
1166 for (auto [i, isf] : enumerate(f.overloads)) {
1167 auto arg0 = isf->args.v[0].type;
1168 if (ConvertsTo(type0, arg0, false, false)) {
1169 if (overload_idx >= 0) {
1170 if (type0->t == V_CLASS) {
1171 auto oarg0 = f.overloads[overload_idx]->args.v[0].type;
1172 // Prefer "closest" supertype.
1173 auto dist = st.SuperDistance(arg0->udt, type0->udt);
1174 auto odist = st.SuperDistance(oarg0->udt, type0->udt);
1175 if (dist < odist) overload_idx = (int)i;
1176 else if (odist < dist) { /* keep old one */ }
1177 else {
1178 TypeError("multiple overloads have the same class: " + f.name +
1179 ", first arg: " + TypeName(type0), call_context);
1180 }
1181 } else {
1182 TypeError("multiple overloads apply: " + f.name + ", first arg: " +
1183 TypeName(type0), call_context);
1184 }
1185 } else {
1186 overload_idx = (int)i;
1187 }
1188 }
1189 }
1190 }
1191 // Then finally try with coercion.
1192 if (overload_idx < 0) {
1193 for (auto [i, isf] : enumerate(f.overloads)) {
1194 if (ConvertsTo(type0, isf->args.v[0].type, true, false)) {
1195 if (overload_idx >= 0) {
1196 TypeError("multiple overloads can coerce: " + f.name +
1197 ", first arg: " + TypeName(type0), call_context);
1198 }
1199 overload_idx = (int)i;
1200 }
1201 }
1202 }
1203 if (overload_idx < 0)
1204 TypeError("no overloads apply: " + f.name + ", first arg: " + TypeName(type0),
1205 call_context);
1206 }
1207 LOG_DEBUG("static dispatch: ", Signature(*f.overloads[overload_idx]));
1208 return TypeCheckCallStatic(overload_idx, true, false);
1209 }
1210
PreSpecializeFunctionTypeChecker1211 SubFunction *PreSpecializeFunction(SubFunction *hsf) {
1212 // Don't pre-specialize named functions, because this is not their call-site.
1213 if (!hsf->parent->anonymous) return hsf;
1214 assert(hsf->parent->overloads.size() == 1);
1215 hsf = hsf->parent->overloads[0];
1216 auto sf = hsf;
1217 if (sf->freevarchecked) {
1218 // See if there's an existing match.
1219 for (; sf; sf = sf->next) if (sf->freevarchecked) {
1220 if (FreeVarsSameAsCurrent(*sf, true)) return sf;
1221 }
1222 sf = CloneFunction(hsf, 0);
1223 } else {
1224 // First time this function has ever been touched.
1225 sf->freevarchecked = true;
1226 }
1227 assert(!sf->freevars.v.size());
1228 // Output without arg types, since those are yet to be overwritten.
1229 LOG_DEBUG("pre-specialization: ", SignatureWithFreeVars(*sf, nullptr, false));
1230 return sf;
1231 }
1232
TypeCheckDynCallTypeChecker1233 pair<TypeRef, Lifetime> TypeCheckDynCall(SpecIdent *fval, List *args, SubFunction *&fspec,
1234 size_t reqret) {
1235 auto &ftype = fval->type;
1236 auto nargs = args->Arity();
1237 // FIXME: split this up in a Call, a Yield and a DynCall(istype = true) node, just like
1238 // GenericCall does.
1239 if (ftype->IsFunction()) {
1240 // We can statically typecheck this dynamic call. Happens for almost all non-escaping
1241 // closures.
1242 auto sf = ftype->sf;
1243 if (nargs < sf->parent->nargs())
1244 TypeError("function value called with too few arguments", *args);
1245 // In the case of too many args, TypeCheckCall will ignore them (and optimizer will
1246 // remove them).
1247 int vtable_idx = -1;
1248 auto type = TypeCheckCall(sf, args, fspec, *args, reqret, vtable_idx);
1249 assert(vtable_idx < 0);
1250 ftype = &fspec->thistype;
1251 return { type, fspec->ltret };
1252 } else if (ftype->t == V_YIELD) {
1253 // V_YIELD must have perculated up from a coroutine call.
1254 if (nargs != 1)
1255 TypeError("coroutine yield call must have exactly one argument", *args);
1256 NoStruct(*args->children[0], "yield"); // FIXME: implement.
1257 AdjustLifetime(args->children[0], LT_KEEP);
1258 for (auto scope : reverse(named_scopes)) {
1259 auto sf = scope.sf;
1260 if (!sf->iscoroutine) continue;
1261 // What yield returns to return_value(). If no arg, then it will return nil.
1262 auto type = args->children[0]->exptype;
1263 RetVal(type, sf, *args);
1264 SubTypeT(type, sf->returntype, *args, "", "yield value");
1265 // Now collect all ids between coroutine and yield, so that we can save these in the
1266 // VM.
1267 bool foundstart = false;
1268 for (auto savescope = scopes.begin(); savescope != scopes.end(); ++savescope) {
1269 auto ssf = savescope->sf;
1270 if (ssf == sf) foundstart = true;
1271 if (!foundstart) continue;
1272 for (auto &arg : ssf->args.v)
1273 sf->coyieldsave.Add(arg);
1274 for (auto &loc : ssf->locals.v)
1275 sf->coyieldsave.Add(Arg(loc.sid, loc.sid->type, loc.flags & AF_WITHTYPE));
1276 }
1277 for (auto &cys : sf->coyieldsave.v) UpdateCurrentSid(cys.sid);
1278 return { sf->coresumetype, LT_KEEP };
1279 }
1280 TypeError("yield function called outside scope of coroutine", *args);
1281 return { type_void, LT_ANY };
1282 } else {
1283 TypeError("dynamic function call value doesn\'t have a function type: " +
1284 TypeName(ftype), *args);
1285 return { type_void, LT_ANY };
1286 }
1287 }
1288
TypeCheckBranchTypeChecker1289 TypeRef TypeCheckBranch(bool iftrue, const Node *condition, Node *&bodycall,
1290 bool reqret, Lifetime recip) {
1291 auto flowstart = CheckFlowTypeChanges(iftrue, condition);
1292 TT(bodycall, reqret, recip);
1293 CleanUpFlow(flowstart);
1294 return bodycall->exptype;
1295 }
1296
CheckFlowTypeIdOrDotTypeChecker1297 void CheckFlowTypeIdOrDot(const Node &n, TypeRef type) {
1298 FlowItem fi(n, type);
1299 if (fi.IsValid()) flowstack.push_back(fi);
1300 }
1301
CheckFlowTypeChangesSubTypeChecker1302 void CheckFlowTypeChangesSub(bool iftrue, const Node *condition) {
1303 condition = SkipCoercions(condition);
1304 auto type = condition->exptype;
1305 if (auto c = Is<IsType>(condition)) {
1306 if (iftrue) CheckFlowTypeIdOrDot(*c->child, c->giventype);
1307 } else if (auto c = Is<Not>(condition)) {
1308 CheckFlowTypeChangesSub(!iftrue, c->child);
1309 } else {
1310 if (iftrue && type->t == V_NIL) CheckFlowTypeIdOrDot(*condition, type->Element());
1311 }
1312 }
1313
CheckFlowTypeChangesAndOrTypeChecker1314 void CheckFlowTypeChangesAndOr(bool iftrue, const BinOp *condition) {
1315 // AND only works for then, and OR only for else.
1316 if (iftrue == (Is<And>(condition) != nullptr)) {
1317 // This allows for a chain of and's without allowing mixed operators.
1318 auto cleft = SkipCoercions(condition->left);
1319 if (typeid(*cleft) == typeid(*condition)) {
1320 CheckFlowTypeChanges(iftrue, condition->left);
1321 } else {
1322 CheckFlowTypeChangesSub(iftrue, condition->left);
1323 }
1324 CheckFlowTypeChangesSub(iftrue, condition->right);
1325 }
1326 }
1327
CheckFlowTypeChangesTypeChecker1328 size_t CheckFlowTypeChanges(bool iftrue, const Node *condition) {
1329 auto start = flowstack.size();
1330 condition = SkipCoercions(condition);
1331 if (auto c = Is<Or>(condition)) {
1332 CheckFlowTypeChangesAndOr(iftrue, c);
1333 } else if (auto c = Is<And>(condition)) {
1334 CheckFlowTypeChangesAndOr(iftrue, c);
1335 } else {
1336 CheckFlowTypeChangesSub(iftrue, condition);
1337 }
1338 return start;
1339 }
1340
AssignFlowPromoteTypeChecker1341 void AssignFlowPromote(Node &left, TypeRef right) {
1342 if ((left.exptype->t == V_ANY && right->t != V_ANY) ||
1343 (left.exptype->t == V_NIL && right->t != V_NIL)) {
1344 CheckFlowTypeIdOrDot(left, right);
1345 }
1346 }
1347
1348 // FIXME: this can in theory find the wrong node, if the same function nests, and the outer
1349 // one was specialized to a nilable and the inner one was not.
1350 // This would be very rare though, and benign.
AssignFlowDemoteTypeChecker1351 TypeRef AssignFlowDemote(FlowItem &left, TypeRef overwritetype, bool coercions) {
1352 // Early out, numeric types are not nillable, nor do they make any sense for "is"
1353 auto &type = left.now;
1354 if (type->Numeric()) return type;
1355 for (auto flow : reverse(flowstack)) {
1356 if (flow.sid == left.sid) {
1357 if (left.derefs.empty()) {
1358 if (flow.derefs.empty()) {
1359 type = flow.old;
1360 goto found;
1361 } else {
1362 // We're writing to var V and V.f is in the stack: invalidate regardless.
1363 goto found;
1364 }
1365 } else {
1366 if (flow.DerefsEqual(left)) {
1367 type = flow.old;
1368 goto found;
1369 }
1370 }
1371 }
1372 continue;
1373 found:
1374 if (!ConvertsTo(overwritetype, flow.now, coercions)) {
1375 // FLow based promotion is invalidated.
1376 flow.now = flow.old;
1377 // TODO: It be cool to instead overwrite with whatever type is currently being
1378 // assigned. That currently doesn't work, since our flow analysis is a
1379 // conservative approximation, so if this assignment happens conditionally it
1380 // wouldn't work.
1381 }
1382 // We continue with the loop here, since a single assignment may invalidate multiple
1383 // promotions
1384 }
1385 return type;
1386 }
1387
UseFlowTypeChecker1388 TypeRef UseFlow(const FlowItem &left) {
1389 if (left.now->Numeric()) return left.now; // Early out, same as above.
1390 for (auto flow : reverse(flowstack)) {
1391 if (flow.sid == left.sid && flow.DerefsEqual(left)) {
1392 return flow.now;
1393 }
1394 }
1395 return left.now;
1396 }
1397
CleanUpFlowTypeChecker1398 void CleanUpFlow(size_t start) {
1399 while (flowstack.size() > start) flowstack.pop_back();
1400 }
1401
TypeCheckAndOrTypeChecker1402 void TypeCheckAndOr(BinOp &ao, bool only_true_type, bool reqret, TypeRef &promoted_type) {
1403 // only_true_type supports patterns like ((a & b) | c) where the type of a doesn't matter,
1404 // and the overal type should be the union of b and c.
1405 // Or a? | b, which should also be the union of a and b.
1406 TypeRef tleft, tright;
1407 TypeCheckAndOrSub(ao.left, Is<Or>(ao), true, tleft);
1408 auto flowstart = CheckFlowTypeChanges(Is<And>(ao), ao.left);
1409 TypeCheckAndOrSub(ao.right, only_true_type, reqret, tright);
1410 CleanUpFlow(flowstart);
1411 if (only_true_type && Is<And>(ao)) {
1412 ao.exptype = tright;
1413 ao.lt = ao.right->lt;
1414 DecBorrowers(ao.left->lt, ao);
1415 } else {
1416 ao.exptype = Union(tleft, tright, false, nullptr);
1417 if (ao.exptype->t == V_UNDEFINED) {
1418 // Special case: unlike elsewhere, we allow merging scalar and reference types,
1419 // since they are just tested and thrown away. To make this work, we force all
1420 // values to bools.
1421 MakeBool(ao.left);
1422 MakeBool(ao.right);
1423 ao.exptype = &st.default_bool_type->thistype;
1424 ao.lt = LT_ANY;
1425 } else {
1426 ao.lt = LifetimeUnion(ao.left, ao.right, Is<And>(ao));
1427 }
1428 }
1429 promoted_type = ao.exptype;
1430 }
1431
TypeCheckAndOrSubTypeChecker1432 void TypeCheckAndOrSub(Node *&n, bool only_true_type, bool reqret, TypeRef &promoted_type) {
1433 // only_true_type supports patterns like ((a & b) | c) where the type of a doesn't matter,
1434 // and the overal type should be the union of b and c.
1435 // Or a? | b, which should also be the union of a and b.
1436 n = RemoveCoercions(n);
1437 if (!Is<And>(n) && !Is<Or>(n)) {
1438 TT(n, reqret, LT_ANY);
1439 NoStruct(*n, "and / or");
1440 promoted_type = n->exptype;
1441 if (promoted_type->t == V_NIL && only_true_type)
1442 promoted_type = promoted_type->Element();
1443 } else {
1444 auto ao = dynamic_cast<BinOp *>(n);
1445 assert(ao);
1446 TypeCheckAndOr(*ao, only_true_type, reqret, promoted_type);
1447 }
1448 }
1449
CheckLvalTypeChecker1450 void CheckLval(Node *n) {
1451 if (auto dot = Is<Dot>(n)) {
1452 auto type = dot->children[0]->exptype;
1453 if (IsStruct(type->t))
1454 TypeError("cannot write to field of value: " + type->udt->name, *n);
1455 }
1456 // This can happen due to late specialization of GenericCall.
1457 if (Is<Call>(n) || Is<NativeCall>(n))
1458 TypeError("function-call cannot be an l-value", *n);
1459 Borrow lv(*n);
1460 if (!lv.IsValid()) return; // FIXME: force these to LT_KEEP?
1461 if (lv.derefs.empty() && LifetimeType(lv.sid->lt) == LT_BORROW) {
1462 // This should only happen for multimethods and anonymous functions used with istype
1463 // where we can't avoid arguments being LT_BORROW.
1464 // All others should have been specialized to LT_KEEP when a var is not
1465 // single_assignment.
1466 // This is not particularly elegant but should be rare.
1467 TypeError(cat("cannot assign to borrowed argument: ", lv.sid->id->name), *n);
1468 }
1469 // FIXME: make this faster.
1470 for (auto &b : reverse(borrowstack)) {
1471 if (!b.IsPrefix(lv)) continue; // Not overwriting this one.
1472 if (!b.refc) continue; // Lval is not borowed, writing is ok.
1473 TypeError(cat("cannot assign to ", lv.Name(), " while borrowed"), *n);
1474 }
1475 }
1476
PushBorrowTypeChecker1477 Lifetime PushBorrow(Node *n) {
1478 if (!IsRefNilVar(n->exptype->t)) return LT_ANY;
1479 Borrow lv(*n);
1480 // FIXME: if this is an exp we don't know how to borrow from (like a[i].b) we
1481 // return a generic borrow, but this disables lock checks so is unsafe.
1482 if (!lv.IsValid()) return LT_BORROW;
1483 for (auto &b : reverse(borrowstack)) {
1484 if (b.sid == lv.sid && b.DerefsEqual(lv)) {
1485 b.refc++;
1486 return (Lifetime)(&b - &borrowstack[0]);
1487 }
1488 }
1489 // FIXME: this path is slow, should not have to scan all of borrowstack.
1490 auto lt = (Lifetime)borrowstack.size();
1491 borrowstack.push_back(lv);
1492 return lt;
1493 }
1494
CheckFreeVariableTypeChecker1495 void CheckFreeVariable(SpecIdent &sid) {
1496 // If this is a free variable, record it in all parents up to the definition point.
1497 // FIXME: this is technically not the same as a "free variable" in the literature,
1498 // since HOFs get marked with freevars of their functionvalue this way.
1499 // This is benign, since the HOF will be specialized to the function value anyway,
1500 // but would be good to clean up.
1501 // We currently don't have an easy way to test for lexically enclosing functions.
1502 for (int i = (int)scopes.size() - 1; i >= 0; i--) {
1503 auto sf = scopes[i].sf;
1504 // Check if we arrived at the definition point.
1505 if (sid.sf_def == sf)
1506 break;
1507 // We use the id's type, not the flow sensitive type, just in case there's multiple uses
1508 // of the var. This will get corrected after the call this is part of.
1509 if (sf->freevars.Add(Arg(&sid, sid.type, AF_GENERIC))) {
1510 //LOG_DEBUG("freevar added: ", id.name, " (", TypeName(id.type),
1511 // ") in ", sf->parent->name);
1512 }
1513 }
1514 }
1515
NeverReturnsTypeChecker1516 bool NeverReturns(const Node *n) {
1517 if (auto call = Is<Call>(n)) {
1518 // Have to be conservative for recursive calls since we're not done typechecking it.
1519 if (call->sf->isrecursivelycalled ||
1520 call->sf->method_of ||
1521 call->sf->iscoroutine ||
1522 call->sf->parent->istype) return false;
1523 if (!call->sf->num_returns) return true;
1524 if (call->sf->num_returns == 1) {
1525 auto ret = AssertIs<Return>(call->sf->body->children.back());
1526 assert(ret->sf == call->sf);
1527 return NeverReturns(ret->child);
1528 }
1529 // TODO: could also check num_returns > 1, but then have to scan all children.
1530 } else if (auto ifthen = Is<If>(n)) {
1531 auto tp = Is<Call>(ifthen->truepart);
1532 auto fp = Is<Call>(ifthen->falsepart);
1533 return tp && fp && NeverReturns(tp) && NeverReturns(fp);
1534 } else if (auto sw = Is<Switch>(n)) {
1535 auto have_default = false;
1536 for (auto c : sw->cases->children) {
1537 auto cas = AssertIs<Case>(c);
1538 if (cas->pattern->children.empty()) have_default = true;
1539 if (!NeverReturns(cas->body)) return false;
1540 }
1541 return have_default;
1542 } else if (auto nc = Is<NativeCall>(n)) {
1543 // A function may end in "assert false" and have only its previous return statements
1544 // taken into account.
1545 Value cval;
1546 if (nc->nf->IsAssert() && nc->children[0]->ConstVal(*this, cval) && !cval.True())
1547 return true;
1548 }
1549 // TODO: Other situations?
1550 return false;
1551 }
1552
TypeCheckListTypeChecker1553 void TypeCheckList(List *n, bool onlylast, size_t reqret, Lifetime lt) {
1554 for (auto &c : n->children) {
1555 auto tovoid = onlylast && c != n->children.back();
1556 TT(c, tovoid ? 0 : reqret,
1557 tovoid ? LT_ANY : lt);
1558 }
1559 }
1560
TypeCheckIdTypeChecker1561 TypeRef TypeCheckId(SpecIdent *sid) {
1562 auto type = sid->type;
1563 CheckFreeVariable(*sid);
1564 return type;
1565 }
1566
IsCoercionTypeChecker1567 const Coercion *IsCoercion(const Node *n) {
1568 return dynamic_cast<const Coercion *>(n);
1569 }
1570
SkipCoercionsTypeChecker1571 const Node *SkipCoercions(const Node *n) {
1572 auto c = IsCoercion(n);
1573 return c ? SkipCoercions(c->child) : n;
1574 }
1575
RemoveCoercionsTypeChecker1576 Node *RemoveCoercions(Node *n) {
1577 auto c = IsCoercion(n);
1578 return c ? RemoveCoercions(DeleteCoercion((Coercion *)c)) : n;
1579 }
1580
DeleteCoercionTypeChecker1581 Node *DeleteCoercion(Coercion *c) {
1582 auto ch = c->child;
1583 c->child = nullptr;
1584 delete c;
1585 return ch;
1586 }
1587
LvalueLifetimeTypeChecker1588 Lifetime LvalueLifetime(const Node &lval, bool deref) {
1589 if (auto idr = Is<IdentRef>(lval)) return idr->sid->lt;
1590 if (deref) {
1591 if (auto dot = Is<Dot>(lval)) return LvalueLifetime(*dot->children[0], deref);
1592 if (auto idx = Is<Indexing>(lval)) return LvalueLifetime(*idx->object, deref);
1593 }
1594 if (auto cod = Is<CoDot>(lval)) return AssertIs<IdentRef>(cod->variable)->sid->lt;
1595 return LT_KEEP;
1596 }
1597
LifetimeUnionTypeChecker1598 Lifetime LifetimeUnion(Node *&a, Node *&b, bool is_and) {
1599 if (a->lt == b->lt) {
1600 DecBorrowers(b->lt, *b);
1601 return a->lt;
1602 } else if (a->lt == LT_ANY && b->lt >= LT_BORROW) {
1603 // This case may apply in an if-then between a var and nil, or an and/or between
1604 // a var and a scalar.
1605 return b->lt;
1606 } else if (b->lt == LT_ANY && a->lt >= LT_BORROW) {
1607 // Same.
1608 return a->lt;
1609 } else if (is_and && a->lt >= LT_BORROW && b->lt >= LT_BORROW) {
1610 // var_a and var_b never results in var_a.
1611 DecBorrowers(a->lt, *a);
1612 return b->lt;
1613 } else {
1614 // If it is an and we want to borrow the lhs since it will never be used.
1615 // Otherwise default to LT_KEEP for everything.
1616 // FIXME: for cases where both sides are >= LT_BORROW (in an if-then) we'd like to
1617 // combine both lifetimes into one, but we currently can't represent that.
1618 AdjustLifetime(a, is_and ? LT_BORROW : LT_KEEP);
1619 if (is_and) DecBorrowers(a->lt, *a);
1620 AdjustLifetime(b, LT_KEEP);
1621 return LT_KEEP;
1622 }
1623 }
1624
BorrowersTypeChecker1625 void Borrowers(Lifetime lt, int change, const Node &context) {
1626 if (lt < 0) return;
1627 auto &b = borrowstack[lt];
1628 assert(IsRefNilVar(b.sid->type->t));
1629 b.refc += change;
1630 LOG_DEBUG("borrow ", change, ": ", b.sid->id->name, " in ", NiceName(context),
1631 ", ", b.refc, " remain");
1632 // FIXME: this should really just not be possible, but hard to guarantee.
1633 if (b.refc < 0)
1634 TypeError(cat(b.sid->id->name, " used in ", NiceName(context),
1635 " without being borrowed"), context);
1636 assert(b.refc >= 0);
1637 (void)context;
1638 }
1639
IncBorrowersTypeChecker1640 void IncBorrowers(Lifetime lt, const Node &context) { Borrowers(lt, 1, context); }
DecBorrowersTypeChecker1641 void DecBorrowers(Lifetime lt, const Node &context) { Borrowers(lt, -1, context); }
1642
ModifyLifetimeTypeChecker1643 void ModifyLifetime(Node *n, size_t i, Lifetime lt) {
1644 if (n->lt == LT_MULTIPLE) {
1645 n->exptype->Set(i, n->exptype->Get(i), lt);
1646 } else {
1647 n->lt = lt;
1648 }
1649 }
1650
1651 void AdjustLifetime(Node *&n, Lifetime recip, const vector<Node *> *idents = nullptr) {
1652 assert(n->lt != LT_UNDEF && recip != LT_UNDEF);
1653 if (recip == LT_ANY) return;
1654 uint64_t incref = 0, decref = 0;
1655 auto rt = n->exptype;
1656 for (size_t i = 0; i < rt->NumValues(); i++) {
1657 assert (n->lt != LT_MULTIPLE || rt->t == V_TUPLE);
1658 auto givenlt = rt->GetLifetime(i, n->lt);
1659 auto given = LifetimeType(givenlt);
1660 if (idents) recip = LvalueLifetime(*(*idents)[i], false); // FIXME: overwrite var?
1661 recip = LifetimeType(recip);
1662 if (given != recip) {
1663 auto rtt = rt->Get(i)->t;
1664 // Sadly, if it a V_VAR we have to be conservate and assume it may become a ref.
1665 if (IsRefNilVar(rtt)) {
1666 // Special action required.
1667 if (i >= sizeof(incref) * 8) TypeError("too many return values", *n);
1668 if (given == LT_BORROW && recip == LT_KEEP) {
1669 incref |= 1LL << i;
1670 DecBorrowers(givenlt, *n);
1671 } else if (given == LT_KEEP && recip == LT_BORROW) {
1672 decref |= 1LL << i;
1673 } else if (given == LT_ANY) {
1674 // These are compatible with whatever recip wants.
1675 } else {
1676 assert(false);
1677 }
1678 } else {
1679 if (given == LT_BORROW) {
1680 // This is a scalar that depends on a borrowed value, but the recipient
1681 // doesn't care.
1682 ModifyLifetime(n, i, LT_ANY); // Avoid it travelling any further.
1683 DecBorrowers(givenlt, *n);
1684 }
1685 }
1686 if (given == LT_ANY) {
1687 // Fill in desired lifetime, for consistency.
1688 ModifyLifetime(n, i, recip);
1689 }
1690 }
1691 }
1692 if (incref || decref) {
1693 LOG_DEBUG("lifetime adjust for ", NiceName(*n), " to ", incref, "/",
1694 decref);
1695 MakeLifetime(n, idents ? LT_MULTIPLE: recip, incref, decref);
1696 }
1697 }
1698
1699 // This is the central function thru which all typechecking flows, so we can conveniently
1700 // match up what the node produces and what the recipient expects.
1701 void TT(Node *&n, size_t reqret, Lifetime recip, const vector<Node *> *idents = nullptr) {
1702 // Central point from which each node is typechecked.
1703 n = n->TypeCheck(*this, reqret);
1704 // Check if we need to do any type adjustmenst.
1705 auto &rt = n->exptype;
1706 n->exptype = rt;
1707 auto nret = rt->NumValues();
1708 if (nret < reqret) {
1709 TypeError(cat(NiceName(*n), " returns ", nret, " values, ", reqret, " needed"), *n);
1710 } else if (nret > reqret) {
1711 for (size_t i = reqret; i < nret; i++) {
1712 // This value will be dropped.
1713 DecBorrowers(rt->GetLifetime(i, n->lt), *n);
1714 // If this is a LT_KEEP value, codegen will make sure to throw it away.
1715 }
1716 switch (reqret) {
1717 case 0:
1718 n->lt = LT_ANY;
1719 rt = type_void;
1720 break;
1721 case 1: {
1722 auto typelt = TypeLT { *n, 0 }; // Get from tuple.
1723 n->lt = typelt.lt;
1724 rt = typelt.type;
1725 break;
1726 }
1727 default: {
1728 auto nt = NewTuple(reqret);
1729 nt->tup->assign(rt->tup->begin(), rt->tup->begin() + reqret);
1730 rt = nt;
1731 }
1732 }
1733 }
1734 // Check if we need to do any lifetime adjustments.
1735 AdjustLifetime(n, recip, idents);
1736 }
1737
1738 // TODO: Can't do this transform ahead of time, since it often depends upon the input args.
ActualBuiltinTypeTypeChecker1739 TypeRef ActualBuiltinType(int flen, TypeRef type, ArgFlags flags, Node *exp,
1740 const NativeFun *nf, bool test_overloads, size_t argn,
1741 const Node &errorn) {
1742 if (flags & NF_BOOL) {
1743 type = type->ElementIfNil();
1744 assert(type->t == V_INT);
1745 return &st.default_bool_type->thistype;
1746 }
1747 // See if we can promote the type to one of the standard vector types
1748 // (xy/xyz/xyzw).
1749 if (!flen) return type;
1750 type = type->ElementIfNil();
1751 auto etype = exp ? exp->exptype : nullptr;
1752 auto e = etype;
1753 size_t i = 0;
1754 for (auto vt = type; vt->t == V_VECTOR && i < SymbolTable::NUM_VECTOR_TYPE_WRAPPINGS;
1755 vt = vt->sub) {
1756 if (vt->sub->Numeric()) {
1757 // Check if we allow any vector length.
1758 if (!e.Null() && flen == -1 && e->t == V_STRUCT_S) {
1759 flen = (int)e->udt->fields.size();
1760 }
1761 if (!etype.Null() && flen == -1 && etype->t == V_VAR) {
1762 // Special case for "F}?" style types that can be matched against a
1763 // DefaultArg, would be good to solve this more elegantly..
1764 // FIXME: don't know arity, but it doesn't matter, so we pick 2..
1765 return st.VectorType(vt, i, 2);
1766 }
1767 if (flen >= 2 && flen <= 4) {
1768 if (!e.Null() && e->t == V_STRUCT_S && (int)e->udt->fields.size() == flen &&
1769 e->udt->sametype == vt->sub) {
1770 // Allow any similar vector type, like "color".
1771 return etype;
1772 }
1773 else {
1774 // Require xy/xyz/xyzw
1775 return st.VectorType(vt, i, flen);
1776 }
1777 }
1778 }
1779 e = !e.Null() && e->t == V_VECTOR ? e->sub : nullptr;
1780 i++;
1781 }
1782 // We arrive here typically if flen == -1 but we weren't able to derive a length.
1783 // Sadly, we can't allow to return a vector type instead of a struct, so we error out,
1784 // and rely on the user to specify more precise types.
1785 // Not sure if there is a better solution.
1786 if (!test_overloads)
1787 TypeError("cannot deduce struct type for " +
1788 (argn ? cat("argument ", argn) : "return value") +
1789 " of " + nf->name + (!etype.Null() ? ", got: " + TypeName(etype) : ""),
1790 errorn);
1791 return type;
1792 };
1793
StatsTypeChecker1794 void Stats() {
1795 if (min_output_level > OUTPUT_INFO) return;
1796 int origsf = 0, clonesf = 0;
1797 size_t orignodes = 0, clonenodes = 0;
1798 typedef pair<size_t, Function *> Pair;
1799 vector<Pair> funstats;
1800 for (auto f : st.functiontable) funstats.push_back({ 0, f });
1801 for (auto sf : st.subfunctiontable) {
1802 auto count = sf->body ? sf->body->Count() : 0;
1803 if (!sf->next) {
1804 origsf++;
1805 orignodes += count;
1806 } else {
1807 clonesf++;
1808 clonenodes += count;
1809 funstats[sf->parent->idx].first += count;
1810 }
1811 }
1812 LOG_INFO("SF count: orig: ", origsf, ", cloned: ", clonesf);
1813 LOG_INFO("Node count: orig: ", orignodes, ", cloned: ", clonenodes);
1814 sort(funstats.begin(), funstats.end(),
1815 [](const Pair &a, const Pair &b) { return a.first > b.first; });
1816 for (auto &[fsize, f] : funstats) if (fsize > orignodes / 100) {
1817 auto &pos = f->overloads.back()->body->line;
1818 LOG_INFO("Most clones: ", f->name, " (", st.filenames[pos.fileidx], ":", pos.line,
1819 ") -> ", fsize, " nodes accross ", f->NumSubf() - f->overloads.size(),
1820 " clones (+", f->overloads.size(), " orig)");
1821 }
1822 }
1823 };
1824
TypeCheck(TypeChecker &,size_t)1825 Node *List::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1826 assert(false); // Parent calls TypeCheckList.
1827 return this;
1828 }
1829
TypeCheck(TypeChecker &,size_t)1830 Node *Unary::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1831 assert(false);
1832 return this;
1833 }
1834
TypeCheck(TypeChecker &,size_t)1835 Node *BinOp::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1836 assert(false);
1837 return this;
1838 }
1839
TypeCheck(TypeChecker &,size_t)1840 Node *Inlined::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1841 assert(false); // Generated after type-checker in optimizer.
1842 return this;
1843 }
1844
TypeCheck(TypeChecker & tc,size_t reqret)1845 Node *Or::TypeCheck(TypeChecker &tc, size_t reqret) {
1846 TypeRef dummy;
1847 tc.TypeCheckAndOr(*this, false, reqret, dummy);
1848 return this;
1849 }
1850
TypeCheck(TypeChecker & tc,size_t reqret)1851 Node *And::TypeCheck(TypeChecker &tc, size_t reqret) {
1852 TypeRef dummy;
1853 tc.TypeCheckAndOr(*this, false, reqret, dummy);
1854 return this;
1855 }
1856
TypeCheck(TypeChecker & tc,size_t reqret)1857 Node *If::TypeCheck(TypeChecker &tc, size_t reqret) {
1858 tc.TT(condition, 1, LT_BORROW);
1859 tc.NoStruct(*condition, "if");
1860 tc.DecBorrowers(condition->lt, *this);
1861 Value cval;
1862 bool isconst = condition->ConstVal(tc, cval);
1863 if (!Is<DefaultVal>(falsepart)) {
1864 if (!isconst) {
1865 auto tleft = tc.TypeCheckBranch(true, condition, truepart, reqret, LT_ANY);
1866 auto tright = tc.TypeCheckBranch(false, condition, falsepart, reqret, LT_ANY);
1867 // FIXME: this is a bit of a hack. Much better if we had an actual type
1868 // to signify NORETURN, to be taken into account in more places.
1869 auto truec = AssertIs<Call>(truepart);
1870 auto falsec = AssertIs<Call>(falsepart);
1871 if (tc.NeverReturns(truec)) {
1872 exptype = tright;
1873 lt = falsepart->lt;
1874 } else if (tc.NeverReturns(falsec)) {
1875 exptype = tleft;
1876 lt = truepart->lt;
1877 } else {
1878 exptype = tc.Union(tleft, tright, true, this);
1879 // These will potentially make either body from T_CALL into some
1880 // coercion.
1881 tc.SubType(truepart, exptype, "then branch", *this);
1882 tc.SubType(falsepart, exptype, "else branch", *this);
1883 lt = tc.LifetimeUnion(truepart, falsepart, false);
1884 }
1885 } else if (cval.True()) {
1886 // Ignore the else part, optimizer guaranteed to cull it.
1887 exptype = tc.TypeCheckBranch(true, condition, truepart, reqret, LT_ANY);
1888 lt = truepart->lt;
1889 } else {
1890 // Ignore the then part, optimizer guaranteed to cull it.
1891 exptype = tc.TypeCheckBranch(false, condition, falsepart, reqret, LT_ANY);
1892 lt = falsepart->lt;
1893 }
1894 } else {
1895 // No else: this always returns void.
1896 if (!isconst || cval.True()) {
1897 tc.TypeCheckBranch(true, condition, truepart, 0, LT_ANY);
1898 truepart->exptype = type_void;
1899 } else {
1900 // constant == false: this if-then will get optimized out entirely, ignore it.
1901 }
1902 falsepart->exptype = type_void;
1903 exptype = type_void;
1904 lt = LT_ANY;
1905 }
1906 return this;
1907 }
1908
TypeCheck(TypeChecker & tc,size_t)1909 Node *While::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
1910 tc.TT(condition, 1, LT_BORROW);
1911 tc.NoStruct(*condition, "while");
1912 tc.DecBorrowers(condition->lt, *this);
1913 // FIXME: this is caused by call forced to LT_KEEP.
1914 auto condc = AssertIs<Call>(Forward<ToLifetime>(condition));
1915 auto condexp = AssertIs<Return>(condc->sf->body->children.back());
1916 tc.TypeCheckBranch(true, condexp->child, body, 0, LT_ANY);
1917 exptype = type_void;
1918 lt = LT_ANY;
1919 return this;
1920 }
1921
TypeCheck(TypeChecker & tc,size_t)1922 Node *For::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
1923 // FIXME: would be good to detect when iter is not written to, so ForLoopElem can be LT_BORROW.
1924 // Alternatively we could IncBorrowers on iter, but that would be very restrictive.
1925 tc.TT(iter, 1, LT_BORROW);
1926 auto itertype = iter->exptype;
1927 if (itertype->t == V_INT) {}
1928 else if (itertype->t == V_STRING)
1929 itertype = type_int;
1930 else if (itertype->t == V_VECTOR)
1931 itertype = itertype->Element();
1932 else tc.TypeError("for can only iterate over int / string / vector, not: " +
1933 TypeName(itertype), *this);
1934 auto bodyc = AssertIs<Call>(body);
1935 auto &args = bodyc->children;
1936 if (args.size()) {
1937 args[0]->exptype = itertype; // ForLoopElem
1938 }
1939 tc.TT(body, 0, LT_ANY);
1940 tc.DecBorrowers(iter->lt, *this);
1941 // Currently always return V_NIL
1942 exptype = type_void;
1943 lt = LT_ANY;
1944 return this;
1945 }
1946
TypeCheck(TypeChecker &,size_t)1947 Node *ForLoopElem::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1948 // Already been assigned a type in For.
1949 lt = LT_KEEP;
1950 return this;
1951 }
1952
TypeCheck(TypeChecker &,size_t)1953 Node *ForLoopCounter::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
1954 exptype = type_int;
1955 lt = LT_ANY;
1956 return this;
1957 }
1958
TypeCheck(TypeChecker & tc,size_t reqret)1959 Node *Switch::TypeCheck(TypeChecker &tc, size_t reqret) {
1960 // TODO: much like If, should only typecheck one case if the value is constant, and do
1961 // the corresponding work in the optimizer.
1962 tc.TT(value, 1, LT_BORROW);
1963 auto ptype = value->exptype;
1964 if (!ptype->Numeric() && ptype->t != V_STRING)
1965 tc.TypeError("switch value must be int / float / string", *this);
1966 exptype = nullptr;
1967 bool have_default = false;
1968 vector<bool> enum_cases;
1969 if (ptype->IsEnum()) enum_cases.resize(ptype->e->vals.size());
1970 for (auto &n : cases->children) {
1971 tc.TT(n, reqret, LT_KEEP);
1972 auto cas = AssertIs<Case>(n);
1973 if (cas->pattern->children.empty()) have_default = true;
1974 for (auto c : cas->pattern->children) {
1975 tc.SubTypeT(c->exptype, ptype, *c, "", "case");
1976 tc.DecBorrowers(c->lt, *cas);
1977 if (ptype->IsEnum()) {
1978 assert(c->exptype->IsEnum());
1979 Value v;
1980 if (c->ConstVal(tc, v)) {
1981 for (auto [i, ev] : enumerate(ptype->e->vals)) if (ev->val == v.ival()) {
1982 enum_cases[i] = true;
1983 break;
1984 }
1985 }
1986 }
1987 }
1988 auto body = AssertIs<Call>(cas->body);
1989 if (!tc.NeverReturns(body)) {
1990 exptype = exptype.Null() ? body->exptype
1991 : tc.Union(exptype, body->exptype, true, cas);
1992 }
1993 }
1994 for (auto n : cases->children) {
1995 auto cas = AssertIs<Case>(n);
1996 auto body = AssertIs<Call>(cas->body);
1997 if (!tc.NeverReturns(body)) {
1998 assert(!exptype.Null());
1999 tc.SubType(cas->body, exptype, "", "case block");
2000 }
2001 }
2002 if (exptype.Null()) exptype = type_void; // Empty switch or all return statements.
2003 if (!have_default) {
2004 if (reqret) tc.TypeError("switch that returns a value must have a default case", *this);
2005 if (ptype->IsEnum()) {
2006 for (auto [i, ev] : enumerate(ptype->e->vals)) if (!enum_cases[i])
2007 tc.TypeError("enum value not tested in switch: " + ev->name, *value);
2008 }
2009 }
2010 tc.DecBorrowers(value->lt, *this);
2011 lt = LT_KEEP;
2012 return this;
2013 }
2014
TypeCheck(TypeChecker & tc,size_t reqret)2015 Node *Case::TypeCheck(TypeChecker &tc, size_t reqret) {
2016 // FIXME: Since string constants are the real use case, LT_KEEP would be more
2017 // natural here, as this will introduce a lot of keeprefs. Alternatively make sure
2018 // string consts don't introduce keeprefs.
2019 tc.TypeCheckList(pattern, false, 1, LT_BORROW);
2020 tc.TT(body, reqret, LT_KEEP);
2021 exptype = body->exptype;
2022 lt = LT_KEEP;
2023 return this;
2024 }
2025
TypeCheck(TypeChecker & tc,size_t)2026 Node *Range::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2027 tc.TT(start, 1, LT_KEEP);
2028 tc.TT(end, 1, LT_KEEP);
2029 exptype = start->exptype;
2030 if (exptype->t != end->exptype->t || !exptype->Numeric())
2031 tc.TypeError("range can only be two equal numeric types", *this);
2032 lt = LT_ANY;
2033 return this;
2034 }
2035
TypeCheck(TypeChecker & tc,size_t)2036 Node *CoDot::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2037 tc.TT(coroutine, 1, LT_BORROW);
2038 // Leave right ident untypechecked.
2039 tc.SubType(coroutine, type_coroutine, "coroutine", *this);
2040 auto sf = coroutine->exptype->sf;
2041 Arg *uarg = nullptr;
2042 // This ident is not necessarily the right one.
2043 auto var = AssertIs<IdentRef>(variable);
2044 auto &name = var->sid->id->name;
2045 for (auto &arg : sf->coyieldsave.v) if (arg.sid->id->name == name) {
2046 if (uarg) tc.TypeError("multiple coroutine variables named: " + name, *this);
2047 uarg = &arg;
2048 }
2049 if (!uarg) tc.TypeError("no coroutine variables named: " + name, *this);
2050 var->sid = uarg->sid;
2051 var->exptype = exptype = uarg->type;
2052 // FIXME: this really also borrows from the actual variable, in case the coroutine is run
2053 // again?
2054 lt = coroutine->lt;
2055 return this;
2056 }
2057
TypeCheck(TypeChecker & tc,size_t)2058 Node *Define::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2059 for (auto &p : sids) {
2060 tc.UpdateCurrentSid(p.first);
2061 // We have to set these here just in case the init exp is a function/coroutine call that
2062 // tries use/assign this variable, type_undefined will force that to be an error.
2063 // TODO: could make this a specialized error, but probably not worth it because it is rare.
2064 p.first->type = type_undefined;
2065 p.first->lt = LT_UNDEF;
2066 }
2067 // We default to LT_KEEP here.
2068 // There are case where we could allow borrow, but in practise this runs into trouble easily:
2069 // - Variables that later get assigned (!sid->id->single_assignment) where taking ownership
2070 // was really what was intended (since the lval being assigned from may go away).
2071 // - old := cur cases, where old is meant to hang on to the previous value as cur gets updated,
2072 // which then runs into borrowing errors.
2073 tc.TT(child, sids.size(), LT_KEEP);
2074 for (auto [i, p] : enumerate(sids)) {
2075 auto var = TypeLT(*child, i);
2076 if (!p.second.Null()) {
2077 var.type = p.second;
2078 // Have to subtype the initializer value, as that node may contain
2079 // unbound vars (a:[int] = []) or values that that need to be coerced
2080 // (a:float = 1)
2081 tc.SubType(child, var.type, "initializer", "definition");
2082 }
2083 auto sid = p.first;
2084 sid->type = var.type;
2085 tc.StorageType(var.type, *this);
2086 sid->type = var.type;
2087 sid->lt = var.lt;
2088 LOG_DEBUG("var: ", sid->id->name, ":", TypeName(var.type));
2089 if (sid->id->logvar) {
2090 for (auto &sc : tc.scopes)
2091 if (sc.sf->iscoroutine)
2092 tc.TypeError("can\'t use log variable inside coroutine", *this);
2093 }
2094 }
2095 exptype = type_void;
2096 lt = LT_ANY;
2097 return this;
2098 }
2099
TypeCheck(TypeChecker & tc,size_t)2100 Node *AssignList::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2101 for (auto &c : children) {
2102 if (c != children.back()) {
2103 tc.TT(c, 1, LT_BORROW);
2104 tc.DecBorrowers(c->lt, *this);
2105 } else {
2106 tc.TT(c, children.size() - 1, LT_MULTIPLE /*unused*/, &children);
2107 }
2108 }
2109 for (size_t i = 0; i < children.size() - 1; i++) {
2110 auto left = children[i];
2111 tc.CheckLval(left);
2112 TypeRef righttype = children.back()->exptype->Get(i);
2113 FlowItem fi(*left, left->exptype);
2114 assert(fi.IsValid());
2115 tc.AssignFlowDemote(fi, righttype, false);
2116 tc.SubTypeT(righttype, left->exptype, *this, "right");
2117 tc.StorageType(left->exptype, *left);
2118 // TODO: should call tc.AssignFlowPromote(*left, vartype) here?
2119 }
2120 exptype = type_void;
2121 lt = LT_ANY;
2122 return this;
2123 }
2124
TypeCheck(TypeChecker &,size_t)2125 Node *IntConstant::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2126 exptype = from ? &from->e->thistype : type_int;
2127 lt = LT_ANY;
2128 return this;
2129 }
2130
TypeCheck(TypeChecker &,size_t)2131 Node *FloatConstant::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2132 exptype = type_float;
2133 lt = LT_ANY;
2134 return this;
2135 }
2136
TypeCheck(TypeChecker &,size_t)2137 Node *StringConstant::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2138 exptype = type_string;
2139 // The VM keeps all the constant strings for the length of the program,
2140 // so these can be borrow, avoiding a ton of keepvars when used in + and
2141 // builtin functions etc (at the cost of some increfs when stored in vars
2142 // and data structures).
2143 lt = STRING_CONSTANTS_KEEP ? LT_KEEP : LT_BORROW;
2144 return this;
2145 }
2146
TypeCheck(TypeChecker & tc,size_t)2147 Node *Nil::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2148 exptype = !giventype.Null() ? giventype : tc.st.Wrap(tc.NewTypeVar(), V_NIL);
2149 lt = LT_ANY;
2150 return this;
2151 }
2152
TypeCheck(TypeChecker & tc,size_t)2153 Node *Plus::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2154 tc.TypeCheckMathOp(*this);
2155 return this;
2156 }
2157
TypeCheck(TypeChecker & tc,size_t)2158 Node *Minus::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2159 tc.TypeCheckMathOp(*this);
2160 return this;
2161 }
2162
TypeCheck(TypeChecker & tc,size_t)2163 Node *Multiply::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2164 tc.TypeCheckMathOp(*this);
2165 return this;
2166 }
2167
TypeCheck(TypeChecker & tc,size_t)2168 Node *Divide::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2169 tc.TypeCheckMathOp(*this);
2170 return this;
2171 }
2172
TypeCheck(TypeChecker & tc,size_t)2173 Node *Mod::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2174 tc.TypeCheckMathOp(*this);
2175 return this;
2176 }
2177
TypeCheck(TypeChecker & tc,size_t)2178 Node *PlusEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2179 tc.TypeCheckMathOpEq(*this);
2180 return this;
2181 }
2182
TypeCheck(TypeChecker & tc,size_t)2183 Node *MultiplyEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2184 tc.TypeCheckMathOpEq(*this);
2185 return this;
2186 }
2187
TypeCheck(TypeChecker & tc,size_t)2188 Node *MinusEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2189 tc.TypeCheckMathOpEq(*this);
2190 return this;
2191 }
2192
TypeCheck(TypeChecker & tc,size_t)2193 Node *DivideEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2194 tc.TypeCheckMathOpEq(*this);
2195 return this;
2196 }
2197
TypeCheck(TypeChecker & tc,size_t)2198 Node *ModEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2199 tc.TypeCheckMathOpEq(*this);
2200 return this;
2201 }
2202
TypeCheck(TypeChecker & tc,size_t)2203 Node *NotEqual::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2204 tc.TypeCheckComp(*this);
2205 return this;
2206 }
2207
TypeCheck(TypeChecker & tc,size_t)2208 Node *Equal::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2209 tc.TypeCheckComp(*this);
2210 return this;
2211 }
2212
TypeCheck(TypeChecker & tc,size_t)2213 Node *GreaterThanEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2214 tc.TypeCheckComp(*this);
2215 return this;
2216 }
2217
TypeCheck(TypeChecker & tc,size_t)2218 Node *LessThanEq::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2219 tc.TypeCheckComp(*this);
2220 return this;
2221 }
2222
TypeCheck(TypeChecker & tc,size_t)2223 Node *GreaterThan::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2224 tc.TypeCheckComp(*this);
2225 return this;
2226 }
2227
TypeCheck(TypeChecker & tc,size_t)2228 Node *LessThan::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2229 tc.TypeCheckComp(*this);
2230 return this;
2231 }
2232
TypeCheck(TypeChecker & tc,size_t)2233 Node *Not::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2234 tc.TT(child, 1, LT_BORROW);
2235 tc.DecBorrowers(child->lt, *this);
2236 tc.NoStruct(*child, "not");
2237 exptype = &tc.st.default_bool_type->thistype;
2238 lt = LT_ANY;
2239 return this;
2240 }
2241
TypeCheck(TypeChecker & tc,size_t)2242 Node *BitAnd::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2243 tc.TypeCheckBitOp(*this);
2244 return this;
2245 }
2246
TypeCheck(TypeChecker & tc,size_t)2247 Node *BitOr::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2248 tc.TypeCheckBitOp(*this);
2249 return this;
2250 }
2251
TypeCheck(TypeChecker & tc,size_t)2252 Node *Xor::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2253 tc.TypeCheckBitOp(*this);
2254 return this;
2255 }
2256
TypeCheck(TypeChecker & tc,size_t)2257 Node *ShiftLeft::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2258 tc.TypeCheckBitOp(*this);
2259 return this;
2260 }
2261
TypeCheck(TypeChecker & tc,size_t)2262 Node *ShiftRight::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2263 tc.TypeCheckBitOp(*this);
2264 return this;
2265 }
2266
TypeCheck(TypeChecker & tc,size_t)2267 Node *Negate::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2268 tc.TT(child, 1, LT_BORROW);
2269 tc.SubType(child, type_int, "negated value", *this);
2270 tc.DecBorrowers(child->lt, *this);
2271 exptype = child->exptype;
2272 lt = LT_ANY;
2273 return this;
2274 }
2275
TypeCheck(TypeChecker & tc,size_t)2276 Node *PostDecr::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2277 tc.TypeCheckPlusPlus(*this);
2278 return this;
2279 }
2280
TypeCheck(TypeChecker & tc,size_t)2281 Node *PostIncr::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2282 tc.TypeCheckPlusPlus(*this);
2283 return this;
2284 }
2285
TypeCheck(TypeChecker & tc,size_t)2286 Node *PreDecr::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2287 tc.TypeCheckPlusPlus(*this);
2288 return this;
2289 }
2290
TypeCheck(TypeChecker & tc,size_t)2291 Node *PreIncr::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2292 tc.TypeCheckPlusPlus(*this);
2293 return this;
2294 }
2295
TypeCheck(TypeChecker & tc,size_t)2296 Node *UnaryMinus::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2297 tc.TT(child, 1, LT_BORROW);
2298 exptype = child->exptype;
2299 if (!exptype->Numeric() &&
2300 (exptype->t != V_STRUCT_S || !exptype->udt->sametype->Numeric()))
2301 tc.TypeError("numeric / numeric struct", exptype, *this);
2302 tc.DecBorrowers(child->lt, *this);
2303 lt = LT_KEEP;
2304 return this;
2305 }
2306
TypeCheck(TypeChecker & tc,size_t)2307 Node *IdentRef::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2308 tc.UpdateCurrentSid(sid);
2309 for (auto &sc : reverse(tc.scopes)) if (sc.sf == sid->sf_def) goto in_scope;
2310 tc.TypeError("free variable not in scope: " + sid->id->name, *this);
2311 in_scope:
2312 exptype = tc.TypeCheckId(sid);
2313 FlowItem fi(*this, exptype);
2314 assert(fi.IsValid());
2315 exptype = tc.UseFlow(fi);
2316 lt = tc.PushBorrow(this);
2317 return this;
2318 }
2319
TypeCheck(TypeChecker & tc,size_t)2320 Node *Assign::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2321 tc.TT(left, 1, LT_BORROW);
2322 tc.DecBorrowers(left->lt, *this);
2323 tc.TT(right, 1, tc.LvalueLifetime(*left, false));
2324 tc.CheckLval(left);
2325 FlowItem fi(*left, left->exptype);
2326 if (fi.IsValid()) {
2327 left->exptype = tc.AssignFlowDemote(fi, right->exptype, true);
2328 }
2329 tc.SubType(right, left->exptype, "right", *this);
2330 if (fi.IsValid()) tc.AssignFlowPromote(*left, right->exptype);
2331 exptype = left->exptype;
2332 if (fi.IsValid()) exptype = tc.UseFlow(fi);
2333 lt = tc.PushBorrow(left);
2334 return this;
2335 }
2336
TypeCheck(TypeChecker & tc,size_t reqret)2337 Node *DefaultVal::TypeCheck(TypeChecker &tc, size_t reqret) {
2338 // This is used as a default value for native call arguments. The variable
2339 // makes it equal to whatever the function expects, then codegen can use that type
2340 // to generate a correct value.
2341 // Also used as an empty else branch.
2342 exptype = reqret ? tc.NewTypeVar() : type_void;
2343 lt = LT_ANY;
2344 return this;
2345 }
2346
TypeCheck(TypeChecker & tc,size_t reqret)2347 Node *GenericCall::TypeCheck(TypeChecker &tc, size_t reqret) {
2348 // Here we decide which of Dot / Call / NativeCall this call should be transformed into.
2349 tc.TypeCheckList(this, false, 1, LT_ANY);
2350 auto nf = tc.parser.natreg.FindNative(name);
2351 auto fld = tc.st.FieldUse(name);
2352 TypeRef type;
2353 UDT *udt = nullptr;
2354 if (children.size()) {
2355 type = children[0]->exptype;
2356 if (IsUDT(type->t)) udt = type->udt;
2357 }
2358 Node *r = nullptr;
2359 if (fld && dotnoparens && udt && udt->Has(fld) >= 0) {
2360 auto dot = new Dot(fld, *this);
2361 dot->children = children;
2362 dot->TypeCheckSpecialized(tc, reqret);
2363 r = dot;
2364 } else {
2365 // See if any of sf's specializations matches type exactly, then it overrides nf.
2366 bool prefer_sf = false;
2367 if (sf && udt && sf->parent->nargs()) {
2368 for (auto sfi : sf->parent->overloads) {
2369 if (sfi->args.v[0].type->udt == udt) {
2370 prefer_sf = true;
2371 break;
2372 }
2373 }
2374 }
2375 if (nf && !prefer_sf) {
2376 auto nc = new NativeCall(nf, *this);
2377 nc->children = children;
2378 nc->TypeCheckSpecialized(tc, reqret);
2379 r = nc;
2380 } else if (sf) {
2381 auto fc = new Call(*this);
2382 fc->children = children;
2383 fc->TypeCheckSpecialized(tc, reqret);
2384 r = fc;
2385 } else {
2386 if (fld && dotnoparens)
2387 tc.TypeError("type " + TypeName(type) + " does not have field: " + fld->name, *this);
2388 tc.TypeError("unknown field/function reference: " + name, *this);
2389 }
2390 }
2391 children.clear();
2392 delete this;
2393 return r;
2394 }
2395
TypeCheckSpecialized(TypeChecker & tc,size_t)2396 void NativeCall::TypeCheckSpecialized(TypeChecker &tc, size_t /*reqret*/) {
2397 if (nf->first->overloads) {
2398 // Multiple overloads available, figure out which we want to call.
2399 auto cnf = nf->first;
2400 auto nargs = Arity();
2401 for (; cnf; cnf = cnf->overloads) {
2402 if (cnf->args.v.size() != nargs) continue;
2403 for (auto [i, arg] : enumerate(cnf->args.v)) {
2404 // Special purpose treatment of V_ANY to allow generic vectors in overloaded
2405 // length() etc.
2406 if (arg.type->t != V_ANY &&
2407 (arg.type->t != V_VECTOR ||
2408 children[i]->exptype->t != V_VECTOR ||
2409 arg.type->sub->t != V_ANY) &&
2410 !tc.ConvertsTo(children[i]->exptype,
2411 tc.ActualBuiltinType(arg.fixed_len, arg.type, arg.flags,
2412 children[i], nf, true, i + 1, *this),
2413 arg.type->t != V_STRING, false)) goto nomatch;
2414 }
2415 nf = cnf;
2416 break;
2417 nomatch:;
2418 }
2419 if (!cnf)
2420 tc.NatCallError("arguments match no overloads of ", nf, *this);
2421 }
2422 vector<TypeRef> argtypes(children.size());
2423 for (auto [i, c] : enumerate(children)) {
2424 auto &arg = nf->args.v[i];
2425 auto argtype = tc.ActualBuiltinType(arg.fixed_len, arg.type, arg.flags, children[i], nf, false, i + 1, *this);
2426 // Filter out functions that are not struct aware.
2427 bool typed = false;
2428 if (argtype->t == V_NIL && argtype->sub->Numeric() && !Is<DefaultVal>(c)) {
2429 // This is somewhat of a hack, because we conflate V_NIL with being optional
2430 // for native functions, but we don't want numeric types to be nilable.
2431 // Codegen has a special case for T_DEFAULTVAL however.
2432 argtype = argtype->sub;
2433 }
2434 if (arg.flags & NF_CONVERTANYTOSTRING && c->exptype->t != V_STRING) {
2435 tc.AdjustLifetime(c, LT_BORROW); // MakeString wants to borrow.
2436 tc.MakeString(c, arg.lt);
2437 argtype = type_string;
2438 typed = true;
2439 }
2440 int flag = NF_SUBARG1;
2441 for (int sa = 0; sa < 3; sa++) {
2442 if (arg.flags & flag) {
2443 tc.SubType(c,
2444 nf->args.v[sa].type->t == V_VECTOR && argtype->t != V_VECTOR
2445 ? argtypes[sa]->sub
2446 : argtypes[sa],
2447 tc.ArgName(i),
2448 nf->name);
2449 // Stop these generic params being turned into any by SubType below.
2450 typed = true;
2451 }
2452 flag *= 2;
2453 }
2454 if (arg.flags & NF_ANYVAR) {
2455 if (argtype->t == V_VECTOR)
2456 argtype = tc.st.Wrap(tc.NewTypeVar(), V_VECTOR);
2457 else if (argtype->t == V_ANY) argtype = tc.NewTypeVar();
2458 else assert(0);
2459 }
2460 if (arg.flags & NF_CORESUME) {
2461 // Specialized typechecking for resume()
2462 assert(argtypes[0]->t == V_COROUTINE);
2463 auto csf = argtypes[0]->sf;
2464 if (csf) {
2465 tc.SubType(c, csf->coresumetype, "resume value", *c);
2466 } else {
2467 if (!Is<DefaultVal>(c))
2468 tc.TypeError("cannot resume a generic coroutine type with an argument",
2469 *this);
2470 }
2471 if (c->exptype->t == V_VAR) {
2472 // No value supplied to resume, and none expected at yield either.
2473 // nil will be supplied, so make type reflect that.
2474 tc.UnifyVar(tc.NewNilTypeVar(), c->exptype);
2475 }
2476 typed = true;
2477 }
2478 if (argtype->t == V_ANY) {
2479 if (!arg.flags) {
2480 // Special purpose type checking to allow any reference type for functions like
2481 // copy/equal/hash etc. Note that this is the only place in the language where
2482 // we allow this!
2483 if (!IsRefNilNoStruct(c->exptype->t))
2484 tc.TypeError("reference type", c->exptype, *c, nf->args.GetName(i), nf->name);
2485 typed = true;
2486 } else if (IsStruct(c->exptype->t) &&
2487 !(arg.flags & NF_PUSHVALUEWIDTH) &&
2488 c->exptype->udt->numslots > 1) {
2489 // Avoid unsuspecting generic functions taking values as args.
2490 // TODO: ideally this does not trigger for any functions.
2491 tc.TypeError("function does not support this struct type", *this);
2492 }
2493 }
2494 if (nf->fun.fnargs >= 0 && !arg.fixed_len && !(arg.flags & NF_PUSHVALUEWIDTH))
2495 tc.NoStruct(*c, nf->name);
2496 if (!typed)
2497 tc.SubType(c, argtype, tc.ArgName(i), nf->name);
2498 auto actualtype = c->exptype;
2499 if (actualtype->IsFunction()) {
2500 // We must assume this is going to get called and type-check it
2501 auto fsf = actualtype->sf;
2502 if (fsf->args.v.size()) {
2503 // we have no idea what args.
2504 tc.TypeError("function passed to " + nf->name +
2505 " cannot take any arguments", *this);
2506 }
2507 auto chosen = fsf;
2508 List args(tc.parser.lex);
2509 int vtable_idx = -1;
2510 tc.TypeCheckCall(fsf, &args, chosen, *c, false, vtable_idx);
2511 assert(vtable_idx < 0);
2512 assert(fsf == chosen);
2513 }
2514 argtypes[i] = actualtype;
2515 tc.StorageType(actualtype, *this);
2516 tc.AdjustLifetime(c, arg.lt);
2517 tc.DecBorrowers(c->lt, *this);
2518 }
2519
2520 exptype = type_void; // no retvals
2521 lt = LT_ANY;
2522 if (nf->retvals.v.size() > 1) exptype = tc.NewTuple(nf->retvals.v.size());
2523 for (auto [i, ret] : enumerate(nf->retvals.v)) {
2524 int sa = 0;
2525 auto type = ret.type;
2526 auto rlt = ret.lt;
2527 switch (ret.flags) {
2528 case NF_SUBARG3: sa++;
2529 case NF_SUBARG2: sa++;
2530 case NF_SUBARG1: {
2531 type = argtypes[sa];
2532 auto nftype = nf->args.v[sa].type;
2533
2534 if (nftype->t == V_TYPEID) {
2535 assert(!sa); // assumes always first.
2536 auto tin = AssertIs<TypeOf>(children[0]);
2537 if (!Is<DefaultVal>(tin->child)) type = tin->child->exptype;
2538 }
2539
2540 if (ret.type->t == V_NIL) {
2541 if (!IsNillable(type->t))
2542 tc.TypeError(cat("argument ", sa + 1, " to ", nf->name,
2543 " has to be a reference type"), *this);
2544 type = tc.st.Wrap(type, V_NIL);
2545 } else if (nftype->t == V_VECTOR && ret.type->t != V_VECTOR) {
2546 if (type->t == V_VECTOR) type = type->sub;
2547 } else if (nftype->t == V_COROUTINE || nftype->t == V_FUNCTION) {
2548 auto csf = type->sf;
2549 if (csf) {
2550 // In theory it is possible this hasn't been generated yet..
2551 type = csf->returntype;
2552 } else {
2553 // This can happen when typechecking a multimethod with a coroutine arg.
2554 tc.TypeError(cat("cannot call ", nf->name, " on generic coroutine type"),
2555 *this);
2556 }
2557 }
2558 if (rlt == LT_BORROW) {
2559 auto alt = nf->args.v[sa].lt;
2560 assert(alt >= LT_BORROW);
2561 rlt = alt;
2562 }
2563 break;
2564 }
2565 case NF_ANYVAR:
2566 type = ret.type->t == V_VECTOR ? tc.st.Wrap(tc.NewTypeVar(), V_VECTOR)
2567 : tc.NewTypeVar();
2568 assert(rlt == LT_KEEP);
2569 break;
2570 }
2571 type = tc.ActualBuiltinType(ret.fixed_len, type, ret.flags,
2572 !i && Arity() ? children[0] : nullptr, nf, false,
2573 0, *this);
2574 if (!IsRefNilVar(type->t)) rlt = LT_ANY;
2575 if (nf->retvals.v.size() > 1) {
2576 exptype->Set(i, type.get(), rlt);
2577 lt = LT_MULTIPLE;
2578 } else {
2579 exptype = type;
2580 lt = rlt;
2581 }
2582 }
2583
2584 if (nf->IsAssert()) {
2585 // Special case, add to flow:
2586 tc.CheckFlowTypeChanges(true, children[0]);
2587 // Also make result non-nil, if it was.
2588 if (exptype->t == V_NIL) exptype = exptype->Element();
2589 }
2590
2591 nattype = exptype;
2592 natlt = lt;
2593 }
2594
TypeCheckSpecialized(TypeChecker & tc,size_t reqret)2595 void Call::TypeCheckSpecialized(TypeChecker &tc, size_t reqret) {
2596 sf = tc.PreSpecializeFunction(sf);
2597 exptype = tc.TypeCheckCall(sf, this, sf, *this, reqret, vtable_idx);
2598 lt = sf->ltret;
2599 }
2600
TypeCheck(TypeChecker & tc,size_t)2601 Node *FunRef::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2602 sf = tc.PreSpecializeFunction(sf);
2603 exptype = &sf->thistype;
2604 lt = LT_ANY;
2605 return this;
2606 }
2607
TypeCheck(TypeChecker & tc,size_t reqret)2608 Node *DynCall::TypeCheck(TypeChecker &tc, size_t reqret) {
2609 tc.UpdateCurrentSid(sid);
2610 tc.TypeCheckId(sid);
2611 //if (sid->type->IsFunction()) sid->type = &tc.PreSpecializeFunction(sid->type->sf)->thistype;
2612 tc.TypeCheckList(this, false, 1, LT_ANY);
2613 tie(exptype, lt) = tc.TypeCheckDynCall(sid, this, sf, reqret);
2614 return this;
2615 }
2616
TypeCheck(TypeChecker & tc,size_t)2617 Node *Return::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2618 exptype = type_void;
2619 lt = LT_ANY;
2620 for (auto isc : reverse(tc.scopes)) {
2621 if (isc.sf->parent == sf->parent) {
2622 sf = isc.sf; // Take specialized version.
2623 break;
2624 }
2625 tc.CheckReturnPast(isc.sf, sf, *this);
2626 }
2627 // TODO: LT_KEEP here is to keep it simple for now, since ideally we want to also allow
2628 // LT_BORROW, but then we have to prove that we don't outlive the owner.
2629 // Additionally, we have to do this for reused specializations on new SpecIdents.
2630 auto reqlt = LT_KEEP;
2631 auto reqret = make_void ? 0 : sf->reqret;
2632 // Special (but very common) case: optimize lifetime for "return var" case, where var owns
2633 // and this is the only return statement. Without this we'd get an inc on the var that's
2634 // immediately undone as the scope ends.
2635 auto ir = Is<IdentRef>(child);
2636 if (ir) {
2637 tc.UpdateCurrentSid(ir->sid); // Ahead of time, because ir not typechecked yet.
2638 if (ir->sid->lt == LT_KEEP &&
2639 ir->sid->sf_def == sf &&
2640 sf->num_returns == 0 &&
2641 reqret &&
2642 sf->body->children.back() == this) {
2643 reqlt = LT_BORROW; // Fake that we're cool borrowing this.
2644 ir->sid->consume_on_last_use = true; // Don't decref this one when going out of scope.
2645 }
2646 }
2647 tc.TT(child, reqret, reqlt);
2648 tc.DecBorrowers(child->lt, *this);
2649 if (sf == tc.st.toplevel) {
2650 // return from program
2651 if (child->exptype->NumValues() > 1)
2652 tc.TypeError("cannot return multiple values from top level", *this);
2653 }
2654 auto nsf = tc.TopScope(tc.named_scopes);
2655 if (nsf != sf) {
2656 // This is a non-local "return from".
2657 if (!sf->typechecked)
2658 tc.parser.Error("return from " + sf->parent->name +
2659 " called out of context", this);
2660 }
2661 auto never_returns = tc.NeverReturns(child);
2662 if (never_returns && make_void && sf->num_returns) {
2663 // A return with other returns inside of it that always bypass this return,
2664 // so should not contribute to return types.
2665 assert(child->exptype->t == V_VOID || child->exptype->t == V_VAR);
2666 return this;
2667 }
2668 if (never_returns && sf->reqret && sf->parent->anonymous) {
2669 // A return to the immediately enclosing anonymous function that needs to return a value
2670 // but is bypassed.
2671 tc.RetVal(child->exptype, sf, *this); // If it's a variable, bind it.
2672 return this;
2673 }
2674 if (!Is<DefaultVal>(child)) {
2675 if (auto mrs = Is<MultipleReturn>(child)) {
2676 tc.RetVal(mrs->exptype, sf, *this);
2677 for (auto [i, mr] : enumerate(mrs->children)) {
2678 if (i < sf->reqret)
2679 tc.SubType(mr, sf->returntype->Get(i), tc.ArgName(i), *this);
2680 }
2681 } else {
2682 tc.RetVal(child->exptype, sf, *this);
2683 tc.SubType(child, sf->returntype, "", *this);
2684 }
2685 } else {
2686 tc.RetVal(type_void, sf, *this);
2687 tc.SubType(child, sf->returntype, "", *this);
2688 }
2689 return this;
2690 }
2691
TypeCheck(TypeChecker &,size_t)2692 Node *TypeAnnotation::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2693 exptype = giventype;
2694 lt = LT_ANY;
2695 return this;
2696 }
2697
TypeCheck(TypeChecker & tc,size_t)2698 Node *IsType::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2699 tc.TT(child, 1, LT_BORROW);
2700 tc.NoStruct(*child, "is"); // FIXME
2701 tc.DecBorrowers(child->lt, *this);
2702 exptype = &tc.st.default_bool_type->thistype;
2703 lt = LT_ANY;
2704 return this;
2705 }
2706
TypeCheck(TypeChecker & tc,size_t)2707 Node *Constructor::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2708 tc.TypeCheckList(this, false, 1, LT_KEEP);
2709 exptype = giventype;
2710 if (exptype.Null()) {
2711 if (Arity()) {
2712 // No type was specified.. first find union of all elements.
2713 TypeRef u(nullptr);
2714 for (auto c : children) {
2715 u = u.Null() ? c->exptype : tc.Union(u, c->exptype, true, c);
2716 }
2717 exptype = tc.st.Wrap(u, V_VECTOR);
2718 tc.StorageType(exptype, *this);
2719 } else {
2720 // special case for empty vectors
2721 exptype = tc.st.Wrap(tc.NewTypeVar(), V_VECTOR);
2722 }
2723 }
2724 if (IsUDT(exptype->t)) {
2725 // We have to check this here, since the parser couldn't check this yet.
2726 if (exptype->udt->fields.v.size() < children.size())
2727 tc.TypeError("too many initializers for: " + exptype->udt->name, *this);
2728 auto udt = tc.FindStructSpecialization(exptype->udt, this);
2729 exptype = &udt->thistype;
2730 }
2731 for (auto [i, c] : enumerate(children)) {
2732 TypeRef elemtype = IsUDT(exptype->t) ? exptype->udt->fields.v[i].type
2733 : exptype->Element();
2734 tc.SubType(c, elemtype, tc.ArgName(i), *this);
2735 }
2736 lt = LT_KEEP;
2737 return this;
2738 }
2739
TypeCheckSpecialized(TypeChecker & tc,size_t)2740 void Dot::TypeCheckSpecialized(TypeChecker &tc, size_t /*reqret*/) {
2741 tc.AdjustLifetime(children[0], LT_BORROW);
2742 tc.DecBorrowers(children[0]->lt, *this); // New borrow created below.
2743 auto stype = children[0]->exptype;
2744 if (!IsUDT(stype->t))
2745 tc.TypeError("class/struct", stype, *this, "object");
2746 auto udt = stype->udt;
2747 auto fieldidx = udt->Has(fld);
2748 if (fieldidx < 0)
2749 tc.TypeError("type " + udt->name + " has no field named " + fld->name, *this);
2750 exptype = udt->fields.v[fieldidx].type;
2751 FlowItem fi(*this, exptype);
2752 if (fi.IsValid()) exptype = tc.UseFlow(fi);
2753 lt = tc.PushBorrow(this);
2754 //lt = children[0]->lt; // Also LT_BORROW, also depending on the same variable.
2755 }
2756
TypeCheck(TypeChecker & tc,size_t)2757 Node *Indexing::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2758 tc.TT(object, 1, LT_BORROW);
2759 tc.TT(index, 1, LT_BORROW);
2760 tc.DecBorrowers(index->lt, *this);
2761 auto vtype = object->exptype;
2762 if (vtype->t != V_VECTOR &&
2763 vtype->t != V_STRING &&
2764 (!IsStruct(vtype->t) || !vtype->udt->sametype->Numeric()))
2765 tc.TypeError("vector/string/numeric struct", vtype, *this, "container");
2766 auto itype = index->exptype;
2767 switch (itype->t) {
2768 case V_INT:
2769 exptype = vtype->t == V_VECTOR
2770 ? vtype->Element()
2771 : (IsUDT(vtype->t) ? vtype->udt->sametype : type_int);
2772 break;
2773 case V_STRUCT_S: {
2774 if (vtype->t != V_VECTOR)
2775 tc.TypeError("multi-dimensional indexing on non-vector", *this);
2776 auto &udt = *itype->udt;
2777 exptype = vtype;
2778 for (auto &field : udt.fields.v) {
2779 if (field.type->t != V_INT)
2780 tc.TypeError("int field", field.type, *this, "index");
2781 if (exptype->t != V_VECTOR)
2782 tc.TypeError("nested vector", exptype, *this, "container");
2783 exptype = exptype->Element();
2784 }
2785 break;
2786 }
2787 default: tc.TypeError("int/struct of int", itype, *this, "index");
2788 }
2789 lt = object->lt; // Also LT_BORROW, also depending on the same variable.
2790 return this;
2791 }
2792
TypeCheck(TypeChecker & tc,size_t reqret)2793 Node *Seq::TypeCheck(TypeChecker &tc, size_t reqret) {
2794 tc.TT(head, 0, LT_ANY);
2795 tc.TT(tail, reqret, LT_ANY);
2796 exptype = tail->exptype;
2797 lt = tail->lt;
2798 return this;
2799 }
2800
TypeCheck(TypeChecker &,size_t)2801 Node *CoClosure::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2802 exptype = type_function_cocl;
2803 lt = LT_ANY;
2804 return this;
2805 }
2806
TypeCheck(TypeChecker & tc,size_t)2807 Node *CoRoutine::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2808 tc.TT(call, 1, LT_KEEP);
2809 tc.NoStruct(*call, "coroutine call return value"); // FIXME
2810 if (auto fc = Is<Call>(call)) {
2811 auto sf = fc->sf;
2812 assert(sf->iscoroutine);
2813 auto ct = tc.st.NewType();
2814 *ct = Type(V_COROUTINE, sf);
2815 exptype = ct;
2816 } else {
2817 tc.TypeError("coroutine constructor must be regular function call", *call);
2818 }
2819 lt = LT_KEEP;
2820 return this;
2821 }
2822
TypeCheck(TypeChecker & tc,size_t)2823 Node *TypeOf::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2824 tc.TT(child, 1, LT_BORROW);
2825 tc.DecBorrowers(child->lt, *this);
2826 exptype = type_typeid;
2827 lt = LT_ANY;
2828 return this;
2829 }
2830
TypeCheck(TypeChecker & tc,size_t)2831 Node *EnumCoercion::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2832 tc.TT(child, 1, LT_BORROW);
2833 tc.SubType(child, type_int, "coerced value", *this);
2834 tc.DecBorrowers(child->lt, *this);
2835 exptype = &e->thistype;
2836 lt = LT_ANY;
2837 return this;
2838 }
2839
TypeCheck(TypeChecker & tc,size_t)2840 Node *MultipleReturn::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2841 tc.TypeCheckList(this, false, 1, LT_ANY);
2842 exptype = tc.NewTuple(children.size());
2843 for (auto [i, mrc] : enumerate(children))
2844 exptype->Set(i, mrc->exptype.get(), mrc->lt);
2845 lt = LT_MULTIPLE;
2846 return this;
2847 }
2848
TypeCheck(TypeChecker &,size_t)2849 Node *EnumRef::TypeCheck(TypeChecker & /*tc*/, size_t /*reqret*/) {
2850 return this;
2851 }
2852
TypeCheck(TypeChecker & tc,size_t)2853 Node *UDTRef::TypeCheck(TypeChecker &tc, size_t /*reqret*/) {
2854 for (auto [i, f] : enumerate(udt->fields.v)) {
2855 if (f.defaultval && f.type->t == V_ANY) {
2856 // FIXME: would be good to not call TT here generically but instead have some
2857 // specialized checking, just in case TT has a side effect.
2858 tc.TT(f.defaultval, 1, LT_ANY);
2859 tc.DecBorrowers(f.defaultval->lt, *this);
2860 f.defaultval->lt = LT_UNDEF;
2861 f.type = f.defaultval->exptype;
2862 }
2863 // FIXME: this is a temp limitation, remove.
2864 if (udt->thistype.t == V_STRUCT_R && i &&
2865 IsRefNil(f.type->t) != IsRefNil(udt->fields.v[0].type->t))
2866 tc.TypeError("structs fields must be either all scalar or all references: " +
2867 udt->name, *this);
2868 }
2869 if (!udt->ComputeSizes())
2870 tc.TypeError("structs cannot be self-referential: " + udt->name, *this);
2871 exptype = type_void;
2872 lt = LT_ANY;
2873 return this;
2874 }
2875
TypeCheck(TypeChecker & tc,size_t reqret)2876 Node *Coercion::TypeCheck(TypeChecker &tc, size_t reqret) {
2877 // These have been added by another specialization. We could check if they still apply, but
2878 // even more robust is just to remove them, and let them be regenerated if need be.
2879 tc.TT(child, reqret, LT_ANY);
2880 return tc.DeleteCoercion(this);
2881 }
2882
ConstVal(TypeChecker & tc,Value & val)2883 bool And::ConstVal(TypeChecker &tc, Value &val) const {
2884 return left->ConstVal(tc, val) && (!val.True() || right->ConstVal(tc, val));
2885 }
2886
ConstVal(TypeChecker & tc,Value & val)2887 bool Or::ConstVal(TypeChecker &tc, Value &val) const {
2888 return left->ConstVal(tc, val) && (val.True() || right->ConstVal(tc, val));
2889 }
2890
ConstVal(TypeChecker & tc,Value & val)2891 bool Not::ConstVal(TypeChecker &tc, Value &val) const {
2892 auto isconst = child->ConstVal(tc, val);
2893 val = Value(!val.True());
2894 return isconst;
2895 }
2896
ConstVal(TypeChecker & tc,Value & val)2897 bool IsType::ConstVal(TypeChecker &tc, Value &val) const {
2898 if (child->exptype == giventype || giventype->t == V_ANY) {
2899 val = Value(true);
2900 return true;
2901 }
2902 if (!tc.ConvertsTo(giventype, child->exptype, false)) {
2903 val = Value(false);
2904 return true;
2905 }
2906 // This means it is always a reference type, since int/float/function don't convert
2907 // into anything without coercion.
2908 return false;
2909 }
2910
ConstVal(TypeChecker & tc,Value & val)2911 bool EnumCoercion::ConstVal(TypeChecker &tc, Value &val) const {
2912 return child->ConstVal(tc, val);
2913 }
2914
2915 } // namespace lobster
2916