#!/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 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

MultiQuery = datastore.MultiQuery

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 [* | __key__ ] [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, strings, booleans, and NULL)

  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 entities; SELECT __key__ will return

  an iterable set of Keys.

  """

  TOKENIZE_REGEX = re.compile(r"""

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

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

    :\w+|

    ,|

    \*|

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

    \w+|

    \(|\)|

    \S+

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

  MAX_ALLOWABLE_QUERIES = datastore.MAX_ALLOWABLE_QUERIES

  __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,

                                     keys_only=self._keys_only))

    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.log(LOG_LEVEL,

                  '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], basestring):

      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('user', values, 'requires one and only one value')

    elif values[0] is None:

      self.__CastError('user', values, 'must be non-null')

    else:

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

  def __EncodeIfNeeded(self, value):

    """Simple helper function to create an str from possibly unicode strings.

    Args:

      value: input string (should pass as an instance of str or unicode).

    """

    if isinstance(value, unicode):

      return value.encode('utf8')

    else:

      return value

  def __CastDate(self, values):

    """Cast DATE values (year/month/day) from input (to datetime.datetime).

    Casts DATE input values formulated as ISO string or time tuple inputs.

    Args:

      values: either a single string with ISO time representation or 3

              integer valued date tuple (year, month, day).

    Returns:

      datetime.datetime value parsed from the input values.

    """

    if len(values) == 1:

      value = self.__EncodeIfNeeded(values[0])

      if isinstance(value, str):

        try:

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

        except ValueError, err:

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

      else:

        self.__CastError('DATE', values, 'Single input value not a string')

    elif len(values) == 3:

      time_tuple = (values[0], values[1], values[2], 0, 0, 0)

    else:

      self.__CastError('DATE', values,

                       'function takes 1 string or 3 integer values')

    try:

      return datetime.datetime(*time_tuple)

    except ValueError, err:

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

  def __CastTime(self, values):

    """Cast TIME values (hour/min/sec) from input (to datetime.datetime).

    Casts TIME input values formulated as ISO string or time tuple inputs.

    Args:

      values: either a single string with ISO time representation or 1-4

              integer valued time tuple (hour), (hour, minute),

              (hour, minute, second), (hour, minute, second, microsec).

    Returns:

      datetime.datetime value parsed from the input values.

    """

    if len(values) == 1:

      value = self.__EncodeIfNeeded(values[0])

      if isinstance(value, str):

        try:

          time_tuple = time.strptime(value, '%H:%M:%S')

        except ValueError, err:

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

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

        time_tuple = time_tuple[0:6]

      elif isinstance(value, int):

        time_tuple = (1970, 1, 1, value)

      else:

        self.__CastError('TIME', values,

                         'Single input value not a string or integer hour')

    elif len(values) <= 4:

      time_tuple = (1970, 1, 1) + tuple(values)

    else:

      self.__CastError('TIME', values,

                       'function takes 1 to 4 integers or 1 string')

    try:

      return datetime.datetime(*time_tuple)

    except ValueError, err:

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

  def __CastDatetime(self, values):

    """Cast DATETIME values (string or tuple) from input (to datetime.datetime).

    Casts DATETIME input values formulated as ISO string or datetime tuple

    inputs.

    Args:

      values: either a single string with ISO representation or 3-7

              integer valued time tuple (year, month, day, ...).

    Returns:

      datetime.datetime value parsed from the input values.

    """

    if len(values) == 1:

      value = self.__EncodeIfNeeded(values[0])

      if isinstance(value, str):

        try:

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

        except ValueError, err:

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

      else:

        self.__CastError('DATETIME', values, 'Single input value not a string')

    else:

      time_tuple = values

    try:

      return datetime.datetime(*time_tuple)

    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")