Subject: Re: URI equivalence (was Re: PaceFeedEquivalence)

From: Tim Bray <[email-masked]>
Date: Sun, 01 Aug 2004 08:24:08 -0700

On Jul 31, 2004, at 5:34 PM, Martin Duerst wrote:

>>> B) Some clients may perform all of these steps, but others may not,
>>> and therefore some will treat these URIs as identical but others
>>> won't.
>> B, so producers SHOULD NOT produce variant spellings of the same URI.
>
> There will be
> implementers that don't read the spec and will try to use this 
> equivalence,
> in the same way there are probably implementers out there that try to
> use case equivalence even when they are not supposed to.
>
> I could for example understand quite well that some spiders take
> http://example.com/UPPER and http://example.com/upper to be equivalent,

Martin, please react to what I actually said, not some fantasy 
exercise.  What I said is that software implementations will do an 
unpredictable set of things, all *within* the spec.  By the way, I have 
written two very large-scale web spiders that have processed in 
aggregate in excess of a billion URLs (and I wrote section 6 of 
2396bis), so I'm not making this up.

> Indeed, I do not
> know any server or client that would behave according to B above.

You do now.  See Sam's recent posting, 
http://www.intertwingly.net/blog/2004/07/31/URI-Equivalence, which 
makes it obvious that two popular software implementations, C# and 
Java, which I guarantee will be used by lots of programmers to compare 
URIs, do URI manipulation inside their equals() method, each one 
differently.  In fact, if you're a Java or C# programmer, you're going 
to have to do extra work to get codepoint rather than "smart" 
comparison.  It is foolish for us to try to stop this.  On the other 
hand, producers should not count on anything more.

The following is actually consistent with software reality:

  Authors of software which compares URIs for equivalence SHOULD 
consider the
  discussion in RFC2396bis Section 6, and such software MAY use
  codepoint-for-codepoint comparison.  Producers of URIs SHOULD NOT 
generate
  variant spellings of the same URI.

If someone wants to argue for a MUST NOT in that last sentence, it's 
worth considering.
  -Tim

---

From: Bill de hÓra <[email-masked]>
Date: Sun, 01 Aug 2004 18:21:00 +0100

Tim Bray wrote:

> [...reality...]
>  
>  Authors of software which compares URIs for equivalence SHOULD consider 
> the
>  codepoint-for-codepoint comparison.  Producers of URIs SHOULD NOT generate

I don't get it. What's the purpose of saying anything here unless 
there is sufficient specification to interoperate with? Whatever 
about reality-as-engineered, if the identity functions, invariants 
and whatnot are *clearly defined* it will be at least apparent what 
obligations producers and consumers are under. So we can file bug 
reports or contribute fixes and stuff.

cheers
Bill

---

From: Sam Ruby <[email-masked]>
Date: Sun, 01 Aug 2004 14:03:39 -0400

Tim Bray wrote:
>  Authors of software which compares URIs for equivalence SHOULD consider the

I'll argue for something stronger.  Different, but stronger.  Let me 
start by enumerating some first principles:

1) The purpose of <id> elements in atom is to enable efficient identity
    comparison.

2) Clients may use a variety of techniques for comparison varying from
    absolutely none to very aggressive normalization prior to comparison.

3) IDs will be transmitted by a variety of means including, but not
    limited to napkins, busses, and keynotes[1].

So, if we can't control how ids are consumed or transmitted, we control 
what we can: ids are recorded.  We have the Atom specification require 
that all ids MUST be in a canonical form.  We start with the rules in 
rfc 2396bis[2].  We add a few: URIs can't be relative.  URIs must be 
utf-8, in fact must be NFC (or whatever form we select).  For schemes 
which define an option port, we require that all ports be explicit (or 
alternately, we require any ports that match the default for the scheme 
chosen be omitted).

What are the benefits?  Interoperability without constraining how 
clients compare URIs.  And the feedvalidator can provide early detection 
of potential problems before they are problems.  And not 
insignificantly, requiring authors to actually think about how the 
define identity .  This last part should not be minimized, given all the 
discussion about not allowing relative URIs and perhaps even 
constraining the scheme to exclude HTTP.

What are the costs?  Authors of sofware will have add code to normalize 
their URIs.  Realistically, these costs will fall disproportionally on 
those who chose to use http URIs.  But even there, the costs likely to 
be minimal, as it can be observed that most URIs in the wild already 
conform to the canonicalization rules of rfc2396bis: the scheme is lower 
case, the character set is mostly ASCII, escaping is only done when 
needed, etc.

Finally, what happens if somebody ignores this requirement?  Beyond 
error messages from the feedvalidator, things will tend to degrade 
gracefully.  Identity comparisons will likely work anyway.  And when 
they don't, and users complain to aggregator authors (let's face it, 
that's who will receive the bulk of these complaints), the authors can 
point to the spec and the feedvalidator as evidence that the problem is 
in the feed itself.

Unless there is violent objection, I'll write up a Pace.

- Sam Ruby

[1]<http://www.imc.org/atom-syntax/mail-archive/msg08193.html>
[2]<http://www.gbiv.com/protocols/uri/rev-2002/draft-fielding-uri-rfc2396bis-03.html#canonical-form>

---

From: Joe Gregorio <[email-masked]>
Date: Sun, 1 Aug 2004 16:34:10 -0400

> Unless there is violent objection, I'll write up a Pace.

+1

-- 
Joe Gregorio        http://bitworking.org

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Sun, 1 Aug 2004 14:12:54 -0700

>    limited to napkins, busses, and keynotes[1].

Say what? Why on earth would I write a feed ID or an entry ID anywhere?

>Unless there is violent objection, I'll write up a Pace.

I non-violently object because I don't understand one of the pillars 
of your proposal.

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: Sam Ruby <[email-masked]>
Date: Sun, 01 Aug 2004 18:07:10 -0400

Paul Hoffman / IMC wrote:
> I non-violently object because I don't understand one of the pillars of 
> your proposal.

In the immortal words of an author of two very large-scale web spiders 
that have processed in aggregate in excess of a billion URLs[2], 
contributor to rfc 2396bis[3], and co-chair of this working group[4], 
"shit happens"[5].

Also, note that the napkins, busses, and keynotes comment was derived 
from another comment by Tim Bray[1].

On the topic of ids, it seems that comparision is the key operation.  My 
first preference would have been to define the rules precisely.  One 
such set of rules would be those defined by Namespaces in XML 1.1[6] 
which are entirely unambiguous.  However, given Tim's strong opinions on 
the subject, it appears likely that such a proposal would not achieve 
consensus.

So, given this reality - and in the interest of interoperability - if we 
can't constrain how ids are compared, I would like to constrain how ids 
are expressed.  Simply put, if people are permitted to use the .Net 
Uri.Equals or the Java URI.equals methods to determine atom:id 
equivalence, I want to make sure that they don't ever treat two distinct 
URIs as equivalent.

Looking at the rfc 2396bis rules, they seem very reasonable and natural. 
  In fact, none of the URI's listed after my signature would violate any 
of them.

- Sam Ruby

[1]<http://www.imc.org/atom-syntax/mail-archive/msg08193.html>
[2]<http://www.imc.org/atom-syntax/mail-archive/msg08213.html>
[3]<http://gbiv.com/protocols/uri/rev-2002/rfc2396bis.html#ack>
[4]<http://www.ietf.org/html.charters/atompub-charter.html>
[5]<http://www.imc.org/atom-syntax/mail-archive/msg08143.html>
[6]<http://www.w3.org/TR/2004/REC-xml-names11-20040204/#IRIComparison>

---

From: Joe Gregorio <[email-masked]>
Date: Mon, 2 Aug 2004 08:00:21 -0400

> the subject, it appears likely that such a proposal would not achieve

This is curious since my reading of the threads looks like 
there is rough concensus on Simple String Comparison 
for the atom:id.

    -joe

---

From: Sam Ruby <[email-masked]>
Date: Mon, 02 Aug 2004 08:43:35 -0400

> there is rough concensus on Simple String Comparison 

First, I'll assert that the rules defined by [6] are Simple String 
Comparison, and I would certainly agree to them.

I'm not sure that there is consensus, however.  For example, my read is 
that Tim wants to enable Simple String Comparision but not preclude 
other comparisons[1], and that Mark wants to require all normalizations 
other than protocol normalization[2].  Few others have weighed in recently.

My preference is that if we are going to allow multiple comparison 
algorithms, I want rules in place to ensure that all such comparisons 
get the same result.  Canonicalization achieves that.

- Sam Ruby

[6] http://www.w3.org/TR/2004/REC-xml-names11-20040204/#IRIComparison
[1] http://www.imc.org/atom-syntax/mail-archive/msg08143.html
[2] http://www.imc.org/atom-syntax/mail-archive/msg08138.html

---

From: Mark Pilgrim <[email-masked]>
Date: Mon, 2 Aug 2004 09:11:33 -0400

> there is rough concensus on Simple String Comparison

Well, it appears we've come full circle.  Norman Walsh suggested that
clients do simple string comparison [1], and Tim explicitly rejected
it [2].  What Sam is suggesting is that clients do simple string
comparison after the publisher canonicalizes the URI, i.e. publishing
uncanonicalized URIs is an error.  But only for atom:id, because it's
special.  (It is; its main purpose in life is for clients to compare
it to other atom:id values.  Thus, comparing should be made as simple
as possible, without introducing ambiguity.)

For that reason, I vehemently reject Tim's reasoning that "shit
happens" and "clients will all act differently anyway," therefore we
should throw up our hands, accept such differences, and bake ambiguity
into the spec.  You know what I call differences like that?  "Bugs." 
We're not judging an elementary school science fair here, where
everyone is a winner simply for participating.  If two programs
compare atom:ids for equivalence and come up with different answers,
at least one of them is wrong and should be fixed ASAP.  It's the
spec's job to say which one.  Why bother having an atom:id if you
can't tell if they're equivalent?  That's madness.

+1 to Sam's proposal.  Go write up PacePublisherNormalizesUri.  I'll
write up the test cases for the feed validator to check for
non-canonical URIs in atom:id.  All the clients in the world can
continue doing what they're doing already.

[1] http://intertwingly.net/wiki/pie/PaceFeedEquivalence
[2] http://www.imc.org/atom-syntax/mail-archive/msg08059.html

-- 
Cheers,
-Mark

---

From: Joe Gregorio <[email-masked]>
Date: Mon, 2 Aug 2004 09:22:49 -0400

> Comparison, and I would certainly agree to them.

Agreed.

> get the same result.  Canonicalization achieves that.

Agreed.

    -joe

---

From: Sam Ruby <[email-masked]>
Date: Mon, 02 Aug 2004 09:55:11 -0400

> Unless there is violent objection, I'll write up a Pace.

http://www.intertwingly.net/wiki/pie/PaceCanonicalIds

All I did was to capture the rules defined by rfc 2396bis with two 
additions, and provide illustrative examples (which will serve as the 
basis for feedvalidator test cases).

- Sam Ruby

---

From: Tim Bray <[email-masked]>
Date: Mon, 02 Aug 2004 07:32:24 -0700

On Aug 2, 2004, at 5:43 AM, Sam Ruby wrote:

> I'm not sure that there is consensus, however.  For example, my read 
> is that Tim wants to enable Simple String Comparision but not preclude 
> other comparisons[1], and that Mark wants to require all 
> normalizations other than protocol normalization[2].  Few others have 
> weighed in recently.

I want to go further and explicitly encourage simple string 
comparisons, but as your tests proved, doing simple-looking things like 
URI.equals() in Java and C# does more than that, and since this can 
never produce a false positive in real life, i.e., since it can never 
cause a problem, why write text to "preclude" it?  In Java/C#, the fact 
that you can do anything.equals(anythingElse) is actually kind of 
useful in some spots and it seems unnecessary and irritating if I have 
to write

boolean test;
if (anything instanceof atomID)
   test = anything.toString().equals(anythingElse.toString());
else
   test = anything.equals(anythingElse);
if (test)
   ....

> get the same result.  Canonicalization achieves that.

and, as you pointed out it's usually unnecessary and typically cheap. 
-Tim

---

From: Tim Bray <[email-masked]>
Date: Mon, 02 Aug 2004 07:34:54 -0700

+1

If we're going to require canonicalization of atom:id, we could go 
further and require all URIs in <link> and so on to be canonicalized, 
or at least suggest it with a SHOULD.  Makes all sorts of irritating 
little problems go away.  But then as a spider wrangler, I'm prejudiced 
:)

  -Tim

---

From: Asbjørn Ulsberg <[email-masked]>
Date: Mon, 02 Aug 2004 16:51:46 +0200

> http://www.intertwingly.net/wiki/pie/PaceCanonicalIds

I guess this pace should be easilly mergable with any other atom:id pace,  
so: +1.

-- 
Asbjørn Ulsberg         -=|=-        [email-masked]
«He's a loathsome offensive brute, yet I can't look away»

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Mon, 2 Aug 2004 09:02:54 -0700

>>I non-violently object because I don't understand one of the 
>>pillars of your proposal.
>
>In the immortal words of an author of two very large-scale web 
>spiders that have processed in aggregate in excess of a billion 
>URLs[2], contributor to rfc 2396bis[3], and co-chair of this working 
>group[4], "shit happens"[5].

Fully agree.

>Also, note that the napkins, busses, and keynotes comment was 
>derived from another comment by Tim Bray[1].

Tim never said that Atom IDs would show up in any of those place. 
This is *exactly* the problem if using URIs as Atom IDs: people think 
that the two have similar properties in the real world.

>On the topic of ids, it seems that comparision is the key operation. 
>My first preference would have been to define the rules precisely. 
>One such set of rules would be those defined by Namespaces in XML 
>1.1[6] which are entirely unambiguous.  However, given Tim's strong 
>opinions on the subject, it appears likely that such a proposal 
>would not achieve consensus.

Tim is one member of the WG, and is no more important than anyone else.

I will soon propose that atom:id is a plain-old-text string, and that 
atom:link is the thing that is dereferenceable.

--Paul Hoffman, Director

---

From: Asbjørn Ulsberg <[email-masked]>
Date: Mon, 02 Aug 2004 18:52:50 +0200

> atom:link is the thing that is dereferenceable.

I would not be -1 on that. (Initially, at least.)

---

From: Dare Obasanjo <[email-masked]>
Date: Mon, 2 Aug 2004 10:29:43 -0700 (PDT)

> the subject, it appears likely that such a proposal

So if one person objects we can't reach consensus? 
 
> equivalence, I want to make sure that they don't

This looks like you are trying to 'hack around' Tim's
objections by achieve the same thing with different
wording. If URIs are always in canonical form then
there is no need to specify the comparison algorithm. 

It seems like a case of six of one and half a dozen of
the other. +1 either way. 

> signature would violate any 

Good. 

=====
THINGS TO DO IF I BECOME AN EVIL OVERLORD #25
No matter how well it would perform, I will never construct any sort of machinery which is completely indestructible except for one small and virtually inaccessible vulnerable spot.

__________________________________
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!
http://promotions.yahoo.com/new_mail

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Mon, 02 Aug 2004 22:02:12 +0200

>alternately, we require any ports that match the default for the scheme 

I think I am opposed to any conformance criteria for which one cannot
write software that determines whether the criteria are met. Here in
particular it is not possible to determine whether the default port is
omitted or not as that would require to know the default port which
would require to know about all present and future schemes. The other
criteria you cite are also problematic. It would be okay to stuff such
criteria into a separate layer, e.g. one that differentiates whether
Atom documents using extensions use these extensions properly.

---

From: Sam Ruby <[email-masked]>
Date: Mon, 02 Aug 2004 16:36:24 -0400

> Atom documents using extensions use these extensions properly.

Presumably, if you chose to support a given scheme, you understand that 
scheme.  As an example, Tim Bray is likely to use http, and probably has 
already figured out that port 80 is the default for that scheme.

For the feedvalidator, I'll probably start with the following set:
   ftp:       21
   telnet:    23
   gopher:    70
   http:      80
   news:     119
   nntp:     119
   prospero: 191
   https:    443
   snews:    563
   snntp:    563

- Sam Ruby

---

From: "Bob Wyman" <[email-masked]>
Date: Mon, 2 Aug 2004 17:38:35 -0400

Sam Ruby wrote:
> we require that all ports be explicit (or 
> alternately, we require any ports that match
> the default for the scheme chosen be omitted).
	These words seem to assume "old style" port assignment practices.
(I.e. the use of fixed ports). New protocols are "supposed" to use DNS SRV
records to disclose port assignments and some actually do (i.e. BEEP, APEX,
and a few others). To *require* that ports be explicit seems to risk making
unreasonable constraints on some schemes and would root Atom in practices
that many would argue should be discouraged.

		bob wyman

---

From: Sam Ruby <[email-masked]>
Date: Mon, 02 Aug 2004 17:47:15 -0400

> that many would argue should be discouraged.

I presume that you are catching up on email... upon further reflection, 
I decided to flip that.  See:

- Sam Ruby

---

From: Walter Underwood <[email-masked]>
Date: Sun, 08 Aug 2004 15:41:49 -0700

--On Monday, August 2, 2004 7:34 AM -0700 Tim Bray <[email-masked]> wrote:
> little problems go away.  But then as a spider wrangler, I'm prejudiced :)

+1

Spider wranglers of the world, unite!

If we require that servers have canonicalization routines for ID,
why not use them elsewhere?

wunder
--
Walter Underwood
Principal Architect, Verity

---

From: Joe Gregorio <[email-masked]>
Date: Mon, 9 Aug 2004 22:27:26 -0400

On Fri, 30 Jul 2004 21:23:53 -0700, Tim Bray <[email-masked]> wrote:
> 
> On Jul 30, 2004, at 5:21 PM, Martin Duerst wrote:
> 
> > My baseline opinion is still very strongly to only require
> > character-by-character (also called codepoint-by-codepoint)
> > comparison for ids. This is the one thing that is easiest
> > for all implementations to get right.
> 
> I think we're all in agreement that this is all that should be
> required.  However, we should acknowledge that robots and that class of
> software will go further, and while it's not required there's nothing
> wrong with that. -Tim

No, we shouldn't acknowledge that.

The robot/spider argument falls apart when you break it 
down into its component parts.

Why?

1. Robots either know about the Atom format or they don't.
1.1 If a robot knows about Atom then when it finds a URI for the 
      atom:id it will know that it is an id and NOT dereference it
      but instead use it to identify duplicate entries. [Look at
      the performace improvement here, we removed an entire
      HTTP Request.]

1.2 If a robot doesn't know about the Atom format
      then it will find the URI, perform all the Normalizations
      you have already discussed, and then proceed to dereference 
      it. [Here the robot, being ignorant of the atom:id, is wasting its
      time dereferencing an atom:id, but since it is not comparing
      equivalence of atom entries it. does. not. matter.]

So let's just keep the comparison of 
atom:id's simple by requiring character-by-character
comparisons. I would prefer not to complexify the 
specification for no reason.

    -joe