blob: 235f9b3923c52f495e1343e564da7cd84af41814 [file] [log] [blame]
# Copyright 2016 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style
# license that can be found in the LICENSE file or at
# https://developers.google.com/open-source/licenses/bsd
"""A set of functions that integrate the GAE search index with Monorail."""
from __future__ import print_function
from __future__ import division
from __future__ import absolute_import
import collections
import datetime
import logging
import re
import time
from google.appengine.api import search
from proto import ast_pb2
from proto import tracker_pb2
# TODO(jrobbins): Consider re-implementing this whole file by using a
# BNF syntax specification and a parser generator or library.
# encodings
UTF8 = 'utf-8'
# Operator used for OR statements.
OR_SYMBOL = ' OR '
# Token types used for parentheses parsing.
SUBQUERY = ast_pb2.TokenType.SUBQUERY
LEFT_PAREN = ast_pb2.TokenType.LEFT_PAREN
RIGHT_PAREN = ast_pb2.TokenType.RIGHT_PAREN
OR = ast_pb2.TokenType.OR
# Field types and operators
BOOL = tracker_pb2.FieldTypes.BOOL_TYPE
DATE = tracker_pb2.FieldTypes.DATE_TYPE
NUM = tracker_pb2.FieldTypes.INT_TYPE
TXT = tracker_pb2.FieldTypes.STR_TYPE
APPROVAL = tracker_pb2.FieldTypes.APPROVAL_TYPE
EQ = ast_pb2.QueryOp.EQ
NE = ast_pb2.QueryOp.NE
LT = ast_pb2.QueryOp.LT
GT = ast_pb2.QueryOp.GT
LE = ast_pb2.QueryOp.LE
GE = ast_pb2.QueryOp.GE
TEXT_HAS = ast_pb2.QueryOp.TEXT_HAS
NOT_TEXT_HAS = ast_pb2.QueryOp.NOT_TEXT_HAS
IS_DEFINED = ast_pb2.QueryOp.IS_DEFINED
IS_NOT_DEFINED = ast_pb2.QueryOp.IS_NOT_DEFINED
KEY_HAS = ast_pb2.QueryOp.KEY_HAS
# Mapping from user query comparison operators to our internal representation.
OPS = {
':': TEXT_HAS,
'=': EQ,
'!=': NE,
'<': LT,
'>': GT,
'<=': LE,
'>=': GE,
}
# When the query has a leading minus, switch the operator for its opposite.
NEGATED_OPS = {
EQ: NE,
NE: EQ,
LT: GE,
GT: LE,
LE: GT,
GE: LT,
TEXT_HAS: NOT_TEXT_HAS,
# IS_DEFINED is handled separately.
}
# This is a partial regular expression that matches all of our comparison
# operators, such as =, 1=, >, and <. Longer ones listed first so that the
# shorter ones don't cause premature matches.
OPS_PATTERN = '|'.join(
map(re.escape, sorted(list(OPS.keys()), key=lambda op: -len(op))))
# This RE extracts search terms from a subquery string.
TERM_RE = re.compile(
r'(-?"[^"]+")|' # E.g., ["division by zero"]
r'(\S+(%s)[^ "]+)|' # E.g., [stars>10]
r'(\w+(%s)"[^"]+")|' # E.g., [summary:"memory leak"]
r'(-?[._\*\w][-._\*\w]+)' # E.g., [-workaround]
% (OPS_PATTERN, OPS_PATTERN), flags=re.UNICODE)
# This RE is used to further decompose a comparison term into prefix, op, and
# value. E.g., [stars>10] or [is:open] or [summary:"memory leak"]. The prefix
# can include a leading "-" to negate the comparison.
OP_RE = re.compile(
r'^(?P<prefix>[-_.\w]*?)'
r'(?P<op>%s)'
r'(?P<value>([-@\w][-\*,./:<=>@\w]*|"[^"]*"))$' %
OPS_PATTERN,
flags=re.UNICODE)
# Predefined issue fields passed to the query parser.
_ISSUE_FIELDS_LIST = [
(ast_pb2.ANY_FIELD, TXT),
('attachment', TXT), # attachment file names
('attachments', NUM), # number of attachment files
('blocked', BOOL),
('blockedon', TXT),
('blockedon_id', NUM),
('blocking', TXT),
('blocking_id', NUM),
('cc', TXT),
('cc_id', NUM),
('comment', TXT),
('commentby', TXT),
('commentby_id', NUM),
('component', TXT),
('component_id', NUM),
('description', TXT),
('gate', TXT),
('hotlist', TXT),
('hotlist_id', NUM),
('id', NUM),
('is_spam', BOOL),
('label', TXT),
('label_id', NUM),
('mergedinto', NUM),
('mergedinto_id', NUM),
('open', BOOL),
('owner', TXT),
('ownerbouncing', BOOL),
('owner_id', NUM),
('project', TXT),
('reporter', TXT),
('reporter_id', NUM),
('spam', BOOL),
('stars', NUM),
('starredby', TXT),
('starredby_id', NUM),
('status', TXT),
('status_id', NUM),
('summary', TXT),
]
_DATE_FIELDS = (
'closed',
'modified',
'opened',
'ownermodified',
'ownerlastvisit',
'statusmodified',
'componentmodified',
)
# Add all _DATE_FIELDS to _ISSUE_FIELDS_LIST.
_ISSUE_FIELDS_LIST.extend((date_field, DATE) for date_field in _DATE_FIELDS)
_DATE_FIELD_SUFFIX_TO_OP = {
'-after': '>',
'-before': '<',
}
SET_BY_SUFFIX = '-by'
SET_ON_SUFFIX = '-on'
APPROVER_SUFFIX = '-approver'
STATUS_SUFFIX = '-status'
_APPROVAL_SUFFIXES = (
SET_BY_SUFFIX,
SET_ON_SUFFIX,
APPROVER_SUFFIX,
STATUS_SUFFIX,
)
BUILTIN_ISSUE_FIELDS = {
f_name: tracker_pb2.FieldDef(field_name=f_name, field_type=f_type)
for f_name, f_type in _ISSUE_FIELDS_LIST}
# Do not treat strings that start with the below as key:value search terms.
# See bugs.chromium.org/p/monorail/issues/detail?id=419 for more detail.
NON_OP_PREFIXES = (
'http:',
'https:',
)
def ParseUserQuery(
query, scope, builtin_fields, harmonized_config, warnings=None,
now=None):
# type: (str, str, Mapping[str, proto.tracker_pb2.FieldDef],
# proto.tracker_pb2.ProjectIssueConfig, Sequence[str], int) ->
# proto.ast_pb2.QueryAST
"""Parse a user query and return a set of structure terms.
Args:
query: string with user's query. E.g., 'Priority=High'.
scope: string search terms that define the scope in which the
query should be executed. They are expressed in the same
user query language. E.g., adding the canned query.
builtin_fields: dict {field_name: FieldDef(field_name, type)}
mapping field names to FieldDef objects for built-in fields.
harmonized_config: config for all the projects being searched.
@@@ custom field name is not unique in cross project search.
- custom_fields = {field_name: [fd, ...]}
- query build needs to OR each possible interpretation
- could be label in one project and field in another project.
@@@ what about searching across all projects?
warnings: optional list to accumulate warning messages.
now: optional timestamp for tests, otherwise time.time() is used.
Returns:
A QueryAST with conjunctions (usually just one), where each has a list of
Condition PBs with op, fields, str_values and int_values. E.g., the query
[priority=high leak OR stars>100] over open issues would return
QueryAST(
Conjunction(Condition(EQ, [open_fd], [], [1]),
Condition(EQ, [label_fd], ['priority-high'], []),
Condition(TEXT_HAS, any_field_fd, ['leak'], [])),
Conjunction(Condition(EQ, [open_fd], [], [1]),
Condition(GT, [stars_fd], [], [100])))
Raises:
InvalidQueryError: If a problem was detected in the user's query.
"""
if warnings is None:
warnings = []
# Convert the overall query into one or more OR'd subqueries.
subqueries = QueryToSubqueries(query)
# Make a dictionary of all fields: built-in + custom in each project.
combined_fields = collections.defaultdict(
list, {field_name: [field_def]
for field_name, field_def in builtin_fields.items()})
for fd in harmonized_config.field_defs:
if fd.field_type != tracker_pb2.FieldTypes.ENUM_TYPE:
# Only do non-enum fields because enums are stored as labels
combined_fields[fd.field_name.lower()].append(fd)
if fd.field_type == APPROVAL:
for approval_suffix in _APPROVAL_SUFFIXES:
combined_fields[fd.field_name.lower() + approval_suffix].append(fd)
conjunctions = [
_ParseConjunction(sq, scope, combined_fields, warnings, now=now)
for sq in subqueries]
return ast_pb2.QueryAST(conjunctions=conjunctions)
def _ParseConjunction(subquery, scope, fields, warnings, now=None):
# type: (str, str, Mapping[str, proto.tracker_pb2.FieldDef], Sequence[str],
# int) -> proto.ast_pb2.Condition
"""Parse part of a user query into a Conjunction PB."""
scoped_query = ('%s %s' % (scope, subquery)).lower()
cond_strs = _ExtractConds(scoped_query, warnings)
conds = [_ParseCond(cond_str, fields, warnings, now=now)
for cond_str in cond_strs]
conds = [cond for cond in conds if cond]
return ast_pb2.Conjunction(conds=conds)
def _ParseCond(cond_str, fields, warnings, now=None):
# type: (str, Mapping[str, proto.tracker_pb2.FieldDef], Sequence[str],
# int) -> proto.ast_pb2.Condition
"""Parse one user query condition string into a Condition PB."""
op_match = OP_RE.match(cond_str)
# Do not treat as key:value search terms if any of the special prefixes match.
special_prefixes_match = any(
cond_str.startswith(p) for p in NON_OP_PREFIXES)
if op_match and not special_prefixes_match:
prefix = op_match.group('prefix')
op = op_match.group('op')
val = op_match.group('value')
# Special case handling to continue to support old date query terms from
# code.google.com. See monorail:151 for more details.
if prefix.startswith(_DATE_FIELDS):
for date_suffix in _DATE_FIELD_SUFFIX_TO_OP:
if prefix.endswith(date_suffix):
prefix = prefix.rstrip(date_suffix)
op = _DATE_FIELD_SUFFIX_TO_OP[date_suffix]
return _ParseStructuredTerm(prefix, op, val, fields, now=now)
# Treat the cond as a full-text search term, which might be negated.
if cond_str.startswith('-'):
op = NOT_TEXT_HAS
cond_str = cond_str[1:]
else:
op = TEXT_HAS
# Construct a full-text Query object as a dry-run to validate that
# the syntax is acceptable.
try:
_fts_query = search.Query(cond_str)
except search.QueryError:
warnings.append('Ignoring full-text term: %s' % cond_str)
return None
# Flag a potential user misunderstanding.
if cond_str.lower() in ('and', 'or', 'not'):
warnings.append(
'The only supported boolean operator is OR (all capitals).')
return ast_pb2.MakeCond(
op, [BUILTIN_ISSUE_FIELDS[ast_pb2.ANY_FIELD]], [cond_str], [])
def _ParseStructuredTerm(prefix, op_str, value, fields, now=None):
# type: (str, str, str, Mapping[str, proto.tracker_pb2.FieldDef]) ->
# proto.ast_pb2.Condition
"""Parse one user structured query term into an internal representation.
Args:
prefix: The query operator, usually a field name. E.g., summary. It can
also be special operators like "is" to test boolean fields.
op_str: the comparison operator. Usually ":" or "=", but can be any OPS.
value: the value to compare against, e.g., term to find in that field.
fields: dict {name_lower: [FieldDef, ...]} for built-in and custom fields.
now: optional timestamp for tests, otherwise time.time() is used.
Returns:
A Condition PB.
"""
unquoted_value = value.strip('"')
# Quick-OR is a convenient way to write one condition that matches any one of
# multiple values, like set membership. E.g., [Priority=High,Critical].
# Ignore empty values caused by duplicated or trailing commas. E.g.,
# [Priority=High,,Critical,] is equivalent to [Priority=High,Critical].
quick_or_vals = [v.strip() for v in unquoted_value.split(',') if v.strip()]
op = OPS[op_str]
negate = False
if prefix.startswith('-'):
negate = True
op = NEGATED_OPS.get(op, op)
prefix = prefix[1:]
if prefix == 'is' and unquoted_value in [
'open', 'blocked', 'spam', 'ownerbouncing']:
return ast_pb2.MakeCond(
NE if negate else EQ, fields[unquoted_value], [], [])
# Search entries with or without any value in the specified field.
if prefix == 'has':
op = IS_NOT_DEFINED if negate else IS_DEFINED
if '.' in unquoted_value: # Possible search for phase field with any value.
phase_name, possible_field = unquoted_value.split('.', 1)
if possible_field in fields:
return ast_pb2.MakeCond(
op, fields[possible_field], [], [], phase_name=phase_name)
elif unquoted_value in fields: # Look for that field with any value.
return ast_pb2.MakeCond(op, fields[unquoted_value], [], [])
else: # Look for any label with that prefix.
return ast_pb2.MakeCond(op, fields['label'], [unquoted_value], [])
# Search entries with certain gates.
if prefix == 'gate':
return ast_pb2.MakeCond(op, fields['gate'], quick_or_vals, [])
# Determine hotlist query type.
# If prefix is not 'hotlist', quick_or_vals is empty, or qov
# does not contain ':', is_fields will remain True
is_fields = True
if prefix == 'hotlist':
try:
if ':' not in quick_or_vals[0]:
is_fields = False
except IndexError:
is_fields = False
phase_name = None
if '.' in prefix and is_fields:
split_prefix = prefix.split('.', 1)
if split_prefix[1] in fields:
phase_name, prefix = split_prefix
# search built-in and custom fields. E.g., summary.
if prefix in fields and is_fields:
# Note: if first matching field is date-type, we assume they all are.
# TODO(jrobbins): better handling for rare case where multiple projects
# define the same custom field name, and one is a date and another is not.
first_field = fields[prefix][0]
if first_field.field_type == DATE:
date_values = [_ParseDateValue(val, now=now) for val in quick_or_vals]
return ast_pb2.MakeCond(op, fields[prefix], [], date_values)
elif first_field.field_type == APPROVAL and prefix.endswith(SET_ON_SUFFIX):
date_values = [_ParseDateValue(val, now=now) for val in quick_or_vals]
return ast_pb2.MakeCond(
op,
fields[prefix], [],
date_values,
key_suffix=SET_ON_SUFFIX,
phase_name=phase_name)
else:
quick_or_ints = []
for qov in quick_or_vals:
try:
quick_or_ints.append(int(qov))
except ValueError:
pass
if first_field.field_type == APPROVAL:
for approval_suffix in _APPROVAL_SUFFIXES:
if prefix.endswith(approval_suffix):
return ast_pb2.MakeCond(op, fields[prefix], quick_or_vals,
quick_or_ints, key_suffix=approval_suffix,
phase_name=phase_name)
return ast_pb2.MakeCond(op, fields[prefix], quick_or_vals,
quick_or_ints, phase_name=phase_name)
# Since it is not a field, treat it as labels, E.g., Priority.
quick_or_labels = ['%s-%s' % (prefix, v) for v in quick_or_vals]
# Convert substring match to key-value match if user typed 'foo:bar'.
if op == TEXT_HAS:
op = KEY_HAS
return ast_pb2.MakeCond(op, fields['label'], quick_or_labels, [])
def _ExtractConds(query, warnings):
# type: (str, Sequence[str]) -> Sequence[str]
"""Parse a query string into a list of individual condition strings.
Args:
query: UTF-8 encoded search query string.
warnings: list to accumulate warning messages.
Returns:
A list of query condition strings.
"""
# Convert to unicode then search for distinct terms.
term_matches = TERM_RE.findall(query)
terms = []
for (phrase, word_label, _op1, phrase_label, _op2,
word) in term_matches:
# Case 1: Quoted phrases, e.g., ["hot dog"].
if phrase_label or phrase:
terms.append(phrase_label or phrase)
# Case 2: Comparisons
elif word_label:
special_prefixes_match = any(
word_label.startswith(p) for p in NON_OP_PREFIXES)
match = OP_RE.match(word_label)
if match and not special_prefixes_match:
label = match.group('prefix')
op = match.group('op')
word = match.group('value')
terms.append('%s%s"%s"' % (label, op, word))
else:
# It looked like a key:value cond, but not exactly, so treat it
# as fulltext search. It is probably a tiny bit of source code.
terms.append('"%s"' % word_label)
# Case 3: Simple words.
elif word:
terms.append(word)
else: # pragma: no coverage
warnings.append('Unparsable search term')
return terms
def _ParseDateValue(val, now=None):
# type: (str, int) -> int
"""Convert the user-entered date into timestamp."""
# Support timestamp value such as opened>1437671476
try:
return int(val)
except ValueError:
pass
# TODO(jrobbins): future: take timezones into account.
# TODO(jrobbins): for now, explain to users that "today" is
# actually now: the current time, not 12:01am in their timezone.
# In fact, it is not very useful because everything in the system
# happened before the current time.
if val == 'today':
return _CalculatePastDate(0, now=now)
elif val.startswith('today-'):
try:
days_ago = int(val.split('-')[1])
except ValueError:
raise InvalidQueryError('Could not parse date: ' + val)
return _CalculatePastDate(days_ago, now=now)
try:
if '/' in val:
year, month, day = [int(x) for x in val.split('/')]
elif '-' in val:
year, month, day = [int(x) for x in val.split('-')]
else:
raise InvalidQueryError('Could not parse date: ' + val)
except ValueError:
raise InvalidQueryError('Could not parse date: ' + val)
try:
return int(time.mktime(datetime.datetime(year, month, day).timetuple()))
except ValueError:
raise InvalidQueryError('Could not parse date: ' + val)
def _CalculatePastDate(days_ago, now=None):
# type: (int, int) -> int
"""Calculates the timestamp N days ago from now."""
if now is None:
now = int(time.time())
ts = now - days_ago * 24 * 60 * 60
return ts
def QueryToSubqueries(query):
# type (str) -> Sequence[str]
"""Splits a query into smaller queries based on Monorail's search syntax.
This function handles parsing parentheses and OR statements in Monorail's
search syntax. By doing this parsing for OR statements and parentheses up
front in FrontendSearchPipeline, we are able to convert complex queries
with lots of ORs into smaller, more easily cacheable query terms.
These outputted subqueries should collectively return the same query results
as the initial input query without containing any ORs or parentheses,
allowing later search layers to parse queries without worrying about ORs
or parentheses.
Some examples of possible queries and their expected output:
- '(A OR B) (C OR D) OR (E OR F)' -> ['A C', 'A D', 'B C', 'B D', 'E', 'F']
- '(A) OR (B)' -> ['A', 'B']
- '(A ((C) OR (D OR (E OR F))))' -> ['A C', 'A D', 'A E', 'A F']
Where A, B, C, D, etc could be any list of conjunctions. ie: "owner:me",
"Pri=1", "hello world Hotlist=test", "label!=a11y", etc
Note: Monorail implicitly ANDs any query terms separated by a space. For
the most part, AND functionality is handled at a later layer in search
processing. However, this case becomes important here when considering the
fact that a prentheses group can either be ANDed or ORed with terms that
surround it.
The _MultiplySubqueries helper is used to AND the results of different
groups together whereas concatenating lists is used to OR subqueries
together.
Args:
query: The initial query that was sent to the search.
Returns:
List of query fragments to be independently processed as search terms.
Raises:
InvalidQueryError if parentheses are unmatched.
"""
tokens = _ValidateAndTokenizeQuery(query)
# Using an iterator allows us to keep our current loop position across
# helpers. This makes recursion a lot easier.
token_iterator = PeekIterator(tokens)
subqueries = _ParseQuery(token_iterator)
if not len(subqueries):
# Several cases, such as an empty query or a query with only parentheses
# will result in an empty set of subqueries. In these cases, we still want
# to give the search pipeline a single empty query to process.
return ['']
return subqueries
def _ParseQuery(token_iterator):
# type (Sequence[proto.ast_pb2.QueryToken]) -> Sequence[str]
"""Recursive helper to convert query tokens into a list of subqueries.
Parses a Query based on the following grammar (EBNF):
Query := OrGroup { [OrOperator] OrGroup }
OrGroup := AndGroup { AndGroup }
AndGroup := Subquery | ParenthesesGroup
ParenthesesGroup := "(" Query ")"
Subquery := /.+/
OrOperator := " OR "
An important nuance is that two groups can be next to each other, separated
only by a word boundary (ie: space or parentheses). In this case, they are
implicitly ANDed. In practice, because unparenthesized fragments ANDed by
spaces are stored as single tokens, we only need to handle the AND case when
a parentheses group is implicitly ANDed with an adjacent group.
Order of precedence is implemented by recursing through OR groups before
recursing through AND groups.
Args:
token_iterator: Iterator over a list of query tokens.
Returns:
List of query fragments to be processed as search terms.
Raises:
InvalidQueryError if tokens were inputted in a format that does not follow
our search grammar.
"""
subqueries = []
try:
if token_iterator.peek().token_type == OR:
# Edge case: Ignore empty OR groups at the starte of a ParenthesesGroup.
# ie: "(OR A)" will be processed as "A"
next(token_iterator)
subqueries = _ParseOrGroup(token_iterator)
while token_iterator.peek().token_type == OR:
# Consume the OR tokens without doing anything with it.
next(token_iterator)
next_token = token_iterator.peek()
if next_token.token_type == RIGHT_PAREN:
# Edge case: Ignore empty OR groups at the end of a ParenthesesGroup.
# ie: "(A OR)" will be processed as "A"
return subqueries
next_subqueries = _ParseOrGroup(token_iterator)
# Concatenate results of OR groups together.
subqueries = subqueries + next_subqueries
except StopIteration:
pass
# Return when we've reached the end of the string.
return subqueries
def _ParseOrGroup(token_iterator):
# type (Sequence[proto.ast_pb2.QueryToken]) -> Sequence[str]
"""Recursive helper to convert a single "OrGroup" into subqueries.
An OrGroup here is based on the following grammar:
Query := OrGroup { [OrOperator] OrGroup }
OrGroup := AndGroup { AndGroup }
AndGroup := Subquery | ParenthesesGroup
ParenthesesGroup := "(" Query ")"
Subquery := /.+/
OrOperator := " OR "
Args:
token_iterator: Iterator over a list of query tokens.
Returns:
List of query fragments to be processed as search terms.
Raises:
InvalidQueryError if tokens were inputted in a format that does not follow
our search grammar.
"""
subqueries = _ParseAndGroup(token_iterator)
try:
# Iterate until there are no more AND groups left to see.
# Subquery or left parentheses are the possible starts of an AndGroup.
while (token_iterator.peek().token_type == SUBQUERY or
token_iterator.peek().token_type == LEFT_PAREN):
# Find subqueries from the next AND group.
next_subqueries = _ParseAndGroup(token_iterator)
# Multiply all results across AND groups together.
subqueries = _MultiplySubqueries(subqueries, next_subqueries)
except StopIteration:
pass
return subqueries
def _ParseAndGroup(token_iterator):
# type (Sequence[proto.ast_pb2.QueryToken]) -> Sequence[str]
"""Recursive helper to convert a single "AndGroup" into subqueries.
An OrGroup here is based on the following grammar:
Query := OrGroup { [OrOperator] OrGroup }
OrGroup := AndGroup { AndGroup }
AndGroup := Subquery | ParenthesesGroup
ParenthesesGroup := "(" Query ")"
Subquery := /.+/
OrOperator := " OR "
Args:
token_iterator: Iterator over a list of query tokens.
Returns:
List of query fragments to be processed as search terms.
Raises:
InvalidQueryError if tokens were inputted in a format that does not follow
our search grammar.
"""
try:
token = next(token_iterator)
if token.token_type == LEFT_PAREN:
if token_iterator.peek().token_type == RIGHT_PAREN:
# Don't recurse into the ParenthesesGroup if there's nothing inside.
next(token_iterator)
return []
# Recurse into the ParenthesesGroup.
subqueries = _ParseQuery(token_iterator)
# Next token should be a right parenthesis.
next(token_iterator)
return subqueries
elif token.token_type == SUBQUERY:
return [token.value]
else:
# This should not happen if other QueryToSubqueries helpers are working
# properly.
raise InvalidQueryError('Inputted tokens do not follow grammar.')
except StopIteration:
pass
return []
def _ValidateAndTokenizeQuery(query):
# type: (str) -> Sequence[proto.ast_pb2.QueryToken]
"""Converts the input query into a set of tokens for easier parsing.
Tokenizing the query string before parsing allows us to not have to as many
string manipulations while parsing, which simplifies our later code.
Args:
query: Query to tokenize.
Returns:
List of Token objects for use in query processing.
Raises:
InvalidQueryError if parentheses are unmatched.
"""
tokens = [] # Function result
count = 0 # Used for checking if parentheses are balanced
s = '' # Records current string fragment. Cleared when a token is added.
for ch in query:
if ch == '(':
count += 1
# Add subquery from before we hit this parenthesis.
tokens.extend(_TokenizeSubqueryOnOr(s))
s = ''
tokens.append(ast_pb2.QueryToken(token_type=LEFT_PAREN))
elif ch == ')':
count -= 1
if count < 0:
# More closing parentheses then open parentheses.
raise InvalidQueryError('Search query has unbalanced parentheses.')
# Add subquery from before we hit this parenthesis.
tokens.extend(_TokenizeSubqueryOnOr(s))
s = ''
tokens.append(ast_pb2.QueryToken(token_type=RIGHT_PAREN))
else:
s += ch
if count != 0:
raise InvalidQueryError('Search query has unbalanced parentheses.')
# Add any trailing tokens.
tokens.extend(_TokenizeSubqueryOnOr(s))
return tokens
def _TokenizeSubqueryOnOr(subquery):
# type: (str) -> Sequence[proto.ast_pb2.QueryToken]
"""Helper to split a subquery by OR and convert the result into tokens.
Args:
subquery: A string without parentheses to tokenize.
Returns:
Tokens for the subquery with OR tokens separating query strings if
applicable.
"""
if len(subquery) == 0:
return []
result = []
fragments = subquery.split(OR_SYMBOL)
for f in fragments:
# Interleave the string fragments with OR tokens.
result.append(ast_pb2.QueryToken(token_type=SUBQUERY, value=f.strip()))
result.append(ast_pb2.QueryToken(token_type=OR))
# Remove trailing OR.
result.pop()
# Trim empty strings at the beginning or end. ie: if subquery is ' OR ',
# we want the list to be ['OR'], not ['', 'OR', ''].
if len(result) > 1 and result[0].value == '':
result.pop(0)
if len(result) > 1 and result[-1].value == '':
result.pop()
return result
def _MultiplySubqueries(a, b):
# type: (Sequence[str], Sequence[str]) -> Sequence[str]
"""Helper to AND subqueries from two separate lists.
Args:
a: First list of subqueries.
b: Second list of subqueries.
Returns:
List with n x m subqueries.
"""
if not len(a):
return b
if not len(b):
return a
res = []
for q1 in a:
for q2 in b:
# AND two subqueries together by concatenating them.
query = (q1.strip() + ' ' + q2.strip()).strip()
res.append(query)
return res
class PeekIterator:
"""Simple iterator with peek() functionality.
Used by QueryToSubqueries to maintain state easily across recursive calls.
"""
def __init__(self, source):
# type: (Sequence[Any])
self.__source = source
self.__i = 0
def peek(self):
# type: () -> Any
"""Gets the next value in the iterator without side effects.
Returns:
Next value in iterator.
Raises:
StopIteration if you're at the end of the iterator.
"""
if self.__i >= len(self.__source):
raise StopIteration
return self.__source[self.__i]
def __iter__(self):
# type: () -> Sequence[Any]
"""Return self to make iterator iterable."""
return self
def __repr__(self):
# type: () -> str
"""Allow logging current iterator value for debugging."""
try:
return str(self.peek())
except StopIteration:
pass
return 'End of PeekIterator'
def next(self):
# type: () -> Any
"""Gets the next value in the iterator and increments pointer.
Returns:
Next value in iterator.
Raises:
StopIteration if you're at the end of the iterator.
"""
if self.__i >= len(self.__source):
raise StopIteration
value = self.__source[self.__i]
self.__i += 1
return value
class Error(Exception):
"""Base exception class for this package."""
pass
class InvalidQueryError(Error):
"""Error raised when an invalid query is requested."""
pass