files: """
  This module contains shared encoding and decoding utilities for translating
  datastore types to bytestrings and vice versa.
  """
  import bisect
  import logging
  import struct
  import sys
  
  import six
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.dbconstants import BadRequest, InternalError
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import entity_pb
  
  # The number of bytes used to encode a read version in a way that is comparable
  # to commit versionstamps.
  READ_VERSION_SIZE = 8
  
  # Byte values that signify a data type. A couple values are left between each
  # one just in case they need adjustment.
  NULL_CODE = 0x01
  # 17 values are reserved for integers in order to allow variable size in both a
  # negative and positive direction.
  INT64_ZERO_CODE = 0x0C
  FALSE_CODE = 0x17
  TRUE_CODE = 0x18
  BYTES_CODE = 0x1B
  DOUBLE_CODE = 0x1E
  POINT_CODE = 0x21
  USER_CODE = 0x24
  REFERENCE_CODE = 0x27
  
  # These are defined for clarity when selecting property type limits.
  MIN_INT64_CODE = INT64_ZERO_CODE - 8
  MAX_INT64_CODE = INT64_ZERO_CODE + 8
  
  # Ensures the shorter of two variable-length values (with identical prefixes)
  # is placed before the longer one. Otherwise, the following byte(s) could
  # determine the sort order. It also allows a decoder to find the end of the
  # value.
  TERMINATOR = 0x00
  
  logger = logging.getLogger(__name__)
  
  
  def reverse_bits(blob):
    return b''.join(map(lambda x: six.int2byte(x ^ 0xFF), six.iterbytes(blob)))
  
  
  def encode_marker(marker, reverse):
    return six.int2byte(marker ^ 0xFF) if reverse else six.int2byte(marker)
  
  
  def decode_str(string):
    """ Converts byte strings to unicode strings. """
    if isinstance(string, six.text_type):
      return string
  
    return string.decode('utf-8')
  
  
  class Int64(object):
    """
    Handles encoding and decoding operations for 64-bit integers. The encoded
    value is variable-length. The value of the marker indicates how many bytes
    were used to encode the value.
    """
    LIMITS = tuple((1 << (i * 8)) - 1 for i in range(9))
  
    @classmethod
    def encode(cls, value, reverse=False):
      if value == 0:
        code = INT64_ZERO_CODE
        packed = b''
      elif value > 0:
        encoded_size = bisect.bisect_left(cls.LIMITS, value)
        adjusted_value = cls.LIMITS[encoded_size] - value if reverse else value
        code = INT64_ZERO_CODE + encoded_size
        packed = struct.pack('>Q', adjusted_value)[-encoded_size:]
      else:
        encoded_size = bisect.bisect_left(cls.LIMITS, -value)
        # Shift negative values to an unsigned space.
        adjusted_value = -value if reverse else cls.LIMITS[encoded_size] + value
        code = INT64_ZERO_CODE - encoded_size
        packed = struct.pack('>Q', adjusted_value)[-encoded_size:]
  
      return encode_marker(code, reverse) + packed
  
    @classmethod
    def decode(cls, marker, blob, pos, reverse=False):
      code = ord(marker) ^ 0xFF if reverse else ord(marker)
      if code == INT64_ZERO_CODE:
        return 0, pos
  
      encoded_size = abs(code - INT64_ZERO_CODE)
      packed = b'\x00' * (8 - encoded_size) + blob[pos:pos + encoded_size]
      pos += encoded_size
      value = struct.unpack('>Q', packed)[0]
      if code > INT64_ZERO_CODE:
        value = cls.LIMITS[encoded_size] - value if reverse else value
      else:
        # Shift values back to their original, negative state.
        value = -value if reverse else value - cls.LIMITS[encoded_size]
  
      return value, pos
  
    @classmethod
    def encode_bare(cls, value, byte_count):
      """
      Encodes an integer without a prefix using the specified number of bytes.
      """
      encoded = struct.pack('>Q', value)
      if any(byte != b'\x00' for byte in encoded[:-byte_count]):
        raise InternalError(u'Value exceeds maximum size')
  
      return encoded[-byte_count:]
  
    @classmethod
    def decode_bare(cls, encoded_value):
      """ Decodes a byte string back to an integer. """
      encoded_value = b'\x00' * (8 - len(encoded_value)) + encoded_value
      return struct.unpack('>Q', encoded_value)[0]
  
  
  class Bytes(object):
    """
    Handles encoding and decoding operations for arbitrary blobs. Since the
    length of the value is variable and there is usually data that follows the
    encoded value, a terminator byte is used to indicate the end of the value.
    Any occurrence of the terminator byte within the value is escaped in order to
    preserve the ordering and allow the parser to find the real terminator.
    """
    @classmethod
    def encode(cls, value, prefix=six.int2byte(BYTES_CODE), reverse=False):
      packed = reverse_bits(value) if reverse else value
      terminator = encode_marker(TERMINATOR, reverse)
      # Replace each occurrence of the terminator with a sequence that maintains
      # the sort order. In order for the parser to be able to find the end of the
      # value, directories that use this codec must ensure that the first byte
      # that follows the encoded Bytes object must not be 0x00 or 0xFF.
      if reverse:
        # The preceding 0xFE ensures a terminator character within the value
        # compares as less than the
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/codecs.py
files: """
  This module contains shared encoding and decoding utilities for translating
  datastore types to bytestrings and vice versa.
  """
  import bisect
  import logging
  import struct
  import sys
  
  import six
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.dbconstants import BadRequest, InternalError
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import entity_pb
  
  # The number of bytes used to encode a read version in a way that is comparable
  # to commit versionstamps.
  READ_VERSION_SIZE = 8
  
  # Byte values that signify a data type. A couple values are left between each
  # one just in case they need adjustment.
  NULL_CODE = 0x01
  # 17 values are reserved for integers in order to allow variable size in both a
  # negative and positive direction.
  INT64_ZERO_CODE = 0x0C
  FALSE_CODE = 0x17
  TRUE_CODE = 0x18
  BYTES_CODE = 0x1B
  DOUBLE_CODE = 0x1E
  POINT_CODE = 0x21
  USER_CODE = 0x24
  REFERENCE_CODE = 0x27
  
  # Ensures the shorter of two variable-length values (with identical prefixes)
  # is placed before the longer one. Otherwise, the following byte(s) could
  # determine the sort order. It also allows a decoder to find the end of the
  # value.
  TERMINATOR = 0x00
  
  logger = logging.getLogger(__name__)
  
  
  def reverse_bits(blob):
    return b''.join(map(lambda x: six.int2byte(x ^ 0xFF), six.iterbytes(blob)))
  
  
  def encode_marker(marker, reverse):
    return six.int2byte(marker ^ 0xFF) if reverse else six.int2byte(marker)
  
  
  def decode_str(string):
    """ Converts byte strings to unicode strings. """
    if isinstance(string, six.text_type):
      return string
  
    return string.decode('utf-8')
  
  
  class Int64(object):
    """
    Handles encoding and decoding operations for 64-bit integers. The encoded
    value is variable-length. The value of the marker indicates how many bytes
    were used to encode the value.
    """
    LIMITS = tuple((1 << (i * 8)) - 1 for i in range(9))
  
    @classmethod
    def encode(cls, value, reverse=False):
      if value == 0:
        code = INT64_ZERO_CODE
        packed = b''
      elif value > 0:
        encoded_size = bisect.bisect_left(cls.LIMITS, value)
        adjusted_value = cls.LIMITS[encoded_size] - value if reverse else value
        code = INT64_ZERO_CODE + encoded_size
        packed = struct.pack('>Q', adjusted_value)[-encoded_size:]
      else:
        encoded_size = bisect.bisect_left(cls.LIMITS, -value)
        # Shift negative values to an unsigned space.
        adjusted_value = -value if reverse else cls.LIMITS[encoded_size] + value
        code = INT64_ZERO_CODE - encoded_size
        packed = struct.pack('>Q', adjusted_value)[-encoded_size:]
  
      return encode_marker(code, reverse) + packed
  
    @classmethod
    def decode(cls, marker, blob, pos, reverse=False):
      code = ord(marker) ^ 0xFF if reverse else ord(marker)
      if code == INT64_ZERO_CODE:
        return 0, pos
  
      encoded_size = abs(code - INT64_ZERO_CODE)
      packed = b'\x00' * (8 - encoded_size) + blob[pos:pos + encoded_size]
      pos += encoded_size
      value = struct.unpack('>Q', packed)[0]
      if code > INT64_ZERO_CODE:
        value = cls.LIMITS[encoded_size] - value if reverse else value
      else:
        # Shift values back to their original, negative state.
        value = -value if reverse else value - cls.LIMITS[encoded_size]
  
      return value, pos
  
    @classmethod
    def encode_bare(cls, value, byte_count):
      """
      Encodes an integer without a prefix using the specified number of bytes.
      """
      encoded = struct.pack('>Q', value)
      if any(byte != b'\x00' for byte in encoded[:-byte_count]):
        raise InternalError(u'Value exceeds maximum size')
  
      return encoded[-byte_count:]
  
    @classmethod
    def decode_bare(cls, encoded_value):
      """ Decodes a byte string back to an integer. """
      encoded_value = b'\x00' * (8 - len(encoded_value)) + encoded_value
      return struct.unpack('>Q', encoded_value)[0]
  
  
  class Bytes(object):
    """
    Handles encoding and decoding operations for arbitrary blobs. Since the
    length of the value is variable and there is usually data that follows the
    encoded value, a terminator byte is used to indicate the end of the value.
    Any occurrence of the terminator byte within the value is escaped in order to
    preserve the ordering and allow the parser to find the real terminator.
    """
    @classmethod
    def encode(cls, value, prefix=six.int2byte(BYTES_CODE), reverse=False):
      packed = reverse_bits(value) if reverse else value
      terminator = encode_marker(TERMINATOR, reverse)
      # Replace each occurrence of the terminator with a sequence that maintains
      # the sort order. In order for the parser to be able to find the end of the
      # value, directories that use this codec must ensure that the first byte
      # that follows the encoded Bytes object must not be 0x00 or 0xFF.
      if reverse:
        # The preceding 0xFE ensures a terminator character within the value
        # compares as less than the real terminator. For example,
        # 0x0200 -> 0xFDFF -> 0xFDFEFF00FF should come before
        # 0x02  
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/codecs.py
files: """
  This module stores and retrieves entity data as well as the metadata needed to
  achieve snapshot isolation during transactions. The DataManager is the main
  interface that clients can use to interact with the data layer. See its
  documentation for implementation details.
  """
  from __future__ import division
  import logging
  import math
  import sys
  
  import six
  import six.moves as sm
  from tornado import gen
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.fdb.codecs import (
    decode_str, encode_versionstamp_index, Int64, Path, Text)
  from appscale.datastore.fdb.utils import (
    ABSENT_VERSION, DS_ROOT, fdb, hash_tuple, ResultIterator, VERSIONSTAMP_SIZE)
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import entity_pb
  
  logger = logging.getLogger(__name__)
  
  first_gt_or_equal = fdb.KeySelector.first_greater_or_equal
  
  
  class VersionEntry(object):
    """ Encapsulates details for an entity version. """
    INCOMPLETE = 1
    __slots__ = ['project_id', 'namespace', 'path', 'commit_versionstamp',
                 'version', '_encoded_entity', '_decoded_entity']
  
    def __init__(self, project_id, namespace, path, commit_versionstamp=None,
                 version=None, encoded_entity=None):
      self.project_id = project_id
      self.namespace = namespace
      self.path = path
      self.commit_versionstamp = commit_versionstamp
      self.version = ABSENT_VERSION if version is None else version
      self._encoded_entity = encoded_entity
      self._decoded_entity = None
  
    def __repr__(self):
      # Since the encoded entity can be large, it probably does not make sense to
      # include it in the string representation.
      blob_repr = self._encoded_entity
      if blob_repr is not None:
        blob_repr = u'<bytes object with length={}>'.format(len(blob_repr))
  
      return u'VersionEntry({!r}, {!r}, {!r}, {!r}, {!r}, {})'.format(
        self.project_id, self.namespace, self.path, self.commit_versionstamp,
        self.version, blob_repr)
  
    @property
    def present(self):
      return self.commit_versionstamp is not None
  
    @property
    def complete(self):
      return self._encoded_entity != self.INCOMPLETE
  
    @property
    def has_entity(self):
      return bool(self._encoded_entity)
  
    @property
    def key(self):
      key = entity_pb.Reference()
      key.set_app(self.project_id)
      if self.namespace is not None:
        key.set_name_space(self.namespace)
  
      key.mutable_path().MergeFrom(Path.decode(self.path))
      return key
  
    @property
    def encoded(self):
      if not self.complete:
        raise ValueError(u'Version entry is not complete')
  
      return self._encoded_entity
  
    @property
    def decoded(self):
      if not self.has_entity:
        return None
  
      if self._decoded_entity is None:
        self._decoded_entity = entity_pb.EntityProto(self.encoded)
  
      return self._decoded_entity
  
    @classmethod
    def from_key(cls, key):
      project_id = decode_str(key.app())
      namespace = None
      if key.has_name_space():
        namespace = decode_str(key.name_space())
  
      path = Path.flatten(key.path())
      return cls(project_id, namespace, path)
  
  
  class DataNamespace(object):
    """
    A DataNamespace handles the encoding and decoding details for entity data
    for a specific project_id/namespace combination.
  
    The directory path looks like (<project-dir>, 'data', <namespace>).
  
    Within this directory, keys are encoded as
    <scatter-byte> + <path> + <commit-versionstamp> + <index>.
  
    The <scatter-byte> is a single byte determined by hashing the entity path.
    Its purpose is to spread writes more evenly across the cluster and minimize
    hotspots.
  
    The <path> contains the entity path. See codecs.Path for encoding details.
  
    The <commit-versionstamp> is a 10-byte versionstamp that specifies the commit version
    of the transaction that wrote the entity data.
  
    The <index> is a single byte specifying the position of the value's chunk.
  
    Values are encoded as <entity-encoding> + <entity> + <entity-version>.
  
    The <entity-encoding> is a single byte specifying the encoding scheme of the
    entity to follow.
  
    The <entity> is an encoded protobuffer value.
  
    The <entity-version> is an integer specifying the approximate insert
    timestamp in microseconds (according to the client performing the insert).
    Though there is a one-to-one mapping of commit versionstamps to entity
    versions, the datastore uses a different value for the entity version in
    order to satisfy the 8-byte constraint and to follow the GAE convention of
    the value representing a timestamp. It is encoded using 7 bytes.
  
    Since encoded values can exceed the size limit imposed by FoundationDB,
    values encoded values are split into chunks. Each chunk is stored as a
    Key-Value and ordered by a unique <index> byte.
    """
    DIR_NAME = u'data'
  
    # The max number of bytes for each FDB value.
    _CHUNK_SIZE = 10000
  
    # The number of bytes used to store an entity version.
    _VERSION_SIZE = 7
  
    # The number of bytes used to encode the chunk index.
    _INDEX_SIZE = 1
  
    # Indicates the encoded blob is a V3 entity object.
    _V3_MARKER = 0x01
  
    def __init__(self, directory):
      self.directory = directory
  
    @property
    def project_id(self):
      return self.directory.get_path()[len(DS_ROOT)]
  
    @property
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/data.py
files: """
  This module stores and retrieves entity data as well as the metadata needed to
  achieve snapshot isolation during transactions. The DataManager is the main
  interface that clients can use to interact with the data layer. See its
  documentation for implementation details.
  """
  from __future__ import division
  import logging
  import math
  import sys
  
  import six
  import six.moves as sm
  from tornado import gen
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.fdb.codecs import (
    decode_str, encode_versionstamp_index, Int64, Path, Text)
  from appscale.datastore.fdb.utils import (
    ABSENT_VERSION, DS_ROOT, fdb, hash_tuple, ResultIterator, VERSIONSTAMP_SIZE)
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import entity_pb
  
  logger = logging.getLogger(__name__)
  
  first_gt_or_equal = fdb.KeySelector.first_greater_or_equal
  
  
  class VersionEntry(object):
    """ Encapsulates details for an entity version. """
    INCOMPLETE = 1
    __slots__ = ['project_id', 'namespace', 'path', 'commit_versionstamp',
                 'version', '_encoded_entity', '_decoded_entity']
  
    def __init__(self, project_id, namespace, path, commit_versionstamp=None,
                 version=None, encoded_entity=None):
      self.project_id = project_id
      self.namespace = namespace
      self.path = path
      self.commit_versionstamp = commit_versionstamp
      self.version = ABSENT_VERSION if version is None else version
      self._encoded_entity = encoded_entity
      self._decoded_entity = None
  
    def __repr__(self):
      # Since the encoded entity can be large, it probably does not make sense to
      # include it in the string representation.
      blob_repr = self._encoded_entity
      if blob_repr is not None:
        blob_repr = u'<bytes object with length={}>'.format(len(blob_repr))
  
      return u'VersionEntry({!r}, {!r}, {!r}, {!r}, {!r}, {})'.format(
        self.project_id, self.namespace, self.path, self.commit_versionstamp,
        self.version, blob_repr)
  
    @property
    def present(self):
      return self.commit_versionstamp is not None
  
    @property
    def complete(self):
      return self._encoded_entity != self.INCOMPLETE
  
    @property
    def has_entity(self):
      return bool(self._encoded_entity)
  
    @property
    def key(self):
      key = entity_pb.Reference()
      key.set_app(self.project_id)
      if self.namespace is not None:
        key.set_name_space(self.namespace)
  
      key.mutable_path().MergeFrom(Path.decode(self.path))
      return key
  
    @property
    def encoded(self):
      if not self.complete:
        raise ValueError(u'Version entry is not complete')
  
      return self._encoded_entity
  
    @property
    def decoded(self):
      if not self.has_entity:
        return None
  
      if self._decoded_entity is None:
        self._decoded_entity = entity_pb.EntityProto(self.encoded)
  
      return self._decoded_entity
  
    @classmethod
    def from_key(cls, key):
      project_id = decode_str(key.app())
      namespace = None
      if key.has_name_space():
        namespace = decode_str(key.name_space())
  
      path = Path.flatten(key.path())
      return cls(project_id, namespace, path)
  
  
  class DataNamespace(object):
    """
    A DataNamespace handles the encoding and decoding details for entity data
    for a specific project_id/namespace combination.
  
    The directory path looks like (<project-dir>, 'data', <namespace>).
  
    Within this directory, keys are encoded as
    <scatter-byte> + <path> + <commit-versionstamp> + <index>.
  
    The <scatter-byte> is a single byte determined by hashing the entity path.
    Its purpose is to spread writes more evenly across the cluster and minimize
    hotspots.
  
    The <path> contains the entity path. See codecs.Path for encoding details.
  
    The <commit-versionstamp> is a 10-byte versionstamp that specifies the commit version
    of the transaction that wrote the entity data.
  
    The <index> is a single byte specifying the position of the value's chunk.
  
    Values are encoded as <entity-encoding> + <entity> + <entity-version>.
  
    The <entity-encoding> is a single byte specifying the encoding scheme of the
    entity to follow.
  
    The <entity> is an encoded protobuffer value.
  
    The <entity-version> is an integer specifying the approximate insert
    timestamp in microseconds (according to the client performing the insert).
    Though there is a one-to-one mapping of commit versionstamps to entity
    versions, the datastore uses a different value for the entity version in
    order to satisfy the 8-byte constraint and to follow the GAE convention of
    the value representing a timestamp. It is encoded using 7 bytes.
  
    Since encoded values can exceed the size limit imposed by FoundationDB,
    values encoded values are split into chunks. Each chunk is stored as a
    Key-Value and ordered by a unique <index> byte.
    """
    DIR_NAME = u'data'
  
    # The max number of bytes for each FDB value.
    _CHUNK_SIZE = 10000
  
    # The number of bytes used to store an entity version.
    _VERSION_SIZE = 7
  
    # The number of bytes used to encode the chunk index.
    _INDEX_SIZE = 1
  
    # Indicates the encoded blob is a V3 entity object.
    _V3_MARKER = 0x01
  
    def __init__(self, directory):
      self.directory = directory
  
    @property
    def project_id(self):
      return self.directory.get_path()[len(DS_ROOT)]
  
    @property
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/data.py
files: """
  This module stores and queries entity indexes. The IndexManager is the main
  interface that clients can use to interact with the index layer. See its
  documentation for implementation details.
  """
  from __future__ import division
  
  import itertools
  import logging
  import monotonic
  import sys
  
  import six
  from tornado import gen
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.fdb import codecs
  from appscale.datastore.fdb.codecs import (
    decode_str, decode_value, encode_value, encode_versionstamp_index, Path)
  from appscale.datastore.fdb.sdk import FindIndexToUse, ListCursor
  from appscale.datastore.fdb.utils import (
    format_prop_val, DS_ROOT, fdb, get_scatter_val, MAX_FDB_TX_DURATION,
    ResultIterator, SCATTER_PROP, VERSIONSTAMP_SIZE)
  from appscale.datastore.dbconstants import BadRequest, InternalError
  from appscale.datastore.index_manager import IndexInaccessible
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import datastore_pb, entity_pb
  from google.appengine.datastore.datastore_pb import Query_Filter, Query_Order
  
  logger = logging.getLogger(__name__)
  
  KEY_PROP = u'__key__'
  
  first_gt_or_equal = fdb.KeySelector.first_greater_or_equal
  
  
  class FilterProperty(object):
    """ Encapsulates details for a FilterProperty that came from a query. """
    __slots__ = ['name', 'filters']
  
    def __init__(self, prop_name, filters):
      self.name = prop_name
      self.filters = filters
  
    @property
    def equality(self):
      return all(op == Query_Filter.EQUAL for op, _ in self.filters)
  
    def __repr__(self):
      return u'FilterProperty(%r, %r)' % (self.name, self.filters)
  
  
  def group_filters(query):
    filter_props = []
    for query_filter in query.filter_list():
      if query_filter.property_size() != 1:
        raise BadRequest(u'Each filter must have exactly one property')
  
      prop = query_filter.property(0)
      prop_name = decode_str(prop.name())
      filter_info = (query_filter.op(), prop.value())
      if filter_props and filter_props[-1].name == prop_name:
        filter_props[-1].filters.append(filter_info)
      else:
        filter_props.append(FilterProperty(prop_name, [filter_info]))
  
    # Since the filter list can come in any order, put inequality filters last.
    inequality_index = None
    for index, filter_prop in enumerate(filter_props):
      if not filter_prop.equality:
        inequality_index = index
        break
  
    if inequality_index is not None:
      inequality_prop = filter_props.pop(inequality_index)
      filter_props.append(inequality_prop)
  
    # Put key filters last.
    key_index = None
    for index, filter_prop in enumerate(filter_props):
      if filter_prop.name == KEY_PROP:
        key_index = index
        break
  
    if key_index is not None:
      key_prop = filter_props.pop(key_index)
      filter_props.append(key_prop)
  
    for filter_prop in filter_props[:-1]:
      if filter_prop.name == KEY_PROP:
        raise BadRequest(
          u'Only the last filter property can be on {}'.format(KEY_PROP))
  
      if not filter_prop.equality:
        raise BadRequest(u'All but the last property must be equality filters')
  
    return tuple(filter_props)
  
  
  def get_order_info(query):
    filter_props = group_filters(query)
  
    # Orders on equality filters can be ignored.
    equality_props = [prop.name for prop in filter_props if prop.equality]
    relevant_orders = [order for order in query.order_list()
                       if order.property() not in equality_props]
  
    order_info = []
    for filter_prop in filter_props:
      if filter_prop.equality:
        continue
  
      direction = next(
        (order.direction() for order in relevant_orders
         if order.property() == filter_prop.name), Query_Order.ASCENDING)
      order_info.append((filter_prop.name, direction))
  
    filter_prop_names = [prop.name for prop in filter_props]
    order_info.extend(
      [(decode_str(order.property()), order.direction())
       for order in relevant_orders
       if order.property() not in filter_prop_names])
  
    return tuple(order_info)
  
  
  def get_scan_direction(query, index):
    order_info = get_order_info(query)
    if not order_info:
      return Query_Order.ASCENDING
  
    first_property, first_direction = order_info[0]
    if first_property == KEY_PROP or isinstance(index, SinglePropIndex):
      return first_direction
  
    index_direction = next(direction for prop_name, direction in index.order_info
                           if prop_name == first_property)
    if index_direction == first_direction:
      return Query_Order.ASCENDING
    else:
      return Query_Order.DESCENDING
  
  
  class IndexEntry(object):
    """ Encapsulates details for an index entry. """
    __slots__ = ['project_id', 'namespace', 'path', 'commit_versionstamp',
                 'deleted_versionstamp']
  
    def __init__(self, project_id, namespace, path, commit_versionstamp,
                 deleted_versionstamp):
      self.project_id = project_id
      self.namespace = namespace
      self.path = path
      self.commit_versionstamp = commit_versionstamp
      self.deleted_versionstamp = deleted_versionstamp
  
    @property
    def kind(self):
      return self.path[-2]
  
    @property
    def key(self):
      key = entity_pb.Reference()
      key.set_app(self.project_id)
      key.set_name_space(self.namespace)
      key.mutable_path().MergeFrom(Path.decode(self.path))
      return key
  
    @property
    def group(self):
     
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/indexes.py
files: """
  This module stores and queries entity indexes. The IndexManager is the main
  interface that clients can use to interact with the index layer. See its
  documentation for implementation details.
  """
  from __future__ import division
  
  import itertools
  import logging
  import monotonic
  import sys
  
  import six
  from tornado import gen
  
  from appscale.common.unpackaged import APPSCALE_PYTHON_APPSERVER
  from appscale.datastore.fdb.codecs import (
    decode_str, decode_value, encode_value, encode_versionstamp_index, Path)
  from appscale.datastore.fdb.sdk import FindIndexToUse, ListCursor
  from appscale.datastore.fdb.utils import (
    format_prop_val, DS_ROOT, fdb, get_scatter_val, MAX_FDB_TX_DURATION,
    ResultIterator, SCATTER_PROP, VERSIONSTAMP_SIZE)
  from appscale.datastore.dbconstants import BadRequest, InternalError
  from appscale.datastore.index_manager import IndexInaccessible
  
  sys.path.append(APPSCALE_PYTHON_APPSERVER)
  from google.appengine.datastore import datastore_pb, entity_pb
  from google.appengine.datastore.datastore_pb import Query_Filter, Query_Order
  
  logger = logging.getLogger(__name__)
  
  KEY_PROP = u'__key__'
  
  first_gt_or_equal = fdb.KeySelector.first_greater_or_equal
  
  
  class FilterProperty(object):
    """ Encapsulates details for a FilterProperty that came from a query. """
    __slots__ = ['name', 'filters']
  
    def __init__(self, prop_name, filters):
      self.name = prop_name
      self.filters = filters
  
    @property
    def equality(self):
      return all(op == Query_Filter.EQUAL for op, _ in self.filters)
  
    def __repr__(self):
      return u'FilterProperty(%r, %r)' % (self.name, self.filters)
  
  
  def group_filters(query):
    filter_props = []
    for query_filter in query.filter_list():
      if query_filter.property_size() != 1:
        raise BadRequest(u'Each filter must have exactly one property')
  
      prop = query_filter.property(0)
      prop_name = decode_str(prop.name())
      filter_info = (query_filter.op(), prop.value())
      if filter_props and filter_props[-1].name == prop_name:
        filter_props[-1].filters.append(filter_info)
      else:
        filter_props.append(FilterProperty(prop_name, [filter_info]))
  
    # Since the filter list can come in any order, put inequality filters last.
    inequality_index = None
    for index, filter_prop in enumerate(filter_props):
      if not filter_prop.equality:
        inequality_index = index
        break
  
    if inequality_index is not None:
      inequality_prop = filter_props.pop(inequality_index)
      filter_props.append(inequality_prop)
  
    # Put key filters last.
    key_index = None
    for index, filter_prop in enumerate(filter_props):
      if filter_prop.name == KEY_PROP:
        key_index = index
        break
  
    if key_index is not None:
      key_prop = filter_props.pop(key_index)
      filter_props.append(key_prop)
  
    for filter_prop in filter_props[:-1]:
      if filter_prop.name == KEY_PROP:
        raise BadRequest(
          u'Only the last filter property can be on {}'.format(KEY_PROP))
  
      if not filter_prop.equality:
        raise BadRequest(u'All but the last property must be equality filters')
  
    return tuple(filter_props)
  
  
  def get_order_info(query):
    filter_props = group_filters(query)
  
    # Orders on equality filters can be ignored.
    equality_props = [prop.name for prop in filter_props if prop.equality]
    relevant_orders = [order for order in query.order_list()
                       if order.property() not in equality_props]
  
    order_info = []
    for filter_prop in filter_props:
      if filter_prop.equality:
        continue
  
      direction = next(
        (order.direction() for order in relevant_orders
         if order.property() == filter_prop.name), Query_Order.ASCENDING)
      order_info.append((filter_prop.name, direction))
  
    filter_prop_names = [prop.name for prop in filter_props]
    order_info.extend(
      [(decode_str(order.property()), order.direction())
       for order in relevant_orders
       if order.property() not in filter_prop_names])
  
    return tuple(order_info)
  
  
  def get_scan_direction(query, index):
    order_info = get_order_info(query)
    if not order_info:
      return Query_Order.ASCENDING
  
    first_property, first_direction = order_info[0]
    if first_property == KEY_PROP or isinstance(index, SinglePropIndex):
      return first_direction
  
    index_direction = next(direction for prop_name, direction in index.order_info
                           if prop_name == first_property)
    if index_direction == first_direction:
      return Query_Order.ASCENDING
    else:
      return Query_Order.DESCENDING
  
  
  class IndexEntry(object):
    """ Encapsulates details for an index entry. """
    __slots__ = ['project_id', 'namespace', 'path', 'commit_versionstamp',
                 'deleted_versionstamp']
  
    def __init__(self, project_id, namespace, path, commit_versionstamp,
                 deleted_versionstamp):
      self.project_id = project_id
      self.namespace = namespace
      self.path = path
      self.commit_versionstamp = commit_versionstamp
      self.deleted_versionstamp = deleted_versionstamp
  
    @property
    def kind(self):
      return self.path[-2]
  
    @property
    def key(self):
      key = entity_pb.Reference()
      key.set_app(self.project_id)
      key.set_name_space(self.namespace)
      key.mutable_path().MergeFrom(Path.decode(self.path))
      return key
  
    @property
    def group(self):
      group = entity_pb.Path()
      group.add_element().
  
  [... the rest is omitted ...]
files: AppDB/appscale/datastore/fdb/indexes.py