use crate::builder::{FollowLinks, Query};
use crate::error::EntryError;
use crate::predicate::{EntryType, MetaMask, eval_all};
use crate::ring::{
CompletionRing, ContainerEnd, ContainerEnter, ContainerId, ContainerName, CqError, CqItem,
EntryMetaOwned, IdSpace, Match, Name, PatternMask, SqOp, SubmissionQueue, Terminal,
TerminalReason,
};
use crate::syntax::CodePoint;
use crate::syntax::set::PatternSet;
use crate::sys::{self, DirEntry, FileId};
use std::collections::{HashMap, HashSet};
use std::path::PathBuf;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{Arc, Condvar, Mutex};
use std::thread::JoinHandle;
use std::time::Duration;
struct ScanJob {
dir: PathBuf,
rel: Arc<Vec<Vec<CodePoint>>>,
container: ContainerId,
parent: Option<ContainerId>,
root: usize,
name: ContainerName,
}
struct ContainerState {
parent: Option<ContainerId>,
refcount: usize,
}
struct Shared {
stack: Vec<ScanJob>,
outstanding: usize,
cancelled: bool,
containers: HashMap<ContainerId, ContainerState>,
open: HashMap<ContainerId, u32>,
visited: HashSet<FileId>,
}
struct Engine {
query: Query,
patterns: PatternSet,
fetch_mask: crate::predicate::MetaMask,
enum_plan: sys::EnumPlan,
ring: Arc<CompletionRing>,
shared: Mutex<Shared>,
work_cv: Condvar,
cancel: AtomicBool,
fatal: AtomicBool,
fatal_error: Mutex<Option<CqError>>,
finished: AtomicBool,
ids: IdSpace,
}
fn file_id_known(id: FileId) -> bool {
id.volume != 0 || id.id != 0
}
impl Engine {
fn emit(&self, item: CqItem) -> bool {
let mut item = item;
loop {
if self.cancel.load(Ordering::Acquire) {
return false;
}
match self.ring.try_push(item) {
Ok(()) => return true,
Err(back) => {
item = back;
self.ring.wait_space_timeout(Duration::from_millis(5));
}
}
}
}
fn next_job(&self) -> Option<ScanJob> {
let mut sh = self.shared.lock().unwrap();
loop {
if sh.cancelled {
return None;
}
if let Some(job) = sh.stack.pop() {
return Some(job);
}
if sh.outstanding == 0 {
self.work_cv.notify_all();
return None;
}
sh = self.work_cv.wait(sh).unwrap();
}
}
fn complete_job(&self) {
let mut sh = self.shared.lock().unwrap();
sh.outstanding -= 1;
if sh.outstanding == 0 {
self.work_cv.notify_all();
}
}
fn release(&self, start: ContainerId) -> Vec<ContainerId> {
let mut ends = Vec::new();
let mut sh = self.shared.lock().unwrap();
let mut id = start;
loop {
let st = sh
.containers
.get_mut(&id)
.expect("container state present until released");
st.refcount -= 1;
if st.refcount == 0 {
let parent = st.parent;
sh.containers.remove(&id);
ends.push(id);
match parent {
Some(p) => id = p,
None => break,
}
} else {
break;
}
}
ends
}
fn launch_child(&self, parent: &ScanJob, entry: &DirEntry) {
let child_id = self.ids.next_container();
let mut child_rel = (*parent.rel).clone();
child_rel.push(entry.name.clone());
let child_dir = parent.dir.join(sys::encode_os_name(&entry.name));
{
let mut sh = self.shared.lock().unwrap();
sh.containers.insert(
child_id,
ContainerState {
parent: Some(parent.container),
refcount: 1,
},
);
if let Some(st) = sh.containers.get_mut(&parent.container) {
st.refcount += 1;
}
sh.stack.push(ScanJob {
dir: child_dir,
rel: Arc::new(child_rel),
container: child_id,
parent: Some(parent.container),
root: parent.root,
name: ContainerName::Entry(Name::from_code_points(&entry.name)),
});
sh.outstanding += 1;
}
self.work_cv.notify_one();
}
fn process(&self, job: ScanJob) {
let depth = job.rel.len() as u32;
let scan = match sys::enumerate(&job.dir, self.enum_plan) {
Ok(scan) => scan,
Err(err) => {
let name = match &job.name {
ContainerName::Entry(n) => Some(n.clone()),
ContainerName::Root(_) => None,
};
let cq_err = CqError {
container: job.parent,
root: Some(job.root as u32),
error: EntryError { name, source: err },
};
if job.parent.is_none() {
self.emit_ends(self.release(job.container));
self.request_fatal(cq_err);
} else {
self.emit(CqItem::Error(cq_err));
self.emit_ends(self.release(job.container));
}
return;
}
};
if !self.emit(CqItem::ContainerEnter(ContainerEnter {
id: job.container,
parent: job.parent,
name: job.name.clone(),
})) {
self.emit_ends(self.release(job.container));
return;
}
self.shared
.lock()
.unwrap()
.open
.insert(job.container, depth);
for failure in scan.entry_errors {
self.emit(CqItem::Error(CqError {
container: Some(job.container),
root: Some(job.root as u32),
error: EntryError {
name: failure.name.map(|cp| Name::from_code_points(&cp)),
source: failure.source,
},
}));
}
let entries = scan.entries;
let mut path: Vec<&[CodePoint]> = job.rel.iter().map(|s| s.as_slice()).collect();
path.reserve_exact(1);
for entry in &entries {
if self.cancel.load(Ordering::Acquire) {
break;
}
let meta = entry.meta(depth);
path.push(&entry.name);
let mut hits = self.patterns.matches(&path);
hits.retain(|&i| self.query.patterns[i].roots.contains(&job.root));
if !hits.is_empty() {
let mut mask = PatternMask::new(self.query.patterns.len());
let mut any = false;
for i in hits {
if eval_all(&self.query.patterns[i].emit, &meta) {
mask.set(i);
any = true;
}
}
if any {
self.emit(CqItem::Match(Match {
container: job.container,
name: Name::from_code_points(&entry.name),
matched: mask,
meta: EntryMetaOwned::from_meta(&meta, self.fetch_mask),
}));
}
}
let dir_candidate = if entry.is_reparse {
self.query.options.follow_links == FollowLinks::Always
} else {
entry.entry_type == EntryType::Dir
};
if dir_candidate
&& self.patterns.should_descend_where(&path, |i| {
self.query.patterns[i].roots.contains(&job.root)
})
&& eval_all(&self.query.descend, &meta)
&& self.admit_descend(entry)
{
self.launch_child(&job, entry);
}
path.pop();
}
self.emit_ends(self.release(job.container));
}
fn admit_descend(&self, entry: &DirEntry) -> bool {
if !(entry.is_reparse && self.query.options.cycle_detection && file_id_known(entry.file_id))
{
return true;
}
let mut sh = self.shared.lock().unwrap();
sh.visited.insert(entry.file_id)
}
fn push_mandatory(&self, item: CqItem) {
let mut item = item;
loop {
match self.ring.try_push(item) {
Ok(()) => return,
Err(back) => {
item = back;
self.ring.wait_space_timeout(Duration::from_millis(5));
}
}
}
}
fn emit_end(&self, id: ContainerId) {
let owed = self.shared.lock().unwrap().open.remove(&id).is_some();
if owed {
self.push_mandatory(CqItem::ContainerEnd(ContainerEnd { id }));
}
}
fn emit_ends(&self, ends: Vec<ContainerId>) {
for id in ends {
self.emit_end(id);
}
}
fn request_fatal(&self, err: CqError) {
{
let mut slot = self.fatal_error.lock().unwrap();
if slot.is_none() {
*slot = Some(err);
}
}
self.fatal.store(true, Ordering::Release);
self.request_cancel();
}
fn request_cancel(&self) {
if self.cancel.swap(true, Ordering::AcqRel) {
return;
}
{
let mut sh = self.shared.lock().unwrap();
sh.cancelled = true;
}
self.work_cv.notify_all();
self.ring.wake_producers();
}
}
fn worker_loop(engine: &Arc<Engine>) {
while let Some(job) = engine.next_job() {
engine.process(job);
engine.complete_job();
}
}
fn sq_loop(engine: &Arc<Engine>, sq: &Arc<SubmissionQueue>) {
while !engine.finished.load(Ordering::Acquire) {
for op in sq.drain() {
match op {
SqOp::Cancel => engine.request_cancel(),
SqOp::DecisionAnswer { .. } => {}
}
}
sq.wait_timeout(Duration::from_millis(25));
}
}
pub struct EngineHandle {
engine: Arc<Engine>,
coordinator: Option<JoinHandle<()>>,
sq_thread: Option<JoinHandle<()>>,
}
impl Drop for EngineHandle {
fn drop(&mut self) {
self.engine.request_cancel();
while !self.engine.finished.load(Ordering::Acquire) {
while self.engine.ring.pop().is_some() {}
std::thread::yield_now();
}
while self.engine.ring.pop().is_some() {}
if let Some(h) = self.coordinator.take() {
let _ = h.join();
}
if let Some(h) = self.sq_thread.take() {
let _ = h.join();
}
}
}
pub fn spawn(query: Query, ring: Arc<CompletionRing>, sq: Arc<SubmissionQueue>) -> EngineHandle {
let patterns =
PatternSet::from_compiled(query.patterns.iter().map(|p| p.glob.clone()).collect());
let fetch_mask = query.fetch_mask();
let stat_mask = MetaMask::SIZE
| MetaMask::MTIME
| MetaMask::ATIME
| MetaMask::CTIME
| MetaMask::BTIME
| MetaMask::ATTRS;
let enum_plan = sys::EnumPlan {
want_stat: fetch_mask.intersects(stat_mask),
want_file_id: false,
want_reparse_file_id: query.options.cycle_detection
&& query.options.follow_links == FollowLinks::Always,
};
let permits = query.options.permits.max(1);
let ids = IdSpace::new();
let mut shared = Shared {
stack: Vec::new(),
outstanding: 0,
cancelled: false,
containers: HashMap::new(),
open: HashMap::new(),
visited: HashSet::new(),
};
let mut referenced = vec![false; query.roots.len()];
for p in &query.patterns {
for &r in &p.roots {
referenced[r] = true;
}
}
for (i, root) in query.roots.iter().enumerate() {
if !referenced[i] {
continue;
}
let cid = ids.next_container();
shared.containers.insert(
cid,
ContainerState {
parent: None,
refcount: 1,
},
);
shared.outstanding += 1;
shared.stack.push(ScanJob {
dir: root.path.clone(),
rel: Arc::new(Vec::new()),
container: cid,
parent: None,
root: i,
name: ContainerName::Root(i as u32),
});
}
let engine = Arc::new(Engine {
query,
patterns,
fetch_mask,
enum_plan,
ring,
shared: Mutex::new(shared),
work_cv: Condvar::new(),
cancel: AtomicBool::new(false),
fatal: AtomicBool::new(false),
fatal_error: Mutex::new(None),
finished: AtomicBool::new(false),
ids,
});
let mut workers = Vec::with_capacity(permits);
for _ in 0..permits {
let e = Arc::clone(&engine);
workers.push(std::thread::spawn(move || worker_loop(&e)));
}
let sq_thread = {
let e = Arc::clone(&engine);
let sq = Arc::clone(&sq);
std::thread::spawn(move || sq_loop(&e, &sq))
};
let coordinator = {
let e = Arc::clone(&engine);
std::thread::spawn(move || {
for w in workers {
let _ = w.join();
}
let mut leftovers: Vec<(ContainerId, u32)> = {
let sh = e.shared.lock().unwrap();
sh.open.iter().map(|(&id, &d)| (id, d)).collect()
};
leftovers.sort_by_key(|&(_, depth)| std::cmp::Reverse(depth));
for (id, _) in leftovers {
e.emit_end(id);
}
let reason = if e.fatal.load(Ordering::Acquire) {
TerminalReason::Failed
} else if e.cancel.load(Ordering::Acquire) {
TerminalReason::Cancelled
} else {
TerminalReason::Completed
};
if let Some(err) = e.fatal_error.lock().unwrap().take() {
e.push_mandatory(CqItem::Error(err));
}
e.push_mandatory(CqItem::Terminal(Terminal { reason }));
e.finished.store(true, Ordering::Release);
})
};
EngineHandle {
engine,
coordinator: Some(coordinator),
sq_thread: Some(sq_thread),
}
}