パーサージェネレーターで柔軟な記述式フィルタを実装した話

ogp

はじめに

この記事はenechain Advent Calendar 2024の19日目の記事になります。

enechainでSWEをしている神楽坂です。業務では、電力の取引仲介をするブローカーが正確・高速にお客様の注文（ナンバー）を管理するための社内ツールを開発しています。

電力という商品は株式などと比較して、どのエリア・時間帯のものか、どのように電力を受渡するか、燃調はあるか、ある場合の具体的な式は何かといった、多種多様な属性が付随します。そのようなナンバーを素早く正確に管理するためには、特定の属性を持つものをフレキシブルにフィルタリングできる機能が求められます。そこで price>10 のような記述式のクエリを使ってナンバーをフィルタリングできる機能を実装したので、本記事ではその実現方法について述べます。

なお、実際に業務で扱っている電力ドメインを例にしてしまうと、本題とは異なる部分で大量の補足説明が必要となってしまうため、以下ではゲームのストアやライブラリを検索するユースケースを例に説明していきます。

クエリのフォーマット

まず、フィルタリングに使うクエリのフォーマットを定義しなければなりません。調べたところデファクトスタンダードと呼べるほどの標準は存在していなそうだったため、今回のやりたいことにちょうどマッチしているAIP-160を採用することにしました。

AIPはAPI Improvement Proposalsの略で、Googleが提供しているAPIのデザインドキュメントをまとめたものです。 AIP-160はその中でも記述式のフィルタリングのフォーマットを定めています。実際にGoogleが提供するAPIでも活用されており、たとえばGCEのリージョンリソースへの操作一覧APIにはAIP-160に準拠した filter パラメータを受け取る設計になっています。

また、AIP-160はEBNFも定義されており、パーサーを実装するための元情報として活用できる点も採用の理由の1つです。

パーサー実装における技術選定

筆者は別のプロダクトでlexer/parserを直接実装する機会に恵まれましたが、それは楽しくも辛い道のりでした。今回は既にEBNFが定義されていることもあり、自前で1から実装するよりはパーサージェネレーターを活用する方針としました。我々のプロダクトはGoで記述されているため、はGoのコードとして出力できる機能を持つ中で、以下の理由からANTLRを採用しました。

ANTLRの定義ファイルg4の文法がEBNFと似ていること
メジャーで利用者が多く、情報が見つけやすかったり、基本的な問題は解決されていることが期待できること
lexerやvisitorも一緒にコード生成してくれるので便利なこと
筆者がJava(正確にはAndroid)育ちなため、親しみがあったこと

API-160のEBNFと文法はほぼ一緒ですが、ちょっとした違いがあるので紹介します。

0回また1回の繰り返しはEBNFでは次のように表現されますが

filter
    : [expression]
    ;

ANTLRでは正規表現ライクに次のように表現します。

filter
    : expression?
    ;

また、0回以上の繰り返しもEBNFでは次のように表現しますが

term
    : [(NOT WS | MINUS)] simple
    ;

ANTLRでは次のように表現します。

term
    : ('NOT' | '-')? simple
    ;

なお、lexerの定義についてはAIP-160のEBNFには含まれていないため、どんな文字種を受けつけたいかに応じて適宜定義しましょう。また、IntelliJ IDEAやVisual Studio CodeなどにはANTLRのプラグイン・拡張が存在しており、クエリが実際にどのようなツリーにパースされるのかを確認できます。たとえば、 price < 2000 AND winter_sale と入力すると、次のようなツリーが表示されます。

意図しない挙動をするクエリがあった場合、このツリーを見ながらデバッグすることで、問題を特定しやすくなります。

実装方法

パーサーのコード生成

まずはEBNFを元に作成したANTLRの定義ファイルからGoのコードを生成します。 GitHubにDockerfileが公開されているので、イメージをビルドします（残念ながらDocker Hubなどにアップロードはされていません）。

$ docker build -t antlr/antlr4 --platform linux/amd64 .

次に、定義ファイル(.g4)からコード生成させます。

$ docker run -it --rm -v $(pwd):/workspace -w /workspace antlr/antlr4 -Dlanguage=Go -package gen -visitor -o gen antlr/*.g4

-package は生成されるGoコードのpackage名、 -o はコードの生成先ディレクトリ、引数は定義ファイルのglobパターンです。 antlrコマンドは生成先ディレクトリに定義ファイルまでのパスを切る仕様になっているため、先の例だと gen/antlr にコードが出力されます。

また、 -visitor はvisitorパターンを使うためのオプションです。 visitorパターンを使わない場合、ANTLRはパース結果の抽象構文木(AST)を深さ優先でwalkし、各ノードに入ったときと出たとき(子を再帰的に探訪し終わったとき)にlistenerのコールバックを呼び出すコードを生成します。シンプルに使える一方で、探索中の中間結果の保持を自前で実装しなければならない点が大変なため、今回はvisitorパターンを採用しました。

ANTLRのvisitorについて

visitorパターンはオブジェクト指向のデザインパターンの一種で、アルゴリズムをオブジェクトの構造から分離させるためのものです。今回のように、ツリーのようなデータ構造の探訪にもよく用いられます。

生成されるvisitorは、具体的には次のような構造のインターフェースです。

type FilteringVisitor interface {
    antlr.ParseTreeVisitor

    // EBNFでは filter として定義されている、ルート要素に探訪したときに呼び出される
    VisitFilter(ctx *FilterContext) interface{}

    // EBNFでは expression として定義されている要素に探訪したときに呼び出される
    VisitExpression(ctx *ExpressionContext) interface{}
 
    // 以下、ノードの種類ごとのVisitメソッドが続く...
}

また、パース結果のASTにアクセスするため、antlr4-goモジュールに定義されている次のインターフェースも満たす必要があります。

type ParseTreeVisitor interface {
    Visit(tree ParseTree) interface{}
    VisitChildren(node RuleNode) interface{}
    VisitTerminal(node TerminalNode) interface{}
    VisitErrorNode(node ErrorNode) interface{}
}

これらのメソッドを実装した構造体を定義し、パース結果のAST (ParseTree) を引数に Visit メソッドを呼び出すことで処理を実行させます。各 Visit 系メソッドはすべて any(=interface{}) を戻り値として返していますが、これは該当するノードを探訪し終えた時点での中間結果です。 VisitXXX では子ノードを探訪してその結果を取得し、自身のノードの役割に沿って結果を加工・統合したうえで返し、それが再帰的に実行されることでルートノードの戻り値が最終的な結果となります。

visitorパターンはデータ構造とアルゴリズムを分離するためのものですから、同じASTに対して異なる実装のvisitorで探訪すると、異なる結果を得られます。本記事ではAIP-160のクエリからSQLのWHERE句を生成するvisitorと、インメモリのコレクションをフィルタリングするvisitorの実装を紹介します。

SQLのWHERE句を生成するvisitor

まずはvisitorの戻り値の型を定義します。SQLのWHERE句は文字列とプレースホルダーにいれる引数で構成されるので、次のように書けます。

const placeholder = "$PLACEHOLDER"

type WhereClause struct {
    clause string
    args   []any
}

func (wc *WhereClause) Clause() string {
    if wc == nil || wc.clause == "" {
        return ""
    }

    // プレースホルダをPostgres仕様に置き換え
    count := 1
    replaced := wc.clause
    for {
        index := strings.Index(replaced, placeholder)
        if index == -1 {
            break
        }
        replacement := fmt.Sprintf("$%d", count)
        replaced = replaced[:index] + replacement + replaced[index+len(placeholder):]
        count++
    }

    return replaced
}

func (wc *WhereClause) Args() []any {
    if wc == nil {
        return nil
    }
    return wc.args
}

func (wc *WhereClause) aggregate(other *WhereClause) *WhereClause {
    if wc == nil {
        return other
    }
    if other == nil {
        return wc
    }
    return &WhereClause{
        clause: wc.clause + other.clause,
        args:   append(wc.args, other.args...),
    }
}

我々のチームではPostgreSQLを利用しており、プレースホルダーは $1, $2, ... という形式になるため、探訪中は $PLACEHOLDER という文字列に置き換えておいて、最後に連番を振っています。

次は ParseTreeVisitor インターフェースの実装です。

func (v *visitor) Visit(tree antlr.ParseTree) any {
    return tree.Accept(v)
}

func (v *visitor) VisitChildren(node antlr.RuleNode) any {
    var res *WhereClause
    for i := range node.GetChildCount() {
        c, ok := node.GetChild(i).(antlr.ParseTree)
        if !ok {
            continue
        }

        if childRes, ok := c.Accept(v).(*WhereClause); ok {
            res = res.aggregate(childRes)
        }
    }
    return res
}

func (v *visitor) VisitTerminal(node antlr.TerminalNode) any {
    tokenType := node.GetSymbol().GetTokenType()

    switch tokenType {
    case gen.FilteringParserEOF:
        return nil
    // 左右にスペースが必要な演算子
    case gen.FilteringParserNOT, gen.FilteringParserAND, gen.FilteringParserOR:
        return &WhereClause{clause: " " + node.GetText() + " ", args: nil}
    default:
        return &WhereClause{clause: node.GetText()}
    }
}

func (v *visitor) VisitErrorNode(node antlr.ErrorNode) any {
    return nil // 実際にプロダクトに組み込む際はちゃんとエラーハンドリングしよう
}

tree の Accept メソッドにvisitor自身を渡すことで、そのノードを探訪します。そして VisitChildren では親ノードとしてのデフォルトの振る舞いを定義します。ここでは子ノードを順番に探訪し、その結果を集約するという挙動です。

VisitTerminal では、終端ノード（葉ノード）の探訪時に呼ばれるメソッドです。基本的にはそのまま文字列としてクエリにしますが、NOT / AND / OR については、SQLとして動作させるために演算子の左右にスペースが必要なため付与するようにしています。また、クエリに使う属性名とSQLのカラム名が異なる場合、ここで変換を実装します。

次に各ノード種別ごとの VisitXXX メソッドを実装します。特別な処理が必要なければ、単にデフォルト実装である VisitChildren を呼び出せばOKです。

func (v *visitor) VisitFilter(ctx *gen.FilterContext) any {
    return v.VisitChildren(ctx)
}

Goはオブジェクト指向言語ではなく、構造体はクラスではないためデフォルト実装を継承により省略できません。素直にコピペしていきましょう。

デフォルトの VisitChildren では不足な実装の代表が OR の取り扱いです。ドキュメントに記載のとおり、AIP-160では AND より OR のほうが優先されるため、たとえば a AND b Or c は a AND (b OR c) と解釈されます。 SQLでは AND のほうが優先されるため、WHERE句に変換する際には OR を優先するようにカッコを入れる必要があります。

func (v *visitor) VisitFactor(ctx *gen.FactorContext) any {
    childResult, ok := v.VisitChildren(ctx).(*WhereClause)
    if !ok || childResult == nil {
        return childResult
    }

    if ctx.GetOp() != nil && ctx.GetOp().GetTokenType() == gen.FilteringParserOR {
        return &WhereClause{
            clause: fmt.Sprintf("(%s)", childResult.Clause()),
            args:   childResult.Args(),
        }
    }

    return childResult
}

OR が1つも含まれないクエリも考えられるため、 nil チェックは怠らないようにしましょう。

同様にSQLに存在しない機能をサポートしたい場合、適切に VisitXXX メソッドを実装していくことになります。たとえばHAS演算子 : を取り扱いたい場合、 VisitRestriction メソッド内で comparator が : の場合の処理を追加します。これについては、ユースケースに応じて必要な機能を実装することをオススメします。 AIP-160に従うことが目的ではないため、本来実現したいことが達成できれば十分です。

インメモリのコレクションをフィルタリングするvisitor

次に、インメモリのコレクションをフィルタリングするvisitorを考えます。方針としては、クエリのパース結果のASTを条件式の木構造に変換し、コレクションの各要素が条件を満たすかを調べることになるでしょう。フィルタリング対象の構造体は以下とします。

type Game struct {
    Price int
    InSale bool
}

まず、条件式の木構造は次のようなコードになります。

type Predicate[T any] interface {
    Eval(x T) bool
}

type PredicateFunc[T any] func(T) bool

func (f PredicateFunc[T]) Eval(x T) bool {
    return f(x)
}

type And[T any] struct {
    Predicates []Predicate[T]
}

func (a And[T]) Eval(x T) bool {
    for _, predicate := range a.Predicates {
        if !predicate.Eval(x) {
            return false
        }
    }
    return true
}

type Or[T any] struct {
    Predicates []Predicate[T]
}

func (o Or[T]) Eval(x T) bool {
    for _, predicate := range o.Predicates {
        if predicate.Eval(x) {
            return true
        }
    }
    return false
}

type Not[T any] struct {
    Predicate Predicate[T]
}

func (n Not[T]) Eval(x T) bool {
    return !n.Predicate.Eval(x)
}

func Filter[T any](items []T, predicate Predicate[T]) []T {
    var result []T
    for _, item := range items {
        if predicate.Eval(item) {
            result = append(result, item)
        }
    }
    return result
}

クエリはvisitorによってこの Predicate に変換され、 Filter 関数に渡すことでフィルタリングを実現します。

次に ParseTreeVisitor インターフェースの実装です。

func (v *visitor) Visit(tree antlr.ParseTree) interface{} {
    return tree.Accept(v)
}

func (v *visitor) VisitChildren(node antlr.RuleNode) interface{} {
    for i := range node.GetChildCount() {
        c, ok := node.GetChild(i).(antlr.ParseTree)
        if !ok {
            continue
        }
        if childRes := c.Accept(v); childRes != nil {
            return childRes
        }
    }
    return nil
}

func (v *visitor) VisitTerminal(node antlr.TerminalNode) interface{} {
    switch node.GetSymbol().GetTokenType() {
    case gen.FilteringParserIDENTIFIER:
        switch node.GetText() {
        case "sale":
            return PredicateFunc[Game](func(x Game) bool { return x.InSale })
        default:
            return nil
        }
    default:
        return nil
    }
}

func (v *visitor) VisitErrorNode(node antlr.ErrorNode) interface{} {
    return nil // 実際にプロダクトに組み込む際はちゃんとエラーハンドリングしよう
}

探訪の結果は Predicate そのものです。 VisitTerminal では sale のように演算子を含まずに特定のキーワードのみで検索条件を表すものをハンドリングします。条件式としては複雑だが、ドメイン上の言葉として一言で表せるものなどは準備しておくとクエリの使い勝手が向上するのでオススメです。

そして論理演算関連の VisitXXX は次のように実装できます。

func (v *visitor) getChildPredicates(ctx antlr.ParserRuleContext) []Predicate[Game] {
    var predicates []Predicate[Game]
    for i := range ctx.GetChildCount() {
        c, ok := ctx.GetChild(i).(antlr.ParseTree)
        if !ok {
            continue
        }
        if childRes, ok := c.Accept(v).(Predicate[Game]); ok && childRes != nil {
            predicates = append(predicates, childRes)
        }
    }
    return predicates
}

func (v *visitor) VisitExpression(ctx *gen.ExpressionContext) interface{} {
    predicates := v.getChildPredicates(ctx)
    switch len(predicates) {
    case 0:
        return nil
    case 1:
        return predicates[0]
    default:
        return And[Game]{Predicates: predicates}
    }
}

func (v *visitor) VisitFactor(ctx *gen.FactorContext) interface{} {
    predicates := v.getChildPredicates(ctx)
    switch len(predicates) {
    case 0:
        return nil
    case 1:
        return predicates[0]
    default:
        return Or[Game]{Predicates: predicates}
    }
}

func (v *visitor) VisitTerm(ctx *gen.TermContext) interface{} {
    if ctx.NOT() != nil && ctx.NOT().GetSymbol().GetTokenType() == gen.FilteringParserNOT {
        if childRes, ok := ctx.Simple().Accept(v).(Predicate[Game]); ok && childRes != nil {
            return Not[Game]{Predicate: childRes}
        }
    }
    return v.VisitChildren(ctx)
}

AND OR NOT に対応する expression factor term の Visit メソッドでそれぞれ該当の Predicate に変換します。これらの論理演算式がなくても、結果のASTには AND ノードなどが含まれうる点に注意が必要です。その場合は子ノードが1つだけになるので、単に子の結果を返すようにします。

最後に price の比較を実装します。

func (v *visitor) VisitRestriction(ctx *gen.RestrictionContext) interface{} {
    // 演算子なしの場合は単に子の結果を使う
    if ctx.Comparator() == nil || ctx.Arg() == nil {
        return v.VisitChildren(ctx)
    }

    // 演算子あり
    if ctx.Comparable() != nil && ctx.Comparator() != nil && ctx.Arg() != nil {
        switch ctx.Comparable().GetText() {
        case "price":
            argText := ctx.Arg().GetText()
            argValue, _ := strconv.Atoi(argText) // 数字に変換

            switch ctx.Comparator().GetText() {
            case "<":
                return PredicateFunc[Game](func(x Game) bool { return x.Price < argValue })
            case "<=":
                return PredicateFunc[Game](func(x Game) bool { return x.Price <= argValue })
            case ">":
                return PredicateFunc[Game](func(x Game) bool { return x.Price > argValue })
            case ">=":
                return PredicateFunc[Game](func(x Game) bool { return x.Price >= argValue })
            case "=", "==":
                return PredicateFunc[Game](func(x Game) bool { return x.Price == argValue })
            case "!=":
                return PredicateFunc[Game](func(x Game) bool { return x.Price != argValue })
            }
        default:
            return nil
        }
    }

    return v.VisitChildren(ctx)
}

エラーハンドリングは諸々サボっていますが、 price > 500 のような比較式は restriction が対応するノードで、 comparable comparator arg がそれぞれ price > 500 に対応します。よってそれを元に Predicate を返すようにすれば、比較を実装できます。

今回は簡単のため Visit メソッドに直接分岐を書いていますが、数字との比較を複数の属性で行うなら比較用の Predicate 実装を作ったりなど、共通化を図るのも一案です。また、我々のチームではそこまでやっていませんが、フィルタリングに使える属性があまりにも多い場合、visitorの実装をも独自にコード生成させるといったアプローチも考えられるでしょう。機械的な実装が中心になるため、自動生成との相性は良いはずです。