blob: 063322c1e6ab025859d8846a43765714093afc17 [file]
/*
Copyright (c) 2014 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Leonardo de Moura
*/
#include <vector>
#include <memory>
#include "runtime/alloc.h"
#include "runtime/interrupt.h"
#include "runtime/thread.h"
#include "kernel/expr.h"
#include "kernel/expr_sets.h"
#include "kernel/ptr_pair_set.h"
#include "util/alloc.h"
namespace lean {
/**
\brief Functional object for comparing expressions.
Remark if CompareBinderInfo is true, then functional object will also compare
binder information attached to lambda and Pi expressions
*/
template<bool CompareBinderInfo>
class expr_eq_fn {
ptr_pair_set m_cache;
size_t m_counter = 0;
bool check_cache(expr const & a, expr const & b) {
if (!is_shared(a) || !is_shared(b))
return false;
return !m_cache.insert(a.raw(), reinterpret_cast<uintptr_t>(b.raw()));
}
bool apply(expr const & a, expr const & b, bool root = false) {
if (is_eqp(a, b)) return true;
if (hash(a) != hash(b)) return false;
if (a.kind() != b.kind()) return false;
switch (a.kind()) {
case expr_kind::BVar: return bvar_idx(a) == bvar_idx(b);
case expr_kind::Lit: return lit_value(a) == lit_value(b);
case expr_kind::MVar: return mvar_name(a) == mvar_name(b);
case expr_kind::FVar: return fvar_name(a) == fvar_name(b);
case expr_kind::Sort: return sort_level(a) == sort_level(b);
default: break;
}
if (!root && check_cache(a, b)) {
return true;
}
/*
We increase the number of heartbeats here because some code (e.g., `simp`) may spend a lot of time comparing
`Expr`s (e.g., checking a cache with many collisions) without allocating any significant amount of memory.
We use the counter to invoke `add_heartbeats` later. Reason: heartbeat is a thread local storage, and morexpensive to update.
*/
m_counter++;
switch (a.kind()) {
case expr_kind::BVar:
case expr_kind::Lit:
case expr_kind::MVar:
case expr_kind::FVar:
case expr_kind::Sort:
lean_unreachable(); // LCOV_EXCL_LINE
case expr_kind::MData:
return
apply(mdata_expr(a), mdata_expr(b)) &&
mdata_data(a) == mdata_data(b);
case expr_kind::Proj:
return
apply(proj_expr(a), proj_expr(b)) &&
proj_sname(a) == proj_sname(b) &&
proj_idx(a) == proj_idx(b);
case expr_kind::Const:
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::App: {
if (!apply(app_arg(a), app_arg(b))) return false;
expr const * curr_a = &app_fn(a);
expr const * curr_b = &app_fn(b);
while (true) {
if (!is_app(*curr_a)) break;
if (!is_app(*curr_b)) return false;
if (!apply(app_arg(*curr_a), app_arg(*curr_b))) return false;
curr_a = &app_fn(*curr_a);
curr_b = &app_fn(*curr_b);
}
return apply(*curr_a, *curr_b);
}
case expr_kind::Lambda: case expr_kind::Pi:
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:
return
apply(let_type(a), let_type(b)) &&
apply(let_value(a), let_value(b)) &&
apply(let_body(a), let_body(b)) &&
let_nondep(a) == let_nondep(b) &&
(!CompareBinderInfo || let_name(a) == let_name(b));
}
lean_unreachable(); // LCOV_EXCL_LINE
}
public:
expr_eq_fn() {}
~expr_eq_fn() {
if (m_counter > 0) add_heartbeats(m_counter);
}
bool operator()(expr const & a, expr const & b) { return apply(a, b, true); }
};
bool is_equal(expr const & a, expr const & b) {
return expr_eq_fn<false>()(a, b);
}
extern "C" LEAN_EXPORT uint8 lean_expr_eqv(b_obj_arg a, b_obj_arg b) {
return expr_eq_fn<false>()(TO_REF(expr, a), TO_REF(expr, b));
}
extern "C" LEAN_EXPORT uint8 lean_expr_equal(b_obj_arg a, b_obj_arg b) {
return expr_eq_fn<true>()(TO_REF(expr, a), TO_REF(expr, b));
}
// Constructor indices of Lean.LBool.
enum class budgeted_eq_result : uint8 { False, True, Exhausted };
/**
Budgeted equality breaks referential transparency: pointer sharing can determine whether a
comparison finishes within the budget. Exhaustion must be handled as an inconclusive result.
*/
template<bool CompareBinderInfo>
class budgeted_expr_eq_fn {
ptr_pair_set m_cache;
size_t const m_initial_budget;
size_t m_remaining;
bool m_exhausted = false;
bool check_cache(expr const & a, expr const & b) {
if (!is_shared(a) || !is_shared(b))
return false;
return !m_cache.insert(a.raw(), reinterpret_cast<uintptr_t>(b.raw()));
}
bool consume(size_t n = 1) {
if (n > m_remaining) {
m_exhausted = true;
return false;
}
m_remaining -= n;
return true;
}
bool charge_payload(object * o) {
if (is_scalar(o)) return true;
if (is_cnstr(o)) {
unsigned n = cnstr_num_objs(o);
if (!consume(n)) return false;
for (unsigned i = 0; i < n; i++)
if (!charge_payload(cnstr_get(o, i))) return false;
} else if (is_array(o)) {
size_t n = array_size(o);
if (!consume(n)) return false;
for (size_t i = 0; i < n; i++)
if (!charge_payload(array_cptr(o)[i])) return false;
} else if (is_string(o)) {
return consume(string_size(o));
} else if (is_mpz(o)) {
return consume(mpz_value(o).size_in_bytes());
} else {
m_exhausted = true;
return false;
}
return true;
}
bool string_eq(string_ref const & s1, string_ref const & s2) {
if (s1.raw() == s2.raw()) return true;
size_t n = s1.num_bytes();
if (n != s2.num_bytes()) return false;
return consume(n) && s1 == s2;
}
bool data_value_eq(data_value const & a, data_value const & b) {
if (a.raw() == b.raw()) return true;
if (a.kind() != b.kind()) return false;
switch (a.kind()) {
case data_value_kind::String:
return string_eq(a.get_string(), b.get_string());
case data_value_kind::Syntax:
// Syntax.structEq revisits shared nodes; bound it by both unfolded trees.
return charge_payload(a.raw()) && charge_payload(b.raw()) && a == b;
default:
return a == b;
}
}
bool mdata_eq(kvmap const & a, kvmap const & b) {
object * it1 = a.raw();
object * it2 = b.raw();
while (!is_scalar(it1) && !is_scalar(it2)) {
if (it1 == it2) return true;
if (!consume()) return false;
kvmap_entry const & e1 = head<kvmap_entry>(it1);
kvmap_entry const & e2 = head<kvmap_entry>(it2);
if (e1.fst() != e2.fst() || !data_value_eq(e1.snd(), e2.snd())) return false;
it1 = cnstr_get(it1, 1);
it2 = cnstr_get(it2, 1);
}
return is_scalar(it1) && is_scalar(it2);
}
bool literal_eq(literal const & a, literal const & b) {
if (a.kind() != b.kind()) return false;
switch (a.kind()) {
case literal_kind::Nat:
return a.get_nat() == b.get_nat();
case literal_kind::String:
return string_eq(a.get_string(), b.get_string());
}
lean_unreachable(); // LCOV_EXCL_LINE
}
bool apply(expr const & a, expr const & b, bool root = false) {
if (is_eqp(a, b)) return true;
if (hash(a) != hash(b)) return false;
if (a.kind() != b.kind()) return false;
switch (a.kind()) {
case expr_kind::BVar: return bvar_idx(a) == bvar_idx(b);
case expr_kind::Lit: return literal_eq(lit_value(a), lit_value(b));
case expr_kind::MVar: return mvar_name(a) == mvar_name(b);
case expr_kind::FVar: return fvar_name(a) == fvar_name(b);
case expr_kind::Sort: return sort_level(a) == sort_level(b);
default: break;
}
if (!root && check_cache(a, b)) {
return true;
}
if (!consume()) return false;
switch (a.kind()) {
case expr_kind::BVar:
case expr_kind::Lit:
case expr_kind::MVar:
case expr_kind::FVar:
case expr_kind::Sort:
lean_unreachable(); // LCOV_EXCL_LINE
case expr_kind::MData:
return
apply(mdata_expr(a), mdata_expr(b)) &&
mdata_eq(mdata_data(a), mdata_data(b));
case expr_kind::Proj:
return
apply(proj_expr(a), proj_expr(b)) &&
proj_sname(a) == proj_sname(b) &&
proj_idx(a) == proj_idx(b);
case expr_kind::Const:
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::App: {
if (!apply(app_arg(a), app_arg(b))) return false;
expr const * curr_a = &app_fn(a);
expr const * curr_b = &app_fn(b);
while (true) {
if (!is_app(*curr_a)) break;
if (!is_app(*curr_b)) return false;
if (!consume()) return false;
if (!apply(app_arg(*curr_a), app_arg(*curr_b))) return false;
curr_a = &app_fn(*curr_a);
curr_b = &app_fn(*curr_b);
}
return apply(*curr_a, *curr_b);
}
case expr_kind::Lambda: case expr_kind::Pi:
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:
return
apply(let_type(a), let_type(b)) &&
apply(let_value(a), let_value(b)) &&
apply(let_body(a), let_body(b)) &&
let_nondep(a) == let_nondep(b) &&
(!CompareBinderInfo || let_name(a) == let_name(b));
}
lean_unreachable(); // LCOV_EXCL_LINE
}
public:
explicit budgeted_expr_eq_fn(size_t budget):m_initial_budget(budget), m_remaining(budget) {}
~budgeted_expr_eq_fn() {
size_t consumed = m_initial_budget - m_remaining;
if (consumed > 0) add_heartbeats(consumed);
}
budgeted_eq_result operator()(expr const & a, expr const & b) {
if (apply(a, b, true)) return budgeted_eq_result::True;
return m_exhausted ? budgeted_eq_result::Exhausted : budgeted_eq_result::False;
}
};
extern "C" LEAN_EXPORT uint8 lean_expr_eqv_budgeted(b_obj_arg a, b_obj_arg b, size_t budget) {
return static_cast<uint8>(budgeted_expr_eq_fn<false>(budget)(TO_REF(expr, a), TO_REF(expr, b)));
}
extern "C" LEAN_EXPORT uint8 lean_expr_equal_budgeted(b_obj_arg a, b_obj_arg b, size_t budget) {
return static_cast<uint8>(budgeted_expr_eq_fn<true>(budget)(TO_REF(expr, a), TO_REF(expr, b)));
}
}