DSL для регулярных выражений на Kotlin

Всем привет!

Эта статья про реализацию одного конкретного DSL (domain specific language, предметно-ориентированный язык) для регулярных выражений средствами Kotlin, но при этом она вполне может дать общее представление, о том, как написать свой DSL на Kotlin и что обычно будет делать "под капотом" любой другой DSL, использующий те же возможности языка.

Многие уже используют Kotlin или хотя бы пробовали это делать, да и остальные вполне могли слышать о том, что Kotlin располагает к написанию изящных DSL, чему есть блестящие примеры — Anko и kotlinx.html.

Конечно же, для регулярных выражений подобное уже делали (и ещё: на Java, на Scala, на C# — реализаций много, похоже, это распространённое развлечение). Но если хочется попрактиковаться или попробовать DSL-ориентированные языковые возможности Kotlin, то добро пожаловать под кат.

Как обычно выглядит DSL, написанный на Kotlin?

В худшем случае, наверное, так.

Большинство DSL на Java предлагают использовать цепочки вызовов для своих конструкций, как в этом примере Java Regex DSL:

Regex regex = RegexBuilder.create()
    .group("#timestamp")
        .number("#hour").constant(":")
        .number("#min").constant(":")
        .number("#secs").constant(":")
        .number("#ms")
    .end()
    .build();

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

• неудобная реализация вложенных конструкций (group и end выше), из-за которых придётся ещё и воевать с форматтером, да и банальной проверки соответствия открывающих и закрывающих элементов нет, можно написать лишний .end();

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

С этими недостатками в Kotlin можно справиться, если реализовать DSL в стиле Type-Safe Groovy-Style Builder (при объяснении технических деталей эта статья будет во многом повторять страницу документации по ссылке). Тогда выглядеть код на нём будет подобно этому примеру Anko:

Показать код

verticalLayout {
    val name = editText()
    button("Say Hello") {
        onClick { toast("Hello, ${name.text}!") }
    }
}

Или этому примеру kotlinx.html:

Показать код

html {
    body {
        div {
            a("http://kotlinlang.org") {
                target = ATarget.blank
                +"Main site"
            }
        }
    }
}

Забегая вперёд, скажу, что получившийся язык будет выглядеть примерно так:

Показать код:

val r = regex {
    group("prefix") {
        literally("+")
        oneOrMore { digit(); letter() }
    }
    3 times { digit() }
    literally(";")
    matchGroup("prefix")
}

Приступим

class RegexContext { }

fun regex(block: RegexContext.() -> Unit): Regex { throw NotImplementedError() }

Что тут написано? Функция regex возвращает построенный объект Regex и принимает единственный аргумент — другую функцию типа RegexContext.() -> Unit. Если вы уже хорошо знакомы с Kotlin, смело пропустите пару абзацев, объясняющих, что это.

Типы функций в Kotlin записываются как-то так: (Int, String) -> Boolean — это предикат двух аргументов — или так: SomeType.(Int) -> Unit — это функция, возвращающая Unit (аналог void-функции), и кроме аргумента Int принимающая ещё и receiver типа SomeType.

Функции, принимающие receiver, нам здорово помогают строить DSL благодаря тому, что можно передать в качестве аргумента такого типа лямбда-выражение, и у него появится неявный this, имеющий такой же тип, как receiver. Простой пример — библиотечная функция with:

fun <T, R> with(t: T, block: T.() -> R): R = t.block() 
// вызывает block со своим первым аргументом в качестве receiver

// передавая лямбду последним аргументом, можно писать её за скобками
with(ArrayList<Int>()) {
    for(i in 1..10) { add(i) } // вызов add с неявным использованием receiver
    println(this) // явное обращение к this -- это ArrayList<Int>
}

Отлично, теперь мы можем вызывать regex { ... } и внутри фигурных скобок работать с неким экземпляром RegexContext, как будто это this. Осталась самая малость — реализовать члены RegexContext. :)

Зачем нужен RegexContext?

Давайте составлять регулярное выражение по частям — каждый statement нашего DSL просто будет дописывать в недостроенное выражение очередную часть. Эти части и будет хранить RegexContext.

class RegexContext {
    internal val regexParts = mutableListOf<String>() // уже добавленные части

    private fun addPart(part: String) { // эту функцию будем вызывать в других
        regexParts.append(part) 
    }
}

Соответственно, функция regex {...} теперь будет выглядеть следующим образом:

fun regex(block: RegexContext.() -> Unit): Regex {
    val context = RegexContext()
    context.block() // вызываем block, который что-то сделает с context
    val pattern = context.regexParts.toString()
    return Regex(pattern) // компилируем собранный из частей паттерн-строку в Regex
}

Далее реализуем функции RegexContext, добавляющие разные части в регулярное выражение.

Следующие функции, если явно не сказано обратного, тоже расположены в теле класса.

Всё очень просто

Так ведь?

fun anyChar(s: String) = addPart(".")

Этот вызов просто добавляет в выражение точку, которой обозначается подвыражение, соответствующее любому одиночному символу.

Аналогично реализуем функции digit(), letter(), alphaNumeric(), whitespace(), wordBoundary(), wordCharacter() и даже startOfString() и endOfString() — все они выглядят примерно одинаково.

А именно:

fun digit() = addPart("\\d")

fun letter() = addPart("[[:alpha:]]")

fun alphaNumeric() = addPart("[A-Za-z0-9]")

fun whitespace() = addPart("\\s")

fun wordBoundary() = addPart("\\b")

fun wordCharacter() = addPart("\\w")

fun startOfString() = addPart("^")

fun endOfString() = addPart("$")

А вот для добавления произвольной строки в регулярное выражение придётся её сначала преобразовать, чтобы присутствующие в строке символы не интерпретировались как служебные. Самый простой способ это сделать — с помощью функции Regex.escape(...):

fun literally(s: String) = addPart(Regex.escape(s))

Например, literally(".:[test]:.") добавит в выражение часть \Q.:[test]:.\E.

Идём глубже

Что насчёт квантификаторов? Очевидное наблюдение: квантификатор навешивается на подвыражение, которое само по себе тоже валидный регекс. Давайте добавим немного вложенности!

Мы хотим вложенным блоком кода в фигурных скобках задавать подвыражение квантификатора, примерно так:

val r = regex {
    oneOrMore {
        optional { anyChar() }
        literally("-")
    }
    literally(";")
}

Делать мы это будем с помощью функций RegexContext, которые ведут себя почти так же, как regex {...}, но сами используют построенное подвыражение. Добавим сначала вспомогательные функции:

 private fun addWithModifier(s: String, modifier: String) {
     addPart("(?:$s)$modifier") // добавляет non-capturing group с модификатором
 }

 private fun pattern(block: RegexContext.() -> Unit): String { 
    // на самом деле немного иначе -- сюда мы ещё вернёмся
    val innerContext = RegexContext()
    innerContext.block() // block запускается на другом RegexContext
    return innerContext.regexParts.toString() // мы берём созданный им паттерн
} 

И потом используем их для реализации наших "квантификаторов":

fun optional(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "?")

fun oneOrMore(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "+")

И так далее (плюс, функции, позволяющие не заворачивать literally в лямбду

fun oneOrMore(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "+")
fun oneOrMore(s: String) = oneOrMore { literally(s) }

fun optional(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "?")
fun optional(s: String) = optional { literally(s) }

fun zeroOrMore(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "*")
fun zeroOrMore(s: String) = zeroOrMore { literally(s) }

Ещё в регексах есть возможность задавать количество ожидаемых вхождений точно или с помощью диапазона. Мы себе такое тоже хотим, правда? А ещё это хороший повод применить инфиксные функции — функции двух аргументов, один из которых — receiver. Вызовы таких функций будут выглядеть следующим образом:

val r = regex {
    3 times { anyChar() }
    2 timesOrMore { whitespace() }
    3..5 times { literally("x") } // 3..5 -- это IntRange
}

А сами функции объявим так:

infix fun Int.times(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "{$this}")

infix fun IntRange.times(block: RegexContext.() -> Unit) =  
    addWithModifier(pattern(block), "{${first},${last}}")

И все вместе, опять с функциями для строк-литералов:

infix fun Int.times(block: RegexContext.() -> Unit) = addWithModifier(pattern(block), "{$this}")
infix fun Int.times(s: String) = this times { literally(s) }

infix fun IntRange.times(block: RegexContext.() -> Unit) = 
    addWithModifier(pattern(block), "{${first},${last}}")
infix fun IntRange.times(s: String) = this times { literally(s) }

infix fun Int.timesOrMore(block: RegexContext.() -> Unit) = 
    addWithModifier(pattern(block), "{$this,}")
infix fun Int.timesOrMore(s: String) = this timesOrMore { literally(s) }

infix fun Int.timesOrLess(block: RegexContext.() -> Unit) = 
    addWithModifier(pattern(block), "{0,$this}")
infix fun Int.timesOrLess(s: String) = this timesOrLess { literally(s) }

Сгруппируйтесь!

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

val r = regex {
    anyChar()
    val separator = group { literally("+"); digit() } // возвращает индекс группы
    anyChar()
    matchGroup(separator) // использует индекс группы
    anyChar()
}

Однако группы вносят новую сложность в структуру регекса: они нумеруются "насквозь" слева направо, игнорируя вложенность подвыражений. А значит, нельзя считать вызовы group {...} независимыми друг от друга, и даже больше: все наши вложенные подвыражения теперь тоже друг с другом связаны.

Чтобы поддерживать нумерацию групп, слегка изменим RegexContext: теперь он будет помнить, сколько групп в нём уже есть:

class RegexContext(var lastGroup: Int = 0) { ... }

И, чтобы наши вложенные контексты знали, сколько групп было до них и сообщали, сколько добавилось внутри них, изменим функцию pattern(...):

private fun pattern(block: RegexContext.() -> Unit): String {
    val innerContext = RegexContext(lastGroup) // передаём внутрь
    innerContext.block()
    lastGroup = innerContext.lastGroup // обновляем количество групп снаружи
    return innerContext.regexParts.toString()
}

Теперь нам ничего не мешает корректно реализовать group:

fun group(block: RegexContext.() -> Unit): Int {
    val result = ++lastGroup
    addPart("(${pattern(block)})")
    return result
}

Случай именованных групп:

fun group(name: String, block: RegexContext.() -> Unit): Int {
    val result = ++lastGroup
    addPart("(?<$name>${pattern(block)})")
    return result
}

И матчинг групп, как индексированных, так и именованных:

fun matchGroup(index: Int) = addPart("\\$index")
fun matchGroup(name: String) = addPart("\\k<$name>")

Что-то ещё?

Да! Мы чуть не забыли важную конструкцию регулярных выражений — альтернативы. Для литералов альтернативы реализуются тривиально:

fun anyOf(vararg terms: String) = addPart(terms.joinToString("|", "(?:", ")") { Regex.escape(it) }) 
// соберёт из terms одну строку с префиксом, суффиксом и разделителем, 
// сначала применив к каждой Regex.escape(...)

Не сложнее реализация для вложенных выражений:

 fun anyOf(vararg blocks: RegexContext.() -> Unit) = 
     addPart(blocks.joinToString("|", "(?:", ")") { pattern(it) })

То же и для наборов символов:

fun anyOf(vararg characters: Char) =
        addPart(characters.joinToString("", "[", "]").replace("\\", "\\\\").replace("^", "\\^"))

fun anyOf(vararg ranges: CharRange) = 
        addPart(ranges.joinToString("", "[", "]") { "${it.first}-${it.last}" })

Но постойте, а что если мы хотим в одном и том же anyOf(...) использовать в качестве альтернатив разные вещи — например, и строку, и блок с кодом для вложенного подвыражения? Тут нас ждёт небольшое разочарование: в Kotlin нет union types (типов-объединений), и написать тип аргумента String | RegexContext.() -> Unit | Char мы не можем. Обойти это я смог только устрашающего вида костылями, которые всё равно не делают DSL лучше, поэтому решил оставить всё так, как написано выше — в конце концов, и String, и Char можно написать во вложенных подвыражениях, используя соответствующую перегрузку anyOf {...}.

Страшные костыли

• Использовать anyOf(vararg parts: Any), где Any — тип, которому принадлежит любой объект. Проверять, который из типов, соответственно, внутри, а в неосторожного пользователя, передавшего плохой аргумент, бросать IllegalArgumentException, чему он будет очень рад.

  
  

• Хардкор. В Kotlin класс может переопределить оператор invoke(), и тогда объекты этого класса можно будет использовать как функции: myObject(arg), и если оператор имеет несколько перегрузок, то и объект будет вести себя как несколько перегрузок функции. Затем можно попробовать каррировать функцию anyOf(...), но, раз она имеет произвольное число аргументов, то мы не знаем, когда они закончатся — следовательно, каждое частичное применение должно отменять результат предыдущего и после этого применяться само, как будто его аргумент последний.

  
  

  Если это аккуратно сделать, оно даже заработает, но мы неожиданно упрёмся в неприятный момент в грамматике Kotlin: в цепочке вызовов оператора invoke нельзя использовать подряд вызовы с фигурными скобками.

  
  

  object anyOf {
      operator fun invoke(s: String) = anyOf // настоящее тело опущено для краткости
      operator fun invoke(r: RegexContext.() -> Unit) = anyOf
  }
  
  anyOf("a")("b")("c") // так можно
  anyOf("123") { anyChar() } { digit() } // а вот так нельзя!
  anyOf("123")({ anyChar() })({ digit() }) // можно так
  ((anyOf("123")) { anyChar() }) { digit() } // или так

  
  

  Ну, и нужно оно нам такое?

  
  

Кроме этого, неплохо было бы переиспользовать регулярные выражения, как построенные нашим DSL, так и пришедшие к нам откуда-то ещё. Сделать это несложно, главное — не забыть про нумерацию групп. Из регекса можно вытащить количество его групп: Pattern.compile(pattern).matcher("").groupCount(), и остаётся только реализовать соответствующую функцию RegexContext:

fun include(regex: Regex) {
    val pattern = regex.pattern
    addPart(pattern)
    lastGroup += Pattern.compile(pattern).matcher("").groupCount()
}

И на этом, пожалуй, обязательные фичи заканчиваются.

Заключение

Спасибо, что дочитали до конца! Что у нас получилось? Вполне жизнеспособный DSL для регексов, которым можно пользоваться:

fun RegexContext.byte() = anyOf({ literally("25"); anyOf('0'..'5') },
                                { literally("2"); anyOf('0'..'4'); digit() },
                                { anyOf("0", "1", ""); digit(); optional { digit() } })
val r = regex {
    3 times { byte(); literally(".") }
    byte()
}

(Вопрос: для чего этот регекс? Правда же, он простой?)

Ещё достоинства:

• Сложно поломать регекс: даже скобки руками писать не надо, если код компилируется и группы правильные, то и регекс валидный.
• Получается наглядно формировать регекс динамически: это делает живой код с любыми валидными конструкциями вроде условий, циклов и вызовов сторонних функций.
• Если вы используете индексированные группы, то индекс группе назначается динамически, и даже изменение большого регекса, написанного на DSL, не поломает индексы групп.
• Расширяемость и переиспользуемость: можно в своём коде написать любую функцию-расширение, подобную byte() выше, и использовать её как составную часть в регексах — russianLetter(), ipAddress(), time()...

Что не получилось:

• Угловато выглядит anyOf(...), не удалось добиться лучшего.
• Плотность записи сильно уступает традиционной форме, регекс в полэкрана длиной превращается в блок в полэкрана высотой. Зато, наверное, читаемо.

Исходники, тесты и готовая к добавлению в проект зависимость — в репозитории на Github.

Что вы думаете по поводу предметно-ориентированных языков для регулярных выражений? Пользовались ли хоть раз? А другими DSL?

Буду рад обсудить всё, что прозвучало.

Удачи!