CODEWITHSUNDEEP
go
dskinner
dskinner

Reputation: 10857

Go - recursive struct with array and losing values

I created an Element struct that has a parent and children, created a helper func called SubElement, and a String method that iterates through all children for print:

package main

import "fmt"

type Element struct {
  parent *Element
  children []Element
  tag string
}

func SubElement(parent *Element, tag string) Element {
  el := Element{}
  el.parent = parent
  el.tag = tag
  parent.children = append(parent.children, el)
  return el
}

func (el Element) String() string {
  s := "<" + el.tag + ">"
  for _, child := range el.children {
    s += child.String()
  }
  s += "</" + el.tag + ">"
  return s
}

func main() {
  root := Element{}
  root.tag = "root"

  a := SubElement(&root, "a")
  b := SubElement(&a, "b")
  SubElement(&b, "c")

  fmt.Println(root) // prints: <root><a></a></root>
  fmt.Println(a) // prints: <a><b></b></a>
  // and so on
}

The problem I'm experiencing is, only the first tier of children are available from the root node I choose to print. I'm sure it's related to the use of append on parent.children, but lack the understanding of how to resolve this correctly.

To work around the issue, I changed children to map[int]Element. Then in my SubElement func, I "append" with parent.children[len(parent.children)] = el. Then to iterate in the correct order, the String method for-loop is for i:= 0; i < len(el.children); i++, accessing el.children[i].

Still, I'd like to know how to do this correctly with an array. Thanks

Upvotes: 1

Views: 2836

Answers (2)

Sonia
Sonia

Reputation: 28345

An answer to explain why the []Element version didn't work.

Structs are copied as values. In SubElement, you create one Element struct, then when you append it, that actually appends a whole new copy of the struct. When you return el and assign it to a, that makes yet another copy. The address of a is not the address of the Element that was appended.

So, you could get tricky and take the address of the element that's actually in the slice, and that might even look like it's working in a test case, but there's a problem with retaining one these pointers such as you do when you store it back in Element.parent. The problem is that a subsequent append can reallocate the slice, and now your retained pointer points into some orphaned memory rather than the currently valid slice.

If the []*Element version solved some other issues, it's likely that they were issues of storing pointers that were subseqently orphaned.

It is possible to implement a tree with slices of structs, but it takes a clear understanding that retaining pointers into slices is usually a mistake. Since storing the parent pointer is not safe, it's best to just remove it from the struct.

package main

import "fmt"

func main() {
    tree := Element{tag: "head"}
    tree.SubElement("tier-1")
    tree.children[0].SubElement("tier-2")
    tree.children[0].SubElement("tier-2")
    tree.SubElement("tier-1")
    tree.children[1].SubElement("tier-2")
    fmt.Println(tree)
}

type Element struct {
    children []Element
    tag      string
}

func (parent *Element) SubElement(tag string) {
    parent.children = append(parent.children, Element{tag: tag})
}

func (el Element) String() string {
    s := "<" + el.tag + ">"
    for _, child := range el.children {
        s += child.String()
    }
    s += "</" + el.tag + ">"
    return s
}

This code, at least, works; but if you had other code that was working with pointers, or that used the parent pointer, it would have to be rethought.

Upvotes: 5

Sonia
Sonia

Reputation: 28345

The first clue is that SubElement doesn't compile as you have it (edit: had it) there (originally.) You could experiment with making it work, but I recommend you change the Element.children to be []*Element rather than []Element. Here's a working example:

package main

import "fmt"

func main() {
    tree := &Element{tag: "head"}
    t1 := SubElement(tree, "tier-1")
    SubElement(t1, "tier-2")
    SubElement(t1, "tier-2")
    t1 = SubElement(tree, "tier-1")
    SubElement(t1, "tier-2")
    fmt.Println(tree)
}

type Element struct {
    parent   *Element
    children []*Element
    tag      string
}

func SubElement(parent *Element, tag string) *Element {
    el := &Element{parent: parent, tag: tag}
    parent.children = append(parent.children, el)
    return el
}

func (el *Element) String() string {
    s := "<" + el.tag + ">"
    for _, child := range el.children {
        s += child.String()
    }
    s += "</" + el.tag + ">"
    return s
}

Output:

<head><tier-1><tier-2></tier-2><tier-2></tier-2></tier-1><tier-1><tier-2></tier-2></tier-1></head>

Upvotes: 2

Related Questions