1use globset::{Glob, GlobSet, GlobSetBuilder};
2use regex::Regex;
3use serde::{Deserialize, Serialize};
4use std::cmp::Ordering;
5use std::fmt::{Display, Formatter};
6use std::mem;
7use std::path::StripPrefixError;
8use std::sync::{Arc, OnceLock};
9use std::{
10 ffi::OsStr,
11 path::{Path, PathBuf},
12 sync::LazyLock,
13};
14
15use crate::rel_path::RelPath;
16
17static HOME_DIR: OnceLock<PathBuf> = OnceLock::new();
18
19/// Returns the path to the user's home directory.
20pub fn home_dir() -> &'static PathBuf {
21 HOME_DIR.get_or_init(|| {
22 if cfg!(any(test, feature = "test-support")) {
23 if cfg!(target_os = "macos") {
24 PathBuf::from("/Users/zed")
25 } else if cfg!(target_os = "windows") {
26 PathBuf::from("C:\\Users\\zed")
27 } else {
28 PathBuf::from("/home/zed")
29 }
30 } else {
31 dirs::home_dir().expect("failed to determine home directory")
32 }
33 })
34}
35
36pub trait PathExt {
37 fn compact(&self) -> PathBuf;
38 fn extension_or_hidden_file_name(&self) -> Option<&str>;
39 fn try_from_bytes<'a>(bytes: &'a [u8]) -> anyhow::Result<Self>
40 where
41 Self: From<&'a Path>,
42 {
43 #[cfg(unix)]
44 {
45 use std::os::unix::prelude::OsStrExt;
46 Ok(Self::from(Path::new(OsStr::from_bytes(bytes))))
47 }
48 #[cfg(windows)]
49 {
50 use anyhow::Context as _;
51 use tendril::fmt::{Format, WTF8};
52 WTF8::validate(bytes)
53 .then(|| {
54 // Safety: bytes are valid WTF-8 sequence.
55 Self::from(Path::new(unsafe {
56 OsStr::from_encoded_bytes_unchecked(bytes)
57 }))
58 })
59 .with_context(|| format!("Invalid WTF-8 sequence: {bytes:?}"))
60 }
61 }
62 fn local_to_wsl(&self) -> Option<PathBuf>;
63}
64
65impl<T: AsRef<Path>> PathExt for T {
66 /// Compacts a given file path by replacing the user's home directory
67 /// prefix with a tilde (`~`).
68 ///
69 /// # Returns
70 ///
71 /// * A `PathBuf` containing the compacted file path. If the input path
72 /// does not have the user's home directory prefix, or if we are not on
73 /// Linux or macOS, the original path is returned unchanged.
74 fn compact(&self) -> PathBuf {
75 if cfg!(any(target_os = "linux", target_os = "freebsd")) || cfg!(target_os = "macos") {
76 match self.as_ref().strip_prefix(home_dir().as_path()) {
77 Ok(relative_path) => {
78 let mut shortened_path = PathBuf::new();
79 shortened_path.push("~");
80 shortened_path.push(relative_path);
81 shortened_path
82 }
83 Err(_) => self.as_ref().to_path_buf(),
84 }
85 } else {
86 self.as_ref().to_path_buf()
87 }
88 }
89
90 /// Returns a file's extension or, if the file is hidden, its name without the leading dot
91 fn extension_or_hidden_file_name(&self) -> Option<&str> {
92 let path = self.as_ref();
93 let file_name = path.file_name()?.to_str()?;
94 if file_name.starts_with('.') {
95 return file_name.strip_prefix('.');
96 }
97
98 path.extension()
99 .and_then(|e| e.to_str())
100 .or_else(|| path.file_stem()?.to_str())
101 }
102
103 /// Converts a local path to one that can be used inside of WSL.
104 /// Returns `None` if the path cannot be converted into a WSL one (network share).
105 fn local_to_wsl(&self) -> Option<PathBuf> {
106 // quite sketchy to convert this back to path at the end, but a lot of functions only accept paths
107 // todo: ideally rework them..?
108 let mut new_path = std::ffi::OsString::new();
109 for component in self.as_ref().components() {
110 match component {
111 std::path::Component::Prefix(prefix) => {
112 let drive_letter = prefix.as_os_str().to_string_lossy().to_lowercase();
113 let drive_letter = drive_letter.strip_suffix(':')?;
114
115 new_path.push(format!("/mnt/{}", drive_letter));
116 }
117 std::path::Component::RootDir => {}
118 std::path::Component::CurDir => {
119 new_path.push("/.");
120 }
121 std::path::Component::ParentDir => {
122 new_path.push("/..");
123 }
124 std::path::Component::Normal(os_str) => {
125 new_path.push("/");
126 new_path.push(os_str);
127 }
128 }
129 }
130
131 Some(new_path.into())
132 }
133}
134
135/// In memory, this is identical to `Path`. On non-Windows conversions to this type are no-ops. On
136/// windows, these conversions sanitize UNC paths by removing the `\\\\?\\` prefix.
137#[derive(Eq, PartialEq, Hash, Ord, PartialOrd)]
138#[repr(transparent)]
139pub struct SanitizedPath(Path);
140
141impl SanitizedPath {
142 pub fn new<T: AsRef<Path> + ?Sized>(path: &T) -> &Self {
143 #[cfg(not(target_os = "windows"))]
144 return Self::unchecked_new(path.as_ref());
145
146 #[cfg(target_os = "windows")]
147 return Self::unchecked_new(dunce::simplified(path.as_ref()));
148 }
149
150 pub fn unchecked_new<T: AsRef<Path> + ?Sized>(path: &T) -> &Self {
151 // safe because `Path` and `SanitizedPath` have the same repr and Drop impl
152 unsafe { mem::transmute::<&Path, &Self>(path.as_ref()) }
153 }
154
155 pub fn from_arc(path: Arc<Path>) -> Arc<Self> {
156 // safe because `Path` and `SanitizedPath` have the same repr and Drop impl
157 #[cfg(not(target_os = "windows"))]
158 return unsafe { mem::transmute::<Arc<Path>, Arc<Self>>(path) };
159
160 // TODO: could avoid allocating here if dunce::simplified results in the same path
161 #[cfg(target_os = "windows")]
162 return Self::new(&path).into();
163 }
164
165 pub fn new_arc<T: AsRef<Path> + ?Sized>(path: &T) -> Arc<Self> {
166 Self::new(path).into()
167 }
168
169 pub fn cast_arc(path: Arc<Self>) -> Arc<Path> {
170 // safe because `Path` and `SanitizedPath` have the same repr and Drop impl
171 unsafe { mem::transmute::<Arc<Self>, Arc<Path>>(path) }
172 }
173
174 pub fn cast_arc_ref(path: &Arc<Self>) -> &Arc<Path> {
175 // safe because `Path` and `SanitizedPath` have the same repr and Drop impl
176 unsafe { mem::transmute::<&Arc<Self>, &Arc<Path>>(path) }
177 }
178
179 pub fn starts_with(&self, prefix: &Self) -> bool {
180 self.0.starts_with(&prefix.0)
181 }
182
183 pub fn as_path(&self) -> &Path {
184 &self.0
185 }
186
187 pub fn file_name(&self) -> Option<&std::ffi::OsStr> {
188 self.0.file_name()
189 }
190
191 pub fn extension(&self) -> Option<&std::ffi::OsStr> {
192 self.0.extension()
193 }
194
195 pub fn join<P: AsRef<Path>>(&self, path: P) -> PathBuf {
196 self.0.join(path)
197 }
198
199 pub fn parent(&self) -> Option<&Self> {
200 self.0.parent().map(Self::unchecked_new)
201 }
202
203 pub fn strip_prefix(&self, base: &Self) -> Result<&Path, StripPrefixError> {
204 self.0.strip_prefix(base.as_path())
205 }
206
207 pub fn to_str(&self) -> Option<&str> {
208 self.0.to_str()
209 }
210
211 pub fn to_path_buf(&self) -> PathBuf {
212 self.0.to_path_buf()
213 }
214}
215
216impl std::fmt::Debug for SanitizedPath {
217 fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
218 std::fmt::Debug::fmt(&self.0, formatter)
219 }
220}
221
222impl Display for SanitizedPath {
223 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
224 write!(f, "{}", self.0.display())
225 }
226}
227
228impl From<&SanitizedPath> for Arc<SanitizedPath> {
229 fn from(sanitized_path: &SanitizedPath) -> Self {
230 let path: Arc<Path> = sanitized_path.0.into();
231 // safe because `Path` and `SanitizedPath` have the same repr and Drop impl
232 unsafe { mem::transmute(path) }
233 }
234}
235
236impl From<&SanitizedPath> for PathBuf {
237 fn from(sanitized_path: &SanitizedPath) -> Self {
238 sanitized_path.as_path().into()
239 }
240}
241
242impl AsRef<Path> for SanitizedPath {
243 fn as_ref(&self) -> &Path {
244 &self.0
245 }
246}
247
248#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
249pub enum PathStyle {
250 Posix,
251 Windows,
252}
253
254impl PathStyle {
255 #[cfg(target_os = "windows")]
256 pub const fn local() -> Self {
257 PathStyle::Windows
258 }
259
260 #[cfg(not(target_os = "windows"))]
261 pub const fn local() -> Self {
262 PathStyle::Posix
263 }
264
265 #[inline]
266 pub fn separator(&self) -> &'static str {
267 match self {
268 PathStyle::Posix => "/",
269 PathStyle::Windows => "\\",
270 }
271 }
272
273 pub fn is_windows(&self) -> bool {
274 *self == PathStyle::Windows
275 }
276
277 pub fn join(self, left: impl AsRef<Path>, right: impl AsRef<Path>) -> Option<String> {
278 let right = right.as_ref().to_str()?;
279 if is_absolute(right, self) {
280 return None;
281 }
282 let left = left.as_ref().to_str()?;
283 if left.is_empty() {
284 Some(right.into())
285 } else {
286 Some(format!(
287 "{left}{}{right}",
288 if left.ends_with(self.separator()) {
289 ""
290 } else {
291 self.separator()
292 }
293 ))
294 }
295 }
296
297 pub fn split(self, path_like: &str) -> (Option<&str>, &str) {
298 let Some(pos) = path_like.rfind(self.separator()) else {
299 return (None, path_like);
300 };
301 let filename_start = pos + self.separator().len();
302 (
303 Some(&path_like[..filename_start]),
304 &path_like[filename_start..],
305 )
306 }
307}
308
309#[derive(Debug, Clone)]
310pub struct RemotePathBuf {
311 style: PathStyle,
312 string: String,
313}
314
315impl RemotePathBuf {
316 pub fn new(string: String, style: PathStyle) -> Self {
317 Self { style, string }
318 }
319
320 pub fn from_str(path: &str, style: PathStyle) -> Self {
321 Self::new(path.to_string(), style)
322 }
323
324 pub fn path_style(&self) -> PathStyle {
325 self.style
326 }
327
328 pub fn to_proto(self) -> String {
329 self.string
330 }
331}
332
333impl Display for RemotePathBuf {
334 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
335 write!(f, "{}", self.string)
336 }
337}
338
339pub fn is_absolute(path_like: &str, path_style: PathStyle) -> bool {
340 path_like.starts_with('/')
341 || path_style == PathStyle::Windows
342 && (path_like.starts_with('\\')
343 || path_like
344 .chars()
345 .next()
346 .is_some_and(|c| c.is_ascii_alphabetic())
347 && path_like[1..]
348 .strip_prefix(':')
349 .is_some_and(|path| path.starts_with('/') || path.starts_with('\\')))
350}
351
352/// A delimiter to use in `path_query:row_number:column_number` strings parsing.
353pub const FILE_ROW_COLUMN_DELIMITER: char = ':';
354
355const ROW_COL_CAPTURE_REGEX: &str = r"(?xs)
356 ([^\(]+)\:(?:
357 \((\d+)[,:](\d+)\) # filename:(row,column), filename:(row:column)
358 |
359 \((\d+)\)() # filename:(row)
360 )
361 |
362 ([^\(]+)(?:
363 \((\d+)[,:](\d+)\) # filename(row,column), filename(row:column)
364 |
365 \((\d+)\)() # filename(row)
366 )
367 |
368 (.+?)(?:
369 \:+(\d+)\:(\d+)\:*$ # filename:row:column
370 |
371 \:+(\d+)\:*()$ # filename:row
372 |
373 \:+()()$
374 )";
375
376/// A representation of a path-like string with optional row and column numbers.
377/// Matching values example: `te`, `test.rs:22`, `te:22:5`, `test.c(22)`, `test.c(22,5)`etc.
378#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
379pub struct PathWithPosition {
380 pub path: PathBuf,
381 pub row: Option<u32>,
382 // Absent if row is absent.
383 pub column: Option<u32>,
384}
385
386impl PathWithPosition {
387 /// Returns a PathWithPosition from a path.
388 pub fn from_path(path: PathBuf) -> Self {
389 Self {
390 path,
391 row: None,
392 column: None,
393 }
394 }
395
396 /// Parses a string that possibly has `:row:column` or `(row, column)` suffix.
397 /// Parenthesis format is used by [MSBuild](https://learn.microsoft.com/en-us/visualstudio/msbuild/msbuild-diagnostic-format-for-tasks) compatible tools
398 /// Ignores trailing `:`s, so `test.rs:22:` is parsed as `test.rs:22`.
399 /// If the suffix parsing fails, the whole string is parsed as a path.
400 ///
401 /// Be mindful that `test_file:10:1:` is a valid posix filename.
402 /// `PathWithPosition` class assumes that the ending position-like suffix is **not** part of the filename.
403 ///
404 /// # Examples
405 ///
406 /// ```
407 /// # use util::paths::PathWithPosition;
408 /// # use std::path::PathBuf;
409 /// assert_eq!(PathWithPosition::parse_str("test_file"), PathWithPosition {
410 /// path: PathBuf::from("test_file"),
411 /// row: None,
412 /// column: None,
413 /// });
414 /// assert_eq!(PathWithPosition::parse_str("test_file:10"), PathWithPosition {
415 /// path: PathBuf::from("test_file"),
416 /// row: Some(10),
417 /// column: None,
418 /// });
419 /// assert_eq!(PathWithPosition::parse_str("test_file.rs"), PathWithPosition {
420 /// path: PathBuf::from("test_file.rs"),
421 /// row: None,
422 /// column: None,
423 /// });
424 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:1"), PathWithPosition {
425 /// path: PathBuf::from("test_file.rs"),
426 /// row: Some(1),
427 /// column: None,
428 /// });
429 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:1:2"), PathWithPosition {
430 /// path: PathBuf::from("test_file.rs"),
431 /// row: Some(1),
432 /// column: Some(2),
433 /// });
434 /// ```
435 ///
436 /// # Expected parsing results when encounter ill-formatted inputs.
437 /// ```
438 /// # use util::paths::PathWithPosition;
439 /// # use std::path::PathBuf;
440 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:a"), PathWithPosition {
441 /// path: PathBuf::from("test_file.rs:a"),
442 /// row: None,
443 /// column: None,
444 /// });
445 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:a:b"), PathWithPosition {
446 /// path: PathBuf::from("test_file.rs:a:b"),
447 /// row: None,
448 /// column: None,
449 /// });
450 /// assert_eq!(PathWithPosition::parse_str("test_file.rs"), PathWithPosition {
451 /// path: PathBuf::from("test_file.rs"),
452 /// row: None,
453 /// column: None,
454 /// });
455 /// assert_eq!(PathWithPosition::parse_str("test_file.rs::1"), PathWithPosition {
456 /// path: PathBuf::from("test_file.rs"),
457 /// row: Some(1),
458 /// column: None,
459 /// });
460 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:1::"), PathWithPosition {
461 /// path: PathBuf::from("test_file.rs"),
462 /// row: Some(1),
463 /// column: None,
464 /// });
465 /// assert_eq!(PathWithPosition::parse_str("test_file.rs::1:2"), PathWithPosition {
466 /// path: PathBuf::from("test_file.rs"),
467 /// row: Some(1),
468 /// column: Some(2),
469 /// });
470 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:1::2"), PathWithPosition {
471 /// path: PathBuf::from("test_file.rs:1"),
472 /// row: Some(2),
473 /// column: None,
474 /// });
475 /// assert_eq!(PathWithPosition::parse_str("test_file.rs:1:2:3"), PathWithPosition {
476 /// path: PathBuf::from("test_file.rs:1"),
477 /// row: Some(2),
478 /// column: Some(3),
479 /// });
480 /// ```
481 pub fn parse_str(s: &str) -> Self {
482 let trimmed = s.trim();
483 let path = Path::new(trimmed);
484 let maybe_file_name_with_row_col = path.file_name().unwrap_or_default().to_string_lossy();
485 if maybe_file_name_with_row_col.is_empty() {
486 return Self {
487 path: Path::new(s).to_path_buf(),
488 row: None,
489 column: None,
490 };
491 }
492
493 // Let's avoid repeated init cost on this. It is subject to thread contention, but
494 // so far this code isn't called from multiple hot paths. Getting contention here
495 // in the future seems unlikely.
496 static SUFFIX_RE: LazyLock<Regex> =
497 LazyLock::new(|| Regex::new(ROW_COL_CAPTURE_REGEX).unwrap());
498 match SUFFIX_RE
499 .captures(&maybe_file_name_with_row_col)
500 .map(|caps| caps.extract())
501 {
502 Some((_, [file_name, maybe_row, maybe_column])) => {
503 let row = maybe_row.parse::<u32>().ok();
504 let column = maybe_column.parse::<u32>().ok();
505
506 let suffix_length = maybe_file_name_with_row_col.len() - file_name.len();
507 let path_without_suffix = &trimmed[..trimmed.len() - suffix_length];
508
509 Self {
510 path: Path::new(path_without_suffix).to_path_buf(),
511 row,
512 column,
513 }
514 }
515 None => {
516 // The `ROW_COL_CAPTURE_REGEX` deals with separated digits only,
517 // but in reality there could be `foo/bar.py:22:in` inputs which we want to match too.
518 // The regex mentioned is not very extendable with "digit or random string" checks, so do this here instead.
519 let delimiter = ':';
520 let mut path_parts = s
521 .rsplitn(3, delimiter)
522 .collect::<Vec<_>>()
523 .into_iter()
524 .rev()
525 .fuse();
526 let mut path_string = path_parts.next().expect("rsplitn should have the rest of the string as its last parameter that we reversed").to_owned();
527 let mut row = None;
528 let mut column = None;
529 if let Some(maybe_row) = path_parts.next() {
530 if let Ok(parsed_row) = maybe_row.parse::<u32>() {
531 row = Some(parsed_row);
532 if let Some(parsed_column) = path_parts
533 .next()
534 .and_then(|maybe_col| maybe_col.parse::<u32>().ok())
535 {
536 column = Some(parsed_column);
537 }
538 } else {
539 path_string.push(delimiter);
540 path_string.push_str(maybe_row);
541 }
542 }
543 for split in path_parts {
544 path_string.push(delimiter);
545 path_string.push_str(split);
546 }
547
548 Self {
549 path: PathBuf::from(path_string),
550 row,
551 column,
552 }
553 }
554 }
555 }
556
557 pub fn map_path<E>(
558 self,
559 mapping: impl FnOnce(PathBuf) -> Result<PathBuf, E>,
560 ) -> Result<PathWithPosition, E> {
561 Ok(PathWithPosition {
562 path: mapping(self.path)?,
563 row: self.row,
564 column: self.column,
565 })
566 }
567
568 pub fn to_string(&self, path_to_string: impl Fn(&PathBuf) -> String) -> String {
569 let path_string = path_to_string(&self.path);
570 if let Some(row) = self.row {
571 if let Some(column) = self.column {
572 format!("{path_string}:{row}:{column}")
573 } else {
574 format!("{path_string}:{row}")
575 }
576 } else {
577 path_string
578 }
579 }
580}
581
582#[derive(Clone, Debug)]
583pub struct PathMatcher {
584 sources: Vec<String>,
585 glob: GlobSet,
586 path_style: PathStyle,
587}
588
589// impl std::fmt::Display for PathMatcher {
590// fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
591// self.sources.fmt(f)
592// }
593// }
594
595impl PartialEq for PathMatcher {
596 fn eq(&self, other: &Self) -> bool {
597 self.sources.eq(&other.sources)
598 }
599}
600
601impl Eq for PathMatcher {}
602
603impl PathMatcher {
604 pub fn new(
605 globs: impl IntoIterator<Item = impl AsRef<str>>,
606 path_style: PathStyle,
607 ) -> Result<Self, globset::Error> {
608 let globs = globs
609 .into_iter()
610 .map(|as_str| Glob::new(as_str.as_ref()))
611 .collect::<Result<Vec<_>, _>>()?;
612 let sources = globs.iter().map(|glob| glob.glob().to_owned()).collect();
613 let mut glob_builder = GlobSetBuilder::new();
614 for single_glob in globs {
615 glob_builder.add(single_glob);
616 }
617 let glob = glob_builder.build()?;
618 Ok(PathMatcher {
619 glob,
620 sources,
621 path_style,
622 })
623 }
624
625 pub fn sources(&self) -> &[String] {
626 &self.sources
627 }
628
629 pub fn is_match<P: AsRef<Path>>(&self, other: P) -> bool {
630 let other_path = other.as_ref();
631 self.sources.iter().any(|source| {
632 let as_bytes = other_path.as_os_str().as_encoded_bytes();
633 as_bytes.starts_with(source.as_bytes()) || as_bytes.ends_with(source.as_bytes())
634 }) || self.glob.is_match(other_path)
635 || self.check_with_end_separator(other_path)
636 }
637
638 fn check_with_end_separator(&self, path: &Path) -> bool {
639 let path_str = path.to_string_lossy();
640 let separator = self.path_style.separator();
641 if path_str.ends_with(separator) {
642 false
643 } else {
644 self.glob.is_match(path_str.to_string() + separator)
645 }
646 }
647}
648
649impl Default for PathMatcher {
650 fn default() -> Self {
651 Self {
652 path_style: PathStyle::local(),
653 glob: GlobSet::empty(),
654 sources: vec![],
655 }
656 }
657}
658
659/// Custom character comparison that prioritizes lowercase for same letters
660fn compare_chars(a: char, b: char) -> Ordering {
661 // First compare case-insensitive
662 match a.to_ascii_lowercase().cmp(&b.to_ascii_lowercase()) {
663 Ordering::Equal => {
664 // If same letter, prioritize lowercase (lowercase < uppercase)
665 match (a.is_ascii_lowercase(), b.is_ascii_lowercase()) {
666 (true, false) => Ordering::Less, // lowercase comes first
667 (false, true) => Ordering::Greater, // uppercase comes after
668 _ => Ordering::Equal, // both same case or both non-ascii
669 }
670 }
671 other => other,
672 }
673}
674
675/// Compares two sequences of consecutive digits for natural sorting.
676///
677/// This function is a core component of natural sorting that handles numeric comparison
678/// in a way that feels natural to humans. It extracts and compares consecutive digit
679/// sequences from two iterators, handling various cases like leading zeros and very large numbers.
680///
681/// # Behavior
682///
683/// The function implements the following comparison rules:
684/// 1. Different numeric values: Compares by actual numeric value (e.g., "2" < "10")
685/// 2. Leading zeros: When values are equal, longer sequence wins (e.g., "002" > "2")
686/// 3. Large numbers: Falls back to string comparison for numbers that would overflow u128
687///
688/// # Examples
689///
690/// ```text
691/// "1" vs "2" -> Less (different values)
692/// "2" vs "10" -> Less (numeric comparison)
693/// "002" vs "2" -> Greater (leading zeros)
694/// "10" vs "010" -> Less (leading zeros)
695/// "999..." vs "1000..." -> Less (large number comparison)
696/// ```
697///
698/// # Implementation Details
699///
700/// 1. Extracts consecutive digits into strings
701/// 2. Compares sequence lengths for leading zero handling
702/// 3. For equal lengths, compares digit by digit
703/// 4. For different lengths:
704/// - Attempts numeric comparison first (for numbers up to 2^128 - 1)
705/// - Falls back to string comparison if numbers would overflow
706///
707/// The function advances both iterators past their respective numeric sequences,
708/// regardless of the comparison result.
709fn compare_numeric_segments<I>(
710 a_iter: &mut std::iter::Peekable<I>,
711 b_iter: &mut std::iter::Peekable<I>,
712) -> Ordering
713where
714 I: Iterator<Item = char>,
715{
716 // Collect all consecutive digits into strings
717 let mut a_num_str = String::new();
718 let mut b_num_str = String::new();
719
720 while let Some(&c) = a_iter.peek() {
721 if !c.is_ascii_digit() {
722 break;
723 }
724
725 a_num_str.push(c);
726 a_iter.next();
727 }
728
729 while let Some(&c) = b_iter.peek() {
730 if !c.is_ascii_digit() {
731 break;
732 }
733
734 b_num_str.push(c);
735 b_iter.next();
736 }
737
738 // First compare lengths (handle leading zeros)
739 match a_num_str.len().cmp(&b_num_str.len()) {
740 Ordering::Equal => {
741 // Same length, compare digit by digit
742 match a_num_str.cmp(&b_num_str) {
743 Ordering::Equal => Ordering::Equal,
744 ordering => ordering,
745 }
746 }
747
748 // Different lengths but same value means leading zeros
749 ordering => {
750 // Try parsing as numbers first
751 if let (Ok(a_val), Ok(b_val)) = (a_num_str.parse::<u128>(), b_num_str.parse::<u128>()) {
752 match a_val.cmp(&b_val) {
753 Ordering::Equal => ordering, // Same value, longer one is greater (leading zeros)
754 ord => ord,
755 }
756 } else {
757 // If parsing fails (overflow), compare as strings
758 a_num_str.cmp(&b_num_str)
759 }
760 }
761 }
762}
763
764/// Performs natural sorting comparison between two strings.
765///
766/// Natural sorting is an ordering that handles numeric sequences in a way that matches human expectations.
767/// For example, "file2" comes before "file10" (unlike standard lexicographic sorting).
768///
769/// # Characteristics
770///
771/// * Case-sensitive with lowercase priority: When comparing same letters, lowercase comes before uppercase
772/// * Numbers are compared by numeric value, not character by character
773/// * Leading zeros affect ordering when numeric values are equal
774/// * Can handle numbers larger than u128::MAX (falls back to string comparison)
775///
776/// # Algorithm
777///
778/// The function works by:
779/// 1. Processing strings character by character
780/// 2. When encountering digits, treating consecutive digits as a single number
781/// 3. Comparing numbers by their numeric value rather than lexicographically
782/// 4. For non-numeric characters, using case-sensitive comparison with lowercase priority
783fn natural_sort(a: &str, b: &str) -> Ordering {
784 let mut a_iter = a.chars().peekable();
785 let mut b_iter = b.chars().peekable();
786
787 loop {
788 match (a_iter.peek(), b_iter.peek()) {
789 (None, None) => return Ordering::Equal,
790 (None, _) => return Ordering::Less,
791 (_, None) => return Ordering::Greater,
792 (Some(&a_char), Some(&b_char)) => {
793 if a_char.is_ascii_digit() && b_char.is_ascii_digit() {
794 match compare_numeric_segments(&mut a_iter, &mut b_iter) {
795 Ordering::Equal => continue,
796 ordering => return ordering,
797 }
798 } else {
799 match compare_chars(a_char, b_char) {
800 Ordering::Equal => {
801 a_iter.next();
802 b_iter.next();
803 }
804 ordering => return ordering,
805 }
806 }
807 }
808 }
809 }
810}
811pub fn compare_rel_paths(
812 (path_a, a_is_file): (&RelPath, bool),
813 (path_b, b_is_file): (&RelPath, bool),
814) -> Ordering {
815 let mut components_a = path_a.components();
816 let mut components_b = path_b.components();
817
818 fn stem_and_extension(filename: &str) -> (Option<&str>, Option<&str>) {
819 if filename.is_empty() {
820 return (None, None);
821 }
822
823 match filename.rsplit_once('.') {
824 // Case 1: No dot was found. The entire name is the stem.
825 None => (Some(filename), None),
826
827 // Case 2: A dot was found.
828 Some((before, after)) => {
829 // This is the crucial check for dotfiles like ".bashrc".
830 // If `before` is empty, the dot was the first character.
831 // In that case, we revert to the "whole name is the stem" logic.
832 if before.is_empty() {
833 (Some(filename), None)
834 } else {
835 // Otherwise, we have a standard stem and extension.
836 (Some(before), Some(after))
837 }
838 }
839 }
840 }
841 loop {
842 match (components_a.next(), components_b.next()) {
843 (Some(component_a), Some(component_b)) => {
844 let a_is_file = a_is_file && components_a.rest().is_empty();
845 let b_is_file = b_is_file && components_b.rest().is_empty();
846
847 let ordering = a_is_file.cmp(&b_is_file).then_with(|| {
848 let (a_stem, a_extension) = a_is_file
849 .then(|| stem_and_extension(component_a))
850 .unwrap_or_default();
851 let path_string_a = if a_is_file { a_stem } else { Some(component_a) };
852
853 let (b_stem, b_extension) = b_is_file
854 .then(|| stem_and_extension(component_b))
855 .unwrap_or_default();
856 let path_string_b = if b_is_file { b_stem } else { Some(component_b) };
857
858 let compare_components = match (path_string_a, path_string_b) {
859 (Some(a), Some(b)) => natural_sort(&a, &b),
860 (Some(_), None) => Ordering::Greater,
861 (None, Some(_)) => Ordering::Less,
862 (None, None) => Ordering::Equal,
863 };
864
865 compare_components.then_with(|| {
866 if a_is_file && b_is_file {
867 let ext_a = a_extension.unwrap_or_default();
868 let ext_b = b_extension.unwrap_or_default();
869 ext_a.cmp(ext_b)
870 } else {
871 Ordering::Equal
872 }
873 })
874 });
875
876 if !ordering.is_eq() {
877 return ordering;
878 }
879 }
880 (Some(_), None) => break Ordering::Greater,
881 (None, Some(_)) => break Ordering::Less,
882 (None, None) => break Ordering::Equal,
883 }
884 }
885}
886
887pub fn compare_paths(
888 (path_a, a_is_file): (&Path, bool),
889 (path_b, b_is_file): (&Path, bool),
890) -> Ordering {
891 let mut components_a = path_a.components().peekable();
892 let mut components_b = path_b.components().peekable();
893
894 loop {
895 match (components_a.next(), components_b.next()) {
896 (Some(component_a), Some(component_b)) => {
897 let a_is_file = components_a.peek().is_none() && a_is_file;
898 let b_is_file = components_b.peek().is_none() && b_is_file;
899
900 let ordering = a_is_file.cmp(&b_is_file).then_with(|| {
901 let path_a = Path::new(component_a.as_os_str());
902 let path_string_a = if a_is_file {
903 path_a.file_stem()
904 } else {
905 path_a.file_name()
906 }
907 .map(|s| s.to_string_lossy());
908
909 let path_b = Path::new(component_b.as_os_str());
910 let path_string_b = if b_is_file {
911 path_b.file_stem()
912 } else {
913 path_b.file_name()
914 }
915 .map(|s| s.to_string_lossy());
916
917 let compare_components = match (path_string_a, path_string_b) {
918 (Some(a), Some(b)) => natural_sort(&a, &b),
919 (Some(_), None) => Ordering::Greater,
920 (None, Some(_)) => Ordering::Less,
921 (None, None) => Ordering::Equal,
922 };
923
924 compare_components.then_with(|| {
925 if a_is_file && b_is_file {
926 let ext_a = path_a.extension().unwrap_or_default();
927 let ext_b = path_b.extension().unwrap_or_default();
928 ext_a.cmp(ext_b)
929 } else {
930 Ordering::Equal
931 }
932 })
933 });
934
935 if !ordering.is_eq() {
936 return ordering;
937 }
938 }
939 (Some(_), None) => break Ordering::Greater,
940 (None, Some(_)) => break Ordering::Less,
941 (None, None) => break Ordering::Equal,
942 }
943 }
944}
945
946#[cfg(test)]
947mod tests {
948 use super::*;
949 use util_macros::perf;
950
951 #[perf]
952 fn compare_paths_with_dots() {
953 let mut paths = vec![
954 (Path::new("test_dirs"), false),
955 (Path::new("test_dirs/1.46"), false),
956 (Path::new("test_dirs/1.46/bar_1"), true),
957 (Path::new("test_dirs/1.46/bar_2"), true),
958 (Path::new("test_dirs/1.45"), false),
959 (Path::new("test_dirs/1.45/foo_2"), true),
960 (Path::new("test_dirs/1.45/foo_1"), true),
961 ];
962 paths.sort_by(|&a, &b| compare_paths(a, b));
963 assert_eq!(
964 paths,
965 vec![
966 (Path::new("test_dirs"), false),
967 (Path::new("test_dirs/1.45"), false),
968 (Path::new("test_dirs/1.45/foo_1"), true),
969 (Path::new("test_dirs/1.45/foo_2"), true),
970 (Path::new("test_dirs/1.46"), false),
971 (Path::new("test_dirs/1.46/bar_1"), true),
972 (Path::new("test_dirs/1.46/bar_2"), true),
973 ]
974 );
975 let mut paths = vec![
976 (Path::new("root1/one.txt"), true),
977 (Path::new("root1/one.two.txt"), true),
978 ];
979 paths.sort_by(|&a, &b| compare_paths(a, b));
980 assert_eq!(
981 paths,
982 vec![
983 (Path::new("root1/one.txt"), true),
984 (Path::new("root1/one.two.txt"), true),
985 ]
986 );
987 }
988
989 #[perf]
990 fn compare_paths_with_same_name_different_extensions() {
991 let mut paths = vec![
992 (Path::new("test_dirs/file.rs"), true),
993 (Path::new("test_dirs/file.txt"), true),
994 (Path::new("test_dirs/file.md"), true),
995 (Path::new("test_dirs/file"), true),
996 (Path::new("test_dirs/file.a"), true),
997 ];
998 paths.sort_by(|&a, &b| compare_paths(a, b));
999 assert_eq!(
1000 paths,
1001 vec![
1002 (Path::new("test_dirs/file"), true),
1003 (Path::new("test_dirs/file.a"), true),
1004 (Path::new("test_dirs/file.md"), true),
1005 (Path::new("test_dirs/file.rs"), true),
1006 (Path::new("test_dirs/file.txt"), true),
1007 ]
1008 );
1009 }
1010
1011 #[perf]
1012 fn compare_paths_case_semi_sensitive() {
1013 let mut paths = vec![
1014 (Path::new("test_DIRS"), false),
1015 (Path::new("test_DIRS/foo_1"), true),
1016 (Path::new("test_DIRS/foo_2"), true),
1017 (Path::new("test_DIRS/bar"), true),
1018 (Path::new("test_DIRS/BAR"), true),
1019 (Path::new("test_dirs"), false),
1020 (Path::new("test_dirs/foo_1"), true),
1021 (Path::new("test_dirs/foo_2"), true),
1022 (Path::new("test_dirs/bar"), true),
1023 (Path::new("test_dirs/BAR"), true),
1024 ];
1025 paths.sort_by(|&a, &b| compare_paths(a, b));
1026 assert_eq!(
1027 paths,
1028 vec![
1029 (Path::new("test_dirs"), false),
1030 (Path::new("test_dirs/bar"), true),
1031 (Path::new("test_dirs/BAR"), true),
1032 (Path::new("test_dirs/foo_1"), true),
1033 (Path::new("test_dirs/foo_2"), true),
1034 (Path::new("test_DIRS"), false),
1035 (Path::new("test_DIRS/bar"), true),
1036 (Path::new("test_DIRS/BAR"), true),
1037 (Path::new("test_DIRS/foo_1"), true),
1038 (Path::new("test_DIRS/foo_2"), true),
1039 ]
1040 );
1041 }
1042
1043 #[perf]
1044 fn path_with_position_parse_posix_path() {
1045 // Test POSIX filename edge cases
1046 // Read more at https://en.wikipedia.org/wiki/Filename
1047 assert_eq!(
1048 PathWithPosition::parse_str("test_file"),
1049 PathWithPosition {
1050 path: PathBuf::from("test_file"),
1051 row: None,
1052 column: None
1053 }
1054 );
1055
1056 assert_eq!(
1057 PathWithPosition::parse_str("a:bc:.zip:1"),
1058 PathWithPosition {
1059 path: PathBuf::from("a:bc:.zip"),
1060 row: Some(1),
1061 column: None
1062 }
1063 );
1064
1065 assert_eq!(
1066 PathWithPosition::parse_str("one.second.zip:1"),
1067 PathWithPosition {
1068 path: PathBuf::from("one.second.zip"),
1069 row: Some(1),
1070 column: None
1071 }
1072 );
1073
1074 // Trim off trailing `:`s for otherwise valid input.
1075 assert_eq!(
1076 PathWithPosition::parse_str("test_file:10:1:"),
1077 PathWithPosition {
1078 path: PathBuf::from("test_file"),
1079 row: Some(10),
1080 column: Some(1)
1081 }
1082 );
1083
1084 assert_eq!(
1085 PathWithPosition::parse_str("test_file.rs:"),
1086 PathWithPosition {
1087 path: PathBuf::from("test_file.rs"),
1088 row: None,
1089 column: None
1090 }
1091 );
1092
1093 assert_eq!(
1094 PathWithPosition::parse_str("test_file.rs:1:"),
1095 PathWithPosition {
1096 path: PathBuf::from("test_file.rs"),
1097 row: Some(1),
1098 column: None
1099 }
1100 );
1101
1102 assert_eq!(
1103 PathWithPosition::parse_str("ab\ncd"),
1104 PathWithPosition {
1105 path: PathBuf::from("ab\ncd"),
1106 row: None,
1107 column: None
1108 }
1109 );
1110
1111 assert_eq!(
1112 PathWithPosition::parse_str("👋\nab"),
1113 PathWithPosition {
1114 path: PathBuf::from("👋\nab"),
1115 row: None,
1116 column: None
1117 }
1118 );
1119
1120 assert_eq!(
1121 PathWithPosition::parse_str("Types.hs:(617,9)-(670,28):"),
1122 PathWithPosition {
1123 path: PathBuf::from("Types.hs"),
1124 row: Some(617),
1125 column: Some(9),
1126 }
1127 );
1128 }
1129
1130 #[perf]
1131 #[cfg(not(target_os = "windows"))]
1132 fn path_with_position_parse_posix_path_with_suffix() {
1133 assert_eq!(
1134 PathWithPosition::parse_str("foo/bar:34:in"),
1135 PathWithPosition {
1136 path: PathBuf::from("foo/bar"),
1137 row: Some(34),
1138 column: None,
1139 }
1140 );
1141 assert_eq!(
1142 PathWithPosition::parse_str("foo/bar.rs:1902:::15:"),
1143 PathWithPosition {
1144 path: PathBuf::from("foo/bar.rs:1902"),
1145 row: Some(15),
1146 column: None
1147 }
1148 );
1149
1150 assert_eq!(
1151 PathWithPosition::parse_str("app-editors:zed-0.143.6:20240710-201212.log:34:"),
1152 PathWithPosition {
1153 path: PathBuf::from("app-editors:zed-0.143.6:20240710-201212.log"),
1154 row: Some(34),
1155 column: None,
1156 }
1157 );
1158
1159 assert_eq!(
1160 PathWithPosition::parse_str("crates/file_finder/src/file_finder.rs:1902:13:"),
1161 PathWithPosition {
1162 path: PathBuf::from("crates/file_finder/src/file_finder.rs"),
1163 row: Some(1902),
1164 column: Some(13),
1165 }
1166 );
1167
1168 assert_eq!(
1169 PathWithPosition::parse_str("crate/utils/src/test:today.log:34"),
1170 PathWithPosition {
1171 path: PathBuf::from("crate/utils/src/test:today.log"),
1172 row: Some(34),
1173 column: None,
1174 }
1175 );
1176 assert_eq!(
1177 PathWithPosition::parse_str("/testing/out/src/file_finder.odin(7:15)"),
1178 PathWithPosition {
1179 path: PathBuf::from("/testing/out/src/file_finder.odin"),
1180 row: Some(7),
1181 column: Some(15),
1182 }
1183 );
1184 }
1185
1186 #[perf]
1187 #[cfg(target_os = "windows")]
1188 fn path_with_position_parse_windows_path() {
1189 assert_eq!(
1190 PathWithPosition::parse_str("crates\\utils\\paths.rs"),
1191 PathWithPosition {
1192 path: PathBuf::from("crates\\utils\\paths.rs"),
1193 row: None,
1194 column: None
1195 }
1196 );
1197
1198 assert_eq!(
1199 PathWithPosition::parse_str("C:\\Users\\someone\\test_file.rs"),
1200 PathWithPosition {
1201 path: PathBuf::from("C:\\Users\\someone\\test_file.rs"),
1202 row: None,
1203 column: None
1204 }
1205 );
1206 }
1207
1208 #[perf]
1209 #[cfg(target_os = "windows")]
1210 fn path_with_position_parse_windows_path_with_suffix() {
1211 assert_eq!(
1212 PathWithPosition::parse_str("crates\\utils\\paths.rs:101"),
1213 PathWithPosition {
1214 path: PathBuf::from("crates\\utils\\paths.rs"),
1215 row: Some(101),
1216 column: None
1217 }
1218 );
1219
1220 assert_eq!(
1221 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs:1:20"),
1222 PathWithPosition {
1223 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs"),
1224 row: Some(1),
1225 column: Some(20)
1226 }
1227 );
1228
1229 assert_eq!(
1230 PathWithPosition::parse_str("C:\\Users\\someone\\test_file.rs(1902,13)"),
1231 PathWithPosition {
1232 path: PathBuf::from("C:\\Users\\someone\\test_file.rs"),
1233 row: Some(1902),
1234 column: Some(13)
1235 }
1236 );
1237
1238 // Trim off trailing `:`s for otherwise valid input.
1239 assert_eq!(
1240 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs:1902:13:"),
1241 PathWithPosition {
1242 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs"),
1243 row: Some(1902),
1244 column: Some(13)
1245 }
1246 );
1247
1248 assert_eq!(
1249 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs:1902:13:15:"),
1250 PathWithPosition {
1251 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs:1902"),
1252 row: Some(13),
1253 column: Some(15)
1254 }
1255 );
1256
1257 assert_eq!(
1258 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs:1902:::15:"),
1259 PathWithPosition {
1260 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs:1902"),
1261 row: Some(15),
1262 column: None
1263 }
1264 );
1265
1266 assert_eq!(
1267 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs(1902,13):"),
1268 PathWithPosition {
1269 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs"),
1270 row: Some(1902),
1271 column: Some(13),
1272 }
1273 );
1274
1275 assert_eq!(
1276 PathWithPosition::parse_str("\\\\?\\C:\\Users\\someone\\test_file.rs(1902):"),
1277 PathWithPosition {
1278 path: PathBuf::from("\\\\?\\C:\\Users\\someone\\test_file.rs"),
1279 row: Some(1902),
1280 column: None,
1281 }
1282 );
1283
1284 assert_eq!(
1285 PathWithPosition::parse_str("C:\\Users\\someone\\test_file.rs:1902:13:"),
1286 PathWithPosition {
1287 path: PathBuf::from("C:\\Users\\someone\\test_file.rs"),
1288 row: Some(1902),
1289 column: Some(13),
1290 }
1291 );
1292
1293 assert_eq!(
1294 PathWithPosition::parse_str("C:\\Users\\someone\\test_file.rs(1902,13):"),
1295 PathWithPosition {
1296 path: PathBuf::from("C:\\Users\\someone\\test_file.rs"),
1297 row: Some(1902),
1298 column: Some(13),
1299 }
1300 );
1301
1302 assert_eq!(
1303 PathWithPosition::parse_str("C:\\Users\\someone\\test_file.rs(1902):"),
1304 PathWithPosition {
1305 path: PathBuf::from("C:\\Users\\someone\\test_file.rs"),
1306 row: Some(1902),
1307 column: None,
1308 }
1309 );
1310
1311 assert_eq!(
1312 PathWithPosition::parse_str("crates/utils/paths.rs:101"),
1313 PathWithPosition {
1314 path: PathBuf::from("crates\\utils\\paths.rs"),
1315 row: Some(101),
1316 column: None,
1317 }
1318 );
1319 }
1320
1321 #[perf]
1322 fn test_path_compact() {
1323 let path: PathBuf = [
1324 home_dir().to_string_lossy().into_owned(),
1325 "some_file.txt".to_string(),
1326 ]
1327 .iter()
1328 .collect();
1329 if cfg!(any(target_os = "linux", target_os = "freebsd")) || cfg!(target_os = "macos") {
1330 assert_eq!(path.compact().to_str(), Some("~/some_file.txt"));
1331 } else {
1332 assert_eq!(path.compact().to_str(), path.to_str());
1333 }
1334 }
1335
1336 #[perf]
1337 fn test_extension_or_hidden_file_name() {
1338 // No dots in name
1339 let path = Path::new("/a/b/c/file_name.rs");
1340 assert_eq!(path.extension_or_hidden_file_name(), Some("rs"));
1341
1342 // Single dot in name
1343 let path = Path::new("/a/b/c/file.name.rs");
1344 assert_eq!(path.extension_or_hidden_file_name(), Some("rs"));
1345
1346 // Multiple dots in name
1347 let path = Path::new("/a/b/c/long.file.name.rs");
1348 assert_eq!(path.extension_or_hidden_file_name(), Some("rs"));
1349
1350 // Hidden file, no extension
1351 let path = Path::new("/a/b/c/.gitignore");
1352 assert_eq!(path.extension_or_hidden_file_name(), Some("gitignore"));
1353
1354 // Hidden file, with extension
1355 let path = Path::new("/a/b/c/.eslintrc.js");
1356 assert_eq!(path.extension_or_hidden_file_name(), Some("eslintrc.js"));
1357 }
1358
1359 #[perf]
1360 fn edge_of_glob() {
1361 let path = Path::new("/work/node_modules");
1362 let path_matcher =
1363 PathMatcher::new(&["**/node_modules/**".to_owned()], PathStyle::Posix).unwrap();
1364 assert!(
1365 path_matcher.is_match(path),
1366 "Path matcher should match {path:?}"
1367 );
1368 }
1369
1370 #[perf]
1371 fn project_search() {
1372 let path = Path::new("/Users/someonetoignore/work/zed/zed.dev/node_modules");
1373 let path_matcher =
1374 PathMatcher::new(&["**/node_modules/**".to_owned()], PathStyle::Posix).unwrap();
1375 assert!(
1376 path_matcher.is_match(path),
1377 "Path matcher should match {path:?}"
1378 );
1379 }
1380
1381 #[perf]
1382 #[cfg(target_os = "windows")]
1383 fn test_sanitized_path() {
1384 let path = Path::new("C:\\Users\\someone\\test_file.rs");
1385 let sanitized_path = SanitizedPath::new(path);
1386 assert_eq!(
1387 sanitized_path.to_string(),
1388 "C:\\Users\\someone\\test_file.rs"
1389 );
1390
1391 let path = Path::new("\\\\?\\C:\\Users\\someone\\test_file.rs");
1392 let sanitized_path = SanitizedPath::new(path);
1393 assert_eq!(
1394 sanitized_path.to_string(),
1395 "C:\\Users\\someone\\test_file.rs"
1396 );
1397 }
1398
1399 #[perf]
1400 fn test_compare_numeric_segments() {
1401 // Helper function to create peekable iterators and test
1402 fn compare(a: &str, b: &str) -> Ordering {
1403 let mut a_iter = a.chars().peekable();
1404 let mut b_iter = b.chars().peekable();
1405
1406 let result = compare_numeric_segments(&mut a_iter, &mut b_iter);
1407
1408 // Verify iterators advanced correctly
1409 assert!(
1410 !a_iter.next().is_some_and(|c| c.is_ascii_digit()),
1411 "Iterator a should have consumed all digits"
1412 );
1413 assert!(
1414 !b_iter.next().is_some_and(|c| c.is_ascii_digit()),
1415 "Iterator b should have consumed all digits"
1416 );
1417
1418 result
1419 }
1420
1421 // Basic numeric comparisons
1422 assert_eq!(compare("0", "0"), Ordering::Equal);
1423 assert_eq!(compare("1", "2"), Ordering::Less);
1424 assert_eq!(compare("9", "10"), Ordering::Less);
1425 assert_eq!(compare("10", "9"), Ordering::Greater);
1426 assert_eq!(compare("99", "100"), Ordering::Less);
1427
1428 // Leading zeros
1429 assert_eq!(compare("0", "00"), Ordering::Less);
1430 assert_eq!(compare("00", "0"), Ordering::Greater);
1431 assert_eq!(compare("01", "1"), Ordering::Greater);
1432 assert_eq!(compare("001", "1"), Ordering::Greater);
1433 assert_eq!(compare("001", "01"), Ordering::Greater);
1434
1435 // Same value different representation
1436 assert_eq!(compare("000100", "100"), Ordering::Greater);
1437 assert_eq!(compare("100", "0100"), Ordering::Less);
1438 assert_eq!(compare("0100", "00100"), Ordering::Less);
1439
1440 // Large numbers
1441 assert_eq!(compare("9999999999", "10000000000"), Ordering::Less);
1442 assert_eq!(
1443 compare(
1444 "340282366920938463463374607431768211455", // u128::MAX
1445 "340282366920938463463374607431768211456"
1446 ),
1447 Ordering::Less
1448 );
1449 assert_eq!(
1450 compare(
1451 "340282366920938463463374607431768211456", // > u128::MAX
1452 "340282366920938463463374607431768211455"
1453 ),
1454 Ordering::Greater
1455 );
1456
1457 // Iterator advancement verification
1458 let mut a_iter = "123abc".chars().peekable();
1459 let mut b_iter = "456def".chars().peekable();
1460
1461 compare_numeric_segments(&mut a_iter, &mut b_iter);
1462
1463 assert_eq!(a_iter.collect::<String>(), "abc");
1464 assert_eq!(b_iter.collect::<String>(), "def");
1465 }
1466
1467 #[perf]
1468 fn test_natural_sort() {
1469 // Basic alphanumeric
1470 assert_eq!(natural_sort("a", "b"), Ordering::Less);
1471 assert_eq!(natural_sort("b", "a"), Ordering::Greater);
1472 assert_eq!(natural_sort("a", "a"), Ordering::Equal);
1473
1474 // Case sensitivity
1475 assert_eq!(natural_sort("a", "A"), Ordering::Less);
1476 assert_eq!(natural_sort("A", "a"), Ordering::Greater);
1477 assert_eq!(natural_sort("aA", "aa"), Ordering::Greater);
1478 assert_eq!(natural_sort("aa", "aA"), Ordering::Less);
1479
1480 // Numbers
1481 assert_eq!(natural_sort("1", "2"), Ordering::Less);
1482 assert_eq!(natural_sort("2", "10"), Ordering::Less);
1483 assert_eq!(natural_sort("02", "10"), Ordering::Less);
1484 assert_eq!(natural_sort("02", "2"), Ordering::Greater);
1485
1486 // Mixed alphanumeric
1487 assert_eq!(natural_sort("a1", "a2"), Ordering::Less);
1488 assert_eq!(natural_sort("a2", "a10"), Ordering::Less);
1489 assert_eq!(natural_sort("a02", "a2"), Ordering::Greater);
1490 assert_eq!(natural_sort("a1b", "a1c"), Ordering::Less);
1491
1492 // Multiple numeric segments
1493 assert_eq!(natural_sort("1a2", "1a10"), Ordering::Less);
1494 assert_eq!(natural_sort("1a10", "1a2"), Ordering::Greater);
1495 assert_eq!(natural_sort("2a1", "10a1"), Ordering::Less);
1496
1497 // Special characters
1498 assert_eq!(natural_sort("a-1", "a-2"), Ordering::Less);
1499 assert_eq!(natural_sort("a_1", "a_2"), Ordering::Less);
1500 assert_eq!(natural_sort("a.1", "a.2"), Ordering::Less);
1501
1502 // Unicode
1503 assert_eq!(natural_sort("文1", "文2"), Ordering::Less);
1504 assert_eq!(natural_sort("文2", "文10"), Ordering::Less);
1505 assert_eq!(natural_sort("🔤1", "🔤2"), Ordering::Less);
1506
1507 // Empty and special cases
1508 assert_eq!(natural_sort("", ""), Ordering::Equal);
1509 assert_eq!(natural_sort("", "a"), Ordering::Less);
1510 assert_eq!(natural_sort("a", ""), Ordering::Greater);
1511 assert_eq!(natural_sort(" ", " "), Ordering::Less);
1512
1513 // Mixed everything
1514 assert_eq!(natural_sort("File-1.txt", "File-2.txt"), Ordering::Less);
1515 assert_eq!(natural_sort("File-02.txt", "File-2.txt"), Ordering::Greater);
1516 assert_eq!(natural_sort("File-2.txt", "File-10.txt"), Ordering::Less);
1517 assert_eq!(natural_sort("File_A1", "File_A2"), Ordering::Less);
1518 assert_eq!(natural_sort("File_a1", "File_A1"), Ordering::Less);
1519 }
1520
1521 #[perf]
1522 fn test_compare_paths() {
1523 // Helper function for cleaner tests
1524 fn compare(a: &str, is_a_file: bool, b: &str, is_b_file: bool) -> Ordering {
1525 compare_paths((Path::new(a), is_a_file), (Path::new(b), is_b_file))
1526 }
1527
1528 // Basic path comparison
1529 assert_eq!(compare("a", true, "b", true), Ordering::Less);
1530 assert_eq!(compare("b", true, "a", true), Ordering::Greater);
1531 assert_eq!(compare("a", true, "a", true), Ordering::Equal);
1532
1533 // Files vs Directories
1534 assert_eq!(compare("a", true, "a", false), Ordering::Greater);
1535 assert_eq!(compare("a", false, "a", true), Ordering::Less);
1536 assert_eq!(compare("b", false, "a", true), Ordering::Less);
1537
1538 // Extensions
1539 assert_eq!(compare("a.txt", true, "a.md", true), Ordering::Greater);
1540 assert_eq!(compare("a.md", true, "a.txt", true), Ordering::Less);
1541 assert_eq!(compare("a", true, "a.txt", true), Ordering::Less);
1542
1543 // Nested paths
1544 assert_eq!(compare("dir/a", true, "dir/b", true), Ordering::Less);
1545 assert_eq!(compare("dir1/a", true, "dir2/a", true), Ordering::Less);
1546 assert_eq!(compare("dir/sub/a", true, "dir/a", true), Ordering::Less);
1547
1548 // Case sensitivity in paths
1549 assert_eq!(
1550 compare("Dir/file", true, "dir/file", true),
1551 Ordering::Greater
1552 );
1553 assert_eq!(
1554 compare("dir/File", true, "dir/file", true),
1555 Ordering::Greater
1556 );
1557 assert_eq!(compare("dir/file", true, "Dir/File", true), Ordering::Less);
1558
1559 // Hidden files and special names
1560 assert_eq!(compare(".hidden", true, "visible", true), Ordering::Less);
1561 assert_eq!(compare("_special", true, "normal", true), Ordering::Less);
1562 assert_eq!(compare(".config", false, ".data", false), Ordering::Less);
1563
1564 // Mixed numeric paths
1565 assert_eq!(
1566 compare("dir1/file", true, "dir2/file", true),
1567 Ordering::Less
1568 );
1569 assert_eq!(
1570 compare("dir2/file", true, "dir10/file", true),
1571 Ordering::Less
1572 );
1573 assert_eq!(
1574 compare("dir02/file", true, "dir2/file", true),
1575 Ordering::Greater
1576 );
1577
1578 // Root paths
1579 assert_eq!(compare("/a", true, "/b", true), Ordering::Less);
1580 assert_eq!(compare("/", false, "/a", true), Ordering::Less);
1581
1582 // Complex real-world examples
1583 assert_eq!(
1584 compare("project/src/main.rs", true, "project/src/lib.rs", true),
1585 Ordering::Greater
1586 );
1587 assert_eq!(
1588 compare(
1589 "project/tests/test_1.rs",
1590 true,
1591 "project/tests/test_2.rs",
1592 true
1593 ),
1594 Ordering::Less
1595 );
1596 assert_eq!(
1597 compare(
1598 "project/v1.0.0/README.md",
1599 true,
1600 "project/v1.10.0/README.md",
1601 true
1602 ),
1603 Ordering::Less
1604 );
1605 }
1606
1607 #[perf]
1608 fn test_natural_sort_case_sensitivity() {
1609 std::thread::sleep(std::time::Duration::from_millis(100));
1610 // Same letter different case - lowercase should come first
1611 assert_eq!(natural_sort("a", "A"), Ordering::Less);
1612 assert_eq!(natural_sort("A", "a"), Ordering::Greater);
1613 assert_eq!(natural_sort("a", "a"), Ordering::Equal);
1614 assert_eq!(natural_sort("A", "A"), Ordering::Equal);
1615
1616 // Mixed case strings
1617 assert_eq!(natural_sort("aaa", "AAA"), Ordering::Less);
1618 assert_eq!(natural_sort("AAA", "aaa"), Ordering::Greater);
1619 assert_eq!(natural_sort("aAa", "AaA"), Ordering::Less);
1620
1621 // Different letters
1622 assert_eq!(natural_sort("a", "b"), Ordering::Less);
1623 assert_eq!(natural_sort("A", "b"), Ordering::Less);
1624 assert_eq!(natural_sort("a", "B"), Ordering::Less);
1625 }
1626
1627 #[perf]
1628 fn test_natural_sort_with_numbers() {
1629 // Basic number ordering
1630 assert_eq!(natural_sort("file1", "file2"), Ordering::Less);
1631 assert_eq!(natural_sort("file2", "file10"), Ordering::Less);
1632 assert_eq!(natural_sort("file10", "file2"), Ordering::Greater);
1633
1634 // Numbers in different positions
1635 assert_eq!(natural_sort("1file", "2file"), Ordering::Less);
1636 assert_eq!(natural_sort("file1text", "file2text"), Ordering::Less);
1637 assert_eq!(natural_sort("text1file", "text2file"), Ordering::Less);
1638
1639 // Multiple numbers in string
1640 assert_eq!(natural_sort("file1-2", "file1-10"), Ordering::Less);
1641 assert_eq!(natural_sort("2-1file", "10-1file"), Ordering::Less);
1642
1643 // Leading zeros
1644 assert_eq!(natural_sort("file002", "file2"), Ordering::Greater);
1645 assert_eq!(natural_sort("file002", "file10"), Ordering::Less);
1646
1647 // Very large numbers
1648 assert_eq!(
1649 natural_sort("file999999999999999999999", "file999999999999999999998"),
1650 Ordering::Greater
1651 );
1652
1653 // u128 edge cases
1654
1655 // Numbers near u128::MAX (340,282,366,920,938,463,463,374,607,431,768,211,455)
1656 assert_eq!(
1657 natural_sort(
1658 "file340282366920938463463374607431768211454",
1659 "file340282366920938463463374607431768211455"
1660 ),
1661 Ordering::Less
1662 );
1663
1664 // Equal length numbers that overflow u128
1665 assert_eq!(
1666 natural_sort(
1667 "file340282366920938463463374607431768211456",
1668 "file340282366920938463463374607431768211455"
1669 ),
1670 Ordering::Greater
1671 );
1672
1673 // Different length numbers that overflow u128
1674 assert_eq!(
1675 natural_sort(
1676 "file3402823669209384634633746074317682114560",
1677 "file340282366920938463463374607431768211455"
1678 ),
1679 Ordering::Greater
1680 );
1681
1682 // Leading zeros with numbers near u128::MAX
1683 assert_eq!(
1684 natural_sort(
1685 "file0340282366920938463463374607431768211455",
1686 "file340282366920938463463374607431768211455"
1687 ),
1688 Ordering::Greater
1689 );
1690
1691 // Very large numbers with different lengths (both overflow u128)
1692 assert_eq!(
1693 natural_sort(
1694 "file999999999999999999999999999999999999999999999999",
1695 "file9999999999999999999999999999999999999999999999999"
1696 ),
1697 Ordering::Less
1698 );
1699
1700 // Mixed case with numbers
1701 assert_eq!(natural_sort("File1", "file2"), Ordering::Greater);
1702 assert_eq!(natural_sort("file1", "File2"), Ordering::Less);
1703 }
1704
1705 #[perf]
1706 fn test_natural_sort_edge_cases() {
1707 // Empty strings
1708 assert_eq!(natural_sort("", ""), Ordering::Equal);
1709 assert_eq!(natural_sort("", "a"), Ordering::Less);
1710 assert_eq!(natural_sort("a", ""), Ordering::Greater);
1711
1712 // Special characters
1713 assert_eq!(natural_sort("file-1", "file_1"), Ordering::Less);
1714 assert_eq!(natural_sort("file.1", "file_1"), Ordering::Less);
1715 assert_eq!(natural_sort("file 1", "file_1"), Ordering::Less);
1716
1717 // Unicode characters
1718 // 9312 vs 9313
1719 assert_eq!(natural_sort("file①", "file②"), Ordering::Less);
1720 // 9321 vs 9313
1721 assert_eq!(natural_sort("file⑩", "file②"), Ordering::Greater);
1722 // 28450 vs 23383
1723 assert_eq!(natural_sort("file漢", "file字"), Ordering::Greater);
1724
1725 // Mixed alphanumeric with special chars
1726 assert_eq!(natural_sort("file-1a", "file-1b"), Ordering::Less);
1727 assert_eq!(natural_sort("file-1.2", "file-1.10"), Ordering::Less);
1728 assert_eq!(natural_sort("file-1.10", "file-1.2"), Ordering::Greater);
1729 }
1730}