1mod char_bag;
2mod fuzzy;
3
4use crate::{
5 editor::{History, Snapshot as BufferSnapshot},
6 sum_tree::{self, Edit, SumTree},
7};
8use anyhow::{anyhow, Result};
9pub use fuzzy::match_paths;
10use fuzzy::PathEntry;
11use gpui::{scoped_pool, AppContext, Entity, ModelContext, ModelHandle, Task};
12use ignore::dir::{Ignore, IgnoreBuilder};
13use parking_lot::Mutex;
14use smol::{channel::Sender, Timer};
15use std::{collections::HashSet, future::Future};
16use std::{
17 ffi::OsStr,
18 fmt, fs,
19 io::{self, Read, Write},
20 ops::{AddAssign, Deref},
21 os::unix::fs::MetadataExt,
22 path::{Path, PathBuf},
23 sync::Arc,
24 time::Duration,
25};
26
27pub use fuzzy::PathMatch;
28
29#[derive(Debug)]
30enum ScanState {
31 Idle,
32 Scanning,
33 Err(io::Error),
34}
35
36pub struct Worktree {
37 snapshot: Snapshot,
38 scanner: Arc<BackgroundScanner>,
39 scan_state: ScanState,
40 poll_scheduled: bool,
41}
42
43#[derive(Clone)]
44pub struct FileHandle {
45 worktree: ModelHandle<Worktree>,
46 inode: u64,
47}
48
49impl Worktree {
50 pub fn new(path: impl Into<Arc<Path>>, ctx: &mut ModelContext<Self>) -> Self {
51 let scan_state = smol::channel::unbounded();
52 let snapshot = Snapshot {
53 id: ctx.model_id(),
54 path: path.into(),
55 root_inode: None,
56 entries: Default::default(),
57 };
58 let scanner = Arc::new(BackgroundScanner::new(snapshot.clone(), scan_state.0));
59 let tree = Self {
60 snapshot,
61 scanner,
62 scan_state: ScanState::Idle,
63 poll_scheduled: false,
64 };
65
66 let scanner = tree.scanner.clone();
67 std::thread::spawn(move || scanner.run());
68
69 ctx.spawn_stream(scan_state.1, Self::observe_scan_state, |_, _| {})
70 .detach();
71
72 tree
73 }
74
75 fn observe_scan_state(&mut self, scan_state: ScanState, ctx: &mut ModelContext<Self>) {
76 self.scan_state = scan_state;
77 self.poll_entries(ctx);
78 }
79
80 fn poll_entries(&mut self, ctx: &mut ModelContext<Self>) {
81 self.snapshot = self.scanner.snapshot();
82 ctx.notify();
83
84 if self.is_scanning() && !self.poll_scheduled {
85 ctx.spawn(Timer::after(Duration::from_millis(100)), |this, _, ctx| {
86 this.poll_scheduled = false;
87 this.poll_entries(ctx);
88 })
89 .detach();
90 self.poll_scheduled = true;
91 }
92 }
93
94 fn is_scanning(&self) -> bool {
95 if let ScanState::Scanning = self.scan_state {
96 true
97 } else {
98 false
99 }
100 }
101
102 pub fn snapshot(&self) -> Snapshot {
103 self.snapshot.clone()
104 }
105
106 pub fn contains_path(&self, path: &Path) -> bool {
107 path.starts_with(&self.snapshot.path)
108 }
109
110 pub fn has_inode(&self, inode: u64) -> bool {
111 self.snapshot.entries.get(&inode).is_some()
112 }
113
114 pub fn file_count(&self) -> usize {
115 self.snapshot.entries.summary().file_count
116 }
117
118 pub fn abs_path_for_inode(&self, ino: u64) -> Result<PathBuf> {
119 let mut result = self.snapshot.path.to_path_buf();
120 result.push(self.path_for_inode(ino, false)?);
121 Ok(result)
122 }
123
124 pub fn load_history(
125 &self,
126 ino: u64,
127 ctx: &AppContext,
128 ) -> impl Future<Output = Result<History>> {
129 let path = self.abs_path_for_inode(ino);
130 ctx.background_executor().spawn(async move {
131 let mut file = std::fs::File::open(&path?)?;
132 let mut base_text = String::new();
133 file.read_to_string(&mut base_text)?;
134 Ok(History::new(Arc::from(base_text)))
135 })
136 }
137
138 pub fn save<'a>(
139 &self,
140 ino: u64,
141 content: BufferSnapshot,
142 ctx: &AppContext,
143 ) -> Task<Result<()>> {
144 let path = self.abs_path_for_inode(ino);
145 ctx.background_executor().spawn(async move {
146 let buffer_size = content.text_summary().bytes.min(10 * 1024);
147 let file = std::fs::File::create(&path?)?;
148 let mut writer = std::io::BufWriter::with_capacity(buffer_size, file);
149 for chunk in content.fragments() {
150 writer.write(chunk.as_bytes())?;
151 }
152 writer.flush()?;
153 Ok(())
154 })
155 }
156
157 #[cfg(test)]
158 pub fn files<'a>(&'a self) -> impl Iterator<Item = u64> + 'a {
159 self.snapshot
160 .entries
161 .cursor::<(), ()>()
162 .filter_map(|entry| {
163 if let Entry::File { inode, .. } = entry {
164 Some(*inode)
165 } else {
166 None
167 }
168 })
169 }
170}
171
172impl Entity for Worktree {
173 type Event = ();
174}
175
176impl Deref for Worktree {
177 type Target = Snapshot;
178
179 fn deref(&self) -> &Self::Target {
180 &self.snapshot
181 }
182}
183
184impl fmt::Debug for Worktree {
185 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
186 self.snapshot.fmt(f)
187 }
188}
189
190#[derive(Clone)]
191pub struct Snapshot {
192 id: usize,
193 path: Arc<Path>,
194 root_inode: Option<u64>,
195 entries: SumTree<Entry>,
196}
197
198impl Snapshot {
199 pub fn file_count(&self) -> usize {
200 self.entries.summary().file_count
201 }
202
203 pub fn root_entry(&self) -> Option<&Entry> {
204 self.root_inode.and_then(|inode| self.entries.get(&inode))
205 }
206
207 fn inode_for_path(&self, path: impl AsRef<Path>) -> Option<u64> {
208 let path = path.as_ref();
209 self.root_inode.and_then(|mut inode| {
210 'components: for path_component in path {
211 if let Some(Entry::Dir { children, .. }) = &self.entries.get(&inode) {
212 for child in children.as_ref() {
213 if self.entries.get(child).map(|entry| entry.name()) == Some(path_component)
214 {
215 inode = *child;
216 continue 'components;
217 }
218 }
219 }
220 return None;
221 }
222 Some(inode)
223 })
224 }
225
226 fn entry_for_path(&self, path: impl AsRef<Path>) -> Option<&Entry> {
227 self.inode_for_path(path)
228 .and_then(|inode| self.entries.get(&inode))
229 }
230
231 pub fn path_for_inode(&self, ino: u64, include_root: bool) -> Result<PathBuf> {
232 let mut components = Vec::new();
233 let mut entry = self
234 .entries
235 .get(&ino)
236 .ok_or_else(|| anyhow!("entry does not exist in worktree"))?;
237 components.push(entry.name());
238 while let Some(parent) = entry.parent() {
239 entry = self.entries.get(&parent).unwrap();
240 components.push(entry.name());
241 }
242
243 let mut components = components.into_iter().rev();
244 if !include_root {
245 components.next();
246 }
247
248 let mut path = PathBuf::new();
249 for component in components {
250 path.push(component);
251 }
252 Ok(path)
253 }
254
255 fn reparent_entry(
256 &mut self,
257 child_inode: u64,
258 new_filename: Option<&OsStr>,
259 old_parent_inode: Option<u64>,
260 new_parent_inode: Option<u64>,
261 ) {
262 let mut edits_len = 1;
263 if old_parent_inode.is_some() {
264 edits_len += 1;
265 }
266 if new_parent_inode.is_some() {
267 edits_len += 1;
268 }
269 let mut deletions = Vec::with_capacity(edits_len);
270 let mut insertions = Vec::with_capacity(edits_len);
271
272 // Remove the entries from the sum tree.
273 deletions.push(Edit::Remove(child_inode));
274 if let Some(old_parent_inode) = old_parent_inode {
275 deletions.push(Edit::Remove(old_parent_inode));
276 }
277 if let Some(new_parent_inode) = new_parent_inode {
278 deletions.push(Edit::Remove(new_parent_inode));
279 }
280 let removed_entries = self.entries.edit(deletions);
281 let mut child_entry = None;
282 let mut old_parent_entry = None;
283 let mut new_parent_entry = None;
284 for removed_entry in removed_entries {
285 if removed_entry.ino() == child_inode {
286 child_entry = Some(removed_entry);
287 } else if Some(removed_entry.ino()) == old_parent_inode {
288 old_parent_entry = Some(removed_entry);
289 } else if Some(removed_entry.ino()) == new_parent_inode {
290 new_parent_entry = Some(removed_entry);
291 }
292 }
293
294 // Update the child entry's parent.
295 let mut child_entry = child_entry.expect("cannot reparent non-existent entry");
296 child_entry.set_parent(new_parent_inode);
297 if let Some(new_filename) = new_filename {
298 child_entry.set_name(new_filename);
299 }
300 insertions.push(Edit::Insert(child_entry));
301
302 // Remove the child entry from it's old parent's children.
303 if let Some(mut old_parent_entry) = old_parent_entry {
304 if let Entry::Dir { children, .. } = &mut old_parent_entry {
305 *children = children
306 .into_iter()
307 .cloned()
308 .filter(|c| *c != child_inode)
309 .collect();
310 insertions.push(Edit::Insert(old_parent_entry));
311 } else {
312 panic!("snapshot entry's new parent was not a directory");
313 }
314 }
315
316 // Add the child entry to it's new parent's children.
317 if let Some(mut new_parent_entry) = new_parent_entry {
318 if let Entry::Dir { children, .. } = &mut new_parent_entry {
319 *children = children
320 .into_iter()
321 .cloned()
322 .chain(Some(child_inode))
323 .collect();
324 insertions.push(Edit::Insert(new_parent_entry));
325 } else {
326 panic!("snapshot entry's new parent is not a directory");
327 }
328 }
329
330 self.entries.edit(insertions);
331 }
332
333 fn fmt_entry(&self, f: &mut fmt::Formatter<'_>, ino: u64, indent: usize) -> fmt::Result {
334 match self.entries.get(&ino).unwrap() {
335 Entry::Dir { name, children, .. } => {
336 write!(
337 f,
338 "{}{}/ ({})\n",
339 " ".repeat(indent),
340 name.to_string_lossy(),
341 ino
342 )?;
343 for child_id in children.iter() {
344 self.fmt_entry(f, *child_id, indent + 2)?;
345 }
346 Ok(())
347 }
348 Entry::File { name, .. } => write!(
349 f,
350 "{}{} ({})\n",
351 " ".repeat(indent),
352 name.to_string_lossy(),
353 ino
354 ),
355 }
356 }
357}
358
359impl fmt::Debug for Snapshot {
360 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
361 if let Some(root_ino) = self.root_inode {
362 self.fmt_entry(f, root_ino, 0)
363 } else {
364 write!(f, "Empty tree\n")
365 }
366 }
367}
368
369impl FileHandle {
370 pub fn path(&self, ctx: &AppContext) -> PathBuf {
371 self.worktree
372 .read(ctx)
373 .path_for_inode(self.inode, false)
374 .unwrap()
375 }
376
377 pub fn load_history(&self, ctx: &AppContext) -> impl Future<Output = Result<History>> {
378 self.worktree.read(ctx).load_history(self.inode, ctx)
379 }
380
381 pub fn save<'a>(&self, content: BufferSnapshot, ctx: &AppContext) -> Task<Result<()>> {
382 let worktree = self.worktree.read(ctx);
383 worktree.save(self.inode, content, ctx)
384 }
385
386 pub fn entry_id(&self) -> (usize, u64) {
387 (self.worktree.id(), self.inode)
388 }
389}
390
391#[derive(Clone, Debug)]
392pub enum Entry {
393 Dir {
394 parent: Option<u64>,
395 name: Arc<OsStr>,
396 inode: u64,
397 is_symlink: bool,
398 is_ignored: bool,
399 children: Arc<[u64]>,
400 pending: bool,
401 },
402 File {
403 parent: Option<u64>,
404 name: Arc<OsStr>,
405 path: PathEntry,
406 inode: u64,
407 is_symlink: bool,
408 is_ignored: bool,
409 },
410}
411
412impl Entry {
413 fn ino(&self) -> u64 {
414 match self {
415 Entry::Dir { inode, .. } => *inode,
416 Entry::File { inode, .. } => *inode,
417 }
418 }
419
420 fn is_dir(&self) -> bool {
421 matches!(self, Entry::Dir { .. })
422 }
423
424 fn parent(&self) -> Option<u64> {
425 match self {
426 Entry::Dir { parent, .. } => *parent,
427 Entry::File { parent, .. } => *parent,
428 }
429 }
430
431 fn set_parent(&mut self, new_parent: Option<u64>) {
432 match self {
433 Entry::Dir { parent, .. } => *parent = new_parent,
434 Entry::File { parent, .. } => *parent = new_parent,
435 }
436 }
437
438 fn name(&self) -> &OsStr {
439 match self {
440 Entry::Dir { name, .. } => name,
441 Entry::File { name, .. } => name,
442 }
443 }
444
445 fn set_name(&mut self, new_name: &OsStr) {
446 match self {
447 Entry::Dir { name, .. } => *name = new_name.into(),
448 Entry::File { name, .. } => *name = new_name.into(),
449 }
450 }
451}
452
453impl sum_tree::Item for Entry {
454 type Summary = EntrySummary;
455
456 fn summary(&self) -> Self::Summary {
457 EntrySummary {
458 max_ino: self.ino(),
459 file_count: if matches!(self, Self::File { .. }) {
460 1
461 } else {
462 0
463 },
464 }
465 }
466}
467
468impl sum_tree::KeyedItem for Entry {
469 type Key = u64;
470
471 fn key(&self) -> Self::Key {
472 self.ino()
473 }
474}
475
476#[derive(Clone, Debug, Default)]
477pub struct EntrySummary {
478 max_ino: u64,
479 file_count: usize,
480}
481
482impl<'a> AddAssign<&'a EntrySummary> for EntrySummary {
483 fn add_assign(&mut self, rhs: &'a EntrySummary) {
484 self.max_ino = rhs.max_ino;
485 self.file_count += rhs.file_count;
486 }
487}
488
489impl<'a> sum_tree::Dimension<'a, EntrySummary> for u64 {
490 fn add_summary(&mut self, summary: &'a EntrySummary) {
491 *self = summary.max_ino;
492 }
493}
494
495#[derive(Copy, Clone, Default, Debug, Eq, PartialEq, Ord, PartialOrd)]
496struct FileCount(usize);
497
498impl<'a> sum_tree::Dimension<'a, EntrySummary> for FileCount {
499 fn add_summary(&mut self, summary: &'a EntrySummary) {
500 self.0 += summary.file_count;
501 }
502}
503
504struct BackgroundScanner {
505 snapshot: Mutex<Snapshot>,
506 notify: Sender<ScanState>,
507 thread_pool: scoped_pool::Pool,
508}
509
510impl BackgroundScanner {
511 fn new(snapshot: Snapshot, notify: Sender<ScanState>) -> Self {
512 Self {
513 snapshot: Mutex::new(snapshot),
514 notify,
515 thread_pool: scoped_pool::Pool::new(16),
516 }
517 }
518
519 fn path(&self) -> Arc<Path> {
520 self.snapshot.lock().path.clone()
521 }
522
523 fn snapshot(&self) -> Snapshot {
524 self.snapshot.lock().clone()
525 }
526
527 fn run(&self) {
528 let path = {
529 let mut snapshot = self.snapshot.lock();
530 let canonical_path = snapshot
531 .path
532 .canonicalize()
533 .map(Arc::from)
534 .unwrap_or_else(|_| snapshot.path.clone());
535 snapshot.path = canonical_path.clone();
536 canonical_path
537 };
538
539 // Create the event stream before we start scanning to ensure we receive events for changes
540 // that occur in the middle of the scan.
541 let event_stream =
542 fsevent::EventStream::new(&[path.as_ref()], Duration::from_millis(100), |events| {
543 if smol::block_on(self.notify.send(ScanState::Scanning)).is_err() {
544 return false;
545 }
546
547 self.process_events(events);
548
549 if smol::block_on(self.notify.send(ScanState::Idle)).is_err() {
550 return false;
551 }
552
553 true
554 });
555
556 if smol::block_on(self.notify.send(ScanState::Scanning)).is_err() {
557 return;
558 }
559
560 if let Err(err) = self.scan_dirs() {
561 if smol::block_on(self.notify.send(ScanState::Err(err))).is_err() {
562 return;
563 }
564 }
565
566 if smol::block_on(self.notify.send(ScanState::Idle)).is_err() {
567 return;
568 }
569
570 event_stream.run();
571 }
572
573 fn scan_dirs(&self) -> io::Result<()> {
574 let path = self.path();
575 let metadata = fs::metadata(&path)?;
576 let inode = metadata.ino();
577 let is_symlink = fs::symlink_metadata(&path)?.file_type().is_symlink();
578 let name = Arc::from(path.file_name().unwrap_or(OsStr::new("/")));
579 let relative_path = PathBuf::from(&name);
580
581 let mut ignore = IgnoreBuilder::new().build().add_parents(&path).unwrap();
582 if metadata.is_dir() {
583 ignore = ignore.add_child(&path).unwrap();
584 }
585 let is_ignored = ignore.matched(&path, metadata.is_dir()).is_ignore();
586
587 if metadata.file_type().is_dir() {
588 let is_ignored = is_ignored || name.as_ref() == ".git";
589 let dir_entry = Entry::Dir {
590 parent: None,
591 name,
592 inode,
593 is_symlink,
594 is_ignored,
595 children: Arc::from([]),
596 pending: true,
597 };
598 self.insert_entries(Some(dir_entry.clone()));
599 self.snapshot.lock().root_inode = Some(inode);
600
601 let (tx, rx) = crossbeam_channel::unbounded();
602
603 tx.send(Ok(ScanJob {
604 ino: inode,
605 path: path.clone(),
606 relative_path,
607 dir_entry,
608 ignore: Some(ignore),
609 scan_queue: tx.clone(),
610 }))
611 .unwrap();
612 drop(tx);
613
614 let mut results = Vec::new();
615 results.resize_with(self.thread_pool.workers(), || Ok(()));
616 self.thread_pool.scoped(|pool| {
617 for result in &mut results {
618 pool.execute(|| {
619 let result = result;
620 while let Ok(job) = rx.recv() {
621 if let Err(err) = job.and_then(|job| self.scan_dir(job, None)) {
622 *result = Err(err);
623 break;
624 }
625 }
626 });
627 }
628 });
629 results.into_iter().collect::<io::Result<()>>()?;
630 } else {
631 self.insert_entries(Some(Entry::File {
632 parent: None,
633 name,
634 path: PathEntry::new(inode, &relative_path, is_ignored),
635 inode,
636 is_symlink,
637 is_ignored,
638 }));
639 self.snapshot.lock().root_inode = Some(inode);
640 }
641
642 Ok(())
643 }
644
645 fn scan_dir(&self, job: ScanJob, mut children: Option<&mut Vec<u64>>) -> io::Result<()> {
646 let scan_queue = job.scan_queue;
647 let mut dir_entry = job.dir_entry;
648
649 let mut new_children = Vec::new();
650 let mut new_entries = Vec::new();
651 let mut new_jobs = Vec::new();
652
653 for child_entry in fs::read_dir(&job.path)? {
654 let child_entry = child_entry?;
655 let name: Arc<OsStr> = child_entry.file_name().into();
656 let relative_path = job.relative_path.join(name.as_ref());
657 let metadata = child_entry.metadata()?;
658 let ino = metadata.ino();
659 let is_symlink = metadata.file_type().is_symlink();
660 let path = job.path.join(name.as_ref());
661
662 new_children.push(ino);
663 if let Some(children) = children.as_mut() {
664 children.push(ino);
665 }
666 if metadata.is_dir() {
667 let mut is_ignored = true;
668 let mut ignore = None;
669
670 if let Some(parent_ignore) = job.ignore.as_ref() {
671 let child_ignore = parent_ignore.add_child(&path).unwrap();
672 is_ignored =
673 child_ignore.matched(&path, true).is_ignore() || name.as_ref() == ".git";
674 if !is_ignored {
675 ignore = Some(child_ignore);
676 }
677 }
678
679 let dir_entry = Entry::Dir {
680 parent: Some(job.ino),
681 name,
682 inode: ino,
683 is_symlink,
684 is_ignored,
685 children: Arc::from([]),
686 pending: true,
687 };
688 new_entries.push(dir_entry.clone());
689 new_jobs.push(ScanJob {
690 ino,
691 path: Arc::from(path),
692 relative_path,
693 dir_entry,
694 ignore,
695 scan_queue: scan_queue.clone(),
696 });
697 } else {
698 let is_ignored = job
699 .ignore
700 .as_ref()
701 .map_or(true, |i| i.matched(&path, false).is_ignore());
702 new_entries.push(Entry::File {
703 parent: Some(job.ino),
704 name,
705 path: PathEntry::new(ino, &relative_path, is_ignored),
706 inode: ino,
707 is_symlink,
708 is_ignored,
709 });
710 };
711 }
712
713 if let Entry::Dir {
714 children, pending, ..
715 } = &mut dir_entry
716 {
717 *children = Arc::from(new_children);
718 *pending = false;
719 } else {
720 unreachable!()
721 }
722 new_entries.push(dir_entry);
723
724 self.insert_entries(new_entries);
725 for new_job in new_jobs {
726 scan_queue.send(Ok(new_job)).unwrap();
727 }
728
729 Ok(())
730 }
731
732 fn process_events(&self, mut events: Vec<fsevent::Event>) {
733 let mut snapshot = self.snapshot();
734
735 events.sort_unstable_by(|a, b| a.path.cmp(&b.path));
736 let mut paths = events.into_iter().map(|e| e.path).peekable();
737 let mut possible_removed_inodes = HashSet::new();
738 let (scan_queue_tx, scan_queue_rx) = crossbeam_channel::unbounded();
739
740 while let Some(path) = paths.next() {
741 let relative_path = match path.strip_prefix(&snapshot.path) {
742 Ok(relative_path) => relative_path.to_path_buf(),
743 Err(e) => {
744 log::error!("Unexpected event {:?}", e);
745 continue;
746 }
747 };
748
749 let snapshot_entry = snapshot.entry_for_path(&relative_path);
750 let fs_entry = self.fs_entry_for_path(&snapshot.path, &path);
751
752 match fs_entry {
753 // If this path currently exists on the filesystem, then ensure that the snapshot's
754 // entry for this path is up-to-date.
755 Ok(Some((fs_entry, ignore))) => {
756 let fs_inode = fs_entry.ino();
757 let fs_parent_inode = fs_entry.parent();
758
759 // If the snapshot already contains an entry for this path, then ensure that the
760 // entry has the correct inode and parent.
761 if let Some(snapshot_entry) = snapshot_entry {
762 let snapshot_inode = snapshot_entry.ino();
763 let snapshot_parent_inode = snapshot_entry.parent();
764
765 // If the snapshot entry already matches the filesystem, then skip to the
766 // next event path.
767 if snapshot_inode == fs_inode && snapshot_parent_inode == fs_parent_inode {
768 continue;
769 }
770
771 // If it does not match, then detach this inode from its current parent, and
772 // record that it may have been removed from the worktree.
773 snapshot.reparent_entry(snapshot_inode, None, snapshot_parent_inode, None);
774 possible_removed_inodes.insert(snapshot_inode);
775 }
776
777 // If the snapshot already contained an entry for the inode that is now located
778 // at this path in the filesystem, then move it to reflect its current parent on
779 // the filesystem.
780 if let Some(snapshot_entry_for_inode) = snapshot.entries.get(&fs_inode) {
781 let snapshot_parent_inode = snapshot_entry_for_inode.parent();
782 snapshot.reparent_entry(
783 fs_inode,
784 path.file_name(),
785 snapshot_parent_inode,
786 fs_parent_inode,
787 );
788 }
789 // If the snapshot has no entry for this inode, then scan the filesystem to find
790 // all descendents of this new inode. Discard any subsequent events that are
791 // contained by the current path, since the directory is already being scanned
792 // from scratch.
793 else {
794 while let Some(next_path) = paths.peek() {
795 if next_path.starts_with(&path) {
796 paths.next();
797 } else {
798 break;
799 }
800 }
801
802 snapshot.entries.insert(fs_entry.clone());
803 snapshot.reparent_entry(fs_inode, None, None, fs_parent_inode);
804
805 if fs_entry.is_dir() {
806 let relative_path = snapshot
807 .path
808 .parent()
809 .map_or(path.as_path(), |parent| path.strip_prefix(parent).unwrap())
810 .to_path_buf();
811 scan_queue_tx
812 .send(Ok(ScanJob {
813 ino: fs_inode,
814 path: Arc::from(path),
815 relative_path,
816 dir_entry: fs_entry,
817 ignore: Some(ignore),
818 scan_queue: scan_queue_tx.clone(),
819 }))
820 .unwrap();
821 }
822 }
823 }
824
825 // If this path no longer exists on the filesystem, then remove it from the snapshot.
826 Ok(None) => {
827 if let Some(snapshot_entry) = snapshot_entry {
828 let snapshot_inode = snapshot_entry.ino();
829 let snapshot_parent_inode = snapshot_entry.parent();
830 snapshot.reparent_entry(snapshot_inode, None, snapshot_parent_inode, None);
831 possible_removed_inodes.insert(snapshot_inode);
832 }
833 }
834 Err(e) => {
835 // TODO - create a special 'error' entry in the entries tree to mark this
836 log::error!("Error reading file on event {:?}", e);
837 }
838 }
839 }
840
841 // For now, update the locked snapshot at this point, because `scan_dir` uses that.
842 *self.snapshot.lock() = snapshot;
843
844 // Scan any directories that were moved into this worktree as part of this event batch.
845 drop(scan_queue_tx);
846 let mut scanned_inodes = Vec::new();
847 scanned_inodes.resize_with(self.thread_pool.workers(), || Ok(Vec::new()));
848 self.thread_pool.scoped(|pool| {
849 for worker_inodes in &mut scanned_inodes {
850 pool.execute(|| {
851 let worker_inodes = worker_inodes;
852 while let Ok(job) = scan_queue_rx.recv() {
853 if let Err(err) = job.and_then(|job| {
854 self.scan_dir(job, Some(worker_inodes.as_mut().unwrap()))
855 }) {
856 *worker_inodes = Err(err);
857 break;
858 }
859 }
860 });
861 }
862 });
863
864 // Remove any entries that became orphaned when processing this events batch.
865 let mut snapshot = self.snapshot();
866 let mut deletions = Vec::new();
867 let mut descendent_stack = Vec::new();
868 for inode in possible_removed_inodes {
869 if let Some(entry) = snapshot.entries.get(&inode) {
870 if entry.parent().is_none() {
871 descendent_stack.push(inode);
872 }
873 }
874
875 // Recursively remove the orphaned nodes' descendants.
876 while let Some(inode) = descendent_stack.pop() {
877 if let Some(entry) = snapshot.entries.get(&inode) {
878 deletions.push(Edit::Remove(inode));
879 if let Entry::Dir { children, .. } = entry {
880 descendent_stack.extend_from_slice(children.as_ref());
881 }
882 }
883 }
884 }
885 snapshot.entries.edit(deletions);
886 *self.snapshot.lock() = snapshot;
887 }
888
889 fn fs_entry_for_path(&self, root_path: &Path, path: &Path) -> Result<Option<(Entry, Ignore)>> {
890 match fs::metadata(&path) {
891 Ok(metadata) => {
892 let mut ignore = IgnoreBuilder::new().build().add_parents(&path).unwrap();
893 if metadata.is_dir() {
894 ignore = ignore.add_child(&path).unwrap();
895 }
896 let is_ignored = ignore.matched(&path, metadata.is_dir()).is_ignore();
897
898 let inode = metadata.ino();
899 let name: Arc<OsStr> = Arc::from(path.file_name().unwrap_or(OsStr::new("/")));
900 let is_symlink = fs::symlink_metadata(&path)?.file_type().is_symlink();
901 let parent = if path == root_path {
902 None
903 } else {
904 Some(fs::metadata(path.parent().unwrap())?.ino())
905 };
906 if metadata.file_type().is_dir() {
907 Ok(Some((
908 Entry::Dir {
909 parent,
910 name,
911 inode,
912 is_symlink,
913 is_ignored,
914 children: Arc::from([]),
915 pending: true,
916 },
917 ignore,
918 )))
919 } else {
920 Ok(Some((
921 Entry::File {
922 parent,
923 name,
924 path: PathEntry::new(
925 inode,
926 root_path
927 .parent()
928 .map_or(path, |parent| path.strip_prefix(parent).unwrap()),
929 is_ignored,
930 ),
931 inode,
932 is_symlink,
933 is_ignored,
934 },
935 ignore,
936 )))
937 }
938 }
939 Err(err) => {
940 if err.kind() == io::ErrorKind::NotFound {
941 Ok(None)
942 } else {
943 Err(anyhow::Error::new(err))
944 }
945 }
946 }
947 }
948
949 fn insert_entries(&self, entries: impl IntoIterator<Item = Entry>) {
950 self.snapshot
951 .lock()
952 .entries
953 .edit(entries.into_iter().map(Edit::Insert).collect::<Vec<_>>());
954 }
955}
956
957struct ScanJob {
958 ino: u64,
959 path: Arc<Path>,
960 relative_path: PathBuf,
961 dir_entry: Entry,
962 ignore: Option<Ignore>,
963 scan_queue: crossbeam_channel::Sender<io::Result<ScanJob>>,
964}
965
966pub trait WorktreeHandle {
967 fn file(&self, entry_id: u64, app: &AppContext) -> Result<FileHandle>;
968}
969
970impl WorktreeHandle for ModelHandle<Worktree> {
971 fn file(&self, inode: u64, app: &AppContext) -> Result<FileHandle> {
972 if self.read(app).has_inode(inode) {
973 Ok(FileHandle {
974 worktree: self.clone(),
975 inode,
976 })
977 } else {
978 Err(anyhow!("entry does not exist in tree"))
979 }
980 }
981}
982
983trait UnwrapIgnoreTuple {
984 fn unwrap(self) -> Ignore;
985}
986
987impl UnwrapIgnoreTuple for (Ignore, Option<ignore::Error>) {
988 fn unwrap(self) -> Ignore {
989 if let Some(error) = self.1 {
990 log::error!("error loading gitignore data: {}", error);
991 }
992 self.0
993 }
994}
995
996#[cfg(test)]
997mod tests {
998 use super::*;
999 use crate::editor::Buffer;
1000 use crate::test::*;
1001 use anyhow::Result;
1002 use gpui::App;
1003 use log::LevelFilter;
1004 use rand::prelude::*;
1005 use serde_json::json;
1006 use simplelog::SimpleLogger;
1007 use std::env;
1008 use std::os::unix;
1009 use std::time::{SystemTime, UNIX_EPOCH};
1010
1011 #[test]
1012 fn test_populate_and_search() {
1013 App::test_async((), |mut app| async move {
1014 let dir = temp_tree(json!({
1015 "root": {
1016 "apple": "",
1017 "banana": {
1018 "carrot": {
1019 "date": "",
1020 "endive": "",
1021 }
1022 },
1023 "fennel": {
1024 "grape": "",
1025 }
1026 }
1027 }));
1028
1029 let root_link_path = dir.path().join("root_link");
1030 unix::fs::symlink(&dir.path().join("root"), &root_link_path).unwrap();
1031
1032 let tree = app.add_model(|ctx| Worktree::new(root_link_path, ctx));
1033 assert_condition(1, 300, || app.read(|ctx| tree.read(ctx).file_count() == 4)).await;
1034 app.read(|ctx| {
1035 let tree = tree.read(ctx);
1036 let results = match_paths(
1037 Some(tree.snapshot()).iter(),
1038 "bna",
1039 false,
1040 false,
1041 false,
1042 10,
1043 ctx.thread_pool().clone(),
1044 )
1045 .iter()
1046 .map(|result| tree.path_for_inode(result.entry_id, true))
1047 .collect::<Result<Vec<PathBuf>, _>>()
1048 .unwrap();
1049 assert_eq!(
1050 results,
1051 vec![
1052 PathBuf::from("root_link/banana/carrot/date"),
1053 PathBuf::from("root_link/banana/carrot/endive"),
1054 ]
1055 );
1056 })
1057 });
1058 }
1059
1060 #[test]
1061 fn test_save_file() {
1062 App::test_async((), |mut app| async move {
1063 let dir = temp_tree(json!({
1064 "file1": "the old contents",
1065 }));
1066
1067 let tree = app.add_model(|ctx| Worktree::new(dir.path(), ctx));
1068 assert_condition(1, 300, || app.read(|ctx| tree.read(ctx).file_count() == 1)).await;
1069
1070 let buffer = Buffer::new(1, "a line of text.\n".repeat(10 * 1024));
1071
1072 let file_inode = app.read(|ctx| {
1073 let tree = tree.read(ctx);
1074 let inode = tree.files().next().unwrap();
1075 assert_eq!(
1076 tree.path_for_inode(inode, false)
1077 .unwrap()
1078 .file_name()
1079 .unwrap(),
1080 "file1"
1081 );
1082 inode
1083 });
1084
1085 tree.update(&mut app, |tree, ctx| {
1086 smol::block_on(tree.save(file_inode, buffer.snapshot(), ctx.as_ref())).unwrap()
1087 });
1088
1089 let loaded_history = app
1090 .read(|ctx| tree.read(ctx).load_history(file_inode, ctx))
1091 .await
1092 .unwrap();
1093 assert_eq!(loaded_history.base_text.as_ref(), buffer.text());
1094 });
1095 }
1096
1097 #[test]
1098 fn test_rescan() {
1099 App::test_async((), |mut app| async move {
1100 let dir2 = temp_tree(json!({
1101 "dir1": {
1102 "dir3": {
1103 "file": "contents",
1104 }
1105 },
1106 "dir2": {
1107 }
1108 }));
1109 let dir = temp_tree(json!({
1110 "dir1": {
1111 "dir3": {
1112 "file": "contents",
1113 }
1114 },
1115 "dir2": {
1116 }
1117 }));
1118
1119 let tree = app.add_model(|ctx| Worktree::new(dir.path(), ctx));
1120 assert_condition(1, 300, || app.read(|ctx| tree.read(ctx).file_count() == 1)).await;
1121
1122 let dir_inode = app.read(|ctx| {
1123 tree.read(ctx)
1124 .snapshot()
1125 .inode_for_path("dir1/dir3")
1126 .unwrap()
1127 });
1128 app.read(|ctx| {
1129 let tree = tree.read(ctx);
1130 assert_eq!(
1131 tree.path_for_inode(dir_inode, false)
1132 .unwrap()
1133 .to_str()
1134 .unwrap(),
1135 "dir1/dir3"
1136 );
1137 });
1138
1139 std::fs::rename(dir2.path(), dir.path().join("foo")).unwrap();
1140 assert_condition(1, 300, || {
1141 app.read(|ctx| {
1142 let tree = tree.read(ctx);
1143 tree.path_for_inode(dir_inode, false)
1144 .unwrap()
1145 .to_str()
1146 .unwrap()
1147 == "dir2/dir3"
1148 })
1149 })
1150 .await;
1151 app.read(|ctx| {
1152 let tree = tree.read(ctx);
1153 assert_eq!(tree.snapshot().inode_for_path("dir2/dir3"), Some(dir_inode));
1154 });
1155 });
1156 }
1157
1158 #[test]
1159 fn test_random() {
1160 if let Ok(true) = env::var("LOG").map(|l| l.parse().unwrap()) {
1161 SimpleLogger::init(LevelFilter::Info, Default::default()).unwrap();
1162 }
1163
1164 let iterations = env::var("ITERATIONS")
1165 .map(|i| i.parse().unwrap())
1166 .unwrap_or(100);
1167 let operations = env::var("OPERATIONS")
1168 .map(|o| o.parse().unwrap())
1169 .unwrap_or(40);
1170 let seeds = if let Ok(seed) = env::var("SEED").map(|s| s.parse().unwrap()) {
1171 seed..seed + 1
1172 } else {
1173 0..iterations
1174 };
1175
1176 for seed in seeds {
1177 dbg!(seed);
1178 let mut rng = StdRng::seed_from_u64(seed);
1179
1180 let root_dir = tempdir::TempDir::new(&format!("test-{}", seed)).unwrap();
1181 for _ in 0..20 {
1182 randomly_mutate_tree(root_dir.path(), 1.0, &mut rng).unwrap();
1183 }
1184 log::info!("Generated initial tree");
1185
1186 let (notify_tx, _notify_rx) = smol::channel::unbounded();
1187 let scanner = BackgroundScanner::new(
1188 Snapshot {
1189 id: 0,
1190 path: root_dir.path().into(),
1191 root_inode: None,
1192 entries: Default::default(),
1193 },
1194 notify_tx,
1195 );
1196 scanner.scan_dirs().unwrap();
1197
1198 let mut events = Vec::new();
1199 let mut mutations_len = operations;
1200 while mutations_len > 1 {
1201 if !events.is_empty() && rng.gen_bool(0.4) {
1202 let len = rng.gen_range(0..=events.len());
1203 let to_deliver = events.drain(0..len).collect::<Vec<_>>();
1204 scanner.process_events(to_deliver);
1205 } else {
1206 events.extend(randomly_mutate_tree(root_dir.path(), 0.6, &mut rng).unwrap());
1207 mutations_len -= 1;
1208 }
1209 }
1210 scanner.process_events(events);
1211
1212 let (notify_tx, _notify_rx) = smol::channel::unbounded();
1213 let new_scanner = BackgroundScanner::new(
1214 Snapshot {
1215 id: 0,
1216 path: root_dir.path().into(),
1217 root_inode: None,
1218 entries: Default::default(),
1219 },
1220 notify_tx,
1221 );
1222 new_scanner.scan_dirs().unwrap();
1223 assert_eq!(scanner.snapshot().to_vec(), new_scanner.snapshot().to_vec());
1224 }
1225 }
1226
1227 fn randomly_mutate_tree(
1228 root_path: &Path,
1229 insertion_probability: f64,
1230 rng: &mut impl Rng,
1231 ) -> Result<Vec<fsevent::Event>> {
1232 let (dirs, files) = read_dir_recursive(root_path.to_path_buf());
1233
1234 let mut events = Vec::new();
1235 let mut record_event = |path: PathBuf| {
1236 events.push(fsevent::Event {
1237 event_id: SystemTime::now()
1238 .duration_since(UNIX_EPOCH)
1239 .unwrap()
1240 .as_secs(),
1241 flags: fsevent::StreamFlags::empty(),
1242 path,
1243 });
1244 };
1245
1246 if (files.is_empty() && dirs.len() == 1) || rng.gen_bool(insertion_probability) {
1247 let path = dirs.choose(rng).unwrap();
1248 let new_path = path.join(gen_name(rng));
1249
1250 if rng.gen() {
1251 log::info!("Creating dir {:?}", new_path.strip_prefix(root_path)?);
1252 fs::create_dir(&new_path)?;
1253 } else {
1254 log::info!("Creating file {:?}", new_path.strip_prefix(root_path)?);
1255 fs::write(&new_path, "")?;
1256 }
1257 record_event(new_path);
1258 } else {
1259 let old_path = {
1260 let file_path = files.choose(rng);
1261 let dir_path = dirs[1..].choose(rng);
1262 file_path.into_iter().chain(dir_path).choose(rng).unwrap()
1263 };
1264
1265 let is_rename = rng.gen();
1266 if is_rename {
1267 let new_path_parent = dirs
1268 .iter()
1269 .filter(|d| !d.starts_with(old_path))
1270 .choose(rng)
1271 .unwrap();
1272 let new_path = new_path_parent.join(gen_name(rng));
1273
1274 log::info!(
1275 "Renaming {:?} to {:?}",
1276 old_path.strip_prefix(&root_path)?,
1277 new_path.strip_prefix(&root_path)?
1278 );
1279 fs::rename(&old_path, &new_path)?;
1280 record_event(old_path.clone());
1281 record_event(new_path);
1282 } else if old_path.is_dir() {
1283 let (dirs, files) = read_dir_recursive(old_path.clone());
1284
1285 log::info!("Deleting dir {:?}", old_path.strip_prefix(&root_path)?);
1286 fs::remove_dir_all(&old_path).unwrap();
1287 for file in files {
1288 record_event(file);
1289 }
1290 for dir in dirs {
1291 record_event(dir);
1292 }
1293 } else {
1294 log::info!("Deleting file {:?}", old_path.strip_prefix(&root_path)?);
1295 fs::remove_file(old_path).unwrap();
1296 record_event(old_path.clone());
1297 }
1298 }
1299
1300 Ok(events)
1301 }
1302
1303 fn read_dir_recursive(path: PathBuf) -> (Vec<PathBuf>, Vec<PathBuf>) {
1304 let child_entries = fs::read_dir(&path).unwrap();
1305 let mut dirs = vec![path];
1306 let mut files = Vec::new();
1307 for child_entry in child_entries {
1308 let child_path = child_entry.unwrap().path();
1309 if child_path.is_dir() {
1310 let (child_dirs, child_files) = read_dir_recursive(child_path);
1311 dirs.extend(child_dirs);
1312 files.extend(child_files);
1313 } else {
1314 files.push(child_path);
1315 }
1316 }
1317 (dirs, files)
1318 }
1319
1320 fn gen_name(rng: &mut impl Rng) -> String {
1321 (0..6)
1322 .map(|_| rng.sample(rand::distributions::Alphanumeric))
1323 .map(char::from)
1324 .collect()
1325 }
1326
1327 impl Snapshot {
1328 fn to_vec(&self) -> Vec<(PathBuf, u64)> {
1329 use std::iter::FromIterator;
1330
1331 let mut paths = Vec::new();
1332
1333 let mut stack = Vec::new();
1334 stack.extend(self.root_inode);
1335 while let Some(inode) = stack.pop() {
1336 let computed_path = self.path_for_inode(inode, true).unwrap();
1337 match self.entries.get(&inode).unwrap() {
1338 Entry::Dir { children, .. } => {
1339 stack.extend_from_slice(children);
1340 }
1341 Entry::File { path, .. } => {
1342 assert_eq!(
1343 String::from_iter(path.path.iter()),
1344 computed_path.to_str().unwrap()
1345 );
1346 }
1347 }
1348 paths.push((computed_path, inode));
1349 }
1350
1351 paths.sort_by(|a, b| a.0.cmp(&b.0));
1352 paths
1353 }
1354 }
1355}