Neil's Place

June 4, 2005

8:07 PM How Templates Work V

During rule processing, the template builder builds up a network of information such as what possible results are available, where content should be generated, and information that indicates what to do when the RDF datasource changes. This network of information remains for the lifetime of the template, or until it is rebuilt. The template builder uses an method based on the RETE algorithm to match data. This allows for a fairly efficient means of updating results when, for instance, a new statement is added to the RDF graph. Rather than rebuild the entire template, the algorithm allows only specific parts of the network of information to be re-examined. A similar method can be used when removing RDF statements.

While the information network created by the template builder contains a number of different pieces of necessary information, for the purposes of this discussion, we will only be interested in the list of possible results. The builder begins with a single possible result, called the seed. The builder processes each of a rule's conditions in sequence. To do this for a particular condition, it iterates over the possible results found so far and either accepts each result or rejects each result. For the first condition, only the seed will be available as a possible result. At each step, new possible results may be added, or more information pertaining to an existing result may be added to the network. Naturally, a rejected result will be removed. Once all results have been examined, the builder moves on to the next condition. Once all conditions have been analyzed, any results which still remain go on to become matches. The matches are the endpoints and will cause content to be generated. So, to summarize:

  1. Start out with a one possible result as the seed
  2. Iterate over the results determined so far and augment them with additional data
  3. Add any new possible results
  4. Remove any rejected results
  5. Repeat steps 2 to 4 for each rule condition
  6. Once done, all remaining results become matches

Each possible result is made up of a set of variable-value pairs. For instance, a result would look something like the following:

(?name = Fred, ?age = 5)

This result has two variables, ?name with the value 'Fred' and ?age with the value 5. Variables begin with a question mark, and values are RDF resources or literals. Here we will use strings for the values so they are easier to read. If we had two results, they might look like this:

(?name = Fred, ?age = 5)
(?name = Mary, ?age = 12)

This is how we'll represent the potential results in this and the following discussions.

Later, we might have a condition which removes all Male results. So, our results after this might look like the following:

(?name = Mary, ?age = 12, ?gender = Female)

This condition has removed Fred from the potential results and added the ?gender variable for Mary. This is typical of how a rule condition works, by adding additional variables to a result and filtering out those that don't match a particular value. If this was the last condition, Mary would go on to become a match to be displayed.

Comments ( 5 )

June 3, 2005

4:10 PM How Templates Work IV

Once the template builder has compiled the rules, rule processing and content generation can begin. The template builder generates content lazily, that is, it processes as little as need, and only continues when necessary. For instance, consider the example below:

<vbox datasources="http://www.xulplanet.com/ds/sample.rdf"
         ref="http://www.xulplanet.com/rdf/A" hidden="true">
  <template>
    ...
  </template>
</vbox>

The <vbox> is hidden as indicated by the 'hidden' attribute. Since any content that would be generated wouldn't be displayed anyway, the template builder doesn't do anything, putting off work until later. If you show the vbox by setting the hidden state to false, the template builder will be invoked and the content will be generated.

Does this mean that templates cannot be used inside hidden areas of the UI? No, you can still do that. Changing the hidden state of an element isn't the only way to cause content to be generated. Calling a DOM API which needs to get at the generated content will cause the template builder to generate output. For example, just calling the code like the following on the hidden vbox above will start off the template builder.

var length = vbox.childNodes.length;

This request to return the number of children of the vbox will make the template builder process the rules and output content. Once done, the correct length can be returned.

All of this is transparent to the XUL developer. When the template builder decides to start generation is determined automatically and you don't need to do anything special to get this to happen. However, there are two cases where content is not generated automatically: menus and child tree items.

Content inside a menu is not generated until the menu is opened. This makes sense since the user can't see the contents of the menu until it is open. However, it also means that the DOM API usage, such as an attempt to get the number of child nodes as above, will also not include generated items until the menu is opened. This is an important distinction. That means that you will not be able to rely on being able to retrieve the generated menu items until the menu is opened. A similar rule applies for child tree items. The children are not generated until the user presses the twisty to open the container, or a script opens a row.

Lazy generation comes in handy for menus and trees especially when dealing with recursive items. It would be rather time consuming to generate output for every item in a tree, even for those not displayed, so the template builder doesn't do so.

The template builder is even lazier. If the generated content itself contains hidden elements, those child elements will not be generated until necessary. When building content, the builder iterates down the node tree, copying and building only when needed.

Next, we'll look into how the template builder processes the rules.

Comments ( 9 )

June 2, 2005

6:26 PM How Templates Work III

A XUL template is made up of series of rules. Each rule contains two things, a set of instructions for navigating through an RDF graph and some XUL content to generate. Given a starting point, the template builder will evaluate the navigation instructions for each rule and will generate a series of endpoints matching that rule. The corresponding content will then be generated. It's actually more complicated than that but this is the basic idea.

There are two syntaxes for declaring the rules, the simplified syntax and the extended (or full) syntax. As its name implies, the simplified syntax is simpler but is limited in the type of data that it can iterate over. It may be used to iterate over one and only one arc (or arrow) in the RDF graph. The extended syntax may navigate anywhere in the graph. Almost always, the simplified syntax will be used to iterate over a set of children of an RDF container like a Seq. An RDF Seq is a container that contains children in a specific order. The template will generate these results in that order.

The simplified syntax is a subset of the extended syntax, that is, it is possible to rewrite a rule that uses the simplified syntax using the extended syntax. In fact, the template builder will internally convert the simpler rule into an extended syntax rule for use. Neither syntax is preferred; you may use the extended syntax exclusively if it feels more natural to you. Note however, that the simplified syntax uses a slight optimization when using more than one rule which the extended syntax does not use. Well look at this in more detail as we look more at rules.

Each rule is declared using the <rule> tag, which you would place directly inside the <template> element. You may have as many rules as you wish, or you may have only one. When using the simplified syntax, you may omit the <rule> element when you have only one rule as its usage will be implied. The extended syntax, however, always requires the <rule> element.

Here is the outline of the template syntax so far.

<vbox datasources="http://www.xulplanet.com/ds/sample.rdf"
         ref="http://www.xulplanet.com/rdf/A" flex="1">
  <template>
    <rule>
      -- rule content goes here --
    </rule>
    <rule>
      -- rule content goes here --
    </rule>
  </template>
</vbox>

When the template builder starts processing, and after it has started the datasource loading, it first must compile the rules. This step involves working through the rules and processing them into internal structures. Thus, changing the rule elements around dynamically doesn't affect anything. However, rebuilding the template (using the builder.rebuild method) will recompile the rules and reapply the template again. This means that you can change the rules using DOM methods, rebuild the template, and get different results.

Comments ( 7 )

June 1, 2005

2:45 PM How Templates Work II

RDF is, in mathematical terms, a labeled directed graph. That means that RDF is a graph of nodes and arrows between them where each node and arrow has some label. Since it's a graph, arrows can point all over the place and nodes can have any number of arrows pointing out of them and pointing at them. And also because it is a graph, there is no real starting point or root node so you can just start anywhere. In the picture below, you can see that node A at the top has arcs pointing to B, C and D. As well, C has an arc pointing to D. You could have arcs pointing elsewhere, for example node D could have an arc pointing back to A. To navigate around, you could start at node A and navigate around the graph following the arrows to B, C or D. Or you could start at B and go to A and then go to C and D. No requirement exists to follow the arrows in the direction they point; you can easily go the other way. The picture was generated from the W3C's RDF validator, a good place to go to check if your RDF is valid.

The text in red are the labels for the arrows, called predicates. In this example, all the arrows have the same label. Usually, this won't be the case. Templates provide a means of navigating around using only arrows with specific labels. Here is the serialized RDF/XML for this graph.

<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
         xmlns:rel="http://www.xulplanet.com/rdf/">
  <rdf:Description rdf:about="http://www.xulplanet.com/rdf/A">
    <rel:relatedItem rdf:resource="http://www.xulplanet.com/rdf/B"/>
    <rel:relatedItem rdf:resource="http://www.xulplanet.com/rdf/C"/>
    <rel:relatedItem rdf:resource="http://www.xulplanet.com/rdf/D"/>
  </rdf:Description>
  <rdf:Description rdf:about="http://www.xulplanet.com/rdf/C">
    <rel:relatedItem rdf:resource="http://www.xulplanet.com/rdf/D"/>
  </rdf:Description>
</rdf:RDF>

For a XUL template query, you first need to select a starting point in the RDF graph. Once you have selected a starting point, you use a number of statements which indicate where to go next when navigating the graph. Eventually, you will end up with a set of nodes you consider the endpoints of your query. These become the results and content would be generated for each of these results. Say you start at A. You could navigate to B, C and D and generate three blocks of output. Or, you could start at D and follow two arrows back. This will get two results, A and B. Look at the graph to see if you can see why two results would be generated in this case.

In XUL template terminology, the starting point is called the container or reference point and the endpoint is called the member. It is so called because it is most common to gather the list of the members, or children, of a container. But this doesn't have to be the case. Any starting point and ending points will do.

Nodes in RDF are identified by a string value. There are two types of nodes in RDF, resources which usually represent 'things', and literals which are values like the names of things, the dates of things, the sizes of things, and so on. A literal's value is, for example, the name of the thing, such as 'Fred'. A resource's value is a URI which for your own RDF data you can just make up. We'll use the URI of the resource nodes in a template. In the image, the resource URI's are the blue labels of each node. There are no literals in this example, but we'll see some later.

Let's say we want the starting point to be A from the above example graph. We will use A's URI (http://www.xulplanet.com/rdf/A) as the reference starting point. In a XUL template, you specify the starting point using the 'ref' attribute. Here is an example:

<vbox datasources="http://www.xulplanet.com/ds/sample.rdf"
      ref="http://www.xulplanet.com/rdf/A" flex="1">

This is an indicator that we want to construct a XUL template using the reference point with the URI 'http://www.xulplanet.com/rdf/A'. Next, we'll see how to construct the template.

Comments ( 9 )

May 31, 2005

5:22 PM How Templates Work I

XUL templates are apparently difficult for many to understand. Unfortunately there are a lot of bits to have to learn to be able to use them effectively: RDF, the querying syntax, and some additional XUL features. The lack of useful logging and error messages makes things doubly difficult. Perhaps templates may be a bit easier on someone if they had an understanding of how tenplates actually work. This is part one in what will hopefully be a longer series of posts about this topic.

To begin, a XUL template is a means of producing a block of content for each result from some query or query-like operation. A good analogy is to the results of a database query. For each result returned from the query, generate some content. The template syntax allows for different rules to generate different content based on particular criteria as well as set attribute values from returned results. Some other systems call this databinding. Effectively, XUL templates are the XUL way of doing databinding. However, with a template, there are two restrictions. First, you can only generate content from the results of a query. You can't just take a single piece of data and assign it to an attribute, since templates are designed for repeated blocks of data. Second, you can only bind to an RDF datasource. These restrictions should be removed in the future.

In XUL, the RDF datasource is specified by placing the 'datasources' attribute on an element. When the XUL parser sees an element with this attribute, it constructs a template builder for the element and attaches it to the element. It is expected that there will be a template inside the element. The template builder loads the datasource, performs the query on the datasource and generates content for each result. The content is inserted into the XUL just as if you had placed it there yourself. Here is an example:

<vbox datasources="http://www.xulplanet.com/ds/sample.rdf">

This example specifies the datasource 'http://www.xulplanet.com/ds/sample.rdf'.

The template builder loads the datasource using the RDF service in the same way as you would create a datasource through the RDF service directly. The datasource is loaded via its URL. Some RDF datasources are provided with Mozilla -- their URL's start with 'rdf:'. Otherwise, the datasource is loaded as any other URL is loaded. If the datasource is already loaded and cached, the template builder can begin work right away. Otherwise, there isn't anything to do until the data is loaded. Actually, this isn't quite true. The RDF service starts the load of the datasource in the background and the template builder goes through the process of building content anyway. Naturally, since there is no data yet, no results will be available so the builder ends up building nothing.

Once some data starts arriving, the template builder scans its information to see if some results can be created. If so, some content can be generated. If not, nothing gets generated again. An interesting thing to note is that due to the nature of the RDF parsing process, the builder generates results and builds content incrementally while the data arrives. Of course, since the data arrives so quickly from the network, you really don't notice this. If the datasource is already loaded, the builder can construct content all in one step, although even this isn't completely true as we'll see later.

The template builder can also use multiple datasources which are all combined into a single datasource as if they were all in one datasource to begin with. An nsIRDFCompositeDataSource is used for this purpose. You can get this composite datasource in a script by using an element's 'database' property if you want to add or remove datasources from it.

As mentioned, the template builder loads the datasources by passing the URLs to the RDF service. However, the special URL rdf:null is used to indicate that you mean no datasources, or an empty datasource. The composite datasource will still be created but no datasources will be added to it. This is used when you need to specify the datasource dynamically with a script.

In addition, for chrome XUL (such as extensions), the datasource rdf:local-store is always included in the composite. The local store is a datasource which is usually used to hold state information such as window sizes, which columns in a tree are showing and which tree items are open. You can query for any data in the local store in a template although this is rarely done.

When multiple datasources are used the RDF is combined as if it was one large datasource. That means that a template query can grab data from anywhere in all of the datasources. This combining of datasources is often termed aggregation. This can be quite a useful feature and works regardless of the datasource. For instance, you might use the built-in bookmarks datasource which holds the user's browser bookmarks and use your own datasource to add custom data about those bookmarks.

<vbox datasources="rdf:bookmarks http://www.xulplanet.com/ds/sample.rdf">

In part two, we'll look at the ref attribute.

Comments ( 4 )

April 21, 2005

10:48 PM Update for April 21

So I took a bit of a break from the XUL templates stuff for a while. In case you didn't know, there's a patch in the bug. It would be great if someone would make a build and stick it up somewhere so people could try it out.

I've been spending much of the last month on some MDG work. It's Mozilla development naturally, but you won't ever see the results, at least not for a long time anyway. But some of you can at least feel good that you are unknowingly paying for it via taxes.

One thing about being involved in an open source project and having at least some name-recognition in that project is that you get numerous job offers. There certainly seems to be some demand building up for experienced XUL developers, of which there aren't many. I wonder if there would be interest in some XUL training sessions. I suppose that would require enough people all in one place though.

In the meantime I've been working on and off on a new tutorial, not a big one, but it should be useful. Oh, and I also posted the patch I made for the slider tag that I wrote a while ago.

I think I'll go on vacation for two weeks.

Comments ( 5 )

March 29, 2005

7:38 PM Templates and Storage

Hey look! It's a XUL template created without the use of any RDF!

Instead of grabbing the data from an RDF datasource, it performs a query on an SQLite database via mozStorage. OK, there is some RDF being used under the hood, but a template author won't need to worry about this. Here is the XUL code used (I've hard coded the database for now):

<tree datasources="some-db" ref="*" rows="10" flex="1"
      flags="dont-build-content dont-recurse">
  <treecols>
    <treecol id="name" label="Country" flex="1"/>
    <treecol id="capital" label="Capital" flex="1"/>
    <treecol id="population" label="Population" flex="1"/>
  </treecols>
  <template>
    <query>
      select * from Countries where name like '%e%'
    </query>
    <action>
      <treechildren>
        <treeitem uri="?">
          <treerow>
            <treecell label="?name"/>
            <treecell label="?capital"/>
            <treecell label="?population"/>
          </treerow>
        </treeitem>
      </treechildren>
    </action>
  </template>
</tree>

The patch to implement this will be coming soon to a bug 285631 near you.

Comments ( 35 )

March 18, 2005

7:29 PM XUL Tutorial Updates

Some significant updates to the XUL Tutorial today, including rearranging the order of the sections and a rewrite of much of the information pertaining to trees. Also, seven new pages on events, DOM scripting, box objects and tree views have been added.

Comments ( 70 )