MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
check.cpp
Go to the documentation of this file.
1#include "mim/check.h"
2
3#include <absl/container/fixed_array.h>
4#include <fe/assert.h>
5
6#include "mim/rewrite.h"
7#include "mim/rule.h"
8#include "mim/world.h"
9
10namespace mim {
11
12bool Def::needs_zonk() const {
13 if (has_dep(Dep::Hole)) {
14 for (auto mut : local_muts())
15 if (Hole::isa_set(mut)) return true;
16 }
17
18 return false;
19}
20
21const Def* Def::zonk() const { return needs_zonk() ? world().zonker().rewrite(this) : this; }
22
23const Def* Def::zonk_mut() const {
24 if (!is_set()) return this;
25
26 if (auto mut = isa_mut()) {
27 if (auto hole = mut->isa<Hole>()) {
28 auto [last, op] = hole->find();
29 return op ? op->zonk() : last;
30 }
31
32 for (auto def : deps())
33 if (def->needs_zonk()) return world().zonker().rewire_mut(mut);
34
35 if (auto imm = mut->immutabilize()) return imm;
36 return this;
37 }
38
39 return zonk();
40}
41
43 return DefVec(defs.size(), [defs](size_t i) { return defs[i]->zonk(); });
44}
45
46/*
47 * Hole
48 */
49
50std::pair<Hole*, const Def*> Hole::find() {
51 auto def = Def::op(0);
52 auto last = this;
53
54 while (def) {
55 if (auto h = def->isa_mut<Hole>()) {
56 def = h->op();
57 last = h;
58 } else {
59 break;
60 }
61 }
62
63 auto root = def ? def : last;
64
65 // path compression
66 for (auto h = this; h != last;) {
67 auto next = h->op()->as_mut<Hole>();
68 h->set(root);
69 h = next;
70 }
71
72 return {last, def};
73}
74
75const Def* Hole::tuplefy(nat_t n) {
76 if (is_set()) return this;
77
78 auto& w = world();
79 auto holes = absl::FixedArray<const Def*>(n);
80 if (auto sigma = type()->isa_mut<Sigma>(); sigma && n >= 1 && sigma->has_var()) {
81 auto var = sigma->has_var();
82 auto rw = VarRewriter(var, this);
83 holes[0] = w.mut_hole(sigma->op(0));
84 for (size_t i = 1; i != n; ++i) {
85 rw.map(sigma->var(n, i - 1), holes[i - 1]);
86 holes[i] = w.mut_hole(rw.rewrite(sigma->op(i)));
87 }
88 } else {
89 for (size_t i = 0; i != n; ++i)
90 holes[i] = w.mut_hole(type()->proj(n, i));
91 }
92
93 auto tuple = w.tuple(holes);
94 set(tuple);
95 return tuple;
96}
97
98/*
99 * Checker
100 */
101
102#ifdef MIM_ENABLE_CHECKS
103template<Checker::Mode mode>
104bool Checker::fail() {
105 if (mode == Check && world().flags().break_on_alpha) fe::breakpoint();
106 return false;
107}
108
109const Def* Checker::fail() {
110 if (world().flags().break_on_alpha) fe::breakpoint();
111 return {};
112}
113#endif
114
116 if (defs.empty()) return nullptr;
117 auto first = defs.front();
118 for (size_t i = 1, e = defs.size(); i != e; ++i)
119 if (!alpha<Test>(first, defs[i])) return nullptr;
120 return first;
121}
122
123const Def* Checker::assignable_(const Def* type, const Def* val) {
124 auto val_ty = val->type()->zonk();
125 if (type == val_ty) return val;
126
127 auto& w = world();
128 if (auto sigma = type->isa<Sigma>()) {
129 if (!alpha_<Check>(type->arity(), val_ty->arity())) return fail();
130
131 size_t a = sigma->num_ops();
132 auto red = sigma->reduce(val);
133 auto new_ops = absl::FixedArray<const Def*>(red.size());
134 for (size_t i = 0; i != a; ++i) {
135 auto new_val = assignable_(red[i], val->proj(a, i));
136 if (new_val)
137 new_ops[i] = new_val;
138 else
139 return fail();
140 }
141 return w.tuple(new_ops);
142 } else if (auto uniq = val->type()->isa<Uniq>()) {
143 if (auto new_val = assignable(type, uniq->op())) return new_val;
144 return fail();
145 }
146
147 return alpha_<Check>(type, val_ty) ? val : fail();
148}
149
150template<Checker::Mode mode>
151bool Checker::alpha_(const Def* d1, const Def* d2) {
152 for (bool todo = true; todo;) {
153 // below we check type and arity which may in turn open up more opportunities for zonking
154 todo = false;
155 d1 = d1->zonk_mut();
156 d2 = d2->zonk_mut();
157
158 // It is only safe to check for pointer equality if there are no Vars involved.
159 // Otherwise, we have to look more thoroughly.
160 // Example: λx.x - λz.x
161 if (!d1->has_dep(Dep::Var) && !d2->has_dep(Dep::Var) && d1 == d2) return true;
162
163 auto h1 = d1->isa_mut<Hole>();
164 auto h2 = d2->isa_mut<Hole>();
165
166 if constexpr (mode == Check) {
167 if (h1) return h1->set(d2), true;
168 if (h2) return h2->set(d1), true;
169 } else if (h1 || h2) // mode == Test and h1 or h2 is an unresolved Hole
170 return fail<Test>();
171
172 if (!d1->is_set() || !d2->is_set()) return fail<mode>();
173
174 auto mut1 = d1->isa_mut();
175 auto mut2 = d2->isa_mut();
176
177 if (mut1 && mut2 && mut1 == mut2) return true;
178
179 // Globals are HACKs and require additionaly HACKs:
180 // Unless they are pointer equal (above) always consider them unequal.
181 if (d1->isa<Global>() || d2->isa<Global>()) return false;
182
183 if (auto [i, ins] = bind(mut1, d2); !ins) return i->second == d2;
184 if (auto [i, ins] = bind(mut2, d1); !ins) return i->second == d1;
185
186 if (d1->isa<Top>() || d2->isa<Top>()) return mode == Check;
187
188 if (auto t1 = d1->type()) {
189 if (auto t2 = d2->type()) {
190 if (!alpha_<mode>(t1, t2)) return fail<mode>();
191 }
192 }
193
194 if (!alpha_<mode>(d1->arity(), d2->arity())) return fail<mode>();
195
196 auto new_d1 = d1->zonk_mut();
197 auto new_d2 = d2->zonk_mut();
198 if (new_d1 != d1 || new_d2 != d2) {
199 todo = true;
200 d1 = new_d1;
201 d2 = new_d2;
202 }
203 }
204
205 auto seq1 = d1->isa<Seq>();
206 auto seq2 = d2->isa<Seq>();
207
208 if constexpr (mode == Mode::Check) {
209 if (auto umax = d1->isa<UMax>(); umax && !d2->isa<UMax>()) return check(umax, d2);
210 if (auto umax = d2->isa<UMax>(); umax && !d1->isa<UMax>()) return check(umax, d1);
211
212 if (seq1 && seq1->arity() == world().lit_nat_1() && !seq2) return check1(seq1, d2);
213 if (seq2 && seq2->arity() == world().lit_nat_1() && !seq1) return check1(seq2, d1);
214
215 if (seq1 && seq2) {
216 if (auto mut_seq = seq1->isa_mut<Seq>(); mut_seq && seq2->isa_imm()) return check(mut_seq, seq2);
217 if (auto mut_seq = seq2->isa_mut<Seq>(); mut_seq && seq1->isa_imm()) return check(mut_seq, seq1);
218 }
219 }
220
221 if (auto prod = d1->isa<Prod>()) return check<mode>(prod, d2);
222 if (auto prod = d2->isa<Prod>()) return check<mode>(prod, d1);
223 if (seq1 && seq2) return alpha_<mode>(seq1->body(), seq2->body());
224
225 if (d1->node() != d2->node() || d1->flags() != d2->flags()) return fail<mode>();
226
227 if (auto var1 = d1->isa<Var>()) {
228 auto var2 = d2->as<Var>();
229 if (auto i = binders_.find(var1->mut()); i != binders_.end()) return i->second == var2->mut();
230 if (auto i = binders_.find(var2->mut()); i != binders_.end()) return fail<mode>(); // var2 is bound
231 // both var1 and var2 are free: OK, when they are the same or in Check mode
232 return var1 == var2 || mode == Check;
233 }
234
235 for (size_t i = 0, e = d1->num_ops(); i != e; ++i)
236 if (!alpha_<mode>(d1->op(i), d2->op(i))) return fail<mode>();
237 return true;
238}
239
240template<Checker::Mode mode>
241bool Checker::check(const Prod* prod, const Def* def) {
242 size_t a = prod->num_ops();
243 for (size_t i = 0; i != a; ++i)
244 if (!alpha_<mode>(prod->op(i), def->proj(a, i))) return fail<mode>();
245 return true;
246}
247
248// alpha(«1; body», def) -> alpha(body, def);
249bool Checker::check1(const Seq* seq, const Def* def) {
250 auto body = seq->reduce(world().lit_idx_1_0()); // try to get rid of var inside of body
251 if (!alpha_<Check>(body, def)) return fail<Check>();
252 if (auto mut_seq = seq->isa_mut<Seq>()) mut_seq->set(world().lit_nat_1(), body->zonk());
253 return true;
254}
255
256// Try to get rid of mut_seq's var: it may occur in its body and vanish after reduction
257// as holes might have been filled in the meantime.
258bool Checker::check(Seq* mut_seq, const Seq* imm_seq) {
259 auto mut_body = mut_seq->reduce(world().top(world().type_idx(mut_seq->arity())));
260 if (!alpha_<Check>(mut_body, imm_seq->body())) return fail<Check>();
261
262 mut_seq->set(mut_seq->arity(), mut_body->zonk());
263 return true;
264}
265
266bool Checker::check(const UMax* umax, const Def* def) {
267 for (auto op : umax->ops())
268 if (!alpha<Check>(op, def)) return fail<Check>();
269 return true;
270}
271
272/*
273 * infer & check
274 */
275
276const Def* Arr::check(size_t, const Def* def) { return def; } // TODO
277
278const Def* Arr::check() {
279 auto t = body()->unfold_type();
281 error(type()->loc(), "declared sort '{}' of array does not match inferred one '{}'", type(), t);
282 return t;
283}
284
286 auto elems = absl::FixedArray<const Def*>(ops.size());
287 for (size_t i = 0, e = ops.size(); i != e; ++i)
288 elems[i] = ops[i]->unfold_type();
289 return world.sigma(elems);
290}
291
293 auto elems = absl::FixedArray<const Def*>(ops.size());
294 for (size_t i = 0, e = ops.size(); i != e; ++i)
295 elems[i] = ops[i]->unfold_type();
296 return w.umax<UMax::Kind>(elems);
297}
298
299const Def* Sigma::check(size_t, const Def* def) { return def; } // TODO
300
302 auto t = infer(world(), ops());
303 if (t != type()) {
304 // TODO HACK
306 return t;
307 else {
308 world().WLOG(
309 "incorrect type '{}' for '{}'. Correct one would be: '{}'. I'll keep this one nevertheless due to "
310 "bugs in clos-conv",
311 type(), this, t);
312 return type();
313 }
314 }
315 return t;
316}
317
318const Def* Pi::infer(const Def* dom, const Def* codom) {
319 auto& w = dom->world();
320 return w.umax<UMax::Kind>({dom->unfold_type(), codom->unfold_type()});
321}
322
323const Def* Pi::check(size_t, const Def* def) { return def; }
324
325const Def* Pi::check() {
326 auto t = infer(dom(), codom());
328 error(type()->loc(), "declared sort '{}' of function type does not match inferred one '{}'", type(), t);
329 return t;
330}
331
332const Def* Lam::check(size_t i, const Def* def) {
333 if (i == 0) {
334 if (auto filter = Checker::assignable(world().type_bool(), def)) return filter;
335 throw Error().error(filter()->loc(), "filter '{}' of lambda is of type '{}' but must be of type 'Bool'",
336 filter(), filter()->type());
337 } else if (i == 1) {
338 if (auto body = Checker::assignable(codom(), def)) return body;
339 throw Error()
340 .error(def->loc(), "body of function is not assignable to declared codomain")
341 .note(def->loc(), "body: '{}'", def)
342 .note(def->loc(), "type: '{}'", def->type())
343 .note(codom()->loc(), "codomain: '{}'", codom());
344 }
345 fe::unreachable();
346}
347
348const Def* Reform::check() {
349 auto t = infer(meta_type());
351 error(type()->loc(), "declared sort '{}' of rule type does not match inferred one '{}'", type(), t);
352 return t;
353}
354
355const Def* Reform::infer(const Def* meta_type) { return meta_type->unfold_type(); }
356
357const Def* Rule::check() {
358 auto t1 = lhs()->type();
359 auto t2 = rhs()->type();
361 error(type()->loc(), "type mismatch: '{}' for lhs, but '{}' for rhs", t1, t2);
362 if (!Checker::assignable(world().type_bool(), guard()))
363 error(guard()->loc(), "condition '{}' of rewrite is of type '{}' but must be of type 'Bool'", guard(),
364 guard()->type());
365
366 return type();
367}
368
369const Def* Rule::check(size_t, const Def* def) {
370 return def;
371 // TODO: do actual check + what are the parameters ?
372}
373
374#ifndef DOXYGEN
375template bool Checker::alpha_<Checker::Check>(const Def*, const Def*);
376template bool Checker::alpha_<Checker::Test>(const Def*, const Def*);
377#endif
378
379} // namespace mim
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition check.cpp:278
static const Def * is_uniform(Defs defs)
Yields defs.front(), if all defs are Check::alpha-equivalent (Mode::Test) and nullptr otherwise.
Definition check.cpp:115
static bool alpha(const Def *d1, const Def *d2)
Definition check.h:96
World & world()
Definition check.h:84
@ Check
In Mode::Check, type inference is happening and Holes will be resolved, if possible.
Definition check.h:89
static const Def * assignable(const Def *type, const Def *value)
Can value be assigned to sth of type?
Definition check.h:103
Base class for all Defs.
Definition def.h:251
bool is_set() const
Yields true if empty or the last op is set.
Definition def.cpp:295
const Def * zonk_mut() const
If *mutable, zonks all ops and tries to immutabilize it; otherwise just zonk.
Definition check.cpp:23
const Def * proj(nat_t a, nat_t i) const
Similar to World::extract while assuming an arity of a, but also works on Sigmas and Arrays.
Definition def.cpp:588
Defs deps() const noexcept
Definition def.cpp:470
const Def * zonk() const
If Holes have been filled, reconstruct the program without them.
Definition check.cpp:21
World & world() const noexcept
Definition def.cpp:439
virtual const Def * check()
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition def.h:583
constexpr auto ops() const noexcept
Definition def.h:305
T * isa_mut() const
If this is mutable, it will cast constness away and perform a dynamic_cast to T.
Definition def.h:485
const Def * op(size_t i) const noexcept
Definition def.h:308
const Def * var(nat_t a, nat_t i) noexcept
Definition def.h:429
const Def * unfold_type() const
Yields the type of this Def and builds a new Type (UInc n) if necessary.
Definition def.cpp:452
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
Definition def.cpp:332
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
Definition def.cpp:447
bool has_dep() const
Definition def.h:357
Loc loc() const
Definition def.h:506
bool needs_zonk() const
Yields true, if Def::local_muts() contain a Hole that is set.
Definition check.cpp:12
Error & error(Loc loc, const char *s, Args &&... args)
Definition dbg.h:72
Error & note(Loc loc, const char *s, Args &&... args)
Definition dbg.h:74
This node is a hole in the IR that is inferred by its context later on.
Definition check.h:14
std::pair< Hole *, const Def * > find()
Transitively walks up Holes until the last one while path-compressing everything.
Definition check.cpp:50
Hole * set(const Def *op)
Definition check.h:33
const Def * tuplefy(nat_t)
If unset, explode to Tuple.
Definition check.cpp:75
static const Def * isa_set(const Def *def)
Definition check.h:48
const Def * filter() const
Definition lam.h:123
const Pi * type() const
Definition lam.h:131
const Def * body() const
Definition lam.h:124
const Def * codom() const
Definition lam.h:133
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition check.cpp:325
static const Def * infer(const Def *dom, const Def *codom)
Definition check.cpp:318
const Def * dom() const
Definition lam.h:36
const Def * codom() const
Definition lam.h:37
Base class for Sigma and Tuple.
Definition tuple.h:10
Def(World *, Node, const Def *type, Defs ops, flags_t flags)
Constructor for an immutable Def.
Definition def.cpp:24
const Def * meta_type() const
Definition rule.h:15
static const Def * infer(const Def *meta_type)
Definition check.cpp:355
const Def * check() override
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition check.cpp:348
const Def * lhs() const
Definition rule.h:50
const Def * guard() const
Definition rule.h:52
const Def * rhs() const
Definition rule.h:51
const Def * check() override
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition check.cpp:357
const Reform * type() const
Definition rule.h:49
Base class for Arr and Pack.
Definition tuple.h:84
const Def * body() const
Definition tuple.h:91
Def(World *, Node, const Def *type, Defs ops, flags_t flags)
Constructor for an immutable Def.
Definition def.cpp:24
A dependent tuple type.
Definition tuple.h:20
friend class World
Definition tuple.h:63
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
Definition check.cpp:301
static const Def * infer(World &, Defs)
Definition check.cpp:292
friend class World
Definition tuple.h:80
static const Def * infer(World &, Defs)
Definition check.cpp:285
@ Kind
Definition def.h:745
Zonker & zonker()
Definition world.h:89
const Def * rewire_mut(Def *)
Definition rewrite.cpp:247
const Def * rewrite(const Def *) final
Definition rewrite.cpp:238
Definition ast.h:14
View< const Def * > Defs
Definition def.h:76
u64 nat_t
Definition types.h:43
Vector< const Def * > DefVec
Definition def.h:77
@ Var
Definition def.h:126
@ Hole
Definition def.h:127
void error(Loc loc, const char *f, Args &&... args)
Definition dbg.h:125
TExt< true > Top
Definition lattice.h:172
@ Global
Definition def.h:114
@ Var
Definition def.h:114
@ Hole
Definition def.h:114
@ Uniq
Definition def.h:114
@ UMax
Definition def.h:114