Thoughts on XSLT

Kernow 1.7 released

2011-01-10T13:56:00.002Z

Kernow 1.7 is now available:

integrates LexEv (which now reports internal and parameter entities, along with CDATA sections, comments, numeric and entity refs, and the DOCTYPE)
On OSX and linux, it uses the "Nimbus" look and feel, on Windows it still uses native
includes the latest Saxon HE 9.3.0.2
directory transforms: input directory structure is now recreated in the output directory
files are correctly released, rather than held while Kernow is open
the caching entity resolver now correctly load all files from the cache dir first
updated to the latest Bounce version, which fixes some freezing in the sandboxes
includes Xerces 2.10 which partially supports XSD 1.1
fixed several small bugs

Kernow 1.7 is released as a trial version which allows you to hit the run button 100 times, after which you will need to enter a code to continue. The code can be purchased using the Help -> Purchase menu.

Kernow 1.7 beta available

2010-07-19T14:45:00.002Z

Kernow 1.7 beta is now available:

integrates LexEv (which now reports internal and parameter entities, along with CDATA sections, comments, numeric and entity refs, and the DOCTYPE)
includes Saxon HE 9.2.1.1
directory transforms: input directory structure is now recreated in the output directory
files are correctly released, rather than held while Kernow is open
the caching entity resolver now correctly load all files from the cache dir first
updated to the latest Bounce version (enabling "folding" in the sandboxes)
includes Xerces 2.9.0 which partially supports XSD 1.1
fixed several small bugs

Mark Logic adds XSLT support

2009-11-17T10:10:00.004Z

Mark Logic currently lacks any support for XSLT... but that's about to change: Norm Walsh has announced upcoming support for it in version 5.

XML Schema 1.1 tutorials

2009-09-14T12:54:00.002Z

Roger Costello has created a couple of good powerpoint presentations on XSD 1.1
One tutorial is for developers, the other for managers which contains more general wordy descriptions of the benefits of 1.1

Some sample templates for use with LexEv

2008-08-22T14:56:00.005Z

If your XML has been parsed using LexEv, here are some sample templates for handling the LexEv markup.

To output an entity reference:


<xsl:template match="lexev:entity">
 <xsl:value-of disable-output-escaping="yes" select="concat('&amp;', @name, ';')"/>   
</xsl:template>

To process a CDATA section as markup:


<xsl:template match="lexev:cdata">
 <xsl:apply-templates/>   
</xsl:template>

To output a DOCTYPE from the processing instructions:

In XSLT 1.0 the doctype-public and doctype-system attributes on xsl:output are static and need to be known at compile time, which means I'm afraid you have to do this:


<xsl:template match="/">
<xsl:value-of disable-output-escaping="yes"
 select="concat('&lt;!DOCTYPE ', name(/*), '&#xa;  PUBLIC &quot;',
  processing-instruction('doctype-public'), '&quot; &quot;',
  processing-instruction('doctype-system'), '&quot;&gt;')"/>
<xsl:apply-templates/>
</xsl:template>

In XSLT 2.0 you can use xsl:result-document where the doctype-public and doctype-system are AVTs which mean their values can be determined at runtime:


<xsl:template match="/">
<xsl:result-document
 doctype-public="{processing-instruction('doctype-public')}"
 doctype-system="{processing-instruction('doctype-system')}">
 <xsl:apply-templates/>
</xsl:result-document>
</xsl:template>

LexEv XMLReader - converts lexical events into markup

2008-08-21T15:34:00.004Z

It's often a requirement to preserve entity references through to the output (which are usually lost during parsing) or to process the contents of CDATA sections as markup. The Lexical Event XMLReader wraps the standard XMLReader to convert lexical events into markup so that they can be processed. Typical uses are:

Converting cdata sections into markup:

<![CDATA[ <p> a para <p> ]]>
to:
<lexev:cdata> <p> a para </p> </lexev:cdata>

Preserving entity references:

hello—world
is converted to:
hello<lexev:entity name="mdash">—</lexev:entity>world

Preserving the doctype declaration:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
is converted to processing instructions:
<?doctype-public -//W3C//DTD XHTML 1.0 Transitional//EN?> <?doctype-system http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd?>

Marking up comments:


is converted to:
<lexev:comment> a comment </lexev:comment>

To use LexEvXMLReader with Saxon:

java -cp saxon9.jar;LexEvXMLReader.jar net.sf.saxon.Transform -x:com.andrewjwelch.lexev.LexEvXMLReader input.xml
stylesheet.xslt

Make sure LexEvXMLReader.jar is on the classpath, and then tell Saxon to use it with the -x switch (copy and paste this line -x:com.andrewjwelch.lexev.LexEvXMLReader)

To use LexEvXMLReader from Java:

XMLReader xmlReader = new LexEvXMLReader();

You can control the following features of LexEv:

enable/disable the marking up of entity references

enable/disable the marking up of CDATA sections

set the default namespace for the CDATA section markup

enable/disable the reporting of the DOCTYPE

enable/disable the marking up of comments

You can set these through the API (if you are including LexEv in an application), or from the command line using the following system properties:

com.andrewjwelch.lexev.inline-entities

com.andrewjwelch.lexev.cdata

com.andrewjwelch.doctype.cdataNamespace

com.andrewjwelch.lexev.doctype

com.andrewjwelch.lexev.comments

For example to set a system property from the command line you would use: -Dcom.andrewjwelch.lexev.comments=false

For support, suggestions and licensing, email lexev@andrewjwelch.com

Kernow 1.6.1

2008-07-18T14:58:00.000Z

Kernow 1.6.1 (beta) is now availble both as a download and via web start.

Notable things in this release:

- Line numbers on the editor panes in the sandboxes (thanks to a new version of Bounce). You might not think so, but getting line numbers down the side of the editor pane is really involved. It's like block indenting (pressing tab or shift-tab when a block of text is selected) in that it's very low level and requires a lot of coding. Why it's not an intergral part of the editor pane I don't know...

- Improved the syntax-checking-as-you-type and highlighting, and added the ability to disable it.

- The output area is now also a JEditorPane using Bounce so it supports tag highlighting. This might slow things down because now it's an HTML document where every addition is inserted at the end of the document, instead of just appending to a JTextArea... if this proves to be A Bad Thing I'll revert it back to a plain old text area with plain text.

- You can now select which tabs are visible (in options -> tabs) so if you never use certain tabs (like Batch or Schematron) you can remove them.

- If you have Saxon SA you can use XML Schema 1.1 (options -> validation)

- Improved the parameters dialog to make it less fiddly to enter params

- Slight graphical tweaks and likely other things that I've forgotten...

The Nimbus Look and Feel

2008-07-17T11:11:00.001Z

This is "Nimbus" - the new look and feel that comes with Java 6 Update 10. This is a cross platform l&f which means it should look the same on all platforms. Kernow currently uses the "platform default" look and feel so it should look like a native app on the platform it's run on, but it's hard to make sure it looks right - often what looks ok on Windows will have obscured buttons on Linux... something I should've fixed but never did.

Anyway, what do you think?

Validating co-constrains in XML Schema 1.1 using xs:alternative

2008-07-11T15:37:00.001Z

Rather than mess around with loads of assertions to check your co-constraints, XML Schema 1.1 introduces the xs:alternative instruction which allows you to change the type used to validate the element based on some condition. Instead of defining one type and then adding assertions to check the variations, just define one type per variation, then assign that type based on the condition.

To do this you first have to define a default type, then define types for each variation by restricting that type. To choose between them, use xs:alternative as a child of xs:element. Here's an example of a co-constraint - this and that are allowed based on the value of the type attribute of node - and how to validate it:

<root>
  <node type="A">
    <this/> 
  </node>
  <node type="B">
    <that/> 
  </node>
</root>

Here's the schema:

<xs:schema 
  xmlns:xs="http://www.w3.org/2001/XMLSchema" 
  elementFormDefault="qualified">

  <xs:element name="root" type="root"/>
  <xs:element name="node" type="node">
    <xs:alternative type="node-type-A" test="@type = 'A'"/>  
    <xs:alternative type="node-type-B" test="@type = 'B'"/>  
  </xs:element>
  <xs:element name="this"/>
  <xs:element name="that"/>
  
  <xs:complexType name="root">
    <xs:sequence>
      <xs:element ref="node" maxOccurs="unbounded"/>
    </xs:sequence>
  </xs:complexType>
  
  <-- Base type -->
  <xs:complexType name="node">
    <xs:sequence>
      <xs:any/>  
    </xs:sequence>
    <xs:attribute name="type" type="allowed-node-types"/>
  </xs:complexType>

  <xs:simpleType name="allowed-node-types">
    <xs:restriction base="xs:string">
      <xs:enumeration value="A"/>
      <xs:enumeration value="B"/>
    </xs:restriction>
  </xs:simpleType>      
  
  <-- Type A -->
  <xs:complexType name="node-type-A">
    <xs:complexContent>
      <xs:restriction base="node">
        <xs:sequence>
          <xs:element ref="this"/>  
        </xs:sequence>  
      </xs:restriction>  
    </xs:complexContent>
  </xs:complexType>
  
  <-- Type B -->
  <xs:complexType name="node-type-B">
    <xs:complexContent>
      <xs:restriction base="node">
        <xs:sequence>
          <xs:element ref="that"/>  
        </xs:sequence>  
      </xs:restriction>  
    </xs:complexContent>
  </xs:complexType>  
</xs:schema>

I really like this... schema 1.1 will be a joy to use.

XML Schema co-occurrence constraint workaround

2008-06-16T14:45:00.001Z

Here's a potential workaround for the co-constraint problem in XML Schema.

Given some XML:


<elem type="typeA">
  <typeA/>
</elem>

<elem type="typeB">
  <typeB/>
</elem>

...the problem is you can't constrain the contents of <elem> based on the value of the type attribute.

You can do it though, if you add an xsi:type attribute to it to explicitly set its type:


<elem type="typeA" xsi:type="elem_typeA">
  <typeA/>
</elem>

<elem type="typeB" xsi:type="elem_typeB">
  <typeB/>
</elem>

with suitable type definitions in the schema:


<xs:complexType name="elem_typeA">
  <xs:sequence>
    <xs:element ref="typeA"/>
    ...

<xs:complexType name="elem_typeB">
  <xs:sequence>
    <xs:element ref="typeB"/>
    ...

...and when the XML is validated the relevant definition will be used.

This technique is far from ideal as it involves modifying the source, but only in a way which doesn't break it for anyone else. Given the various options for validating co-constraints, this could well be the most straightforward way (at least until 1.1 comes along).

The Scrabble Reference

2008-04-25T13:48:00.001Z

The Scrabble Reference is an ebook I've created which allows Scrabble players to easily check if words are legal, to suggest longer words or sub-anagrams given a word and to show what words can be made given some letters (up to 15 letters).

There are two versions, TWL and SOWPODS (TWL is used in the USA, Canada, Thailand and Israel and SOWPODS in the rest of the world)

The ebook is in the Mobipocket format which deals with running the ebooks on all devices - PDAs, mobile phones, Blackberries etc so you just need to transform the input to suitable Mobipocket markup, compile the ebook and their client does the rest.

I must admit to not being interested in Scrabble, but of course I am interested in XSLT, and given the list of words allowed in Scrabble I thought I should turn them into a product - one that you can run on your phone seems perfect.

Generating the ebook was very straightforward - list of strings in, markup out... XSLT 2.0 is ideal for the task.

Relative paths and the document() function

2008-04-25T11:18:00.000Z

A nice gotcha cropped up today on xsl-list...

Relative paths passed to the document() function are resolved against either the XML or the stylesheet depending on what is passed in: a node from the XML will mean the path is resolved against the XML, a string will mean it's resolved against the stylesheet.

The gotcha is this - if you modify this:

document(@path)

to this:

<xsl:variable name="path" select="@path" as="xs:string"/>
...
document($path)

and @path contains a relative path, then you could get a document not found error, or worse if your XML and XSLT are in the same directory, you won't notice...

XML Schema - element with text and attributes

2008-02-29T16:23:00.001Z

For some reason I always forget how to define an element that contains only text but also has attributes. Perhaps it's because it's so verbose, or so non-intuitive for something so simple, who knows. Either way it's something that needs to be committed to memory...

So the element:


<foo bar="bar" baz="baz"/>

is described using:


<xs:complexType name="foo">
    <xs:simpleContent>
        <xs:extension base="xs:string">
            <xs:attribute name="bar" type="xs:string"/>
            <xs:attribute name="baz" type="xs:string"/>
        </xs:extension>
    </xs:simpleContent>                
</xs:complexType>

nice!

schema-aware.com

2008-02-27T16:10:00.000Z

I've created a new website schema-aware.com which is inteded to contain lots of examples of schema-aware XSLT and XQuery. I've started it off with half a dozen or so and hope to add more as time goes on.

I also intend to add a few articles about schema-aware transforms - how the run them from the command line, from Java, the various flags involved, how to write schemas to allow you to use the types in your XSLT etc... My intentions are good, we'll have to see how much I actually do.

Kernow 1.6 beta

2008-01-31T15:01:00.000Z

I've uploaded a new version of Kernow (1.6) which contains the rather nice "XSLT Sandbox" tab. This tab has the XML pane on the left, the XSLT pane on the right and a transform button... and that's it. It's intended for anyone who wants to quickly try something out without the hassle of files, the command line or starting up a proper IDE. It does error checking as you type and highlights any problems.

It's available as the usual download from Sourceforge, or through Java Web Start. If you already run the JWS version it should automatically update itself (any problems just re-install it). I've finally figured out the temperamental errors with the JWS version - it turns out the ant jars included with Kernow were already signed by a previous version and so weren't being signed again, but because they were marked as "lazy" in the jnlp the JWS version would start anyway. (You can tell if a jar has been signed by looking for *.SF and *.DSA in the META-INF directory.)

The other improvement I'm pleased to have sorted out is that kernow.config (where all of the settings and combobox history are saved) is now stored in a directory called .kernow in your user.home (which is one up from My Documents in XP). Previously it would've been stored on the deskop for the JWS version which is really annoying - sorry about that. As usual it was a 10 minute job, but just took a while to get around to.

I've also separated out the SOAP and eXists extension functions into a separate package, so there's no longer the need for the largish eXist.jar, xmldb.jar and log4j.jar jars to be part of the download.

I'll release a non-beta version in a few weeks if no bugs are reported, and I've got around to updating all of the documentation.

Parsing XML into Java 5 Enums

2008-01-31T14:52:00.000Z

Often when parsing XML into pojos I just resort to writing my own SAX based parser. It can be long winded but I think gives you the greatest flexibility and control over how you get from the XML to objects you can process.

One example is with Java 5's Enums, which are great. Given the kind of XML fragment where currencies are represented using internal codes:

<currency refid="001"/> <!-- 001 is Sterling -->
<currency refid="002"/> <!-- 002 is Euros -->
<currency refid="003"/> <!-- 003 is United States Dollars -->

You can represent each currency element with an Enum, which contains extra fields for the additional information:

public enum Currency {

    GBP ("001", "GBP", "Sterling"),
    USD ("002", "EUR", "Euros"),
    USD ("003", "USD", "United States Dollar");    

    private final String refId;
    private final String code;
    private final String desc;

    Currency(String refId, String code, String desc) {
        this.refId = refId;
        this.code = code;
        this.desc = desc;
    }

    public String refId() {
        return refId;
    }

    public String code() {
        return code;
    }

    public String desc() {
        return desc;
    }

    // Returns the enum based on it's property rather than its name
    // (This loop could possibly be replaced with a static map, but be aware
    //  that static member variables are initialized *after* the enum and therefore
    //  aren't available to the constructor, so you'd need a static block.  
    public static Currency getTypeByRefId(String refId) {
        for (Currency type : Currency.values()) {
            if (type.refId().equals(refId)) {
                return type;
            }
        }

        throw new IllegalArgumentException("Don't have enum for: " + refId);
    }    
}

Notice how each enum calls its own contructor with the 3 parameters - the refId, the code, and the description.

You parse the XML into the enum by calling Currency.getTypeByRefId(String refId) passing in the @refid from the XML. The benefit of using the Enum is that you can then do things like:

if (currency.equals(Currency.GBP))

which is nice and clear, while at the same time being able to call currency.refId() and currency.desc() to get to the other values.

The drawback is that because static member variables are initialized after the enum, you can't create a HashMap and fill it for a faster lookup later (unless you use a static block). Instead you have to loop through all known values() for the enum given a refId. Although it feels wrong to loop, the worst case is only the size the of enum so I don't think it's too bad.

Portability of a stylesheet across schema-aware and non-schema-aware processors

2008-01-22T14:06:00.000Z

I came across this today, which I thought was really cool and worth a post. It basically allows you to code a transform that is only schema-aware if a schema-aware processor is running it, otherwise it's just a standard transform.

In this case I want to do input and output validation, so first I sort out the schemas:

<xsl:import-schema schema-location="input.xsd"
    namespace="http://www.foo.com"
    use-when="system-property('xsl:is-schema-aware')='yes'"/>

<xsl:import-schema schema-location="output.xsd"
    use-when="system-property('xsl:is-schema-aware')='yes'"/>

Note the use-when...

Next define two root matching templates, one for schema-aware, one for basic:

<xsl:template match="/"
    use-when="system-property('xsl:is-schema-aware')='yes'"
    priority="2">

    <xsl:variable name="input" as="document-node()">
        <xsl:document validation="strict">
            <xsl:copy-of select="/"/>
        </xsl:document>
    </xsl:variable>

    <xsl:result-document validation="strict">
        <xsl:apply-templates select="$input/the-root-elem"/>
    </xsl:result-document>

</xsl:template>

<xsl:template match="/">
    <xsl:apply-templates select="the-root-elem"/>
</xsl:template>

<xsl:template match="the-root-elem">
    ...
</xsl:template>

The root matching template for schema-aware processing uses xsl:document to validate the input, and xsl:result-document to validate the output. Validation can also be controlled from outside the transform, but this way forces it on.

I think this is great :)

The identity transform for XSLT 2.0

2008-01-22T13:47:00.001Z

I was looking at the standard identity transform the other day and realised that for nodes other than elements, the call to apply-templates is redundant.

<xsl:template match="@*|node()">
  <xsl:copy>
    <xsl:apply-templates select="@*|node()"/>
  </xsl:copy>
</xsl:template>

Also, although it might be intuitive to think that attributes have separate nodes for their name and value, they are in fact a single node that's copied in it's entirety by xsl:copy.

I raised this on xsl-list and suggested seperating out the attribute into a template of its own with just xsl:copy for its body:

<xsl:template match="node()">
  <xsl:copy>
    <xsl:apply-templates select="@*|node()"/>
  </xsl:copy>
</xsl:template>

<xsl:template match="@*">
  <xsl:copy/>
</xsl:template>

Mike Kay suggested a more logical version would be:

<xsl:template match="element()">
  <xsl:copy>
    <xsl:apply-templates select="@*,node()"/>
   </xsl:copy>
</xsl:template>

<xsl:template match="attribute()|text()|comment()|processing-instruction()">
  <xsl:copy/>
</xsl:template>

This turned out to be ideal for three reasons:

- the comma between @* and node() will mean the selected nodes will be processed in that order, removing the sorting and deduplication that takes place with union |
- apply-templates is only called when it will have an effect
- it's clearer that attributes are leaf nodes

So there it is... the identity transform for XSLT 2.0

Kernow 1.5.2

2007-09-28T13:04:00.000Z

I've just uploaded the non-beta version of Kernow 1.5.2.

This version contains:

- French and German translations
- XQuery syntax highlighting and checking as-you-type
- Improved cancelling of Single File and Standalone tasks
- icon and splash screen
- An exe to launch it (for windows users)
- context menus
- comboboxes remember their selected index
- individual combobox entries can be removed by deleting the entry
- other small fixes

Connecting to Oracle from XSLT

2007-09-12T12:01:00.000Z

Today I generated a report by connecting directly to an Oracle database from XSLT, and thought I'd share the basic stylesheet. I used Saxon's SQL extension, which is available when saxon8-sql.jar is on the classpath. As I was connecting to Oracle, I also needed to put ojdcb14.jar on the classpath.

Here's the stylesheet in it's most basic form, formatted for display in this blog.

The important things to note here are:

- The sql prefix is bound to "/net.sf.saxon.sql.SQLElementFactory"
- The driver is "oracle.jdbc.driver.OracleDriver"
- The connection string format is "jdbc:oracle:thin:@1.2.3.4:1234:sid" (note the colon between thin and @ - I missed that first time round) where the IP, port and sid are placeholders for the real values
- remember that saxon8-sql.jar and ojdbc14.jar needed to be on the classpath


<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:sql="/net.sf.saxon.sql.SQLElementFactory"
 exclude-result-prefixes="xs"
 extension-element-prefixes="sql">
 
<xsl:output indent="yes"/>

<xsl:param name="driver" 
  select="'oracle.jdbc.driver.OracleDriver'" 
  as="xs:string"/>

<xsl:param name="database" 
  select="'jdbc:oracle:thin:@123.123.123.123:1234:sid'" 
  as="xs:string"/>

<xsl:param name="user" select="'un'" as="xs:string"/>
<xsl:param name="password" select="'pw'" as="xs:string"/>

<xsl:variable name="connection"
  as="java:java.sql.Connection" 
  xmlns:java="http://saxon.sf.net/java-type">
 
  <sql:connect driver="{$driver}" database="{$database}" 
    user="{$user}" password="{$password}"/>
</xsl:variable>
 
<xsl:template match="/" name="main">
  <root>
    <sql:query connection="$connection" 
      table="some_table" 
      column="*"
      row-tag="row" 
      column-tag="col"/>
  </root>
</xsl:template>

</xsl:stylesheet>

The result of this transform outputs XML in the form:


<root>
  <row>
    <col>data1</col>
    <col>data2</col>
    <col>data3</col>
    <col>data4</col>
  </row>
  ....
</root>

where <root> is the wrapper element, and <row> and <col> are the element names specified in the <sql:query> element.

And that's it - connecting to an Oracle database from within XSLT.

Kernow 1.5.2 beta b2 available

2007-09-03T15:59:00.000Z

I've just uploaded a new version of Kernow. This one was pretty much already available via Java Web Start, this makes it available via the normal download route.

New features/fixes:

- Added syntax highlighting and checking as-you-type to the XQuery Sandbox tab. Syntax highlighting's provided using Bounce's XMLEditorKit - I'm hoping to use Netbeans' nbEditorKit in a future version which will add line numbers, code completion etc. I've put together the checking-as-you-type and error highlighting using Saxon's error reporting. This is really cool, so I'm planning on doing an equivalent "XSLT Sandbox" soon... perhaps using Netbeans RCP. Not sure yet.

- Added an icon and splashsceen. These came about because JWS and the exe benefit from them. Are they any good? I'm not really a graphics person...

- Kernow.jar is now a proper executable jar, so you can double click it to run Kernow (if you're on a mac for example)

- It's all compiled using Java 1.5, again for mac users where 1.6 isn't supported yet.

It's available here: Kernow

Kernow now available via Java Web Start

2007-08-30T15:16:00.000Z

I've been playing around with making Kernow available through Java Web Start. This should be the ideal way to run Kernow as it places a shortcut on your desktop (and in your start menu in Windows) and auto-updates whenever a new version is available.

Reading around it seems Java Web Start has had mixed reviews. Personally I really like it, perhaps because I'm using Java 1.6 and Netbeans 6 M10 which makes it all pretty straightforward (auto jar-signing is really helpful in M10).

Give it a go, let me know what you think: Kernow - Java Web Start

Using XQuery and the slash operator to quickly try out XPaths

2007-08-17T14:18:00.000Z

This is the coolest thing I've seen in a while...

In XQuery you can constuct a node just by writing it, eg:


<node>I'm a node</node>

and then you can use slash operator to apply an XPath to that node:


<node>I'm a node</node>/data(.)

returns "I'm a node"

The XML doesn't have to be limited to a single node - you can do:


<root>
  <node>foo</node>
  <node>bar</node>
</root>/node/data(.)

...to get "foo bar".

Or:


<root>
  <node>foo</node>
  <node>bar</node>
</root>/node[1]

to get:


<node>foo</node>

Using this technique in combination with Kernow's XQuery Sandbox makes it straightforward to paste in some XML and start trying out some XPaths.

When a = b and a != b both return true...

2007-08-16T14:59:00.000Z

In XPath = and != are set operators. That is, they return true if any item on the left hand side returns true when compared with any item on the right hand side. Or in other words:

some x in $seqA, y in $seqB satisfies x op y

...where "op" is = or != (or > or < etc)

To demonstrate this take the two sets ('a', 'b') and ('b', 'c'):

$seqA = $seqB returns true because both sets contains 'b'

$seqA != $seqB returns true because setA contains 'a' which is not equal to 'c' in setB

This catches me out a lot, even though I've been caught out before several times. I really have to think hard about what it is exactly that I'm comparing, and still end up getting it wrong.

A simple rules to follow is "never use != where both sides are sequences of more than one item". 99.9% of the time you won't need to, as much as it feels like the right thing to do.

Below are some of the most common operations on sequences, put together for a reference.

The two sequences are ('a', 'b') and ('b', 'c'), which can be defined in XSLT as:

<xsl:variable name="seqA" select="('a', 'b')" as="xs:string+"/>
<xsl:variable name="seqB" select="('b', 'c')" as="xs:string+"/>

or in XQuery as:

let $seqA := ('a', 'b')
let $seqB := ('b', 'c')

Select all items in both sequences

($seqA, $seqB)

Result: a b b c

Select all items in both sequences, eliminating duplicates

distinct-values(($seqA, $seqB))

Result: a b c

Select all items that occur in $seq1 but not $seq2

$seqA[not(. = $seqB)]

Result: a

Select all items that occur in both sequences

$seqA[. = $seqB]

Result: b

Select all items that do not occur in both sequences

($seqA[not(. = $seqB)],$seqB[not(. = $seqA)])

or

($seqA, $seqB)[not(. = $seqA[. = $seqB])]

Result: a c

Determine if both sequences are identical

deep-equal($seqA, $seqB)

Result: false

Test if all items in the sequence are different

count(distinct-values($seqA)) eq count($seqA)

Result: true

The Worlds Fastest Sudoku Solution in XSLT 2.0 for the Worlds Hardest Sudoku - Al Escargot

2007-08-15T09:24:00.000Z

I get a lot of traffic to this blog because of my Sudoku solver. Google analytics tells me most of it lands on the original version that I wrote, and not the optimised version that's now the worlds fastest XSLT 2.0 solution - an issue which this post should hopefully rectify.

The puzzle on the right is apparently the worlds hardest Sudoku puzzle. If I run my solver "Sudoku.xslt" using Kernow's performance testing feature I get this result:

Ran 5 times
Run 1: 328 ms
Run 2: 344 ms
Run 3: 328 ms
Run 4: 391 ms
Run 5: 328 ms
Ignoring first 2 times
Total Time (last 3 runs): 1 second 47 ms
Average Time (last 3 runs): 349 ms

So on my machine the average execution time is 349ms, which is pretty good considering the original version would take minutes for several puzzles. As far as I know this version will solve all puzzles in under a second on my machine (Core 2 duo E6600, 2gb).

How does it do it? This is taken from the web page where it's hosted:

It accepts the puzzle as 81 comma separated integers in the range 0 to 9, with zero representing empty. It works by continuously reducing the number of possible values for each cell, and only when the possible values can't be reduced any further it starts backtracking.

The first phase attempts to populate as many cells of the board based on the start values. For each empty cell it works out the possible values using the "Naked Single", "Hidden Single" and "Naked Tuples" techniques in that order (read here for more on the techniques). Cells where only one possible value exists are populated and then the second phase begins.

The second phase follows this process:

* Find all empty cells and get all the possible values for each cell (using Naked Single and Hidden Single techniques)
* Sort the cells by least possible values first
* Populate the cells with only one possible value
* If more there's more than one value, go through them one by one
* Repeat

This is how it solves the Al Esgargot: A slightly modified version of the solution gives this output with the $verbose parameter set to true. As you can see it's found that it can insert a 1 at position 66 using the static analysis of the puzzle (position 66 is middle-right of the bottom-left group). Next it's decided that there are two possible values 4 and 6 at index 12 (middle-right cell of top-left group), so it tries 4 and continues. With that 4 in place it's found that there's only one possible value at index 39, a 3, so it inserts that and continues. It will keep reducing the possible values based on the current state of the board, inserting the only possible values or trying each one when there are many, until either there are no possible values for an empty cell, or the puzzle is solved.

(the solution is shown below)

Populated single value cell at index 66 with 1
Trying 4 out of a possible 4 6 at index 12
Only one value 3 for index 39
Trying 5 out of a possible 5 7 at index 10
Trying 1 out of a possible 1 9 at index 13
Only one value 9 for index 15
Trying 6 out of a possible 6 7 at index 16
Only one value 7 for index 17
Trying 2 out of a possible 2 4 at index 7
Trying 6 out of a possible 6 8 at index 2
Only one value 8 for index 3
Only one value 2 for index 48
Only one value 6 for index 57
Only one value 5 for index 60
Only one value 9 for index 63
Only one value 5 for index 74
Only one value 1 for index 78
Only one value 3 for index 69
Only one value 5 for index 71
Only one value 6 for index 81
Only one value 4 for index 36
! Cannot go any further !
Trying 8 out of a possible 8 at index 2
Only one value 6 for index 3
Trying 4 out of a possible 4 5 at index 4
Only one value 3 for index 9
Only one value 3 for index 23
Only one value 4 for index 26
Only one value 3 for index 53
Only one value 5 for index 54
Only one value 4 for index 36
Only one value 6 for index 44
Only one value 8 for index 48
Only one value 2 for index 57
Only one value 8 for index 73
Only one value 9 for index 47
Only one value 7 for index 50
Only one value 6 for index 60
Only one value 9 for index 64
! Cannot go any further !
Trying 5 out of a possible 5 at index 4
Only one value 9 for index 47
Only one value 2 for index 67
Only one value 7 for index 49
Only one value 9 for index 64
Only one value 2 for index 80
Only one value 1 for index 32
Only one value 2 for index 48
Only one value 5 for index 50
Only one value 8 for index 58
Only one value 8 for index 73
! Cannot go any further !
Trying 4 out of a possible 4 at index 7
Only one value 3 for index 9
Only one value 4 for index 23
Only one value 3 for index 24
Only one value 2 for index 26
Only one value 3 for index 53
Only one value 5 for index 54
Only one value 8 for index 4
Trying 2 out of a possible 2 6 at index 2
Only one value 6 for index 3
Trying 7 out of a possible 7 8 at index 19
Only one value 8 for index 20
Only one value 7 for index 29
Only one value 9 for index 40
Only one value 7 for index 50
Only one value 6 for index 44
Only one value 2 for index 49
Only one value 2 for index 28
Only one value 8 for index 48
Only one value 2 for index 57
Only one value 5 for index 67
Only one value 7 for index 58
Only one value 8 for index 61
Only one value 3 for index 68
Only one value 2 for index 70
! Cannot go any further !
Trying 8 out of a possible 8 at index 19
Only one value 7 for index 20
Only one value 8 for index 29
Only one value 9 for index 47
Only one value 2 for index 48
Only one value 8 for index 57
Only one value 4 for index 37
Only one value 9 for index 40
Only one value 7 for index 49
! Cannot go any further !
Trying 6 out of a possible 6 at index 2
Only one value 2 for index 3
Only one value 6 for index 57
Trying 7 out of a possible 7 8 at index 19
Only one value 8 for index 20
Trying 2 out of a possible 2 4 at index 28
Only one value 7 for index 29
Only one value 9 for index 47
Only one value 2 for index 49
Only one value 9 for index 40
Only one value 6 for index 44
Only one value 7 for index 50
Only one value 9 for index 59
! Cannot go any further !
Trying 4 out of a possible 4 at index 28
Only one value 9 for index 37
Only one value 4 for index 44
Only one value 6 for index 42
Trying 2 out of a possible 2 7 at index 29
Only one value 7 for index 47
Only one value 2 for index 49
Only one value 7 for index 32
Only one value 9 for index 50
! Cannot go any further !
Trying 7 out of a possible 7 at index 29
Only one value 1 for index 32
Only one value 2 for index 33
Only one value 2 for index 47
Trying 7 out of a possible 7 9 at index 49
Only one value 9 for index 50
Only one value 6 for index 77
Only one value 1 for index 78
Only one value 5 for index 80
Only one value 5 for index 56
Only one value 8 for index 60
Only one value 2 for index 61
Only one value 8 for index 70
Only one value 6 for index 71
Only one value 9 for index 74
Only one value 2 for index 64
Only one value 4 for index 81
Only one value 4 for index 58
Only one value 9 for index 67
Only one value 8 for index 73
Only one value 2 for index 76
Done!

1, 6, 2,   8, 5, 7,   4, 9, 3,
5, 3, 4,   1, 2, 9,   6, 7, 8,
7, 8, 9,   6, 4, 3,   5, 2, 1,

4, 7, 5,   3, 1, 2,   9, 8, 6,
9, 1, 3,   5, 8, 6,   7, 4, 2,
6, 2, 8,   7, 9, 4,   1, 3, 5,

3, 5, 6,   4, 7, 8,   2, 1, 9,
2, 4, 1,   9, 3, 5,   8, 6, 7,
8, 9, 7,   2, 6, 1,   3, 5, 4,

If you have a solution that can statically detect more cells to fill using different techniques than I have, or has a better strategy than simply backtracking when there's more than one value, then I'd be interested to know it works.

I'm pretty sure the XSLT is as good as it can be, but if you think it can be improved in any way then let me know.

Combining XSLT 2.0's Grouping with eXist

2007-07-23T10:23:00.000Z

I work a lot with large XML datasets that are arranged as thousands of 1 - 10mb XML files. I spend most of my days writing transforms and transformation pipelines to process these files, which is where Kernow came from. I also like messing around with eXist (I'm yet to use it commercially, but I hope to one day) and enjoying the speed a native XML database gives you.

Requirements that regularly come up are to generate indexes and reports for the dataset. This is nice and simple using XSLT 2.0's grouping but require the whole dataset to be in memory, unless you use saxon:discard-document(). It can also be quite slow, if only because you have to read GB's from disk and parse the whole of each and every XML input file to just get the snippet that you're interested in (such as the title, or say all of the elements).

Conversely, XQuery doesn't suffer from the dataset size but lacks XSLT 2.0's grouping features. It's perfectly possible (although a bit involved - you could say "a bit XSLT 1.0") to recreate the grouping in XQuery, but it's just so much nicer in XSLT 2.0. So to get the best of both, you can use eXist's fanstastic REST style interface to select the parts of the XML you're interested in, and then use XSLT 2.0's for-each-group to arrange the results.

In the example stylesheet below I create an index by getting the <title> for each XML document, and then grouping the titles by their first letter, then sorting by title itself. I use eXist to get the <title> element, then XSLT 2.0 to do the sorting and grouping.

I have an instance of eXist running on my local machine and fully populated with the XML dataset. The function fn:eXist() takes the collection I'm interested in and the XQuery to execute against that collection, constructs the correct URI for the REST interface and calls doc() with that URI. The result is a proprietary XML format containing each tuple that I then group using xsl:for-each-group. It's worth noting the -1 value for the _howmany parameter on the query - without this it defaults to 10.

<xsl:stylesheet
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:fn="fn"
xmlns:exist="http://exist.sourceforge.net/NS/exist"
version="2.0">

<xsl:output indent="yes" />

<xsl:param name="db-uri" select="'http://localhost:8080/exist/rest'" />

<xsl:function name="fn:eXist">
    <xsl:param name="collection" />
    <xsl:param name="query" />
    <xsl:sequence select="doc(concat($db-uri, $collection, '?_query=', $query, '&_start=1&_howmany=-1'))/exist:result/node()" />
</xsl:function>

<xsl:template match="/">
    <div>
        <xsl:for-each-group select="fn:eXist('/db/mycomp/myproject', '/doc/head/title')" group-by="substring(., 1, 1)">
            <xsl:sort select="." />
            <div>
                <div><xsl:value-of select="current-grouping-key()" /></div>
                <xsl:for-each select="current-group()">
                    <xsl:sort select="." />
                    <div><xsl:value-of select="." /></div>
                </xsl:for-each>
            </div>
        </xsl:for-each-group>
    </div>
</xsl:template>

</xsl:stylesheet>

It's as simple as that... what would normally take minutes takes seconds (once the database setup is done). If you haven't used eXist yet I highly recommend it.

This article is repeated here

CSV to XML transform updated

2007-07-11T12:42:00.000Z

I've posted a new version of the CSV to XML transform. This version handles nested quotes correctly - the previous version would generate extra tokens either side of the quoted value.

Kernow 1.5.0.9 [beta] available

2007-06-29T09:26:00.000Z

I've made a new beta version of Kernow available:

XSLT directory transforms are now multi-threaded, with the size of the thread pool configurable in the options. For systems with multi-core processors and enough available memory this can really improve directory transform time.
Single File / Standalone transforms now have a "Performance Testing" feature where the transforms are run repeatedly and the average time displayed.
The panels can now be resized for the XQuery Sandbox tab. The fixed size XQuery Sandbox made it pretty useless before - at least now you can see more than four lines!
Other minor bug fixes

There's loads still to do, but I'm trying to stick to the "release early, release often" policy.

UK Postcode Googlemaps mashup

2007-06-18T14:19:00.000Z

Everyone else has done a mashup so I thought I should do one too. My mashup combines GoogleMaps with StreetMap.co.uk's GridConvert to get the nearest postcode for a given longitude and latitude. I had to use some server side PHP to get around cross domain scripting issues and to scrape the postcode from result HTML, but other than that it's all through the GoogleMaps API.

Sukoku Solver - much improved.

2007-06-15T10:50:00.000Z

I've just uploaded the latest version of my Sudoku Solver.

I wrote the initial version of this in March 2006, and have since been in competition with Dimitre Novatchev to have the fastest solution. Dimitre's held that title for while, but with this version I think I may have won it back.

The additions here are Naked Tuple discovery in the first phase, and then repeatedly re-ordering the cells by least-number-of-possible-values as each cell is populated in the second phase. Sounds obvious but its something I missed first time around.

On my machine this latest version solves the vast majority of puzzles (including AI Escargot) in under a second, with the occasional one taking just under two seconds. The previous version would take up to a minute on some puzzles, so I'm pleased with improvement.

Hopefully Dimitre will do some comparisons using his latest version, and then tell me the good news :)

My new homepage

2007-06-15T10:46:00.000Z

I'd like to draw attention to my new homepage: andrewjwelch.com. I've created this as a better place to store the code samples that were posted in this blog, and to link to my open source projects.

I'll try to keep news and opinions to this blog, and code samples on the homepage.

A long drawn out redundancy...

2007-06-08T13:21:00.000Z

I've been informed that I will be made redundant... in October! That's a long 4 1/2 months away. In the mean time I'm meant to be performing maintenance and handover tasks (4 months of handover ?!?!) while the redundancy + retention carrot is tentatively dangled to keep us here until then...

So if you can see that far ahead and need a Java/XML/XSLT bod to fill a high paying contract, let me know :)

Er, the real "hardest Sudoku"

2007-03-30T10:58:00.000Z

Following the comment from Malcom below, I've run my Sudoku solver against the real "AL Escargot"...

Using Saxon 8.9.0.3b from the command line with the -3 option (to discount java startup time) the average time across three runs is 2213ms... which isn't bad at all.

This is when I just solve the puzzle starting at the top-left - if I turn on the ordering feature where empty cells are processing by least number of possibilities first, then the time dramatically increases to ~58 seconds, which shows why Sudoku is NP-complete.

If you're interested the solution it produced is:


1, 6, 2,   8, 5, 7,   4, 9, 3
5, 3, 4,   1, 2, 9,   6, 7, 8
7, 8, 9,   6, 4, 3,   5, 2, 1

4, 7, 5,   3, 1, 2,   9, 8, 6
9, 1, 3,   5, 8, 6,   7, 4, 2
6, 2, 8,   7, 9, 4,   1, 3, 5

3, 5, 6,   4, 7, 8,   2, 1, 9,
2, 4, 1,   9, 3, 5,   8, 6, 7,
8, 9, 7,   2, 6, 1,   3, 5, 4,

The Worlds Hardest Sudoku

2007-03-29T15:17:00.000Z

A mathematician claims to have penned the world's hardest Sudoku puzzle.

Running it through my Sudoku Solver it took ~24 seconds on my work machine (most puzzles are sub 1 second on the same machine) so I would think it must be reasonably hard.

A CSV to XML converter in XSLT 2.0

2007-02-23T10:33:00.000Z

* Note: This transform has been updated http://andrewjwelch.com/code/xslt/csv/csv-to-xml_v2.html

I wrote a rudimentary csv to XML converter a while back which broke when the csv contained quoted values, eg foo, "foo, bar", bar Dealing with these quotes is surprisingly hard, especially when you take into account quotes are escaped by doubling them.

I raised it on xsl-list, and Abel Braaksma came up with a genious solution - the technique is to use both sides of analyze-string - read his post for the best explanation.

To keep the transform generic I've used an attribute instead of an element for the column names to cope with names that aren't valid QNames (for example ones that contain a space) - for my own use would add a function to convert names to valid QNames and then change <elem name="{...}"> to <xsl:element name="{fn:getQName(...)}"> as it generates nicer XML. I've also modified the non-matching-substring side of analyze-string to only return tokens that contain values.

So this sample input:

Col 1, Col 2, Col 3
foo, "foo,bar", "foo:""bar"""

...creates this output:


<root>
<row>
  <elem name="Col 1">foo</elem>
  <elem name="Col 2">foo,bar</elem>
  <elem name="Col 3">foo:"bar"</elem>
</row>
</root>

Here's the finished transform:


<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:fn="fn"
exclude-result-prefixes="xs fn">

<xsl:output indent="yes" encoding="US-ASCII"/>

<xsl:param name="pathToCSV" select="'file:///c:/csv.csv'"/>

<xsl:function name="fn:getTokens" as="xs:string+">
<xsl:param name="str" as="xs:string"/>
<xsl:analyze-string regex='("[^"]*")+' select="$str">
   <xsl:matching-substring>
       <xsl:sequence select='replace(., "^""|""$|("")""", "$1")'/>
   </xsl:matching-substring>
   <xsl:non-matching-substring>
       <xsl:for-each select="tokenize(., '\s*,\s*')">
           <xsl:sequence select="."/>
       </xsl:for-each>
   </xsl:non-matching-substring>
</xsl:analyze-string>
</xsl:function>

<xsl:template match="/" name="main">
<xsl:choose>
    <xsl:when test="unparsed-text-available($pathToCSV)">
        <xsl:variable name="csv" select="unparsed-text($pathToCSV)"/>
        <xsl:variable name="lines" select="tokenize($csv, '&#xa;')" as="xs:string+"/>
        <xsl:variable name="elemNames" select="fn:getTokens($lines[1])" as="xs:string+"/>
        <root>
            <xsl:for-each select="$lines[position() > 1]">
                <row>
                    <xsl:variable name="lineItems" select="fn:getTokens(.)" as="xs:string+"/>

                    <xsl:for-each select="$elemNames">
                        <xsl:variable name="pos" select="position()"/>
                        <elem name="{.}">
                            <xsl:value-of select="$lineItems[$pos]"/>
                        </elem>
                    </xsl:for-each>
                </row>
            </xsl:for-each>
        </root>
    </xsl:when>
    <xsl:otherwise>
        <xsl:text>Cannot locate : </xsl:text>
        <xsl:value-of select="$pathToCSV"/>
    </xsl:otherwise>
</xsl:choose>
</xsl:template>

</xsl:stylesheet>

A Soap Extension Function

2007-02-05T13:48:00.000Z

Recently I had to write a client to retrieve XML from a web service that required authentication. All this meant was that the credentials needed to be in the soap header, eg:

<soapenv:Envelope>
<soapenv:Header>
<c:AuthHeader>
<c:Username>foo</c:Username>
<c:Password>bar</c:Password>
</c:AuthHeader>
</soapenv:Header>
<soapenv:Body>
...

Anyone that's coded any Java web service clients will know how hard it is to get the methods generated for you to add this soap header to your calls... its a nightmare. It varies between generation tool and the specification level you're coding to. What makes it worse is the whole reason you go through this pain is to send XML down the wire and get XML back. It would be much nicer if you could just make the call in XSLT....

I've written the following extension function to do just that. It accepts a soap request and an endpoint, makes the request and returns the soap response. It leaves the "complexity" of creating the request and processing to response to the XSLT, where it's pretty straightforward. Here's the java:

package net.sf.kernow.soapextension;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.StringWriter;
import java.io.UnsupportedEncodingException;
import java.net.HttpURLConnection;
import java.net.MalformedURLException;
import java.net.ProtocolException;
import java.net.URL;
import java.net.URLConnection;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerConfigurationException;
import javax.xml.transform.TransformerException;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.stream.StreamResult;
import net.sf.saxon.om.NodeInfo;

/**
* Enables the calling of SOAP based web services from XSLT.
* @author Andrew Welch
*/
public class SOAPExtension {

public static String soapRequest(NodeInfo requestXML, String endpoint) {
 String result = makeCall(transformToString(requestXML), endpoint);
 return result;
}

public static String soapRequest(String requestXML, String endpoint) {
 String result = makeCall(requestXML, endpoint);
 return result;
}

private static String transformToString(NodeInfo sourceXML) {

 StringWriter sw = new StringWriter();

 try {
     TransformerFactory tFactory = new net.sf.saxon.TransformerFactoryImpl();
     Transformer transformer = tFactory.newTransformer();
     transformer.transform(sourceXML, new StreamResult(sw));
 } catch (TransformerConfigurationException ex) {
     ex.printStackTrace();
 } catch (TransformerException ex) {
     ex.printStackTrace();
 }

 return sw.toString();
}

private static String makeCall(String requestXML, String endpoint) {
 
 String SOAPUrl = endpoint;
 StringBuffer responseBuf = new StringBuffer();

 try {    
     // Create the connection to the endpoint
     URL url = new URL(SOAPUrl);
     URLConnection connection = url.openConnection();
     HttpURLConnection httpConn = (HttpURLConnection) connection;
                  
     byte[] b = requestXML.getBytes("UTF-8");

     // Set the appropriate HTTP parameters.
     httpConn.setRequestProperty( "Content-Length", String.valueOf(b.length));
     httpConn.setRequestProperty("Content-Type","text/xml; charset=utf-8");

     httpConn.setRequestMethod("POST");
     httpConn.setDoOutput(true);
     httpConn.setDoInput(true);

     // Send the the request
     OutputStream out = httpConn.getOutputStream();
     out.write(b);
     out.close();

     // Read the response and write it to the response buffer.    
     InputStreamReader isr = new InputStreamReader(httpConn.getInputStream());
     BufferedReader in = new BufferedReader(isr);

     String line;
     do {
         line = in.readLine();
         if (line != null) {
             responseBuf.append(line);
         }
     } while (line != null);

     in.close();

 } catch (ProtocolException ex) {
     ex.printStackTrace();
 } catch (MalformedURLException ex) {
     ex.printStackTrace();
 } catch (UnsupportedEncodingException ex) {
     ex.printStackTrace();
 } catch (IOException ex) {
     ex.printStackTrace();
 }

 return responseBuf.toString();
}
}

I've put the extension function in the "net.sf.kernow.soapextension" package and called it SOAPExtension (it will be in the 1.5 version of Kernow when I eventually release it). Now the XSLT to make and process the requests:

<xsl:stylesheet version="2.0"
xmlns:soap="net.sf.kernow.soapextension.SOAPExtension"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:saxon="http://saxon.sf.net/"
xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
exclude-result-prefixes="xs">

<xsl:param name="endpoint" select="'http://somewebservice'"/>

<xsl:variable name="request">
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:ws="http://somewebservice/">
<soapenv:Body>
<ws:getSomething>
  <urn>name123</urn>
</ws:getSomething>
</soapenv:Body>
</soapenv:Envelope>
</xsl:variable>

<xsl:template match="/" name="main">
<xsl:apply-templates select="saxon:parse(soap:soapRequest($request, $endpoint))" mode="process-SOAP-message"/>
</xsl:template>

<xsl:template match="/" mode="process-SOAP-message">
<xsl:apply-templates select="saxon:parse(soapenv:Envelope/soapenv:Body/*/return/node())" mode="process-response-payload"/>
</xsl:template>

<xsl:template match="/" mode="process-response-payload">
<xsl:apply-templates/>
</xsl:template>


</xsl:stylesheet>

There are a couple of thing to notice - firstly you call soapRequest() with the message as a document node, and the endpoint as a string. The extension will also accept the message as a string, but that would just request the extra step of saxon:serialize($request).

Secondly you need to use saxon:parse to parse the response string into XML. Applying templates to saxon:parse() will search for the root matching template, so to avoid endless loops different modes are used to separate the various root matching templates.

The template in the mode "process-SOAP-message" deals with processing the soap response, so the root element here would be , so in order to get to the actual payload (and to treat it as a document in its own right) I use:

saxon:parse(soapenv:Envelope/soapenv:Body/*/return/node())

...and a third root matching template in the mode "process-response-payload" (the actual path may vary for your payload). In this template you deal with actual response, so you can apply-templates to it, write it to disk etc

And that's it, it really is as simple as that. The S in SOAP can mean Simple :)

Testing XSLT - CheckXML

2007-02-04T13:11:00.000Z

It's well known that XSLT isn't easily unit-testable, and there isn't currently a standard way of testing transforms for correctness. I've long thought that the only way to do this is to run the transform using a given input and check the result, and through that infer correctness in the transform.

I wrote a stylesheet to do this in XSLT 2.0 with heavy use of extensions (to perform the transforms and execute the XPaths) which was nice from an academic standpoint, but it soon became clear that this would be more useful as a Java app runnable from Ant.

This little project grew into a way of checking any XML file (to check a transform it runs the transform first and then checks the result). I'm provisionally calling this "CheckXML" and it's still early days but I think it's got the potential to be something really good.

CheckXML will allow you perform various checks on an XML file - XML Schema, XPath 2.0, XSLT 2.0, XQuery and Relax NG. This allows users to augment schema checks with XPath/XSLT checks to fully check the correctness of an XML file. A sample CheckXML configuration file would be:
<checkXML> <xml src="SampleXML.xml"> <check>SampleXSD.xsd</check> <check>count(distinct-values(//@id)) = count(//id)</check> <check>SampleXSLT.xslt</check> </xml> </checkXML>
Here the XML file "SampleXML.xml" first has the XML Schema SampleXSD.xsd applied to it, the then the XPath in the second check and finally the XSLT check. The CheckXML app will run each check and look for a result of "true" - any value that isn't true will be reported as a fail. This is the crucial point - it offloads the reponsbility of a creating a useful error to the check writer, and because the check write has the full power of XSLT/XPath/XQuery the error message can be as detailed as necessary (XSD/RNG check will return the error message if the XML isn't valid).

For example, modifying the XPath above to return a helpful message could be like this:

<check>if (count(distinct-values(//@id)) = count(//@id)) then 'true' else concat('The following id is not unique: ', distinct-values(for $x in //@id return $x[count(//@id[. = $x]) > 1]))</check>

This would output "The following id is not unique: 123" if you had two @id's with the value "123". The XPath's can get pretty complicated pretty quickly, which is why most of them should be moved into XSLT files, but it still might be more convenient to just use the XPath in the check config file itself. As the check writer has full control over the return message, it can be as simple or complicated as needed.

The CheckConfig files can have multiple <xml> elements (<transform> elements for checking transforms) with each one having as many <check>'s as required. A CheckSuite will point to multiple CheckConfig files. CheckXML will be callable from Ant, with any fails causing the Ant build to fail (with all details of the fail in the logs). I'm also planning a GUI with a nice green/red progress bar :) and a CheckConfig editor, but that's down the line.

Using collection() and saxon:discard-document() to create reports

2006-11-09T13:22:00.000Z

You can process directories of XML using the collection() function, and keep memory usage constant by using the Saxon extension saxon:discard-document()

<xsl:for-each select="for $x in collection('file:///c:/xmlDir?select=*.xml;recurse=yes;on-error=ignore') return saxon:discard-document($x)">

You have to be careful that Saxon doesn't optimize out the call to saxon:discard-document() - this basic outer xsl:for-each works well and has become boilerplate code for whenever I start a new report.

This technique allows you to do things that would otherwise not be feasible with XSLT, and would take longer in another language. For example finding, grouping and sorting all links in your collection of XML files. Coding the XSLT takes minutes and running it takes time proportional to your dataset size, but the restriction of system memory has gone.

Table Normalization in XSLT 2.0

2006-09-04T17:45:00.000Z

Some time ago I wrote a 1.0 stylesheet that normalizes a table - it's currently available on Dave Pawson's FAQ.

The problem of table normalization is to remove colspans and rowspans from a table placing a copy of the content in each cell.

This table:


+-----------+-----------+
| a         | b         |
|           +-----+-----+
|           | c   | d   |
+-----------+-----+     |
| e               |     |
+-----+-----+-----+     |
| f   | g   | h   |     |
+-----+-----+-----+-----+

Would become this:


+-----+-----+-----+-----+
| a   | a   | b   | b   |
+-----+-----+-----+-----+
| a   | a   | c   | d   |
+-----+-----+-----+-----+
| e   | e   | e   | d   |
+-----+-----+-----+-----+
| f   | g   | h   | d   |
+-----+-----+-----+-----+

The 1.0 solution I wrote used a neat recursive template that maintained pointers to the previous and current rows to deal with the tricky rowspans (colspans are the easy part). In rewriting the transform in 2.0 I've simplified it a great deal, but sadly not with any new 2.0 only feature, just with a better algorithm. Here's the transform:

<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
exclude-result-prefixes="xs">

<xsl:output method="xhtml" indent="yes"
omit-xml-declaration="yes"
encoding="UTF-8" />

<xsl:variable name="table_with_no_colspans">
<xsl:apply-templates mode="colspan"/>
</xsl:variable>

<xsl:variable name="table_with_no_rowspans">
<xsl:for-each select="$table_with_no_colspans">
<xsl:apply-templates mode="rowspan"/>
</xsl:for-each>
</xsl:variable>

<xsl:template match="/">
<xsl:apply-templates select="$table_with_no_rowspans" mode="final"/>
</xsl:template>

<xsl:template match="@*|*" mode="#all">
<xsl:copy>
<xsl:apply-templates select="@*|*" mode="#current"/>
</xsl:copy>
</xsl:template>

<xsl:template match="td" mode="colspan">
<xsl:choose>
<xsl:when test="@colspan">
<xsl:variable name="this" select="." as="element()"/>
<xsl:for-each select="1 to @colspan">
<td>
<xsl:copy-of select="$this/@*[not(name() = 'colspan')][not(name() = 'width')]"/>
<xsl:copy-of select="$this/node()"/>
</td>
</xsl:for-each>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="."/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

<xsl:template match="tbody" mode="rowspan">
<xsl:copy>
<xsl:copy-of select="tr[1]" />
<xsl:apply-templates select="tr[2]" mode="rowspan">
<xsl:with-param name="previousRow" select="tr[1]"/>
</xsl:apply-templates>
</xsl:copy>
</xsl:template>

<xsl:template match="tr" mode="rowspan">
<xsl:param name="previousRow"/>

<xsl:variable name="currentRow" select="."/>

<xsl:variable name="normalizedTDs">
<xsl:for-each select="$previousRow/td">
<xsl:choose>
<xsl:when test="@rowspan > 1">
<xsl:copy>
<xsl:attribute name="rowspan">
<xsl:value-of select="@rowspan - 1" />
</xsl:attribute>

<xsl:copy-of select="@*[not(name() = 'rowspan')]"/>
<xsl:copy-of select="node()"/>
</xsl:copy>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="$currentRow/td[1 + count(current()/preceding-sibling::td[not(@rowspan) or (@rowspan = 1)])]"/>
</xsl:otherwise>
</xsl:choose>
</xsl:for-each>
</xsl:variable>

<xsl:variable name="newRow" as="element(tr)">
<xsl:copy>
<xsl:copy-of select="$currentRow/@*"/>
<xsl:copy-of select="$normalizedTDs"/>
</xsl:copy>
</xsl:variable>

<xsl:copy-of select="$newRow"/>

<xsl:apply-templates select="following-sibling::tr[1]" mode="rowspan">
<xsl:with-param name="previousRow" select="$newRow"/>
</xsl:apply-templates>
</xsl:template>

<xsl:template match="td" mode="final">
<xsl:choose>
<xsl:when test="@rowspan">
<xsl:copy>
<xsl:copy-of select="@*[not(name() = 'rowspan')]"/>
<xsl:copy-of select="node()"/>
</xsl:copy>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="."/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

</xsl:stylesheet>

Kernow 1.4 released

2006-07-07T13:05:00.000Z

I've finally got around to releasing a new version of Kernow.

This version adds a few new features and I've also fixed a few annoying bugs:

Added optional caching URI and entity resolvers (including an entity resolver for documents referenced through the collection() function)
Added directory validation using SaxonSA, Xerces or JAXP (choice of XSD or RNG where possible).
Added the ability to run schema aware XQueries
Added default, lax and strict validation for schema aware transforms and queries
Added the ability to choose the type of files to process in a directory (eg, xml, xhtml, or well-formed html)
Fixed a number of small bugs, such as the progress bar occasionally throwing an NPE.

Saxon 8.7.3 released

2006-06-14T12:02:00.000Z

Mike Kay has released Saxon 8.7.3

Saxon-B: http://saxon.sf.net/
Saxon-SA: http://www.saxonica.com/

"This maintenance release clears 35 documented bugs, and on .NET it adds the
capability to process a DOM Document "in situ" rather than by first copying
it to create a Saxon tree.

(Saxon 8.7.2, in case you missed it, was a rebuild of Saxon-SA on .NET with
no changed functionality.)"

A Caching EntityResolver for the collection() function

2006-06-12T14:33:00.000Z

XSLT 2.0 allows you to write a "standalone stylesheet", that is, a transform with no input XML. Instead you must provide the name of the template where execution should begin. The stylesheet can then use the document() or doc() functions to process individual files, and the collection() function to process directories of XML. I use the standalone XSLT model a lot where you have multiple input files and a single output file, for example generating a report or creating an index page.

I recently ran into a problem though, where a few thousand of several thousand input files referenced entity files hosted at the w3.org. This only became apparent when the transforms started failing for no reason. It turns out that the network admins where I work had turned off the proxy, so each and every entity file was being fetched from the w3c - where making 500 requests in 10 minutes mean you get a 24 hour ban...

In a standard transform catching and caching requests for entity files is easy - you write a custom EntityResolver and tell the XMLReader to use that. For the collection() function however it's a lot more complicated. In Saxon 8.7.1, the URI used in the collection() function is resolved using the StandardCollectionURIResolver(). You can use your own one of these by calling setCollectionURIResolver() on the Configuration, and then do what you like within that class. To create a CollectionURIResolver() that caches entities files, it's pretty much a case of copying whats in the StandardCollectionURIResolver() and then modifying it to suit your needs.

I've added this functionality to the next release of Kernow, so that standalone transforms and XQueries have the option of a caching EntityResolver. I get the impression it's early days here, and this will become a common enough requirement that a setter will be exposed for an EntityResolver on the XMLReader used by the collection() function, making this kind of task much easier in the future.

Character encoding, character references and Windows-1252

2006-05-25T14:32:00.000Z

Consider this XML:

<?xml version="1.0" encoding="Windows-1252" ?>
<foo>&_#150;0x96</foo>

Here there is the character reference #150 and the actual character 0x96 that character reference #150 resolves to. The underscore is used to prevent the character reference being resolved by the browser, and the string '0x96' is used instead of the actual character 0x96 because blogger complains otherwise (stick with me...) Note the encoding used in the prolog.

Transforming that XML with this stylesheet:

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
<xsl:output encoding="US-ASCII"/>
<xsl:template match="/">
  <xsl:copy-of select="."/>
</xsl:template>
</xsl:stylesheet>

Gives this result:

<foo>&_#150;&_#8211;</foo>

Here you can see the character reference has been written back out as the same character, however character 0x96 has become 0x2013 (8211 in decimal). Character 150 is the unicode character "START OF GUARDED AREA" in the non-displayed C1 control character range, but in the Windows-1252 encoding it's mapped to to the displayable character 0x2013 "en-dash" (a short dash). Microsoft squeezed more characters into the single byte range by replacing non-displayed control characters with more useful displayable characters, but mistakenly went on to label files encoded in this way as ISO-8859-1 in some MS Office applications. In ISO-8859-1 the characters in the C0 and C1 ranges are the non-displayable control characters, but this mis-labelling was so widespread that parsers began detecting this situation and silently switching the read encoding to Windows-1252.

This problem surfaces when serving XHTML to an XHTML browser. While browsers are reading files using their HTML parsers, any file mis-labelled as ISO-8859-1 that contains characters in the C0 or C1 ranges will still auto-magically display the characters in those ranges, as the forgiving parsers auto-switch the read encoding. However, when an XHTML file is served (using the correct mime type eg "application/xhtml+xml") XHTML browsers such as Firefox will parse the file using its stricter XML parser - and all the characters in the C0 and C1 ranges will remain as those non-displayed characters. The auto-switch won't take place and characters such as 0x96 (en-dash) that were once displayed will just disappear.

This problem only occurs when an XML file is saved in Windows-1252 but is labelled as something else, usually IS0-8859-1. The most common culprit is Notepad, where a user has edited and saved an XML file without realising/caring that Notepad is unaware of the XML prolog.

So back to the example above:

<?xml version="1.0" encoding="Windows-1252" ?>
<foo>&_#150;0x96</foo>

The main point to realise here is that character references (the #150 in the example) are always resolved using Unicode codepoints, regardless of the specified encoding. Actual characters in the file will be read using the specified encoding. Therefore the #150 is resolved to 0x96 (its Unicode codepoint), while the actual character 0x96 in the source becomes 0x2013 (#8211) as specified in the Windows-1252 encoding.

The result of the transformation demonstrates this when serialised using the US-ASCII encoding (so all bytes above 127 will be written out as character references) looks like this:

<foo>&_#150;&_#8211;</foo>

A great example I think :)

Wikipedia has lots more information: http://en.wikipedia.org/wiki/ISO_8859-1

*There are two versions of ISO-8859-1 - The ISO and IANA versions. The ISO versions doesn't contain the C0 and C1 control characters, the IANA version does contain them. The XML recommendation uses the IANA version.

Kernow 1.3 released

2006-05-07T14:50:00.000Z

I've uploaded a new version Kernow that contains Saxon 8.7.1 with a few minor bugs fixed. These mainly centered around paths - the systemId of the source XML and base uri used by xsl:result-document.

The latter was pretty straightforward, the base uri used by xsl:result-document is set using Controller.setBaseOutputURI() - this value is now set to either the uri of the stylesheet, or the output file/directory (depending if one is supplied). This makes sense, as if you are outputting to a given file/directory, you would like the output from your xsl:result-document instructions to be relative to that (in my view, anyway). If you haven't supplied an output file/directory and you're outputting to the Kernow output window, then it should be resovled against the stylesheet.

Setting the systemId of the TransformerHandler to be that of the XML file seemed wrong to me at first, as you would expect it to be used by the stylesheet. After thinking about it a little, it makes some sense: the TransformerHandler knows the systemId of the stylesheet from when it was created - it doesn't know the location of the source XML as that arrives as a series of SAX events - therefore it's possible to set it through setSystemId. Perhaps someone knows for sure...

Sudoku Solver complete - and shes fast

2006-05-02T13:37:00.000Z

(NOTE: I've improved on this version here)

I finally got around to finishing the Sudoku solver after several weeks of other things getting the way.

I've improved the heuristics that check for the allowed values for a given cell. It now checks the row and column "friends" - the other rows and columns in a group (eg columns 1 and 2 when the cell is in column 3, or columns 1 and 3 when the cell is in 2). This is quite straightforward for a human and is done almost without noticing, but its reasonably involved to code.

The other change was to recursively insert all the values into cells with only one possible value, and then re-evaluate the allowed values with those cells inserted. This takes care of the situation where there are initially two possible values, but after inserting a definite value elsewhere there is only one possible values left.

Ultimately all this reduces the number of times the transform has to guess - on certain boards it would take a long time to solve purely because it was guessing wrongly early on, and then have to go through all the permutations before working its way back to that early point and trying the next number. Now there should be the maximum number of values in place before it has to guess (if at all) so that it doesn't waste time backtracking.

Here it is. To try it out run it using Saxon with "-it main" set, or run it against a dummy input XML. The are a few sample boards included, to try them out change the main template to point the variable containing the board, or cut and paste it's contents into the param at the top of the stylesheet.

If you find a board that this stylesheet can't process quickly, please let me know.



<xsl:stylesheet version="2.0"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:saxon="http://saxon.sf.net/"
xmlns:fn="sudoku">

<xsl:param name="board" select="(
1,0,0,  3,0,0,  6,0,0,
0,2,0,  5,0,0,  0,0,4,
0,0,9,  0,0,0,  5,2,0,

0,0,0,  9,6,3,  0,0,0,
7,1,6,  0,0,0,  0,0,0,
0,0,0,  0,8,0,  0,4,0,

9,0,0,  0,0,5,  3,0,7,
8,0,0,  4,0,6,  0,0,0,
3,5,0,  0,0,0,  0,0,1
)" as="xs:integer+"/>

<xsl:param name="verbose" select="false()" as="xs:boolean"/>

<xsl:variable name="rowStarts" select="(1, 10, 19, 28, 37, 46, 55, 64, 73)" as="xs:integer+"/>
<xsl:variable name="topLeftGroup"     select="(1, 2, 3,     10, 11, 12,  19, 20, 21)" as="xs:integer+"/>
<xsl:variable name="topGroup"         select="(4, 5, 6,     13, 14, 15,  22, 23, 24)" as="xs:integer+"/>
<xsl:variable name="topRightGroup"    select="(7, 8, 9,     16, 17, 18,  25, 26, 27)" as="xs:integer+"/>
<xsl:variable name="midLeftGroup"     select="(28, 29, 30,  37, 38, 39,  46, 47, 48)" as="xs:integer+"/>
<xsl:variable name="center"           select="(31, 32, 33,  40, 41, 42,  49, 50, 51)" as="xs:integer+"/>
<xsl:variable name="midRightGroup"    select="(34, 35, 36,  43, 44, 45,  52, 53, 54)" as="xs:integer+"/>
<xsl:variable name="bottomLeftGroup"  select="(55, 56, 57,  64, 65, 66,  73, 74, 75)" as="xs:integer+"/>
<xsl:variable name="bottomGroup"      select="(58, 59, 60,  67, 68, 69,  76, 77, 78)" as="xs:integer+"/>
<xsl:variable name="bottomRightGroup" select="(61, 62, 63,  70, 71, 72,  79, 80, 81)" as="xs:integer+"/>

<xsl:function name="fn:getRowStart" as="xs:integer+" saxon:memo-function="yes">
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="xs:integer(floor(($index - 1) div 9) * 9) + 1"/>
</xsl:function>

<xsl:function name="fn:getRowNumber" as="xs:integer+" saxon:memo-function="yes">
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="(($index - 1) idiv 9) + 1"/>
</xsl:function>

<xsl:function name="fn:getColNumber" as="xs:integer+" saxon:memo-function="yes">
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="(($index - 1) mod 9) + 1"/>
</xsl:function>

<xsl:function name="fn:getRow" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="subsequence($board, fn:getRowStart($index), 9)"/>
</xsl:function>

<xsl:function name="fn:getCol" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:variable name="gap" select="($index - 1) mod 9" as="xs:integer"/>
 <xsl:variable name="colIndexes" select="for $x in $rowStarts return $x + $gap" as="xs:integer+"/>
 <xsl:sequence select="for $x in $colIndexes return $board[$x]"/>
</xsl:function>

<xsl:function name="fn:getGroup" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:choose>
  <xsl:when test="$index = $topLeftGroup">
   <xsl:sequence select="for $x in $topLeftGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $topGroup">
   <xsl:sequence select="for $x in $topGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $topRightGroup">
   <xsl:sequence select="for $x in $topRightGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $midLeftGroup">
   <xsl:sequence select="for $x in $midLeftGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $center">
   <xsl:sequence select="for $x in $center return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $midRightGroup">
   <xsl:sequence select="for $x in $midRightGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomLeftGroup">
   <xsl:sequence select="for $x in $bottomLeftGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomGroup">
   <xsl:sequence select="for $x in $bottomGroup return $board[$x]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomRightGroup">
   <xsl:sequence select="for $x in $bottomRightGroup return $board[$x]"/>
  </xsl:when>
 </xsl:choose>
</xsl:function>

<xsl:function name="fn:getOtherValuesInTriple" as="xs:integer+" saxon:memo-function="yes">
 <xsl:param name="num" as="xs:integer"/>
 <xsl:sequence select="(xs:integer(((($num -1) idiv 3) * 3) + 1) to xs:integer(((($num - 1) idiv 3) * 3) + 3))[. != $num]"/>
</xsl:function>

<xsl:function name="fn:getRowFriends" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="for $x in fn:getOtherValuesInTriple($index) return $board[$x]"/>
</xsl:function>

<xsl:function name="fn:getColFriends" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:sequence select="for $x in fn:getOtherValuesInTriple(fn:getRowNumber($index))
            return
             $board[(($x * 9) - 8) + (($index - 1) mod 9)]"/>
</xsl:function>

<xsl:function name="fn:reducePossibleValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:param name="possibleValues" as="xs:integer+"/>
 
 <xsl:variable name="rowFriends" select="fn:getRowFriends($board, $index)" as="xs:integer+"/>
 <xsl:variable name="colFriends" select="fn:getColFriends($board, $index)" as="xs:integer+"/>
 
 <xsl:variable name="otherRow1" select="fn:getRow($board, 9 * fn:getOtherValuesInTriple(fn:getRowNumber($index))[1])" as="xs:integer+"/>
 <xsl:variable name="otherRow2" select="fn:getRow($board, 9 * fn:getOtherValuesInTriple(fn:getRowNumber($index))[2])" as="xs:integer+"/>
 
 <xsl:variable name="otherCol1" select="fn:getCol($board, fn:getOtherValuesInTriple($index)[1])" as="xs:integer+"/>
 <xsl:variable name="otherCol2" select="fn:getCol($board, fn:getOtherValuesInTriple($index)[2])" as="xs:integer+"/>

 <xsl:variable name="reducedValues" as="xs:integer*">
  <xsl:for-each select="$possibleValues">
   <xsl:if test=". = $otherCol1 and . = $otherCol2">
    <xsl:choose>
     <xsl:when test="not($colFriends = 0)">
      <xsl:sequence select="."/>
     </xsl:when>
     <xsl:when test="$colFriends != 0">
      <xsl:choose>
       <xsl:when test="$colFriends[1] = 0">
        <xsl:if test=". = $otherRow1">
         <xsl:sequence select="."/>
        </xsl:if>
       </xsl:when>
       <xsl:when test="$colFriends[2] = 0">
        <xsl:if test=". = $otherRow2">
         <xsl:sequence select="."/>
        </xsl:if>
       </xsl:when>
      </xsl:choose>
     </xsl:when>
    </xsl:choose>
   </xsl:if>
   
   <xsl:if test=". = $otherRow1 and . = $otherRow2">
    <xsl:choose>
     <xsl:when test="not($rowFriends = 0)">
      <xsl:sequence select="."/>
     </xsl:when>
     <xsl:when test="$rowFriends != 0">
      <xsl:choose>
       <xsl:when test="$rowFriends[1] = 0">
        <xsl:if test=". = $otherCol1">
         <xsl:sequence select="."/>
        </xsl:if>
       </xsl:when>
       <xsl:when test="$rowFriends[2] = 0">
        <xsl:if test=". = $otherCol2">
         <xsl:sequence select="."/>
        </xsl:if>
       </xsl:when>
      </xsl:choose>
     </xsl:when>
    </xsl:choose>
   </xsl:if>
  </xsl:for-each>
 </xsl:variable>
 
 <xsl:sequence select="if (count($reducedValues) = 1) then $reducedValues else $possibleValues"/>

</xsl:function>

<xsl:function name="fn:getAllowedValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 
 <xsl:variable name="possibleValues" select="(1 to 9)[not(. = (fn:getRow($board, $index), fn:getCol($board, $index), fn:getGroup($board, $index)))]" as="xs:integer*"/>
 
 <xsl:choose>
  <xsl:when test="count($possibleValues) > 1">
      <xsl:variable name="reducedValues" select="fn:reducePossibleValues($board, $index, $possibleValues)" as="xs:integer*"/>
   
   <xsl:sequence select="$reducedValues"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:sequence select="$possibleValues"/>
  </xsl:otherwise>
 </xsl:choose>

</xsl:function>

<xsl:function name="fn:tryValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="emptyCells" as="xs:integer+"/>
 <xsl:param name="possibleValues" as="xs:integer+"/>
 
 <xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
 
 <xsl:variable name="newBoard" select="(subsequence($board, 1, $index - 1), $possibleValues[1], subsequence($board, $index + 1))" as="xs:integer+"/>
 
 <xsl:if test="$verbose">
  <xsl:message>
   <xsl:value-of select="concat('Trying ', $possibleValues[1], ' out of a possible ', string-join(for $i in $possibleValues return xs:string($i), ' '), ' at index ', $index)"/>
  </xsl:message>
 </xsl:if>
 
 <xsl:variable name="result" select="fn:populateValues($newBoard, subsequence($emptyCells, 2))" as="xs:integer*"/>
 
 <xsl:sequence select="if (empty($result)) then
                               if (count($possibleValues) > 1) then
                                 fn:tryValues($board, $emptyCells, subsequence($possibleValues, 2))
                               else
                                 ()
                             else
                               $result"/>
</xsl:function>

<xsl:function name="fn:populateValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="emptyCells" as="xs:integer*"/>
 
 <xsl:choose>
  <xsl:when test="empty($emptyCells)">
   <xsl:message>Done!</xsl:message>
   <xsl:sequence select="$board"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
   <xsl:variable name="possibleValues" select="fn:getAllowedValues($board, $index)" as="xs:integer*"/>
   <xsl:choose>
    <xsl:when test="count($possibleValues) = 0">
     <xsl:if test="$verbose">
      <xsl:message>! Cannot go any further !</xsl:message>
     </xsl:if>
     <xsl:sequence select="()"/>
    </xsl:when>
    <xsl:when test="count($possibleValues) > 1">
     <xsl:sequence select="fn:tryValues($board, $emptyCells, $possibleValues)"/>
    </xsl:when>
    <xsl:when test="count($possibleValues) = 1">
     <xsl:variable name="newBoard" select="(subsequence($board, 1, $index - 1), $possibleValues[1], subsequence($board, $index + 1))" as="xs:integer+"/>

     <xsl:if test="$verbose">
      <xsl:message>
       <xsl:value-of>
        <xsl:text>Only one value </xsl:text>
        <xsl:value-of select="$possibleValues[1]"/>
        <xsl:text> for index </xsl:text>
        <xsl:value-of select="$index"/>
       </xsl:value-of>
      </xsl:message>
     </xsl:if>

     <xsl:sequence select="fn:populateValues($newBoard, subsequence($emptyCells, 2))"/>
    </xsl:when>
   </xsl:choose>
  </xsl:otherwise>
 </xsl:choose>
</xsl:function>

<xsl:function name="fn:populateSingleValueCells" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="emptyCellsXML" as="element()*"/>
 
 <xsl:for-each select="1 to 81">
  <xsl:variable name="pos" select="." as="xs:integer"/>
  <xsl:choose>
   <xsl:when test="$emptyCellsXML[@index = $pos]/@possibleValues = 1">
    <xsl:sequence select="$emptyCellsXML[@index = $pos]/@values"/>
   </xsl:when>
   <xsl:otherwise>
    <xsl:sequence select="$board[$pos]"/>
   </xsl:otherwise>
  </xsl:choose>
 </xsl:for-each>

</xsl:function>

<xsl:function name="fn:populateSingleValueCells" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 
 <xsl:variable name="emptyCells" select="for $x in (1 to 81) return $x[$board[$x] = 0]" as="xs:integer*"/>

 <xsl:variable name="emptyCellsXML" as="element()*">
  <xsl:for-each select="$emptyCells">
   <xsl:variable name="allowedValues" select="fn:getAllowedValues($board, .)" as="xs:integer*"/>
   <cell index="{.}" possibleValues="{count($allowedValues)}" values="{$allowedValues}"/>
  </xsl:for-each>
 </xsl:variable>
 
 <xsl:choose>
  <xsl:when test="$emptyCellsXML/@possibleValues = 1">
   <xsl:variable name="newBoard" select="fn:populateSingleValueCells($board, $emptyCellsXML)" as="xs:integer+"/>
   <xsl:sequence select="fn:populateSingleValueCells($newBoard)"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:sequence select="$board"/>
  </xsl:otherwise>
 </xsl:choose>
 
</xsl:function>

<xsl:function name="fn:solveSudoku" as="xs:integer+">
 <xsl:param name="startBoard" as="xs:integer+"/>

 <xsl:variable name="board" select="fn:populateSingleValueCells($startBoard)" as="xs:integer+"/>
 
 <xsl:variable name="emptyCells" select="for $x in (1 to 81) return $x[$board[$x] = 0]" as="xs:integer*"/>
 
 <xsl:variable name="emptyCellsXML" as="element()*">
  <xsl:for-each select="$emptyCells">
   <xsl:variable name="allowedValues" select="fn:getAllowedValues($board, .)" as="xs:integer*"/>
   <cell index="{.}" possibleValues="{count($allowedValues)}" values="{$allowedValues}"/>
  </xsl:for-each>
 </xsl:variable> 
 
 <xsl:variable name="emptyCellsOrdered" as="xs:integer*">
  <xsl:for-each select="$emptyCellsXML">
   <xsl:sort select="@possibleValues" data-type="number" order="ascending"/>
   <xsl:sequence select="@index"/>
  </xsl:for-each>
 </xsl:variable>
 
 <xsl:variable name="endBoard" select="fn:populateValues($board, $emptyCells)" as="xs:integer*"/>

 <xsl:choose>
  <xsl:when test="empty($endBoard)">
   <xsl:message>! Invalid board - The starting board is not correct</xsl:message>
   <xsl:sequence select="$startBoard"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:sequence select="$endBoard"/>
  </xsl:otherwise>
 </xsl:choose>
</xsl:function>

<xsl:template match="/tt" name="maintt">
 <div>
  <xsl:variable name="emptyCellsXML" as="element()*">
   <xsl:for-each select="for $x in (1 to 81) return $x[$board[$x] = 0]">
    <cell index="{.}" possibleValues="{count(fn:getAllowedValues($board, .))}" values="{fn:getAllowedValues($board, .)}"/>
   </xsl:for-each>
  </xsl:variable>
 
  <xsl:for-each select="$emptyCellsXML">
   <xsl:sort select="@possibleValues" data-type="number" order="ascending"/>
   <xsl:copy-of select="."/>
  </xsl:for-each>
 </div>
</xsl:template>

<xsl:template match="/" name="main">
 <xsl:call-template name="drawResult">
  <xsl:with-param name="board" select="fn:solveSudoku($board)"/>
 </xsl:call-template>
</xsl:template>

<xsl:template name="drawResult">
 <xsl:param name="board" as="xs:integer+"/>
 <html>
  <head>
   <title>Sudoku - XSLT</title>
   <style>
    table { border-collapse: collapse;
    border: 1px solid black; }
    td { padding: 10px; }
    .norm { border-left: 1px solid #CCC;
      border-top: 1px solid #CCC;}
    .csep { border-left: 1px solid black; }
    .rsep { border-top: 1px solid black; }
   </style>
  </head>
  <body>
   <xsl:call-template name="drawBoard">
    <xsl:with-param name="board" select="$board"/>
   </xsl:call-template>
  </body>
 </html>
</xsl:template>

<xsl:template name="drawBoard">
 <xsl:param name="board" as="xs:integer+"/>
 <table>
  <xsl:for-each select="1 to 9">
   <xsl:variable name="i" select="."/>
   <tr>
    <xsl:for-each select="1 to 9">
     <xsl:variable name="pos" select="(($i - 1) * 9) + ."/>
     <td class="{if (position() mod 3 = 1) then 'csep' else ('norm')} {if ($i mod 3 = 1) then 'rsep' else ('norm')}">
      <xsl:value-of select="$board[$pos]"/>
     </td>
    </xsl:for-each>
   </tr>
  </xsl:for-each>
 </table>
</xsl:template>

<xsl:template name="drawBasicBoard">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:for-each select="1 to 9">
  <xsl:variable name="i" select="."/>

  <xsl:for-each select="1 to 9">
   <xsl:variable name="pos" select="(($i - 1) * 9) + ."/>
   <xsl:value-of select="$board[$pos]"/>
   <xsl:value-of select="if ($pos mod 3 = 0) then ',   ' else ', '"/>
  </xsl:for-each>

  <xsl:value-of select="if ($i mod 3 = 0) then '


' else '
'"/>
 </xsl:for-each>
</xsl:template>

<!-- Easy board, 32 existing numbers -->
<xsl:variable name="testBoard1" select="(
0,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>

<!-- Hard board, 24 existing numbers -->
<xsl:variable name="testBoard2" select="(
1,0,0,  5,6,0,  0,0,0,
9,0,0,  0,0,0,  2,0,8,
0,0,0,  0,0,0,  7,0,0,

0,8,0,  9,0,7,  0,0,2,
2,0,0,  0,0,0,  0,0,1,
6,0,0,  3,0,2,  0,4,0,

0,0,5,  0,0,0,  0,0,0,
4,0,3,  0,0,0,  0,0,9,
0,0,0,  0,4,1,  0,0,6
)" as="xs:integer+"/>

<!-- Extremely Hard board -->
<xsl:variable name="testBoard3" select="(
4,0,6,  7,8,0,  2,0,0,
0,5,7,  0,0,0,  0,0,0,
8,0,0,  0,0,0,  4,0,0,

0,0,0,  0,5,0,  0,9,0,
9,1,2,  0,0,0,  0,0,0,
0,4,0,  0,1,0,  0,0,3,

0,0,4,  3,0,0,  0,2,0,
7,0,3,  0,0,6,  0,0,0,
0,0,0,  5,0,7,  6,0,8
)" as="xs:integer+"/>

<!-- Fiendish board -->
<xsl:variable name="testBoard4" select="(
0,0,0,  0,0,5,  0,0,0,
0,0,0,  0,2,0,  9,0,0,
0,8,4,  9,0,0,  7,0,0,

2,0,0,  0,9,0,  4,0,0,
0,3,0,  6,0,2,  0,8,0,
0,0,7,  0,3,0,  0,0,6,

0,0,2,  0,0,9,  8,1,0,
0,0,6,  0,4,0,  0,0,0,
0,0,0,  5,0,0,  0,0,0
)" as="xs:integer+"/>

<!-- Fiendish 2 board -->
<xsl:variable name="testBoard5" select="(
 0,0,0,  0,0,5,  1,0,0,
 0,3,5,  0,0,0,  0,4,0,
 8,0,0,  4,0,0,  0,2,0,
 
 9,0,0,  0,3,0,  5,0,0,
 0,0,0,  2,0,8,  0,0,0,
 0,0,7,  0,9,0,  0,0,8,
 
 0,5,0,  0,0,9,  0,0,2,
 0,4,0,  0,0,0,  9,8,0,
 0,0,1,  7,0,0,  0,0,0
)" as="xs:integer+"/>

<xsl:variable name="testBoard_Fiendish_060323" select="(
 5,3,0,  0,9,0,  0,0,6,
 0,0,0,  1,5,0,  0,0,3,
 0,0,2,  0,0,0,  8,0,0,
 
 0,0,0,  0,0,0,  0,8,0,
 1,7,0,  0,4,0,  0,2,9,
 0,9,0,  0,0,0,  0,0,0,
 
 0,0,6,  0,0,0,  3,0,0,
 4,0,0,  0,1,2,  0,0,0,
 3,0,0,  0,6,0,  0,5,4
)" as="xs:integer+"/>

<!-- Fiendish 060403-->
<xsl:variable name="testBoard38" select="(
 5,0,0, 0,0,1, 0,0,2,
 0,6,0, 0,7,0, 0,0,0,
 0,0,0, 6,0,0, 8,0,0,
 
 0,0,3, 0,0,5, 0,0,8,
 0,9,0, 0,1,0, 0,2,0,
 2,0,0, 3,0,0, 7,0,0,
 
 0,0,1, 0,0,2, 0,0,0,
 0,0,0, 0,6,0, 0,9,0,
 8,0,0, 7,0,0, 0,0,5
)" as="xs:integer+"/>

<!-- Failing board, an erroneous 9 has been added at index 1 -->
<xsl:variable name="testBoard_Fail" select="(
9,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>

</xsl:stylesheet>

VTD-XML

2006-03-27T13:47:00.000Z

Ian Jones pointed me to an article on javaworld about VTD-XML, which is apparently "A new option that overcomes the problems of DOM and SAX".

It all sounds promising, although the article is light on code examples and heavy on comparisons, so I'll reserve judgement until I've used it. It does seem to concentrate on speed without mentioning conformity, which is not a good sign.

2006-03-24T19:13:00.000Z

Well when I said "blisteringly fast" I should have said "very fast, but give it a week or two and we'll get faster"...

I've since found a way of improving the performance of my solution... and I think Dimitre has improved his. Watch this space, because neither is quite ready yet. I'll stick my neck out and say once it's done, mine should solve any board pretty much instantly. (I'm going to regret saying that, because mine probably won't but Dimitre's will...)

Dimitre's tuned Sudoku solution

2006-03-20T17:11:00.000Z

Never one to settle for second place Dimitre set about performance tuning his Sudoku solving stylesheet... with dramatic effect.

His latest effort is *blisteringly* fast...

With this board, known as "Fiendish 2" his solution takes just 7.1 seconds. To put that into perspective, my performance tuned implementation takes well over 5 minutes! I'll have to find out why the time is so bad for me...

Here's the "Fiendish 2" board, in the format Dimite's solution requires:


<board>
 <row>0,0,0,0,0,5,1,0,0</row>
 <row>0,3,5,0,0,0,0,4,0</row>
 <row>8,0,0,4,0,0,0,2,0</row>
 <row>9,0,0,0,3,0,5,0,0</row>
 <row>0,0,0,2,0,8,0,0,0</row>
 <row>0,0,7,0,9,0,0,0,8</row>
 <row>0,5,0,0,0,9,0,0,2</row>
 <row>0,4,0,0,0,0,9,8,0</row>
 <row>0,0,1,7,0,0,0,0,0</row>
</board>

Dimitre's stylesheet:


<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="f xs">
 
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">


  <xsl:variable name="vFixed" select="f:cellsGroup('Fixed', /*/*)"/>
  <xsl:variable name="vEmpty" select="f:cellsGroup('Empty', /*/*)"/>
  
  <xsl:variable name="vallFillers" as="element()*">
   <xsl:for-each select=
    "f:makeFillers(f:cellsGroup('Fixed', /*/*), f:cellsGroup('Empty', /*/*))">
     <xsl:sort select="@row"/>
     <xsl:sort select="@col"/>

     <xsl:sequence select="."/>
   </xsl:for-each>
  </xsl:variable>

  
   <xsl:sequence
     select="f:sudoku($vFixed, $vEmpty, $vallFillers)"/>
 </xsl:template>
 
 <xsl:variable name="vAllVals" select="1 to 9" as="xs:integer+"/>
 
 <xsl:function name="f:cellsGroup" as="element()*">
   <xsl:param name="pgrpType" as="xs:string"/>
   <xsl:param name="pRows" as="element()*"/>
     <xsl:sequence select=
      "for $i in 1 to count($pRows),
            $vRow in $pRows[$i],
                $vNum in tokenize($vRow, ',')
                           [if($pgrpType='Fixed')
                               then . ne '0'
                               else . eq '0'
                           ][if($pgrpType='Empty')
                               then 1
                               else true()],
                $k in index-of(tokenize($vRow, ','),$vNum)
               return
                 f:makeCell($i,$k, xs:integer($vNum))
      "/>
 </xsl:function>

 <xsl:function name="f:makeCell" as="element()">
  <xsl:param name="pnRow" as="xs:integer"/>
  <xsl:param name="pnCol" as="xs:integer"/>
  <xsl:param name="pnVal" as="xs:integer"/>
  
  <cell row="{$pnRow}" col="{$pnCol}" val="{$pnVal}"/>
 </xsl:function>
 
 <xsl:function name="f:sudoku" as="item()*">
   <xsl:param name="pFixedCells" as="element()*"/>
   <xsl:param name="pEmptyCells" as="element()*"/>
   <xsl:param name="pallFillers" as="element()*"/>
   
<!--
   <xsl:message>
  f:sudoku:
     Fixed: <xsl:sequence select="count($pFixedCells)"/>
     Empty: <xsl:sequence select="count($pEmptyCells)"/>
   </xsl:message>
-->
   <xsl:choose>
    <xsl:when test="empty($pEmptyCells)">
       <xsl:sequence select="f:printBoard($pFixedCells)"/>
    </xsl:when>
    <xsl:otherwise>
   <xsl:if test="f:canContinue($pFixedCells, $pEmptyCells, $pallFillers)">
       <xsl:variable name="vBestCells" as="element()*"
         select="f:bestCellsToTry($pEmptyCells,$pallFillers)"/>
    <xsl:variable name="vBestCell" select="$vBestCells[1]"/>
       <xsl:variable name="vcellFillers" as="element()+"
         select="f:cellFillers($pallFillers,$vBestCell)"/>

           <xsl:sequence select=
             "f:tryFillers($pFixedCells,$pEmptyCells, $pallFillers,
                           $vcellFillers,$vBestCell)"
             />
      </xsl:if>
    </xsl:otherwise>
   </xsl:choose>
 </xsl:function>
 
 <xsl:function name="f:canContinue" as="xs:boolean">
   <xsl:param name="pFixedCells" as="element()*"/>
   <xsl:param name="pEmptyCells" as="element()*"/>
   <xsl:param name="pallFillers" as="element()*"/>
   <xsl:sequence select=
      "empty($pEmptyCells[empty(f:cellFillers($pallFillers,.))])"
   />
<!-- -->
 </xsl:function>
 
 <xsl:function name="f:cellFillers" as="element()*">
   <xsl:param name="pallFillers" as="element()*"/>
   <xsl:param name="pemptyCell" as="element()"/>
   
   <xsl:sequence select="$pallFillers[@row eq $pemptyCell/@row
                                     and
                                      @col eq $pemptyCell/@col
                                     ]"/>

 </xsl:function>
 
 <xsl:function name="f:bestCellsToTry" as="element()*">
   <xsl:param name="pEmptyCells" as="element()*"/>
   <xsl:param name="pallFillers" as="element()*"/>

   <xsl:for-each select="$pEmptyCells">
     <xsl:sort select="count(f:cellFillers($pallFillers,.))" order="ascending"/>
     
     <xsl:sequence select="."/>
   </xsl:for-each>

   <xsl:variable name="vbestRow" as="element()+">
    <xsl:for-each-group select="$pEmptyCells" group-by="@row">
       <xsl:sort select="count(current-group())" order="ascending"/>
       <xsl:sequence select=
           "if(position() = 1)
               then current-group()
               else ()"/>
    </xsl:for-each-group>
   </xsl:variable>
  <!--  Output the resulting cell -->
 <xsl:for-each-group select="$vbestRow"
       group-by="count(f:column($pEmptyCells, current()/@col))">
    <xsl:sort select="current-grouping-key()" order="ascending"/>
 
    <xsl:sequence select="."/>
  </xsl:for-each-group>
 </xsl:function>
 
 <xsl:function name="f:makeFillers" as="element()*">
  <xsl:param name="pFixedCells" as="element()*"/>
  <xsl:param name="pEmptyCells" as="element()*"/>

  <xsl:sequence select="$pEmptyCells/f:makeFillersForCell($pFixedCells,.)"/>
 </xsl:function>

 <xsl:function name="f:makeFillersForCell" as="element()*">
  <xsl:param name="pFixedCells" as="element()*"/>
  <xsl:param name="pEmptyCell" as="element()"/>
  
    <xsl:for-each select="$vAllVals">
      <xsl:if test="not(. = f:column($pFixedCells,$pEmptyCell/@col)/@val)
                  and
                    not(. = f:row($pFixedCells,$pEmptyCell/@row)/@val)
                  and
                    not(. = f:region($pFixedCells, $pEmptyCell)/@val)
                   ">
      <xsl:sequence select="f:makeCell($pEmptyCell/@row,$pEmptyCell/@col,.)"/>
      </xsl:if>
    </xsl:for-each>
 </xsl:function>

 <xsl:function name="f:tryFillers" as="item()*">
  <xsl:param name="pFixedCells" as="element()*"/>
  <xsl:param name="pEmptyCells" as="element()*"/>
  <xsl:param name="pallFillers" as="element()*"/>
  <xsl:param name="pFillers" as="element()*"/>
  <xsl:param name="pBestCell" as="element()"/>
  
  <xsl:if test="exists($pFillers)">
   <xsl:variable name="vtheFiller" select="$pFillers[1]"/>
<!--
   <xsl:message>
     Trying filler: <xsl:sequence select="$vtheFiller"/>
   </xsl:message>
-->
   <xsl:variable name="vreducedFilllers" as="element()*"
    select="f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)"/>
<!--
   <xsl:variable name="vmadeFilllers" as="element()*"
    select="f:makeFillers(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)])"/>
   <xsl:if test="count($vmadeFilllers) != count($vreducedFilllers)">
      <xsl:message>
           Problem:
    count($vmadeFilllers) = <xsl:value-of select="count($vmadeFilllers)"/>
    count($vreducedFilllers) = <xsl:value-of select="count($vreducedFilllers)"/>
    
    madeFillers:
    <xsl:copy-of select="$vmadeFilllers"/>
    
    reducedFillers:
    <xsl:copy-of select="$vreducedFilllers"/>
      </xsl:message>
   </xsl:if>
-->
   <xsl:variable name="vSolution" select=
   "f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)],
             f:reduceAllFillers($pallFillers, $pBestCell,$vtheFiller)
             (: f:makeFillers(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)]) :)
             )
   "/>
   
     <xsl:choose>
       <xsl:when test="exists($vSolution)">
     <xsl:sequence select="$vSolution"/>
       </xsl:when>
       <xsl:otherwise>
         <xsl:sequence select=
         "f:tryFillers($pFixedCells,$pEmptyCells, $pallFillers,
                       $pFillers[position() gt 1],$pBestCell)"/>
       </xsl:otherwise>
     </xsl:choose>
  </xsl:if>
 </xsl:function>
 
 <xsl:function name="f:reduceAllFillers" as="element()*">
  <xsl:param name="pallFillers" as="element()*"/>
  <xsl:param name="ppickedCell" as="element()"/>
  <xsl:param name="pthisFiller" as="element()"/>

  <xsl:sequence select=
   "$pallFillers[(@row ne $ppickedCell/@row
                or
                 @col ne $ppickedCell/@col
                  )
                and
                 (
                 if(@row = $ppickedCell/@row
                    or
                     @col = $ppickedCell/@col
                    or
                      (
                       ((@row - 1) idiv 3 eq ($ppickedCell/@row -1) idiv 3)
                      and
                        ((@col - 1) idiv 3 eq ($ppickedCell/@col -1) idiv 3)
                       )
                     )
                     then
                       @val ne $pthisFiller/@val
                     else
                       true()
                  )
                 ]"
   />
 </xsl:function>
 
 <xsl:function name="f:column" as="element()*">
   <xsl:param name="pCells" as="element()*"/>
   <xsl:param name="pColno" as="xs:integer"/>

   <xsl:sequence select="$pCells[@col = $pColno]"/>
 </xsl:function>

 <xsl:function name="f:row" as="element()*">
   <xsl:param name="pCells" as="element()*"/>
   <xsl:param name="pRowno" as="xs:integer"/>

   <xsl:sequence select="$pCells[@row = $pRowno]"/>
 </xsl:function>

 <xsl:function name="f:region" as="element()*">
   <xsl:param name="pCells" as="element()*"/>
   <xsl:param name="paCell" as="element()"/>

   <xsl:variable name="vregRowStart" as="xs:integer"
        select="3*(($paCell/@row -1) idiv 3) +1"/>
   <xsl:variable name="vregColStart" as="xs:integer"
        select="3*(($paCell/@col -1) idiv 3) +1"/>
        
   <xsl:sequence select=
      "$pCells[xs:integer(@row) ge $vregRowStart and xs:integer(@row) lt ($vregRowStart +3)
        and
          xs:integer(@col) ge $vregColStart and xs:integer(@col) lt ($vregColStart +3)
              ]"/>
 </xsl:function>

 <xsl:function name="f:printBoard">
  <xsl:param name="pCells" as="element()+"/>
  
  <xsl:for-each-group select="$pCells" group-by="@row">
    <xsl:sort select="current-grouping-key()"/>
    <row>
       <xsl:for-each select="current-group()">
         <xsl:sort select="@col"/>
         <xsl:value-of select=
          "concat(@val, if(position() ne last()) then ', ' else ())"
          />
       </xsl:for-each>
    </row>
  </xsl:for-each-group>
 </xsl:function>
</xsl:stylesheet>

Dimitre Novatchev's Sudoku solution

2006-03-16T17:33:00.000Z

The Sudoku solving stylesheet craze has been catching on...

Dimitre Novatchev, creator of FXSL and xsl-list regular, has written a stylesheet (in typical Dimitre style) which attacks the problem from a slightly different angle.


<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="f xs">

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:sequence
    select="f:sudoku(f:cellsGroup('Fixed', /*/*),
f:cellsGroup('Empty', /*/*))"/>
 </xsl:template>

 <xsl:variable name="vAllVals" select="1 to 9" as="xs:integer+"/>

 <xsl:function name="f:cellsGroup" as="element()*">
  <xsl:param name="pgrpType" as="xs:string"/>
  <xsl:param name="pRows" as="element()*"/>
    <xsl:sequence select=
     "for $i in 1 to count($pRows),
           $vRow in $pRows[$i],
               $vNum in tokenize($vRow, ',')
                          [if($pgrpType='Fixed')
                              then . ne '0'
                              else . eq '0'
                          ][if($pgrpType='Empty')
                              then 1
                              else true()],
               $k in index-of(tokenize($vRow, ','),$vNum)
              return
                f:makeCell($i,$k, xs:integer($vNum))
     "/>
 </xsl:function>

 <xsl:function name="f:makeCell" as="element()">
 <xsl:param name="pnRow" as="xs:integer"/>
 <xsl:param name="pnCol" as="xs:integer"/>
 <xsl:param name="pnVal" as="xs:integer"/>

 <cell row="{$pnRow}" col="{$pnCol}" val="{$pnVal}"/>
 </xsl:function>

 <xsl:function name="f:sudoku" as="item()*">
  <xsl:param name="pFixedCells" as="element()*"/>
  <xsl:param name="pEmptyCells" as="element()*"/>

  <xsl:choose>
   <xsl:when test="empty($pEmptyCells)">
      <xsl:sequence select="f:printBoard($pFixedCells)"/>
   </xsl:when>
   <xsl:otherwise>
      <xsl:variable name="vBestCells" as="element()*"
        select="f:bestCellsToTry($pEmptyCells)"/>
         <xsl:if test="empty($vBestCells[empty(f:fillers($pFixedCells,.))])">
            <xsl:variable name="vBestCell" select="$vBestCells[1]"/>
            <xsl:variable name="vFillers" as="element()+"
                select="f:fillers($pFixedCells,$vBestCell)"/>

          <xsl:sequence select=
            "f:tryFillers($pFixedCells,$pEmptyCells, $vFillers,$vBestCell)"
            />
       </xsl:if>
   </xsl:otherwise>
  </xsl:choose>
 </xsl:function>

 <xsl:function name="f:bestCellsToTry" as="element()*">
  <xsl:param name="pEmptyCells" as="element()*"/>

  <xsl:variable name="vbestRow" as="element()+">
          <xsl:for-each-group select="$pEmptyCells" group-by="@row">
             <xsl:sort select="count(current-group())" order="ascending"/>
             <xsl:sequence select=
                 "if(position() = 1)
                     then current-group()
                     else ()"/>
          </xsl:for-each-group>
  </xsl:variable>
 <!--  Output the resulting cell -->
       <xsl:for-each-group select="$vbestRow"
             group-by="count(f:column($pEmptyCells, current()/@col))">
          <xsl:sort select="current-grouping-key()" order="ascending"/>

          <xsl:sequence select="."/>
        </xsl:for-each-group>
 </xsl:function>

 <xsl:function name="f:fillers" as="element()*">
 <xsl:param name="pFixedCells" as="element()*"/>
 <xsl:param name="pEmptyCell" as="element()"/>

   <xsl:for-each select="$vAllVals">
     <xsl:if test="not(. = f:column($pFixedCells,$pEmptyCell/@col)/@val)
                 and
                   not(. = f:row($pFixedCells,$pEmptyCell/@row)/@val)
                 and
                   not(. = f:region($pFixedCells, $pEmptyCell)/@val)
                  ">
         <xsl:sequence
select="f:makeCell($pEmptyCell/@row,$pEmptyCell/@col,.)"/>
     </xsl:if>
   </xsl:for-each>
 </xsl:function>

 <xsl:function name="f:tryFillers" as="item()*">
 <xsl:param name="pFixedCells" as="element()*"/>
 <xsl:param name="pEmptyCells" as="element()*"/>
 <xsl:param name="pFillers" as="element()*"/>
 <xsl:param name="pBestCell" as="element()"/>

 <xsl:if test="exists($pFillers)">
  <xsl:variable name="vtheFiller" select="$pFillers[1]"/>

  <xsl:variable name="vSolution" select=
  "f:sudoku(($pFixedCells,$vtheFiller),$pEmptyCells[not(. is $pBestCell)])
  "/>

    <xsl:choose>
      <xsl:when test="exists($vSolution)">
          <xsl:sequence select="$vSolution"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:sequence select=
        "f:tryFillers($pFixedCells,$pEmptyCells, $pFillers[position()
gt 1],$pBestCell)"/>
      </xsl:otherwise>
    </xsl:choose>
 </xsl:if>
 </xsl:function>

 <xsl:function name="f:column" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="pColno" as="xs:integer"/>

  <xsl:sequence select="$pCells[@col = $pColno]"/>
 </xsl:function>

 <xsl:function name="f:row" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="pRowno" as="xs:integer"/>

  <xsl:sequence select="$pCells[@row = $pRowno]"/>
 </xsl:function>

 <xsl:function name="f:region" as="element()*">
  <xsl:param name="pCells" as="element()*"/>
  <xsl:param name="paCell" as="element()"/>

  <xsl:variable name="vregRowStart" as="xs:integer"
       select="3*(($paCell/@row -1) idiv 3) +1"/>
  <xsl:variable name="vregColStart" as="xs:integer"
       select="3*(($paCell/@col -1) idiv 3) +1"/>

  <xsl:sequence select=
     "$pCells[xs:integer(@row) ge $vregRowStart and xs:integer(@row)
lt ($vregRowStart +3)
                                   and
                                           xs:integer(@col) ge $vregColStart and xs:integer(@col) lt
($vregColStart +3)
             ]"/>
 </xsl:function>

 <xsl:function name="f:printBoard">
 <xsl:param name="pCells" as="element()+"/>

 <xsl:for-each-group select="$pCells" group-by="@row">
   <xsl:sort select="current-grouping-key()"/>
   <row>
      <xsl:for-each select="current-group()">
        <xsl:sort select="@col"/>
        <xsl:value-of select=
         "concat(@val, if(position() ne last()) then ', ' else ())"
         />
      </xsl:for-each>
   </row>
 </xsl:for-each-group>
 </xsl:function>
</xsl:stylesheet>

xq2xml

2006-03-15T15:08:00.000Z

David Carlisle is currently undertaking a project to convert XQuery expressions into other languages, by first converting the query to XML and then on from there.

The "xq2xml" page can be found at http://monet.nag.co.uk/xq2xml/index.html

His notes on the differences between XQuery and XSLT can be found at http://monet.nag.co.uk/xq2xml/xq2xslnotes.html

It's all very interesting reading, but I kept asking myself "why?" so I mailed him asking if there's a real world application behind all this...

David's reply: "is 'teach myself xquery' a real world application?"

I guess the "because it's there" mentality applies to programming too :)

David Carlisle's XQuery conversion of the Sudoku stylesheet

2006-03-14T20:55:00.000Z

After posting the Sudoku stylesheet to xsl-list, David Carlisle mailed me back off-list with the XQuery equivalent, and very fine it is too.

I did start doing some performance comparisons between this and the XSLT 2.0 version, but when the first few results were produced I remembered Saxon compiles much of it into the same internal represenation...


declare namespace fn = "sudoku";

declare variable  $board as xs:integer+ := (
1,0,0,  3,0,0,  6,0,0,
0,2,0,  5,0,0,  0,0,4,
0,0,9,  0,0,0,  5,2,0,

0,0,0,  9,6,3,  0,0,0,
7,1,6,  0,0,0,  0,0,0,
0,0,0,  0,8,0,  0,4,0,

9,0,0,  0,0,5,  3,0,7,
8,0,0,  4,0,6,  0,0,0,
3,5,0,  0,0,0,  0,0,1);

declare variable  $rowStarts as xs:integer+  := (1, 10, 19, 28, 37, 46, 55, 64,73);

declare variable  $groups as xs:integer+  := (
1,1,1,  2,2,2,  3,3,3,
1,1,1,  2,2,2,  3,3,3,
1,1,1,  2,2,2,  3,3,3,

4,4,4,  5,5,5,  6,6,6,
4,4,4,  5,5,5,  6,6,6,
4,4,4,  5,5,5,  6,6,6,

7,7,7,  8,8,8,  9,9,9,
7,7,7,  8,8,8,  9,9,9,
7,7,7,  8,8,8,  9,9,9
);


declare function fn:getRow ($board as xs:integer+, $index as xs:integer) as xs:integer+ {
 let $rowStart := floor(($index - 1) div 9) * 9
 return
  $board[position() > $rowStart and position() <= $rowStart + 9]
};


declare  function fn:getCol ($board as xs:integer+, $index as xs:integer)  as xs:integer+ {
 let $gap := ($index - 1) mod 9,
    $colIndexes := for $x in $rowStarts return $x + $gap
      return
  $board[position() = $colIndexes]};


declare  function fn:getGroup ($board as xs:integer+, $index as xs:integer)  as xs:integer+ {
 let $group :=    $groups[$index]
 return
   $board[for $x in position()  return $groups[$x]= $group]
};


declare  function fn:getAllowedValues ($board as xs:integer+, $index as xs:integer)  as xs:integer* {
 let $existingValues := (fn:getRow($board,
$index), fn:getCol($board, $index), fn:getGroup($board, $index))
return
 for $x in (1 to 9) return
                               if (not($x = $existingValues))
                                 then $x
                           else ()
};


declare  function  fn:tryValues($board as xs:integer+,
                               $emptyCells as xs:integer+,
                               $possibleValues as xs:integer+) as xs:integer* {
 let $index as xs:integer := $emptyCells[1],
    $newBoard as xs:integer+ := ($board[position() <$index],
                            $possibleValues[1], $board[position() > $index]),
    $result as xs:integer* := fn:populateValues($newBoard, $emptyCells[position() != 1])
   return
    if (empty($result)) then
     if (count($possibleValues) > 1) then
       fn:tryValues($board, $emptyCells, $possibleValues[position() != 1])
     else
       ()
   else
    $result
};

declare  function  fn:populateValues($board as xs:integer+,
                                    $emptyCells as xs:integer*) as xs:integer*{

 if (not(empty($emptyCells)))
       then
  let $index as xs:integer :=$emptyCells[1],
      $possibleValues as xs:integer* := distinct-values(fn:getAllowedValues($board, $index))
    return
      if (count($possibleValues) > 1)
  then
      fn:tryValues($board, $emptyCells, $possibleValues)
  else if (count($possibleValues) = 1)
      then
 let $newBoard as xs:integer+ :=($board[position() <
$index], $possibleValues[1], $board[position() > $index])
  return
   fn:populateValues($newBoard, $emptyCells[position() != 1])
    else ()
else
 $board
};

declare  function  fn:solveSudoku ($startBoard as xs:integer+) as  xs:integer+{
 let $emptyCells as xs:integer* :=for $x in (1 to 81) return if
($startBoard[$x] = 0) then $x else (),
     $endBoard as xs:integer* :=fn:populateValues($startBoard,$emptyCells)
    return
  if (empty($endBoard))
  then
  $startBoard
  else
   $endBoard};


declare  function  fn:drawResult ($board as xs:integer+) as  element(){
       <html>
               <head>
                       <title>Sudoku - XSLT</title>
                       <style>
                         table {{ border-collapse: collapse;
                                 border: 1px solid black; }}
                         td {{ padding: 10px; }}
                         .norm {{ border-left: 1px solid #CCC;
                                 border-top: 1px solid #CCC;}}
                         .csep {{ border-left: 1px solid black; }}
                         .rsep {{ border-top: 1px solid black; }}
                       </style>
               </head>
               <body>
         {fn:drawBoard($board)}
               </body>
       </html>
};

declare  function  fn:drawBoard ($board as xs:integer+) as  element(){
       <table>
           { for $i in 1 to 9
             return
                               <tr>
 {for $j at $p in 1 to 9
 let $pos := (($i - 1) * 9) + $j
  return
 <td class="{if ($p mod 3 = 1) then 'csep' else ('norm')}
{if ($i mod 3 = 1) then 'rsep' else ('norm')}">
       {$board[$pos]}
  </td>
}
                               </tr>
         }
       </table>
};


fn:drawResult(fn:solveSudoku($board))

A Sudoku solution in XSLT 2.0

2006-03-10T15:39:00.000Z

Here's a stylesheet I've written to solve a Sudoku puzzle. It came about when some friends and I were talking about Sudoku over lunch, and one them pointed at me and said "aah I bet XSLT can't do that!" .... which laid down the challenge.

After studying Michael Kay's Knights Tour stylesheet (in the samples directory of the Saxon download) for some time I was able to get going on this. This uses the same recursive technique, trying a particular "route" and then backtracking to the point where a different route can be taken when the last one failed. It uses an intelligent brute force technique (if those aren't mutually exclusive...) - it finds all of the available values for a cell, and then tries each one in turn until the puzzle is solved.

Once the stylesheet was written, it was quite interesting to try out different approaches to get the best performance. For example, the same friend (who reckons he's some kind of Sudoku expert) says that once you have the center squares its just a matter of time before you solve the rest of the board. So instead of just processing the "empty" squares (the zero values here) in the order they appear from 1 to 81, I processed the center squares first followed by the rest. This led to quite an improvement in performance...

It didn't make much sense to sense to then process the empty cells in the top-left group as they aren't affect by the center group, so I modified it to process the center group, then the top-middle group, followed by the rest. This has given the best performance so far...

Anyway, here it is. There are some test boards at the bottom of the stylesheet so just change the parameter value in the main template to use one of them.


<xsl:stylesheet version="2.0"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:fn="sudoku">

<xsl:param name="board" select="(
1,0,0,  3,0,0,  6,0,0,
0,2,0,  5,0,0,  0,0,4,
0,0,9,  0,0,0,  5,2,0,

0,0,0,  9,6,3,  0,0,0,
7,1,6,  0,0,0,  0,0,0,
0,0,0,  0,8,0,  0,4,0,

9,0,0,  0,0,5,  3,0,7,
8,0,0,  4,0,6,  0,0,0,
3,5,0,  0,0,0,  0,0,1
)" as="xs:integer+"/>

<xsl:param name="verbose" select="false()" as="xs:boolean"/>

<xsl:variable name="rowStarts" select="(1, 10, 19, 28, 37, 46, 55, 64, 73)" as="xs:integer+"/>
<xsl:variable name="topLeftGroup"     select="(1, 2, 3,     10, 11, 12,  19, 20, 21)" as="xs:integer+"/>
<xsl:variable name="topGroup"         select="(4, 5, 6,     13, 14, 15,  22, 23, 24)" as="xs:integer+"/>
<xsl:variable name="topRightGroup"    select="(7, 8, 9,     16, 17, 18,  25, 26, 27)" as="xs:integer+"/>
<xsl:variable name="midLeftGroup"     select="(28, 29, 30,  37, 38, 39,  46, 47, 48)" as="xs:integer+"/>
<xsl:variable name="center"           select="(31, 32, 33,  40, 41, 42,  49, 50, 51)" as="xs:integer+"/>
<xsl:variable name="midRightGroup"    select="(34, 35, 36,  43, 44, 45,  52, 53, 54)" as="xs:integer+"/>
<xsl:variable name="bottomLeftGroup"  select="(55, 56, 57,  64, 65, 66,  73, 74, 75)" as="xs:integer+"/>
<xsl:variable name="bottomGroup"      select="(58, 59, 60,  67, 68, 69,  76, 77, 78)" as="xs:integer+"/>
<xsl:variable name="bottomRightGroup" select="(61, 62, 63,  70, 71, 72,  79, 80, 81)" as="xs:integer+"/>

<xsl:function name="fn:getRow" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:variable name="rowStart" select="floor(($index - 1) div 9) * 9"/>
 <xsl:sequence select="$board[position() > $rowStart and position() <= $rowStart + 9]"/>
</xsl:function>

<xsl:function name="fn:getCol" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:variable name="gap" select="($index - 1) mod 9"/>
 <xsl:variable name="colIndexes" select="for $x in $rowStarts return $x + $gap" as="xs:integer+"/>
 <xsl:sequence select="$board[some $x in position() satisfies $x = $colIndexes]"/>
</xsl:function>

<xsl:function name="fn:getGroup" as="xs:integer+">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:choose>
  <xsl:when test="$index = $topLeftGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $topLeftGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $topGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $topGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $topRightGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $topRightGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $midLeftGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $midLeftGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $center">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $center]"/>
  </xsl:when>
  <xsl:when test="$index = $midRightGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $midRightGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomLeftGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $bottomLeftGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $bottomGroup]"/>
  </xsl:when>
  <xsl:when test="$index = $bottomRightGroup">
   <xsl:sequence select="$board[some $x in position() satisfies $x = $bottomRightGroup]"/>
  </xsl:when>
 </xsl:choose>
</xsl:function>

<xsl:function name="fn:getAllowedValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="index" as="xs:integer+"/>
 <xsl:variable name="existingValues" select="(fn:getRow($board, $index), fn:getCol($board, $index), fn:getGroup($board, $index))" as="xs:integer+"/>
 <xsl:sequence select="for $x in (1 to 9) return
                               if (not($x = $existingValues))
                                 then $x
                               else ()"/>
</xsl:function>

<xsl:function name="fn:tryValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="emptyCells" as="xs:integer+"/>
 <xsl:param name="possibleValues" as="xs:integer+"/>
 
 <xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
 <xsl:variable name="newBoard" select="($board[position() < $index], $possibleValues[1], $board[position() > $index])" as="xs:integer+"/>
 
 <xsl:if test="$verbose">
  <xsl:message>Trying 
   <xsl:value-of select="$possibleValues[1]"/> out of a possible 
   <xsl:value-of select="$possibleValues"/> at index 
   <xsl:value-of select="$index"/>
  </xsl:message>
 </xsl:if>
 
 <xsl:variable name="result" select="fn:populateValues($newBoard, $emptyCells[position() != 1])" as="xs:integer*"/>
 
 <xsl:sequence select="if (empty($result)) then
                               if (count($possibleValues) > 1) then
                                 fn:tryValues($board, $emptyCells, $possibleValues[position() != 1])
                               else
                                 ()
                             else
                               $result"/>
</xsl:function>

<xsl:function name="fn:populateValues" as="xs:integer*">
 <xsl:param name="board" as="xs:integer+"/>
 <xsl:param name="emptyCells" as="xs:integer*"/>
 
 <xsl:choose>
  <xsl:when test="not(empty($emptyCells))">
   <xsl:variable name="index" select="$emptyCells[1]" as="xs:integer"/>
   <xsl:variable name="possibleValues" select="distinct-values(fn:getAllowedValues($board, $index))" as="xs:integer*"/>
   <xsl:choose>
    <xsl:when test="count($possibleValues) > 1">
     <xsl:sequence select="fn:tryValues($board, $emptyCells, $possibleValues)"/>
    </xsl:when>
    <xsl:when test="count($possibleValues) = 1">
     <xsl:variable name="newBoard" select="($board[position() < $index], $possibleValues[1], $board[position() > $index])" as="xs:integer+"/>
     
     <xsl:if test="$verbose">
      <xsl:message>Only one value
       <xsl:value-of select="$possibleValues[1]"/> for index
       <xsl:value-of select="$index"/>
      </xsl:message>
     </xsl:if>
     
     <xsl:sequence select="fn:populateValues($newBoard, $emptyCells[position() != 1])"/>
    </xsl:when>
    <xsl:otherwise>
     <xsl:if test="$verbose">
      <xsl:message>! Cannot go any further !</xsl:message>
     </xsl:if>
     <xsl:sequence select="()"/>
    </xsl:otherwise>
   </xsl:choose>
  </xsl:when>
  <xsl:otherwise>
   <xsl:message>Done!</xsl:message>
   <xsl:sequence select="$board"/>
  </xsl:otherwise>
 </xsl:choose>
</xsl:function>

<xsl:function name="fn:solveSudoku" as="xs:integer+">
 <xsl:param name="startBoard" as="xs:integer+"/>
 
 <!-- First process the center cells, then the top, then the rest of the board.
      This should give better performance than starting top-left and working from there. -->
 <xsl:variable name="theRest" select="for $x in 1 to 81 return $x[not($x = $center)][not($x = $topGroup)]" as="xs:integer+"/>
 
 <xsl:variable name="emptyCells" select="for $x in ($center, $topGroup, $theRest) return if ($startBoard[$x] = 0) then $x else ()" as="xs:integer*"/>
 
 <xsl:variable name="endBoard" select="fn:populateValues($startBoard, $emptyCells)" as="xs:integer*"/>
 
 <xsl:choose>
  <xsl:when test="empty($endBoard)">
   <xsl:message>! Invalid board - The starting board is not correct</xsl:message>
   <xsl:sequence select="$startBoard"/>
  </xsl:when>
  <xsl:otherwise>
   <xsl:sequence select="$endBoard"/>
  </xsl:otherwise>
 </xsl:choose>
</xsl:function>

<xsl:template match="/" name="main">
 <xsl:call-template name="drawResult">
  <xsl:with-param name="board" select="fn:solveSudoku($board)"/>
 </xsl:call-template>
</xsl:template>

<xsl:template name="drawResult">
 <xsl:param name="board" as="xs:integer+"/>
 <html>
  <head>
   <title>Sudoku - XSLT</title>
   <style>
    table { border-collapse: collapse;
    border: 1px solid black; }
    td { padding: 10px; }
    .norm { border-left: 1px solid #CCC;
      border-top: 1px solid #CCC;}
    .csep { border-left: 1px solid black; }
    .rsep { border-top: 1px solid black; }
   </style>
  </head>
  <body>
   <xsl:call-template name="drawBoard">
    <xsl:with-param name="board" select="$board"/>
   </xsl:call-template>
  </body>
 </html>
</xsl:template>

<xsl:template name="drawBoard">
 <xsl:param name="board" as="xs:integer+"/>
 <table>
  <xsl:for-each select="1 to 9">
   <xsl:variable name="i" select="."/>
   <tr>
    <xsl:for-each select="1 to 9">
     <xsl:variable name="pos" select="(($i - 1) * 9) + ."/>
     <td class="{if (position() mod 3 = 1) then 'csep' else ('norm')} {if ($i mod 3 = 1) then 'rsep' else ('norm')}">
      <xsl:value-of select="$board[$pos]"/>
     </td>
    </xsl:for-each>
   </tr>
  </xsl:for-each>
 </table>
</xsl:template>

<!-- Easy board, 32 existing numbers -->
<xsl:variable name="testBoard1" select="(
0,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>

<!-- Hard board, 24 existing numbers -->
<xsl:variable name="testBoard2" select="(
1,0,0,  5,6,0,  0,0,0,
9,0,0,  0,0,0,  2,0,8,
0,0,0,  0,0,0,  7,0,0,

0,8,0,  9,0,7,  0,0,2,
2,0,0,  0,0,0,  0,0,1,
6,0,0,  3,0,2,  0,4,0,

0,0,5,  0,0,0,  0,0,0,
4,0,3,  0,0,0,  0,0,9,
0,0,0,  0,4,1,  0,0,6
)" as="xs:integer+"/>

<!-- Extremely Hard board -->
<xsl:variable name="testBoard3" select="(
4,0,6,  7,8,0,  2,0,0,
0,5,7,  0,0,0,  0,0,0,
8,0,0,  0,0,0,  4,0,0,

0,0,0,  0,5,0,  0,9,0,
9,1,2,  0,0,0,  0,0,0,
0,4,0,  0,1,0,  0,0,3,

0,0,4,  3,0,0,  0,2,0,
7,0,3,  0,0,6,  0,0,0,
0,0,0,  5,0,7,  6,0,8
)" as="xs:integer+"/>

<!-- Failing board, an erroneous 9 has been added at index 1 -->
<xsl:variable name="testBoard_Fail" select="(
9,2,0,  0,0,0,  0,3,6,
0,0,7,  4,0,0,  0,9,0,
0,0,5,  6,0,0,  0,4,8,

0,0,0,  9,3,0,  0,1,2,
2,9,0,  0,0,0,  0,7,5,
1,5,0,  0,8,2,  0,0,0,

6,7,0,  0,0,9,  1,0,0,
0,3,0,  0,0,7,  6,0,0,
4,8,0,  0,0,0,  0,2,0
)" as="xs:integer+"/>

</xsl:stylesheet>

Kernow 1.2

2006-03-10T15:25:00.000Z

I've released Kernow 1.2 which, after fixing a broken zip, is available from http://sourceforge.net/projects/easytransformer/

(It used to be called EasyTransformer, but since it nows supports XQuery and I really didn't like the name Easy.... EZ... eee zee... etc a name change was long overdue).

Kernow is an open source graphical front end for Saxon, the XSLT and XQuery processor. It's written in Java, with the Swing UI created using Matisse - the new UI editor in Netbeans 5. For me eclipse still wins on the IDE front (as it's just better for everyday usage), but Matisse is really special so it's worth putting up with Netbeans just for that.

Kernow basically gives you file choosers for the files involved in the transform, parameter and named template discovery, a caching entity resovler and improved directory transforms through compiling the stylesheet. It also stores all of the files involved and makes them selectable through combo boxes to reduce the amout of setup time when you get going. Hopefully it's useful to someone...

2006-03-10T14:48:00.000Z

The first post. I've set this blog up as a place to link through to some of the things I'm doing...