二項演算子のASTを参考にした動的なフィルターのデータ構造

この記事はDeNA 21 新卒 ×22 新卒内定者 Advent Calendar 2021の 1 日目の記事です。

こんにちは、@p1assです。

いよいよDeNA 21 新卒 ×22 新卒内定者 Advent Calendar 2021が始まります 🙌
今年は新卒と内定者によるこの Advent Calendar と DeNA のエンジニアが担当するDeNA Advent Calendar 2021の 2 種類があるので、どちらもぜひチェックしてください！ （執筆時点では新卒 Advent Calendar はまだ埋めてないですがこれから埋まっていくはず...!）

さて、ここからは本題に入っていきます。

世の中には何らかのコレクションから条件に一致するものをフィルターする処理がよくあります。 例えば、「ユーザ一覧の中から年齢が一定以上の人のみを表示する」などです。(こういった条件をこれ以降「フィルター条件」と呼びます。)

このようなフィルター条件は 1 つであれば簡単ですが、複数の条件が組み合わさると少しずつ複雑になっていきます。 また、これらの条件がプログラムの中に静的に埋め込まれるのではなく、エンドユーザーのリクエストによって動的に変化すると、より面倒になってきます。

今回はいくつかのフィルター条件を自由自在に組み合わせて新たな合成フィルター条件を作り出すためのデータ構造を紹介します。 デザインパターンを知っている人にとっては既知の構造ですが自由度を保ちつつ複雑なフィルター条件を実装できるので、参考になれば幸いです。

想定する要件

文章を読みやすくするために、具体例を見せつつ今回やりたいことを説明します。

今回は Twitter API から取得したユーザ一覧データからフィルター条件に一致するユーザーの一覧を返す関数を実装したいです。 ただし、フィルター条件はプログラムの中で静的に記述されるのではなく、エンドユーザーからのリクエストによって動的に変化します。 また、エンドユーザーは複数のフィルター条件を AND・OR で組み合わせることができます。 Web 上でエンドユーザが適用したいフィルター条件にチェックボックスをつけるイメージですね。

フィルター条件が動的なため、プログラムでもフィルター条件を動的に生成して扱う必要があります。

// extractFilteredUsers は引数で渡されたユーザの中から条件に一致するユーザのsliceを返す
// TODO: 引数でフィルター条件を渡せるようにする
func extractFilteredUsers(users []twitter.User) []twitter.User {
  // TODO: フィルター条件の扱いを考える
  return users
}

AND や OR も１つのフィルター条件として扱うデータ構造

先述の要件に対して私が書いたのは次のようなコードです。

type FilterCondition interface {
	filter(user twitter.User) bool
}

// NameContainFilter はFilterConditionを実装する構造体
// エンドユーザーが指定できるフィルター条件の一例
type NameContainFilter struct {
	containWord string
}

func (f *NameContainFilter) filter(user twitter.User) bool {
	return strings.Contains(user.Name, f.containWord)
}

// ANDFilter はleftとright両方を満たしているか確認する
type ANDFilter struct {
	left  FilterCondition
	right FilterCondition
}

func (f *ANDFilter) filter(user twitter.User) bool {
	return f.left.filter(user) && f.right.filter(user)
}

// ORFilter はleftとrightのいずれかを満たしているか確認する
type ORFilter struct {
	left  FilterCondition
	right FilterCondition
}

func (f *ORFilter) filter(user twitter.User) bool {
	return f.left.filter(user) || f.right.filter(user)
}

// extractFilteredUsers は引数で渡されたユーザの中から条件に一致するユーザのsliceを返す
func extractFilteredUsers(users []twitter.User, filterCondition FilterCondition) []twitter.User {
	var filtered []twitter.User
	for _, user := range users {
		if filterCondition.filter(user) {
			filtered = append(filtered, user)
		}
	}
	return filtered
}

まず、FilterCondition としてフィルター条件を表す interface を定義します。 そして、それを実装する形でNameContainFilterというフィルター条件を一例として実装しています。

鍵になるのが、ANDFilter や ORFilter で、これらも同様に FilterCondition を実装しています。 このように実装することで、任意の FilterCondition を複数合成して、複雑な FilterCondition を生成できます。

func TestFilterCondition(t *testing.T) {
	users := []twitter.User{
		{Name: "山田 太郎"},
		{Name: "山田 次郎"},
		{Name: "佐藤 一郎"},
	}

	var filterCondition FilterCondition

	// 名前に「太郎」か「佐藤」が含まれるユーザを抜き出すフィルター条件
	filterCondition = &ORFilter{
		left:  &NameContainFilter{containingWord: "太郎"},
		right: &NameContainFilter{containingWord: "佐藤"},
	}

	expect := []twitter.User{
		{Name: "山田 太郎"},
		{Name: "佐藤 一郎"},
	}

	got := extractFilteredUsers(users, filterCondition)

	if !reflect.DeepEqual(got, expect) {
		t.Errorf("extractFilteredUsers does not matched")
	}
}

さらに ORFilter や ANDFilter も FilterCondition を満たしていることから、これらをネストしてさらに複雑なフィルター条件を作ることもできます。

nestedFilter := &ANDFilter{
  left: &ORFilter{
    left:  &NameContainFilter{containingWord: "山田"},
    right: &NameContainFilter{containingWord: "佐藤"},
  },
  right: &ORFilter{
    left:  &NameContainFilter{containingWord: "太郎"},
    right: &NameContainFilter{containingWord: "次郎"},
  },
}

このように、AND や OR も含めて統一した interface で扱うことで、柔軟にフィルター条件を動的に生成することができます。

二項演算子の AST から着想を得たアイデア

今回の実装は、二項演算子を持つ式(binary expression)の抽象構文木(AST)から着想を得ています。

例えば、Go で hoge && fuga を AST で表すと次のような形になります。

package main

import (
	"fmt"
)

func main() {
	hoge := true
	fuga := false
	fmt.Println(hoge && fuga)
}

/*
   119  .  .  .  .  .  .  .  .  0: *ast.BinaryExpr {
   120  .  .  .  .  .  .  .  .  .  X: *ast.Ident {
   121  .  .  .  .  .  .  .  .  .  .  NamePos: foo:10:14
   122  .  .  .  .  .  .  .  .  .  .  Name: "hoge"
   123  .  .  .  .  .  .  .  .  .  .  Obj: *(obj @ 60)
   124  .  .  .  .  .  .  .  .  .  }
   125  .  .  .  .  .  .  .  .  .  OpPos: foo:10:19
   126  .  .  .  .  .  .  .  .  .  Op: &&
   127  .  .  .  .  .  .  .  .  .  Y: *ast.Ident {
   128  .  .  .  .  .  .  .  .  .  .  NamePos: foo:10:22
   129  .  .  .  .  .  .  .  .  .  .  Name: "fuga"
   130  .  .  .  .  .  .  .  .  .  .  Obj: *(obj @ 84)
   131  .  .  .  .  .  .  .  .  .  }
   132  .  .  .  .  .  .  .  .  }
   */

https://yuroyoro.github.io/goast-viewer/ を利用しています。

この例では、*ast.BinaryExpr が演算子を表し、X と Y にそれぞれ *ast.Ident が含まれています。 *ast.BinaryExpr と *ast.Ident は両方とも ast.Node インターフェースを満たしています。

この関係性は ANDFilter と NameContainFilter が両方とも FilterCondition を満たす関係性と同じです。

Composite パターン

今回はボトムアップ的に AST とフィルター条件のデータ構造の共通性を見出しましたが、ある方からこのような共通のインターフェースを実装した木構造を伴う再帰的なデータ構造は Composite パターンと呼ばれていると教えてもらいました。

Wikipedia より引用

Composite パターンの他の利用例としては、ファイルシステムなどが挙げられます。

おわりに

今回は二項演算子の AST から着想を得たデータ構造を用いて、任意のフィルター条件を自由自在に組み合わせるデータ構造を紹介しました。

結果としては Composite パターンを自ら発見したというだけで、目新しさがあるわけでもない記事になってしまいましたが、「別の用途でよく使われているデータ構造を他の用途にも応用できるかも？」と考えるきっかけになれば幸いです。 また、これを機に体系化されているデザインパターンについて調べてみようかと思います。

最後になりますが、DeNA 21 新卒 ×22 新卒内定者 Advent Calendar 2021と DeNA Advent Calendar 2021はそれぞれ新しい記事がどんどん投稿されていきます。 新着記事の情報は DeNA 公式 Twitter アカウント @DeNAxTechでキャッチできるので、ぜひフォローをお願いします！

それでは、明日以降の記事もお楽しみに！