如何检查两个 Span<T> 是否相交？

Question

考虑以下函数：

public static bool TryToDoStuff(ReadOnlySpan<byte> input, Span<byte> destination) {
    ...
}

此函数返回基于input的内容，是否能够在destination上“执行操作”。

我想检查input和destination“包含”的内存区域是否相交，如果相交，则抛出异常，因为这会破坏input的数据。我该如何做到这一点（不使用反射或不安全的代码）？

我知道我可以编写一些xmldoc并警告用户参数不应相交，但这是一个贫民解决方案。

编辑：对于那些要求示例的人，Wazner的示例是正确的。

// On arrays
Span<byte> firstArray = new byte[10];
Span<byte> secondArray = new byte[10];
Intersects<byte>(firstArray.Slice(5, 5), firstArray.Slice(3, 5)); // Should throw
Intersects<byte>(firstArray.Slice(5, 5), secondArray.Slice(3, 5)); // Should not throw

// And on stackallocated memory
Span<byte> firstStack = stackalloc byte[10];
Span<byte> secondStack = stackalloc byte[10];
Intersects<byte>(firstStack.Slice(5, 5), firstStack.Slice(3, 5)); // Should throw
Intersects<byte>(firstStack.Slice(5, 5), secondStack.Slice(3, 5)); // Should not throw

- Trauer

---

Span<T> 实现了方法 int32 IndexOfAny(ReadOnlySpan<T> values)。你尝试过像这样的代码吗？if (destination.IndexOfAny(input) >= 0) throw new IntersectException(); - Michal Šuvada

@MichalŠuvada：那将是比较值，而不是内存位置，这是我认为OP感兴趣的。 - Jon Skeet

@DaisyShipton - 哎呀，不对。上面有点小失误。更长的跨度可以完全包含更短的跨度，因此您必须迭代更长的跨度以及更短的跨度的起始/结束位置。 - Damien_The_Unbeliever

@Damien_The_Unbeliever：没错。所以如果跨度可以合理地长，那么这是“可行但不实际的”:( - Jon Skeet

@HansPassant - 你如何获得两个不同但指向同一块内存的 byte[] 数组，而不进行严重不安全的操作？ - Damien_The_Unbeliever

Answer 1

可以使用 System.Runtime.CompilerServices.Unsafe NuGet 包中的一种方法实现。它提供了像 ByteOffset 和 SizeOf 这样的低级方法。

使用这些方法，您可以编写以下方法:

public static bool Intersects<T>(ReadOnlySpan<T> a, ReadOnlySpan<T> b) 
{
    var elementSize = Unsafe.SizeOf<T>();
    var distance = (long)Unsafe.ByteOffset<T>(ref MemoryMarshal.GetReference(a), ref MemoryMarshal.GetReference(b));
    if (distance < 0) 
    {
        return -distance < b.Length * elementSize;
    }
    else if (distance > 0) 
    {
        return distance < a.Length * elementSize;
    }
    return true;
}

该方法确定每个span中第一个元素之间的字节数距离。然后确定此距离是否小于span中项数乘以单个元素在span中的大小（以字节为单位）。

通过使用Unsafe.SizeOf<T>，即使对于非基元类型，也可以使用此方法。引用类型如字符串和类别的大小为本机整数(IntPtr.Size)。

以下是一些测试用例，说明此方法有效：

// On arrays
Span<byte> firstArray = new byte[10];
Span<byte> secondArray = new byte[10];
Intersects<byte>(firstArray.Slice(5, 5), firstArray.Slice(3, 5)); // true
Intersects<byte>(firstArray.Slice(5, 5), secondArray.Slice(3, 5)); // false

// And on stackallocated memory
Span<byte> firstStack = stackalloc byte[10];
Span<byte> secondStack = stackalloc byte[10];
Intersects<byte>(firstStack.Slice(5, 5), firstStack.Slice(3, 5)); // true
Intersects<byte>(firstStack.Slice(5, 5), secondStack.Slice(3, 5)); // false

注意：使用System.Runtime.CompilerServices.Unsafe包需要使用ref-returns，这是C# 7才有的特性。

- Wazner

---

这确实解决了我的问题，因为我正在处理字节。但出于好奇，Unsafe.SizeOf<T>() 对任何 T 都能正确地工作吗？ - Trauer

@Trauer 我不能确定对于任何 T 都适用，但我已经测试过自定义结构体、字符串、类类型和大多数基本类型的 Spans。我已经修改了答案以反映这一点。 - Wazner

Answer 2

我在dotnet/corefx存储库上创建了一个问题，其中一位贡献者发布了这个链接：https://learn.microsoft.com/en-us/dotnet/api/system.memoryextensions.overlaps?view=netcore-2.1。所以，是的，有一种优雅、简洁、安全且符合框架的解决方案来解决这个问题。

- Trauer

Answer 3

“不使用反射或不安全的代码”是不可能的，因为Span<T>的_pointer属性没有以任何方式公开暴露出来。

https://github.com/dotnet/corefx/blob/ab27e64721496ab7404fd52d8d7720db572fc2f4/src/Common/src/CoreLib/System/Span.Fast.cs#L30

- We Are All Monica

---

根据问题中的评论，看起来这是“可能的”——但不一定是“实际可行的”。 - Jon Skeet