Fix for SPACK-39: Concretization was too restrictive.

- concretize_version() now Use satisfies(), not intersection.
- version class updated with better intersection/union commands
- version now 1.6 "contains" 1.6.5
- added test for new version functionality

- remove none_high and none_low classes
  - version module is now self-contained; save for external 2.7
    functools.total_ordering for 2.6 compatibility.

6 files changed, 163 insertions, 170 deletions

diff --git a/lib/spack/llnl/util/compare/__init__.py b/lib/spack/llnl/util/compare/__init__.py
deleted file mode 100644
index e69de29bb2..0000000000
--- a/lib/spack/llnl/util/compare/__init__.py
+++ /dev/null
diff --git a/lib/spack/llnl/util/compare/none_high.py b/lib/spack/llnl/util/compare/none_high.py
deleted file mode 100644
index 78b41cbaf6..0000000000
--- a/lib/spack/llnl/util/compare/none_high.py
+++ /dev/null
@@ -1,70 +0,0 @@
-##############################################################################
-# Copyright (c) 2013, Lawrence Livermore National Security, LLC.
-# Produced at the Lawrence Livermore National Laboratory.
-#
-# This file is part of Spack.
-# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
-# LLNL-CODE-647188
-#
-# For details, see https://scalability-llnl.github.io/spack
-# Please also see the LICENSE file for our notice and the LGPL.
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License (as published by
-# the Free Software Foundation) version 2.1 dated February 1999.
-#
-# This program is distributed in the hope that it will be useful, but
-# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
-# conditions of the GNU General Public License for more details.
-#
-# You should have received a copy of the GNU Lesser General Public License
-# along with this program; if not, write to the Free Software Foundation,
-# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-##############################################################################
-"""
-Functions for comparing values that may potentially be None.
-These none_high functions consider None as greater than all other values.
-"""
-
-# Preserve builtin min and max functions
-_builtin_min = min
-_builtin_max = max
-
-
-def lt(lhs, rhs):
-    """Less-than comparison.  None is greater than any value."""
-    return lhs != rhs and (rhs is None or (lhs is not None and lhs < rhs))
-
-
-def le(lhs, rhs):
-    """Less-than-or-equal comparison.  None is greater than any value."""
-    return lhs == rhs or lt(lhs, rhs)
-
-
-def gt(lhs, rhs):
-    """Greater-than comparison.  None is greater than any value."""
-    return lhs != rhs and not lt(lhs, rhs)
-
-
-def ge(lhs, rhs):
-    """Greater-than-or-equal comparison.  None is greater than any value."""
-    return lhs == rhs or gt(lhs, rhs)
-
-
-def min(lhs, rhs):
-    """Minimum function where None is greater than any value."""
-    if lhs is None:
-        return rhs
-    elif rhs is None:
-        return lhs
-    else:
-        return _builtin_min(lhs, rhs)
-
-
-def max(lhs, rhs):
-    """Maximum function where None is greater than any value."""
-    if lhs is None or rhs is None:
-        return None
-    else:
-        return _builtin_max(lhs, rhs)
diff --git a/lib/spack/llnl/util/compare/none_low.py b/lib/spack/llnl/util/compare/none_low.py
deleted file mode 100644
index 307bcc8a26..0000000000
--- a/lib/spack/llnl/util/compare/none_low.py
+++ /dev/null
@@ -1,70 +0,0 @@
-##############################################################################
-# Copyright (c) 2013, Lawrence Livermore National Security, LLC.
-# Produced at the Lawrence Livermore National Laboratory.
-#
-# This file is part of Spack.
-# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
-# LLNL-CODE-647188
-#
-# For details, see https://scalability-llnl.github.io/spack
-# Please also see the LICENSE file for our notice and the LGPL.
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License (as published by
-# the Free Software Foundation) version 2.1 dated February 1999.
-#
-# This program is distributed in the hope that it will be useful, but
-# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
-# conditions of the GNU General Public License for more details.
-#
-# You should have received a copy of the GNU Lesser General Public License
-# along with this program; if not, write to the Free Software Foundation,
-# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-##############################################################################
-"""
-Functions for comparing values that may potentially be None.
-These none_low functions consider None as less than all other values.
-"""
-
-# Preserve builtin min and max functions
-_builtin_min = min
-_builtin_max = max
-
-
-def lt(lhs, rhs):
-    """Less-than comparison.  None is lower than any value."""
-    return lhs != rhs and (lhs is None or (rhs is not None and lhs < rhs))
-
-
-def le(lhs, rhs):
-    """Less-than-or-equal comparison.  None is less than any value."""
-    return lhs == rhs or lt(lhs, rhs)
-
-
-def gt(lhs, rhs):
-    """Greater-than comparison.  None is less than any value."""
-    return lhs != rhs and not lt(lhs, rhs)
-
-
-def ge(lhs, rhs):
-    """Greater-than-or-equal comparison.  None is less than any value."""
-    return lhs == rhs or gt(lhs, rhs)
-
-
-def min(lhs, rhs):
-    """Minimum function where None is less than any value."""
-    if lhs is None or rhs is None:
-        return None
-    else:
-        return _builtin_min(lhs, rhs)
-
-
-def max(lhs, rhs):
-    """Maximum function where None is less than any value."""
-    if lhs is None:
-        return rhs
-    elif rhs is None:
-        return lhs
-    else:
-        return _builtin_max(lhs, rhs)
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index e6d1bb87d4..9f9cd1789d 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -68,11 +68,13 @@ class DefaultConcretizer(object):
         # If there are known avaialble versions, return the most recent
         # version that satisfies the spec
         pkg = spec.package
-        valid_versions = pkg.available_versions.intersection(spec.versions)
+        valid_versions = [v for v in pkg.available_versions
+                          if any(v.satisfies(sv) for sv in spec.versions)]
         if valid_versions:
             spec.versions = ver([valid_versions[-1]])
         else:
-            raise NoValidVerionError(spec)
+            print spec
+            raise NoValidVersionError(spec)
 
 
     def concretize_architecture(self, spec):
@@ -160,9 +162,9 @@ class UnavailableCompilerVersionError(spack.error.SpackError):
             "Run 'spack compilers' to see available compiler Options.")
 
 
-class NoValidVerionError(spack.error.SpackError):
+class NoValidVersionError(spack.error.SpackError):
     """Raised when there is no available version for a package that
        satisfies a spec."""
     def __init__(self, spec):
-        super(NoValidVerionError, self).__init__(
+        super(NoValidVersionError, self).__init__(
             "No available version of %s matches '%s'" % (spec.name, spec.versions))
diff --git a/lib/spack/spack/test/versions.py b/lib/spack/spack/test/versions.py
index 454ab36b8a..20e946e90e 100644
--- a/lib/spack/spack/test/versions.py
+++ b/lib/spack/spack/test/versions.py
@@ -95,6 +95,10 @@ class VersionsTest(unittest.TestCase):
         self.assertEqual(ver(expected), ver(a).intersection(ver(b)))
 
 
+    def check_union(self, expected, a, b):
+        self.assertEqual(ver(expected), ver(a).union(ver(b)))
+
+
     def test_two_segments(self):
         self.assert_ver_eq('1.0', '1.0')
         self.assert_ver_lt('1.0', '2.0')
@@ -217,12 +221,16 @@ class VersionsTest(unittest.TestCase):
         self.assert_in('1.3.5-7', '1.2:1.4')
         self.assert_not_in('1.1', '1.2:1.4')
         self.assert_not_in('1.5', '1.2:1.4')
-        self.assert_not_in('1.4.2', '1.2:1.4')
+
+        self.assert_in('1.4.2', '1.2:1.4')
+        self.assert_not_in('1.4.2', '1.2:1.4.0')
 
         self.assert_in('1.2.8', '1.2.7:1.4')
         self.assert_in('1.2.7:1.4', ':')
         self.assert_not_in('1.2.5', '1.2.7:1.4')
-        self.assert_not_in('1.4.1', '1.2.7:1.4')
+
+        self.assert_in('1.4.1', '1.2.7:1.4')
+        self.assert_not_in('1.4.1', '1.2.7:1.4.0')
 
 
     def test_in_list(self):
@@ -254,6 +262,17 @@ class VersionsTest(unittest.TestCase):
         self.assert_overlaps('1.6:1.9', ':')
 
 
+    def test_overlap_with_containment(self):
+        self.assert_in('1.6.5', '1.6')
+        self.assert_in('1.6.5', ':1.6')
+
+        self.assert_overlaps('1.6.5', ':1.6')
+        self.assert_overlaps(':1.6', '1.6.5')
+
+        self.assert_not_in(':1.6', '1.6.5')
+        self.assert_in('1.6.5', ':1.6')
+
+
     def test_lists_overlap(self):
         self.assert_overlaps('1.2b:1.7,5', '1.6:1.9,1')
         self.assert_overlaps('1,2,3,4,5', '3,4,5,6,7')
@@ -311,6 +330,32 @@ class VersionsTest(unittest.TestCase):
         self.check_intersection(['0:1'], [':'], ['0:1'])
 
 
+    def test_intersect_with_containment(self):
+        self.check_intersection('1.6.5', '1.6.5', ':1.6')
+        self.check_intersection('1.6.5', ':1.6', '1.6.5')
+
+        self.check_intersection('1.6:1.6.5', ':1.6.5', '1.6')
+        self.check_intersection('1.6:1.6.5', '1.6', ':1.6.5')
+
+
+    def test_union_with_containment(self):
+        self.check_union(':1.6', '1.6.5', ':1.6')
+        self.check_union(':1.6', ':1.6', '1.6.5')
+
+        self.check_union(':1.6', ':1.6.5', '1.6')
+        self.check_union(':1.6', '1.6', ':1.6.5')
+
+
+    def test_union_with_containment(self):
+        self.check_union(':', '1.0:', ':2.0')
+
+        self.check_union('1:4', '1:3', '2:4')
+        self.check_union('1:4', '2:4', '1:3')
+
+        # Tests successor/predecessor case.
+        self.check_union('1:4', '1:2', '3:4')
+
+
     def test_basic_version_satisfaction(self):
         self.assert_satisfies('4.7.3',   '4.7.3')
 
@@ -326,6 +371,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_does_not_satisfy('4.8',   '4.9')
         self.assert_does_not_satisfy('4',     '4.9')
 
+
     def test_basic_version_satisfaction_in_lists(self):
         self.assert_satisfies(['4.7.3'],   ['4.7.3'])
 
@@ -341,6 +387,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_does_not_satisfy(['4.8'],   ['4.9'])
         self.assert_does_not_satisfy(['4'],     ['4.9'])
 
+
     def test_version_range_satisfaction(self):
         self.assert_satisfies('4.7b6', '4.3:4.7')
         self.assert_satisfies('4.3.0', '4.3:4.7')
@@ -352,6 +399,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_satisfies('4.7b6',        '4.3:4.7')
         self.assert_does_not_satisfy('4.8.0', '4.3:4.7')
 
+
     def test_version_range_satisfaction_in_lists(self):
         self.assert_satisfies(['4.7b6'], ['4.3:4.7'])
         self.assert_satisfies(['4.3.0'], ['4.3:4.7'])
diff --git a/lib/spack/spack/version.py b/lib/spack/spack/version.py
index fbf86db8e1..cc83634137 100644
--- a/lib/spack/spack/version.py
+++ b/lib/spack/spack/version.py
@@ -50,10 +50,6 @@ from bisect import bisect_left
 from functools import wraps
 from external.functools import total_ordering
 
-import llnl.util.compare.none_high as none_high
-import llnl.util.compare.none_low as none_low
-import spack.error
-
 # Valid version characters
 VALID_VERSION = r'[A-Za-z0-9_.-]'
 
@@ -256,18 +252,39 @@ class Version(object):
 
     @coerced
     def __contains__(self, other):
-        return self == other
+        if other is None:
+            return False
+        return other.version[:len(self.version)] == self.version
+
+
+    def is_predecessor(self, other):
+        """True if the other version is the immediate predecessor of this one.
+           That is, NO versions v exist such that:
+           (self < v < other and v not in self).
+        """
+        if len(self.version) != len(other.version):
+            return False
+
+        sl = self.version[-1]
+        ol = other.version[-1]
+        return type(sl) == int and type(ol) == int and (ol - sl == 1)
+
+
+    def is_successor(self, other):
+        return other.is_predecessor(self)
 
 
     @coerced
     def overlaps(self, other):
-        return self == other
+        return self in other or other in self
 
 
     @coerced
     def union(self, other):
-        if self == other:
+        if self == other or other in self:
             return self
+        elif self in other:
+            return other
         else:
             return VersionList([self, other])
 
@@ -290,7 +307,7 @@ class VersionRange(object):
 
         self.start = start
         self.end = end
-        if start and end and  end < start:
+        if start and end and end < start:
             raise ValueError("Invalid Version range: %s" % self)
 
 
@@ -312,9 +329,12 @@ class VersionRange(object):
         if other is None:
             return False
 
-        return (none_low.lt(self.start, other.start) or
-                (self.start == other.start and
-                 none_high.lt(self.end, other.end)))
+        s, o = self, other
+        if s.start != o.start:
+            return s.start is None or (o.start is not None and s.start < o.start)
+
+        return (s.end != o.end and
+                o.end is None or (s.end is not None and s.end < o.end))
 
 
     @coerced
@@ -335,8 +355,23 @@ class VersionRange(object):
 
     @coerced
     def __contains__(self, other):
-        return (none_low.ge(other.start, self.start) and
-                none_high.le(other.end, self.end))
+        if other is None:
+            return False
+
+        in_lower = (self.start == other.start or
+                    self.start is None or
+                    (other.start is not None and (
+                        self.start < other.start or
+                        other.start in self.start)))
+        if not in_lower:
+            return False
+
+        in_upper = (self.end == other.end or
+                    self.end is None or
+                    (other.end is not None and (
+                        self.end > other.end or
+                        other.end in self.end)))
+        return in_upper
 
 
     @coerced
@@ -372,27 +407,75 @@ class VersionRange(object):
 
     @coerced
     def overlaps(self, other):
-        return (other in self or self in other or
-                ((self.start == None or other.end is None or
-                  self.start <= other.end) and
-                 (other.start is None or self.end == None or
-                  other.start <= self.end)))
+        return ((self.start == None or other.end is None or
+                 self.start <= other.end or
+                 other.end in self.start or self.start in other.end) and
+                (other.start is None or self.end == None or
+                 other.start <= self.end or
+                 other.start in self.end or self.end in other.start))
 
 
     @coerced
     def union(self, other):
-        if self.overlaps(other):
-            return VersionRange(none_low.min(self.start, other.start),
-                                none_high.max(self.end, other.end))
-        else:
+        if not self.overlaps(other):
+            if (self.end is not None and other.start is not None and
+                self.end.is_predecessor(other.start)):
+                return VersionRange(self.start, other.end)
+
+            if (other.end is not None and self.start is not None and
+                other.end.is_predecessor(self.start)):
+                return VersionRange(other.start, self.end)
+
             return VersionList([self, other])
 
+        # if we're here, then we know the ranges overlap.
+        if self.start is None or other.start is None:
+            start = None
+        else:
+            start = self.start
+            # TODO: See note in intersection() about < and in discrepancy.
+            if self.start in other.start or other.start < self.start:
+                start = other.start
+
+        if self.end is None or other.end is None:
+            end = None
+        else:
+            end = self.end
+            # TODO: See note in intersection() about < and in discrepancy.
+            if not other.end in self.end:
+                if end in other.end or other.end > self.end:
+                    end = other.end
+
+        return VersionRange(start, end)
+
 
     @coerced
     def intersection(self, other):
         if self.overlaps(other):
-            return VersionRange(none_low.max(self.start, other.start),
-                                none_high.min(self.end, other.end))
+            if self.start is None:
+                start = other.start
+            else:
+                start = self.start
+                if other.start is not None:
+                    if other.start > start or other.start in start:
+                        start = other.start
+
+            if self.end is None:
+                end = other.end
+            else:
+                end = self.end
+                # TODO: does this make sense?
+                # This is tricky:
+                #     1.6.5 in 1.6 = True  (1.6.5 is more specific)
+                #     1.6 < 1.6.5  = True  (lexicographic)
+                # Should 1.6 NOT be less than 1.6.5?  Hm.
+                # Here we test (not end in other.end) first to avoid paradox.
+                if other.end is not None and not end in other.end:
+                    if other.end < end or other.end in end:
+                        end = other.end
+
+            return VersionRange(start, end)
+
         else:
             return VersionList()