#!/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. # """Represents a lexographic range of namespaces.""" __all__ = [ 'NAMESPACE_CHARACTERS', 'MAX_NAMESPACE_LENGTH', 'MAX_NAMESPACE', 'MIN_NAMESPACE', 'NAMESPACE_BATCH_SIZE', 'NamespaceRange', 'get_namespace_keys', ] import itertools import string from google.appengine.api import datastore from google.appengine.ext import db from google.appengine.ext.db import metadata NAMESPACE_CHARACTERS = ''.join(sorted(string.digits + string.lowercase + string.uppercase + '._-')) MAX_NAMESPACE_LENGTH = 100 MIN_NAMESPACE = '' NAMESPACE_BATCH_SIZE = 50 def _setup_constants(alphabet=NAMESPACE_CHARACTERS, max_length=MAX_NAMESPACE_LENGTH, batch_size=NAMESPACE_BATCH_SIZE): """Calculate derived constant values. Only useful for testing.""" global NAMESPACE_CHARACTERS global MAX_NAMESPACE_LENGTH global MAX_NAMESPACE global _LEX_DISTANCE global NAMESPACE_BATCH_SIZE NAMESPACE_CHARACTERS = alphabet MAX_NAMESPACE_LENGTH = max_length MAX_NAMESPACE = NAMESPACE_CHARACTERS[-1] * MAX_NAMESPACE_LENGTH NAMESPACE_BATCH_SIZE = batch_size _LEX_DISTANCE = [1] for i in range(1, MAX_NAMESPACE_LENGTH): _LEX_DISTANCE.append( _LEX_DISTANCE[i-1] * len(NAMESPACE_CHARACTERS) + 1) del i _setup_constants() def _ord_to_namespace(n, _max_length=None): """Convert a namespace ordinal to a namespace string. Converts an int, representing the sequence number of a namespace ordered lexographically, into a namespace string. >>> _ord_to_namespace(0) '' >>> _ord_to_namespace(1) '-' >>> _ord_to_namespace(2) '--' >>> _ord_to_namespace(3) '---' Args: n: A number representing the lexographical ordering of a namespace. _max_length: The maximum namespace length. Returns: A string representing the nth namespace in lexographical order. """ if _max_length is None: _max_length = MAX_NAMESPACE_LENGTH length = _LEX_DISTANCE[_max_length - 1] if n == 0: return '' n -= 1 return (NAMESPACE_CHARACTERS[n / length] + _ord_to_namespace(n % length, _max_length - 1)) def _namespace_to_ord(namespace): """Converts a namespace string into an int representing its lexographic order. >>> _namespace_to_ord('') '' >>> _namespace_to_ord('_') 1 >>> _namespace_to_ord('__') 2 Args: namespace: A namespace string. Returns: An int representing the lexographical order of the given namespace string. """ n = 0 for i, c in enumerate(namespace): n += (_LEX_DISTANCE[MAX_NAMESPACE_LENGTH - i- 1] * NAMESPACE_CHARACTERS.index(c) + 1) return n def _key_for_namespace(namespace, app): """Return the __namespace__ key for a namespace. Args: namespace: The namespace whose key is requested. app: The id of the application that the key belongs to. Returns: A db.Key representing the namespace. """ if namespace: return db.Key.from_path(metadata.Namespace.KIND_NAME, namespace, _app=app) else: return db.Key.from_path(metadata.Namespace.KIND_NAME, metadata.Namespace.EMPTY_NAMESPACE_ID, _app=app) class NamespaceRange(object): """An inclusive lexographical range of namespaces. This class is immutable. """ def __init__(self, namespace_start=None, namespace_end=None, _app=None): """Initializes a NamespaceRange instance. Args: namespace_start: A string representing the start of the namespace range. namespace_start is included in the range. If namespace_start is None then the lexographically first namespace is used. namespace_end: A string representing the end of the namespace range. namespace_end is included in the range and must be >= namespace_start. If namespace_end is None then the lexographically last namespace is used. Raises: ValueError: if namespace_start > namespace_end. """ if namespace_start is None: namespace_start = MIN_NAMESPACE if namespace_end is None: namespace_end = MAX_NAMESPACE if namespace_start > namespace_end: raise ValueError('namespace_start (%r) > namespace_end (%r)' % ( namespace_start, namespace_end)) self.__namespace_start = namespace_start self.__namespace_end = namespace_end self.__app = _app @property def app(self): return self.__app @property def namespace_start(self): return self.__namespace_start @property def namespace_end(self): return self.__namespace_end @property def is_single_namespace(self): """True if the namespace range only includes a single namespace.""" return self.namespace_start == self.namespace_end def split_range(self): """Splits the NamespaceRange into two nearly equal-sized ranges. Returns: If this NamespaceRange contains a single namespace then a list containing this NamespaceRange is returned. Otherwise a two-element list containing two NamespaceRanges whose total range is identical to this NamespaceRange's is returned. """ if self.is_single_namespace: return [self] mid_point = (_namespace_to_ord(self.namespace_start) + _namespace_to_ord(self.namespace_end)) // 2 return [NamespaceRange(self.namespace_start, _ord_to_namespace(mid_point), _app=self.app), NamespaceRange(_ord_to_namespace(mid_point+1), self.namespace_end, _app=self.app)] def __copy__(self): return self.__class__(self.__namespace_start, self.__namespace_end, self.__app) def __eq__(self, o): return (self.namespace_start == o.namespace_start and self.namespace_end == o.namespace_end) def __hash__(self): return hash((self.namespace_start, self.namespace_end, self.app)) def __repr__(self): if self.app is None: return 'NamespaceRange(namespace_start=%r, namespace_end=%r)' % ( self.namespace_start, self.namespace_end) else: return 'NamespaceRange(namespace_start=%r, namespace_end=%r, _app=%r)' % ( self.namespace_start, self.namespace_end, self.app) def with_start_after(self, after_namespace): """Returns a copy of this NamespaceName with a new namespace_start. Args: after_namespace: A namespace string. Returns: A NamespaceRange object whose namespace_start is the lexographically next namespace after the given namespace string. Raises: ValueError: if the NamespaceRange includes only a single namespace. """ namespace_start = _ord_to_namespace(_namespace_to_ord(after_namespace) + 1) return NamespaceRange(namespace_start, self.namespace_end, _app=self.app) def make_datastore_query(self, cursor=None): """Returns a datastore.Query that generates all namespaces in the range. Args: cursor: start cursor for the query. Returns: A datastore.Query instance that generates db.Keys for each namespace in the NamespaceRange. """ filters = {} filters['__key__ >= '] = _key_for_namespace( self.namespace_start, self.app) filters['__key__ <= '] = _key_for_namespace( self.namespace_end, self.app) return datastore.Query('__namespace__', filters=filters, keys_only=True, cursor=cursor, _app=self.app) def normalized_start(self): """Returns a NamespaceRange with leading non-existant namespaces removed. Returns: A copy of this NamespaceRange whose namespace_start is adjusted to exclude the portion of the range that contains no actual namespaces in the datastore. None is returned if the NamespaceRange contains no actual namespaces in the datastore. """ namespaces_after_key = list(self.make_datastore_query().Run(limit=1)) if not namespaces_after_key: return None namespace_after_key = namespaces_after_key[0].name() or '' return NamespaceRange(namespace_after_key, self.namespace_end, _app=self.app) def to_json_object(self): """Returns a dict representation that can be serialized to JSON.""" obj_dict = dict(namespace_start=self.namespace_start, namespace_end=self.namespace_end) if self.app is not None: obj_dict['app'] = self.app return obj_dict @classmethod def from_json_object(cls, json): """Returns a NamespaceRange from an object deserialized from JSON.""" return cls(json['namespace_start'], json['namespace_end'], _app=json.get('app')) @classmethod def split(cls, n, contiguous, can_query=itertools.chain(itertools.repeat(True, 50), itertools.repeat(False)).next, _app=None): """Splits the complete NamespaceRange into n equally-sized NamespaceRanges. Args: n: The maximum number of NamespaceRanges to return. Fewer than n namespaces may be returned. contiguous: If True then the returned NamespaceRanges will cover the entire space of possible namespaces (i.e. from MIN_NAMESPACE to MAX_NAMESPACE) without gaps. If False then the returned NamespaceRanges may exclude namespaces that don't appear in the datastore. can_query: A function that returns True if split() can query the datastore to generate more fair namespace range splits, and False otherwise. If not set then split() is allowed to make 50 datastore queries. Returns: A list of at most n NamespaceRanges representing a near-equal distribution of actual existant datastore namespaces. The returned list will be sorted lexographically. Raises: ValueError: if n is < 1. """ if n < 1: raise ValueError('n must be >= 1') ranges = None if can_query(): if not contiguous: ns_keys = get_namespace_keys(_app, n + 1) if not ns_keys: return [] else: if len(ns_keys) <= n: ns_range = [] for ns_key in ns_keys: ns_range.append(NamespaceRange(ns_key.name() or '', ns_key.name() or '', _app=_app)) return sorted(ns_range, key=lambda ns_range: ns_range.namespace_start) ranges = [NamespaceRange(ns_keys[0].name() or '', _app=_app)] else: ns_range = NamespaceRange(_app=_app).normalized_start() if ns_range is None: return [NamespaceRange(_app=_app)] ranges = [ns_range] else: ranges = [NamespaceRange(_app=_app)] singles = [] while ranges and (len(ranges) + len(singles)) < n: namespace_range = ranges.pop(0) if namespace_range.is_single_namespace: singles.append(namespace_range) else: left, right = namespace_range.split_range() if can_query(): right = right.normalized_start() if right is not None: ranges.append(right) ranges.append(left) ns_ranges = sorted(singles + ranges, key=lambda ns_range: ns_range.namespace_start) if contiguous: if not ns_ranges: return [NamespaceRange(_app=_app)] continuous_ns_ranges = [] for i in range(len(ns_ranges)): if i == 0: namespace_start = MIN_NAMESPACE else: namespace_start = ns_ranges[i].namespace_start if i == len(ns_ranges) - 1: namespace_end = MAX_NAMESPACE else: namespace_end = _ord_to_namespace( _namespace_to_ord(ns_ranges[i+1].namespace_start) - 1) continuous_ns_ranges.append(NamespaceRange(namespace_start, namespace_end, _app=_app)) return continuous_ns_ranges else: return ns_ranges def __iter__(self): """Iterate over all the namespaces within this range.""" cursor = None while True: query = self.make_datastore_query(cursor=cursor) count = 0 for ns_key in query.Run(limit=NAMESPACE_BATCH_SIZE): count += 1 yield ns_key.name() or '' if count < NAMESPACE_BATCH_SIZE: break cursor = query.GetCursor() def get_namespace_keys(app, limit): """Get namespace keys.""" ns_query = datastore.Query('__namespace__', keys_only=True, _app=app) return list(ns_query.Run(limit=limit, batch_size=limit))