1pub use super::fuzzy::PathMatch;
2use super::{
3 char_bag::CharBag,
4 fuzzy::{self, PathEntry},
5};
6use crate::{editor::History, timer, util::post_inc};
7use anyhow::{anyhow, Result};
8use crossbeam_queue::SegQueue;
9use easy_parallel::Parallel;
10use gpui::{AppContext, Entity, ModelContext, ModelHandle};
11use ignore::dir::{Ignore, IgnoreBuilder};
12use parking_lot::RwLock;
13use smol::prelude::*;
14use std::{
15 collections::HashMap,
16 ffi::{OsStr, OsString},
17 fmt, fs, io,
18 os::unix::fs::MetadataExt,
19 path::Path,
20 path::PathBuf,
21 sync::Arc,
22 time::Duration,
23};
24
25#[derive(Clone)]
26pub struct Worktree(Arc<RwLock<WorktreeState>>);
27
28struct WorktreeState {
29 id: usize,
30 path: PathBuf,
31 entries: Vec<Entry>,
32 file_paths: Vec<PathEntry>,
33 histories: HashMap<usize, History>,
34 scanning: bool,
35}
36
37struct DirToScan {
38 id: usize,
39 path: PathBuf,
40 relative_path: PathBuf,
41 ignore: Option<Ignore>,
42 dirs_to_scan: Arc<SegQueue<io::Result<DirToScan>>>,
43}
44
45impl Worktree {
46 pub fn new<T>(id: usize, path: T, ctx: Option<&mut ModelContext<Self>>) -> Self
47 where
48 T: Into<PathBuf>,
49 {
50 let tree = Self(Arc::new(RwLock::new(WorktreeState {
51 id,
52 path: path.into(),
53 entries: Vec::new(),
54 file_paths: Vec::new(),
55 histories: HashMap::new(),
56 scanning: ctx.is_some(),
57 })));
58
59 if let Some(ctx) = ctx {
60 tree.0.write().scanning = true;
61
62 let tree = tree.clone();
63 let (tx, rx) = smol::channel::bounded(1);
64 std::thread::spawn(move || {
65 let _ = smol::block_on(tx.send(tree.scan_dirs()));
66 });
67 let _ = ctx.spawn(async move { rx.recv().await.unwrap() }, Self::done_scanning);
68
69 let _ = ctx.spawn_stream_local(
70 timer::repeat(Duration::from_millis(100)).map(|_| ()),
71 Self::scanning,
72 );
73 }
74
75 tree
76 }
77
78 fn scan_dirs(&self) -> io::Result<()> {
79 let path = self.0.read().path.clone();
80 let metadata = fs::metadata(&path)?;
81 let ino = metadata.ino();
82 let is_symlink = fs::symlink_metadata(&path)?.file_type().is_symlink();
83 let name = path
84 .file_name()
85 .map(|name| OsString::from(name))
86 .unwrap_or(OsString::from("/"));
87 let relative_path = PathBuf::from(&name);
88
89 let mut ignore = IgnoreBuilder::new().build().add_parents(&path).unwrap();
90 if metadata.is_dir() {
91 ignore = ignore.add_child(&path).unwrap();
92 }
93 let is_ignored = ignore.matched(&path, metadata.is_dir()).is_ignore();
94
95 if metadata.file_type().is_dir() {
96 let is_ignored = is_ignored || name == ".git";
97 let id = self.push_dir(None, name, ino, is_symlink, is_ignored);
98 let queue = Arc::new(SegQueue::new());
99
100 queue.push(Ok(DirToScan {
101 id,
102 path,
103 relative_path,
104 ignore: Some(ignore),
105 dirs_to_scan: queue.clone(),
106 }));
107
108 Parallel::<io::Result<()>>::new()
109 .each(0..16, |_| {
110 while let Some(result) = queue.pop() {
111 self.scan_dir(result?)?;
112 }
113 Ok(())
114 })
115 .run()
116 .into_iter()
117 .collect::<io::Result<()>>()?;
118 } else {
119 self.push_file(None, name, ino, is_symlink, is_ignored, relative_path);
120 }
121
122 Ok(())
123 }
124
125 fn scan_dir(&self, to_scan: DirToScan) -> io::Result<()> {
126 let mut new_children = Vec::new();
127
128 for child_entry in fs::read_dir(&to_scan.path)? {
129 let child_entry = child_entry?;
130 let name = child_entry.file_name();
131 let relative_path = to_scan.relative_path.join(&name);
132 let metadata = child_entry.metadata()?;
133 let ino = metadata.ino();
134 let is_symlink = metadata.file_type().is_symlink();
135
136 if metadata.is_dir() {
137 let path = to_scan.path.join(&name);
138 let mut is_ignored = true;
139 let mut ignore = None;
140
141 if let Some(parent_ignore) = to_scan.ignore.as_ref() {
142 let child_ignore = parent_ignore.add_child(&path).unwrap();
143 is_ignored = child_ignore.matched(&path, true).is_ignore() || name == ".git";
144 if !is_ignored {
145 ignore = Some(child_ignore);
146 }
147 }
148
149 let id = self.push_dir(Some(to_scan.id), name, ino, is_symlink, is_ignored);
150 new_children.push(id);
151
152 let dirs_to_scan = to_scan.dirs_to_scan.clone();
153 let _ = to_scan.dirs_to_scan.push(Ok(DirToScan {
154 id,
155 path,
156 relative_path,
157 ignore,
158 dirs_to_scan,
159 }));
160 } else {
161 let is_ignored = to_scan.ignore.as_ref().map_or(true, |i| {
162 i.matched(to_scan.path.join(&name), false).is_ignore()
163 });
164
165 new_children.push(self.push_file(
166 Some(to_scan.id),
167 name,
168 ino,
169 is_symlink,
170 is_ignored,
171 relative_path,
172 ));
173 };
174 }
175
176 if let Entry::Dir { children, .. } = &mut self.0.write().entries[to_scan.id] {
177 *children = new_children.clone();
178 }
179
180 Ok(())
181 }
182
183 fn push_dir(
184 &self,
185 parent: Option<usize>,
186 name: OsString,
187 ino: u64,
188 is_symlink: bool,
189 is_ignored: bool,
190 ) -> usize {
191 let entries = &mut self.0.write().entries;
192 let dir_id = entries.len();
193 entries.push(Entry::Dir {
194 parent,
195 name,
196 ino,
197 is_symlink,
198 is_ignored,
199 children: Vec::new(),
200 });
201 dir_id
202 }
203
204 fn push_file(
205 &self,
206 parent: Option<usize>,
207 name: OsString,
208 ino: u64,
209 is_symlink: bool,
210 is_ignored: bool,
211 path: PathBuf,
212 ) -> usize {
213 let path = path.to_string_lossy();
214 let lowercase_path = path.to_lowercase().chars().collect::<Vec<_>>();
215 let path = path.chars().collect::<Vec<_>>();
216 let path_chars = CharBag::from(&path[..]);
217
218 let mut state = self.0.write();
219 let entry_id = state.entries.len();
220 state.entries.push(Entry::File {
221 parent,
222 name,
223 ino,
224 is_symlink,
225 is_ignored,
226 });
227 state.file_paths.push(PathEntry {
228 entry_id,
229 path_chars,
230 path,
231 lowercase_path,
232 is_ignored,
233 });
234 entry_id
235 }
236
237 pub fn entry_path(&self, mut entry_id: usize) -> Result<PathBuf> {
238 let state = self.0.read();
239
240 if entry_id >= state.entries.len() {
241 return Err(anyhow!("Entry does not exist in tree"));
242 }
243
244 let mut entries = Vec::new();
245 loop {
246 let entry = &state.entries[entry_id];
247 entries.push(entry);
248 if let Some(parent_id) = entry.parent() {
249 entry_id = parent_id;
250 } else {
251 break;
252 }
253 }
254
255 let mut path = PathBuf::new();
256 for entry in entries.into_iter().rev() {
257 path.push(entry.name());
258 }
259 Ok(path)
260 }
261
262 pub fn abs_entry_path(&self, entry_id: usize) -> Result<PathBuf> {
263 let mut path = self.0.read().path.clone();
264 path.pop();
265 Ok(path.join(self.entry_path(entry_id)?))
266 }
267
268 fn fmt_entry(&self, f: &mut fmt::Formatter<'_>, entry_id: usize, indent: usize) -> fmt::Result {
269 match &self.0.read().entries[entry_id] {
270 Entry::Dir { name, children, .. } => {
271 write!(
272 f,
273 "{}{}/ ({})\n",
274 " ".repeat(indent),
275 name.to_string_lossy(),
276 entry_id
277 )?;
278 for child_id in children.iter() {
279 self.fmt_entry(f, *child_id, indent + 2)?;
280 }
281 Ok(())
282 }
283 Entry::File { name, .. } => write!(
284 f,
285 "{}{} ({})\n",
286 " ".repeat(indent),
287 name.to_string_lossy(),
288 entry_id
289 ),
290 }
291 }
292
293 pub fn path(&self) -> PathBuf {
294 PathBuf::from(&self.0.read().path)
295 }
296
297 pub fn contains_path(&self, path: &Path) -> bool {
298 path.starts_with(self.path())
299 }
300
301 pub fn iter(&self) -> Iter {
302 Iter {
303 tree: self.clone(),
304 stack: Vec::new(),
305 started: false,
306 }
307 }
308
309 pub fn files(&self) -> FilesIter {
310 FilesIter {
311 iter: self.iter(),
312 path: PathBuf::new(),
313 }
314 }
315
316 pub fn entry_count(&self) -> usize {
317 self.0.read().entries.len()
318 }
319
320 pub fn file_count(&self) -> usize {
321 self.0.read().file_paths.len()
322 }
323
324 pub fn load_history(&self, entry_id: usize) -> impl Future<Output = Result<History>> {
325 let tree = self.clone();
326
327 async move {
328 if let Some(history) = tree.0.read().histories.get(&entry_id) {
329 return Ok(history.clone());
330 }
331
332 let path = tree.abs_entry_path(entry_id)?;
333
334 let mut file = smol::fs::File::open(&path).await?;
335 let mut base_text = String::new();
336 file.read_to_string(&mut base_text).await?;
337 let history = History { base_text };
338 tree.0.write().histories.insert(entry_id, history.clone());
339 Ok(history)
340 }
341 }
342
343 fn scanning(&mut self, _: Option<()>, ctx: &mut ModelContext<Self>) {
344 if self.0.read().scanning {
345 ctx.notify();
346 } else {
347 ctx.halt_stream();
348 }
349 }
350
351 fn done_scanning(&mut self, result: io::Result<()>, ctx: &mut ModelContext<Self>) {
352 self.0.write().scanning = false;
353 if let Err(error) = result {
354 log::error!("error populating worktree: {}", error);
355 } else {
356 ctx.notify();
357 }
358 }
359}
360
361impl fmt::Debug for Worktree {
362 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
363 if self.entry_count() == 0 {
364 write!(f, "Empty tree\n")
365 } else {
366 self.fmt_entry(f, 0, 0)
367 }
368 }
369}
370
371impl Entity for Worktree {
372 type Event = ();
373}
374
375pub trait WorktreeHandle {
376 fn file(&self, entry_id: usize, app: &AppContext) -> Result<FileHandle>;
377}
378
379impl WorktreeHandle for ModelHandle<Worktree> {
380 fn file(&self, entry_id: usize, app: &AppContext) -> Result<FileHandle> {
381 if entry_id >= self.as_ref(app).entry_count() {
382 return Err(anyhow!("Entry does not exist in tree"));
383 }
384
385 Ok(FileHandle {
386 worktree: self.clone(),
387 entry_id,
388 })
389 }
390}
391
392#[derive(Clone, Debug)]
393pub enum Entry {
394 Dir {
395 parent: Option<usize>,
396 name: OsString,
397 ino: u64,
398 is_symlink: bool,
399 is_ignored: bool,
400 children: Vec<usize>,
401 },
402 File {
403 parent: Option<usize>,
404 name: OsString,
405 ino: u64,
406 is_symlink: bool,
407 is_ignored: bool,
408 },
409}
410
411impl Entry {
412 fn parent(&self) -> Option<usize> {
413 match self {
414 Entry::Dir { parent, .. } | Entry::File { parent, .. } => *parent,
415 }
416 }
417
418 fn name(&self) -> &OsStr {
419 match self {
420 Entry::Dir { name, .. } | Entry::File { name, .. } => name,
421 }
422 }
423}
424
425#[derive(Clone)]
426pub struct FileHandle {
427 worktree: ModelHandle<Worktree>,
428 entry_id: usize,
429}
430
431impl FileHandle {
432 pub fn path(&self, app: &AppContext) -> PathBuf {
433 self.worktree.as_ref(app).entry_path(self.entry_id).unwrap()
434 }
435
436 pub fn load_history(&self, app: &AppContext) -> impl Future<Output = Result<History>> {
437 self.worktree.as_ref(app).load_history(self.entry_id)
438 }
439
440 pub fn entry_id(&self) -> (usize, usize) {
441 (self.worktree.id(), self.entry_id)
442 }
443}
444
445struct IterStackEntry {
446 entry_id: usize,
447 child_idx: usize,
448}
449
450pub struct Iter {
451 tree: Worktree,
452 stack: Vec<IterStackEntry>,
453 started: bool,
454}
455
456impl Iterator for Iter {
457 type Item = Traversal;
458
459 fn next(&mut self) -> Option<Self::Item> {
460 let state = self.tree.0.read();
461
462 if !self.started {
463 self.started = true;
464
465 return if let Some(entry) = state.entries.first().cloned() {
466 self.stack.push(IterStackEntry {
467 entry_id: 0,
468 child_idx: 0,
469 });
470
471 Some(Traversal::Push { entry_id: 0, entry })
472 } else {
473 None
474 };
475 }
476
477 while let Some(parent) = self.stack.last_mut() {
478 if let Entry::Dir { children, .. } = &state.entries[parent.entry_id] {
479 if parent.child_idx < children.len() {
480 let child_id = children[post_inc(&mut parent.child_idx)];
481
482 self.stack.push(IterStackEntry {
483 entry_id: child_id,
484 child_idx: 0,
485 });
486
487 return Some(Traversal::Push {
488 entry_id: child_id,
489 entry: state.entries[child_id].clone(),
490 });
491 } else {
492 self.stack.pop();
493
494 return Some(Traversal::Pop);
495 }
496 } else {
497 self.stack.pop();
498
499 return Some(Traversal::Pop);
500 }
501 }
502
503 None
504 }
505}
506
507#[derive(Debug)]
508pub enum Traversal {
509 Push { entry_id: usize, entry: Entry },
510 Pop,
511}
512
513pub struct FilesIter {
514 iter: Iter,
515 path: PathBuf,
516}
517
518pub struct FilesIterItem {
519 pub entry_id: usize,
520 pub path: PathBuf,
521}
522
523impl Iterator for FilesIter {
524 type Item = FilesIterItem;
525
526 fn next(&mut self) -> Option<Self::Item> {
527 loop {
528 match self.iter.next() {
529 Some(Traversal::Push {
530 entry_id, entry, ..
531 }) => match entry {
532 Entry::Dir { name, .. } => {
533 self.path.push(name);
534 }
535 Entry::File { name, .. } => {
536 self.path.push(name);
537 return Some(FilesIterItem {
538 entry_id,
539 path: self.path.clone(),
540 });
541 }
542 },
543 Some(Traversal::Pop) => {
544 self.path.pop();
545 }
546 None => {
547 return None;
548 }
549 }
550 }
551 }
552}
553
554trait UnwrapIgnoreTuple {
555 fn unwrap(self) -> Ignore;
556}
557
558impl UnwrapIgnoreTuple for (Ignore, Option<ignore::Error>) {
559 fn unwrap(self) -> Ignore {
560 if let Some(error) = self.1 {
561 log::error!("error loading gitignore data: {}", error);
562 }
563 self.0
564 }
565}
566
567pub fn match_paths(
568 trees: &[Worktree],
569 query: &str,
570 include_ignored: bool,
571 smart_case: bool,
572 max_results: usize,
573) -> Vec<PathMatch> {
574 let tree_states = trees.iter().map(|tree| tree.0.read()).collect::<Vec<_>>();
575 fuzzy::match_paths(
576 &tree_states
577 .iter()
578 .map(|tree| {
579 let skip_prefix = if trees.len() == 1 {
580 if let Some(Entry::Dir { name, .. }) = tree.entries.get(0) {
581 let name = name.to_string_lossy();
582 if name == "/" {
583 1
584 } else {
585 name.chars().count() + 1
586 }
587 } else {
588 0
589 }
590 } else {
591 0
592 };
593
594 (tree.id, skip_prefix, &tree.file_paths[..])
595 })
596 .collect::<Vec<_>>()[..],
597 query,
598 include_ignored,
599 smart_case,
600 max_results,
601 )
602}
603
604// #[cfg(test)]
605// mod test {
606// use super::*;
607// use crate::test_utils::*;
608// use anyhow::Result;
609// use std::os::unix;
610//
611// // #[test]
612// // fn test_populate_and_search() -> Result<()> {
613// // let dir = build_tempdir(json!({
614// // "root": {
615// // "apple": "",
616// // "banana": {
617// // "carrot": {
618// // "date": "",
619// // "endive": "",
620// // }
621// // },
622// // "fennel": {
623// // "grape": "",
624// // }
625// // }
626// // }));
627// //
628// // let root_link_path = dir.path().join("root_link");
629// // unix::fs::symlink(&dir.path().join("root"), &root_link_path)?;
630// //
631// // let tree = Worktree::new(1, root_link_path, None);
632// // let (tx, _) = channel::unbounded();
633// // tree.populate(&tx)?;
634// // assert_eq!(tree.file_count(), 4);
635// //
636// // let results = match_paths(&[tree.clone()], "bna", false, false, 10)
637// // .iter()
638// // .map(|result| tree.entry_path(result.entry_id))
639// // .collect::<Result<Vec<PathBuf>, _>>()?;
640// //
641// // assert_eq!(
642// // results,
643// // vec![
644// // PathBuf::from("root_link/banana/carrot/date"),
645// // PathBuf::from("root_link/banana/carrot/endive"),
646// // ]
647// // );
648// //
649// // Ok(())
650// // }
651// }