7#include <absl/container/btree_map.h>
8#include <absl/container/btree_set.h>
49#ifdef MIM_ENABLE_CHECKS
54 assert((!s1.pod.loc || !s2.pod.loc) &&
"Why is get_loc() still set?");
56#ifdef MIM_ENABLE_CHECKS
57 swap(s1.breakpoints, s2.breakpoints);
69 :
World(&other.driver(), other.state()) {
83 Sym
name()
const {
return state_.pod.name; }
101 , old_loc_(old_loc) {}
109 Loc
get_loc()
const {
return state_.pod.loc; }
120 Sym
sym(std::string_view);
121 Sym
sym(
const char*);
122 Sym
sym(
const std::string&);
134 bool old = state_.pod.frozen;
135 state_.pod.frozen = on;
153#ifdef MIM_ENABLE_CHECKS
168 auto annexes()
const {
return move_.flags2annex | std::views::values; }
173 if (
auto i = move_.flags2annex.find(
flags); i != move_.flags2annex.end())
return i->second;
192 auto externals()
const {
return move_.sym2external | std::views::values; }
206 if constexpr (level == 0)
208 else if constexpr (level == 1)
215 return unify<Proxy>(ops.size(),
type, ops, index, tag);
226 assert(
this == &res->world());
234 return unify<Axiom>(0, n, curry, trip,
type, p, t, s);
251 const Pi*
pi(
const Def* dom,
const Def* codom,
bool implicit =
false) {
return unify<Pi>(2,
Pi::infer(dom, codom), dom, codom, implicit); }
252 const Pi*
pi(
Defs dom,
const Def* codom,
bool implicit =
false) {
return pi(
sigma(dom), codom, implicit); }
253 const Pi*
pi(
const Def* dom,
Defs codom,
bool implicit =
false) {
return pi(dom,
sigma(codom), implicit); }
266 const Pi*
fn(
const Def* dom,
const Def* codom,
bool implicit =
false) {
return cn({ dom ,
cn(codom)}, implicit); }
267 const Pi*
fn(
Defs dom,
const Def* codom,
bool implicit =
false) {
return fn(
sigma(dom), codom, implicit); }
268 const Pi*
fn(
const Def* dom,
Defs codom,
bool implicit =
false) {
return fn( dom ,
sigma(codom), implicit); }
277 return std::get<const Def*>(
filter);
307 template<
bool Normalize = true>
const Def*
app(
const Def* callee,
const Def* arg);
308 template<
bool Normalize = true>
const Def*
app(
const Def* callee,
Defs args) {
333 return arr(
DefVec(shape.size(), [&](
size_t i) { return lit_nat(shape[i]); }), body);
354 return pack(
DefVec(shape.size(), [&](
auto i) { return lit_nat(shape[i]); }), body);
400 static_assert(std::is_integral<I>());
421 const Lit*
lit_bool(
bool val) {
return data_.lit_bool[size_t(val)]; }
497 template<
bool Normalize = true,
class E>
499 requires std::is_enum_v<E> && std::is_same_v<std::underlying_type_t<E>,
nat_t>
506 template<
class Id,
bool Normalize =
true,
class... Args>
const Def*
call(Id
id, Args&&... args) {
return call_<Normalize>(
annex(
id), std::forward<Args>(args)...); }
507 template<
class Id,
bool Normalize =
true,
class... Args>
const Def*
call( Args&&... args) {
return call_<Normalize>(
annex<Id>(), std::forward<Args>(args)...); }
514 [[nodiscard]]
auto&
vars() {
return move_.vars; }
515 [[nodiscard]]
auto&
muts() {
return move_.muts; }
516 [[nodiscard]]
const auto&
vars()
const {
return move_.vars; }
517 [[nodiscard]]
const auto&
muts()
const {
return move_.muts; }
524 void dump(std::ostream& os);
527 void write(
const char* file);
539 void dot(std::ostream& os,
bool annexes =
false,
bool types =
false)
const;
541 void dot(
const char* file =
nullptr,
bool annexes =
false,
bool types =
false)
const;
548 template<
bool Normalize =
true,
class T,
class... Args>
const Def* call_(
const Def* callee, T arg, Args&&... args) {
549 return call_<Normalize>(
implicit_app(callee, arg), std::forward<Args>(args)...);
551 template<
bool Normalize = true,
class T>
const Def* call_(
const Def* callee, T arg) {
558 template<
class T,
class... Args>
const T* unify(
size_t num_ops, Args&&... args) {
559 auto state = move_.arena.state();
560 auto def = allocate<T>(num_ops, std::forward<Args&&>(args)...);
561 if (
auto loc =
get_loc()) def->set(loc);
562 assert(!def->isa_mut());
563#ifdef MIM_ENABLE_CHECKS
564 if (
flags().trace_gids)
outln(
"{}: {} - {}", def->node_name(), def->gid(), def->flags());
565 if (
flags().reeval_breakpoints &&
breakpoints().contains(def->gid())) fe::breakpoint();
568 --state_.pod.curr_gid;
569 auto i = move_.defs.find(def);
570 deallocate<T>(
state, def);
571 if (i != move_.defs.end())
return static_cast<const T*
>(*i);
575 if (
auto [i, ins] = move_.defs.emplace(def); !ins) {
576 deallocate<T>(
state, def);
577 return static_cast<const T*
>(*i);
579#ifdef MIM_ENABLE_CHECKS
580 if (!
flags().reeval_breakpoints &&
breakpoints().contains(def->gid())) fe::breakpoint();
585 template<
class T>
void deallocate(fe::Arena::State
state,
const T* ptr) {
587 move_.arena.deallocate(
state);
590 template<
class T,
class... Args> T*
insert(
size_t num_ops, Args&&... args) {
591 auto def = allocate<T>(num_ops, std::forward<Args&&>(args)...);
592 if (
auto loc =
get_loc()) def->set(loc);
593#ifdef MIM_ENABLE_CHECKS
594 if (
flags().trace_gids)
outln(
"{}: {} - {}", def->node_name(), def->gid(), def->flags());
595 if (
breakpoints().contains(def->gid())) fe::breakpoint();
601#if (!defined(_MSC_VER) && defined(NDEBUG))
603 Lock() { assert((guard_ = !guard_) &&
"you are not allowed to recursively invoke allocate"); }
604 ~Lock() { guard_ = !guard_; }
613 template<
class T,
class... Args> T* allocate(
size_t num_ops, Args&&... args) {
614 static_assert(
sizeof(Def) ==
sizeof(T),
615 "you are not allowed to introduce any additional data in subclasses of Def");
617 auto num_bytes =
sizeof(Def) +
sizeof(uintptr_t) * num_ops;
618 auto ptr = move_.arena.allocate(num_bytes,
alignof(T));
619 auto res =
new (ptr) T(std::forward<Args&&>(args)...);
620 assert(res->num_ops() == num_ops);
629 size_t operator()(
const Def* def)
const {
return def->hash(); }
633 bool operator()(
const Def* d1,
const Def* d2)
const {
return d1->equal(d2); }
637 absl::btree_map<flags_t, const Def*> flags2annex;
638 absl::btree_map<Sym, Def*> sym2external;
640 absl::flat_hash_set<const Def*, SeaHash, SeaEq> defs;
642 Sets<const Var> vars;
645 friend void swap(Move& m1, Move& m2)
noexcept {
648 swap(m1.flags2annex, m2.flags2annex);
649 swap(m1.sym2external, m2.sym2external);
650 swap(m1.arena, m2.arena);
651 swap(m1.defs, m2.defs);
652 swap(m1.vars, m2.vars);
653 swap(m1.muts, m2.muts);
654 swap(m1.cache, m2.cache);
672 const Def* table_not;
686 swap(w1.state_, w2.state_);
687 swap(w1.data_, w2.data_ );
688 swap(w1.move_, w2.move_ );
691 swap(w1.data_.univ->world_, w2.data_.univ->world_);
692 assert(&w1.univ()->world() == &w1);
693 assert(&w2.univ()->world() == &w2);
A (possibly paramterized) Array.
DefVec reduce(const Def *arg) const
Rewrites Def::ops by substituting this mutable's Var with arg.
Some "global" variables needed all over the place.
This node is a hole in the IR that is inferred by its context later on.
A built-in constant of type Nat -> *.
static constexpr nat_t bitwidth2size(nat_t n)
std::variant< bool, const Def * > Filter
Facility to log what you are doing.
A (possibly paramterized) Tuple.
A dependent function type.
static const Def * infer(const Def *dom, const Def *codom)
Specific Bound depending on Up.
Data constructor for a Sigma.
This is a thin wrapper for absl::InlinedVector<T, N, A> which is a drop-in replacement for std::vecto...
The World represents the whole program and manages creation of MimIR nodes (Defs).
const Lit * lit_idx(nat_t size, u64 val)
Constructs a Lit of type Idx of size size.
const Lit * lit_idx(I val)
const Def * insert(const Def *d, const Def *i, const Def *val)
const Pi * fn(Defs dom, const Def *codom, bool implicit=false)
const Def * meet(Defs ops)
const auto & flags2annex() const
const Lam * con(Defs dom, Lam::Filter f, const Def *body)
const Def * uinc(const Def *op, level_t offset=1)
const Def * raw_app(const Axiom *axiom, u8 curry, u8 trip, const Def *type, const Def *callee, const Def *arg)
const Lit * lit(const Def *type, u64 val)
TBound< Up > * mut_bound(const Def *type, size_t size)
const Def * arr(u64 n, const Def *body)
friend void swap(World &w1, World &w2) noexcept
const Def * implicit_app(const Def *callee, nat_t arg)
const Def * extract(const Def *d, u64 a, u64 i)
Hole * mut_hole_infer_entity()
Either a value ?:?:Type ? or a type ?:Type ?:Type ?.
const Pi * cn(const Def *dom, bool implicit=false)
const Def * type_int(nat_t width)
Constructs a type Idx of size 2^width.
World & operator=(World)=delete
const Lit * lit_i16(u16 val)
const Lit * lit_i1(bool val)
const Def * arr(View< u64 > shape, const Def *body)
const Def * ac(const Def *type, Defs ops)
Lam * mut_fun(const Def *dom, Defs codom)
const Type * type(const Def *level)
void make_external(Def *)
const Driver & driver() const
const Lam * lam(const Def *dom, const Def *codom, Lam::Filter f, const Def *body)
Lam * mut_lam(const Def *dom, Defs codom)
const Def * filter(Lam::Filter filter)
const Def * sigma(Defs ops)
const auto & sym2external() const
const Def * type_idx(nat_t size)
const Def * pack(const Def *arity, const Def *body)
void set(std::string_view name)
const Def * app(const Def *callee, const Def *arg)
u32 curr_gid() const
Manage global identifier - a unique number for each Def.
World inherit()
Inherits the state into the new World.
const Def * arr(const Def *shape, const Def *body)
const Pi * pi(const Def *dom, const Def *codom, bool implicit=false)
const Def * pack(u64 n, const Def *body)
const Axiom * axiom(NormalizeFn n, u8 curry, u8 trip, const Def *type, plugin_t p, tag_t t, sub_t s)
const Def * insert(const Def *d, u64 a, u64 i, const Def *val)
const auto & muts() const
const Lam * lam(Defs dom, const Def *codom, Lam::Filter f, const Def *body)
const Lam * fun(Defs dom, const Def *codom, Lam::Filter f, const Def *body)
World & verify()
Verifies that all externals() and annexes() are Def::is_closed(), if MIM_ENABLE_CHECKS.
const Def * bot(const Def *type)
Arr * mut_arr(const Def *type)
const Lam * lam(const Def *dom, Defs codom, Lam::Filter f, const Def *body)
const Lit * lit_idx_mod(nat_t mod, u64 val)
Constructs a Lit of type Idx of size mod.
Pi * mut_pi(const Def *type, bool implicit=false)
const Def * annex(Id id)
Lookup annex by Axiom::id.
const Def * implicit_app(const Def *callee, E arg)
Join * mut_join(const Def *type, size_t size)
const Pi * cn(Defs dom, bool implicit=false)
void dump()
Dump to std::cout.
const Lam * fun(const Def *dom, Defs codom, Lam::Filter f, const Def *body)
void write()
Same above but file name defaults to World::name.
const Lam * lam(Defs dom, Defs codom, Lam::Filter f, const Def *body)
const Def * register_annex(plugin_t p, tag_t t, sub_t s, const Def *def)
Lam * mut_fun(Defs dom, const Def *codom)
Lam * mut_fun(const Def *dom, const Def *codom)
const Pi * fn(const Def *dom, Defs codom, bool implicit=false)
const Def * pick(const Def *type, const Def *value)
Hole * mut_hole(const Def *type)
const Lam * lam(const Pi *pi, Lam::Filter f, const Def *body)
const Def * tuple(Defs ops)
const Lam * fun(Defs dom, Defs codom, Lam::Filter f, const Def *body)
Lam * mut_lam(const Def *dom, const Def *codom)
const Def * gid2def(u32 gid)
Lookup Def by gid.
Flags & flags()
Retrieve compile Flags.
const Def * implicit_app(const Def *callee, const Def *arg)
Places Holes as demanded by Pi::is_implicit() and then apps arg.
const Def * implicit_app(const Def *callee, Defs args)
const Axiom * axiom(NormalizeFn n, u8 curry, u8 trip, const Def *type)
Builds a fresh Axiom with descending Axiom::sub.
void debug_dump()
Dump in Debug build if World::log::level is Log::Level::Debug.
const Def * extract(const Def *d, u64 i)
const Lam * fun(const Def *dom, const Def *codom, Lam::Filter f, const Def *body)
const Def * call(Args &&... args)
const auto & breakpoints()
const Def * var(const Def *type, Def *mut)
const Def * app(const Def *callee, Defs args)
const Def * pack(View< u64 > shape, const Def *body)
Lam * mut_fun(Defs dom, Defs codom)
const Lit * lit_i2(u8 val)
const Def * extract(const Def *d, const Def *i)
Pack * mut_pack(const Def *type)
const Axiom * axiom(const Def *type, plugin_t p, tag_t t, sub_t s)
Sym sym(std::string_view)
Global * global(const Def *type, bool is_mutable=true)
Lam * mut_lam(Defs dom, const Def *codom)
const Lit * lit_nat_max()
const Def * raw_app(const Def *type, const Def *callee, Defs args)
const Pi * pi(Defs dom, const Def *codom, bool implicit=false)
Def * external(Sym name)
Lookup by name.
const Def * bound(Defs ops)
const Def * join(Defs ops)
const Def * ext(const Def *type)
Sym append_suffix(Sym name, std::string suffix)
Appends a suffix or an increasing number if the suffix already exists.
void make_internal(Def *)
Join * mut_join(size_t size)
const Proxy * proxy(const Def *type, Defs ops, u32 index, u32 tag)
const Lit * lit_i32(u32 val)
const Lit * lit_i8(u8 val)
Lam * mut_lam(Defs dom, Defs codom)
Sigma * mut_sigma(size_t size)
A *mut*able Sigma of type level.
const Lit * lit_univ(u64 level)
const Pi * pi(Defs dom, Defs codom, bool implicit=false)
const Tuple * tuple()
the unit value of type []
const Type * type_infer_univ()
const Def * call(Id id, Args &&... args)
Complete curried call of annexes obeying implicits.
const Def * vel(const Def *type, const Def *value)
const Def * uniq(const Def *inhabitant)
Vector< Def * > copy_externals() const
const Lam * con(const Def *dom, Lam::Filter f, const Def *body)
Meet * mut_meet(const Def *type, size_t size)
const Def * arr_unsafe(const Def *body)
const Lit * lit_i64(u64 val)
const Sigma * sigma()
The unit type within Type 0.
const Lit * lit_nat(nat_t a)
const State & state() const
const auto & vars() const
TBound< Up > * mut_bound(size_t size)
A *mut*able Bound of Type level.
const Def * register_annex(flags_t f, const Def *)
const Def * top(const Def *type)
const Def * type_idx(const Def *size)
Lam * mut_con(const Def *dom)
const Lit * lit_int(nat_t width, u64 val)
Constructs a Lit of type Idx of size 2^width.
const Lit * lit_bool(bool val)
void breakpoint(u32 gid)
Trigger breakpoint in your debugger when creating Def with Def::gid gid.
Meet * mut_meet(size_t size)
const Def * select(const Def *cond, const Def *t, const Def *f)
Builds (f, t)#cond.
Sigma * mut_sigma(const Def *type, size_t size)
const Pi * fn(const Def *dom, const Def *codom, bool implicit=false)
World(World &&other) noexcept
const Pi * pi(const Def *dom, Defs codom, bool implicit=false)
bool freeze(bool on=true) const
Yields old frozen state.
const Lit * lit_i4(u8 val)
const Def * test(const Def *value, const Def *probe, const Def *match, const Def *clash)
void dot(std::ostream &os, bool annexes=false, bool types=false) const
Dumps DOT to os.
const Def * insert(const Def *d, u64 i, const Def *val)
const Pi * fn(Defs dom, Defs codom, bool implicit=false)
const Axiom * axiom(const Def *type)
See above.
Lam * mut_lam(const Pi *pi)
const Def * annex()
Get Axiom from a plugin.
Vector< const Def * > DefVec
absl::flat_hash_map< DefDef, To, DefDefHash, DefDefEq > DefDefMap
auto assert_emplace(C &container, Args &&... args)
Invokes emplace on container, asserts that insertion actually happened, and returns the iterator.
auto lookup(const C &container, const K &key)
Yields pointer to element (or the element itself if it is already a pointer), if found and nullptr ot...
void error(Loc loc, const char *f, Args &&... args)
std::ostream & outln(const char *fmt, Args &&... args)
auto match(const Def *def)
const Def *(*)(const Def *, const Def *, const Def *) NormalizeFn
Compiler switches that must be saved and looked up in later phases of compilation.
static constexpr plugin_t Global_Plugin
static Sym demangle(Driver &, plugin_t plugin)
Reverts an Axiom::mangled string to a Sym.
static constexpr flags_t Base
Freezer(const World &world)
ScopedLoc(World &world, Loc old_loc)
friend void swap(State &s1, State &s2) noexcept
struct mim::World::State::POD pod
absl::flat_hash_set< uint32_t > breakpoints