From 064d261357f7aa27c96be561b8b0eb22b57074ae Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 27 Feb 2021 22:51:32 -0700 Subject: [PATCH] implement logical update semantics for dynamic database predicates --- src/codegen.rs | 181 ++++--- src/indexing.rs | 797 +++++++++++++++++++++++------- src/instructions.rs | 113 ++++- src/lib/builtins.pl | 58 +-- src/machine/code_repo.rs | 98 +++- src/machine/code_walker.rs | 8 + src/machine/compile.rs | 515 ++++++++++++++++--- src/machine/load_state.rs | 12 +- src/machine/loader.rs | 51 +- src/machine/machine_indices.rs | 34 +- src/machine/machine_state.rs | 20 +- src/machine/machine_state_impl.rs | 376 +++++++++++++- src/machine/mod.rs | 11 +- src/machine/system_calls.rs | 12 +- src/macros.rs | 1 + src/write.rs | 37 +- 16 files changed, 1905 insertions(+), 419 deletions(-) diff --git a/src/codegen.rs b/src/codegen.rs index cb9c4a97..7a5d8ba3 100644 --- a/src/codegen.rs +++ b/src/codegen.rs @@ -21,24 +21,6 @@ use std::cell::Cell; use std::collections::VecDeque; use std::rc::Rc; -#[inline] -pub fn trust_me(non_counted_bt: bool) -> ChoiceInstruction { - if non_counted_bt { - ChoiceInstruction::DefaultTrustMe(0) - } else { - ChoiceInstruction::TrustMe(0) - } -} - -#[inline] -pub fn retry_me_else(offset: usize, non_counted_bt: bool) -> ChoiceInstruction { - if non_counted_bt { - ChoiceInstruction::DefaultRetryMeElse(offset) - } else { - ChoiceInstruction::RetryMeElse(offset) - } -} - #[derive(Debug)] pub struct ConjunctInfo<'a> { pub perm_vs: VariableFixtures<'a>, @@ -109,16 +91,93 @@ impl<'a> ConjunctInfo<'a> { #[derive(Clone, Copy, Debug)] pub struct CodeGenSettings { + pub global_clock_tick: Option, pub is_extensible: bool, pub non_counted_bt: bool, } impl CodeGenSettings { #[inline] - pub fn new(is_extensible: bool, non_counted_bt: bool) -> Self { - CodeGenSettings { - is_extensible, - non_counted_bt, + pub fn is_dynamic(&self) -> bool { + self.global_clock_tick.is_some() + } + + #[inline] + pub fn internal_try_me_else(&self, offset: usize) -> ChoiceInstruction { + if let Some(global_clock_time) = self.global_clock_tick { + ChoiceInstruction::DynamicInternalElse( + global_clock_time, + Death::Infinity, + if offset == 0 { NextOrFail::Next(0) } else { NextOrFail::Next(offset) }, + ) + } else { + ChoiceInstruction::TryMeElse(offset) + } + } + + pub fn try_me_else(&self, offset: usize) -> ChoiceInstruction { + if let Some(global_clock_tick) = self.global_clock_tick { + ChoiceInstruction::DynamicElse( + global_clock_tick, + Death::Infinity, + if offset == 0 { NextOrFail::Next(0) } else { NextOrFail::Next(offset) }, + ) + } else { + ChoiceInstruction::TryMeElse(offset) + } + } + + pub fn internal_retry_me_else(&self, offset: usize) -> ChoiceInstruction { + if let Some(global_clock_tick) = self.global_clock_tick { + ChoiceInstruction::DynamicInternalElse( + global_clock_tick, + Death::Infinity, + if offset == 0 { NextOrFail::Next(0) } else { NextOrFail::Next(offset) }, + ) + } else { + ChoiceInstruction::RetryMeElse(offset) + } + } + + pub fn retry_me_else(&self, offset: usize) -> ChoiceInstruction { + if let Some(global_clock_tick) = self.global_clock_tick { + ChoiceInstruction::DynamicElse( + global_clock_tick, + Death::Infinity, + if offset == 0 { NextOrFail::Next(0) } else { NextOrFail::Next(offset) }, + ) + } else if self.non_counted_bt { + ChoiceInstruction::DefaultRetryMeElse(offset) + } else { + ChoiceInstruction::RetryMeElse(offset) + } + } + + pub fn internal_trust_me(&self) -> ChoiceInstruction { + if let Some(global_clock_tick) = self.global_clock_tick { + ChoiceInstruction::DynamicInternalElse( + global_clock_tick, + Death::Infinity, + NextOrFail::Fail(0), + ) + } else if self.non_counted_bt { + ChoiceInstruction::DefaultTrustMe(0) + } else { + ChoiceInstruction::TrustMe(0) + } + } + + pub fn trust_me(&self) -> ChoiceInstruction { + if let Some(global_clock_tick) = self.global_clock_tick { + ChoiceInstruction::DynamicElse( + global_clock_tick, + Death::Infinity, + NextOrFail::Fail(0), + ) + } else if self.non_counted_bt { + ChoiceInstruction::DefaultTrustMe(0) + } else { + ChoiceInstruction::TrustMe(0) } } } @@ -128,8 +187,7 @@ pub struct CodeGenerator { atom_tbl: TabledData, marker: TermMarker, pub var_count: IndexMap, usize>, - non_counted_bt: bool, - is_extensible: bool, + settings: CodeGenSettings, pub skeleton: PredicateSkeleton, pub jmp_by_locs: Vec, global_jmp_by_locs_offset: usize, @@ -141,8 +199,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { atom_tbl, marker: Allocator::new(), var_count: IndexMap::new(), - non_counted_bt: settings.non_counted_bt, - is_extensible: settings.is_extensible, + settings, skeleton: PredicateSkeleton::new(), jmp_by_locs: vec![], global_jmp_by_locs_offset: 0, @@ -889,27 +946,6 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { self.add_conditional_call(code, term, num_perm_vars_left); } - /* - pub fn compile_query(&mut self, query: &'a Vec) -> Result { - let iter = ChunkedIterator::from_term_sequence(query); - let conjunct_info = self.collect_var_data(iter); - - let mut code = Vec::new(); - self.compile_seq_prelude(&conjunct_info, &mut code); - - let iter = ChunkedIterator::from_term_sequence(query); - self.compile_seq(iter, &conjunct_info, &mut code, true)?; - - conjunct_info.mark_unsafe_vars(UnsafeVarMarker::new(), &mut code); - - if let Some(query_term) = query.last() { - Self::compile_cleanup(&mut code, &conjunct_info, query_term); - } - - Ok(code) - } - */ - #[inline] fn increment_jmp_by_locs_by(&mut self, incr: usize) { let offset = self.global_jmp_by_locs_offset; @@ -986,15 +1022,19 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { subseqs } - fn compile_pred_subseq<'b: 'a>( + fn compile_pred_subseq<'b: 'a, I: Indexer>( &mut self, clauses: &'b [PredicateClause], optimal_index: usize, ) -> Result { let mut code = VecDeque::new(); - let mut code_offsets = CodeOffsets::new(self.atom_tbl.clone(), optimal_index + 1); - let mut skip_stub_try_me_else = false; + let mut code_offsets = CodeOffsets::new( + self.atom_tbl.clone(), + I::new(), + optimal_index + 1, + ); + let mut skip_stub_try_me_else = false; let jmp_by_locs_len = self.jmp_by_locs.len(); for (i, clause) in clauses.iter().enumerate() { @@ -1010,13 +1050,14 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { if clauses.len() > 1 { let choice = match i { - 0 => ChoiceInstruction::TryMeElse(clause_code.len() + 1), - _ if i == clauses.len() - 1 => trust_me(self.non_counted_bt), - _ => retry_me_else(clause_code.len() + 1, self.non_counted_bt), + 0 => self.settings.internal_try_me_else(clause_code.len() + 1), + //ChoiceInstruction::TryMeElse(clause_code.len() + 1), + _ if i == clauses.len() - 1 => self.settings.internal_trust_me(), + _ => self.settings.internal_retry_me_else(clause_code.len() + 1), }; code.push_back(Line::Choice(choice)); - } else if self.is_extensible { + } else if self.settings.is_extensible { /* generate stub choice instructions for extensible predicates. if predicates are added to either the @@ -1028,8 +1069,9 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { over them. */ - code.push_front(Line::Choice(ChoiceInstruction::TryMeElse(0))); - skip_stub_try_me_else = true; + code.push_front(Line::Choice(self.settings.internal_try_me_else(0))); + //Line::Choice(ChoiceInstruction::TryMeElse(0))); + skip_stub_try_me_else = !self.settings.is_dynamic(); //true; } let arg = match clause.args() { @@ -1045,7 +1087,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { code_offsets.index_term(arg, index, &mut clause_index_info); } - if !skip_stub_try_me_else { + if !(clauses.len() == 1 && self.settings.is_extensible) { self.increment_jmp_by_locs_by(code.len()); } @@ -1065,7 +1107,11 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { } else { self.increment_jmp_by_locs_by(1); } - } else if skip_stub_try_me_else { + } else if clauses.len() == 1 && self.settings.is_extensible { + // the condition is the value of skip_stub_try_me_else, which is + // true if the predicate is not dynamic. This operation must apply + // to dynamic predicates also, though. + // remove the TryMeElse(0). code.pop_front(); } @@ -1089,22 +1135,27 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator { for (l, r) in split_pred { let skel_lower_bound = self.skeleton.clauses.len(); - let code_segment = self.compile_pred_subseq(&clauses[l..r], optimal_index)?; + let code_segment = if self.settings.is_dynamic() { + self.compile_pred_subseq::(&clauses[l..r], optimal_index)? + } else { + self.compile_pred_subseq::(&clauses[l..r], optimal_index)? + }; + let clause_start_offset = code.len(); if multi_seq { let choice = match l { - 0 => ChoiceInstruction::TryMeElse(code_segment.len() + 1), - _ if r == clauses.len() => trust_me(self.non_counted_bt), - _ => retry_me_else(code_segment.len() + 1, self.non_counted_bt), + 0 => self.settings.try_me_else(code_segment.len() + 1), + _ if r == clauses.len() => self.settings.trust_me(), + _ => self.settings.retry_me_else(code_segment.len() + 1), }; code.push(Line::Choice(choice)); - } else if self.is_extensible { - code.push(Line::Choice(ChoiceInstruction::TryMeElse(0))); + } else if self.settings.is_extensible { + code.push(Line::Choice(self.settings.try_me_else(0))); } - if self.is_extensible { + if self.settings.is_extensible { let segment_is_indexed = to_indexing_line(&code_segment[0]).is_some(); for clause_index_info in self.skeleton.clauses[skel_lower_bound..].iter_mut() { diff --git a/src/indexing.rs b/src/indexing.rs index 49a3afdf..754cc57d 100644 --- a/src/indexing.rs +++ b/src/indexing.rs @@ -13,11 +13,13 @@ use slice_deque::{sdeq, SliceDeque}; use std::convert::TryFrom; use std::hash::Hash; use std::iter::once; +use std::mem; use std::rc::Rc; #[derive(Debug, Clone, Copy)] pub enum IndexingCodePtr { External(usize), // the index points past the indexing instruction prelude. + DynamicExternal(usize), // an External index of a dynamic predicate, potentially invalidated by retraction. Fail, Internal(usize), // the index points into the indexing instruction prelude. } @@ -66,10 +68,10 @@ fn search_skeleton_for_first_key_type( struct IndexingCodeMergingPtr<'a> { skeleton: &'a mut [ClauseIndexInfo], - // merged_clause_index: usize, indexing_code: &'a mut Vec, offset: usize, append_or_prepend: AppendOrPrepend, + is_dynamic: bool, } impl<'a> IndexingCodeMergingPtr<'a> { @@ -79,11 +81,23 @@ impl<'a> IndexingCodeMergingPtr<'a> { indexing_code: &'a mut Vec, append_or_prepend: AppendOrPrepend, ) -> Self { + let is_dynamic = match &indexing_code[0] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, v, ..)) => { + match v { + IndexingCodePtr::External(_) => false, + IndexingCodePtr::DynamicExternal(_) => true, + _ => unreachable!() + } + } + _ => unreachable!() + }; + Self { skeleton, indexing_code, offset: 0, append_or_prepend, + is_dynamic, } } @@ -106,11 +120,12 @@ impl<'a> IndexingCodeMergingPtr<'a> { } if let IndexingCodePtr::Internal(_) = constant_ptr { + let last_index = self.indexing_code.len(); + self.indexing_code.push(IndexingLine::Indexing( IndexingInstruction::SwitchOnConstant(constants), )); - let last_index = self.indexing_code.len() - 1; self.indexing_code.swap(self.offset, last_index); } else { self.offset = self.indexing_code.len(); @@ -121,7 +136,7 @@ impl<'a> IndexingCodeMergingPtr<'a> { } } - fn add_indexed_choice_for_constant( + fn add_static_indexed_choice_for_constant( &mut self, external: usize, constant: Constant, @@ -140,8 +155,35 @@ impl<'a> IndexingCodeMergingPtr<'a> { }; let indexing_code_len = self.indexing_code.len(); - self.indexing_code - .push(IndexingLine::IndexedChoice(third_level_index)); + self.indexing_code.push(IndexingLine::IndexedChoice(third_level_index)); + + match &mut self.indexing_code[self.offset] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant(ref mut constants)) => { + constants.insert( + constant, + IndexingCodePtr::Internal(indexing_code_len - self.offset), + ); + } + _ => { + unreachable!() + } + } + } + + fn add_dynamic_indexed_choice_for_constant( + &mut self, + external: usize, + constant: Constant, + index: usize, + ) { + let third_level_index = if self.append_or_prepend.is_append() { + sdeq![external, index] + } else { + sdeq![index, external] + }; + + let indexing_code_len = self.indexing_code.len(); + self.indexing_code.push(IndexingLine::DynamicIndexedChoice(third_level_index)); match &mut self.indexing_code[self.offset] { IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant(ref mut constants)) => { @@ -168,6 +210,14 @@ impl<'a> IndexingCodeMergingPtr<'a> { uncap_choice_seq_with_try(indexed_choice_instrs); indexed_choice_instrs.push_front(IndexedChoiceInstruction::Try(index)); } + IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) + if self.append_or_prepend.is_append() => + { + indexed_choice_instrs.push_back(index); + } + IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) => { + indexed_choice_instrs.push_front(index); + } _ => { unreachable!() } @@ -186,11 +236,15 @@ impl<'a> IndexingCodeMergingPtr<'a> { match &mut self.indexing_code[self.offset] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, ref mut c, ..)) => { match *c { + IndexingCodePtr::Fail if self.is_dynamic => { + *c = IndexingCodePtr::DynamicExternal(index); + break; + } IndexingCodePtr::Fail => { *c = IndexingCodePtr::External(index); break; } - IndexingCodePtr::External(_) => { + IndexingCodePtr::DynamicExternal(_) | IndexingCodePtr::External(_) => { let mut constants = IndexMap::new(); constants.insert(orig_constant.clone(), *c); @@ -209,12 +263,23 @@ impl<'a> IndexingCodeMergingPtr<'a> { } IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant(constants)) => { match constants.get(&overlapping_constant).cloned() { + None | Some(IndexingCodePtr::Fail) if self.is_dynamic => { + constants.insert( + overlapping_constant, + IndexingCodePtr::DynamicExternal(index), + ); + } None | Some(IndexingCodePtr::Fail) => { - constants - .insert(overlapping_constant, IndexingCodePtr::External(index)); + constants.insert( + overlapping_constant, + IndexingCodePtr::External(index), + ); + } + Some(IndexingCodePtr::DynamicExternal(o)) => { + self.add_dynamic_indexed_choice_for_constant(o, overlapping_constant, index); } Some(IndexingCodePtr::External(o)) => { - self.add_indexed_choice_for_constant(o, overlapping_constant, index); + self.add_static_indexed_choice_for_constant(o, overlapping_constant, index); } Some(IndexingCodePtr::Internal(o)) => { self.offset += o; @@ -224,7 +289,7 @@ impl<'a> IndexingCodeMergingPtr<'a> { break; } - IndexingLine::IndexedChoice(_) => { + IndexingLine::IndexedChoice(_) | IndexingLine::DynamicIndexedChoice(_) => { self.internalize_constant(IndexingCodePtr::Internal( indexing_code_len - self.offset, )); @@ -243,6 +308,10 @@ impl<'a> IndexingCodeMergingPtr<'a> { match &mut self.indexing_code[self.offset] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, ref mut c, ..)) => { match *c { + IndexingCodePtr::Fail if self.is_dynamic => { + *c = IndexingCodePtr::DynamicExternal(index); + break; + } IndexingCodePtr::Fail => { *c = IndexingCodePtr::External(index); break; @@ -251,6 +320,10 @@ impl<'a> IndexingCodeMergingPtr<'a> { *c = IndexingCodePtr::Internal(indexing_code_len - self.offset); self.internalize_constant(IndexingCodePtr::External(o)); } + IndexingCodePtr::DynamicExternal(o) => { + *c = IndexingCodePtr::Internal(indexing_code_len - self.offset); + self.internalize_constant(IndexingCodePtr::DynamicExternal(o)); + } IndexingCodePtr::Internal(o) => { self.offset += o; } @@ -258,11 +331,17 @@ impl<'a> IndexingCodeMergingPtr<'a> { } IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant(constants)) => { match constants.get(&constant).cloned() { + None | Some(IndexingCodePtr::Fail) if self.is_dynamic => { + constants.insert(constant, IndexingCodePtr::DynamicExternal(index)); + } None | Some(IndexingCodePtr::Fail) => { constants.insert(constant, IndexingCodePtr::External(index)); } + Some(IndexingCodePtr::DynamicExternal(o)) => { + self.add_dynamic_indexed_choice_for_constant(o, constant, index); + } Some(IndexingCodePtr::External(o)) => { - self.add_indexed_choice_for_constant(o, constant, index); + self.add_static_indexed_choice_for_constant(o, constant, index); } Some(IndexingCodePtr::Internal(o)) => { self.offset += o; @@ -272,7 +351,7 @@ impl<'a> IndexingCodeMergingPtr<'a> { break; } - IndexingLine::IndexedChoice(_) => { + IndexingLine::IndexedChoice(_) | IndexingLine::DynamicIndexedChoice(_) => { self.internalize_constant(IndexingCodePtr::Internal( indexing_code_len - self.offset, )); @@ -303,11 +382,12 @@ impl<'a> IndexingCodeMergingPtr<'a> { } if let IndexingCodePtr::Internal(_) = structure_ptr { + let last_index = self.indexing_code.len(); + self.indexing_code.push(IndexingLine::Indexing( IndexingInstruction::SwitchOnStructure(structures), )); - let last_index = self.indexing_code.len() - 1; self.indexing_code.swap(self.offset, last_index); } else { self.offset = self.indexing_code.len(); @@ -318,7 +398,7 @@ impl<'a> IndexingCodeMergingPtr<'a> { } } - fn add_indexed_choice_for_structure( + fn add_static_indexed_choice_for_structure( &mut self, external: usize, key: PredicateKey, @@ -353,6 +433,34 @@ impl<'a> IndexingCodeMergingPtr<'a> { } } + fn add_dynamic_indexed_choice_for_structure( + &mut self, + external: usize, + key: PredicateKey, + index: usize, + ) { + let third_level_index = if self.append_or_prepend.is_append() { + sdeq![external, index] + } else { + sdeq![index, external] + }; + + let indexing_code_len = self.indexing_code.len(); + self.indexing_code.push(IndexingLine::DynamicIndexedChoice(third_level_index)); + + match &mut self.indexing_code[self.offset] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnStructure(ref mut structures)) => { + structures.insert( + key, + IndexingCodePtr::Internal(indexing_code_len - self.offset), + ); + } + _ => { + unreachable!() + } + } + } + fn index_structure(&mut self, key: PredicateKey, index: usize) { loop { let indexing_code_len = self.indexing_code.len(); @@ -365,10 +473,18 @@ impl<'a> IndexingCodeMergingPtr<'a> { _, ref mut s, )) => match *s { + IndexingCodePtr::Fail if self.is_dynamic => { + *s = IndexingCodePtr::DynamicExternal(index); + break; + } IndexingCodePtr::Fail => { *s = IndexingCodePtr::External(index); break; } + IndexingCodePtr::DynamicExternal(o) => { + *s = IndexingCodePtr::Internal(indexing_code_len - self.offset); + self.internalize_structure(IndexingCodePtr::DynamicExternal(o)); + } IndexingCodePtr::External(o) => { *s = IndexingCodePtr::Internal(indexing_code_len - self.offset); self.internalize_structure(IndexingCodePtr::External(o)); @@ -379,11 +495,17 @@ impl<'a> IndexingCodeMergingPtr<'a> { }, IndexingLine::Indexing(IndexingInstruction::SwitchOnStructure(structures)) => { match structures.get(&key).cloned() { + None | Some(IndexingCodePtr::Fail) if self.is_dynamic => { + structures.insert(key, IndexingCodePtr::DynamicExternal(index)); + } None | Some(IndexingCodePtr::Fail) => { structures.insert(key, IndexingCodePtr::External(index)); } + Some(IndexingCodePtr::DynamicExternal(o)) => { + self.add_dynamic_indexed_choice_for_structure(o, key, index); + } Some(IndexingCodePtr::External(o)) => { - self.add_indexed_choice_for_structure(o, key, index); + self.add_static_indexed_choice_for_structure(o, key, index); } Some(IndexingCodePtr::Internal(o)) => { self.offset += o; @@ -393,7 +515,7 @@ impl<'a> IndexingCodeMergingPtr<'a> { break; } - IndexingLine::IndexedChoice(_) => { + IndexingLine::IndexedChoice(_) | IndexingLine::DynamicIndexedChoice(_) => { // replace this value, at self.offset, with // SwitchOnStructures, and swap this IndexedChoice // vector to the end of self.indexing_code. @@ -414,9 +536,24 @@ impl<'a> IndexingCodeMergingPtr<'a> { match &mut self.indexing_code[self.offset] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, _, ref mut l, _)) => { match *l { + IndexingCodePtr::Fail if self.is_dynamic => { + *l = IndexingCodePtr::DynamicExternal(index); + } IndexingCodePtr::Fail => { *l = IndexingCodePtr::External(index); } + IndexingCodePtr::DynamicExternal(o) => { + *l = IndexingCodePtr::Internal(indexing_code_len - self.offset); + + let third_level_index = if self.append_or_prepend.is_append() { + sdeq![o, index] + } else { + sdeq![index, o] + }; + + self.indexing_code + .push(IndexingLine::DynamicIndexedChoice(third_level_index)); + } IndexingCodePtr::External(o) => { *l = IndexingCodePtr::Internal(indexing_code_len - self.offset); @@ -459,8 +596,11 @@ pub fn merge_clause_index( AppendOrPrepend::Prepend => skeleton.first_mut().unwrap().opt_arg_index_key.take(), }; - let mut merging_ptr = - IndexingCodeMergingPtr::new(skeleton, target_indexing_code, append_or_prepend); + let mut merging_ptr = IndexingCodeMergingPtr::new( + skeleton, + target_indexing_code, + append_or_prepend, + ); match &opt_arg_index_key { OptArgIndexKey::Constant(_, index_loc, ref constant, ref overlapping_constants) => { @@ -498,17 +638,6 @@ pub fn merge_clause_index( } } -#[inline] -fn remove_instruction_with_offset(code: &mut SliceDeque, offset: usize) { - for (index, line) in code.iter().enumerate() { - if offset == line.offset() { - code.remove(index); - cap_choice_seq(code); - return; - } - } -} - pub fn remove_constant_indices( constant: &Constant, overlapping_constants: &[Constant], @@ -521,7 +650,7 @@ pub fn remove_constant_indices( match &mut indexing_code[index] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, ref mut c, ..)) => { match *c { - IndexingCodePtr::External(_) => { + IndexingCodePtr::DynamicExternal(_) | IndexingCodePtr::External(_) => { *c = IndexingCodePtr::Fail; return; } @@ -541,7 +670,6 @@ pub fn remove_constant_indices( let mut constants_index = 0; for constant in iter { - // (constant, index_loc) in iter.zip(index_locs.iter()) { loop { match &mut indexing_code[index] { IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant( @@ -550,7 +678,9 @@ pub fn remove_constant_indices( constants_index = index; match constants.get(constant).cloned() { - Some(IndexingCodePtr::External(_)) | Some(IndexingCodePtr::Fail) => { + Some(IndexingCodePtr::DynamicExternal(_)) | + Some(IndexingCodePtr::External(_)) | + Some(IndexingCodePtr::Fail) => { constants.remove(constant); break; } @@ -563,29 +693,61 @@ pub fn remove_constant_indices( } } IndexingLine::IndexedChoice(ref mut indexed_choice_instrs) => { - remove_instruction_with_offset(indexed_choice_instrs, offset); + StaticCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); if indexed_choice_instrs.len() == 1 { - let ext = IndexingCodePtr::External( - indexed_choice_instrs.pop_back().unwrap().offset(), - ); - - match &mut indexing_code[constants_index] { - IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( - _, - _, - ref mut c, - .., - )) => { - *c = ext; - } - IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant( - ref mut constants, - )) => { - constants.insert(constant.clone(), ext); + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::External( + indexed_choice_instr.offset() + ); + + match &mut indexing_code[constants_index] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + ref mut c, + .., + )) => { + *c = ext; + } + IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant( + ref mut constants, + )) => { + constants.insert(constant.clone(), ext); + } + _ => { + unreachable!() + } } - _ => { - unreachable!() + } + } + + break; + } + IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) => { + DynamicCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); + + if indexed_choice_instrs.len() == 1 { + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::DynamicExternal(indexed_choice_instr); + + match &mut indexing_code[constants_index] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + ref mut c, + .., + )) => { + *c = ext; + } + IndexingLine::Indexing(IndexingInstruction::SwitchOnConstant( + ref mut constants, + )) => { + constants.insert(constant.clone(), ext); + } + _ => { + unreachable!() + } } } } @@ -627,7 +789,7 @@ pub fn remove_structure_index( match &mut indexing_code[index] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, _, _, ref mut s)) => { match *s { - IndexingCodePtr::External(_) => { + IndexingCodePtr::DynamicExternal(_) | IndexingCodePtr::External(_) => { *s = IndexingCodePtr::Fail; return; } @@ -652,7 +814,7 @@ pub fn remove_structure_index( structures_index = index; match structures.get(&(name.clone(), arity)).cloned() { - Some(IndexingCodePtr::External(_)) => { + Some(IndexingCodePtr::DynamicExternal(_)) | Some(IndexingCodePtr::External(_)) => { structures.remove(&(name.clone(), arity)); break; } @@ -665,30 +827,61 @@ pub fn remove_structure_index( } } IndexingLine::IndexedChoice(ref mut indexed_choice_instrs) => { - remove_instruction_with_offset(indexed_choice_instrs, offset); + StaticCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); if indexed_choice_instrs.len() == 1 { - let ext = IndexingCodePtr::External( - indexed_choice_instrs.pop_back().unwrap().offset(), - ); + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::External(indexed_choice_instr.offset()); - match &mut indexing_code[structures_index] { - IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( - _, - _, - _, - _, - ref mut s, - )) => { - *s = ext; - } - IndexingLine::Indexing(IndexingInstruction::SwitchOnStructure( - ref mut structures, - )) => { - structures.insert((name.clone(), arity), ext); + match &mut indexing_code[structures_index] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + _, + _, + ref mut s, + )) => { + *s = ext; + } + IndexingLine::Indexing(IndexingInstruction::SwitchOnStructure( + ref mut structures, + )) => { + structures.insert((name.clone(), arity), ext); + } + _ => { + unreachable!() + } } - _ => { - unreachable!() + } + } + + break; + } + IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) => { + DynamicCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); + + if indexed_choice_instrs.len() == 1 { + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::DynamicExternal(indexed_choice_instr); + + match &mut indexing_code[structures_index] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + _, + _, + ref mut s, + )) => { + *s = ext; + } + IndexingLine::Indexing(IndexingInstruction::SwitchOnStructure( + ref mut structures, + )) => { + structures.insert((name.clone(), arity), ext); + } + _ => { + unreachable!() + } } } } @@ -730,7 +923,7 @@ pub fn remove_list_index(indexing_code: &mut Vec, offset: usize) { match &mut indexing_code[index] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, _, _, ref mut l, _)) => { match *l { - IndexingCodePtr::External(_) => { + IndexingCodePtr::DynamicExternal(_) | IndexingCodePtr::External(_) => { *l = IndexingCodePtr::Fail; return; } @@ -749,24 +942,49 @@ pub fn remove_list_index(indexing_code: &mut Vec, offset: usize) { match &mut indexing_code[index] { IndexingLine::IndexedChoice(ref mut indexed_choice_instrs) => { - remove_instruction_with_offset(indexed_choice_instrs, offset); + StaticCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); if indexed_choice_instrs.len() == 1 { - let ext = - IndexingCodePtr::External(indexed_choice_instrs.pop_back().unwrap().offset()); - - match &mut indexing_code[0] { - IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( - _, - _, - _, - ref mut l, - _, - )) => { - *l = ext; + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::External(indexed_choice_instr.offset()); + + match &mut indexing_code[0] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + _, + ref mut l, + _, + )) => { + *l = ext; + } + _ => { + unreachable!() + } } - _ => { - unreachable!() + } + } + } + IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) => { + DynamicCodeIndices::remove_instruction_with_offset(indexed_choice_instrs, offset); + + if indexed_choice_instrs.len() == 1 { + if let Some(indexed_choice_instr) = indexed_choice_instrs.pop_back() { + let ext = IndexingCodePtr::DynamicExternal(indexed_choice_instr); + + match &mut indexing_code[0] { + IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm( + _, + _, + _, + ref mut l, + _, + )) => { + *l = ext; + } + _ => { + unreachable!() + } } } } @@ -778,7 +996,6 @@ pub fn remove_list_index(indexing_code: &mut Vec, offset: usize) { } pub fn remove_index( - //skeleton: &[ClauseIndexInfo], opt_arg_index_key: &OptArgIndexKey, indexing_code: &mut Vec, clause_loc: usize, @@ -790,7 +1007,6 @@ pub fn remove_index( overlapping_constants, indexing_code, clause_loc, - //&skeleton[index].index_locs, ); } OptArgIndexKey::Structure(_, _, ref name, ref arity) => { @@ -799,14 +1015,12 @@ pub fn remove_index( *arity, indexing_code, clause_loc, - //&skeleton[index].index_locs, ); } OptArgIndexKey::List(..) => { remove_list_index( indexing_code, clause_loc, - //&skeleton[index].index_locs, ); } OptArgIndexKey::None => { @@ -815,64 +1029,6 @@ pub fn remove_index( } } -fn second_level_index( - indices: IndexMap>, - prelude: &mut SliceDeque, -) -> IndexMap { - let mut index_locs = IndexMap::new(); - - for (key, mut code) in indices.into_iter() { - if code.len() > 1 { - index_locs.insert(key, IndexingCodePtr::Internal(prelude.len() + 1)); - cap_choice_seq_with_trust(&mut code); - prelude.push_back(IndexingLine::from(code)); - } else { - code.first().map(|i| { - index_locs.insert(key, IndexingCodePtr::External(i.offset())); - }); - } - } - - index_locs -} - -fn switch_on( - mut instr_fn: impl FnMut(IndexMap) -> IndexingInstruction, - index: IndexMap>, - prelude: &mut SliceDeque, -) -> IndexingCodePtr { - let index = second_level_index(index, prelude); - - if index.len() > 1 { - let instr = instr_fn(index); - prelude.push_front(IndexingLine::from(instr)); - - IndexingCodePtr::Internal(1) - } else { - index - .into_iter() - .next() - .map(|(_, v)| v) - .unwrap_or(IndexingCodePtr::Fail) - } -} - -fn switch_on_list( - mut lists: SliceDeque, - prelude: &mut SliceDeque, -) -> IndexingCodePtr { - if lists.len() > 1 { - cap_choice_seq_with_trust(&mut lists); - prelude.push_back(IndexingLine::from(lists)); - IndexingCodePtr::Internal(1) - } else { - lists - .first() - .map(|i| IndexingCodePtr::External(i.offset())) - .unwrap_or(IndexingCodePtr::Fail) - } -} - #[inline] fn cap_choice_seq(prelude: &mut [IndexedChoiceInstruction]) { prelude.first_mut().map(|instr| { @@ -909,15 +1065,6 @@ fn uncap_choice_seq_with_try(prelude: &mut [IndexedChoiceInstruction]) { }); } -fn compute_index(is_first_index: bool, index: usize) -> IndexedChoiceInstruction { - // in either case, increment index to skip the IndexingLine vector. - if is_first_index { - IndexedChoiceInstruction::Try(index + 1) - } else { - IndexedChoiceInstruction::Retry(index + 1) - } -} - pub fn constant_key_alternatives(constant: &Constant, atom_tbl: TabledData) -> Vec { let mut constants = vec![]; @@ -968,43 +1115,311 @@ pub fn constant_key_alternatives(constant: &Constant, atom_tbl: TabledData } #[derive(Debug)] -pub struct CodeOffsets { +pub(crate) struct StaticCodeIndices { + constants: IndexMap>, + lists: SliceDeque, + structures: IndexMap<(ClauseName, usize), SliceDeque>, +} + +#[derive(Debug)] +pub(crate) struct DynamicCodeIndices { + constants: IndexMap>, + lists: SliceDeque, + structures: IndexMap<(ClauseName, usize), SliceDeque>, +} + +pub trait Indexer { + type ThirdLevelIndex; + + fn new() -> Self; + + fn constants(&mut self) -> &mut IndexMap>; + fn lists(&mut self) -> &mut SliceDeque; + fn structures(&mut self) -> &mut IndexMap<(ClauseName, usize), SliceDeque>; + + fn compute_index(is_initial_index: bool, index: usize) -> Self::ThirdLevelIndex; + + fn second_level_index( + indices: IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexMap; + + fn switch_on( + instr_fn: impl FnMut(IndexMap) -> IndexingInstruction, + index: &mut IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr; + + fn switch_on_list( + lists: &mut SliceDeque, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr; + + fn remove_instruction_with_offset( + code: &mut SliceDeque, + offset: usize, + ); + + fn var_offset_wrapper(var_offset: usize) -> IndexingCodePtr; +} + +impl Indexer for StaticCodeIndices { + type ThirdLevelIndex = IndexedChoiceInstruction; + + #[inline] + fn new() -> Self { + Self { + constants: IndexMap::new(), + lists: sdeq![], + structures: IndexMap::new(), + } + } + + #[inline] + fn constants(&mut self) -> &mut IndexMap> { + &mut self.constants + } + + #[inline] + fn lists(&mut self) -> &mut SliceDeque { + &mut self.lists + } + + #[inline] + fn structures(&mut self) -> &mut IndexMap<(ClauseName, usize), SliceDeque> { + &mut self.structures + } + + fn compute_index(is_initial_index: bool, index: usize) -> IndexedChoiceInstruction { + if is_initial_index { + IndexedChoiceInstruction::Try(index + 1) + } else { + IndexedChoiceInstruction::Retry(index + 1) + } + } + + fn second_level_index( + indices: IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexMap { + let mut index_locs = IndexMap::new(); + + for (key, mut code) in indices.into_iter() { + if code.len() > 1 { + index_locs.insert(key, IndexingCodePtr::Internal(prelude.len() + 1)); + cap_choice_seq_with_trust(&mut code); + prelude.push_back(IndexingLine::from(code)); + } else { + code.first().map(|i| { + index_locs.insert(key, IndexingCodePtr::External(i.offset())); + }); + } + } + + index_locs + } + + fn switch_on( + mut instr_fn: impl FnMut(IndexMap) -> IndexingInstruction, + index: &mut IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr { + let index = mem::replace(index, IndexMap::new()); + let index = Self::second_level_index(index, prelude); + + if index.len() > 1 { + let instr = instr_fn(index); + prelude.push_front(IndexingLine::from(instr)); + + IndexingCodePtr::Internal(1) + } else { + index + .into_iter() + .next() + .map(|(_, v)| v) + .unwrap_or(IndexingCodePtr::Fail) + } + } + + fn switch_on_list( + lists: &mut SliceDeque, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr { + if lists.len() > 1 { + cap_choice_seq_with_trust(lists); + let lists = mem::replace(lists, sdeq![]); + prelude.push_back(IndexingLine::from(lists)); + + IndexingCodePtr::Internal(1) + } else { + lists + .first() + .map(|i| IndexingCodePtr::External(i.offset())) + .unwrap_or(IndexingCodePtr::Fail) + } + } + + #[inline] + fn remove_instruction_with_offset(code: &mut SliceDeque, offset: usize) { + for (index, line) in code.iter().enumerate() { + if offset == line.offset() { + code.remove(index); + cap_choice_seq(code); + return; + } + } + } + + #[inline] + fn var_offset_wrapper(var_offset: usize) -> IndexingCodePtr { + IndexingCodePtr::External(var_offset) + } +} + +impl Indexer for DynamicCodeIndices { + type ThirdLevelIndex = usize; + + #[inline] + fn new() -> Self { + Self { + constants: IndexMap::new(), + lists: sdeq![], + structures: IndexMap::new(), + } + } + + #[inline] + fn constants(&mut self) -> &mut IndexMap> { + &mut self.constants + } + + #[inline] + fn lists(&mut self) -> &mut SliceDeque { + &mut self.lists + } + + #[inline] + fn structures(&mut self) -> &mut IndexMap<(ClauseName, usize), SliceDeque> { + &mut self.structures + } + + #[inline] + fn compute_index(_: bool, index: usize) -> usize { + index + 1 + } + + fn second_level_index( + indices: IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexMap { + let mut index_locs = IndexMap::new(); + + for (key, code) in indices.into_iter() { + if code.len() > 1 { + index_locs.insert(key, IndexingCodePtr::Internal(prelude.len() + 1)); + prelude.push_back(IndexingLine::DynamicIndexedChoice(code)); + } else { + code.first().map(|i| { + index_locs.insert(key, IndexingCodePtr::DynamicExternal(*i)); + }); + } + } + + index_locs + } + + fn switch_on( + mut instr_fn: impl FnMut(IndexMap) -> IndexingInstruction, + index: &mut IndexMap>, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr { + let index = mem::replace(index, IndexMap::new()); + let index = Self::second_level_index(index, prelude); + + if index.len() > 1 { + let instr = instr_fn(index); + prelude.push_front(IndexingLine::from(instr)); + + IndexingCodePtr::Internal(1) + } else { + index + .into_iter() + .next() + .map(|(_, v)| v) + .unwrap_or(IndexingCodePtr::Fail) + } + } + + fn switch_on_list( + lists: &mut SliceDeque, + prelude: &mut SliceDeque, + ) -> IndexingCodePtr { + if lists.len() > 1 { + let lists = mem::replace(lists, sdeq![]); + prelude.push_back(IndexingLine::DynamicIndexedChoice(lists)); + IndexingCodePtr::Internal(1) + } else { + lists + .first() + .map(|i| IndexingCodePtr::DynamicExternal(*i)) + .unwrap_or(IndexingCodePtr::Fail) + } + } + + #[inline] + fn remove_instruction_with_offset(code: &mut SliceDeque, offset: usize) { + for (index, line) in code.iter().enumerate() { + if offset == *line { + code.remove(index); + return; + } + } + } + + #[inline] + fn var_offset_wrapper(var_offset: usize) -> IndexingCodePtr { + IndexingCodePtr::DynamicExternal(var_offset) + } +} + +#[derive(Debug)] +pub struct CodeOffsets { atom_tbl: TabledData, - pub constants: IndexMap>, - pub lists: SliceDeque, - pub structures: IndexMap<(ClauseName, usize), SliceDeque>, + indices: I, optimal_index: usize, } -impl CodeOffsets { - pub fn new(atom_tbl: TabledData, optimal_index: usize) -> Self { +impl CodeOffsets { + pub fn new( + atom_tbl: TabledData, + indices: I, + optimal_index: usize, + ) -> Self { CodeOffsets { atom_tbl, - constants: IndexMap::new(), - lists: sdeq![], - structures: IndexMap::new(), + indices, optimal_index, } } fn index_list(&mut self, index: usize) { - let is_initial_index = self.lists.is_empty(); - self.lists.push_back(compute_index(is_initial_index, index)); + let is_initial_index = self.indices.lists().is_empty(); + let index = I::compute_index(is_initial_index, index); + self.indices.lists().push_back(index); } fn index_constant(&mut self, constant: &Constant, index: usize) -> Vec { let overlapping_constants = constant_key_alternatives(constant, self.atom_tbl.clone()); - - let code = self.constants.entry(constant.clone()).or_insert(sdeq![]); + let code = self.indices.constants().entry(constant.clone()).or_insert(sdeq![]); let is_initial_index = code.is_empty(); - code.push_back(compute_index(is_initial_index, index)); + code.push_back(I::compute_index(is_initial_index, index)); for constant in &overlapping_constants { - let code = self.constants.entry(constant.clone()).or_insert(sdeq![]); + let code = self.indices.constants().entry(constant.clone()).or_insert(sdeq![]); let is_initial_index = code.is_empty(); - let index = compute_index(is_initial_index, index); + let index = I::compute_index(is_initial_index, index); code.push_back(index); } @@ -1013,15 +1428,15 @@ impl CodeOffsets { } fn index_structure(&mut self, name: &ClauseName, arity: usize, index: usize) -> usize { - let code = self - .structures + let code = self.indices + .structures() .entry((name.clone(), arity)) .or_insert(sdeq![]); let code_len = code.len(); let is_initial_index = code.is_empty(); - code.push_back(compute_index(is_initial_index, index)); + code.push_back(I::compute_index(is_initial_index, index)); code_len } @@ -1057,15 +1472,15 @@ impl CodeOffsets { } } - pub fn no_indices(&self) -> bool { - let no_constants = self.constants.is_empty(); - let no_structures = self.structures.is_empty(); - let no_lists = self.lists.is_empty(); + pub fn no_indices(&mut self) -> bool { + let no_constants = self.indices.constants().is_empty(); + let no_structures = self.indices.structures().is_empty(); + let no_lists = self.indices.lists().is_empty(); no_constants && no_structures && no_lists } - pub fn compute_indices(self, skip_stub_try_me_else: bool) -> Vec { + pub fn compute_indices(mut self, skip_stub_try_me_else: bool) -> Vec { if self.no_indices() { return vec![]; } @@ -1075,23 +1490,23 @@ impl CodeOffsets { let mut emitted_switch_on_structure = false; let mut emitted_switch_on_constant = false; - let mut lst_loc = switch_on_list(self.lists, &mut prelude); + let mut lst_loc = I::switch_on_list(self.indices.lists(), &mut prelude); - let mut str_loc = switch_on( + let mut str_loc = I::switch_on( |index| { emitted_switch_on_structure = true; IndexingInstruction::SwitchOnStructure(index) }, - self.structures, + self.indices.structures(), &mut prelude, ); - let con_loc = switch_on( + let con_loc = I::switch_on( |index| { emitted_switch_on_constant = true; IndexingInstruction::SwitchOnConstant(index) }, - self.constants, + self.indices.constants(), &mut prelude, ); @@ -1114,7 +1529,7 @@ impl CodeOffsets { prelude.push_front(IndexingLine::from(IndexingInstruction::SwitchOnTerm( self.optimal_index, - var_offset, + I::var_offset_wrapper(var_offset), con_loc, lst_loc, str_loc, diff --git a/src/instructions.rs b/src/instructions.rs index 5cdf472d..e552c8e3 100644 --- a/src/instructions.rs +++ b/src/instructions.rs @@ -46,8 +46,33 @@ impl ArithmeticTerm { } } +#[derive(Debug, Clone, Copy)] +pub enum NextOrFail { + Next(usize), + Fail(usize), +} + +impl NextOrFail { + #[inline] + pub fn is_next(&self) -> bool { + if let NextOrFail::Next(_) = self { + true + } else { + false + } + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +pub enum Death { + Finite(usize), + Infinity, +} + #[derive(Debug)] pub enum ChoiceInstruction { + DynamicElse(usize, Death, NextOrFail), + DynamicInternalElse(usize, Death, NextOrFail), DefaultRetryMeElse(usize), DefaultTrustMe(usize), RetryMeElse(usize), @@ -56,8 +81,76 @@ pub enum ChoiceInstruction { } impl ChoiceInstruction { - pub fn to_functor(&self) -> MachineStub { + pub fn to_functor(&self, h: usize) -> MachineStub { match self { + &ChoiceInstruction::DynamicElse(birth, death, next_or_fail) => { + match (death, next_or_fail) { + (Death::Infinity, NextOrFail::Next(i)) => { + functor!( + "dynamic_else", + [integer(birth), atom("inf"), integer(i)] + ) + } + (Death::Infinity, NextOrFail::Fail(i)) => { + let next_functor = functor!("fail", [integer(i)]); + + functor!( + "dynamic_else", + [integer(birth), atom("inf"), aux(h, 0)], + [next_functor] + ) + } + (Death::Finite(d), NextOrFail::Fail(i)) => { + let next_functor = functor!("fail", [integer(i)]); + + functor!( + "dynamic_else", + [integer(birth), integer(d), aux(h, 0)], + [next_functor] + ) + } + (Death::Finite(d), NextOrFail::Next(i)) => { + functor!( + "dynamic_else", + [integer(birth), integer(d), integer(i)] + ) + } + } + } + &ChoiceInstruction::DynamicInternalElse(birth, death, next_or_fail) => { + match (death, next_or_fail) { + (Death::Infinity, NextOrFail::Next(i)) => { + functor!( + "dynamic_internal_else", + [integer(birth), atom("inf"), integer(i)] + ) + } + (Death::Infinity, NextOrFail::Fail(i)) => { + let next_functor = functor!("fail", [integer(i)]); + + functor!( + "dynamic_internal_else", + [integer(birth), atom("inf"), aux(h, 0)], + [next_functor] + ) + } + (Death::Finite(d), NextOrFail::Fail(i)) => { + let next_functor = functor!("fail", [integer(i)]); + + functor!( + "dynamic_internal_else", + [integer(birth), integer(d), aux(h, 0)], + [next_functor] + ) + } + (Death::Finite(d), NextOrFail::Next(i)) => { + functor!( + "dynamic_internal_else", + [integer(birth), integer(d), integer(i)] + ) + } + } + } &ChoiceInstruction::TryMeElse(offset) => { functor!("try_me_else", [integer(offset)]) } @@ -143,6 +236,7 @@ impl IndexedChoiceInstruction { pub enum IndexingLine { Indexing(IndexingInstruction), IndexedChoice(SliceDeque), + DynamicIndexedChoice(SliceDeque), } impl From for IndexingLine { @@ -168,6 +262,7 @@ pub enum Line { Fact(FactInstruction), IndexingCode(Vec), IndexedChoice(IndexedChoiceInstruction), + DynamicIndexedChoice(usize), Query(QueryInstruction), } @@ -184,7 +279,7 @@ impl Line { pub fn enqueue_functors(&self, mut h: usize, functors: &mut Vec) { match self { &Line::Arithmetic(ref arith_instr) => functors.push(arith_instr.to_functor(h)), - &Line::Choice(ref choice_instr) => functors.push(choice_instr.to_functor()), + &Line::Choice(ref choice_instr) => functors.push(choice_instr.to_functor(h)), &Line::Control(ref control_instr) => functors.push(control_instr.to_functor()), &Line::Cut(ref cut_instr) => functors.push(cut_instr.to_functor(h)), &Line::Fact(ref fact_instr) => functors.push(fact_instr.to_functor(h)), @@ -203,12 +298,22 @@ impl Line { functors.push(section); } } + IndexingLine::DynamicIndexedChoice(indexed_choice_instrs) => { + for indexed_choice_instr in indexed_choice_instrs { + let section = functor!("dynamic", [integer(*indexed_choice_instr)]); + h += section.len(); + functors.push(section); + } + } } } } &Line::IndexedChoice(ref indexed_choice_instr) => { functors.push(indexed_choice_instr.to_functor()) } + &Line::DynamicIndexedChoice(ref indexed_choice_instr) => { + functors.push(functor!("dynamic", [integer(*indexed_choice_instr)])); + } &Line::Query(ref query_instr) => functors.push(query_instr.to_functor(h)), } } @@ -454,7 +559,7 @@ pub enum IndexingInstruction { // The first index is the optimal argument being indexed. SwitchOnTerm( usize, - usize, + IndexingCodePtr, IndexingCodePtr, IndexingCodePtr, IndexingCodePtr, @@ -471,7 +576,7 @@ impl IndexingInstruction { "switch_on_term", [ integer(arg), - integer(vars), + indexing_code_ptr(h, vars), indexing_code_ptr(h, constants), indexing_code_ptr(h, lists), indexing_code_ptr(h, structures) diff --git a/src/lib/builtins.pl b/src/lib/builtins.pl index abf650c2..bc393c40 100644 --- a/src/lib/builtins.pl +++ b/src/lib/builtins.pl @@ -802,11 +802,11 @@ setof(Template, Goal, Solution) :- ; functor(H, Name, Arity) -> ( Name == '.' -> throw(error(type_error(callable, H), clause/2)) - ; '$no_such_predicate'(Module, H) -> - '$fail' ; '$head_is_dynamic'(Module, H) -> '$clause_body_is_valid'(B), Module:'$clause'(H, B) + ; '$no_such_predicate'(Module, H) -> + '$fail' ; throw(error(permission_error(access, private_procedure, Name/Arity), clause/2)) ) @@ -825,12 +825,12 @@ clause(H, B) :- arg(1, H, Module), arg(2, H, F), '$module_clause'(F, B, Module) - ; '$no_such_predicate'(user, H) -> %% '$no_such_predicate' fails if - %% H is not callable. - '$fail' ; '$head_is_dynamic'(user, H) -> '$clause_body_is_valid'(B), '$clause'(H, B) + ; '$no_such_predicate'(user, H) -> %% '$no_such_predicate' fails if + %% H is not callable. + '$fail' ; throw(error(permission_error(access, private_procedure, Name/Arity), clause/2)) ) @@ -865,10 +865,10 @@ asserta_clause(Head, Body) :- arg(1, Head, Module), arg(2, Head, F), module_asserta_clause(F, Body, Module) - ; '$no_such_predicate'(user, Head) -> - call_asserta(Head, Body, Name, Arity, user) ; '$head_is_dynamic'(user, Head) -> call_asserta(Head, Body, Name, Arity, user) + ; '$no_such_predicate'(user, Head) -> + call_asserta(Head, Body, Name, Arity, user) ; throw(error(permission_error(modify, static_procedure, Name/Arity), asserta/1)) ) ; throw(error(type_error(callable, Head), asserta/1)) @@ -889,10 +889,10 @@ module_assertz_clause(Head, Body, Module) :- ; functor(Head, Name, Arity), atom(Name), Name \== '.' -> - ( '$no_such_predicate'(Module, Head) -> - call_assertz(Head, Body, Name, Arity, Module) - ; '$head_is_dynamic'(Module, Head) -> + ( '$head_is_dynamic'(Module, Head) -> call_assertz(Head, Body, Name, Arity, Module) + ; '$no_such_predicate'(Module, Head) -> + call_assertz(Head, Body, Name, Arity, Module) ; throw(error(permission_error(modify, static_procedure, Name/Arity), assertz/1)) ) @@ -916,10 +916,10 @@ assertz_clause(Head, Body) :- arg(1, Head, Module), arg(2, Head, F), module_assertz_clause(F, Body, Module) - ; '$no_such_predicate'(user, Head) -> - call_assertz(Head, Body, Name, Arity, user) ; '$head_is_dynamic'(user, Head) -> call_assertz(Head, Body, Name, Arity, user) + ; '$no_such_predicate'(user, Head) -> + call_assertz(Head, Body, Name, Arity, user) ; throw(error(permission_error(modify, static_procedure, Name/Arity), assertz/1)) ) @@ -939,11 +939,13 @@ assertz(Clause) :- module_retract_clauses([Clause|Clauses0], Head, Body, Name, Arity, Module) :- functor(VarHead, Name, Arity), findall((VarHead :- VarBody), Module:'$clause'(VarHead, VarBody), Clauses1), - first_match_index(Clauses1, (Head :- Body), 0, N), + ( first_match_index(Clauses1, (Head :- Body), 0, N) -> + '$retract_clause'(Name, Arity, N, Module) + ; Clause = (Head :- Body) + ), ( Clauses0 == [] -> ! ; true - ), - '$retract_clause'(Name, Arity, N, Module). + ). module_retract_clauses([_|Clauses0], Head, Body, Name, Arity, Module) :- module_retract_clauses(Clauses0, Head, Body, Name, Arity, Module). @@ -969,22 +971,22 @@ retract_module_clause(Head, Body, Module) :- ). -first_match_index([Clause0 | Clauses], Clause1, N0, N) :- - ( Clause0 \= Clause1 -> - N1 is N0 + 1, - first_match_index(Clauses, Clause1, N1, N) - ; N0 = N, - Clause0 = Clause1 - ). +first_match_index([Clause | Clauses], Clause, N, N) :- + !. +first_match_index([_ | Clauses], Clause, N0, N) :- + N1 is N0 + 1, + first_match_index(Clauses, Clause, N1, N). retract_clauses([Clause | Clauses0], Head, Body, Name, Arity) :- functor(VarHead, Name, Arity), findall((VarHead :- VarBody), builtins:'$clause'(VarHead, VarBody), Clauses1), - first_match_index(Clauses1, (Head :- Body), 0, N), + ( first_match_index(Clauses1, (Head :- Body), 0, N) -> + '$retract_clause'(Name, Arity, N, user) + ; Clause = (Head :- Body) + ), ( Clauses0 == [] -> ! ; true - ), - '$retract_clause'(Name, Arity, N, user). + ). retract_clauses([_ | Clauses0], Head, Body, Name, Arity) :- retract_clauses(Clauses0, Head, Body, Name, Arity). @@ -1065,10 +1067,10 @@ abolish(Pred) :- ; max_arity(N), Arity > N -> throw(error(representation_error(max_arity), abolish/1)) ; functor(Head, Name, Arity) -> - ( '$no_such_predicate'(user, Head) -> - true - ; '$head_is_dynamic'(user, Head) -> + ( '$head_is_dynamic'(user, Head) -> '$abolish_clause'(user, Name, Arity) + ; '$no_such_predicate'(user, Head) -> + true ; throw(error(permission_error(modify, static_procedure, Pred), abolish/1)) ) ) diff --git a/src/machine/code_repo.rs b/src/machine/code_repo.rs index 7db42530..1a812b58 100644 --- a/src/machine/code_repo.rs +++ b/src/machine/code_repo.rs @@ -37,6 +37,9 @@ impl CodeRepo { &IndexingLine::IndexedChoice(ref indexed_choice_instrs) => { RefOrOwned::Owned(Line::IndexedChoice(indexed_choice_instrs[i])) } + &IndexingLine::DynamicIndexedChoice(ref indexed_choice_instrs) => { + RefOrOwned::Owned(Line::DynamicIndexedChoice(indexed_choice_instrs[i])) + } _ => { unreachable!() } @@ -86,11 +89,98 @@ impl CodeRepo { &CodePtr::VerifyAttrInterrupt(p) => { Some(RefOrOwned::Borrowed(&self.code[p])) } -/* - &CodePtr::DynamicTransaction(..) => { - None + } + } + + pub(super) + fn find_living_dynamic_else(&self, mut p: usize, cc: usize) -> Option<(usize, usize)> { + loop { + match &self.code[p] { + &Line::Choice(ChoiceInstruction::DynamicElse(birth, death, NextOrFail::Next(i))) => { + if birth < cc && Death::Finite(cc) <= death { + return Some((p, i)); + } else if i > 0 { + p += i; + } else { + return None; + } + } + &Line::Choice(ChoiceInstruction::DynamicElse(birth, death, NextOrFail::Fail(_))) => { + if birth < cc && Death::Finite(cc) <= death { + return Some((p, 0)); + } else { + return None; + } + } + &Line::Choice(ChoiceInstruction::DynamicInternalElse( + birth, + death, + NextOrFail::Next(i), + )) => { + if birth < cc && Death::Finite(cc) <= death { + return Some((p, i)); + } else if i > 0 { + p += i; + } else { + return None; + } + } + &Line::Choice(ChoiceInstruction::DynamicInternalElse( + birth, + death, + NextOrFail::Fail(_)), + ) => { + if birth < cc && Death::Finite(cc) <= death { + return Some((p, 0)); + } else { + return None; + } + } + &Line::Control(ControlInstruction::RevJmpBy(i)) => { + p -= i; + } + _ => { + unreachable!(); + } + } + } + } + + pub(super) + fn find_living_dynamic(&self, p: LocalCodePtr, cc: usize) -> Option<(usize, usize, usize, bool)> { + let (p, oi, mut ii) = match p { + LocalCodePtr::IndexingBuf(p, oi, ii) => (p, oi, ii), + _ => unreachable!(), + }; + + let indexed_choice_instrs = match &self.code[p] { + Line::IndexingCode(ref indexing_code) => match &indexing_code[oi] { + IndexingLine::DynamicIndexedChoice(ref indexed_choice_instrs) => { + indexed_choice_instrs + } + _ => unreachable!() + } + _ => unreachable!() + }; + + loop { + match &indexed_choice_instrs.get(ii) { + Some(&offset) => { + match &self.code[p + offset - 1] { + &Line::Choice(ChoiceInstruction::DynamicInternalElse( + birth, death, next_or_fail, + )) => { + if birth < cc && Death::Finite(cc) <= death { + return Some((offset, oi, ii, next_or_fail.is_next())); + } else { + ii += 1; + } + } + _ => unreachable!(), + } + } + None => return None, } -*/ } } } diff --git a/src/machine/code_walker.rs b/src/machine/code_walker.rs index 94944889..2d199fd6 100644 --- a/src/machine/code_walker.rs +++ b/src/machine/code_walker.rs @@ -11,6 +11,14 @@ fn capture_offset(line: &Line, index: usize, stack: &mut Vec) -> bool { &Line::Choice(ChoiceInstruction::RetryMeElse(offset)) if offset > 0 => { stack.push(index + offset); } + &Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(offset))) + if offset > 0 => { + stack.push(index + offset); + } + &Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(offset))) + if offset > 0 => { + stack.push(index + offset); + } &Line::Control(ControlInstruction::JmpBy(_, offset, _, false)) => { stack.push(index + offset); } diff --git a/src/machine/compile.rs b/src/machine/compile.rs index ebdcb134..bfea3f2f 100644 --- a/src/machine/compile.rs +++ b/src/machine/compile.rs @@ -2,7 +2,7 @@ use prolog_parser::clause_name; use crate::codegen::*; use crate::debray_allocator::*; -use crate::indexing::{merge_clause_index, remove_index}; +use crate::indexing::{IndexingCodePtr, merge_clause_index, remove_index}; use crate::machine::load_state::*; use crate::machine::loader::*; use crate::machine::preprocessor::*; @@ -74,7 +74,12 @@ pub(super) fn compile_appendix( } // false because the inner predicate is a one-off, hence not extensible. - let settings = CodeGenSettings::new(false, non_counted_bt); + let settings = CodeGenSettings { + global_clock_tick: None, + is_extensible: false, + non_counted_bt, + }; + let mut cg = CodeGenerator::::new(atom_tbl.clone(), settings); let tl = queue.pop_front().unwrap(); @@ -115,11 +120,22 @@ fn derelictize_try_me_else( retraction_info: &mut RetractionInfo, ) -> Option { match &mut code[index] { + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(0))) => None, + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(ref mut o))) => { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(index, *o)); + Some(mem::replace(o, 0)) + } + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(0))) => None, + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(ref mut o))) => { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(index, *o)); + Some(mem::replace(o, 0)) + } + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Fail(_))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Fail(_))) => None, Line::Choice(ChoiceInstruction::TryMeElse(0)) => None, - Line::Choice(ChoiceInstruction::TryMeElse(ref mut offset)) => { - retraction_info.push_record(RetractionRecord::ModifiedTryMeElse(index, *offset)); - - Some(mem::replace(offset, 0)) + Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) => { + retraction_info.push_record(RetractionRecord::ModifiedTryMeElse(index, *o)); + Some(mem::replace(o, 0)) } _ => { unreachable!() @@ -165,23 +181,80 @@ fn merge_indices( } } -fn find_inner_choice_instr(code: &Code, mut index: usize, index_loc: usize) -> usize { +fn find_outer_choice_instr( + code: &Code, + mut index: usize, +) -> usize { loop { match &code[index] { - Line::Choice(ChoiceInstruction::TryMeElse(o)) - | Line::Choice(ChoiceInstruction::RetryMeElse(o)) => { + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(i))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(i))) + if *i > 0 => + { + index += i; + } + _ => { + return index; + } + } + } +} + +fn find_inner_choice_instr( + code: &Code, + mut index: usize, + index_loc: usize, +) -> usize { + loop { + match &code[index] { + Line::Choice(ChoiceInstruction::TryMeElse(o)) | + Line::Choice(ChoiceInstruction::RetryMeElse(o)) => { if *o > 0 { return index; } else { index = index_loc; } } + &Line::Choice(ChoiceInstruction::DynamicElse(_, _, next_or_fail)) | + &Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, next_or_fail)) => { + match next_or_fail { + NextOrFail::Next(i) => { + if i == 0 { + index = index_loc; + } else { + return index; + } + } + NextOrFail::Fail(_) => { + return index; + } + } + } Line::Choice(ChoiceInstruction::TrustMe(_)) => { return index; } Line::IndexingCode(indexing_code) => match &indexing_code[0] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, v, ..)) => { - index += v; + match v { + IndexingCodePtr::External(v) => { + index += v; + } + IndexingCodePtr::DynamicExternal(v) => { + match &code[index + v] { + &Line::Choice(ChoiceInstruction::DynamicInternalElse( + _, + _, + NextOrFail::Next(0), + )) => { + return index + v; + } + _ => { + index += v; + } + } + } + _ => unreachable!() + } } _ => { unreachable!(); @@ -253,7 +326,7 @@ fn merge_indexed_subsequences( match &mut code[inner_try_me_else_loc] { Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) => { retraction_info.push_record(RetractionRecord::ModifiedTryMeElse( - skeleton.clauses[upper_lower_bound].clause_start, + inner_try_me_else_loc, *o, )); @@ -357,9 +430,35 @@ fn blunt_leading_choice_instr( return instr_loc; } - Line::Choice(ChoiceInstruction::TrustMe(offset)) => { + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(_))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(_))) => { + return instr_loc; + } + &mut Line::Choice(ChoiceInstruction::DynamicElse(b, d, NextOrFail::Fail(o))) => { + retraction_info.push_record( + RetractionRecord::AppendedNextOrFail(instr_loc, NextOrFail::Fail(o)), + ); + + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicElse(b, d, NextOrFail::Next(0)), + ); + + return instr_loc; + } + &mut Line::Choice(ChoiceInstruction::DynamicInternalElse(b, d, NextOrFail::Fail(o))) => { + retraction_info.push_record( + RetractionRecord::AppendedNextOrFail(instr_loc, NextOrFail::Fail(o)), + ); + + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicInternalElse(b, d, NextOrFail::Next(0)), + ); + + return instr_loc; + } + Line::Choice(ChoiceInstruction::TrustMe(o)) => { retraction_info - .push_record(RetractionRecord::AppendedTrustMe(instr_loc, *offset, false)); + .push_record(RetractionRecord::AppendedTrustMe(instr_loc, *o, false)); code[instr_loc] = Line::Choice(ChoiceInstruction::TryMeElse(0)); return instr_loc + 1; @@ -388,15 +487,22 @@ fn set_switch_var_offset_to_choice_instr( ) { let target_indexing_line = to_indexing_line_mut(&mut code[index_loc]).unwrap(); - let v = match &mut target_indexing_line[0] { - IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, v, ..)) => *v, + let v = match &target_indexing_line[0] { + &IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, v, ..)) => { + match v { + IndexingCodePtr::External(v) | IndexingCodePtr::DynamicExternal(v) => v, + _ => unreachable!() + } + } _ => { unreachable!(); } }; match &code[index_loc + v] { - Line::Choice(ChoiceInstruction::TryMeElse(_)) => {} + Line::Choice(ChoiceInstruction::TryMeElse(_)) | + Line::Choice(ChoiceInstruction::DynamicElse(..)) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(..)) => {} _ => { set_switch_var_offset(code, index_loc, offset, retraction_info); } @@ -414,7 +520,15 @@ fn set_switch_var_offset( let old_v = match &mut target_indexing_line[0] { IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(_, ref mut v, ..)) => { - mem::replace(v, offset) + match *v { + IndexingCodePtr::DynamicExternal(_) => { + mem::replace(v, IndexingCodePtr::DynamicExternal(offset)) + } + IndexingCodePtr::External(_) => { + mem::replace(v, IndexingCodePtr::External(offset)) + } + _ => unreachable!() + } } _ => { unreachable!() @@ -432,6 +546,53 @@ fn internalize_choice_instr_at( retraction_info: &mut RetractionInfo, ) { match &mut code[instr_loc] { + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Fail(_))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Fail(_))) => { + } + Line::Choice(ChoiceInstruction::DynamicElse(_, _, ref mut o @ NextOrFail::Next(0))) => { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(instr_loc, 0)); + *o = NextOrFail::Fail(0); + } + &mut Line::Choice(ChoiceInstruction::DynamicElse(b, d, NextOrFail::Next(o))) => { + retraction_info.push_record( + RetractionRecord::AppendedNextOrFail(instr_loc, NextOrFail::Next(o)), + ); + + match &mut code[instr_loc + o] { + Line::Control(ControlInstruction::RevJmpBy(p)) if *p == 0 => { + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicElse(b, d, NextOrFail::Fail(o)), + ); + } + _ => { + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicElse(b, d, NextOrFail::Next(o)), + ); + } + } + } + Line::Choice(ChoiceInstruction::DynamicInternalElse( + _, _, ref mut o @ NextOrFail::Next(0), + )) => { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(instr_loc, 0)); + *o = NextOrFail::Fail(0); + } + &mut Line::Choice(ChoiceInstruction::DynamicInternalElse(b, d, NextOrFail::Next(o))) => { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(instr_loc, o)); + + match &mut code[instr_loc + o] { + Line::Control(ControlInstruction::RevJmpBy(p)) if *p == 0 => { + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicInternalElse(b, d, NextOrFail::Fail(o)), + ); + } + _ => { + code[instr_loc] = Line::Choice( + ChoiceInstruction::DynamicInternalElse(b, d, NextOrFail::Next(o)), + ); + } + } + } Line::Choice(ChoiceInstruction::TryMeElse(0)) => { retraction_info.push_record(RetractionRecord::ModifiedTryMeElse(instr_loc, 0)); @@ -465,8 +626,8 @@ fn thread_choice_instr_at_to( ) { loop { match &mut code[instr_loc] { - Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) - | Line::Choice(ChoiceInstruction::RetryMeElse(ref mut o)) + Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) | + Line::Choice(ChoiceInstruction::RetryMeElse(ref mut o)) if target_loc >= instr_loc => { retraction_info.push_record(RetractionRecord::ReplacedChoiceOffset(instr_loc, *o)); @@ -474,8 +635,20 @@ fn thread_choice_instr_at_to( *o = target_loc - instr_loc; return; } - Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) - | Line::Choice(ChoiceInstruction::RetryMeElse(ref mut o)) => { + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(ref mut o))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(ref mut o))) + if target_loc >= instr_loc => + { + retraction_info.push_record(RetractionRecord::ReplacedDynamicElseOffset(instr_loc, *o)); + *o = target_loc - instr_loc; + return; + } + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Next(ref mut o))) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Next(ref mut o))) => { + instr_loc += *o; + } + Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) | + Line::Choice(ChoiceInstruction::RetryMeElse(ref mut o)) => { instr_loc += *o; } Line::Control(ControlInstruction::RevJmpBy(ref mut o)) if instr_loc >= target_loc => { @@ -484,6 +657,44 @@ fn thread_choice_instr_at_to( *o = instr_loc - target_loc; return; } + &mut Line::Choice(ChoiceInstruction::DynamicElse(birth, death, ref mut fail)) + if target_loc >= instr_loc => + { + retraction_info.push_record( + RetractionRecord::AppendedNextOrFail(instr_loc, *fail), + ); + + code[instr_loc] = + Line::Choice(ChoiceInstruction::DynamicElse( + birth, death, NextOrFail::Next(target_loc - instr_loc), + )); + + return; + } + Line::Choice(ChoiceInstruction::DynamicElse(_, _, NextOrFail::Fail(o))) + if *o > 0 => + { + instr_loc += *o; + } + &mut Line::Choice(ChoiceInstruction::DynamicInternalElse(birth, death, ref mut fail)) + if target_loc >= instr_loc => + { + retraction_info.push_record( + RetractionRecord::AppendedNextOrFail(instr_loc, *fail), + ); + + code[instr_loc] = + Line::Choice(ChoiceInstruction::DynamicInternalElse( + birth, death, NextOrFail::Next(target_loc - instr_loc), + )); + + return; + } + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, _, NextOrFail::Fail(o))) + if *o > 0 => + { + instr_loc += *o; + } Line::Choice(ChoiceInstruction::TrustMe(ref mut o)) if target_loc >= instr_loc => { retraction_info.push_record( RetractionRecord::AppendedTrustMe(instr_loc, *o, false), @@ -619,6 +830,29 @@ fn remove_leading_unindexed_clause( } } +fn find_dynamic_outer_choice_instr( + code: &Code, + index_loc: usize, +) -> usize { + match &code[index_loc] { + Line::IndexingCode(indexing_code) => { + match &indexing_code[0] { + &IndexingLine::Indexing( + IndexingInstruction::SwitchOnTerm( + _, + IndexingCodePtr::DynamicExternal(v), + .., + ) + ) => { + index_loc + v - 2 + } + _ => unreachable!() + } + } + _ => unreachable!() + } +} + fn prepend_compiled_clause( code: &mut Code, compilation_target: CompilationTarget, @@ -626,14 +860,25 @@ fn prepend_compiled_clause( mut clause_code: Code, skeleton: &mut PredicateSkeleton, retraction_info: &mut RetractionInfo, -) -> usize { + global_clock_tick: usize, +) -> IndexPtr { let clause_loc = code.len(); let mut prepend_queue = sdeq![]; let target_arg_num = skeleton.clauses[0].opt_arg_index_key.arg_num(); let head_arg_num = skeleton.clauses[1].opt_arg_index_key.arg_num(); + + let settings = CodeGenSettings { + global_clock_tick: if skeleton.is_dynamic { + Some(global_clock_tick) + } else { + None + }, + is_extensible: true, + non_counted_bt: false, + }; - if skeleton.clauses[0] + let clause_loc = if skeleton.clauses[0] .opt_arg_index_key .switch_on_term_loc() .is_some() @@ -650,7 +895,11 @@ fn prepend_compiled_clause( skeleton.clauses[0].clause_start, )); - let outer_thread_choice_loc = skeleton.clauses[1].clause_start - 2; + let outer_thread_choice_loc = if skeleton.is_dynamic { + find_dynamic_outer_choice_instr(code, index_loc) + } else { + skeleton.clauses[1].clause_start - 2 + }; retraction_info.push_record(RetractionRecord::SkeletonClauseStartReplaced( compilation_target, @@ -669,9 +918,9 @@ fn prepend_compiled_clause( inner_thread_rev_offset, ))); - prepend_queue.push_front(Line::Choice(ChoiceInstruction::TryMeElse( - prepend_queue.len(), - ))); + prepend_queue.push_front(Line::Choice( + settings.internal_try_me_else(prepend_queue.len()), + )); // prepend_queue is now: // | TryMeElse N_2 @@ -716,9 +965,9 @@ fn prepend_compiled_clause( } }; - prepend_queue.push_front(Line::Choice(ChoiceInstruction::TryMeElse( - outer_thread_choice_offset, - ))); + prepend_queue.push_front(Line::Choice( + settings.try_me_else(outer_thread_choice_offset), + )); // prepend_queue is now: // | TryMeElse N_3 @@ -747,7 +996,11 @@ fn prepend_compiled_clause( code.extend(prepend_queue.into_iter()); - clause_loc + (outer_thread_choice_offset == 0) as usize + if skeleton.is_dynamic { + clause_loc + } else { + clause_loc + (outer_thread_choice_offset == 0) as usize + } } _ => { prepend_queue.extend(clause_code.drain(1..)); @@ -755,7 +1008,18 @@ fn prepend_compiled_clause( skeleton.clauses[0].opt_arg_index_key += clause_loc; skeleton.clauses[0].clause_start = clause_loc + 2; - let old_clause_start = skeleton.clauses[1].clause_start; + let old_clause_start = + match skeleton.clauses[1].opt_arg_index_key.switch_on_term_loc() { + Some(index_loc) if skeleton.is_dynamic => { + find_dynamic_outer_choice_instr(code, index_loc) + } + Some(_) => { + skeleton.clauses[1].clause_start - 2 + } + None => { + skeleton.clauses[1].clause_start + } + }; let inner_thread_rev_offset = 2 + prepend_queue.len() + clause_loc - old_clause_start; @@ -770,6 +1034,11 @@ fn prepend_compiled_clause( Line::Choice(ChoiceInstruction::TryMeElse(ref mut o)) if *o == 0 => { *o = prepend_queue_len - 2; } + Line::Choice(ChoiceInstruction::DynamicInternalElse( + _, _, ref mut o @ NextOrFail::Next(0), + )) => { + *o = NextOrFail::Fail(prepend_queue_len - 2); + } _ => { unreachable!(); } @@ -779,9 +1048,9 @@ fn prepend_compiled_clause( inner_thread_rev_offset, ))); - prepend_queue.push_front(Line::Choice(ChoiceInstruction::TryMeElse( - prepend_queue.len(), - ))); + prepend_queue.push_front(Line::Choice( + settings.try_me_else(prepend_queue.len()), + )); // prepend_queue is now: // | TryMeElse(N_2) @@ -799,10 +1068,14 @@ fn prepend_compiled_clause( } } else { match skeleton.clauses[1].opt_arg_index_key.switch_on_term_loc() { - Some(_) => { + Some(index_loc) => { prepend_queue.extend(clause_code.drain(1..)); - let old_clause_start = skeleton.clauses[1].clause_start - 2; + let old_clause_start = if skeleton.is_dynamic { + find_dynamic_outer_choice_instr(code, index_loc) + } else { + skeleton.clauses[1].clause_start - 2 + }; let inner_thread_rev_offset = 1 + prepend_queue.len() + clause_loc - old_clause_start; @@ -811,9 +1084,9 @@ fn prepend_compiled_clause( inner_thread_rev_offset, ))); - prepend_queue.push_front(Line::Choice(ChoiceInstruction::TryMeElse( - prepend_queue.len(), - ))); + prepend_queue.push_front(Line::Choice( + settings.try_me_else(prepend_queue.len()), + )); // prepend_queue is now: // | TryMeElse(N_2) @@ -841,9 +1114,9 @@ fn prepend_compiled_clause( inner_thread_rev_offset, ))); - prepend_queue.push_front(Line::Choice(ChoiceInstruction::TryMeElse( - prepend_queue.len(), - ))); + prepend_queue.push_front(Line::Choice( + settings.try_me_else(prepend_queue.len()), + )); // prepend_queue is now: // | TryMeElse(N_2) @@ -857,9 +1130,15 @@ fn prepend_compiled_clause( // skeleton.clauses[0].opt_arg_index_key += clause_loc; skeleton.clauses[0].clause_start = clause_loc; - clause_loc // + (outer_thread_choice_offset == 0 as usize) + clause_loc } } + }; + + if skeleton.is_dynamic { + IndexPtr::DynamicIndex(clause_loc) + } else { + IndexPtr::Index(clause_loc) } } @@ -868,12 +1147,22 @@ fn append_compiled_clause( mut clause_code: Code, skeleton: &mut PredicateSkeleton, retraction_info: &mut RetractionInfo, -) -> Option { + global_clock_tick: usize, +) -> Option { let clause_loc = code.len(); let target_pos = skeleton.clauses.len() - 1; let lower_bound = lower_bound_of_target_clause(skeleton, target_pos); - code.push(Line::Choice(ChoiceInstruction::TrustMe(0))); + let settings = CodeGenSettings { + global_clock_tick: if skeleton.is_dynamic { + Some(global_clock_tick) + } else { + None + }, + is_extensible: true, + non_counted_bt: false, + }; + skeleton.clauses[target_pos].clause_start = clause_loc; let mut code_ptr_opt = None; @@ -886,6 +1175,8 @@ fn append_compiled_clause( .switch_on_term_loc() { Some(index_loc) if lower_bound_arg_num == target_arg_num => { + code.push(Line::Choice(settings.internal_trust_me())); + code.extend(clause_code.drain(3..)); // skip the indexing code // set skeleton[target_pos].opt_arg_index_key to @@ -912,8 +1203,13 @@ fn append_compiled_clause( index_loc, ); + let target_pos_clause_start = find_outer_choice_instr( + code, + target_pos_clause_start, + ); + if lower_bound + 1 == target_pos { - set_switch_var_offset( + set_switch_var_offset_to_choice_instr( code, index_loc, target_pos_clause_start - index_loc, @@ -924,6 +1220,8 @@ fn append_compiled_clause( target_pos_clause_start // skeleton.clauses[target_pos - 1].clause_start } _ => { + code.push(Line::Choice(settings.trust_me())); + skeleton.clauses[target_pos].opt_arg_index_key += clause_loc; code.extend(clause_code.drain(1..)); @@ -936,7 +1234,7 @@ fn append_compiled_clause( code_ptr_opt = Some(skeleton.clauses[lower_bound].clause_start - 2); } - skeleton.clauses[lower_bound].clause_start - 2 + find_outer_choice_instr(code, skeleton.clauses[lower_bound].clause_start - 2) } None => { if lower_bound == 0 { @@ -953,12 +1251,14 @@ fn append_compiled_clause( // its variable offset. skeleton.clauses[target_pos].clause_start += 2; - set_switch_var_offset(code, index_loc, 2, retraction_info); + if !skeleton.is_dynamic { + set_switch_var_offset(code, index_loc, 2, retraction_info); + } } None => {} } - skeleton.clauses[lower_bound].clause_start + find_outer_choice_instr(code, skeleton.clauses[lower_bound].clause_start) } } } @@ -966,7 +1266,13 @@ fn append_compiled_clause( thread_choice_instr_at_to(code, threaded_choice_instr_loc, clause_loc, retraction_info); - code_ptr_opt + code_ptr_opt.map(|p| { + if skeleton.is_dynamic { + IndexPtr::DynamicIndex(p) + } else { + IndexPtr::Index(p) + } + }) } #[inline] @@ -1139,7 +1445,11 @@ impl<'a> LoadState<'a> { &predicates.compilation_target, key, &code_index, - IndexPtr::Index(code_ptr), + if settings.is_dynamic() { + IndexPtr::DynamicIndex(code_ptr) + } else { + IndexPtr::Index(code_ptr) + }, ); self.wam.code_repo.code.extend(code.into_iter()); @@ -1191,15 +1501,36 @@ impl<'a> LoadState<'a> { append_or_prepend, ); - match self + let settings = match self .wam .indices .get_predicate_skeleton_mut(&compilation_target, &key) { - Some(skeleton) if !skeleton.clauses.is_empty() => {}, - _ => { - // true because this predicate is extensible. - let settings = CodeGenSettings::new(true, non_counted_bt); + Some(skeleton) if !skeleton.clauses.is_empty() => { + CodeGenSettings { + global_clock_tick: if skeleton.is_dynamic { + Some(self.wam.machine_st.global_clock) + } else { + None + }, + is_extensible: true, + non_counted_bt, + } + }, + skeleton_opt => { + let settings = CodeGenSettings { + global_clock_tick: if let Some(skeleton) = skeleton_opt { + if skeleton.is_dynamic { + Some(self.wam.machine_st.global_clock) + } else { + None + } + } else { + None + }, + is_extensible: true, + non_counted_bt, + }; let mut predicate_queue = predicate_queue![clause]; predicate_queue.compilation_target = compilation_target; @@ -1208,7 +1539,6 @@ impl<'a> LoadState<'a> { } }; - let settings = CodeGenSettings::new(true, non_counted_bt); let atom_tbl = self.wam.machine_st.atom_tbl.clone(); let StandaloneCompileResult { @@ -1245,6 +1575,7 @@ impl<'a> LoadState<'a> { clause_code, skeleton, &mut self.retraction_info, + self.wam.machine_st.global_clock, ); match self @@ -1284,13 +1615,13 @@ impl<'a> LoadState<'a> { compilation_target.clone(), ); - if let Some(new_code_index) = result { + if let Some(new_code_ptr) = result { set_code_index( &mut self.retraction_info, &compilation_target, key, &code_index, - IndexPtr::Index(new_code_index), + new_code_ptr, ); } @@ -1309,13 +1640,14 @@ impl<'a> LoadState<'a> { key.clone(), )); - let threaded_choice_instr_loc = prepend_compiled_clause( + let new_code_ptr = prepend_compiled_clause( &mut self.wam.code_repo.code, compilation_target.clone(), key.clone(), clause_code, skeleton, &mut self.retraction_info, + self.wam.machine_st.global_clock, ); match self @@ -1360,7 +1692,7 @@ impl<'a> LoadState<'a> { &compilation_target, key, &code_index, - IndexPtr::Index(threaded_choice_instr_loc), + new_code_ptr, ); Ok(()) @@ -1368,6 +1700,51 @@ impl<'a> LoadState<'a> { } } + pub(super) fn retract_dynamic_clause(&mut self, key: PredicateKey, target_pos: usize) -> usize { + let skeleton = match self + .wam + .indices + .get_predicate_skeleton_mut(&self.compilation_target, &key) + { + Some(skeleton) => skeleton, + None => { + unreachable!(); + } + }; + + let clause_loc = match skeleton.clauses[target_pos] + .opt_arg_index_key + .switch_on_term_loc() + { + Some(index_loc) => { + find_inner_choice_instr( + &self.wam.code_repo.code, + skeleton.clauses[target_pos].clause_start, + index_loc, + ) + } + None => { + skeleton.clauses[target_pos].clause_start + } + }; + + match &mut self.wam.code_repo.code[clause_loc] { + Line::Choice(ChoiceInstruction::DynamicElse(_, ref mut d, _)) | + Line::Choice(ChoiceInstruction::DynamicInternalElse(_, ref mut d, _)) => { + *d = Death::Finite(self.wam.machine_st.global_clock); + } + _ => unreachable!() + } + + delete_from_skeleton( + self.compilation_target.clone(), + key, + skeleton, + target_pos, + &mut self.retraction_info, + ) + } + pub(super) fn retract_clause(&mut self, key: PredicateKey, target_pos: usize) -> usize { let code_index = self.get_or_insert_code_index( key.clone(), @@ -1835,6 +2212,7 @@ impl<'a, TS: TermStream> Loader<'a, TS> { clause_clause_compilation_target, (clause_name!("$clause"), 2), (0 .. skeleton.clauses.len()).map(Some).collect(), + false, // the builtin M:'$clause'/2 is never dynamic. ); predicate_info.is_dynamic = false; @@ -1851,11 +2229,22 @@ impl<'a, TS: TermStream> Loader<'a, TS> { } } - let settings = CodeGenSettings::new(predicate_info.is_extensible, non_counted_bt); + let settings = CodeGenSettings { + global_clock_tick: if predicate_info.is_dynamic { + Some(self.load_state.wam.machine_st.global_clock) + } else { + None + }, + is_extensible: predicate_info.is_extensible, + non_counted_bt, + }; + self.load_state.compile(key.clone(), &mut self.predicates, settings)?; } if predicate_info.is_dynamic { + self.load_state.wam.machine_st.global_clock += 1; + let clauses_vec: Vec<_> = self.clause_clauses .drain(0 .. predicates_len) .collect(); diff --git a/src/machine/load_state.rs b/src/machine/load_state.rs index d652724b..b2567725 100644 --- a/src/machine/load_state.rs +++ b/src/machine/load_state.rs @@ -346,25 +346,27 @@ impl<'a> LoadState<'a> { key: PredicateKey, clause_locs: &SliceDeque, ) { - let clause_target_poses: Vec<_> = self + let (clause_target_poses, is_dynamic) = self .wam .indices .get_predicate_skeleton(&compilation_target, &key) .map(|skeleton| { - clause_locs + (clause_locs .iter() .map(|clause_clause_loc| { skeleton.target_pos_of_clause_clause_loc( *clause_clause_loc, ) }) - .collect() + .collect(), + skeleton.is_dynamic) }).unwrap(); self.retract_local_clauses_by_locs( compilation_target, key, clause_target_poses, + is_dynamic, ); } @@ -373,6 +375,7 @@ impl<'a> LoadState<'a> { compilation_target: CompilationTarget, key: PredicateKey, mut clause_target_poses: Vec>, + is_dynamic: bool, ) { let old_compilation_target = mem::replace( &mut self.compilation_target, @@ -381,6 +384,9 @@ impl<'a> LoadState<'a> { while let Some(target_pos_opt) = clause_target_poses.pop() { match target_pos_opt { + Some(target_pos) if is_dynamic => { + self.retract_dynamic_clause(key.clone(), target_pos); + } Some(target_pos) => { self.retract_clause(key.clone(), target_pos); } diff --git a/src/machine/loader.rs b/src/machine/loader.rs index 96c449dc..691871c6 100644 --- a/src/machine/loader.rs +++ b/src/machine/loader.rs @@ -68,7 +68,7 @@ pub(crate) enum RetractionRecord { RemovedIndex(usize, OptArgIndexKey, usize), ReplacedChoiceOffset(usize, usize), AppendedTrustMe(usize, usize, bool), - ReplacedSwitchOnTermVarIndex(usize, usize), + ReplacedSwitchOnTermVarIndex(usize, IndexingCodePtr), ModifiedTryMeElse(usize, usize), ModifiedRetryMeElse(usize, usize), ModifiedRevJmpBy(usize, usize), @@ -94,6 +94,8 @@ pub(crate) enum RetractionRecord { SliceDeque, ), RemovedSkeleton(CompilationTarget, PredicateKey, PredicateSkeleton), + ReplacedDynamicElseOffset(usize, usize), + AppendedNextOrFail(usize, NextOrFail), } /* @@ -626,6 +628,32 @@ impl<'a> Drop for LoadState<'a> { } } } + RetractionRecord::ReplacedDynamicElseOffset(instr_loc, next) => { + match &mut self.wam.code_repo.code[instr_loc] { + Line::Choice(ChoiceInstruction::DynamicElse( + _, _, NextOrFail::Next(ref mut o), + )) | + Line::Choice(ChoiceInstruction::DynamicInternalElse( + _, _, NextOrFail::Next(ref mut o), + )) => { + *o = next; + } + _ => {} + } + } + RetractionRecord::AppendedNextOrFail(instr_loc, fail) => { + match &mut self.wam.code_repo.code[instr_loc] { + Line::Choice(ChoiceInstruction::DynamicElse( + _, _, ref mut next_or_fail, + )) | + Line::Choice(ChoiceInstruction::DynamicInternalElse( + _, _, ref mut next_or_fail, + )) => { + *next_or_fail = fail; + } + _ => {} + } + } } } @@ -1720,6 +1748,13 @@ impl Machine { fetch_op_spec(clause_name!(":-"), 2, &loader.load_state.wam.indices.op_dir), ); + // if a new predicate was just created, make it dynamic. + loader.add_dynamic_predicate( + compilation_target.clone(), + key.0.clone(), + key.1, + )?; + loader.load_state.incremental_compile_clause( key.clone(), asserted_clause, @@ -1728,13 +1763,8 @@ impl Machine { append_or_prepend, )?; - // if a new predicate was just created, make it dynamic. - loader - .load_state - .wam - .indices - .get_predicate_skeleton_mut(&compilation_target, &key) - .map(|skeleton| skeleton.is_dynamic = true); + // the global clock is incremented after each assertion. + loader.load_state.wam.machine_st.global_clock += 1; loader.compile_clause_clauses( key, @@ -1883,7 +1913,10 @@ impl Machine { let mut loader = Loader::new(LiveTermStream::new(ListingSource::User), self); loader.load_state.compilation_target = compilation_target; - let clause_clause_loc = loader.load_state.retract_clause(key, target_pos); + let clause_clause_loc = loader.load_state.retract_dynamic_clause(key, target_pos); + + // the global clock is incremented after each retraction. + loader.load_state.wam.machine_st.global_clock += 1; let target_pos = match loader.load_state.wam.indices.get_predicate_skeleton( &clause_clause_compilation_target, diff --git a/src/machine/machine_indices.rs b/src/machine/machine_indices.rs index 04a60feb..17bfa4a6 100644 --- a/src/machine/machine_indices.rs +++ b/src/machine/machine_indices.rs @@ -372,6 +372,7 @@ impl From for HeapCellValue { #[derive(Debug, Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)] pub enum IndexPtr { DynamicUndefined, // a predicate, declared as dynamic, whose location in code is as yet undefined. + DynamicIndex(usize), Index(usize), Undefined, } @@ -405,6 +406,7 @@ impl CodeIndex { pub fn local(&self) -> Option { match self.0.get() { IndexPtr::Index(i) => Some(i), + IndexPtr::DynamicIndex(i) => Some(i), _ => None, } } @@ -555,38 +557,6 @@ impl LocalCodePtr { } } -/* -impl PartialOrd for CodePtr { - fn partial_cmp(&self, other: &CodePtr) -> Option { - match (self, other) { - (&CodePtr::Local(ref l1), &CodePtr::Local(ref l2)) => { - l1.partial_cmp(l2) - } - _ => { - Some(Ordering::Greater) - } - } - } -} - -impl PartialOrd for LocalCodePtr { - fn partial_cmp(&self, other: &LocalCodePtr) -> Option { - match (self, other) { - (&LocalCodePtr::DirEntry(p1), &LocalCodePtr::DirEntry(ref p2)) | - (&LocalCodePtr::TopLevel(_, p1), &LocalCodePtr::TopLevel(_, ref p2)) => { - p1.partial_cmp(p2) - } - (_, &LocalCodePtr::TopLevel(_, _)) => { - Some(Ordering::Less) - } - _ => { - Some(Ordering::Greater) - } - } - } -} -*/ - impl Default for CodePtr { #[inline] fn default() -> Self { diff --git a/src/machine/machine_state.rs b/src/machine/machine_state.rs index 26686fd8..71801f3b 100644 --- a/src/machine/machine_state.rs +++ b/src/machine/machine_state.rs @@ -269,6 +269,12 @@ impl Default for HeapPtr { } } +#[derive(Debug)] +pub enum FirstOrNext { + First, + Next, +} + #[derive(Debug)] pub struct MachineState { pub(crate) atom_tbl: TabledData, @@ -295,7 +301,9 @@ pub struct MachineState { pub(super) last_call: bool, pub(crate) heap_locs: HeapVarDict, pub(crate) flags: MachineFlags, - pub(crate) at_end_of_expansion: bool, + pub(crate) cc: usize, + pub(crate) global_clock: usize, + pub(crate) dynamic_mode: FirstOrNext, } impl MachineState { @@ -911,8 +919,12 @@ pub(crate) trait CallPolicy: Any + fmt::Debug { IndexPtr::Undefined => { return Err(machine_st.throw_undefined_error(name, arity)); } + IndexPtr::DynamicIndex(compiled_tl_index) => { + machine_st.dynamic_mode = FirstOrNext::First; + machine_st.call_at_index(arity, dir_entry!(compiled_tl_index)); + } IndexPtr::Index(compiled_tl_index) => { - machine_st.call_at_index(arity, LocalCodePtr::DirEntry(compiled_tl_index)); + machine_st.call_at_index(arity, dir_entry!(compiled_tl_index)); } } @@ -934,6 +946,10 @@ pub(crate) trait CallPolicy: Any + fmt::Debug { IndexPtr::Undefined => { return Err(machine_st.throw_undefined_error(name, arity)); } + IndexPtr::DynamicIndex(compiled_tl_index) => { + machine_st.dynamic_mode = FirstOrNext::First; + machine_st.execute_at_index(arity, dir_entry!(compiled_tl_index)); + } IndexPtr::Index(compiled_tl_index) => { machine_st.execute_at_index(arity, dir_entry!(compiled_tl_index)) } diff --git a/src/machine/machine_state_impl.rs b/src/machine/machine_state_impl.rs index 5b946b0d..3262daa5 100644 --- a/src/machine/machine_state_impl.rs +++ b/src/machine/machine_state_impl.rs @@ -54,7 +54,9 @@ impl MachineState { last_call: false, heap_locs: HeapVarDict::new(), flags: MachineFlags::default(), - at_end_of_expansion: false, + cc: 0, + global_clock: 0, + dynamic_mode: FirstOrNext::First, } } @@ -1302,9 +1304,35 @@ impl MachineState { pub(super) fn execute_indexing_instr( &mut self, indexing_lines: &Vec, - call_policy: &mut Box, - global_variables: &mut GlobalVarDir, + code_repo: &CodeRepo, ) { + fn dynamic_external_of_clause_is_valid( + machine_st: &mut MachineState, + code: &Code, + p: usize, + ) -> bool { + match &code[p] { + Line::Choice(ChoiceInstruction::DynamicInternalElse(..)) => { + machine_st.dynamic_mode = FirstOrNext::First; + return true; + } + _ => {} + } + + match &code[p-1] { + &Line::Choice(ChoiceInstruction::DynamicInternalElse(birth, death, _)) => { + if birth < machine_st.cc && Death::Finite(machine_st.cc) <= death { + return true; + } else { + return false; + } + } + _ => {} + } + + true + } + let mut index = 0; let addr = match &indexing_lines[0] { &IndexingLine::Indexing(IndexingInstruction::SwitchOnTerm(arg, ..)) => { @@ -1323,7 +1351,7 @@ impl MachineState { IndexingCodePtr::Fail } Addr::HeapCell(_) | Addr::StackCell(..) | Addr::AttrVar(..) => { - IndexingCodePtr::External(v) + v } Addr::PStrLocation(..) => l, Addr::Char(_) @@ -1342,6 +1370,20 @@ impl MachineState { self.fail = true; break; } + IndexingCodePtr::DynamicExternal(o) => { + // either points directly to a + // DynamicInternalElse, or just ahead of + // one. Or neither! + let p = self.p.local().abs_loc(); + + if !dynamic_external_of_clause_is_valid(self, &code_repo.code, p + o) { + self.fail = true; + } else { + self.p += o; + } + + break; + } IndexingCodePtr::External(o) => { self.p += o; break; @@ -1365,6 +1407,20 @@ impl MachineState { self.fail = true; break; } + IndexingCodePtr::DynamicExternal(o) => { + // either points directly to a + // DynamicInternalElse, or just ahead of + // one. Or neither! + let p = self.p.local().abs_loc(); + + if !dynamic_external_of_clause_is_valid(self, &code_repo.code, p + o) { + self.fail = true; + } else { + self.p += o; + } + + break; + } IndexingCodePtr::External(o) => { self.p += o; break; @@ -1394,6 +1450,17 @@ impl MachineState { self.fail = true; break; } + IndexingCodePtr::DynamicExternal(o) => { + let p = self.p.local().abs_loc(); + + if !dynamic_external_of_clause_is_valid(self, &code_repo.code, p + o) { + self.fail = true; + } else { + self.p += o; + } + + break; + } IndexingCodePtr::External(o) => { self.p += o; break; @@ -1403,18 +1470,23 @@ impl MachineState { } } } - &IndexingLine::IndexedChoice(ref instrs) => { + &IndexingLine::IndexedChoice(_) => { if let LocalCodePtr::DirEntry(p) = self.p.local() { self.p = CodePtr::Local(LocalCodePtr::IndexingBuf(p, index, 0)); } else { unreachable!() } - self.execute_indexed_choice_instr( - instrs.first().unwrap(), - call_policy, - global_variables, - ); + break; + } + &IndexingLine::DynamicIndexedChoice(_) => { + self.dynamic_mode = FirstOrNext::First; + + if let LocalCodePtr::DirEntry(p) = self.p.local() { + self.p = CodePtr::Local(LocalCodePtr::IndexingBuf(p, index, 0)); + } else { + unreachable!() + } break; } @@ -3028,6 +3100,113 @@ impl MachineState { }; } + pub(super) fn execute_dynamic_indexed_choice_instr( + &mut self, + code_repo: &CodeRepo, + call_policy: &mut Box, + global_variables: &mut GlobalVarDir, + ) { + let p = self.p.local(); + + match code_repo.find_living_dynamic(p, self.cc) { + Some((offset, oi, ii, is_next_clause)) => { + self.p = CodePtr::Local(LocalCodePtr::IndexingBuf( + p.abs_loc(), oi, ii, + )); + + match self.dynamic_mode { + FirstOrNext::First if !is_next_clause => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry( + p.abs_loc() + offset, + )); + } + FirstOrNext::First => { + // there's a leading DynamicElse that sets self.cc. + // self.cc = self.global_clock; + + match code_repo.find_living_dynamic( + LocalCodePtr::IndexingBuf(p.abs_loc(), oi, ii + 1), + self.cc, + ) { + Some(_) => { + self.registers[self.num_of_args + 1] = Addr::Usize(self.cc); + self.num_of_args += 1; + + self.execute_indexed_choice_instr( + &IndexedChoiceInstruction::Try(offset), + call_policy, + global_variables, + ); + + self.num_of_args -= 1; + } + None => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry( + p.abs_loc() + offset, + )); + } + } + } + FirstOrNext::Next => { + let n = self + .stack + .index_or_frame(self.b) + .prelude + .univ_prelude + .num_cells; + + self.cc = match self.stack.index_or_frame(self.b)[n - 1] { + Addr::Usize(cc) => cc, + _ => unreachable!(), + }; + + if is_next_clause { + match code_repo.find_living_dynamic( + LocalCodePtr::IndexingBuf(p.abs_loc(), oi, ii + 1), + self.cc, + ) { + Some(_) => { + try_or_fail!( + self, + call_policy.retry( + self, + offset, + global_variables, + ) + ) + } + None => { + try_or_fail!( + self, + call_policy.trust( + self, + offset, + global_variables, + ) + ) + } + } + } else { + try_or_fail!( + self, + call_policy.trust( + self, + offset, + global_variables, + ) + ) + } + } + } + + self.dynamic_mode = FirstOrNext::Next; + } + None => { + self.fail = true; + } + } + } + pub(super) fn execute_indexed_choice_instr( &mut self, instr: &IndexedChoiceInstruction, @@ -3073,10 +3252,187 @@ impl MachineState { pub(super) fn execute_choice_instr( &mut self, instr: &ChoiceInstruction, + code_repo: &CodeRepo, call_policy: &mut Box, global_variables: &mut GlobalVarDir, ) { match instr { + &ChoiceInstruction::DynamicElse(..) => { + if let FirstOrNext::First = self.dynamic_mode { + self.cc = self.global_clock; + } + + let p = self.p.local().abs_loc(); + + match code_repo.find_living_dynamic_else(p, self.cc) { + Some((p, next_i)) => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry(p)); + + match self.dynamic_mode { + FirstOrNext::First if next_i == 0 => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry(p + 1)); + } + FirstOrNext::First => { + self.cc = self.global_clock; + + match code_repo.find_living_dynamic_else(p + next_i, self.cc) { + Some(_) => { + self.registers[self.num_of_args + 1] = Addr::Usize(self.cc); + self.num_of_args += 1; + + self.execute_choice_instr( + &ChoiceInstruction::TryMeElse(next_i), + code_repo, + call_policy, + global_variables, + ); + + self.num_of_args -= 1; + } + None => { + self.p += 1; + } + } + } + FirstOrNext::Next => { + let n = self + .stack + .index_or_frame(self.b) + .prelude + .univ_prelude + .num_cells; + + self.cc = match self.stack.index_or_frame(self.b)[n - 1] { + Addr::Usize(cc) => cc, + _ => unreachable!(), + }; + + if next_i > 0 { + match code_repo.find_living_dynamic_else(p + next_i, self.cc) { + Some(_) => { + try_or_fail!( + self, + call_policy.retry_me_else( + self, + next_i, + global_variables, + ) + ) + } + None => { + try_or_fail!( + self, + call_policy.trust_me( + self, + global_variables, + ) + ) + } + } + } else { + try_or_fail!( + self, + call_policy.trust_me( + self, + global_variables, + ) + ) + } + } + } + } + None => { + self.fail = true; + } + } + + self.dynamic_mode = FirstOrNext::Next; + } + &ChoiceInstruction::DynamicInternalElse(..) => { + let p = self.p.local().abs_loc(); + + match code_repo.find_living_dynamic_else(p, self.cc) { + Some((p, next_i)) => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry(p)); + + match self.dynamic_mode { + FirstOrNext::First if next_i == 0 => { + self.p = CodePtr::Local(LocalCodePtr::DirEntry(p + 1)); + } + FirstOrNext::First => { + match code_repo.find_living_dynamic_else(p + next_i, self.cc) { + Some(_) => { + self.registers[self.num_of_args + 1] = Addr::Usize(self.cc); + self.num_of_args += 1; + + self.execute_choice_instr( + &ChoiceInstruction::TryMeElse(next_i), + code_repo, + call_policy, + global_variables, + ); + + self.num_of_args -= 1; + } + None => { + self.p += 1; + } + } + } + FirstOrNext::Next => { + let n = self + .stack + .index_or_frame(self.b) + .prelude + .univ_prelude + .num_cells; + + self.cc = match self.stack.index_or_frame(self.b)[n - 1] { + Addr::Usize(cc) => cc, + _ => unreachable!(), + }; + + if next_i > 0 { + match code_repo.find_living_dynamic_else(p + next_i, self.cc) { + Some(_) => { + try_or_fail!( + self, + call_policy.retry_me_else( + self, + next_i, + global_variables, + ) + ) + } + None => { + try_or_fail!( + self, + call_policy.trust_me( + self, + global_variables, + ) + ) + } + } + } else { + try_or_fail!( + self, + call_policy.trust_me( + self, + global_variables, + ) + ) + } + } + } + } + None => { + self.fail = true; + } + } + + self.dynamic_mode = FirstOrNext::Next; + } &ChoiceInstruction::TryMeElse(offset) => { let n = self.num_of_args; let b = self.stack.allocate_or_frame(n); diff --git a/src/machine/mod.rs b/src/machine/mod.rs index d23580ba..b0f607f2 100644 --- a/src/machine/mod.rs +++ b/src/machine/mod.rs @@ -562,6 +562,7 @@ impl MachineState { &Line::Choice(ref choice_instr) => { self.execute_choice_instr( choice_instr, + code_repo, &mut policies.call_policy, &mut indices.global_variables, ) @@ -585,8 +586,7 @@ impl MachineState { &Line::IndexingCode(ref indexing_lines) => { self.execute_indexing_instr( indexing_lines, - &mut policies.call_policy, - &mut indices.global_variables, + code_repo, ) } &Line::IndexedChoice(ref choice_instr) => { @@ -596,6 +596,13 @@ impl MachineState { &mut indices.global_variables, ) } + &Line::DynamicIndexedChoice(_) => { + self.execute_dynamic_indexed_choice_instr( + code_repo, + &mut policies.call_policy, + &mut indices.global_variables, + ) + } &Line::Query(ref query_instr) => { self.execute_query_instr(&query_instr); self.p += 1; diff --git a/src/machine/system_calls.rs b/src/machine/system_calls.rs index 72e6b3a9..a2307ed2 100644 --- a/src/machine/system_calls.rs +++ b/src/machine/system_calls.rs @@ -3496,14 +3496,16 @@ impl MachineState { self.fail = match self.store(self.deref(self[temp_v!(2)])) { Addr::Str(s) => match &self.heap[s] { - &HeapCellValue::NamedStr(arity, ref name, ref spec) => indices - .get_predicate_code_index( + &HeapCellValue::NamedStr(arity, ref name, ref spec) => { + CLAUSE_TYPE_FORMS.borrow().get(&(name.as_str(), arity)).is_some() || + indices.get_predicate_code_index( name.clone(), arity, module_name, spec.clone(), ) - .is_some(), + .is_some() + } _ => { unreachable!() } @@ -3513,8 +3515,8 @@ impl MachineState { let spec = fetch_atom_op_spec(name.clone(), spec.clone(), &indices.op_dir); - indices - .get_predicate_code_index(name.clone(), 0, module_name, spec) + CLAUSE_TYPE_FORMS.borrow().get(&(name.as_str(), 0)).is_some() || + indices.get_predicate_code_index(name.clone(), 0, module_name, spec) .is_some() } else { unreachable!() diff --git a/src/macros.rs b/src/macros.rs index 7e03e231..b8b6d802 100644 --- a/src/macros.rs +++ b/src/macros.rs @@ -126,6 +126,7 @@ macro_rules! functor_term { (indexing_code_ptr($h:expr, $e:expr), $arity:expr, $aux_lens:expr, $addendum:ident) => ({ let stub = match $e { + IndexingCodePtr::DynamicExternal(o) => functor!("dynamic_external", [integer(o)]), IndexingCodePtr::External(o) => functor!("external", [integer(o)]), IndexingCodePtr::Internal(o) => functor!("internal", [integer(o)]), IndexingCodePtr::Fail => vec![HeapCellValue::Atom(clause_name!("fail"), None)], diff --git a/src/write.rs b/src/write.rs index e98b550f..4aa84e99 100644 --- a/src/write.rs +++ b/src/write.rs @@ -96,7 +96,7 @@ impl fmt::Display for IndexPtr { match self { &IndexPtr::DynamicUndefined => write!(f, "undefined"), &IndexPtr::Undefined => write!(f, "undefined"), - &IndexPtr::Index(i) => write!(f, "{}", i), + &IndexPtr::DynamicIndex(i) | &IndexPtr::Index(i) => write!(f, "{}", i), } } } @@ -339,6 +339,30 @@ impl fmt::Display for IndexedChoiceInstruction { impl fmt::Display for ChoiceInstruction { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self { + &ChoiceInstruction::DynamicElse(offset, Death::Infinity, NextOrFail::Next(i)) => { + write!(f, "dynamic_else {}, {}, {}", offset, "inf", i) + } + &ChoiceInstruction::DynamicElse(offset, Death::Infinity, NextOrFail::Fail(i)) => { + write!(f, "dynamic_else {}, {}, fail({})", offset, "inf", i) + } + &ChoiceInstruction::DynamicElse(offset, Death::Finite(d), NextOrFail::Next(i)) => { + write!(f, "dynamic_else {}, {}, {}", offset, d, i) + } + &ChoiceInstruction::DynamicElse(offset, Death::Finite(d), NextOrFail::Fail(i)) => { + write!(f, "dynamic_else {}, {}, fail({})", offset, d, i) + } + &ChoiceInstruction::DynamicInternalElse(offset, Death::Infinity, NextOrFail::Next(i)) => { + write!(f, "dynamic_internal_else {}, {}, {}", offset, "inf", i) + } + &ChoiceInstruction::DynamicInternalElse(offset, Death::Infinity, NextOrFail::Fail(i)) => { + write!(f, "dynamic_internal_else {}, {}, fail({})", offset, "inf", i) + } + &ChoiceInstruction::DynamicInternalElse(offset, Death::Finite(d), NextOrFail::Next(i)) => { + write!(f, "dynamic_internal_else {}, {}, {}", offset, d, i) + } + &ChoiceInstruction::DynamicInternalElse(offset, Death::Finite(d), NextOrFail::Fail(i)) => { + write!(f, "dynamic_internal_else {}, {}, fail({})", offset, d, i) + } &ChoiceInstruction::TryMeElse(offset) => write!(f, "try_me_else {}", offset), &ChoiceInstruction::DefaultRetryMeElse(offset) => { @@ -357,6 +381,9 @@ impl fmt::Display for ChoiceInstruction { impl fmt::Display for IndexingCodePtr { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self { + &IndexingCodePtr::DynamicExternal(o) => { + write!(f, "IndexingCodePtr::DynamicExternal({})", o) + } &IndexingCodePtr::External(o) => { write!(f, "IndexingCodePtr::External({})", o) } @@ -480,6 +507,13 @@ impl fmt::Display for IndexingLine { write!(f, "{}", indexed_choice_instr)?; } + Ok(()) + } + &IndexingLine::DynamicIndexedChoice(ref indexed_choice_instrs) => { + for indexed_choice_instr in indexed_choice_instrs { + write!(f, "dynamic({})", indexed_choice_instr)?; + } + Ok(()) } } @@ -502,6 +536,7 @@ impl fmt::Display for Line { Ok(()) } &Line::IndexedChoice(ref indexed_choice_instr) => write!(f, "{}", indexed_choice_instr), + &Line::DynamicIndexedChoice(ref indexed_choice_instr) => write!(f, "{}", indexed_choice_instr), &Line::Query(ref query_instr) => write!(f, "{}", query_instr), } } -- 2.54.0