Subject: Query on discovery algoritm for LRDD (draft-hammer-discovery-04)

From: John Panzer <[email-masked]>
Date: Thu, 25 Mar 2010 16:41:29 -0700

All,

This is my attempt to translate *
http://tools.ietf.org/html/draft-hammer-discovery-04* into an actionable
algorithm, as a first step in attempting to write a truly general resource
discovery library that matches the latest spec.  It is written under the
assumption that a client may wish to query for sets of links with a given
relvalue, and is not going to wish to retrieve and re-parse host-meta files
any more often than necessary.  Feedback welcomed!

*Definitions*

   - *startURI*: Starting point for discovery; input into the discovery
   process.  Discovery produces metadata for *startURI.*
   - *meta data:*A collection of links and properties for the resource.
   - *link*: An abstract edge between the*startURI*resource and another
   resource identified by a field *href.  *Has a*rel*field indicating the
   relationship from *startURI *to *href.* Has a *lrdd_pri *field indicating
   ordering within the *rel *value.  Has a *secure *boolean field indicating
   whether it was retrieved securely.  Can be annotated with arbitrary *
   properties*.
   - *property*: A piece of metadata about a resource less structured than
   a *link.* Only present for XRD-derived data.  Has a *secure *boolean
   field indicating whether it was retrieved securely.

*Algorithm*

   1. Determine priority order (Host-priority or Resource-priority):
      1. lookup HostMetaLRDD(startURI)
      2. if above lookup fails because Host(startURI) is not available,
      priority = Resource (goto step 2)
      3. Else, does result contain XRD/Property@type=
      http://lrdd.net/priority/resource?
      4. If yes, then priority = Resource (goto step 2)
      5. Otherwise, priority = Host (goto step 2)
   2. If priority = Host:  *// priority order is host-meta, HTTP Link,
   <Link> elements*
      1. metadata = lookup HostMetaLRDD(startURI, 1)
      2. augment metadata with result of lookup HeaderLinks(startURI, 2)
      3. augment metadata with lookup ResourceLinks(startURI, 3)
   3. If priority = Resource:*// priority order is <Link> elements, HTTP
   Link, host-meta*
      1. metadata = lookup ResourceLinks(startURI, 1)
      2. augment metadata with result of lookup HeaderLinks(startURI, 2)
      3. augment metadata with lookup HostMetaLRDD(startURI, 3)

*where*

HostMetaLRDD(uri, pri) is:

   1. Revalidate local XRD data cache for hostof(*uri*
   )/.well-known/host-meta.
   2. Find*the first link*with rel=”lrdd” in host-meta document (call the
   href value *lrdd_url*)
   3. Revalidate local XRD data cache for *lrdd_url,*annotating each link
   with *lrdd_pri*=pri
   4. Return metadata (non-lrdd links and properties) for *lrdd_uri*

HeaderLinks(uri, pri) is:

   1. If uri is not dereferenceable (e.g., acct:) return empty set
   2. Revalidate local resource link cache for *uri*
   3. Retrieve Link: headers for resource from cache, annotating each link
   with *lrdd_pri*=pri
   4. Return links to caller

ResourceLinks(uri, pri) is:

   1. If uri is not dereferenceable (e.g., acct:) return empty set
   2. Revalidate local resource link cache for *uri*, annotating each link
   with *lrddsrc =*resource
   3. Retrieve MIME-type-specific set of links known for resource,
   annotating each link with *lrdd_pri=*pri
   4. Return links to caller

augment X with Y with priority pri is:

   1. For each set of links y in Y sharing link relation r:
      1. if r==”lrdd”, and X does not already contain a link with
      rel=”lrdd”:, augment X with results of:
         1. Revalidate local XRD data cache for first *href *for rel=”lrdd”,
         annotating each link with *lrdd_pri*= pri
         2. Augment X with resulting metadata from *href*
      2. else, add list of links y to X.
   2. Add all properties in Y to X.

NB: Some link types can contain space-separated rel values, which are
interpreted as a series of links with each of the space-separated rel value
names in the above algorithm.

NB: Ordering of links and properties from each source with the same rel/type
values is retained throughout, with the caveat that HTTP headers do not have
a guaranteed stable order.

Security is not shown here, but is based on either TLS used throughout the
retrievals or (for XRD) the XRD signature specification.  Content type
specific security may also be used to verify links within content (e.g.,
Magic Signatures over link elements).  When set, the *secure *boolean
indicates that a specific link or property was retrieved securely; when not
set, it indicates that the retrieval path contained one or more insecure
steps.  The algorithm will also reject data that is red-flagged (e.g., if a
CRL check shows that a certificate has been revoked as opposed to merely
expiring).  (?)

*Result*:

An ordered collection of metadata, consisting of links and properties, each
of which is annotated with its*lrddsrc*provenance.  There is at most one
rel=”lrdd” link in the collection which identifies the specific LRDD
document used, if any.

A client which wishes to coalesce links and properties found in all three
places within a given rel or type value can just query the collection for
the desired rel or type and retrieve collections of links or properties.

Once retrieved, the set of metadata can be queried.  An important/useful
query is to retrieve the list of links with a given rel value:

get_links(metadata, rel)  # Get sequence of links with given rel value, or
empty list if not found.

Sometimes you may require that only the first set of links found count:

get_top_priority_links(metadata, rel)  # Get sequence of links with given
rel value, ignoring all but the first set found

...and of course you can do a similar query for properties.

---

From: John Panzer <[email-masked]>
Date: Fri, 26 Mar 2010 10:07:54 -0700

Note:  By popular demand, I've attempted to convert this into a
readable plain text form (below).

This is my attempt to translate
http://tools.ietf.org/html/draft-hammer-discovery-04 into an
actionable algorithm, as a first step in attempting to write a truly
general resource discovery library that matches the latest spec.
It is written under the assumption that a client may wish to query
for sets of links with a given relvalue, and is not going to wish
to retrieve and re-parse host-meta files any more often than
necessary.  Feedback welcomed!

Definitions

startURI: Starting point for discovery; input into the
discovery process.  Discovery produces metadata for startURI.

metadata: A collection of links and properties for the resource.

link: An abstract edge between the startURI resource and another resource
identified by a field href.  Has a rel field indicating the relationship
from startURI to href. Has a lrdd_pri field indicating ordering
within the rel value.  Has a secure boolean field indicating whether
it was retrieved securely.  Can be annotated with arbitrary properties.

property: A piece of metadata about a resource less structured than
a link. Only present for XRD-derived data.  Has a secure boolean
field indicating whether it was retrieved securely.

Algorithm

Determine priority order (Host-priority or Resource-priority):

lookup HostMetaLRDD(startURI)
if above lookup fails because Host(startURI) is not available,
priority = Resource
Else, does result contain
XRD/Property@type=http://lrdd.net/priority/resource?  If yes, then
priority = Resource.  Otherwise, priority = Host

If priority = Host:
  // priority order is host-meta, HTTP Link, <Link> elements
  metadata = lookup HostMetaLRDD(startURI, 1)
  augment metadata with result of lookup HeaderLinks(startURI, 2)
  augment metadata with lookup ResourceLinks(startURI, 3)

If priority = Resource:
  // priority order is <Link> elements, HTTP Link, host-meta
  metadata = lookup ResourceLinks(startURI, 1)
  augment metadata with result of lookup HeaderLinks(startURI, 2)
  augment metadata with lookup HostMetaLRDD(startURI, 3)

where

HostMetaLRDD(uri, pri) is:
  Revalidate local XRD data cache for hostof(uri)/.well-known/host-meta.
  Findthe first linkwith rel=”lrdd” in host-meta document (call
    the href value lrdd_url)
  Revalidate local XRD data cache for lrdd_url,annotating each link
    with lrdd_pri=pri
  Return metadata (non-lrdd links and properties) for lrdd_uri

HeaderLinks(uri, pri) is:
  If uri is not dereferenceable (e.g., acct:) return empty set
  Revalidate local resource link cache for uri
  Retrieve Link: headers for resource from cache, annotating
    each link with lrdd_pri=pri
  Return links to caller

ResourceLinks(uri, pri) is:
  If uri is not dereferenceable (e.g., acct:) return empty set
  Revalidate local resource link cache for uri
  Retrieve MIME-type-specific set of links known for resource, annotating each
    link with lrdd_pri=pri
  Return links to caller

augment X with Y with priority pri is:
  For each set of links y in Y sharing link relation r:
    if r==”lrdd”, and X does not already
      contain a link with rel=”lrdd”:
      augment X with results of:
        Revalidate local XRD data cache for first href for rel=”lrdd”,
          annotating each link with lrdd_pri=pri
        Augment X with resulting metadata from href
    else,
      add list of links y to X.
      Add all properties in Y to X.

NB: Some link types can contain space-separated rel values, which
are interpreted as a series of links with each of the space-separated
rel value names in the above algorithm.

NB: Ordering of links and properties from each source with the same
rel/type values is retained throughout, with the caveat that HTTP
headers do not have a guaranteed stable order.

Security is not shown here, but is based on either TLS used throughout
the retrievals or (for XRD) the XRD signature specification.  Content
type specific security may also be used to verify links within
content (e.g., Magic Signatures over link elements).  When set, the
secure boolean indicates that a specific link or property was
retrieved securely; when not set, it indicates that the retrieval
path contained one or more insecure steps.  The algorithm will also
reject data that is red-flagged (e.g., if a CRL check shows that a
certificate has been revoked as opposed to merely expiring).  (?)

Result:

An ordered collection of metadata, consisting of links and properties,
each of which is annotated with its lrdd_pri in case it matters.  There is at
most one rel=”lrdd” link in the collection which identifies the
specific LRDD document used, if any, and any metadata from that lrdd
document is transcluded into the metadata collection.

A client which wishes to coalesce links and properties found in all
three places within a given rel or type value can just query the
collection for the desired rel or type and retrieve collections of
links or properties.

get_links(metadata, rel)  # Get sequence of links with given rel
value, or empty list if not found.

Sometimes you may require that only the first set of links found
count:

get_top_priority_links(metadata, rel)  # Get sequence of links with
given rel value, ignoring all but the first set found

---

From: Eran Hammer-Lahav <[email-masked]>
Date: Sat, 27 Mar 2010 14:41:40 -0700

> -----Original Message-----
> From: John Panzer [mailto:[email-masked]]
> Sent: Friday, March 26, 2010 10:08 AM

> http://tools.ietf.org/html/draft-hammer-discovery-04 into an actionable
> discovery library that matches the latest spec.
> It is written under the assumption that a client may wish to query for sets of
> links with a given relvalue, and is not going to wish to retrieve and re-parse
> host-meta files any more often than necessary.  Feedback welcomed!
> 
> Definitions
> 
> startURI: Starting point for discovery; input into the discovery process.
> Discovery produces metadata for startURI.
> 
> identified by a field href.  Has a rel field indicating the relationship from
> startURI to href. Has a lrdd_pri field indicating ordering within the rel value.
> Has a secure boolean field indicating whether it was retrieved securely.  Can
> be annotated with arbitrary properties.
> 
> property: A piece of metadata about a resource less structured than a link.
> Only present for XRD-derived data.  Has a secure boolean field indicating
> whether it was retrieved securely.

Link headers and elements can include extension parameters that are either rel-specific or document specific. These will be in the form of key/value pairs but in which the key is a short name, not a URI (like XRD <Property> type). In markup the can have a namespace.

I generally prefer people used the XRD <Property> facility instead of extending the link schema (for header format).

> lookup HostMetaLRDD(startURI)

What does this do in this context? Your Function below is aimed for getting metadata, not just raw host-meta.

> if above lookup fails because Host(startURI) is not available, priority =
> Resource Else, does result contain
> XRD/Property@type=http://lrdd.net/priority/resource?  If yes, then priority
> = Resource.  Otherwise, priority = Host
> 
> If priority = Host:

How do you handle http vs https?
Follow redirections.
Validate host-meta is valid for the desired host.

>   Find the first link with rel="lrdd" in host-meta document (call
>     the href value lrdd_url)

Apply template...

>   If uri is not dereferenceable (e.g., acct:) return empty set

If you URI is not http/https, or if a GET/HEAD returns a response that does not contains a representation for the requested resource. See: http://tools.ietf.org/html/draft-ietf-httpbis-p2-semantics-09#section-6.1

>     if r=="lrdd", and X does not already
>       contain a link with rel="lrdd":
>         Revalidate local XRD data cache for first href for rel="lrdd",
> values is retained throughout, with the caveat that HTTP headers do not
> have a guaranteed stable order.
> 
> retrievals or (for XRD) the XRD signature specification.  Content type specific
> security may also be used to verify links within content (e.g., Magic
> Signatures over link elements).  When set, the secure boolean indicates that
> a specific link or property was retrieved securely; when not set, it indicates
> that the retrieval path contained one or more insecure steps.  The algorithm
> will also reject data that is red-flagged (e.g., if a CRL check shows that a
> An ordered collection of metadata, consisting of links and properties, each of
> which is annotated with its lrdd_pri in case it matters.  There is at most one
> rel="lrdd" link in the collection which identifies the specific LRDD document
> used, if any, and any metadata from that lrdd document is transcluded into
> the metadata collection.

There can be more than one LRDD document, but only one is used from each source. There should not be any rel='lrdd' in the collection because it is either expanded or dropped (not first).

> places within a given rel or type value can just query the collection for the
> desired rel or type and retrieve collections of links or properties.
> 
> get_top_priority_links(metadata, rel)  # Get sequence of links with given rel
> value, ignoring all but the first set found
> 

EHL

---

From: Eran Hammer-Lahav <[email-masked]>
Date: Sat, 27 Mar 2010 16:03:04 -0700

> From: [email-masked]
> [mailto:[email-masked]] On Behalf Of Joseph Holsten
> Sent: Saturday, March 27, 2010 3:54 PM
> To: [email-masked]
> Cc: [email-masked]; [email-masked]
> Subject: Re: Query on discovery algoritm for LRDD (draft-hammer-discovery-
> 04)
> 
> On Mar 27, 2010, at 4:41 PM, Eran Hammer-Lahav wrote:
> > If you URI is not http/https, or if a GET/HEAD returns a response that does
> not contains a representation for the requested resource. See:
> http://tools.ietf.org/html/draft-ietf-httpbis-p2-semantics-09#section-6.1
> 
> That reminds me, is there a good Accept header for the initial URI request?
> The draft mentions ways to get links from  application/xrd+xml,
> application/atom+xml, application/xhtml+xml, text/html. Are there any
> other situations that can usually work? Should a client claim support for
> application/xml and text/xml, since they could include a atom:link? Are there
> other link formats that clients should be supporting? XLink is used in SVG, if I
> remember correctly.
> 
> I'm thinking the Accept has to have */*, due to all the */*+xml types, so the
> only purpose of the Accept will be to express preference for xhtml over
> html, &c.

At this point HTML, XHTML, and ATOM support typed links with compatible semantics. If you have other formats its up to you to decide if you want your client to use links found there.

> I notice draft-hammer-discovery-04 uses an explicit Accept: text/html on
> page 3. Is that really intended? Should I read anything into that?

The client is asking for HTML because that's one of the markup formats it understands. There is no requirement for clients to speak ATOM if they don't deal with ATOM documents as part of the resources they care about.

EHL

> http://josephholsten.com
> 
> To unsubscribe from this group, send email to
> webfinger+unsubscribegooglegroups.com or reply to this email with the
> words "REMOVE ME" as the subject.

---

From: Joseph Holsten <[email-masked]>
Date: Sat, 27 Mar 2010 17:54:11 -0500

> If you URI is not http/https, or if a GET/HEAD returns a response that does not contains a representation for the requested resource. See: http://tools.ietf.org/html/draft-ietf-httpbis-p2-semantics…

That reminds me, is there a good Accept header for the initial URI request? The draft mentions ways to get links from  application/xrd+xml, application/atom+xml, application/xhtml+xml, text/html. Are there any other situations that can usually work? Should a client claim support for application/xml and text/xml, since they could include a atom:link? Are there other link formats that clients should be supporting? XLink is used in SVG, if I remember correctly.

I'm thinking the Accept has to have */*, due to all the */*+xml types, so the only purpose of the Accept will be to express preference for xhtml over html, &c. 

I notice draft-hammer-discovery-04 uses an explicit Accept: text/html on page 3. Is that really intended? Should I read anything into that?
--
http://josephholsten.com