src/detail/normalize.cpp

99.5% Lines (396 / 398) 100.0% Functions (25 / 25)

[ ] prev/next file n p prev/next uncovered line

normalize.cpp

f(x) Functions (25)

Function Calls Lines Blocks

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