HritSample Module

I've managed to create a CMS-independent Hello World! Hrit module that runs in Joomla!

So what, huh? Well, this will make it easy for anyone to write a Hrit module in future, which they can load into any popular CMS, starting with Joomla! The cross-CMS compatibility is provided by a single php file, that is the first point of entry in the extension by the Joomla! system. Also needed is a Joomla!-specific xml file for describing the extension. Thereafter the php entry point delegates everything to the 'module', which is a folder containing a real controller and a real view class that doesn't refer to Joomla! in any way, shape or form.

A HRIT Module wrapper tool

Eventually we will need a wrapper program to take such a module and prepare it for the various CMSes automatically. For that purpose an XML file would have to be added to each module to describe its contents, which the wrapper would read and turn into a CMS-specific form.

Hritcore module

To make writing Hrit modules really easy all of the Hrit-specific functionality is contained in another CMS-independent module called hritcore, which is added to the php include-path and from which not only superclasses for Hrit but also the mvdguilib.js Javascript functions, which provide cross-browser functionality for interactivity, can be called.

One of these support files is a surrogate or imitation HritRest service, which just accesses a local database for experimental purposes, rather than a remote service over the web. There is only one public method: get, which takes a REST-style URL as its only argument, and spews back whatever the caller requested. So if users request:

http://localhost/cortex/english/shakespeare/kinglear/act1/scene1/F1

they will get the F1 version of act 1, scene 1 of Shakespeare's King Lear, etc. And if they replace the first bit of the url by 'corcode' they will get the corcode for that version, and similarly for corpix.

Where this still needs to go

Later, when this kind of url is possible on the real REST service the HritRest.php file can be done away with. Shouldn't be long before the two example views: SingleView and CompareView are ready to demonstrate.

Next step, though, is to incorporate formatter (and why not also splitter and stripper?) into the php service and do away with XSLT forever. Oh, what a joy!

Formatter inside PHP

The formatter is a program to replace XSLT, but it uses our standoff markup solution called CorTex/CorCode. At the moment the CorCodeDemo calls formatter on the command line as an external script. But it struck me that because it replaces XSLT it ought to be called the same way that XSTL is - within the PHP daemon as a PHP extension. That way we won't get the hit of inefficiency by running it as a commandline tool. Instead it will just be available, once installed, for any HRIT-modules we design. I don't yet know how to do it, but since everything is open-source it should be easy.

Another refinement is the reuse of MvdCore, a Joomla! component I wrote to facilitate writing a robust set of Joomla! plugins for the MVD-GUI. But since it doesn't refer to Joomla!, except in order to exist as a module, I thought I would use it as a basis for every HRIT module, as a kind of framework library. That way, writing new modules should be dead easy and they will automatically work in every browser. Now that's cool.

Brave New World

Now we've thrashed out a pretty good picture of how the HRIT system will look, I decided to make the MVD-GUI in its image. That is, to use the HRIT REST service, the HRIT API, and write a HRIT compatibility layer for all my modules to run in. The BIG advantage of this is that, provided a compatibility layer is available for a particular CMS, the same module will run unmodified in that CMS (Content Management System). The only catch is that I'd have to find somewhere to host the HRIT Java REST service (cloud, left). So here's my current design for the compatibility layer:

In the Model-View-Controller design the Model handles all interactions with the database. Give me this, here is that, etc. So an implementation of the HRIT API fits that design pretty well (the pink box). It wouldn't have to access any databases directly, because it would get all the data it needs from the REST Service. So it could be the same on all CMSes.

The Controller on the other hand (orange boxes) deals with all the user-clicks in the view and decides what to do with them. It interposes between the view and the model to decide when to call the model and what to return to the view. It's the 'business logic' of the application. An individual CMS can't and does not in practice mandate an MVC design, but it does define conventions for calling modules. So in Drupal and Joomla!, HRIT modules will be defined with a library of functions that will act as the master controller for the module. Whereas the module itself will have its own private controller that will call the master one. The private controller will include the master controller with a require statement and assume the existence of certain functions or static methods inside that controller, say HRITController::doSomething().

The View (green box) can do what it likes, so long as it only uses PHP functionality, and doesn't call any CMS-specific routines or rely on any CMS-specific data. If it needs something like that it will have to get it from the compatibility layer via its private controller.

HRIT standoff format

The HRIT standoff XML format is designed to replace embedded markup by using standoff properties. It is not intended to be definitive, and the same information could easily be recorded using another format. All that matters is that it suffices. It supports the following features:

1. The text is in a separate file, which may be referred to by multiple HRIT markup files.
2. Several markup files can be combined to enrich the text simultaneously.
3. Properties may overlap
4. Both HRIT markup files and the underlying text files can be freely edited

The format doesn't perform these functions it just allows them to happen. So it is actually pretty simple.

Header

The header provides some essential structure and infomation:

<?xml version="1.0" encoding="UTF-8"?>
<hrit-markup style="TEI">

A CorCode is of course closely bound to a CorTex version. In the HRIT system each cortex and corcode is uniquely identified by a URN in the FRBR mould as a sequence of hierarchical names, e.g. "/corcode/english/shakespeare/kinglear/act1/scene1/folios/F1". A CorCode URN is the same as the corresponding CorTex URN except that the first component is "/corcode" instead of "/cortex". So there is no need to record that relationship explicitly in the markup.

The "style" attribute on the other hand is a reference to the URN identifying a CSS format file. This is used to render a CorCode into an external HTML form for display. It's not a complete name because the same corcode/cortex might be rendered in multiple ways, depending on the application and the user's preferences. Each CSS file points to just one CorCode, and hence the unique style name here. A full format identifier would look more like "/corform/TEI/hritsingle/luc-style", which would mean 'the core format for "TEI" corcodes in the hrit-single application in the LUC style'. The CorForm concept is new and we are still working out the details, but it seems clear that this kind of information has to be stored in the "cloud" with the cortexs and corcodes.

Ranges

The body of a HRIT markup file is composed of an ordered series of ranges. Each range points to a span in the base text and is specified by its relative offset from the previous range and its length. This facilitates editing, since changing one range only invalidates the immediately following one. It also has a name because it represents a property. Finally it may contain annotations, which are mostly leftover attributes from XML, although they can also be used to store invisible programming information such as links. But these will need to be backed up by direct functionality in a GUI; they are not intended to be edited by the user.

<range name="pb" reloff="0" len="0">
<annotation name="ed" value="F3"/>
<annotation name="n" value="765"/>
</range>
<range name="sp" reloff="271" len="20"/>

Removed ranges

If a range is labelled as removed="true", it can't be formatted and cannot specify a range in the base text. An example is the teiHeader element in TEI. Since this is metadata its content has a fundamentally different status to the text of the body. So the default recipe of stripper specifies that this element and all its children are removed. A removed element may have its own private content that is stored as part of the standoff markup. This 'content' can belong to any point in the file, but usually to the start, so it can have a reloff attribute, though not a len:

<range name="title" removed="true" reloff=0">
<content>Mr. William Shakespeares Comedies, Histories, &amp; 
Tragedies. Published according to the True Originall Copies.
</content>
</range>

This may sound like a hack, but the information has to be stored somehow if we later want to reverse the conversion from HRIT back to TEI. Of course files originating in the HRIT system itself won't have any removed elements.

Nesting of ranges

If a HRIT markup file has been imported from XML then its ranges will effectively be nested. But this information is not used during formatting, since ranges can freely overlap.

Tail

This is just:

</hrit-markup>

This format is still subject to development and may be changed in future.

How fast can we diff two strings?

On this question I have yet to read of any advance on Esko Ukkonen's 'Algorithms for Approximate String Matching' which appeared in Information and Control, 64, 100-118 in 1985. As per his predecessors, he uses the edit-graph to model the matching process, laying out the B-string across the top and the A-string down the left hand side (see diagram below). Finding the shortest edit script is akin to moving through this graph one square at a time. The x coordinates are just indices into the B-string, and the y-coordinates are expressed as x-i, where i is the index of the relevant diagonal. (The diagonals are numbered 0 at the origin, with increasing negative values on the 'down' side and increasing positive values on the 'right' side.) From each square there are three possible moves: right, corresponding to a deletion from the B-string; down, corresponding to an insertion from the A string; diagonally down and right, corresponding to a match (if the characters at that point are equal) or to an exchange if they are not.

In this diagram we transform 'aback' into 'beak'. First we delete 'a'. Then we match 'b', insert 'e', match 'a', delete 'c' and match 'k'. Note that each move takes us one beyond the square it was performed in.

Progressive refinement of the p-band

The basic idea of Ukkonen's (and Myers) algorithm is that the only positions of interest as we traverse the graph are the most advanced positions on each diagonal. So instead of storing NxM positions (as in the dynamic programming method of Needleman and Wunsch for example) we only need to store N+M diagonal positions – quite a saving. Ukkonen further reduces the search space to a narrow diagonal strip down the centre of the graph – the p-band (p.105f) – which can gradually narrow as we proceed toward the end (p.106). Both ideas have been republished as alleged improvements to his algorithm (e.g. Wu 1989 – cited 88 times). Ukkonen defines p as ⌊1/2(d_mn/Δ–|n-m|)⌋. In plain English the worst possible cost is incurred by exchanging all the characters on the 0 diagonal and then deleting all the characters horizontally until you get to M,N. Any path on the graph that is more than half that cost away from the goal has no chance of reaching it more efficiently than that. What is more, we can update p as we get closer to the goal, and we get a better idea of the cost of reaching D_mn.

Based on this idea my program assesses dynamically, for each move in the graph, whether it could result in a shorter path to the goal than the worst result of the currently best diagonal. If not, then it is dropped. My algorithm is also very space-efficient. Rather than allocating an array of size M+N (the lengths of the two strings) to hold the diagonals, I use a linked list to store only the active ones.

Moving through the graph

We construct a linked list of diagonals and number them, starting with the one between the two strings at 0,0 (the origin), numbered 0. The other diagonals along the y-axis are numbered -1,-2,-3 etc and the ones along the x-axis are numbered 1,2,3 etc. Then we assess the even and odd numbered diagonals in the list in alternate passes. The reason is that the computation of the even-diagonals interferes with that of the odd-diagonals. For each diagonal at index i and horizontal position x we compute the maximum x-value that would result from:

an insertion from the i+1 diagonal
a deletion from the i-1 diagonal
an exchange on the i diagonal

Whichever takes us further east along the diagonal (and by implication also further down) will be the best move. All things being equal we favour the exchange move because it promises to be the cheapest overall. After processing the even and odd diagonals we increment the d-value: our record of how much it has cost to transform B into A so far. If we are at one or the other edge of the linked list, and it is necessary, we also create a new diagonal to the left or right. This won't be processed in the current pass because it is odd when we are even and vice versa.

Finding the snakes

A match or 'snake' as Myers called them, is just a run of matching characters in the edit graph, and they give the diagonal method all its speed. But we have to be clear as to when we look for them. The very first square of the edit graph at 0,0 may or may not contain a matching character. If it does, we have to match the snake before checking for an exchange, but we will still have to do a delete and an insertion from 0,0. The reason is that otherwise we might miss an optimal snake starting on the -1 or 1 diagonal. Another position of care arises at the very last square at M-1,N-1. Until we have checked that square for a match as well as for insertion, deletion and exchange we won't have reached the real 'end', which is one character beyond M-1,N-1. For all other squares we just test for the existence of snakes after each edit operation, so we can be certain at the start of the next pass that the characters at the head of each diagonal do not match.

Exchanges vs insertions and deletions

Traditionally diff algorithms don't compute the exchanges. But an exchange move from x,y to x+1,y+1 costs only 1, whereas a deletion+insertion move to the same location costs 2. So exchanges are often much cheaper. The insertion/deletion pair can be recovered from any pair of exchanges. Replacing xxx with yyy is the same as deleting xxx and inserting yyy. Here's the result of my implementation of Ukkonen's algorithm. When you consider how many comparisons the program could have made (the entire graph) as opposed to the ones it did make (the squares marked with 'x'), you can see how efficient it is:

Recording the path

Finding the optimal path through the graph is no use if it doesn't allow us to construct a shortest edit script. One simple way to do this is to associate a path with each diagonal. The path will be implemented as a linked list. Each component of the path has an x,i origin, a length and a type (nothing [for the initial move], inserted, deleted, exchanged or matched). If the type changes, from, say, matched to exchanged, we create a new path-component and link it backwards to the last one. (If we went forwards we would need multi-way branches.) But if the type is unchanged we simply increase the length of the existing one. When we finally get to the end, the backwards-pointing path of the successful diagonal will contain the shortest edit script. To print it we just reverse the order and print it out. Here's the edit script for the above graph:

matched 11 chars at x=0 y=0
exchanged 4 chars at x=11 y=11
matched 25 chars at x=15 y=15
exchanged 3 chars at x=40 y=40
matched 1 chars at x=43 y=43

Downloadables

pdiff prints out an edit script but also generates a trace of moves taken in the edit graph if both strings are smaller than 100 bytes. It's free under the GPLv3 and is written in C++. It can also diff entire files.

Joomla! 1.6: An Attack of Biggerism

I was quite relieved to try out Joomla! 1.6. So it's not just me who releases software before it is ready. In fact the link to download its more stable predecessor, version 1.5, is about 1/10th of the size. So the users are being recruited to do the testing. The danger of this strategy is that they might just move off somewhere else, say Drupal.

On my Linux laptop running Firefox the default installation gave me a 20mm white border at the top of the page. Heaven only knows what for. Below that a cavernous banner that consumes another 40 mm, leaving a thin strip for content at the bottom. In the administrator pages gratuitous icons the size of surfboards float around in the limited space, dwarfing the innumerable input controls, which seem more bewildering than ever before.

Gone is the list of components. Instead you have a melange of components, plugins and modules, which you have to manually filter to get what you want. The old way of doing this, while not ideal, was better and required fewer clicks on the part of the user. What if after filtering I want to just see the modules I installed? More mouse-clicks which destroy my previous configuration. I think they need to take a hard look at how to design a usable interface not go wild on artwork.

Gone, too, are the polished templates of 1.5. Joni Mitchell was right: 'You don't know what you got till it's gone'. In its place a collection of ugly and nearly useless ones. On the banner we read: 'We are volunteers', which sounds more like an apology than as a boast. They are at serious risk of losing their market dominance. My rating so far: 2/10

Pixel-perfect positioning of elements in HTML

The web is full of advice, most of it bad, on how to find out the precise position of any element on an HTML page in any browser. Well the answer is simpler than I thought.

The Box Model

Each element on a HTML page is surrounded first by its padding, then by its border finally by its margin. Or put it another way, the margin is on the outside of the border and the padding is on the inside. Padding is usually included in an element's height and width calculation, border may be and margin almost never is.

Computing the offset of an element from the top of its window

First you need to determine the top and left offset of an element. I believe this works in all browsers.

function getTopOffset( elem )
{
 var offset = 0;
 while ( elem != null )
 {
  offset += elem.offsetTop;
  elem = elem.offsetParent;
 }
 return offset;
}

This works because the use of a fixed point on each element insures that all other margins, padding and border values add up correctly. As for the margin of the body element, although different browsers use different values, the offsetTop property is measured to the outer edge of the border, just like the value stored in offsetHeight, so includes the margin. So if, as in IE, the margin-top value of body is 15 then the offsetTop property of the first element inside body will be 15. A similar routine will work for the left offset.

Measuring the height of an element

The height of an element (or its width) is more complex because we usually don't include the border width. The cross-browser property clientHeight is only cross browser in name because in IE it is only set for formatted elements. For unformatted elements like div and p its value is 0. You can force it to have a clientHeight property by giving it a css property "display: inline-block" as recommended on many websites. This is a hack that changes the way the element is displayed, which could play havoc with your display. A cleaner way is to use the offsetHeight property. It's always set even in IE. The only problem is subtracting the border-top-width and border-bottom-width. But these can be reliably computed from the css style:

function getHeight( elem, inclBorder )
{
    var borderHeight = getStyleValue(elem,"border-top-width")
        +getStyle(elem,"border-bottom-width");
    if ( elem.clientHeight )
        return (inclBorder)?borderHeight+elem.clientHeight
            :elem.clientHeight;
    else
        return (inclBorder)?elem.offsetHeight
            :elem.offsetHeight-borderHeight;
}
function getStyleValue( elem, prop )
{
    var value = getStyle( elem, prop );
    if ( value )
        return parseInt( value );
    else
        return 0;
}
function getStyle( elem, prop )
{
    // test if in IE
    if ( elem.currentStyle )
        var y = elem.currentStyle[cssToIE(prop)];
    else if ( window.getComputedStyle )
        var y = window.getComputedStyle(elem,null)
            .getPropertyValue(prop);
    return y;
}
function cssToIE( prop )
{
 var parts = prop.split("-");
 if ( parts.length > 0 )
 {
  var ccProp = parts[0];
  for ( var i=1;i 0 )
   {
    ccProp += parts[i].substr(0,1).toUpperCase()
     +parts[i].substr(1,parts[i].length-1);
   }
  }
  return ccProp;
 }
 else
  return prop;
}

Again, width is computed similarly. The css properties are always set even if you add them via a style= attribute on the element. getComputedStyle (Mozilla) and the element's currentStyle property (IE) both give you the computed css styles of an element. Only problem is that IE uses camelCase names for the hyphenated property names. That's easily fixed.

Getting Window height

The Firefox way to get window height is just window.innerHeight. But this doesn't work on IE of course. You have to use document.body.offsetHeight or document.documentElement.offsetHeight. (Everyone says to use the clientHeight property but that doesn't include the borders and you can thus get the wrong answer on IE):

function getWindowHeight()
{
 var myHeight = 0;
   if ( typeof(window.innerWidth) == 'number' )
     myHeight = window.innerHeight;
 else if ( document.documentElement
  && document.documentElement.offsetHeight )
     //IE 6+ in 'standards compliant mode'
  myHeight = document.documentElement.offsetHeight;
 else if ( document.body && document.body.offsetHeight )
    //IE 4+ non-compliant mode
  myHeight = document.body.offsetHeight;
 return myHeight;
}

Using these properties my tests indicate that any browser will give you pixel-perfect readouts of the position of elements on the page.