Re: #1047 Path field delimiters and syntax - status

[Seth Breidbart <sethb@xxxxxxxxx>]

Bruce Lilly <blilly@xxxxxxxxx> wrote:

> Note that there are any number of ways to do so which do not require
> parsing the Path field more than once, or other than left-to-right,
> at any given server.  It necessarily means comparing M non-comment,
> non- diagnostic, non-keyword, non-bogus path entries to N peer names
> (although clearly the tests can be short-circuited once a match for
> a specific peer is found). For an article with M valid path entries
> and at a site with N peers, none of which are listed in the path
> field, that is a minimum complexity of O(N*M).

We just had that discussion.  It's O(N+M), where M is the length of
the Path header and N is the sum of the lengths of the peer names.

"I can't think of a faster way" does not imply "minimum complexity";
complexity theory is non-trivial.

> 1. skipping from '(' to the matching unquoted ')' is outside of the
>   loop; it is one-time field parsing and none of the skipped content
>   is checked against any peer names.  Nor does it affect the number
>   of non-comment entries to be checked.

If there's a simple (O(1)) way to determine what is or isn't part of a
comment as you read the Path header, then the overall complexity is
still O(N+M).  (Note that this doesn't imply that "commentness" is a
regular expression, deterministic context-free is good enough, so
nested comments aren't a problem.)

>> All of which is why we removed <comment>s from the Path quite some
> time ago.
>
> "we" didn't remove them.  It was a one-person, non-consensus, unilateral
> action based on flawed reasoning.

OK, who put comments _into_ Path?

Seth