CompatibilityMatrix::combine handles multiple instances.

Fix an edge case:
1.xml states 1.0/default AND 1.0/custom
2.xml states 2.0/default AND 2.0/strong

The old code generates:
(1.0/default AND 1.0/custom) OR
(2.0/default AND 2.0/custom)

The new code correctly generates:
(1.0/default OR 2.0/default) AND
(1.0/custom)                 AND
(Optional 2.0/strong)

Test: libvintf_test
Test: vintf_object_test
Bug: 74341777

Change-Id: I07f0529b9bc1d046c269fc41f33be307f599422a
Merged-In: I07f0529b9bc1d046c269fc41f33be307f599422a
diff --git a/CompatibilityMatrix.cpp b/CompatibilityMatrix.cpp
index 3f05881..5b216f7 100644
--- a/CompatibilityMatrix.cpp
+++ b/CompatibilityMatrix.cpp
@@ -75,6 +75,30 @@
     return "";
 }
 
+// Split existingHal into a HAL that contains only interface/instance and a HAL
+// that does not contain it. Return the HAL that contains only interface/instance.
+// - Return nullptr if existingHal does not contain interface/instance
+// - Return existingHal if existingHal contains only interface/instance
+// - Remove interface/instance from existingHal, and return a new MatrixHal (that is added
+//   to "this") that contains only interface/instance.
+MatrixHal* CompatibilityMatrix::splitInstance(MatrixHal* existingHal, const std::string& interface,
+                                              const std::string& instance) {
+    if (!existingHal->hasInstance(interface, instance)) {
+        return nullptr;
+    }
+
+    if (existingHal->hasOnlyInstance(interface, instance)) {
+        return existingHal;
+    }
+
+    existingHal->removeInstance(interface, instance);
+    MatrixHal copy = *existingHal;
+    copy.clearInstances();
+    copy.insertInstance(interface, instance);
+
+    return addInternal(std::move(copy));
+}
+
 // Add all package@other_version::interface/instance as an optional instance.
 // If package@this_version::interface/instance is in this (that is, some instance
 // with the same package and interface and instance exists), then other_version is
@@ -89,16 +113,27 @@
         const std::string& name = pair.first;
         MatrixHal& halToAdd = pair.second;
 
-        bool added = false;
-        for (auto* existingHal : getHals(name)) {
-            if (existingHal->containsInstances(halToAdd)) {
-                existingHal->insertVersionRanges(halToAdd);
-                added = true;
-                // Do not break here; try other <hal> with the same name as well.
+        std::set<std::pair<std::string, std::string>> insertedInstances;
+        auto existingHals = getHals(name);
+
+        halToAdd.forEachInstance([&](const std::vector<VersionRange>& versionRanges,
+                                     const std::string& interface, const std::string& instance) {
+            for (auto* existingHal : existingHals) {
+                MatrixHal* splitInstance = this->splitInstance(existingHal, interface, instance);
+                if (splitInstance != nullptr) {
+                    splitInstance->insertVersionRanges(versionRanges);
+                    insertedInstances.insert(std::make_pair(interface, instance));
+                }
             }
+            return true;
+        });
+
+        // Add the remaining instances.
+        for (const auto& pair : insertedInstances) {
+            halToAdd.removeInstance(pair.first, pair.second);
         }
 
-        if (!added) {
+        if (halToAdd.hasAnyInstance()) {
             halToAdd.setOptional(true);
             if (!add(std::move(halToAdd))) {
                 if (error) {