From a68bf969015a177e8e23d50eae55dafd4a6978ca Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9mie=20Astor?= Date: Mon, 20 Sep 2021 20:13:21 +0200 Subject: [PATCH] :art: Add deep equality --- include/emit.h | 9 + include/lang_private.h | 1 + src/emit/emit.c | 8 +- src/lib/deep_equal.c | 240 +++++++++++++++++++++++++++ src/lib/engine.c | 2 + src/lib/object_op.c | 10 +- tests/deep_equal/eq.gw | 14 ++ tests/deep_equal/eq_fail.gw | 13 ++ tests/deep_equal/eq_fallback.gw | 2 + tests/deep_equal/eq_fallback_fail.gw | 2 + tests/deep_equal/ne.gw | 12 ++ tests/deep_equal/ne_fail.gw | 13 ++ tests/deep_equal/ne_fallback.gw | 2 + tests/deep_equal/ne_fallback_fail.gw | 2 + 14 files changed, 325 insertions(+), 5 deletions(-) create mode 100644 src/lib/deep_equal.c create mode 100644 tests/deep_equal/eq.gw create mode 100644 tests/deep_equal/eq_fail.gw create mode 100644 tests/deep_equal/eq_fallback.gw create mode 100644 tests/deep_equal/eq_fallback_fail.gw create mode 100644 tests/deep_equal/ne.gw create mode 100644 tests/deep_equal/ne_fail.gw create mode 100644 tests/deep_equal/ne_fallback.gw create mode 100644 tests/deep_equal/ne_fallback_fail.gw diff --git a/include/emit.h b/include/emit.h index 05c633df..35656e4d 100644 --- a/include/emit.h +++ b/include/emit.h @@ -65,6 +65,7 @@ m_bool emit_instantiate_object(const Emitter, const Type, const Array_Sub, const m_bool); ANN m_uint emit_code_offset(const Emitter emit); ANN m_uint emit_local(const Emitter emit, const Type t); +ANN m_uint emit_localn(const Emitter emit, const Type t); ANN void* emit_localx(const Emitter emit, const Type t); ANN m_bool emit_exp_spork(const Emitter, const Exp_Unary *); ANN m_bool emit_exp(const Emitter, const Exp); @@ -98,4 +99,12 @@ ANN Instr emit_dotstatic(Emitter, const m_uint, const bool); ANN Instr emit_dotmember(Emitter, const m_uint, const bool); ANN Instr emit_structmember(Emitter, const m_uint, const bool); ANN Instr emit_unionmember(Emitter, const m_uint, const bool); + + +ANN static inline m_uint emit_code_size(const Emitter emit) { + return vector_size(&emit->code->instr); +} + +ANN void emit_push_scope(const Emitter emit); +ANN void emit_pop_scope(const Emitter emit); #endif diff --git a/include/lang_private.h b/include/lang_private.h index 4a84b6ed..eb61ce14 100644 --- a/include/lang_private.h +++ b/include/lang_private.h @@ -15,4 +15,5 @@ ANN m_bool import_object_op(const Gwi gwi); ANN m_bool import_values(const Gwi gwi); ANN m_bool import_union(const Gwi gwi); ANN m_bool import_ref(const Gwi gwi); +ANN m_bool import_deep_equal(const Gwi gwi); #endif diff --git a/src/emit/emit.c b/src/emit/emit.c index 60f113c5..6c649b5e 100644 --- a/src/emit/emit.c +++ b/src/emit/emit.c @@ -133,11 +133,11 @@ ANN static inline m_bool ensure_emit(const Emitter emit, const Type t) { .flag = tflag_emit}; return envset_run(&es, t); } - +/* ANN static inline m_uint emit_code_size(const Emitter emit) { return vector_size(&emit->code->instr); } - +*/ ANN static void emit_struct_ctor(const Emitter emit, const Type type, const m_uint offset) { emit->code->frame->curr_offset += SZ_INT; @@ -247,7 +247,7 @@ ANN static void free_code(MemPool p, Code *code) { mp_free(p, Code, code); } -ANN static void emit_pop_scope(const Emitter emit) { +ANN void emit_pop_scope(const Emitter emit) { m_int offset; struct Vector_ v; vector_init(&v); @@ -277,7 +277,7 @@ ANN static inline void emit_pop_code(const Emitter emit) { emit->code = (Code *)vector_pop(&emit->stack); } -ANN static inline void emit_push_scope(const Emitter emit) { +ANN void emit_push_scope(const Emitter emit) { frame_push(emit->code->frame); vector_add(&emit->info->pure, 0); if (emit->info->debug) emit_add_instr(emit, DebugPush); diff --git a/src/lib/deep_equal.c b/src/lib/deep_equal.c new file mode 100644 index 00000000..11ec7109 --- /dev/null +++ b/src/lib/deep_equal.c @@ -0,0 +1,240 @@ +#include "gwion_util.h" +#include "gwion_ast.h" +#include "gwion_env.h" +#include "vm.h" +#include "instr.h" +#include "emit.h" +#include "gwion.h" +#include "object.h" +#include "operator.h" +#include "import.h" +#include "gwi.h" +#include "traverse.h" + +// fallbacks +#define deep_any(_name, _data, action, ACTION, _test, _t, _op) \ +static OP_##ACTION(op##action##_deep_##_t##_any) { \ + Exp_Binary *bin = data; \ + _test(_name##_exp(_data, bin->lhs)); \ + _test(_name##_exp(_data, bin->rhs)); \ + struct Op_Import opi = { \ + .lhs = bin->lhs->type, \ + .rhs = bin->rhs->type, \ + .op = insert_symbol(_data->gwion->st, #_op), \ + .data = (m_uint)bin, \ + .pos = exp_self(bin)->pos \ + }; \ + return op_##_name(_data, &opi); \ +} + +deep_any(check, env, ck, CHECK, CHECK_ON, eq, ==); +deep_any(emit, emit, em, EMIT, CHECK_BB, eq, ==); +deep_any(check, env, ck, CHECK, CHECK_ON, ne, !=); +deep_any(emit, emit, em, EMIT, CHECK_BB, ne, !=); + +// get members of a specific type +static void type_get_member(const Gwion gwion, const Type t, const Vector v) { + const Map m = &t->nspc->info->value->map; + for(m_uint i = 0; i < map_size(m); i++) { + const Value value = (Value)map_at(m, i); + if(!vflag(value, vflag_member)) continue; + if(isa(value->type, gwion->type[et_function]) > 0 && !is_fptr(gwion, value->type)) continue; + vector_add(v, (m_uint)value); + } +} + +// get members of a type, starting from parents +static void compound_get_member(const Env env, const Type t, const Vector v) { + if(t->info->parent && t->info->parent->nspc) + compound_get_member(env, t->info->parent, v); + type_get_member(env->gwion, t, v); +} + +ANN static inline void check_deep_equal_exp(const Env env, const Exp e, const Vector v) { + vector_init(v); + compound_get_member(env, e->type, v); + if(tflag(e->type, tflag_struct)) + exp_setvar(e, true); +} + +#define MK_DOT(_data, _exp, _value) \ + { \ + .d = { \ + .exp_dot = { \ + .base = _exp, \ + .xid = insert_symbol(_data->gwion->st, _value->name) \ + } \ + }, \ + .type = _value->type, \ + .exp_type = ae_exp_dot, \ + .pos = _exp->pos \ + } + +#define MK_BIN(_lhs, _rhs, _bin) \ + { \ + .d = { \ + .exp_binary = { \ + .lhs = &_lhs, \ + .rhs = &_rhs, \ + .op = _bin->op \ + } \ + }, \ + .exp_type = ae_exp_binary, \ + .pos = exp_self(_bin)->pos \ + } + +static bool deep_check(const Env env, const Exp_Binary *bin, + const Vector l, const Vector r) { + const m_uint lsz = vector_size(l), + rsz = vector_size(r); + if(lsz && rsz >= lsz) { + for(m_uint i = 0; i < lsz; i++) { + const Value lval = (Value)vector_at(l, i), + rval = (Value)vector_at(r, i); + struct Exp_ lexp = MK_DOT(env, bin->lhs, lval), + rexp = MK_DOT(env, bin->rhs, rval), + temp = MK_BIN(lexp, rexp, bin); + if(!check_exp(env, &temp)) + return false; + } + } else return false; + return true; +} + +static OP_CHECK(opck_deep_equal) { + Exp_Binary *const bin = data; + struct Vector_ l, r; + check_deep_equal_exp(env, bin->lhs, &l); + check_deep_equal_exp(env, bin->rhs, &r); + const bool ret = deep_check(env, bin, &l, &r); + vector_release(&l); + vector_release(&r); + if(ret > 0) return env->gwion->type[et_bool]; + ERR_N(exp_self(bin)->pos, "no deep operation for: {G+/}%s{0} {+}%s{0} {G+/}%s{0}", + bin->lhs->type->name, s_name(bin->op), bin->rhs->type->name); +} + +struct DeepEmit { + Exp exp; + Value val; + Exp tmp; + struct Vector_ vec; +}; + +ANN static inline Type deep_type(const Gwion gwion, const Type t) { + if(!tflag(t, tflag_struct)) + return t; + char c[128]; + sprintf(c, "Ref:[%s]", t->name); + return str2type(gwion, c, t->info->value->from->loc); +} + +ANN static void deep_emit_init(const Emitter emit, struct DeepEmit *d, const m_int offset) { + char name[256]; + sprintf(name, "@%u:%u", d->exp->pos.first.line, d->exp->pos.first.column); + d->val = new_value(emit->gwion->mp, deep_type(emit->gwion, d->exp->type), name); + d->tmp = new_prim_id(emit->gwion->mp, insert_symbol(emit->gwion->st, d->val->name), d->exp->pos); + d->tmp->d.prim.value = d->val; + d->tmp->type = d->val->type; + check_deep_equal_exp(emit->env, d->exp, &d->vec); + const Instr instr = emit_add_instr(emit, Reg2Mem); + instr->m_val2 = offset; + d->val->from->offset = instr->m_val = emit_localn(emit, d->val->type); +} + +ANN static void deep_emit_release(const Emitter emit, struct DeepEmit *d) { + free_exp(emit->gwion->mp, d->tmp); + value_remref(d->val, emit->gwion); + vector_release(&d->vec); +} + +struct DeepEmits { + struct DeepEmit *lhs; + struct DeepEmit *rhs; + struct Vector_ acc; + Exp_Binary *bin; +}; + +static void deep_emits_init(const Emitter emit, struct DeepEmits *ds) { + emit_add_instr(emit, RegMove)->m_val = -SZ_INT*2; + deep_emit_init(emit, ds->lhs, 0); + deep_emit_init(emit, ds->rhs, SZ_INT); + vector_init(&ds->acc); +} + +ANN static void deep_emits_release(const Emitter emit, struct DeepEmits *ds) { + deep_emit_release(emit, ds->lhs); + deep_emit_release(emit, ds->rhs); + vector_release(&ds->acc); +} + +ANN static void emit_deep_fail(const Emitter emit, const Vector v) { + const m_uint sz = emit_code_size(emit); + for(m_uint i = 0; i < vector_size(v); i++) { + const Instr branch = (Instr)vector_at(v, i); + branch->m_val = sz; + } + emit_add_instr(emit, RegMove)->m_val = -SZ_INT; + emit_add_instr(emit, RegSetImm)->m_val2 = -SZ_INT; +} + +ANN static bool deep_emit(const Emitter emit, struct DeepEmits *ds) { + for(m_uint i = 0; i < vector_size(&ds->lhs->vec); i++) { + const Value lhs = (Value)vector_at(&ds->lhs->vec, i), + rhs = (Value)vector_at(&ds->rhs->vec, i); + struct Exp_ lexp = MK_DOT(emit, ds->lhs->tmp, lhs); + struct Exp_ rexp = MK_DOT(emit, ds->rhs->tmp, rhs); + struct Exp_ temp = MK_BIN(lexp, rexp, ds->bin); + temp.type=emit->gwion->type[et_bool]; + if(emit_exp(emit, &temp) < 0) return false; + vector_add(&ds->acc, (m_uint)emit_add_instr(emit, BranchEqInt)); + const Instr pop = emit_add_instr(emit, RegMove); + pop->m_val = -SZ_INT; + } + const Instr jmp = emit_add_instr(emit, Goto); + emit_deep_fail(emit, &ds->acc); + jmp->m_val = emit_code_size(emit); + return true; +} + +static OP_EMIT(opem_deep_equal) { + emit_push_scope(emit); + Exp_Binary *const bin = data; + struct DeepEmit dl = { .exp=bin->lhs }; + struct DeepEmit dr = { .exp=bin->rhs }; + struct DeepEmits ds = { .lhs=&dl, .rhs=&dr, .bin = bin }; + deep_emits_init(emit, &ds); + const bool ret = deep_emit(emit, &ds); + deep_emits_release(emit, &ds); + emit_pop_scope(emit); + return ret ? GW_OK: GW_ERROR; +} + +GWION_IMPORT(deep_equal) { + + GWI_BB(gwi_oper_ini(gwi, (m_str)OP_ANY_TYPE, (m_str)OP_ANY_TYPE, "bool")) + + gwidoc(gwi, "Deep Equality fallback"); + GWI_BB(gwi_oper_add(gwi, opck_deep_eq_any)) + GWI_BB(gwi_oper_emi(gwi, opem_deep_eq_any)) + GWI_BB(gwi_oper_end(gwi, "?=", NULL)) + + gwidoc(gwi, "Deep Inequality fallback"); + GWI_BB(gwi_oper_add(gwi, opck_deep_ne_any)) + GWI_BB(gwi_oper_emi(gwi, opem_deep_ne_any)) + GWI_BB(gwi_oper_end(gwi, "<>", NULL)) + + GWI_BB(gwi_oper_ini(gwi, "@Compound", "@Compound", "bool")) + + gwidoc(gwi, "Deep Equality"); + GWI_BB(gwi_oper_add(gwi, opck_deep_equal)) + GWI_BB(gwi_oper_emi(gwi, opem_deep_equal)) + GWI_BB(gwi_oper_end(gwi, "?=", NULL)) + + gwidoc(gwi, "Deep Inequality"); + GWI_BB(gwi_oper_add(gwi, opck_deep_equal)) + GWI_BB(gwi_oper_emi(gwi, opem_deep_equal)) + GWI_BB(gwi_oper_end(gwi, "<>", NULL)) + + return GW_OK; +} diff --git a/src/lib/engine.c b/src/lib/engine.c index 756bbbde..9ee335c7 100644 --- a/src/lib/engine.c +++ b/src/lib/engine.c @@ -229,6 +229,8 @@ ANN static m_bool import_core_libs(const Gwi gwi) { GWI_BB(gwi_oper_add(gwi, opck_class_call)) GWI_BB(gwi_oper_end(gwi, "=>", NULL)) + GWI_BB(import_deep_equal(gwi)); + gwi_enum_ini(gwi, "@hidden_enum"); gwi_enum_add(gwi, "@hidden_enum", 0); gwi_enum_end(gwi); diff --git a/src/lib/object_op.c b/src/lib/object_op.c index f41a24d4..6155ae98 100644 --- a/src/lib/object_op.c +++ b/src/lib/object_op.c @@ -234,9 +234,17 @@ OP_CHECK(opck_object_dot) { return value->type; } +ANN static Type member_type(const Gwion gwion, const Type base) { + const Type t = actual_type(gwion, base); + if(strncmp(t->name, "Ref:[", 5)) + return t; + return (Type)vector_front(&t->info->tuple->contains); +} + OP_EMIT(opem_object_dot) { const Exp_Dot *member = (Exp_Dot *)data; - const Type t_base = actual_type(emit->gwion, member->base->type); +// const Type t_base = actual_type(emit->gwion, member->base->type); + const Type t_base = member_type(emit->gwion, member->base->type); const Value value = find_value(t_base, member->xid); if (is_class(emit->gwion, value->type)) { const Instr instr = emit_add_instr(emit, RegPushImm); diff --git a/tests/deep_equal/eq.gw b/tests/deep_equal/eq.gw new file mode 100644 index 00000000..e432a3b2 --- /dev/null +++ b/tests/deep_equal/eq.gw @@ -0,0 +1,14 @@ +#! [contains] false + +struct C { + 12 => const int i; +} + +struct D { + 42 => const int i; +} + +const C c; +const D d; + +<<< c ?= d >>>; diff --git a/tests/deep_equal/eq_fail.gw b/tests/deep_equal/eq_fail.gw new file mode 100644 index 00000000..4f4bfe4e --- /dev/null +++ b/tests/deep_equal/eq_fail.gw @@ -0,0 +1,13 @@ +#! [contains] no deep operation +struct C { + 12 => const int i; + 12 => const int j; +} +struct D { + 42 => const int i; +} + +var C c; +var D d; + +<<< c ?= d >>>; diff --git a/tests/deep_equal/eq_fallback.gw b/tests/deep_equal/eq_fallback.gw new file mode 100644 index 00000000..6e05c18f --- /dev/null +++ b/tests/deep_equal/eq_fallback.gw @@ -0,0 +1,2 @@ +#! [contains] true +<<< 1 ?= 1 >>>; diff --git a/tests/deep_equal/eq_fallback_fail.gw b/tests/deep_equal/eq_fallback_fail.gw new file mode 100644 index 00000000..d36e8b3e --- /dev/null +++ b/tests/deep_equal/eq_fallback_fail.gw @@ -0,0 +1,2 @@ +#! [contains] no match found for operator +<<< 1 ?= me >>>; diff --git a/tests/deep_equal/ne.gw b/tests/deep_equal/ne.gw new file mode 100644 index 00000000..14e9c532 --- /dev/null +++ b/tests/deep_equal/ne.gw @@ -0,0 +1,12 @@ +#! [contains] true +struct C { + 12 => const int i; +} +struct D { + 42 => const int i; +} + +var C c; +var D d; + +<<< c <> d >>>; diff --git a/tests/deep_equal/ne_fail.gw b/tests/deep_equal/ne_fail.gw new file mode 100644 index 00000000..b6009545 --- /dev/null +++ b/tests/deep_equal/ne_fail.gw @@ -0,0 +1,13 @@ +#! [contains] no deep operation +struct C { + 12 => const int i; + 12 => const int j; +} +struct D { + 42 => const int i; +} + +var C c; +var D d; + +<<< c <> d >>>; diff --git a/tests/deep_equal/ne_fallback.gw b/tests/deep_equal/ne_fallback.gw new file mode 100644 index 00000000..cbd88897 --- /dev/null +++ b/tests/deep_equal/ne_fallback.gw @@ -0,0 +1,2 @@ +#! [contains] false +<<< 1 <> 1 >>>; diff --git a/tests/deep_equal/ne_fallback_fail.gw b/tests/deep_equal/ne_fallback_fail.gw new file mode 100644 index 00000000..8cb09247 --- /dev/null +++ b/tests/deep_equal/ne_fallback_fail.gw @@ -0,0 +1,2 @@ +#! [contains] no match found for operator +<<< 1 <> me >>>; -- 2.43.0