void ConstraintManager::addConstraint(expr constraint) {
	cid idx = id2Constraint.size();
	expr pi = Utils::get_ctx().bool_const(string("pmuc"+to_string(idx)).c_str());
	id2Constraint.push_back(constraint);
	if (isHLC)
		constraint = Utils::convert_to_cnf_simplified(constraint);

	vector<clid> clauses;
	if (constraint.decl().decl_kind() == Z3_OP_AND) {
		for (unsigned i = 0; i < constraint.num_args(); ++i) {
			clauses.push_back(clid2Clause.size());
			clid2Clause.push_back(constraint.arg(i));
			clid2Cid.push_back(idx);
		}
	}
	else {
		clauses.push_back(clid2Clause.size());
		clid2Clause.push_back(constraint);
		clid2Cid.push_back(idx);
	}
	cid2clauses.push_back(clauses);
	id2CnfConstraint.push_back(constraint);
	id2AssumptionP.push_back(pi);
	p2Id[pi] = idx;


}

expr_let::expr_let(name const & n, expr const & t, expr const & v, expr const & b):
    expr_cell(expr_kind::Let, ::lean::hash(v.hash(), b.hash()), v.has_metavar() || b.has_metavar() || (t && t.has_metavar())),
    m_name(n),
    m_type(t),
    m_value(v),
    m_body(b) {
}

    expr visit(expr const & e) {
        switch (e.kind()) {
        case expr_kind::Sort:  case expr_kind::Constant:
        case expr_kind::Var:   case expr_kind::Meta:
        case expr_kind::Local:
            return e;
        default:
            break;
        }

        check_system("unfold macros");
        auto it = m_cache.find(e);
        if (it != m_cache.end())
            return it->second;

        switch (e.kind()) {
        case expr_kind::Sort:  case expr_kind::Constant:
        case expr_kind::Var:   case expr_kind::Meta:
        case expr_kind::Local:
            lean_unreachable();
        case expr_kind::Macro:
            return save_result(e, visit_macro(e));
        case expr_kind::App:
            return save_result(e, visit_app(e));
        case expr_kind::Lambda: case expr_kind::Pi:
            return save_result(e, visit_binding(e));
        }
        lean_unreachable();
    }

expr update_mlocal(expr const & e, expr const & new_type) {
    if (is_eqp(mlocal_type(e), new_type))
        return e;
    else if (is_metavar(e))
        return mk_metavar(mlocal_name(e), new_type, e.get_tag());
    else
        return mk_local(mlocal_name(e), local_pp_name(e), new_type, local_info(e), e.get_tag());
}

 bool apply(expr const & a, expr const & b) {
     if (is_eqp(a, b))          return true;
     if (a.hash() != b.hash())  return false;
     if (a.kind() != b.kind())  return false;
     if (is_var(a))             return var_idx(a) == var_idx(b);
     if (m_cache.check(a, b))
         return true;
     switch (a.kind()) {
     case expr_kind::Var:
         lean_unreachable(); // LCOV_EXCL_LINE
     case expr_kind::Constant:
         return
             const_name(a) == const_name(b) &&
             compare(const_levels(a), const_levels(b), [](level const & l1, level const & l2) { return l1 == l2; });
     case expr_kind::Meta:
         return
             mlocal_name(a) == mlocal_name(b) &&
             apply(mlocal_type(a), mlocal_type(b));
     case expr_kind::Local:
         return
             mlocal_name(a) == mlocal_name(b) &&
             apply(mlocal_type(a), mlocal_type(b)) &&
             (!CompareBinderInfo || local_pp_name(a) == local_pp_name(b)) &&
             (!CompareBinderInfo || local_info(a) == local_info(b));
     case expr_kind::App:
         check_system();
         return
             apply(app_fn(a), app_fn(b)) &&
             apply(app_arg(a), app_arg(b));
     case expr_kind::Lambda: case expr_kind::Pi:
         check_system();
         return
             apply(binding_domain(a), binding_domain(b)) &&
             apply(binding_body(a), binding_body(b)) &&
             (!CompareBinderInfo || binding_name(a) == binding_name(b)) &&
             (!CompareBinderInfo || binding_info(a) == binding_info(b));
     case expr_kind::Let:
         check_system();
         return
             apply(let_type(a), let_type(b)) &&
             apply(let_value(a), let_value(b)) &&
             apply(let_body(a), let_body(b)) &&
             (!CompareBinderInfo || let_name(a) == let_name(b));
     case expr_kind::Sort:
         return sort_level(a) == sort_level(b);
     case expr_kind::Macro:
         check_system();
         if (macro_def(a) != macro_def(b) || macro_num_args(a) != macro_num_args(b))
             return false;
         for (unsigned i = 0; i < macro_num_args(a); i++) {
             if (!apply(macro_arg(a, i), macro_arg(b, i)))
                 return false;
         }
         return true;
     }
     lean_unreachable(); // LCOV_EXCL_LINE
 }

/*!\brief Expand an expression of the form scale * addition
 *
 * Provided \c scale is not a sum, expand the expression
 * <tt>scale * (+ c a1 ...)</tt> into <tt>scale * c + scale * a1 + ...</tt>.
 */
ptr<const sum>
expand_prod_sum( const expr &scale, const sum  &addition )
{
  ASSERT( addition.is_expanded() && ! scale.is_a< sum >() );

  if( scale.is_numerical() )
  { // easy case -> sum::sca does the work
    const number &ns = scale.as_a< numerical >()->get();

    ptr< const sum > ret
      = ns.unit()
      ? &addition
      : sum::sca( ns, addition );

    ret->basic::expand();
    return ret;
  }

  // hard case : distribute term by term

  number coef = 0;

  ptr< const prod > scale_prod = scale.get()->as_prod();

  // addition.size() for nsp * addition
  // + 1 for scale_prod * addition.coef()
  container::ptr_unsafe_vector< const prod > seq ( addition.size() + 1 );

  { // coefficient handling
    const prod* ph = scale_prod.get();

    // cannot be numerical since [scale_prod] isn't
    seq.push_back( prod::handle::sca( ph, addition.coef() ) );
  }
  for(const prod* p : addition)
  {
    ASSERT( p );

    const expr ex = prod::mul( *p, *scale_prod );

    // seams reasonable here
    ASSERT( ! ex.is_a< sum >() );

    if( ex.is_numerical() )
      coef += ex.as_a< numerical >()->get();

    else
      seq.push_back( ex.get()->as_prod() );
  }

  expand_detail::sort( seq.begin(), seq.end() );

  ptr< const sum > ret = sum::from_sorted_prod_range( coef, seq.begin(), seq.end() );
  ret->basic::expand(); // mark expanded
  return ret;
}

bool basic::match(const expr &e, match_state &mm) const
{
  if( e.is_a< wildcard_ >() )
    return match_wild( *this, *e.as_a< wildcard_ >(), mm );

  if( RTTI_ID( this ) != RTTI_ID( e.get() ) )
    return false;

  return match_same_type( *e.get(), mm );
}

bool is_arrow(expr const & t) {
    optional<bool> r = t.raw()->is_arrow();
    if (r) {
        return *r;
    } else {
        bool res = is_pi(t) && !has_free_var(binding_body(t), 0);
        t.raw()->set_is_arrow(res);
        return res;
    }
}

unsigned get_weight(expr const & e) {
    switch (e.kind()) {
    case expr_kind::Var:  case expr_kind::Constant: case expr_kind::Sort:
    case expr_kind::Meta: case expr_kind::Local:
        return 1;
    case expr_kind::Lambda: case expr_kind::Pi:  case expr_kind::Macro:
    case expr_kind::App:    case expr_kind::Let:
        return static_cast<expr_composite*>(e.raw())->m_weight;
    }
    lean_unreachable(); // LCOV_EXCL_LINE
}

unsigned abstract_expr_manager::hash(expr const & e) {
    unsigned h;
    switch (e.kind()) {
    case expr_kind::Constant:
    case expr_kind::Local:
    case expr_kind::Meta:
    case expr_kind::Sort:
    case expr_kind::Var:
    case expr_kind::Macro:
        return e.hash();
    case expr_kind::Lambda:
    case expr_kind::Pi:
        h = hash(binding_domain(e));
        // Remark binding_domain(e) may contain de-bruijn variables.
        // We can instantiate them eagerly as we do here, or lazily.
        // The lazy approach is potentially more efficient, but we would have
        // to use something more sophisticated than an instantiate_rev at expr_kind::App
        m_locals.push_back(instantiate_rev(m_tctx.mk_tmp_local(binding_domain(e)), m_locals.size(), m_locals.data()));
        h = ::lean::hash(h, hash(binding_body(e)));
        m_locals.pop_back();
        return h;
    case expr_kind::Let:
        // Let-expressions must be unfolded before invoking this method
        lean_unreachable();
    case expr_kind::App:
        buffer<expr> args;
        expr const & f     = get_app_args(e, args);
        unsigned prefix_sz = m_congr_lemma_manager.get_specialization_prefix_size(instantiate_rev(f, m_locals.size(), m_locals.data()), args.size());
        expr new_f = e;
        unsigned rest_sz   = args.size() - prefix_sz;
        for (unsigned i = 0; i < rest_sz; i++)
            new_f = app_fn(new_f);
        new_f = instantiate_rev(new_f, m_locals.size(), m_locals.data());
        optional<congr_lemma> congr = m_congr_lemma_manager.mk_congr(new_f, rest_sz);
        h = hash(new_f);
        if (!congr) {
            for (unsigned i = prefix_sz; i < args.size(); i++) {
                h = ::lean::hash(h, hash(args[i]));
            }
        } else {
            lean_assert(length(congr->get_arg_kinds()) == rest_sz);
            unsigned i = prefix_sz;
            for_each(congr->get_arg_kinds(), [&](congr_arg_kind const & c_kind) {
                    if (c_kind != congr_arg_kind::Cast) {
                        h = ::lean::hash(h, hash(args[i]));
                    }
                    i++;
                });
        }
        return h;
    }
    lean_unreachable();
}

expr_app::expr_app(expr const & fn, expr const & arg, tag g):
    expr_composite(expr_kind::App, ::lean::hash(fn.hash(), arg.hash()),
                   fn.has_expr_metavar() || arg.has_expr_metavar(),
                   fn.has_univ_metavar() || arg.has_univ_metavar(),
                   fn.has_local()        || arg.has_local(),
                   fn.has_param_univ()   || arg.has_param_univ(),
                   inc_weight(add_weight(get_weight(fn), get_weight(arg))),
                   std::max(get_free_var_range(fn), get_free_var_range(arg)),
                   g),
    m_fn(fn), m_arg(arg) {
    m_hash = ::lean::hash(m_hash, m_weight);
}

bool is_lt_no_level_params(expr const & a, expr const & b) {
    if (is_eqp(a, b))                    return false;
    unsigned wa = get_weight(a);
    unsigned wb = get_weight(b);
    if (wa < wb)                         return true;
    if (wa > wb)                         return false;
    if (a.kind() != b.kind())            return a.kind() < b.kind();
    switch (a.kind()) {
    case expr_kind::Var:
        return var_idx(a) < var_idx(b);
    case expr_kind::Constant:
        if (const_name(a) != const_name(b))
            return const_name(a) < const_name(b);
        else
            return is_lt_no_level_params(const_levels(a), const_levels(b));
    case expr_kind::App:
        if (is_lt_no_level_params(app_fn(a), app_fn(b)))
            return true;
        else if (is_lt_no_level_params(app_fn(b), app_fn(a)))
            return false;
        else
            return is_lt_no_level_params(app_arg(a), app_arg(b));
    case expr_kind::Lambda: case expr_kind::Pi:
        if (is_lt_no_level_params(binding_domain(a), binding_domain(b)))
            return true;
        else if (is_lt_no_level_params(binding_domain(b), binding_domain(a)))
            return false;
        else
            return is_lt_no_level_params(binding_body(a), binding_body(b));
    case expr_kind::Sort:
        return is_lt_no_level_params(sort_level(a), sort_level(b));
    case expr_kind::Local: case expr_kind::Meta:
        if (mlocal_name(a) != mlocal_name(b))
            return mlocal_name(a) < mlocal_name(b);
        else
            return is_lt_no_level_params(mlocal_type(a), mlocal_type(b));
    case expr_kind::Macro:
        if (macro_def(a) != macro_def(b))
            return macro_def(a) < macro_def(b);
        if (macro_num_args(a) != macro_num_args(b))
            return macro_num_args(a) < macro_num_args(b);
        for (unsigned i = 0; i < macro_num_args(a); i++) {
            if (is_lt_no_level_params(macro_arg(a, i), macro_arg(b, i)))
                return true;
            else if (is_lt_no_level_params(macro_arg(b, i), macro_arg(a, i)))
                return false;
        }
        return false;
    }
    lean_unreachable();
}

 expr apply(expr const & a) {
     auto r = m_cache.find(a);
     if (r != m_cache.end()) {
         lean_assert((*r).raw()->max_shared());
         return *r;
     }
     if (a.raw()->max_shared()) {
         m_cache.insert(a);
         return a;
     }
     switch (a.kind()) {
     case expr_kind::Var: case expr_kind::Constant: case expr_kind::Type: case expr_kind::Value:
         cache(a);
         return a;
     case expr_kind::App: {
         expr r = update_app(a, [=](expr const & c){ return apply(c); });
         cache(r);
         return r;
     }
     case expr_kind::Eq : {
         expr r = update_eq(a, [=](expr const & l, expr const & r){ return std::make_pair(apply(l), apply(r)); });
         cache(r);
         return r;
     }
     case expr_kind::Lambda:
     case expr_kind::Pi: {
         expr r = update_abst(a, [=](expr const & t, expr const & b) { return std::make_pair(apply(t), apply(b)); });
         cache(r);
         return r;
     }
     case expr_kind::Let: {
         expr r = update_let(a, [=](expr const & t, expr const & v, expr const & b) {
                 expr new_t = t ? apply(t) : expr();
                 return std::make_tuple(new_t, apply(v), apply(b));
             });
         cache(r);
         return r;
     }
     case expr_kind::MetaVar: {
         expr r = update_metavar(a, [=](meta_entry const & e) -> meta_entry {
                 if (e.is_inst())
                     return mk_inst(e.s(), apply(e.v()));
                 else
                     return e;
             });
         cache(r);
         return r;
     }}
     lean_unreachable();
 }

expr copy(expr const & a) {
    switch (a.kind()) {
    case expr_kind::Var:      return mk_var(var_idx(a));
    case expr_kind::Constant: return mk_constant(const_name(a));
    case expr_kind::Type:     return mk_type(ty_level(a));
    case expr_kind::Value:    return mk_value(static_cast<expr_value*>(a.raw())->m_val);
    case expr_kind::App:      return mk_app(num_args(a), begin_args(a));
    case expr_kind::Eq:       return mk_eq(eq_lhs(a), eq_rhs(a));
    case expr_kind::Lambda:   return mk_lambda(abst_name(a), abst_domain(a), abst_body(a));
    case expr_kind::Pi:       return mk_pi(abst_name(a), abst_domain(a), abst_body(a));
    case expr_kind::Let:      return mk_let(let_name(a), let_type(a), let_value(a), let_body(a));
    case expr_kind::MetaVar:  return mk_metavar(metavar_idx(a), metavar_ctx(a));
    }
    lean_unreachable();
}

optional<expr> mk_class_instance(environment const & env, io_state const & ios, local_context const & ctx,
                                 name const & prefix, expr const & type, bool relax_opaque, bool use_local_instances,
                                 unifier_config const & cfg) {
    auto C = std::make_shared<class_instance_context>(env, ios, prefix, relax_opaque, use_local_instances);
    if (!is_ext_class(C->tc(), type))
        return none_expr();
    expr meta       = ctx.mk_meta(C->m_ngen, some_expr(type), type.get_tag());
    unsigned depth  = 0;
    constraint c    = mk_class_instance_cnstr(C, ctx, meta, depth);
    unifier_config new_cfg(cfg);
    new_cfg.m_discard        = true;
    new_cfg.m_use_exceptions = true;
    new_cfg.m_pattern        = true;
    new_cfg.m_kind           = C->m_conservative ? unifier_kind::VeryConservative : unifier_kind::Liberal;
    try {
        auto seq = unify(env, 1, &c, C->m_ngen.mk_child(), substitution(), new_cfg);
        while (true) {
            auto p = seq.pull();
            lean_assert(p);
            substitution s = p->first.first;
            expr r = s.instantiate_all(meta);
            if (!has_expr_metavar_relaxed(r))
                return some_expr(r);
            seq = p->second;
        }
    } catch (exception &) {
        return none_expr();
    }
}

// scoped_expr_actions must occur after a Binder/Binders.
static void validate_transitions(bool nud, unsigned num, transition const * ts, expr const & a) {
    unsigned nargs = 0;
    if (!nud)
        nargs++; // led tables have an implicit left argument
    bool found_binder = false;
    for (unsigned i = 0; i < num; i++) {
        action const & a = ts[i].get_action();
        switch (a.kind()) {
        case action_kind::Binder: case action_kind::Binders:
            found_binder = true;
            break;
        case action_kind::Expr: case action_kind::Exprs: case action_kind::Ext: case action_kind::LuaExt:
            nargs++;
            break;
        case action_kind::ScopedExpr:
            if (!found_binder)
                throw exception("invalid notation declaration, a scoped expression must occur after a binder element");
            nargs++;
            break;
        case action_kind::Skip:
            break;
        }
    }
    if (get_free_var_range(a) > nargs)
        throw exception("invalid notation declaration, expression template has more free variables than arguments");
}

value expr_copy(const expr &e)
{
  value res = expr_allocate();
  Field( res, 1 ) = RTTI_ID( e.get() );
  expr_construct( res ) expr( e );
  return res;
}

 expr apply(expr const & a) {
     check_system("max_sharing");
     auto r = m_expr_cache.find(a);
     if (r != m_expr_cache.end())
         return *r;
     expr res;
     switch (a.kind()) {
     case expr_kind::Var:
         res = a;
         break;
     case expr_kind::Constant:
         res = update_constant(a, map(const_levels(a), [&](level const & l) { return apply(l); }));
         break;
     case expr_kind::Sort:
         res = update_sort(a, apply(sort_level(a)));
         break;
     case expr_kind::App:
         res = update_app(a, apply(app_fn(a)), apply(app_arg(a)));
         break;
     case expr_kind::Lambda: case expr_kind::Pi:
         res = update_binding(a, apply(binding_domain(a)), apply(binding_body(a)));
         break;
     case expr_kind::Meta:  case expr_kind::Local:
         res = update_mlocal(a, apply(mlocal_type(a)));
         break;
     case expr_kind::Macro: {
         buffer<expr> new_args;
         for (unsigned i = 0; i < macro_num_args(a); i++)
             new_args.push_back(macro_arg(a, i));
         res = update_macro(a, new_args.size(), new_args.data());
         break;
     }}
     m_expr_cache.insert(res);
     return res;
 }

void forward_branch_extension::index_expr(expr const & e) {
    // TODO(dhs): index the target when it gets updated

    if (auto head_idx = to_head_index(e)) {
        m_index.insert(head_index(e), e);
    }
    switch (e.kind()) {
    case expr_kind::Var:
        lean_unreachable();  // LCOV_EXCL_LINE
    case expr_kind::Local:
    case expr_kind::Meta:
    case expr_kind::Sort:
    case expr_kind::Constant:
    case expr_kind::Macro: // TODO(dhs): do I unfold macros?
        break;
    case expr_kind::Lambda:
    case expr_kind::Pi:
        // TODO(dhs): confirm that I only index quantified-free hypotheses
        break;
    case expr_kind::Let:
        // Let-expressions must be unfolded before invoking this method
        lean_unreachable();
    case expr_kind::App:
        index_expr(app_fn(e));
        index_expr(app_arg(e));
        break;
    }
}

 /** \brief Return true iff all recursive applications in \c e are structurally smaller than \c m_pattern. */
 bool check_rhs(expr const & e) {
     switch (e.kind()) {
     case expr_kind::Var:   case expr_kind::Meta:
     case expr_kind::Local: case expr_kind::Constant:
     case expr_kind::Sort:
         return true;
     case expr_kind::Macro:
         for (unsigned i = 0; i < macro_num_args(e); i++)
             if (!check_rhs(macro_arg(e, i)))
                 return false;
         return true;
     case expr_kind::App: {
         buffer<expr> args;
         expr const & fn = get_app_args(e, args);
         if (!check_rhs(fn))
             return false;
         for (unsigned i = 0; i < args.size(); i++)
             if (!check_rhs(args[i]))
                 return false;
         if (is_local(fn) && mlocal_name(fn) == mlocal_name(m_fn)) {
             /* recusive application */
             if (m_arg_idx < args.size()) {
                 expr const & arg = args[m_arg_idx];
                 /* arg must be structurally smaller than m_pattern */
                 if (!is_lt(arg, m_pattern)) {
                     trace_struct_aux(tout() << "structural recursion on argument #" << (m_arg_idx+1)
                                      << " was not used "
                                      << "for '" << m_fn << "'\nargument #" << (m_arg_idx+1)
                                      << " in the application\n  "
                                      << e << "\nis not structurally smaller than the one occurring in "
                                      << "the equation left-hand-side\n  "
                                      << m_lhs << "\n";);
                     return false;
                 }
             } else {