propagation: improve performance

This updates the propagation logic used in `concretize.lp` to avoid rules with `path()`
in the body and instead base propagation around `depends_on()`.

3 files changed, 68 insertions, 61 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index fffa58f337..f0437b9309 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -1411,7 +1411,7 @@ class SpackSolverSetup(object):
                 clauses.append(f.variant_value(spec.name, vname, value))
 
                 if variant.propagate:
-                    clauses.append(f.variant_propagate(spec.name, vname))
+                    clauses.append(f.variant_propagate(spec.name, vname, value, spec.name))
 
                 # Tell the concretizer that this is a possible value for the
                 # variant, to account for things like int/str values where we
@@ -2074,15 +2074,13 @@ class SpecBuilder(object):
         # FIXME: is there a way not to special case 'dev_path' everywhere?
         if name == "dev_path":
             self._specs[pkg].variants.setdefault(
-                name,
-                spack.variant.SingleValuedVariant(name, value)
+                name, spack.variant.SingleValuedVariant(name, value)
             )
             return
 
         if name == "patches":
             self._specs[pkg].variants.setdefault(
-                name,
-                spack.variant.MultiValuedVariant(name, value)
+                name, spack.variant.MultiValuedVariant(name, value)
             )
             return
 
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index a176803074..2bbf3091c6 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -31,6 +31,7 @@ opt_criterion(300, "number of input specs not concretized").
 attr(Name, A1)         :- literal(LiteralID, Name, A1), literal_solved(LiteralID).
 attr(Name, A1, A2)     :- literal(LiteralID, Name, A1, A2), literal_solved(LiteralID).
 attr(Name, A1, A2, A3) :- literal(LiteralID, Name, A1, A2, A3), literal_solved(LiteralID).
+attr(Name, A1, A2, A3, A4) :- literal(LiteralID, Name, A1, A2, A3, A4), literal_solved(LiteralID).
 
 % For these two atoms we only need implications in one direction
 root(Package)         :- attr("root", Package).
@@ -52,6 +53,7 @@ variant_default_value_from_cli(Package, Variant, Value)
 #defined literal/3.
 #defined literal/4.
 #defined literal/5.
+#defined literal/6.
 
 %-----------------------------------------------------------------------------
 % Version semantics
@@ -175,18 +177,20 @@ node_version_satisfies(Package, Constraint)
 % corresponding spec attributes hold.
 condition_holds(ID) :-
   condition(ID, _);
-  attr(Name, A1)         : condition_requirement(ID, Name, A1);
-  attr(Name, A1, A2)     : condition_requirement(ID, Name, A1, A2);
-  attr(Name, A1, A2, A3) : condition_requirement(ID, Name, A1, A2, A3).
+  attr(Name, A1)             : condition_requirement(ID, Name, A1);
+  attr(Name, A1, A2)         : condition_requirement(ID, Name, A1, A2);
+  attr(Name, A1, A2, A3)     : condition_requirement(ID, Name, A1, A2, A3);
+  attr(Name, A1, A2, A3, A4) : condition_requirement(ID, Name, A1, A2, A3, A4).
 
 % condition_holds(ID) implies all imposed_constraints, unless do_not_impose(ID)
 % is derived. This allows imposed constraints to be canceled in special cases.
 impose(ID) :- condition_holds(ID), not do_not_impose(ID).
 
 % conditions that hold impose constraints on other specs
-attr(Name, A1)         :- impose(ID), imposed_constraint(ID, Name, A1).
-attr(Name, A1, A2)     :- impose(ID), imposed_constraint(ID, Name, A1, A2).
-attr(Name, A1, A2, A3) :- impose(ID), imposed_constraint(ID, Name, A1, A2, A3).
+attr(Name, A1)             :- impose(ID), imposed_constraint(ID, Name, A1).
+attr(Name, A1, A2)         :- impose(ID), imposed_constraint(ID, Name, A1, A2).
+attr(Name, A1, A2, A3)     :- impose(ID), imposed_constraint(ID, Name, A1, A2, A3).
+attr(Name, A1, A2, A3, A4) :- impose(ID), imposed_constraint(ID, Name, A1, A2, A3, A4).
 
 % we cannot have additional variant values when we are working with concrete specs
 :- node(Package), hash(Package, Hash),
@@ -202,9 +206,11 @@ attr(Name, A1, A2, A3) :- impose(ID), imposed_constraint(ID, Name, A1, A2, A3).
 #defined condition_requirement/3.
 #defined condition_requirement/4.
 #defined condition_requirement/5.
+#defined condition_requirement/6.
 #defined imposed_constraint/3.
 #defined imposed_constraint/4.
 #defined imposed_constraint/5.
+#defined imposed_constraint/6.
 
 %-----------------------------------------------------------------------------
 % Concrete specs
@@ -378,6 +384,7 @@ possible_provider_weight(Dependency, Virtual, 100, "fallback") :- provider(Depen
 #defined required_provider_condition/3.
 #defined required_provider_condition/4.
 #defined required_provider_condition/5.
+#defined required_provider_condition/6.
 
 %-----------------------------------------------------------------------------
 % Spec Attributes
@@ -400,7 +407,7 @@ node_target(Package, Target)           :- attr("node_target", Package, Target).
 node_target_satisfies(Package, Target) :- attr("node_target_satisfies", Package, Target).
 variant_value(Package, Variant, Value) :- attr("variant_value", Package, Variant, Value).
 variant_set(Package, Variant, Value)   :- attr("variant_set", Package, Variant, Value).
-variant_propagate(Package, Variant)    :- attr("variant_propagate", Package, Variant).
+variant_propagate(Package, Variant, Value, Source)    :- attr("variant_propagate", Package, Variant, Value, Source).
 node_flag(Package, FlagType, Flag)     :- attr("node_flag", Package, FlagType, Flag).
 node_compiler(Package, Compiler)       :- attr("node_compiler", Package, Compiler).
 depends_on(Package, Dependency, Type)  :- attr("depends_on", Package, Dependency, Type).
@@ -422,7 +429,7 @@ attr("node_target", Package, Target)           :- node_target(Package, Target).
 attr("node_target_satisfies", Package, Target) :- node_target_satisfies(Package, Target).
 attr("variant_value", Package, Variant, Value) :- variant_value(Package, Variant, Value).
 attr("variant_set", Package, Variant, Value)   :- variant_set(Package, Variant, Value).
-attr("variant_propagate", Package, Variant)    :- variant_propagate(Package, Variant).
+attr("variant_propagate", Package, Variant, Value, Source)    :- variant_propagate(Package, Variant, Value, Source).
 attr("node_flag", Package, FlagType, Flag)     :- node_flag(Package, FlagType, Flag).
 attr("node_compiler", Package, Compiler)       :- node_compiler(Package, Compiler).
 attr("depends_on", Package, Dependency, Type)  :- depends_on(Package, Dependency, Type).
@@ -509,6 +516,7 @@ error(2, "Attempted to use external for '{0}' which does not satisfy any configu
 #defined external_spec_condition/3.
 #defined external_spec_condition/4.
 #defined external_spec_condition/5.
+#defined external_spec_condition/6.
 
 %-----------------------------------------------------------------------------
 % Config required semantics
@@ -565,23 +573,23 @@ error(2, "Cannot satisfy requirement group for package '{0}'", Package) :-
 variant(Package, Variant) :- variant_condition(ID, Package, Variant),
                              condition_holds(ID).
 
-% propagate the variant
-variant_value(Descendant, Variant, Value) :-
-  node(Package), path(Package, Descendant),
+variant_propagate(Package, Variant, Value, Source) :-
+  node(Package),
+  depends_on(Parent, Package),
+  variant_propagate(Parent, Variant, Value, Source),
+  not variant_set(Package, Variant).
+
+variant_value(Package, Variant, Value) :-
+  node(Package),
   variant(Package, Variant),
-  variant(Descendant, Variant),
-  variant_value(Package, Variant, Value),
-  variant_propagate(Package, Variant),
-  not variant_set(Descendant, Variant),
-  variant_possible_value(Descendant, Variant, Value).
-
-error(2, "{0} and dependency {1} cannot both propagate variant '{2}'", Package1, Package2, Variant) :-
-  Package1 != Package2,
-  variant_propagate(Package1, Variant),
-  variant_propagate(Package2, Variant),
-  path(Package1, Descendent),
-  path(Package2, Descendent),
-  build(Package).
+  variant_propagate(Package, Variant, Value, _),
+  variant_possible_value(Package, Variant, Value).
+
+error(2, "{0} and {1} cannot both propagate variant '{2}' to package {3} with values '{4}' and '{5}'", Source1, Source2, Variant, Package, Value1, Value2) :-
+  variant_propagate(Package, Variant, Value1, Source1),
+  variant_propagate(Package, Variant, Value2, Source2),
+  variant(Package, Variant),
+  Value1 != Value2.
 
 % a variant cannot be set if it is not a variant on the package
 error(2, "Cannot set variant '{0}' for package '{1}' because the variant condition cannot be satisfied for the given spec", Variant, Package)
@@ -727,7 +735,7 @@ variant_single_value(Package, "dev_path")
 % warnings like 'info: atom does not occur in any rule head'.
 #defined variant/2.
 #defined variant_sticky/2.
-#defined variant_propagate/2.
+#defined variant_propagate/4.
 #defined variant_set/3.
 #defined variant_condition/3.
 #defined variant_single_value/2.
@@ -1033,24 +1041,28 @@ compiler_weight(Package, 100)
 
 % propagate flags when compiler match
 can_inherit_flags(Package, Dependency, FlagType)
- :- path(Package, Dependency),
+ :- depends_on(Package, Dependency),
     node_compiler(Package, Compiler),
     node_compiler(Dependency, Compiler),
     not node_flag_set(Dependency, FlagType, _),
     compiler(Compiler), flag_type(FlagType).
+
 node_flag_inherited(Dependency, FlagType, Flag)
  :- node_flag_set(Package, FlagType, Flag), can_inherit_flags(Package, Dependency, FlagType),
     node_flag_propagate(Package, FlagType).
-% Insure propagation
+% Ensure propagation
 :- node_flag_inherited(Package, FlagType, Flag),
     can_inherit_flags(Package, Dependency, FlagType),
     node_flag_propagate(Package, FlagType).
 
-error(0, "{0} and dependency {1} cannot both propagate compiler flags '{2}'", Package, Dependency, FlagType) :-
-  node(Dependency),
-  node_flag_propagate(Package, FlagType),
-  node_flag_propagate(Dependency, FlagType),
-  path(Package, Dependency).
+error(2, "{0} and {1} cannot both propagate compiler flags '{2}' to {3}", Source1, Source2, Package, FlagType) :-
+  depends_on(Source1, Package),
+  depends_on(Source2, Package),
+  node_flag_propagate(Source1, FlagType),
+  node_flag_propagate(Source2, FlagType),
+  can_inherit_flags(Source1, Package, FlagType),
+  can_inherit_flags(Source2, Package, FlagType),
+  Source1 != Source2.
 
 % remember where flags came from
 node_flag_source(Package, FlagType, Package) :- node_flag_set(Package, FlagType, _).
@@ -1060,8 +1072,7 @@ node_flag_source(Dependency, FlagType, Q)
 
 % compiler flags from compilers.yaml are put on nodes if compiler matches
 node_flag(Package, FlagType, Flag)
- :- not node_flag_set(Package, FlagType, _),
-    compiler_version_flag(Compiler, Version, FlagType, Flag),
+ :- compiler_version_flag(Compiler, Version, FlagType, Flag),
     node_compiler_version(Package, Compiler, Version),
     flag_type(FlagType),
     compiler(Compiler),
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 194726baa9..dd1ce821d9 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -156,13 +156,13 @@ is_windows = sys.platform == "win32"
 
 identifier_re = r"\w[\w-]*"
 
-compiler_color = "@g"          #: color for highlighting compilers
-version_color = "@c"           #: color for highlighting versions
-architecture_color ="@m"      #: color for highlighting architectures
-enabled_variant_color = "@B"   #: color for highlighting enabled variants
+compiler_color = "@g"  #: color for highlighting compilers
+version_color = "@c"  #: color for highlighting versions
+architecture_color = "@m"  #: color for highlighting architectures
+enabled_variant_color = "@B"  #: color for highlighting enabled variants
 disabled_variant_color = "r"  #: color for highlighting disabled varaints
-dependency_color = "@."        #: color for highlighting dependencies
-hash_color = "@K"              #: color for highlighting package hashes
+dependency_color = "@."  #: color for highlighting dependencies
+hash_color = "@K"  #: color for highlighting package hashes
 
 #: This map determines the coloring of specs when using color output.
 #: We make the fields different colors to enhance readability.
@@ -4984,19 +4984,19 @@ class SpecLexer(spack.parse.Lexer):
                 (
                     r"\@([\w.\-]*\s*)*(\s*\=\s*\w[\w.\-]*)?",
                     lambda scanner, val: self.token(VER, val),
-                 ),
-                (r"\:",    lambda scanner, val: self.token(COLON, val)),
-                (r"\,",    lambda scanner, val: self.token(COMMA, val)),
-                (r"\^",    lambda scanner, val: self.token(DEP, val)),
-                (r"\+\+",  lambda scanner, val: self.token(D_ON,  val)),
-                (r"\+",    lambda scanner, val: self.token(ON, val)),
-                (r"\-\-",  lambda scanner, val: self.token(D_OFF, val)),
-                (r"\-",    lambda scanner, val: self.token(OFF, val)),
-                (r"\~\~",  lambda scanner, val: self.token(D_OFF, val)),
-                (r"\~",    lambda scanner, val: self.token(OFF, val)),
-                (r"\%",    lambda scanner, val: self.token(PCT, val)),
-                (r"\=\=",  lambda scanner, val: self.token(D_EQ,  val)),
-                (r"\=",    lambda scanner, val: self.token(EQ, val)),
+                ),
+                (r"\:", lambda scanner, val: self.token(COLON, val)),
+                (r"\,", lambda scanner, val: self.token(COMMA, val)),
+                (r"\^", lambda scanner, val: self.token(DEP, val)),
+                (r"\+\+", lambda scanner, val: self.token(D_ON, val)),
+                (r"\+", lambda scanner, val: self.token(ON, val)),
+                (r"\-\-", lambda scanner, val: self.token(D_OFF, val)),
+                (r"\-", lambda scanner, val: self.token(OFF, val)),
+                (r"\~\~", lambda scanner, val: self.token(D_OFF, val)),
+                (r"\~", lambda scanner, val: self.token(OFF, val)),
+                (r"\%", lambda scanner, val: self.token(PCT, val)),
+                (r"\=\=", lambda scanner, val: self.token(D_EQ, val)),
+                (r"\=", lambda scanner, val: self.token(EQ, val)),
                 # Filenames match before identifiers, so no initial filename
                 # component is parsed as a spec (e.g., in subdir/spec.yaml/json)
                 (filename_reg, lambda scanner, v: self.token(FILE, v)),
@@ -5133,9 +5133,7 @@ class SpecParser(spack.parse.Parser):
                         # Raise an error if the previous spec is already
                         # concrete (assigned by hash)
                         if specs and specs[-1]._hash:
-                            raise RedundantSpecError(specs[-1],
-                                                     'compiler, version, '
-                                                     'or variant')
+                            raise RedundantSpecError(specs[-1], "compiler, version, " "or variant")
                         specs.append(self.spec(None))
                     else:
                         self.unexpected_token()