[ILVerify] Implement stack merging (#4448)

* Added test case for unequal stack merging on fallthrough.

* Added test case for merging stack with constrained generic.

* Added additional tests for stack merging.

* Implemented merging of stack values for import fallthrough.

* Modified stack merge for arrays and block reverification.

* Changed ErrorCount check to be performed in ImportFallthrough.

* Changed IsValidBranchTarget to use ref var.

* Implemented Equals for StackValue.

* Added test for invalid unequal stack merge with generics.

* Fixed test AssignReturnValueFromContrainedProperty not using box instruction.

* Refactored and optimized stack merging.

* Removed uneccessary null check in StackValue == operator. Renamed MergeClasses.

* Fixed stack merging producing false negatives for array constrained generics.

4 files changed, 470 insertions, 12 deletions

diff --git a/src/ILVerify/src/ILImporter.StackValue.cs b/src/ILVerify/src/ILImporter.StackValue.cs
index 096c5fcdc..c347ca5fd 100644
--- a/src/ILVerify/src/ILImporter.StackValue.cs
+++ b/src/ILVerify/src/ILImporter.StackValue.cs
@@ -108,13 +108,45 @@ namespace Internal.IL
                 case TypeFlags.ByRef:
                     return CreateByRef(((ByRefType)type).ParameterType);
                 default:
-                    if (type.IsValueType)
+                    if (type.IsValueType || type.IsGenericParameter)
                         return CreateValueType(type);
                     else
                         return CreateObjRef(type);
             }
         }
 
+        public override bool Equals(object obj)
+        {
+            if (Object.ReferenceEquals(this, obj))
+                return true;
+
+            if (!(obj is StackValue))
+                return false;
+
+            var value = (StackValue)obj;
+            return this.Kind == value.Kind && this.Flags == value.Flags && this.Type == value.Type;
+        }
+
+        public static bool operator ==(StackValue left, StackValue right)
+        {
+            return left.Equals(right);
+        }
+
+        public static bool operator !=(StackValue left, StackValue right)
+        {
+            return !(left == right);
+        }
+
+        public override int GetHashCode()
+        {
+                const int prime = 17;
+                int hash = 23;
+                hash = (hash * prime) ^ Type.GetHashCode();
+                hash = (hash * prime) ^ Kind.GetHashCode();
+                hash = (hash * prime) ^ Flags.GetHashCode();
+                return hash;
+        }
+
         // For now, match PEVerify type formating to make it easy to compare with baseline
         static string TypeToStringForByRef(TypeDesc type)
         {
@@ -247,6 +279,229 @@ namespace Internal.IL
             }
         }
 
+        /// <summary>
+        /// Merges two stack values to a common stack value as defined in the ECMA-335 
+        /// standard III.1.8.1.3 (Merging stack states).
+        /// </summary>
+        /// <param name="valueA">The value to be merged with <paramref name="valueB"/>.</param>
+        /// <param name="valueB">The value to be merged with <paramref name="valueA"/>.</param>
+        /// <param name="merged">The resulting type of merging <paramref name="valueA"/> and <paramref name="valueB"/>.</param>
+        /// <returns>True if merge operation was successful, false if the merge operation failed.</returns>
+        public static bool TryMergeStackValues(StackValue valueA, StackValue valueB, out StackValue merged)
+        {
+            merged = valueA;
+
+            if (valueB.IsReadOnly)
+                merged.SetIsReadOnly();
+
+            // Same type
+            if (valueA.Kind == valueB.Kind && valueA.Type == valueB.Type)
+                return true;
+
+            if (valueA.IsNullReference)
+            {
+                //Null can be any reference type
+                if (valueB.Kind == StackValueKind.ObjRef)
+                {
+                    merged = valueB;
+                    return true;
+                }
+            }
+            else if (valueA.Kind == StackValueKind.ObjRef)
+            {
+                if (valueB.Kind != StackValueKind.ObjRef)
+                    return false;
+
+                // Null can be any reference type
+                if (valueB.IsNullReference)
+                    return true;
+
+                // Merging classes always succeeds since System.Object always works
+                merged = StackValue.CreateFromType(MergeObjectReferences(valueA.Type, valueB.Type)); 
+                return true;
+            }
+
+            return false;
+        }
+
+        // Used to merge stack states.
+        static TypeDesc MergeObjectReferences(TypeDesc classA, TypeDesc classB)
+        {
+            if (classA == classB)
+                return classA;
+
+            // Array case
+            if (classA.IsArray)
+            {
+                if (classB.IsArray)
+                    return MergeArrayTypes((ArrayType)classA, (ArrayType)classB);
+            }
+
+            // Assumes generic parameters are boxed at this point.
+            // Return supertype, if related, otherwhise object
+            if (classA.IsGenericParameter || classB.IsGenericParameter)
+            {
+                if (classA.CanCastTo(classB))
+                    return classB;
+                if (classB.CanCastTo(classA))
+                    return classA;
+
+                return classA.Context.GetWellKnownType(WellKnownType.Object);
+            }
+
+            if (classB.IsInterface)
+            {
+                if (classA.IsInterface)
+                    return MergeInterfaceWithInterface(classA, classB);
+                else
+                    return MergeClassWithInterface(classA, classB);
+            }
+            else if (classA.IsInterface)
+                return MergeClassWithInterface(classB, classA);
+
+            return MergeClassWithClass(classA, classB);
+        }
+
+        static TypeDesc MergeInterfaceWithInterface(TypeDesc interfA, TypeDesc interfB)
+        {
+            foreach (var interf in interfA.RuntimeInterfaces)
+            {
+                if (interf == interfB)
+                    return interfB; // Interface A extends interface B
+            }
+
+            foreach (var interf in interfB.RuntimeInterfaces)
+            {
+                if (interf == interfA)
+                    return interfA; // Interface B extends interface A
+            }
+
+            // Get common supertype
+            foreach (var subInterfB in interfB.RuntimeInterfaces)
+            {
+                foreach (var subInterfA in interfA.RuntimeInterfaces)
+                {
+                    if (subInterfA == subInterfB)
+                        return subInterfA;
+                }
+            }
+
+            // No compatible interface found, return Object
+            return interfA.Context.GetWellKnownType(WellKnownType.Object);
+        }
+
+        static TypeDesc MergeClassWithClass(TypeDesc classA, TypeDesc classB)
+        {
+            // Find class hierarchy depth for both classes
+            int aDepth = 0;
+            int bDepth = 0;
+            TypeDesc curType;
+
+            for (curType = classA; curType != null; curType = curType.BaseType)
+                aDepth++;
+
+            for (curType = classB; curType != null; curType = curType.BaseType)
+                bDepth++;
+
+            // Walk up superclass chain until both classes at same level
+            while (aDepth > bDepth)
+            {
+                classA = classA.BaseType;
+                aDepth--;
+            }
+
+            while (bDepth > aDepth)
+            {
+                classB = classB.BaseType;
+                bDepth--;
+            }
+
+            while (classA != classB)
+            {
+                classA = classA.BaseType;
+                classB = classB.BaseType;
+            }
+
+            // At this point we should either have found a common supertype or end up at System.Object
+            Debug.Assert(classA != null);
+
+            return classA;
+        }
+
+        static TypeDesc MergeClassWithInterface(TypeDesc classType, TypeDesc interfaceType)
+        {
+            // Check if class implements interface
+            foreach (var interf in classType.RuntimeInterfaces)
+            {
+                if (interf == interfaceType)
+                    return interfaceType;
+            }
+
+            // Check if class and interface implement common interface
+            foreach (var iInterf in interfaceType.RuntimeInterfaces)
+            {
+                foreach (var cInterf in classType.RuntimeInterfaces)
+                {
+                    if (iInterf == cInterf)
+                        return iInterf;
+                }
+            }
+
+            // No compatible merge, return Object
+            return classType.Context.GetWellKnownType(WellKnownType.Object);
+        }
+
+        static TypeDesc MergeArrayTypes(ArrayType arrayTypeA, ArrayType arrayTypeB)
+        {
+            if (arrayTypeA == arrayTypeB)
+                return arrayTypeA;
+
+            var basicArrayType = arrayTypeA.Context.GetWellKnownType(WellKnownType.Array);
+
+            // If non matching rank, common ancestor = System.Array
+            var rank = arrayTypeA.Rank;
+            var mergeCategory = arrayTypeA.Category;
+            if (rank != arrayTypeB.Rank)
+                return basicArrayType;
+
+            if (arrayTypeA.Category != arrayTypeB.Category)
+            {
+                if (rank == 1)
+                    mergeCategory = TypeFlags.Array;
+                else
+                    return basicArrayType;
+            }
+
+            // Determine merged array element type
+            TypeDesc mergedElementType;
+            if (arrayTypeA.ElementType == arrayTypeB.ElementType)
+                mergedElementType = arrayTypeA.ElementType;
+            else if (arrayTypeA.ElementType.IsArray && arrayTypeB.ElementType.IsArray)
+            {
+                // Array of arrays -> find merged type
+                mergedElementType = MergeArrayTypes(arrayTypeA, arrayTypeB);
+            }
+            //Both array element types are ObjRefs
+            else if ((!arrayTypeA.ElementType.IsValueType && !arrayTypeA.ElementType.IsByRef) && 
+                     (!arrayTypeB.ElementType.IsValueType && !arrayTypeB.ElementType.IsByRef))
+            {
+                // Find common ancestor of the element types
+                mergedElementType = MergeObjectReferences(arrayTypeA.ElementType, arrayTypeB.ElementType);
+            }
+            else
+            {
+                // Array element types have nothing in common
+                return basicArrayType;
+            }
+
+            Debug.Assert(mergeCategory == TypeFlags.Array || mergeCategory == TypeFlags.SzArray);
+
+            if (mergeCategory == TypeFlags.SzArray)
+                return arrayTypeA.Context.GetArrayType(mergedElementType);
+            else
+                return arrayTypeA.Context.GetArrayType(mergedElementType, rank);
+        }
+
         static bool IsSameReducedType(TypeDesc src, TypeDesc dst)
         {
             return GetReducedType(src) == GetReducedType(dst);
@@ -274,6 +529,9 @@ namespace Internal.IL
             if (src.Kind == dst.Kind && src.Type == dst.Type)
                 return true;
 
+            if (dst.Type == null)
+                return false;
+
             switch (src.Kind)
             {
             case StackValueKind.ObjRef:
@@ -397,7 +655,7 @@ namespace Internal.IL
     }
 
     return FALSE;
-#endif 
+#endif
         }
 
 
diff --git a/src/ILVerify/src/ILImporter.Verify.cs b/src/ILVerify/src/ILImporter.Verify.cs
index d0f1375c0..6af162074 100644
--- a/src/ILVerify/src/ILImporter.Verify.cs
+++ b/src/ILVerify/src/ILImporter.Verify.cs
@@ -96,6 +96,16 @@ namespace Internal.IL
             public int? TryIndex;
             public int? HandlerIndex;
             public int? FilterIndex;
+
+            public int ErrorCount
+            {
+                get;
+                private set;
+            }
+            public void IncrementErrorCount()
+            {
+                ErrorCount++;
+            }
         };
 
         void EmptyTheStack() => _stackTop = 0;
@@ -271,12 +281,18 @@ namespace Internal.IL
         // If not, report verification error and continue verification.
         void VerificationError(VerifierError error)
         {
+            if (_currentBasicBlock != null)
+                _currentBasicBlock.IncrementErrorCount();
+
             var args = new VerificationErrorArgs() { Code = error, Offset = _currentInstructionOffset };
             ReportVerificationError(args);
         }
 
         void VerificationError(VerifierError error, object found)
         {
+            if (_currentBasicBlock != null)
+                _currentBasicBlock.IncrementErrorCount();
+
             var args = new VerificationErrorArgs()
             {
                 Code = error,
@@ -288,6 +304,9 @@ namespace Internal.IL
 
         void VerificationError(VerifierError error, object found, object expected)
         {
+            if (_currentBasicBlock != null)
+                _currentBasicBlock.IncrementErrorCount();
+
             var args = new VerificationErrorArgs()
             {
                 Code = error, 
@@ -381,8 +400,8 @@ namespace Internal.IL
                     VerificationError(VerifierError.BranchOutOfTry);
                 else
                 {
-                    var srcRegion = _exceptionRegions[(int)src.TryIndex].ILRegion;
-                    var targetRegion = _exceptionRegions[(int)target.TryIndex].ILRegion;
+                    ref var srcRegion = ref _exceptionRegions[(int)src.TryIndex].ILRegion;
+                    ref var targetRegion = ref _exceptionRegions[(int)target.TryIndex].ILRegion;
                     // If target is inside source region
                     if (srcRegion.TryOffset <= targetRegion.TryOffset && 
                         target.StartOffset < srcRegion.TryOffset + srcRegion.TryLength)
@@ -404,8 +423,8 @@ namespace Internal.IL
                     VerificationError(VerifierError.BranchOutOfFilter);
                 else
                 {
-                    var srcRegion = _exceptionRegions[(int)src.FilterIndex].ILRegion;
-                    var targetRegion = _exceptionRegions[(int)target.FilterIndex].ILRegion;
+                    ref var srcRegion = ref _exceptionRegions[(int)src.FilterIndex].ILRegion;
+                    ref var targetRegion = ref _exceptionRegions[(int)target.FilterIndex].ILRegion;
                     if (srcRegion.FilterOffset <= targetRegion.FilterOffset)
                         VerificationError(VerifierError.BranchIntoFilter);
                     else
@@ -421,8 +440,8 @@ namespace Internal.IL
                     VerificationError(VerifierError.BranchOutOfHandler);
                 else
                 {
-                    var srcRegion = _exceptionRegions[(int)src.HandlerIndex].ILRegion;
-                    var targetRegion = _exceptionRegions[(int)target.HandlerIndex].ILRegion;
+                    ref var srcRegion = ref _exceptionRegions[(int)src.HandlerIndex].ILRegion;
+                    ref var targetRegion = ref _exceptionRegions[(int)target.HandlerIndex].ILRegion;
                     if (srcRegion.HandlerOffset <= targetRegion.HandlerOffset)
                         VerificationError(VerifierError.BranchIntoHandler);
                     else
@@ -1116,9 +1135,21 @@ namespace Internal.IL
                     
                     if (entryStack[i].Type != _stack[i].Type)
                     {
-                        // if we have two object references and one of them has a null type, then this is no error (see test Branching.NullConditional_Valid)
-                        if (_stack[i].Kind == StackValueKind.ObjRef && entryStack[i].Type != null && _stack[i].Type != null)
-                            FatalCheck(false, VerifierError.PathStackUnexpected, entryStack[i], _stack[i]);
+                        if (!IsAssignable(_stack[i], entryStack[i]))
+                        {
+                            StackValue mergedValue;
+                            if (!TryMergeStackValues(entryStack[i], _stack[i], out mergedValue))
+                                FatalCheck(false, VerifierError.PathStackUnexpected, entryStack[i], _stack[i]);
+
+                            // If merge actually changed entry stack
+                            if (mergedValue != entryStack[i])
+                            {
+                                entryStack[i] = mergedValue;
+
+                                if (next.ErrorCount == 0)
+                                    next.EndOffset = 0; // Make sure block is reverified
+                            }
+                        }
                     }
                 }
             }
diff --git a/src/ILVerify/tests/ILTests/BranchingTests.il b/src/ILVerify/tests/ILTests/BranchingTests.il
index d223bb2b8..7b0f45cdd 100644
--- a/src/ILVerify/tests/ILTests/BranchingTests.il
+++ b/src/ILVerify/tests/ILTests/BranchingTests.il
@@ -10,6 +10,40 @@
 {
 }
 
+// Custom Comparer class implementing IEqualityComparer for testing
+.class private auto ansi beforefieldinit CustomComparer
+    extends [System.Runtime]System.Object
+    implements [System.Runtime]System.Collections.IEqualityComparer
+{
+    .method public hidebysig specialname rtspecialname 
+        instance void .ctor () cil managed 
+    {
+        ldarg.0
+        call      instance void [System.Runtime]System.Object::.ctor()
+        ret
+    }
+
+    .method public final hidebysig newslot virtual 
+        instance bool Equals (
+            object x,
+            object y
+        ) cil managed 
+    {
+        ldc.i4.0
+        ret
+    }
+
+    .method public final hidebysig newslot virtual 
+        instance int32 GetHashCode (
+            object obj
+        ) cil managed 
+    {
+        ldarg.1
+        callvirt  instance int32 [System.Runtime]System.Object::GetHashCode()
+        ret
+    }
+}
+
 .class public auto ansi beforefieldinit BranchingTestsType
        extends [System.Runtime]System.Object
 {
@@ -40,7 +74,7 @@
         IL_0014: ret
     }
 
-    .method static public hidebysig void Branching.NullConditional_Invalid_StackUnexpected.PathStackUnexpected() cil managed
+    .method static public hidebysig void Branching.NullConditional_Invalid_StackUnexpected() cil managed
     {
         //object o = null;
         //Type t = o != null ? o.GetType() : o;
@@ -67,6 +101,140 @@
         IL_0014: ret
     }
 
+    .method static public hidebysig void Branching.UnequalStackMerge_Valid(class [System.Runtime]System.Collections.IEqualityComparer equalityComparer,
+        class CustomComparer customComparer) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] class [System.Runtime]System.Collections.IEqualityComparer
+        )
+
+        ldc.i4.0
+        brfalse.s   lbl_cComp
+
+        ldarg.0
+        br.s        lbl_store
+
+    lbl_cComp:
+        ldarg.1
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
+    .method static public hidebysig void Branching.UnequalStackMergeConstrained_Valid<([System.Runtime]System.Collections.IEqualityComparer) T>
+        (class [System.Runtime]System.Collections.IEqualityComparer equalityComparer, !!T customComparer) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] class [System.Runtime]System.Collections.IEqualityComparer
+        )
+
+        ldc.i4.0
+        brfalse.s   lbl_cComp
+
+        ldarg.0
+        br.s        lbl_store
+
+    lbl_cComp:
+        ldarg.1
+        box     !!T
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
+    .method static public hidebysig void Branching.UnequalStackMergeArrays_Valid(class CustomComparer[] comparers,
+        class [System.Runtime]System.Collections.IEqualityComparer[] customComparer) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] class [System.Runtime]System.Collections.IEqualityComparer[]
+        )
+
+        ldarg.0
+        brfalse.s   lbl_cComp
+
+        ldarg.0
+        br.s        lbl_store
+
+    lbl_cComp:
+        ldarg.1
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
+    .method static public hidebysig void Branching.UnequalStackMergeArrays_Invalid_StackUnexpected(class CustomComparer[] comparers,
+        class [System.Runtime]System.Collections.IEqualityComparer[] customComparer) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] class CustomComparer[]
+        )
+
+        ldarg.0
+        brfalse.s   lbl_cComp
+
+        ldarg.0
+        br.s        lbl_store
+
+    lbl_cComp:
+        ldarg.1
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
+    .method static public hidebysig void Branching.UnequalStackMergeGeneric_Invalid_PathStackUnexpected<T>(!!T generic,
+        object obj) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] object obj
+        )
+
+        ldarg.1
+        brfalse.s   lbl_gen
+
+        ldarg.1
+        br.s        lbl_store
+
+    lbl_gen:
+        ldarg.0
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
+    .method static public hidebysig void Branching.UnequalStackMergeGenericArrayConstrain_Valid<(int32[]) T>(!!T generic,
+        int32[] arr) cil managed
+    {
+        .maxstack 1
+        .locals init(
+            [0] int32[] dest
+        )
+
+        ldarg.1
+        brfalse.s   lbl_arr
+
+        ldarg.0
+        box     !!T
+        br.s        lbl_store
+
+    lbl_arr:
+        ldarg.1
+
+    lbl_store:
+        stloc.0
+        ret
+    }
+
     .method static public hidebysig void Branching.InsideTry_Valid() cil managed
     {
         .maxstack 2
diff --git a/src/ILVerify/tests/ILTests/CastingTests.il b/src/ILVerify/tests/ILTests/CastingTests.il
index f26ff16d7..daedc1ee7 100644
--- a/src/ILVerify/tests/ILTests/CastingTests.il
+++ b/src/ILVerify/tests/ILTests/CastingTests.il
@@ -243,6 +243,7 @@
 
         ldarg.0
         callvirt instance !0 class GenericTypeWithConstrained<!!TValueType>::get_Value()
+        box      !!TValueType
         stloc.0
         ret
     }