ReadOnlySequence<T>.GetPosition(<size>) behaviour

[thargy]

Current Behaviour

The current behaviour of ReadOnlySequence<T>.GetPosition() is demonstrated in the following code:

ReadOnlySequence<byte> sequence = new ReadOnlySequence<byte>(new byte[size]);
object firstObject = sequence.Start.GetObject();

// End returns a sequence with index int.MinValue, and object is set to last segment
Console.WriteLine(ReferenceEquals(sequence.End.GetObject(), firstObject).ToString()); // True
Console.WriteLine(sequence.End.GetInteger().ToString()); // -2147483647

// GetPosition(0) returns a sequence with index 0, and object is set to first segment
SequencePosition zeroPosition = sequence.GetPosition(0); // True
Console.WriteLine(ReferenceEquals(zeroPosition.GetObject(), firstObject).ToString()); // 0
Console.WriteLine(zeroPosition.GetInteger().ToString()); // True

// GetPosition(0) returns a sequence that equals sequence.Start
Console.WriteLine(zeroPosition.Equals(sequence.Start).ToString()); // True

// GetPosition(size) returns a sequence with last object and index = size ?
SequencePosition sizePosition = sequence.GetPosition(size);
Console.WriteLine(ReferenceEquals(sizePosition.GetObject(), firstObject).ToString()); // True
Console.WriteLine(sizePosition.GetInteger().ToString()); // size

// GetPosition(size) does not match sequence.End
Console.WriteLine(sizePosition.Equals(sequence.End).ToString()); // False

// Asking for size + 1 correctly detects OOB, throwing ArgumentOutOfRangeException
Sequence sizePlusOnePosition = sequence.GetPosition(size + 1);

Summary

The following behaviour is intuitive:

• ReadOnlySequence<T>.End appears to point after the end of the sequence (index = index.MaxValue, object is last segment).
• ReadOnlySequence<T>.Start points to first segment, index 0
• ReadOnlySequence<T>.GetPosition(0) is identical to Sequence.Start
• ReadOnlySequence<T>.GetPosition(-1) throws an ArgumentOutOfRangeException
• ReadOnlySequence<T>.GetPosition(<size> + 1) throws an ArgumentOutOfRangeException

However, ReadOnlySequence<T>.GetPosition(<size>) does not appear intuitive to me, unless I'm missing something? Although SequencePosition.GetObject() returns the last segment, SequencePosition.GetIndex() seems to indicate an index beyond the sequence and does not match ReadOnlySequence<T>.End. In the absence of any other indicator there is no obvious way to see this SequencePosition is outside the bounds of the sequence. In constrast, asking for -1 and size+1 throw exceptions indicating that the parameter is bounded.

Expected Behaviour

I would expect one of the following to occur (in order of preference):

1. ReadOnlySequence<T>.GetPosition(<size>) throws an ArgumentOutOfRangeException as it is beyond the bounds of the sequence - this makes it act more like an array accessor and is more like the rest of the framework. [Preferred]
2. ReadOnlySequence<T>.GetPosition(<size>) returns a SequencePosition equal to ReadOnlySequence<T>.End, indicating it's immediately beyond the end of the sequence.
3. ReadOnlySequence<T>.GetPosition(<size>) returns default(SequencePosition), to indicate out of bounds of the array - this is non-intuitive as it implies -1 and size + 1 should also return this value.

On a related note, it would be nice if ReadOnlySequence<T>.GetPosition(offset, origin) supported negative offsets. I understand this may have an impact on pipes, but on many sequences it would be an entirely valid concept.

[thargy]

It is worth noting, that I think this can cause a related issue in ReadOnlySequence<T>.TryGet(). If passed a position retrieved via ReadOnlySequence<T>.GetPosition(<size>), ReadOnlySequence<T>.TryGet() will return true, but output.Length will be 0.

[benaadams]

As I understand it the SequencePosition sub properties are implementation dependent and shouldn't be directly used https://github.com/dotnet/corefx/issues/29001

/cc @pakrym

[thargy]

I’ve read though that issue. I can’t see any justification for GetPostion(length) not throwing an AOORException when GetPosition(length+1) and GetPosition(-1) do already. Also the idea that you can have a SequencePosition returned from APIs that doesn’t point into the sequence (and isn’t default or an EOS indicator of some form) and appears ‘valid’ is a recipe for endless bugs.

That GetObiect() and GetIndex() are exposed at all seems a poor design choice. As it is, there’s no cheap way to detect if a sequence position is actually contained within a sequence.

[benaadams]

SequencePosition needs the methods public so it can be used by other data types other than ReadOnlySequence<T>; otherwise I assume they would have been internal.

GetIndex() should have probably be called GetToken() though :-/

[thargy]

In which case, as puclic they form part of the Standard. Therefore they have to actually mean something consistently otherwise the other code could not rely on them.

In reality, they are used throughout ROS to determine which sequence segment the position relates to. So there’s at least an implied contract that if two SPs share the same Object then they are on the same segment; e.g. if SP.GetObject() == ROS.Start.GetObject(), then SP is on the first segment. This understanding is leveraged throughout for performance.

The issue above though is more easily reduced to, why does GetPosition(length) not throw an exception? Not sure I’m seeing a defence yet.

[pakrym]

@benaadams is right, SP is only intended to be retrieved from and passed into ROS.

Its properties should not be observed and they should not be compared directly because we give no guarantees about the content of object and index. ROS relies on values only because it both produces and consumes them keeping implementation details of what SP stores inside ROS itself.

// End returns a sequence with index int.MinValue, and object is set to last segment
Console.WriteLine(ReferenceEquals(sequence.End.GetObject(), firstObject).ToString()); // True
Console.WriteLine(sequence.End.GetInteger().ToString()); // -2147483647

It's not int.MinValue it's size | (1 << 31).

It's too late to change what GetPosition(size) does and the only guarantee that ROS gives is that it would produce equivalent results when passed in as ros.End would.

[thargy]

@benaadams is right, SP is only intended to be retrieved from and passed into ROS.

Thanks for the information, where is that documented? Also if that is the only intent then there is no reason for those properties to be public and, at most, they should be protected internal. As you say -

ROS relies on values only because it both produces and consumes them keeping implementation details of what SP stores inside ROS itself.

You then go to correct a throwaway comment in my code sample about a properties value that, apparently, I shouldn't use.

It's not int.MinValue it's size | (1 << 31).

I'm so sorry, you're absolutely right, and I apologise for my mistake in that comment. It's clearly not int.MinValue when it's actually int.MinValue+1. Of course, it's irrelevant, because I shouldn't be using the actual index value (in reality I haven't, I just put it there for info).

It's too late to change what GetPosition(size) does

It seems you are more than willing to dispute that dismissal when it suits, so let me remind you of your own comment when faced with such a non-response yourself.

does and the only guarantee that ROS gives is that it would produce equivalent results when passed in as ros.End would.

Yup, and where's that particularly 'gaurantee' documented too - it being too late to change it?

I have to be honest, I put a lot of effort into writing a respectful and carefully asked query to raise a legitimate concern about what appears to someone using the interface as an area that is confused and difficult to understand, leads to bugs in real world scenarios, and exposes an area of missing functionality. Your response hasn't actually addressed my query in any way accept to state:

• You shouldn't use those public properties, there an implementation detail (so why are they public)?
• Here's some gaurantees that you can rely on, but they're not obvious (wait I thought you said I shouldn't use them)?
• It's too late to change...

It doesn't justify why the design decision was made. It makes no effort to address or mitigate my concerns and is incredibly dismissive. It makes me question whether you are actually interested in the views of your users.

Please can you actually respond and explain to me how you feel the current behaviour makes sense to end-users? Do you have any plans to make it possible for a consumer to actually be able to tell if a position lies within the sequence - currently the best way is to check to see if position+1 throw an OORException, or do you have a way that I should be using instead?

Gratefully Yours

[pakrym]

Thanks for the information, where is that documented?

https://github.com/dotnet/corefx/blob/master/src/System.Memory/src/System/SequencePosition.cs#L12

It seems you are more than willing to dispute that dismissal when it suits, so let me remind you of your own comment when faced with such a non-response yourself.

That was before System.IO.Pipelines shipped. It would be a breaking change to start throwing now.

Also if that is the only intent then there is no reason for those properties to be public and, at most, they should be protected internal.
You shouldn't use those public properties, there an implementation detail (so why are they public)?

SequencePosition is not tied to ROS. There were plans for adding other types that would use SP (https://github.com/dotnet/corefxlab/blob/master/src/System.Buffers.Primitives/System/Collections/ISequence.cs#L8) and store different information in it.

Here's some gaurantees that you can rely on, but they're not obvious (wait I thought you said I shouldn't use them)?

There are no guarantees about interpreting SP at all. We only support documented behaviours of ROS.

Do you have any plans to make it possible for a consumer to actually be able to tell if a position lies within the sequence - currently the best way is to check to see if position+1 throw an OORException, or do you have a way that I should be using instead?

We didn't find a use case for such a check before but it not hard to implement it as part of ROS. Can you share your use case?

Current state of things is combination of perfomance related reasons

• SequencePosition has to be a struct and can't have a back reference to ROS
• ROS has to store internal flags inside SP to reduce struct size
• Requirement to normalize sequence positions to be able to compare them

and intent to reuse SP in other types (not allowing us to guarantee anything about isolated SP).
If you have ideas about how to make SequencePositions correctly comparable without losing performance I'm glad to implement it.

While I agree that situation is not ideal, ROS is advanced use primitive and it was decided that a bit of learning curve is acceptable considering the performance gain and ability to tweak things in the future.

[thargy]

SequencePosition is not tied to ROS. There were plans for adding other types that would use SP...

Using that ROS (or something else) via that interface would have performance implications in breach of your justification for the design - you can't have it both ways. Either it's supposed to be so performant that you need it to be a struct which holds those properties or you're happy accessing via the interface. A more obvious challenge is, if you're happy to pay the cost of using interfaces then have the interface expose and ISequencePosition rather than the raw struct. After all, no framework code can make any assumptions, or use of the GetIndex() and GetObject() methods as they are reserved for the implementation - over which you'd have no gaurantees -

There are no guarantees about interpreting SP at all. We only support documented behaviours of ROS.

Put simply, I can't see why you should have the interface or make the methods public considering the end goal. Let other concepts use their own structs, after all a SequencePosition in one ROS has no meaning in another, never mind another class, etc.

We didn't find a use case for such a check before but it not hard to implement it as part of ROS. Can you share your use case?

My first attempt at using them was to chunk them into 32 bytes chunks efficiently. You can see the result in dotnet/corefx#33098 and this gist.

Put simply, a call to ReadOnlySequence<T>.TryGet() with advance set to true, will return the SequencePosition of the start of the next chunk, if one is available. However, there is no way to determine whether that returned position is in the sequence, so you can't tell, in one step, whether the segment returned for a successful call to TryGet is the last segment of not. Nor can you compare the returned value to ReadOnlySequence<T>.End -

ReadOnlySequence<byte> sequence = new ReadOnlySequence<byte>(new byte[5]);
SequencePosition size = sequence.GetPosition(5);
SequencePosition end = sequence.End;
SequencePosition last = sequence.GetPosition(4);
Assert.True(sequence.TryGet(ref last, out ReadOnlyMemory<byte> memory));
this.output.WriteLine($"Size Obj: {size.GetObject()}, Index: {size.GetInteger()}");
this.output.WriteLine($"End  Obj: {end.GetObject()}, Index: {end.GetInteger()}");
this.output.WriteLine($"Last Obj: {last.GetObject()}, Index: {last.GetInteger()}");

// Size Obj: System.Byte[], Index: 5
// End Obj: System.Byte[], Index: -2147483643
// Last Obj: , Index: 0

Currently, I check if GetObject() is null - but that's not allowed. The only other alternative is to repeat the TryGet call on the returned position, which has a substantial performance impact.

I could compare todefault, is that behaviour gauranteed in this scenario or is that implementation dependent? However, that check wouldn't pick up size and end, which are also outside the sequence and, if passed into my method, result in an unecessary TryGet check - which confusingly returns true but the returned segment is empty (again I don't think this is intuitive, desirable, or necessary behaviour).

Having a way to reliably see all 3 of the above positions as outside of the sequence, without requiring a method invocation has many legitimate uses. The cheapest would be if all 3 were actually just default.

• ROS has to store internal flags inside SP to reduce struct size

Yup, agreed, so make them internal.

and intent to reuse SP in other types (not allowing us to guarantee anything about isolated SP).

As above, if you can't gaurantee anything about the SP implementation you can't reliably make use of the GetObject() and GetIndex() methods exposed and so they should be internal. As is your constraining the design in those other unspecified planned types.

If you have ideas about how to make SequencePositions correctly comparable without losing performance I'm glad to implement it.

If you need to implement code that only relies on two structs being equitable, and are wanting to avoid the object allocations, you could make that code accept a positional struct as a generic constraint, e.g. ReadOnlySequence<TItem, TPosition> where TPosition:struct. The existing ROS would descend ReadOnlySequence<TItem> : ReadOnlySequence<TItem, SequencePosition> you could then rely on the struct's override of object.Equals(object obj). Although that does a boxing. At the moment you are using the IEquatable<SequencePosition> interface, so you'd have to run performance checks tos see which was preferrable (and you could add IEquatable<TPosition> as a type constraint, or you could have an ISequencePosition : IEquatable<ISequencePosition> interface and type constraint.

Looking through the code, you seem to use GetObject() to mostly confirm two SequencePositions lie on the same sequence. Having an ISequencePosition interface could delegate that concept properly to the underlying implementation. I haven't written a micro benchmark to assess performance of two calls to GetObject() on the struct compared to one call of ISequencePosition.IsSameSegment(ISequencePosition) or similar with the boxing costs associated. You could also have an ISequencePosition.IsInSequence and optionally an ISequencePosition.IsEOS. But no doubt you already rejected interfaces having ran your own performance tests?

While I agree that situation is not ideal, ROS is advanced use primitive and it was decided that a bit of learning curve is acceptable considering the performance gain and ability to tweak things in the future.

I think the issue with this approach is, at minimum, it required good documentation of the behaviour, and that, to be brutally honest, is absent. For some reason, I'm not even seeing intellisense on the methods in Visual Studio, but even if it were available, looking at the source code would provide the only real insight as the comments are minimal. For example, GetPosition() makes no mention of the behaviour of asking for indexes outside of the sequence, or of the sequence size, nor does it mention exceptions. Similarly, it accepts negative values in the offset and an origin implying you could use GetPosition(-1, sequence.End) to get the true last position - but you can't. In reality, I haven't found a use case for sequence.End as it appears most useful for seeing if you're in the last sequence, by comparing it's GetObject() with you're own, but that turns out to be very costly in performance.

You made a lot of statements about performance, and 'other types using it', but I can't see how you have addressed the original issue as raised, so let me restate it, what is the -

... justification for GetPostion(length) not throwing an AOORException when GetPosition(length+1) and GetPosition(-1) do already?

If there is no justification and this is just code smell, then feel free to go on and bemoan how we're now stuck with it in .Net Core. At least I can hope to justify it not being ready for introduction into Standard before it's too late (dotnet/standard/issues/932).

[thargy]

In summary (for anyone arriving new to the thread), the following issues arise in ROS as it stands and make it a ready source of bugs for consumers:

• ROS.GetPosition behaviour is not intuitive. GetPosition(size) does not throw, yet GetPosition(size+1) and GetPosition(-1) do.
• GetPosition(size) != GetPostion(ROS.End) yet GetPosition(size) and GetPosition(ROS.End) are required to demonstrate the same behaviour when supplied to ROS.
• TryGet(GetPosition(size) and TryGet(GetPosition(End) both return true, even though there is no more elements in the sequence, and so the returned memory is empty (size 0). Why do they not return false?
• SequencePosition.GetObject() and SequencePosition.GetIndex() are public yet shouldn't be used. Despite this ROS relies on them, without any gaurantee about their meaning. It does so to check if two positions lie on the same segment and relies on positions being equatable. Again GetPosition(size) and ROS.End are equivalent but not equitable.
• GetPosition() throws AOOBExceptions, for a performance API, it would be nicer if returned default for any index outside the sequence, at least then it could be safely used to validate a supplied position.
• GetPosition(offset, origin) accepts a signed offset, but does not support negative offset for seeking backwards. As such GetPostion(-1, sequence.End) is invalid and there is no quick way to get to the last item of the sequence, as ROS.End does not point to (being exclusive).
• SequencePointer does not reflect whether it is in the sequence making it impossible to efficiently determine if a given pointer is in a sequence. This has many implications, for example you cannot establish whether the returned pointer from a TryGet() call (with advance set to true and a result of true) lies in the sequence, meaning an extra call is needed to assess whether a returned sequence is the last one.

I believe without convincing arguments for the above, or better changes to make it intuitive and more inline with the rest of the Standard, this shouldn't be part of .Net Standard.

[benaadams]

Current SequencePosition has GetInteger() rather than GetIndex and both GetObject and GetInteger are [EditorBrowsable(EditorBrowsableState.Never)]

In which case, as puclic they form part of the Standard. Therefore they have to actually mean something consistently otherwise the other code could not rely on them.

SequencePosition is a more rich position; but it is like using int for the position on an array. Getting the int position from one array doesn't mean that that int position is valid for another array.

The issue above though is more easily reduced to, why does GetPosition(length) not throw an exception? Not sure I’m seeing a defence yet.

Looking at the output

var size = 10;
ReadOnlySequence<byte> sequence = new ReadOnlySequence<byte>(new byte[size]);
object lastObject = sequence.End.GetObject();
int lastInteger = sequence.End.GetInteger();

var pos = sequence.GetPosition(size);

Console.WriteLine(lastObject == pos.GetObject()); // True
Console.WriteLine(lastInteger == pos.GetInteger()); // False

Console.WriteLine(sequence.Slice(sequence.End).Length); // 0
Console.WriteLine(sequence.Slice(pos).Length); // 0

pos = sequence.GetPosition(size - 1);
Console.WriteLine(sequence.Slice(pos).Length); // 1

pos = sequence.GetPosition(size + 1); // Arg out of range

Both sequence.End and sequence.GetPosition(size) point to after the last element and slicing to them both return a 0 length ROS; whereas slicing at sequence.GetPosition(size - 1) returns a 1 element sequence.

So maybe its more a question of why .End and .GetPosition(size) don't return the same values; although they behave the same in use?

[thargy]

SequencePosition is a more rich position; but it is like using int for the position on an array. Getting the int position from one array doesn't mean that that int position is valid for another array.

I fully understand that, however, the existing Standard API's would return a -1, or throw an exception for anything outside the bounds of the array. They wouldn't return a positive integer for the (size+1)th item. This API does.

So maybe its more a question of why .End and .GetPosition(size) don't return the same values; although they behave the same in use?

I keep saying exactly that, e.g.:

• GetPosition(size) != GetPostion(ROS.End) yet GetPosition(size) and GetPosition(ROS.End) are required to demonstrate the same behaviour when supplied to ROS.

[benaadams]

ROS.End directly returns _sequenceEnd which has a type flags on it; whereas GetPosition doesn't have that (and it starting at the other end which has a different marker); so perhaps ROS.End and ROS.Start should remove their type markers before returning?

[thargy]

No one has yet explained why ROS.End is exclusive anyway, and most of these issues flow from a desire to expose a position after the end of the sequence. Given that it is, for some unexplained reason, required, then making ROS.End == ROS.GetPosition(size) would at least allow that comparison to be used.

Again, I still haven't seen a solid justification for the two Getxxx methods to be public instead of internal

[pakrym]

@benaadams it's only one thing that makes them incomparable, there are others. For example: should end of one segment be equal to the start of next? What if ROS you got this position from doesn't include next segment, etc. etc. To implement correct comparison you need to have knowledge about data structure that created ROS.