diff options
Diffstat (limited to 'forest/src/bytes.rs')
| -rw-r--r-- | forest/src/bytes.rs | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/forest/src/bytes.rs b/forest/src/bytes.rs index 951abad..d0d7e1e 100644 --- a/forest/src/bytes.rs +++ b/forest/src/bytes.rs @@ -78,6 +78,9 @@ use super::Forest; use grammar::{GrammarLabel, GrammarLabelType, TNT}; +use graph::error::Error as GError; + +use std::array::TryFromSliceError; /// Convert any type that implements the `Forest` trait into a /// sequence of bytes. @@ -174,3 +177,280 @@ pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> { bytes } + +/// The type of a forest that is represented as a sequence of bytes. +#[derive(Debug, Clone, Default)] +pub struct BytesForest { + /// The sequence of bytes. + bytes: Vec<u8>, + /// The number of nodes. + nodes_len: usize, + /// The offset of labels + offset: usize, +} + +/// The errors encountered when parsing a sequence of bytes into a +/// forest. +#[derive(Debug)] +pub enum BytesError { + /// File size and forest length do not match. + LengthNotMatched(usize, usize), + /// The underlying sequence has the wrong length. + WrongBytesLen(usize, usize), + /// The file is too small. + TooSmall(usize, usize), + /// The special mark at the beginning is corrupted. + SpecialCorrupted(u8, u8, u8), + /// An error occurs during conversion of slices. + WrongSliceConversion(TryFromSliceError), + /// The data indicates a wrong offset. + InvalidOffset(usize, usize), + /// Wrong node index. + WrongNodeIndex(usize, usize), +} + +impl std::fmt::Display for BytesError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::WrongBytesLen(wrong, correct) => write!( + f, + "the sequence has length {wrong} but should have length {correct}" + ), + Self::LengthNotMatched(file, forest) => write!( + f, + "the file size is {file}, but the file indicates that the size should be {forest}" + ), + Self::TooSmall(len, threshold) => { + write!(f, "the file size {len} is less than {threshold} bytes") + } + Self::SpecialCorrupted(a, b, c) => { + write!(f, "the special mark is [{a}, {b}, {c}] which is wrong") + } + Self::WrongSliceConversion(e) => { + write!(f, "error during slice conversion: {e}") + } + Self::InvalidOffset(offset, len) => write!( + f, + "Data says offset = {offset} but the total length is {len}" + ), + Self::WrongNodeIndex(index, len) => write!( + f, + "node index {index} is greater than or equal to the length {len} of nodes" + ), + } + } +} + +impl From<TryFromSliceError> for BytesError { + fn from(value: TryFromSliceError) -> Self { + Self::WrongSliceConversion(value) + } +} + +impl std::error::Error for BytesError {} + +impl TryFrom<Vec<u8>> for BytesForest { + type Error = BytesError; + + fn try_from(bytes: Vec<u8>) -> Result<Self, Self::Error> { + let forest_len = bytes.len(); + + if forest_len < 27 { + return Err(BytesError::TooSmall(forest_len, 27)); + } + + let indicated_len = usize::from_be_bytes((&bytes[..8]).try_into()?); + + if forest_len != indicated_len { + return Err(BytesError::LengthNotMatched(forest_len, indicated_len)); + } + + let nodes_len = usize::from_be_bytes((&bytes[11..19]).try_into()?); + + let special_marks = &bytes[8..11]; + + if special_marks != [114, 101, 112] { + return Err(BytesError::SpecialCorrupted( + special_marks[0], + special_marks[1], + special_marks[2], + )); + } + + let offset = usize::from_be_bytes((&bytes[19..27]).try_into()?); + + let threshold = std::cmp::max(offset + 34 * nodes_len, 27 + 16 * nodes_len); + + if forest_len < threshold { + return Err(BytesError::TooSmall(forest_len, threshold)); + } + + let mut total_degree = 0usize; + + for node in 0..nodes_len { + let degree = + usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?); + + total_degree += degree; + } + + let total_degree = total_degree; + + let correct_len: usize = 27 + 50 * nodes_len + 8 * total_degree; + + if forest_len != correct_len { + return Err(BytesError::WrongBytesLen(forest_len, correct_len)); + } + + for node in 0..nodes_len { + let degree = + usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?); + + let node_offset = + usize::from_be_bytes((&bytes[(35 + 16 * node)..(43 + 16 * node)]).try_into()?); + + if forest_len <= node_offset + 8 * degree { + return Err(BytesError::InvalidOffset(node_offset, forest_len)); + } + + for n in 0..degree { + let target = usize::from_be_bytes( + (&bytes[(node_offset + 8 * n)..(node_offset + 8 * n + 8)]).try_into()?, + ); + + if nodes_len <= target { + return Err(BytesError::WrongNodeIndex(target, nodes_len)); + } + } + } + + Ok(Self { + bytes, + nodes_len, + offset, + }) + } +} + +/// The delegation of iterators for children of nodes. +#[derive(Debug, Clone)] +pub struct BytesChildrenIter<'a> { + vec: &'a [u8], + offset: usize, + degree: usize, + current: usize, +} + +impl<'a> Iterator for BytesChildrenIter<'a> { + type Item = usize; + + fn next(&mut self) -> Option<Self::Item> { + if self.current + 1 >= self.degree { + return None; + } + + let len = self.vec.len(); + + if self.offset + 8 * self.degree > len { + dbg!(); + return None; + } + + Some(usize::from_be_bytes( + (&self.vec[(self.offset + 8 * self.current)..(self.offset + 8 * self.current + 8)]) + .try_into() + .ok()?, + )) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.degree, Some(self.degree)) + } +} + +impl<'a> ExactSizeIterator for BytesChildrenIter<'a> { + fn len(&self) -> usize { + self.degree + } +} + +impl graph::Graph for BytesForest { + type Iter<'a> = BytesChildrenIter<'a> + where + Self: 'a; + + fn is_empty(&self) -> bool { + self.bytes.is_empty() + } + + fn nodes_len(&self) -> usize { + self.nodes_len + } + + fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> { + if node_id >= self.nodes_len { + return Err(GError::IndexOutOfBounds(node_id, self.nodes_len)); + } + + let degree = usize::from_be_bytes( + (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let offset = usize::from_be_bytes( + (&self.bytes[(35 + 16 * node_id)..(43 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let current = 0; + + let vec = &self.bytes; + + Ok(BytesChildrenIter { + vec, + offset, + degree, + current, + }) + } + + fn degree(&self, node_id: usize) -> Result<usize, GError> { + if node_id >= self.nodes_len { + return Err(GError::IndexOutOfBounds(node_id, self.nodes_len)); + } + + let degree = usize::from_be_bytes( + (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + Ok(degree) + } + + fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> { + Ok(self.degree(node_id)? == 0) + } + + fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> { + for child in self.children_of(source)? { + if child == target { + return Ok(true); + } + } + + Ok(false) + } + + fn replace_by_builder(&mut self, builder: impl graph::Builder<Result = Self>) { + let result = builder.build(); + + self.nodes_len = result.nodes_len; + self.offset = result.offset; + self.bytes = result.bytes; + } +} + +// TODO: Implement labelgraph |