Aliasing of slices












2














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?










share|improve this question




















  • 1




    You must compare the addresses of their elements. Check if the ranges overlap.
    – Volker
    Nov 13 at 11:54
















2














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?










share|improve this question




















  • 1




    You must compare the addresses of their elements. Check if the ranges overlap.
    – Volker
    Nov 13 at 11:54














2












2








2


1





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?










share|improve this question















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?







arrays pointers go memory slice






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 13 at 12:18









icza

162k24314354




162k24314354










asked Nov 13 at 11:47









Ecir Hana

3,822104184




3,822104184








  • 1




    You must compare the addresses of their elements. Check if the ranges overlap.
    – Volker
    Nov 13 at 11:54














  • 1




    You must compare the addresses of their elements. Check if the ranges overlap.
    – Volker
    Nov 13 at 11:54








1




1




You must compare the addresses of their elements. Check if the ranges overlap.
– Volker
Nov 13 at 11:54




You must compare the addresses of their elements. Check if the ranges overlap.
– Volker
Nov 13 at 11:54












2 Answers
2






active

oldest

votes


















3














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.






share|improve this answer























  • b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
    – Peter
    Nov 13 at 14:37












  • Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
    – Ecir Hana
    Nov 13 at 14:47










  • @Peter I've misunderstood the question. Editing now.
    – icza
    Nov 13 at 14:59










  • @EcirHana Misunderstood, edited the question to answer that.
    – icza
    Nov 13 at 15:05



















0














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).







share|improve this answer





















    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53280378%2faliasing-of-slices%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    3














    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.






    share|improve this answer























    • b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
      – Peter
      Nov 13 at 14:37












    • Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
      – Ecir Hana
      Nov 13 at 14:47










    • @Peter I've misunderstood the question. Editing now.
      – icza
      Nov 13 at 14:59










    • @EcirHana Misunderstood, edited the question to answer that.
      – icza
      Nov 13 at 15:05
















    3














    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.






    share|improve this answer























    • b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
      – Peter
      Nov 13 at 14:37












    • Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
      – Ecir Hana
      Nov 13 at 14:47










    • @Peter I've misunderstood the question. Editing now.
      – icza
      Nov 13 at 14:59










    • @EcirHana Misunderstood, edited the question to answer that.
      – icza
      Nov 13 at 15:05














    3












    3








    3






    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.






    share|improve this answer














    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Nov 13 at 15:01

























    answered Nov 13 at 12:16









    icza

    162k24314354




    162k24314354












    • b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
      – Peter
      Nov 13 at 14:37












    • Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
      – Ecir Hana
      Nov 13 at 14:47










    • @Peter I've misunderstood the question. Editing now.
      – icza
      Nov 13 at 14:59










    • @EcirHana Misunderstood, edited the question to answer that.
      – icza
      Nov 13 at 15:05


















    • b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
      – Peter
      Nov 13 at 14:37












    • Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
      – Ecir Hana
      Nov 13 at 14:47










    • @Peter I've misunderstood the question. Editing now.
      – icza
      Nov 13 at 14:59










    • @EcirHana Misunderstood, edited the question to answer that.
      – icza
      Nov 13 at 15:05
















    b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
    – Peter
    Nov 13 at 14:37






    b, c and d are all backed by the same array, so overlap(b, c) should return true as well; as shown in the question (and the name is misleading). Unless I'm missing something, it should be enough to compare the addresses of x[cap(x)-1]: play.golang.org/p/ULB3RJhz07i
    – Peter
    Nov 13 at 14:37














    Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
    – Ecir Hana
    Nov 13 at 14:47




    Thanks but the question is whether the backing array is the same (and not whether the slices overlap).
    – Ecir Hana
    Nov 13 at 14:47












    @Peter I've misunderstood the question. Editing now.
    – icza
    Nov 13 at 14:59




    @Peter I've misunderstood the question. Editing now.
    – icza
    Nov 13 at 14:59












    @EcirHana Misunderstood, edited the question to answer that.
    – icza
    Nov 13 at 15:05




    @EcirHana Misunderstood, edited the question to answer that.
    – icza
    Nov 13 at 15:05













    0














    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).







    share|improve this answer


























      0














      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).







      share|improve this answer
























        0












        0








        0






        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).







        share|improve this answer












        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).








        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 13 at 14:45









        Ecir Hana

        3,822104184




        3,822104184






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53280378%2faliasing-of-slices%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Guess what letter conforming each word

            Port of Spain

            Run scheduled task as local user group (not BUILTIN)