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