From 04ba58067aedc8e79f6220a5ea0b28d9656b5051 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 25 Feb 2023 21:52:18 -0700 Subject: [PATCH] add, implement and use the Unifier trait --- Cargo.lock | 12 + Cargo.toml | 1 + src/machine/machine_state_impl.rs | 1173 ++--------------------------- src/machine/mod.rs | 1 + src/machine/system_calls.rs | 1 - src/machine/unify.rs | 763 +++++++++++++++++++ 6 files changed, 834 insertions(+), 1117 deletions(-) create mode 100644 src/machine/unify.rs diff --git a/Cargo.lock b/Cargo.lock index 63784cd9..3b817784 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -367,6 +367,17 @@ dependencies = [ "syn 1.0.103", ] +[[package]] +name = "derive_deref" +version = "1.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dcdbcee2d9941369faba772587a565f4f534e42cb8d17e5295871de730163b2b" +dependencies = [ + "proc-macro2 1.0.47", + "quote 1.0.21", + "syn 1.0.103", +] + [[package]] name = "difflib" version = "0.4.0" @@ -1821,6 +1832,7 @@ dependencies = [ "crossterm", "crrl", "ctrlc", + "derive_deref", "dirs-next", "divrem", "futures", diff --git a/Cargo.toml b/Cargo.toml index 6c98ea43..b21d4921 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -63,6 +63,7 @@ hyper = { version = "0.14", features = ["full"] } hyper-tls = "0.5.0" tokio = { version = "1.24.2", features = ["full"] } futures = "0.3" +derive_deref = "1.1.1" [dev-dependencies] assert_cmd = "1.0.3" diff --git a/src/machine/machine_state_impl.rs b/src/machine/machine_state_impl.rs index b486fc31..b457ecae 100644 --- a/src/machine/machine_state_impl.rs +++ b/src/machine/machine_state_impl.rs @@ -11,10 +11,10 @@ use crate::machine::machine_indices::*; use crate::machine::machine_state::*; use crate::machine::partial_string::*; use crate::machine::stack::*; +use crate::machine::unify::*; use crate::parser::ast::*; use crate::parser::rug::{Integer, Rational}; -use fxhash::FxBuildHasher; use indexmap::IndexSet; use std::cmp::Ordering; @@ -235,634 +235,96 @@ impl MachineState { ) } - fn unify_structure(&mut self, s1: usize, value: HeapCellValue) { - // s1 is the value of a STR cell. - let (n1, a1) = cell_as_atom_cell!(self.heap[s1]).get_name_and_arity(); - - read_heap_cell!(value, - (HeapCellValueTag::Str, s2) => { - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - if n1 == n2 && a1 == a2 { - for idx in (0..a1).rev() { - self.pdl.push(heap_loc_as_cell!(s2+1+idx)); - self.pdl.push(heap_loc_as_cell!(s1+1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::Lis, l2) => { - if a1 == 2 && n1 == atom!(".") { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(l2+1+idx)); - self.pdl.push(heap_loc_as_cell!(s1+1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::Atom, (n2, a2)) => { - if !(a1 == 0 && a2 == 0 && n1 == n2) { - self.fail = true; - } - } - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), str_loc_as_cell!(s1)); - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), str_loc_as_cell!(s1)); - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), str_loc_as_cell!(s1)); - } - _ => { - self.fail = true; - } - ) + #[inline] + pub(super) fn bind_with_occurs_check_wrapper(&mut self, r: Ref, value: HeapCellValue) { + let mut unifier = CompositeUnifierForOccursCheck::from(DefaultUnifier::from(self)); + unifier.bind(r, value); } - fn unify_list(&mut self, l1: usize, d2: HeapCellValue) { - read_heap_cell!(d2, - (HeapCellValueTag::Lis, l2) => { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(l2 + idx)); - self.pdl.push(heap_loc_as_cell!(l1 + idx)); - } - } - (HeapCellValueTag::Str, s2) => { - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); + #[inline] + pub(super) fn bind_with_occurs_check_with_error_wrapper( + &mut self, + r: Ref, + value: HeapCellValue, + ) { + let mut unifier = CompositeUnifierForOccursCheckWithError::from( + DefaultUnifier::from(self), + ); - if a2 == 2 && n2 == atom!(".") { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(s2+1+idx)); - self.pdl.push(heap_loc_as_cell!(l1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::PStrLoc | HeapCellValueTag::CStr | HeapCellValueTag::PStr) => { - self.unify_partial_string(list_loc_as_cell!(l1), d2) - } - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), list_loc_as_cell!(l1)); - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), list_loc_as_cell!(l1)); - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), list_loc_as_cell!(l1)); - } - _ => { - self.fail = true; - } - ) + unifier.bind(r, value); } - pub fn unify_complete_string(&mut self, atom: Atom, value: HeapCellValue) { - if let Some(r) = value.as_var() { - if atom == atom!("") { - self.bind(r, atom_as_cell!(atom!("[]"))); - } else { - self.bind(r, atom_as_cstr_cell!(atom)); - } - - return; - } - - read_heap_cell!(value, - (HeapCellValueTag::Atom, (cstr_atom, arity)) if atom == atom!("") => { - debug_assert_eq!(arity, 0); - self.fail = cstr_atom != atom!("[]"); - } - (HeapCellValueTag::Str, s) => { - let (name, arity) = cell_as_atom_cell!(self.heap[s]) - .get_name_and_arity(); - - if arity == 0 { - self.fail = atom == atom!("") && name != atom!("[]"); - } else { - // this is intentionally the same policy for - // value.tag() == Lis and PStrLoc. they're not - // grouped together to allow for arity == 0. - self.unify_partial_string(atom_as_cstr_cell!(atom), value); - - if !self.pdl.is_empty() { - self.unify(); - } - } - } - (HeapCellValueTag::CStr, cstr_atom) => { - self.fail = atom != cstr_atom; - } - (HeapCellValueTag::Lis | HeapCellValueTag::PStrLoc) => { - self.unify_partial_string(atom_as_cstr_cell!(atom), value); - - if !self.pdl.is_empty() { - self.unify(); - } - } - _ => { - self.fail = true; - } - ); + pub fn unify(&mut self) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_internal(); } - // d1's tag is LIS, STR or PSTRLOC. - pub fn unify_partial_string(&mut self, d1: HeapCellValue, d2: HeapCellValue) { - if let Some(r) = d2.as_var() { - self.bind(r, d1); - return; - } - - let s1 = self.heap.len(); - - self.heap.push(d1); - self.heap.push(d2); - - let mut pstr_iter1 = HeapPStrIter::new(&self.heap, s1); - let mut pstr_iter2 = HeapPStrIter::new(&self.heap, s1 + 1); - - match compare_pstr_prefixes(&mut pstr_iter1, &mut pstr_iter2) { - PStrCmpResult::Ordered(Ordering::Equal) => {} - PStrCmpResult::Ordered(Ordering::Less) => { - if pstr_iter2.focus.as_var().is_none() { - self.fail = true; - } else { - self.pdl.push(empty_list_as_cell!()); - self.pdl.push(pstr_iter2.focus); - } - } - PStrCmpResult::Ordered(Ordering::Greater) => { - if pstr_iter1.focus.as_var().is_none() { - self.fail = true; - } else { - self.pdl.push(empty_list_as_cell!()); - self.pdl.push(pstr_iter1.focus); - } - } - continuable @ PStrCmpResult::FirstIterContinuable(iteratee) | - continuable @ PStrCmpResult::SecondIterContinuable(iteratee) => { - if continuable.is_second_iter() { - std::mem::swap(&mut pstr_iter1, &mut pstr_iter2); - } - - let mut chars_iter = PStrCharsIter { - iter: pstr_iter1, - item: Some(iteratee), - }; - - let mut focus = pstr_iter2.focus; - - 'outer: loop { - while let Some(c) = chars_iter.peek() { - read_heap_cell!(focus, - (HeapCellValueTag::Lis, l) => { - let val = pstr_iter2.heap[l]; - - self.pdl.push(val); - self.pdl.push(char_as_cell!(c)); - - focus = pstr_iter2.heap[l+1]; - } - (HeapCellValueTag::Str, s) => { - let (name, arity) = cell_as_atom_cell!(pstr_iter2.heap[s]) - .get_name_and_arity(); - - if name == atom!(".") && arity == 2 { - self.pdl.push(pstr_iter2.heap[s+1]); - self.pdl.push(char_as_cell!(c)); - - focus = pstr_iter2.heap[s+2]; - } else { - self.fail = true; - break 'outer; - } - } - (HeapCellValueTag::AttrVar | HeapCellValueTag::Var, h) => { - match chars_iter.item.unwrap() { - PStrIteratee::Char(focus, _) => { - self.pdl.push(self.heap[focus]); - self.pdl.push(heap_loc_as_cell!(h)); - } - PStrIteratee::PStrSegment(focus, _, n) => { - read_heap_cell!(self.heap[focus], - (HeapCellValueTag::CStr | HeapCellValueTag::PStr, pstr_atom) => { - if focus < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - if n == 0 { - let target_cell = match self.heap[focus].get_tag() { - HeapCellValueTag::CStr => { - atom_as_cstr_cell!(pstr_atom) - } - HeapCellValueTag::PStr => { - pstr_loc_as_cell!(focus) - } - _ => { - unreachable!() - } - }; - - self.pdl.push(target_cell); - self.pdl.push(heap_loc_as_cell!(h)); - } else { - let h_len = self.heap.len(); - - self.heap.push(pstr_offset_as_cell!(focus)); - self.heap.push(fixnum_as_cell!( - Fixnum::build_with(n as i64) - )); - - self.pdl.push(pstr_loc_as_cell!(h_len)); - self.pdl.push(heap_loc_as_cell!(h)); - } - - return; - } - (HeapCellValueTag::PStrOffset, pstr_loc) => { - let n0 = cell_as_fixnum!(self.heap[focus+1]) - .get_num() as usize; - - if pstr_loc < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - if n == n0 { - self.pdl.push(pstr_loc_as_cell!(focus)); - self.pdl.push(heap_loc_as_cell!(h)); - } else { - let h_len = self.heap.len(); - - self.heap.push(pstr_offset_as_cell!(pstr_loc)); - self.heap.push(fixnum_as_cell!( - Fixnum::build_with(n as i64) - )); - - self.pdl.push(pstr_loc_as_cell!(h_len)); - self.pdl.push(heap_loc_as_cell!(h)); - } - - return; - } - _ => { - } - ); - - if focus < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - self.pdl.push(self.heap[focus]); - self.pdl.push(heap_loc_as_cell!(h)); - - return; - } - } - - break 'outer; - } - _ => { - self.fail = true; - break 'outer; - } - ); - - chars_iter.next(); - } - - chars_iter.iter.next(); - - self.pdl.push(focus); - self.pdl.push(chars_iter.iter.focus); + pub fn unify_structure(&mut self, s1: usize, value: HeapCellValue) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_structure(s1, value); + } - break; - } - } - PStrCmpResult::Unordered => { - self.pdl.push(pstr_iter1.focus); - self.pdl.push(pstr_iter2.focus); - } - } + pub fn unify_atom(&mut self, atom: Atom, value: HeapCellValue) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_atom(atom, value); + } - self.heap.pop(); - self.heap.pop(); + pub fn unify_list(&mut self, l1: usize, value: HeapCellValue) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_list(l1, value); } - pub fn unify_atom(&mut self, atom: Atom, value: HeapCellValue) { - read_heap_cell!(value, - (HeapCellValueTag::Atom, (name, arity)) => { - self.fail = !(arity == 0 && name == atom); - } - (HeapCellValueTag::Str, s) => { - let (name, arity) = cell_as_atom_cell!(self.heap[s]) - .get_name_and_arity(); + pub fn unify_complete_string(&mut self, atom: Atom, value: HeapCellValue) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_complete_string(atom, value); + } - self.fail = !(arity == 0 && name == atom); - } - (HeapCellValueTag::CStr, cstr_atom) if atom == atom!("[]") => { - self.fail = cstr_atom != atom!(""); - } - (HeapCellValueTag::Char, c1) => { - if let Some(c2) = atom.as_char() { - self.fail = c1 != c2; - } else { - self.fail = true; - } - } - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), atom_as_cell!(atom)); - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), atom_as_cell!(atom)); - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), atom_as_cell!(atom)); - } - _ => { - self.fail = true; - } - ); + pub fn unify_partial_string(&mut self, value_1: HeapCellValue, value_2: HeapCellValue) { + let mut unifier = DefaultUnifier::from(self); + unifier.unify_partial_string(value_1, value_2); } pub fn unify_char(&mut self, c: char, value: HeapCellValue) { - read_heap_cell!(value, - (HeapCellValueTag::Atom, (name, arity)) => { - if let Some(c2) = name.as_char() { - self.fail = !(c == c2 && arity == 0); - } else { - self.fail = true; - } - } - (HeapCellValueTag::Str, s) => { - let (name, arity) = cell_as_atom_cell!(self.heap[s]) - .get_name_and_arity(); - - if let Some(c2) = name.as_char() { - self.fail = !(c == c2 && arity == 0); - } else { - self.fail = true; - } - } - (HeapCellValueTag::Char, c2) => { - if c != c2 { - self.fail = true; - } - } - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), char_as_cell!(c)); - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), char_as_cell!(c)); - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), char_as_cell!(c)); - } - _ => { - self.fail = true; - } - ); + let mut unifier = DefaultUnifier::from(self); + unifier.unify_char(c, value); } pub fn unify_fixnum(&mut self, n1: Fixnum, value: HeapCellValue) { - if let Some(r) = value.as_var() { - self.bind(r, fixnum_as_cell!(n1)); - return; - } - - match Number::try_from(value) { - Ok(n2) => match n2 { - Number::Fixnum(n2) if n1.get_num() == n2.get_num() => {} - Number::Integer(n2) if n1.get_num() == *n2 => {} - Number::Rational(n2) if n1.get_num() == *n2 => {} - _ => { - self.fail = true; - } - }, - Err(_) => { - self.fail = true; - } - } + let mut unifier = DefaultUnifier::from(self); + unifier.unify_fixnum(n1, value); } pub fn unify_big_int(&mut self, n1: TypedArenaPtr, value: HeapCellValue) { - if let Some(r) = value.as_var() { - self.bind(r, typed_arena_ptr_as_cell!(n1)); - return; - } - - match Number::try_from(value) { - Ok(n2) => match n2 { - Number::Fixnum(n2) if *n1 == n2.get_num() => {} - Number::Integer(n2) if *n1 == *n2 => {} - Number::Rational(n2) if *n1 == *n2 => {} - _ => { - self.fail = true; - } - }, - Err(_) => { - self.fail = true; - } - } + let mut unifier = DefaultUnifier::from(self); + unifier.unify_big_num(n1, value); } pub fn unify_rational(&mut self, n1: TypedArenaPtr, value: HeapCellValue) { - if let Some(r) = value.as_var() { - self.bind(r, typed_arena_ptr_as_cell!(n1)); - return; - } - - match Number::try_from(value) { - Ok(n2) => match n2 { - Number::Fixnum(n2) if *n1 == n2.get_num() => {} - Number::Integer(n2) if *n1 == *n2 => {} - Number::Rational(n2) if *n1 == *n2 => {} - _ => { - self.fail = true; - } - }, - Err(_) => { - self.fail = true; - } - } + let mut unifier = DefaultUnifier::from(self); + unifier.unify_big_num(n1, value); } pub fn unify_f64(&mut self, f1: F64Ptr, value: HeapCellValue) { - if let Some(r) = value.as_var() { - self.bind(r, HeapCellValue::from(f1)); - return; - } - - read_heap_cell!(value, - (HeapCellValueTag::F64, f2) => { - self.fail = **f1 != **f2; - } - _ => { - self.fail = true; - } - ); + let mut unifier = DefaultUnifier::from(self); + unifier.unify_f64(f1, value); } pub fn unify_constant(&mut self, ptr: UntypedArenaPtr, value: HeapCellValue) { - if let Some(ptr2) = value.to_untyped_arena_ptr() { - if ptr.get_ptr() == ptr2.get_ptr() { - return; - } - } - - match_untyped_arena_ptr!(ptr, - (ArenaHeaderTag::Integer, int_ptr) => { - self.unify_big_int(int_ptr, value); - } - (ArenaHeaderTag::Rational, rat_ptr) => { - self.unify_rational(rat_ptr, value); - } - _ => { - if let Some(r) = value.as_var() { - self.bind(r, untyped_arena_ptr_as_cell!(ptr)); - } else { - self.fail = true; - } - } - ); + let mut unifier = DefaultUnifier::from(self); + unifier.unify_constant(ptr, value); } - pub fn unify(&mut self) { - let mut tabu_list = IndexSet::with_hasher(FxBuildHasher::default()); - - while !(self.pdl.is_empty() || self.fail) { - let s1 = self.pdl.pop().unwrap(); - let s1 = self.deref(s1); - - let s2 = self.pdl.pop().unwrap(); - let s2 = self.deref(s2); - - if s1 != s2 { - let d1 = self.store(s1); - let d2 = self.store(s2); - - read_heap_cell!(d1, - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), d2); - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), d2); - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), d2); - } - (HeapCellValueTag::Atom, (name, arity)) => { - debug_assert!(arity == 0); - self.unify_atom(name, d2); - } - (HeapCellValueTag::Str, s1) => { - if tabu_list.contains(&(d1, d2)) { - continue; - } - - self.unify_structure(s1, d2); - - if !self.fail { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::Lis, l1) => { - if d2.is_ref() { - if tabu_list.contains(&(d1, d2)) { - continue; - } - } - - self.unify_list(l1, d2); - - if !self.fail { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::PStrLoc) => { - read_heap_cell!(d2, - (HeapCellValueTag::PStrLoc | - HeapCellValueTag::Lis | - HeapCellValueTag::Str) => { - if tabu_list.contains(&(d1, d2)) { - continue; - } - } - (HeapCellValueTag::CStr | - HeapCellValueTag::AttrVar | - HeapCellValueTag::Var | - HeapCellValueTag::StackVar) => { - } - _ => { - self.fail = true; - break; - } - ); - - self.unify_partial_string(d1, d2); + pub(super) fn unify_with_occurs_check_with_error(&mut self) { + let mut unifier = CompositeUnifierForOccursCheckWithError::from( + DefaultUnifier::from(self), + ); - if !self.fail && !d2.is_constant() { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::CStr) => { - read_heap_cell!(d2, - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), d1); - continue; - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), d1); - continue; - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), d1); - continue; - } - (HeapCellValueTag::Str | - HeapCellValueTag::Lis | - HeapCellValueTag::PStrLoc) => { - } - (HeapCellValueTag::CStr) => { - self.fail = d1 != d2; - continue; - } - _ => { - self.fail = true; - return; - } - ); + unifier.unify_internal(); + } - self.unify_partial_string(d2, d1); - } - (HeapCellValueTag::F64, f1) => { - self.unify_f64(f1, d2); - } - (HeapCellValueTag::Fixnum, n1) => { - self.unify_fixnum(n1, d2); - } - (HeapCellValueTag::Char, c1) => { - self.unify_char(c1, d2); - } - (HeapCellValueTag::Cons, ptr_1) => { - self.unify_constant(ptr_1, d2); - } - _ => { - unreachable!(); - } - ); - } - } + pub(super) fn unify_with_occurs_check(&mut self) { + let mut unifier = CompositeUnifierForOccursCheck::from(DefaultUnifier::from(self)); + unifier.unify_internal(); } pub(super) fn set_ball(&mut self) { @@ -883,527 +345,6 @@ impl MachineState { self.fail = true; } - #[inline] - pub fn bind_with_occurs_check(&mut self, r: Ref, value: HeapCellValue) -> bool { - if let RefTag::StackCell = r.get_tag() { - // local variable optimization -- r cannot occur in the - // heap structure bound to value, so don't bother - // traversing value. - self.bind(r, value); - return false; - } - - let mut occurs_triggered = false; - - if !value.is_constant() { - for addr in stackful_preorder_iter(&mut self.heap, value) { - let addr = unmark_cell_bits!(addr); - - if let Some(inner_r) = addr.as_var() { - if r == inner_r { - occurs_triggered = true; - break; - } - } - } - } - - if occurs_triggered { - self.fail = true; - } else { - self.bind(r, value); - } - - return occurs_triggered; - } - - #[inline] - pub(super) fn bind_with_occurs_check_wrapper(&mut self, r: Ref, value: HeapCellValue) { - self.bind_with_occurs_check(r, value); - } - - #[inline] - pub(super) fn bind_with_occurs_check_with_error_wrapper( - &mut self, - r: Ref, - value: HeapCellValue, - ) { - if self.bind_with_occurs_check(r, value) { - let err = self.representation_error(RepFlag::Term); - let stub = functor_stub(atom!("unify_with_occurs_check"), 2); - let err = self.error_form(err, stub); - - self.throw_exception(err); - } - } - - pub(super) fn unify_with_occurs_check_with_error(&mut self) { - let mut throw_error = false; - self.unify_with_occurs_check_loop(|| throw_error = true); - - if throw_error { - let err = self.representation_error(RepFlag::Term); - let stub = functor_stub(atom!("unify_with_occurs_check"), 2); - let err = self.error_form(err, stub); - - self.throw_exception(err); - } - } - - pub(super) fn unify_with_occurs_check(&mut self) { - self.unify_with_occurs_check_loop(|| {}) - } - - fn unify_structure_with_occurs_check( - &mut self, - s1: usize, - value: HeapCellValue, - mut occurs_trigger: impl FnMut(), - ) { - // s1 is the value of a STR cell. - let (n1, a1) = cell_as_atom_cell!(self.heap[s1]).get_name_and_arity(); - - read_heap_cell!(value, - (HeapCellValueTag::Str, s2) => { - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - if n1 == n2 && a1 == a2 { - for idx in (0..a1).rev() { - self.pdl.push(heap_loc_as_cell!(s2+1+idx)); - self.pdl.push(heap_loc_as_cell!(s1+1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::Lis, l2) => { - if a1 == 2 && n1 == atom!(".") { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(l2+idx)); - self.pdl.push(heap_loc_as_cell!(s1+1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::Atom, (n2, a2)) => { - self.fail = !(a1 == 0 && a2 == 0 && n1 == n2); - } - (HeapCellValueTag::AttrVar, h) => { - if self.bind_with_occurs_check(Ref::attr_var(h), str_loc_as_cell!(s1)) { - occurs_trigger(); - } - } - (HeapCellValueTag::Var, h) => { - if self.bind_with_occurs_check(Ref::heap_cell(h), str_loc_as_cell!(s1)) { - occurs_trigger(); - } - } - (HeapCellValueTag::StackVar, s) => { - if self.bind_with_occurs_check(Ref::stack_cell(s), str_loc_as_cell!(s1)) { - occurs_trigger(); - } - } - _ => { - self.fail = true; - } - ) - } - - // the return value of unify_partial_string_with_occurs_check is - // interpreted as follows: - // - // Some(None) -- the strings are equal, nothing to unify - // Some(Some(f2,f1)) -- prefixes equal, try to unify focus values f2, f1 - // None -- prefixes not equal, unification fails - // - // d1's tag is assumed to be one of LIS, STR or PSTRLOC. - pub fn unify_partial_string_with_occurs_check( - &mut self, - d1: HeapCellValue, - d2: HeapCellValue, - mut occurs_trigger: impl FnMut(), - ) { - if let Some(r) = d2.as_var() { - if self.bind_with_occurs_check(r, d1) { - occurs_trigger(); - } - - return; - } - - let s1 = self.heap.len(); - - self.heap.push(d1); - self.heap.push(d2); - - let mut pstr_iter1 = HeapPStrIter::new(&self.heap, s1); - let mut pstr_iter2 = HeapPStrIter::new(&self.heap, s1 + 1); - - match compare_pstr_prefixes(&mut pstr_iter1, &mut pstr_iter2) { - PStrCmpResult::Ordered(Ordering::Equal) => {} - PStrCmpResult::Ordered(Ordering::Less) => { - if pstr_iter2.focus.as_var().is_none() { - self.fail = true; - } else { - self.pdl.push(empty_list_as_cell!()); - self.pdl.push(pstr_iter2.focus); - } - } - PStrCmpResult::Ordered(Ordering::Greater) => { - if pstr_iter1.focus.as_var().is_none() { - self.fail = true; - } else { - self.pdl.push(empty_list_as_cell!()); - self.pdl.push(pstr_iter1.focus); - } - } - continuable @ PStrCmpResult::FirstIterContinuable(iteratee) | - continuable @ PStrCmpResult::SecondIterContinuable(iteratee) => { - if continuable.is_second_iter() { - std::mem::swap(&mut pstr_iter1, &mut pstr_iter2); - } - - let mut chars_iter = PStrCharsIter { - iter: pstr_iter1, - item: Some(iteratee), - }; - - let mut focus = pstr_iter2.focus; - - 'outer: loop { - while let Some(c) = chars_iter.peek() { - read_heap_cell!(focus, - (HeapCellValueTag::Lis, l) => { - let val = pstr_iter2.heap[l]; - - self.pdl.push(val); - self.pdl.push(char_as_cell!(c)); - - focus = pstr_iter2.heap[l+1]; - } - (HeapCellValueTag::Str, s) => { - let (name, arity) = cell_as_atom_cell!(pstr_iter2.heap[s]) - .get_name_and_arity(); - - if name == atom!(".") && arity == 2 { - self.pdl.push(pstr_iter2.heap[s+1]); - self.pdl.push(char_as_cell!(c)); - - focus = pstr_iter2.heap[s+2]; - } else { - self.fail = true; - break 'outer; - } - } - (HeapCellValueTag::AttrVar | HeapCellValueTag::Var, h) => { - match chars_iter.item.unwrap() { - PStrIteratee::Char(focus, _) => { - self.pdl.push(self.heap[focus]); - self.pdl.push(heap_loc_as_cell!(h)); - } - PStrIteratee::PStrSegment(focus, _, n) => { - read_heap_cell!(self.heap[focus], - (HeapCellValueTag::CStr | HeapCellValueTag::PStr, pstr_atom) => { - if focus < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - if n == 0 { - let target_cell = match self.heap[focus].get_tag() { - HeapCellValueTag::CStr => { - atom_as_cstr_cell!(pstr_atom) - } - HeapCellValueTag::PStr => { - pstr_loc_as_cell!(focus) - } - _ => { - unreachable!() - } - }; - - self.pdl.push(target_cell); - self.pdl.push(heap_loc_as_cell!(h)); - } else { - let h_len = self.heap.len(); - - self.heap.push(pstr_offset_as_cell!(focus)); - self.heap.push(fixnum_as_cell!( - Fixnum::build_with(n as i64) - )); - - self.pdl.push(pstr_loc_as_cell!(h_len)); - self.pdl.push(heap_loc_as_cell!(h)); - } - - return; - } - (HeapCellValueTag::PStrOffset, pstr_loc) => { - let n0 = cell_as_fixnum!(self.heap[focus+1]) - .get_num() as usize; - - if pstr_loc < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - if n == n0 { - self.pdl.push(pstr_loc_as_cell!(focus)); - self.pdl.push(heap_loc_as_cell!(h)); - } else { - let h_len = self.heap.len(); - - self.heap.push(pstr_offset_as_cell!(pstr_loc)); - self.heap.push(fixnum_as_cell!( - Fixnum::build_with(n as i64) - )); - - self.pdl.push(pstr_loc_as_cell!(h_len)); - self.pdl.push(heap_loc_as_cell!(h)); - } - - return; - } - _ => { - } - ); - - if focus < self.heap.len() - 2 { - self.heap.pop(); - self.heap.pop(); - } - - self.pdl.push(self.heap[focus]); - self.pdl.push(heap_loc_as_cell!(h)); - - return; - } - } - - break 'outer; - } - _ => { - self.fail = true; - break 'outer; - } - ); - - chars_iter.next(); - } - - chars_iter.iter.next(); - - self.pdl.push(chars_iter.iter.focus); - self.pdl.push(focus); - - break; - } - } - PStrCmpResult::Unordered => { - self.pdl.push(pstr_iter1.focus); - self.pdl.push(pstr_iter2.focus); - } - } - - self.heap.pop(); - self.heap.pop(); - } - - fn unify_list_with_occurs_trigger( - &mut self, - l1: usize, - d2: HeapCellValue, - mut occurs_trigger: impl FnMut(), - ) { - read_heap_cell!(d2, - (HeapCellValueTag::Lis, l2) => { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(l2+idx)); - self.pdl.push(heap_loc_as_cell!(l1+idx)); - } - } - (HeapCellValueTag::Str, s2) => { - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - if a2 == 2 && n2 == atom!(".") { - for idx in (0..2).rev() { - self.pdl.push(heap_loc_as_cell!(s2+1+idx)); - self.pdl.push(heap_loc_as_cell!(l1+idx)); - } - } else { - self.fail = true; - } - } - (HeapCellValueTag::PStrLoc | HeapCellValueTag::CStr | HeapCellValueTag::PStr) => { - self.unify_partial_string_with_occurs_check( - list_loc_as_cell!(l1), - d2, - &mut occurs_trigger, - ) - } - (HeapCellValueTag::AttrVar, h) => { - if self.bind_with_occurs_check(Ref::attr_var(h), list_loc_as_cell!(l1)) { - occurs_trigger(); - } - } - (HeapCellValueTag::Var, h) => { - if self.bind_with_occurs_check(Ref::heap_cell(h), list_loc_as_cell!(l1)) { - occurs_trigger(); - } - } - (HeapCellValueTag::StackVar, s) => { - if self.bind_with_occurs_check(Ref::stack_cell(s), list_loc_as_cell!(l1)) { - occurs_trigger(); - } - } - _ => { - self.fail = true; - } - ) - } - - pub(super) fn unify_with_occurs_check_loop(&mut self, mut occurs_trigger: impl FnMut()) { - let mut tabu_list = IndexSet::with_hasher(FxBuildHasher::default()); - - // self.fail = false; - - while !(self.pdl.is_empty() || self.fail) { - let s1 = self.pdl.pop().unwrap(); - let s1 = self.deref(s1); - - let s2 = self.pdl.pop().unwrap(); - let s2 = self.deref(s2); - - if s1 != s2 { - let d1 = self.store(s1); - let d2 = self.store(s2); - - read_heap_cell!(d1, - (HeapCellValueTag::AttrVar, h) => { - if self.bind_with_occurs_check(Ref::attr_var(h), d2) { - occurs_trigger(); - } - } - (HeapCellValueTag::Var, h) => { - if self.bind_with_occurs_check(Ref::heap_cell(h), d2) { - occurs_trigger(); - } - } - (HeapCellValueTag::StackVar, s) => { - if self.bind_with_occurs_check(Ref::stack_cell(s), d2) { - occurs_trigger(); - } - } - (HeapCellValueTag::Atom, (name, arity)) => { - debug_assert!(arity == 0); - self.unify_atom(name, d2); - } - (HeapCellValueTag::Str, s1) => { - if tabu_list.contains(&(d1, d2)) { - continue; - } - - self.unify_structure_with_occurs_check(s1, d2, &mut occurs_trigger); - - if !self.fail { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::Lis, l1) => { - if d2.is_ref() { - if tabu_list.contains(&(d1, d2)) { - continue; - } - } - - self.unify_list_with_occurs_trigger(l1, d2, &mut occurs_trigger); - - if !self.fail { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::PStrLoc) => { - read_heap_cell!(d2, - (HeapCellValueTag::PStrLoc | - HeapCellValueTag::Lis | - HeapCellValueTag::Str) => { - if tabu_list.contains(&(d1, d2)) { - continue; - } - } - (HeapCellValueTag::CStr | - HeapCellValueTag::AttrVar | - HeapCellValueTag::Var | - HeapCellValueTag::StackVar) => { - } - _ => { - self.fail = true; - break; - } - ); - - self.unify_partial_string_with_occurs_check( - d1, - d2, - &mut occurs_trigger, - ); - - if !self.fail && !d2.is_constant() { - let d2 = self.store(d2); - tabu_list.insert((d1, d2)); - } - } - (HeapCellValueTag::CStr) => { - read_heap_cell!(d2, - (HeapCellValueTag::AttrVar, h) => { - self.bind(Ref::attr_var(h), d1); - continue; - } - (HeapCellValueTag::Var, h) => { - self.bind(Ref::heap_cell(h), d1); - continue; - } - (HeapCellValueTag::StackVar, s) => { - self.bind(Ref::stack_cell(s), d1); - continue; - } - (HeapCellValueTag::Str | - HeapCellValueTag::Lis | - HeapCellValueTag::PStrLoc) => { - } - _ => { - self.fail = true; - return; - } - ); - - self.unify_partial_string(d2, d1); - } - (HeapCellValueTag::F64, f1) => { - self.unify_f64(f1, d2); - } - (HeapCellValueTag::Fixnum, n1) => { - self.unify_fixnum(n1, d2); - } - (HeapCellValueTag::Char, c1) => { - self.unify_char(c1, d2); - } - (HeapCellValueTag::Cons, ptr_1) => { - self.unify_constant(ptr_1, d2); - } - _ => { - unreachable!(); - } - ); - } - } - } - pub(crate) fn read_s(&mut self) -> HeapCellValue { match &mut self.s { &mut HeapPtr::HeapCell(h) => self.deref(self.heap[h + self.s_offset]), diff --git a/src/machine/mod.rs b/src/machine/mod.rs index cad80661..21fc3e54 100644 --- a/src/machine/mod.rs +++ b/src/machine/mod.rs @@ -21,6 +21,7 @@ pub mod stack; pub mod streams; pub mod system_calls; pub mod term_stream; +pub mod unify; use crate::arena::*; use crate::arithmetic::*; diff --git a/src/machine/system_calls.rs b/src/machine/system_calls.rs index e39f3d22..e9ce7731 100644 --- a/src/machine/system_calls.rs +++ b/src/machine/system_calls.rs @@ -7213,4 +7213,3 @@ impl hkdf::KeyType for MyKey { self.0 } } - diff --git a/src/machine/unify.rs b/src/machine/unify.rs new file mode 100644 index 00000000..19445fe4 --- /dev/null +++ b/src/machine/unify.rs @@ -0,0 +1,763 @@ +use crate::arena::*; +use crate::forms::*; +use crate::heap_iter::stackful_preorder_iter; +use crate::machine::*; +use crate::machine::machine_state::*; +use crate::machine::partial_string::*; +use crate::types::*; + +use std::cmp::Ordering; +use std::ops::{Deref, DerefMut}; + +use derive_deref::*; +use fxhash::FxBuildHasher; +use indexmap::IndexSet; + +pub(crate) trait Unifier: DerefMut { + fn unify_structure(&mut self, s1: usize, value: HeapCellValue) { + // s1 is the value of a STR cell. + let (n1, a1) = cell_as_atom_cell!(self.heap[s1]).get_name_and_arity(); + + read_heap_cell!(value, + (HeapCellValueTag::Str, s2) => { + let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) + .get_name_and_arity(); + + if n1 == n2 && a1 == a2 { + for idx in (0..a1).rev() { + self.pdl.push(heap_loc_as_cell!(s2+1+idx)); + self.pdl.push(heap_loc_as_cell!(s1+1+idx)); + } + } else { + self.fail = true; + } + } + (HeapCellValueTag::Lis, l2) => { + if a1 == 2 && n1 == atom!(".") { + for idx in (0..2).rev() { + self.pdl.push(heap_loc_as_cell!(l2+1+idx)); + self.pdl.push(heap_loc_as_cell!(s1+1+idx)); + } + } else { + self.fail = true; + } + } + (HeapCellValueTag::Atom, (n2, a2)) => { + self.fail = !(a1 == 0 && a2 == 0 && n1 == n2); + } + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), str_loc_as_cell!(s1)); + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), str_loc_as_cell!(s1)); + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), str_loc_as_cell!(s1)); + } + _ => { + self.fail = true; + } + ); + } + + fn unify_list(&mut self, l1: usize, value: HeapCellValue) { + read_heap_cell!(value, + (HeapCellValueTag::Lis, l2) => { + for idx in (0..2).rev() { + self.pdl.push(heap_loc_as_cell!(l2 + idx)); + self.pdl.push(heap_loc_as_cell!(l1 + idx)); + } + } + (HeapCellValueTag::Str, s2) => { + let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) + .get_name_and_arity(); + + if a2 == 2 && n2 == atom!(".") { + for idx in (0..2).rev() { + self.pdl.push(heap_loc_as_cell!(s2+1+idx)); + self.pdl.push(heap_loc_as_cell!(l1+idx)); + } + } else { + self.fail = true; + } + } + (HeapCellValueTag::PStrLoc | HeapCellValueTag::CStr | HeapCellValueTag::PStr) => { + Self::unify_partial_string(self, list_loc_as_cell!(l1), value) + } + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), list_loc_as_cell!(l1)); + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), list_loc_as_cell!(l1)); + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), list_loc_as_cell!(l1)); + } + _ => { + self.fail = true; + } + ); + } + + fn unify_complete_string(&mut self, atom: Atom, value: HeapCellValue) { + if let Some(r) = value.as_var() { + if atom == atom!("") { + Self::bind(self, r, atom_as_cell!(atom!("[]"))); + } else { + Self::bind(self, r, atom_as_cstr_cell!(atom)); + } + + return; + } + + read_heap_cell!(value, + (HeapCellValueTag::Atom, (cstr_atom, arity)) if atom == atom!("") => { + debug_assert_eq!(arity, 0); + self.fail = cstr_atom != atom!("[]"); + } + (HeapCellValueTag::Str, s) => { + let (name, arity) = cell_as_atom_cell!(self.heap[s]) + .get_name_and_arity(); + + if arity == 0 { + self.fail = atom == atom!("") && name != atom!("[]"); + } else { + // this is intentionally the same policy for + // value.tag() == Lis and PStrLoc. they're not + // grouped together to allow for arity == 0. + Self::unify_partial_string(self, atom_as_cstr_cell!(atom), value); + + if !self.pdl.is_empty() { + Self::unify_internal(self); + } + } + } + (HeapCellValueTag::CStr, cstr_atom) => { + self.fail = atom != cstr_atom; + } + (HeapCellValueTag::Lis | HeapCellValueTag::PStrLoc) => { + Self::unify_partial_string(self, atom_as_cstr_cell!(atom), value); + + if !self.pdl.is_empty() { + Self::unify_internal(self); + } + } + _ => { + self.fail = true; + } + ); + } + + // the return value of unify_partial_string is interpreted as + // follows: + // + // Some(None) -- the strings are equal, nothing to unify + // Some(Some(f2,f1)) -- prefixes equal, try to unify focus values f2, f1 + // None -- prefixes not equal, unification fails + // + // d1's tag is assumed to be one of LIS, STR or PSTRLOC. + fn unify_partial_string(&mut self, value_1: HeapCellValue, value_2: HeapCellValue) { + if let Some(r) = value_2.as_var() { + Self::bind(self, r, value_1); + return; + } + + let machine_st = self.deref_mut(); + + let s1 = machine_st.heap.len(); + + machine_st.heap.push(value_1); + machine_st.heap.push(value_2); + + let mut pstr_iter1 = HeapPStrIter::new(&machine_st.heap, s1); + let mut pstr_iter2 = HeapPStrIter::new(&machine_st.heap, s1 + 1); + + match compare_pstr_prefixes(&mut pstr_iter1, &mut pstr_iter2) { + PStrCmpResult::Ordered(Ordering::Equal) => {} + PStrCmpResult::Ordered(Ordering::Less) => { + if pstr_iter2.focus.as_var().is_none() { + machine_st.fail = true; + } else { + machine_st.pdl.push(empty_list_as_cell!()); + machine_st.pdl.push(pstr_iter2.focus); + } + } + PStrCmpResult::Ordered(Ordering::Greater) => { + if pstr_iter1.focus.as_var().is_none() { + machine_st.fail = true; + } else { + machine_st.pdl.push(empty_list_as_cell!()); + machine_st.pdl.push(pstr_iter1.focus); + } + } + continuable @ PStrCmpResult::FirstIterContinuable(iteratee) | + continuable @ PStrCmpResult::SecondIterContinuable(iteratee) => { + if continuable.is_second_iter() { + std::mem::swap(&mut pstr_iter1, &mut pstr_iter2); + } + + let mut chars_iter = PStrCharsIter { + iter: pstr_iter1, + item: Some(iteratee), + }; + + let mut focus = pstr_iter2.focus; + + 'outer: loop { + while let Some(c) = chars_iter.peek() { + read_heap_cell!(focus, + (HeapCellValueTag::Lis, l) => { + let val = pstr_iter2.heap[l]; + + machine_st.pdl.push(val); + machine_st.pdl.push(char_as_cell!(c)); + + focus = pstr_iter2.heap[l+1]; + } + (HeapCellValueTag::Str, s) => { + let (name, arity) = cell_as_atom_cell!(pstr_iter2.heap[s]) + .get_name_and_arity(); + + if name == atom!(".") && arity == 2 { + machine_st.pdl.push(pstr_iter2.heap[s+1]); + machine_st.pdl.push(char_as_cell!(c)); + + focus = pstr_iter2.heap[s+2]; + } else { + machine_st.fail = true; + break 'outer; + } + } + (HeapCellValueTag::AttrVar | HeapCellValueTag::Var, h) => { + match chars_iter.item.unwrap() { + PStrIteratee::Char(focus, _) => { + machine_st.pdl.push(machine_st.heap[focus]); + machine_st.pdl.push(heap_loc_as_cell!(h)); + } + PStrIteratee::PStrSegment(focus, _, n) => { + read_heap_cell!(machine_st.heap[focus], + (HeapCellValueTag::CStr | HeapCellValueTag::PStr, pstr_atom) => { + if focus < machine_st.heap.len() - 2 { + machine_st.heap.pop(); + machine_st.heap.pop(); + } + + if n == 0 { + let target_cell = match machine_st.heap[focus].get_tag() { + HeapCellValueTag::CStr => { + atom_as_cstr_cell!(pstr_atom) + } + HeapCellValueTag::PStr => { + pstr_loc_as_cell!(focus) + } + _ => { + unreachable!() + } + }; + + machine_st.pdl.push(target_cell); + machine_st.pdl.push(heap_loc_as_cell!(h)); + } else { + let h_len = machine_st.heap.len(); + + machine_st.heap.push(pstr_offset_as_cell!(focus)); + machine_st.heap.push(fixnum_as_cell!( + Fixnum::build_with(n as i64) + )); + + machine_st.pdl.push(pstr_loc_as_cell!(h_len)); + machine_st.pdl.push(heap_loc_as_cell!(h)); + } + + return; + } + (HeapCellValueTag::PStrOffset, pstr_loc) => { + let n0 = cell_as_fixnum!(machine_st.heap[focus+1]) + .get_num() as usize; + + if pstr_loc < machine_st.heap.len() - 2 { + machine_st.heap.pop(); + machine_st.heap.pop(); + } + + if n == n0 { + machine_st.pdl.push(pstr_loc_as_cell!(focus)); + machine_st.pdl.push(heap_loc_as_cell!(h)); + } else { + let h_len = machine_st.heap.len(); + + machine_st.heap.push(pstr_offset_as_cell!(pstr_loc)); + machine_st.heap.push(fixnum_as_cell!( + Fixnum::build_with(n as i64) + )); + + machine_st.pdl.push(pstr_loc_as_cell!(h_len)); + machine_st.pdl.push(heap_loc_as_cell!(h)); + } + + return; + } + _ => { + } + ); + + if focus < machine_st.heap.len() - 2 { + machine_st.heap.pop(); + machine_st.heap.pop(); + } + + machine_st.pdl.push(machine_st.heap[focus]); + machine_st.pdl.push(heap_loc_as_cell!(h)); + + return; + } + } + + break 'outer; + } + _ => { + machine_st.fail = true; + break 'outer; + } + ); + + chars_iter.next(); + } + + chars_iter.iter.next(); + + machine_st.pdl.push(focus); + machine_st.pdl.push(chars_iter.iter.focus); + + break; + } + } + PStrCmpResult::Unordered => { + machine_st.pdl.push(pstr_iter1.focus); + machine_st.pdl.push(pstr_iter2.focus); + } + } + + machine_st.heap.pop(); + machine_st.heap.pop(); + } + + fn unify_atom(&mut self, atom: Atom, value: HeapCellValue) { + read_heap_cell!(value, + (HeapCellValueTag::Atom, (name, arity)) => { + self.fail = !(arity == 0 && name == atom); + } + (HeapCellValueTag::Str, s) => { + let (name, arity) = cell_as_atom_cell!(self.heap[s]) + .get_name_and_arity(); + + self.fail = !(arity == 0 && name == atom); + } + (HeapCellValueTag::CStr, cstr_atom) if atom == atom!("[]") => { + self.fail = cstr_atom != atom!(""); + } + (HeapCellValueTag::Char, c1) => { + if let Some(c2) = atom.as_char() { + self.fail = c1 != c2; + } else { + self.fail = true; + } + } + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), atom_as_cell!(atom)); + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), atom_as_cell!(atom)); + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), atom_as_cell!(atom)); + } + _ => { + self.fail = true; + } + ); + } + + fn unify_char(&mut self, c: char, value: HeapCellValue) { + read_heap_cell!(value, + (HeapCellValueTag::Atom, (name, arity)) => { + if let Some(c2) = name.as_char() { + self.fail = !(c == c2 && arity == 0); + } else { + self.fail = true; + } + } + (HeapCellValueTag::Str, s) => { + let (name, arity) = cell_as_atom_cell!(self.heap[s]) + .get_name_and_arity(); + + if let Some(c2) = name.as_char() { + self.fail = !(c == c2 && arity == 0); + } else { + self.fail = true; + } + } + (HeapCellValueTag::Char, c2) => { + if c != c2 { + self.fail = true; + } + } + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), char_as_cell!(c)); + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), char_as_cell!(c)); + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), char_as_cell!(c)); + } + _ => { + self.fail = true; + } + ); + } + + fn unify_fixnum(&mut self, n1: Fixnum, value: HeapCellValue) { + if let Some(r) = value.as_var() { + Self::bind(self, r, fixnum_as_cell!(n1)); + return; + } + + match Number::try_from(value) { + Ok(n2) => match n2 { + Number::Fixnum(n2) if n1.get_num() == n2.get_num() => {} + Number::Integer(n2) if n1.get_num() == *n2 => {} + Number::Rational(n2) if n1.get_num() == *n2 => {} + _ => { + self.fail = true; + } + }, + Err(_) => { + self.fail = true; + } + } + } + + fn unify_big_num(&mut self, n1: TypedArenaPtr, value: HeapCellValue) + where N: PartialEq + + PartialEq + + PartialEq + + ArenaAllocated + { + if let Some(r) = value.as_var() { + Self::bind(self, r, typed_arena_ptr_as_cell!(n1)); + return; + } + + match Number::try_from(value) { + Ok(n2) => match n2 { + Number::Fixnum(n2) if *n1 == n2.get_num() => {} + Number::Integer(n2) if *n1 == *n2 => {} + Number::Rational(n2) if *n1 == *n2 => {} + _ => { + self.fail = true; + } + }, + Err(_) => { + self.fail = true; + } + } + } + + fn unify_f64(&mut self, f1: F64Ptr, value: HeapCellValue) { + if let Some(r) = value.as_var() { + Self::bind(self, r, HeapCellValue::from(f1)); + return; + } + + read_heap_cell!(value, + (HeapCellValueTag::F64, f2) => { + self.fail = **f1 != **f2; + } + _ => { + self.fail = true; + } + ); + } + + fn unify_constant(&mut self, ptr: UntypedArenaPtr, value: HeapCellValue) { + if let Some(ptr2) = value.to_untyped_arena_ptr() { + if ptr.get_ptr() == ptr2.get_ptr() { + return; + } + } + + match_untyped_arena_ptr!(ptr, + (ArenaHeaderTag::Integer, int_ptr) => { + Self::unify_big_num(self, int_ptr, value); + } + (ArenaHeaderTag::Rational, rat_ptr) => { + Self::unify_big_num(self, rat_ptr, value); + } + _ => { + if let Some(r) = value.as_var() { + Self::bind(self, r, untyped_arena_ptr_as_cell!(ptr)); + } else { + self.fail = true; + } + } + ); + } + + fn unify_internal(&mut self) { + let mut tabu_list = IndexSet::with_hasher(FxBuildHasher::default()); + + while !(self.pdl.is_empty() || self.fail) { + let s1 = self.pdl.pop().unwrap(); + let s1 = (self.deref() as &MachineState).deref(s1); + + let s2 = self.pdl.pop().unwrap(); + let s2 = (self.deref() as &MachineState).deref(s2); + + if s1 != s2 { + let d1 = self.store(s1); + let d2 = self.store(s2); + + read_heap_cell!(d1, + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), d2); + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), d2); + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), d2); + } + (HeapCellValueTag::Atom, (name, arity)) => { + debug_assert_eq!(arity, 0); + Self::unify_atom(self, name, d2); + } + (HeapCellValueTag::Str, s1) => { + if tabu_list.contains(&(d1, d2)) { + continue; + } + + Self::unify_structure(self, s1, d2); + + if !self.fail { + let d2 = self.store(d2); + tabu_list.insert((d1, d2)); + } + } + (HeapCellValueTag::Lis, l1) => { + if d2.is_ref() { + if tabu_list.contains(&(d1, d2)) { + continue; + } + } + + Self::unify_list(self, l1, d2); + + if !self.fail { + let d2 = self.store(d2); + tabu_list.insert((d1, d2)); + } + } + (HeapCellValueTag::PStrLoc) => { + read_heap_cell!(d2, + (HeapCellValueTag::PStrLoc | + HeapCellValueTag::Lis | + HeapCellValueTag::Str) => { + if tabu_list.contains(&(d1, d2)) { + continue; + } + } + (HeapCellValueTag::CStr | + HeapCellValueTag::AttrVar | + HeapCellValueTag::Var | + HeapCellValueTag::StackVar) => { + } + _ => { + self.fail = true; + break; + } + ); + + Self::unify_partial_string(self, d1, d2); + + if !self.fail && !d2.is_constant() { + let d2 = self.store(d2); + tabu_list.insert((d1, d2)); + } + } + (HeapCellValueTag::CStr) => { + read_heap_cell!(d2, + (HeapCellValueTag::AttrVar, h) => { + Self::bind(self, Ref::attr_var(h), d1); + continue; + } + (HeapCellValueTag::Var, h) => { + Self::bind(self, Ref::heap_cell(h), d1); + continue; + } + (HeapCellValueTag::StackVar, s) => { + Self::bind(self, Ref::stack_cell(s), d1); + continue; + } + (HeapCellValueTag::Str | + HeapCellValueTag::Lis | + HeapCellValueTag::PStrLoc) => { + } + (HeapCellValueTag::CStr) => { + self.fail = d1 != d2; + continue; + } + _ => { + self.fail = true; + return; + } + ); + + Self::unify_partial_string(self, d2, d1); + } + (HeapCellValueTag::F64, f1) => { + Self::unify_f64(self, f1, d2); + } + (HeapCellValueTag::Fixnum, n1) => { + Self::unify_fixnum(self, n1, d2); + } + (HeapCellValueTag::Char, c1) => { + Self::unify_char(self, c1, d2); + } + (HeapCellValueTag::Cons, ptr_1) => { + Self::unify_constant(self, ptr_1, d2); + } + _ => { + unreachable!(); + } + ); + } + } + } + + fn bind(&mut self, r: Ref, value: HeapCellValue); +} + +#[inline] +fn bind_with_occurs_check(unifier: &mut U, r: Ref, value: HeapCellValue) -> bool { + if let RefTag::StackCell = r.get_tag() { + // local variable optimization -- r cannot occur in the + // heap structure bound to value, so don't bother + // traversing value. + U::bind(unifier, r, value); + return false; + } + + let mut occurs_triggered = false; + + if !value.is_constant() { + for addr in stackful_preorder_iter(&mut unifier.heap, value) { + let addr = unmark_cell_bits!(addr); + + if let Some(inner_r) = addr.as_var() { + if r == inner_r { + occurs_triggered = true; + break; + } + } + } + } + + if occurs_triggered { + unifier.fail = true; + } else { + U::bind(unifier, r, value); + } + + return occurs_triggered; +} + +#[derive(Deref, DerefMut)] +pub(crate) struct DefaultUnifier<'a> { + machine_st: &'a mut MachineState, +} + +impl<'a> From<&'a mut MachineState> for DefaultUnifier<'a> { + #[inline(always)] + fn from(machine_st: &'a mut MachineState) -> Self { + Self { machine_st } + } +} + +impl<'a> Unifier for DefaultUnifier<'a> { + fn bind(&mut self, r: Ref, value: HeapCellValue) { + self.machine_st.bind(r, value); + } +} + +pub(crate) struct CompositeUnifierForOccursCheck { + unifier: U, +} + +impl Deref for CompositeUnifierForOccursCheck { + type Target = MachineState; + + #[inline(always)] + fn deref(&self) -> &Self::Target { + self.unifier.deref() + } +} + +impl DerefMut for CompositeUnifierForOccursCheck { + #[inline(always)] + fn deref_mut(&mut self) -> &mut Self::Target { + self.unifier.deref_mut() + } +} + +impl From for CompositeUnifierForOccursCheck { + #[inline(always)] + fn from(unifier: U) -> Self { + Self { unifier } + } +} + +impl Unifier for CompositeUnifierForOccursCheck { + fn bind(&mut self, r: Ref, value: HeapCellValue) { + bind_with_occurs_check(&mut self.unifier, r, value); + } +} + +pub(crate) struct CompositeUnifierForOccursCheckWithError { + unifier: U, +} + +impl Deref for CompositeUnifierForOccursCheckWithError { + type Target = MachineState; + + #[inline(always)] + fn deref(&self) -> &Self::Target { + self.unifier.deref() + } +} + +impl DerefMut for CompositeUnifierForOccursCheckWithError { + #[inline(always)] + fn deref_mut(&mut self) -> &mut Self::Target { + self.unifier.deref_mut() + } +} + +impl From for CompositeUnifierForOccursCheckWithError { + #[inline(always)] + fn from(unifier: U) -> Self { + Self { unifier } + } +} + +impl Unifier for CompositeUnifierForOccursCheckWithError { + fn bind(&mut self, r: Ref, value: HeapCellValue) { + if bind_with_occurs_check(&mut self.unifier, r, value) { + let err = self.representation_error(RepFlag::Term); + let stub = functor_stub(atom!("unify_with_occurs_check"), 2); + let err = self.error_form(err, stub); + + self.throw_exception(err); + } + } +} -- 2.54.0