「xpath のような記述で辞書検索」をパーサジェネレータを使って自作 (in Python)

動機のおさらいと作りたい式の構文

これに書いた通り。「「辞書探索のためのリッチなクエリ式」として、XPath そのものは使えない」、「出来合いのものを探すのが結構大変」、「せっかくいいパーサジェネレータ見つけたので、いいお題だよね」てことで。

作りたい式のデザインはこんな感じ:

1 dquery(d, '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..')

スラッシュが XPath のそれと同じなのはいいだろう。「..」は親ノード。「**」は任意の深さ潜る。「[]」は辞書・リストの「[]」そのもの(リストならスライスも出来るとして)、「``」は「[]」内にあるならそのまま「[]」内に展開し、そうでないものは「filter(lambda k, v: {}, node.items())」の「{}」部分に埋めて評価する。そんな感じ。

スラッシュは今回のターゲットの場合なくてもいいんだけれど、あった方が読みやすいので。

式の構文解析、まで

ここまでで2時間ほど費やしてしまったのだが、これははじめ Lark で書き始めて、セマンティクスアクションが書きにくかったもんで竜 TatSu に乗り換えた時間も含む。のでまぁ「順調なほう」だろう、たぶん。

まだ「辞書探索の実現」がない、ただのパース:

 1 # -*- coding: utf-8 -*-
 2 #
 3 from __future__ import absolute_import
 4 from __future__ import unicode_literals
 5 from __future__ import print_function
 6 
 7 import tatsu
 8 
 9 # '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
10 parser = tatsu.compile("""
11     start = q_chain $ ;
12 
13     q_chain = q_curnode {q_chain_following}* ;
14 
15     q_chain_following = "/" q_curnode ;
16 
17     q_curnode = expression
18               | expression_getitem
19               | any_hier
20               | parent
21               ;
22 
23     expression_getitem = "[" expression "]" ;
24 
25     expression = "`" expression_str "`" ;
26     expression_str = {expression_chars}* ;
27     expression_chars = {"\\`"|/[^`]/}
28                      | expression_chars {expression_chars}* ;
29 
30     any_hier = "**" ;
31 
32     parent = ".." ;
33 
34 """, start="q_chain")
35 
36 class _Semantics(object):
37     def q_chain(self, ast):
38         """
39         q_chain = q_curnode {q_chain_following}* ;
40         """
41         # flatten
42         res = [ast[0]]
43         for f in ast[1]:
44             if isinstance(f[0], (tuple,)):
45                 res.append(f[0])
46             else:
47                 res.append(f)
48         return res
49 
50     def q_chain_following(self, ast):
51         """
52         q_chain_following = "/" q_curnode ;
53         """
54         return tuple([ast[1]])
55 
56     def expression_getitem(self, ast):
57         """
58         expression_getitem = "[" expression "]" ;
59         """
60         return tuple(ast[:-1])
61 
62     def expression(self, ast):
63         """
64         expression = "`" expression_str "`" ;
65         """
66         return (ast[0][0], ast[1])
67 
68     def expression_str(self, ast):
69         """
70         expression_str = {expression_chars}* ;
71         """
72         return "".join(ast[0])
73 
74     def any_hier(self, ast):
75         """
76         any_hier = "**" ;
77         """
78         return (ast,)
79 
80     def parent(self, ast):
81         """
82         parent = ".." ;
83         """
84         return (ast,)
85 
86 tree = parser.parse(
87     '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..',
88     semantics=_Semantics())
89 print(*tree)

Lark だろうが Tatsu だろうが共通の「悩ましい部分」は、Lark の共通定義にあるこれ:

1 //
2 // Strings
3 //
4 STRING_INNER: ("\\\""|/[^"]/)
5 ESCAPED_STRING: "\"" STRING_INNER* "\""

に似たことをしようとするとハマる、という点。この例の「STRING_INNER」は非常に貪欲な正規表現であるため、最優先でマッチするように書いてしまうと、ほかのどのルールにもマッチ出来なくなってしまう。

うろ覚えの知識をフル動員してこれを理解するならば、「たぶん終端(terminal)として STRING_INNER (に似たもの)を定義しようとしてはいけない」てことだと思う。

ワタシの例の場合は expression_chars がそれにあたるんだけれど、ただ Lark で LALR でやってたのと Tatsu が PEG であるのとでの違いは出てたかも。Lark 側でこの問題をクリアした後で乗り換えたんで「Tatsu でも同じだった」かどうかがわからない。

STRING_INNER、expression_chars には「貪欲過ぎる」こと以外にも使い勝手の問題があって、読めばわかると思うけれどこれは「一文字ずつ逐一トークンにバラける」。

この問題はもう避けようがないんだよね。ワタシの例の場合は「`(バッククオート)で囲まれた完全なフリーテキスト(バッククオート自身はバックスラッシュでエスケープ可)」というもので、「完全なフリーテキスト」とその他キーワード(「**」など)を共存させるために。これはどんな定義を書く場合もほとんど共通と思う。

セマンティクスアクションの方は簡単に言えばこういう構造に読み替えてるだけ:

1 全体: (コマンド[, 引数]), ...
2 コマンド: "**", "..", "`"

例えば:

1 INPUT: '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
2 
3 RESULT:
4 ('[', ('`', '"bkey"')),
5 ('**',),
6 ('[', ('`', '"akey"')),
7 ('[', ('`', '1:-1')),
8 ('`', '"xyz" in k.lower()'),
9 ('..',)

ここまで来ればもう「実際の辞書探索実装を書くだけ」。

実際の辞書探索実装、のポイント

昨日脳内だけで考えていた際に一番苦労していたのが「**」。これは(昔懐かしい) ant なんかで提供されていたのと同じもので、「カレントノードのもの全てとその配下ノード全て」の意味。xpath ではこれは出来なかったような気がするがどうだったっけか? 一番これこそが欲しいのよ。つまり、「aaa/Xxx/Yyy」「aaa/bbb/Xxx/Yyy」という相手に対して「**/Xxx/Yyy」でどちらもマッチさせたいのだ。

これは深さ方向にノードを潜っていく際、「**」に続く記述が真になるまでコマンドリストを先に進めない、というような考え方でいけるはずだ。今まだ実装書いてないが、たぶんそんな感じ。

まずは「**」実装なし

辞書トラバースの実装を (今の場合の) _Semantics に埋め込むかそうしないかはケースバイケースと思う。今の例の場合は既に書いた _Semantics が返す形が既に十分扱いやすいので、 _Semantics とは完全に分けてしまう。

一気に全部書こうかとも思ったが、想定通り「**」の実現はムゴいことになるので、まずはないものだけ先に書いてみる:

 1 # ... (省略) ...
 2 
 3 def query(d, expr):
 4     r"""
 5     >>> query({
 6     ...     "x1": {
 7     ...         "lst": [1, 3, 5, 7, 9],
 8     ...     },
 9     ...     "x2": {
10     ...         "lst": [9, 3, 1, 7, 5],
11     ...     },
12     ... }, '[`"x1"`]/[`"lst"`]/[`::2`]')
13     [[1, 5, 9]]
14     """
15     def _query(node, q, result, parents):
16         def _eval(node, cur_q, parents):
17             F1 = 'node[{}]'
18             F2 = '[(k, v) for k, v in node.items() if {}]'
19             cmd = cur_q[0]
20             if cmd == "..":
21                 return parents.pop(-1)
22             elif cmd == "[":
23                 # ex. '1:-1' -> 'node[1:-1]'
24                 # ex. '"x1"' -> 'node["x1"]'
25                 try:
26                     return eval(F1.format(cur_q[1][1]))
27                 except Exception:
28                     # unsupported operation in current node
29                     pass
30             elif cmd == "`":
31                 # ex. '"xyz" in k.lower()'
32                 #  -> '[(k, v) for k, v in node.items() if "xyz" in k.lower()]'
33                 try:
34                     return [v for k, v in eval(F2.format(cur_q[1]))]
35                 except Exception:
36                     # unsupported operation in current node
37                     pass
38 
39         cur_q = q[0]
40         nextq = q[1:]
41         cmd = cur_q[0]
42         cands = None
43         cands = _eval(node, cur_q, parents)
44         if nextq:
45             _query(cands, nextq, result, parents + [node])
46         elif cands is not None:
47             # leaf query
48             result.append(cands)
49 
50     q = parser.parse(expr, semantics=_Semantics())
51     result = []
52     _query(d, q, result, [])
53     return result
54 
55 
56 if __name__ == '__main__':
57     import doctest
58     doctest.testmod()

既に若干使用感に不満があったりもする。けどまぁこのまま進めるとする。動いてるとこだけ見てるぶんにはいい感じには見えるね。

parent の振る舞いがおかしいことは今時点でわかっている(二つ上に上がれないとか色々)が、ひとまず放置。

ひとまずの初版

ひとまずこんなだね:

  1 # -*- coding: utf-8 -*-
  2 #
  3 from __future__ import absolute_import
  4 from __future__ import unicode_literals
  5 from __future__ import print_function
  6 
  7 import sys
  8 
  9 import tatsu
 10 
 11 
 12 # '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
 13 parser = tatsu.compile("""
 14     start = q_chain $ ;
 15 
 16     q_chain = q_curnode {q_chain_following}* ;
 17 
 18     q_chain_following = "/" q_curnode ;
 19 
 20     q_curnode = expression
 21               | expression_getitem
 22               | any_hier
 23               | parent
 24               ;
 25 
 26     expression_getitem = "[" expression "]" ;
 27 
 28     expression = "`" expression_str "`" ;
 29     expression_str = {expression_chars}* ;
 30     expression_chars = {"\\`"|/[^`]/}
 31                      | expression_chars {expression_chars}* ;
 32 
 33     any_hier = "**" ;
 34 
 35     parent = ".." ;
 36 
 37 """, start="q_chain")
 38 
 39 class _Semantics(object):
 40     def q_chain(self, ast):
 41         """
 42         q_chain = q_curnode {q_chain_following}* ;
 43         """
 44         # flatten
 45         res = [ast[0]]
 46         for f in ast[1]:
 47             if isinstance(f[0], (tuple,)):
 48                 res.append(f[0])
 49             else:
 50                 res.append(f)
 51         return res
 52 
 53     def q_chain_following(self, ast):
 54         """
 55         q_chain_following = "/" q_curnode ;
 56         """
 57         return tuple([ast[1]])
 58 
 59     def expression_getitem(self, ast):
 60         """
 61         expression_getitem = "[" expression "]" ;
 62         """
 63         return tuple(ast[:-1])
 64 
 65     def expression(self, ast):
 66         """
 67         expression = "`" expression_str "`" ;
 68         """
 69         return (ast[0][0], ast[1])
 70 
 71     def expression_str(self, ast):
 72         """
 73         expression_str = {expression_chars}* ;
 74         """
 75         return "".join(ast[0])
 76 
 77     def any_hier(self, ast):
 78         """
 79         any_hier = "**" ;
 80         """
 81         return (ast,)
 82 
 83     def parent(self, ast):
 84         """
 85         parent = ".." ;
 86         """
 87         return (ast,)
 88 
 89 #tree = parser.parse(
 90 #    '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..',
 91 #    semantics=_Semantics())
 92 #print(*tree)
 93 
 94 def query(d, expr):
 95     r"""
 96     >>> query({
 97     ...     "x1": {
 98     ...         "lst": [1, 3, 5, 7, 9],
 99     ...     },
100     ...     "x2": {
101     ...         "lst": [9, 3, 1, 7, 5],
102     ...     },
103     ... }, '[`"x1"`]/[`"lst"`]/[`::2`]')
104     [[1, 5, 9]]
105     >>> list(sorted(query({
106     ...     "x1": {
107     ...         "lst": [1, 3, 5, 7, 9],
108     ...     },
109     ...     "x2": {
110     ...         "lst": [9, 3, 1, 7, 5],
111     ...     },
112     ... }, '**/[`"lst"`]/[`::2`]')))
113     [[1, 5, 9], [9, 1, 5]]
114     >>> list(sorted(query({
115     ...     "x1": {
116     ...         "lst": [1, 3, 5, 7, 9],
117     ...     },
118     ...     "x2": {
119     ...         "lst": [9, 3, 1, 7, 5],
120     ...     },
121     ... }, '**/[`"lst"`]/`v > 2`')))
122     [[3, 5, 7, 9], [9, 3, 7, 5]]
123     >>> query({
124     ...     "x1": {
125     ...         "lst": [1, 3, 5, 7, 9],
126     ...     },
127     ...     "x2": {
128     ...         "lst": [9, 3, 1, 7, 5],
129     ...     },
130     ... }, '`k.endswith("2")`')
131     [[{'lst': [9, 3, 1, 7, 5]}]]
132     """
133     def _query(node, q, result, parents):
134         def _eval(node, cur_q, parents):
135             F1 = 'node[{}]'
136             F2 = '[v for k, v in node.items() if {}]'
137             F3 = '[v for v in node if {}]'
138             cmd = cur_q[0]
139             if cmd == "..":
140                 return parents.pop(-1)
141             elif cmd == "[":
142                 # ex. '1:-1' -> 'node[1:-1]'
143                 # ex. '"x1"' -> 'node["x1"]'
144                 try:
145                     return eval(F1.format(cur_q[1][1]))
146                 except Exception:
147                     # unsupported operation in current node
148                     pass
149             elif cmd == "`":
150                 if isinstance(node, (dict,)):
151                     # ex. '"xyz" in k.lower()'
152                     #  -> '[v for k, v in node.items() if "xyz" in k.lower()]'
153                     return eval(F2.format(cur_q[1]))
154                 elif isinstance(node, (list,)):
155                     return eval(F3.format(cur_q[1]))
156                 else:
157                     # what should we do?
158                     pass
159 
160         cur_q = q[0]
161         nextq = q[1:]
162         cmd = cur_q[0]
163         cands = None
164         if cmd == "**":
165             if isinstance(node, (dict,)):
166                 childs = node.values()
167             elif isinstance(node, (list,)):
168                 childs = list(node)
169             else:
170                 # what should we do?
171                 childs = []
172             for child in childs:
173                 _query(child, nextq, result, parents + [node])
174         else:
175             cands = _eval(node, cur_q, parents)
176             if nextq:
177                 _query(cands, nextq, result, parents + [node])
178             elif cands is not None:
179                 # leaf query
180                 result.append(cands)
181 
182     q = parser.parse(expr, semantics=_Semantics())
183     result = []
184     _query(d, q, result, [])
185     return result
186 
187 
188 if __name__ == '__main__':
189     import doctest
190     doctest.testmod()

完成させないの? ⇒ させないよ、今は

入り口には立ったぞ、てことで、完成までやるのはやめとく。ほかにやることたんまりあるんで、こればっかやってるわけいんはいかんのよ。

parent はおかしいままだし、期待した結果になってないとこもある。実際にイザ使おうとしたら全然使えないことがわかるであろう。

まぁこの記事が言いたいことは「辞書に対するリッチな検索を完成させる」ことにはなくて、「やってやれないことはない、やれば?」と言うがためのもんであって、まぁこれ自分でも欲しいやつなんで、いずれはちゃんと完成させようとは思わないでもないけれど、いつになるかは知らんよ、一年後かもしらんし、五年後かもしらん。そんときは追記するかもしれん。ただその前に出来合いのものを見つけてしまいそうな気がするわね。

もしこの手のことに興味があって、自分で続けてみたいと思うのであれば、以下のことには注意してくたさい:

必ずパーサジェネレータがないと書けない、と主張しているのではないので、「どうありがたいのか」を理解しながら遊んで欲しい。
セマンティクスアクション部分の書き方は色々考え方があるので、ワタシの書き方をみて「こういうもんだ」と思わない方がいいよ。ここは実際に自分で動かしてみて感覚をつかんだほうがいい。
性能の件。これはワタシの今回のこれは、「まったくもって無頓着」にやってる。てことはお忘れなく。
eval の是非について。eval を使うことで「Python で出来ること全てが出来てしまう」ことは、危険も背負い込むことになることに注意。DSL (ドメイン固有言語)の動機の一つには「出来ることを制限する」ことにもあったりするので、それが目的なのであれば、構文のほうをもっと頑張る必要があります。(ワタシのは `～` 内は完全に無法地帯。)