非常令人困惑的变量更改

Question

http://play.golang.org/p/Vd3meom5VF

I have this code for some context free grammar in Go

And I am looking at this code so many times and still don't see any reason for the struct values to be changed. Could anybody see why the change like the following happens?

Rules:
S -> . [DP VP]
VP -> . [V DP]
VP -> . [V DP AdvP]

After I run some functions as in the line

 or2 = append(or2, OstarCF([]QRS{q}, []string{"sees"}, g2.Nullables(), g2.ChainsTo(g2.Nullables()))...)

Somehow my struct value is changed... I don't know why...

Rules:
S -> . [VP VP]
VP -> . [DP DP]
VP -> . [AdvP AdvP AdvP]

This should have been same as above.

 Rules:
 S -> DP,VP
 VP -> V,DP
 VP -> V,DP,AdvP

 or2 := []QRS{}
 g2 := ToGrammar(cfg2)
 fmt.Printf("%s
", g2)

 for _, rule := range g2.Rules {
        q := QRS{
            one:   rule.Src,
            two:   []string{},
            three: rule.Right,
        }
        or2 = append(or2, OstarCF([]QRS{q}, []string{"sees"}, g2.Nullables(), g2.ChainsTo(g2.Nullables()))...)
    }

    fmt.Printf("%s
", g2)

As you see, I do not use any pointer the variable rule, and they are only used to instantiate another struct value, but how come the original struct field rule has changed? The function OstarCF does not do anything about this field rule

 func OstarCF(Qs []QRS, R []string, nD map[string]bool, cD map[string][]string) []QRS {
    symbols := []string{}
    for _, r := range R {
        symbols = append(symbols, cD[r]...)
    }
    product := []QRS{}
    for _, Q := range Qs {
        a := Q.one
        b := Q.two
        c := Q.three
        if len(c) > 0 && CheckStr(c[0], symbols) {
            b = append(b, c[0])
            np := QRS{
                one:   a,
                two:   b,
                three: c[1:],
            }
            product = append(product, np)

            for len(np.three) > 0 && nD[np.three[0]] == true {
                np.two = append(np.two, np.three[0])
                np = QRS{
                    one:   np.one,
                    two:   np.two,
                    three: np.three[1:],
                }
                product = append(product, np)
            }
        }
    }
    return product
 }

Answer 1

The original Rules field changes because pointers and slices (which are references as well) are used.

Before calling OstarCF, the ChainsTo method is called. It uses the grammar object by value, so a copy is done, but the Rules field is a slice of pointers on Rules. So when this field is copied, it still points to the data of the original object.

Then, in method ChainsTo, there is a loop on the Rules field. It copies the Right field which is a slice of strings (so it still points to data of the original object):

rhs := rule.Right

Finally, a ns variable is declared by slicing rhs:

ns := rhs[:i]
ns = append(ns, rhs[i+1:]...)

At this stage, the ns variable still points to the buffer containing the slice of strings of the original object. Initially, i=0, so ns is an empty slice reusing the buffer. When items are appended, they replace the original data.

That's why your data are changed.

You can fix this problem by explicitly making a copy, for instance by replacing the above lines by:

ns := make( []string, 0, len(rhs) )
ns = append( ns, rhs[:i]...)
ns = append( ns, rhs[i+1:]...)

Go slices have replaced C pointer arithmetic, but they can be almost as dangerous/misleading in some cases.