Guarantee a stable ordering with build metadatastable-sort-with-build

Sorting any permutation of Version objects should always yield the same
result, even if those hold some build metadata.

To that end, the "precedence_key" is now used exclusively for sorting;
direct comparisons between Version objects still ignores the "build"
metadata, using a different precedence key.

For performance improvements, both precedence keys are cached.

Closes: #132

4 files changed, 66 insertions, 11 deletions

diff --git a/ChangeLog b/ChangeLog
index 0d30c7e..110b054 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,10 +1,14 @@
 ChangeLog
 =========
 
-2.9.1 (unreleased)
-------------------
+2.10.0 (unreleased)
+-------------------
+
+*New:*
 
-- Nothing changed yet.
+    * `132 <https://github.com/rbarrois/python-semanticversion/issues/132>`_:
+      Ensure sorting a collection of versions is always stable, even with
+      build metadata.
 
 
 2.9.0 (2022-02-06)
diff --git a/docs/reference.rst b/docs/reference.rst
index 6d1101b..b2946d9 100644
--- a/docs/reference.rst
+++ b/docs/reference.rst
@@ -130,7 +130,16 @@ Representing a version (the Version class)
         The actual value of the attribute is considered an implementation detail; the only
         guarantee is that ordering versions by their precedence_key will comply with semver precedence rules.
 
-        Note that the :attr:`~Version.build` isn't included in the precedence_key computatin.
+
+        .. warning::
+
+           .. versionchanged:: 2.10.0
+
+           The :attr:`~Version.build` is included in the precedence_key computation, but
+           only for ordering stability.
+           The only guarantee is that, for a given release of python-semanticversion, two versions'
+           :attr:`~Version.precedence_key` will always compare in the same direction if they include
+           build metadata; that ordering is an implementation detail and shouldn't be relied upon.
 
     .. attribute:: partial
 
diff --git a/semantic_version/base.py b/semantic_version/base.py
index 82a9af0..777c27a 100644
--- a/semantic_version/base.py
+++ b/semantic_version/base.py
@@ -118,6 +118,12 @@ class Version(object):
 
         self.partial = partial
 
+        # Cached precedence keys
+        # _cmp_precedence_key is used for semver-precedence comparison
+        self._cmp_precedence_key = self._build_precedence_key(with_build=False)
+        # _sort_precedence_key is used for self.precedence_key, esp. for sorted(...)
+        self._sort_precedence_key = self._build_precedence_key(with_build=True)
+
     @classmethod
     def _coerce(cls, value, allow_none=False):
         if value is None and allow_none:
@@ -408,11 +414,15 @@ class Version(object):
         # at least a field being `None`.
         return hash((self.major, self.minor, self.patch, self.prerelease, self.build))
 
-    @property
-    def precedence_key(self):
+    def _build_precedence_key(self, with_build=False):
+        """Build a precedence key.
+
+        The "build" component should only be used when sorting an iterable
+        of versions.
+        """
         if self.prerelease:
             prerelease_key = tuple(
-                NumericIdentifier(part) if re.match(r'^[0-9]+$', part) else AlphaIdentifier(part)
+                NumericIdentifier(part) if part.isdigit() else AlphaIdentifier(part)
                 for part in self.prerelease
             )
         else:
@@ -420,13 +430,31 @@ class Version(object):
                 MaxIdentifier(),
             )
 
+        if not with_build:
+            return (
+                self.major,
+                self.minor,
+                self.patch,
+                prerelease_key,
+            )
+
+        build_key = tuple(
+            NumericIdentifier(part) if part.isdigit() else AlphaIdentifier(part)
+            for part in self.build or ()
+        )
+
         return (
             self.major,
             self.minor,
             self.patch,
             prerelease_key,
+            build_key,
         )
 
+    @property
+    def precedence_key(self):
+        return self._sort_precedence_key
+
     def __cmp__(self, other):
         if not isinstance(other, self.__class__):
             return NotImplemented
@@ -458,22 +486,22 @@ class Version(object):
     def __lt__(self, other):
         if not isinstance(other, self.__class__):
             return NotImplemented
-        return self.precedence_key < other.precedence_key
+        return self._cmp_precedence_key < other._cmp_precedence_key
 
     def __le__(self, other):
         if not isinstance(other, self.__class__):
             return NotImplemented
-        return self.precedence_key <= other.precedence_key
+        return self._cmp_precedence_key <= other._cmp_precedence_key
 
     def __gt__(self, other):
         if not isinstance(other, self.__class__):
             return NotImplemented
-        return self.precedence_key > other.precedence_key
+        return self._cmp_precedence_key > other._cmp_precedence_key
 
     def __ge__(self, other):
         if not isinstance(other, self.__class__):
             return NotImplemented
-        return self.precedence_key >= other.precedence_key
+        return self._cmp_precedence_key >= other._cmp_precedence_key
 
 
 class SpecItem(object):
diff --git a/tests/test_base.py b/tests/test_base.py
index 4a844c3..e6a3733 100755
--- a/tests/test_base.py
+++ b/tests/test_base.py
@@ -229,6 +229,20 @@ class VersionTestCase(unittest.TestCase):
         self.assertTrue(v != '0.1.0')
         self.assertFalse(v == '0.1.0')
 
+    def test_stable_ordering(self):
+        a = [
+            base.Version('0.1.0'),
+            base.Version('0.1.0+a'),
+            base.Version('0.1.0+a.1'),
+            base.Version('0.1.1-a1'),
+        ]
+        b = [a[1], a[3], a[0], a[2]]
+
+        self.assertEqual(
+            sorted(a, key=lambda v: v.precedence_key),
+            sorted(b, key=lambda v: v.precedence_key),
+        )
+
     def test_bump_clean_versions(self):
         # We Test each property explicitly as the == comparator for versions
         # does not distinguish between prerelease or builds for equality.