Subject: Re: URI canonicalization

From: "Roy T. Fielding" <[email-masked]>
Date: Mon, 31 Jan 2005 21:57:01 -0800

There is no reason to require any particular comparison algorithm.
One application is going to compare them the same way every time.
Two different applications may reach different conclusions about
two equivalent identifiers, but nobody cares because AT WORST the
result is a bit of inefficient use of storage.

The guidance, if any, should simply state that identifier
constructs must be unique.  It is not our responsibility to
prevent people from assigning the same (equivalent) identifiers
to two different resources, nor do I care how many errors
occur when they violate such a basic requirement.

....Roy

---

From: Sam Ruby <[email-masked]>
Date: Tue, 01 Feb 2005 07:48:48 -0500

> result is a bit of inefficient use of storage.

It is worse than that.  To give a concrete example: Radio Userland's 
aggregator will not present to you an item that you have seen before, no 
matter how different the current content is.

- Sam Ruby

---

From: Henry Story <[email-masked]>
Date: Tue, 1 Feb 2005 17:01:15 +0100

On 1 Feb 2005, at 13:48, Sam Ruby wrote:
> aggregator will not present to you an item that you have seen before, 
> no matter how different the current content is.

So? They will just go out of business, as people find better 
aggregators or editors.
Leaves a bit of space for my Open Source, BSD licenced BlogEd to make 
headway.

Henry Story

---

From: Sam Ruby <[email-masked]>
Date: Tue, 01 Feb 2005 13:50:00 -0500

Henry Story wrote:
> So? They will just go out of business, as people find better aggregators 
> or editors.

That was just one example.  NetNewsWire will correlate messages with 
equivalent ids and optionally present HTML diffs.

Identifying which messages have been seen before and which ones have not 
is a significant area where the user experience with current aggregators 
has been suboptimal.

- Sam Ruby

---

From: Antone Roundy <[email-masked]>
Date: Tue, 1 Feb 2005 15:33:04 -0700

> occur when they violate such a basic requirement.
While we certainly shouldn't be in the business of saying "IDs MUST be 
compared using the C function 'strcmp'", I think we need to be specific 
about what it means for an IDs to be unique. Given that we're using 
URIs as IDs, and two URIs can be functionally identical without being 
characterwise identical, we need to explain that we mean by "unique".  
If we don't want to mandate a particular algorithm, then we need to 
find a way to get the point across some other way.  Perhaps (the first 
sentence is the existing first sentence):

    Instances of Identity constructs can be compared to determine whether
    an entry or feed is the same as one seen before.  The values of two
    Identity constructs are considered to be the same if a case-sensitive
    character-by-character comparison would recognize them as identical.

This language doesn't mandate actually performing a "case-sensitive 
character-by-character comparison", but it should be clear from the 
this language what it means to be the same.  If we want to get even 
further from talking about algorithms, we could go with something like 
this, but it begins to sound a little strained:

    Instances of Identity constructs can be compared to determine whether
    an entry or feed is the same as one seen before.  The values of two
    Identity constructs are considered to be the same if they contain 
exactly
    the same code points in exactly the same order.

If we want to get even more precise, and don't mind getting more wordy:

    Instances of Identity constructs can be compared to determine whether
    an entry or feed is the same as one seen before.  The values of two
    Identity constructs are considered to be the same if, after XML
    deserialization, but before any other processing such as decoding of
    percent-encoded characters, they contain exactly the same code points
    in exactly the same order.

---

From: Graham <[email-masked]>
Date: Tue, 1 Feb 2005 23:03:32 +0000

>    character-by-character comparison would recognize them as identical.

Aren't we approaching this problem from the wrong end? The id spec 
should be instructions for publishers saying "Any two versions of the 
same entry must use the same id, which requires that all characters are 
the same. Any two different entries must have different ids, which 
requires that at least one character is different [we could also go 
further and say they should canonicalize to different things or some 
such]." That way publishers know what to do, consumers know what the 
publishers are trying to express, but aren't constrained in their 
implementations, and we also define "permanent" and "universally 
unique", which the current spec fails to.

Graham

---

From: Eric Scheid <[email-masked]>
Date: Wed, 02 Feb 2005 10:33:24 +1100

> unique", which the current spec fails to.

+1

---

From: "Roy T. Fielding" <[email-masked]>
Date: Tue, 1 Feb 2005 16:18:12 -0800

> no matter how different the current content is.

So, at worst, if two different feeds use the same id, then the
first one received will eclipse all later ones.  How does requiring
a specific comparison algorithm change that?  The goal should be
different ids, not jumping through hoops to artificially
differentiate between equivalent URIs.

Besides, I don't think that existing sites with obvious security
holes should be used as an example for format requirements, unless
said requirements are going to close those holes.

....Roy

---

From: "Roy T. Fielding" <[email-masked]>
Date: Tue, 1 Feb 2005 16:52:40 -0800

On Feb 1, 2005, at 3:03 PM, Graham wrote:
> same entry must use the same id, which requires that all characters 
> are the same. Any two different entries must have different ids, ...

Yes, place the requirement where it will do some good.  It is
okay to require publishers to spell their URIs consistently.
There is no need to explain what "different ids" means -- any two
URIs that are different identifiers will never compare as
"equivalent", regardless of the comparison algorithm used.

....Roy

---

From: Graham <[email-masked]>
Date: Wed, 2 Feb 2005 01:12:10 +0000

> "equivalent", regardless of the comparison algorithm used.

Pardon? If I use case sensitive ids (eg base64 style 
"http://www.example.com/aBCde" and "http://www.example.com/aBCdE" are 
different), and the client is case-insensitive, that's not going to 
work.

Graham

---

From: "Roy T. Fielding" <[email-masked]>
Date: Tue, 1 Feb 2005 18:34:32 -0800

> different), and the client is case-insensitive, that's not going to 

I meant regardless of the URI comparison algorithm used, as
described in RFC3986.  I wouldn't expect comparison based on
number of "1" bits to work either.

....Roy

---

From: Graham <[email-masked]>
Date: Wed, 2 Feb 2005 02:39:51 +0000

> number of "1" bits to work either.

That RFC defines 4 different levels of equivalence. I'd be happy for 
the spec to say "Two different entries must have ids that are different 
under all provisions of RFC3986 Sect 6.2" This would also remove the 
last barrier to losing the canonicalization fluff.

Graham

---

From: Eric Scheid <[email-masked]>
Date: Wed, 02 Feb 2005 18:01:55 +1100

On 2/2/05 11:52 AM, "Roy T. Fielding" <[email-masked]> wrote:

> any two

what about false negatives though?

e.