[delegate] Fix multicast remove behaviour

The .NET delegate removal semantic is a bit unpredictable. For example, the following (d1 + d2 + d3) - (d1 + d3) is going to return the d123 delegate, and not the d2 delegate as we could have guessed. This is because removal will remove the `list' of delegates as a whole, and not the elements in the list.

The previous implementation would then have a different behavior than the one observed on .NET.

Fixes bug #36646

2 files changed, 77 insertions, 36 deletions

diff --git a/mcs/class/corlib/System/MulticastDelegate.cs b/mcs/class/corlib/System/MulticastDelegate.cs
index b09280ab52b..4d7c91c10c4 100644
--- a/mcs/class/corlib/System/MulticastDelegate.cs
+++ b/mcs/class/corlib/System/MulticastDelegate.cs
@@ -170,6 +170,32 @@ namespace System
 			return ret;
 		}
 
+		/* Based on the Boyer–Moore string search algorithm */
+		int LastIndexOf (Delegate[] haystack, Delegate[] needle)
+		{
+			if (haystack.Length < needle.Length)
+				return -1;
+
+			if (haystack.Length == needle.Length) {
+				for (int i = 0; i < haystack.Length; ++i)
+					if (!haystack [i].Equals (needle [i]))
+						return -1;
+
+				return 0;
+			}
+
+			for (int i = haystack.Length - needle.Length, j; i >= 0;) {
+				for (j = 0; needle [j].Equals (haystack [i]); ++i, ++j) {
+					if (j == needle.Length - 1)
+						return i - j;
+				}
+
+				i -= j + 1;
+			}
+
+			return -1;
+		}
+
 		protected sealed override Delegate RemoveImpl (Delegate value)
 		{
 			if (value == null)
@@ -210,42 +236,23 @@ namespace System
 				return ret;
 			} else {
 				/* wild case : remove MulticastDelegate from MulticastDelegate
-				 * complexity is O(m * n), with n the number of elements in
+				 * complexity is O(m + n), with n the number of elements in
 				 * this.delegates and m the number of elements in other.delegates */
-				MulticastDelegate ret = AllocDelegateLike_internal (this);
-				ret.delegates = new Delegate [delegates.Length];
-
-				/* we should use a set with O(1) lookup complexity
-				 * but HashSet is implemented in System.Core.dll */
-				List<Delegate> other_delegates = new List<Delegate> ();
-				for (int i = 0; i < other.delegates.Length; ++i)
-					other_delegates.Add (other.delegates [i]);
 
-				int idx = delegates.Length;
+				if (delegates.Equals (other.delegates))
+					return null;
 
 				/* we need to remove elements from the end to the beginning, as
 				 * the addition and removal of delegates behaves like a stack */
-				for (int i = delegates.Length - 1; i >= 0; --i) {
-					/* if delegates[i] is not in other_delegates,
-					 * then we can safely add it to ret.delegates
-					 * otherwise we remove it from other_delegates */
-					if (!other_delegates.Remove (delegates [i]))
-						ret.delegates [--idx] = delegates [i];
-				}
-
-				/* the elements are at the end of the array, we
-				 * need to move them back to the beginning of it */
-				int count = delegates.Length - idx;
-				Array.Copy (ret.delegates, idx, ret.delegates, 0, count);
-
-				if (count == 0)
-					return null;
+				int idx = LastIndexOf (delegates, other.delegates);
+				if (idx == -1)
+					return this;
 
-				if (count == 1)
-					return ret.delegates [0];
+				MulticastDelegate ret = AllocDelegateLike_internal (this);
+				ret.delegates = new Delegate [delegates.Length - other.delegates.Length];
 
-				if (count != delegates.Length)
-					Array.Resize (ref ret.delegates, count);
+				Array.Copy (delegates, ret.delegates, idx);
+				Array.Copy (delegates, idx + other.delegates.Length, ret.delegates, idx, delegates.Length - idx - other.delegates.Length);
 
 				return ret;
 			}
diff --git a/mono/tests/delegate7.cs b/mono/tests/delegate7.cs
index a89657a4ba2..dd3a2a3ea27 100644
--- a/mono/tests/delegate7.cs
+++ b/mono/tests/delegate7.cs
@@ -16,6 +16,10 @@ class Tests {
 		v += 4;
 		Console.WriteLine ("Test.F4");
 	}
+	static void F8 () {
+		v += 8;
+		Console.WriteLine ("Test.F8");
+	}
 
 	public static int Main () {
 		return TestDriver.RunTests (typeof (Tests));
@@ -33,6 +37,7 @@ class Tests {
 		SimpleDelegate d1 = new SimpleDelegate (F1);
 		SimpleDelegate d2 = new SimpleDelegate (F2);
 		SimpleDelegate d4 = new SimpleDelegate (F4);
+		SimpleDelegate d8 = new SimpleDelegate (F8);
 
 		if (d1 - d1 != null)
 			return 1;
@@ -82,21 +87,21 @@ class Tests {
 
 		if (d12 - d12 != null)
 			return 21;
-		if (!check_is_expected_v (d12 - d14, 2))
+		if (!check_is_expected_v (d12 - d14, 3))
 			return 22;
-		if (!check_is_expected_v (d12 - d24, 1))
+		if (!check_is_expected_v (d12 - d24, 3))
 			return 23;
 
-		if (!check_is_expected_v (d14 - d12, 4))
+		if (!check_is_expected_v (d14 - d12, 5))
 			return 24;
 		if (d14 - d14 != null)
 			return 25;
-		if (!check_is_expected_v (d14 - d24, 1))
+		if (!check_is_expected_v (d14 - d24, 5))
 			return 26;
 
-		if (!check_is_expected_v (d24 - d12, 4))
+		if (!check_is_expected_v (d24 - d12, 6))
 			return 27;
-		if (!check_is_expected_v (d24 - d14, 2))
+		if (!check_is_expected_v (d24 - d14, 6))
 			return 28;
 		if (d24 - d24 != null)
 			return 29;
@@ -112,7 +117,7 @@ class Tests {
 
 		if (!check_is_expected_v (d124 - d12, 4))
 			return 34;
-		if (!check_is_expected_v (d124 - d14, 2))
+		if (!check_is_expected_v (d124 - d14, 7))
 			return 35;
 		if (!check_is_expected_v (d124 - d24, 1))
 			return 36;
@@ -120,6 +125,35 @@ class Tests {
 		if (d124 - d124 != null)
 			return 37;
 
+		SimpleDelegate d1248 = d1 + d2 + d4 + d8;
+
+		if (!check_is_expected_v (d1248 - (d1 + d2), 12))
+			return 41;
+		if (!check_is_expected_v (d1248 - (d1 + d4), 15))
+			return 42;
+		if (!check_is_expected_v (d1248 - (d1 + d8), 15))
+			return 43;
+		if (!check_is_expected_v (d1248 - (d2 + d4), 9))
+			return 44;
+		if (!check_is_expected_v (d1248 - (d2 + d8), 15))
+			return 45;
+		if (!check_is_expected_v (d1248 - (d4 + d8), 3))
+			return 46;
+
+		if (!check_is_expected_v (d1248 - (d1 + d2 + d4), 8))
+			return 51;
+		if (!check_is_expected_v (d1248 - (d1 + d2 + d8), 15))
+			return 52;
+		if (!check_is_expected_v (d1248 - (d1 + d4 + d8), 15))
+			return 53;
+		if (!check_is_expected_v (d1248 - (d2 + d4 + d8), 1))
+			return 54;
+		if (!check_is_expected_v (d1248 - (d2 + d4 + d8), 1))
+			return 54;
+
+		if (d1248 - d1248 != null)
+			return 55;
+
 		return 0;
 	}