diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/spack/llnl/util/lang.py | 254 | ||||
-rw-r--r-- | lib/spack/spack/architecture.py | 78 | ||||
-rw-r--r-- | lib/spack/spack/spec.py | 138 | ||||
-rw-r--r-- | lib/spack/spack/test/spec_syntax.py | 8 | ||||
-rw-r--r-- | lib/spack/spack/variant.py | 17 |
5 files changed, 340 insertions, 155 deletions
diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py index 17c1fe8427..4097e4bf6f 100644 --- a/lib/spack/llnl/util/lang.py +++ b/lib/spack/llnl/util/lang.py @@ -14,6 +14,11 @@ from datetime import datetime, timedelta from six import string_types import sys +if sys.version_info < (3, 0): + from itertools import izip_longest # novm + zip_longest = izip_longest +else: + from itertools import zip_longest # novm if sys.version_info >= (3, 3): from collections.abc import Hashable, MutableMapping # novm @@ -227,48 +232,222 @@ def list_modules(directory, **kwargs): yield re.sub('.py$', '', name) -def key_ordering(cls): - """Decorates a class with extra methods that implement rich comparison - operations and ``__hash__``. The decorator assumes that the class - implements a function called ``_cmp_key()``. The rich comparison - operations will compare objects using this key, and the ``__hash__`` - function will return the hash of this key. +def decorator_with_or_without_args(decorator): + """Allows a decorator to be used with or without arguments, e.g.:: + + # Calls the decorator function some args + @decorator(with, arguments, and=kwargs) + + or:: + + # Calls the decorator function with zero arguments + @decorator + + """ + # See https://stackoverflow.com/questions/653368 for more on this + @functools.wraps(decorator) + def new_dec(*args, **kwargs): + if len(args) == 1 and len(kwargs) == 0 and callable(args[0]): + # actual decorated function + return decorator(args[0]) + else: + # decorator arguments + return lambda realf: decorator(realf, *args, **kwargs) + + return new_dec + + +#: sentinel for testing that iterators are done in lazy_lexicographic_ordering +done = object() + + +def tuplify(seq): + """Helper for lazy_lexicographic_ordering().""" + return tuple((tuplify(x) if callable(x) else x) for x in seq()) + + +def lazy_eq(lseq, rseq): + """Equality comparison for two lazily generated sequences. + + See ``lazy_lexicographic_ordering``. + """ + liter = lseq() # call generators + riter = rseq() + + # zip_longest is implemented in native code, so use it for speed. + # use zip_longest instead of zip because it allows us to tell + # which iterator was longer. + for left, right in zip_longest(liter, riter, fillvalue=done): + if (left is done) or (right is done): + return False + + # recursively enumerate any generators, otherwise compare + equal = lazy_eq(left, right) if callable(left) else left == right + if not equal: + return False + + return True - If a class already has ``__eq__``, ``__ne__``, ``__lt__``, ``__le__``, - ``__gt__``, or ``__ge__`` defined, this decorator will overwrite them. - Raises: - TypeError: If the class does not have a ``_cmp_key`` method +def lazy_lt(lseq, rseq): + """Less-than comparison for two lazily generated sequences. + + See ``lazy_lexicographic_ordering``. """ - def setter(name, value): - value.__name__ = name - setattr(cls, name, value) - - if not has_method(cls, '_cmp_key'): - raise TypeError("'%s' doesn't define _cmp_key()." % cls.__name__) - - setter('__eq__', - lambda s, o: - (s is o) or (o is not None and s._cmp_key() == o._cmp_key())) - setter('__lt__', - lambda s, o: o is not None and s._cmp_key() < o._cmp_key()) - setter('__le__', - lambda s, o: o is not None and s._cmp_key() <= o._cmp_key()) - - setter('__ne__', - lambda s, o: - (s is not o) and (o is None or s._cmp_key() != o._cmp_key())) - setter('__gt__', - lambda s, o: o is None or s._cmp_key() > o._cmp_key()) - setter('__ge__', - lambda s, o: o is None or s._cmp_key() >= o._cmp_key()) - - setter('__hash__', lambda self: hash(self._cmp_key())) + liter = lseq() + riter = rseq() + + for left, right in zip_longest(liter, riter, fillvalue=done): + if (left is done) or (right is done): + return left is done # left was shorter than right + + sequence = callable(left) + equal = lazy_eq(left, right) if sequence else left == right + if equal: + continue + + if sequence: + return lazy_lt(left, right) + if left is None: + return True + if right is None: + return False + + return left < right + + return False # if equal, return False + + +@decorator_with_or_without_args +def lazy_lexicographic_ordering(cls, set_hash=True): + """Decorates a class with extra methods that implement rich comparison. + + This is a lazy version of the tuple comparison used frequently to + implement comparison in Python. Given some objects with fields, you + might use tuple keys to implement comparison, e.g.:: + + class Widget: + def _cmp_key(self): + return ( + self.a, + self.b, + (self.c, self.d), + self.e + ) + + def __eq__(self, other): + return self._cmp_key() == other._cmp_key() + + def __lt__(self): + return self._cmp_key() < other._cmp_key() + + # etc. + + Python would compare ``Widgets`` lexicographically based on their + tuples. The issue there for simple comparators is that we have to + bulid the tuples *and* we have to generate all the values in them up + front. When implementing comparisons for large data structures, this + can be costly. + + Lazy lexicographic comparison maps the tuple comparison shown above + to generator functions. Instead of comparing based on pre-constructed + tuple keys, users of this decorator can compare using elements from a + generator. So, you'd write:: + + @lazy_lexicographic_ordering + class Widget: + def _cmp_iter(self): + yield a + yield b + def cd_fun(): + yield c + yield d + yield cd_fun + yield e + + # operators are added by decorator + + There are no tuples preconstructed, and the generator does not have + to complete. Instead of tuples, we simply make functions that lazily + yield what would've been in the tuple. The + ``@lazy_lexicographic_ordering`` decorator handles the details of + implementing comparison operators, and the ``Widget`` implementor + only has to worry about writing ``_cmp_iter``, and making sure the + elements in it are also comparable. + + Some things to note: + + * If a class already has ``__eq__``, ``__ne__``, ``__lt__``, + ``__le__``, ``__gt__``, ``__ge__``, or ``__hash__`` defined, this + decorator will overwrite them. + + * If ``set_hash`` is ``False``, this will not overwrite + ``__hash__``. + + * This class uses Python 2 None-comparison semantics. If you yield + None and it is compared to a non-None type, None will always be + less than the other object. + + Raises: + TypeError: If the class does not have a ``_cmp_iter`` method + + """ + if not has_method(cls, "_cmp_iter"): + raise TypeError("'%s' doesn't define _cmp_iter()." % cls.__name__) + + # comparison operators are implemented in terms of lazy_eq and lazy_lt + def eq(self, other): + if self is other: + return True + return (other is not None) and lazy_eq(self._cmp_iter, other._cmp_iter) + + def lt(self, other): + if self is other: + return False + return (other is not None) and lazy_lt(self._cmp_iter, other._cmp_iter) + + def ne(self, other): + if self is other: + return False + return (other is None) or not lazy_eq(self._cmp_iter, other._cmp_iter) + + def gt(self, other): + if self is other: + return False + return (other is None) or lazy_lt(other._cmp_iter, self._cmp_iter) + + def le(self, other): + if self is other: + return True + return (other is not None) and not lazy_lt(other._cmp_iter, + self._cmp_iter) + + def ge(self, other): + if self is other: + return True + return (other is None) or not lazy_lt(self._cmp_iter, other._cmp_iter) + + def h(self): + return hash(tuplify(self._cmp_iter)) + + def add_func_to_class(name, func): + """Add a function to a class with a particular name.""" + func.__name__ = name + setattr(cls, name, func) + + add_func_to_class("__eq__", eq) + add_func_to_class("__ne__", ne) + add_func_to_class("__lt__", lt) + add_func_to_class("__le__", le) + add_func_to_class("__gt__", gt) + add_func_to_class("__ge__", ge) + if set_hash: + add_func_to_class("__hash__", h) return cls -@key_ordering +@lazy_lexicographic_ordering class HashableMap(MutableMapping): """This is a hashable, comparable dictionary. Hash is performed on a tuple of the values in the dictionary.""" @@ -291,8 +470,9 @@ class HashableMap(MutableMapping): def __delitem__(self, key): del self.dict[key] - def _cmp_key(self): - return tuple(sorted(self.values())) + def _cmp_iter(self): + for _, v in sorted(self.items()): + yield v def copy(self): """Type-agnostic clone method. Preserves subclass type.""" diff --git a/lib/spack/spack/architecture.py b/lib/spack/spack/architecture.py index 6341df857d..ba2d824010 100644 --- a/lib/spack/spack/architecture.py +++ b/lib/spack/spack/architecture.py @@ -65,7 +65,7 @@ import archspec.cpu import six import llnl.util.tty as tty -from llnl.util.lang import memoized, list_modules, key_ordering +import llnl.util.lang as lang import spack.compiler import spack.compilers @@ -232,7 +232,7 @@ class Target(object): ) -@key_ordering +@lang.lazy_lexicographic_ordering class Platform(object): """ Abstract class that each type of Platform will subclass. Will return a instance of it once it is returned. @@ -329,23 +329,27 @@ class Platform(object): def __str__(self): return self.name - def _cmp_key(self): - t_keys = ''.join(str(t._cmp_key()) for t in - sorted(self.targets.values())) - o_keys = ''.join(str(o._cmp_key()) for o in - sorted(self.operating_sys.values())) - return (self.name, - self.default, - self.front_end, - self.back_end, - self.default_os, - self.front_os, - self.back_os, - t_keys, - o_keys) - - -@key_ordering + def _cmp_iter(self): + yield self.name + yield self.default + yield self.front_end + yield self.back_end + yield self.default_os + yield self.front_os + yield self.back_os + + def targets(): + for t in sorted(self.targets.values()): + yield t._cmp_iter + yield targets + + def oses(): + for o in sorted(self.operating_sys.values()): + yield o._cmp_iter + yield oses + + +@lang.lazy_lexicographic_ordering class OperatingSystem(object): """ Operating System will be like a class similar to platform extended by subclasses for the specifics. Operating System will contain the @@ -363,8 +367,9 @@ class OperatingSystem(object): def __repr__(self): return self.__str__() - def _cmp_key(self): - return (self.name, self.version) + def _cmp_iter(self): + yield self.name + yield self.version def to_dict(self): return syaml_dict([ @@ -373,7 +378,7 @@ class OperatingSystem(object): ]) -@key_ordering +@lang.lazy_lexicographic_ordering class Arch(object): """Architecture is now a class to help with setting attributes. @@ -423,20 +428,21 @@ class Arch(object): self.target is not None) __bool__ = __nonzero__ - def _cmp_key(self): + def _cmp_iter(self): if isinstance(self.platform, Platform): - platform = self.platform.name + yield self.platform.name else: - platform = self.platform + yield self.platform + if isinstance(self.os, OperatingSystem): - os = self.os.name + yield self.os.name else: - os = self.os + yield self.os + if isinstance(self.target, Target): - target = self.target.microarchitecture + yield self.target.microarchitecture else: - target = self.target - return (platform, os, target) + yield self.target def to_dict(self): str_or_none = lambda v: str(v) if v else None @@ -458,7 +464,7 @@ class Arch(object): return arch_for_spec(spec) -@memoized +@lang.memoized def get_platform(platform_name): """Returns a platform object that corresponds to the given name.""" platform_list = all_platforms() @@ -494,13 +500,13 @@ def arch_for_spec(arch_spec): return Arch(arch_plat, arch_spec.os, arch_spec.target) -@memoized +@lang.memoized def _all_platforms(): classes = [] mod_path = spack.paths.platform_path parent_module = "spack.platforms" - for name in list_modules(mod_path): + for name in lang.list_modules(mod_path): mod_name = '%s.%s' % (parent_module, name) class_name = mod_to_class(name) mod = __import__(mod_name, fromlist=[class_name]) @@ -515,7 +521,7 @@ def _all_platforms(): return classes -@memoized +@lang.memoized def _platform(): """Detects the platform for this machine. @@ -546,7 +552,7 @@ platform = _platform all_platforms = _all_platforms -@memoized +@lang.memoized def default_arch(): """Default ``Arch`` object for this machine. @@ -570,7 +576,7 @@ def sys_type(): return str(default_arch()) -@memoized +@lang.memoized def compatible_sys_types(): """Returns a list of all the systypes compatible with the current host.""" compatible_archs = [] diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py index e43947b60b..370a5d2f0c 100644 --- a/lib/spack/spack/spec.py +++ b/lib/spack/spack/spec.py @@ -203,7 +203,7 @@ def colorize_spec(spec): return clr.colorize(re.sub(_separators, insert_color(), str(spec)) + '@.') -@lang.key_ordering +@lang.lazy_lexicographic_ordering class ArchSpec(object): def __init__(self, spec_or_platform_tuple=(None, None, None)): """ Architecture specification a package should be built with. @@ -252,8 +252,10 @@ class ArchSpec(object): return spec_like return ArchSpec(spec_like) - def _cmp_key(self): - return self.platform, self.os, self.target + def _cmp_iter(self): + yield self.platform + yield self.os + yield self.target def _dup(self, other): self.platform = other.platform @@ -534,7 +536,7 @@ class ArchSpec(object): return string in str(self) or string in self.target -@lang.key_ordering +@lang.lazy_lexicographic_ordering class CompilerSpec(object): """The CompilerSpec field represents the compiler or range of compiler versions that a package should be built with. CompilerSpecs have a @@ -623,8 +625,9 @@ class CompilerSpec(object): clone.versions = self.versions.copy() return clone - def _cmp_key(self): - return (self.name, self.versions) + def _cmp_iter(self): + yield self.name + yield self.versions def to_dict(self): d = syaml.syaml_dict([('name', self.name)]) @@ -648,7 +651,7 @@ class CompilerSpec(object): return str(self) -@lang.key_ordering +@lang.lazy_lexicographic_ordering class DependencySpec(object): """DependencySpecs connect two nodes in the DAG, and contain deptypes. @@ -686,10 +689,10 @@ class DependencySpec(object): self.deptypes + dp.canonical_deptype(type) ) - def _cmp_key(self): - return (self.parent.name if self.parent else None, - self.spec.name if self.spec else None, - self.deptypes) + def _cmp_iter(self): + yield self.parent.name if self.parent else None + yield self.spec.name if self.spec else None + yield self.deptypes def __str__(self): return "%s %s--> %s" % (self.parent.name if self.parent else None, @@ -747,8 +750,15 @@ class FlagMap(lang.HashableMap): clone[name] = value return clone - def _cmp_key(self): - return tuple((k, tuple(v)) for k, v in sorted(six.iteritems(self))) + def _cmp_iter(self): + for k, v in sorted(self.items()): + yield k + + def flags(): + for flag in v: + yield flag + + yield flags def __str__(self): sorted_keys = [k for k in sorted(self.keys()) if self[k] != []] @@ -1016,7 +1026,7 @@ class SpecBuildInterface(lang.ObjectWrapper): ) -@lang.key_ordering +@lang.lazy_lexicographic_ordering(set_hash=False) class Spec(object): #: Cache for spec's prefix, computed lazily in the corresponding property @@ -1060,7 +1070,7 @@ class Spec(object): self._hash = None self._build_hash = None - self._cmp_key_cache = None + self._dunder_hash = None self._package = None # Most of these are internal implementation details that can be @@ -3358,7 +3368,7 @@ class Spec(object): before possibly copying the dependencies of ``other`` onto ``self`` caches (bool or None): preserve cached fields such as - ``_normal``, ``_hash``, and ``_cmp_key_cache``. By + ``_normal``, ``_hash``, and ``_dunder_hash``. By default this is ``False`` if DAG structure would be changed by the copy, ``True`` if it's an exact copy. @@ -3432,13 +3442,13 @@ class Spec(object): if caches: self._hash = other._hash self._build_hash = other._build_hash - self._cmp_key_cache = other._cmp_key_cache + self._dunder_hash = other._dunder_hash self._normal = other._normal self._full_hash = other._full_hash else: self._hash = None self._build_hash = None - self._cmp_key_cache = None + self._dunder_hash = None self._normal = False self._full_hash = None @@ -3562,13 +3572,17 @@ class Spec(object): deps = self.flat_dependencies() return tuple(deps[name] for name in sorted(deps)) - def _eq_dag(self, other, vs, vo, deptypes): - """Recursive helper for eq_dag and ne_dag. Does the actual DAG - traversal.""" + def eq_dag(self, other, deptypes=True, vs=None, vo=None): + """True if the full dependency DAGs of specs are equal.""" + if vs is None: + vs = set() + if vo is None: + vo = set() + vs.add(id(self)) vo.add(id(other)) - if self.ne_node(other): + if not self.eq_node(other): return False if len(self._dependencies) != len(other._dependencies): @@ -3596,58 +3610,38 @@ class Spec(object): continue # Recursive check for equality - if not s._eq_dag(o, vs, vo, deptypes): + if not s.eq_dag(o, deptypes, vs, vo): return False return True - def eq_dag(self, other, deptypes=True): - """True if the full dependency DAGs of specs are equal.""" - return self._eq_dag(other, set(), set(), deptypes) - - def ne_dag(self, other, deptypes=True): - """True if the full dependency DAGs of specs are not equal.""" - return not self.eq_dag(other, set(), set(), deptypes) - def _cmp_node(self): - """Comparison key for just *this node* and not its deps.""" - # Name or namespace None will lead to invalid comparisons for abstract - # specs. Replace them with the empty string, which is not a valid spec - # name nor namespace so it will not create spurious equalities. - return (self.name or '', - self.namespace or '', - tuple(self.versions), - self.variants, - self.architecture, - self.compiler, - self.compiler_flags) + """Yield comparable elements of just *this node* and not its deps.""" + yield self.name or '' + yield self.namespace or '' + yield self.versions + yield self.variants + yield self.compiler + yield self.compiler_flags + yield self.architecture def eq_node(self, other): """Equality with another spec, not including dependencies.""" - return self._cmp_node() == other._cmp_node() - - def ne_node(self, other): - """Inequality with another spec, not including dependencies.""" - return self._cmp_node() != other._cmp_node() - - def _cmp_key(self): - """This returns a key for the spec *including* DAG structure. + return (other is not None) and lang.lazy_eq( + self._cmp_node, other._cmp_node + ) - The key is the concatenation of: - 1. A tuple describing this node in the DAG. - 2. The hash of each of this node's dependencies' cmp_keys. - """ - if self._cmp_key_cache: - return self._cmp_key_cache + def _cmp_iter(self): + """Lazily yield components of self for comparison.""" + for item in self._cmp_node(): + yield item - dep_tuple = tuple( - (d.spec.name, hash(d.spec), tuple(sorted(d.deptypes))) - for name, d in sorted(self._dependencies.items())) - - key = (self._cmp_node(), dep_tuple) - if self._concrete: - self._cmp_key_cache = key - return key + def deps(): + for _, dep in sorted(self._dependencies.items()): + yield dep.spec.name + yield tuple(sorted(dep.deptypes)) + yield hash(dep.spec) + yield deps def colorized(self): return colorize_spec(self) @@ -4339,6 +4333,22 @@ class Spec(object): if hasattr(self, attr): setattr(self, attr, None) + def __hash__(self): + # If the spec is concrete, we leverage the DAG hash and just use + # a 64-bit prefix of it. The DAG hash has the advantage that it's + # computed once per concrete spec, and it's saved -- so if we + # read concrete specs we don't need to recompute the whole hash. + # This is good for large, unchanging specs. + if self.concrete: + if not self._dunder_hash: + self._dunder_hash = self.dag_hash_bit_prefix(64) + return self._dunder_hash + + # This is the normal hash for lazy_lexicographic_ordering. It's + # slow for large specs because it traverses the whole spec graph, + # so we hope it only runs on abstract specs, which are small. + return hash(lang.tuplify(self._cmp_iter)) + class LazySpecCache(collections.defaultdict): """Cache for Specs that uses a spec_like as key, and computes lazily diff --git a/lib/spack/spack/test/spec_syntax.py b/lib/spack/spack/test/spec_syntax.py index a523dffca8..fd5108c809 100644 --- a/lib/spack/spack/test/spec_syntax.py +++ b/lib/spack/spack/test/spec_syntax.py @@ -352,10 +352,10 @@ class TestSpecSyntax(object): def test_ambiguous_hash(self, mutable_database): x1 = Spec('a') x1.concretize() - x1._hash = 'xy' + x1._hash = 'xyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy' x2 = Spec('a') x2.concretize() - x2._hash = 'xx' + x2._hash = 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx' mutable_database.add(x1, spack.store.layout) mutable_database.add(x2, spack.store.layout) @@ -557,10 +557,6 @@ class TestSpecSyntax(object): with specfile.open('w') as f: f.write(s['libelf'].to_yaml(hash=ht.build_hash)) - print("") - print("") - print("PARSING HERE") - # Make sure we can use yaml path as dependency, e.g.: # "spack spec libdwarf ^ /path/to/libelf.yaml" specs = sp.parse('libdwarf ^ {0}'.format(specfile.strpath)) diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py index be3b74b97d..0929a5ea44 100644 --- a/lib/spack/spack/variant.py +++ b/lib/spack/spack/variant.py @@ -201,7 +201,7 @@ def implicit_variant_conversion(method): return convert -@lang.key_ordering +@lang.lazy_lexicographic_ordering class AbstractVariant(object): """A variant that has not yet decided who it wants to be. It behaves like a multi valued variant which **could** do things. @@ -282,21 +282,14 @@ class AbstractVariant(object): # to a set self._value = tuple(sorted(set(value))) - def _cmp_value(self): - """Returns a tuple of strings containing the values stored in - the variant. + def _cmp_iter(self): + yield self.name - Returns: - tuple of str: values stored in the variant - """ value = self._value if not isinstance(value, tuple): value = (value,) - stringified = tuple(str(x) for x in value) - return stringified - - def _cmp_key(self): - return self.name, self._cmp_value() + value = tuple(str(x) for x in value) + yield value def copy(self): """Returns an instance of a variant equivalent to self |