Hi guys:
I met a problem when I try to understand slice when using as function
parameters. After writing some code, I made a conclusion by myself, but
need some real check and explanation here, with your help.
As far as I know, Golang's function parameters are passed by value, and
slice could be treated as a descriptor, which seems like *{pointer to first
element of underlying array, length of element, capacity of array}*
according to Go Slices: usage and internals
<https://blog.golang.org/go-slices-usage-and-internals>. So, can I say:
*When passing a slice as a function parameter, it is, in fact, passing a
pointer, and two int values (or as a whole struct, or maybe more parameters
to describe the slice, whatever).*
To make it clear using code:
func foo(s []T) {...}
// can this function be treated as following 3-parameter function?
func foo(p Pointer, length, capa int) {...}
// Note: type is not the point here,
// and we just need 3 parameters, while there maybe more
You may wonder why I have this question? Here is where everything started:
func foo(s []int) {
s := []int{1,2,3}
foo(s)
fmt.Println(s)
}
Everyone know it will print [1 2 3], not [1 2 3 100]. But what I am
interested in, is *whether the function call does modify the memory* just
after the tail of element 3, to an int of 100. If my assumption above is
right, then the modification may happen.
So, I made some experiments.
package main
import "fmt"
import "strconv"
type Node struct {
val int
left *Node
right *Node
}
func (n Node) String () string {
return strconv.Itoa(n.val)
}
func newNode(val int) *Node {
return &Node{val, nil, nil}
}
// Given a binary tree and a target sum, find all root-to-leaf paths
// where each path's sum equals the given sum
func bs(root *Node, path []*Node, now int, target int, ret *[][]*Node) {
if root == nil {
return
}
path = append(path, root)
now += root.val
if now == target && root.left == nil && root.right == nil {
*ret = append(*ret, path)
return
}
bs(root.left, path, now, target, ret)
bs(root.right, path, now, target, ret)
}
func main() {
// a simple tree like:
// 0
// / \
// 1 2
root := newNode(0)
left := newNode(1)
right := newNode(2)
root.left = left
root.right = right
ret := [][]*Node{}
bs(root, make([]*Node, 0, 10), 0, 1, &ret)
fmt.Println(ret)
}
As the code above, it is a function to find all root-to-leaf paths where
each path's sum equals the given sum in a binary tree, and, I make a simple
test case which there are only 3 nodes: one root, two children, with values
of 0, 1 and 2.
Say, I want to find the paths of sum of 1. So, I call this function as:
bs(root, make([]*Node, 0, 10), 0, 1, &ret)
It is petty common to make a guess that, this call will give us a final
result of [0, 1], which is obviously the correct answer, however, it gives
us [0, 2], try yourself if you don't believe:
https://play.golang.org/p/hSKIOaVK2S
The algorithm here is correct, don't worry about it. Instead, please pay
attention to the second parameter of bs(). It makes a slice which has no
element in it, and has a capacity of 10. What if we change this parameter
to:
bs(root, make([]*Node, 0, 1), 0, 1, &ret)
Yes, just make the slice's capacity as 1. This time you will get the right
answer, [0, 1]. Try yourself if you are interested.
Here is my understanding of this strange problem, feel free to point out
anything wrong:
Still the simplest code:
package main
import (
"fmt"
)
func foo(s []int) {
fmt.Println(len(s), cap(s)) // 3 3
s = append(s, 100)
fmt.Println(len(s), cap(s)) // 4 8
}
func main() {
s := []int{1,2,3}
foo(s)
fmt.Println(len(s), cap(s)) // 3 3
fmt.Println(s) // [1 2 3]
}
When the function foo() called, it has 3 parameters: a pointer of the first
element of the array, which points to the element 1, an int for array
length: 3, an int for array capacity: 3. In foo(), it tries to append 100
at the tail, but there is no room for it, according to the parameter of
capacity it receive, so, it makes a larger array, which capacity is 8, then
do some copy-and-append job. Unfortunately, all the work it does is useless
because all three parameters is still themselves. So, at last, it prints [1
2 3]
But, what will happen if the slice passed into foo() is large enough
already?
package main
import (
"fmt"
)
func foo(s []int) {
fmt.Println(len(s), cap(s)) // 3 10
s = append(s, 100)
fmt.Println(len(s), cap(s)) // 4 10
}
func main() {
s := make([]int, 3, 10)
s[0], s[1], s[2] = 1, 2, 3
foo(s)
fmt.Println(len(s), cap(s)) // 3 10
fmt.Println(s) // [1 2 3]
}
Now, foo() is lucky, he does not need to allocate any memory, he just
append 100 at the tail, the descriptor now becomes {address somewhere, 4,
10}. However, in main, it is still {address somewhere, 3, 10} on account of
the pass-by-value-calling-rule, *so, we just care about the first 3
elements of the array, and ignore others because the descriptor tells us
to, even though there does exist the 4th one.*
How to prove there is a 4th one? Which is equal to ask, how to prove the
function call modify the passed slice? Check the path-of-sum algorithm
above, it may show something indirectly.
The algorithm starts from the root, 0, then goes to his left child, 1,
there it meets the target sum, 1 (0+1), so it append 1 into the path slice
(which now is [0,1], descriptor as {address, 2, 10}) and append the path
slice into ret. After this, it will find no child exists, so it returns
from current position and goes back to the root to check root's right
child. Now, the path slice's descriptor is {address, 1, 10}. When checking
the right child, it append 2 into path, which does modify the memory where
1 sits already. At last, it will print [0, 2] as the wrong result.
This tells us one thing: function calls may modify your passed slice, but
the slice descriptor keeps you from knowing it.
My personal explanation is done, and here are my questions:
1. Am I right? What's wrong?
2. If I am right, mostly, how to prevent it gracefully? Any rules, or any
blogs I can learn from?
3. Any better code snippet to do some experiment to make it more
convincing? Does packet reflect <https://golang.org/pkg/reflect/> helpful?
can I just print the 4th element even though the slice descriptor tell me
its length is 3?
4. Where can I find the code of implementation of slice?
Thanks a lot.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
