source: tagsplugin/trunk/tractags/query.py

Last change on this file was 18146, checked in by Cinc-th, 2 years ago

TagsPlugin: fixed a string/byte problem with QueryNode. Fixed some tests where we expected a list but got dict_keys instead. Fixed test where sort order of a set was assumed.

Refs #13994
  • Property svn:eol-style set to native
File size: 14.2 KB
Line 
1# -*- coding: utf-8 -*-
2#
3# Copyright (C) 2006 Alec Thomas <alec@swapoff.org>
4#
5# This software is licensed as described in the file COPYING, which
6# you should have received as part of this distribution.
7#
8
9"""
10A generalised query parser and matcher.
11"""
12
13import re
14
15from trac.core import TracError
16from trac.util.text import to_unicode
17
18from tractags.api import _
19
20__all__ = ['Query', 'InvalidQuery']
21
22
23class InvalidQuery(TracError):
24    """Raised when a query is invalid."""
25
26
27class QueryNode(object):
28    """A query parse node.
29
30    >>> QueryNode(QueryNode.TERM, 'one')
31    ("one")
32    >>> QueryNode(QueryNode.AND,
33    ...     left=QueryNode(QueryNode.TERM, 'one'),
34    ...     right=QueryNode(QueryNode.TERM, 'two'))
35    (and
36      ("one")
37      ("two"))
38    >>> QueryNode(QueryNode.NOT, left=QueryNode(QueryNode.TERM, 'one'))
39    (not
40      ("one")
41      nil)
42    """
43
44
45    # TODO Separate lexer and parser identifiers
46    NULL = 0
47    TERM = 1
48    NOT = 2
49    AND = 3
50    OR = 4
51    ATTR = 5
52    BEGINSUB = 6
53    ENDSUB = 7
54
55    __slots__ = ('type', 'value', 'left', 'right')
56
57    _type_map = {None: 'null', NULL: 'null', TERM: 'term', NOT: 'not', AND:
58                 'and', OR: 'or', ATTR: 'attr'}
59
60    def __init__(self, type, value=None, left=None, right=None):
61        self.type = type
62        self.value = value
63        self.left = left
64        self.right = right
65
66    def __repr__(self):
67        def show(node, depth=0):
68            if node.type == QueryNode.TERM:
69                text = u'%s("%s"' % (u'  ' * depth, node.value)
70            elif node.type == QueryNode.ATTR:
71                text = u'%s(attr' % (u'  ' * depth,)
72            else:
73                text = u'%s(%s%s' % (u'  ' * depth, self._type_map[node.type],
74                                    node.value and u' "%s"' % (node.value,) or
75                                    u'')
76            if node.left or node.right:
77                text += u'\n'
78                if node.left:
79                    text += show(node.left, depth + 1)
80                else:
81                    text += u'%snil' % (u'  ' * (depth + 1))
82                text += u'\n'
83                if node.right:
84                    text += show(node.right, depth + 1)
85                else:
86                    text += u'%snil' % (u'  ' * (depth + 1))
87            text += u')'
88            return text
89        return to_unicode(show(self))
90
91
92class Query(QueryNode):
93    """Query parser.
94
95    Converts a simple query language into a parse tree which Indexers can then
96    convert into their own implementation-specific representation.
97
98    The query language is in the following form:
99
100        <term> <term>     Document must contain all of these terms.
101        "some term"       Return documents matching this exact phrase.
102        -<term>           Exclude documents containing this term.
103        <term> or <term>  Return documents matching either term.
104
105        <attr>:<term>     Customisable attribute matching.
106
107    eg.
108
109    >>> Query('lettuce tomato -cheese')
110    (and
111      ("lettuce")
112      (and
113        ("tomato")
114        (not
115          ("cheese")
116          nil)))
117
118    >>> Query('"mint slices" -timtams')
119    (and
120      ("mint slices")
121      (not
122        ("timtams")
123        nil))
124
125    >>> Query('"brie cheese" or "camembert cheese"')
126    (or
127      ("brie cheese")
128      ("camembert cheese"))
129
130    >>> Query('type:(soft or hard) (brie or camembert or cheddar)')
131    (and
132      (attr
133        ("type")
134        (or
135          ("soft")
136          ("hard")))
137      (or
138        ("brie")
139        (or
140          ("camembert")
141          ("cheddar"))))
142    """
143
144    _tokenise_re = re.compile(r"""
145        (?P<not>-)|
146        (?P<or>or)\s+|
147        (?P<dquote>"(?:\\.|[^"])*")|
148        (?P<squote>'(?:\\.|[^'])*')|
149        (?P<startsub>\()|
150        (?P<endsub>\))|
151        (?P<attr>:)|
152        (?P<term>[^:()\s]+)""", re.UNICODE | re.IGNORECASE | re.VERBOSE)
153
154    _group_map = {'dquote': QueryNode.TERM, 'squote': QueryNode.TERM,
155                  'term': QueryNode.TERM, 'not': QueryNode.NOT,
156                  'or': QueryNode.OR, 'attr': QueryNode.ATTR,
157                  'startsub': QueryNode.BEGINSUB, 'endsub': QueryNode.ENDSUB}
158
159    def __init__(self, phrase, attribute_handlers=None):
160        """Construct a new Query.
161
162        Attribute handlers are callables with the signature
163        (attribute_name, node, context) where node is the QueryNode
164        representing the RHS of the attribute expression and context is a custom
165        parameter passed to Query.__call__().
166
167        :param phrase: Query phrase.
168        :param attribute_handlers: A dictionary of attribute handlers.
169        """
170        QueryNode.__init__(self, None)
171        tokens = self._tokenise(phrase)
172        root = self.parse(tokens)
173        self.phrase = phrase
174        self._compiled = None
175        self.attribute_handlers = attribute_handlers or {}
176        self.attribute_handlers.setdefault('*', self._invalid_handler)
177        if root:
178            # Make ourselves into the root node
179            for k in self.__slots__:
180                setattr(self, k, getattr(root, k))
181
182    def parse(self, tokens):
183        left = self.parse_unary(tokens)
184        while tokens:
185            if tokens[0][0] == QueryNode.ENDSUB:
186                return left
187            if tokens[0][0] == QueryNode.OR:
188                tokens.pop(0)
189                return QueryNode(QueryNode.OR, left=left,
190                                 right=self.parse(tokens))
191            elif tokens[0][0] == QueryNode.ATTR:
192                tokens.pop(0)
193                if left.type is not QueryNode.TERM:
194                    raise InvalidQuery(_("Attribute must be a word"))
195                left = QueryNode(QueryNode.ATTR, left=left,
196                                 right=self.parse_unary(tokens))
197            else:
198                return QueryNode(QueryNode.AND, left=left,
199                                 right=self.parse(tokens))
200        return left
201
202    def parse_unary(self, tokens):
203        """Parse a unary operator. Currently only NOT.
204
205        >>> q = Query('')
206        >>> q.parse_unary(q._tokenise('-foo'))
207        (not
208          ("foo")
209          nil)
210        """
211        if not tokens:
212            return None
213        if tokens[0][0] == QueryNode.BEGINSUB:
214            tokens.pop(0)
215            if tokens[0][0] == QueryNode.ENDSUB:
216                return None
217            node = self.parse(tokens)
218            if not tokens or tokens[0][0] != QueryNode.ENDSUB:
219                raise InvalidQuery(_("Expected ) at end of sub-expression"))
220            tokens.pop(0)
221            return node
222        if tokens[0][0] == QueryNode.NOT:
223            tokens.pop(0)
224            return QueryNode(QueryNode.NOT, left=self.parse_terminal(tokens))
225        return self.parse_terminal(tokens)
226
227    def parse_terminal(self, tokens):
228        """Parse a terminal token.
229
230        >>> q = Query('')
231        >>> q.parse_terminal(q._tokenise('foo'))
232        ("foo")
233        """
234
235        if not tokens:
236            raise InvalidQuery(_("Unexpected end of string"))
237        if tokens[0][0] in (QueryNode.TERM, QueryNode.OR):
238            token = tokens.pop(0)[1]
239            if token[0] in ('"', "'"):
240                token = re.sub(r'\\(.)', r'\1', token[1:-1])
241            return QueryNode(QueryNode.TERM, value=token)
242        raise InvalidQuery(_("Expected terminal, got '%s'") % tokens[0][1])
243
244    def terms(self, exclude_not=True):
245        """A generator returning the terms contained in the Query.
246
247        >>> q = Query('foo -bar or baz')
248        >>> list(q.terms())
249        ['foo', 'baz']
250        >>> list(q.terms(exclude_not=False))
251        ['foo', 'bar', 'baz']
252        """
253        def _convert(node):
254            if not node:
255                return
256            if node.type == node.TERM:
257                yield node.value
258            elif node.type == node.ATTR:
259                return
260            elif node.type == node.NOT and exclude_not:
261                return
262            else:
263                for child in _convert(node.left):
264                    yield child
265                for child in _convert(node.right):
266                    yield child
267
268        return _convert(self)
269
270    def __call__(self, terms, context=None):
271        """Match the query against a sequence of terms."""
272        return self.match(self, terms, context)
273
274    def match(self, node, terms, context=None):
275        """Match a node against a set of terms."""
276        def _match(node):
277            if not node or node.type == node.NULL:
278                return True
279            elif node.type == node.TERM:
280                return node.value in terms
281            elif node.type == node.AND:
282                return _match(node.left) and _match(node.right)
283            elif node.type == node.OR:
284                return _match(node.left) or _match(node.right)
285            elif node.type == node.NOT:
286                return not _match(node.left)
287            elif node.type == node.ATTR:
288                return self.attribute_handlers.get(
289                    node.left.value,
290                    self.attribute_handlers['*']
291                    )(node.left.value, node.right, context)
292            elif node.type is None:
293                return True
294            else:
295                raise NotImplementedError(node.type)
296        return _match(node)
297
298
299    def _compile_call(self, text, attribute_handlers=None):
300        import compiler
301        import types
302        from compiler import ast, misc, pycodegen
303
304        raise NotImplementedError('Incomplete')
305
306        # TODO Make this work?
307        def _generate(node):
308            if node.type == node.TERM:
309                return ast.Compare(ast.Const(node.value),
310                                   [('in', ast.Name('text'))])
311            elif node.type == node.AND:
312                return ast.And([_generate(node.left), _generate(node.right)])
313            elif node.type == node.OR:
314                return ast.Or([_generate(node.left), _generate(node.right)])
315            elif node.type == node.NOT:
316                return ast.Not(_generate(node.left))
317            elif node.type == node.ATTR:
318                raise NotImplementedError
319
320        qast = ast.Expression(ast.Lambda(['self', 'text',
321                                          'attribute_handlers'],
322                                         [ast.Name('None')],
323                                         0,
324                                         _generate(self)))
325        misc.set_filename('<%s compiled query>' % self.__class__.__name__,
326                          qast)
327        gen = pycodegen.ExpressionCodeGenerator(qast)
328        self.__call__ = types.MethodType(eval(gen.getCode()), self, Query)
329        return self.__call__(text)
330
331    def as_string(self, and_=' AND ', or_=' OR ', not_='NOT '):
332        """Convert Query to a boolean expression. Useful for indexers with
333        "typical" boolean query syntaxes.
334
335        eg. "term AND term OR term AND NOT term"
336
337        The expanded operators can be customised for syntactical variations.
338
339        >>> Query('foo bar').as_string()
340        'foo AND bar'
341        >>> Query('foo bar or baz').as_string()
342        'foo AND bar OR baz'
343        >>> Query('foo -bar or baz').as_string()
344        'foo AND NOT bar OR baz'
345        """
346        def _convert(node):
347            if not node or not node.type or node.type == node.NULL:
348                return ''
349            if node.type == node.AND:
350                return '%s%s%s' % (_convert(node.left), and_,
351                                   _convert(node.right))
352            elif node.type == node.OR:
353                return '%s%s%s' % (_convert(node.left), or_,
354                                   _convert(node.right))
355            elif node.type == node.NOT:
356                return '%s%s' % (not_, _convert(node.left))
357            elif node.type == node.TERM:
358                return node.value
359            elif node.type == node.ATTR:
360                return '%s:%s' % (_convert(node.left), _convert(node.right))
361            else:
362                raise NotImplementedError
363        return _convert(self)
364
365    def as_sql(self, col_name):
366        """Convert Query to a SQL expression.
367
368        The table column name must be given as argument.
369
370        >>> Query('foo bar').as_sql('c')
371        "c='foo' AND c='bar'"
372        >>> Query('foo bar or baz').as_sql('c')
373        "c='foo' AND c='bar' OR c='baz'"
374        >>> Query('foo -bar or baz').as_sql('c')
375        "c='foo' AND NOT c='bar' OR c='baz'"
376        """
377        def _convert(node):
378            if not node or not node.type or node.type == node.NULL:
379                return ''
380            if node.type == node.AND:
381                return '%s AND %s' % (_convert(node.left),
382                                   _convert(node.right))
383            elif node.type == node.OR:
384                return '%s OR %s' % (_convert(node.left),
385                                   _convert(node.right))
386            elif node.type == node.NOT:
387                return 'NOT %s' % _convert(node.left)
388            elif node.type == node.TERM:
389                return "%s='%s'" % (col_name, node.value)
390            elif node.type == node.ATTR:
391                raise NotImplementedError
392            else:
393                raise NotImplementedError
394        return _convert(self)
395
396    def reduce(self, reduce):
397        """Pass each TERM node through `Reducer`."""
398        def _reduce(node):
399            if not node:
400                return
401            if node.type == node.TERM:
402                node.value = reduce(node.value, unique=False, split=False)
403            _reduce(node.left)
404            _reduce(node.right)
405        _reduce(self)
406
407    # Internal methods
408    def _tokenise(self, phrase):
409        """Tokenise a phrase string.
410
411        >>> q = Query('')
412        >>> q._tokenise('one')
413        [(1, 'one')]
414        >>> q._tokenise('one two')
415        [(1, 'one'), (1, 'two')]
416        >>> q._tokenise('one or two')
417        [(1, 'one'), (4, 'or'), (1, 'two')]
418        >>> q._tokenise('"one two"')
419        [(1, '"one two"')]
420        >>> q._tokenise("'one two'")
421        [(1, "'one two'")]
422        >>> q._tokenise('-one')
423        [(2, '-'), (1, 'one')]
424        """
425        tokens = [(self._group_map[token.lastgroup], token.group(token.lastindex))
426                  for token in self._tokenise_re.finditer(phrase)]
427        return tokens
428
429    def _invalid_handler(self, name, node, context):
430        raise InvalidQuery(_("Invalid attribute '%s'") % name)
431
432if __name__ == '__main__':
433    import doctest
434    doctest.testmod()
Note: See TracBrowser for help on using the repository browser.