Fix non-determinism in Regex source generator (#78103)

* Fix non-determinism in Regex source generator

The source generator enumerates a Hashtable to write out its contents.  When the keys of the Hashtable are strings, string hash code randomization may result in the order of that enumeration being different in different processes, leading to non-deterministic ordering of values written out and thus non-deterministic source generator output.

* Address PR feedback

5 files changed, 65 insertions, 8 deletions

diff --git a/src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs b/src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
index 16bf09065ae..04ec466a090 100644
--- a/src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
+++ b/src/libraries/System.Text.RegularExpressions/gen/RegexGenerator.Emitter.cs
@@ -123,13 +123,13 @@ namespace System.Text.RegularExpressions.Generator
             if (rm.Tree.CaptureNumberSparseMapping is not null)
             {
                 writer.Write("        base.Caps = new Hashtable {");
-                AppendHashtableContents(writer, rm.Tree.CaptureNumberSparseMapping);
+                AppendHashtableContents(writer, rm.Tree.CaptureNumberSparseMapping.Cast<DictionaryEntry>().OrderBy(de => de.Key as int?));
                 writer.WriteLine($" }};");
             }
             if (rm.Tree.CaptureNameToNumberMapping is not null)
             {
                 writer.Write("        base.CapNames = new Hashtable {");
-                AppendHashtableContents(writer, rm.Tree.CaptureNameToNumberMapping);
+                AppendHashtableContents(writer, rm.Tree.CaptureNameToNumberMapping.Cast<DictionaryEntry>().OrderBy(de => de.Key as string, StringComparer.Ordinal));
                 writer.WriteLine($" }};");
             }
             if (rm.Tree.CaptureNames is not null)
@@ -149,11 +149,10 @@ namespace System.Text.RegularExpressions.Generator
             writer.WriteLine(runnerFactoryImplementation);
             writer.WriteLine($"}}");
 
-            static void AppendHashtableContents(IndentedTextWriter writer, Hashtable ht)
+            static void AppendHashtableContents(IndentedTextWriter writer, IEnumerable<DictionaryEntry> contents)
             {
-                IDictionaryEnumerator en = ht.GetEnumerator();
                 string separator = "";
-                while (en.MoveNext())
+                foreach (DictionaryEntry en in contents)
                 {
                     writer.Write(separator);
                     separator = ", ";
diff --git a/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs b/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs
index 1598c7e3801..6516af531e2 100644
--- a/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs
+++ b/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Regex.cs
@@ -322,6 +322,7 @@ namespace System.Text.RegularExpressions
                 {
                     result[(int)de.Value!] = (int)de.Key;
                 }
+                Array.Sort(result);
             }
 
             return result;
diff --git a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.GetGroupNames.Tests.cs b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.GetGroupNames.Tests.cs
index b270ea509ec..8b1d21f2504 100644
--- a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.GetGroupNames.Tests.cs
+++ b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/Regex.GetGroupNames.Tests.cs
@@ -149,6 +149,10 @@ namespace System.Text.RegularExpressions.Tests
 
             int[] numbers = regex.GetGroupNumbers();
             Assert.Equal(expectedNumbers.Length, numbers.Length);
+            for (int i = 0; i < numbers.Length - 1; i++)
+            {
+                Assert.True(numbers[i] <= numbers[i + 1]);
+            }
 
             string[] names = regex.GetGroupNames();
             Assert.Equal(expectedNames.Length, names.Length);
diff --git a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorHelper.netcoreapp.cs b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorHelper.netcoreapp.cs
index d3a54c331f3..04e9683bdd2 100644
--- a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorHelper.netcoreapp.cs
+++ b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorHelper.netcoreapp.cs
@@ -67,8 +67,8 @@ namespace System.Text.RegularExpressions.Tests
             throw new InvalidOperationException();
         }
 
-        internal static async Task<IReadOnlyList<Diagnostic>> RunGenerator(
-            string code, bool compile = false, LanguageVersion langVersion = LanguageVersion.Preview, MetadataReference[]? additionalRefs = null, bool allowUnsafe = false, CancellationToken cancellationToken = default)
+        private static async Task<(Compilation, GeneratorDriverRunResult)> RunGeneratorCore(
+            string code, LanguageVersion langVersion = LanguageVersion.Preview, MetadataReference[]? additionalRefs = null, bool allowUnsafe = false, CancellationToken cancellationToken = default)
         {
             var proj = new AdhocWorkspace()
                 .AddSolution(SolutionInfo.Create(SolutionId.CreateNewId(), VersionStamp.Create()))
@@ -87,7 +87,13 @@ namespace System.Text.RegularExpressions.Tests
             var generator = new RegexGenerator();
             CSharpGeneratorDriver cgd = CSharpGeneratorDriver.Create(new[] { generator.AsSourceGenerator() }, parseOptions: CSharpParseOptions.Default.WithLanguageVersion(langVersion));
             GeneratorDriver gd = cgd.RunGenerators(comp!, cancellationToken);
-            GeneratorDriverRunResult generatorResults = gd.GetRunResult();
+            return (comp, gd.GetRunResult());
+        }
+
+        internal static async Task<IReadOnlyList<Diagnostic>> RunGenerator(
+            string code, bool compile = false, LanguageVersion langVersion = LanguageVersion.Preview, MetadataReference[]? additionalRefs = null, bool allowUnsafe = false, CancellationToken cancellationToken = default)
+        {
+            (Compilation comp, GeneratorDriverRunResult generatorResults) = await RunGeneratorCore(code, langVersion, additionalRefs, allowUnsafe, cancellationToken);
             if (!compile)
             {
                 return generatorResults.Diagnostics;
@@ -107,6 +113,20 @@ namespace System.Text.RegularExpressions.Tests
             return generatorResults.Diagnostics.Concat(results.Diagnostics).Where(d => d.Severity != DiagnosticSeverity.Hidden).ToArray();
         }
 
+        internal static async Task<string> GenerateSourceText(
+            string code, LanguageVersion langVersion = LanguageVersion.Preview, MetadataReference[]? additionalRefs = null, bool allowUnsafe = false, CancellationToken cancellationToken = default)
+        {
+            (Compilation comp, GeneratorDriverRunResult generatorResults) = await RunGeneratorCore(code, langVersion, additionalRefs, allowUnsafe, cancellationToken);
+            string generatedSource = string.Concat(generatorResults.GeneratedTrees.Select(t => t.ToString()));
+
+            if (generatorResults.Diagnostics.Length != 0)
+            {
+                throw new ArgumentException(string.Join(Environment.NewLine, generatorResults.Diagnostics) + Environment.NewLine + generatedSource);
+            }
+
+            return generatedSource;
+        }
+
         internal static async Task<Regex> SourceGenRegexAsync(
             string pattern, CultureInfo? culture, RegexOptions? options = null, TimeSpan? matchTimeout = null, CancellationToken cancellationToken = default)
         {
diff --git a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorParserTests.cs b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorParserTests.cs
index f9ccaaf568a..642bba87ad0 100644
--- a/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorParserTests.cs
+++ b/src/libraries/System.Text.RegularExpressions/tests/FunctionalTests/RegexGeneratorParserTests.cs
@@ -3,7 +3,9 @@
 
 using Microsoft.CodeAnalysis;
 using Microsoft.CodeAnalysis.CSharp;
+using Microsoft.DotNet.RemoteExecutor;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Globalization;
 using System.Threading.Tasks;
 using Xunit;
@@ -839,5 +841,36 @@ namespace System.Text.RegularExpressions.Tests
                     public static partial Regex Valid();
                 }", compile: true));
         }
+
+        [ConditionalFact(typeof(RemoteExecutor), nameof(RemoteExecutor.IsSupported))]
+        [OuterLoop("Takes several seconds")]
+        public void Deterministic_SameRegexProducesSameSource()
+        {
+            string first = Generate();
+            for (int trials = 0; trials < 3; trials++)
+            {
+                Assert.Equal(first, Generate());
+            }
+
+            static string Generate()
+            {
+                const string Code =
+                    @"using System.Text.RegularExpressions;
+                    partial class C
+                    {
+                        [GeneratedRegex(""(?<Name>\w+) (?<Street>\w+), (?<City>\w+) (?<State>[A-Z]{2}) (?<Zip>[0-9]{5})"")]
+                        public static partial Regex Valid();
+                    }";
+
+                // Generate the source in a new process so that any process-specific randomization is different between runs,
+                // e.g. hash code randomization for strings.
+
+                using RemoteInvokeHandle handle = RemoteExecutor.Invoke(
+                    async () => Console.WriteLine(await RegexGeneratorHelper.GenerateSourceText(Code)),
+                    new RemoteInvokeOptions { StartInfo = new ProcessStartInfo { RedirectStandardOutput = true } });
+
+                return handle.Process.StandardOutput.ReadToEnd();
+            }
+        }
     }
 }