Add native comparison of configured targets

... and use it when normalizing the origins of actions. For this
task, any well-defined linear order is sufficient. Using a native
comparision (rather than comparing the canonical serialisation)
significantly speeds up that normalisation process, as the assumption
that it would be rare that an action has more than one origin turned
out to be false. In fact, we have seeen cases where this sorting
used to take several seconds before this change, so that this change
reduced analysis time by more than a factor of 5.

4 files changed, 45 insertions, 2 deletions

diff --git a/src/buildtool/build_engine/base_maps/entity_name_data.hpp b/src/buildtool/build_engine/base_maps/entity_name_data.hpp
index 4302d902..f4241de6 100644
--- a/src/buildtool/build_engine/base_maps/entity_name_data.hpp
+++ b/src/buildtool/build_engine/base_maps/entity_name_data.hpp
@@ -15,6 +15,7 @@
 #ifndef INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_BASE_MAPS_ENTITY_NAME_DATA_HPP
 #define INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_BASE_MAPS_ENTITY_NAME_DATA_HPP
 
+#include <compare>
 #include <cstddef>
 #include <cstdint>
 #include <filesystem>
@@ -38,6 +39,16 @@ struct AnonymousTarget {
         -> bool {
         return rule_map == other.rule_map and target_node == other.target_node;
     }
+    [[nodiscard]] auto operator<(AnonymousTarget const& other) const noexcept
+        -> bool {
+        if (rule_map < other.rule_map) {
+            return true;
+        }
+        if (other.rule_map < rule_map) {
+            return false;
+        }
+        return target_node < other.target_node;
+    }
 };
 
 enum class ReferenceType : std::int8_t {
@@ -80,6 +91,19 @@ struct NamedTarget {
                                          NamedTarget const& y) -> bool {
         return not(x == y);
     }
+    [[nodiscard]] auto operator<(NamedTarget const& other) const noexcept
+        -> bool {
+        if (auto const res = repository <=> other.repository; res != 0) {
+            return res < 0;
+        }
+        if (auto const res = module <=> other.module; res != 0) {
+            return res < 0;
+        }
+        if (auto const res = name <=> other.name; res != 0) {
+            return res < 0;
+        }
+        return reference_t < other.reference_t;
+    }
 };
 
 class EntityName {
@@ -107,6 +131,9 @@ class EntityName {
     friend auto operator==(EntityName const& a, EntityName const& b) -> bool {
         return a.entity_name_ == b.entity_name_;
     }
+    friend auto operator<(EntityName const& a, EntityName const& b) -> bool {
+        return a.entity_name_ < b.entity_name_;
+    }
     [[nodiscard]] auto IsAnonymousTarget() const -> bool {
         return std::holds_alternative<AnonymousTarget>(entity_name_);
     }
diff --git a/src/buildtool/build_engine/expression/configuration.hpp b/src/buildtool/build_engine/expression/configuration.hpp
index ec3fde66..dadb71d2 100644
--- a/src/buildtool/build_engine/expression/configuration.hpp
+++ b/src/buildtool/build_engine/expression/configuration.hpp
@@ -16,6 +16,7 @@
 #define INCLUDED_SRC_BUILDTOOL_BUILD_ENGINE_EXPRESSION_CONFIGURATION_HPP
 
 #include <algorithm>
+#include <compare>
 #include <cstddef>
 #include <functional>
 #include <optional>
@@ -92,6 +93,10 @@ class Configuration {
         return expr_ == other.expr_;
     }
 
+    [[nodiscard]] auto operator<(const Configuration& other) const -> bool {
+        return expr_->ToHash() < other.expr_->ToHash();
+    }
+
     [[nodiscard]] auto hash() const noexcept -> std::size_t {
         return std::hash<ExpressionPtr>{}(expr_);
     }
diff --git a/src/buildtool/build_engine/target_map/configured_target.hpp b/src/buildtool/build_engine/target_map/configured_target.hpp
index 8e8c6033..61702dc7 100644
--- a/src/buildtool/build_engine/target_map/configured_target.hpp
+++ b/src/buildtool/build_engine/target_map/configured_target.hpp
@@ -48,6 +48,17 @@ struct ConfiguredTarget {
             target.ToString(),
             AbbreviateJson(PruneJson(config.ToJson()), config_length));
     }
+
+    [[nodiscard]] auto operator<(ConfiguredTarget const& other) const noexcept
+        -> bool {
+        if (target < other.target) {
+            return true;
+        }
+        if (other.target < target) {
+            return false;
+        }
+        return config < other.config;
+    }
 };
 
 using ConfiguredTargetPtr = std::shared_ptr<ConfiguredTarget>;
diff --git a/src/buildtool/build_engine/target_map/result_map.hpp b/src/buildtool/build_engine/target_map/result_map.hpp
index 9d688823..7f6a8e14 100644
--- a/src/buildtool/build_engine/target_map/result_map.hpp
+++ b/src/buildtool/build_engine/target_map/result_map.hpp
@@ -228,8 +228,8 @@ class ResultTargetMap {
                 std::sort(origin_map[i.first].begin(),
                           origin_map[i.first].end(),
                           [](auto const& left, auto const& right) {
-                              auto left_target = left.first.ToString();
-                              auto right_target = right.first.ToString();
+                              auto const& left_target = left.first;
+                              auto const& right_target = right.first;
                               return (left_target < right_target) or
                                      (left_target == right_target and
                                       left.second < right.second);