Сегодня я хочу рассказать об XSLT. Этот, весьма своеобразный, язык может оказаться очень полезным в тех случаях, когда требуется обработать XML-данные, сколь нибудь не тривиальным образом. Я расскажу о двух наиболее популярных (в среде Java-разработчиков) реализациях XSLT-процессора, подробно остановлюсь на вопросах их использования из Java-кода и попытаюсь сравнить их производительность. В качестве теста для сравнения производительности, я буду использовать широко известную задачу о расстановке 8-ми ферзей на шахматной доске.

Поскольку решение подобных задач, с использованием XSLT вряд ли можно отнести к категории нормальной деятельности, топик помещен в соответствующий раздел. В то же время, я надеюсь, что эта статья будет полезна, в качестве учебного материала.

Xalan vs Saxon

Несмотря на достаточно большое количество существующих реализаций XSLT, в случае, если мы говорим о разработке на языке Java, выбор (на мой взгляд) сводиться к двум упомянутым в заголовке. Действительно, использование реализации от Microsoft, затруднено тем, что она поставляется в виде нейтивной dll, а реализация от Oracle предназначена для использования непосредственно в базе данных. Другие реализации гораздо менее известны (меня действительно интересует этот вопрос и я буду рад дополнительно рассмотреть любую из Java-совместимых реализаций XSLT, предложенную участниками Хабра).

Saxon, на мой взгляд, является наиболее развитым, на сегодняшний день, XSLT-процессором. Матрица предоставляемых им возможностей действительно впечатляет. Хотя наиболее интересные из этих возможностей поддерживаются только коммерческими дистрибутивами, поставляемый по условиям Mozilla Public License version 1.0 Saxon HE также предоставляет полноценную поддержку XPath и XSLT как версии 1.0, так и версии 2.0. Для того, чтобы понять, насколько поддержка XSLT 2.0 может облегчить жизнь, достаточно бегло ознакомиться с содержанием популярного учебника XSLT Cookbook за авторством Sal Mangano.

Главным достоинством Xalan, в отличии от Saxon, является использование менее ограничивающей Apache License Version 1.1. Эта реализация обеспечивает полноценную поддержку XSLT версии 1.0. Еще одним козырем, как Xalan так и Saxon, является заявленная ими полная поддержка промышленного стандарта TrAX. О том, что это такое и для чего оно нужно, я расскажу в следующем разделе.

Именем TrAX-а и JAXP-а его

TrAX — это API для выполнения XML-преобразований, разработанное рядом заинтересованных организаций с целью унификации взаимодействия с XSLT-процессорами. В части относящейся к Java API он был опубликован Sun как JAXP 6 февраля 2001 года. Для ознакомления с возможностями использования JAXP я рекомендую прочитать следующие статьи.

Коротко говоря, JAXP позволяет работать с XML-документами в Java, используя как DOM, так и SAX (в том числе, реализуя XSLT-преобразования), не привязывая код к используемой реализации и версии обработчика. Для корректной работы достаточно обеспечить присутствие используемого jar-а в classpath и установить соответствующее System Property (последнее не обязательно если нет разницы какой из обработчиков упомянутых в classpath использовать).

Посмотрим, как это выглядит на практике. Для начала, попробуем загрузить XML-файл в память и получить из него некоторое значение, используя выражение XPath.

XML-файл будет выглядеть следующим образом:

<?xml version="1.0"?>
<size>5</size>

Здесь не так много данных, но начинать надо всегда с простого (в дальнейшем, мы будем использовать это значение для задания размера шахматной доски).

Достаем значение используя DOM

	private void test_xpath_dom() throws Exception {
		InputSource in = new InputSource(new FileInputStream("xml/data.xml"));
		DocumentBuilderFactory df = DocumentBuilderFactory.newInstance();
		Document doc = df.newDocumentBuilder().parse(in);
		
		NodeIterator nl = XPathAPI.selectNodeIterator(doc, "/size");
		Node n;
	    while ((n = nl.nextNode())!= null) {
	    	if (n.getNodeType() == Node.TEXT_NODE) {
	    		System.out.println(n.getNodeValue());
	    	} else {
	    		System.out.println(n.getTextContent());
	    	}
	    }
	}

Здесь мы получаем итератор по простому XPath-запросу, проходим по набору узлов (состоящему из одного узла) и выводим его значение (если это текстовый узел) или текстовое содержимое (в случае использованного запроса всегда будет работать этот вариант). Как мы видим, все совсем не сложно, но если мы достаем скалярное значение, можно поступить еще проще:

Достаем скалярное значение используя DOM

	private void test_xpath_dom() throws Exception {
		System.setProperty(JAVAX_TRANSFORM_FACTORY, XALAN_TRANSFORM_FACTORY);
		InputSource in = new InputSource(new FileInputStream("xml/data.xml"));
		DocumentBuilderFactory df = DocumentBuilderFactory.newInstance();
		Document doc = df.newDocumentBuilder().parse(in);
		
		XPathFactory xpathFactory = XPathFactory.newInstance();
		XPath xpath = xpathFactory.newXPath();
		XPathExpression xpathExpression = xpath.compile("/size");
		System.out.println(xpathExpression.evaluate(doc));
	}

Иногда (особенно при обработке XML-файлов большого объема) использования DOM стараются избегать (поскольку данные требуется целиком загружать в память). В таких случаях, для разбора XML применяют SAX. JAXP позволяет преобразовать один формат в другой (например SAX в DOM) используя следующую трансформацию (если при выполнении трансформации не указана таблица стилей, выполняется тождественное преобразование, что зачастую бывает весьма удобно):

Используем SAX-парсер

	private void test_xpath_sax_file() throws Exception {
		TransformerFactory tf = TransformerFactory.newInstance();
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(DOMResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler h = stf.newTransformerHandler();
	    	XMLReader reader = XMLReaderFactory.createXMLReader();
	        reader.setContentHandler(h);
	        reader.setProperty("http://xml.org/sax/properties/lexical-handler", h);

			DocumentBuilderFactory df = DocumentBuilderFactory.newInstance();
			Document doc = df.newDocumentBuilder().newDocument();
			Result out = new DOMResult(doc);
			h.setResult(out);
			reader.parse("xml/data.xml");
	        
	        XPathFactory xpathFactory = XPathFactory.newInstance();
	        XPath xpath = xpathFactory.newXPath();
	        XPathExpression xpathExpression = xpath.compile("/size");
	        System.out.println(xpathExpression.evaluate(doc));
	    } else {
	    	throw new Exception("Can''t support SAXSource or DOMResult");
	    }
	}

Понятно, что таким образом мы не избавимся от загрузки XML-файла в оперативную память, поскольку для промежуточного хранения мы все равно используем DOM. Как мы можем обрабатывать большие файлы? Например, мы можем получить SAX-поток при разборе большого XML-файла и преобразовать его таким образом, чтобы в память загружался не один большой, а множество мелких файлов поочередно. Попробуем сформировать SAX-события вручную:

Загрузка SAX-потока

	private void generateData(ContentHandler h, String data) throws SAXException {
		h.startDocument();
		h.startElement("", "size", "size", new AttributesImpl());
		h.characters(data.toCharArray(), 0, data.length());
		h.endElement("", "size", "size");
		h.endDocument();
	}
	

	private void test_xpath_sax_stream(String size) throws Exception {
		TransformerFactory tf = TransformerFactory.newInstance();
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(DOMResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler h = stf.newTransformerHandler();

			DocumentBuilderFactory df = DocumentBuilderFactory.newInstance();
			Document doc = df.newDocumentBuilder().newDocument();
			Result out = new DOMResult(doc);
			h.setResult(out);
			generateData(h, size);
	        
	        XPathFactory xpathFactory = XPathFactory.newInstance();
	        XPath xpath = xpathFactory.newXPath();
	        XPathExpression xpathExpression = xpath.compile("/size");
	        System.out.println(xpathExpression.evaluate(doc));
	    } else {
	    	throw new Exception("Can''t support SAXSource or DOMResult");
	    }
	}

Как мы видим, здесь также нет ничего сложного. Хочу лишь предостеречь от возможной передачи в параметр uri вызовов startElement и endElement null-значений. Для Xalan это работает нормально, но Saxon выбрасывает NullPointerException.

Для полноты картины, осталось добавить, что преобразования можно связывать в цепочки, образуя конвейер. На выходе, результат можно сохранять, например, в файл:

Конвейер

	private void test_solution(String size) throws Exception {
		TransformerFactory tf = TransformerFactory.newInstance();
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(SAXResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler solve  = stf.newTransformerHandler();
	        TransformerHandler filter = stf.newTransformerHandler();
	        TransformerHandler view   = stf.newTransformerHandler();
	        Result result = new StreamResult(new File("xml/result.xml"));
	        
	        solve.setResult(new SAXResult(filter));
	        filter.setResult(new SAXResult(view));
	        view.setResult(result);
			generateData(solve, size);
	    } else {
	    	throw new Exception("Can''t support SAXSource or SAXResult");
	    }
	}

Пока, мы видим здесь три пустых обработчика, выполняющих тождественное преобразование. В следующем разделе мы начнем наполнять их XSLT-кодом.

Первый подход к снаряду

Итак, нам надо расставить ферзей на шахматной доске таким образом, чтобы они не били друг-друга. Для начала нам требуется сгенерировать список позиций, удовлетворяющих условию задачи. Определимся с кодированием позиций. Поскольку, по условиям задачи, фигуры не могут располагаться на одной вертикали, мы можем использовать строку десятичных цифр для кодирования корректных позиций.

Позиция цифры будет означать номер вертикали, а само значение — номер горизонтали, на которой расположена фигура. Поскольку мы используем десятичные цифры, начиная с единицы, мы сможем решать задачу для квадратной доски размером от 1x1 до 9x9 клеток. Чтобы расчеты выполнялись быстрее, рекомендую установить размер меньше 8-ми (5x5 клеток будет в самый раз). Код на XSLT (несмотря на свою излишнюю многословность) вполне понятный:

solution.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  version="1.0">

  <xsl:template match="size">
    <result>
      <xsl:call-template name="queens">
        <xsl:with-param name="r"/>
        <xsl:with-param name="n" select="."/>
        <xsl:with-param name="s" select="."/>
      </xsl:call-template>
    </result>
  </xsl:template>

  <xsl:template name="queens">
    <xsl:param name="r"/>
    <xsl:param name="n"/>
    <xsl:param name="s"/>
    <xsl:choose>
      <xsl:when test="$n = 0">
        <position>
          <xsl:copy-of select="$r"/>
        </position>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="step">
          <xsl:with-param name="r" select="$r"/>
          <xsl:with-param name="n" select="$n"/>
          <xsl:with-param name="v" select="$s"/>
          <xsl:with-param name="s" select="$s"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="step">
    <xsl:param name="r"/>
    <xsl:param name="n"/>
    <xsl:param name="v"/>
    <xsl:param name="s"/>
    <xsl:if test="$v != 0">
      <xsl:variable name="c">
        <xsl:call-template name="check">
          <xsl:with-param name="r" select="$r"/>
          <xsl:with-param name="v" select="$v"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:if test="$c != 0">
        <xsl:variable name="l">
          <xsl:value-of select="concat($v,$r)"/> 
        </xsl:variable>
        <xsl:call-template name="queens">
          <xsl:with-param name="r" select="$l"/>
          <xsl:with-param name="n" select="$n - 1"/>
          <xsl:with-param name="s" select="$s"/>
        </xsl:call-template>
      </xsl:if>
      <xsl:call-template name="step">
        <xsl:with-param name="r" select="$r"/>
        <xsl:with-param name="n" select="$n"/>
        <xsl:with-param name="v" select="$v - 1"/>
        <xsl:with-param name="s" select="$s"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

  <xsl:template name="check">
    <xsl:param name="r"/>
    <xsl:param name="v"/>
    <xsl:if test="contains($r,$v)">0</xsl:if>
  </xsl:template>

</xsl:stylesheet>

Здесь мы используем упрощенную проверку на взаимный бой фигур, не выполняя проверку боя по диагонали. Запустив следующую программу на выполнение:

8 ладей

	private void test_solution(String size) throws Exception {
		TransformerFactory tf = TransformerFactory.newInstance();
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(SAXResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler solve  = stf.newTransformerHandler(new StreamSource("xsl/solution.xsl"));
	        TransformerHandler filter = stf.newTransformerHandler();
	        TransformerHandler view   = stf.newTransformerHandler();
	        Result result = new StreamResult(new File("xml/result.xml"));
	        
	        solve.setResult(new SAXResult(filter));
	        filter.setResult(new SAXResult(view));
	        view.setResult(result);
			generateData(solve, size);
	    } else {
	    	throw new Exception("Can''t support SAXSource or SAXResult");
	    }
	}

… можно получить список возможных решений задачи «8 ладей».

Чтобы исключить возможные обвинения в подмене условий задачи, усложним проверку взаимного боя фигур. Для упрощения повторного использования кода, XSLT предлагает использовать возможность импорта. Ей мы и воспользуемся:

queens.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  version="1.0">

  <xsl:import href="solution.xsl"/>

  <xsl:template name="check">
    <xsl:param name="r"/>
    <xsl:param name="v"/>
    <xsl:choose>
      <xsl:when test="contains($r,$v)">0</xsl:when>
      <xsl:otherwise>
        <xsl:variable name="y">
          <xsl:call-template name="additional_check">
            <xsl:with-param name="r" select="$r"/>
            <xsl:with-param name="v" select="$v"/>
            <xsl:with-param name="d" select="1"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:value-of select="$y"/> 
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="additional_check">
    <xsl:param name="r"/>
    <xsl:param name="v"/>
    <xsl:param name="d"/>
    <xsl:if test="$d &lt;= string-length($r)">
      <xsl:variable name="u" select="substring($r,$d,1)"/>
      <xsl:variable name="b">
        <xsl:call-template name="abs">
          <xsl:with-param name="x" select="$v - $u"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:choose>
        <xsl:when test="$b = $d">0</xsl:when>
        <xsl:otherwise>
          <xsl:call-template name="additional_check">
            <xsl:with-param name="r" select="$r"/>
            <xsl:with-param name="v" select="$v"/>
            <xsl:with-param name="d" select="$d + 1"/>
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:if>
  </xsl:template>

  <xsl:template name="abs">
    <xsl:param name="x"/>
    <xsl:choose>
      <xsl:when test="$x &lt; 0">
        <xsl:value-of select="$x * -1"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$x"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

</xsl:stylesheet>

Замечу, что здесь необходимо использовать именно инструкцию import, а не инструкцию include, чтобы обеспечить более высокий приоритет шаблонов в импортирующей таблице по сравнению с импортируемой (это очень похоже на наследование).

Чтобы весь этот импорт заработал, необходимо внести еще одно небольшое изменение в Java-код. Определим URIResolver, который будет вызываться при запросе URI в процессе разбора XSLT:

Resolver.java

import java.io.File;

import javax.xml.transform.Source;
import javax.xml.transform.TransformerException;
import javax.xml.transform.URIResolver;
import javax.xml.transform.stream.StreamSource;

public class Resolver implements URIResolver {

	public Source resolve(String href, String base) throws TransformerException {
		return new StreamSource(new File("xsl/" + href));
	}
}

… и передадим его фабрике:

8 ферзей

	private void test_queens(String size) throws Exception {
		TransformerFactory tf = TransformerFactory.newInstance();
+	tf.setURIResolver(new Resolver());
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(SAXResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler solve  = stf.newTransformerHandler(new StreamSource("xsl/queens.xsl"));
	        TransformerHandler filter = stf.newTransformerHandler();
	        TransformerHandler view   = stf.newTransformerHandler();
	        Result result = new StreamResult(new File("xml/result.xml"));
	        
	        solve.setResult(new SAXResult(filter));
	        filter.setResult(new SAXResult(view));
	        view.setResult(result);
			generateData(solve, size);
	    } else {
	    	throw new Exception("Can''t support SAXSource or SAXResult");
	    }
	}

Конечно, в нашем случае, когда все xsl-файлы загружаются из одного дискового каталога, XSLT-процессор и сам прекрасно разберется в том откуда подгрузить файл, но представьте себе, например, что XSLT-код загружается из LOB-поля в базе данных!

Запустив программу на выполнение, мы получим список решений задачи.

Что нам с ним делать?

Список решений в том виде, в котором мы его составили, не очень удобен для человека. Он компактен, но не дает наглядного представления о позициях (без некоторого мысленного усилия). Считать количество решений вручную, используя его, также не слишком удобно. К счастью, обработка таких данных — это именно то, для чего предназначен XSLT. Добавив в конец цепочки трансформаций вызов еще одного обработчика, мы сможем легко подсчитать количество решений:

count.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  version="1.0">

  <xsl:template match="result">
    <result>
      <xsl:value-of select="count(position)"/> 
    </result>
  </xsl:template>

</xsl:stylesheet>

… либо, показать их в наглядной форме:

boards.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  xmlns:redirect="http://xml.apache.org/xalan/redirect"
  extension-element-prefixes="redirect"
  version="1.0">

<xsl:output method="html"/>

  <xsl:template match="/result/position">
    <a href="{concat(. , '.html')}">
      <xsl:value-of select="."/>
    </a><br/>
    <redirect:write select="concat('xml/', . , '.html')">
      <style>
      table {
       display:block;
       margin:10px;
       border:0;
       border-collapse: collapse;
      }
      table tr {
       border:0;
      }
      table tr td {
       border:1px solid #999;
       width:15px;
       height:15px;
       padding: 0;
      }
      .active {
       background: #898989;
      }
      </style>
      <table border="1" style="border-collapse:collapse">
        <xsl:call-template name="line">
          <xsl:with-param name="r" select="."/>
          <xsl:with-param name="s" select="string-length(.)"/>
        </xsl:call-template>
      </table>
    </redirect:write>
  </xsl:template>

  <xsl:template name="line">
    <xsl:param name="r"/>
    <xsl:param name="s"/>
    <xsl:if test="string-length($r) != 0">
      <xsl:variable name="x" select="substring($r,1,1)"/>
      <tr>
        <xsl:call-template name="col">
          <xsl:with-param name="x" select="$x"/>
          <xsl:with-param name="i" select="$s"/>
        </xsl:call-template>
      </tr>
      <xsl:call-template name="line">
        <xsl:with-param name="r" select="substring($r,2)"/>
        <xsl:with-param name="s" select="$s"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

  <xsl:template name="col">
    <xsl:param name="x"/>
    <xsl:param name="i"/>
    <xsl:if test="$i != 0">
      <xsl:choose>
        <xsl:when test="$x = $i"><td class="active"/></xsl:when>
        <xsl:otherwise><td/></xsl:otherwise>
      </xsl:choose>
      <xsl:call-template name="col">
        <xsl:with-param name="x" select="$x"/>
        <xsl:with-param name="i" select="$i - 1"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

</xsl:stylesheet>

например такой:

В этом примере следует обратить внимание на нестандартное расширение Xalan redirect:write, позволяющее перенаправить вывод в другой файл (в XSLT 2.0, для этих целей, добавлена стандартная инструкция). К сожалению, мне не удалось перенаправить результат такого redirect-а в произвольный SAX-поток, что, на мой взгляд, несколько снижает его ценность.

Магия отражений

Мы получили решения, но их как-то слишком много. Это потому, что мы не отсеиваем повторы с учетом возможных поворотов и отражений доски. Давайте получим список уникальных решений?

Если немного подумать, становиться понятно, что всевозможных поворотов и отражений доски всего 8 (учитывая первоначальный вариант). Реализуем вспомогательные шаблоны для отражения позиции (в нашем внутреннем представлении) по вертикали (flip), горизонтали (reverse) и поворота доски на 90 градусов (rotate):

utils.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  version="1.0">

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

  <xsl:template match="position">
    <position>
      <xsl:value-of select="."/>
    </position>
    <flip>
      <xsl:call-template name="flip">
        <xsl:with-param name="x" select="."/>
      </xsl:call-template>
    </flip>
    <reverse>
      <xsl:call-template name="reverse">
        <xsl:with-param name="x" select="."/>
      </xsl:call-template>
    </reverse>
    <rotate>
      <xsl:call-template name="rotate">
        <xsl:with-param name="x" select="."/>
      </xsl:call-template>
    </rotate>
  </xsl:template>

  <xsl:template name="flip">
    <xsl:param name="x"/>
    <xsl:call-template name="flip_internal">
      <xsl:with-param name="x" select="$x"/>
      <xsl:with-param name="s" select="string-length($x) + 1"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="flip_internal">
    <xsl:param name="x"/>
    <xsl:param name="s"/>
    <xsl:if test="string-length($x) != 0">
      <xsl:value-of select="$s - substring($x,1,1)"/>
      <xsl:call-template name="flip_internal">
        <xsl:with-param name="x" select="substring($x,2)"/>
        <xsl:with-param name="s" select="$s"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

  <!-- XSLT Cookbook By Sal Mangano http://shop.oreilly.com/product/9780596003722.do -->
  <xsl:template name="reverse">
    <xsl:param name="x"/>
    <xsl:variable name="len" select="string-length($x)"/>
    <xsl:choose>
      <xsl:when test="$len &lt; 2">
        <xsl:value-of select="$x"/>
      </xsl:when>
      <xsl:when test="$len = 2">
        <xsl:value-of select="substring($x,2,1)"/>
        <xsl:value-of select="substring($x,1,1)"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="mid" select="floor($len div 2)"/>
        <xsl:call-template name="reverse">
          <xsl:with-param name="x" select="substring($x,$mid+1,$mid+1)"/>
        </xsl:call-template>
        <xsl:call-template name="reverse">
          <xsl:with-param name="x" select="substring($x,1,$mid)"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="rotate">
    <xsl:param name="x"/>
    <xsl:call-template name="rotate_internal">
      <xsl:with-param name="x" select="$x"/>
      <xsl:with-param name="i" select="1"/>
      <xsl:with-param name="r"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="rotate_internal">
    <xsl:param name="x"/>
    <xsl:param name="i"/>
    <xsl:param name="r"/>
    <xsl:variable name="p">
      <xsl:call-template name="index-of">
        <xsl:with-param name="input" select="$x"/>
        <xsl:with-param name="substr" select="$i"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:choose>
      <xsl:when test="$p = 0">
        <xsl:value-of select="$r"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="rotate_internal">
          <xsl:with-param name="x" select="$x"/>
          <xsl:with-param name="i" select="$i + 1"/>
          <xsl:with-param name="r" select="concat($p,$r)"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <!-- XSLT Cookbook By Sal Mangano http://shop.oreilly.com/product/9780596003722.do -->
  <xsl:template name="index-of">
    <xsl:param name="input"/>
    <xsl:param name="substr"/>
    <xsl:choose>
      <xsl:when test="contains($input,$substr)">
        <xsl:value-of select="string-length(substring-before($input,$substr))+1"/>
      </xsl:when>
      <xsl:otherwise>0</xsl:otherwise>
    </xsl:choose>
  </xsl:template>

</xsl:stylesheet>

Здесь использованы реализации функций reverse и index-of из замечательной книги Сэл Мангано «XSLT Сборник рецептов». Сама фильтрация уникальных значений — классическая задача на использование оси preceding-sibling:

distinct.xsl

<?xml version="1.0"?> 

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
  version="1.0">

  <xsl:import href="utils.xsl"/>

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

  <xsl:template match="position">
    <xsl:variable name="l" select="preceding-sibling::position"/>
    <xsl:variable name="a" select="."/>
    <xsl:variable name="b">
      <xsl:call-template name="flip">
        <xsl:with-param name="x" select="$a"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="c">
      <xsl:call-template name="reverse">
        <xsl:with-param name="x" select="$b"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="d">
      <xsl:call-template name="flip">
        <xsl:with-param name="x" select="$c"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="e">
      <xsl:call-template name="rotate">
        <xsl:with-param name="x" select="$a"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="f">
      <xsl:call-template name="flip">
        <xsl:with-param name="x" select="$e"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="g">
      <xsl:call-template name="reverse">
        <xsl:with-param name="x" select="$f"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:variable name="h">
      <xsl:call-template name="flip">
        <xsl:with-param name="x" select="$g"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:choose>
      <xsl:when test="$b = $l"></xsl:when>
      <xsl:when test="$c = $l"></xsl:when>
      <xsl:when test="$d = $l"></xsl:when>
      <xsl:when test="$e = $l"></xsl:when>
      <xsl:when test="$f = $l"></xsl:when>
      <xsl:when test="$g = $l"></xsl:when>
      <xsl:when test="$h = $l"></xsl:when>
      <xsl:otherwise>
        <position>
          <xsl:value-of select="$a"/>
        </position>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

</xsl:stylesheet>

К сожалению, в XSLT 1.0, мы не можем решить эту задачу одним XPath выражением, но в XSLT 2.0 добавлена возможность «обертывания» шаблонов в пользовательские функции.

На этом все! Мы решили задачу.

Осталось померять…

Кто быстрее?

Измерения будем проводить при помощи следующего кода:

Меряем производительность

	private final static String JAVAX_TRANSFORM_FACTORY = "javax.xml.transform.TransformerFactory";
	private final static String SAXON_TRANSFORM_FACTORY = "net.sf.saxon.TransformerFactoryImpl";
	private final static String XALAN_TRANSFORM_FACTORY = "org.apache.xalan.processor.TransformerFactoryImpl";

	private void test_full(String size) throws Exception {
		System.setProperty(JAVAX_TRANSFORM_FACTORY, SAXON_TRANSFORM_FACTORY);
		TransformerFactory tf = TransformerFactory.newInstance();
		tf.setURIResolver(new Resolver());
	    if (tf.getFeature(SAXSource.FEATURE) && tf.getFeature(SAXResult.FEATURE)) {
	        SAXTransformerFactory stf = (SAXTransformerFactory)tf;	  
	        TransformerHandler solve  = stf.newTransformerHandler(new StreamSource("xsl/queens.xsl"));
	        TransformerHandler filter = stf.newTransformerHandler(new StreamSource("xsl/distinct.xsl"));
	        TransformerHandler view   = stf.newTransformerHandler(new StreamSource("xsl/count.xsl"));
	        Result result = new StreamResult(new File("xml/result.xml"));
	        
	        solve.setResult(new SAXResult(filter));
	        filter.setResult(new SAXResult(view));
	        view.setResult(result);
	        
	        Long timestamp = System.currentTimeMillis();
			generateData(solve, size);
			System.out.println("Elapsed Time: " + Long.toString(System.currentTimeMillis() - timestamp));
	    } else {
	    	throw new Exception("Can''t support SAXSource or SAXResult");
	    }
	}

Заменяя константу SAXON_TRANSFORM_FACTORY на XALAN_TRANSFORM_FACTORY можно переключаться с одного XSLT-процессора на другой.

К сожалению (по непонятной мне причине) мне не удалось заставить нормально работать ни одну из версий ветки Saxon-HE. Код работает, но каждый вызов отрабатывает невероятно медленно. Например вызов TransformerFactory.newInstance() отрабатывал несколько минут! При этом один из CPU утилизировался полностью, а код (судя по отладчику) большую часть времени находился где-то в районе реализации SHA-2.

К счастью, более ранняя версия из соседней ветки работает нормально. Вот итоговые картинки:

Можно заметить, что, в этой задаче, оба XSLT-процессора работают приблизительно с одинаковой скоростью. Таким образом, использование Saxon может быть оправдано только при использовании функциональности XSLT 2.0 или XSLT 3.0.

Все исходные тексты, как обычно, выложены на GitHub.

Напоследок, хочу поблагодарить jonic за помощь оказанную им при подготовке статьи.

Xalan, Saxon и 8 ферзей