Ensure deterministic insertion of lambda target methods

Bug: 217727847
Change-Id: If4942f1e4405a9432d8e71986a7ff7895dbed051
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
index 9dbacf4..d37deba 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
@@ -31,10 +31,12 @@
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
@@ -235,6 +237,9 @@
     private void finalizeLambdaDesugaring(
         ClassConverterResult.Builder classConverterResultBuilder,
         Consumer<ProgramMethod> needsProcessing) {
+      // Sort synthesized lambda classes to ensure deterministic insertion of the synthesized
+      // $r8$lambda$ target methods.
+      synthesizedLambdaClasses.sort(Comparator.comparing(LambdaClass::getType));
       for (LambdaClass lambdaClass : synthesizedLambdaClasses) {
         lambdaClass.target.ensureAccessibilityIfNeeded(
             classConverterResultBuilder, needsProcessing);
@@ -422,9 +427,18 @@
     }
 
     private void finalizeLambdaDesugaring() {
+      // Sort synthesized lambda classes to ensure deterministic insertion of the synthesized
+      // $r8$lambda$ target methods.
+      List<Entry<LambdaClass, ProgramMethod>> sortedSynthesizedLambdaClasses =
+          new ArrayList<>(synthesizedLambdaClasses.entrySet());
+      sortedSynthesizedLambdaClasses.sort(Comparator.comparing(entry -> entry.getKey().getType()));
+
       Set<DexProgramClass> classesWithSerializableLambdas = Sets.newIdentityHashSet();
-      synthesizedLambdaClasses.forEach(
-          (lambdaClass, context) -> {
+      sortedSynthesizedLambdaClasses.forEach(
+          entry -> {
+            LambdaClass lambdaClass = entry.getKey();
+            ProgramMethod context = entry.getValue();
+
             lambdaClass.target.ensureAccessibilityIfNeeded();
 
             // Populate set of types with serialized lambda method for removal.