sark_http/uri/
path.rs

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

sark_http/uri/
path.rs
