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 "decode.hpp"
15 : #include <boost/url/segments_encoded_view.hpp>
16 : #include <boost/url/grammar/ci_string.hpp>
17 : #include <boost/assert.hpp>
18 : #include <boost/core/ignore_unused.hpp>
19 : #include <cstring>
20 : #include "normalize.hpp"
21 :
22 : namespace boost {
23 : namespace urls {
24 : namespace detail {
25 :
26 : void
27 7280 : pop_encoded_front(
28 : core::string_view& s,
29 : char& c,
30 : std::size_t& n) noexcept
31 : {
32 7280 : if(s.front() != '%')
33 : {
34 7190 : c = s.front();
35 7190 : s.remove_prefix(1);
36 : }
37 : else
38 : {
39 90 : detail::decode_unsafe(
40 : &c,
41 : &c + 1,
42 : s.substr(0, 3));
43 90 : s.remove_prefix(3);
44 : }
45 7280 : ++n;
46 7280 : }
47 :
48 : int
49 77 : compare_encoded(
50 : core::string_view lhs,
51 : core::string_view rhs) noexcept
52 : {
53 77 : std::size_t n0 = 0;
54 77 : std::size_t n1 = 0;
55 77 : char c0 = 0;
56 77 : char c1 = 0;
57 77 : while(
58 535 : !lhs.empty() &&
59 253 : !rhs.empty())
60 : {
61 240 : pop_encoded_front(lhs, c0, n0);
62 240 : pop_encoded_front(rhs, c1, n1);
63 240 : if (c0 < c1)
64 20 : return -1;
65 220 : if (c1 < c0)
66 15 : return 1;
67 : }
68 42 : n0 += detail::decode_bytes_unsafe(lhs);
69 42 : n1 += detail::decode_bytes_unsafe(rhs);
70 42 : if (n0 == n1)
71 21 : return 0;
72 21 : if (n0 < n1)
73 8 : return -1;
74 13 : return 1;
75 : }
76 :
77 : void
78 1216 : digest_encoded(
79 : core::string_view s,
80 : fnv_1a& hasher) noexcept
81 : {
82 1216 : char c = 0;
83 1216 : std::size_t n = 0;
84 1724 : while(!s.empty())
85 : {
86 508 : pop_encoded_front(s, c, n);
87 508 : hasher.put(c);
88 : }
89 1216 : }
90 :
91 : int
92 159 : ci_compare_encoded(
93 : core::string_view lhs,
94 : core::string_view rhs) noexcept
95 : {
96 159 : std::size_t n0 = 0;
97 159 : std::size_t n1 = 0;
98 159 : char c0 = 0;
99 159 : char c1 = 0;
100 159 : while (
101 4385 : !lhs.empty() &&
102 2121 : !rhs.empty())
103 : {
104 2115 : pop_encoded_front(lhs, c0, n0);
105 2115 : pop_encoded_front(rhs, c1, n1);
106 2115 : c0 = grammar::to_lower(c0);
107 2115 : c1 = grammar::to_lower(c1);
108 2115 : if (c0 < c1)
109 8 : return -1;
110 2107 : if (c1 < c0)
111 2 : return 1;
112 : }
113 149 : n0 += detail::decode_bytes_unsafe(lhs);
114 149 : n1 += detail::decode_bytes_unsafe(rhs);
115 149 : if (n0 == n1)
116 142 : return 0;
117 7 : if (n0 < n1)
118 1 : return -1;
119 6 : return 1;
120 : }
121 :
122 : void
123 304 : ci_digest_encoded(
124 : core::string_view s,
125 : fnv_1a& hasher) noexcept
126 : {
127 304 : char c = 0;
128 304 : std::size_t n = 0;
129 2366 : while(!s.empty())
130 : {
131 2062 : pop_encoded_front(s, c, n);
132 2062 : c = grammar::to_lower(c);
133 2062 : hasher.put(c);
134 : }
135 304 : }
136 :
137 : int
138 46 : compare(
139 : core::string_view lhs,
140 : core::string_view rhs) noexcept
141 : {
142 46 : auto rlen = (std::min)(lhs.size(), rhs.size());
143 104 : for (std::size_t i = 0; i < rlen; ++i)
144 : {
145 79 : char c0 = lhs[i];
146 79 : char c1 = rhs[i];
147 79 : if (c0 < c1)
148 13 : return -1;
149 66 : if (c1 < c0)
150 8 : return 1;
151 : }
152 25 : if ( lhs.size() == rhs.size() )
153 4 : return 0;
154 21 : if ( lhs.size() < rhs.size() )
155 8 : return -1;
156 13 : return 1;
157 : }
158 :
159 : int
160 196 : ci_compare(
161 : core::string_view lhs,
162 : core::string_view rhs) noexcept
163 : {
164 196 : auto rlen = (std::min)(lhs.size(), rhs.size());
165 989 : for (std::size_t i = 0; i < rlen; ++i)
166 : {
167 800 : char c0 = grammar::to_lower(lhs[i]);
168 800 : char c1 = grammar::to_lower(rhs[i]);
169 800 : if (c0 < c1)
170 6 : return -1;
171 794 : if (c1 < c0)
172 1 : return 1;
173 : }
174 189 : if ( lhs.size() == rhs.size() )
175 182 : return 0;
176 7 : if ( lhs.size() < rhs.size() )
177 6 : return -1;
178 1 : return 1;
179 : }
180 :
181 : void
182 304 : ci_digest(
183 : core::string_view s,
184 : fnv_1a& hasher) noexcept
185 : {
186 1034 : for (char c: s)
187 : {
188 730 : c = grammar::to_lower(c);
189 730 : hasher.put(c);
190 : }
191 304 : }
192 :
193 : /* Check if a string ends with the specified suffix (decoded comparison)
194 :
195 : This function determines if a string ends with the specified suffix
196 : when the string and suffix are compared after percent-decoding.
197 :
198 : @param str The string to check (percent-encoded)
199 : @param suffix The suffix to check for (percent-decoded)
200 : @return The number of encoded chars consumed in the string
201 : */
202 : std::size_t
203 2136 : path_ends_with(
204 : core::string_view str,
205 : core::string_view suffix) noexcept
206 : {
207 2136 : BOOST_ASSERT(!str.empty());
208 2136 : BOOST_ASSERT(!suffix.empty());
209 2136 : BOOST_ASSERT(!suffix.contains("%2F"));
210 2136 : BOOST_ASSERT(!suffix.contains("%2f"));
211 5848 : auto consume_last = [](
212 : core::string_view::iterator& it,
213 : core::string_view::iterator& end,
214 : char& c)
215 : {
216 5848 : BOOST_ASSERT(end > it);
217 5848 : BOOST_ASSERT(it != end);
218 9808 : if ((end - it) < 3 ||
219 3960 : *(std::prev(end, 3)) != '%')
220 : {
221 5800 : c = *--end;
222 5800 : return false;
223 : }
224 48 : detail::decode_unsafe(
225 : &c,
226 : &c + 1,
227 : core::string_view(std::prev(
228 : end, 3), 3));
229 48 : end -= 3;
230 48 : return true;
231 : };
232 :
233 2136 : auto it0 = str.begin();
234 2136 : auto end0 = str.end();
235 2136 : auto it1 = suffix.begin();
236 2136 : auto end1 = suffix.end();
237 2136 : char c0 = 0;
238 2136 : char c1 = 0;
239 2136 : while(
240 3248 : it0 < end0 &&
241 3006 : it1 < end1)
242 : {
243 2932 : bool const is_encoded = consume_last(it0, end0, c0);
244 : // The suffix never contains an encoded slash (%2F), and a decoded
245 : // slash is not equivalent to an encoded slash
246 2932 : if (is_encoded && c0 == '/')
247 16 : return 0;
248 2916 : consume_last(it1, end1, c1);
249 2916 : if (c0 != c1)
250 1804 : return 0;
251 : }
252 316 : bool const consumed_suffix = it1 == end1;
253 316 : if (consumed_suffix)
254 : {
255 110 : std::size_t const consumed_encoded = str.end() - end0;
256 110 : return consumed_encoded;
257 : }
258 206 : return 0;
259 : }
260 :
261 : std::size_t
262 832 : remove_dot_segments(
263 : char* dest0,
264 : char const* end,
265 : core::string_view input) noexcept
266 : {
267 : // 1. The input buffer `s` is initialized with
268 : // the now-appended path components and the
269 : // output buffer `dest0` is initialized to
270 : // the empty string.
271 832 : char* dest = dest0;
272 832 : bool const is_absolute = input.starts_with('/');
273 :
274 : // Step 2 is a loop through 5 production rules:
275 : // https://www.rfc-editor.org/rfc/rfc3986#section-5.2.4
276 : //
277 : // There are no transitions between all rules,
278 : // which enables some optimizations.
279 : //
280 : // Initial:
281 : // - Rule A: handle initial dots
282 : // If the input buffer begins with a
283 : // prefix of "../" or "./", then remove
284 : // that prefix from the input buffer.
285 : // Rule A can only happen at the beginning.
286 : // Errata 4547: Keep "../" in the beginning
287 : // https://www.rfc-editor.org/errata/eid4547
288 : //
289 : // Then:
290 : // - Rule D: ignore a final ".." or "."
291 : // if the input buffer consists only of "."
292 : // or "..", then remove that from the input
293 : // buffer.
294 : // Rule D can only happen after Rule A because:
295 : // - B and C write "/" to the input
296 : // - E writes "/" to input or returns
297 : //
298 : // Then:
299 : // - Rule B: ignore ".": write "/" to the input
300 : // - Rule C: apply "..": remove seg and write "/"
301 : // - Rule E: copy complete segment
302 : auto append =
303 1492 : [](char*& first, char const* last, core::string_view in)
304 : {
305 : // append `in` to `dest`
306 1492 : BOOST_ASSERT(in.size() <= std::size_t(last - first));
307 1492 : std::memmove(first, in.data(), in.size());
308 1492 : first += in.size();
309 : ignore_unused(last);
310 1492 : };
311 :
312 9563 : auto dot_starts_with = [](
313 : core::string_view str, core::string_view dots, std::size_t& n)
314 : {
315 : // starts_with for encoded/decoded dots
316 : // or decoded otherwise. return how many
317 : // chars in str match the dots
318 9563 : n = 0;
319 16918 : for (char c: dots)
320 : {
321 16368 : if (str.starts_with(c))
322 : {
323 7355 : str.remove_prefix(1);
324 7355 : ++n;
325 7355 : continue;
326 : }
327 :
328 : // In the general case, we would need to
329 : // check if the next char is an encoded
330 : // dot.
331 : // However, an encoded dot in `str`
332 : // would have already been decoded in
333 : // url_base::normalize_path().
334 : // This needs to be undone if
335 : // `remove_dot_segments` is used in a
336 : // different context.
337 : // if (str.size() > 2 &&
338 : // c == '.'
339 : // &&
340 : // str[0] == '%' &&
341 : // str[1] == '2' &&
342 : // (str[2] == 'e' ||
343 : // str[2] == 'E'))
344 : // {
345 : // str.remove_prefix(3);
346 : // n += 3;
347 : // continue;
348 : // }
349 :
350 9013 : n = 0;
351 9013 : return false;
352 : }
353 550 : return true;
354 : };
355 :
356 4777 : auto dot_equal = [&dot_starts_with](
357 4777 : core::string_view str, core::string_view dots)
358 : {
359 4777 : std::size_t n = 0;
360 4777 : dot_starts_with(str, dots, n);
361 4777 : return n == str.size();
362 832 : };
363 :
364 : // Rule A
365 : std::size_t n;
366 848 : while (!input.empty())
367 : {
368 767 : if (dot_starts_with(input, "../", n))
369 : {
370 : // Errata 4547
371 4 : append(dest, end, "../");
372 4 : input.remove_prefix(n);
373 4 : continue;
374 : }
375 763 : else if (!dot_starts_with(input, "./", n))
376 : {
377 751 : break;
378 : }
379 12 : input.remove_prefix(n);
380 : }
381 :
382 : // Rule D
383 832 : if( dot_equal(input, "."))
384 : {
385 82 : input = {};
386 : }
387 750 : else if( dot_equal(input, "..") )
388 : {
389 : // Errata 4547
390 3 : append(dest, end, "..");
391 3 : input = {};
392 : }
393 :
394 : // 2. While the input buffer is not empty,
395 : // loop as follows:
396 2441 : while (!input.empty())
397 : {
398 : // Rule B
399 1648 : bool const is_dot_seg = dot_starts_with(input, "/./", n);
400 1648 : if (is_dot_seg)
401 : {
402 32 : input.remove_prefix(n - 1);
403 32 : continue;
404 : }
405 :
406 1616 : bool const is_final_dot_seg = dot_equal(input, "/.");
407 1616 : if (is_final_dot_seg)
408 : {
409 : // We can't remove "." from a core::string_view
410 : // So what we do here is equivalent to
411 : // replacing s with '/' as required
412 : // in Rule B and executing the next
413 : // iteration, which would append this
414 : // '/' to the output, as required by
415 : // Rule E
416 8 : append(dest, end, input.substr(0, 1));
417 8 : input = {};
418 8 : break;
419 : }
420 :
421 : // Rule C
422 1608 : bool const is_dotdot_seg = dot_starts_with(input, "/../", n);
423 1608 : if (is_dotdot_seg)
424 : {
425 193 : core::string_view cur_out(dest0, dest - dest0);
426 193 : std::size_t p = cur_out.find_last_of('/');
427 193 : bool const has_multiple_segs = p != core::string_view::npos;
428 193 : if (has_multiple_segs)
429 : {
430 : // output has multiple segments
431 : // "erase" [p, end] if not "/.."
432 132 : core::string_view last_seg(dest0 + p, dest - (dest0 + p));
433 132 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
434 132 : if (!prev_is_dotdot_seg)
435 : {
436 121 : dest = dest0 + p;
437 : }
438 : else
439 : {
440 11 : append(dest, end, "/..");
441 : }
442 : }
443 61 : else if (dest0 != dest)
444 : {
445 : // Only one segment in the output: remove it
446 11 : core::string_view last_seg(dest0, dest - dest0);
447 11 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
448 11 : if (!prev_is_dotdot_seg)
449 : {
450 9 : dest = dest0;
451 9 : if (!is_absolute)
452 : {
453 9 : input.remove_prefix(1);
454 : }
455 : }
456 : else
457 : {
458 2 : append(dest, end, "/..");
459 : }
460 : }
461 : else
462 : {
463 : // Output is empty
464 50 : if (is_absolute)
465 : {
466 50 : append(dest, end, "/..");
467 : }
468 : else
469 : {
470 : // AFREITAS: Although we have no formal proof
471 : // for that, the output can't be relative
472 : // and empty at this point because relative
473 : // paths will fall in the `dest0 != dest`
474 : // case above of this rule C and then the
475 : // general case of rule E for "..".
476 0 : append(dest, end, "..");
477 : }
478 : }
479 193 : input.remove_prefix(n - 1);
480 193 : continue;
481 193 : }
482 :
483 1415 : bool const is_final_dotdot_seg = dot_equal(input, "/..");
484 1415 : if (is_final_dotdot_seg)
485 : {
486 31 : core::string_view cur_out(dest0, dest - dest0);
487 31 : std::size_t p = cur_out.find_last_of('/');
488 31 : bool const has_multiple_segs = p != core::string_view::npos;
489 31 : if (has_multiple_segs)
490 : {
491 : // output has multiple segments
492 : // "erase" [p, end] if not "/.."
493 18 : core::string_view last_seg(dest0 + p, dest - (dest0 + p));
494 18 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
495 18 : if (!prev_is_dotdot_seg)
496 : {
497 14 : dest = dest0 + p;
498 14 : append(dest, end, "/");
499 : }
500 : else
501 : {
502 4 : append(dest, end, "/..");
503 : }
504 : }
505 13 : else if (dest0 != dest)
506 : {
507 : // Only one segment in the output: remove it
508 3 : core::string_view last_seg(dest0, dest - dest0);
509 3 : bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
510 3 : if (!prev_is_dotdot_seg) {
511 1 : dest = dest0;
512 : }
513 : else
514 : {
515 2 : append(dest, end, "/..");
516 : }
517 : }
518 : else
519 : {
520 : // Output is empty: append dotdot
521 10 : if (is_absolute)
522 : {
523 10 : append(dest, end, "/..");
524 : }
525 : else
526 : {
527 : // AFREITAS: Although we have no formal proof
528 : // for that, the output can't be relative
529 : // and empty at this point because relative
530 : // paths will fall in the `dest0 != dest`
531 : // case above of this rule C and then the
532 : // general case of rule E for "..".
533 0 : append(dest, end, "..");
534 : }
535 : }
536 31 : input = {};
537 31 : break;
538 : }
539 :
540 : // Rule E
541 1384 : std::size_t p = input.find_first_of('/', 1);
542 1384 : if (p != core::string_view::npos)
543 : {
544 676 : append(dest, end, input.substr(0, p));
545 676 : input.remove_prefix(p);
546 : }
547 : else
548 : {
549 708 : append(dest, end, input);
550 708 : input = {};
551 : }
552 : }
553 :
554 : // 3. Finally, the output buffer is set
555 : // as the result of remove_dot_segments,
556 : // and we return its size
557 832 : return dest - dest0;
558 : }
559 :
560 : char
561 1154 : path_pop_back( core::string_view& s )
562 : {
563 1676 : if (s.size() < 3 ||
564 522 : *std::prev(s.end(), 3) != '%')
565 : {
566 1102 : char c = s.back();
567 1102 : s.remove_suffix(1);
568 1102 : return c;
569 : }
570 52 : char c = 0;
571 104 : detail::decode_unsafe(
572 104 : &c, &c + 1, s.substr(s.size() - 3));
573 52 : if (c != '/')
574 : {
575 44 : s.remove_suffix(3);
576 44 : return c;
577 : }
578 8 : c = s.back();
579 8 : s.remove_suffix(1);
580 8 : return c;
581 : };
582 :
583 : void
584 538 : pop_last_segment(
585 : core::string_view& str,
586 : core::string_view& seg,
587 : std::size_t& level,
588 : bool remove_unmatched) noexcept
589 : {
590 538 : seg = {};
591 538 : std::size_t n = 0;
592 700 : while (!str.empty())
593 : {
594 : // B. if the input buffer begins with a
595 : // prefix of "/./" or "/.", where "." is
596 : // a complete path segment, then replace
597 : // that prefix with "/" in the input
598 : // buffer; otherwise,
599 558 : n = detail::path_ends_with(str, "/./");
600 558 : if (n)
601 : {
602 10 : seg = str.substr(str.size() - n);
603 10 : str.remove_suffix(n);
604 10 : continue;
605 : }
606 548 : n = detail::path_ends_with(str, "/.");
607 548 : if (n)
608 : {
609 12 : seg = str.substr(str.size() - n, 1);
610 12 : str.remove_suffix(n);
611 12 : continue;
612 : }
613 :
614 : // C. if the input buffer begins with a
615 : // prefix of "/../" or "/..", where ".."
616 : // is a complete path segment, then
617 : // replace that prefix with "/" in the
618 : // input buffer and remove the last
619 : // segment and its preceding "/"
620 : // (if any) from the output buffer
621 : // otherwise,
622 536 : n = detail::path_ends_with(str, "/../");
623 536 : if (n)
624 : {
625 42 : seg = str.substr(str.size() - n);
626 42 : str.remove_suffix(n);
627 42 : ++level;
628 42 : continue;
629 : }
630 494 : n = detail::path_ends_with(str, "/..");
631 494 : if (n)
632 : {
633 46 : seg = str.substr(str.size() - n);
634 46 : str.remove_suffix(n);
635 46 : ++level;
636 46 : continue;
637 : }
638 :
639 : // E. move the first path segment in the
640 : // input buffer to the end of the output
641 : // buffer, including the initial "/"
642 : // character (if any) and any subsequent
643 : // characters up to, but not including,
644 : // the next "/" character or the end of
645 : // the input buffer.
646 448 : std::size_t p = str.size() > 1
647 448 : ? str.find_last_of('/', str.size() - 2)
648 448 : : core::string_view::npos;
649 448 : if (p != core::string_view::npos)
650 : {
651 276 : seg = str.substr(p + 1);
652 276 : str.remove_suffix(seg.size());
653 : }
654 : else
655 : {
656 172 : seg = str;
657 172 : str = {};
658 : }
659 :
660 448 : if (level == 0)
661 396 : return;
662 52 : if (!str.empty())
663 42 : --level;
664 : }
665 : // we still need to skip n_skip + 1
666 : // but the string is empty
667 142 : if (remove_unmatched && level)
668 : {
669 34 : seg = "/";
670 34 : level = 0;
671 34 : return;
672 : }
673 108 : else if (level)
674 : {
675 4 : if (!seg.empty())
676 : {
677 4 : seg = "/../";
678 : }
679 : else
680 : {
681 : // AFREITAS: this condition
682 : // is correct, but it might
683 : // unreachable.
684 0 : seg = "/..";
685 : }
686 4 : --level;
687 4 : return;
688 : }
689 104 : seg = {};
690 : }
691 :
692 : void
693 304 : normalized_path_digest(
694 : core::string_view str,
695 : bool remove_unmatched,
696 : fnv_1a& hasher) noexcept
697 : {
698 304 : core::string_view seg;
699 304 : std::size_t level = 0;
700 : do
701 : {
702 538 : pop_last_segment(
703 : str, seg, level, remove_unmatched);
704 1692 : while (!seg.empty())
705 : {
706 1154 : char c = path_pop_back(seg);
707 1154 : hasher.put(c);
708 : }
709 : }
710 538 : while (!str.empty());
711 304 : }
712 :
713 : // compare segments as if there were a normalized
714 : int
715 173 : segments_compare(
716 : segments_encoded_view seg0,
717 : segments_encoded_view seg1) noexcept
718 : {
719 : // calculate path size as if it were normalized
720 : auto normalized_size =
721 346 : [](segments_encoded_view seg) -> std::size_t
722 : {
723 346 : if (seg.empty())
724 108 : return seg.is_absolute();
725 :
726 238 : std::size_t n = 0;
727 238 : std::size_t skip = 0;
728 238 : auto begin = seg.begin();
729 238 : auto it = seg.end();
730 900 : while (it != begin)
731 : {
732 662 : --it;
733 662 : decode_view dseg = **it;
734 662 : if (dseg == "..")
735 167 : ++skip;
736 495 : else if (dseg != ".")
737 : {
738 457 : if (skip)
739 85 : --skip;
740 : else
741 372 : n += dseg.size() + 1;
742 : }
743 : }
744 238 : n += skip * 3;
745 238 : n -= !seg.is_absolute();
746 238 : return n;
747 : };
748 :
749 : // find the normalized size for the comparison
750 173 : std::size_t n0 = normalized_size(seg0);
751 173 : std::size_t n1 = normalized_size(seg1);
752 173 : std::size_t n00 = n0;
753 173 : std::size_t n10 = n1;
754 :
755 : // consume the last char from a segment range
756 : auto consume_last =
757 1640 : [](
758 : std::size_t& n,
759 : decode_view& dseg,
760 : segments_encoded_view::iterator& begin,
761 : segments_encoded_view::iterator& it,
762 : decode_view::iterator& cit,
763 : std::size_t& skip,
764 : bool& at_slash) -> char
765 : {
766 1640 : if (cit != dseg.begin())
767 : {
768 : // return last char from current segment
769 1009 : at_slash = false;
770 1009 : --cit;
771 1009 : --n;
772 1009 : return *cit;
773 : }
774 :
775 631 : if (!at_slash)
776 : {
777 : // current segment dseg is over and
778 : // previous char was not a slash
779 : // so we output one
780 371 : at_slash = true;
781 371 : --n;
782 371 : return '/';
783 : }
784 :
785 : // current segment dseg is over and
786 : // last char was already the slash
787 : // between segments, so take the
788 : // next final segment to consume
789 260 : at_slash = false;
790 498 : while (cit == dseg.begin())
791 : {
792 : // take next segment
793 498 : if (it != begin)
794 376 : --it;
795 : else
796 122 : break;
797 376 : if (**it == "..")
798 : {
799 : // skip next if this is ".."
800 140 : ++skip;
801 : }
802 236 : else if (**it != ".")
803 : {
804 208 : if (skip)
805 : {
806 : // discount skips
807 70 : --skip;
808 : }
809 : else
810 : {
811 : // or update current seg
812 138 : dseg = **it;
813 138 : cit = dseg.end();
814 138 : break;
815 : }
816 : }
817 : }
818 : // consume from the new current
819 : // segment
820 260 : --n;
821 260 : if (cit != dseg.begin())
822 : {
823 : // in the general case, we consume
824 : // one more character from the end
825 123 : --cit;
826 123 : return *cit;
827 : }
828 :
829 : // nothing left to consume in the
830 : // current and new segment
831 137 : if (it == begin)
832 : {
833 : // if this is the first
834 : // segment, the segments are
835 : // over and there can only
836 : // be repetitions of "../" to
837 : // output
838 128 : return "/.."[n % 3];
839 : }
840 : // at other segments, we need
841 : // a slash to transition to the
842 : // next segment
843 9 : at_slash = true;
844 9 : return '/';
845 : };
846 :
847 : // consume final segments from seg0 that
848 : // should not influence the comparison
849 173 : auto begin0 = seg0.begin();
850 173 : auto it0 = seg0.end();
851 173 : decode_view dseg0;
852 173 : if (it0 != seg0.begin())
853 : {
854 119 : --it0;
855 119 : dseg0 = **it0;
856 : }
857 173 : decode_view::iterator cit0 = dseg0.end();
858 173 : std::size_t skip0 = 0;
859 173 : bool at_slash0 = true;
860 307 : while (n0 > n1)
861 : {
862 134 : consume_last(n0, dseg0, begin0, it0, cit0, skip0, at_slash0);
863 : }
864 :
865 : // consume final segments from seg1 that
866 : // should not influence the comparison
867 173 : auto begin1 = seg1.begin();
868 173 : auto it1 = seg1.end();
869 173 : decode_view dseg1;
870 173 : if (it1 != seg1.begin())
871 : {
872 119 : --it1;
873 119 : dseg1 = **it1;
874 : }
875 173 : decode_view::iterator cit1 = dseg1.end();
876 173 : std::size_t skip1 = 0;
877 173 : bool at_slash1 = true;
878 207 : while (n1 > n0)
879 : {
880 34 : consume_last(n1, dseg1, begin1, it1, cit1, skip1, at_slash1);
881 : }
882 :
883 173 : int cmp = 0;
884 909 : while (n0)
885 : {
886 736 : char c0 = consume_last(
887 : n0, dseg0, begin0, it0, cit0, skip0, at_slash0);
888 736 : char c1 = consume_last(
889 : n1, dseg1, begin1, it1, cit1, skip1, at_slash1);
890 736 : if (c0 < c1)
891 36 : cmp = -1;
892 700 : else if (c1 < c0)
893 41 : cmp = +1;
894 : }
895 :
896 173 : if (cmp != 0)
897 41 : return cmp;
898 132 : if ( n00 == n10 )
899 130 : return 0;
900 2 : if ( n00 < n10 )
901 1 : return -1;
902 1 : return 1;
903 : }
904 :
905 : } // detail
906 : } // urls
907 : } // boost
908 :
909 :
|
