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