From d96c9e00b7d959c297d59efa4e66abc4b4511bbc Mon Sep 17 00:00:00 2001 From: Mark Date: Sat, 14 Oct 2023 16:37:18 -0600 Subject: [PATCH] correct more acyclic_term/1 issues (#2111, #2114), add acyclic_term tests --- src/machine/gc.rs | 18 ++-- src/tests/acyclic_term.pl | 185 ++++++++++++++++++++++++++++++++++++++ tests/scryer/src_tests.rs | 9 ++ 3 files changed, 203 insertions(+), 9 deletions(-) create mode 100644 src/tests/acyclic_term.pl diff --git a/src/machine/gc.rs b/src/machine/gc.rs index bb90a29c..d7837395 100644 --- a/src/machine/gc.rs +++ b/src/machine/gc.rs @@ -270,14 +270,14 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { } #[inline] - fn is_cyclic(&self, h: usize) -> bool { - if self.heap[h].is_var() { - self.heap[h].get_forwarding_bit() - } else if self.heap[h].is_ref() { - // the cell h in the second branch contains its original - // value whether h is marked or unmarked, meaning the + fn is_cyclic(&self, var_current: usize, var_next: usize) -> bool { + if self.heap[var_next].is_var() { + var_current != var_next && self.current + 1 != var_current + } else if self.heap[var_next].is_ref() { + // the cell var_next in the second branch contains its original + // value whether var_next is marked or unmarked, meaning the // is_compound check is well-founded in either case. - self.heap[h].get_forwarding_bit() || self.heap[h].is_compound(self.heap) + self.heap[var_next].get_forwarding_bit() } else { false } @@ -294,7 +294,7 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { let current = self.current; if let Some(cell) = UMP::forward_attr_var(self) { - if current as u64 != next && self.is_cyclic(next as usize) { + if self.is_cyclic(current, next as usize) { self.iter_state.cycle_detected(); } @@ -313,7 +313,7 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { let current = self.current; if let Some(cell) = self.forward_var() { - if current as u64 != next && self.is_cyclic(next as usize) { + if self.is_cyclic(current, next as usize) { self.iter_state.cycle_detected(); } diff --git a/src/tests/acyclic_term.pl b/src/tests/acyclic_term.pl new file mode 100644 index 00000000..a7354a3f --- /dev/null +++ b/src/tests/acyclic_term.pl @@ -0,0 +1,185 @@ +:- use_module(library(format)). + +term1(A) :- + B=[C|D], + A=[D|C], + B=[C|B]. + +term2(A) :- + A=[B|C], + D=[C|C], + D=[B|D]. + +term3(A) :- + A=[_B|C], + D=[C|_E], + A=[C|D]. + +test("acyclic_term_1", ( + L = [_Y,[M,B],B|M], acyclic_term(L) +)). + +test("acyclic_term_2", ( + L = [_Y,[M,_B,L]|M], \+ acyclic_term(L) +)). + +test("acyclic_term_3", ( + L = [_Y,[M,B,L,B]|M], \+ acyclic_term(L) +)). + +test("acyclic_term_4", ( + L = [_Y,[L,_A,_B]|_M], \+ acyclic_term(L) +)). + +test("acyclic_term_5", ( + L = [_Y,[M,_A,_B]|M], acyclic_term(L) +)). + +test("acyclic_term_6", ( + L = [_Y,[L,_A,_B]|_M], \+ acyclic_term(L) +)). + +test("acyclic_term_7", ( + L = [A], A = [T], T = [_|X], X = Y, Y = L, \+ acyclic_term(T) +)). + +test("acyclic_term_8", ( + L = [A], A = [T], T = [_|X], X = Y, Y = L, \+ acyclic_term(L) +)). + +test("acyclic_term_9", ( + L = [A], A = [T], T = [_|X], X = Y, Y = L, \+ acyclic_term(A) +)). + +test("acyclic_term_10", ( + L = [A], A = [T], T = [_|X], X = Y, Y = L, \+ acyclic_term(Y) +)). + +test("acyclic_term_11", ( + L = [A], A = [T], T = [_|X], X = Y, Y = L, \+ acyclic_term(X) +)). + +test("acyclic_term_12", ( + A = [1|2], X = A, T=a(X, A), acyclic_term(T) +)). + +test("acyclic_term_13", ( + A = [A|2], X = A, T=a(X, A), \+ acyclic_term(T) +)). + +test("acyclic_term_13", ( + A = [T|2], X = A, T=a(X, A), \+ acyclic_term(T) +)). + +test("acyclic_term_14", ( + T = [_A|T], \+ acyclic_term(T) +)). + +test("acyclic_term_15", ( + T = [T|_L], \+ acyclic_term(T) +)). + +test("acyclic_term_16", ( + A = [1|A], X = A, T=a(X, A), \+ acyclic_term(T) +)). + +test("acyclic_term_17", ( + T = [_A| [[[[L|T]|[]]]]], acyclic_term(L) +)). + +test("acyclic_term_18", ( + T = [A| [[[[_L|T]|[]]]]], acyclic_term(A) +)). + +test("acyclic_term_19", ( + T = [_A| [[[[_L|T]|[]]]]], \+ acyclic_term(T) +)). + +test("acyclic_term_20", ( + A = [_C|_B], X = A, T=a(t(X,A), A), acyclic_term(T) +)). + +test("acyclic_term_21", ( + X = [a | Rest], Rest = [_Y | Rest], \+ acyclic_term(X) +)). + +test("acyclic_term_22", ( + _X = [a | Rest], Rest = [_Y | Rest], \+ acyclic_term(Rest) +)). + +test("acyclic_term_23", ( + T = [[_A, T]], G = [1|T], \+ acyclic_term(G) +)). + +test("acyclic_term_24", ( + T = [[_A, T]], \+ acyclic_term(T) +)). + +test("acyclic_term_25", ( + T = [[_, _], T], \+ acyclic_term(T) +)). + +test("acyclic_term_26", ( + T = [[T, _], 1], \+ acyclic_term(T) +)). + +test("acyclic_term#2111_1", ( + term1(A), \+ acyclic_term(A) +)). + +test("acyclic_term#2111_2", ( + term2(A), \+ acyclic_term(A) +)). + +test("acyclic_term#2111_3", ( + term3(A), \+ acyclic_term(A) +)). + +test("acyclic_term#2113", ( + A=[]*B,B=[]*B, \+ acyclic_term(A) +)). + +test("acyclic_term#2114", ( + A=B*B, acyclic_term(A) +)). + +test("acyclic_term_27", ( + T = str(A,A), acyclic_term(T) +)). + +test("acyclic_term_28", ( + T = str(A,A,A), acyclic_term(T) +)). + +main :- + findall(test(Name, Goal), test(Name, Goal), Tests), + run_tests(Tests, Failed), + show_failed(Failed), + halt. + +main_quiet :- + findall(test(Name, Goal), test(Name, Goal), Tests), + run_tests_quiet(Tests, Failed), + ( Failed = [] -> + format("All tests passed", []) + ; format("Some tests failed: ~w~n", [Failed]) + ), + halt. + +run_tests([], []). +run_tests([test(Name, Goal)|Tests], Failed) :- + format("Running test \"~s\"~n", [Name]), + ( call(Goal) -> + Failed = Failed1 + ; format("Failed test \"~s\"~n", [Name]), + Failed = [Name|Failed1] + ), + run_tests(Tests, Failed1). + +run_tests_quiet([], []). +run_tests_quiet([test(Name, Goal)|Tests], Failed) :- + ( call(Goal) -> + Failed = Failed1 + ; Failed = [Name|Failed1] + ), + run_tests_quiet(Tests, Failed1). diff --git a/tests/scryer/src_tests.rs b/tests/scryer/src_tests.rs index edc43d32..05d24c9e 100644 --- a/tests/scryer/src_tests.rs +++ b/tests/scryer/src_tests.rs @@ -102,3 +102,12 @@ fn term_variables_tests() { "All tests passed", ); } + +#[test] +fn acyclic_term_tests() { + run_top_level_test_with_args( + &["src/tests/acyclic_term.pl", "-f", "-g", "main_quiet"], + "", + "All tests passed", + ); +} -- 2.54.0