new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

1 files changed, 991 insertions, 0 deletions

diff --git a/forest/src/iter/archive.txt b/forest/src/iter/archive.txt
new file mode 100644
index 0000000..dcdae7f
--- /dev/null
+++ b/forest/src/iter/archive.txt
@@ -0,0 +1,991 @@
+/// Archive of failed attempts
+
+/// The label of a query graph.
+///
+/// Such a label is responsible for matching forest labels.
+pub trait QueryLabel: GraphLabel {
+    /// The type of labels this matches against.
+    type Obj: GraphLabel;
+
+    /// Determine whether or not a label matches this query label.
+    fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool {
+        let _ = label;
+        let _ = status;
+
+        false
+    }
+
+    /// Perform the query for one single query label.
+    fn run<F>(
+        &self,
+        forest: &F,
+        node: usize,
+        packs: &mut Vec<(usize, usize)>,
+    ) -> Result<Option<usize>, QRError>
+    where
+        F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>,
+    {
+        let mut dfs_stack: Vec<usize> = vec![node];
+
+        let nodes_len = forest.nodes_len();
+
+        while let Some(node) = dfs_stack.pop() {
+            let label = match forest.vertex_label(node) {
+                Ok(None) => return Err(QRError::NodeNoLabel(node)),
+                Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)),
+                Ok(Some(label)) => label,
+            };
+
+            let status = label.status();
+            let label = label.label();
+
+            if status == ForestLabelType::Packed {
+                packs.push((node, 0));
+
+                dfs_stack.extend(forest.children_of(node).unwrap().take(1));
+
+                continue;
+            }
+
+            if self.matches(label, status) {
+                return Ok(Some(node));
+            }
+
+            dfs_stack.extend(
+                forest
+                    .children_of(node)
+                    .unwrap()
+                    .collect::<Vec<_>>()
+                    .into_iter()
+                    .rev(),
+            );
+        }
+
+        Ok(None)
+    }
+}
+
+/// How should the current query skip nodes
+#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)]
+pub enum SkipState {
+    /// Skip anything in the depth-first search
+    Any,
+    /// Skip siblings
+    Sibling,
+    /// Do not skip
+    #[default]
+    None,
+}
+
+impl std::fmt::Display for SkipState {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::Any => write!(f, "skip anything"),
+            Self::Sibling => write!(f, "skip siblings"),
+            Self::None => write!(f, "no skipping"),
+        }
+    }
+}
+
+impl From<bool> for SkipState {
+    fn from(value: bool) -> Self {
+        if value {
+            Self::Sibling
+        } else {
+            Self::None
+        }
+    }
+}
+
+/// A branch switch is of the form (n, m, v), where n means the n-th
+/// node in the forest and m means the m-th child, and v is the vector
+/// of children of the packed node.
+#[derive(Debug, Clone, Default)]
+pub struct BranchSwitch {
+    n: usize,
+    m: usize,
+    v: Vec<usize>,
+}
+
+impl BranchSwitch {
+    #[allow(dead_code)]
+    fn new(n: usize, m: usize, v: Vec<usize>) -> Self {
+        Self { n, m, v }
+    }
+
+    #[allow(dead_code)]
+    fn node(&self) -> usize {
+        self.n
+    }
+
+    #[allow(dead_code)]
+    fn child(&self) -> Option<usize> {
+        self.v.get(self.m).copied()
+    }
+
+    #[allow(dead_code)]
+    fn advance(&mut self) -> bool {
+        if self.m < self.v.len() {
+            self.m += 1;
+
+            return true;
+        }
+
+        false
+    }
+}
+
+// REVIEW: Change the types into boxed slices so that we can guarantee
+// no capacity is ever wasted.
+
+/// The type of forests that would be walked.
+///
+/// In plain terms this is a preprocessed graph that provides some
+/// extra information than a plain graph, which will be useful in
+/// walking.
+#[derive(Debug, Clone)]
+#[allow(unused)]
+pub struct QForest {
+    current: Option<usize>,
+    /// Just for example uses.
+    pub dfs_next: Vec<usize>,
+    /// Just for example uses.
+    pub subtree_ranges: Vec<std::ops::RangeInclusive<usize>>,
+    // /// Just for example uses.
+    // pub next_branch: Vec<Option<usize>>,
+    num_seen_switches: usize,
+    /// Switches of branches are packed nodes along with the current
+    /// index of the child.  One can switch to use a different child
+    /// to "switch branches".
+    pub branch_switches: Vec<BranchSwitch>,
+    /// Map ordinary node numbering to depth-first numbering.
+    ord_to_dfs: Vec<usize>,
+    /// Map depth-first numbering to ordinary node numbering.
+    dfs_to_ord: Vec<usize>,
+    restriction: Option<usize>,
+}
+
+impl QForest {
+    fn new(
+        dfs_next: Vec<usize>,
+        subtree_ranges: Vec<std::ops::RangeInclusive<usize>>,
+        // next_branch: Vec<Option<usize>>,
+        branch_switches: Vec<BranchSwitch>,
+        ord_to_dfs: Vec<usize>,
+        dfs_to_ord: Vec<usize>,
+    ) -> Self {
+        let current: Option<usize> = None;
+        let restriction: Option<usize> = None;
+        let num_seen_switches = 0usize;
+
+        Self {
+            current,
+            dfs_next,
+            subtree_ranges,
+            // next_branch,
+            num_seen_switches,
+            branch_switches,
+            restriction,
+            ord_to_dfs,
+            dfs_to_ord,
+        }
+    }
+
+    /// Translate the node index from ordinary index to depth-first
+    /// index.
+    pub fn translate_to_dfs(&self, id: usize) -> Option<usize> {
+        self.ord_to_dfs.get(id).copied()
+    }
+
+    /// Translate the node index from depth-first index to ordinary
+    /// index.
+    pub fn translate_from_dfs(&self, id: usize) -> Option<usize> {
+        self.dfs_to_ord.get(id).copied()
+    }
+}
+
+impl Default for QForest {
+    fn default() -> Self {
+        let current = Default::default();
+        let dfs_next = Default::default();
+        let subtree_ranges = Default::default();
+        // let next_branch = Default::default();
+        let branch_switches = Default::default();
+        let restriction = Default::default();
+        let num_seen_switches = 0usize;
+
+        let ord_to_dfs = Default::default();
+        let dfs_to_ord = Default::default();
+
+        Self {
+            current,
+            dfs_next,
+            subtree_ranges,
+            // next_branch,
+            num_seen_switches,
+            branch_switches,
+            restriction,
+            ord_to_dfs,
+            dfs_to_ord,
+        }
+    }
+}
+
+impl Queryable for QForest {
+    fn current(&self) -> Option<usize> {
+        self.current
+    }
+
+    fn next(&mut self) -> bool {
+        let current = if let Some(current) = self.current {
+            current
+        } else {
+            return false;
+        };
+
+        let mut next = if let Some(next) = self.dfs_next.get(current) {
+            *next
+        } else {
+            return false;
+        };
+
+        match self.branch_switches.get(self.num_seen_switches) {
+            Some(switch) if switch.node() == next => {
+                if let Some(child) = switch.child() {
+                    next = child;
+                }
+
+                self.num_seen_switches += 1;
+            }
+            _ => {}
+        }
+
+        let dfs_len = self.dfs_next.len();
+
+        if (0..dfs_len).contains(&next) {
+            self.current.replace(next);
+
+            true
+        } else {
+            false
+        }
+    }
+
+    fn next_branch(&mut self) -> bool {
+        self.branch_switches.iter_mut().any(BranchSwitch::advance)
+
+        // let current = if let Some(current) = self.current {
+        //     current
+        // } else {
+        //     return false;
+        // };
+
+        // let next = if let Some(next) = self.next_branch.get(current).copied().flatten() {
+        //     next
+        // } else {
+        //     return false;
+        // };
+
+        // self.current.replace(next);
+
+        // true
+    }
+
+    fn restrict(&mut self, node: usize) -> bool {
+        let range = if let Some(range) = self.subtree_ranges.get(node) {
+            range
+        } else {
+            return false;
+        };
+
+        self.restriction.replace(node);
+
+        let current = if let Some(current) = &self.current {
+            current
+        } else {
+            return false;
+        };
+
+        range.contains(current)
+    }
+}
+
+/// Calculate some extra information for later processing.
+pub fn preprocess_forest<T, F>(forest: F, root: usize) -> Result<QForest, GError>
+where
+    T: GraphLabel,
+    F: LabelGraph<ForestLabel<T>>,
+{
+    let forest_len = forest.nodes_len();
+
+    // let current: Option<usize> = None;
+
+    let mut dfs_next: Vec<usize> = (0..forest_len).map(|i| i + 1).collect();
+
+    let mut subtree_ranges: Vec<std::ops::RangeInclusive<usize>> =
+        (0..forest_len).map(|i| i..=i).collect();
+
+    // let next_branch: Vec<Option<usize>> = std::iter::repeat(None).take(forest_len).collect();
+
+    let mut branch_switches: Vec<BranchSwitch> = Vec::with_capacity(forest_len);
+
+    // let restriction: Option<usize> = None;
+
+    let mut dfs_to_ord: Vec<usize> = (0..forest_len).collect();
+    let mut ord_to_dfs: Vec<usize> = (0..forest_len).collect();
+
+    if forest.is_empty_node(root).unwrap_or(true) {
+        if let Some(root_item) = dfs_next.get_mut(root) {
+            *root_item = forest_len; // out of bounds
+        }
+
+        return Ok(QForest::new(
+            // current,
+            dfs_next,
+            subtree_ranges,
+            // next_branch,
+            // restriction,
+            branch_switches,
+            ord_to_dfs,
+            dfs_to_ord,
+        ));
+    }
+
+    #[derive(Debug, Clone, Copy)]
+    enum StackItem {
+        Normal(usize),
+        Reflection(usize),
+    }
+
+    impl From<usize> for StackItem {
+        fn from(value: usize) -> Self {
+            Self::Normal(value)
+        }
+    }
+
+    impl StackItem {
+        fn is_normal(&self) -> bool {
+            matches!(self, Self::Normal(_))
+        }
+
+        fn get_value(&self) -> usize {
+            match *self {
+                StackItem::Normal(item) => item,
+                StackItem::Reflection(item) => item,
+            }
+        }
+
+        fn reflect(&self) -> Self {
+            match self {
+                StackItem::Normal(item) => Self::Reflection(*item),
+                StackItem::Reflection(_) => *self,
+            }
+        }
+    }
+
+    let mut stack: Vec<StackItem> = Vec::with_capacity(forest_len);
+
+    let mut prev = root;
+
+    let mut children_vec: Vec<usize> = Vec::with_capacity(forest_len);
+
+    stack.extend({
+        children_vec.extend(forest.children_of(root)?);
+
+        children_vec.iter().copied().rev().map(StackItem::from)
+    });
+
+    let mut seen_nodes: HashMap<usize, Option<usize>> = HashMap::with_capacity(forest_len);
+
+    seen_nodes.insert(root, None);
+
+    let mut dfs_order = 1usize;
+
+    while let Some(top) = stack.pop() {
+        let top_value = top.get_value();
+        let top_label = forest
+            .vertex_label(top_value)?
+            .expect("node without label: {top_value}");
+        if top.is_normal() {
+            if let Some(prev_item) = dfs_next.get_mut(prev) {
+                *prev_item = top_value;
+            }
+
+            if let std::collections::hash_map::Entry::Vacant(e) = seen_nodes.entry(top_value) {
+                if let Some(item) = dfs_to_ord.get_mut(dfs_order) {
+                    *item = top_value;
+                }
+
+                if let Some(item) = ord_to_dfs.get_mut(top_value) {
+                    *item = dfs_order;
+                }
+
+                dfs_order += 1;
+
+                stack.push(top.reflect());
+
+                e.insert(top_label.clone_index().map(|_| prev));
+
+                children_vec.clear();
+
+                children_vec.extend(forest.children_of(top_value)?);
+
+                stack.extend(children_vec.iter().copied().rev().map(StackItem::from));
+            }
+
+            prev = top_value;
+        } else {
+            if let Some(range) = subtree_ranges.get_mut(top_value) {
+                let top_dfs = ord_to_dfs.get(top_value).copied().unwrap();
+                let prev_dfs = ord_to_dfs.get(prev).copied().unwrap();
+
+                *range = top_dfs..=prev_dfs;
+            }
+
+            // if top_is_cloned {
+            //     if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) {
+            //         // update branches
+            //         let top_dfs = ord_to_dfs.get(top_value).copied().unwrap();
+            //         let prev_dfs = ord_to_dfs.get(prev).copied().unwrap();
+
+            //         for i in (top_dfs + 1)..=prev_dfs {
+            //             let j = dfs_to_ord.get(i).copied().unwrap();
+
+            //             match next_branch.get_mut(j) {
+            //                 Some(branch) if branch.is_none() => {
+            //                     *branch = Some(next.get_value());
+            //                 }
+
+            //                 _ => {}
+            //             }
+            //         }
+            //     }
+            // }
+
+            if !top_label.is_packed() {
+                continue;
+            }
+
+            let top_children: Vec<usize> = forest.children_of(top_value)?.collect();
+
+            if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) {
+                for child in top_children.iter() {
+                    let child_prev = if let Some(Some(item)) = seen_nodes.get(child) {
+                        *item
+                    } else {
+                        continue;
+                    };
+
+                    if let Some(prev_item) = dfs_next.get_mut(child_prev) {
+                        *prev_item = next.get_value();
+
+                        // dbg!(child_prev, next.get_value(), child);
+                    }
+                }
+            }
+
+            branch_switches.push(BranchSwitch::new(top_value, 0, top_children));
+        }
+    }
+
+    Ok(QForest::new(
+        // current,
+        dfs_next,
+        subtree_ranges,
+        // next_branch,
+        // restriction,
+        branch_switches,
+        ord_to_dfs,
+        dfs_to_ord,
+    ))
+}
+
+// TODO: The query graph needs the ability to jump to a parent and
+// restore the querying contexts.
+
+/// The type that represents queries as dependency graphs of query
+/// labels.
+///
+/// The labels of vertices are query labels that match against forest
+/// labels, whereas the labels of graphs indicate whether or not the
+/// edge should allow skipping siblings before matching.
+#[derive(Debug, Clone, Graph)]
+pub struct Query<T: QueryLabel> {
+    graph: SLGraph<SkipState>,
+    vertex_labels: Vec<T>,
+    root: Option<usize>,
+}
+
+impl<T: QueryLabel> Query<T> {
+    /// Construct a new query from raw fields.
+    pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self {
+        Self {
+            graph,
+            vertex_labels,
+            root,
+        }
+    }
+
+    /// Return the root of this query.
+    ///
+    /// This returns `None` if and only if the graph is empty.
+    pub fn root(&self) -> Option<usize> {
+        self.root
+    }
+
+    /// Return the label of the given node.
+    ///
+    /// This cannot be implemented as a method of the `LabelGraph`
+    /// trait as the type differs from that of the labels.
+    #[inline]
+    pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> {
+        self.vertex_labels
+            .get(node)
+            .copied()
+            .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len()))
+    }
+}
+
+impl<T: QueryLabel> Default for Query<T> {
+    fn default() -> Self {
+        let graph = Default::default();
+        let vertex_labels = Vec::new();
+        let root = None;
+
+        Self {
+            graph,
+            vertex_labels,
+            root,
+        }
+    }
+}
+
+// delegation of labelgraph
+
+impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> {
+    type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a>
+    where
+        Self: 'a;
+
+    type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a>
+    where
+        Self: 'a;
+
+    type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a>
+    where
+        Self: 'a;
+
+    type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a>
+    where
+        Self: 'a;
+
+    #[inline]
+    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> {
+        self.graph.edge_label(source, target)
+    }
+
+    fn find_children_with_label(
+        &self,
+        _node_id: usize,
+        _label: &SkipState,
+    ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> {
+        unimplemented!("Unsupported operation")
+    }
+
+    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
+        unimplemented!("Unsupported operation")
+    }
+
+    #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.tuples_of(node_id)
+    }
+
+    #[inline]
+    fn has_edge_label(
+        &self,
+        node_id: usize,
+        label: &SkipState,
+        target: usize,
+    ) -> Result<bool, GError> {
+        self.graph.has_edge_label(node_id, label, target)
+    }
+}
+
+#[derive(Debug, Clone)]
+/// The type of errors that can occur when querying forests.
+pub enum QRError {
+    /// An index is out of bounds.
+    IndexOutOfBounds(usize, usize),
+    /// A node has no labels while it is required to have one.
+    NodeNoLabel(usize),
+    /// Encounter an invalid error in converting from an error of
+    /// graphs.
+    InvalidGraphError(GError),
+    /// Not enough memory for vectors.
+    NoMemory(std::collections::TryReserveError),
+}
+
+impl std::fmt::Display for QRError {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            QRError::IndexOutOfBounds(n, b) => {
+                write!(f, "index {n} out of bound {b}")
+            }
+            QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"),
+            QRError::InvalidGraphError(g) => {
+                write!(f, "an invalid error for forest iterators: {g}")
+            }
+            QRError::NoMemory(e) => write!(f, "not enough memory: {e}"),
+        }
+    }
+}
+
+impl std::error::Error for QRError {}
+
+impl From<GError> for QRError {
+    fn from(value: GError) -> Self {
+        match value {
+            GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b),
+            _ => Self::InvalidGraphError(value),
+        }
+    }
+}
+
+impl From<std::collections::TryReserveError> for QRError {
+    fn from(value: std::collections::TryReserveError) -> Self {
+        Self::NoMemory(value)
+    }
+}
+
+/// An implementation of the forest iterator for querying purposes.
+#[derive(Debug, Clone)]
+pub struct QRun<T: QueryLabel> {
+    /// The currently visited node.
+    current: Option<Vec<usize>>,
+    /// The queries dependency graph.
+    query: Query<T>,
+    /// The nodes of the query graph, in the depth-first order.
+    query_dfs: Vec<usize>,
+    /// The nodes of the forest, in the depth-first order.
+    forest_dfs: Vec<usize>,
+    /// The packed nodes that can be used to change to another branch
+    /// if needed.
+    ///
+    /// The tuple is in the following format
+    ///
+    /// (forest_index, query_index),
+    ///
+    /// where the indicies are the indices of nodes, in the
+    /// depth-first order, of the respective graphs.
+    packs: Vec<(usize, usize)>,
+}
+
+impl<T: QueryLabel> Default for QRun<T> {
+    fn default() -> Self {
+        let current = Default::default();
+        let query = Default::default();
+        let packs = Default::default();
+
+        let query_dfs = Default::default();
+        let forest_dfs = Default::default();
+
+        Self {
+            current,
+            query,
+            query_dfs,
+            forest_dfs,
+            packs,
+        }
+    }
+}
+
+impl<T: QueryLabel> ForestIter for QRun<T> {
+    #[inline]
+    fn current(&self) -> Option<&[usize]> {
+        self.current.as_ref().map(|v| &v[..])
+    }
+
+    type ForestLabel = <T as QueryLabel>::Obj;
+
+    type Item<'a> = Option<&'a [usize]>
+    where
+        Self: 'a;
+
+    type Error = QRError;
+
+    #[allow(unused)]
+    #[allow(clippy::collapsible_if)]
+    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
+    where
+        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
+    {
+        #[derive(Debug, Clone, Copy, Default)]
+        enum QueryIndex {
+            /// A normal index
+            Normal(usize),
+            #[default]
+            /// This means the query is now accepting anything.
+            Empty,
+        }
+
+        macro_rules! query_match (
+            ($index:expr, $label:expr, $status:expr) => {
+                if let QueryIndex::Normal($index) = index {
+                    self.query
+                        .label_of_vertex(qtop)
+                        .map(|q| q.matches($label, $status))
+                } else {
+                    Ok(true)
+                }
+            }
+        );
+
+        #[derive(Debug, Clone, Copy)]
+        enum ForestIndex {
+            /// A normal index
+            Normal(usize),
+            /// How many times we fallback in the query graph
+            FallbackTimes(usize),
+        }
+
+        impl ForestIndex {
+            fn is_normal(&self) -> bool {
+                matches!(self, Self::Normal(_))
+            }
+
+            // /// Increment the index if it is normal, decrement it otherwise.
+            // ///
+            // /// Return `None` if the advanced index would be out of bounds.
+            // fn advance_forest_index(&self, forest_len: usize) -> Option<Self> {
+            //     match self {
+            //         ForestIndex::Normal(index) => {
+            //             if *index + 1 >= forest_len {
+            //                 None
+            //             } else {
+            //                 Some(Self::Normal(*index + 1))
+            //             }
+            //         }
+            //         ForestIndex::FallbackTimes(time) => {
+            //             if *time == 0 {
+            //                 None
+            //             } else {
+            //                 Some(Self::FallbackTimes(*time - 1))
+            //             }
+            //         }
+            //     }
+            // }
+
+            fn get_index(&self, current_indices: &[usize]) -> Result<usize, QRError> {
+                match self {
+                    ForestIndex::Normal(index) => Ok(*index),
+                    ForestIndex::FallbackTimes(time) => current_indices
+                        .get(*time)
+                        .copied()
+                        .ok_or(QRError::IndexOutOfBounds(*time, current_indices.len())),
+                }
+            }
+
+            fn get_query_index(&self) -> usize {
+                match self {
+                    ForestIndex::Normal(_) => 0,
+                    ForestIndex::FallbackTimes(time) => *time,
+                }
+            }
+        }
+
+        let query_empty_p = self.query.is_empty();
+
+        let query_len = self.query.nodes_len();
+        let forest_len = forest.nodes_len();
+
+        let query_root = if let Some(r) = self.query.root() {
+            r
+        } else {
+            return Ok(State::Finish);
+        };
+
+        let orig_top: ForestIndex = match &self.current {
+            Some(current) => {
+                // re-starting search
+                ForestIndex::FallbackTimes(current.len() - 1)
+            }
+            None => {
+                // fresh new search
+                ForestIndex::Normal(0)
+            }
+        };
+
+        let mut top = orig_top.get_index(if let Some(current) = &self.current {
+            &current[..]
+        } else {
+            &[]
+        })?;
+
+        let mut qtop = orig_top.get_query_index();
+
+        let mut candidate_captures: Vec<usize> = self
+            .current
+            .clone()
+            .unwrap_or_else(|| std::iter::repeat(0).take(query_len).collect());
+
+        'search: loop {
+            let top_index = self
+                .forest_dfs
+                .get(top)
+                .copied()
+                .ok_or(QRError::IndexOutOfBounds(top, forest_len))?;
+            let top_label = forest
+                .vertex_label(top_index)?
+                .ok_or(QRError::NodeNoLabel(top_index))?;
+
+            if top_label.is_packed() {
+                if forest.is_empty_node(top_index)? {
+                    if self.packs.is_empty() {
+                        return Ok(State::Finish);
+                    } else {
+                        return Ok(State::ChangeBranch);
+                    }
+                }
+
+                top = forest.children_of(top_index)?.next().unwrap();
+
+                continue 'search;
+            }
+
+            let query_label = self
+                .query_dfs
+                .get(qtop)
+                .copied()
+                .and_then(|ind| self.query.label_of_vertex(ind).ok());
+
+            if query_label
+                .map(|label| label.matches(top_label.label(), top_label.status()))
+                .unwrap_or(true)
+            {
+                if let Some(captured_value) = candidate_captures.get_mut(qtop) {
+                    *captured_value = top;
+                }
+
+                top += 1;
+                qtop += 1;
+
+                if query_empty_p || qtop >= query_len {
+                    self.current.replace(candidate_captures);
+
+                    return Ok(State::Continue);
+                }
+            } else if qtop == 0 {
+                if self.packs.is_empty() {
+                    return Ok(State::Finish);
+                } else {
+                    return Ok(State::ChangeBranch);
+                }
+            } else {
+                qtop -= 1;
+            }
+        }
+    }
+
+    #[inline]
+    fn clear(&mut self) {
+        self.current.take();
+        self.packs.clear();
+    }
+}
+
+#[cfg(test)]
+mod test_forest_query {
+    use std::io::Write;
+
+    use super::*;
+
+    #[test]
+    fn test_read_forest() -> Result<(), Box<dyn std::error::Error>> {
+        let mut file = std::fs::OpenOptions::new().read(true).open("forest.rep")?;
+
+        use std::io::Read;
+
+        let mut source: Vec<u8> = Vec::new();
+
+        file.read_to_end(&mut source)?;
+
+        use crate::bytes::BytesForest;
+
+        let bytes_forest = BytesForest::try_from(source)?;
+
+        dbg!(
+            bytes_forest.nodes_len(),
+            bytes_forest.children_of(0)?.collect::<Vec<_>>()
+        );
+
+        #[cfg(feature = "test-print-viz")]
+        bytes_forest.print_viz("test forest.gv")?;
+
+        let preprocessed = preprocess_forest(bytes_forest, 0)?;
+
+        // dbg!(&preprocessed);
+
+        use std::io::BufRead;
+
+        println!("Input a query:");
+        std::io::stdout().flush()?;
+
+        for line in std::io::stdin().lock().lines() {
+            let line = line?;
+
+            if line == "q" {
+                break;
+            }
+
+            let qtype = if line.starts_with('s') {
+                1u8
+            } else if line.starts_with('n') {
+                2u8
+            } else {
+                0u8
+            };
+
+            let type_str: &str;
+
+            let q = if line.starts_with('s') || line.starts_with('n') {
+                if let Ok(n) = line[1..].parse::<usize>() {
+                    n
+                } else {
+                    continue;
+                }
+            } else if let Ok(n) = line.parse::<usize>() {
+                n
+            } else {
+                continue;
+            };
+
+            let ans = match qtype {
+                0 => {
+                    type_str = "dfs";
+                    format!("{:?}", preprocessed.dfs_next.get(q).copied())
+                }
+                1 => {
+                    type_str = "subtree range";
+                    format!("{:?}", preprocessed.subtree_ranges.get(q))
+                }
+                _ => {
+                    type_str = "next branch";
+                    format!("{:?}", "haha")
+                }
+            };
+
+            println!("answer for {type_str} = {ans}");
+
+            println!("Input a query:");
+            std::io::stdout().flush()?;
+        }
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_preprocess() -> Result<(), Box<dyn std::error::Error>> {
+        Ok(())
+    }
+}