From b64d45a74eb1652e1787260ac94c202d725de1e1 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sun, 19 Apr 2020 20:58:53 -0600 Subject: [PATCH] speed comparisons of partial strings --- src/prolog/machine/machine_state.rs | 112 ++++++++++++++++++++++- src/prolog/machine/machine_state_impl.rs | 49 +++++++++- src/prolog/machine/mod.rs | 7 ++ 3 files changed, 163 insertions(+), 5 deletions(-) diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index cc9a74c2..d247abe5 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -100,7 +100,7 @@ impl<'a> Iterator for HeapPStrIter<'a> { } else { Addr::EmptyList }; - + return Some(PStrIteratee::PStrSegment(h, n)); } else { unreachable!() @@ -147,6 +147,116 @@ impl<'a> Iterator for HeapPStrIter<'a> { } } +#[inline] +pub(super) +fn compare_pstr_prefixes<'a>( + i1: &mut HeapPStrIter<'a>, + i2: &mut HeapPStrIter<'a>, +) -> Option { + let mut r1 = i1.next(); + let mut r2 = i2.next(); + + loop { + if let Some(r1i) = r1 { + if let Some(r2i) = r2 { + match (r1i, r2i) { + (PStrIteratee::Char(c1), PStrIteratee::Char(c2)) => { + if c1 != c2 { + return c1.partial_cmp(&c2); + } + } + (PStrIteratee::Char(c1), PStrIteratee::PStrSegment(h, n)) => { + if let &HeapCellValue::PartialString(ref pstr, _) = &i2.machine_st.heap[h] { + if let Some(c2) = pstr.as_str_from(n).chars().next() { + if c1 != c2 { + return c1.partial_cmp(&c2); + } else { + r1 = i1.next(); + r2 = Some(PStrIteratee::PStrSegment(h, n + c2.len_utf8())); + + continue; + } + } else { + r2 = i2.next(); + continue; + } + } else { + unreachable!() + } + } + (PStrIteratee::PStrSegment(h, n), PStrIteratee::Char(c2)) => { + if let &HeapCellValue::PartialString(ref pstr, _) = &i1.machine_st.heap[h] { + if let Some(c1) = pstr.as_str_from(n).chars().next() { + if c1 != c2 { + return c2.partial_cmp(&c1); + } else { + r1 = i1.next(); + r2 = Some(PStrIteratee::PStrSegment(h, n + c1.len_utf8())); + + continue; + } + } else { + r1 = i1.next(); + continue; + } + } else { + unreachable!() + } + } + (PStrIteratee::PStrSegment(h1, n1), PStrIteratee::PStrSegment(h2, n2)) => { + match (&i1.machine_st.heap[h1], &i2.machine_st.heap[h2]) { + ( + &HeapCellValue::PartialString(ref pstr1, _), + &HeapCellValue::PartialString(ref pstr2, _), + ) => { + let str1 = pstr1.as_str_from(n1); + let str2 = pstr2.as_str_from(n2); + + if str1.starts_with(str2) { + r1 = Some(PStrIteratee::PStrSegment(h1, n1 + str2.len())); + r2 = i2.next(); + + continue; + } else if str2.starts_with(str1) { + r1 = i1.next(); + r2 = Some(PStrIteratee::PStrSegment(h2, n2 + str1.len())); + + continue; + } else { + return str1.partial_cmp(str2); + } + } + _ => { + unreachable!() + } + } + } + } + + r1 = i1.next(); + r2 = i2.next(); + + continue; + } + } + + return match (i1.focus(), i2.focus()) { + (Addr::EmptyList, Addr::EmptyList) => { + Some(Ordering::Equal) + } + (Addr::EmptyList, _) => { + Some(Ordering::Less) + } + (_, Addr::EmptyList) => { + Some(Ordering::Greater) + } + _ => { + None + } + }; + } +} + #[inline] pub(super) fn compare_pstr_to_string<'a>( diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 188b3673..350ca33d 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -1886,8 +1886,28 @@ impl MachineState { if !self.flags.double_quotes.is_atom() => { continue; } - (Addr::PStrLocation(..), Addr::PStrLocation(..)) => { - continue; + (pstr1 @ Addr::PStrLocation(..), pstr2 @ Addr::PStrLocation(..)) => { + let mut i1 = self.heap_pstr_iter(pstr1); + let mut i2 = self.heap_pstr_iter(pstr2); + + let ordering = compare_pstr_prefixes(&mut i1, &mut i2); + + if let Some(ordering) = ordering { + if ordering != Ordering::Equal { + return false; + } + } + + let (lstack, rstack) = iter.stack(); + + lstack.pop(); + lstack.pop(); + + rstack.pop(); + rstack.pop(); + + lstack.push(i1.focus()); + rstack.push(i2.focus()); } (Addr::Lis(_), Addr::Lis(_)) => { continue; @@ -2274,9 +2294,30 @@ impl MachineState { ) => { } ( - Addr::PStrLocation(..), - Addr::PStrLocation(..), + pstr1 @ Addr::PStrLocation(..), + pstr2 @ Addr::PStrLocation(..), ) => { + let mut i1 = self.heap_pstr_iter(pstr1); + let mut i2 = self.heap_pstr_iter(pstr2); + + let ordering = compare_pstr_prefixes(&mut i1, &mut i2); + + if let Some(ordering) = ordering { + if ordering != Ordering::Equal { + return Some(ordering); + } + } else { + let (lstack, rstack) = iter.stack(); + + lstack.pop(); + lstack.pop(); + + rstack.pop(); + rstack.pop(); + + lstack.push(i1.focus()); + rstack.push(i2.focus()); + } } ( Addr::Str(h1), diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index 1a58482a..c951135f 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -72,6 +72,13 @@ impl MachinePolicies { } } +impl Default for MachinePolicies { + #[inline] + fn default() -> Self { + MachinePolicies::new() + } +} + pub struct Machine { pub(super) machine_st: MachineState, pub(super) inner_heap: Heap, -- 2.54.0