Go code critique requested

carlca · January 17, 2017, 12:19pm

Hello folks. Well I’m attempting to start my own code and I thought I’d start with a tree node implementation. It’s very vaguely based on an old Delphi code base though obviously rewritten to take advantage of Go idioms. However, I have gotten myself in a bit of a mess with pointers. Could some kind soul take a quick look at the code below and offer some constructive criticism. The intent of the code should be obvious:

package main

import (
	"fmt"
	"strings"
)  

const dbg = true

type node struct {
	Next *node
	Prev *node
	Parent *node
	FirstChild *node
	Data interface{}
	Level int32
}

func (n node) AddChild(data interface{}) *node {
	newNode := node{Data: data}
	newNode.Parent = &n

	if dbg { fmt.Println(newNode.Parent.Data)}

	if n.FirstChild == nil {
		n.FirstChild = &newNode
	}
	newNode.Level = n.Level + 1
	return &newNode
}

func (n node) AddSib(data interface{}) *node {
	newNode := node{Data: data}
	n.Next = &newNode
	newNode.Prev = &n
	newNode.Parent = n.Parent
	newNode.Level = n.Level
	return &newNode
}

func AddRoot(data interface{}) *node {
	newNode := node{Data: data}
	newNode.Level = 0
	return &newNode
}

func (n node) GetNext() *node {
	if n.FirstChild != nil {
		return n.FirstChild
	} else {
		if n.Next != nil {
			return n.Next
		} else {
			nn := n.Parent
			for nn != nil && nn.Next == nil {
				nn = nn.Parent
			}
			if nn != nil {
				return nn.Next
			} else {
				return nil
			}
		}
	}
}

func main () {
	root := AddRoot("Root node")
	root.AddChild("Child 1")
	child2 := root.AddChild("Child 2")
	child2.AddSib("Sib 1")
	child2.AddSib("Sib 2")

	nn := root
	fmt.Println(nn.Data)
	nn = nn.GetNext()
	fmt.Println(nn.Data)

	for nn != nil {
		fmt.Print(strings.Repeat(" ", int(nn.Level)))
		fmt.Println(nn.Data)
		nn = nn.GetNext()
	}
}

Thanks in advance,
Carl

dfc · January 17, 2017, 12:27pm

First suggestion, use the code macro to properly format your post. Go programmers are used to looking at gofmt’d code, anything that does not look like it has been formatted correctly is effectively invisible to them.

nathankerr · January 17, 2017, 12:35pm

Using the playground also works.

https://play.golang.org/p/RNXnFqy7bA

carlca · January 17, 2017, 12:40pm

Sorry about that - wasn’t sure how to do that. Should be formatted now!

nathankerr · January 17, 2017, 12:41pm

It is. Thanks.

nathankerr · January 17, 2017, 1:13pm

Running the code (on the playground) gives me:

Root node
Root node
Root node
panic: runtime error: invalid memory address or     nil pointer dereference
[signal SIGSEGV: segmentation violation code=0xffffffff addr=0x0 pc=0x20ca7]

goroutine 1 [running]:
panic(0x1045c0, 0x1040a038)
/usr/local/go/src/runtime/panic.go:500 +0x720
main.main()
/tmp/sandbox635847588/main.go:79 +0x907

The SIGSEGV (triggered from line 79) can be solved by changing AddChild to a pointer receiver:

func (n *node) AddChild(data interface{}) *node {
	newNode := node{Data: data}
	newNode.Parent = n

	if dbg {
		fmt.Println(newNode.Parent.Data)
	}

	if n.FirstChild == nil {
		n.FirstChild = &newNode
	}
	newNode.Level = n.Level + 1
	return &newNode
}

This is needed to modify n. A similar change is needed for AddSib. Note that since n is now a *node you do not need to &n to get a pointer to the node, as it already is one.

nathankerr · January 17, 2017, 2:45pm

Most of my comments are about style.

My version, after applying these notes, is at https://play.golang.org/p/1oY9KkArda

The bugs I noticed at at the end. I think I did not fix or add any bugs.

Node Literals

Save some typing and make things clearer by:

Immediately getting a pointer to node
Adding all data possible to the node when you create it

Transform from:

func (n *node) AddSib(data interface{}) *node {
    newNode := node{Data: data}
    n.Next = &newNode
    newNode.Prev = n
    newNode.Parent = n.Parent
    newNode.Level = n.Level
    return &newNode
}

to:

func (n *node) AddSib(data interface{}) *node {
    newNode := &node{
        Data:   data,
        Prev:   n,
        Parent: n.Parent,
        Level:  n.Level,
    }
    n.Next = newNode

    return newNode
}

Notice how the modification to n.Next is easier to separate from the setting of newNode's members.

Use `log` for debug logging

For these sort of exploratory or prototype programs I like to start my main() with log.SetFlags(Lshortfile). This tells the log package to print the filename (without its path) and line number out anytime log.Print* is called. Changing your

fmt.Println(nn.Data)

to

log.Println(nn.Data)

will produce output like:

tree.go:79: Root node

I don’t use things like if dbg in these sorts of programs because I can easily find the individual log statements and delete or comment them out.

Don’t set zero values

AddRoot contains the line:

newNode.Level = 0

Level is an int32 (I think it should be an int). Integers have a zero value of 0, therefore there is no need to explicitly set it.

Also, you can directly return composite literals:

func AddRoot(data interface{}) *node {
    return &node{Data: data}
}

Don’t use `else` with early returns

When the true branch of an if returns, the rest of the function is part of an else. Since it will already not be executed when the if is true, an additional level of indentation can avoided by not using else.

I think of functions in this style as a series of filters. As soon as the right (or wrong, in the case of error handling) condition is met, the function returns.

Following this convention, GetNext changes from:

func (n node) GetNext() *node {
    if n.FirstChild != nil {
        return n.FirstChild
    } else {
        if n.Next != nil {
            return n.Next
        } else {
            nn := n.Parent
            for nn != nil && nn.Next == nil {
                nn = nn.Parent
            }
            if nn != nil {
                return nn.Next
            } else {
                return nil
            }
        }
    }
}

to:

func (n node) GetNext() *node {
    if n.FirstChild != nil {
        return n.FirstChild
    }

    if n.Next != nil {
        return n.Next
    }

    nn := n.Parent
    for nn != nil && nn.Next == nil {
        nn = nn.Parent
    }
    if nn != nil {
        return nn.Next
    }

    return nil
}

I also tend to separate related chunks of code by blank lines, almost as if they were paragraphs.

`for` loop setup, conditions, and increment

When possible, put the setup, condition, and increment as part of the for loop:

for nn := root; nn != nil; nn = nn.GetNext() {
    fmt.Print(strings.Repeat(" ", int(nn.Level)))
    fmt.Println(nn.Data)
}

this makes figuring the loop out easier and allows the increment to work well when continueing the loop.

The loop in GetNext is an example of when I would not do this because:

nn is needed outside of the loop’s scope and did not already exist
the loop does nothing besides looping
there is no potential need to continue (because the loop only loops)
the condition is long enough that the for line would become longer than I would like

Bugs I noticed

but did not fix so as to not ruin your learning experience:

AddChild only adds the first child added
AddSib replaces n.Next with the new node. Only the latest sibling added will exist in the tree.

I recommend writing tests to reproduce these bugs before fixing them.

Egon · January 17, 2017, 3:08pm

The intent of the code should be obvious:

Not really.

I do understand that it is trying to implement a tree, but I do not understand the purpose. The reason for writing a tree can vary and hence the way you write the tree can vary. Or alternatively, there might be a better data-structure suited for the purpose.

Just as a start:

type Node struct {
	Parent *Node
	Children []*Node
	Data interface{}
	Level int32
}
// or 
type Node struct {
	Children []*Node
	Value interface{}
	Level int
}

Depending on the purpose of writing the Tree there may be alternative solutions that are faster, look nicer and cleaner in Go. Not that there is anything particular wrong with using a tree; in the correct situation it can be a perfect solution.

So, my main criticism is that the code does not reveal the purpose or why the code was written in the first place. This in turn harms readability and understandability (e.g. one side-effect is that you need to use interface{}).

carlca · January 17, 2017, 3:40pm

Nathan, thank you that was exactly the type of response I was after! I like the use of node literals to flatten out the code. In fact I like all the suggestions - I will go away and study them at length and endeavour to correct the remaining bugs. I really appreciate the time you took to help me, thanks again.

Best,
Carl

system · April 17, 2017, 3:40pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.