Limitations of XSugar

In previous posts, I explained how XSugar could be used to transform configuration files to XML and back. Preserving white characters (space, tab, carriage return, etc.) is possible by creating special elements to hold them. In a simple round-trip, when the XML document is not modified, it works well. But, there are issues when the XML document is modified. For example, be this simple XML with strict nodes, from the students example of XSugar.

<students xmlns="http://studentsRus.org/">
  <student sid="19701234">
    <name>John Doe</name>
    <email>john_doe@notmail.org</email>
  </student>
  <space1> </space1>
  <space2> </space2>
  <newline>
</newline>
  <student sid="19785678">
    <name>Jane Dow</name>
    <email>dow@bmail.org</email>
  </student>
  <space1> </space1>
  <space2> </space2>
  <newline>
</newline>
</students>

There are spaces and newline elements that follow the student record. They are used to restitute the exact formating of the original string. We can then modify an existing value, and spaces will be preserved, and this correspond to a minimal edit.

But, say another record is inserted after the first student, but before space1 element, then the first record will see it's spacing reset to default values, and the new inserted element will get the spaces from the first record! This doesn't correspond to minimal edit, and is similar to alignment problem found by Foster et. al. in Boomerang.

If a student element is removed, but spaces elements are left, then it will cause a syntax error according to XSugar stylesheet. If an element is moved, it must inserted to right place in the XML, otherwise syntax error may occur.

It may be possible to fix the XML before transformation to non-XML, by adding, moving or deleting space elements. The idea to use the original document and the modified one to produce the updated output is already what does a lens, and is exactly what Augeas does. And now, with the introduction of the recursive lens, Augeas is about to support context-free languages, and opens the door to handle the Web server Apache configuration, and many other.

That's all for now, stay tuned!

Static validation of strict bidirectionality

These days, I had some fun to validate XSugar stylesheet for their strict bidirectional property. XSugar can convert non-XML documents to XML documents, and vice-versa. In theory, you get back exactly the same file if it does a round-trip to and from XML. But, there are few tricky things that prevent it to be exactly the same. XSugar verify statically the reversibility of a stylesheet, by verifying that both grammars are bijections. It means that there is no ambiguity, and so there will be always one way to do the conversion. But, not all stylesheet that are valid in this respect will yield correct behavior when performing actual transformation. The problem is linked to the fact that some white spaces may be lost in the transformation. To understand the problem, I will use a concrete example.

Say you have the following file, and want to convert it to XML. There are a bloc of numbers lines followed by words lines. Elements are separated by space, and there may be spaces before and after each lines.

  123  456  789  
  987  654  321  
  abc  def  ghi  
  ihg  fed  cba  

We will convert this file to the following XML.

<?xml version="1.0" encoding="UTF-8"?>
<a xmlns:b="http://udes.ca/noesis">
  123 456 789
987 654 321

  <z>
    <y>abc</y>
    <y>def</y>
    <y>ghi</y>
  </z>
  <z>
    <y>ihg</y>
    <y>fed</y>
    <y>cba</y>
  </z>
</a>

The stylesheet looks like this...

xmlns:b = "http://udes.ca/noesis"

NUM = [0-9]+ (MAX)   /* numbers */
ALPHA = [a-zA-Z]+ (MAX) /* letters */
NL   = \n|\r|\r\n   /* mandatory new line */
SP = [ \t]+ (MAX)   /* mandatory white space */
OSP = [ \t]* (MAX)   /* optional white space */

/* top-level rule : define the whole document */
a : [xs x] [ys y] = <a> [xs x] [ys y] </>

/* sequence of lines of numbers separated by space, with optional leading and endin white space  */
xs : [OSP] [ns n1] [OSP] [NL] [xs n2] =  [ns n1] [NL] [xs n2]
: =

/* numbers sequence */
ns : [NUM num] [SP] [ns n] = [NUM num] [SP] [ns n]
: [NUM num] = [NUM num]

/* sequence of lines of words separated by space, with optional leading and ending white space */
ys :[OSP] [y y1] [OSP] [NL] [ys y2] = <z> [y y1] </> [ys y2] 
: = 

/* sequence of <y> elements that hold actual words */
y : [ALPHA alpha] [SP] [y y1] = <y> [ALPHA alpha] </> [y y1]
: [ALPHA alpha] = <y> [ALPHA alpha] </>

... and it validates well.

$ xsugar -b strict-test3.xsg
Transformation is guaranteed to be reversible!

But, when we actually try to convert the XML back to the non-XML format, we get a parse error on char 74. When activating the debug mode of XSugar, we can see the result of XML normalization, which is a preparation step done before parsing.

Normalized input:
<a>123 456 789
987 654 321<z><y>abc</><y>def</><y>ghi</></><z><y>ihg</><y>fed</><y>cba</></></>

We see that spaces and carriage return before and after the number text node are lost. This is because the interleaved text with other element is trimmed. Spaces inside the text are preserved by the trim. This doesn't occur when an element contains only text. The parse error occur because the last mandatory new line is dropped. Let's fix the xs rule.

/* sequence of lines of numbers separated by space, with optional leading and endin white space  */
xs : [OSP] [ns n1] [OSP] [NL] [xs n2] =  [ns n1] [NL] [xs n2]
: [OSP] [ns n1] [OSP] [NL] = [ns n1]

This makes the last return carriage optional, and parsing succeed. Let's look at the diff between the result and the original file.

$ diff -u strict-test.txt strict-test3.txt.back
--- strict-test.txt 2010-03-05 15:33:52.043893254 -0500
+++ strict-test3.txt.back 2010-03-12 00:23:12.482905316 -0500
@@ -1,4 +1,4 @@
-  123  456  789  
-  987  654  321  
-  abc  def  ghi  
-  ihg  fed  cba  
+123 456 789
+987 654 321
+abc def ghi
+ihg fed cba

The content is there, but the actual diff shows that every lines are modified. This is because some terminals are not labeled. When this is the case, their values are lost, and example string is generated back when there is not corresponding item. It explains why spaces are all reset to their default values, the empty string for the optional white space, one space for the mandatory white space, and the default carriage return.

Hence, we have to look at two things to make sure stylesheets are strictly bidirectional.

First, the easy part, all items in the stylesheet must be labeled. This way, we can be sure the XML document will contain all chars from the input, and no information will be lost. We only have to traverse the stylesheet and make sure that every RegexpTerminal are labeled.

Second, interleaved text nodes must not begin or end with white characters [ \t\r\n], otherwise those chars will be lost. This is harder to do. First, we must detect if an element contains text nodes, elements, or both, from the stylesheet. Determining this for StringTerminal, RegexpTerminal and Element objects is straight forward. First two generate text, while the other yield elements. But, this is non-trivial for Nonterminal objects, because of the recursive nature of these items. The problem is a chicken and egg problem, because to determine the actual possible values for a nonterminal, we have to compute this nonterminal and substitute it's actual value in a recursive rule, which produces a loop. One solution to this problem is to compute the regular approximation of the XML stylesheet rules. It yields an automaton for each nonterminal that accepts a superset of the XML content than the stylesheet allow. Here is an example for the rule y.



We can know which kind of content this nonterminal have by looking at the transitions of the automaton. In the last example, we know for sure that the nonterminal will yield only elements. The last step is to verify that the interleaved text content beginning and end may overlap with white chars. Here again, regular approximation of nonterminal is used, but this time on the grammar itself. The overlap operator, used for horizontal ambiguity detection, is used. If such overlap exists, such as "WHITE <-> TEXT <-> WHITE", information lost may occur.

With this new information, developers can adjust the stylesheet to label items and enclose text inside elements and prevent information lost.

In summary, strict bidirectionality is required to prevent lost information in a transformation round-trip. Information lost can be caused by unlabeled items in the stylesheet, or because of trimming of interleaved text nodes. A method to detect areas that may not be strict, based on regular approximation of the stylesheet and the grammar, using the overlap operator, is proposed. Results from different stylesheets will be given soon. Stay tuned!

Why iPad is Evil

Apple just launched the iPad last week, and I was a bit shaken by it. It's a piece of art of human interaction design, and it changes the relation we could have with a computer, more ubiquitous than ever. The device itself is amazing at the technical level, and set the bar for competitors.

But, let's think about the concept in a whole. Apple provides stores for music, books and applications. In fact, this device is a personal buying device, where you can buy only content provided by Apple and it's partner. It's a kind of perfect world, where the consumer is captive like anything ever before, a garden of pure ideology, in each one may bloom, secure, away from the pests, and ... wait a minute! Doesn't it makes you think about 1984?

http://www.youtube.com/watch?v=OYecfV3ubP8

What a closed world we would be in if Apple had dominated the market, closed hardware, closed software, and forced to buy content from Apple!

So, I say no to that iPad, and I will wait for an truly open platform.

Strict reversibility in XSugar

XSugar is a tool to do bidirectional transformations between two file format. This is particulary useful to provide common API to configuration files under Linux. For example, here is the result of a stylesheet on /etc/hosts file :

<hosts xmlns="http://usherbrooke.ca/">
<record>
<ipaddr>127.0.0.1</ipaddr>
<canonical>localhost</canonical>
</record>
</hosts>

This file can be converted back to it's flat format. But, as you may notice, indentation doesn't appears in the XML file, and will be lost. Spacing is reset to a default value. The round-trip between hosts file and XML format keeps the semantic, but looses formating. Even without modification, if the file is written back, diff will show changes. Once spaces are reset, round-trip will yield identity function i.e. strings will be exactly the same.

One solution to overcome this problem is to add to the XML all elements that would be lost otherwise. This can be done by labeling terminal elements, and add corresponding nodes to XML part of the stylesheet. For examples, this rule loose optional "a" header :

A = [a]*
X = [x]+
n : [A] [X x] "z" = <x> [X x] </x>

Providing input "aaaaxxz" will give the following XML :
<x>xx</x>
Converting it back to non-XML will yield the string "xxz". Since the empty string matches "[a]*", this is the default string that is returned.

Now, let's label the terminal "A" :

A = [a]*
X = [x]+
n : [A a] [X x] "z" = <x> [X x] <a> [A a] <a></x>

Now, we get the string
<x>
  xx
  <a>aaaa</a>
</x>
and converting it back to non-XML format yield "aaaaxxz", the exact same string as the original input.

Preserving semantic of the file is simple bidirectional property. In addition, if the stylesheet preserve the concrete representation of an input, I call this strict bidirectionality.

Strict bidirectionality can be achieved by labeling unlabeled terminal, and add corresponding element to the XML part. I did a small prototype of this algorithm, that augment the resulting stylesheet. Hence, any stylesheet can be made strict bidirectional.

It rises the question : can we staticaly verify that a stylesheet is strictly bidirectional. Hopefully yes, it's really simple. We have to do the basic check that the stylesheet is bidirectional, and then verify that all regular expression terminal are labeled. This way, we are sure that all the variable concrete string will be represented in the XML.

Automatic strict bidirectionality for stylesheet and static validation of this property will be useful to provide the behavior a system administrator would expect from a tool that modify configuration files under Linux. Let's go on!

Bcfg2 V.S. Puppet

Bcfg2 and Puppets are two tools for system configuration management, where we want to install configuration files, packages and adjust permissions. It seems simple said like this, but it's near from trivial when the target machines are various operating system and versions.

Bcfg2 and Puppet, while they share the same goal, are completely different in terms of their concepts, how does the desired state is modeled. The fundamental concept here is more important than the actual implementation.

Puppet is like a programming language for system administration. It's another meta-language, with it's own syntax, to indicate what files, packages, users and such, should be present on a system. It's concepts are very close to Cfengine. Well, I used Cfengine a lot, even developing a small utility to automating the management of files under Subversion (svnengine). But, while using this tool, I really came to one simple conclusion : what a mess for so little! I ended up doing everything in scripts, which are copied by cfengine and run in a cron. Big deal.

Bcfg2 is not the same, because unlike Puppet, you don't program configuration elements, they are declared in XML document. The client, specific to a target, encapsulate actions on that target, their sequencing, error handling, etc. This model enables advanced behavior, because the model can be manipulated programmatically, which is not the case for Puppet. If you want to output a Puppet manifest, you have to output strings, which is a Middle Age practice!

Bcfg2 implementation itself has some glitches that must be fixed, but the concept behind it represents a building block for semantic system configuration management, which represent the future. Bcfg2 belongs to scientific field, while I think that Puppet has the exposure it has now because of marketing wave.

But, as the history reminds us, it's not always the best product or software that wins...

Pragmatic testing

It's certainly a matter of fact that good practice in software development include automated testing. Developing without unit tests is stone age practice. I read few books about testing, and many of them are about writing bureaucracy plans, not code. Reading documentation about unit testing framework doesn't provide much information about how to design tests. Here are few learnings from my experience.

• Automated tests should be easy to write and run. If they are hard to run, if they require a special manual setup, then they will be run infrequently. If you need a database or a daemon, it should be setup and launched automatically on localhost by test running scripts. Default config that just work should be provided to avoid configuration mess. Document needed packages from known archives to run tests, that may be different than running or compiling the software.
  
• Take care to apparmor when trying to launch a daemon with unusual locations : it may fail to start because of security restrictions. Disabling it may be necessary in some conditions.
  
• If the program operates on file, then create them in a temporary directory, flushed at each run. A program that copy files is testable : execute the operation and verify that files are where they should be.
  
• Running tests should be fast. if testing requires few minutes each time, and you are interested only to the result of one of them, it's not efficient. A simple solution is to provide a way to test only a subset of all tests.
• Running tests should usually not require root access, excepted for special purpose. If you bind ports, use a port over 1024 to avoid restrictions. Don't use global settings, use relative path to settings and files. If you get data from system library, you can simulate obtained data by providing objects with the same interface.
  
• Software always operates on data. You will need test data that simulate possible inputs. If your application reads input files, then those files should be held beside test code.
• One tests should not depend on previous test to succeed, they should be independent. In other words, the result should not depend on the order in which tests are executed. To make sure that tests are not linked together, always start from a known state. It means reloading initial data for each test, recreating objects and such. This is conveniently done with setup and tear down method usually available from unit testing framework.
• Test Driven Development is about creating test and code for some functionality together. This is the basic thing to do to make sure at least it works. Testing can go further for critical code, by trying to break the code, use it in ways that it may not have been thought by programmers. This kind of tests needs a different point of view, and should be done by someone else.
• Don't depend on external services. Tests environment should be self-contained, and running tests should be possible without network access. This may not be possible for all situations, for example if the application is interacting with google API, we can do the assumption that the service will be available, and anyway, we can't reproduce the service on localhost. But providing local servers when possible limit dependencies to run tests, and avoid network delays.
  

I hope that these few advices will help you build better testing!

Django, soooo cool

A log time ago, I did a small form in PHP to feed data in a database. I did create the HTML form and the database schema, wrote small functions to validate the form, all inside one php page. SQL statements, fields names and everything else was hardcoded, and it was a nightmare to test and maintain. I was feeling like a prehistoric men, who was trying to survive with rudiment tools. Well, it was the old days.

Now, I had a revelation while using Django! Don't loose your time with other crappy framework and use Django! Django contains all pieces needed for all the gory details of web development, like session management, forms, database and templating. It's so powerfull : you write your model once, Django generate sql statements for the database, generate HTML form to add or modify data, with data validation in bonus, in few lines or code. Documentation is wonderful.

There are some days like that when I really feel that technology is getting better, and Django is a wise and beautiful piece of work.

Look at www.djangoproject.com