From 29cd80510ba8b81905c634348995d1c1ed665d3a Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Thu, 11 Dec 2025 22:08:16 -0800 Subject: [PATCH] replace compare_term_test with parallel iterator, add is_not_variant --- build/instructions_template.rs | 7 +- src/forms.rs | 10 +- src/heap_iter.rs | 357 +++++++++++++++++++++++++++ src/instructions.rs | 2 - src/machine/attributed_variables.rs | 5 +- src/machine/dispatch.rs | 103 +++----- src/machine/machine_state_impl.rs | 364 ++-------------------------- src/machine/mock_wam.rs | 51 ++-- src/machine/system_calls.rs | 49 +++- src/macros.rs | 15 -- 10 files changed, 488 insertions(+), 475 deletions(-) diff --git a/build/instructions_template.rs b/build/instructions_template.rs index 16f37bcb..8971f505 100644 --- a/build/instructions_template.rs +++ b/build/instructions_template.rs @@ -643,15 +643,12 @@ enum SystemClauseType { UnattributedVar, #[strum_discriminants(strum(props(Arity = "4", Name = "$get_db_refs")))] GetDBRefs, - #[strum_discriminants(strum(props( - Arity = "2", - Name = "$keysort_with_constant_var_ordering" - )))] - KeySortWithConstantVarOrdering, #[strum_discriminants(strum(props(Arity = "0", Name = "$inference_limit_exceeded")))] InferenceLimitExceeded, #[strum_discriminants(strum(props(Arity = "1", Name = "$argv")))] Argv, + #[strum_discriminants(strum(props(Arity = "2", Name = "$variant")))] + IsVariant, Repl(ReplCodePtr), } diff --git a/src/forms.rs b/src/forms.rs index 447328f7..d6cc39d4 100644 --- a/src/forms.rs +++ b/src/forms.rs @@ -170,13 +170,9 @@ impl PartialOrd for BranchNumber { impl BranchNumber { pub(crate) fn has_as_subbranch(&self, other: &Self) -> bool { - let delta_ratio = &self.delta / &other.delta; - - if !delta_ratio.denominator().is_one() { - return false; - } - - other.branch_num >= self.branch_num && other.branch_num < &self.branch_num + &self.delta + other.delta <= self.delta && + other.branch_num >= self.branch_num && + other.branch_num < &self.branch_num + &self.delta } pub(crate) fn split(&self) -> BranchNumber { diff --git a/src/heap_iter.rs b/src/heap_iter.rs index 70314082..05b91293 100644 --- a/src/heap_iter.rs +++ b/src/heap_iter.rs @@ -1,21 +1,378 @@ #![allow(clippy::new_without_default)] // annotating structs annotated with #[bitfield] doesn't work #![allow(unused_parens)] // see mthom/scryer-prolog#3092 and rust-lang/rust#147126 +use crate::arena::Arena; +use crate::forms::Number; #[cfg(test)] pub(crate) use crate::machine::gc::StacklessPreOrderHeapIter; use crate::atom_table::*; use crate::machine::cycle_detection::*; use crate::machine::heap::*; +use crate::machine::machine_indices::TermOrderCategory; use crate::machine::stack::*; +use crate::parser::lexer::MachineState; use crate::types::*; use core::marker::PhantomData; +use fxhash::FxBuildHasher; +use indexmap::IndexSet; use scryer_modular_bitfield::prelude::*; +use std::cmp::Ordering; use std::ops::Deref; use std::vec::Vec; +// iterate through the subterms of a pair of terms +// for as long as they structurally agree, reporting +// the earliest (pre-order) difference before returning +// None's and pairs of variables as the Iterator Item. + +pub struct ParallelHeapIter<'a> { + stack: Vec, + heap: &'a Heap, + arena: &'a Arena, + tabu_list: IndexSet<(usize, usize), FxBuildHasher>, +} + +impl<'a> ParallelHeapIter<'a> { + pub fn from(machine_st: &'a MachineState, h1: HeapCellValue, h2: HeapCellValue) -> Self { + Self { + stack: vec![h2, h1], + heap: &machine_st.heap, + arena: &machine_st.arena, + tabu_list: IndexSet::with_hasher(FxBuildHasher::new()), + } + } +} + +#[derive(Debug)] +pub enum TermPair { + Vars(usize, usize), + Less(HeapCellValue, HeapCellValue), + Greater(HeapCellValue, HeapCellValue), + Unordered(HeapCellValue, HeapCellValue), +} + +impl ParallelHeapIter<'_> { + #[inline] + fn parallel_cmp( + &mut self, + v1: Cmp, + v2: Cmp, + h1: HeapCellValue, + h2: HeapCellValue, + ) -> Option { + match v1.cmp(&v2) { + Ordering::Greater => { + self.stack.clear(); + Some(TermPair::Greater(h1, h2)) + } + Ordering::Less => { + self.stack.clear(); + Some(TermPair::Less(h1, h2)) + } + Ordering::Equal => None, + } + } +} + +macro_rules! some_or_return { + ($e:expr) => { + if let Some(x) = $e { + return Some(x); + } + }; +} + +impl Iterator for ParallelHeapIter<'_> { + type Item = TermPair; + + fn next(&mut self) -> Option { + use crate::offset_table::F64Offset; + + while let Some(s1) = self.stack.pop() { + let s1 = heap_bound_deref(self.heap, s1); + + let s2 = self.stack.pop().unwrap(); + let s2 = heap_bound_deref(self.heap, s2); + + if s1 == s2 { + continue; + } + + let v1 = heap_bound_store(self.heap, s1); + let v2 = heap_bound_store(self.heap, s2); + + let order_cat_v1 = v1.order_category(self.heap); + let order_cat_v2 = v2.order_category(self.heap); + + some_or_return!(self.parallel_cmp(order_cat_v1, order_cat_v2, v1, v2)); + + match order_cat_v1 { + Some(TermOrderCategory::Variable) => { + let v1 = v1.get_value() as usize; + let v2 = v2.get_value() as usize; + + return Some(TermPair::Vars(v1, v2)); + } + Some(TermOrderCategory::FloatingPoint) => { + let v1_offset = cell_as_f64_offset!(v1); + let v2_offset = cell_as_f64_offset!(v2); + + let v1_f64 = self.arena.f64_tbl.get_entry(v1_offset); + let v2_f64 = self.arena.f64_tbl.get_entry(v2_offset); + + some_or_return!(self.parallel_cmp(v1_f64, v2_f64, v1, v2)); + } + Some(TermOrderCategory::Integer) => { + let v1_int = Number::try_from((v1, &self.arena.f64_tbl)).unwrap(); + let v2_int = Number::try_from((v2, &self.arena.f64_tbl)).unwrap(); + + some_or_return!(self.parallel_cmp(v1_int, v2_int, v1, v2)); + } + Some(TermOrderCategory::Atom) => { + read_heap_cell!(v1, + (HeapCellValueTag::Atom, (n1, _a1)) => { + read_heap_cell!(v2, + (HeapCellValueTag::Atom, (n2, _a2)) => { + some_or_return!(self.parallel_cmp(n1, n2, v1, v2)); + } + (HeapCellValueTag::Str, s) => { + let n2 = cell_as_atom_cell!(self.heap[s]) + .get_name(); + + some_or_return!(self.parallel_cmp(n1, n2, v1, v2)); + } + _ => { + unreachable!(); + } + ) + } + (HeapCellValueTag::Str, s) => { + let n1 = cell_as_atom_cell!(self.heap[s]) + .get_name(); + + read_heap_cell!(v2, + (HeapCellValueTag::Atom, (n2, _a2)) => { + some_or_return!(self.parallel_cmp(n1, n2, v1, v2)); + } + (HeapCellValueTag::Str, s) => { + let n2 = cell_as_atom_cell!(self.heap[s]) + .get_name(); + + some_or_return!(self.parallel_cmp(n1, n2, v1, v2)); + } + _ => { + unreachable!(); + } + ) + } + _ => { + unreachable!() + } + ) + } + Some(TermOrderCategory::Compound) => { + read_heap_cell!(v1, + (HeapCellValueTag::Lis, l1) => { + read_heap_cell!(v2, + (HeapCellValueTag::PStrLoc, l2) => { + if self.tabu_list.contains(&(l1, l2)) { + continue; + } + + self.tabu_list.insert((l1, l2)); + + // like the action of partial_string_to_stack here but the + // ordering of stack pushes is (crucially for comparison + // correctness) different. + let (c, succ_cell) = self.heap.last_str_char_and_tail(l2); + + self.stack.push(succ_cell); + self.stack.push(heap_loc_as_cell!(l1 + 1)); + + self.stack.push(char_as_cell!(c)); + self.stack.push(heap_loc_as_cell!(l1)); + } + (HeapCellValueTag::Lis, l2) => { + if self.tabu_list.contains(&(l1, l2)) { + continue; + } + + self.tabu_list.insert((l1, l2)); + + self.stack.push(self.heap[l2 + 1]); + self.stack.push(self.heap[l1 + 1]); + + self.stack.push(self.heap[l2]); + self.stack.push(self.heap[l1]); + } + (HeapCellValueTag::Str, s2) => { + if self.tabu_list.contains(&(l1, s2)) { + continue; + } + + let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) + .get_name_and_arity(); + + some_or_return!(self.parallel_cmp((2, atom!(".")), (a2, n2), v1, v2)); + + self.tabu_list.insert((l1, s2)); + + self.stack.push(self.heap[s2 + 2]); + self.stack.push(self.heap[l1 + 1]); + + self.stack.push(self.heap[s2 + 1]); + self.stack.push(self.heap[l1]); + } + _ => { + unreachable!(); + } + ) + } + (HeapCellValueTag::PStrLoc, l1) => { + read_heap_cell!(v2, + (HeapCellValueTag::PStrLoc, l2) => { + if self.tabu_list.contains(&(l1, l2)) { + continue; + } + + match self.heap.compare_pstr_segments(l1, l2) { + PStrSegmentCmpResult::Continue(v1, v2) => { + self.tabu_list.insert((l1, l2)); + + self.stack.push(v1.offset_by(l1)); + self.stack.push(v2.offset_by(l2)); + } + PStrSegmentCmpResult::Less => { + self.stack.clear(); + return Some(TermPair::Less(v1, v2)); + } + PStrSegmentCmpResult::Greater => { + self.stack.clear(); + return Some(TermPair::Greater(v1, v2)); + } + } + } + (HeapCellValueTag::Lis, l2) => { + if self.tabu_list.contains(&(l1, l2)) { + continue; + } + + self.tabu_list.insert((l1, l2)); + + let (c, succ_cell) = self.heap.last_str_char_and_tail(l1); + + self.stack.push(succ_cell); + self.stack.push(heap_loc_as_cell!(l2 + 1)); + + self.stack.push(char_as_cell!(c)); + self.stack.push(heap_loc_as_cell!(l2)); + } + (HeapCellValueTag::Str, s2) => { + if self.tabu_list.contains(&(l1, s2)) { + continue; + } + + self.tabu_list.insert((l1, s2)); + + let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) + .get_name_and_arity(); + + some_or_return!(self.parallel_cmp((2, atom!(".")), (a2, n2), v1, v2)); + + let (c, succ_cell) = self.heap.last_str_char_and_tail(l1); + + self.stack.push(heap_loc_as_cell!(s2+2)); + self.stack.push(succ_cell); + + self.stack.push(heap_loc_as_cell!(s2+1)); + self.stack.push(char_as_cell!(c)); + } + _ => { + unreachable!() + } + ); + } + (HeapCellValueTag::Str, s1) => { + read_heap_cell!(v2, + (HeapCellValueTag::Str, s2) => { + if self.tabu_list.contains(&(s1, s2)) { + continue; + } + + let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) + .get_name_and_arity(); + + let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) + .get_name_and_arity(); + + some_or_return!(self.parallel_cmp((a1, n1), (a2, n2), v1, v2)); + + self.tabu_list.insert((s1, s2)); + + for idx in (1 .. a1+1).rev() { + self.stack.push(self.heap[s2+idx]); + self.stack.push(self.heap[s1+idx]); + } + } + (HeapCellValueTag::Lis, l2) => { + if self.tabu_list.contains(&(s1, l2)) { + continue; + } + + let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) + .get_name_and_arity(); + + some_or_return!(self.parallel_cmp((a1, n1), (2, atom!(".")), v1, v2)); + + self.stack.push(self.heap[l2]); + self.stack.push(self.heap[s1+1]); + + self.stack.push(self.heap[l2+1]); + self.stack.push(self.heap[s1+2]); + } + (HeapCellValueTag::PStrLoc, l2) => { + if self.tabu_list.contains(&(s1, l2)) { + continue; + } + + let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) + .get_name_and_arity(); + + some_or_return!(self.parallel_cmp((a1, n1), (2, atom!(".")), v1, v2)); + + self.tabu_list.insert((s1, l2)); + + let (c, succ_cell) = self.heap.last_str_char_and_tail(l2); + + self.stack.push(succ_cell); + self.stack.push(heap_loc_as_cell!(s1+2)); + + self.stack.push(char_as_cell!(c)); + self.stack.push(heap_loc_as_cell!(s1+1)); + } + _ => { + unreachable!() + } + ) + } + _ => { + unreachable!() + } + ); + } + None => { + return Some(TermPair::Unordered(v1, v2)); + } + } + } + + None + } +} + #[inline(always)] pub fn eager_stackful_preorder_iter( heap: &mut Heap, diff --git a/src/instructions.rs b/src/instructions.rs index 076c2672..f029e463 100644 --- a/src/instructions.rs +++ b/src/instructions.rs @@ -726,7 +726,6 @@ impl Instruction { | &Instruction::CallDeleteAllAttributesFromVar | &Instruction::CallUnattributedVar | &Instruction::CallGetDBRefs - | &Instruction::CallKeySortWithConstantVarOrdering | &Instruction::CallInferenceLimitExceeded | &Instruction::CallFetchGlobalVar | &Instruction::CallFirstStream @@ -986,7 +985,6 @@ impl Instruction { | &Instruction::ExecuteDeleteAllAttributesFromVar | &Instruction::ExecuteUnattributedVar | &Instruction::ExecuteGetDBRefs - | &Instruction::ExecuteKeySortWithConstantVarOrdering | &Instruction::ExecuteInferenceLimitExceeded | &Instruction::ExecuteFetchGlobalVar | &Instruction::ExecuteFirstStream diff --git a/src/machine/attributed_variables.rs b/src/machine/attributed_variables.rs index fdedabcc..6b822b95 100644 --- a/src/machine/attributed_variables.rs +++ b/src/machine/attributed_variables.rs @@ -103,9 +103,8 @@ impl MachineState { .collect() }; - attr_vars.sort_unstable_by(|a1, a2| { - compare_term_test!(self, *a1, *a2).unwrap_or(Ordering::Less) - }); + attr_vars + .sort_unstable_by(|a1, a2| self.compare_term_test(*a1, *a2).unwrap_or(Ordering::Less)); attr_vars.dedup(); attr_vars diff --git a/src/machine/dispatch.rs b/src/machine/dispatch.rs index f67b0df2..d68f8efe 100644 --- a/src/machine/dispatch.rs +++ b/src/machine/dispatch.rs @@ -118,7 +118,7 @@ impl MachineState { } ); - let atom = match compare_term_test!(self, a2, a3) { + let atom = match self.compare_term_test(a2, a3) { Some(Ordering::Greater) => { atom!(">") } @@ -151,11 +151,8 @@ impl MachineState { let stub_gen = || functor_stub(atom!("sort"), 2); let mut list = self.try_from_list(self.registers[1], stub_gen)?; - list.sort_unstable_by(|v1, v2| { - compare_term_test!(self, *v1, *v2).unwrap_or(Ordering::Less) - }); - - list.dedup_by(|v1, v2| compare_term_test!(self, *v1, *v2) == Some(Ordering::Equal)); + list.sort_unstable_by(|v1, v2| self.compare_term_test(*v1, *v2).unwrap_or(Ordering::Less)); + list.dedup_by(|v1, v2| self.compare_term_test(*v1, *v2) == Some(Ordering::Equal)); let heap_addr = resource_error_call_result!( self, @@ -167,7 +164,7 @@ impl MachineState { Ok(()) } - fn keysort(&mut self, var_comparison: VarComparison) -> CallResult { + fn keysort(&mut self) -> CallResult { self.check_keysort_errors()?; let stub_gen = || functor_stub(atom!("keysort"), 2); @@ -180,9 +177,7 @@ impl MachineState { key_pairs.push((key, val)); } - key_pairs.sort_by(|a1, a2| { - compare_term_test!(self, a1.0, a2.0, var_comparison).unwrap_or(Ordering::Less) - }); + key_pairs.sort_by(|a1, a2| self.compare_term_test(a1.0, a2.0).unwrap_or(Ordering::Less)); let heap_addr = resource_error_call_result!( self, @@ -2034,8 +2029,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Greater) = compare_term_test!(self.machine_st, a1, a2) - { + if let Some(Ordering::Greater) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.p += 1; } else { self.machine_st.backtrack(); @@ -2045,8 +2039,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Greater) = compare_term_test!(self.machine_st, a1, a2) - { + if let Some(Ordering::Greater) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.p = self.machine_st.cp; } else { self.machine_st.backtrack(); @@ -2056,7 +2049,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Less) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Less) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.p += 1; } else { self.machine_st.backtrack(); @@ -2066,7 +2059,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Less) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Less) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.p = self.machine_st.cp; } else { self.machine_st.backtrack(); @@ -2076,7 +2069,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Greater | Ordering::Equal) => { self.machine_st.p += 1; } @@ -2089,7 +2082,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Greater | Ordering::Equal) => { self.machine_st.p = self.machine_st.cp; } @@ -2102,7 +2095,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Less | Ordering::Equal) => { self.machine_st.p += 1; } @@ -2115,7 +2108,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Less | Ordering::Equal) => { self.machine_st.p = self.machine_st.cp; } @@ -2188,7 +2181,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Equal) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Equal) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.backtrack(); } else { self.machine_st.p += 1; @@ -2198,7 +2191,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Equal) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Equal) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.backtrack(); } else { self.machine_st.p = self.machine_st.cp; @@ -2213,19 +2206,11 @@ impl Machine { step_or_fail!(self.machine_st, self.machine_st.p = self.machine_st.cp); } &Instruction::DefaultCallKeySort => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Distinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); step_or_fail!(self.machine_st, self.machine_st.p += 1); } &Instruction::DefaultExecuteKeySort => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Distinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); if self.machine_st.fail { self.machine_st.backtrack(); @@ -2323,8 +2308,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Greater) = compare_term_test!(self.machine_st, a1, a2) - { + if let Some(Ordering::Greater) = self.machine_st.compare_term_test(a1, a2) { increment_call_count!(self.machine_st); self.machine_st.p += 1; } else { @@ -2335,8 +2319,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Greater) = compare_term_test!(self.machine_st, a1, a2) - { + if let Some(Ordering::Greater) = self.machine_st.compare_term_test(a1, a2) { increment_call_count!(self.machine_st); self.machine_st.p = self.machine_st.cp; } else { @@ -2347,7 +2330,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Less) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Less) = self.machine_st.compare_term_test(a1, a2) { increment_call_count!(self.machine_st); self.machine_st.p += 1; } else { @@ -2358,7 +2341,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Less) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Less) = self.machine_st.compare_term_test(a1, a2) { increment_call_count!(self.machine_st); self.machine_st.p = self.machine_st.cp; } else { @@ -2369,7 +2352,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Greater | Ordering::Equal) => { increment_call_count!(self.machine_st); self.machine_st.p += 1; @@ -2383,7 +2366,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Greater | Ordering::Equal) => { increment_call_count!(self.machine_st); self.machine_st.p = self.machine_st.cp; @@ -2397,7 +2380,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Less | Ordering::Equal) => { increment_call_count!(self.machine_st); self.machine_st.p += 1; @@ -2411,7 +2394,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - match compare_term_test!(self.machine_st, a1, a2) { + match self.machine_st.compare_term_test(a1, a2) { Some(Ordering::Less | Ordering::Equal) => { increment_call_count!(self.machine_st); self.machine_st.p = self.machine_st.cp; @@ -2503,7 +2486,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Equal) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Equal) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.backtrack(); } else { increment_call_count!(self.machine_st); @@ -2514,7 +2497,7 @@ impl Machine { let a1 = self.machine_st.registers[1]; let a2 = self.machine_st.registers[2]; - if let Some(Ordering::Equal) = compare_term_test!(self.machine_st, a1, a2) { + if let Some(Ordering::Equal) = self.machine_st.compare_term_test(a1, a2) { self.machine_st.backtrack(); } else { increment_call_count!(self.machine_st); @@ -2542,11 +2525,7 @@ impl Machine { } } &Instruction::CallKeySort => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Distinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); if self.machine_st.fail { self.machine_st.backtrack(); @@ -2556,11 +2535,7 @@ impl Machine { } } &Instruction::ExecuteKeySort => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Distinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); if self.machine_st.fail { self.machine_st.backtrack(); @@ -2570,11 +2545,7 @@ impl Machine { } } &Instruction::CallKeySortWithConstantVarOrdering => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Indistinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); if self.machine_st.fail { self.machine_st.backtrack(); @@ -2584,11 +2555,7 @@ impl Machine { } } &Instruction::ExecuteKeySortWithConstantVarOrdering => { - try_or_throw!( - self.machine_st, - self.machine_st.keysort(VarComparison::Indistinct), - continue - ); + try_or_throw!(self.machine_st, self.machine_st.keysort(), continue); if self.machine_st.fail { self.machine_st.backtrack(); @@ -4813,6 +4780,14 @@ impl Machine { try_or_throw!(self.machine_st, self.argv(), continue); step_or_fail!(self.machine_st, self.machine_st.p = self.machine_st.cp); } + &Instruction::CallIsVariant => { + self.machine_st.fail = self.machine_st.is_not_variant(); + step_or_fail!(self.machine_st, self.machine_st.p += 1); + } + &Instruction::ExecuteIsVariant => { + self.machine_st.fail = self.machine_st.is_not_variant(); + step_or_fail!(self.machine_st, self.machine_st.p = self.machine_st.cp); + } &Instruction::CallCurrentTime => { self.current_time(); step_or_fail!(self.machine_st, self.machine_st.p += 1); diff --git a/src/machine/machine_state_impl.rs b/src/machine/machine_state_impl.rs index 7b777ae6..668a5bc0 100644 --- a/src/machine/machine_state_impl.rs +++ b/src/machine/machine_state_impl.rs @@ -7,7 +7,6 @@ use crate::machine::copier::*; use crate::machine::heap::AllocError; use crate::machine::heap::*; use crate::machine::machine_errors::*; -use crate::machine::machine_indices::*; use crate::machine::machine_state::*; use crate::machine::partial_string::*; use crate::machine::stack::*; @@ -17,8 +16,6 @@ use crate::parser::ast::*; use crate::parser::dashu::{Integer, Rational}; use crate::types::*; -use indexmap::IndexSet; - use std::cmp::Ordering; use std::convert::TryFrom; @@ -380,347 +377,6 @@ impl MachineState { } } - pub fn compare_term_test(&mut self, var_comparison: VarComparison) -> Option { - let mut tabu_list = IndexSet::new(); - - while let Some(s1) = self.pdl.pop() { - let s1 = self.deref(s1); - - let s2 = self.pdl.pop().unwrap(); - let s2 = self.deref(s2); - - if s1 == s2 { - continue; - } - - let v1 = self.store(s1); - let v2 = self.store(s2); - - let order_cat_v1 = v1.order_category(&self.heap); - let order_cat_v2 = v2.order_category(&self.heap); - - if order_cat_v1 != order_cat_v2 { - self.pdl.clear(); - return Some(order_cat_v1.cmp(&order_cat_v2)); - } - - match order_cat_v1 { - Some(TermOrderCategory::Variable) => { - if let VarComparison::Distinct = var_comparison { - let v1 = v1.as_var().unwrap(); - let v2 = v2.as_var().unwrap(); - - if v1 != v2 { - self.pdl.clear(); - return Some(v1.cmp(&v2)); - } - } - } - Some(TermOrderCategory::FloatingPoint) => { - let v1 = cell_as_f64_offset!(v1); - let v2 = cell_as_f64_offset!(v2); - - let v1 = self.arena.f64_tbl.get_entry(v1); - let v2 = self.arena.f64_tbl.get_entry(v2); - - if v1 != v2 { - self.pdl.clear(); - return Some(v1.cmp(&v2)); - } - } - Some(TermOrderCategory::Integer) => { - let v1 = Number::try_from((v1, &self.arena.f64_tbl)).unwrap(); - let v2 = Number::try_from((v2, &self.arena.f64_tbl)).unwrap(); - - if v1 != v2 { - self.pdl.clear(); - return Some(v1.cmp(&v2)); - } - } - Some(TermOrderCategory::Atom) => { - read_heap_cell!(v1, - (HeapCellValueTag::Atom, (n1, _a1)) => { - read_heap_cell!(v2, - (HeapCellValueTag::Atom, (n2, _a2)) => { - if n1 != n2 { - self.pdl.clear(); - return Some(n1.cmp(&n2)); - } - } - (HeapCellValueTag::Str, s) => { - let n2 = cell_as_atom_cell!(self.heap[s]) - .get_name(); - - if n1 != n2 { - self.pdl.clear(); - return Some(n1.cmp(&n2)); - } - } - _ => { - unreachable!(); - } - ) - } - (HeapCellValueTag::Str, s) => { - let n1 = cell_as_atom_cell!(self.heap[s]) - .get_name(); - - read_heap_cell!(v2, - (HeapCellValueTag::Atom, (n2, _a2)) => { - if n1 != n2 { - self.pdl.clear(); - return Some(n1.cmp(&n2)); - } - } - (HeapCellValueTag::Str, s) => { - let n2 = cell_as_atom_cell!(self.heap[s]) - .get_name(); - - if n1 != n2 { - self.pdl.clear(); - return Some(n1.cmp(&n2)); - } - } - _ => { - unreachable!(); - } - ) - } - _ => { - unreachable!() - } - ) - } - Some(TermOrderCategory::Compound) => { - read_heap_cell!(v1, - (HeapCellValueTag::Lis, l1) => { - read_heap_cell!(v2, - (HeapCellValueTag::PStrLoc, l2) => { - if tabu_list.contains(&(l1, l2)) { - continue; - } - - tabu_list.insert((l1, l2)); - - // like the action of - // partial_string_to_pdl here but - // the ordering of PDL pushes is - // (crucially for comparison - // correctness) different. - let (c, succ_cell) = self.heap.last_str_char_and_tail(l2); - - self.pdl.push(succ_cell); - self.pdl.push(heap_loc_as_cell!(l1 + 1)); - - self.pdl.push(char_as_cell!(c)); - self.pdl.push(heap_loc_as_cell!(l1)); - } - (HeapCellValueTag::Lis, l2) => { - if tabu_list.contains(&(l1, l2)) { - continue; - } - - tabu_list.insert((l1, l2)); - - self.pdl.push(self.heap[l2 + 1]); - self.pdl.push(self.heap[l1 + 1]); - - self.pdl.push(self.heap[l2]); - self.pdl.push(self.heap[l1]); - } - (HeapCellValueTag::Str, s2) => { - if tabu_list.contains(&(l1, s2)) { - continue; - } - - let (name, arity) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - match (2, atom!(".")).cmp(&(arity, name)) { - Ordering::Equal => { - tabu_list.insert((l1, s2)); - - self.pdl.push(self.heap[s2 + 2]); - self.pdl.push(self.heap[l1 + 1]); - - self.pdl.push(self.heap[s2 + 1]); - self.pdl.push(self.heap[l1]); - } - ordering => { - self.pdl.clear(); - return Some(ordering); - } - } - } - _ => { - unreachable!(); - } - ) - } - (HeapCellValueTag::PStrLoc, l1) => { - read_heap_cell!(v2, - (HeapCellValueTag::PStrLoc, l2) => { - if tabu_list.contains(&(l1, l2)) { - continue; - } - - tabu_list.insert((l1, l2)); - - match self.heap.compare_pstr_segments(l1, l2) { - PStrSegmentCmpResult::Continue(v1, v2) => { - self.pdl.push(v1.offset_by(l1)); - self.pdl.push(v2.offset_by(l2)); - } - PStrSegmentCmpResult::Less => { - self.pdl.clear(); - return Some(Ordering::Less); - } - PStrSegmentCmpResult::Greater => { - self.pdl.clear(); - return Some(Ordering::Greater); - } - } - } - (HeapCellValueTag::Lis, l2) => { - if tabu_list.contains(&(l1, l2)) { - continue; - } - - tabu_list.insert((l1, l2)); - - let (c, succ_cell) = self.heap.last_str_char_and_tail(l1); - - self.pdl.push(succ_cell); - self.pdl.push(heap_loc_as_cell!(l2 + 1)); - - self.pdl.push(char_as_cell!(c)); - self.pdl.push(heap_loc_as_cell!(l2)); - } - (HeapCellValueTag::Str, s2) => { - if tabu_list.contains(&(l1, s2)) { - continue; - } - - tabu_list.insert((l1, s2)); - - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - match (2, atom!(".")).cmp(&(a2,n2)) { - Ordering::Equal => { - let (c, succ_cell) = self.heap.last_str_char_and_tail(l1); - - self.pdl.push(heap_loc_as_cell!(s2+2)); - self.pdl.push(succ_cell); - - self.pdl.push(heap_loc_as_cell!(s2+1)); - self.pdl.push(char_as_cell!(c)); - } - ordering => { - self.pdl.clear(); - return Some(ordering); - } - } - } - _ => { - unreachable!() - } - ); - } - (HeapCellValueTag::Str, s1) => { - read_heap_cell!(v2, - (HeapCellValueTag::Str, s2) => { - if tabu_list.contains(&(s1, s2)) { - continue; - } - - let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) - .get_name_and_arity(); - - let (n2, a2) = cell_as_atom_cell!(self.heap[s2]) - .get_name_and_arity(); - - match (a1,n1).cmp(&(a2, n2)) { - Ordering::Equal => { - tabu_list.insert((s1, s2)); - - for idx in (1 .. a1+1).rev() { - self.pdl.push(self.heap[s2+idx]); - self.pdl.push(self.heap[s1+idx]); - } - } - ordering => { - self.pdl.clear(); - return Some(ordering); - } - } - } - (HeapCellValueTag::Lis, l2) => { - if tabu_list.contains(&(s1, l2)) { - continue; - } - - tabu_list.insert((s1, l2)); - - let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) - .get_name_and_arity(); - - match (a1,n1).cmp(&(2, atom!("."))) { - Ordering::Equal => { - self.pdl.push(self.heap[l2]); - self.pdl.push(self.heap[s1+1]); - - self.pdl.push(self.heap[l2+1]); - self.pdl.push(self.heap[s1+2]); - } - ordering => { - self.pdl.clear(); - return Some(ordering); - } - } - } - (HeapCellValueTag::PStrLoc, l2) => { - let (n1, a1) = cell_as_atom_cell!(self.heap[s1]) - .get_name_and_arity(); - - match (a1,n1).cmp(&(2, atom!("."))) { - Ordering::Equal => { - let (c, succ_cell) = self.heap.last_str_char_and_tail(l2); - - self.pdl.push(succ_cell); - self.pdl.push(heap_loc_as_cell!(s1+2)); - - self.pdl.push(char_as_cell!(c)); - self.pdl.push(heap_loc_as_cell!(s1+1)); - } - ordering => { - self.pdl.clear(); - return Some(ordering); - } - } - } - _ => { - unreachable!() - } - ) - } - _ => { - unreachable!() - } - ); - } - None => { - if v1 != v2 { - self.pdl.clear(); - return None; - } - } - } - } - - Some(Ordering::Equal) - } - pub(crate) fn setup_call_n_init_goal_info( &mut self, goal: HeapCellValue, @@ -891,16 +547,32 @@ impl MachineState { } // returns true on failure, false on success. - pub fn eq_test(&mut self, h1: HeapCellValue, h2: HeapCellValue) -> bool { + pub fn eq_test(&self, h1: HeapCellValue, h2: HeapCellValue) -> bool { if h1 == h2 { return false; } - compare_term_test!(self, h1, h2) + self.compare_term_test(h1, h2) .map(|o| o != Ordering::Equal) .unwrap_or(true) } + pub fn compare_term_test(&self, h1: HeapCellValue, h2: HeapCellValue) -> Option { + for term_pair in ParallelHeapIter::from(self, h1, h2) { + match term_pair { + TermPair::Vars(v1_offset, v2_offset) if v1_offset != v2_offset => { + return Some(v1_offset.cmp(&v2_offset)); + } + TermPair::Less(..) => return Some(Ordering::Less), + TermPair::Greater(..) => return Some(Ordering::Greater), + TermPair::Unordered(cell_1, cell_2) if cell_1 != cell_2 => return None, + _ => {} + } + } + + Some(Ordering::Equal) + } + #[inline(always)] fn try_functor_compound_case(&mut self, name: Atom, arity: usize) { self.try_functor_unify_components(atom_as_cell!(name), arity); diff --git a/src/machine/mock_wam.rs b/src/machine/mock_wam.rs index 7fcc5613..082ed62c 100644 --- a/src/machine/mock_wam.rs +++ b/src/machine/mock_wam.rs @@ -581,56 +581,44 @@ mod tests { }); assert_eq!( - compare_term_test!(wam, wam.heap[0], wam.heap[1]), + wam.compare_term_test(wam.heap[0], wam.heap[1]), Some(Ordering::Less) ); assert_eq!( - compare_term_test!(wam, wam.heap[1], wam.heap[0]), + wam.compare_term_test(wam.heap[1], wam.heap[0]), Some(Ordering::Greater) ); assert_eq!( - compare_term_test!(wam, wam.heap[0], wam.heap[0]), + wam.compare_term_test(wam.heap[0], wam.heap[0]), Some(Ordering::Equal) ); assert_eq!( - compare_term_test!(wam, wam.heap[1], wam.heap[1]), + wam.compare_term_test(wam.heap[1], wam.heap[1]), Some(Ordering::Equal) ); let cstr_cell = wam.heap.allocate_cstr("string").unwrap(); assert_eq!( - compare_term_test!(wam, atom_as_cell!(atom!("atom")), cstr_cell), + wam.compare_term_test(atom_as_cell!(atom!("atom")), cstr_cell), Some(Ordering::Less) ); assert_eq!( - compare_term_test!( - wam, - atom_as_cell!(atom!("atom")), - atom_as_cell!(atom!("atom")) - ), + wam.compare_term_test(atom_as_cell!(atom!("atom")), atom_as_cell!(atom!("atom"))), Some(Ordering::Equal) ); assert_eq!( - compare_term_test!( - wam, - atom_as_cell!(atom!("atom")), - atom_as_cell!(atom!("aaa")) - ), + wam.compare_term_test(atom_as_cell!(atom!("atom")), atom_as_cell!(atom!("aaa"))), Some(Ordering::Greater) ); assert_eq!( - compare_term_test!( - wam, - fixnum_as_cell!(Fixnum::build_with(6)), - heap_loc_as_cell!(1) - ), + wam.compare_term_test(fixnum_as_cell!(Fixnum::build_with(6)), heap_loc_as_cell!(1)), Some(Ordering::Greater) ); @@ -644,12 +632,12 @@ mod tests { }); assert_eq!( - compare_term_test!(wam, heap_loc_as_cell!(0), heap_loc_as_cell!(0)), + wam.compare_term_test(heap_loc_as_cell!(0), heap_loc_as_cell!(0)), Some(Ordering::Equal) ); assert_eq!( - compare_term_test!(wam, heap_loc_as_cell!(0), atom_as_cell!(atom!("a"))), + wam.compare_term_test(heap_loc_as_cell!(0), atom_as_cell!(atom!("a"))), Some(Ordering::Greater) ); @@ -676,23 +664,22 @@ mod tests { }); assert_eq!( - compare_term_test!(wam, heap_loc_as_cell!(7), heap_loc_as_cell!(7)), + wam.compare_term_test(heap_loc_as_cell!(7), heap_loc_as_cell!(7)), Some(Ordering::Equal) ); assert_eq!( - compare_term_test!(wam, heap_loc_as_cell!(0), heap_loc_as_cell!(7)), + wam.compare_term_test(heap_loc_as_cell!(0), heap_loc_as_cell!(7)), Some(Ordering::Greater) ); assert_eq!( - compare_term_test!(wam, empty_list_as_cell!(), heap_loc_as_cell!(7)), + wam.compare_term_test(empty_list_as_cell!(), heap_loc_as_cell!(7)), Some(Ordering::Less) ); assert_eq!( - compare_term_test!( - wam, + wam.compare_term_test( empty_list_as_cell!(), fixnum_as_cell!(Fixnum::build_with(1)) ), @@ -702,29 +689,29 @@ mod tests { let cstr_cell = wam.heap.allocate_cstr("string").unwrap(); assert_eq!( - compare_term_test!(wam, empty_list_as_cell!(), cstr_cell), + wam.compare_term_test(empty_list_as_cell!(), cstr_cell), Some(Ordering::Less) ); assert_eq!( - compare_term_test!(wam, empty_list_as_cell!(), atom_as_cell!(atom!("atom"))), + wam.compare_term_test(empty_list_as_cell!(), atom_as_cell!(atom!("atom"))), Some(Ordering::Less) ); assert_eq!( - compare_term_test!(wam, atom_as_cell!(atom!("atom")), empty_list_as_cell!()), + wam.compare_term_test(atom_as_cell!(atom!("atom")), empty_list_as_cell!()), Some(Ordering::Greater) ); let one_p_one = HeapCellValue::from(float_alloc!(1.1, &mut wam.arena)); assert_eq!( - compare_term_test!(wam, one_p_one, fixnum_as_cell!(Fixnum::build_with(1))), + wam.compare_term_test(one_p_one, fixnum_as_cell!(Fixnum::build_with(1))), Some(Ordering::Less) ); assert_eq!( - compare_term_test!(wam, fixnum_as_cell!(Fixnum::build_with(1)), one_p_one), + wam.compare_term_test(fixnum_as_cell!(Fixnum::build_with(1)), one_p_one), Some(Ordering::Greater) ); } diff --git a/src/machine/system_calls.rs b/src/machine/system_calls.rs index d2db935e..aff084db 100644 --- a/src/machine/system_calls.rs +++ b/src/machine/system_calls.rs @@ -38,7 +38,7 @@ use rand::{Rng, SeedableRng}; use ordered_float::OrderedFloat; use fxhash::{FxBuildHasher, FxHasher}; -use indexmap::IndexSet; +use indexmap::*; use std::cell::Cell; use std::cmp::Ordering; @@ -574,6 +574,53 @@ pub(crate) struct FindallCopyInfo { } impl MachineState { + // determine whether two terms are variants, i.e. if there exists + // a bijection between their variable sets such that applying it + // to h1 produces h2 (ISO Prolog standard section 7.1.6.1). + // return true on failure and false on success. + #[inline(always)] + pub fn is_not_variant(&self) -> bool { + let h1 = self.registers[1]; + let h2 = self.registers[2]; + + let mut a_to_b = IndexMap::with_hasher(FxBuildHasher::default()); + let mut b_to_a = IndexMap::with_hasher(FxBuildHasher::default()); + + for term_pair in ParallelHeapIter::from(self, h1, h2) { + match term_pair { + TermPair::Vars(v1_offset, v2_offset) => { + match a_to_b.entry(v1_offset) { + indexmap::map::Entry::Occupied(stored_v2_offset) => { + if v2_offset != *stored_v2_offset.get() { + return true; + } + } + indexmap::map::Entry::Vacant(entry) => { + entry.insert_entry(v2_offset); + } + } + + match b_to_a.entry(v2_offset) { + indexmap::map::Entry::Occupied(stored_v1_offset) => { + if v1_offset != *stored_v1_offset.get() { + return true; + } + } + indexmap::map::Entry::Vacant(entry) => { + entry.insert_entry(v1_offset); + } + } + } + TermPair::Less(..) => return true, + TermPair::Greater(..) => return true, + TermPair::Unordered(cell_1, cell_2) if cell_1 != cell_2 => return true, + _ => {} + } + } + + false + } + fn copy_lifted_heap_from_offset(&mut self, offset: usize, lh_offset: usize) { let reserve_size = self.lifted_heap.cell_len() - lh_offset; let mut writer = step_or_resource_error!(self, self.heap.reserve(reserve_size)); diff --git a/src/macros.rs b/src/macros.rs index 7e7853dc..8d60e959 100644 --- a/src/macros.rs +++ b/src/macros.rs @@ -426,21 +426,6 @@ macro_rules! unify_with_occurs_check { }}; } -macro_rules! compare_term_test { - ($machine_st:expr, $e1:expr, $e2:expr) => {{ - $machine_st.pdl.push($e2); - $machine_st.pdl.push($e1); - - $machine_st.compare_term_test(VarComparison::Distinct) - }}; - ($machine_st:expr, $e1:expr, $e2:expr, $var_comparison:expr) => {{ - $machine_st.pdl.push($e2); - $machine_st.pdl.push($e1); - - $machine_st.compare_term_test($var_comparison) - }}; -} - macro_rules! step_or_resource_error { ($machine_st:expr, $val:expr) => {{ match $val { -- 2.54.0