diff options
Diffstat (limited to 'support/texlab/src/symbol/project_order.rs')
-rw-r--r-- | support/texlab/src/symbol/project_order.rs | 142 |
1 files changed, 142 insertions, 0 deletions
diff --git a/support/texlab/src/symbol/project_order.rs b/support/texlab/src/symbol/project_order.rs new file mode 100644 index 0000000000..31b71f36bb --- /dev/null +++ b/support/texlab/src/symbol/project_order.rs @@ -0,0 +1,142 @@ +use crate::syntax::*; +use crate::workspace::*; +use petgraph::algo::tarjan_scc; +use petgraph::{Directed, Graph}; +use std::collections::HashSet; +use std::sync::Arc; + +#[derive(Debug, PartialEq, Eq, Clone)] +pub struct ProjectOrdering { + ordering: Vec<Arc<Document>>, +} + +impl ProjectOrdering { + pub fn new(workspace: &Workspace) -> Self { + let mut ordering = Vec::new(); + let connected_components = Self::connected_components(workspace); + for connected_component in connected_components { + let graph = Self::build_dependency_graph(&connected_component); + + let mut visited = HashSet::new(); + let root_index = *graph.node_weight(tarjan_scc(&graph)[0][0]).unwrap(); + let mut stack = vec![Arc::clone(&connected_component[root_index])]; + + while let Some(document) = stack.pop() { + if !visited.insert(document.uri.as_str().to_owned()) { + continue; + } + + ordering.push(Arc::clone(&document)); + if let SyntaxTree::Latex(tree) = &document.tree { + for include in tree.includes.iter().rev() { + for targets in &include.all_targets { + for target in targets { + if let Some(child) = workspace.find(target) { + stack.push(child); + } + } + } + } + } + } + } + + Self { ordering } + } + + fn connected_components(workspace: &Workspace) -> Vec<Vec<Arc<Document>>> { + let mut components = Vec::new(); + let mut visited = HashSet::new(); + for root in &workspace.documents { + if !visited.insert(root.uri.clone()) { + continue; + } + + let component = workspace.related_documents(&root.uri); + for document in &component { + visited.insert(document.uri.clone()); + } + components.push(component); + } + components + } + + fn build_dependency_graph(documents: &[Arc<Document>]) -> Graph<usize, (), Directed> { + let mut graph = Graph::new(); + let nodes: Vec<_> = (0..documents.len()).map(|i| graph.add_node(i)).collect(); + + for (i, document) in documents.iter().enumerate() { + if let SyntaxTree::Latex(tree) = &document.tree { + for targets in tree + .includes + .iter() + .flat_map(|include| &include.all_targets) + { + for target in targets { + if let Some(j) = documents.iter().position(|doc| doc.uri == *target) { + graph.add_edge(nodes[j], nodes[i], ()); + break; + } + } + } + } + } + graph + } + + pub fn get(&self, uri: &Uri) -> usize { + self.ordering + .iter() + .position(|doc| doc.uri == *uri) + .unwrap_or(std::usize::MAX) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_no_cycles() { + let mut builder = WorkspaceBuilder::new(); + let a = builder.document("a.tex", ""); + let b = builder.document("b.tex", ""); + let c = builder.document("c.tex", "\\include{b}\\include{a}"); + + let project_ordering = ProjectOrdering::new(&builder.workspace); + + assert_eq!(project_ordering.get(&a), 2); + assert_eq!(project_ordering.get(&b), 1); + assert_eq!(project_ordering.get(&c), 0); + } + + #[test] + fn test_cycles() { + let mut builder = WorkspaceBuilder::new(); + let a = builder.document("a.tex", "\\include{b}"); + let b = builder.document("b.tex", "\\include{a}"); + let c = builder.document("c.tex", "\\include{a}"); + + let project_ordering = ProjectOrdering::new(&builder.workspace); + + assert_eq!(project_ordering.get(&a), 1); + assert_eq!(project_ordering.get(&b), 2); + assert_eq!(project_ordering.get(&c), 0); + } + + #[test] + fn test_multiple_roots() { + let mut builder = WorkspaceBuilder::new(); + let a = builder.document("a.tex", "\\include{b}"); + let b = builder.document("b.tex", ""); + let c = builder.document("c.tex", ""); + let d = builder.document("d.tex", "\\include{c}"); + + let project_ordering = ProjectOrdering::new(&builder.workspace); + + assert_eq!(project_ordering.get(&a), 0); + assert_eq!(project_ordering.get(&b), 1); + assert_eq!(project_ordering.get(&d), 2); + assert_eq!(project_ordering.get(&c), 3); + } +} |