Relative path resolver without normalization

[RobinTF]

Hi,
I was wondering if I could use Boost.URL to implement resolving of relative IRIs as mandated in the SPARQL standard:
https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#relIRIs

Basically it refers to section 5.2 of the RFC 3986, but explicitly states that "Neither Syntax-Based Normalization nor Scheme-Based Normalization (described in sections 6.2.2 and 6.2.3 of RFC3986)" should be performed, which is done by Boost.URL without any way to turn it off.
So that leads me to two questions:

1. Could you implement a variant of the resolve algorithm that explicitly only removes dot segments?
2. And if not, could I just copy the code and replace all calls to normalize_path with calls to

   url/src/detail/normalize.cpp

   Lines 316 to 613 in 3f8a428

   	std::size_t
   	remove_dot_segments(
   	char* dest0,
   	char const* end,
   	core::string_view input) noexcept
   	{
   	// 1. The input buffer `s` is initialized with
   	// the now-appended path components and the
   	// output buffer `dest0` is initialized to
   	// the empty string.
   	char* dest = dest0;
   	bool const is_absolute = input.starts_with('/');
   	// Step 2 is a loop through 5 production rules:
   	// https://www.rfc-editor.org/rfc/rfc3986#section-5.2.4
   	//
   	// There are no transitions between all rules,
   	// which enables some optimizations.
   	//
   	// Initial:
   	// - Rule A: handle initial dots
   	// If the input buffer begins with a
   	// prefix of "../" or "./", then remove
   	// that prefix from the input buffer.
   	// Rule A can only happen at the beginning.
   	// Errata 4547: Keep "../" in the beginning
   	// https://www.rfc-editor.org/errata/eid4547
   	//
   	// Then:
   	// - Rule D: ignore a final ".." or "."
   	// if the input buffer consists only of "."
   	// or "..", then remove that from the input
   	// buffer.
   	// Rule D can only happen after Rule A because:
   	// - B and C write "/" to the input
   	// - E writes "/" to input or returns
   	//
   	// Then:
   	// - Rule B: ignore ".": write "/" to the input
   	// - Rule C: apply "..": remove seg and write "/"
   	// - Rule E: copy complete segment
   	auto append =
   	[](char*& first, char const* last, core::string_view in)
   	{
   	// append `in` to `dest`
   	BOOST_ASSERT(in.size() <= std::size_t(last - first));
   	std::memmove(first, in.data(), in.size());
   	first += in.size();
   	ignore_unused(last);
   	};
   	auto dot_starts_with = [](
   	core::string_view str, core::string_view dots, std::size_t& n)
   	{
   	// starts_with for encoded/decoded dots
   	// or decoded otherwise. return how many
   	// chars in str match the dots
   	n = 0;
   	for (char c: dots)
   	{
   	if (str.starts_with(c))
   	{
   	str.remove_prefix(1);
   	++n;
   	continue;
   	}
   	// In the general case, we would need to
   	// check if the next char is an encoded
   	// dot.
   	// However, an encoded dot in `str`
   	// would have already been decoded in
   	// url_base::normalize_path().
   	// This needs to be undone if
   	// `remove_dot_segments` is used in a
   	// different context.
   	// if (str.size() > 2 &&
   	// c == '.'
   	// &&
   	// str[0] == '%' &&
   	// str[1] == '2' &&
   	// (str[2] == 'e' ||
   	// str[2] == 'E'))
   	// {
   	// str.remove_prefix(3);
   	// n += 3;
   	// continue;
   	// }
   	n = 0;
   	return false;
   	}
   	return true;
   	};
   	auto dot_equal = [&dot_starts_with](
   	core::string_view str, core::string_view dots)
   	{
   	std::size_t n = 0;
   	dot_starts_with(str, dots, n);
   	return n == str.size();
   	};
   	// Rule A
   	std::size_t n;
   	while (!input.empty())
   	{
   	if (dot_starts_with(input, "../", n))
   	{
   	// Errata 4547
   	append(dest, end, "../");
   	input.remove_prefix(n);
   	continue;
   	}
   	else if (!dot_starts_with(input, "./", n))
   	{
   	break;
   	}
   	input.remove_prefix(n);
   	}
   	// Rule D
   	if( dot_equal(input, "."))
   	{
   	input = {};
   	}
   	else if( dot_equal(input, "..") )
   	{
   	// Errata 4547
   	append(dest, end, "..");
   	input = {};
   	}
   	// 2. While the input buffer is not empty,
   	// loop as follows:
   	while (!input.empty())
   	{
   	// Rule B
   	bool const is_dot_seg = dot_starts_with(input, "/./", n);
   	if (is_dot_seg)
   	{
   	input.remove_prefix(n - 1);
   	continue;
   	}
   	bool const is_final_dot_seg = dot_equal(input, "/.");
   	if (is_final_dot_seg)
   	{
   	// We can't remove "." from a core::string_view
   	// So what we do here is equivalent to
   	// replacing s with '/' as required
   	// in Rule B and executing the next
   	// iteration, which would append this
   	// '/' to the output, as required by
   	// Rule E
   	append(dest, end, input.substr(0, 1));
   	input = {};
   	break;
   	}
   	// Rule C
   	bool const is_dotdot_seg = dot_starts_with(input, "/../", n);
   	if (is_dotdot_seg)
   	{
   	core::string_view cur_out(dest0, dest - dest0);
   	std::size_t p = cur_out.find_last_of('/');
   	bool const has_multiple_segs = p != core::string_view::npos;
   	if (has_multiple_segs)
   	{
   	// output has multiple segments
   	// "erase" [p, end] if not "/.."
   	core::string_view last_seg(dest0 + p, dest - (dest0 + p));
   	bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
   	if (!prev_is_dotdot_seg)
   	{
   	dest = dest0 + p;
   	}
   	else
   	{
   	append(dest, end, "/..");
   	}
   	}
   	else if (dest0 != dest)
   	{
   	// Only one segment in the output: remove it
   	core::string_view last_seg(dest0, dest - dest0);
   	bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
   	if (!prev_is_dotdot_seg)
   	{
   	dest = dest0;
   	if (!is_absolute)
   	{
   	input.remove_prefix(1);
   	}
   	}
   	else
   	{
   	append(dest, end, "/..");
   	}
   	}
   	else
   	{
   	// Output is empty
   	if (is_absolute)
   	{
   	append(dest, end, "/..");
   	}
   	else
   	{
   	// AFREITAS: Although we have no formal proof
   	// for that, the output can't be relative
   	// and empty at this point because relative
   	// paths will fall in the `dest0 != dest`
   	// case above of this rule C and then the
   	// general case of rule E for "..".
   	append(dest, end, "..");
   	}
   	}
   	input.remove_prefix(n - 1);
   	continue;
   	}
   	bool const is_final_dotdot_seg = dot_equal(input, "/..");
   	if (is_final_dotdot_seg)
   	{
   	core::string_view cur_out(dest0, dest - dest0);
   	std::size_t p = cur_out.find_last_of('/');
   	bool const has_multiple_segs = p != core::string_view::npos;
   	if (has_multiple_segs)
   	{
   	// output has multiple segments
   	// "erase" [p, end] if not "/.."
   	core::string_view last_seg(dest0 + p, dest - (dest0 + p));
   	bool const prev_is_dotdot_seg = dot_equal(last_seg, "/..");
   	if (!prev_is_dotdot_seg)
   	{
   	dest = dest0 + p;
   	append(dest, end, "/");
   	}
   	else
   	{
   	append(dest, end, "/..");
   	}
   	}
   	else if (dest0 != dest)
   	{
   	// Only one segment in the output: remove it
   	core::string_view last_seg(dest0, dest - dest0);
   	bool const prev_is_dotdot_seg = dot_equal(last_seg, "..");
   	if (!prev_is_dotdot_seg) {
   	dest = dest0;
   	}
   	else
   	{
   	append(dest, end, "/..");
   	}
   	}
   	else
   	{
   	// Output is empty: append dotdot
   	if (is_absolute)
   	{
   	append(dest, end, "/..");
   	}
   	else
   	{
   	// AFREITAS: Although we have no formal proof
   	// for that, the output can't be relative
   	// and empty at this point because relative
   	// paths will fall in the `dest0 != dest`
   	// case above of this rule C and then the
   	// general case of rule E for "..".
   	append(dest, end, "..");
   	}
   	}
   	input = {};
   	break;
   	}
   	// Rule E
   	std::size_t p = input.find_first_of('/', 1);
   	if (p != core::string_view::npos)
   	{
   	append(dest, end, input.substr(0, p));
   	input.remove_prefix(p);
   	}
   	else
   	{
   	append(dest, end, input);
   	input = {};
   	}
   	}
   	// 3. Finally, the output buffer is set
   	// as the result of remove_dot_segments,
   	// and we return its size
   	return dest - dest0;
   	}

   to make it work?

Thank you.

[alandefreitas]

Hi!

I'm trying to understand the problem.

What Syntax or Scheme-Based Normalization is being performed by Boost.URL and would have to be conditionally removed? And by what functions?

Are you sure you need none of that in

url/include/boost/url/impl/url_base.hpp

Line 1998 in 3f8a428

normalize_path()

?

Because this function is doing these three operations:

• normalize_octets_impl
• validating commas in the first segment
• remove_dot_segments

With the exception of normalize_octets_impl, the other two operations aren't optional for ensuring valid URLs, and url_view can't hold invalid URLs. Even normalize_octets_impl might affect how step 2 goes, so I wouldn't be so sure it's optional.

[RobinTF]

@alandefreitas The RFC gives an example:

6.2.2.  Syntax-Based Normalization

   Implementations may use logic based on the definitions provided by
   this specification to reduce the probability of false negatives.
   This processing is moderately higher in cost than character-for-
   character string comparison.  For example, an application using this
   approach could reasonably consider the following two URIs equivalent:

      example://a/b/c/%7Bfoo%7D
      eXAMPLE://a/./b/../b/%63/%7bfoo%7d

   Web user agents, such as browsers, typically apply this type of URI
   normalization when determining whether a cached response is
   available.  Syntax-based normalization includes such techniques as
   case normalization, percent-encoding normalization, and removal of
   dot-segments.

and the boost documentation for normalize path states:

Applies Syntax‐based normalization to the URL path.

Percent‐encoding triplets are normalized to uppercase letters.
Percent‐encoded octets that correspond to unreserved characters are decoded
Redundant path‐segments are removed.

https://www.boost.org/doc/libs/latest/doc/antora/url/reference/boost/urls/url/normalize_path.html

So basically I can't have the upper lowercase logic and normalisation of percent encoded values I believe.

[alandefreitas]

and normalisation of percent encoded values

What about the initial encoding of commas? Won't this lead to invalid URLs?

[RobinTF]

@alandefreitas You mean syntactically invalid?
Wouldn't that imply that the original URL is also invalid?
If the values are invalid before resolving the result doesn't matter. Garbage in garbage out

[alandefreitas]

Wouldn't that imply that the original URL is also invalid?

I don't think so.

[RobinTF]

@alandefreitas Can you provide an example?

[alandefreitas]

Consider ./foo:bar: a valid relative reference (the ./ prefix disambiguates it from a URI with scheme foo, per RFC 3986 Section 4.2).

After remove_dot_segments, the ./ is removed, leaving foo:bar. This is no longer a relative reference: any conforming parser will interpret foo as a scheme. The meaning of the URL has changed entirely, so the result is wrong.

That's why normalize_path needs the colon-encoding step: it produces foo%3Abar to keep the result a valid relative reference with the same meaning as the original.

This is handled in normalize_path (url_base.hpp:2033-2056): when it sees a ./ prefix on a no-scheme, no-authority URL, it checks whether removing the ./ would expose a colon in the first segment and sets encode_colons = true.

[RobinTF]

@alandefreitas Sorry for my delayed response, but I've finally gotten around to do some experiments, comparing the Boost.URL implementation against the uriparser C library, which claims to be 100% spec compliant.

Base URL: http://example.com/abc/def/

relative URL	uriparser	Boost.URL
%2E%2E/xyz	http://example.com/abc/def/%2E%2E/xyz	http://example.com/abc/xyz
../xyz	http://example.com/abc/xyz	http://example.com/abc/xyz
/%c3%A4	http://example.com/%c3%A4	http://example.com/%C3%A4
./foo:bar	http://example.com/abc/def/foo:bar	http://example.com/abc/def/foo:bar

So as you can see, there are some minor differences between the two, nothing too crazy, but the %2E%2E for example is not treated as a relative folder in this case. I think I misunderstood your original argument, you were talking about the code of this library (which absolutely makes sense), where I was thinking about the definition of the standard (I think).

[alandefreitas]

So the difference between them is just that uriparser doesn't normalize it (not even removing path segments)? And by "doesn't normalize it," I actually mean "it only applies an arbitrary subset of the normalization rules" (because some segments are in fact being collapsed)?

The pattern I'm noticing is that in one extreme, you can just append the relative path to the base path. At the other extreme, you have appending and normalization (or a cheaper operation as if that happened). I see value in both extremes, but everything in between (arbitrary partial normalization) seems hard to justify.

[RobinTF]

@alandefreitas Yes, pretty much. No idea why the URL RFC does explicitly treat "Syntax-Based Normalization" and "Scheme-Based Normalization" differently.

[alandefreitas]

No idea why the URL RFC does explicitly treat "Syntax-Based Normalization" and "Scheme-Based Normalization" differently.

"Scheme-Based Normalization" differently depends on the scheme. For instance, when the scheme is HTTP and the port is 80, you can omit the port because that's the default port, and both URLs point to the same resource once we assume the scheme's rules.

In "Syntax-Based Normalization", which is the only thing we and other URL libraries support, we don't make assumptions about the scheme. So we only apply normalization that's valid for any URL with any scheme.

[RobinTF]

@alandefreitas I see, so what do you think? Is it feasible for Boost.URL to provide a mode without the extra normalize in the near future? It's quite the hassle to use the uriparser lib in comparison.

[alandefreitas]

without the extra normalize

But that's the point. Maybe I'm missing something but there's absolutely no extra normalization in Boost.URL. I just did the same comparison with node just to be sure:

relative URL	uriparser	Boost.URL	Node.js URL
%2E%2E/xyz	http://example.com/abc/def/%2E%2E/xyz	http://example.com/abc/xyz	http://example.com/abc/xyz
../xyz	http://example.com/abc/xyz	http://example.com/abc/xyz	http://example.com/abc/xyz
/%c3%A4	http://example.com/%c3%A4	http://example.com/%C3%A4	http://example.com/%c3%A4
./foo:bar	http://example.com/abc/def/foo:bar	http://example.com/abc/def/foo:bar	http://example.com/abc/def/foo:bar

Boost.URL matches Node.js URL in all cases. http://example.com/abc/def/%2E%2E/xyz is not according to the spec and a safety issue. http://example.com/%c3%A4 is not according to the spec and creates unnecessary ambiguity / false positives.

As far as I understand, what Boost.URL provides is just regular normalization exactly as described by the RFC. No more and no less.

• If you want resolution with no normalization, you can just append the string.
• If you want regular vanilla normalization by the spec, that's what Boost.URL does.

What uriparser seems to be doing is partial normalization (which is, in fact, quite dangerous because the ".." was left in the final URL). But if we want a feature for partial normalization, this is what needs extra motivation and specification. In other words, what subset of normalization rules would we apply and why? Of course, we could abstract the problem once again, break down all normalization rules into individual options, and the user would be forced to always pass an object specifying which normalization rules should be applied, but this has its own problems. This complexity would need even more motivation because it's basically a safety issue now (for instance, the user could use patterns that would leave the dotdot segments there, etc).

[RobinTF]

@alandefreitas Well the RFC 3986 which defines how URIs work describes the resolver algorithm in section 5.2. And this base algorithm does explicitly only "normalize" the . and .. segments if any. This is what I want to follow the SPARQL spec, which explicitly prohibits the normalization of section 6.2.2 and 6.2.3. Your claim that just appending would resolve the URL is not true, you can't just append http://example or just /example, or even abc to a base url like http://test/xyz that would result in the wrong URL (that's more or less what we've been doing so far and it doesn't work for so many cases, that's why I want to replace it in the first place).
For my use-case in the SPARQL context the URIs (or rather IRIs) are not really used as references to actual URLs most of the time, instead they are just used as textual representations of an id to differentiate different items.
I don't know why the SPARQL standard prohibits syntax based normalization, nor do I think that's a particularly useful restriction, but I'd like to follow the standard, however silly it may be.

[alandefreitas]

Your claim that just appending would resolve the URL is not true

Yes. You're right. I meant that the resulting URL would be valid. The implied assumption was that we're only talking about paths, and you would check if the "/" suffixes and prefixes match. Sorry for making too many assumptions here. 😅

in the SPARQL context the URIs

At this point, I'm not sure whether the requirements for the SPARQL spec and for uriparser (which you used as an example) are meant to illustrate the same thing. In fact, I think we changed the point of the discussion a few times. The latest discussion, number 2, was about uriparser, and it seems to be more about who implements the spec correctly rather than a subset of normalization. It seems like uriparser doesn't collapse %2E%2E, while Boost.URL and node do. It also seems like uriparser and node don't uppercase the hex decimals.

Back to the issue...

I think the feature request and the problem being solved are valid, but I also think it's currently underspecified with what we know about the problem. We need to answer a few questions and develop a design that doesn't conflict with what we have right now. The solution you want, "a relative path resolver without normalization," is what needs to be specified. I'll try to explain what terminology I've been using and why there are still open questions.

Back to "discussion 1" about SPARQL, the point I was trying to make depends on our agreeing on the terminology. I've been referring to this as a subset of the normalization steps, because remove_dot_segments is a normalization step. It's not that obvious that this is an extra step or special step, or anything. Or that the other steps are extra, special, or anything. Because a URL after "5.2.2 Transform References" but before "5.2.4. Remove Dot Segments" is already resolved, but unnormalized, since the definition of resolved and normalized in the RFC is in terms of false negatives and positives. For instance, a/b/../c and a/c are both resolved because they point to the same resource (no false negatives). They're not normalized because a/c is the canonical string for this resource (no false positives). "6.2.2.3. Path Segment Normalization" is concerned defines "5.2.4. Remove Dot Segments" as a normalization step just like any other.

I hope I wasn't too tedious in this description, and I promise I'm not nitpicking. I understand you could then reasonably say it's just too obvious that "5.2.4. Remove Dot Segments" is clearly a special normalization step because it makes part of a definition of "special" in this context as "the minimum set of normalization steps necessary for (safe?) URL resolution". This seems a little arbitrary, but not so much because "5.2.1. Pre-parse the Base URI" says:

Normalization of the base URI, as described in Sections [6.2.2](https://datatracker.ietf.org/doc/html/rfc3986#section-6.2.2) and 6.2.3, is optional.  A URI reference must be transformed to its target URI before it can be normalized.

So the first set of open questions is, what precisely does that mean? This leaves a lot of room for interpretation:

• If normalizing the base URI is optional, is normalizing the relative URL optional as well?
• Is normalizing the ultimate target URI optional?
• Also, if the last sentence means we should resolve and then normalize, then we can indeed separate the steps into resolution-only (without normalization) and normalization-only.

(Maybe not all of them need to be answered because the answer to one question might invalidate other questions)

Then the second set of questions is what precisely this is allowed to mean:

• Note that not all interpretations of the paragraph above are equally valid. For instance, as I noted before, if resolution includes no normalization at all, there would be no remove_dot_segments. It would just be "5.2.2. Transform References" and "5.2.3. Merge Paths". Does this solve the problem? From what you said so far, I don't think it does.
• But let's assume that it's just "too obvious" that we need "5.2.4. Remove Dot Segments" to go with resolution "without normalization", or that we need at least two more versions of the function: a) resolution with all normalization steps applied, b) transform references + remove dot segments only, c) transform references only. So, should we implement versions b and c?
• Now we have a new open question, which is what to do about other normalization steps that remove-dot-segments depend on. I gave an example regarding initial dot segments, and we've also just seen an example where uriparser generates a problematic URL.
• Are these other normalization steps also included in the minimal set of normalizations?
• Should unsafe operations (uriparser did) be part of the minimal set?
• Should operations that potentially lead to false negatives be in the set?
• Should operations that break the URL (like the case with initial dot segments) be in this set?
• What does that final set look like? Will it end up being "all steps minus uppercasing the hex values"?
• And if so, is it worth the effort?
• Is the argument for the ROI on this function based on the assumption that normalization steps are all independent? In other words, do we have the argument for "since all steps potentially depend on each other, let's provide all steps minus uppercasing the hex values, because that's the only one that wouldn't potentially break the URL" that is as good as the argument for "why not provide this as a separate function since they're all completely independent anyway".

The answers to these questions are hard to find. In most of these cases, once people notice that the steps depend on each other to maintain valid URLs, I think implementations just look at what other implementations do, and all implementations end up merging normalization with resolution to some extent to make it safe. That's why uriparser, Boost.URLs and Node.js URLs look the way they do, but they all include some normalization step with resolution. Even the behavior of "5.2.2. Transform References" tends to be different from one library to another.