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