//! Path normalization.
use core::fmt;
use core::ops::Range;
use crate::parser::str::{find_split_hole, rfind};
use crate::spec::{Spec, UriSpec};
use super::pct_case::PctCaseNormalized;
use super::{Error, NormalizationMode, NormalizationOp};
/// Path that is (possibly) not yet processed or being processed.
#[derive(Debug, Clone, Copy)]
pub(crate) enum Path<'a> {
/// The result. No more processing is needed.
Done(&'a str),
/// Not yet completely processed path.
NeedsProcessing(PathToNormalize<'a>),
}
/// Path that needs merge and/or dot segment removal.
///
/// # Invariants
///
/// If the first field (prefix field) is not `None`, it must end with a slash.
#[derive(Debug, Clone, Copy)]
pub(crate) struct PathToNormalize<'a>(Option<&'a str>, &'a str);
impl<'a> PathToNormalize<'a> {
/// Creates a `PathToNormalize` from the given single path.
#[inline]
#[must_use]
pub(crate) fn from_single_path(path: &'a str) -> Self {
Self(None, path)
}
/// Creates a `PathToNormalize` from the given base and reference paths to be resolved.
#[must_use]
pub(crate) fn from_paths_to_be_resolved(base: &'a str, reference: &'a str) -> Self {
if reference.starts_with('/') {
return Self(None, reference);
}
match rfind(base.as_bytes(), b'/') {
Some(last_slash_pos) => Self(Some(&base[..=last_slash_pos]), reference),
None => Self(None, reference),
}
}
/// Returns true if the path is empty string.
#[inline]
#[must_use]
fn is_empty(&self) -> bool {
// If `self.0` is `Some(_)`, it ends with a slash, i.e. it is not empty.
self.0.is_none() && self.1.is_empty()
}
/// Returns the length of the not yet normalized path.
#[inline]
#[must_use]
pub(super) fn len(&self) -> usize {
self.len_prefix() + self.1.len()
}
/// Returns the length of the prefix part.
///
/// Returns 0 if the prefix part is empty.
#[inline]
#[must_use]
fn len_prefix(&self) -> usize {
self.0.map_or(0, |s| s.len())
}
/// Returns a byte at the given position.
#[must_use]
fn byte_at(&self, mut i: usize) -> Option<u8> {
if let Some(prefix) = self.0 {
if i < prefix.len() {
return Some(prefix.as_bytes()[i]);
}
i -= prefix.len();
}
self.1.as_bytes().get(i).copied()
}
/// Returns the position of the next slash of the byte at the given position.
#[must_use]
fn find_next_slash(&self, scan_start: usize) -> Option<usize> {
if let Some(prefix) = self.0 {
let prefix_len = prefix.len();
if scan_start < prefix_len {
prefix[scan_start..].find('/').map(|rel| rel + scan_start)
} else {
let local_i = scan_start - prefix_len;
self.1[local_i..].find('/').map(|rel| rel + scan_start)
}
} else {
self.1[scan_start..].find('/').map(|rel| rel + scan_start)
}
}
/// Removes the `len` characters from the beginning of `self`.
fn remove_start(&mut self, len: usize) {
if let Some(prefix) = self.0 {
if let Some(suffix_trim_len) = len.checked_sub(prefix.len()) {
self.0 = None;
self.1 = &self.1[suffix_trim_len..];
} else {
self.0 = Some(&prefix[len..]);
}
} else {
self.1 = &self.1[len..];
}
}
/// Removes the prefix that are ignorable on normalization.
// Skips the prefix dot segments without leading slashes (such as `./`,
// `../`, and `../.././`).
// This is necessary because such segments should be removed with the
// FOLLOWING slashes, not leading slashes.
fn remove_ignorable_prefix(&mut self) {
while let Some(seg) = PathSegmentsIter::new(self).next() {
if seg.has_leading_slash {
// The first segment starting with a slash is not target.
break;
}
match seg.kind(self) {
SegmentKind::Dot | SegmentKind::DotDot => {
// Attempt to skip the following slash by `+ 1`.
let skip = self.len().min(seg.range.end + 1);
self.remove_start(skip);
}
SegmentKind::Normal => break,
}
}
}
}
impl PathToNormalize<'_> {
/// Writes the normalized path.
pub(crate) fn fmt_write_normalize<S: Spec, W: fmt::Write>(
&self,
f: &mut W,
op: NormalizationOp,
authority_is_present: bool,
) -> fmt::Result {
debug_assert!(
self.0.map_or(true, |s| s.ends_with('/')),
"[validity] the prefix field of `PathToNormalize` should end with a slash"
);
if self.is_empty() {
return Ok(());
}
if (op.mode == NormalizationMode::PreserveAuthoritylessRelativePath)
&& !authority_is_present
&& self.byte_at(0) != Some(b'/')
{
// Treat the path as "opaque", i.e. do not apply dot segments removal.
// See <https://github.com/lo48576/iri-string/issues/29>.
debug_assert!(
op.mode.case_pct_normalization(),
"[consistency] case/pct normalization should still be applied"
);
if let Some(prefix) = self.0 {
write!(f, "{}", PctCaseNormalized::<S>::new(prefix))?;
}
write!(f, "{}", PctCaseNormalized::<S>::new(self.1))?;
return Ok(());
}
let mut rest = *self;
// Skip the prefix dot segments without leading slashes (such as `./`,
// `../`, and `../.././`).
// This is necessary because such segments should be removed with the
// FOLLOWING slashes, not leading slashes.
rest.remove_ignorable_prefix();
if rest.is_empty() {
// Path consists of only `/.`s and `/..`s.
// In this case, if the authority component is present, the result
// should be `/`, not empty.
if authority_is_present {
f.write_char('/')?;
}
return Ok(());
}
// None: No segments are written yet.
// Some(false): Something other than `/` is already written as the path.
// Some(true): Only a `/` is written as the path.
let mut only_a_slash_is_written = None;
let mut too_deep_area_may_have_dot_segments = true;
while !rest.is_empty() && too_deep_area_may_have_dot_segments {
/// The size of the queue to track the path segments.
///
/// This should be nonzero.
const QUEUE_SIZE: usize = 8;
{
// Skip `/.` and `/..` segments at the head.
let mut skipped_len = 0;
for seg in PathSegmentsIter::new(&rest) {
match seg.kind(&rest) {
SegmentKind::Dot | SegmentKind::DotDot => {
debug_assert!(
seg.has_leading_slash,
"[consistency] `.` or `..` segments without a
leading slash have already been skipped"
);
skipped_len = seg.range.end;
}
_ => break,
}
}
rest.remove_start(skipped_len);
if rest.is_empty() {
// Finished with a dot segment.
// The last `/.` or `/..` should be replaced to `/`.
if !authority_is_present && (only_a_slash_is_written == Some(true)) {
// Insert a dot segment to break the prefix `//`.
// Without this, the path starts with `//` and it may
// be confused with the prefix of an authority.
f.write_str(".//")?;
} else {
f.write_char('/')?;
}
break;
}
}
let mut queue: [Option<&'_ str>; QUEUE_SIZE] = Default::default();
let mut level: usize = 0;
let mut first_segment_has_leading_slash = false;
// Find higher path segments.
let mut end = 0;
for seg in PathSegmentsIter::new(&rest) {
let kind = seg.kind(&rest);
match kind {
SegmentKind::Dot => {
too_deep_area_may_have_dot_segments = true;
}
SegmentKind::DotDot => {
level = level.saturating_sub(1);
too_deep_area_may_have_dot_segments = true;
if level < queue.len() {
queue[level] = None;
}
}
SegmentKind::Normal => {
if level < queue.len() {
queue[level] = Some(seg.segment(&rest));
too_deep_area_may_have_dot_segments = false;
end = seg.range.end;
if level == 0 {
first_segment_has_leading_slash = seg.has_leading_slash;
}
}
level += 1;
}
}
}
// Write the path segments as possible, and update the internal state.
for segname in queue.iter().flatten() {
Self::emit_segment::<S, _>(
f,
&mut only_a_slash_is_written,
first_segment_has_leading_slash,
segname,
authority_is_present,
op,
)?;
}
rest.remove_start(end);
}
if !rest.is_empty() {
// No need of searching dot segments anymore.
assert!(
!too_deep_area_may_have_dot_segments,
"[consistency] loop condition of the previous loop"
);
// Apply only normalization (if needed).
for seg in PathSegmentsIter::new(&rest) {
assert_eq!(
seg.kind(&rest),
SegmentKind::Normal,
"[consistency] already confirmed that there are no more dot segments"
);
let segname = seg.segment(&rest);
Self::emit_segment::<S, _>(
f,
&mut only_a_slash_is_written,
seg.has_leading_slash,
segname,
authority_is_present,
op,
)?;
}
}
Ok(())
}
/// Emits a non-dot segment and update the current state.
//
// `first_segment_has_leading_slash` can be any value if the segment is not the first one.
fn emit_segment<S: Spec, W: fmt::Write>(
f: &mut W,
only_a_slash_is_written: &mut Option<bool>,
first_segment_has_leading_slash: bool,
segname: &str,
authority_is_present: bool,
op: NormalizationOp,
) -> fmt::Result {
// Omit the leading slash of the segment only if the segment is
// the first one and marked as not having a leading slash.
match *only_a_slash_is_written {
None => {
// First segment.
// This pass can be possible if `./` is repeated `QUEUE_SIZE`
// times at the beginning.
if first_segment_has_leading_slash {
f.write_char('/')?;
}
*only_a_slash_is_written =
Some(first_segment_has_leading_slash && segname.is_empty());
}
Some(only_a_slash) => {
if only_a_slash && !authority_is_present {
// Apply serialization like WHATWG URL Standard.
// This prevents `<scheme=foo>:<path=//bar>` from written as
// `foo://bar`, which is interpreted as
// `<scheme=foo>://<authority=bar>`. Prepending `./`, the
// serialization result would be `foo:/.//bar`, which is safe.
f.write_str("./")?;
*only_a_slash_is_written = Some(false);
}
f.write_char('/')?;
}
}
// Write the segment name.
if op.mode.case_pct_normalization() {
write!(f, "{}", PctCaseNormalized::<S>::new(segname))
} else {
f.write_str(segname)
}
}
/// Checks if the path is normalizable by RFC 3986 algorithm when the authority is absent.
///
/// Returns `Ok(())` when normalizable, returns `Err(_)` if not.
pub(crate) fn ensure_rfc3986_normalizable_with_authority_absent(&self) -> Result<(), Error> {
/// A sink to get the prefix of the input.
#[derive(Default)]
struct PrefixRetriever {
/// The buffer to remember the prefix of the input.
buf: [u8; 3],
/// The next write position in the buffer.
cursor: usize,
}
impl PrefixRetriever {
/// Returns the read prefix data.
#[inline]
#[must_use]
fn as_bytes(&self) -> &[u8] {
&self.buf[..self.cursor]
}
}
impl fmt::Write for PrefixRetriever {
fn write_str(&mut self, s: &str) -> fmt::Result {
if !s.is_empty() && (self.cursor >= self.buf.len()) {
// Enough bytes are read.
return Err(fmt::Error);
}
self.buf[self.cursor..]
.iter_mut()
.zip(s.bytes())
.for_each(|(dest, src)| *dest = src);
self.cursor = self.cursor.saturating_add(s.len()).min(self.buf.len());
Ok(())
}
}
let mut prefix = PrefixRetriever::default();
// The failure of this write indicates more than 3 characters are read.
// This is safe to ignore since the check needs only 3 characters.
let _ = self.fmt_write_normalize::<UriSpec, _>(
&mut prefix,
NormalizationOp {
mode: NormalizationMode::None,
},
// Assume the authority is absent.
false,
);
if prefix.as_bytes() == b"/./" {
Err(Error::new())
} else {
Ok(())
}
}
}
/// Characteristic of a path.
#[derive(Debug, Clone, Copy)]
pub(crate) enum PathCharacteristic {
/// Absolute path, not special.
CommonAbsolute,
/// Absolute path, not special.
CommonRelative,
/// The first path segment of the relative path has one or more colon characters.
RelativeFirstSegmentHasColon,
/// The path starts with the double slash.
StartsWithDoubleSlash,
}
impl PathCharacteristic {
/// Returns true if the path is absolute.
#[inline]
#[must_use]
pub(crate) fn is_absolute(self) -> bool {
matches!(self, Self::CommonAbsolute | Self::StartsWithDoubleSlash)
}
/// Returns the characteristic of the path.
pub(crate) fn from_path_to_display<S: Spec>(
path: &PathToNormalize<'_>,
op: NormalizationOp,
authority_is_present: bool,
) -> Self {
/// Dummy writer to get necessary values.
#[derive(Default, Clone, Copy)]
struct Writer {
/// Result.
result: Option<PathCharacteristic>,
/// Whether the normalized path is absolute.
is_absolute: Option<bool>,
}
impl fmt::Write for Writer {
fn write_str(&mut self, mut s: &str) -> fmt::Result {
if self.result.is_some() {
// Nothing more to do.
return Err(fmt::Error);
}
while !s.is_empty() {
if self.is_absolute.is_none() {
// The first input.
match s.strip_prefix('/') {
Some(rest) => {
self.is_absolute = Some(true);
s = rest;
}
None => {
self.is_absolute = Some(false);
}
}
continue;
}
if self.is_absolute == Some(true) {
let result = if s.starts_with('/') {
PathCharacteristic::StartsWithDoubleSlash
} else {
PathCharacteristic::CommonAbsolute
};
self.result = Some(result);
return Err(fmt::Error);
}
// Processing the first segment of the relative path.
match find_split_hole(s, b'/') {
Some((first_seg, _rest)) => {
let result = if first_seg.contains(':') {
PathCharacteristic::RelativeFirstSegmentHasColon
} else {
PathCharacteristic::CommonRelative
};
self.result = Some(result);
return Err(fmt::Error);
}
None => {
// `s` might not be the complete first segment.
if s.contains(':') {
self.result =
Some(PathCharacteristic::RelativeFirstSegmentHasColon);
return Err(fmt::Error);
}
break;
}
}
}
Ok(())
}
}
let mut writer = Writer::default();
match path.fmt_write_normalize::<S, _>(&mut writer, op, authority_is_present) {
// Empty path.
Ok(_) => PathCharacteristic::CommonRelative,
Err(_) => writer
.result
.expect("[consistency] the formatting quits early by `Err` when the check is done"),
}
}
}
/// Path segment kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum SegmentKind {
/// `.` or the equivalents.
Dot,
/// `..` or the equivalents.
DotDot,
/// Other normal (not special) segments.
Normal,
}
impl SegmentKind {
/// Creates a new `SegmentKind` from the given segment name.
#[must_use]
fn from_segment(s: &str) -> Self {
match s {
"." | "%2E" | "%2e" => SegmentKind::Dot,
".." | ".%2E" | ".%2e" | "%2E." | "%2E%2E" | "%2E%2e" | "%2e." | "%2e%2E"
| "%2e%2e" => SegmentKind::DotDot,
_ => SegmentKind::Normal,
}
}
}
/// A segment with optional leading slash.
#[derive(Debug, Clone)]
struct PathSegment {
/// Presence of a leading slash.
has_leading_slash: bool,
/// Range of the segment name (without any slashes).
range: Range<usize>,
}
impl PathSegment {
/// Returns the segment without any slashes.
#[inline]
#[must_use]
fn segment<'a>(&self, path: &PathToNormalize<'a>) -> &'a str {
if let Some(prefix) = path.0 {
let prefix_len = prefix.len();
if self.range.end <= prefix_len {
&prefix[self.range.clone()]
} else {
let range = (self.range.start - prefix_len)..(self.range.end - prefix_len);
&path.1[range]
}
} else {
&path.1[self.range.clone()]
}
}
/// Returns the segment kind.
#[inline]
#[must_use]
fn kind(&self, path: &PathToNormalize<'_>) -> SegmentKind {
SegmentKind::from_segment(self.segment(path))
}
}
/// Iterator of path segments.
struct PathSegmentsIter<'a> {
/// Path.
path: &'a PathToNormalize<'a>,
/// Current cursor position.
cursor: usize,
}
impl<'a> PathSegmentsIter<'a> {
/// Creates a new iterator of path segments.
#[inline]
#[must_use]
fn new(path: &'a PathToNormalize<'a>) -> Self {
Self { path, cursor: 0 }
}
}
impl Iterator for PathSegmentsIter<'_> {
type Item = PathSegment;
fn next(&mut self) -> Option<Self::Item> {
let path_len = self.path.len();
if self.cursor >= path_len {
return None;
}
let has_leading_slash = self.path.byte_at(self.cursor) == Some(b'/');
let prefix_len = self.path.len_prefix();
if (prefix_len != 0) && (self.cursor == prefix_len - 1) {
debug_assert!(has_leading_slash);
let end = self.path.1.find('/').unwrap_or(self.path.1.len()) + prefix_len;
self.cursor = end;
return Some(PathSegment {
has_leading_slash,
range: prefix_len..end,
});
}
if has_leading_slash {
// Skip the leading slash.
self.cursor += 1;
};
let start = self.cursor;
self.cursor = self.path.find_next_slash(self.cursor).unwrap_or(path_len);
Some(PathSegment {
has_leading_slash,
range: start..self.cursor,
})
}
}
