3#include <absl/container/fixed_array.h>
24 if (!
is_set())
return this;
27 if (
auto hole = mut->isa<
Hole>()) {
28 auto [last,
op] = hole->find();
29 return op ?
op->zonk() : last;
32 for (
auto def :
deps())
35 if (
auto imm = mut->immutabilize())
return imm;
43 return DefVec(defs.size(), [defs](
size_t i) { return defs[i]->zonk(); });
55 if (
auto h = def->isa_mut<Hole>()) {
63 auto root = def ? def : last;
66 for (
auto h =
this; h != last;) {
67 auto next = h->op()->as_mut<Hole>();
79 auto holes = absl::FixedArray<const Def*>(n);
81 auto var = sigma->has_var();
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)));
89 for (
size_t i = 0; i != n; ++i)
90 holes[i] = w.mut_hole(
type()->
proj(n, i));
93 auto tuple = w.tuple(holes);
102#ifdef MIM_ENABLE_CHECKS
103template<Checker::Mode mode>
104bool Checker::fail() {
105 if (mode ==
Check &&
world().flags().break_on_alpha) fe::breakpoint();
109const Def* Checker::fail() {
110 if (
world().flags().break_on_alpha) fe::breakpoint();
116 if (defs.empty())
return nullptr;
117 auto first = defs.front();
118 for (
size_t i = 1, e = defs.size(); i != e; ++i)
123const Def* Checker::assignable_(
const Def* type,
const Def* val) {
125 if (type == val_ty)
return val;
128 if (
auto sigma = type->isa<
Sigma>()) {
129 if (!alpha_<Check>(type->arity(), val_ty->arity()))
return fail();
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));
137 new_ops[i] = new_val;
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;
147 return alpha_<Check>(type, val_ty) ? val : fail();
150template<Checker::Mode mode>
151bool Checker::alpha_(
const Def* d1,
const Def* d2) {
152 for (
bool todo =
true; todo;) {
161 if (!d1->has_dep(
Dep::Var) && !d2->has_dep(
Dep::Var) && d1 == d2)
return true;
163 auto h1 = d1->isa_mut<
Hole>();
164 auto h2 = d2->isa_mut<
Hole>();
167 if (h1)
return h1->set(d2),
true;
168 if (h2)
return h2->set(d1),
true;
172 if (!d1->is_set() || !d2->is_set())
return fail<mode>();
174 auto mut1 = d1->isa_mut();
175 auto mut2 = d2->isa_mut();
177 if (mut1 && mut2 && mut1 == mut2)
return true;
181 if (d1->isa<
Global>() || d2->isa<
Global>())
return false;
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;
188 if (
auto t1 = d1->type()) {
189 if (
auto t2 = d2->type()) {
190 if (!alpha_<mode>(t1, t2))
return fail<mode>();
194 if (!alpha_<mode>(d1->arity(), d2->arity()))
return fail<mode>();
196 auto new_d1 = d1->zonk_mut();
197 auto new_d2 = d2->zonk_mut();
198 if (new_d1 != d1 || new_d2 != d2) {
205 auto seq1 = d1->isa<Seq>();
206 auto seq2 = d2->isa<Seq>();
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);
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);
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);
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());
225 if (d1->node() != d2->node() || d1->flags() != d2->flags())
return fail<mode>();
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>();
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>();
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>();
249bool Checker::check1(
const Seq* seq,
const Def* def) {
250 auto body = seq->reduce(
world().lit_idx_1_0());
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());
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>();
262 mut_seq->set(mut_seq->arity(), mut_body->zonk());
266bool Checker::check(
const UMax* umax,
const Def* def) {
267 for (
auto op :
umax->ops())
281 error(
type()->
loc(),
"declared sort '{}' of array does not match inferred one '{}'",
type(), t);
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);
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();
309 "incorrect type '{}' for '{}'. Correct one would be: '{}'. I'll keep this one nevertheless due to "
319 auto& w =
dom->world();
323const Def*
Pi::check(
size_t,
const Def* def) {
return def; }
328 error(
type()->
loc(),
"declared sort '{}' of function type does not match inferred one '{}'",
type(), t);
335 throw Error().
error(
filter()->
loc(),
"filter '{}' of lambda is of type '{}' but must be of type 'Bool'",
340 .
error(def->
loc(),
"body of function is not assignable to declared codomain")
341 .
note(def->
loc(),
"body: '{}'", def)
351 error(
type()->
loc(),
"declared sort '{}' of rule type does not match inferred one '{}'",
type(), t);
361 error(
type()->
loc(),
"type mismatch: '{}' for lhs, but '{}' for rhs", t1, t2);
363 error(
guard()->
loc(),
"condition '{}' of rewrite is of type '{}' but must be of type 'Bool'",
guard(),
375template bool Checker::alpha_<Checker::Check>(
const Def*,
const Def*);
376template bool Checker::alpha_<Checker::Test>(
const Def*,
const Def*);
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
static const Def * is_uniform(Defs defs)
Yields defs.front(), if all defs are Check::alpha-equivalent (Mode::Test) and nullptr otherwise.
static bool alpha(const Def *d1, const Def *d2)
@ Check
In Mode::Check, type inference is happening and Holes will be resolved, if possible.
static const Def * assignable(const Def *type, const Def *value)
Can value be assigned to sth of type?
bool is_set() const
Yields true if empty or the last op is set.
const Def * zonk_mut() const
If *mutable, zonks all ops and tries to immutabilize it; otherwise just zonk.
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.
Defs deps() const noexcept
const Def * zonk() const
If Holes have been filled, reconstruct the program without them.
World & world() const noexcept
virtual const Def * check()
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
constexpr auto ops() const noexcept
T * isa_mut() const
If this is mutable, it will cast constness away and perform a dynamic_cast to T.
const Def * op(size_t i) const noexcept
const Def * var(nat_t a, nat_t i) noexcept
const Def * unfold_type() const
Yields the type of this Def and builds a new Type (UInc n) if necessary.
Muts local_muts() const
Mutables reachable by following immutable deps(); mut->local_muts() is by definition the set { mut }...
const Def * type() const noexcept
Yields the "raw" type of this Def (maybe nullptr).
bool needs_zonk() const
Yields true, if Def::local_muts() contain a Hole that is set.
Error & error(Loc loc, const char *s, Args &&... args)
Error & note(Loc loc, const char *s, Args &&... args)
This node is a hole in the IR that is inferred by its context later on.
std::pair< Hole *, const Def * > find()
Transitively walks up Holes until the last one while path-compressing everything.
Hole * set(const Def *op)
const Def * tuplefy(nat_t)
If unset, explode to Tuple.
static const Def * isa_set(const Def *def)
const Def * filter() const
const Def * codom() const
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
static const Def * infer(const Def *dom, const Def *codom)
const Def * codom() const
Base class for Sigma and Tuple.
Def(World *, Node, const Def *type, Defs ops, flags_t flags)
Constructor for an immutable Def.
const Def * guard() const
const Def * check() override
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
const Reform * type() const
Base class for Arr and Pack.
Def(World *, Node, const Def *type, Defs ops, flags_t flags)
Constructor for an immutable Def.
const Def * check() final
After all Def::ops have ben Def::set, this method will be invoked to check the type of this mutable.
static const Def * infer(World &, Defs)
static const Def * infer(World &, Defs)
const Def * rewire_mut(Def *)
const Def * rewrite(const Def *) final
Vector< const Def * > DefVec
void error(Loc loc, const char *f, Args &&... args)