7 ms·

Go(lang): Robust generic functions on slices

• jerf 3y ago
  A missing tidbit that may help contextualize this post: One of the things about Go that surprised me is that if you have a slice which does not represent the full capacity of the underlying array, you can go ahead and reslice it up to that full capacity even though it's a panic to access the things you're reslicing directly: https://go.dev/play/p/oThz2bNFwgr https://go.dev/play/p/oThz2bNFwgr Consequently, the GC has to assume that anything forward of any given slice into the underlying array may become accessible in the future as there is legal Go that can access it. It's still memory safe, but it surprised me. I had some code that was using my incorrect belief that slices could not be resliced up in size to implement some light security boundaries. Fortunately it was still legal, because the code in question simply didn't slice things larger and it's not like I was allowing arbitrary user-supplied code to run, so it was still correct in what it was doing. But I was expecting the runtime to scream if I did somehow screw it up when in fact it may not, depending on the exact capacity and what happened when. It's also asymmetric, as far as I know; you can slice forward into the array if there is capacity, but if you've got a slice that starts after index 0 in the backing array you can't use that slice to walk back into the underlying array. That is, with s := []int{11, 12, 13, 14, 15} s = s[2:] as far as I know, 11 and 12 are no longer accessible to any legal Go code (not using "unsafe") after that second line executes. Corrections (again not involving "unsafe", it's obvious those two values are still accessible through "unsafe") welcome. I was wrong once, it's easy to believe I could be wrong again.
  • sitzkrieg 3y ago
    interesting catch, thanks for sharing. my poor memory is already racing thinking about cases where i may have left traps with the same assumption
  • stock_toaster 3y ago
    You can prevent later longer reslicing by add an additional cap() element to the slicing to shrink the capacity. s = s[:3:3] from your first example link.
  • never_inline 3y ago
    It is reinforcing my belief that language design is hard. Go is supposed to be a simple language, one may write it for long time, but there will be some trap you discover once in a while.
    • bobbylarrybobby 3y ago
      Language design is hard, but... Jesus Christ, Go really just threw away 50 years of CS language research/experience in the name of “simplicity”.
      • bananapub 3y ago
        it's got all the latest features from the 1980s built right in
  • infogulch 3y ago
    One detail in the latest 1.22 release is a change in the "slices" library [1] (the library is based on generics, introduced in 1.21) that helps avoid such cases: > Functions that shrink the size of a slice (Delete, DeleteFunc, Compact, CompactFunc, and Replace) now zero the elements between the new length and the old length. [1]: https://tip.golang.org/doc/go1.22#slices https://tip.golang.org/doc/go1.22#slices [2]: https://pkg.go.dev/slices https://pkg.go.dev/slices
    • deleted 3y ago
      [deleted]
  • hairyplanter 3y ago
    In your playground example, if you print the capacity and the length before and after “re-extension”, it becomes clear what happened. In fact, accessing item 5 after reduction gives a size panic, where as accessing item 6 after re-extension gives you a capacity panic. Understanding rsc’s “Go Slices” blog is very helpful here. Coming from Java or something, this exposure of underlying storage could be jarring, but coming from C, Go slices are basically built in fat arrays, and this behavior doesn’t surprise me. Maybe it was a design mistake to expose so much of the underlying machinery. Ymmv.
  • everybodyknows 3y ago
    > ... the GC has to assume that anything forward of any given slice into the underlying array may become accessible in the future as there is legal Go that can access it. This property complicates the semantics of slices.Delete() in an interesting way: It is out of scope of the current proposal to write anything to the original tail https://github.com/golang/go/issues/63393 https://github.com/golang/go/issues/63393
• TheDong 3y ago
  The problems with the API they point out are almost all things that rust's ownership system was built to solve. Things like: slices.Sort(s) // correct slices.Compact(s) // incorrect slices.Delete(s, ...) // incorrect s := slices.Delete(s, ...) // incorrect if 's' is referenced again in the outer scope s = slices.Delete(s, ...) // correct All of those are solved by having functions like 'slices.Sort' take a '&mut' reference in rust speak, and having 'slices.Compact' and 'Delete' take an owned slice, and return a new owned slice.
  • lifthrasiir 3y ago
    You don't even need a notion of ownership. A distinction between an immutable and mutable slice should be enough, because an immutable slice can never be changed which implies that its excess capacity (if any) can't be exploited for optimization.
    • tsimionescu 3y ago
      None of these functions would apply to an immutable slice, so how is it related?
      • lifthrasiir 3y ago
        If immutable and mutable slices are differently typed [2], it is natural to define two functions (say, `slices.Compact` vs. `slices.Compacted`) to handle each type, like Python `list.sort` vs. `sorted`. It should be natural to expect `slices.Compacted` to never alter its input, and any attempt to use a mutable version will be very explicit except for slicing [1]. [1] Especially given that the capacity is preserved by default, which contributes to the current confusion. See my older comment: https://news.ycombinator.com/item?id=39112735 https://news.ycombinator.com/item?id=39112735 [2] Originally "...are different" but edited for clarity.
        • ikiris 3y ago
          This sounds awful in practice having to memorize different functions for the same thing based on mutability of the thing.
• gslaller 3y ago
  > func Index[S ~[]E, E comparable](s S, v E) int { After seeing this signature, I think that Go is giving up on it's simpleness principle.
  • quickthrower2 3y ago
    what does the ~ do here anyway?
    • onefiveone 3y ago
      type Something []string ensure that the underlying type is a slice
      • deleted 3y ago
        [deleted]
      • shakow 3y ago
        Why do you need a tilda for `S ~[]E`, but not for `E comparable`? Both are type-constraining annotations, so why two syntaxes?
        • quickthrower2 3y ago
          Guessing that E is the element, so is not a slice (or more accurately we don’t care if it is a slice or not!)
        • therein 3y ago
          It is like S: where S = []E where E: comperable. I like the way Rust has it a lot more but it is still imperfect and feels arbitrary in ways. I find myself unsure where to put the templatization parameters and it doesn't feel perfectly symmetrical. Unsure if impl MyType<T> where T: X is comperable to impl MyType<T: X> Sometimes it needs impl<T> MyType<T> where T: X
          • shakow 3y ago
• stouset 3y ago
  I feel like I’m taking crazy pills. How are these APIs even remotely defensible? slices.Sort(s) // fine slices.Compact(s) // broken s = slices.Compact(s) // fine s := slices.Compact(s) // broken (!!!) slices.Delete(s, …) // broken s = slices.Delete(s, …) // fine How is one intended to remember which functions require overwriting (due to invalidating) their input and which don’t? Why does the language make it so easy to render function parameters unusable upon return but impossible to enforce that they aren’t used afterward? How on earth did it take twelve years for this “simple” language to make a function to delete elements from an array, with `s = append(s[:start], s[end:]...)` having to suffice until then? How on earth does the “better” API twelve years later have such a gaping footgun? This is a core type that quite literally every program uses. How have things gone so far off the rails that “setting the obsolete pointers to nil” is such an intractable problem for end users they had to add a new keyword to the language? For other languages I see posts where weird language corner cases bring up challenging issues that really reinforce the idea that language design is hard. Rust—for example—has unsoundness issues in corner cases of the type system. But for go, it feels like there’s a constant stream of own goals on core areas of the language where the design should have knocked it out of the park. “Simple manipulation of arrays” just should not have this many footguns.
  • omeid2 3y ago
    Without defending this API, the easiest way to go about avoiding bugs when working with slice mutating functions is to consider all those "fine" scenarios as not fine. Always assume that only the return value of slice mutating functions are the valid reference and the old one always invalid. This is not always completely accurate, but it is very useful in that, it is also never "wrong".
    • masklinn 3y ago
      > Without defending this API, the easiest way to go about avoiding bugs when working with slice mutating functions is to consider all those "fine" scenarios as not fine. Always assume that only the return value of slice mutating functions are the valid reference and the old one always invalid. The first "fine" scenario is fine because `slices.Sort` works in place, it doesn't return a value at all. And the other "fine" versions do essentially what you advocate, by overwriting the invalid reference with the new one.
• ori_b 3y ago
  The ideal toolkit for building accidentally quadratic code.
• ergonaught 3y ago
  I loved C++ for years, but the more I learned about it the less I wanted to deal with it anymore. The past year or two, Go increasingly tries to repeat that experience. Should have just stuck with Common Lisp I guess.
• tialaramex 3y ago
  From the article: > Several new functions (Insert, Replace, Delete, etc.) modify the slice. To understand how they work, and how to properly use them, we need to examine the underlying structure of slices. [My emphasis] What this is telling us, although perhaps the author doesn't appreciate, is that this isn't an abstraction. If it was an abstraction we don't need to "examine the underlying structure of slices" in order to properly use them, we can just treat them as opaque. But in Go that's not an option, intimate knowledge of the inner workings is crucial to correct programming in Go. And that's not necessarily a problem for its main authors, who have anyway got such an understanding, but it should have given pause to somebody who thought about how you can effectively teach others to use this language. For Go in particular that's a huge problem because it's intended as a language for software engineering and for that purpose you do want to rely heavily on abstraction.