[This local archive copy is from the official and canonical URL, http://journals.ecs.soton.ac.uk/xml4j/xlinkexperience.html; please refer to the canonical source document if possible. Some font characteristics have been changed in this copy to enable viewing on low-end browsers.]

Initial Experiences of an XLink Implementation Leslie Carr, Multimedia Research Group
University of Southampton. lac@ecs.soton.ac.uk

Background
A Simple XLink Application
Design of the XLink API
Complexities in Link Resolution
- Proposal for Allowing Resolution Restraints within the API
Implementation Notes
Questions about the Standard
Conclusions and Further Work
References

Background

The aim of this work has been to produce a collection of classes that support XLink processing, identifying and resolving the data that is pointed at by the XLink locators, and allowing application-defined semantics to be brought to bear on those combinations of data. The result has been the uk.ac.soton.xlink package, consisting of the XLink, XAnchor, XLinkCollection and XLinkUtilities classes, along with some modifications and extensions to the com.ibm.xml.xpointer package.

An initial objective was to re-create the Knit application, designed by the Language Technology at Edinburgh as part of the LTXML package, which performed ‘transclusion’ operations to replace inline, simple id()-based links in an XML file with the data object to which it was linked. The ExtremeKnit class uses the XLink package to extend that functionality to extended links in XML documents using (almost) the full XPointer semantics.

Beyond these direct aims, it is hoped to use this package as a testbed and demonstrator for ideas about open hypermedia. In particular, to address the current debate about separating behaviours into logically distinct components [Nurnberg], the extent to which semantics can pass between a general link processor and application [Carr] and to create a model for the life cycle of the followlink process [Trigg].

This work is at an early stage, and is currently being tested in house.
To obtain the software, please contact the author on the email above.

A Simple XLink Application

Usage: ExtremeKnit [-[IOAB]] [-[iot]] URL

Application Behaviour

The XML document at the given URL is output on the standard output with all the simple and extended links processed. For simple links, the linking element is replaced by the linked element. For extended links, the elements pointed at by the source anchors are replaced by those pointed at by the destination anchors. Links are obtained as normal from the document, from any file referenced as part of an XLink extended link group, but in addition a default file of links is examined in the current directory under the name ".linkbase.xml". This effect of this application is to render the document with EMBED/AUTO semantics forced on each of the links.

Options

The first option controls whether or not the replacement affects the (I)nner contents of the source element or the (O)uter element itself, or whether the destination is inserted or appended (B)efore or (A)fter the link source instead of replacing it. The second option controls whether the (i)nner contents of the linked element, the (o)uter element itself or the (t)ext contents of the element are linked.

Warning!

ExtremeKnit modifies the document's DOM in place, This provides problems when using the —i or —o option as an element can be replaced by one of its ancestors e.g. an XPointer which just specifies #root(). This application does not detect and avoid such infinite loops!

Sample Usage

The following table shows an original XML file (at http://journals.ecs.soton.ac.uk/xml4j/generic.xml) which explicitly refers to a linkbase containing 1 link between all occurrences of the word 'hypertext' and a couple of explanatory notes in another file. The last row shows the results of running ExtremeKnit -A -i on the XML file.

The original XML file	<?xml version="1.0"?> <!DOCTYPE XLinkTest SYSTEM "http://journals.ecs.soton.ac.uk/xml4j/generic.dtd"> <XLinkTest> <body> <div> <h1>Reasons to be Cheerful</h1> <p>One, two three. Well, the hypertext conference is a good one!</p> <p>I think that open hypertext has a lot going for it. There are still a lot of people in the WWW community that don't understand hypertext very well. I could become a bit of a salesman!</p> </div> </body> <linkbases> <linkbase href="http://journals.ecs.soton.ac.uk/xml4j/linkbase.xml"/> </linkbases> </XLinkTest>
The linkbase	<?xml version="1.0"?> <!DOCTYPE linkbase SYSTEM "http://journals.ecs.soton.ac.uk/xml4j/linkbase.dtd"> <linkbase> <link type='generic'> <locator href="#root().string(all,'hypertext',1,9)" role="source" title="hypertext gloss"/> <locator href="http://journals.ecs.soton.ac.uk/xml4j/htgloss.xml#id(hypertext)" role="destination" title="Dr Frankenstein"/> </link> <link type='generic'> <locator href="#root().string(all,'WWW',1,3)" role="source" title="WWW gloss"/> <locator href="http://journals.ecs.soton.ac.uk/xml4j/htgloss.xml#id(WWW)" role="destination" title="Mr WWW"/> <locator href="http://journals.ecs.soton.ac.uk/xml4j/htgloss.xml#id(w3c)" role="destination" title="Home of Hypertext"/> </link> </linkbase>
The glossary file	`<?xml version="1.0"?> <!DOCTYPE glossary [ <!ELEMENT glossary (gloss)+> <!ELEMENT gloss (#PCDATA)> <!ATTLIST gloss id ID #REQUIRED> ]> <glossary> <!-- some trivial hypertext thingies --> <gloss id="hypertext">(One of Vanevar Bush's better ideas!)</gloss> <gloss id="w3c">(Visit W3C - The home of hypertext on the Web!)</gloss> <gloss id="WWW">[Insanely good idea of Tim BL]</gloss> </glossary>`
The result of `ExtremeKnitware` `-A -i`	<?xml version="1.0"?> <!DOCTYPE XLinkTest SYSTEM "http://journals.ecs.soton.ac.uk/xml4j/generic.dtd" > <XLinkTest> <body> <div> <h1>Reasons to be Cheerful</h1> <p>One, two three. Well, the hypertext(One of Vanevar Bush's better ideas!)(Visit Webcosm - The home of hypertext on the Web!) conference is a good one!</p> <p>I think that open hypertext(One of Vanevar Bush's better ideas!)(Visit Webcosm - The home of hypertext on the Web!) has a lot going for it. There are still a lot of people in the WWW community that don't understand hypertext(One of Vanevar Bush's better ideas!)(Visit Webcosm - The home of hypertext on the Web!) very well. I could become a bit of a salesman!</p> </div> </body> <linkbases xml:link="group"> <linkbase href="http://journals.ecs.soton.ac.uk/xml4j/linkbase.xml" xml:link="document"/> </linkbases> </XLinkTest>
A sample XSL rule to display the linked glosses	`<rule> <target-element type="gloss"/> <SPAN font-weight="bold" color="green"> <children/> </SPAN> </rule>`
The result of running the MSXL processor on the output of `ExtremeKnitware -A` and the XSL fragment shown above.	Reasons to be Cheerful One, two three. Well, the ACM hypertext (One of Vanevar Bush's better ideas!) conference is a good one! I think that open hypertext (One of Vanevar Bush's better ideas!) has a lot going for it. There are still a lot of people that don't understand hypertext (One of Vanevar Bush's better ideas!) very well. I could become a bit of a WWW [Insanely good idea of Tim BL] salesman!

Design of the XLink API

XLink class which embodies the core concept of a link, ignoring any specifically markup-oriented issues. An XLink consists of a role and a title together with a set of XAnchors. Each XAnchor is modelled on an XLink locator, and contains a title, role and the result of evaluating an XPointer, i.e. a collection of Nodes (often a collection of size 1).

Brief Notes on the XPointer API

The IBM xpointer classes provide for the parsing and resolving of XPointers. An XPointer object (created from an XPointer string found in an href attribute of an XLink conforming XML document) can be resolved with respect to a particular document (provided as the DOM object Document). The act of turning an XPointer string into an XPointer object consists of passing the string to an XPointer constructor for parsing. The act of turning an XPointer object into a specification of the place at which it points consists of evaluating the XPointer's pointsAt() method, which returns a Pointed object, a subclass of Vector. Each element in the vector is an Item, which consists of a Node and a type (T_NODE, T_STRING or T_STRINGINNODE) together with information (offset, length) about the position of the selected string within the node which is only applicable if the type is T_STRINGINNODE (i.e. for string() XPointers).

Using XLink with XPointer

After parsing the XML document, the user parses, resolves and stores all the link structures into a Vector collection as follows:

Doc d=parse(inputXMLFile);
Vector allLinks=getLinks(d);

The user can then process all the links by iterating through them

for(int i=0; i<links.size(); i++){
    XLink xl=(XLink)links.elementAt(i);
    //process each link
    }

And then process each link by iterating through the anchors:

Vector anchors=xl.getAnchors();
for(int j=0; j<anchors.size(); j++){
   XAnchor xa=(XAnchor)anchors.elementAt(j);
    //process each anchor
            }

And then process each anchor according to its role, iterating through the pointed at nodes if necessary:

String role=xa.getRole();
if(role.indexOf("source")>=0){
    Pointed ps=xa.getPoint();
    for(int k=0; k<ps.size(); k++){
       Item it=(Item)ps.elementAt(k);
       Node n=it.node;
       Parent p=(Parent)n.getParentNode();
       Text t=maindoc.createTextNode("Look here! ->");
       p.insertBefore(t,n);
      }
   }

Alternative Abstractions for Link Processing

The above allows for complete control over the linking process (whatever that turns out to mean for any given application). However, it is very tedious, requiring three levels of iteration in the most trivial case or five levels if combinations of two anchors are to be conjoined. As an alternative, the user parses, resolves and stores all the link structures into an XLinkCollection as follows:

Doc d=parse(inputXMLFile);XlinkCollection allLinks=getLinks(d);

In a navigation-style hypertext, the imperative is to find all the source links and connect them to their destinations. To support this, the XLinkCollection can be scanned for all the sources as follows:

Enumeration sources=allLinks.getAnchorsByRole("source").elements();

And then each source anchor can be processed to find its matching destinations

while(sources.hasMoreElements()){
    XAnchor theSource=sources.nextElement();
    XLink xl=theSource.getLink();
    Vector dests=xl.getAnchorsByRole("destination");
    //Knit theSource together with all the dests. Somehow.
            }

Alternatively, all the other anchors can be enumerated by the expression

dests=theSource.getSiblings();

Knitting Link Anchors Together

The ultimate aim of any link processor is to somehow ‘knit’ the various anchors together, whether by adding nodes to the XML DOM, or by changing the display and interaction attributes associated with the DOM elements. A knit function must therefore iterate over the XAnchors in a standard way, performing some non-standard processing for each matching combination. The above example left this deliberately vague, as it involves more tedious layers of iteration to find all the Items of all the complementary XAnchors.

The following usage allows the programmer to (almost) completely abandon the multiple layers of iteration over the XLinks, XAnchors and Items, reducing it instead to a single loop over every possible combination of pairs of matching source and destination link anchor points.

Enumeration combos=allLinks.getNodesComboByRoles("source","dest");
while(combos.hasMoreElements()){
    Node src=combos.nextElement();
    Node dest=combos.nextElement();
    //Now do the hard work at the DOM level
    Parent p=(Parent)src.getParentNode();
    Text newText=doc.createTextNode("["+dest.getData()+"]");
    p.insertAfter(newText, dest);
    }

The drawback with this mechanism is that the collection implementation is unclear (please, not another Vector!), relying on the programmer's discipline to keep the alternating node roles synchronised. It is also not clear why combinations of two should not be extended to three or more, but this may be better handled by application-specific code.

A variant implementation (getNodesAndXAnchorsComboByRoles) alternates the Nodes with their containing XAnchors, allowing the API user to find more information about the linking context of the Node in question. From there, the programmer can call the getSiblingNodes(thisNode) method of the XAnchor to find all the other nodes that this anchor shares. From there also the programmer can use the XAnchor class’ getLink() method to find information about which XLink any of these anchors is connected to, and hence to find any other attributes of this or any of the other XAnchors. (In an ideal world, the owning XAnchor would be an attribute of each pointed Item).

Complexities in Link Resolution

Having established some general processing methodologies that are useful for implementing a link processing application, let us return to the issue of recognising and resolving the links and their associated data references.

The naïve model (which has been presented thus far) resolves every link, evaluating every XPointer on every locator of every link, so that the complete forest of DOM Nodes is instantly available. For some limited applications this is fine, but more general processing may render this unusable.

Consider a typical Microcosm session: it contains many active linkbases, each with many dozens (or even hundreds) of generic, keyword links whose source anchor contains an XPointer of the form #root().string(all, keyword, 1, 7). Any particular document may only contain a small fraction of the phrases which trigger those generic links, and so the majority of source links for the linkbases will resolve to null places. Effectively, those links are inactive for that particular document. However, our naïve approach will force all the destination anchors to be resolved irrespective of whether they are needed or not. This will mean parsing and storing hundreds of irrelevant documents. By contrast, the required behaviour for this scenario is to first attempt to resolve the XAnchor with the "source" role, and only if it succeeds to resolve the remaining anchors.

In this scenario, the source anchor acts as a guard for the link. Other circumstances may act as further guards: in the Microcosm system all link processing acts on the current document. This would imply that links whose source anchors lie outside the current document are also ineligible for processing. Other more complex rules will apply for other applications.

Even if the link is found to be valid in the above sense, it may be the case that it is sensible to defer the resolution of the other anchors (such as the destinations) until they are actually needed. Application-specific processing may mean that many of the links are not required (for example, only a window of a scrollable document may be rendered). In the ExtremeKnit application, it would have been pointless to defer the resolution of any of the destination anchors as they are all eventually used. However other applications may find it advantageous to delay resolving any anchor pointing outside the scope of the local document.

Proposal for Allowing Resolution Restraints within the API

If one of the anchor roles acts as a guard in a specific application, this should be communicated to the API through a modified version of the getLinks() method.

Expected use: XLinkCollection l=getLinks(document, "source");
or XLinkCollection l=getLinks(document, "source src");

If a guard is specified, only links containing an anchor with that guard role will be eligible for use. That anchor's XPointer must also correctly resolve to a non-null position in order for the link to be useful.

Further behaviour can be predicated on the guard role: if the LOCAL behaviour is requested then the guard must resolve to some data in the current document. If the DEFER behaviour is requested then only the guard will be resolved. The XPointers of other anchors will be resolved at the point when they are needed. This behaviour will be part of the XAnchor class, invisible to the user of the API.

Expected use: XLinkCollection l=getLinks(document, "src", XAnchor.DEFER);

Implementation Notes

Firstly, the XML parser was chosen after investigating various alternatives. From an application viewpoint, linking does not seem to require of itself a valid document and so various experiments were carried out using a non-validating parser. However, to make the XLink elements sufficiently abstract to be readable they need to at least have #FIXED attributes inherited from the DTD.

Next, the FREEDOM interface was used with the aelfred parser to implement the Knit program from the ground up. This involved interpreting the XPointers by hand, but as the original Knit program only worked for the #id() forms this was not too great a problem.

In the middle of building up a fuller XPointer class, I discovered that IBM's xml4java already provided XPointer support, and so I switched to that product. Within that environment I have tried to keep strictly to the DOM interface, although some of the native facilities have been resorted to on occasions. Some changes have been made to the native XPointer package, in particular those relating to the parsing and handling of string() terms. Because Microcosm relies so much on the ability to address within-node data, it was an important to add proper support for the string term to the XPointer package. This has been done, although the current implementation does not allow individual string matches to straddle node boundaries. Support for span() and origin() has still not been provided.

Peculiarity of string() handling

The initial Knit application did its work by writing the linked elements to the output as it traversed the DOM. Subsequent versions actually rewrote the DOM structure in place as it traversed the set of links. With this behaviour, any pointers to substrings of text within a particular node became invalid as soon as another link caused the contents of the node to alter. (This is a specific consequence of the open hypertext general editing problem [Davis]).

In order to make the results of resolving a within-node XPointer generally useful in the situation where the document tree is to be processing by in-place transformation, the following strategy (shown graphically in Figure 1) was evolved.

Gather together all the DOM-specific string() XPointers
Resolve them all
Iterate through all the pointed-at text nodes thus
Find all references to the current text node
Put them in descending order of in-text offset
Replace the single text node with THREE nodes

The text from the beginning of the node up to the‘pointed at’ text
The‘pointed at’ text
The text after the ‘pointed at’ text to the end of the node

Rewrite the current XPointer ‘point’ so that it references (b) instead of the old node
Rewrite every other XPointer ‘point’ that used to point at the old node so that it now points at (a)

This process is undertaken as part of the getLinks() method and means that every XPointer() now points to a complete node and (more importantly) that rewrites of the document structure are now consistent with the link pointers. The downside is that the application no longer sees the original DOM, but this is irrelevant as XPointers are the only mechanism for addressing into the DOM but they were all resolved with reference to the original DOM. Of course, this may be an issue to XSL and other document processors beyond the link processor, but only if they share the in-memory copy of the document. A better mechanism would be to annotate the nodes rather than rewrite them, but no such facility exists in the current DOM interface.


Figure 1a: The word hypertext, the subject of a notional string XPointer #id(x).string(1,hypertext,1,9) is shown embedded in a DOM structure.	Figure 1b: The DOM structure is now rewritten so that the target string has its own separate TEXT node.

Outstanding Issues

One immediate problem comes with link semantics which involve rewriting the original document at the XML source level: almost any non-trivial change will entail violating the original DTD. Conversely, any change which does not violate the DTD requires a lot of prior knowledge about the document architecture and the linking architecture and will require a high degree of binding between the documents and the application. Although this is not a bad thing per se, the aim of this package is to provide a broad spectrum of support for general link processing utilities as well as bespoke applications.

Outstanding implementation

Wanton disregard of XLink steps, in-line, out-of-line, attribute remapping

XPointer support for spans() and origin().

Outstanding Bugs

Overlapping string() XPointers are not handled by the rewriting process.

Questions about the Standard

How do you specify the role of the remote resource in a simple inline link? The role attribute for the local resource has already been swapped to content-role so as not to clash with the link's own role.
Does the existence of a local resource in an inline link mean that resource has to be "pre-traversed". ie Does lexical inclusion imply functional inclusion? At what level is the inline-ness working---at the hypertext level or at the XML level or both?
Microcosm generic links can be approximated with string() XPointers, however NO FUZZY MATCHING (case folding, ignoring diacritical marks, compressing 'non-token' characters) is allowed by the XPointer standard. This is not a question, this is a problem, err, opportunity. Should query-type facilities be part of the standard or part of the application? Are they pragmatically dropped for v1.0, or philosophically dropped for ever?
What is the 'containing resource' by which the absolute XPointer terms root() and id() are judged? If links and data are contained in the same document then there is no problem. If, indeed the links are in separate 'link documents' which contain no other data then the term is fairly unambiguous. But what if the links are in a document n steps away, a document which contains paragraphs of interesting data as well as links?

As a specific example, imagine a document about Sheep Farming, contained in an XML file contained at URL d. Imagine a glossary document at URL g which contains paragraphs describing the various breeds of sheep and also a set of links from mentions of each breed in d to the descriptions in g. If the hrefs include specific URIs then fine, but if not does #root().string(1,'Merino',1,6) identify the first occurrence of the string 'Merino' in d or g? If the former, how can a locator be specified for the glossary item? If the latter how can a locator be specified for the data document? If specific URL's are resorted to, then is it possible to create a g that can be used with any document about Sheep Farming?

Conclusions and Further Work

The xlink package is at a very rudimentary stage. By building a number of other applications it is hoped to be able to deduce a generally useful API for XLink processing. Significant hypertext research and experience has fed into the design of XLink. The Dexter Model, which separates the document, link and anchor storage and management is much in evidence here. The XLink package could make that more explicit, providing a "Dexter interface" for XLink processing, however that really only deals with the basic level of providing access to the components of the link. An important topic of hypertext research (and an important topic for developers of hypertext systems) is given the links and given the data that is being linked, what should be done and how should it be achieved.
Investigate the possibility of driving XSL patterns by referring to elements that have been linked via XLink. Currently it is necessary to transclude them as in the above example.
Proper support for Microcosm generic links and other content-based query meta-links.

References

Carr, L.A. and Hall, W. (1998) "Implications of XML for Open Hypermedia Systems", Proceedings of the Fourth Workshop on Open Hypermedia Systems at the Ninth ACM Conference on Hypertext, Pittsburgh.

Davis, H. C. (1998) "Referential Integrity of Links in Open Hypermedia Systems", Proceedings of the Ninth ACM Conference on Hypertext, Pittsburgh.

Davis, H., W. Hall, I. Heath, G. Hill and R. Wilkins (1992), “Towards an Integrated Information Environment with Open Hypermedia Systems,” In ECHT ’92, Proceedings of the Fourth ACM Conference on Hypertext, Milan.

Nurnberg, P. (1997) "As we should have thought", Proceedings of the Eigth ACM Conference on Hypertext, Southampton.

Trigg R. H. (1998) "A straw model for link traversal in open hypermedia systems", Proceedings of the Fourth Workshop on Open Hypermedia Systems at the Ninth ACM Conference on Hypertext, Pittsburgh.

Table of Contents