Corefxlab: Span<T> - find if one span contains another; perhaps IsSliceOf

[mgravell]

A scenario I find myself needing is to see whether one span is a sub-span of another. This test is semantically valid for both array and pointer spans, and is a related operation to Slice

Suggested API:

Span<T>
    bool IsSliceOf(Span<T> span);
    bool IsSliceOf(Span<T> span, out int offset);

where it is:

• true if both spans are array-based, for the exact same array, where the inner offet >= outer offset, and inner offset+count <= outer offset+count
• true if both spans are pointer-based, and inner ptr >= outer ptr and inner ptr+count <= outer ptr+count
• false otherwise

or could be unified to:

    int GetSliceIndex(Span<T> span)

(returns -1 if not a slice; kinda ugly)

Would be happy to contribute towards the code, but wanted to discuss API first.

[omariom]

What if the first Span is array based but the second one is pointer based created from the same pinned array?
Is it currently possible to handle such case without pinning the array based Span?

[juliusfriedman]

Can't we 0 1 this N open with GetHashCode and the block already computed?

On Sep 20, 2016 08:01, "OmariO" [email protected] wrote:

What if the first Span is array based but the second one is pointer based
created from the same _pinned_ array?
Is it currently possible to handle such case without pinning the array
based Span?

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/dotnet/corefxlab/issues/827#issuecomment-248281266,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AHfOYg3wBzhiDRG-I_tRR9AOgg7EAExhks5qr8szgaJpZM4KBfUO
.

[mgravell]

that would be the false case, IMO; it could not have been created as a result of Slice

[KrzysztofCwalina]

Can we get the same semantics for this span (three field) and the byref filed span in coreclr repo?

cc @jkotas

[jkotas]

What if the first Span is array based but the second one is pointer based created from the same pinned array?

IsSliceOf should detect the overlap in this case as well.

Is it currently possible to handle such case without pinning the array based Span?

You either need to pin, or have more unsafe helpers that operate with byrefs.

Can we get the same semantics for this span (three field) and the byref filed span in coreclr repo?

I think so.

[mgravell]

@jkotas it _feels_ like it would be reasonable to _not_ detect it, though; I guess what we're asking is:

given Span<T> foo and bar, is there an i for which we could have called foo = bar.Slice(i, {foo.Length}); (and optionally, tell me the i)

To my mind, _that_ is what IsSlice means. However, if foo and bar are of different fundamental types, the answer to that question is simply: "no".

As a corollary, I would expect that if I called:

if(foo.IsSlice(bar, out i)) {
    var proveIt = bar.Slice(i, foo.Length);
    Assert.True(proveIt == foo);
}

And _that_ will fail at the moment, because Equals compares Object, Offset and Length

[jkotas]

To me, Span is a safe pointer to a block of memory. The internal representation of the block of memory (pinned vs. not-pinned) should not leak into behavior. If the internal representation leaks into behavior:

• It makes it hard to reliably write algorithms like "if (spans do not overlap) { do something cheap; } else {do something more expensive with extra copy }"
• It is not possible to maintain the same semantics with the more efficient Span built into runtime

[mgravell]

Everything I have spoken of relates to the existing public Slice API. Nothing to do with internal representation. If what I have said leaks implementation, then it leaks it in exactly the same way that == etc already do. It is consistent in its leakiness :)

[mgravell]

Suggest that moves to Memory<T> (#844) which doesn't have the same restrictions / pain points.

[KrzysztofCwalina]

We just need to be careful that we don't add APIs to Memory that will make it just like Span in terms of safety issues, which in turn would force us to make it stack-only, and the cycle would complete.

i.e. I think Memory should be just a "promise of a span" with pinning support.

[mgravell]

@KrzysztofCwalina I understand the concern, but I do not see that it applies in this case. Now, a separate and worthwhile discussion is "should this API exist". All I can say there is: I know I would find it genuinely useful, from real-world usage in Channels. Memory<T> has the same Memory<T> Slice(...) aspect that Span<T> has, but does not have the concerns that made IsSliceOf awkward on Span<T>.

[jkotas]

made IsSliceOf awkward on Span<T>

IsSliceOf is a good fit for Span<T>. I do think that it is awkward. The implementation may be more complex/expensive than one would wish in the corefxlab implementation of Span<T> - but it is the case to some degree for the corefxlab implementation as a whole.

[mgravell]

@jkotas you yourself said "The internal representation of the block of memory (pinned vs. not-pinned) should not leak into behavior. " - however, the reality is that both Equals (existing) and IsSliceOf (proposed) _do_ leak into the behavior. Which is, I agree, a problem. This problem would not apply to Memory<T>, is my point.

[KrzysztofCwalina]

I think it would be worth exploring making Memory the ugly type that is sometimes unsafe and leaky, and then make Span the beautiful type that is always safe and a perfect abstraction.

Otherwise we might end up with two ugly types with slightly different (but hard to understand) semantics/guarantees.

[ahsonkhan]

A scenario I find myself needing is to see whether one span is a sub-span of another.

@mgravell, can you provide more details about the scenario where this API is useful/necessary (possibly with sample usage code within your scenario)?

[mgravell]

@ahsonkhan the specific example was trying to find the parent block that owns a range (one of several known blocks) so we can do a slice and dice - however, it occurs that the moment I say "one of several" it is clear that we aren't talking just about stack-based spans, so all of this could work just as well against Buffer-T if that would be preferable. The exact scenario was: https://github.com/davidfowl/Channels/pull/86/files#diff-2265f88526c85122b370d0d37969d072R620 (search IsSliceOf).

[ahsonkhan]

Moved to https://github.com/dotnet/corefx/issues/18750 since Span predominantly lives in System.Memory.