slicing strided arrays by unbounded ranges

[cassella]

Summary of Problem

Slicing a strided array by an unstrided unaligned unbounded range fails with an out of bounds access. I think it should work according to the spec.

var D = {1..20 by 4};
var A: [D] int = 1..20;

writeln(A);

writeln(A[..9 by 4 align 1]);
writeln(A[9.. by 4 align 1]);

writeln(D[..9]);

var D2 = D[..9];
writeln(A[D2]);

writeln(A[..9]);
writeln(A[9..]); // Also OOB

1 2 3 4 5
1 2 3
3 4 5
{1..9 by 4}
1 2 3
$CHPL_HOME/modules/internal/ChapelArray.chpl:1215: error: halt reached - array slice out of bounds
note: slice index was ..9 but array bounds are 1..20 by 4

The spec section 21.6.1 Rectangular Array Slicing second paragraph talks about slicing an array by a range directly.

These range-based slices may also be expressed using partially
unbounded or completely unbounded ranges. This is equivalent to
slicing the array’s defining domain by the specified ranges to create
a subdomain as described in §21.6 and then using that subdomain to
slice the array.

So I think A[..9] should be equivalent to D2 = D[..9]; A[D2]. But the former halts due to OOB, and the latter works.

modules/packages/Sort.chpl's quickSort fails due to this when Data is strided:

      quickSort(Data[..loptr-stride], minlen, comparator);  // could use unbounded ranges here
      quickSort(Data[loptr+stride..], minlen, comparator);

Associated Future Test(s):

None yet

Configuration Information

chpl version 1.20.0 pre-release (144b3b7)

CHPL_TARGET_PLATFORM: linux64
CHPL_TARGET_COMPILER: gnu
CHPL_TARGET_ARCH: x86_64
CHPL_TARGET_CPU: native *
CHPL_LOCALE_MODEL: flat
CHPL_COMM: gasnet *
  CHPL_COMM_SUBSTRATE: udp
  CHPL_GASNET_SEGMENT: everything
CHPL_TASKS: qthreads
CHPL_LAUNCHER: amudprun
CHPL_TIMERS: generic
CHPL_UNWIND: none
CHPL_MEM: jemalloc
CHPL_ATOMICS: cstdlib
  CHPL_NETWORK_ATOMICS: none
CHPL_GMP: gmp
CHPL_HWLOC: hwloc
CHPL_REGEXP: re2
CHPL_LLVM: none
CHPL_AUX_FILESYS: none

gcc (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609

[cassella]

OOC, why does that definition apply only to unbounded ranges? Slicing by a bounded range requires the range be a subset of the array's domain, but slicing by an unbounded range (should) compute the intersection and use that. Why not do the latter for bounded ranges too?

[cassella]

I meant to mention that if D is not strided, then A[..9] and A[9..] work, which is why the issue is titled "slicing strided arrays...".

[bradcray]

Thanks for reporting this Paul. I'm working towards some improvements to slicing arrays with ranges (which have performance and, as you point out, correctness issues), and will add this to that queue.

OOC, why does that definition apply only to unbounded ranges? Slicing by a bounded range requires the range be a subset of the array's domain, but slicing by an unbounded range (should) compute the intersection and use that. Why not do the latter for bounded ranges too?

I agree that this is a little inconsistent. The historical rationale here for bounded ranges is that we treat slicing by a bounded range (or domain) as being a promotion of indexing, so "for all indices in the range/domain, access the array." For that reason, we wanted OOB indices to generate an error rather than get silently swept under the rug.

If we did the same for unbounded ranges (or domains, if we supported them), then it would never be legal / possible to slice with an unbounded range (since no array is unbounded). But that seems too useful of a pattern to leave by the wayside.

[cassella]

These range-based slices may also be expressed using partially unbounded or completely unbounded ranges. This is equivalent to slicing the array’s defining domain by the specified ranges to create a subdomain as described in §21.6 and then using that subdomain to slice the array.

I think the code in ChapelArray/ChapelRange that implements this only really considers the boundedness of the range in this equivalence, not the range's stride wrt the sliced array's domain's stride.

ChapelArray:

    // array slicing by a tuple of ranges
    proc this(ranges...rank) where chpl__isTupleOfRanges(ranges) {
      if boundsChecking then
        checkSlice((... ranges), value=_value);

ChapelArray:

    proc checkSlice(ranges...rank, value) where chpl__isTupleOfRanges(ranges) {
      writeln("\n");
      if this.isRectangular() {
        var ok = true;
        for param i in 0..rank-1 {
          ok &&= value.dom.dsiDim(i).boundsCheck(ranges(i));
      writeln("Bounds check (",ranges(i),") : ", ok);
        }
        if ok == false {
          if rank == 1 {
            halt("array slice out of bounds\n",
                 "note: slice index was ", ranges(0),
                 " but array bounds are ", value.dom.dsiDim(0));

ChapelRange:

inline proc range.boundsCheck(other: range(?e,?b,?s))
  {
    if this.isAmbiguous() || other.isAmbiguous()
      then return false;

    var boundedOther = new range(
                          idxType, BoundedRangeType.bounded,
                          s || this.stridable,
                          if other.hasLowBound() then other._low else _low,
                          if other.hasHighBound() then other._high else _high,
                          other.stride,
                          chpl__idxToInt(other.alignment),
                          true);

    return (boundedOther.sizeAs(uint) == 0) || contains(boundedOther);

Here, the boundedOther for 9.. is 9..20, and 9..20 by 4 doesn't contain that.

Domains OTOH don't do any obvious bounds cheking on slicing:

ChapelDomain:

    // domain slicing by tuple of ranges
    pragma "no doc"
    proc this(ranges...rank)
    where chpl__isTupleOfRanges(ranges) {
      param stridable = _value.stridable || chpl__anyStridable(ranges);
      var r: rank*range(_value.idxType,
                        BoundedRangeType.bounded,
                        stridable);

      for param i in 0..rank-1 {
        r(i) = _value.dsiDim(i)(ranges(i));
    writeln("domain slice: ", r(i));
      }
      return new _domain(dist, rank, _value.idxType, stridable, r);
    }

I'm assuming the Range checkSlice() -> boundsCheck() need to have the semantics they have for other callers. So I think in order to implement the spec as written, the array.this(range) needs to handle the bounds checking it does in some other way.

OTOH, Maybe the current behavior is the better behavior, and the spec should be updated? That is, if the intent of allowing slicing by an unbounded range is really only about the unboundedness, maybe it should be an error to slice by an unbounded range whose stride/alignment includes indices within the bounds that the sliced array's domain doesn't include?

[bradcray]

@cassella — @vasslitvinov and I went around and around on slicing semantics over the past year or two, and I think that the OOB error here is what we want / I'd expect, making me think the spec text that you pointed out should be updated. Vass, do you agree?

As rationale, I view A[..9] to be equivalent to A[A.low..9] or A[1..9] which looks to be trying to read all indices from 1 through 9; but they don't all exist. If we think of slicing as being like promoted indexing, this would be like [i in 1..9] ...A[i]... which would give OOB errors. We could make an exception for unbounded ranges as the spec text suggests (and maybe we used to?), but I don't find it intuitive, personally. Similarly A[..10] seems problematic in that it seems to explicitly refer to an index that is not in the array's domain, but if we took the "intersect the domain first" approach, it would be legal (while A[1..10] would not be). So I think the code is correct here and the spec outdated.