From 68b4951bc97d3f6e7abc4d97b69dde519196b21e Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Mon, 25 Apr 2022 22:55:28 -0600 Subject: [PATCH] replace SliceDeque with VecDeque --- Cargo.lock | 21 ---------- Cargo.toml | 1 - build/instructions_template.rs | 5 +-- src/codegen.rs | 5 ++- src/forms.rs | 27 +++++++------ src/indexing.rs | 49 ++++++++++++----------- src/machine/compile.rs | 38 +++++++++--------- src/machine/load_state.rs | 10 ++--- src/machine/loader.rs | 72 +++++++++++++++++----------------- 9 files changed, 105 insertions(+), 123 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 35f7b0a8..0de5eae8 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -778,15 +778,6 @@ version = "0.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "c41e0c4fef86961ac6d6f8a82609f55f31b05e4fce149ac5710e439df7619ba4" -[[package]] -name = "mach" -version = "0.3.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "b823e83b2affd8f40a9ee8c29dbc56404c1e34cd2710921f2801e2cf29527afa" -dependencies = [ - "libc", -] - [[package]] name = "markup5ever" version = "0.8.1" @@ -1663,7 +1654,6 @@ dependencies = [ "select", "serial_test", "sha3", - "slice-deque", "smallvec", "sodiumoxide", "static_assertions", @@ -1826,17 +1816,6 @@ version = "0.4.5" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "9def91fd1e018fe007022791f865d0ccc9b3a0d5001e01aabb8b40e46000afb5" -[[package]] -name = "slice-deque" -version = "0.3.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "31ef6ee280cdefba6d2d0b4b78a84a1c1a3f3a4cec98c2d4231c8bc225de0f25" -dependencies = [ - "libc", - "mach", - "winapi", -] - [[package]] name = "smallvec" version = "1.8.0" diff --git a/Cargo.toml b/Cargo.toml index d0c0d710..680280d8 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -63,7 +63,6 @@ base64 = "0.12.3" smallvec = "1.8.0" sodiumoxide = "0.2.6" static_assertions = "1.1.0" -slice-deque = "0.3.0" ryu = "1.0.9" hyper = { version = "0.14", features = ["full"] } hyper-tls = "0.5.0" diff --git a/build/instructions_template.rs b/build/instructions_template.rs index b16e7bd8..988067f8 100644 --- a/build/instructions_template.rs +++ b/build/instructions_template.rs @@ -807,7 +807,6 @@ fn generate_instruction_preface() -> TokenStream { use crate::types::*; use indexmap::IndexMap; - use slice_deque::SliceDeque; use std::collections::VecDeque; @@ -1030,8 +1029,8 @@ fn generate_instruction_preface() -> TokenStream { #[derive(Clone, Debug)] pub enum IndexingLine { Indexing(IndexingInstruction), - IndexedChoice(SliceDeque), - DynamicIndexedChoice(SliceDeque), + IndexedChoice(VecDeque), + DynamicIndexedChoice(VecDeque), } impl From for IndexingLine { diff --git a/src/codegen.rs b/src/codegen.rs index 0b89e9e8..c298c9e0 100644 --- a/src/codegen.rs +++ b/src/codegen.rs @@ -1151,7 +1151,10 @@ impl<'b, TermMarker: Allocator> CodeGenerator<'b, TermMarker> { if self.settings.is_extensible { let segment_is_indexed = code_segment[0].to_indexing_line().is_some(); - for clause_index_info in self.skeleton.clauses[skel_lower_bound..].iter_mut() { + for clause_index_info in self.skeleton.clauses + .make_contiguous()[skel_lower_bound..] + .iter_mut() + { clause_index_info.clause_start += clause_start_offset + 2 * (segment_is_indexed as usize); clause_index_info.opt_arg_index_key += clause_start_offset + 1; diff --git a/src/forms.rs b/src/forms.rs index bdcb86dc..b1427193 100644 --- a/src/forms.rs +++ b/src/forms.rs @@ -15,9 +15,8 @@ use fxhash::FxBuildHasher; use indexmap::{IndexMap, IndexSet}; use ordered_float::OrderedFloat; -use slice_deque::*; - use std::cell::Cell; +use std::collections::VecDeque; use std::convert::TryFrom; use std::fmt; use std::ops::AddAssign; @@ -820,7 +819,7 @@ pub(crate) struct LocalPredicateSkeleton { pub(crate) is_discontiguous: bool, pub(crate) is_dynamic: bool, pub(crate) is_multifile: bool, - pub(crate) clause_clause_locs: SliceDeque, + pub(crate) clause_clause_locs: VecDeque, pub(crate) clause_assert_margin: usize, pub(crate) retracted_dynamic_clauses: Option>, // always None if non-dynamic. } @@ -832,7 +831,7 @@ impl LocalPredicateSkeleton { is_discontiguous: false, is_dynamic: false, is_multifile: false, - clause_clause_locs: sdeq![], + clause_clause_locs: VecDeque::new(), clause_assert_margin: 0, retracted_dynamic_clauses: Some(vec![]), } @@ -873,7 +872,7 @@ impl LocalPredicateSkeleton { #[derive(Clone, Debug)] pub(crate) struct PredicateSkeleton { pub(crate) core: LocalPredicateSkeleton, - pub(crate) clauses: SliceDeque, + pub(crate) clauses: VecDeque, } impl PredicateSkeleton { @@ -881,7 +880,7 @@ impl PredicateSkeleton { pub(crate) fn new() -> Self { PredicateSkeleton { core: LocalPredicateSkeleton::new(), - clauses: sdeq![], + clauses: VecDeque::new(), } } @@ -897,18 +896,22 @@ impl PredicateSkeleton { } pub(crate) fn target_pos_of_clause_clause_loc( - &self, + &mut self, clause_clause_loc: usize, ) -> Option { - let search_result = self.core.clause_clause_locs[0..self.core.clause_assert_margin] + let search_result = self.core.clause_clause_locs + .make_contiguous()[0..self.core.clause_assert_margin] .binary_search_by(|loc| clause_clause_loc.cmp(&loc)); match search_result { Ok(loc) => Some(loc), - Err(_) => self.core.clause_clause_locs[self.core.clause_assert_margin..] - .binary_search_by(|loc| loc.cmp(&clause_clause_loc)) - .map(|loc| loc + self.core.clause_assert_margin) - .ok(), + Err(_) => { + self.core.clause_clause_locs + .make_contiguous()[self.core.clause_assert_margin..] + .binary_search_by(|loc| loc.cmp(&clause_clause_loc)) + .map(|loc| loc + self.core.clause_assert_margin) + .ok() + } } } } diff --git a/src/indexing.rs b/src/indexing.rs index 5deccb80..9d7af807 100644 --- a/src/indexing.rs +++ b/src/indexing.rs @@ -5,7 +5,6 @@ use crate::forms::*; use crate::instructions::*; use indexmap::IndexMap; -use slice_deque::{sdeq, SliceDeque}; use std::collections::VecDeque; use std::hash::Hash; @@ -148,15 +147,15 @@ impl<'a> IndexingCodeMergingPtr<'a> { index: usize, ) { let third_level_index = if self.append_or_prepend.is_append() { - sdeq![ + vec![ IndexedChoiceInstruction::Try(external), IndexedChoiceInstruction::Trust(index) - ] + ].into() } else { - sdeq![ + vec![ IndexedChoiceInstruction::Try(index), IndexedChoiceInstruction::Trust(external) - ] + ].into() }; let indexing_code_len = self.indexing_code.len(); @@ -182,9 +181,9 @@ impl<'a> IndexingCodeMergingPtr<'a> { index: usize, ) { let third_level_index = if self.append_or_prepend.is_append() { - sdeq![external, index] + vec![external, index].into() } else { - sdeq![index, external] + vec![index, external].into() }; let indexing_code_len = self.indexing_code.len(); @@ -208,11 +207,11 @@ impl<'a> IndexingCodeMergingPtr<'a> { IndexingLine::IndexedChoice(ref mut indexed_choice_instrs) if self.append_or_prepend.is_append() => { - uncap_choice_seq_with_trust(indexed_choice_instrs); + uncap_choice_seq_with_trust(indexed_choice_instrs.make_contiguous()); indexed_choice_instrs.push_back(IndexedChoiceInstruction::Trust(index)); } IndexingLine::IndexedChoice(ref mut indexed_choice_instrs) => { - uncap_choice_seq_with_try(indexed_choice_instrs); + uncap_choice_seq_with_try(indexed_choice_instrs.make_contiguous()); indexed_choice_instrs.push_front(IndexedChoiceInstruction::Try(index)); } IndexingLine::DynamicIndexedChoice(ref mut indexed_choice_instrs) @@ -430,15 +429,15 @@ impl<'a> IndexingCodeMergingPtr<'a> { index: usize, ) { let third_level_index = if self.append_or_prepend.is_append() { - sdeq![ + vec![ IndexedChoiceInstruction::Try(external), IndexedChoiceInstruction::Trust(index) - ] + ].into() } else { - sdeq![ + vec![ IndexedChoiceInstruction::Try(index), IndexedChoiceInstruction::Trust(external) - ] + ].into() }; let indexing_code_len = self.indexing_code.len(); @@ -464,9 +463,9 @@ impl<'a> IndexingCodeMergingPtr<'a> { index: usize, ) { let third_level_index = if self.append_or_prepend.is_append() { - sdeq![external, index] + vec![external, index].into() } else { - sdeq![index, external] + vec![index, external].into() }; let indexing_code_len = self.indexing_code.len(); @@ -570,9 +569,9 @@ impl<'a> IndexingCodeMergingPtr<'a> { *l = IndexingCodePtr::Internal(indexing_code_len - self.offset); let third_level_index = if self.append_or_prepend.is_append() { - sdeq![o, index] + vec![o, index].into() } else { - sdeq![index, o] + vec![index, o].into() }; self.indexing_code @@ -582,15 +581,15 @@ impl<'a> IndexingCodeMergingPtr<'a> { *l = IndexingCodePtr::Internal(indexing_code_len - self.offset); let third_level_index = if self.append_or_prepend.is_append() { - sdeq![ + vec![ IndexedChoiceInstruction::Try(o), IndexedChoiceInstruction::Trust(index) - ] + ].into() } else { - sdeq![ + vec![ IndexedChoiceInstruction::Try(index), IndexedChoiceInstruction::Trust(o) - ] + ].into() }; self.indexing_code @@ -1178,7 +1177,7 @@ pub(crate) trait Indexer { prelude: &mut VecDeque, ) -> IndexingCodePtr; - fn remove_instruction_with_offset(code: &mut SliceDeque, offset: usize); + fn remove_instruction_with_offset(code: &mut VecDeque, offset: usize); fn var_offset_wrapper(var_offset: usize) -> IndexingCodePtr; } @@ -1281,13 +1280,13 @@ impl Indexer for StaticCodeIndices { #[inline] fn remove_instruction_with_offset( - code: &mut SliceDeque, + code: &mut VecDeque, offset: usize, ) { for (index, line) in code.iter().enumerate() { if offset == line.offset() { code.remove(index); - cap_choice_seq(code); + cap_choice_seq(code.make_contiguous()); return; } } @@ -1390,7 +1389,7 @@ impl Indexer for DynamicCodeIndices { } #[inline] - fn remove_instruction_with_offset(code: &mut SliceDeque, offset: usize) { + fn remove_instruction_with_offset(code: &mut VecDeque, offset: usize) { for (index, line) in code.iter().enumerate() { if offset == *line { code.remove(index); diff --git a/src/machine/compile.rs b/src/machine/compile.rs index adef5759..bbfa1c00 100644 --- a/src/machine/compile.rs +++ b/src/machine/compile.rs @@ -12,8 +12,6 @@ use crate::machine::term_stream::*; use crate::machine::*; use crate::parser::ast::*; -use slice_deque::{sdeq, SliceDeque}; - use std::cell::Cell; use std::collections::VecDeque; use std::mem; @@ -425,8 +423,8 @@ fn delete_from_skeleton( target_pos: usize, retraction_info: &mut RetractionInfo, ) -> usize { - let clause_index_info = skeleton.clauses.remove(target_pos); - let clause_clause_loc = skeleton.core.clause_clause_locs.remove(target_pos); + let clause_index_info = skeleton.clauses.remove(target_pos).unwrap(); + let clause_clause_loc = skeleton.core.clause_clause_locs.remove(target_pos).unwrap(); if target_pos < skeleton.core.clause_assert_margin { skeleton.core.clause_assert_margin -= 1; @@ -887,7 +885,7 @@ fn prepend_compiled_clause( global_clock_tick: usize, ) -> IndexPtr { let clause_loc = code.len(); - let mut prepend_queue = sdeq![]; + let mut prepend_queue = VecDeque::new(); 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(); @@ -995,7 +993,7 @@ fn prepend_compiled_clause( merge_clause_index( target_indexing_line, - &mut skeleton.clauses, + skeleton.clauses.make_contiguous(), &skeleton.core.retracted_dynamic_clauses, clause_loc + 2, // == skeleton.clauses[0].clause_start AppendOrPrepend::Prepend, @@ -1189,7 +1187,7 @@ fn append_compiled_clause( merge_clause_index( target_indexing_line, - &mut skeleton.clauses[lower_bound..], + &mut skeleton.clauses.make_contiguous()[lower_bound..], &skeleton.core.retracted_dynamic_clauses, clause_loc, AppendOrPrepend::Append, @@ -1406,7 +1404,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { )?; if settings.is_extensible { - let mut clause_clause_locs = sdeq![]; + let mut clause_clause_locs = VecDeque::new(); for clause_index_info in cg.skeleton.clauses.iter_mut() { clause_index_info.clause_start += code_len; @@ -1434,7 +1432,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { skeleton .core .clause_clause_locs - .extend_from_slice(&clause_clause_locs[0..]); + .extend(&clause_clause_locs.make_contiguous()[0..]); self.payload.retraction_info .push_record(RetractionRecord::SkeletonClauseTruncateBack( @@ -1447,7 +1445,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { cg.skeleton .core .clause_clause_locs - .extend_from_slice(&clause_clause_locs[0..]); + .extend(&clause_clause_locs.make_contiguous()[0..]); let skeleton = cg.skeleton; @@ -1495,7 +1493,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { &mut self, compilation_target: &CompilationTarget, key: &PredicateKey, - clause_clause_locs: SliceDeque, + mut clause_clause_locs: VecDeque, ) { let listing_src_file_name = self.listing_src_file_name(); @@ -1519,7 +1517,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { skeleton .clause_clause_locs - .extend_from_slice(&clause_clause_locs[0..]); + .extend(&clause_clause_locs.make_contiguous()[0..]); } None => { let mut skeleton = LocalPredicateSkeleton::new(); @@ -1972,7 +1970,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { code, later_indexing_loc, 0..target_pos - lower_bound, - &mut skeleton.clauses[lower_bound..], + &mut skeleton.clauses.make_contiguous()[lower_bound..], &skeleton.core.retracted_dynamic_clauses, &mut self.payload.retraction_info, ); @@ -1997,7 +1995,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { code, target_indexing_loc, target_pos + 1 - lower_bound..skeleton.clauses.len() - lower_bound, - &mut skeleton.clauses[lower_bound..], + &mut skeleton.clauses.make_contiguous()[lower_bound..], &skeleton.core.retracted_dynamic_clauses, &mut self.payload.retraction_info, ); @@ -2196,15 +2194,17 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { { Some(skeleton) if append_or_prepend.is_append() => { let tail_num = skeleton.core.clause_clause_locs.len() - num_clause_predicates; - skeleton.core.clause_clause_locs[tail_num..] + skeleton.core.clause_clause_locs.make_contiguous()[tail_num..] + .iter() + .cloned() + .collect() + } + Some(skeleton) => { + skeleton.core.clause_clause_locs.make_contiguous()[0..num_clause_predicates] .iter() .cloned() .collect() } - Some(skeleton) => skeleton.core.clause_clause_locs[0..num_clause_predicates] - .iter() - .cloned() - .collect(), None => { unreachable!() } diff --git a/src/machine/load_state.rs b/src/machine/load_state.rs index 1ad94f15..e7f88095 100644 --- a/src/machine/load_state.rs +++ b/src/machine/load_state.rs @@ -10,8 +10,8 @@ use crate::parser::ast::*; use fxhash::FxBuildHasher; use indexmap::IndexSet; use ref_thread_local::RefThreadLocal; -use slice_deque::{sdeq, SliceDeque}; +use std::collections::VecDeque; use std::fs::File; use std::mem; @@ -334,12 +334,12 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { &mut self, compilation_target: CompilationTarget, key: PredicateKey, - clause_locs: &SliceDeque, + clause_locs: &VecDeque, ) { let result_opt = self .wam_prelude .indices - .get_predicate_skeleton(&compilation_target, &key) + .get_predicate_skeleton_mut(&compilation_target, &key) .map(|skeleton| { ( clause_locs @@ -396,7 +396,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { pub(super) fn retract_local_clause_clauses( &mut self, clause_clause_compilation_target: CompilationTarget, - clause_locs: &SliceDeque, + clause_locs: &VecDeque, ) { let key = (atom!("$clause"), 2); let listing_src_file_name = self.listing_src_file_name(); @@ -415,7 +415,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { payload_compilation_target, clause_clause_compilation_target, key, - mem::replace(&mut skeleton.clause_clause_locs, sdeq![]), + mem::replace(&mut skeleton.clause_clause_locs, VecDeque::new()), ), ); diff --git a/src/machine/loader.rs b/src/machine/loader.rs index 2ab85de4..bf7456be 100644 --- a/src/machine/loader.rs +++ b/src/machine/loader.rs @@ -14,9 +14,9 @@ use crate::parser::ast::*; use crate::types::*; use indexmap::IndexSet; -use slice_deque::{sdeq, SliceDeque}; use std::cell::Cell; +use std::collections::VecDeque; use std::convert::TryFrom; use std::fmt; use std::mem; @@ -96,7 +96,7 @@ pub(crate) enum RetractionRecord { CompilationTarget, CompilationTarget, PredicateKey, - SliceDeque, + VecDeque, ), RemovedSkeleton(CompilationTarget, PredicateKey, PredicateSkeleton), ReplacedDynamicElseOffset(usize, usize), @@ -900,7 +900,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { key, ) { Some(skeleton) => { - skeleton.clause_clause_locs.truncate_back(len); + skeleton.clause_clause_locs.truncate(len); } None => {} } @@ -912,8 +912,8 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { .get_predicate_skeleton_mut(&compilation_target, &key) { Some(skeleton) => { - skeleton.clauses.truncate_back(len); - skeleton.core.clause_clause_locs.truncate_back(len); + skeleton.clauses.truncate(len); + skeleton.core.clause_clause_locs.truncate(len); } None => {} } @@ -1358,7 +1358,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { *key, ) { Some(skeleton) if !skeleton.clause_clause_locs.is_empty() => { - mem::replace(&mut skeleton.clause_clause_locs, sdeq![]) + mem::replace(&mut skeleton.clause_clause_locs, VecDeque::new()) } _ => return, }; @@ -1973,33 +1973,42 @@ impl Machine { let mut clause_clause_target_poses: Vec<_> = loader .wam_prelude .indices - .get_predicate_skeleton(&compilation_target, &key) + .remove_predicate_skeleton(&compilation_target, &key) .map(|skeleton| { - loader + let mut clause_clause_skeleton = loader .wam_prelude .indices - .get_predicate_skeleton( + .remove_predicate_skeleton( &clause_clause_compilation_target, &(atom!("$clause"), 2), - ) - .map(|clause_clause_skeleton| { - skeleton - .core - .clause_clause_locs - .iter() - .map(|clause_clause_loc| { - clause_clause_skeleton - .target_pos_of_clause_clause_loc(*clause_clause_loc) - .unwrap() - }) - .collect() + ).unwrap(); + + let result = skeleton.core + .clause_clause_locs + .iter() + .map(|clause_clause_loc| { + clause_clause_skeleton + .target_pos_of_clause_clause_loc(*clause_clause_loc) + .unwrap() }) - .unwrap() - }) - .unwrap(); + .collect(); - loader - .wam_prelude + loader.add_extensible_predicate( + key, + skeleton, + compilation_target, + ); + + loader.add_extensible_predicate( + (atom!("$clause"), 2), + clause_clause_skeleton, + clause_clause_compilation_target, + ); + + result + }).unwrap(); + + loader.wam_prelude .indices .remove_predicate_skeleton(&compilation_target, &key); @@ -2008,15 +2017,6 @@ impl Machine { code_index.set(IndexPtr::Undefined); - /* - loader - .wam_prelude - .indices - .get_predicate_skeleton_mut(&compilation_target, &key) - .map(|skeleton| skeleton.reset()); - - */ - loader.payload.compilation_target = clause_clause_compilation_target; while let Some(target_pos) = clause_clause_target_poses.pop() { @@ -2076,7 +2076,7 @@ impl Machine { // the global clock is incremented after each retraction. LiveLoadAndMachineState::machine_st(&mut loader.payload).global_clock += 1; - let target_pos = match loader.wam_prelude.indices.get_predicate_skeleton( + let target_pos = match loader.wam_prelude.indices.get_predicate_skeleton_mut( &clause_clause_compilation_target, &(atom!("$clause"), 2), ) { -- 2.54.0