Разбор XML на F# с помощью комбинаторов

Возникла задача разбора потока данных XML, выдаваемых стандартным дотнетовским парсером XmlReader. Раньше я много раз это проделывал на C#, но часто приходилось создавать много дополнительных методов для обработки вложенных тегов XML. Код неприлично разрастался. Теперь захотелось выразительности и декларативности, чтобы разбор сводился к заданию структуры тегов с вкраплениями кода для сбора данных. Получилась представленная ниже крошечная библиотека, идейно близкая к парсер-комбинаторам.

Итак, входной поток задается объектом-значением XmlReader. Неприятность в том, что этот объект несет в себе изменяемое состояние. Это ограничивает наши возможности по разбору. Вероятно, об откатах придется забыть.

Представим наш парсер в виде функции, которая по заданному объекту XmlReader возвращает прочитанные данные в случае успеха, либо сигнализирует о неудаче.

namespace Maritegra.Xml

open System.Xml

type XmlReader<'a> = XmlReader -> 'a option

Нужно поставить сразу условие. Если мы изменяем состояние объекта XmlReader, то тогда должны вернуть Some, т.е. успех. Наоборот, если функция парсера возвращает None, то тогда гарантируется, что состояние XmlReader не претерпело изменений. Следование этому условию делает разбор надежным, но заметно ограничивает наши возможности. Справедливый обмен.

В определении полиморфного типа XmlReader<’a> использована такая особенность дотнета, которая разделяет одноименные типы по параметрам. То есть, введенный тип XmlReader<’a> и стандартный тип XmlReader из System.Xml – это два разных типа. Далее полиморфный тип XmlReader<’a> я буду называть парсером, а, говоря о стандартном типе XmlReader, буду просто использовать его название.

Если сравнивать с другими парсерами, то введенный отличается тем, что аргумент функции, т.е. объект XmlReader, имеет состояние, а потому возвращать как результат его ненужно. Отсюда же возникает наложенное выше условие. В большинстве случаев мы не можем просто так прикоснуться к объекту XmlReader, не изменив его.

Ближе к делу. Очевидно, что парсер XmlReader<’a> является монадой. Сильно не буду углубляться в эту тему. Лишь приведу необходимые определения.

Вот, основные монадические функции, скрытые внутри отдельного модуля (новый F# обычно не позволяет определять глобальные функции вне модулей):

module XmlReaderImpl =

    let returnXR a = fun (r: XmlReader) -> Some a
    let bindXR m k = fun (r: XmlReader) -> match m r with | Some a -> (k a) r | None -> None
    let delayXR k  = fun (r: XmlReader) -> (k ()) r
    let zeroXR     = fun (r: XmlReader) -> Some ()
    let combineXR m1 m2 = fun (r: XmlReader) -> match m1 r with | Some () -> m2 r | None -> None

Теперь для монады нужен построитель, тип которого задается очень просто:

open XmlReaderImpl

type XmlReaderBuilder () =

    member x.Return (a)  = returnXR a
    member x.Bind (m, k) = bindXR m k
    member x.Delay (k)   = delayXR (k: unit -> XmlReader<'a>)
    member x.Zero ()     = zeroXR
    member x.Combine (m1, m2) = combineXR m1 m2

Завершающее определение построителя монады xmlreader:

[<AutoOpen>]
module XmlReaderWorkflow =

    let xmlreader = XmlReaderBuilder ()

Атрибут AutoOpen автоматически делает доступным определение построителя.

Сейчас создадим еще один XmlReader, но уже модуль. Язык F# превосходно справляется с таким смешением имен, но для этого модуль нужно снабдить следующим длинным атрибутом CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix). Поместим в этот модуль функции запуска run и отображения map. В комментариях указана сигнатура функций. Кроме того, модуль снабдим атрибутом RequireQualifiedAccess, который указывает на обязательность имени модуля при обращении к функциям.

[<RequireQualifiedAccess>]
[<CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix)>]
module XmlReader =

    // val run: XmlReader -> XmlReader<'a> -> 'a
    let run (r: XmlReader) m = 
        match m r with
        | Some a -> a
        | None -> failwithf "Invalid input data"

    // val map: ('a -> 'b) -> XmlReader<'a> -> XmlReader<'b>
    let map f m = fun (r: XmlReader) ->
        match m r with
        | Some a -> Some (f a)
        | None -> None

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

Начнем с простых комбинаторов, которые извлекают информацию об атрибутах. Они безболезненны и не меняют состояние объекта XmlReader. По заданному имени или порядковому номеру получаем значение атрибута, обернутое в монаду:

    // val attr: string -> XmlReader<string>
    let attr (name: string) = fun (r: XmlReader) -> Some <| r.GetAttribute (name)

    // val attri: int -> XmlReader<string>
    let attri (i: int) = fun (r: XmlReader) -> Some <| r.GetAttribute (i)

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

    // val text: XmlReader<string>
    let text = fun (r: XmlReader) -> Some <| r.ReadElementContentAsString ()

Более сложный случай – это разбор элемента. Комбинатор elem разбирает элемент с заданным именем, применяя для содержимого другой парсер. Если элемент не тот, то, не меняя состояния XmlReader, сразу возвращается None, как и было оговорено в изначальном условии, накладываемом на парсер.

    // val elem: string -> XmlReader<'a> -> XmlReader<'a>
    let elem (name: string) m = fun (r: XmlReader) ->
        if r.IsStartElement (name) then m r else None

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

    // val contents: XmlReader<unit> -> XmlReader<unit>
    let contents (m: XmlReader<unit>) = fun (r: XmlReader) ->
        if r.IsStartElement () then
            if not r.IsEmptyElement then
                let depth = r.Depth
                while r.Read () && (r.Depth > depth) do
                    if (r.Depth = 1 + depth) then 
                        m r |> ignore
            Some ()
        else
            None
            
    // val selectContents: XmlReader<'a> -> XmlReader<'a list>
    let selectContents (m: XmlReader<_>) = fun (r: XmlReader) ->
        if r.IsStartElement () then
            [ if not r.IsEmptyElement then
                let depth = r.Depth
                while r.Read () && (r.Depth > depth) do
                if (r.Depth = 1 + depth) then
                    match m r with
                    | Some a -> yield a
                    | None -> ()
            ] |> Some
        else None

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

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

module Operators =

    // val (+++): XmlReader<'a> -> XmlReader<'a> -> XmlReader<'a>
    let (+++) m1 m2 = fun (r: XmlReader) ->
        match m1 r with
        | Some a as n -> n
        | None -> m2 r

Библиотека закончена. Она содержится в пространстве имен Maritegra.Xml.

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

let document = 
    @"<struct>
        <items>
           <item id='1001' x='1'>10</item>
           <item id='1002' x='2'>20</item>
           <item id='1003' x='3'>30</item>
        </items>
        <links>
           <link source-id='1001' target-id='1003'>PuperLink</link>
           <link source-id='1001' target-id='1002'>WeakLink</link>
        </links>
      </struct>"

Задача состоит в извлечении информации из тегов item и link. Сделать это довольно просто:

open System
open System.Collections
open System.Collections.Generic
open System.IO
open System.Xml

open Maritegra.Xml
open Maritegra.Xml.Operators

type Item = Item of string * string * string
type Link = Link of string * string * string

let proc document =

    use reader = new XmlTextReader (new StringReader (document))
    
    let items = List<_> ()
    let links = List<_> ()
    
    (XmlReader.elem "struct" <|
        (XmlReader.contents <|
            (XmlReader.elem "items" <|
                (XmlReader.contents <|
                    (XmlReader.elem "item" <|
                        xmlreader {
                            let! id   = XmlReader.attr "id"
                            let! x    = XmlReader.attr "x"
                            let! text = XmlReader.text
                            items.Add (Item (id, x, text))
                        })))
            +++
            (XmlReader.elem "links" <|
                (XmlReader.contents <|
                    (XmlReader.elem "link" <|
                        xmlreader {
                            let! sourceId = XmlReader.attr "source-id"
                            let! targetId = XmlReader.attr "target-id"
                            let! text = XmlReader.text
                            links.Add (Link (sourceId, targetId, text))
                        })))))
    |> XmlReader.run reader

    (items, links)

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

let (items, links) = proc document

let sprintItem (Item (id, x, text)) = sprintf "Item (%s, %s, %s)" id x text
let sprintLink (Link (sid, tid, text)) = sprintf "Link (%s, %s, %s)" sid tid text

items |> Seq.map sprintItem
      |> Seq.reduce (fun s1 s2 -> s1 + ", " + s2)
      |> printfn "items = seq [%s]"

links |> Seq.map sprintLink
      |> Seq.reduce (fun s1 s2 -> s1 + ", " + s2)
      |> printfn "links = seq [%s]"

Итак, удалось довольно рутинный разбор XML втиснуть внутрь одной функции. На мой взгляд, получилось выразительно, хотя и несколько пестрит словом XmlReader. Используя вышеприведенный подход, можно разбирать довольно сложный XML с большой степенью вложенности, оставаясь в рамках одной функции или выражения. Конечно, метод не претендует на полноту. Например, пока не придумал, как разбирать текстовые поля, чередующиеся с тегами на одном уровне, но мне это и ненужно. Тем не менее, метод интересен тем, что XmlReader очень быстр и легковесен в отличие от того же XmlDocument. Правда стоит отметить, что для XmlDocument можно использовать такую чудесную вещь как активное сопоставление с образцом, что позволяет писать чрезвычайно наглядный и выразительный код, но там нужно предварительно полностью загрузить документ XML в промежуточное представление XmlDocument. В общем, нет в мире совершенства!