use std::collections::{HashSet, VecDeque};
use std::path::{Path, PathBuf};
use crate::file::paths::{FileProvider, normalize_path};
use crate::index::store::{StoreStats, SummaryStore};
pub struct Worklist<'s, F: FileProvider> {
store: &'s mut SummaryStore<F>,
open: VecDeque<(PathBuf, usize)>,
tail: VecDeque<(PathBuf, usize)>,
seen: HashSet<String>,
}
impl<'s, F: FileProvider> Worklist<'s, F> {
pub fn new(
store: &'s mut SummaryStore<F>,
open: impl IntoIterator<Item = PathBuf>,
project: impl IntoIterator<Item = PathBuf>,
) -> Self {
let mut seen = HashSet::new();
let mut queue = |paths: Vec<PathBuf>| -> VecDeque<(PathBuf, usize)> {
paths
.into_iter()
.filter(|path| seen.insert(key(path)))
.map(|path| (path, 0))
.collect()
};
let open = queue(open.into_iter().collect());
let tail = queue(project.into_iter().collect());
Worklist {
store,
open,
tail,
seen,
}
}
pub fn step(&mut self) -> Option<Step> {
let (path, priority, depth) = match self.open.pop_front() {
Some((path, depth)) => (path, Priority::Open, depth),
None => {
let (path, depth) = self.tail.pop_front()?;
(path, Priority::Rest, depth)
}
};
let before = self.store.stats();
let includes = self
.store
.get(&path)
.map(|summary| {
summary
.includes
.iter()
.filter_map(|include| include.resolved.clone())
.collect::<Vec<PathBuf>>()
})
.unwrap_or_default();
let after = self.store.stats();
let outcome = outcome_of(before, after);
let next: Vec<(PathBuf, usize)> = includes
.into_iter()
.filter(|include| self.seen.insert(key(include)))
.map(|include| (include, depth + 1))
.collect();
match priority {
Priority::Open => self.open.extend(next),
Priority::Rest => self.tail.extend(next),
}
Some(Step {
path,
priority,
depth,
outcome,
with_the_environment: false,
})
}
pub fn pending(&self) -> usize {
self.open.len() + self.tail.len()
}
pub fn is_empty(&self) -> bool {
self.pending() == 0
}
pub fn reached(&self) -> usize {
self.seen.len()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Priority {
Open,
Rest,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Step {
pub path: PathBuf,
pub priority: Priority,
pub depth: usize,
pub outcome: StepOutcome,
pub with_the_environment: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StepOutcome {
Reused,
Built,
Unstored,
Missing,
}
fn key(path: &Path) -> String {
normalize_path(path, cfg!(windows))
}
pub fn outcome_of(before: StoreStats, after: StoreStats) -> StepOutcome {
if after == before {
StepOutcome::Missing
} else if after.reused > before.reused {
StepOutcome::Reused
} else if after.unstored > before.unstored {
StepOutcome::Unstored
} else {
StepOutcome::Built
}
}
impl<F: FileProvider> SummaryStore<F> {
pub fn worklist<'s>(
&'s mut self,
open: impl IntoIterator<Item = PathBuf>,
project: impl IntoIterator<Item = PathBuf>,
) -> Worklist<'s, F> {
Worklist::new(self, open, project)
}
}
#[cfg(test)]
mod tests {
use super::{Priority, StepOutcome, Worklist};
use crate::file::paths::MemoryFiles;
use crate::include::config::CompilerConfig;
use crate::index::store::SummaryStore;
use std::path::{Path, PathBuf};
fn store(name: &str, files: &MemoryFiles) -> (SummaryStore<MemoryFiles>, std::path::PathBuf) {
let root = std::env::temp_dir().join("cppls-worklist-tests").join(name);
let _ = std::fs::remove_dir_all(&root);
let store = SummaryStore::with_provider(&root, CompilerConfig::default(), files.clone());
(store, root)
}
fn paths(names: &[&str]) -> Vec<PathBuf> {
names.iter().map(PathBuf::from).collect()
}
fn run(list: &mut Worklist<'_, MemoryFiles>) -> Vec<super::Step> {
let mut steps = Vec::new();
while let Some(step) = list.step() {
steps.push(step);
}
steps
}
#[test]
fn the_open_files_come_first_then_what_they_include_then_the_rest() {
let files = MemoryFiles::new()
.with_file("/p/main.cpp", "#include \"a.h\"\nvoid f() { }\n")
.with_file("/p/a.h", "#include \"b.h\"\n")
.with_file("/p/b.h", "struct B { int x; };\n")
.with_file("/p/z.cpp", "int z;\n")
.with_file("/p/y.cpp", "int y;\n");
let (mut store, root) = store("order", &files);
let mut list = store.worklist(paths(&["/p/main.cpp"]), paths(&["/p/z.cpp", "/p/y.cpp"]));
let steps = run(&mut list);
let worked: Vec<String> = steps
.iter()
.map(|step| step.path.to_string_lossy().replace('\\', "/"))
.collect();
assert_eq!(
worked,
["/p/main.cpp", "/p/a.h", "/p/b.h", "/p/z.cpp", "/p/y.cpp"],
"the open file, its includes breadth-first, and only then the project"
);
assert_eq!(files.reads(), worked);
assert_eq!(steps[0].priority, Priority::Open);
assert_eq!(steps[0].depth, 0);
assert_eq!(
(steps[1].priority, steps[1].depth),
(Priority::Open, 1),
"a.h is one include away"
);
assert_eq!((steps[2].priority, steps[2].depth), (Priority::Open, 2));
assert_eq!(steps[3].priority, Priority::Rest);
assert_eq!(steps[3].depth, 0, "z.cpp is a project root");
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn the_closure_is_not_pushed_behind_a_long_project_list() {
let mut builder = MemoryFiles::new()
.with_file("/p/main.cpp", "#include \"a.h\"\n")
.with_file("/p/a.h", "#include \"b.h\"\n")
.with_file("/p/b.h", "struct B { int x; };\n");
let project: Vec<String> = (0..50).map(|index| format!("/p/file{index}.cpp")).collect();
for path in &project {
builder = builder.with_file(path, "int x;\n");
}
let (mut store, root) = store("long-project", &builder);
let mut list = store.worklist(
paths(&["/p/main.cpp"]),
project.iter().map(PathBuf::from).collect::<Vec<_>>(),
);
let steps = run(&mut list);
let first_rest = steps
.iter()
.position(|step| step.priority == Priority::Rest)
.expect("the project half is worked");
assert_eq!(
first_rest,
3,
"all three files of the closure are done before the first project file: {:?}",
steps
.iter()
.map(|step| step.path.display().to_string())
.collect::<Vec<_>>()
);
assert_eq!(steps.len(), 53, "and nothing is worked twice");
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_file_in_both_lists_is_worked_once_and_in_the_open_half() {
let files = MemoryFiles::new().with_file("/p/main.cpp", "int x;\n");
let (mut store, root) = store("both-lists", &files);
let mut list = store.worklist(paths(&["/p/main.cpp"]), paths(&["/p/main.cpp"]));
let steps = run(&mut list);
assert_eq!(steps.len(), 1, "one file, one step: {:?}", steps);
assert_eq!(steps[0].priority, Priority::Open);
assert_eq!(files.reads(), ["/p/main.cpp"]);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_diamond_of_includes_works_the_shared_file_once() {
let files = MemoryFiles::new()
.with_file("/p/main.cpp", "#include \"a.h\"\n#include \"b.h\"\n")
.with_file("/p/a.h", "#include \"common.h\"\n")
.with_file("/p/b.h", "#include \"common.h\"\n")
.with_file("/p/common.h", "int shared;\n");
let (mut store, root) = store("diamond", &files);
let mut list = store.worklist(paths(&["/p/main.cpp"]), paths(&[]));
let steps = run(&mut list);
let worked: Vec<String> = steps
.iter()
.map(|step| step.path.to_string_lossy().replace('\\', "/"))
.collect();
assert_eq!(
worked,
["/p/main.cpp", "/p/a.h", "/p/b.h", "/p/common.h"],
"the second path to common.h is not a second step"
);
assert_eq!(list.reached(), 4);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_cycle_of_includes_terminates() {
let files = MemoryFiles::new()
.with_file("/p/a.h", "#include \"b.h\"\nstruct A { int x; };\n")
.with_file("/p/b.h", "#include \"a.h\"\nstruct B { int y; };\n");
let (mut store, root) = store("cycle", &files);
let mut list = store.worklist(paths(&["/p/a.h"]), paths(&[]));
let steps = run(&mut list);
assert_eq!(steps.len(), 2);
assert!(list.is_empty());
assert_eq!(list.pending(), 0);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_project_root_discovers_the_headers_it_includes() {
let files = MemoryFiles::new()
.with_file("/p/tu.cpp", "#include \"deep/middle.h\"\nvoid f() { }\n")
.with_file("/p/deep/middle.h", "#include \"leaf.h\"\n")
.with_file("/p/deep/leaf.h", "struct Leaf { int x; };\n");
let (mut store, root) = store("discovery", &files);
let mut list = store.worklist(paths(&[]), paths(&["/p/tu.cpp"]));
let steps = run(&mut list);
let worked: Vec<String> = steps
.iter()
.map(|step| step.path.to_string_lossy().replace('\\', "/"))
.collect();
assert_eq!(worked, ["/p/tu.cpp", "/p/deep/middle.h", "/p/deep/leaf.h"]);
assert!(steps.iter().all(|step| step.priority == Priority::Rest));
assert!(
matches!(
store.index().definition("Leaf", Path::new("/p/tu.cpp")),
crate::Known::Yes(_)
),
"the discovered header is visible from the unit that includes it"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_second_run_over_the_same_project_reads_nothing_new() {
let files = MemoryFiles::new()
.with_file("/p/main.cpp", "#include \"a.h\"\nvoid f() { }\n")
.with_file("/p/a.h", "struct A { int x; };\n");
let (mut store, root) = store("twice", &files);
let first = run(&mut store.worklist(paths(&["/p/main.cpp"]), paths(&[])));
assert_eq!(
first.iter().map(|step| step.outcome).collect::<Vec<_>>(),
[StepOutcome::Built, StepOutcome::Built]
);
let mut again =
SummaryStore::with_provider(&root, CompilerConfig::default(), files.clone());
let second = run(&mut again.worklist(paths(&["/p/main.cpp"]), paths(&[])));
assert_eq!(
second.iter().map(|step| step.outcome).collect::<Vec<_>>(),
[StepOutcome::Reused, StepOutcome::Reused],
"a warm cache means the parser is not asked"
);
assert_eq!(again.stats().rebuilt, 0);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_file_that_cannot_be_read_is_a_step_like_any_other() {
let files = MemoryFiles::new().with_file("/p/here.cpp", "int x;\n");
let (mut store, root) = store("missing", &files);
let mut list = store.worklist(paths(&["/p/gone.cpp"]), paths(&["/p/here.cpp"]));
let steps = run(&mut list);
assert_eq!(steps.len(), 2);
assert_eq!(steps[0].outcome, StepOutcome::Missing);
assert_eq!(steps[0].path, Path::new("/p/gone.cpp"));
assert_eq!(steps[1].outcome, StepOutcome::Built);
assert_eq!(steps[1].path, Path::new("/p/here.cpp"));
assert_eq!(
list.reached(),
2,
"the missing file is held, not dropped and retried"
);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn a_file_whose_include_does_not_resolve_is_still_a_step() {
let files =
MemoryFiles::new().with_file("/p/main.cpp", "#include \"nope.h\"\nvoid f() { }\n");
let (mut store, root) = store("unresolved", &files);
let mut list = store.worklist(paths(&["/p/main.cpp"]), paths(&[]));
let steps = run(&mut list);
assert_eq!(steps.len(), 1, "nothing to queue for an unresolved include");
assert_eq!(steps[0].outcome, StepOutcome::Unstored);
assert_eq!(store.stats().unstored, 1);
let _ = std::fs::remove_dir_all(&root);
}
#[test]
fn pending_grows_as_the_list_discovers_files() {
let files = MemoryFiles::new()
.with_file("/p/main.cpp", "#include \"a.h\"\n")
.with_file("/p/a.h", "#include \"b.h\"\n")
.with_file("/p/b.h", "int x;\n");
let (mut store, root) = store("pending", &files);
let mut list = store.worklist(paths(&["/p/main.cpp"]), paths(&["/p/z.cpp"]));
assert_eq!(list.pending(), 2, "one open file and one project file");
assert_eq!(list.reached(), 2);
list.step().expect("the open file is worked");
assert_eq!(
list.pending(),
2,
"one file left plus the include it just discovered"
);
assert_eq!(list.reached(), 3, "and a.h is now known");
list.step().expect("a.h is worked");
assert_eq!(
list.pending(),
2,
"b.h was discovered, z.cpp is still there"
);
run(&mut list);
assert_eq!(list.pending(), 0);
assert!(list.is_empty());
assert_eq!(list.reached(), 4);
let _ = std::fs::remove_dir_all(&root);
}
}