Nrthugu

How to check whether two slices are backed up by the same array?

For example:

a := int{1, 2, 3}

b := a[0:1]

c := a[2:3]



alias(b, c) == true

How should alias look like?

In general you can't tell if the backing array is shared between 2 slices, because using a full slice expression, one might control the capacity of the resulting slice, and then there will be no overlap even when checking the capacity.

As an example, if you have a backing array with 10 elements, a slice may be created that only contains the first 2 elements, and its capacity might be 2. And another slice may be create that only holds its last 2 elements, its capacity again being 2.

See this example:

a := [10]int{}



x := a[0:2:2]

y := a[8:10:10]



fmt.Println("len(x) = ", len(x), ", cap(x) = ", cap(x))

fmt.Println("len(y) = ", len(y), ", cap(y) = ", cap(y))

The above will print that both lengths and capcities of x and y are 2. They obviously have the same backing array, but you won't have any means to tell that.

Edit: I've misunderstood the question, and the following describes how to tell if (elements of) 2 slices overlap.

There is no language support for this, but since slices have a contiguous section of some backing array, we can check if the address range of their elements overlap.

Unfortunately pointers are not ordered in the sense that we can't apply the < and > operators on them (there are pointers in Go, but there is no pointer arithmetic). And checking if all the addresses of the elements of the first slice matches any from the second, that's not feasible.

But we can obtain a pointer value (an address) as a type of uintptr using the reflect package, more specifically the Value.Pointer() method (or we could also do that using package unsafe, but reflect is "safer"), and uintptr values are integers, they are ordered, so we can compare them.

So what we can do is obtain the addresses of the first and last elements of the slices, and by comparing them, we can tell if they overlap.

Here's a simple implementation:

func overlap(a, b int) bool {

    if len(a) == 0 || len(b) == 0 {

        return false

    }



    amin := reflect.ValueOf(&a[0]).Pointer()

    amax := reflect.ValueOf(&a[len(a)-1]).Pointer()

    bmin := reflect.ValueOf(&b[0]).Pointer()

    bmax := reflect.ValueOf(&b[len(b)-1]).Pointer()



    return !(amax < bmin || amin > bmax)

}

Testing it:

a := int{0, 1, 2, 3}

b := a[0:2]

c := a[2:4]

d := a[0:3]



fmt.Println(overlap(a, b)) // true

fmt.Println(overlap(b, c)) // false

fmt.Println(overlap(c, d)) // true

Try it on the Go Playground.

Found one way of this here. The idea is that while I don't think there's a way of finding the beginning of the backing array, ptr + cap of a slice should[*] point to the end of it. So then one compares the last pointer for equality, like:

func alias(x, y nat) bool {

    return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]

}

[*] The code includes the following note:

Note: alias assumes that the capacity of underlying arrays is never changed for nat values; i.e. that there are no 3-operand slice expressions in this code (or worse, reflect-based operations to the same effect).