From aa1fd869a1736d33c980ae652eea845b7d12d1c8 2022-02-15 10:16:16 From: mh Date: 2022-02-15 10:16:16 Subject: [PATCH] Refactored type table --- diff --git a/src/protocol/parser/type_table.rs b/src/protocol/parser/type_table.rs index 2c41358e636475fcb6570524a23047baa4072bf6..db185dcb1b7bd322239cbdde25ffb4c83505bfa8 100644 --- a/src/protocol/parser/type_table.rs +++ b/src/protocol/parser/type_table.rs @@ -401,13 +401,21 @@ impl MonoType { /// that have already been added to the type table before. #[derive(Clone)] struct MonoSearchKey { - parts: Vec<(bool, ConcreteTypePart)>, + // Uses bitflags to denote when parts between search keys should match and + // whether they should be checked. Needs to have a system like this to + // accommodate tuples. + parts: Vec<(u8, ConcreteTypePart)>, + change_bit: u8, } impl MonoSearchKey { + const KEY_IN_USE: u8 = 0x01; + const KEY_CHANGE_BIT: u8 = 0x02; + fn with_capacity(capacity: usize) -> Self { return MonoSearchKey{ parts: Vec::with_capacity(capacity), + change_bit: 0, }; } @@ -431,17 +439,23 @@ impl MonoSearchKey { /// after calling this function fn set_top_type(&mut self, type_part: ConcreteTypePart) { self.parts.clear(); - self.parts.push((true, type_part)); + self.parts.push((self.change_bit | Self::KEY_IN_USE, type_part)); + self.change_bit ^= Self::KEY_CHANGE_BIT; } fn push_subtype(&mut self, concrete_type: &[ConcreteTypePart], in_use: bool) { + let flag = self.change_bit | (if in_use { Self::KEY_IN_USE } else { 0 }); + for part in concrete_type { - self.parts.push((in_use, *part)); + self.parts.push((flag, *part)); } + self.change_bit ^= Self::KEY_CHANGE_BIT; } fn push_subtree(&mut self, concrete_type: &[ConcreteTypePart], poly_var_in_use: &[PolymorphicVariable]) { - self.parts.push((true, concrete_type[0])); + self.parts.push((self.change_bit | Self::KEY_IN_USE, concrete_type[0])); + self.change_bit ^= Self::KEY_CHANGE_BIT; + let mut poly_var_index = 0; for subtype in ConcreteTypeIter::new(concrete_type, 0) { let in_use = poly_var_in_use[poly_var_index].is_in_use; @@ -451,15 +465,38 @@ impl MonoSearchKey { debug_assert_eq!(poly_var_index, poly_var_in_use.len()); } + + // Utilities for hashing and comparison + fn find_end_index(&self, start_index: usize) -> usize { + // Check if we're already at the end + let mut index = start_index; + if index >= self.parts.len() { + return index; + } + + // Iterate until bit flips, or until at end + let expected_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT; + + index += 1; + while index < self.parts.len() { + let current_bit = self.parts[index].0 & Self::KEY_CHANGE_BIT; + if current_bit != expected_bit { + return index; + } + + index += 1; + } + + return self.parts.len(); + } } impl Hash for MonoSearchKey { fn hash(&self, state: &mut H) { for index in 0..self.parts.len() { - let is_in_use = self.parts[index].0; - if is_in_use { - let type_part = &self.parts[index].1; - type_part.hash(state); + let (flags, part) = self.parts[index]; + if flags & Self::KEY_IN_USE != 0 { + part.hash(state); } } } @@ -471,26 +508,49 @@ impl PartialEq for MonoSearchKey { let mut other_index = 0; while self_index < self.parts.len() && other_index < other.parts.len() { - let (self_in_use, self_part) = &self.parts[self_index]; - let (other_in_use, other_part) = &other.parts[self_index]; - let self_end_index = ConcreteType::type_parts_subtree_end_idx(&self.parts, ) + // Retrieve part and flags + let (self_bits, _) = self.parts[self_index]; + let (other_bits, _) = other.parts[other_index]; + let self_in_use = (self_bits & Self::KEY_IN_USE) != 0; + let other_in_use = (other_bits & Self::KEY_IN_USE) != 0; + + // Determine ending indices + let self_end_index = self.find_end_index(self_index); + let other_end_index = other.find_end_index(other_index); + + if self_in_use == other_in_use { - if *self_in_use { - // Both are in use, so both should be equal - if self_part != other_part { + if self_in_use { + // Both are in use, so both parts should be equal + let delta_self = self_end_index - self_index; + let delta_other = other_end_index - other_index; + if delta_self != delta_other { + // Both in use, but not of equal length, so the types + // cannot match return false; } - self_index - } // else: both not in use, so we don't care + for _ in 0..delta_self { + let (_, self_part) = self.parts[self_index]; + let (_, other_part) = self.parts[other_index]; + + if self_part != other_part { + return false; + } + + self_index += 1; + other_index += 1; + } + } else { + // Both not in use, so skip associated parts + self_index = self_end_index; + other_index = other_end_index; + } } else { // No agreement on importance of parts. This is practically // impossible unreachable!(); } - - self_index = ConcreteType::type_parts_subtree_end_idx(); - other_index += 1; } // Everything matched, so if we're at the end of both arrays then we're diff --git a/src/protocol/tests/parser_monomorphs.rs b/src/protocol/tests/parser_monomorphs.rs index 76e6004ddd79e3bad7b879cbeb65c9e21c87a139..2926b727bfa3360ea90779f6de4d5f43ab281694 100644 --- a/src/protocol/tests/parser_monomorphs.rs +++ b/src/protocol/tests/parser_monomorphs.rs @@ -71,8 +71,8 @@ fn test_enum_monomorphs() { } " ).for_enum("Answer", |e| { e - .assert_has_monomorph("2Answer") - .assert_num_monomorphs(1); + .assert_num_monomorphs(1) + .assert_has_monomorph("Answer"); }); }