sark_http/uri/
path.rs

1use std::num::NonZero;
2
3use crate::{field::metadata::map::record, uri::Source};
4
5const LANE: usize = 16;
6
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub enum Error {
9    Byte {
10        at: usize,
11        byte: u8,
12    },
13    Escape {
14        at: usize,
15        first: Option<u8>,
16        second: Option<u8>,
17    },
18}
19
20#[derive(Clone, Copy)]
21pub(crate) struct Plan {
22    end: usize,
23    query: Option<NonZero<usize>>,
24}
25
26impl Plan {
27    pub(crate) const fn end(self) -> usize {
28        self.end
29    }
30
31    pub(crate) const fn query(self) -> Option<NonZero<usize>> {
32        self.query
33    }
34
35    pub(crate) fn path_end(self) -> usize {
36        match self.query {
37            None => self.end,
38            Some(start) => start.get() - 1,
39        }
40    }
41}
42
43pub(crate) enum Outcome {
44    Complete(Plan),
45    Incomplete,
46    Invalid(Error),
47}
48
49#[repr(transparent)]
50pub(crate) struct Scan<'a>(&'a [u8]);
51
52impl<'a> Scan<'a> {
53    pub(crate) const fn new(bytes: &'a [u8]) -> Self {
54        Self(bytes)
55    }
56
57    pub(crate) fn prefix(self) -> Outcome {
58        match run::<true>(self.0, |at, query| self.locate(at, query)) {
59            Ok(Stage::Found(plan)) => Outcome::Complete(plan),
60            Ok(Stage::Exhausted(_)) => Outcome::Incomplete,
61            Err(error) => Outcome::Invalid(error),
62        }
63    }
64
65    /// Parses the whole input; reaching its end is a completed plan.
66    pub(crate) fn complete(self) -> Result<Plan, Error> {
67        let len = self.0.len();
68        match run::<false>(self.0, |at, query| self.locate(at, query))? {
69            Stage::Found(plan) => Ok(plan),
70            Stage::Exhausted(query) => Ok(Plan { end: len, query }),
71        }
72    }
73
74    fn locate(&self, start: usize, query: bool) -> Progress {
75        let Some(input) = self.0.get(start..) else {
76            return Progress::End;
77        };
78        let (lanes, tail) = input.as_chunks::<LANE>();
79        let Some((first, rest)) = lanes.split_first() else {
80            return Progress::Tail(start);
81        };
82        if let Some(offset) = Self::first(Self::mask(*first, query)) {
83            return Progress::Special(start + offset);
84        }
85        let mut index = start + LANE;
86        let (groups, rest) = rest.as_chunks::<4>();
87        for group in groups {
88            let masks = group.map(|chunk| Self::mask(chunk, query));
89            if masks[0] | masks[1] | masks[2] | masks[3] != 0 {
90                for (lane, mask) in masks.into_iter().enumerate() {
91                    if let Some(offset) = Self::first(mask) {
92                        return Progress::Special(index + lane * LANE + offset);
93                    }
94                }
95            }
96            index += 4 * LANE;
97        }
98        for lane in rest {
99            if let Some(offset) = Self::first(Self::mask(*lane, query)) {
100                return Progress::Special(index + offset);
101            }
102            index += LANE;
103        }
104        if tail.is_empty() {
105            Progress::End
106        } else {
107            Progress::Tail(index)
108        }
109    }
110
111    /// Offset of the first nonzero byte in a little-endian lane bitmap.
112    fn first(bits: u128) -> Option<usize> {
113        (bits != 0).then(|| bits.trailing_zeros() as usize / u8::BITS as usize)
114    }
115
116    fn mask(chunk: [u8; LANE], query: bool) -> u128 {
117        u128::from_le_bytes(chunk.map(|byte| u8::from(!Self::is_path(byte, query)).wrapping_neg()))
118    }
119
120    fn is_path(byte: u8, query: bool) -> bool {
121        byte.is_ascii_alphabetic()
122            | (byte.wrapping_sub(b'&') <= b';' - b'&')
123            | (byte == b'!')
124            | (byte == b'$')
125            | (byte == b'=')
126            | (byte == b'@')
127            | (byte == b'_')
128            | (byte == b'~')
129            | (query & (byte == b'?'))
130    }
131}
132
133/// Parses a complete path/query without joining its borrowed segments.
134pub(crate) fn complete_span(value: record::Span<'_>) -> Result<Plan, Error> {
135    let (first, second) = value.parts();
136    if second.is_empty() {
137        return Scan::new(first).complete();
138    }
139    if first.is_empty() {
140        return Scan::new(second).complete();
141    }
142    match run::<false>(value, |at, _| Progress::Tail(at))? {
143        Stage::Found(plan) => Ok(plan),
144        Stage::Exhausted(query) => Ok(Plan {
145            end: value.len(),
146            query,
147        }),
148    }
149}
150
151fn run<'a, const PREFIX: bool>(
152    source: impl Source<'a>,
153    locate: impl Fn(usize, bool) -> Progress,
154) -> Result<Stage, Error> {
155    let mut cursor = 0;
156    let mut query = None;
157    loop {
158        let in_query = query.is_some();
159        let at = match locate(cursor, in_query) {
160            Progress::Special(at) => at,
161            Progress::Tail(at) => {
162                let Some(tail) = source.sub(at, source.len()) else {
163                    return Ok(Stage::Exhausted(query));
164                };
165                let Some(offset) = tail
166                    .span()
167                    .iter()
168                    .position(|byte| !Scan::is_path(*byte, in_query))
169                else {
170                    return Ok(Stage::Exhausted(query));
171                };
172                at + offset
173            }
174            Progress::End => return Ok(Stage::Exhausted(query)),
175        };
176        let Some(byte) = source.get(at) else {
177            return Ok(Stage::Exhausted(query));
178        };
179        match byte {
180            b' ' if PREFIX => return Ok(Stage::Found(Plan { end: at, query })),
181            b'?' if !in_query => {
182                cursor = at + 1;
183                query = NonZero::new(cursor);
184            }
185            b'%' => match escape(source, at) {
186                Ok(next) => cursor = next,
187                Err(Error::Escape { first, second, .. })
188                    if PREFIX
189                        && second.is_none()
190                        && first.is_none_or(|byte| byte.is_ascii_hexdigit()) =>
191                {
192                    return Ok(Stage::Exhausted(query));
193                }
194                Err(error) => return Err(error),
195            },
196            byte => return Err(Error::Byte { at, byte }),
197        }
198    }
199}
200
201fn escape<'a>(source: impl Source<'a>, at: usize) -> Result<usize, Error> {
202    let first = at.checked_add(1).and_then(|index| source.get(index));
203    let second = at.checked_add(2).and_then(|index| source.get(index));
204    if first.is_some_and(|byte| byte.is_ascii_hexdigit())
205        && second.is_some_and(|byte| byte.is_ascii_hexdigit())
206    {
207        return at.checked_add(3).ok_or(Error::Escape { at, first, second });
208    }
209    Err(Error::Escape { at, first, second })
210}
211
212enum Progress {
213    Special(usize),
214    Tail(usize),
215    End,
216}
217
218/// Terminal of one scan: a located terminator, or the input running out.
219enum Stage {
220    Found(Plan),
221    Exhausted(Option<NonZero<usize>>),
222}
223
224const _: () = assert!(core::mem::size_of::<Scan<'_>>() == core::mem::size_of::<&[u8]>());
225const _: () = assert!(core::mem::size_of::<Plan>() == 2 * core::mem::size_of::<usize>());
sark_http/uri/path.rs

sark_http/uri/
path.rs
