From 3ae0cf9898485a2ec35df7d23cd274e7dea5796d Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 8 Jan 2024 16:13:19 +0800 Subject: a commit before the forst query I think the main functionalities are already there, but the lack of querying capabilities makes this not very useful at the moment. This commit is right before an attempt to add this missing piece. --- forest/src/bytes.rs | 280 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 280 insertions(+) (limited to 'forest/src/bytes.rs') 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>(forest: &F) -> Vec { 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, + /// 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 for BytesError { + fn from(value: TryFromSliceError) -> Self { + Self::WrongSliceConversion(value) + } +} + +impl std::error::Error for BytesError {} + +impl TryFrom> for BytesForest { + type Error = BytesError; + + fn try_from(bytes: Vec) -> Result { + 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 { + 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) { + (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, 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 { + 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 { + Ok(self.degree(node_id)? == 0) + } + + fn has_edge(&self, source: usize, target: usize) -> Result { + 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) { + let result = builder.build(); + + self.nodes_len = result.nodes_len; + self.offset = result.offset; + self.bytes = result.bytes; + } +} + +// TODO: Implement labelgraph -- cgit v1.2.3-18-g5258