path: root/chain/src/archive.txt

// Temporary archive

//        let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(stack.len());
//
//        // dbg!(&stack);
//
//        // self.forest.print_viz("dbg forest.gv").unwrap();
//
//        while let Some(mut top) = stack.pop() {
//            if seen_nodes.contains(&top) {
//                continue;
//            }
//
//            seen_nodes.insert(top);
//
//            let mut top_label = self
//                .forest
//                .vertex_label(top)?
//                .ok_or(Error::NodeNoLabel(top))?;
//
//            if !top_label.is_packed()
//                && matches!(top_label.label().label().tnt(), Some(TNT::Non(_)))
//                && top_label.label().end().is_none()
//            {
//                let degree = self.forest.degree(top)?;
//                let last_index = if degree > 0 { degree - 1 } else { 0 };
//
//                let pos = if degree > 0 {
//                    let last_child = self.forest.nth_child(top, last_index)?;
//                    let last_child_label = self
//                        .forest
//                        .vertex_label(last_child)?
//                        .ok_or(Error::NodeNoLabel(last_child))?
//                        .label();
//                    let last_child_end = last_child_label.end();
//
//                    if !matches!(last_child_label.label().rule(),
//                                 Some(rule) if
//                                 self
//                                 .atom
//                                 .is_accepting(2*rule+1)
//                                 .map_err(index_out_of_bounds_conversion)?)
//                    {
//                        continue;
//                    }
//
//                    if let Some(pos) = last_child_end {
//                        pos
//                    } else {
//                        stack.extend(self.forest.children_of(last_child)?);
//                        continue;
//                    }
//                } else {
//                    top_label.label().start() + 1
//                };
//
//                top = self.forest.splone(top, Some(pos), last_index, true)?;
//                top_label = self
//                    .forest
//                    .vertex_label(top)?
//                    .ok_or(Error::NodeNoLabel(top))?;
//            } else if top_label.is_packed()
//                || top_label.label().label().rule().is_some() && top_label.label().end().is_none()
//            {
//                stack.extend(self.forest.children_of(top)?);
//            }
//
//            if top_label.clone_index().is_some() {
//                let mut parents = self.forest.parents_of(top)?;
//                if parents.len() != 1 {
//                    dbg!(top, top_label, parents.len());
//                    self.forest.print_viz("dbg forest.gv").unwrap();
//                    panic!("0 parent?");
//                }
//
//                top = parents.next().unwrap().node();
//            }
//
//            stack.extend(self.forest.parents_of(top)?.map(|parent| parent.node()));
//        }


// extra reduction archive function

// /// Perform extra reductions.
// ///
// /// To be precise, this function first splones the bottom node,
// /// and then queries the reducer to find the next nodes to splone,
// /// and repeats this process until either we find the top node, or
// /// the reducer says to stop.
// ///
// /// One nuance to note is that after we splone a node, if we split
// /// that node, then the splitted node will have a cloned parent,
// /// see
// /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
// /// for details.  So for each parent pointed out by the reducer,
// /// we need to find its clone that has the splitted node as a
// /// child.
// #[allow(dead_code)]
// fn extra_reductions(
//     &mut self,
//     botop: BoTop,
//     pos: usize,
//     reducer: &Reducer,
//     atom: &DefaultAtom,
// ) -> Result<Vec<usize>, Error> {
//     if botop.bottom() == botop.top() {
//         return Ok(vec![self.node_from_pavi(botop.top())?]);
//     }
// 
//     let top = botop.top();
//     let bottom = botop.bottom();
// 
//     let bottom_closed = self.close_pavi(atom.borrow(), bottom, pos)?;
// 
//     let top_node = self.node_from_pavi(top)?;
//     let bottom_node = self.node_from_pavi(bottom)?;
// 
//     let mut stack = vec![(bottom_closed, bottom_node)];
// 
//     // Exclude duplicate nodes to ensure that no infinite
//     // recursion occurs.  In the future I shall experiment if this
//     // is necessary, and get rid of this if possible.
//     // let mut seen_nodes: HashSet<usize> = Default::default();
// 
//     let mut result = Vec::new();
// 
//     // NOTE: We must query the reducer by the original nodes,
//     // otherwise the reducer has no chance to know about the new
//     // nodes that were created by a previous iteration here.  At
//     // the same time, we must splone a clone of the queried result
//     // which is the parent of the previously sploned node, so that
//     // we are on the right track.
//     //
//     // A summary is that we record both the original node and the
//     // sploned node in the stack, so that we can query by the
//     // original node, and then find the correct clone of the
//     // queried result by means of the sploned node.
// 
//     let mut seen_nodes = HashSet::new();
// 
//     while let Some((bottom_sploned, bottom_original)) = stack.pop() {
//         if seen_nodes.contains(&bottom_original) {
//             continue;
//         }
// 
//         seen_nodes.insert(bottom_original);
// 
//         if pos == 4 {
//             println!("stack popped: {bottom_sploned}, {bottom_original}");
//         }
// 
//         let query_result = reducer.query(bottom_original, top_node);
// 
//         let mut sploned = bottom_sploned;
// 
//         let mut label_set: HashSet<GrammarLabel> = HashSet::with_capacity(query_result.len());
// 
//         if query_result.len() != 0 {
//             if pos == 4 {
//                 println!("reducer:");
//             }
// 
//             for node in query_result {
//                 if pos == 4 {
//                     println!("{node}");
//                 }
// 
//                 label_set.insert(
//                     self.vertex_label(node)?
//                         .ok_or(Error::NodeNoLabel(node))?
//                         .label(),
//                 );
//             }
// 
//             let sploned_label = self
//                 .vertex_label(sploned)?
//                 .ok_or(Error::NodeNoLabel(sploned))?;
// 
//             if sploned_label.clone_index().is_some() {
//                 let mut parents = self.parents_of(sploned)?;
// 
//                 #[cfg(debug_assertions)]
//                 if parents.len() != 1 {
//                     panic!("assumption fails");
//                 }
// 
//                 sploned = parents.next().unwrap().node();
//             }
// 
//             // NOTE: We cannot borrow self mutably and immutably
//             // at the same time, so we have to collect the nodes
//             // first.
//             let mut to_splone = Vec::with_capacity(label_set.len());
// 
//             for rule_parent in self.parents_of(sploned)? {
//                 if self.degree(rule_parent.node())? != 1 {
//                     panic!("assumption fails");
//                 }
// 
//                 for parent in self.parents_of(rule_parent.node())? {
//                     let parent_node = parent.node();
// 
//                     let parent_label = self
//                         .vertex_label(parent_node)?
//                         .ok_or(Error::NodeNoLabel(parent_node))?
//                         .label();
// 
//                     if label_set.contains(&parent_label) {
//                         to_splone.push(parent_node);
//                     }
//                 }
//             }
// 
//             for parent_node in to_splone {
//                 let degree = self.degree(parent_node)?;
//                 let last_index = std::cmp::max(degree, 1) - 1;
//                 let parent_sploned = self.splone(parent_node, Some(pos), last_index, false)?;
// 
//                 stack.push((parent_sploned, parent_node));
//             }
//         } else {
//             result.push(bottom_sploned);
//         }
//     }
// 
//     Ok(result)
// }

// BoTop is now unused

// / TODO: Add a hashmap mapping tuples of forest positions (top,
// / bottom) to vectors of tuples of unsigned integers.  Each tuple
// / represents a non-terminal and a rule.  The tuple means that we need
// / to close the expansion of the non-terminal by the rule position, if
// / we want to move from bottom to top.
// /
// / After we move up one layer, we are now in a new forest position, so
// / we just query again with the new bottom and top.  This means we do
// / not need to clear the map.
// 
// / REVIEW: Why is the above needed?
// 
// // This represents a tuple of bottom and top forest positions.
// //
// // It is supposed to be used as keys to query the reduction
// // information.  See the type [`Reducer`] for more details.
// [derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
// ub(crate) struct BoTop {
//    bottom: PaVi,
//    top: PaVi,
// 
// 
// mpl BoTop {
//    #[allow(dead_code)]
//    pub(crate) fn new(bottom: PaVi, top: PaVi) -> Self {
//        Self { bottom, top }
//    }
// 
//    pub(crate) fn top(&self) -> PaVi {
//        self.top
//    }
// 
//    pub(crate) fn bottom(&self) -> PaVi {
//        self.bottom
//    }
// 


// FIXME: Fix this outdated documentation.
// This hashmap records information for performing extra reductions
// when we insert items.

// When we want to *jump* from the bottom to the top positions in the
// forest, we need to perform a set of reductions, in order to jump
// one layer upwards.  After one step, we query again for the next
// step of reductions to perform.

// # Reduction format

// The value records a set of tuples of the form `(non-terminal,
// starting_position)`.  Such a tuple means we want to reduce from
// the expansion of the given `non-terminal`, which expands from the
// given starting position.  We need to restrict the
// pub(crate) type Reducer = Map<usize, HashSet<usize>>;

// /// Check if every child already has an end.
// fn every_child_is_completed(&self, node_id: usize, atom: &DefaultAtom) -> Result<bool, Error> {
//     let children = self.children_of(node_id)?;

//     if children.len() == 0 {
//         return Ok(true);
//     }

//     let mut pos = self
//         .vertex_label(node_id)?
//         .ok_or(Error::NodeNoLabel(node_id))?
//         .label()
//         .start();

//     let mut last_child_label = None;

//     for child in children {
//         let child_label = self
//             .vertex_label(child)?
//             .ok_or(Error::NodeNoLabel(child))?
//             .label();

//         last_child_label = Some(child_label);

//         if child_label.start() != pos || child_label.end().is_none() {
//             return Ok(false);
//         }

//         pos = child_label.end().unwrap();
//     }

//     if let Some(label) = last_child_label {
//         if let Some(rule) = label.label().rule() {
//             if !atom
//                 .is_accepting(2 * rule + 1)
//                 .map_err(|_| Error::IndexOutOfBounds(2 * rule + 1, atom.nodes_len()))?
//             {
//                 return Ok(false);
//             }
//         }
//     }

//     Ok(true)
// }

// /// Complete the forest by trying to set the ending position of
// /// every node that does not have an end, by the ending position
// /// of its last child.
// pub fn complete(&mut self, atom: &DefaultAtom) -> Result<(), Error> {
//     let mut stack: Vec<_> = self
//         .nodes()
//         .filter(|node| {
//             let label = self.vertex_label(*node).unwrap().unwrap().label();

//             label.label().rule().is_some() && label.end().is_some()
//         })
//         .collect();

//     let mut second_stack: Vec<usize> = Vec::new();

//     let mut pending_candidates: Vec<usize> = Vec::new();

//     let nodes_len = self.nodes_len();

//     let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(nodes_len);

//     while !stack.is_empty() {
//         while let Some(mut top) = stack.pop() {
//             if seen_nodes.contains(&top) {
//                 continue;
//             }

//             seen_nodes.insert(top);

//             let top_label = self.vertex_label(top)?.unwrap();

//             if top_label.clone_index().is_some() {
//                 let mut top_parents = self.parents_of(top)?;

//                 if top_parents.len() != 1 {
//                     return Err(Error::InvalidClone(top));
//                 }

//                 top = top_parents.next().unwrap().node();
//             }

//             let rule_parents = self.parents_of(top)?;

//             let candidates = {
//                 let mut result = Vec::with_capacity(rule_parents.len());

//                 for parent in rule_parents {
//                     // for parent in self.parents_of(parent.node())? {
//                     // if self.degree(parent.node())? <= parent.edge() + 1 {
//                     result.push(parent);
//                     // }
//                     // }
//                 }

//                 result
//             };

//             for candidate in candidates {
//                 if matches!(self.vertex_label(candidate.node())?, Some(label) if label.label().end().is_none())
//                 {
//                     if self.every_child_is_completed(candidate.node(), atom)? {
//                         let last_child = self
//                             .nth_child(candidate.node(), self.degree(candidate.node())? - 1)?;
//                         let end = self
//                             .vertex_label(last_child)?
//                             .ok_or(Error::NodeNoLabel(last_child))?
//                             .label()
//                             .end();

//                         let sploned_node = self.splone(
//                             candidate.node(),
//                             end,
//                             self.degree(candidate.node())? - 1,
//                             true,
//                         )?;

//                         second_stack.push(sploned_node);
//                     } else {
//                         pending_candidates.push(candidate.node());
//                     }
//                 } else {
//                     second_stack.push(candidate.node());
//                 }
//             }

//             let mut new_pending = Vec::with_capacity(pending_candidates.len());

//             while let Some(node) = pending_candidates.pop() {
//                 if self.every_child_is_completed(node, atom)? {
//                     let last_edge = self.degree(node)? - 1;
//                     let last_child = self.nth_child(node, last_edge)?;
//                     let end = self
//                         .vertex_label(last_child)?
//                         .ok_or(Error::NodeNoLabel(last_child))?
//                         .label()
//                         .end();

//                     let sploned_node = self.splone(node, end, last_edge, true)?;

//                     second_stack.push(sploned_node);
//                 } else {
//                     new_pending.push(node);
//                 }
//             }

//             std::mem::swap(&mut pending_candidates, &mut new_pending);
//         }

//         std::mem::swap(&mut stack, &mut second_stack);
//     }

//     Ok(())
// }

// /// Unconditionally set the label of the node to be the new label.
// ///
// /// # Warning
// ///
// /// Use with caution: it does not do anything special, so it is
// /// the responsibility of the caller to ensure this operation is
// /// legal.
// #[allow(dead_code)]
// pub(crate) fn set_label(&mut self, node: usize, label: GrammarLabel) -> Result<(), Error> {
//     let status = self
//         .vertex_label(node)?
//         .ok_or(Error::NodeNoLabel(node))?
//         .status;

//     let label = ForestLabel::new(label, status);

//     let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

//     builder.set_label(node, label)?;

//     Ok(())
// }

// /// Extract the node from `pavi`.
// ///
// /// If pavi is a parent, this returns the child pointed to by the
// /// represented edge.
// ///
// /// If pavi is a virtual node, this simply returns the virtual
// /// node.
// ///
// /// If pavi is empty, this returns the root, unless the forest is
// /// empty.
// ///
// /// # Guarantee
// ///
// /// The returned node is guaranteed to be a valid node.
// pub(crate) fn node_from_pavi(&self, pavi: PaVi) -> Result<usize, Error> {
//     match pavi {
//         PaVi::Parent(_node, _edge, child) => Ok(child),
//         PaVi::Virtual(_, _, node) => {
//             if node >= self.nodes_len() {
//                 return Err(Error::IndexOutOfBounds(node, self.nodes_len()));
//             }
// 
//             Ok(node)
//         }
//         PaVi::Empty => Ok(self.root().ok_or(Error::IndexOutOfBounds(0, 0))?),
//     }
// }

// /// Find the last child of the given node whose start and end
// /// positions contain the given position.  If no such child is
// /// found, return `Ok(None)`.
// ///
// /// The returned tuple is of the form (child, index), where
// /// `child` is the index of the child node in question, and
// /// `index` means that the child is the `index`-th child of the
// /// node.
// #[allow(dead_code)]
// pub(crate) fn position_search(
//     &self,
//     node: usize,
//     pos: usize,
// ) -> Result<Option<(usize, usize)>, Error> {
//     fn range_contains(label: GrammarLabel, pos: usize) -> bool {
//         let start = label.start();
// 
//         if let Some(end) = label.end() {
//             (start..end).contains(&pos)
//         } else {
//             (start..).contains(&pos)
//         }
//     }
// 
//     let node_label = self
//         .vertex_label(node)?
//         .ok_or(Error::NodeNoLabel(node))?
//         .label();
// 
//     if !range_contains(node_label, pos) {
//         return Ok(None);
//     }
// 
//     for (index, child) in self.children_of(node)?.enumerate().rev() {
//         let child_label = self
//             .vertex_label(child)?
//             .ok_or(Error::NodeNoLabel(child))?
//             .label();
// 
//         if range_contains(child_label, pos) {
//             return Ok(Some((child, index)));
//         }
//     }
// 
//     Ok(None)
// }

// let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

// // Just a dummy label for use in adding edges.
// //
// // REVIEW: I probably should refactor the API for builder_mut.
// let root_label = fragment
//     .vertex_label(root)?
//     .ok_or(Error::NodeNoLabel(root))?;

// let nodes_len = fragment.nodes_len();

// /// If the fragment root has a duplicate label, the forest
// /// will not grow, so we use the label to find the adjoined
// /// node index.
// ///
// /// The nodes hava already been added to the forest, so it is
// /// safe to call unwrap.
// macro_rules! conversion (
//     ($node:expr) => {
//         {
//             builder
//                 .query_label(
//                     fragment
//                         .vertex_label($node)?
//                         .ok_or(Error::NodeNoLabel($node))?
//                 ).unwrap()
//         }
//     }
// );

// // If the fragment has been planted before, we just add an
// // edge.

// if planted {
//     builder.add_edge(node_id, conversion!(root), root_label)?;

//     return Ok(());
// }

// // First adjoin the relevant nodes and join the edges later.

// let mut used_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();

// let mut stack = vec![root];

// while let Some(top) = stack.pop() {
//     if used_nodes.get(top).copied() == Some(true) {
//         continue;
//     }

//     *used_nodes
//         .get_mut(top)
//         .ok_or(Error::IndexOutOfBounds(top, nodes_len))? = true;

//     stack.extend(fragment.children_of(top)?);
// }

// let used_nodes = used_nodes;

// for node in (0..nodes_len).filter(|node| used_nodes.get(*node).copied() == Some(true)) {
//     let label = fragment
//         .vertex_label(node)?
//         .ok_or(Error::NodeNoLabel(node))?;

//     builder.add_vertex(label);
// }

// // Don't forget to join the new sub-forest to the original
// // forest, at the specified position.

// builder.add_edge(node_id, conversion!(root), root_label)?;

// // We can try to calculate the depth of fragments, if we need
// // to lower the memory usage.  But in our use cases, we
// // usually deal with fragments where each node has at most one
// // child, so the depth is supposed to be equal to the length
// // in this case.
// let mut stack = Vec::with_capacity(fragment.nodes_len());

// stack.push(root);

// let mut seen_nodes = std::collections::HashSet::<usize>::new();

// while let Some(top) = stack.pop() {
//     seen_nodes.insert(top);

//     for child in fragment.children_of(top)? {
//         builder.add_edge(conversion!(top), conversion!(child), root_label)?;

//         if !seen_nodes.contains(&child) {
//             seen_nodes.insert(child);
//             stack.push(child);
//         }
//     }
// }

// Ok(())