Intro

Прелюдия к компилятору

Введение

Началось всё с того, что в один прекрасный момент понадобилось мне разбирать строковые SQL-подобные выражения-фильтры (они же - WHERE clause в терминах SQL), и превращать их в .Net Expressions для дальнейшего использования во всяких LINQ запросах.

Например, выражение

Lenght = 3 and Value in (1, 2, 3) 

превращалось бы в Expression, описывающий следующую функцию

x => x.Length == 3 && (new int[] {1,2,3}).Contains(x.Value) 

Конечно, подразумевается, что у класса объекта x есть свойства Length и Value.

Начало

Сразу приходит в голову несколько вариантов решения поставленной задачи:

  • Разбирать строку регулярными выражениями и строить Expression по мере разбора
  • Писать свой разборщик с блэкджеком и прочими радостями
  • Использовать персер-генераторы, типа ANTLR, Lexx/Yacc и пр.
  • Воспользоваться специализированным инструментом - Irony
  • Использовать библиотеку монадных парсеров типа FParsec

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

Если внимательно посмотреть в каталог bin поставки F#, там можно обнаружить два исполняемых файла "fslex.exe" и "fsyacc.exe", которые, как и многое другое, позаимствованы из OCaml (там они назывались OcamlLex и OcamlYacc соответственно). С документацией по этим программам можно ознакомиться вот здесь. (Если уж говорить совсем откровенно, то и OCaml реализации этих утилит не являются первичными, интересующиеся могут найти нужную информацию здесь и здесь).

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

Реализация

Начнём с того, что договоримся о требованиях к выражениям, которые будем разбирать:

  • Выражение - это некоторая операция над свойством объекта
  • Под свойством объекта может пониматься цепочка свойств, например person.Name.Length
  • Операции над свойствами включают:
    • Операции сравнения (=, != или <>, >, >=, <, <=)
    • Строковые операции (Contains, StartsWith, EndsWith)
    • Операция включения (In)
  • Выражения могут объединяться при помощи логических операций Or и And
  • Выражения или группы выражений могут заключаться в круглые скобки

Опишем то же самое на F# при помощи Discriminated Union.

type LogOp =
    | Or
    | And

type Cond =
    | Eq
    | Neq
    | Greater
    | Less
    | GreaterOrEqual
    | LessOrEqual
    | Contains
    | StartsWith
    | EndsWith
    | In

type Item =
    | Prop of string array

type Val =
    | Number of int
    | Str of string
    | Numbers of int array
    | Strs of string array

type Clause =
    | Simple of Item * Cond * Val
    | Complex of Clause * LogOp * Clause

Как видите, ничего сверх того, что мы уже и так написали по-русски в списке выше. Разве что, поддерживается ограниченный набор типов обрабатываемых значений (Int32 и String), которых, впрочем, вполне достаточно для наших целей.

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

{
module Wepr.Lexer

open System
open System.Text
open Wepr
open Wepr.Parser

let toString bs =   Encoding.ASCII.GetString(bs)
let unquote (s:String) = s.[1..(s.Length-2)]
let splitString (sep:String) (s:String) = s.Split([|sep|], StringSplitOptions.RemoveEmptyEntries)
let trimString (s:String) = s.Trim()    
  
}

let whitespace = ['\t' ' ']
let quotes = ['\'']
let literal = ['a'-'z' 'A'-'Z']+
let prop = ['a'-'z' 'A'-'Z' '.']+
let number = ['0'-'9']+
let quoted = ('\'' [^'\'']* '\'')

let in_strings = (quoted (',' [' ']+ quoted)*)+
let in_numbers = (number (',' [' ']+ number)*)+

rule token = parse
      whitespace    { token lexbuf }
    | "AND" | "and" { AND }
    | "OR"  | "or"  { OR }
    | '('           { LPAREN }
    | ')'           { RPAREN }
    | "="           { EQ }
    | "!="          { NEQ }
    | "<>"          { NEQ }
    | ">"           { GREATER }
    | "<"           { LESS }
    | ">="          { GREATEROREQ }
    | "<="          { LESSOREQ }
    | "Contains"    { CONTAINS }
    | "StartsWith"  { STARTSWITH }
    | "EndsWith"    { ENDSWITH }
    | number        { INT (toString lexbuf.Lexeme |> Int32.Parse) }    
    | quoted        { QUOTED (toString lexbuf.Lexeme |> unquote) }
    
    | ("IN" | "in") { IN }
    | in_strings    {         
        STRINGS (toString lexbuf.Lexeme |> splitString "," |> Array.map (trimString >> unquote) )}
    | in_numbers    {
        NUMBERS (toString lexbuf.Lexeme |> splitString "," |> Array.map (trimString >> Int32.Parse) )}       
                    
    | prop          { PROP (toString lexbuf.Lexeme |> splitString ".") }
    | eof           { EOF }

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

%{
    open Wepr
%}

%start Start
%token <string> STRING
%token <string> QUOTED
%token <string array> PROP
%token <string array> STRINGS
%token <int array> NUMBERS
%token <int> INT
%token LPAREN RPAREN DOT
%token AND OR
%token EQ NEQ LESS GREATER LESSOREQ GREATEROREQ CONTAINS STARTSWITH ENDSWITH IN
%token EOF
%type <Clause> Start

%%

Start: Clause { $1 }

Clause:
      LPAREN Clause RPAREN      { $2 }
    | Clause AND Clause         { Complex ($1, And, $3) }
    | Clause OR Clause          { Complex ($1, Or, $3) }
    | Field EQ Literal          { Simple ($1, Eq, $3) }
    | Field NEQ Literal         { Simple ($1, Neq, $3) }
    | Field LESS Literal        { Simple ($1, Less, $3) }
    | Field GREATER Literal     { Simple ($1, Greater, $3) }
    | Field LESSOREQ Literal    { Simple ($1, LessOrEqual, $3) }
    | Field GREATEROREQ Literal { Simple ($1, GreaterOrEqual, $3) }
    | Field CONTAINS Literal    { Simple ($1, Contains, $3) }
    | Field STARTSWITH Literal  { Simple ($1, StartsWith, $3) }
    | Field ENDSWITH Literal    { Simple ($1, EndsWith, $3) }
    | Field IN LPAREN STRINGS RPAREN { Simple ($1, In, (Strs $4)) }
    | Field IN LPAREN NUMBERS RPAREN { Simple ($1, In, (Numbers $4)) }

Field:
    | PROP                      { Prop ($1) }
    
Literal:
      QUOTED                    { Str $1 }
    | INT                       { Number $1 }  
    | STRINGS                   { Strs $1 }
    | NUMBERS                   { Numbers $1 }

Парсер в свою очередь описывает варианты группировки токенов и правила построения абстрактного синтаксического дерева из них.

Путём нехитрых манипуляций, а именно, передачи этих файлов на вход соответствующим утилитам, получаем вполне работоспособный код парсера и лексера, которые умеют превращать строку в экземпляр типа Clause. Теперь осталось только обработать этот Clause таким образом, чтобы сформировать Expression Tree, которое может обрабатываться стандартными средствами .Net.

let rec toExpr (par:ParameterExpression) (clause: Clause) =
    let constExpr (x:'a) =
        Expression.Constant(x, typeof<'a>) |> asExpr
    let callExpr (i:Expression) (m:String) (p:Expression) =
        Expression.Call(i, m, Array.empty, p)        
    let arrExpr (xs:'a array) =
        Expression.NewArrayInit(typeof<'a>, Array.map (constExpr >> asExpr) xs) |> asExpr
    let inExpr (vEx:Expression) (arrEx:Expression) =
        Expression.Call(typeof<Enumerable>, "Contains", [|vEx.Type|], arrEx, vEx) |> asExpr

    match clause with
    | Simple (l, op, r) -> 
        let lEx = toProperty par l
        let rEx = match r with
                    | Number n      -> constExpr n
                    | Str s         -> constExpr s
                    | Numbers ns    -> arrExpr ns
                    | Strs ss       -> arrExpr ss
            
        let equality (f:(Expression * Expression) -> BinaryExpression) =
            f (lEx, rEx) |> asExpr
        let call name =
            callExpr lEx name rEx |> asExpr
        match op with
        | Eq                -> equality Expression.Equal
        | Neq               -> equality Expression.NotEqual
        | Greater           -> equality Expression.GreaterThan
        | Less              -> equality Expression.LessThan
        | GreaterOrEqual    -> equality Expression.GreaterThanOrEqual
        | LessOrEqual       -> equality Expression.LessThanOrEqual
        
        | Contains          -> call "Contains"
        | StartsWith        -> call "StartsWith"
        | EndsWith          -> call "EndsWith"        
        | In                -> inExpr lEx rEx
        
    | Complex (l, logOp, r) ->
        let lEx = toExpr par l
        let rEx = toExpr par r
        let logical (f: Expression * Expression -> BinaryExpression) =
            f (lEx, rEx) |> asExpr
        match logOp with
        | Or        -> logical Expression.Or
        | And       -> logical Expression.And

Давайте посмотрим на код повнимательнее. В самом начале пара вспомогательных функций, которые не имеют отношения к основной задаче, и могут быть вынесены наружу. Следом же за этими функциями следует match clause, то есть сравнение с образцом. Так как тип Clause является алгебраическим типом данных (aka discriminated union или размеченным объединением), то для полной его обработки нам надо реализовать функцию toExpr для каждого конструктора: Simple и Complex. Так как Complex является рекурсивной веткой объявления типа, то и обработка его будет использовать рекурсивный вызов для правого и левого подвыражений.

Этот код работает, но чего-то не хватает. Явная рекурсия опять же, а в функциональном программировании не принято выпячивать рекурсию, если можно от неё избавиться. Тут на помощь нам придёт замечательная статья "Катаморфизм в F#", особенно её часть про "Свёртку на обобщённых размеченных объединениях".

Напомню, что разработанный нами тип Clause как раз и является тем самым размеченным объединением. Так что никто не мешает нам реализовать для него операцию свёртки, которая будет выглядеть вот так:

let foldClause simpleF complexF clause =
        let unitem = function
            | Prop ss -> ss
        let rec loop clause cont =
            match clause with
            | Simple (item, condition, value) ->
                cont (simpleF (unitem item) condition value)
            | Complex (l, op, r) ->
                loop l (fun lval ->
                loop r (fun rval ->
                cont (complexF lval op rval)))
        loop clause id

В результате мы имеем функциональный аналог паттерна Visitor для нашего дерева выражений. Передавая в foldClause функции обработки для "простой" и "составной" форм выражения мы можем получить какое угодно преобразование исходной структуры, в том числе и преобразование в Expression Tree.

let toExpr (par:ParameterExpression) (clause: Clause) =
    let constExpr (x:'a) =
        Expression.Constant(x, typeof<'a>) |> asExpr
    let callExpr (i:Expression) (m:String) (p:Expression) =
        Expression.Call(i, m, Array.empty, p)        
    let arrExpr (xs:'a array) =
        Expression.NewArrayInit(typeof<'a>, Array.map (constExpr >> asExpr) xs) |> asExpr
    let inExpr (vEx:Expression) (arrEx:Expression) =
        Expression.Call(typeof<Enumerable>, "Contains", [|vEx.Type|], arrEx, vEx) |> asExpr
            
    let simpleF props condition value =
        let lEx = toProperty par props
        let rEx = match value with
                    | Number n      -> constExpr n
                    | Str s         -> constExpr s
                    | Numbers ns    -> arrExpr ns
                    | Strs ss       -> arrExpr ss
        let equality (f:(Expression * Expression) -> BinaryExpression) =
            f (lEx, rEx) |> asExpr
        let call name =
            callExpr lEx name rEx |> asExpr
        match condition with
        | Eq                -> equality Expression.Equal
        | Neq               -> equality Expression.NotEqual
        | Greater           -> equality Expression.GreaterThan
        | Less              -> equality Expression.LessThan
        | GreaterOrEqual    -> equality Expression.GreaterThanOrEqual
        | LessOrEqual       -> equality Expression.LessThanOrEqual
        
        | Contains          -> call "Contains"
        | StartsWith        -> call "StartsWith"
        | EndsWith          -> call "EndsWith"        
        | In                -> inExpr lEx rEx

    let complexF left logOp right =
        let logical (f: Expression * Expression -> BinaryExpression) =
            f (left, right) |> asExpr
        match logOp with
        | Or        -> logical Expression.Or
        | And       -> logical Expression.And

    Clause.Fold simpleF complexF clause

Если сравнить эту реализацию с предыдущей, то можно увидеть, что не так и много изменилось: обработка “простого” и “составного” вариантов выражений теперь не скомкана внутри одного гигантского блока match, а разнесена по двум независимым функциям, каждая из которых может при желании быть повторно использована и оттестирована, кроме того мы избавились от явной рекурсии и получили универсальный механизм обхода /Clause.

Вот, например, как можно реализовать тот же паттерн Visitor на основе свёртки для тех, кому более близок объектно-ориентированный подход.

type IClauseVisitor<'TState> = 
    abstract member Simple : String array * Condition * Val -> 'TState
    abstract member Complex : 'TState * LogicalOperation * 'TState -> 'TState

let visitClause (visitor:#IClauseVisitor<'TState>) clause =
    let simpleF props (cond:Cond) value = visitor.Simple(props, (cond.ToEnum()), value)
    let complexF left (logOp:LogOp) right = visitor.Complex(left, (logOp.ToEnum()), right)
    Clause.Fold simpleF complexF clause

Заключение

Ну и напоследок, небольшой бонус. Не так давно, Scott Hanselman написал в своём блоге о DynamicQueryable, в результате применения которого становятся возможными вызовы вроде такого:

items.Where("p.Id = 2 And p.OtherField > 4.0")

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

module Extensions =

    // F# extension methods
    type System.Linq.IQueryable<'TSource> with
    
        member this.Where (s:String) =
            let expr = Wepr.GetExpression<'TSource> s :?> Expression<Func<'TSource, bool>>
            Queryable.Where(this, expr)
            
    type System.Collections.Generic.IEnumerable<'TSource> with
    
        member this.Where (s:String) =
            let dlg = Wepr.Compile<'TSource> s
            let predicate (arg: 'TSource) = dlg.DynamicInvoke arg :?> bool
            Enumerable.Where(this, predicate)
            
[<System.Runtime.CompilerServices.Extension>]            
module QueryableExtensions =
    open Extensions
    // C#-visible extension methods
    [<System.Runtime.CompilerServices.Extension>]
    let Where (src:IQueryable<'a>, where:String) = src.Where(where)
    
[<System.Runtime.CompilerServices.Extension>]            
module EnumerableExtensions =    
    open Extensions
    [<System.Runtime.CompilerServices.Extension>]
    let Where (src:IEnumerable<'a>, where:String) = src.Where(where)

При помощи этих методов расширений становится возможным следующий код:

string[] strings = new string[] { "1", "123", "12", "12ab", "a", "ab", "abc" };
var res = strings.Where("Length >= 3");

Весь исходный код доступен по адресу: http://bitbucket.org/moiseev/wepr

Updated

Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.