sugar_path 3.0.0

use std::{
  borrow::Cow,
  ffi::{OsStr, OsString},
  io,
  iter::Peekable,
  path::{Component, Path, PathBuf},
};

use memchr::{memchr, memrchr};
use smallvec::SmallVec;

use crate::{SugarPath, utils::try_get_current_dir};

type StrVec<'a> = SmallVec<[&'a str; 8]>;
type OsStrVec<'a> = SmallVec<[&'a OsStr; 16]>;

enum OwnedNormalizeOutcome {
  Unchanged,
  CurrentDirectory,
  Owned(PathBuf),
}

#[derive(Clone, Copy, PartialEq, Eq)]
enum TrailingSeparator {
  Preserve,
  Strip,
}

enum RelativeOutcome<'a> {
  BorrowedNative(&'a Path),
  Native(PathBuf),
  Slash(String),
}

impl<'a> RelativeOutcome<'a> {
  fn into_path_buf(self) -> PathBuf {
    match self {
      Self::BorrowedNative(path) => path.to_owned(),
      Self::Native(path) => path,
      Self::Slash(path) => {
        #[cfg(target_family = "windows")]
        {
          PathBuf::from(path.replace('/', "\\"))
        }
        #[cfg(not(target_family = "windows"))]
        {
          PathBuf::from(path)
        }
      }
    }
  }

  fn into_cow_path(self) -> Cow<'a, Path> {
    match self {
      Self::BorrowedNative(path) => Cow::Borrowed(path),
      outcome => Cow::Owned(outcome.into_path_buf()),
    }
  }
}

#[derive(Clone, Copy)]
struct LexicalRelativeShape {
  unresolved_parents: usize,
  surviving_normals: usize,
  max_normal_depth: usize,
}

fn classify_lexical_relative(path: &Path) -> Option<LexicalRelativeShape> {
  let mut unresolved_parents = 0;
  let mut surviving_normals = 0;
  let mut max_normal_depth = 0;

  for component in path.components() {
    match component {
      Component::CurDir => {}
      Component::ParentDir => {
        if surviving_normals > 0 {
          surviving_normals -= 1;
        } else {
          unresolved_parents += 1;
        }
      }
      Component::Normal(_) => {
        surviving_normals += 1;
        max_normal_depth = max_normal_depth.max(surviving_normals);
      }
      Component::Prefix(_) | Component::RootDir => return None,
    }
  }

  Some(LexicalRelativeShape { unresolved_parents, surviving_normals, max_normal_depth })
}

fn collect_lexical_normals<'a>(path: &'a Path, shape: LexicalRelativeShape) -> OsStrVec<'a> {
  let mut normals = OsStrVec::with_capacity(shape.max_normal_depth);
  for component in path.components() {
    match component {
      Component::CurDir => {}
      Component::ParentDir => {
        normals.pop();
      }
      Component::Normal(normal) => normals.push(normal),
      Component::Prefix(_) | Component::RootDir => {
        unreachable!("classified lexical relative paths have no prefix or root")
      }
    }
  }
  debug_assert_eq!(normals.len(), shape.surviving_normals);
  normals
}

fn try_relative_lexically(target: &Path, base: &Path) -> Option<PathBuf> {
  let target_shape = classify_lexical_relative(target)?;
  let base_shape = classify_lexical_relative(base)?;
  if target_shape.unresolved_parents != base_shape.unresolved_parents {
    return None;
  }

  let target = collect_lexical_normals(target, target_shape);
  let base = collect_lexical_normals(base, base_shape);

  let common_len = target
    .iter()
    .zip(&base)
    .take_while(|(target, base)| {
      #[cfg(target_family = "windows")]
      {
        target.eq_ignore_ascii_case(base)
      }
      #[cfg(not(target_family = "windows"))]
      {
        target == base
      }
    })
    .count();

  let up_len = base.len() - common_len;
  let target_suffix = &target[common_len..];
  #[cfg(target_family = "windows")]
  if up_len == 0
    && target_suffix.first().is_some_and(|component| {
      !windows_standalone_relative_bytes_are_representable(component.as_encoded_bytes())
    })
  {
    return None;
  }
  let component_count = up_len + target_suffix.len();
  let capacity = up_len * 2
    + target_suffix.iter().map(|component| component.len()).sum::<usize>()
    + component_count.saturating_sub(1);
  #[cfg(target_family = "windows")]
  {
    let mut relative = OsString::with_capacity(capacity);
    for _ in 0..up_len {
      push_windows_relative_component(&mut relative, OsStr::new(".."));
    }
    for component in target_suffix {
      push_windows_relative_component(&mut relative, component);
    }
    Some(PathBuf::from(relative))
  }
  #[cfg(not(target_family = "windows"))]
  let mut relative = PathBuf::with_capacity(capacity);
  #[cfg(not(target_family = "windows"))]
  for _ in 0..up_len {
    relative.push(Component::ParentDir);
  }
  #[cfg(not(target_family = "windows"))]
  for component in target_suffix {
    relative.push(component);
  }
  #[cfg(not(target_family = "windows"))]
  Some(relative)
}

#[cfg(target_family = "windows")]
fn classify_drive_relative(path: &Path) -> Option<(u8, LexicalRelativeShape)> {
  use std::path::Prefix;

  if path.has_root() {
    return None;
  }
  let mut components = path.components();
  let Component::Prefix(prefix) = components.next()? else {
    return None;
  };
  let Prefix::Disk(parsed_drive) = prefix.kind() else {
    return None;
  };
  let drive = windows_drive_spelling(path).unwrap_or(parsed_drive);

  let mut unresolved_parents = 0;
  let mut surviving_normals = 0;
  let mut max_normal_depth = 0;
  for component in components {
    match component {
      Component::CurDir => {}
      Component::ParentDir => {
        if surviving_normals > 0 {
          surviving_normals -= 1;
        } else {
          unresolved_parents += 1;
        }
      }
      Component::Normal(_) => {
        surviving_normals += 1;
        max_normal_depth = max_normal_depth.max(surviving_normals);
      }
      Component::Prefix(_) | Component::RootDir => return None,
    }
  }

  Some((drive, LexicalRelativeShape { unresolved_parents, surviving_normals, max_normal_depth }))
}

#[cfg(target_family = "windows")]
fn windows_drive_spelling(path: &Path) -> Option<u8> {
  let bytes = path.as_os_str().as_encoded_bytes();
  if bytes.len() >= 2 && bytes[1] == b':' && bytes[0].is_ascii_alphabetic() {
    return Some(bytes[0]);
  }
  if bytes.len() >= 6
    && matches!(bytes[0], b'/' | b'\\')
    && matches!(bytes[1], b'/' | b'\\')
    && bytes[2] == b'?'
    && matches!(bytes[3], b'/' | b'\\')
    && bytes[5] == b':'
    && bytes[4].is_ascii_alphabetic()
  {
    return Some(bytes[4]);
  }
  None
}

#[cfg(target_family = "windows")]
fn push_windows_relative_component(path: &mut OsString, component: &OsStr) {
  if !path.is_empty() {
    path.push("\\");
  }
  path.push(component);
}

#[cfg(target_family = "windows")]
fn push_windows_path_component(
  path: &mut OsString,
  component: &OsStr,
  forward_slash_is_separator: bool,
) {
  let has_separator = matches!(path.as_encoded_bytes().last(), Some(b'\\'))
    || (forward_slash_is_separator && matches!(path.as_encoded_bytes().last(), Some(b'/')));
  if !path.is_empty() && !has_separator {
    path.push("\\");
  }
  path.push(component);
}

#[cfg(target_family = "windows")]
fn collect_drive_relative_normals(path: &Path, shape: LexicalRelativeShape) -> OsStrVec<'_> {
  let mut normals = OsStrVec::with_capacity(shape.max_normal_depth);
  for component in path.components().skip(1) {
    match component {
      Component::CurDir => {}
      Component::ParentDir => {
        normals.pop();
      }
      Component::Normal(normal) => normals.push(normal),
      Component::Prefix(_) | Component::RootDir => {
        unreachable!("classified drive-relative paths have one prefix and no root")
      }
    }
  }
  debug_assert_eq!(normals.len(), shape.surviving_normals);
  normals
}

#[cfg(target_family = "windows")]
fn try_relative_drive_lexically(target: &Path, base: &Path) -> Option<PathBuf> {
  let (target_drive, target_shape) = classify_drive_relative(target)?;
  let (base_drive, base_shape) = classify_drive_relative(base)?;
  if !target_drive.eq_ignore_ascii_case(&base_drive)
    || target_shape.unresolved_parents != base_shape.unresolved_parents
  {
    return None;
  }

  let target = collect_drive_relative_normals(target, target_shape);
  let base = collect_drive_relative_normals(base, base_shape);
  let common_len =
    target.iter().zip(&base).take_while(|(target, base)| target.eq_ignore_ascii_case(base)).count();
  let up_len = base.len() - common_len;
  let target_suffix = &target[common_len..];
  if up_len == 0
    && target_suffix.first().is_some_and(|component| {
      !windows_standalone_relative_bytes_are_representable(component.as_encoded_bytes())
    })
  {
    return None;
  }
  let component_count = up_len + target_suffix.len();
  let capacity = up_len * 2
    + target_suffix.iter().map(|component| component.len()).sum::<usize>()
    + component_count.saturating_sub(1);
  let mut relative = OsString::with_capacity(capacity);
  for _ in 0..up_len {
    push_windows_relative_component(&mut relative, OsStr::new(".."));
  }
  for component in target_suffix {
    push_windows_relative_component(&mut relative, component);
  }
  Some(PathBuf::from(relative))
}

#[cfg(target_family = "windows")]
fn windows_absolute_disk_drive(path: &Path) -> Option<(u8, bool)> {
  use std::path::Prefix;

  let Component::Prefix(prefix) = path.components().next()? else {
    return None;
  };
  match prefix.kind() {
    Prefix::Disk(drive) => Some((windows_drive_spelling(path).unwrap_or(drive), true)),
    Prefix::VerbatimDisk(drive) => Some((windows_drive_spelling(path).unwrap_or(drive), false)),
    _ => None,
  }
}

#[cfg(target_family = "windows")]
fn rebuild_windows_disk_path(path: &Path, drive: u8) -> Option<PathBuf> {
  let mut rebuilt = OsString::with_capacity(path.as_os_str().len().max(3));
  let prefix = [drive, b':', b'\\'];
  rebuilt.push(std::str::from_utf8(&prefix).expect("Windows drive prefix is ASCII"));
  for component in path.components() {
    match component {
      Component::Prefix(_) | Component::RootDir | Component::CurDir => {}
      Component::ParentDir | Component::Normal(_) => {
        if memchr(b'/', component.as_os_str().as_encoded_bytes()).is_some() {
          return None;
        }
        push_windows_path_component(&mut rebuilt, component.as_os_str(), true);
      }
    }
  }
  Some(PathBuf::from(rebuilt))
}

#[cfg(target_family = "windows")]
fn rebuild_windows_verbatim_disk_path(path: &Path, drive: u8) -> PathBuf {
  let mut rebuilt = OsString::with_capacity(path.as_os_str().len().max(7));
  let prefix = [b'\\', b'\\', b'?', b'\\', drive, b':', b'\\'];
  rebuilt.push(std::str::from_utf8(&prefix).expect("Windows verbatim drive prefix is ASCII"));
  for component in path.components() {
    match component {
      Component::Prefix(_) | Component::RootDir | Component::CurDir => {}
      Component::ParentDir | Component::Normal(_) => {
        push_windows_path_component(&mut rebuilt, component.as_os_str(), false);
      }
    }
  }
  PathBuf::from(rebuilt)
}

#[cfg(target_family = "windows")]
fn preserve_windows_drive_spelling(path: PathBuf, drive: u8) -> PathBuf {
  match windows_absolute_disk_drive(&path) {
    Some((actual, true)) if actual == drive => path,
    Some((actual, true)) if actual.eq_ignore_ascii_case(&drive) => {
      rebuild_windows_disk_path(&path, drive).unwrap_or(path)
    }
    Some((actual, false)) if actual.eq_ignore_ascii_case(&drive) => {
      rebuild_windows_verbatim_disk_path(&path, drive)
    }
    _ => path,
  }
}

#[cfg(target_family = "windows")]
fn absolutize_drive_relative_with<P>(path: &Path, cwd: P, drive: u8) -> Cow<'_, Path>
where
  P: AsRef<Path> + Into<PathBuf>,
{
  let Some((cwd_drive, ordinary_disk)) = windows_absolute_disk_drive(cwd.as_ref()) else {
    return normalize_for_resolution(path);
  };
  if !cwd_drive.eq_ignore_ascii_case(&drive) {
    return normalize_for_resolution(path);
  }

  let resolved = if cwd_drive == drive {
    cwd.into()
  } else if ordinary_disk {
    rebuild_windows_disk_path(cwd.as_ref(), drive)
      .expect("ordinary Windows disk components contain no literal forward slash")
  } else {
    rebuild_windows_verbatim_disk_path(cwd.as_ref(), drive)
  };
  let mut resolved = resolved.into_os_string();
  for component in path.components().skip(1) {
    push_windows_path_component(&mut resolved, component.as_os_str(), ordinary_disk);
  }
  Cow::Owned(normalize_owned_for_resolution(PathBuf::from(resolved)))
}

fn normalize_owned_path_buf_with(mut path: PathBuf, trailing: TrailingSeparator) -> PathBuf {
  let outcome = match normalize_path(&path, trailing) {
    Cow::Borrowed(normalized) if std::ptr::eq(normalized, path.as_path()) => {
      OwnedNormalizeOutcome::Unchanged
    }
    Cow::Borrowed(normalized) if normalized.as_os_str() == OsStr::new(".") => {
      OwnedNormalizeOutcome::CurrentDirectory
    }
    Cow::Borrowed(normalized) => OwnedNormalizeOutcome::Owned(normalized.to_owned()),
    Cow::Owned(normalized) => OwnedNormalizeOutcome::Owned(normalized),
  };

  match outcome {
    OwnedNormalizeOutcome::Unchanged => path,
    OwnedNormalizeOutcome::CurrentDirectory => {
      path.clear();
      path.push(".");
      path
    }
    OwnedNormalizeOutcome::Owned(normalized) => normalized,
  }
}

pub(crate) fn normalize_owned_path_buf(path: PathBuf) -> PathBuf {
  normalize_owned_path_buf_with(path, TrailingSeparator::Preserve)
}

fn normalize_owned_for_resolution(path: PathBuf) -> PathBuf {
  normalize_owned_path_buf_with(path, TrailingSeparator::Strip)
}

fn normalize_path(path: &Path, trailing: TrailingSeparator) -> Cow<'_, Path> {
  if !needs_normalization(path, trailing) {
    return Cow::Borrowed(path);
  }
  normalize_inner(
    path.components().peekable(),
    path.as_os_str().len(),
    trailing == TrailingSeparator::Preserve && has_trailing_separator(path),
    {
      #[cfg(target_family = "windows")]
      {
        windows_drive_spelling(path)
      }
      #[cfg(not(target_family = "windows"))]
      {
        None
      }
    },
  )
}

fn normalize_for_resolution(path: &Path) -> Cow<'_, Path> {
  normalize_path(path, TrailingSeparator::Strip)
}

#[inline]
fn has_trailing_separator(path: &Path) -> bool {
  let Some(last) = path.as_os_str().as_encoded_bytes().last() else {
    return false;
  };
  if *last == std::path::MAIN_SEPARATOR as u8 {
    return true;
  }

  #[cfg(target_family = "windows")]
  {
    *last == b'/'
      && !matches!(
        path.components().next(),
        Some(Component::Prefix(prefix))
          if windows_prefix_is_verbatim(prefix.kind())
      )
  }
  #[cfg(not(target_family = "windows"))]
  {
    false
  }
}

fn replace_main_separator_in_owned(mut string: String) -> String {
  if std::path::MAIN_SEPARATOR == '/' {
    string
  } else {
    let mut offset = 0;
    while let Some(position) = memchr(std::path::MAIN_SEPARATOR as u8, &string.as_bytes()[offset..])
    {
      let separator = offset + position;
      string.replace_range(separator..=separator, "/");
      offset = separator + 1;
    }
    string
  }
}

pub(crate) fn try_path_buf_into_slash(path: PathBuf) -> Result<String, PathBuf> {
  match path.into_os_string().into_string() {
    Ok(string) => Ok(replace_main_separator_in_owned(string)),
    Err(path) => Err(PathBuf::from(path)),
  }
}

pub(crate) fn path_buf_into_slash(path: PathBuf) -> String {
  try_path_buf_into_slash(path).expect("path is not valid Unicode")
}

pub(crate) fn path_buf_into_slash_lossy(path: PathBuf) -> String {
  match try_path_buf_into_slash(path) {
    Ok(string) => string,
    Err(path) => replace_main_separator_in_owned(path.to_string_lossy().into_owned()),
  }
}

#[cfg(target_family = "windows")]
fn windows_absolute_parts(path: &Path) -> Option<(std::path::Prefix<'_>, &Path)> {
  let mut components = path.components();
  let Component::Prefix(prefix) = components.next()? else {
    return None;
  };
  if matches!(components.clone().next(), Some(Component::RootDir)) {
    components.next();
  }
  Some((prefix.kind(), components.as_path()))
}

#[cfg(target_family = "windows")]
fn windows_prefix_is_verbatim(prefix: std::path::Prefix<'_>) -> bool {
  matches!(
    prefix,
    std::path::Prefix::Verbatim(_)
      | std::path::Prefix::VerbatimDisk(_)
      | std::path::Prefix::VerbatimUNC(_, _)
  )
}

#[cfg(target_family = "windows")]
fn windows_standalone_relative_is_representable(path: &str) -> bool {
  windows_standalone_relative_bytes_are_representable(path.as_bytes())
}

#[cfg(target_family = "windows")]
fn windows_standalone_relative_bytes_are_representable(path: &[u8]) -> bool {
  !matches!(path.first(), Some(b'/' | b'\\'))
    && !(path.len() >= 2 && path[0].is_ascii_alphabetic() && path[1] == b':')
}

#[cfg(target_family = "windows")]
fn windows_relative_component_has_literal_slash(component: &Component<'_>) -> bool {
  let Component::Normal(component) = component else {
    return false;
  };
  memchr(b'/', component.as_encoded_bytes()).is_some()
}

#[cfg(target_family = "windows")]
fn windows_native_relative_input_is_clean(path: &str) -> bool {
  if memchr(b'/', path.as_bytes()).is_some() {
    return false;
  }

  let path = path.trim_end_matches('\\');
  let mut offset = 0;
  while offset < path.len() {
    let end = memchr(b'\\', &path.as_bytes()[offset..])
      .map(|position| offset + position)
      .unwrap_or(path.len());
    let component = &path[offset..end];
    if component.is_empty() || component == "." || component == ".." {
      return false;
    }
    offset = end.saturating_add(1);
  }
  true
}

#[cfg(target_family = "windows")]
fn relative_windows_native_fast<'a>(target: &'a str, base: &str) -> Option<RelativeOutcome<'a>> {
  if !windows_native_relative_input_is_clean(target)
    || !windows_native_relative_input_is_clean(base)
  {
    return None;
  }

  let target = target.trim_end_matches('\\');
  let base = base.trim_end_matches('\\');
  let common_byte_len = target
    .as_bytes()
    .iter()
    .zip(base.as_bytes())
    .take_while(|(target, base)| target.eq_ignore_ascii_case(base))
    .count();
  let at_boundary = (common_byte_len == target.len() && common_byte_len == base.len())
    || (common_byte_len == target.len() && base.as_bytes().get(common_byte_len) == Some(&b'\\'))
    || (common_byte_len == base.len() && target.as_bytes().get(common_byte_len) == Some(&b'\\'));
  let common_prefix = if at_boundary {
    common_byte_len
  } else {
    memrchr(b'\\', &target.as_bytes()[..common_byte_len]).unwrap_or(0)
  };

  let base_remaining = &base.as_bytes()[common_prefix..];
  let mut ups = 0usize;
  let mut offset = 0;
  while offset < base_remaining.len() {
    if base_remaining[offset] == b'\\' {
      offset += 1;
      continue;
    }
    ups += 1;
    offset = memchr(b'\\', &base_remaining[offset..])
      .map(|position| offset + position + 1)
      .unwrap_or(base_remaining.len());
  }

  let target_suffix = target[common_prefix..].trim_start_matches('\\');
  if ups == 0 {
    if !windows_standalone_relative_is_representable(target_suffix) {
      return None;
    }
    return Some(RelativeOutcome::BorrowedNative(Path::new(target_suffix)));
  }

  let mut relative = String::with_capacity(ups * 3 + target_suffix.len());
  for _ in 0..ups {
    if !relative.is_empty() {
      relative.push('\\');
    }
    relative.push_str("..");
  }
  if !target_suffix.is_empty() {
    relative.push('\\');
    relative.push_str(target_suffix);
  }
  Some(RelativeOutcome::Native(PathBuf::from(relative)))
}

#[cfg(target_family = "windows")]
fn try_relative_windows_absolute<'a>(
  target_path: &'a Path,
  base_path: &Path,
) -> Option<RelativeOutcome<'a>> {
  let (target_prefix, target_rest) = windows_absolute_parts(target_path)?;
  let (base_prefix, base_rest) = windows_absolute_parts(base_path)?;
  if !windows_prefixes_eq_ignore_ascii_case(target_prefix, base_prefix) {
    return Some(RelativeOutcome::Native(normalize_for_resolution(target_path).into_owned()));
  }

  // A forward slash is a literal byte inside a verbatim path component. The
  // normalized-string fallback would reinterpret it as a separator, so let
  // the component fallback retain the native `std::path` meaning instead.
  if windows_prefix_is_verbatim(target_prefix)
    && (memchr(b'/', target_rest.as_os_str().as_encoded_bytes()).is_some()
      || memchr(b'/', base_rest.as_os_str().as_encoded_bytes()).is_some())
  {
    return None;
  }

  let (target_str, base_str) = (target_rest.to_str()?, base_rest.to_str()?);
  if let Some(outcome) = relative_windows_native_fast(target_str, base_str) {
    return Some(outcome);
  }

  // Dirty or mixed-separator paths retain the established normalized-string
  // fallback. Its temporary allocations stay off the canonical Rolldown path.
  let target_fwd = normalize_backslash_cow(target_str);
  let base_fwd = normalize_backslash_cow(base_str);
  let relative = relative_str(&target_fwd, &base_fwd);
  if !windows_standalone_relative_is_representable(&relative) {
    return None;
  }
  Some(match relative {
    Cow::Borrowed(relative) => {
      let target_without_trailing = target_str.trim_end_matches(['/', '\\']);
      debug_assert!(relative.len() <= target_without_trailing.len());
      let original_relative =
        &target_without_trailing[target_without_trailing.len() - relative.len()..];
      if memchr(b'/', original_relative.as_bytes()).is_none() {
        RelativeOutcome::BorrowedNative(Path::new(original_relative))
      } else {
        RelativeOutcome::Slash(relative.to_owned())
      }
    }
    Cow::Owned(relative) => RelativeOutcome::Slash(relative),
  })
}

#[cfg(target_family = "windows")]
fn try_relative_windows_root_lexically(target: &Path, base: &Path) -> Option<PathBuf> {
  if !matches!(target.components().next(), Some(Component::RootDir))
    || !matches!(base.components().next(), Some(Component::RootDir))
  {
    return None;
  }

  let target = normalize_for_resolution(target).into_owned();
  let base = normalize_for_resolution(base).into_owned();
  Some(relative_from_resolved(base, target).into_path_buf())
}

fn relative_without_cwd<'a>(
  target_path: &'a Path,
  base_path: &Path,
) -> Option<RelativeOutcome<'a>> {
  // Fast path: absolute inputs do not need cwd state. Unix can scan the UTF-8
  // spelling directly. Windows first compares borrowed prefix components, then
  // scans canonical native separators without allocating normalized copies.
  #[cfg(target_family = "windows")]
  if target_path.is_absolute()
    && base_path.is_absolute()
    && let Some(outcome) = try_relative_windows_absolute(target_path, base_path)
  {
    return Some(outcome);
  }

  #[cfg(not(target_family = "windows"))]
  if target_path.is_absolute()
    && base_path.is_absolute()
    && let (Some(target_str), Some(base_str)) = (target_path.to_str(), base_path.to_str())
  {
    return Some(match relative_str(target_str, base_str) {
      Cow::Borrowed(relative) => RelativeOutcome::BorrowedNative(Path::new(relative)),
      Cow::Owned(relative) => RelativeOutcome::Slash(relative),
    });
  }

  #[cfg(target_family = "windows")]
  if let Some(relative) = try_relative_windows_root_lexically(target_path, base_path) {
    return Some(RelativeOutcome::Native(relative));
  }

  #[cfg(target_family = "windows")]
  if let Some(relative) = try_relative_drive_lexically(target_path, base_path) {
    return Some(RelativeOutcome::Native(relative));
  }

  // Plain relative paths with the same number of unresolved leading parents
  // resolve from the same cwd ancestor. Their relative path is therefore
  // independent of the cwd itself.
  if !target_path.has_root()
    && !base_path.has_root()
    && let Some(relative) = try_relative_lexically(target_path, base_path)
  {
    return Some(RelativeOutcome::Native(relative));
  }

  None
}

fn relative_from_resolved<'a>(base: PathBuf, target: PathBuf) -> RelativeOutcome<'a> {
  #[cfg(target_family = "windows")]
  if windows_paths_have_different_prefixes(&base, &target) {
    return RelativeOutcome::Native(target);
  }

  if base == target {
    return RelativeOutcome::Native(PathBuf::new());
  }

  let filter_fn = |component: &Component| {
    matches!(component, Component::Normal(_) | Component::Prefix(_) | Component::RootDir)
  };
  let base_components = base.components().filter(filter_fn);
  let target_components = target.components().filter(filter_fn);
  let common_len = base_components
    .clone()
    .zip(target_components.clone())
    .take_while(|(from, to)| {
      #[cfg(target_family = "windows")]
      {
        windows_components_eq_ignore_ascii_case(from, to)
      }
      #[cfg(not(target_family = "windows"))]
      {
        from == to
      }
    })
    .count();
  let up_len = base_components.count().saturating_sub(common_len);
  #[cfg(target_family = "windows")]
  {
    let target_suffix = target_components.clone().skip(common_len);
    if target_suffix
      .clone()
      .any(|component| windows_relative_component_has_literal_slash(&component))
      || (up_len == 0
        && target_suffix.clone().next().is_some_and(|component| {
          !windows_standalone_relative_bytes_are_representable(
            component.as_os_str().as_encoded_bytes(),
          )
        }))
    {
      return RelativeOutcome::Native(target);
    }

    let suffix_count = target_suffix.clone().count();
    let component_count = up_len + suffix_count;
    let capacity = up_len * 2
      + target_suffix.clone().map(|component| component.as_os_str().len()).sum::<usize>()
      + component_count.saturating_sub(1);
    let mut relative = OsString::with_capacity(capacity);
    for _ in 0..up_len {
      push_windows_relative_component(&mut relative, OsStr::new(".."));
    }
    for component in target_suffix {
      push_windows_relative_component(&mut relative, component.as_os_str());
    }
    RelativeOutcome::Native(PathBuf::from(relative))
  }
  #[cfg(not(target_family = "windows"))]
  let relative =
    (0..up_len).map(|_| Component::ParentDir).chain(target_components.skip(common_len)).collect();
  #[cfg(not(target_family = "windows"))]
  RelativeOutcome::Native(relative)
}

fn try_relative_outcome<'a>(
  target_path: &'a Path,
  base_path: &Path,
) -> io::Result<RelativeOutcome<'a>> {
  if let Some(outcome) = relative_without_cwd(target_path, base_path) {
    return Ok(outcome);
  }

  // Slow path: avoid current_dir() for already-absolute paths.
  let base = if base_path.is_absolute() {
    normalize_for_resolution(base_path).into_owned()
  } else {
    base_path.try_absolutize()?.into_owned()
  };
  let target = if target_path.is_absolute() {
    normalize_for_resolution(target_path).into_owned()
  } else {
    target_path.try_absolutize()?.into_owned()
  };

  Ok(relative_from_resolved(base, target))
}

fn relative_outcome_with<'a, P>(
  target_path: &'a Path,
  base_path: &Path,
  cwd: P,
) -> RelativeOutcome<'a>
where
  P: AsRef<Path> + Into<PathBuf>,
{
  if let Some(outcome) = relative_without_cwd(target_path, base_path) {
    return outcome;
  }

  assert!(cwd.as_ref().is_absolute(), "explicit current directory must be absolute");

  let base = if base_path.is_absolute() {
    normalize_for_resolution(base_path).into_owned()
  } else {
    base_path.absolutize_with(cwd.as_ref()).into_owned()
  };
  let target = if target_path.is_absolute() {
    normalize_for_resolution(target_path).into_owned()
  } else {
    target_path.absolutize_with(cwd).into_owned()
  };

  if !base.is_absolute() || !target.is_absolute() {
    return RelativeOutcome::Native(normalize_for_resolution(&target).into_owned());
  }

  relative_from_resolved(base, target)
}

impl SugarPath for Path {
  fn normalize(&self) -> Cow<'_, Path> {
    normalize_path(self, TrailingSeparator::Preserve)
  }

  fn absolutize(&self) -> Cow<'_, Path> {
    self.try_absolutize().expect("failed to resolve path against the current directory")
  }

  fn try_absolutize(&self) -> io::Result<Cow<'_, Path>> {
    if self.is_absolute() {
      return Ok(normalize_for_resolution(self));
    }

    #[cfg(target_family = "windows")]
    if let Some((drive, _)) = classify_drive_relative(self) {
      let absolute = std::path::absolute(self)?;
      return Ok(Cow::Owned(normalize_owned_for_resolution(preserve_windows_drive_spelling(
        absolute, drive,
      ))));
    }

    let cwd = try_get_current_dir()?;
    Ok(self.absolutize_with(cwd))
  }

  fn absolutize_with(&self, cwd: impl AsRef<Path> + Into<PathBuf>) -> Cow<'_, Path> {
    if self.is_absolute() {
      return normalize_for_resolution(self);
    }

    assert!(cwd.as_ref().is_absolute(), "explicit current directory must be absolute");

    #[cfg(target_family = "windows")]
    if let Some((drive, _)) = classify_drive_relative(self) {
      return absolutize_drive_relative_with(self, cwd, drive);
    }

    let mut resolved: PathBuf = cwd.into();
    resolved.push(self);
    Cow::Owned(normalize_owned_for_resolution(resolved))
  }

  fn relative(&self, base: impl AsRef<Path>) -> Cow<'_, Path> {
    self.try_relative(base).expect("failed to resolve relative paths against the current directory")
  }

  fn try_relative(&self, base: impl AsRef<Path>) -> io::Result<Cow<'_, Path>> {
    try_relative_outcome(self, base.as_ref()).map(RelativeOutcome::into_cow_path)
  }

  fn relative_with(
    &self,
    base: impl AsRef<Path>,
    cwd: impl AsRef<Path> + Into<PathBuf>,
  ) -> Cow<'_, Path> {
    relative_outcome_with(self, base.as_ref(), cwd).into_cow_path()
  }

  fn to_slash(&self) -> Cow<'_, str> {
    self.try_to_slash().expect("path is not valid Unicode")
  }

  fn try_to_slash(&self) -> Option<Cow<'_, str>> {
    if std::path::MAIN_SEPARATOR == '/' {
      self.to_str().map(Cow::Borrowed)
    } else {
      self.to_str().map(|s| match replace_main_separator(s) {
        Some(replaced) => Cow::Owned(replaced),
        None => Cow::Borrowed(s),
      })
    }
  }

  fn to_slash_lossy(&self) -> Cow<'_, str> {
    if std::path::MAIN_SEPARATOR == '/' {
      self.to_string_lossy()
    } else {
      match self.to_string_lossy() {
        Cow::Borrowed(s) => match replace_main_separator(s) {
          Some(replaced) => Cow::Owned(replaced),
          None => Cow::Borrowed(s),
        },
        Cow::Owned(owned) => match replace_main_separator(&owned) {
          Some(replaced) => Cow::Owned(replaced),
          None => Cow::Owned(owned),
        },
      }
    }
  }

  fn as_path(&self) -> &Path {
    self
  }
}

/// Check whether a path needs normalization. Returns `false` for already-clean
/// paths, allowing `normalize()` to return `Cow::Borrowed` with zero allocation.
#[inline]
#[cfg(not(target_family = "windows"))]
fn needs_normalization(path: &Path, trailing: TrailingSeparator) -> bool {
  let Some(s) = path.to_str() else {
    return true;
  };
  let bytes = s.as_bytes();
  if bytes.is_empty() {
    return true;
  }
  if bytes == b"." || (trailing == TrailingSeparator::Preserve && bytes == b"./") {
    return false;
  }
  // A leading `.` needs normalization. A leading run of `..` can be clean when
  // every remaining component is normal (`...` and `.foo` are normal names).
  if bytes[0] == b'.' {
    if bytes.len() == 1 || bytes[1] == b'/' {
      return true;
    }
    if bytes[1] == b'.' && (bytes.len() == 2 || bytes[2] == b'/') {
      return !leading_parent_path_is_normalized(
        bytes,
        b'/',
        trailing == TrailingSeparator::Preserve,
      );
    }
  }
  // Trailing `/` (unless path is exactly `/`)
  if trailing == TrailingSeparator::Strip && bytes.len() > 1 && bytes[bytes.len() - 1] == b'/' {
    return true;
  }
  // memchr scan for `//`, `/.`, `/..`
  let mut offset = 0;
  while let Some(pos) = memchr(b'/', &bytes[offset..]) {
    let slash = offset + pos;
    let next = slash + 1;
    if next < bytes.len() {
      let b = bytes[next];
      // `//` — consecutive slashes
      if b == b'/' {
        return true;
      }
      // `/.` — could be `/.` or `/..`
      if b == b'.' {
        let after_dot = next + 1;
        // "/." at end or "/./"
        if after_dot >= bytes.len() || bytes[after_dot] == b'/' {
          return true;
        }
        // "/.." at end or "/../"
        if bytes[after_dot] == b'.'
          && (after_dot + 1 >= bytes.len() || bytes[after_dot + 1] == b'/')
        {
          return true;
        }
      }
    }
    offset = next;
  }
  false
}

/// Check whether a path needs normalization (Windows variant).
#[inline]
#[cfg(target_family = "windows")]
fn needs_normalization(path: &Path, trailing: TrailingSeparator) -> bool {
  let Some(s) = path.to_str() else {
    return true;
  };
  let bytes = s.as_bytes();
  if bytes.is_empty() {
    return true;
  }
  if bytes == b"." || (trailing == TrailingSeparator::Preserve && bytes == b".\\") {
    return false;
  }
  // Any forward slash means normalization is needed (gets converted to `\`)
  if memchr(b'/', bytes).is_some() {
    return true;
  }
  // UNC prefix `\\` at start — always bail out to normalizer
  if bytes.len() >= 2 && bytes[0] == b'\\' && bytes[1] == b'\\' {
    return true;
  }
  // A bare drive `X:` normalizes to `X:.`. Other drive-relative paths keep
  // their drive spelling and lexical form.
  if bytes.len() == 2 && bytes[1] == b':' && bytes[0].is_ascii_alphabetic() {
    return true; // bare `C:`
  }
  // `C:.` and `C:.\` are canonical drive-relative current-directory
  // spellings, but the same component before another segment is redundant.
  if bytes.len() > 4
    && bytes[1] == b':'
    && bytes[0].is_ascii_alphabetic()
    && bytes[2] == b'.'
    && bytes[3] == b'\\'
  {
    return true;
  }
  // A leading `.` needs normalization. A leading run of `..` can be clean when
  // every remaining component is normal (`...` and `.foo` are normal names).
  if bytes[0] == b'.' {
    if bytes.len() == 1 || bytes[1] == b'\\' {
      return true;
    }
    if bytes[1] == b'.' && (bytes.len() == 2 || bytes[2] == b'\\') {
      return !leading_parent_path_is_normalized(
        bytes,
        b'\\',
        trailing == TrailingSeparator::Preserve,
      );
    }
  }
  // Trailing `\` (unless path is `\` alone or `X:\`)
  if trailing == TrailingSeparator::Strip && bytes[bytes.len() - 1] == b'\\' {
    // `\` alone is clean
    if bytes.len() == 1 {
      return false;
    }
    // `X:\` is clean
    if bytes.len() == 3 && bytes[1] == b':' && bytes[0].is_ascii_alphabetic() {
      return false;
    }
    return true;
  }
  // memchr scan for `\\` (consecutive), `\.`, `\..`
  let mut offset = 0;
  while let Some(pos) = memchr(b'\\', &bytes[offset..]) {
    let slash = offset + pos;
    let next = slash + 1;
    if next < bytes.len() {
      let b = bytes[next];
      // `\\` — consecutive separators
      if b == b'\\' {
        return true;
      }
      // `\.` — could be `\.` or `\..`
      if b == b'.' {
        let after_dot = next + 1;
        // "\." at end or "\.\"
        if after_dot >= bytes.len() || bytes[after_dot] == b'\\' {
          return true;
        }
        // "\.." at end or "\..\"
        if bytes[after_dot] == b'.'
          && (after_dot + 1 >= bytes.len() || bytes[after_dot + 1] == b'\\')
        {
          return true;
        }
      }
    }
    offset = next;
  }
  false
}

/// Return whether an unprefixed path starting with a `..` component is already
/// in the exact spelling produced by `normalize_inner`.
///
/// A canonical path may contain one or more leading `..` components followed
/// only by normal components. Empty components, `.`, a `..` after any normal
/// component, and a trailing separator all require normalization.
#[inline]
fn leading_parent_path_is_normalized(bytes: &[u8], separator: u8, preserve_trailing: bool) -> bool {
  debug_assert!(bytes == b".." || bytes.starts_with(&[b'.', b'.', separator]));

  let mut offset = 0;
  let mut saw_normal = false;
  loop {
    let end =
      memchr(separator, &bytes[offset..]).map(|position| offset + position).unwrap_or(bytes.len());
    let component = &bytes[offset..end];

    if component == b".." {
      if saw_normal {
        return false;
      }
    } else if component.is_empty() || component == b"." {
      return false;
    } else {
      saw_normal = true;
    }

    if end == bytes.len() {
      return true;
    }
    offset = end + 1;
    if offset == bytes.len() {
      return preserve_trailing;
    }
  }
}

#[inline]
fn normalize_inner<'a>(
  mut components: Peekable<impl Iterator<Item = Component<'a>>>,
  hint_cap: usize,
  preserve_trailing: bool,
  _drive_spelling: Option<u8>,
) -> Cow<'a, Path> {
  let sep_byte = std::path::MAIN_SEPARATOR as u8;
  let mut buf: Vec<u8> = Vec::with_capacity(hint_cap);
  let mut has_root = false;
  let mut depth: usize = 0; // count of Normal segments currently in buf
  let mut need_sep = false;

  // --- Prefix (Windows only) ---
  #[cfg(target_family = "windows")]
  let prefix_len: usize;
  #[cfg(target_family = "windows")]
  let prefix_only_suffix: Option<u8>;
  #[cfg(target_family = "windows")]
  let prefix_root_is_optional: bool;
  #[cfg(target_family = "windows")]
  {
    if let Some(Component::Prefix(p)) = components.peek() {
      let (suffix, optional_root) = match p.kind() {
        std::path::Prefix::VerbatimDisk(drive) => {
          buf.extend_from_slice(b"\\\\?\\");
          buf.push(_drive_spelling.unwrap_or(drive));
          buf.push(b':');
          // `\\?\C:` has no RootDir component. A slash would add one, while
          // a dot would make Rust parse the whole prefix as generic Verbatim.
          (None, false)
        }
        std::path::Prefix::DeviceNS(device) => {
          buf.extend_from_slice(b"\\\\.\\");
          buf.extend_from_slice(device.as_encoded_bytes());
          (None, true)
        }
        std::path::Prefix::UNC(server, share) => {
          buf.extend_from_slice(b"\\\\");
          buf.extend_from_slice(server.as_encoded_bytes());
          buf.push(b'\\');
          buf.extend_from_slice(share.as_encoded_bytes());
          (Some(b'\\'), false)
        }
        std::path::Prefix::Disk(drive) => {
          buf.push(_drive_spelling.unwrap_or(drive));
          buf.push(b':');
          (Some(b'.'), false)
        }
        std::path::Prefix::Verbatim(_) | std::path::Prefix::VerbatimUNC(_, _) => {
          buf.extend_from_slice(p.as_os_str().as_encoded_bytes());
          (None, true)
        }
      };
      prefix_only_suffix = suffix;
      prefix_root_is_optional = optional_root;
      components.next();
    } else {
      prefix_only_suffix = None;
      prefix_root_is_optional = false;
    }
    prefix_len = buf.len();
  }

  // --- RootDir ---
  if matches!(components.peek(), Some(Component::RootDir)) {
    #[cfg(target_family = "windows")]
    let prefix_has_synthetic_root = buf.len() == hint_cap && prefix_root_is_optional;
    #[cfg(not(target_family = "windows"))]
    let prefix_has_synthetic_root = false;
    if !prefix_has_synthetic_root {
      buf.push(sep_byte);
    }
    has_root = true;
    components.next();
  }

  let root_end = buf.len();

  // --- Remaining components ---
  for component in components {
    match component {
      Component::Prefix(prefix) => unreachable!("Unexpected prefix for {:?}", prefix),
      Component::RootDir => unreachable!("Unexpected RootDir after initial position"),
      Component::CurDir => {}
      Component::ParentDir => {
        if depth > 0 {
          // Roll back the last Normal segment using memrchr.
          let search_region = &buf[root_end..];
          if let Some(pos) = memrchr(sep_byte, search_region) {
            buf.truncate(root_end + pos);
          } else {
            buf.truncate(root_end);
          }
          depth -= 1;
          need_sep = buf.len() > root_end;
        } else if !has_root {
          // Relative path going above start: write ".." literally
          if need_sep {
            buf.push(sep_byte);
          }
          buf.extend_from_slice(b"..");
          need_sep = true;
        }
        // else: has_root && depth == 0 → ignore (can't go above root)
      }
      Component::Normal(s) => {
        if need_sep {
          buf.push(sep_byte);
        }
        buf.extend_from_slice(s.as_encoded_bytes());
        depth += 1;
        need_sep = true;
      }
    }
  }

  #[cfg(target_family = "windows")]
  if prefix_root_is_optional && depth == 0 && !preserve_trailing {
    buf.truncate(prefix_len);
  }

  // A normal component such as `C:foo` is only a drive prefix at the start of
  // a standalone Windows path. Keep the minimal `.\` spelling when removing
  // earlier lexical components would otherwise change that component's type.
  #[cfg(target_family = "windows")]
  if prefix_len == 0 && !has_root && !windows_standalone_relative_bytes_are_representable(&buf) {
    let len = buf.len();
    buf.reserve(2);
    buf.resize(len + 2, 0);
    buf.copy_within(0..len, 2);
    buf[0] = b'.';
    buf[1] = sep_byte;
  }

  // --- Empty result → "." ---
  if buf.is_empty() {
    if preserve_trailing {
      let mut current_directory = PathBuf::from(".");
      current_directory.push("");
      return Cow::Owned(current_directory);
    }
    return Cow::Borrowed(Path::new("."));
  }

  // --- Prefix-only: preserve its component semantics or use its canonical suffix ---
  #[cfg(target_family = "windows")]
  if buf.len() == prefix_len
    && prefix_len > 0
    && let Some(suffix) = prefix_only_suffix
  {
    buf.push(suffix);
  }

  if preserve_trailing && buf.last() != Some(&sep_byte) {
    buf.push(sep_byte);
  }

  // SAFETY: `buf` was built entirely from:
  // - encoded bytes of OsStr components (valid platform encoding)
  // - ASCII separator bytes and ASCII '.' characters
  // This preserves the encoding invariants required by OsString.
  Cow::Owned(PathBuf::from(unsafe { OsString::from_encoded_bytes_unchecked(buf) }))
}

impl SugarPath for str {
  fn normalize(&self) -> Cow<'_, Path> {
    Path::new(self).normalize()
  }

  fn absolutize(&self) -> Cow<'_, Path> {
    Path::new(self).absolutize()
  }

  fn try_absolutize(&self) -> io::Result<Cow<'_, Path>> {
    Path::new(self).try_absolutize()
  }

  fn absolutize_with(&self, cwd: impl AsRef<Path> + Into<PathBuf>) -> Cow<'_, Path> {
    Path::new(self).absolutize_with(cwd)
  }

  fn relative(&self, base: impl AsRef<Path>) -> Cow<'_, Path> {
    Path::new(self).relative(base)
  }

  fn try_relative(&self, base: impl AsRef<Path>) -> io::Result<Cow<'_, Path>> {
    Path::new(self).try_relative(base)
  }

  fn relative_with(
    &self,
    base: impl AsRef<Path>,
    cwd: impl AsRef<Path> + Into<PathBuf>,
  ) -> Cow<'_, Path> {
    Path::new(self).relative_with(base, cwd)
  }

  fn to_slash(&self) -> Cow<'_, str> {
    if std::path::MAIN_SEPARATOR == '/' {
      Cow::Borrowed(self)
    } else {
      match replace_main_separator(self) {
        Some(replaced) => Cow::Owned(replaced),
        None => Cow::Borrowed(self),
      }
    }
  }

  fn try_to_slash(&self) -> Option<Cow<'_, str>> {
    Some(self.to_slash())
  }

  fn to_slash_lossy(&self) -> Cow<'_, str> {
    self.to_slash()
  }

  fn as_path(&self) -> &Path {
    Path::new(self)
  }
}

#[cfg(target_family = "windows")]
fn windows_paths_have_different_prefixes(base: &Path, target: &Path) -> bool {
  match (base.components().next(), target.components().next()) {
    (Some(Component::Prefix(base)), Some(Component::Prefix(target))) => {
      !windows_prefixes_eq_ignore_ascii_case(base.kind(), target.kind())
    }
    (Some(Component::Prefix(_)), _) | (_, Some(Component::Prefix(_))) => true,
    _ => false,
  }
}

#[cfg(target_family = "windows")]
fn windows_components_eq_ignore_ascii_case(from: &Component<'_>, to: &Component<'_>) -> bool {
  match (from, to) {
    (Component::Normal(from), Component::Normal(to)) => {
      from.as_encoded_bytes().eq_ignore_ascii_case(to.as_encoded_bytes())
    }
    (Component::Prefix(from), Component::Prefix(to)) => {
      windows_prefixes_eq_ignore_ascii_case(from.kind(), to.kind())
    }
    _ => from == to,
  }
}

#[cfg(target_family = "windows")]
fn windows_prefixes_eq_ignore_ascii_case(
  from: std::path::Prefix<'_>,
  to: std::path::Prefix<'_>,
) -> bool {
  use std::path::Prefix;

  let os_eq_ignore_ascii_case = |from: &std::ffi::OsStr, to: &std::ffi::OsStr| {
    from.as_encoded_bytes().eq_ignore_ascii_case(to.as_encoded_bytes())
  };

  match (from, to) {
    (Prefix::Disk(from), Prefix::Disk(to))
    | (Prefix::VerbatimDisk(from), Prefix::VerbatimDisk(to)) => from.eq_ignore_ascii_case(&to),
    (Prefix::UNC(from_server, from_share), Prefix::UNC(to_server, to_share))
    | (Prefix::VerbatimUNC(from_server, from_share), Prefix::VerbatimUNC(to_server, to_share)) => {
      os_eq_ignore_ascii_case(from_server, to_server)
        && os_eq_ignore_ascii_case(from_share, to_share)
    }
    (Prefix::DeviceNS(from), Prefix::DeviceNS(to))
    | (Prefix::Verbatim(from), Prefix::Verbatim(to)) => os_eq_ignore_ascii_case(from, to),
    _ => false,
  }
}

/// String-based relative path computation. Dispatches to the fast path when
/// the component spelling is already canonical, otherwise normalizes first.
fn relative_str<'a>(target: &'a str, base: &str) -> Cow<'a, str> {
  let target = target.trim_end_matches('/');
  let base = base.trim_end_matches('/');
  if needs_relative_normalization(target) || needs_relative_normalization(base) {
    Cow::Owned(relative_str_slow(target, base))
  } else {
    relative_str_fast(target, base)
  }
}

#[cfg(not(target_family = "windows"))]
#[inline]
fn common_prefix_len_case_sensitive(left: &[u8], right: &[u8]) -> usize {
  #[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
  {
    common_prefix_len_neon(left, right)
  }
  #[cfg(not(all(target_arch = "aarch64", target_feature = "neon")))]
  {
    common_prefix_len_scalar(left, right)
  }
}

#[cfg(not(target_family = "windows"))]
#[inline]
fn common_prefix_len_scalar(left: &[u8], right: &[u8]) -> usize {
  left
    .iter()
    .zip(right)
    .position(|(left, right)| left != right)
    .unwrap_or(left.len().min(right.len()))
}

#[cfg(all(not(target_family = "windows"), target_arch = "aarch64", target_feature = "neon"))]
#[inline]
fn common_prefix_len_neon(left: &[u8], right: &[u8]) -> usize {
  use std::arch::aarch64::{vceqq_u8, vld1q_u8, vminvq_u8, vst1q_u8};

  let len = left.len().min(right.len());
  let vector_end = len & !15;
  let mut offset = 0;

  while offset < vector_end {
    // SAFETY: `vector_end` is `len` rounded down to a multiple of 16, and
    // `offset` advances by exactly 16. Both loads therefore stay within the
    // shorter input, including when either slice starts at an unaligned address.
    let equal = unsafe {
      let left_chunk = vld1q_u8(left.as_ptr().add(offset));
      let right_chunk = vld1q_u8(right.as_ptr().add(offset));
      vceqq_u8(left_chunk, right_chunk)
    };
    // Equality lanes are all ones for a match and all zeroes for a mismatch.
    if unsafe { vminvq_u8(equal) } != u8::MAX {
      let mut equal_bytes = [0; 16];
      // SAFETY: `equal_bytes` has exactly enough initialized space for one
      // 16-byte vector store.
      unsafe { vst1q_u8(equal_bytes.as_mut_ptr(), equal) };
      let mismatch_bits = !u128::from_le_bytes(equal_bytes);
      debug_assert_ne!(mismatch_bits, 0);
      return offset + mismatch_bits.trailing_zeros() as usize / 8;
    }
    offset += 16;
  }

  offset + common_prefix_len_scalar(&left[offset..len], &right[offset..len])
}

/// Check if a path contains components or separators that need normalization.
/// Uses `memchr` to jump between `/` positions — most bytes in a path aren't `/`,
/// so this skips the vast majority of the input.
#[inline]
fn needs_relative_normalization(path: &str) -> bool {
  let bytes = path.as_bytes();
  if bytes.len() > 1 && bytes.last() == Some(&b'/') {
    return true;
  }
  if bytes.first() == Some(&b'.') {
    if bytes.len() == 1 || bytes.get(1) == Some(&b'/') {
      return true;
    }
    if bytes.get(1) == Some(&b'.') && (bytes.len() == 2 || bytes.get(2) == Some(&b'/')) {
      return true;
    }
  }
  let mut offset = 0;
  while let Some(pos) = memchr(b'/', &bytes[offset..]) {
    let slash = offset + pos;
    if slash + 1 < bytes.len() && bytes[slash + 1] == b'/' {
      return true;
    }
    if slash + 1 < bytes.len() && bytes[slash + 1] == b'.' {
      let after_dot = slash + 2;
      // "/." at end or "/./"
      if after_dot >= bytes.len() || bytes[after_dot] == b'/' {
        return true;
      }
      // "/.." at end or "/../"
      if bytes[after_dot] == b'.' && (after_dot + 1 >= bytes.len() || bytes[after_dot + 1] == b'/')
      {
        return true;
      }
    }
    offset = slash + 1;
  }
  false
}

/// Fast path: no normalization needed. Operates directly on `&str` slices
/// with zero intermediate allocation.
fn relative_str_fast<'a>(target: &'a str, base: &str) -> Cow<'a, str> {
  let common_byte_len = {
    #[cfg(target_family = "windows")]
    {
      target
        .as_bytes()
        .iter()
        .zip(base.as_bytes().iter())
        .take_while(|(a, b)| a.eq_ignore_ascii_case(b))
        .count()
    }
    #[cfg(not(target_family = "windows"))]
    {
      common_prefix_len_case_sensitive(target.as_bytes(), base.as_bytes())
    }
  };

  // Adjust to last '/' boundary to ensure we match full path components
  // Check if common_byte_len falls on a component boundary:
  // - exact match (both exhausted)
  // - one side exhausted and the other has '/' next (prefix match)
  let at_boundary = (common_byte_len == target.len() && common_byte_len == base.len())
    || (common_byte_len == target.len() && base.as_bytes().get(common_byte_len) == Some(&b'/'))
    || (common_byte_len == base.len() && target.as_bytes().get(common_byte_len) == Some(&b'/'));
  let common_prefix = if at_boundary {
    common_byte_len
  } else {
    memrchr(b'/', &target.as_bytes()[..common_byte_len]).unwrap_or(0)
  };

  // Count remaining base components
  let base_remaining = &base.as_bytes()[common_prefix..];
  let mut ups = 0u32;
  {
    let mut offset = 0;
    while offset < base_remaining.len() {
      if base_remaining[offset] == b'/' {
        offset += 1;
        continue;
      }
      ups += 1;
      offset = match memchr(b'/', &base_remaining[offset..]) {
        Some(pos) => offset + pos + 1,
        None => base_remaining.len(),
      };
    }
  }

  let target_suffix = target[common_prefix..].trim_start_matches('/');
  let ups = ups as usize;
  if ups == 0 {
    return Cow::Borrowed(target_suffix);
  }
  let suffix_iter = if target_suffix.is_empty() { None } else { Some(target_suffix) };
  let mut result = String::with_capacity(ups * 3 + target_suffix.len());
  std::iter::repeat_n("..", ups).chain(suffix_iter).for_each(|s| {
    if !result.is_empty() {
      result.push('/');
    }
    result.push_str(s);
  });
  Cow::Owned(result)
}

/// Slow path: normalize `.` and `..` components first, then compute relative path.
fn relative_str_slow(target: &str, base: &str) -> String {
  let target_parts = normalize_parts(target);
  let base_parts = normalize_parts(base);

  let common_len = {
    #[cfg(target_family = "windows")]
    {
      target_parts
        .iter()
        .zip(base_parts.iter())
        .take_while(|(a, b)| a.eq_ignore_ascii_case(b))
        .count()
    }
    #[cfg(not(target_family = "windows"))]
    {
      target_parts.iter().zip(base_parts.iter()).take_while(|(a, b)| a == b).count()
    }
  };

  let ups = base_parts.len() - common_len;
  let remaining = &target_parts[common_len..];

  let remaining_len: usize =
    remaining.iter().map(|s| s.len()).sum::<usize>() + remaining.len().saturating_sub(1);
  let mut result = String::with_capacity(ups * 3 + remaining_len);
  std::iter::repeat_n("..", ups).chain(remaining.iter().copied()).for_each(|s| {
    if !result.is_empty() {
      result.push('/');
    }
    result.push_str(s);
  });
  result
}

/// Split a path into normalized components, resolving `.` and `..` lexically.
fn normalize_parts(path: &str) -> StrVec<'_> {
  let mut parts = StrVec::new();
  for part in path.split('/') {
    match part {
      "" | "." => {}
      ".." => {
        parts.pop();
      }
      _ => parts.push(part),
    }
  }
  parts
}

/// Replace `\` with `/` using memchr SIMD search. Returns the input unchanged
/// (zero allocation) when no backslashes are present.
#[cfg(target_family = "windows")]
fn normalize_backslash_cow(s: &str) -> Cow<'_, str> {
  let bytes = s.as_bytes();
  let Some(first) = memchr(b'\\', bytes) else {
    return Cow::Borrowed(s);
  };
  let mut out = Vec::with_capacity(bytes.len());
  out.extend_from_slice(&bytes[..first]);
  out.push(b'/');
  let mut offset = first + 1;
  while let Some(pos) = memchr(b'\\', &bytes[offset..]) {
    out.extend_from_slice(&bytes[offset..offset + pos]);
    out.push(b'/');
    offset += pos + 1;
  }
  out.extend_from_slice(&bytes[offset..]);
  // SAFETY: input is valid UTF-8, and we only replaced `\` (single ASCII byte) with `/`
  Cow::Owned(unsafe { String::from_utf8_unchecked(out) })
}

#[cfg(all(test, not(target_family = "windows"), target_arch = "aarch64", target_feature = "neon"))]
mod common_prefix_tests {
  use super::{common_prefix_len_neon, common_prefix_len_scalar};

  fn bytes(len: usize) -> Vec<u8> {
    (0..len).map(|index| ((index * 37 + 11) % 251) as u8).collect()
  }

  #[test]
  fn neon_matches_scalar_for_lengths_and_every_mismatch() {
    for len in 0..=256 {
      let left = bytes(len);
      assert_eq!(common_prefix_len_neon(&left, &left), len, "equal input length {len}");

      for mismatch in 0..len {
        let mut right = left.clone();
        right[mismatch] ^= u8::MAX;
        assert_eq!(
          common_prefix_len_neon(&left, &right),
          common_prefix_len_scalar(&left, &right),
          "input length {len}, mismatch {mismatch}",
        );
      }
    }
  }

  #[test]
  fn neon_matches_scalar_for_every_length_pair() {
    let input = bytes(256);
    for left_len in 0..=256 {
      for right_len in 0..=256 {
        assert_eq!(
          common_prefix_len_neon(&input[..left_len], &input[..right_len]),
          common_prefix_len_scalar(&input[..left_len], &input[..right_len]),
          "left length {left_len}, right length {right_len}",
        );
      }
    }
  }

  #[test]
  fn neon_handles_all_sixteen_byte_alignment_pairs() {
    for left_offset in 0..16 {
      for right_offset in 0..16 {
        for len in 0..=256 {
          let mut left = [0xa5; 288];
          let mut right = [0x5a; 288];
          for index in 0..len {
            let value = ((index * 37 + 11) % 251) as u8;
            left[left_offset + index] = value;
            right[right_offset + index] = value;
          }
          let left = &left[left_offset..left_offset + len];
          let right = &right[right_offset..right_offset + len];
          assert_eq!(
            common_prefix_len_neon(left, right),
            len,
            "left offset {left_offset}, right offset {right_offset}, length {len}",
          );
        }
      }
    }
  }
}

fn replace_main_separator(input: &str) -> Option<String> {
  let sep = std::path::MAIN_SEPARATOR;
  let mut replaced: Option<String> = None;
  let mut segment_start = 0;

  for (idx, ch) in input.char_indices() {
    if ch == sep {
      let buf = replaced.get_or_insert_with(|| String::with_capacity(input.len()));
      buf.push_str(&input[segment_start..idx]);
      buf.push('/');
      segment_start = idx + ch.len_utf8();
    }
  }

  if let Some(mut buf) = replaced {
    buf.push_str(&input[segment_start..]);
    Some(buf)
  } else {
    None
  }
}