summaryrefslogtreecommitdiff
path: root/support/texlab/src/features/symbol/project_order.rs
diff options
context:
space:
mode:
Diffstat (limited to 'support/texlab/src/features/symbol/project_order.rs')
-rw-r--r--support/texlab/src/features/symbol/project_order.rs223
1 files changed, 223 insertions, 0 deletions
diff --git a/support/texlab/src/features/symbol/project_order.rs b/support/texlab/src/features/symbol/project_order.rs
new file mode 100644
index 0000000000..08b43ad50c
--- /dev/null
+++ b/support/texlab/src/features/symbol/project_order.rs
@@ -0,0 +1,223 @@
+use std::{sync::Arc, usize};
+
+use petgraph::{algo::tarjan_scc, Directed, Graph};
+use rustc_hash::FxHashSet;
+
+use crate::{Uri, Workspace, WorkspaceSubset};
+
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub struct ProjectOrdering {
+ ordering: Vec<Arc<Uri>>,
+}
+
+impl ProjectOrdering {
+ pub fn get(&self, uri: &Uri) -> usize {
+ self.ordering
+ .iter()
+ .position(|u| u.as_ref() == uri)
+ .unwrap_or(usize::MAX)
+ }
+}
+
+impl From<&dyn Workspace> for ProjectOrdering {
+ fn from(workspace: &dyn Workspace) -> Self {
+ let mut ordering = Vec::new();
+ let uris: FxHashSet<Arc<Uri>> = workspace
+ .documents()
+ .into_iter()
+ .map(|document| Arc::clone(&document.uri))
+ .collect();
+
+ let comps = connected_components(workspace);
+ for comp in comps {
+ let graph = build_dependency_graph(&comp);
+
+ let mut visited = FxHashSet::default();
+ let root_index = *graph.node_weight(tarjan_scc(&graph)[0][0]).unwrap();
+ let mut stack = vec![Arc::clone(&comp.documents[root_index].uri)];
+
+ while let Some(uri) = stack.pop() {
+ if !visited.insert(Arc::clone(&uri)) {
+ continue;
+ }
+
+ ordering.push(Arc::clone(&uri));
+ if let Some(document) = workspace.get(&uri) {
+ if let Some(data) = document.data.as_latex() {
+ for link in data.extras.explicit_links.iter().rev() {
+ for target in &link.targets {
+ if uris.contains(target.as_ref()) {
+ stack.push(Arc::clone(target));
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ Self { ordering }
+ }
+}
+
+fn connected_components(workspace: &dyn Workspace) -> Vec<WorkspaceSubset> {
+ let mut components = Vec::new();
+ let mut visited = FxHashSet::default();
+ for root_document in workspace.documents() {
+ if !visited.insert(Arc::clone(&root_document.uri)) {
+ continue;
+ }
+
+ let subset = workspace.subset(Arc::clone(&root_document.uri)).unwrap();
+ for document in &subset.documents {
+ visited.insert(Arc::clone(&document.uri));
+ }
+ components.push(subset);
+ }
+ components
+}
+
+fn build_dependency_graph(subset: &WorkspaceSubset) -> Graph<usize, (), Directed> {
+ let mut graph = Graph::new();
+ let nodes: Vec<_> = (0..subset.documents.len())
+ .map(|i| graph.add_node(i))
+ .collect();
+
+ for (i, document) in subset.documents.iter().enumerate() {
+ if let Some(data) = document.data.as_latex() {
+ for link in &data.extras.explicit_links {
+ for target in &link.targets {
+ if let Some(j) = subset
+ .documents
+ .iter()
+ .position(|document| document.uri.as_ref() == target.as_ref())
+ {
+ graph.add_edge(nodes[j], nodes[i], ());
+ break;
+ }
+ }
+ }
+ }
+ }
+ graph
+}
+
+#[cfg(test)]
+mod tests {
+ use anyhow::Result;
+
+ use crate::{create_workspace_fast, DocumentLanguage, ServerContext, WorkspaceSource};
+
+ use super::*;
+
+ #[test]
+ fn test_no_cycles() -> Result<()> {
+ let workspace: Arc<dyn Workspace> = Arc::new(create_workspace_fast(Arc::new(
+ ServerContext::new(std::env::temp_dir()),
+ ))?);
+
+ let a = workspace.open(
+ Arc::new(Uri::parse("http://example.com/a.tex")?),
+ "".into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let b = workspace.open(
+ Arc::new(Uri::parse("http://example.com/b.tex")?),
+ "".into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let c = workspace.open(
+ Arc::new(Uri::parse("http://example.com/c.tex")?),
+ r#"\include{b}\include{a}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let ordering = ProjectOrdering::from(workspace.as_ref());
+
+ assert_eq!(ordering.get(&a.uri), 2);
+ assert_eq!(ordering.get(&b.uri), 1);
+ assert_eq!(ordering.get(&c.uri), 0);
+ Ok(())
+ }
+
+ #[test]
+ fn test_cycles() -> Result<()> {
+ let workspace: Arc<dyn Workspace> = Arc::new(create_workspace_fast(Arc::new(
+ ServerContext::new(std::env::temp_dir()),
+ ))?);
+
+ let a = workspace.open(
+ Arc::new(Uri::parse("http://example.com/a.tex")?),
+ r#"\include{b}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let b = workspace.open(
+ Arc::new(Uri::parse("http://example.com/b.tex")?),
+ r#"\include{a}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let c = workspace.open(
+ Arc::new(Uri::parse("http://example.com/c.tex")?),
+ r#"\include{a}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let ordering = ProjectOrdering::from(workspace.as_ref());
+
+ assert_eq!(ordering.get(&a.uri), 1);
+ assert_eq!(ordering.get(&b.uri), 2);
+ assert_eq!(ordering.get(&c.uri), 0);
+ Ok(())
+ }
+
+ #[test]
+ fn test_multiple_roots() -> Result<()> {
+ let workspace: Arc<dyn Workspace> = Arc::new(create_workspace_fast(Arc::new(
+ ServerContext::new(std::env::temp_dir()),
+ ))?);
+
+ let a = workspace.open(
+ Arc::new(Uri::parse("http://example.com/a.tex")?),
+ r#"\include{b}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let b = workspace.open(
+ Arc::new(Uri::parse("http://example.com/b.tex")?),
+ r#""#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let c = workspace.open(
+ Arc::new(Uri::parse("http://example.com/c.tex")?),
+ r#""#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let d = workspace.open(
+ Arc::new(Uri::parse("http://example.com/d.tex")?),
+ r#"\include{c}"#.into(),
+ DocumentLanguage::Latex,
+ WorkspaceSource::Client,
+ );
+
+ let ordering = ProjectOrdering::from(workspace.as_ref());
+
+ assert!(ordering.get(&a.uri) < ordering.get(&b.uri));
+ assert!(ordering.get(&d.uri) < ordering.get(&c.uri));
+ Ok(())
+ }
+}