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