[RFC] Array Slice Access

Tucker Taft Thu, Jan 12, 2023 at 7:58 PM

One alternative approach would be to improve the support for user-defined indexing, which I would suggest be based on the notion of an "aliased return" object, and then you can create an efficient private type representation for a slice using user-defined indexing. If you don't make the components aliased, then you will almost certainly need to do something nearly equivalent to this. Note that the current user-defined indexing mechanism is pretty heavy, involving finalization if you want read-write access to the components, or return-by-copy if you can settle for read-only access. The aliased return object notion could eliminate both of these problems. On the other hand, if you are willing to make the array components aliased, then you can use uncheckedconversion to an access-to-constrained-array from the 'Access of the initial component of the slice and get pretty close to what you need. You might want to bundle this unchecked conversion into a generic that is recognizable by SPARK. Take care,

Stephen Baird Fri, Jan 13, 2023 at 2:06 AM

I think Tuck makes a good point about considering other approaches including support for aliased return objects (see Tuck's proposal https://github.com/Ada-Rapporteur-Group/User-Community-Input/issues/32 ). As a very minor point, it might also be useful to define a Pass_By_Reference Boolean aspect which could be specified for a type (perhaps not for an elementary type) in order to specify that the type is a by-reference type; this could ensure (among other things) that slice parameters are always passed by reference. In practice such slices are already passed by reference, so this might be nice for portability but it probably wouldn't make a big difference. For the rest of this reply, I'll ignore the bigger question of whether some other major approach should be considered and I'll look at the proposal described in the RFC. That does not mean the bigger question should be ignored. I also think it would be premature to attempt RM-appropriate wording at this point - let's first agree on what ideas we want to express. To implement access-to-slice, I think we will need to use a fat-pointer representation, presumably similar (at least at the implementation level) to the idea discussed on VC19-026. It's not clear how much we want this to be user-visible as opposed to under-the-covers. I could imagine, for example, specifying some new Boolean-valued aspect for either the (named) access type or the designated array type to enable this new capability. Suppose we simply say that the example given in the RFC works without any new aspects or anything like that being specified for either the designated type or the access type. That would, IIUC, require conservatively using a fat representation for general access types where the designated type is not known (certainly if the designated type comes from a limited view then it is "not known"; the situation is less clear in the case of a Taft-amendment type; in the case of an incomplete type that is completed later in the same compilation unit, peeking ahead is probably possible). And we would need to be careful about compatibility issues with anonymous access types in profiles of both access-to-subprogram types and dispatching subprograms for any form of indirect call, the caller and the executed callee always need to agree on fat/thin questions). And there would be problems with System.Address_To_Access_Conversions. And the other issues discussed on VC19-026 (e.g., with type conversions in general and, more specifically, with interactions between type conversions and Unchecked_Deallocation).Things would be simpler if we enabled this feature via a Boolean-valued aspect specified on the access type (I would prefer to not continue GNAT's practice of using a Size specification to indicate Thin-vs.-Fat. In the VC19-026 proposal, the size of a fat pointer depends on the designated type and we don't want users to have to be aware of those details). This means that only named access types would be capable of designating slices. One could imagine instead specifying the aspect on the designated type (rather than on the access type), but that brings anonymous access types into the picture. If we decide that we really want "fat" anonymous access types, then specifying the aspect on the designated type is one way to go; I don't think we should do that. So suppose we define a new Boolean-valued aspect that can be specified for a non-derived general access type T whose designated subtype is an unconstrained array subtype. This aspect indicates that

1) In the context of a T-valued (or descendant-of-T-valued) Access/Unchecked_Access attribute reference prefix, a slice of an aliased array is considered to be aliased. 2) Various compile-time restrictions on type conversions and similar things are enforced. For generic bodies and formal access types, we can either be conservative (i.e., assume the worst and perform the checks in the generic body) or more precise (i.e., assume the best in the generic and recheck instance bodies). TBD. 3) The representation (in particular the size) for T may be affected. Does this sound like the right general approach? -- Steve

Tucker Taft Fri, Jan 13, 2023 at 2:45 AM

I would certainly agree the aspect should be on the (named) access type, at least as an initial approach. If you want to designate arbitrary array types, then presumably the access value points at the start of the array, with both an actual low bound and a range of indices that are defined for the slice. -Tuck

Stephen Baird Fri, Jan 13, 2023 at 9:59 PM

Tuck wrote:

If you want to designate arbitrary array types, then presumably the access value points at the start of the array, with both an actual low bound and a range of indices that are defined for the slice. That would work (storing 3 index values for each dimension) and would have the benefit that it could support packed arrays (e.g., references to slices of packed bit vectors). This approach (storing 3 values instead of 2) is not what we have been discussing on VC19-026. Instead, we have been focusing on storing only two values - the slice bounds - and a pointer to the first element of the slice. This approach only works if components of the array are byte-aligned. Alternatives include: 1) Use the three-index implementation unconditionally. 2) Use the two-index implementation unconditionally and impose an additional compile-time restriction that the new aspect shall not be specified for an array type whose components are not aliased (that seems tidier than requiring that components must be byte-aligned, but that's also an option). 3) Get fancy and use the two-index implementation when it is known to work (details TBD) and the three-index implementation in other cases. I suggest #2, with the idea that we could relax the restriction and transition to #3 later if that seems appropriate. Opinions? -- Steve

Stephen Baird Fri, Jan 13, 2023 at 10:12 PM

I wrote: "storing 3 index values for each dimension" Just to clarify, I understand that slicing is only defined for one-dimensional array types. There has been discussion of the multidimensional case on VC19-026 in the context of using fat pointers to refer to things other than slices. -- Steve

Tucker Taft Mon, Jan 16, 2023 at 12:26 AM

My favorite would be to use the 3-index-value approach always, as it seems simplest and most flexible. I don't see this as a significant performance issue. These slice pointers are not going to be that common, and once you have a fat pointer, whether it includes two indices or three indices seems extremely minor and not worth optimizing. -Tuck

Fabien Chouteau Thu, Jan 19, 2023 at 1:56 PM

On Thu, Jan 12, 2023 at 7:59 PM Tucker Taft taft@adacore.com wrote:

One alternative approach would be to improve the support for user-defined indexing, which I would suggest be based on the notion of an "aliased return" object, and then you can create an efficient private type representation for a slice using user-defined indexing. If you don't make the components aliased, then you will almost certainly need to do something nearly equivalent to this. Note that the current user-defined indexing mechanism is pretty heavy, involving finalization if you want read-write access to the components, or return-by- copy if you can settle for read-only access. The aliased return object notion could eliminate both of these problems.

Sounds like a lot of work, and I am not sure "hiding" the access in private type is always a good thing. I think my problem with workarounds, and why I want this feature in the first place, is that in my option getting an access to the full array or just a slice should be exactly the same.

Tucker Taft Thu, Jan 19, 2023 at 3:15 PM

Sounds like a lot of work, and I am not sure "hiding" the access in private type is always a good thing.I think my problem with workarounds, and why I want this feature in the first place, is that in my option getting an access to the full array or just a slice should be exactly the same.

Fair enough. As I indicated in another response, I would then recommend using a "three-index" fat pointer in all cases for access types that permit pointing at slices (which should be indicated with an appropriate aspect specification on the declaration of the access type).

Take care, -Tuck

Fabien Chouteau Fri, Jan 20, 2023 at 2:24 PM On Thu, Jan 19, 2023 at 3:15 PM Tucker Taft taft@adacore.com wrote:

Fair enough. As I indicated in another response, I would then recommend using a "three-index" fat pointer in all cases for access types that permit pointing at slices (which should be indicated with an appropriate aspect specification on the declaration of the access type).

Does it have to be enabled by an aspect?

Tucker Taft Fri, Jan 20, 2023 at 2:30 PM

Yes, you would need to enable it with an aspect on the access-to-array type. It could cause major upheaval, with significant binary incompatibilities, to expect that every access-to-array type, including non-fat-pointer access types, would be able to point at a slice. Take care, -Tuck

Stephen Baird Fri, Jan 20, 2023 at 6:23 PM

On Fri, Jan 20, 2023 at 5:30 AM Tucker Taft taft@adacore.com wrote:

It could cause major upheaval, with significant binary incompatibilities, to expect that every access-to-array type, including non-fat-pointer access types,would be able to point at a slice.

Agreed. One part of this upheaval would be the compile-time rejection of previously-legal representation specifications which rely on assumptions about the size of an access type component. -- Steve

Raphael Amiard Mon, Jan 23, 2023 at 11:00 AM

WRT. Tucker's point, I think extending user defined indexing is a great idea personally, but to be frank I'm not sure I understand how it would help to allow array slices accesses on arrays, which are built-in types. You could make a wrapper type but I think it's a bit overkill. We already have an RFC, that was written a very long time ago by Manu Briot, on extending user defined indexing to slices, here: https://github.com/AdaCore/ada-spark-rfcs/pull/9

Tucker Taft Mon, Jan 23, 2023 at 6:53 PM

What I was suggesting is that you could define your own "pointer-to-slice" type which would support indexing, just like any other access-to-array type. I was not proposing a wrapper for the array, I was proposing a user-defined access-to-slice type. This was trying to be supportive of the idea of rather than extending the language and fiddling with the compiler for this special case, we improve the general capabilities of user-defined indexing so that a user can create their own access-to-slice type using these new building blocks. In any case, I have accepted the desire to have something special here, where by just adding an appropriate aspect on an access-to-array type we could allow it to point to slices. Given that, I was recommending an implementation model that is straightforward and fully general (three-index-model).

We already have an RFC, that was written a very long time ago by Manu Briot, on extending user defined indexing to slices, here: https://github.com/AdaCore/ada-spark-rfcs/pull/9

I was going the other direction, of extending user-defined indexing to a user-defined pointer-to-slice type. Take care, -Tuck

AdaCore / ada-spark-rfcs

[RFC] Array Slice Access #102