Язык в языке или встраиваем XPath в Scala

в 9:20, , рубрики: macro, macros, scala, xpath, метки: , , ,

Scala — великолепный язык. В него можно влюбиться. Код может быть лаконичным, но понятным; гибким, но строго типизированным. Продуманные до мелочей инструменты позволяют не бороться с языком, а выражать на нем свои идеи.

Но эти же инструменты позволяют писать крайне сложный код.
Использование интеллектуальной эквилибристики в стиле scalaz или вычислений на системе типов в духе shapeless — гарантия того, что ваш код поймут единицы.

В этой статье я расскажу о том, чего делать, скорее всего, не стоит.
Я расскажу как встроить в scala другой язык.

И хотя встраивать мы с вами будем XPath, но описываемый способ подходит для любого языка, для которого вы сможете построить синтаксическое дерево.

Причины

В scala есть возможность использовать все инструменты для работы с xml, что есть в Java (а их не мало). Но и код будет напоминать стары добрый Java-код. Не слишком радостная перспектива.

Есть собственный xml, встроенный в синтаксис языка:

scala> <root>
     |   <node attr="aaa"/>
     |   <node attr="111"> text</node>
     | </root>
res0: scala.xml.Elem = 
<root>
  <node attr="aaa"/>
  <node attr="111"> text</node>
</root>

scala> res0 \ "node"
res1: scala.xml.NodeSeq = NodeSeq(<node attr="aaa"/>, <node attr="111"> text</node>)

scala> res1 \ "@attr"
res2: scala.xml.NodeSeq = NodeSeq(aaa, 111)

Кажется, что вот оно счастье, но нет. Это лишь отдаленно напоминает XPath. Хоть немного сложные запросы становятся громоздкими и не читаемыми.

Но после некоторого знакомства со scala становится понятно, что создатели не голословно называют scala расширяемым (scalable) языком. И если чего-то не хватает, то это можно добавить.

Задачей я себе поставил максимальную приближенность к XPath с удобной интеграцией в язык.

Результат

Все наработки здесь: https://github.com/senia-psm/scala-xpath.git

Как посмотреть.

Если у вас еще нет git и sbt, то их придется установить (git, sbt) и, при необходимости, настроит прокси (git, sbt — в Program Files (x86)SBT есть специальный txt для подобных опций).

Клонируйте репозиторий:

git clone https://github.com/senia-psm/scala-xpath.git

Переходите в папку с репозиторием (scala-xpath) и открывайте REPL в проекте:

sbt console

Так же во многих примерах предполагается, что выполнены следующие импорты:

import senia.scala_xpath.macros._, senia.scala_xpath.model._

Что и как

Способ достижения цели однозначно определяется самой целью.
Встроить XPath в виде DSL, очевидно, не получится. Иначе это будет уже не совсем XPath. XPath выражение в scala можно поместить только в виде строки.
А значит:

  1. Parser combinators. Нам придется строку распарсить для валидации.
  2. String interpolation. Для встраивания переменных и функций в XPath.
  3. Macros. Для проверки на этапе компиляции.

Подготавливаем объектную модель.

Берем спецификацию XPath 1.0 и переписываем ее на scala.
Почти вся логика выражена через систему типов и механизм наследования scala. Исключения — в паре мест ограничения через require.
Здесь стоит отметить ключевое слово «sealed», запрещающее наследовать класс (или реализовывать интерфейс) вне данного файла. В частности при сопоставлении с образцом «sealed» позволяет компилятору проконтролировать, что учтены все возможные варианты.

Парсим XPath

Введение в парсеры

Парсеры представляют из себя функции, принимающие последовательность элементов и возвращающие в случае успеха результат обработки и оставшуюся часть последовательности.
Не успешные же результаты бывают двух видов «неудача» (Failure) и «ошибка» (Error).
Образно говоря парсер откусывает часть последовательности с начала и преобразовывает откушенное в объект определенного типа.

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

Для создания такого парсера из элемента используется метод accept, принимающий элемент. Этот метод определен как неявный (implicit), и если компилятор встретит элемент там, где ожидает встретить парсер, он добавит применение этого метода к элементу.
Допустим мы парсим последовательность символов:

def elementParser: Parser[Char] = 'c' //до компиляции
def elementParser: Parser[Char] = accept('c') //во время компиляции

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

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

Комбинируем парсеры

Ложь во благо

На самом деле в scala нет операторов, но если вы это знаете, то, скорее всего, про парсеры вам рассказывать не надо.

Бинарный оператор "~". Объединяет 2 парсера по принципу «и». Успешен только если успешен сначала первый парсер, а затем второй на остатке, который отдал первый.
Образно говоря сначала первый парсер откусывает то, что ему подходит, а затем второй пирует на остатках.
В качестве результата возвращается контейнер, содержащий результаты обоих парсеров.

parser1 ~ parser2

Таким образом можно скомбинировать любой набор парсеров.
У этого комбинатора есть 2 родственных: "~>" и "<~". Работают они так же, но возвращают результат только одного из скомбинированных парсеров.

Бинарный оператор "|". Объединение по принципу «или». Успешен, если на исходном входе успешен хотя бы один из результатов. Если первый парсер вернул «неудачу» (но не ошибку), то пробуем скормить тот же вход второму.

rep. Последовательность. Если у вас есть парсер «myParser», то парсер, образованный при помощи «rep(myParser)», будет «откусывать» при помощи «myParser» от входа до первого не удачного применения. Результаты всех «укусов» объединяются в коллекцию.
Есть родственные преобразования, для не пустой коллекции результатов (rep1) и для последовательности с разделителями (repsep)

Преобразуем результат

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

Комбинирование парсеров (и грамотность спецификаций w3c) позволяет написать парсер не задумываясь.
Фактически мы переписываем спецификацию уже во второй раз. Единственное существенное отличие — рекурсивные определения я заменил на «циклические» (rep и repsep).

Например:

Спецификация:

[15]   	PrimaryExpr	   ::=   	VariableReference	
                                      | '(' Expr ')'	
                                      | Literal	
                                      | Number	
                                      | FunctionCall

Парсер:

  def primaryExpr: Parser[PrimaryExpr] = variableReference
                                       | `(` ~> expr <~ `)` ^^ { GroupedExpr }
                                       | functionCall
                                       | number
                                       | literal

Единственное условие — требуется следить, чтобы наиболее «строгие» парсеры шли в объединении через "|" раньше остальных. В данном примере literal, очевидно, будет успешен везде, где успешен functionCall просто из-за того, что успешно распарсит имя функции, так что если literal поставить раньше, то до functionCall дело просто не дойдет.
Весь набор парсеров уложился в полторы сотни строк, что существенно короче определения объектной модели.

Подмешиваем переменные

Для добавления переменных в выражение будем использовать механизм string interpolation, появившийся в версии 2.10.
Механизм довольно прост: встретив строку перед которой (без пробела) стоит валидное имя метода компилятор производит простое преобразование:

t"strinf $x interpolation ${ obj.name.toString } "
StringContext("strinf ", " interpolation ", " ").t(x, { obj.name.toString })

Строка разбивается на куски по вхождениям переменных и выражений и передается в фабричный метод StringContext. Имя, предваряющее строку, используется как имя метода, а все переменные и выражения передаются в этот метод как параметры.
Если с методами вроде «s» и «f» на этом все заканчивается, то для методов, отсутствующих в StringContext, компилятор ищет implicit class — обертку над StringContext, содержащий нужный метод. Такой поиск является общим механизмом для scala и не относится на прямую к интерполяции строк.
Итоговый код:

 new MyStringContextHelper(StringContext("strinf ", " interpolation ", " ")).t(x, { obj.name.toString })

Но что же с нашим парсером? У нас больше нет непрерывной последовательности символов. А есть последовательность символов и чего-то еще.
Неужели вся работа коту под хвост?
Вот тут-то и приоткрывается полезность возможности парсить не только последовательность символов.
У нас есть последовательность символов и чего-то еще (об этом позже). Это как раз описывается концепцией Either. На хабре пару статьей про Either переводил Sigrlami.
Чтобы вернуть себе всю мощь парсеров надо лишь написать пару вспомогательных инструментов. В частности преобразование из Char, String и Regex в соответствующие парсеры.
Вот весь необходимый инструмент: EitherParsers. Стоит обратить внимание на абстрактный тип R. Про него не сделано ни каких предположений, так что инструментарий подходит для заранее не известного способа представления переменных.

Вмешиваемся в компиляцию

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

scala> import scala.reflect.runtime.universe._
import scala.reflect.runtime.universe._

scala> showRaw(reify( "str" -> 'symb ))
res0: String = Expr(Apply(Select(Apply(Select(Ident(scala.Predef), newTermName("any2ArrowAssoc")), List(Literal(Constant("str")))), newTermName("$minus$greater")), List(Apply(Select(Ident(scala.Symbol), newTermName("apply")), List(Literal(Constant("symb")))))))

Строить подобное самостоятельно нет ни малейшего желания.
Посмотрим что же нам предлагает scala с сохранением типизации и без ручной работы.
С одной стороны не много: метод literal, позволяющий преобразовывать некоторый ограниченный набор «базовых типов» к синтаксическим деревьям, да reify, производящий за вас всю ручную работу, но только в случае если любые переменные вы в него снаружи привносите в виде все того же дерева, после чего используете метод splice этого дерева, предназначенный специально для информирования reify о вашем желании встроить выражения типа Expt[T], как часть нового дерева с итоговым типом T.
С другой стороны этих методов вполне хватает. Дополнительные можно написать на основе имеющихся.

Само добавление интерполяции, обрабатываемой макросом, крайне лаконично:

  implicit class XPathContext(sc: StringContext) {
    def xp(as: Any*): LocationPath = macro xpathImpl
  }

Обрабатывающая макрос функция объявляется следующим обрзом:

def xpathImpl(c: Context)(as: c.Expr[Any]*): c.Expr[LocationPath]

Ясно откуда брать переменные, но как получить строки?
Для этого можно при помощи контекста «выглянуть» из функции. Так сказать оглядеться по сторонам.
А точнее посмотреть на то выражение у которого вызывается целевой метод xp.
Сделать это можно пр помощи c.prefix.
Но что мы там обнаружим? Ранее упоминалось, что там должно быть выраджение вида StringContext(«strinf », " interpolation ", " ").
Посмотрим на соответствующее дерево:

scala> import scala.reflect.runtime.universe._
import scala.reflect.runtime.universe._

scala> showRaw(reify(StringContext("strinf ", " interpolation ", " ")))
res0: String = Expr(Apply(Select(Ident(scala.StringContext), newTermName("apply")), List(Literal(Constant("strinf ")), Literal(Constant(" interpolation ")), Literal(Constant(" ")))))

Как мы видим отсюда можно получить все строки в явном виде, что мы и сделаем:

    val strings = c.prefix.tree match {
      case Apply(_, List(Apply(_, ss))) => ss
      case _ => c.abort(c.enclosingPosition, "not a interpolation of XPath. Cannot extract parts.")
    }

    val chars = strings.map{
      case c.universe.Literal(Constant(source: String)) => source.map{ Left(_) }
      case _ => c.abort(c.enclosingPosition, "not a interpolation of XPath. Cannot extract string.")
    }

Но изменился не только вход. Результатом работы парсера больше не может быть объект из нашей объектной модели — его просто не построить основываясь не на значении, а на параметре вида c.Expr[Any].

Изменим наш парсер соответствующим образом. Если в результате может хоть как-то фигурировать внешняя переменная, то парсер больше не может возвращать T, а должен возвращать c.Expr[T]. Для преобразований не элементарных типов к соответствующим Expr напишем вспомогательные методы literal на основе имеющихся, например:

  def literal(name: QName): lc.Expr[QName] = reify{ QName(literal(name.prefix).splice, literal(name.localPart).splice) } 

Принцип всех таких функций очень прост: разбираем аргумент на достаточно элементарные части и собираем его заново внутри reify.

Это потребует некоторой механической работы, но наш парсер изменится не сильно.

Последним этапом идет внедрение нескольких парсеров, способных распарсить переменную на входе.
Вот парсер для встраивания переменной:

    accept("xc.Expr[Any]", { case Right(e) => e } ) ^? ({
        case e: xc.Expr[BigInt] if confirmType(e, tagOfBigInt.tpe) =>
          reify{ CustomIntVariableExpr(VariableReference(QName(None, NCName(xc.literal(nextVarName).splice))), e.splice) }
        case e: xc.Expr[Double] if confirmType(e, xc.universe.definitions.DoubleClass.toType) =>
          reify{ CustomDoubleVariableExpr(VariableReference(QName(None, NCName(xc.literal(nextVarName).splice))), e.splice) }
        case e: xc.Expr[String] if confirmType(e, xc.universe.definitions.StringClass.toType) =>
          reify{ CustomStringVariableExpr(VariableReference(QName(None, NCName(xc.literal(nextVarName).splice))), e.splice) }
      },
      e => s"Int, Long, BigInt, Double or String expression expected, $e found."
      )

Исходный парсер «accept(»xc.Expr[Any]", { case Right(e) => e } )" очень прост — он принимает любой контейнер Right с деревом и возвращает это дерево.
Дальнейшее преобразование определяет можно ли эту переменную использовать как один из трех желаемых типов и, затем, преобразовывает в такое использование.

В результате мы получим следующее поведение:

scala> val xml = <book attr="111"/>
xml: scala.xml.Elem = <book attr="111"/>

scala> val os = Option("111")
os: Option[String] = Some(111)

scala> xml \ xp"*[@attr = $os]" // Option[String] нам не подходит
<console>:16: error: Int, Long, BigInt, Double or String expression expected, Expr[Nothing](os) found.
              xml \ xp"*[@attr = $os]"
                     ^

scala> xml \ xp"*[@attr = ${ os.getOrElse("") } ]" // а вот String уже подходит
res1: scala.xml.NodeSeq = NodeSeq(<book attr="111"/>)

И если сообщения об ошибках еще требуют доработки, то переменные встроены уже вполне удобно.

Встраивание функций потребовало довольно много кода (23 варианта, по одному для вариантов от 0 до 22 параметров) и работает не слишком удобно, так как принимать необходимо только Any, а приходит в основном NodeList (но может и строка прийти или Double):

scala> import org.w3c.dom.NodeList
import org.w3c.dom.NodeList

scala> val isAlluwedAttributeOrText = (_: Any, _: Any) match { // какая-нибудь страння, возможно даже заранее не известная функция
     |   case (a: NodeList, t: NodeList) if a.getLength == 1 && t.getLength == 1 =>
     |     a.head.getTextContent == "aaa" ||
     |     t.head.getTextContent.length > 4
     |   case _ => false
     | }
isAlluwedAttributeOrText: (Any, Any) => Boolean = <function2>

scala> val xml = <root attr="11111" ><inner attr="111" /><inner attr="aaa" >inner text</inner> text </root>
xml: scala.xml.Elem = <root attr="11111"><inner attr="111"/><inner attr="aaa">inner text</inner> text </root>

scala> xml \ xp"*[$isAlluwedAttributeOrText(@attr, text())]"
res0: scala.xml.NodeSeq = NodeSeq(<root attr="11111"><inner attr="111"/><inner attr="aaa">inner text</inner> text </root>, <inner attr="aaa">inner text</inner>)

Здесь мы получили первое отсупление от синтаксиса XPath (если не считать возможности вместо переменных писать выражения вида ${ произвольный код }) — внедряемую функцию требуется предварять долларом.

Внедрение методов

Естественно сами методы "" и "\" у scala.xml.NodeSeq не появились по мановению волшебной палочки, они добавляются при помощи implicit class в пакетном объекте модели.

Аналогичные методы встроены в org.w3c.dom.Node и NodeList.

И вот с применением полученного XPath возникают определенные проблемы.

Не решенные проблемы

Избавиться от java.lang.System.setSecurityManager(null). Судя по реализации com.sun.org.apache.xpath.internal.jaxp.XPathFactoryImpl по другому собственный обработчик функций не добавить.

Ошибки на этапе компиляции требуют доработки.
Если при не верно заданной функции сообщение об ошибке идеально (отдельный комплимент в сторону продуманности компилятора):

scala> xml \ xp"*[$isAlluwedAttributeOrText(@attr)]"
<console>:1: error: type mismatch;
 found   : (Any, Any) => Boolean
 required: Any => Any
              xml \ xp"*[$isAlluwedAttributeOrText(@attr)]"
                           ^

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

Производительность при работе с scala.xml оставляет желать много лучшего. Фактически происходит сначала преобразование из scala.xml в w3c.dom через строку, а затем обратное.
Единственное возможное решение — самостоятельно обрабатывать XPath.
Заодно это позволит избавиться от не слишком удобной типизации функций.

Производительность при работе с w3c.dom может быть немного повышена. на данный момент XPath компилируется из строки, хотя имеется готовая объектная модель. Преобразование между объектными моделями может несколько ускорить создание XPath.

Вывод

Встроить XPath в scala удалось без серьезных проблем и ограничений.
Переменные и функции из текущей области видимости допустимы везде, где их допускает спецификация.
При использовании с w3c.dom и при некоторых доработках возможно даже минорное ускорение за счет разбора выражение при компиляции.

Все гораздо проще. чем кажется на первый взгляд.
В начале сама идея внедрения в компиляцию вызывает оторопь. Результат же достигается с минимальными усилиями.
Да, API компилятора документировано гораздо хуже основной библиотеки, но оно логично и понятно.
Да, IDEA плохо понимает path-dependent types, зато осуществляет очень удобную навигацию, к том числе по API компилятора и учитывает неявные преобразования.

Автор: senia

Источник

Поделиться

* - обязательные к заполнению поля