TLA Line data Source code
1 : //
2 : // Copyright (c) 2016-2019 Vinnie Falco (vinnie dot falco at gmail dot com)
3 : // Copyright (c) 2022 Alan de Freitas (alandefreitas@gmail.com)
4 : //
5 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
6 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 : //
8 : // Official repository: https://github.com/boostorg/url
9 : //
10 :
11 :
12 : #include <boost/url/detail/config.hpp>
13 : #include <boost/url/decode_view.hpp>
14 : #include <boost/url/detail/decode.hpp>
15 : #include <boost/url/segments_encoded_view.hpp>
16 : #include <boost/url/grammar/ci_string.hpp>
17 : #include <boost/url/grammar/lut_chars.hpp>
18 : #include <boost/assert.hpp>
19 : #include <boost/core/ignore_unused.hpp>
20 : #include <cstring>
21 : #include <boost/url/detail/normalize.hpp>
22 :
23 : namespace boost {
24 : namespace urls {
25 : namespace detail {
26 :
27 : void
28 HIT 7864 : pop_encoded_front(
29 : core::string_view& s,
30 : char& c,
31 : std::size_t& n) noexcept
32 : {
33 7864 : if(s.front() != '%')
34 : {
35 7698 : c = s.front();
36 7698 : s.remove_prefix(1);
37 : }
38 : else
39 : {
40 166 : detail::decode_unsafe(
41 : &c,
42 : &c + 1,
43 : s.substr(0, 3));
44 166 : s.remove_prefix(3);
45 : }
46 7864 : ++n;
47 7864 : }
48 :
49 : int
50 64 : compare_encoded(
51 : core::string_view lhs,
52 : core::string_view rhs) noexcept
53 : {
54 64 : std::size_t n0 = 0;
55 64 : std::size_t n1 = 0;
56 64 : char c0 = 0;
57 64 : char c1 = 0;
58 64 : while(
59 486 : !lhs.empty() &&
60 228 : !rhs.empty())
61 : {
62 215 : pop_encoded_front(lhs, c0, n0);
63 215 : pop_encoded_front(rhs, c1, n1);
64 215 : if (c0 < c1)
65 18 : return -1;
66 197 : if (c1 < c0)
67 3 : return 1;
68 : }
69 43 : n0 += detail::decode_bytes_unsafe(lhs);
70 43 : n1 += detail::decode_bytes_unsafe(rhs);
71 43 : if (n0 == n1)
72 22 : return 0;
73 21 : if (n0 < n1)
74 8 : return -1;
75 13 : return 1;
76 : }
77 :
78 : int
79 28 : compare_encoded_query(
80 : core::string_view lhs,
81 : core::string_view rhs) noexcept
82 : {
83 : static constexpr
84 : grammar::lut_chars
85 : query_compare_exception_lut = "&=+";
86 :
87 28 : std::size_t n0 = 0;
88 28 : std::size_t n1 = 0;
89 28 : char c0 = 0;
90 28 : char c1 = 0;
91 28 : while(
92 254 : !lhs.empty() &&
93 122 : !rhs.empty())
94 : {
95 121 : bool const lhs_was_decoded = lhs.front() != '%';
96 121 : bool const rhs_was_decoded = rhs.front() != '%';
97 121 : pop_encoded_front(lhs, c0, n0);
98 121 : pop_encoded_front(rhs, c1, n1);
99 121 : if (c0 < c1)
100 2 : return -1;
101 119 : if (c1 < c0)
102 12 : return 1;
103 : // The decoded chars are the same, but
104 : // are these query exceptions that have
105 : // different meanings when decoded?
106 107 : if (query_compare_exception_lut(c0))
107 : {
108 : // If so, we only continue if both
109 : // chars were decoded or encoded
110 : // the same way.
111 40 : if (lhs_was_decoded == rhs_was_decoded)
112 37 : continue;
113 : // Otherwise, we return a value != 0
114 : // because these chars are not equal.
115 : // If rhs was the decoded one, it contains
116 : // an ascii char higher than '%'
117 3 : if (rhs_was_decoded)
118 2 : return -1;
119 : else
120 1 : return 1;
121 : }
122 : }
123 11 : n0 += detail::decode_bytes_unsafe(lhs);
124 11 : n1 += detail::decode_bytes_unsafe(rhs);
125 11 : if (n0 == n1)
126 9 : return 0;
127 2 : if (n0 < n1)
128 1 : return -1;
129 1 : return 1;
130 : }
131 :
132 : void
133 1552 : digest_encoded(
134 : core::string_view s,
135 : fnv_1a& hasher) noexcept
136 : {
137 1552 : char c = 0;
138 1552 : std::size_t n = 0;
139 2060 : while(!s.empty())
140 : {
141 508 : pop_encoded_front(s, c, n);
142 508 : hasher.put(c);
143 : }
144 1552 : }
145 :
146 : int
147 183 : ci_compare_encoded(
148 : core::string_view lhs,
149 : core::string_view rhs) noexcept
150 : {
151 183 : std::size_t n0 = 0;
152 183 : std::size_t n1 = 0;
153 183 : char c0 = 0;
154 183 : char c1 = 0;
155 183 : while (
156 4799 : !lhs.empty() &&
157 2317 : !rhs.empty())
158 : {
159 2311 : pop_encoded_front(lhs, c0, n0);
160 2311 : pop_encoded_front(rhs, c1, n1);
161 2311 : c0 = grammar::to_lower(c0);
162 2311 : c1 = grammar::to_lower(c1);
163 2311 : if (c0 < c1)
164 10 : return -1;
165 2301 : if (c1 < c0)
166 2 : return 1;
167 : }
168 171 : n0 += detail::decode_bytes_unsafe(lhs);
169 171 : n1 += detail::decode_bytes_unsafe(rhs);
170 171 : if (n0 == n1)
171 164 : return 0;
172 7 : if (n0 < n1)
173 1 : return -1;
174 6 : return 1;
175 : }
176 :
177 : void
178 388 : ci_digest_encoded(
179 : core::string_view s,
180 : fnv_1a& hasher) noexcept
181 : {
182 388 : char c = 0;
183 388 : std::size_t n = 0;
184 2450 : while(!s.empty())
185 : {
186 2062 : pop_encoded_front(s, c, n);
187 2062 : c = grammar::to_lower(c);
188 2062 : hasher.put(c);
189 : }
190 388 : }
191 :
192 : int
193 46 : compare(
194 : core::string_view lhs,
195 : core::string_view rhs) noexcept
196 : {
197 46 : auto rlen = (std::min)(lhs.size(), rhs.size());
198 104 : for (std::size_t i = 0; i < rlen; ++i)
199 : {
200 79 : char c0 = lhs[i];
201 79 : char c1 = rhs[i];
202 79 : if (c0 < c1)
203 13 : return -1;
204 66 : if (c1 < c0)
205 8 : return 1;
206 : }
207 25 : if ( lhs.size() == rhs.size() )
208 4 : return 0;
209 21 : if ( lhs.size() < rhs.size() )
210 8 : return -1;
211 13 : return 1;
212 : }
213 :
214 : int
215 226 : ci_compare(
216 : core::string_view lhs,
217 : core::string_view rhs) noexcept
218 : {
219 226 : auto rlen = (std::min)(lhs.size(), rhs.size());
220 1155 : for (std::size_t i = 0; i < rlen; ++i)
221 : {
222 936 : char c0 = grammar::to_lower(lhs[i]);
223 936 : char c1 = grammar::to_lower(rhs[i]);
224 936 : if (c0 < c1)
225 6 : return -1;
226 930 : if (c1 < c0)
227 1 : return 1;
228 : }
229 219 : if ( lhs.size() == rhs.size() )
230 211 : return 0;
231 8 : if ( lhs.size() < rhs.size() )
232 6 : return -1;
233 2 : return 1;
234 : }
235 :
236 : void
237 388 : ci_digest(
238 : core::string_view s,
239 : fnv_1a& hasher) noexcept
240 : {
241 1118 : for (char c: s)
242 : {
243 730 : c = grammar::to_lower(c);
244 730 : hasher.put(c);
245 : }
246 388 : }
247 :
248 : std::size_t
249 1107 : remove_dot_segments(
250 : char* dest0,
251 : char const* end,
252 : core::string_view input) noexcept
253 : {
254 : // 1. The input buffer `s` is initialized with
255 : // the now-appended path components and the
256 : // output buffer `dest0` is initialized to
257 : // the empty string.
258 1107 : char* dest = dest0;
259 1107 : bool const is_absolute = input.starts_with('/');
260 :
261 : // Step 2 is a loop through 5 production rules:
262 : // https://www.rfc-editor.org/rfc/rfc3986#section-5.2.4
263 : //
264 : // There are no transitions between all rules,
265 : // which enables some optimizations.
266 : //
267 : // Initial:
268 : // - Rule A: handle initial dots
269 : // If the input buffer begins with a
270 : // prefix of "../" or "./", then remove
271 : // that prefix from the input buffer.
272 : // Rule A can only happen at the beginning.
273 : // Errata 4547: Keep "../" in the beginning
274 : // https://www.rfc-editor.org/errata/eid4547
275 : //
276 : // Then:
277 : // - Rule D: ignore a final ".." or "."
278 : // if the input buffer consists only of "."
279 : // or "..", then remove that from the input
280 : // buffer.
281 : // Rule D can only happen after Rule A because:
282 : // - B and C write "/" to the input
283 : // - E writes "/" to input or returns
284 : //
285 : // Then:
286 : // - Rule B: ignore ".": write "/" to the input
287 : // - Rule C: apply "..": remove seg and write "/"
288 : // - Rule E: copy complete segment
289 : auto append =
290 1945 : [](char*& first, char const* last, core::string_view in)
291 : {
292 : // append `in` to `dest`
293 1945 : BOOST_ASSERT(in.size() <= std::size_t(last - first));
294 1945 : std::memmove(first, in.data(), in.size());
295 1945 : first += in.size();
296 : ignore_unused(last);
297 1945 : };
298 :
299 12503 : auto dot_starts_with = [](
300 : core::string_view str, core::string_view dots, std::size_t& n)
301 : {
302 : // starts_with for encoded/decoded dots
303 : // or decoded otherwise. return how many
304 : // chars in str match the dots
305 12503 : n = 0;
306 21903 : for (char c: dots)
307 : {
308 21257 : if (str.starts_with(c))
309 : {
310 9400 : str.remove_prefix(1);
311 9400 : ++n;
312 9400 : continue;
313 : }
314 :
315 : // In the general case, we would need to
316 : // check if the next char is an encoded
317 : // dot.
318 : // However, an encoded dot in `str`
319 : // would have already been decoded in
320 : // url_base::normalize_path().
321 : // This needs to be undone if
322 : // `remove_dot_segments` is used in a
323 : // different context.
324 : // if (str.size() > 2 &&
325 : // c == '.'
326 : // &&
327 : // str[0] == '%' &&
328 : // str[1] == '2' &&
329 : // (str[2] == 'e' ||
330 : // str[2] == 'E'))
331 : // {
332 : // str.remove_prefix(3);
333 : // n += 3;
334 : // continue;
335 : // }
336 :
337 11857 : n = 0;
338 11857 : return false;
339 : }
340 646 : return true;
341 : };
342 :
343 6260 : auto dot_equal = [&dot_starts_with](
344 : core::string_view str, core::string_view dots)
345 : {
346 6260 : std::size_t n = 0;
347 6260 : dot_starts_with(str, dots, n);
348 6260 : return n == str.size();
349 1107 : };
350 :
351 : // Rule A
352 : std::size_t n;
353 1129 : while (!input.empty())
354 : {
355 1003 : if (dot_starts_with(input, "../", n))
356 : {
357 : // Errata 4547
358 4 : append(dest, end, "../");
359 4 : input.remove_prefix(n);
360 4 : continue;
361 : }
362 999 : else if (!dot_starts_with(input, "./", n))
363 : {
364 981 : break;
365 : }
366 18 : input.remove_prefix(n);
367 : }
368 :
369 : // Rule D
370 1107 : if( dot_equal(input, "."))
371 : {
372 127 : input = {};
373 : }
374 980 : else if( dot_equal(input, "..") )
375 : {
376 : // Errata 4547
377 3 : append(dest, end, "..");
378 3 : input = {};
379 : }
380 :
381 : // 2. While the input buffer is not empty,
382 : // loop as follows:
383 3209 : while (!input.empty())
384 : {
385 : // Rule B
386 2147 : bool const is_dot_seg = dot_starts_with(input, "/./", n);
387 2147 : if (is_dot_seg)
388 : {
389 43 : input.remove_prefix(n - 1);
390 43 : continue;
391 : }
392 :
393 2104 : bool const is_final_dot_seg = dot_equal(input, "/.");
394 2104 : if (is_final_dot_seg)
395 : {
396 : // We can't remove "." from a core::string_view
397 : // So what we do here is equivalent to
398 : // replacing s with '/' as required
399 : // in Rule B and executing the next
400 : // iteration, which would append this
401 : // '/' to the output, as required by
402 : // Rule E
403 10 : append(dest, end, input.substr(0, 1));
404 10 : input = {};
405 10 : break;
406 : }
407 :
408 : // Rule C
409 2094 : bool const is_dotdot_seg = dot_starts_with(input, "/../", n);
410 2094 : if (is_dotdot_seg)
411 : {
412 227 : core::string_view cur_out(dest0, dest - dest0);
413 227 : std::size_t p = cur_out.find_last_of('/');
414 227 : bool const has_multiple_segs = p != core::string_view::npos;
415 227 : if (has_multiple_segs)
416 : {
417 : // output has multiple segments
418 : // "erase" [p, end] if not "/.."
419 147 : core::string_view last_seg(dest0 + p, dest - (dest0 + p));
420 147 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
421 147 : if (!prev_is_dotdot_seg)
422 : {
423 136 : dest = dest0 + p;
424 : }
425 : else
426 : {
427 11 : append(dest, end, "/..");
428 : }
429 : }
430 80 : else if (dest0 != dest)
431 : {
432 : // Only one segment in the output: remove it
433 30 : core::string_view last_seg(dest0, dest - dest0);
434 30 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
435 30 : if (!prev_is_dotdot_seg)
436 : {
437 28 : dest = dest0;
438 28 : if (!is_absolute)
439 : {
440 28 : input.remove_prefix(1);
441 : }
442 : }
443 : else
444 : {
445 2 : append(dest, end, "/..");
446 : }
447 : }
448 : else
449 : {
450 : // Output is empty
451 50 : if (is_absolute)
452 : {
453 50 : append(dest, end, "/..");
454 : }
455 : else
456 : {
457 : // AFREITAS: Although we have no formal proof
458 : // for that, the output can't be relative
459 : // and empty at this point because relative
460 : // paths will fall in the `dest0 != dest`
461 : // case above of this rule C and then the
462 : // general case of rule E for "..".
463 MIS 0 : append(dest, end, "..");
464 : }
465 : }
466 HIT 227 : input.remove_prefix(n - 1);
467 227 : continue;
468 227 : }
469 :
470 1867 : bool const is_final_dotdot_seg = dot_equal(input, "/..");
471 1867 : if (is_final_dotdot_seg)
472 : {
473 35 : core::string_view cur_out(dest0, dest - dest0);
474 35 : std::size_t p = cur_out.find_last_of('/');
475 35 : bool const has_multiple_segs = p != core::string_view::npos;
476 35 : if (has_multiple_segs)
477 : {
478 : // output has multiple segments
479 : // "erase" [p, end] if not "/.."
480 21 : core::string_view last_seg(dest0 + p, dest - (dest0 + p));
481 21 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
482 21 : if (!prev_is_dotdot_seg)
483 : {
484 17 : dest = dest0 + p;
485 17 : append(dest, end, "/");
486 : }
487 : else
488 : {
489 4 : append(dest, end, "/..");
490 : }
491 : }
492 14 : else if (dest0 != dest)
493 : {
494 : // Only one segment in the output: remove it
495 4 : core::string_view last_seg(dest0, dest - dest0);
496 4 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
497 4 : if (!prev_is_dotdot_seg) {
498 2 : dest = dest0;
499 : }
500 : else
501 : {
502 2 : append(dest, end, "/..");
503 : }
504 : }
505 : else
506 : {
507 : // Output is empty: append dotdot
508 10 : if (is_absolute)
509 : {
510 10 : append(dest, end, "/..");
511 : }
512 : else
513 : {
514 : // AFREITAS: Although we have no formal proof
515 : // for that, the output can't be relative
516 : // and empty at this point because relative
517 : // paths will fall in the `dest0 != dest`
518 : // case above of this rule C and then the
519 : // general case of rule E for "..".
520 MIS 0 : append(dest, end, "..");
521 : }
522 : }
523 HIT 35 : input = {};
524 35 : break;
525 : }
526 :
527 : // Rule E
528 1832 : std::size_t p = input.find_first_of('/', 1);
529 1832 : if (p != core::string_view::npos)
530 : {
531 900 : append(dest, end, input.substr(0, p));
532 900 : input.remove_prefix(p);
533 : }
534 : else
535 : {
536 932 : append(dest, end, input);
537 932 : input = {};
538 : }
539 : }
540 :
541 : // 3. Finally, the output buffer is set
542 : // as the result of remove_dot_segments,
543 : // and we return its size
544 1107 : return dest - dest0;
545 : }
546 :
547 : namespace {
548 :
549 : /* The chars of a normalized path, from the end
550 :
551 : segments_compare()
552 : and normalized_path_digest()
553 : must see the path that url_base::normalize()
554 : would produce, but they cannot allocate, so
555 : that path is never materialized. This class
556 : produces its path chars one at a time in
557 : reverse order instead, reading the encoded
558 : segments in place:
559 :
560 : @code
561 : input: /a/./b/../c/
562 : normalized: /a/c/
563 : next(): '/' 'c' '/' 'a' '/'
564 : @endcode
565 :
566 : @par Why from the end
567 :
568 : Doing it in reverse order ensures we
569 : don't have to allocate memory.
570 :
571 : Whether a segment survives depends on the
572 : segments after it. In "a/b/.." the ".."
573 : removes "b", so "b" cannot be emitted, or
574 : skipped, before the ".." is seen. Reading
575 : from the end, the ".." always comes first,
576 : and a count of pending ".." is enough to
577 : decide each segment the moment it is read:
578 :
579 : @code
580 : input: a/b/..
581 : read pending result
582 : ".." 1
583 : "b" 0 removed by the ".."
584 : "a" 0 emitted
585 : @endcode
586 :
587 : Reading from the front would need to keep
588 : every segment read so far until it is known
589 : that no later ".." removes it, which is the
590 : buffer remove_dot_segments() writes to.
591 : However, in this algorithm we have no buffer
592 : to write to and cannot allocate memory.
593 :
594 : Producing the chars backward still gives a
595 : lexicographic comparison in O(n).
596 : segments_compare() aligns both paths at
597 : their first char, reads the pairs of chars
598 : from the end, and keeps the last difference
599 : it sees, which is the first difference from
600 : the front. For that it needs the size of
601 : each path before the first char is produced,
602 : so it can skip the extra chars at the end
603 : of the longer path.
604 :
605 : The only extra cost is comparing O(n) chars
606 : even in cases where the distinction between
607 : paths would be evident by comparing the first
608 : normalized chars. The only way to implement
609 : this as an optimization would be to have another
610 : algorithm that doesn't operate in reverse but
611 : covers a few limited cases where we can do it
612 : in regular order, like paths whose size is
613 : limited by a constant (in which case we can
614 : use a buffer) or paths without dotdot
615 : segments. Another possible optimization is not
616 : using `compare` as the implementation for
617 : `operator==` and having a faster bool version
618 : of compare segments that fails on the first
619 : difference, in which case the order doesn't
620 : matter.
621 :
622 : @par How
623 :
624 : advance() reads the segments once, from the
625 : end, and decides each one as it is read. Two
626 : decisions depend on other segments, and both
627 : are made only when they are needed:
628 :
629 : @li Whether the path ends with "/" is decided
630 : by the first call to advance(). When the
631 : last segment is "..", this reads ahead until
632 : that ".." removes a segment or the front is
633 : reached: "/a/b/.." ends with "/" after
634 : reading "b", and "/x/../.." does not, after
635 : reading every segment.
636 :
637 : @li Whether the path gets a "./" prefix is
638 : decided after the segments that survive were
639 : produced, because it depends on whether the
640 : first of them is empty.
641 :
642 : The size of the normalized path is not known
643 : in advance. normalized_path_size() counts it
644 : by reading the path once more.
645 :
646 : @par Rules
647 :
648 : The rules are the ones of remove_dot_segments()
649 : and url_base::normalize_path():
650 :
651 : @li "." segments are removed and ".." segments
652 : remove the closest preceding segment:
653 : "/a/./b/../c" becomes "/a/c".
654 :
655 : @li ".." segments with nothing left to remove
656 : are kept at the front, as errata 4547
657 : requires: "/a/../../b" becomes "/../b" and
658 : "a/../.." becomes "..".
659 :
660 : @li A path whose last segment is "." or a ".."
661 : that removed a segment ends with "/" (RFC 3986
662 : section 5.2.4, rules B and C): "/a/.." becomes
663 : "/", "/." becomes "/" and "x/./y/.." becomes
664 : "x/".
665 :
666 : @li A relative path left with nothing but one
667 : empty segment is the empty path: "a/.." and
668 : "." become "".
669 :
670 : @li A relative path whose first segment is
671 : empty would serialize with a leading "//",
672 : which reads as an authority, so normalize()
673 : adds a "./" prefix that this class emits too:
674 : "a/..//b" and ".//b" both become ".//b".
675 :
676 : @li Segments are compared after decoding, so
677 : "%2E%2E" is "..". An encoded slash ("%2F") is
678 : not decoded by normalize() and is not a
679 : separator, so it is produced as '/' with a
680 : flag that lets callers tell it apart.
681 : */
682 : class normalized_path_reverse
683 : {
684 : /* The types of segment advance() produces
685 :
686 : advance() goes through these types in
687 : the order they are declared, which is the
688 : order these types of segments appear when
689 : the normalized path is read from its end
690 : to its front:
691 :
692 : @code
693 : path: ../a/b/.
694 : normalized: ../a/b/
695 : advance(): "" trailing_empty_segment
696 : "b", "a" surviving_segment
697 : ".." dotdot_prefix
698 : @endcode
699 :
700 : dot_prefix comes last because it is the
701 : first segment of the normalized path. A
702 : path never has both a dot_prefix and a
703 : dotdot_prefix: the "./" prefix is only
704 : needed when nothing is left over at the
705 : front.
706 : */
707 : enum class segment_type
708 : {
709 : // The empty last segment of a path that
710 : // ends with "/". For "/a/b/..", which
711 : // normalizes to "/a/", this produces "".
712 : trailing_empty_segment,
713 :
714 : // The segments that survive, last first.
715 : // For "/a/./b/../c", which normalizes to
716 : // "/a/c", this produces "c", then "a".
717 : surviving_segment,
718 :
719 : // The ".." left over at the front. For
720 : // "a/../../..", which normalizes to
721 : // "../..", this produces "..", then "..".
722 : dotdot_prefix,
723 :
724 : // The "." of the "./" prefix. For
725 : // "a/..//b", which normalizes to ".//b",
726 : // this produces ".".
727 : dot_prefix,
728 :
729 : // Nothing is left, so advance() returns
730 : // false.
731 : end
732 : };
733 :
734 : // The type of segment advance() produces
735 : // next. It starts at trailing_empty_segment,
736 : // the type that comes first when reading
737 : // from the end, and only moves forward. For
738 : // "../a/b/." it stays at surviving_segment
739 : // while producing "b" and "a", then moves
740 : // to dotdot_prefix to produce "..".
741 : segment_type cur_segment_type_ =
742 : segment_type::trailing_empty_segment;
743 :
744 : // The segments, and the next one to read
745 : // from the end
746 : segments_encoded_view::iterator begin_;
747 : segments_encoded_view::iterator it_;
748 :
749 : // What is left of the segment being produced
750 : core::string_view seg_;
751 :
752 : // Number of ".." read by advance() that have
753 : // not removed a segment yet. While it is not
754 : // zero, each segment read is removed instead
755 : // of produced: in "a/b/../..", both "b" and
756 : // "a" are removed.
757 : std::size_t pending_dotdots_ = 0;
758 :
759 : // The path starts with "/". next() produces
760 : // that "/" as its very last char, after all
761 : // segments: "/a" produces 'a', then '/'.
762 : bool absolute_ = false;
763 :
764 : // Number of segments advance() returned so
765 : // far. next() puts no '/' after the first
766 : // one, and the "./" prefix needs at least
767 : // two: "a/..//b" produces "b" and "" before
768 : // the ".".
769 : std::size_t n_produced_ = 0;
770 :
771 : // The last segment produced as a
772 : // surviving_segment was empty. They come
773 : // last first, so this is the first segment
774 : // of the normalized path, and an empty one
775 : // needs the "./" prefix: in "a/..//b" it is
776 : // the "" before "b".
777 : bool front_surviving_empty_ = false;
778 :
779 : // advance() produced a leftover "..". The
780 : // path then starts with "..", so it never
781 : // needs the "./" prefix: "a/../..//b"
782 : // normalizes to "..//b".
783 : bool produced_dotdot_ = false;
784 :
785 : // Nothing is left to produce, so next()
786 : // returns false.
787 : bool done_ = false;
788 :
789 : /* A char of a segment after decoding
790 :
791 : The decoded value, and whether it was an
792 : encoded slash ("%2F"). An encoded slash
793 : decodes to '/' but is not a separator, so
794 : callers need to tell it apart.
795 :
796 : @code
797 : "b" -> { 'b', false }
798 : "%41" -> { 'A', false }
799 : "%2F" -> { '/', true }
800 : @endcode
801 : */
802 : struct decoded_char
803 : {
804 : char value;
805 : bool encoded_slash;
806 : };
807 :
808 : /* Remove the decoded last char of a segment
809 :
810 : Returns the decoded last char and removes
811 : it from the encoded segment.
812 :
813 : @code
814 : "ab" -> { 'b', false }, leaves "a"
815 : "a%41" -> { 'A', false }, leaves "a"
816 : "a%2F" -> { '/', true }, leaves "a"
817 : @endcode
818 : */
819 : static
820 : decoded_char
821 4876 : pop_last_decoded_char(
822 : core::string_view& s) noexcept
823 : {
824 4876 : BOOST_ASSERT(!s.empty());
825 7060 : if (s.size() >= 3 &&
826 2184 : s[s.size() - 3] == '%')
827 : {
828 182 : char c = 0;
829 364 : detail::decode_unsafe(
830 364 : &c, &c + 1, s.substr(s.size() - 3));
831 182 : s.remove_suffix(3);
832 182 : return { c, c == '/' };
833 : }
834 4694 : char c = s.back();
835 4694 : s.remove_suffix(1);
836 4694 : return { c, false };
837 : }
838 :
839 : /* Whether a segment is "." after decoding
840 :
841 : @code
842 : is_encoded_dot(".") -> true
843 : is_encoded_dot("%2E") -> true
844 : is_encoded_dot("..") -> false
845 : @endcode
846 : */
847 : static
848 : bool
849 3760 : is_encoded_dot(pct_string_view s) noexcept
850 : {
851 3760 : return *s == ".";
852 : }
853 :
854 : /* Whether a segment is ".." after decoding
855 :
856 : @code
857 : is_encoded_dotdot("..") -> true
858 : is_encoded_dotdot(".%2E") -> true
859 : is_encoded_dotdot("...") -> false
860 : @endcode
861 : */
862 : static
863 : bool
864 4468 : is_encoded_dotdot(pct_string_view s) noexcept
865 : {
866 4468 : return *s == "..";
867 : }
868 :
869 : /* Whether the normalized path ends with "/"
870 :
871 : It does when the last segment is "." or a
872 : ".." that removes a segment. For a "..",
873 : this reads ahead, without moving it_, until
874 : that ".." removes a segment or the front is
875 : reached:
876 :
877 : @code
878 : path normalized result
879 : /a/b/. /a/b/ true: the last segment is "."
880 : /a/b/.. /a/ true: reads "b", which the
881 : ".." removes
882 : /x/../.. /.. false: reads every segment, and
883 : the last ".." removes
884 : nothing
885 : /a/b /a/b false: the last segment is
886 : neither "." nor ".."
887 : @endcode
888 : */
889 : bool
890 1736 : ends_with_slash() const noexcept
891 : {
892 1736 : if (it_ == begin_)
893 : {
894 375 : return false;
895 : }
896 1361 : auto it = it_;
897 1361 : --it;
898 1361 : if (is_encoded_dot(*it))
899 : {
900 46 : return true;
901 : }
902 1315 : if (!is_encoded_dotdot(*it))
903 : {
904 1126 : return false;
905 : }
906 189 : std::size_t pending = 1;
907 232 : while (it != begin_)
908 : {
909 130 : --it;
910 130 : pct_string_view seg = *it;
911 130 : if (is_encoded_dotdot(seg))
912 : {
913 22 : ++pending;
914 : }
915 108 : else if (
916 108 : !is_encoded_dot(seg) &&
917 : --pending == 0)
918 : {
919 87 : return true;
920 : }
921 : }
922 102 : return false;
923 : }
924 :
925 : /* Move to the next segment of the output
926 :
927 : Sets seg_ to the next segment of the
928 : normalized path, from the last to the
929 : first, and returns false when there are
930 : no more. The segments come in the order
931 : of the types declared in segment_type:
932 :
933 : @li trailing_empty_segment: the empty
934 : segment of a trailing "/"
935 : @li surviving_segment: the segments that
936 : survive, last first
937 : @li dotdot_prefix: the ".." left over at
938 : the front
939 : @li dot_prefix: the "." of the "./" prefix
940 :
941 : @code
942 : path: ../a/b/..
943 : normalized: ../a/
944 : advance(): "", "a", "..", false
945 : @endcode
946 : */
947 : bool
948 3814 : advance() noexcept
949 : {
950 : // next() only asks for another segment
951 : // when the previous one was fully
952 : // produced and the output is not over
953 3814 : BOOST_ASSERT(seg_.empty());
954 3814 : BOOST_ASSERT(!done_);
955 3814 : if (cur_segment_type_ == segment_type::trailing_empty_segment)
956 : {
957 : // no segment was read yet
958 1736 : BOOST_ASSERT(pending_dotdots_ == 0);
959 1736 : BOOST_ASSERT(n_produced_ == 0);
960 1736 : cur_segment_type_ = segment_type::surviving_segment;
961 1736 : if (ends_with_slash())
962 : {
963 133 : ++n_produced_;
964 133 : seg_ = {};
965 133 : return true;
966 : }
967 : }
968 3681 : if (cur_segment_type_ == segment_type::surviving_segment)
969 : {
970 4601 : while (it_ != begin_)
971 : {
972 3023 : --it_;
973 3023 : pct_string_view s = *it_;
974 3023 : if (is_encoded_dotdot(s))
975 : {
976 732 : ++pending_dotdots_;
977 : }
978 2291 : else if (is_encoded_dot(s))
979 : {
980 145 : continue;
981 : }
982 2146 : else if (pending_dotdots_)
983 : {
984 392 : --pending_dotdots_;
985 : }
986 : else
987 : {
988 1754 : ++n_produced_;
989 1754 : front_surviving_empty_ = s.empty();
990 1754 : seg_ = s;
991 1754 : return true;
992 : }
993 : }
994 1578 : cur_segment_type_ = segment_type::dotdot_prefix;
995 : }
996 1927 : if (cur_segment_type_ == segment_type::dotdot_prefix)
997 : {
998 : // every regular segment was read
999 1860 : BOOST_ASSERT(it_ == begin_);
1000 1860 : if (pending_dotdots_)
1001 : {
1002 340 : --pending_dotdots_;
1003 340 : ++n_produced_;
1004 340 : produced_dotdot_ = true;
1005 340 : seg_ = "..";
1006 340 : return true;
1007 : }
1008 1520 : cur_segment_type_ = segment_type::dot_prefix;
1009 : }
1010 1587 : if (cur_segment_type_ == segment_type::dot_prefix)
1011 : {
1012 : // every segment was read and every
1013 : // leftover ".." was produced
1014 1520 : BOOST_ASSERT(it_ == begin_);
1015 1520 : BOOST_ASSERT(pending_dotdots_ == 0);
1016 1520 : cur_segment_type_ = segment_type::end;
1017 : // A relative path whose first segment
1018 : // is empty, with more after it, would
1019 : // start with "//" and read as an
1020 : // authority: "a/..//b" produced "b"
1021 : // and "", so it gets a ".".
1022 1520 : bool const needs_dot_prefix =
1023 2260 : !absolute_ &&
1024 740 : !produced_dotdot_ &&
1025 2396 : front_surviving_empty_ &&
1026 136 : n_produced_ >= 2;
1027 1520 : if (needs_dot_prefix)
1028 : {
1029 126 : ++n_produced_;
1030 126 : seg_ = ".";
1031 126 : return true;
1032 : }
1033 : }
1034 : // every path to here went through the
1035 : // transition to end
1036 1461 : BOOST_ASSERT(
1037 : cur_segment_type_ == segment_type::end);
1038 1461 : return false;
1039 : }
1040 :
1041 : public:
1042 : /* Prepare to read a path from its end
1043 :
1044 : Nothing is read until the first call to
1045 : next().
1046 : */
1047 : explicit
1048 1896 : normalized_path_reverse(
1049 : segments_encoded_view segs) noexcept
1050 1896 : : begin_(segs.begin())
1051 1896 : , it_(segs.end())
1052 3792 : , absolute_(segs.is_absolute())
1053 : {
1054 1896 : }
1055 :
1056 : /* Produce the next char from the end
1057 :
1058 : Returns false when all chars were
1059 : produced. The flag is set when the char
1060 : is an encoded slash.
1061 :
1062 : @code
1063 : path: x/./y/..
1064 : next(): '/', 'x', false ("x/")
1065 : @endcode
1066 : */
1067 : bool
1068 7790 : next(
1069 : char& c,
1070 : bool& encoded_slash) noexcept
1071 : {
1072 7790 : encoded_slash = false;
1073 : for (;;)
1074 : {
1075 9151 : if (!seg_.empty())
1076 : {
1077 : decoded_char const d =
1078 4876 : pop_last_decoded_char(seg_);
1079 4876 : c = d.value;
1080 4876 : encoded_slash = d.encoded_slash;
1081 4876 : return true;
1082 : }
1083 4275 : if (done_)
1084 : {
1085 461 : return false;
1086 : }
1087 3814 : if (advance())
1088 : {
1089 2353 : if (n_produced_ == 1)
1090 : {
1091 : // nothing follows the last segment
1092 1361 : continue;
1093 : }
1094 992 : c = '/';
1095 992 : return true;
1096 : }
1097 1461 : done_ = true;
1098 1461 : if (absolute_)
1099 : {
1100 780 : c = '/';
1101 780 : return true;
1102 : }
1103 681 : return false;
1104 1361 : }
1105 : }
1106 :
1107 : /* Produce the next char from the end
1108 :
1109 : Like the other overload, for callers that
1110 : only count or skip chars and do not need
1111 : to know whether it was an encoded slash.
1112 :
1113 : @code
1114 : path: x/./y/..
1115 : next(): '/', 'x', false ("x/")
1116 : @endcode
1117 : */
1118 : bool
1119 3702 : next(char& c) noexcept
1120 : {
1121 3702 : bool encoded_slash = false;
1122 3702 : return next(c, encoded_slash);
1123 : }
1124 :
1125 : /* Skip the next n chars from the end
1126 :
1127 : The path must have at least n chars left.
1128 :
1129 : @code
1130 : path: /a/b/
1131 : skip(2): skips '/' and 'b'
1132 : next(): '/', 'a', '/', false
1133 : @endcode
1134 : */
1135 : void
1136 377 : skip(std::size_t n) noexcept
1137 : {
1138 377 : char c = 0;
1139 687 : for (; n != 0; --n)
1140 : {
1141 310 : bool const ok = next(c);
1142 310 : BOOST_ASSERT(ok);
1143 : ignore_unused(ok);
1144 : }
1145 377 : }
1146 : };
1147 :
1148 : /* The size of a path after normalization
1149 :
1150 : Counts the chars normalized_path_reverse
1151 : produces, reading the path once.
1152 :
1153 : @code
1154 : "/a/b/.." -> 3 ("/a/")
1155 : "a/../.." -> 2 ("..")
1156 : "a/.." -> 0 ("")
1157 : @endcode
1158 : */
1159 : std::size_t
1160 754 : normalized_path_size(
1161 : segments_encoded_view segs) noexcept
1162 : {
1163 754 : normalized_path_reverse r(segs);
1164 754 : std::size_t n = 0;
1165 754 : char c = 0;
1166 3392 : while (r.next(c))
1167 : {
1168 2638 : ++n;
1169 : }
1170 754 : return n;
1171 : }
1172 :
1173 : } // (anon)
1174 :
1175 : /* Hash a path as if it were normalized
1176 :
1177 : Hashes the chars of the path that
1178 : url_base::normalize() would produce, so
1179 : paths that segments_compare() finds equal
1180 : always hash equal. The chars are hashed
1181 : from the end of the path, in the order
1182 : normalized_path_reverse produces them. An
1183 : encoded slash is written "%2F" in
1184 : uppercase, as normalize() writes it, and
1185 : those three chars are hashed from the end
1186 : too, like any others:
1187 :
1188 : @code
1189 : path normalized hashed
1190 : /. / '/'
1191 : a/../.. .. '.' '.'
1192 : a%2fb a%2Fb 'b' 'F' '2' '%' 'a'
1193 : @endcode
1194 : */
1195 : void
1196 388 : normalized_path_digest(
1197 : segments_encoded_view segs,
1198 : fnv_1a& hasher) noexcept
1199 : {
1200 388 : normalized_path_reverse r(segs);
1201 388 : char c = 0;
1202 388 : bool encoded_slash = false;
1203 1760 : while (r.next(c, encoded_slash))
1204 : {
1205 1372 : if (!encoded_slash)
1206 : {
1207 1360 : hasher.put(c);
1208 1360 : continue;
1209 : }
1210 : // an encoded slash stays encoded in
1211 : // the normalized path, and its chars
1212 : // are hashed from the end as well
1213 12 : hasher.put('F');
1214 12 : hasher.put('2');
1215 12 : hasher.put('%');
1216 : }
1217 388 : }
1218 :
1219 : /* Compare two paths as if they were normalized
1220 :
1221 : The result is the order of the paths that
1222 : url_base::normalize() would produce, without
1223 : producing them, so that the function does not
1224 : allocate. Paths compare equal exactly when
1225 : they normalize to the same path:
1226 :
1227 : @code
1228 : compare("/a/b/..", "/a/") -> 0 ("/a/" and "/a/")
1229 : compare("a/../..", "..") -> 0 (".." and "..")
1230 : compare("/a/b/..", "/a") -> +1 ("/a/" and "/a")
1231 : compare("a%2Fb", "a/b") -> -1 ("%2F" is not "/")
1232 : @endcode
1233 :
1234 : Both paths are read from the end with
1235 : normalized_path_reverse, which explains why
1236 : the chars come in that order. The paths are
1237 : aligned at their first common char: the extra chars
1238 : at the end of the longer path are skipped,
1239 : then the remaining chars are compared in
1240 : pairs. Each difference overwrites the
1241 : previous one, so the result is the last
1242 : difference read, which is the first one from
1243 : the front. If there is none, the shorter path
1244 : comes first:
1245 :
1246 : @code
1247 : lhs: /a/c/ (size 5)
1248 : rhs: /b/c (size 4)
1249 : skip: '/' of lhs
1250 : pairs: ('c','c') ('/','/') ('a','b') ('/','/')
1251 : result: -1, from ('a','b')
1252 : @endcode
1253 :
1254 : An encoded slash and a '/' are the same char
1255 : with a different meaning. The encoded slash
1256 : sorts first, as the '%' it is written with
1257 : would.
1258 : */
1259 : int
1260 377 : segments_compare(
1261 : segments_encoded_view seg0,
1262 : segments_encoded_view seg1) noexcept
1263 : {
1264 377 : normalized_path_reverse r0(seg0);
1265 377 : normalized_path_reverse r1(seg1);
1266 377 : std::size_t const n0 = normalized_path_size(seg0);
1267 377 : std::size_t const n1 = normalized_path_size(seg1);
1268 377 : std::size_t const n = (std::min)(n0, n1);
1269 :
1270 : // skip the chars at the end of the longer
1271 : // path that have nothing to be compared
1272 : // with
1273 377 : normalized_path_reverse& longer =
1274 377 : n0 > n1 ? r0 : r1;
1275 377 : longer.skip((std::max)(n0, n1) - n);
1276 :
1277 :
1278 : // compare the common prefix from the end,
1279 : // keeping the first difference
1280 377 : int cmp = 0;
1281 377 : char c0 = 0;
1282 377 : char c1 = 0;
1283 377 : bool e0 = false;
1284 377 : bool e1 = false;
1285 1541 : for (std::size_t i = 0; i < n; ++i)
1286 : {
1287 1164 : bool const ok0 = r0.next(c0, e0);
1288 1164 : bool const ok1 = r1.next(c1, e1);
1289 1164 : BOOST_ASSERT(ok0 && ok1);
1290 : ignore_unused(ok0, ok1);
1291 1164 : if (c0 < c1)
1292 : {
1293 87 : cmp = -1;
1294 : }
1295 1077 : else if (c1 < c0)
1296 : {
1297 72 : cmp = +1;
1298 : }
1299 1005 : else if (e0 != e1)
1300 : {
1301 : // same char, but only one of them
1302 : // is an encoded slash, which is
1303 : // not a path separator: it sorts
1304 : // like the '%' it keeps
1305 10 : cmp = e0 ? -1 : +1;
1306 : }
1307 : }
1308 377 : if (cmp != 0 ||
1309 272 : n0 == n1)
1310 : {
1311 356 : return cmp;
1312 : }
1313 21 : if (n0 < n1)
1314 : {
1315 11 : return -1;
1316 : }
1317 10 : return 1;
1318 : }
1319 :
1320 : } // detail
1321 : } // urls
1322 : } // boost
1323 :
|
