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