chore: implement generalized symmetric difference for set comparison

Emyrk · Emyrk · commit c184fe1f67d3 · 2024-08-22T17:06:24.000-05:00
Going to be used in Organization Sync + maybe group sync. Felt
better to reuse, rather than copy
diff --git a/coderd/rbac/roles.go b/coderd/rbac/roles.go
@@ -764,29 +764,9 @@ func SiteRoles() []Role {
 // RBAC checks can be applied using "ActionCreate" and "ActionDelete" for
 // "added" and "removed" roles respectively.
 func ChangeRoleSet(from []RoleIdentifier, to []RoleIdentifier) (added []RoleIdentifier, removed []RoleIdentifier) {
-	has := make(map[RoleIdentifier]struct{})
-	for _, exists := range from {
-		has[exists] = struct{}{}
-	}
-
-	for _, roleName := range to {
-		// If the user already has the role assigned, we don't need to check the permission
-		// to reassign it. Only run permission checks on the difference in the set of
-		// roles.
-		if _, ok := has[roleName]; ok {
-			delete(has, roleName)
-			continue
-		}
-
-		added = append(added, roleName)
-	}
-
-	// Remaining roles are the ones removed/deleted.
-	for roleName := range has {
-		removed = append(removed, roleName)
-	}
-
-	return added, removed
+	return slice.SymmetricDifferenceFunc(from, to, func(a, b RoleIdentifier) bool {
+		return a.Name == b.Name && a.OrganizationID == b.OrganizationID
+	})
 }
 
 // Permissions is just a helper function to make building roles that list out resources
diff --git a/coderd/util/slice/slice.go b/coderd/util/slice/slice.go
@@ -107,3 +107,40 @@ func Ascending[T constraints.Ordered](a, b T) int {
 func Descending[T constraints.Ordered](a, b T) int {
 	return -Ascending[T](a, b)
 }
+
+// SymmetricDifference returns the elements that need to be added and removed
+// to get from set 'a' to set 'b'.
+// In classical set theory notation, SymmetricDifference returns
+// all elements of {add} and {remove} together. It is more useful to
+// return them as their own slices.
+// Example:
+//
+//	a := []int{1, 3, 4}
+//	b := []int{1, 2}
+//	add, remove := SymmetricDifference(a, b)
+//	fmt.Println(add)    // [2]
+//	fmt.Println(remove) // [3, 4]
+func SymmetricDifference[T comparable](a, b []T) (add []T, remove []T) {
+	return Difference(b, a), Difference(a, b)
+}
+
+// Difference returns the elements in 'a' that are not in 'b'.
+func Difference[T comparable](a []T, b []T) []T {
+	return DifferenceFunc(a, b, func(a, b T) bool {
+		return a == b
+	})
+}
+
+func SymmetricDifferenceFunc[T any](a, b []T, equal func(a, b T) bool) (add []T, remove []T) {
+	return DifferenceFunc(a, b, equal), DifferenceFunc(b, a, equal)
+}
+
+func DifferenceFunc[T any](a []T, b []T, equal func(a, b T) bool) []T {
+	tmp := make([]T, 0, len(a))
+	for _, v := range a {
+		if !ContainsCompare(b, v, equal) {
+			tmp = append(tmp, v)
+		}
+	}
+	return tmp
+}
diff --git a/coderd/util/slice/slice_test.go b/coderd/util/slice/slice_test.go
@@ -131,3 +131,49 @@ func TestOmit(t *testing.T) {
 		slice.Omit([]string{"a", "b", "c", "d", "e", "f"}, "c", "d", "e"),
 	)
 }
+
+func TestSymmetricDifference(t *testing.T) {
+	t.Parallel()
+
+	t.Run("Simple", func(t *testing.T) {
+		add, remove := slice.SymmetricDifference([]int{1, 3, 4}, []int{1, 2})
+		require.ElementsMatch(t, []int{2}, add)
+		require.ElementsMatch(t, []int{3, 4}, remove)
+	})
+
+	t.Run("Large", func(t *testing.T) {
+		add, remove := slice.SymmetricDifference(
+			[]int{1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15},
+			[]int{1, 3, 7, 9, 11, 13, 17},
+		)
+		require.ElementsMatch(t, []int{7, 9, 17}, add)
+		require.ElementsMatch(t, []int{2, 4, 5, 10, 12, 14, 15}, remove)
+	})
+
+	t.Run("AddOnly", func(t *testing.T) {
+		add, remove := slice.SymmetricDifference(
+			[]int{1, 2},
+			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9},
+		)
+		require.ElementsMatch(t, []int{3, 4, 5, 6, 7, 8, 9}, add)
+		require.ElementsMatch(t, []int{}, remove)
+	})
+
+	t.Run("RemoveOnly", func(t *testing.T) {
+		add, remove := slice.SymmetricDifference(
+			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9},
+			[]int{1, 2},
+		)
+		require.ElementsMatch(t, []int{}, add)
+		require.ElementsMatch(t, []int{3, 4, 5, 6, 7, 8, 9}, remove)
+	})
+
+	t.Run("Equal", func(t *testing.T) {
+		add, remove := slice.SymmetricDifference(
+			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9},
+			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9},
+		)
+		require.ElementsMatch(t, []int{}, add)
+		require.ElementsMatch(t, []int{}, remove)
+	})
+}
