View source for parsing-brainstorming

This is an attempt to get some of my thoughts on parsing, from practical experience implementing [http://buzzword.org.uk/cognition/ Cognition], out of my head and onto the wiki. Hopefully it will replace [[parsing]] once it reaches consensus, as this document is somewhat more detailed. It deals with how to parse the properties of a compound microformat once we have located the root element, which we shall call <code>root</code>. It deals with simple properties which have no sub-properties (such as <code>fn</code> in hCard), and with properties which may include an embedded microformat (such as <code>agent</code> in hCard) — 95% of properties do fall into these categories. (Many of the others can be parsed by treating the property element as <code>root</code> and then finding sub-properties using the techniques on this page, but some do occasionally require special handling.) [[User:TobyInk|TobyInk]]

'''Note:''' as a courtesy, I'd like to ask people not to edit this page for the next few days, until I have gotten the initial version stable. Thanks. [[User:TobyInk|TobyInk]] 01:14, 21 Jul 2008 (PDT)

= General Algorithm =

# Make a ''copy'' of the DOM tree to operate on. All future references to DOM traversal and manipulation refer to this clone.
# Implement [[include-pattern|the include pattern]] by removing any nodes with <code>class="include"</code> and replacing them with the node which they point to. (Unless the node pointed to is a parent node of the node with <code>class="include"</code>!!)
# Parse all properties that may contain nested microformats. For example within hCard, the agent property may contain a nested hCard. For each property <code>prop</code> which may contain a nested microformat:
## Create an empty array to store the value(s) of <code>prop</code> in. Call this <code>A</code>.
## OUTER: Find all elements with <code>class="prop"</code> that are descended from <code>root</code>. For each of those elements <code>e</code>:
### INNER: For each microformat root class name that might be present (e.g. within an hCalendar event's <code>location</code> property you might reasonably expect to find an hCard, and adr or a geo!):
#### Create an empty list <code>F</code>.
#### Search for any elements within <code>e</code> which have the microformat root class name. Bear in mind that perhaps this element might ''be'' <code>e</code> — this is allowed. For each such element, <code>e2</code>:
##### Parse <code>e2</code> as an embedded microformat and place the result in <code>F</code> if it is valid.
##### Run the DESTROY_ELEMENT function on <code>e2</code>
#### If <code>F</code> is not empty:
##### Move the first item in <code>F</code> to <code>A</code>
##### Jump out of the INNER loop.
### If <code>A</code> is not empty:
#### Change the <code>class</code> attribute on <code>e</code>, removing <code>prop</code> from the class list.
#### If property <code>prop</code> is singular, jump out of the OUTER loop.
## If <code>prop</code> is a singular property, let <code>A[0]</code> be its value. If plural, let <code>A</code> be the list of its values.
# Run the DESTROYER function on <code>root</code>.
#* Depending on what microformat you're parsing, you will want to pass a further parameter to DESTROYER indicating a list of microformats to "save" from destruction. In particular, when parsing hCard, it is useful to save adr and geo. (At the time of writing, I don't know of any other useful things to "save" here.)
# Parse all properties. There are three different categories of property — singular, plural and concatenated. Most properties are either singular or plural, but a handful are concatenated, such as <code>entry-summary</code> in [[hAtom]]. For each property <code>prop</code> within <code>root</code>:
## Create an empty array to store the value(s) of <code>prop</code> in. Call this <code>A</code>.
## Find all elements with <code>class="prop"</code> that are descended from <code>root</code>.
## For each element <code>e</code>, run this:
### Find the value of <code>e</code>, using the techniques in the section below.
### If the value of <code>e</code> is not NULL, add it to <code>A</code>
### If the <code>prop</code> is a singular property and <code>A</code> is not empty, jump out of this foreach loop.
## If <code>prop</code> is a singular property, then its value is <code>A[0]</code>.
## If <code>prop</code> is a plural property, then its values are <code>A</code>.
## If <code>prop</code> is a concatenated property, then its values are formed by concatenating the values of <code>A</code> together.

= Finding Values =

There are at least five different types of property that can be parsed, each of which requires different techniques:

* HTML properties, such as <code>entry-content</code> in hAtom
* URI properties, such as <code>url</code> in [[hCard]]
* ID properties, such as <code>uid</code> in hCard
* Datetime properties, such as <code>dtstart</code> in [[hCalendar]]
* Plain text properties, such as <code>title</code> in hCard

Arguments can be made for duration properties and numeric properties to also have variations in the algorithm, but for now, we'll just treat them as plain text properties.

== HTML Properties ==

These are the easiest to parse. Given an element <code>e</code>, just use the HTML representation of its DOM node. Some DOM implementations make this available as <code>.outerHTML</code>.

== URI Properties ==

Certain HTML elements are capable of linking to other resources. The most obvious is <code>&lt;a></code> though there are many others. The following list of linking elements is derived from Perl's ''HTML::Tagset'' module:

<pre><nowiki>{
	'a'       => ['href'],
	'applet'  => ['codebase', 'archive', 'code'],
	'area'    => ['href'],
#	'base'    => ['href'],
	'bgsound' => ['src'],
	'blockquote' => ['cite'],
#	'body'    => ['background'],
	'del'     => ['cite'],
	'embed'   => ['src', 'pluginspage'],
	'form'    => ['action'],
	'frame'   => ['src', 'longdesc'],
	'iframe'  => ['src', 'longdesc'],
#	'ilayer'  => ['background'],
	'img'     => ['src', 'lowsrc', 'longdesc', 'usemap'],
	'input'   => ['src', 'usemap'],
	'ins'     => ['cite'],
	'isindex' => ['action'],
#	'head'    => ['profile'],
	'layer'   => ['src'], # 'background'
	'link'    => ['href'],
	'object'  => ['data', 'classid', 'codebase', 'archive', 'usemap'],
	'q'       => ['cite'],
	'script'  => ['src', 'for'],
#	'table'   => ['background'],
#	'td'      => ['background'],
#	'th'      => ['background'],
#	'tr'      => ['background'],
	'xmp'     => ['href'],
}</nowiki></pre>

Note that some are commented out as they might be too counter-intuitive to implement!

If we're parsing an element <code>e</code> and looking for a URI, here is the algorithm we use:

# Set variable <code>u</code> to NULL.
# Search <code>e</code> for any descendent elements with <code>class="value"</code>. Call this list <code>V</code>.
# Add the element <code>e</code> itself to the list <code>V</code>, at the ''front'' of the list.
# OUTER: for each element <code>v</code> from list <code>V</code>:
## If <code>v</code> is a linking element from the above list
### INNER: for each attribute <code>a</code> associated that the tag name of <code>v</code> in the above list
#### If <code>a</code> is set
##### Set <code>u</code> to the contents of <code>a</code>
##### Jump out of the OUTER loop.
# If <code>u</code> is not null, and is a relative URI, convert it to an absolute URI.

The URI has hopefully been found in <code>u</code>. If no URI has been found, then fall back to plain text parsing.

== UID Properties ==

UID properties are parsed similarly to URL properties, but with a slightly modified algorithm, allowing for UIDs to be specified in the <code>id</code> attribute. The following example has a UID of "http://example.com/page#foo".

<pre><nowiki>
<base href="http://example.com/page" />
<div class="uid" id="foo">...</div>
</nowiki></pre>

The modified algorithm used is:

# Set variable <code>u</code> to NULL.
# Search <code>e</code> for any descendent elements with <code>class="value"</code>. Call this list <code>V</code>.
# Add the element <code>e</code> itself to the list <code>V</code>, at the ''front'' of the list.
# OUTER: for each element <code>v</code> from list <code>V</code>:
## If <code>v</code> is a linking element from the above list
### INNER: for each attribute <code>a</code> associated that the tag name of <code>v</code> in the above list
#### If <code>a</code> is set
##### Set <code>u</code> to the contents of <code>a</code>
##### Jump out of the OUTER loop.
## If <code>v</code> has an <code>id</code> attribute set
### Set <code>u</code> to the contents of <code>id</code>, with the character "#" prepended
### Jump out of the OUTER loop.
# If <code>u</code> is not null, and is a relative URI, convert it to an absolute URI.

Again, if no <code>u</code> has been found by the algorithm, then fall back to parsing it as a plain text property.

== Datetime Properties ==

Parsing property <code>prop</code>, if <code>class="prop"</code> is found on element <code>e</code>.

# If element <code>e</code> has an attribute <code>datetime</code>, then the content of that attribute is the value and the rest of these steps should be skipped.
# Create a list <code>D</code>, which is empty.
# Create a list <code>V</code> of elements with <code>class="value"</code>.
# For each element <code>v</code> in <code>V</code>:
## If <code>v</code> has an attribute <code>datetime</code>, then add the content of that attribute to <code>D</code>
## Otherwise, run the STRINGIFY function on <code>v</code> and add the result to <code>D</code>
# If <code>D</code> is empty, then run the STRINGIFY function on <code>e</code> and let the result be the value, and skip the rest of these steps.
# If <code>D</code> contains only one item, and it looks like an ISO date or ISO datetime, then let that be the value, and skip the rest of these steps.
# If <code>D</code> contains two items, and the first looks like an ISO date, and the second like a time, concatenate them, joining with an upper case 'T', let that be the value, and skip the rest of these steps.
# If <code>D</code> contains three items, and the first looks like an ISO date, the second like a time, and the last like a timezone (may need normalisation), concatenate them, joining the first two with an upper case 'T' and the last one with no intervening character, let that be the value, and skip the rest of these steps.
# Concatenate all the items in <code>D</code> and let that be the value.

The final value should be interpreted as liberally as possible with regards to punctuation as an ISO date or ISO datetime.

=== Normalizing Timezones ===

Where ''S'' is a sign (+ or -) and the letters ''a, b, c, d'' are numerals, then:

* Sa &rarr; S0a00
* Sab &rarr; Sab00
* Sabc &rarr; S0abc
* Sa: &rarr; S0a00
* Sab: &rarr; Sab00
* Sa:b &rarr; S0ab0
* S:ab &rarr; S00ab
* Sa:bc &rarr; S0abc
* Sab:c &rarr; Sabc0
* Sab:cd &rarr; Sabcd

== Plain text Properties ==

To obtain the value of the property, run STRINGIFY on the property node.

= Stringification =

The STRINGIFY function performs a text serialisation of an HTML node, with a few adjustments to implement the [[abbr-pattern|ABBR pattern]]. It uses a helper function, _STRINGIFY.

== STRINGIFY ==

* First parameter: element to stringify, <code>e</code>.
* Second parameter: whether to perform value excerpting - default yes.
* Third parameter: whether to perform abbr pattern - default yes.

# If <code>e</code> is an <code>&lt;abbr></code> or <code>&lt;acronym></code> element, and has a <code>title</code> attribute, then return that attribute.
# If you want to implement any proposed alternatives to the ABBR pattern, then here is the place to do so.
# If value excerpting is enabled:
## Create an empty list <code>S</code>
## Search for any descendant elements of <code>e</code> with <code>class="value"</code>. Put these into a list <code>V</code>.
## For each element <code>v</code> in <code>V</code>
### Recursion: call STRINGIFY on <code>v</code>, disabling value excerpting but enabling the ABBR pattern. Add the result to <code>S</code>.
## Concatenate the items in <code>S</code> to form a string. If this string is not empty, then return the string.
# Run _STRINGIFY on <code>e</code>, trim excess white space from the result and return it.

== _STRINGIFY ==

This is a somewhat simplified version of the real algorithm that I use. You probably want to refine it by adding better whitespace handling rules (e.g. line breaks after block elements, asterisks for list items, etc).

_STRINGIFY is called with one parameter, the element <code>e</code> to be stringified.

# If <code>e</code> is text node (not an element), then return it.
# If <code>e</code> is an <code>&lt;img></code> tag, return the <code>alt</code> text.
# If <code>e</code> is an <code>&lt;input></code> tag, return the text of the <code>value</code> attribute.
# If <code>e</code> is an <code>&lt;br></code> tag, return a linebreak character.
# If <code>e</code> is an <code>&lt;del></code> tag, return a zero-length string.
# Otherwise, create an empty list <code>S</code>.
# For each direct child node <code>c</code> of <code>e</code>:
## Run _STRINGIFY on <code>c</code> and add the result to <code>S</code>.
# Concatenate the items in list <code>S</code> and return them.

= Destruction =

In some cases it is necessary to render an element and its children opaque to later microformat processing. The two functions DESTROYER and DESTROY_ELEMENT deal with this.

== DESTROYER ==

(coming soon)

== DESTROY_ELEMENT ==

The aim of this function is to make the innards of a particular element opaque to microformat parsing. The algorithm for "destroying" element <code>e</code> is as follows:

# Search for all elements which descend from <code>e</code>. For each such element <code>d</code>:
## Set the <code>class</code> attribute to the empty string.
## Set the <code>rel</code> attribute to the empty string.
## Set the <code>rev</code> attribute to the empty string.

= Examples =

== URL Examples ==

The following are all parsed as the same URL.

<pre><nowiki><a class="url" href="http://example.com/page">Page</a></nowiki></pre>

<pre><nowiki><p class="url">
  <a href="http://example.com/not-this">Not this</a>
  <a class="value" href="http://example.com/page">Page</a>
</p></nowiki></pre>

<pre><nowiki><p class="url">
  <a class="value" href="http://example.com/page">Page</a>
  <a class="value" href="http://example.com/not-this">Not this</a>
</p></nowiki></pre>

<pre><nowiki><p class="url">
  <span class="value">http://example.com/</span>
  Not this
  <span class="value">page</span>
</p></nowiki></pre>

<pre><nowiki><img class="url" alt="foo" src="http://example.com/page"
    longdesc="http://example.com/not-this"></nowiki></pre>

<pre><nowiki><!-- (invalid, but works) -->
<img class="url" longdesc="http://example.com/page"></nowiki></pre>

<pre><nowiki><!-- (strange, but true) -->
<p class="url">
  <img src="http://example.com/not-this"
  alt="http://example.com/page">
</p></nowiki></pre>

== Datetime Examples ==

<pre><nowiki><time class="dtstart" datetime="2008-07-21">Monday</time></nowiki></pre>

<pre><nowiki><p class="dtstart">
  <time class="value" datetime="2008-07-21">Monday</time> at
  <time class="value" datetime="21:30">9:30pm</time>.
</p></nowiki></pre>

<pre><nowiki><p class="dtstart">
  <time class="value" datetime="2008-07-21">Monday</time> at
  <time class="value" datetime="21:30">9:30pm</time>
  <time class="value" datetime="+1">(UK)</time>.
</p></nowiki></pre>

<pre><nowiki><p class="dtstart">
  <abbr class="value" title="2008-07-21">Monday</time> at
  <abbr class="value" title="T21:30">9:30pm</time>
  <abbr class="value" title="+0100">(UK)</time>.
</p></nowiki></pre>

== Combination Examples ==

<pre><nowiki><ins class="rev url" datetime="2008-07-21T21:30:00+0100">
  I launched my <a href="http://example.com/" class="value">new
  website</a> today.
</ins></nowiki></pre>

Parsed as:

* rev = 2008-07-21T21:30:00+0100
* url = http://example.com/