source: tagsplugin/tags/0.7/tractags/query.py

Last change on this file was 13392, checked in by Steffen Hoffmann, 10 years ago

TagsPlugin: Provide faster tag counter implementations by a Counter class, refs #4503.

Handling of tag collections in Counter objects is more efficient,
because we skip creation of associated resources and permission checks.
We use a feature-stripped, more PEP8-conform version of the original recipe.

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