blob: 5af2417fe47ac85752784254a4045381d1bd9978 [file] [log] [blame]
#!/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))