#!/usr/bin/env python

#

# Copyright 2007 Google Inc.

#

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

#

#     http://www.apache.org/licenses/LICENSE-2.0

#

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

#

"""GQL -- the SQL-like interface to the datastore.

Defines the GQL-based query class, which is a query mechanism

for the datastore which provides an alternative model for interacting with

data stored.

"""

import calendar

import datetime

import heapq

import logging

import re

import time

from google.appengine.api import datastore

from google.appengine.api import datastore_errors

from google.appengine.api import datastore_types

from google.appengine.api import users

LOG_LEVEL = logging.DEBUG - 1

_EPOCH = datetime.datetime.utcfromtimestamp(0)

def Execute(query_string, *args, **keyword_args):

  """Execute command to parse and run the query.

  Calls the query parser code to build a proto-query which is an

  unbound query. The proto-query is then bound into a real query and

  executed.

  Args:

    query_string: properly formatted GQL query string.

    args: rest of the positional arguments used to bind numeric references in

          the query.

    keyword_args: dictionary-based arguments (for named parameters).

  Returns:

    the result of running the query with *args.

  """

  app = keyword_args.pop('_app', None)

  proto_query = GQL(query_string, _app=app)

  return proto_query.Bind(args, keyword_args).Run()

class GQL(object):

  """A GQL interface to the datastore.

  GQL is a SQL-like language which supports more object-like semantics

  in a langauge that is familiar to SQL users. The language supported by

  GQL will change over time, but will start off with fairly simple

  semantics.

  - reserved words are case insensitive

  - names are case sensitive

  The syntax for SELECT is fairly straightforward:

  SELECT * FROM <entity>

    [WHERE <condition> [AND <condition> ...]]

    [ORDER BY <property> [ASC | DESC] [, <property> [ASC | DESC] ...]]

    [LIMIT [<offset>,]<count>]

    [OFFSET <offset>]

    [HINT (ORDER_FIRST | HINT FILTER_FIRST | HINT ANCESTOR_FIRST)]

  <condition> := <property> {< | <= | > | >= | = | != | IN} <value>

  <condition> := <property> {< | <= | > | >= | = | != | IN} CAST(<value>)

  <condition> := <property> IN (<value>, ...)

  <condition> := ANCESTOR IS <entity or key>

  Currently the parser is LL(1) because of the simplicity of the grammer

  (as it is largely predictive with one token lookahead).

  The class is implemented using some basic regular expression tokenization

  to pull out reserved tokens and then the recursive descent parser will act

  as a builder for the pre-compiled query. This pre-compiled query is then

  bound to arguments before executing the query.

  Initially, three parameter passing mechanisms are supported when calling

  Execute():

  - Positional parameters

  Execute('SELECT * FROM Story WHERE Author = :1 AND Date > :2')

  - Named parameters

  Execute('SELECT * FROM Story WHERE Author = :author AND Date > :date')

  - Literals (numbers, and strings)

  Execute('SELECT * FROM Story WHERE Author = \'James\'')

  Users are also given the option of doing type conversions to other datastore

  types (e.g. db.Email, db.GeoPt). The language provides a conversion function

  which allows the caller to express conversions of both literals and

  parameters. The current conversion operators are:

  - GEOPT(float, float)

  - USER(str)

  - KEY(kind, id/name[, kind, id/name...])

  - DATETIME(year, month, day, hour, minute, second)

  - DATETIME('YYYY-MM-DD HH:MM:SS')

  - DATE(year, month, day)

  - DATE('YYYY-MM-DD')

  - TIME(hour, minute, second)

  - TIME('HH:MM:SS')

  We will properly serialize and quote all values.

  It should also be noted that there are some caveats to the queries that can

  be expressed in the syntax. The parser will attempt to make these clear as

  much as possible, but some of the caveats include:

    - There is no OR operation. In most cases, you should prefer to use IN to

      express the idea of wanting data matching one of a set of values.

    - You cannot express inequality operators on multiple different properties

    - You can only have one != operator per query (related to the previous

      rule).

    - The IN and != operators must be used carefully because they can

      dramatically raise the amount of work done by the datastore. As such,

      there is a limit on the number of elements you can use in IN statements.

      This limit is set fairly low. Currently, a max of 30 datastore queries is

      allowed in a given GQL query. != translates into 2x the number of

      datastore queries, and IN multiplies by the number of elements in the

      clause (so having two IN clauses, one with 5 elements, the other with 6

      will cause 30 queries to occur).

    - Literals can take the form of basic types or as type-cast literals. On

      the other hand, literals within lists can currently only take the form of

      simple types (strings, integers, floats).

  SELECT * will return an iterable set of entries, but other operations (schema

  queries, updates, inserts or field selections) will return alternative

  result types.

  """

  TOKENIZE_REGEX = re.compile(r"""

    (?:'[^'\n\r]*')+|

    <=|>=|!=|=|<|>|

    :\w+|

    ,|

    \*|

    -?\d+(?:\.\d+)?|

    \w+|

    \(|\)|

    \S+

    """, re.VERBOSE | re.IGNORECASE)

  MAX_ALLOWABLE_QUERIES = 30

  __ANCESTOR = -1

  def __init__(self, query_string, _app=None, _auth_domain=None):

    """Ctor.

    Parses the input query into the class as a pre-compiled query, allowing

    for a later call to Bind() to bind arguments as defined in the

    documentation.

    Args:

      query_string: properly formatted GQL query string.

    Raises:

      datastore_errors.BadQueryError: if the query is not parsable.

    """

    self._entity = ''

    self.__filters = {}

    self.__has_ancestor = False

    self.__orderings = []

    self.__offset = -1

    self.__limit = -1

    self.__hint = ''

    self.__app = _app

    self.__auth_domain = _auth_domain

    self.__symbols = self.TOKENIZE_REGEX.findall(query_string)

    self.__next_symbol = 0

    if not self.__Select():

      raise datastore_errors.BadQueryError(

          'Unable to parse query')

    else:

      pass

  def Bind(self, args, keyword_args):

    """Bind the existing query to the argument list.

    Assumes that the input args are first positional, then a dictionary.

    So, if the query contains references to :1, :2 and :name, it is assumed

    that arguments are passed as (:1, :2, dict) where dict contains a mapping

    [name] -> value.

    Args:

      args: the arguments to bind to the object's unbound references.

      keyword_args: dictionary-based arguments (for named parameters).

    Raises:

      datastore_errors.BadArgumentError: when arguments are left unbound

        (missing from the inputs arguments) or when arguments do not match the

        expected type.

    Returns:

      The bound datastore.Query object. This may take the form of a MultiQuery

      object if the GQL query will require multiple backend queries to statisfy.

    """

    num_args = len(args)

    input_args = frozenset(xrange(num_args))

    used_args = set()

    queries = []

    enumerated_queries = self.EnumerateQueries(used_args, args, keyword_args)

    if enumerated_queries:

      query_count = len(enumerated_queries)

    else:

      query_count = 1

    for i in xrange(query_count):

      queries.append(datastore.Query(self._entity, _app=self.__app))

    logging.log(LOG_LEVEL,

                'Binding with %i positional args %s and %i keywords %s'

                , len(args), args, len(keyword_args), keyword_args)

    for ((identifier, condition), value_list) in self.__filters.iteritems():

      for (operator, params) in value_list:

        value = self.__Operate(args, keyword_args, used_args, operator, params)

        if not self.__IsMultiQuery(condition):

          for query in queries:

            self.__AddFilterToQuery(identifier, condition, value, query)

    unused_args = input_args - used_args

    if unused_args:

      unused_values = [unused_arg + 1 for unused_arg in unused_args]

      raise datastore_errors.BadArgumentError('Unused positional arguments %s' %

                                              unused_values)

    if enumerated_queries:

      logging.debug('Multiple Queries Bound: %s' % enumerated_queries)

      for (query, enumerated_query) in zip(queries, enumerated_queries):

        query.update(enumerated_query)

    if self.__orderings:

      for query in queries:

        query.Order(*tuple(self.__orderings))

    if query_count > 1:

      return MultiQuery(queries, self.__orderings)

    else:

      return queries[0]

  def EnumerateQueries(self, used_args, args, keyword_args):

    """Create a list of all multi-query filter combinations required.

    To satisfy multi-query requests ("IN" and "!=" filters), multiple queries

    may be required. This code will enumerate the power-set of all multi-query

    filters.

    Args:

      used_args: set of used positional parameters (output only variable used in

        reporting for unused positional args)

      args: positional arguments referenced by the proto-query in self. This

        assumes the input is a tuple (and can also be called with a varargs

        param).

      keyword_args: dict of keyword arguments referenced by the proto-query in

        self.

    Returns:

      A list of maps [(identifier, condition) -> value] of all queries needed

      to satisfy the GQL query with the given input arguments.

    """

    enumerated_queries = []

    for ((identifier, condition), value_list) in self.__filters.iteritems():

      for (operator, params) in value_list:

        value = self.__Operate(args, keyword_args, used_args, operator, params)

        self.__AddMultiQuery(identifier, condition, value, enumerated_queries)

    return enumerated_queries

  def __CastError(self, operator, values, error_message):

    """Query building error for type cast operations.

    Args:

      operator: the failed cast operation

      values: value list passed to the cast operator

      error_message: string to emit as part of the 'Cast Error' string.

    Raises:

      BadQueryError and passes on an error message from the caller. Will raise

      BadQueryError on all calls.

    """

    raise datastore_errors.BadQueryError(

        'Type Cast Error: unable to cast %r with operation %s (%s)' %

        (values, operator.upper(), error_message))

  def __CastNop(self, values):

    """Return values[0] if it exists -- default for most where clauses."""

    if len(values) != 1:

      self.__CastError(values, 'nop', 'requires one and only one value')

    else:

      return values[0]

  def __CastList(self, values):

    """Return the full list of values -- only useful for IN clause."""

    if values:

      return values

    else:

      return None

  def __CastKey(self, values):

    """Cast input values to Key() class using encoded string or tuple list."""

    if not len(values) % 2:

      return datastore_types.Key.from_path(_app=self.__app, *values)

    elif len(values) == 1 and isinstance(values[0], str):

      return datastore_types.Key(values[0])

    else:

      self.__CastError('KEY', values,

                       'requires an even number of operands'

                       'or a single encoded string')

  def __CastGeoPt(self, values):

    """Cast input to GeoPt() class using 2 input parameters."""

    if len(values) != 2:

      self.__CastError('GEOPT', values, 'requires 2 input parameters')

    return datastore_types.GeoPt(*values)

  def __CastUser(self, values):

    """Cast to User() class using the email address in values[0]."""

    if len(values) != 1:

      self.__CastError(values, 'user', 'requires one and only one value')

    else:

      return users.User(email=values[0], _auth_domain=self.__auth_domain)

  def __CastDate(self, values):

    """Cast date values to DATETIME() class using ISO string or tuple inputs."""

    try:

      if len(values) == 1 and isinstance(values[0], str):

        time_tuple = time.strptime(values[0], '%Y-%m-%d')

        return datetime.datetime(*time_tuple[0:6])

      else:

        return datetime.datetime(values[0], values[1], values[2], 0, 0, 0)

    except ValueError, err:

      self.__CastError('DATE', values, err)

  def __CastTime(self, values):

    """Cast time values to DATETIME() class using ISO string or tuple inputs."""

    try:

      if len(values) == 1 and isinstance(values[0], str):

        time_tuple = time.strptime(values[0], '%H:%M:%S')

        time_tuple = (1970, 1, 1) + time_tuple[3:]

        return datetime.datetime(*time_tuple[0:6])

      else:

        return datetime.datetime(1970, 1, 1, *values)

    except ValueError, err:

      self.__CastError('TIME', values, err)

  def __CastDatetime(self, values):

    """Cast values to DATETIME() class using ISO string or tuple inputs."""

    try:

      if len(values) == 1 and isinstance(values[0], str):

        time_tuple = time.strptime(values[0], '%Y-%m-%d %H:%M:%S')

        return datetime.datetime(*time_tuple[0:6])

      else:

        return datetime.datetime(*values)

    except ValueError, err:

      self.__CastError('DATETIME', values, err)

  def __Operate(self, args, keyword_args, used_args, operator, params):

    """Create a single output value from params using the operator string given.

    Args:

      args,keyword_args: arguments passed in for binding purposes (used in

          binding positional and keyword based arguments).

      used_args: set of numeric arguments accessed in this call.

          values are ints representing used zero-based positional arguments.

          used as an output parameter with new used arguments appended to the

          list.

      operator: string representing the operator to use 'nop' just returns

          the first value from params.

      params: parameter list to operate on (positional references, named

          references, or literals).

    Returns:

      A value which can be used as part of a GQL filter description (either a

      list of datastore types -- for use with IN, or a single datastore type --

      for use with other filters).

    """

    if not params:

      return None

    param_values = []

    for param in params:

      if isinstance(param, Literal):

        value = param.Get()

      else:

        value = self.__GetParam(param, args, keyword_args)

        if isinstance(param, int):

          used_args.add(param - 1)

        logging.log(LOG_LEVEL, 'found param for bind: %s value: %s',

                    param, value)

      param_values.append(value)

    logging.log(LOG_LEVEL, '%s Operating on values: %s',

                operator, repr(param_values))

    if operator in self.__cast_operators:

      result = self.__cast_operators[operator](self, param_values)

    else:

      self.__Error('Operation %s is invalid' % operator)

    return result

  def __IsMultiQuery(self, condition):

    """Return whether or not this condition could require multiple queries."""

    return condition.lower() in ('in', '!=')

  def __GetParam(self, reference, args, keyword_args):

    """Get the specified parameter from the input arguments.

    Args:

      reference: id for a filter reference in the filter list (string or

          number)

      args: positional args passed in by the user (tuple of arguments, indexed

          numerically by "reference")

      keyword_args: dict of keyword based arguments (strings in "reference")

    Returns:

      The specified param from the input list.

    Raises:

      BadArgumentError if the referenced argument doesn't exist.

    """

    num_args = len(args)

    if isinstance(reference, int):

      if reference <= num_args:

        return args[reference - 1]

      else:

        raise datastore_errors.BadArgumentError(

            'Missing argument for bind, requires argument #%i, '

            'but only has %i args.' % (reference, num_args))

    elif isinstance(reference, str):

      if reference in keyword_args:

        return keyword_args[reference]

      else:

        raise datastore_errors.BadArgumentError(

            'Missing named arguments for bind, requires argument %s' %

            reference)

    else:

      assert False, 'Unknown reference %s' % reference

  def __AddMultiQuery(self, identifier, condition, value, enumerated_queries):

    """Helper function to add a muti-query to previously enumerated queries.

    Args:

      identifier: property being filtered by this condition

      condition: filter condition (e.g. !=,in)

      value: value being bound

      enumerated_queries: in/out list of already bound queries -> expanded list

        with the full enumeration required to satisfy the condition query

    Raises:

      BadArgumentError if the filter is invalid (namely non-list with IN)

    """

    def CloneQueries(queries, n):

      """Do a full copy of the queries and append to the end of the queries.

      Does an in-place replication of the input list and sorts the result to

      put copies next to one-another.

      Args:

        queries: list of all filters to clone

        n: number of copies to make

      Returns:

        Number of iterations needed to fill the structure

      """

      if not enumerated_queries:

        for i in xrange(n):

          queries.append({})

        return 1

      else:

        old_size = len(queries)

        tmp_queries = []

        for i in xrange(n - 1):

          [tmp_queries.append(filter_map.copy()) for filter_map in queries]

        queries.extend(tmp_queries)

        queries.sort()

        return old_size

    if condition == '!=':

      if len(enumerated_queries) * 2 > self.MAX_ALLOWABLE_QUERIES:

        raise datastore_errors.BadArgumentError(

          'Cannot satisfy query -- too many IN/!= values.')

      num_iterations = CloneQueries(enumerated_queries, 2)

      for i in xrange(num_iterations):

        enumerated_queries[2 * i]['%s <' % identifier] = value

        enumerated_queries[2 * i + 1]['%s >' % identifier] = value

    elif condition.lower() == 'in':

      if not isinstance(value, list):

        raise datastore_errors.BadArgumentError('List expected for "IN" filter')

      in_list_size = len(value)

      if len(enumerated_queries) * in_list_size > self.MAX_ALLOWABLE_QUERIES:

        raise datastore_errors.BadArgumentError(

          'Cannot satisfy query -- too many IN/!= values.')

      num_iterations = CloneQueries(enumerated_queries, in_list_size)

      for clone_num in xrange(num_iterations):

        for value_num in xrange(len(value)):

          list_val = value[value_num]

          query_num = in_list_size * clone_num + value_num

          filt = '%s =' % identifier

          enumerated_queries[query_num][filt] = list_val