From 58ed37436320a56bfe5f6da7a803ac01bb674582 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Mon, 24 Sep 2018 22:24:23 -0600 Subject: [PATCH] enable backtracking on partial strings --- Cargo.lock | 6 +- Cargo.toml | 2 +- src/prolog/machine/machine_state.rs | 45 ++++++- src/prolog/machine/machine_state_impl.rs | 143 ++++++++++++++++------- src/prolog/or_stack.rs | 22 ++-- src/tests.rs | 51 ++++++-- 6 files changed, 205 insertions(+), 64 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 064bcf48..98b175f9 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -86,8 +86,7 @@ dependencies = [ [[package]] name = "prolog_parser" -version = "0.7.15" -source = "registry+https://github.com/rust-lang/crates.io-index" +version = "0.7.16" dependencies = [ "num 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", "ordered-float 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)", @@ -113,7 +112,7 @@ dependencies = [ "downcast 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)", "num 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)", "ordered-float 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)", - "prolog_parser 0.7.15 (registry+https://github.com/rust-lang/crates.io-index)", + "prolog_parser 0.7.16", "termion 1.5.1 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -152,7 +151,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index" "checksum num-traits 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)" = "cacfcab5eb48250ee7d0c7896b51a2c5eec99c1feea5f32025635f5ae4b00070" "checksum num-traits 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "630de1ef5cc79d0cdd78b7e33b81f083cbfe90de0f4b2b2f07f905867c70e9fe" "checksum ordered-float 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "58d25b6c0e47b20d05226d288ff434940296e7e2f8b877975da32f862152241f" -"checksum prolog_parser 0.7.15 (registry+https://github.com/rust-lang/crates.io-index)" = "11f378539616d1cd7b8fc006f309b5a4b483b82cbab76e898a9f1c99318b4dfa" "checksum redox_syscall 0.1.32 (registry+https://github.com/rust-lang/crates.io-index)" = "ab105df655884ede59d45b7070c8a65002d921461ee813a024558ca16030eea0" "checksum redox_termios 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7e891cfe48e9100a70a3b6eb652fef28920c117d366339687bd5576160db0f76" "checksum termion 1.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "689a3bdfaab439fd92bc87df5c4c78417d3cbe537487274e9b0b2dce76e92096" diff --git a/Cargo.toml b/Cargo.toml index 787ffe60..68282b9b 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -10,7 +10,7 @@ license = "BSD-3-Clause" downcast = "0.9.1" num = "0.2" ordered-float = "0.5.0" -prolog_parser = "0.7.15" +prolog_parser = "0.7.16" [dependencies.termion] version = "1.4.0" \ No newline at end of file diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index 7a8efc85..04e67939 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -249,7 +249,8 @@ pub struct MachineState { pub(super) or_stack: OrStack, pub(super) registers: Registers, pub(super) trail: Vec, - pub(super) partial_string_trail: Vec<(StringList, usize)>, + pub(super) pstr_trail: Vec<(usize, StringList, usize)>, // b, String, trunc_pt + pub(super) pstr_tr: usize, pub(super) tr: usize, pub(super) hb: usize, pub(super) block: usize, // an offset into the OR stack. @@ -298,6 +299,15 @@ pub(crate) trait CallPolicy: Any { machine_st.tr = machine_st.or_stack[b].tr; machine_st.trail.truncate(machine_st.tr); + + let old_pstr_tr = machine_st.or_stack[b].pstr_tr; + let curr_pstr_tr = machine_st.pstr_tr; + + machine_st.unwind_pstr_trail(old_pstr_tr, curr_pstr_tr); + machine_st.pstr_tr = machine_st.or_stack[b].pstr_tr; + + machine_st.pstr_trail.truncate(machine_st.pstr_tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); machine_st.hb = machine_st.heap.h; @@ -324,9 +334,18 @@ pub(crate) trait CallPolicy: Any { let curr_tr = machine_st.tr; machine_st.unwind_trail(old_tr, curr_tr); - machine_st.tr = machine_st.or_stack[b].tr; + machine_st.tr = machine_st.or_stack[b].tr; machine_st.trail.truncate(machine_st.tr); + + let old_pstr_tr = machine_st.or_stack[b].pstr_tr; + let curr_pstr_tr = machine_st.pstr_tr; + + machine_st.unwind_pstr_trail(old_pstr_tr, curr_pstr_tr); + machine_st.pstr_tr = machine_st.or_stack[b].pstr_tr; + + machine_st.pstr_trail.truncate(machine_st.pstr_tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); machine_st.hb = machine_st.heap.h; @@ -351,10 +370,18 @@ pub(crate) trait CallPolicy: Any { let curr_tr = machine_st.tr; machine_st.unwind_trail(old_tr, curr_tr); - machine_st.tr = machine_st.or_stack[b].tr; + machine_st.trail.truncate(machine_st.tr); + let old_pstr_tr = machine_st.or_stack[b].pstr_tr; + let curr_pstr_tr = machine_st.pstr_tr; + + machine_st.unwind_pstr_trail(old_pstr_tr, curr_pstr_tr); + machine_st.pstr_tr = machine_st.or_stack[b].pstr_tr; + + machine_st.pstr_trail.truncate(machine_st.pstr_tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); machine_st.b = machine_st.or_stack[b].b; @@ -382,10 +409,18 @@ pub(crate) trait CallPolicy: Any { let curr_tr = machine_st.tr; machine_st.unwind_trail(old_tr, curr_tr); - machine_st.tr = machine_st.or_stack[b].tr; + machine_st.trail.truncate(machine_st.tr); + let old_pstr_tr = machine_st.or_stack[b].pstr_tr; + let curr_pstr_tr = machine_st.pstr_tr; + + machine_st.unwind_pstr_trail(old_pstr_tr, curr_pstr_tr); + machine_st.pstr_tr = machine_st.or_stack[b].pstr_tr; + + machine_st.pstr_trail.truncate(machine_st.pstr_tr); + machine_st.heap.truncate(machine_st.or_stack[b].h); machine_st.b = machine_st.or_stack[b].b; @@ -842,6 +877,7 @@ fn cut_body(machine_st: &mut MachineState, addr: Addr) -> bool { if b > b0 { machine_st.b = b0; machine_st.tidy_trail(); + machine_st.tidy_pstr_trail(); machine_st.or_stack.truncate(machine_st.b); } } else { @@ -923,6 +959,7 @@ impl CutPolicy for SCCCutPolicy { if b > b0 { machine_st.b = b0; machine_st.tidy_trail(); + machine_st.tidy_pstr_trail(); machine_st.or_stack.truncate(machine_st.b); } } else { diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 03dcdf59..5e2245f5 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -49,7 +49,8 @@ impl MachineState { or_stack: OrStack::new(), registers: vec![Addr::HeapCell(0); MAX_ARITY + 1], // self.registers[0] is never used. trail: vec![], - partial_string_trail: vec![], + pstr_trail: vec![], + pstr_tr: 0, tr: 0, hb: 0, block: 0, @@ -162,6 +163,51 @@ impl MachineState { printer.print(addr) } + pub(super) + fn unify_string(&mut self, pdl: &mut Vec, s1: &mut StringList, s2: &mut StringList) -> bool + { + if let Some(c1) = s1.head() { + if let Some(c2) = s2.head() { + if c1 == c2 { + pdl.push(Addr::Con(Constant::String(s1.tail()))); + pdl.push(Addr::Con(Constant::String(s2.tail()))); + + return true; + } + } else if s2.is_expandable() { + self.pstr_trail(s2.clone()); + + pdl.push(Addr::Con(Constant::String(s2.push_char(c1)))); + pdl.push(Addr::Con(Constant::String(s1.tail()))); + + return true; + } + } else if s1.is_expandable() { + if let Some(c) = s2.head() { + self.pstr_trail(s1.clone()); + + pdl.push(Addr::Con(Constant::String(s1.push_char(c)))); + pdl.push(Addr::Con(Constant::String(s2.tail()))); + } else if s2.is_expandable() { + return s1 == s2; + } else { + self.pstr_trail(s1.clone()); + s1.set_non_expandable(); + } + + return true; + } else if s2.head().is_none() { + if s2.is_expandable() { + self.pstr_trail(s2.clone()); + } + + s2.set_non_expandable(); + return true; + } + + false + } + pub(super) fn unify(&mut self, a1: Addr, a2: Addr) { let mut pdl = vec![a1, a2]; @@ -208,6 +254,8 @@ impl MachineState { continue; } else if s.is_expandable() { + let prev_s = s.clone(); + let mut stepper = |c| { let new_s = s.push_char(c); @@ -217,12 +265,14 @@ impl MachineState { match self.heap[a1].clone() { HeapCellValue::Addr(Addr::Con(Constant::Char(c))) => { + self.pstr_trail(prev_s); stepper(c); continue; }, HeapCellValue::Addr(Addr::Con(Constant::Atom(ref a, _))) => if let Some(c) = a.as_str().chars().next() { if c.len_utf8() == a.as_str().len() { + self.pstr_trail(prev_s); stepper(c); continue; } @@ -237,6 +287,7 @@ impl MachineState { | (Addr::Con(Constant::String(ref s)), Addr::Con(Constant::EmptyList)) if self.flags.double_quotes.is_chars() => { if s.is_expandable() && s.is_empty() { + self.pstr_trail(s.clone()); s.set_non_expandable(); continue; } @@ -251,43 +302,9 @@ impl MachineState { pdl.push(Addr::HeapCell(a2 + 1)); }, (Addr::Con(Constant::String(ref mut s1)), - Addr::Con(Constant::String(ref mut s2))) => { - let mut stepper = |s1: &mut StringList, s2: &mut StringList| -> bool { - if let Some(c1) = s1.head() { - if let Some(c2) = s2.head() { - if c1 == c2 { - pdl.push(Addr::Con(Constant::String(s1.tail()))); - pdl.push(Addr::Con(Constant::String(s2.tail()))); - - return true; - } - } else if s2.is_expandable() { - pdl.push(Addr::Con(Constant::String(s2.push_char(c1)))); - pdl.push(Addr::Con(Constant::String(s1.tail()))); - - return true; - } - } else if s1.is_expandable() { - if let Some(c) = s2.head() { - pdl.push(Addr::Con(Constant::String(s1.push_char(c)))); - pdl.push(Addr::Con(Constant::String(s2.tail()))); - } else if s2.is_expandable() { - return s1 == s2; - } else { - s1.set_non_expandable(); - } - - return true; - } else if s2.head().is_none() { - s2.set_non_expandable(); - return true; - } - - false - }; - - self.fail = !(stepper(s1, s2) || stepper(s2, s1)); - }, + Addr::Con(Constant::String(ref mut s2))) => + self.fail = !(self.unify_string(&mut pdl, s1, s2) + || self.unify_string(&mut pdl, s2, s1)), (Addr::Con(ref c1), Addr::Con(ref c2)) => if c1 != c2 { self.fail = true; @@ -317,6 +334,19 @@ impl MachineState { } } + #[inline] + fn pstr_trail(&mut self, s: StringList) { + if let Some((prev_b, prev_s, _)) = self.pstr_trail.last().cloned() { + if prev_b == self.b && prev_s == s { + return; + } + } + + let len = s.len(); + self.pstr_trail.push((self.b, s, len)); + self.pstr_tr += 1; + } + fn trail(&mut self, r: Ref) { match r { Ref::HeapCell(hc) => @@ -356,6 +386,35 @@ impl MachineState { } } + pub(super) fn unwind_pstr_trail(&mut self, a1: usize, a2: usize) { + for i in a1 .. a2 { + let (_, mut s, end) = self.pstr_trail[i].clone(); + s.truncate(end); + } + } + + pub(super) fn tidy_pstr_trail(&mut self) { + if self.b == 0 { + return; + } + + let b = self.b - 1; + let mut i = self.or_stack[b].pstr_tr; + + while i < self.pstr_tr { + let str_b = self.pstr_trail[i].0; + + if b < str_b { + let pstr_tr = self.pstr_tr; + let val = self.pstr_trail[pstr_tr - 1].clone(); + self.pstr_trail[i] = val; + self.pstr_tr -= 1; + } else { + i += 1; + } + } + } + pub(super) fn tidy_trail(&mut self) { if self.b == 0 { return; @@ -402,6 +461,8 @@ impl MachineState { #[inline] fn write_char_to_string(&mut self, s: &mut StringList, c: char) -> bool { + self.pstr_trail(s.clone()); + let new_s = s.push_char(c); self.heap.push(HeapCellValue::Addr(Addr::Con(Constant::String(new_s)))); false @@ -422,6 +483,7 @@ impl MachineState { Constant::EmptyList if self.flags.double_quotes.is_chars() => !s.is_empty(), Constant::String(ref s2) if s.is_empty() && s.is_expandable() => { + self.pstr_trail(s.clone()); s.append(s2); false }, @@ -2140,6 +2202,7 @@ impl MachineState { self.b, self.p.clone() + 1, self.tr, + self.pstr_tr, self.heap.h, self.b0, self.num_of_args); @@ -2175,6 +2238,7 @@ impl MachineState { self.b, self.p.clone() + offset, self.tr, + self.pstr_tr, self.heap.h, self.b0, self.num_of_args); @@ -2246,13 +2310,14 @@ impl MachineState { self.b0 = 0; self.s = 0; self.tr = 0; + self.pstr_tr = 0; self.p = CodePtr::default(); self.cp = LocalCodePtr::default(); self.num_of_args = 0; self.fail = false; self.trail.clear(); - self.partial_string_trail.clear(); + self.pstr_trail.clear(); self.heap.clear(); self.mode = MachineMode::Write; self.and_stack.clear(); diff --git a/src/prolog/or_stack.rs b/src/prolog/or_stack.rs index 6fda0971..dce84db0 100644 --- a/src/prolog/or_stack.rs +++ b/src/prolog/or_stack.rs @@ -10,6 +10,7 @@ pub struct Frame { pub b: usize, pub bp: CodePtr, pub tr: usize, + pub pstr_tr: usize, pub h: usize, pub b0: usize, args: Vec @@ -22,20 +23,22 @@ impl Frame { b: usize, bp: CodePtr, tr: usize, + pstr_tr: usize, h: usize, b0: usize, n: usize) -> Self { Frame { - global_index: global_index, - e: e, - cp: cp, - b: b, - bp: bp, - tr: tr, - h: h, - b0: b0, + global_index, + e, + cp, + b, + bp, + tr, + pstr_tr, + h, + b0, args: vec![Addr::HeapCell(0); n] } } @@ -59,11 +62,12 @@ impl OrStack { b: usize, bp: CodePtr, tr: usize, + pstr_tr: usize, h: usize, b0: usize, n: usize) { - self.0.push(Frame::new(global_index, e, cp, b, bp, tr, h, b0, n)); + self.0.push(Frame::new(global_index, e, cp, b, bp, tr, pstr_tr, h, b0, n)); } pub fn len(&self) -> usize { diff --git a/src/tests.rs b/src/tests.rs index 3af70b07..33f5cb98 100644 --- a/src/tests.rs +++ b/src/tests.rs @@ -1488,7 +1488,7 @@ fn test_queries_on_builtins() [["Term = [[[[_22, _26], _26], _22]]", "X = _2", "Y = _0"]]); assert_prolog_success!(&mut wam, "?- duplicate_term([X, [Y, [X]]], Term).", [["Term = [_12, [_16, [_12]]]", "X = _0", "Y = _4"]]); - + // test duplicate_term on cyclic terms. assert_prolog_failure!(&mut wam, "?- X = g(X, Y), Y = f(X), duplicate_term(Y, g(Z))."); assert_prolog_success!(&mut wam, "?- X = g(X, Y), Y = f(X), duplicate_term(Y, f(Z)).", @@ -1499,7 +1499,7 @@ fn test_queries_on_builtins() [["NewTerm = f(_16, _16, [_19, a, [], _16])", "Term = f(_0, Y, [_6, a, [], Y])", "X = _6", "Y = _0"]]); - + assert_prolog_success!(&mut wam, "?- float(3.14159269)."); assert_prolog_failure!(&mut wam, "?- float(3)."); assert_prolog_failure!(&mut wam, "?- float(\"sdfsa\")."); @@ -1640,12 +1640,12 @@ fn test_queries_on_builtins() assert_prolog_success!(&mut wam, "?- call_with_inference_limit((setup_call_cleanup(S=1,(G=2;fail),writeq(S+G>B)), B=3, !), 100, R).", [["G = 2", "B = 3", "R = !", "S = 1"]]); assert_prolog_success!(&mut wam, "?- call_with_inference_limit((setup_call_cleanup(S=1,(G=2;fail),writeq(S+G>B)), B=3, !), 10, R).", - [["S = _1", "G = _4", "B = _14", "R = inference_limit_exceeded"]]); - + [["S = _1", "G = _4", "B = _14", "R = inference_limit_exceeded"]]); + assert_prolog_success!(&mut wam, "?- X = '\\n'.", [["X = '\\n'"]]); assert_prolog_success!(&mut wam, "?- X = '\\b'.", - [["X = '\\b'"]]); + [["X = '\\b'"]]); assert_prolog_success!(&mut wam, "?- X = '\\v'.", [["X = '\\v'"]]); assert_prolog_success!(&mut wam, "?- X = '\\a'.", @@ -1889,7 +1889,7 @@ fn test_queries_on_string_lists() assert_prolog_success!(&mut wam, "?- X = \"abc\", Y = \"abc\", X =@= Y."); assert_prolog_success!(&mut wam, "?- partial_string(\"abc\", X), partial_string(\"abc\", Y), X =@= Y."); - + submit(&mut wam, "matcher([a,b,c|X], ['d','e','f'|X])."); assert_prolog_success!(&mut wam, "?- matcher(\"abcdef\", \"defdef\")."); @@ -1973,7 +1973,7 @@ fn test_queries_on_string_lists() assert_prolog_failure!(&mut wam, "?- partial_string(\"abc\", X), X \\=@= \"abc\"."); assert_prolog_failure!(&mut wam, "?- partial_string(\"abc\", X), X @< \"abc\"."); - assert_prolog_success!(&mut wam, "?- partial_string(\"ab\", X), matcher(X, Y), Y = [a,b|V], + assert_prolog_success!(&mut wam, "?- partial_string(\"ab\", X), matcher(X, Y), Y = [a,b|V], matcher(Y, Z), is_partial_string(Y).", [["V = [c | _]", "X = [a, b, c, a, b, c | _]", "Y = [a, b, c | _]", "Z = _"]]); assert_prolog_success!(&mut wam, "?- partial_string(\"a\", X), matcher(X, Y).", @@ -1982,4 +1982,41 @@ fn test_queries_on_string_lists() [["X = [a, b, c | _]", "Y = _"]]); assert_prolog_success!(&mut wam, "?- partial_string(\"a\", X), matcher(X, Y), Y = \"def\".", [["X = [a, b, c, d, e, f]", "Y = [d, e, f]"]]); + + submit(&mut wam, "matcher([a,b,c|X], X). + matcher([a,b,d|X], X)."); + + assert_prolog_success!(&mut wam, "?- partial_string(\"ab\", X), matcher(X, Y).", + [["X = [a, b, c | _]", "Y = _"], + ["X = [a, b, d | _]", "Y = _"]]); + + submit(&mut wam, "matcher([a,b,c,d|X], X). + matcher([a,c,d|X], X)."); + + assert_prolog_success!(&mut wam, "?- partial_string(\"ab\", X), matcher(X, Y).", + [["X = [a, b, c, d | _]", "Y = _"]]); + + assert_prolog_success!(&mut wam, "?- partial_string(\"a\", X), matcher(X, Y).", + [["X = [a, b, c, d | _]", "Y = _"], + ["X = [a, c, d | _]", "Y = _"]]); + + submit(&mut wam, "matcher([a,b,c,d|X], X). + matcher([a,c,d|X], X). + matcher([a,e,f|X], X)."); + + assert_prolog_success!(&mut wam, "?- partial_string(\"a\", X), matcher(X, Y).", + [["X = [a, b, c, d | _]", "Y = _"], + ["X = [a, c, d | _]", "Y = _"], + ["X = [a, e, f | _]", "Y = _"]]); + assert_prolog_success!(&mut wam, "?- partial_string(\"a\", X), matcher(X, Y), Y = \" t\".", + [["X = [a, b, c, d, ' ', t]", "Y = [' ', t]"], + ["X = [a, c, d, ' ', t]", "Y = [' ', t]"], + ["X = [a, e, f, ' ', t]", "Y = [' ', t]"]]); + + submit(&mut wam, "matcher([a,b,c|X], X) :- X = []. + matcher([a,b,c|X], X)."); + + assert_prolog_success!(&mut wam, "?- partial_string(\"abc\", X), matcher(X, Y).", + [["X = [a, b, c]", "Y = []"], + ["X = [a, b, c | _]", "Y = _"]]); } -- 2.54.0