asteris-llc/converge

// Copyright © 2016 Asteris, LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package graph_test

import (
    "errors"
    "math/rand"
    "sort"

    "strconv"
    "sync"
    "testing"

    "github.com/asteris-llc/converge/graph"
    "github.com/asteris-llc/converge/graph/node"
    "github.com/asteris-llc/converge/helpers/logging"
    "github.com/stretchr/testify/assert"
    "github.com/stretchr/testify/require"
    "golang.org/x/net/context"
)

func TestGet(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))

    t.Run("found", func(t *testing.T) {
        val, found := g.Get("one")
        assert.Equal(t, 1, val.Value())
        assert.True(t, found)
    })

    t.Run("not found", func(t *testing.T) {
        val, found := g.Get("two")
        assert.False(t, found)
        assert.Nil(t, val)
    })
}

func TestContains(t *testing.T) {
    t.Parallel()
    g := graph.New()
    g.Add(node.New("one", 1))
    assert.True(t, g.Contains("one"))
    assert.False(t, g.Contains("two"))
}

func BenchmarkAddThenGet(b *testing.B) {
    g := graph.New()
    b.RunParallel(func(pb *testing.PB) {
        for pb.Next() {
            id := strconv.Itoa(rand.Int())
            g.Add(node.New(id, id))
            g.Get(id)
        }
    })
}

func BenchmarkCopyParallel(b *testing.B) {
    g := graph.New()
    b.RunParallel(func(pb *testing.PB) {
        for pb.Next() {
            g.Copy()
        }
    })
}

func TestRemove(t *testing.T) {
    // Remove should remove a vertex
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Remove("one")

    _, ok := g.Get("one")
    assert.False(t, ok)
}

func TestDownEdges(t *testing.T) {
    // DownEdges should return string IDs for the downward edges of a given node
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Add(node.New("two", 2))
    g.Connect("one", "two")

    assert.Equal(t, []string{"two"}, graph.Targets(g.DownEdges("one")))
    assert.Equal(t, 0, len(g.DownEdges("two")))
}

// TestDownEdgesInGroup tests that DownEdgesInGroup returns only edges with
// values in a group
func TestDownEdgesInGroup(t *testing.T) {
    t.Parallel()

    group := "group"
    g := graph.New()
    g.Add(newGroupNode("one", group, 1))
    g.Add(newGroupNode("two", group, 2))
    g.Add(node.New("three", 3))
    g.Connect("one", "two")
    g.Connect("one", "three")

    assert.Equal(t, []string{"two"}, g.DownEdgesInGroup("one", group))
    assert.Equal(t, 0, len(g.DownEdges("two")))
}

func TestUpEdges(t *testing.T) {
    // UpEdges should return string IDs for the upward edges of a given node
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Add(node.New("two", 2))
    g.Connect("one", "two")

    assert.Equal(t, []string{"one"}, graph.Sources(g.UpEdges("two")))
    assert.Equal(t, 0, len(g.UpEdges("one")))
}

// TestUpEdgesInGroup tests that UpEdgesInGroup returns only edges with values
// in a group
func TestUpEdgesInGroup(t *testing.T) {
    t.Parallel()

    group := "test"
    g := graph.New()
    g.Add(newGroupNode("one", group, 1))
    g.Add(newGroupNode("two", group, 2))
    g.Add(node.New("three", 2)) // no group
    g.Connect("one", "two")
    g.Connect("three", "two")

    assert.Equal(t, []string{"one"}, g.UpEdgesInGroup("two", group))
}

// TestNodes tests that Nodes returns nodes in the graph
func TestNodes(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Add(node.New("two", 2))
    g.Add(node.New("three", 2))
    g.Connect("one", "two")
    g.Connect("three", "two")

    nodes := g.Nodes()
    nodeIDs := make([]string, len(nodes))
    for i, node := range nodes {
        nodeIDs[i] = node.ID
    }
    sort.Strings(nodeIDs)

    assert.Equal(t, len(g.Vertices()), len(nodes))
    assert.Equal(t, []string{"one", "three", "two"}, nodeIDs)
}

// TestGroupNodes tests that GroupNodes only returns nodes in a specific group
func TestGroupNodes(t *testing.T) {
    t.Parallel()

    group := "test"
    newNode := func(id string, val int) *node.Node {
        n := node.New(id, val)
        n.Group = group
        return n
    }

    g := graph.New()
    g.Add(newNode("one", 1))
    g.Add(newNode("two", 2))
    g.Add(node.New("three", 2)) // no group
    g.Connect("one", "two")
    g.Connect("three", "two")

    nodes := g.GroupNodes(group)
    nodeIDs := make([]string, len(nodes))
    for i, node := range nodes {
        nodeIDs[i] = node.ID
    }
    sort.Strings(nodeIDs)

    assert.Equal(t, []string{"one", "two"}, nodeIDs)
}

// TestSafeConnect tests that calling SafeConnect on a an invalid graph will
// return an error
func TestSafeConnect(t *testing.T) {
    t.Parallel()
    t.Run("valid", func(t *testing.T) {
        g := graph.New()
        g.Add(node.New("a", nil))
        g.Add(node.New("b", nil))
        err := g.SafeConnect("a", "b")

        assert.NoError(t, err)
    })

    t.Run("invalid", func(t *testing.T) {
        g := invalidGraph()
        g.Add(node.New("a", nil))
        g.Add(node.New("b", nil))
        err := g.SafeConnect("a", "b")

        assert.Error(t, err)
    })
}

func TestDisconnect(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Add(node.New("two", 2))
    g.Connect("one", "two")
    g.Disconnect("one", "two")

    assert.NotContains(t, g.DownEdges("one"), "two")
}

// TestSafeDisconnect tests that calling SafeDisconnect on a an invalid graph
// will return an error
func TestSafeDisconnect(t *testing.T) {
    t.Parallel()
    t.Run("valid", func(t *testing.T) {
        g := graph.New()
        g.Add(node.New("one", 1))
        g.Add(node.New("two", 2))
        g.Add(node.New("three", 2))
        g.Connect("one", "two")
        g.Connect("one", "three")
        g.Connect("two", "three")

        err := g.SafeDisconnect("two", "three")
        assert.NoError(t, err)
    })

    t.Run("invalid", func(t *testing.T) {
        g := invalidGraph()
        g.Add(node.New("one", 1))
        g.Add(node.New("two", 2))
        g.Add(node.New("three", 2))
        g.Connect("one", "two")
        g.Connect("one", "three")
        g.Connect("two", "three")
        err := g.SafeDisconnect("two", "three")

        assert.Error(t, err)
    })
}

func TestDescendents(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("one", 1))
    g.Add(node.New("one/two", 2))
    g.Connect("one", "one/two")

    assert.Equal(t, []string{"one/two"}, g.Descendents("one"))
}

// TestChildren tests to ensure the correct behavior when getting children
func TestChildren(t *testing.T) {
    t.Parallel()
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("root", nil))
    g.Add(node.New("child1", nil))
    g.Add(node.New("child2", nil))

    g.Add(node.New("child1.1", nil))
    g.Add(node.New("child1.2", nil))
    g.Add(node.New("child1.3", nil))

    g.Add(node.New("child.1.1.1", nil))

    g.Add(node.New("child2.1", nil))
    g.Add(node.New("child2.2", nil))
    g.Add(node.New("child2.3", nil))

    g.ConnectParent("root", "child1")
    g.ConnectParent("root", "child2")

    g.ConnectParent("child1", "child1.1")
    g.ConnectParent("child1", "child1.2")
    g.ConnectParent("child1", "child1.3")

    g.ConnectParent("child2", "child2.1")
    g.ConnectParent("child2", "child2.2")
    g.ConnectParent("child2", "child2.3")

    g.ConnectParent("child1.1", "child.1.1.1")

    g.Connect("child1", "child2.1")
    g.Connect("child1", "child2.2")
    g.Connect("child1", "child2.3")

    children := g.Children("child1")

    expected := []string{"child1.1", "child1.2", "child1.3"}
    sort.Strings(expected)
    sort.Strings(children)
    assert.Equal(t, expected, children)
}

func TestWalkOrder(t *testing.T) {
    // the walk order should start with leaves and head towards the root
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("root", nil))
    g.Add(node.New("child1", nil))
    g.Add(node.New("child2", nil))

    g.ConnectParent("root", "child1")
    g.ConnectParent("root", "child2")

    out, err := idsInOrderOfExecution(g)

    assert.NoError(t, err)
    assert.Equal(t, "root", out[len(out)-1])
}

func TestWalkOrderDiamond(t *testing.T) {
    /*
        Tree in the form

        |    a    |
        |   / \   |
        |  b   c  |
        |   \ /   |
        |    d    |

        A proper dependency order search would always result in `d` being the first
        element processed
    */
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("a", nil))
    g.Add(node.New("b", nil))
    g.Add(node.New("c", nil))
    g.Add(node.New("d", nil))

    g.ConnectParent("a", "b")
    g.ConnectParent("a", "c")
    g.ConnectParent("b", "d")
    g.ConnectParent("c", "d")

    out, err := idsInOrderOfExecution(g)

    assert.NoError(t, err)
    if assert.True(t, len(out) > 3, "out was %s", out) {
        assert.Equal(t, "a", out[3])
        assert.Equal(t, "d", out[0])
    }
}

func TestWalkOrderParentDependency(t *testing.T) {
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("root", 1))
    g.Add(node.New("dependent", 1))
    g.Add(node.New("dependency", 1))
    g.Add(node.New("dependent/child", 1))
    g.Add(node.New("dependency/child", 1))

    g.ConnectParent("root", "dependent")
    g.ConnectParent("root", "dependency")
    g.ConnectParent("dependent", "dependent/child")
    g.ConnectParent("dependency", "dependency/child")

    g.Connect("dependent", "dependency")

    exLock := new(sync.Mutex)
    var execution []string

    require.NoError(t,
        g.Walk(
            context.Background(),
            func(meta *node.Node) error {
                exLock.Lock()
                defer exLock.Unlock()

                execution = append(execution, meta.ID)

                return nil
            },
        ),
    )

    assert.Equal(
        t,
        []string{
            "dependency/child",
            "dependency",
            "dependent/child",
            "dependent",
            "root",
        },
        execution,
    )
}

func TestWalkError(t *testing.T) {
    g := graph.New()

    g.Add(node.New("a", nil))
    g.Add(node.New("b", nil))
    g.Add(node.New("c", nil))

    g.ConnectParent("a", "b")
    g.ConnectParent("b", "c")

    err := g.Walk(
        context.Background(),
        func(meta *node.Node) error {
            if meta.ID == "c" {
                return errors.New("test")
            }
            return nil
        },
    )

    if assert.Error(t, err) {
        assert.EqualError(t, err, "1 error(s) occurred:\n\n* c: test")
    }
}

func TestValidateNoRoot(t *testing.T) {
    // Validate should error if there is no root
    t.Parallel()

    g := graph.New()

    err := g.Validate()
    if assert.Error(t, err) {
        assert.EqualError(t, err, "no roots found")
    }
}

func TestValidateCycle(t *testing.T) {
    // Validate should error if there is a cyle
    t.Parallel()

    g := graph.New()
    g.Add(node.New("a", nil))
    g.Add(node.New("b", nil))
    g.Add(node.New("c", nil))

    // a is just a root
    g.Connect("a", "b")

    // now the cycle
    g.Connect("b", "c")
    g.Connect("c", "b")

    err := g.Validate()
    if assert.Error(t, err) {
        assert.Contains(t, err.Error(), "1 error(s) occurred:\n\n* Cycle: ")
    }
}

func TestValidateDanglingEdge(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("a", nil))
    g.Connect("a", "nope")

    err := g.Validate()
    if assert.Error(t, err) {
        assert.EqualError(t, err, "nonexistent vertices in edges: nope")
    }
}

func TestTransform(t *testing.T) {
    // Transforming in the same type should work
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("int", 1))

    transformed, err := g.Transform(
        context.Background(),
        func(meta *node.Node, dest *graph.Graph) error {
            dest.Add(node.New(meta.ID, 2))

            return nil
        },
    )

    assert.NoError(t, err)
    meta, ok := transformed.Get("int")
    require.True(t, ok, "node was not present in graph")
    assert.Equal(t, 2, meta.Value().(int))
}

func TestParent(t *testing.T) {
    // the graph should return the parent with ID
    t.Parallel()

    g := graph.New()
    g.Add(node.New(graph.ID("root"), 1))
    g.Add(node.New(graph.ID("root", "child"), 2))

    g.ConnectParent(graph.ID("root"), graph.ID("root", "child"))

    require.NoError(t, g.Validate())

    actual, ok := g.GetParent(graph.ID("root", "child"))
    require.True(t, ok)
    should, _ := g.Get(graph.ID("root"))
    assert.Equal(t, should, actual)
}

func TestRootFirstWalk(t *testing.T) {
    // the graph should walk nodes root-to-leaf
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("root", nil))
    g.Add(node.New("root/child", nil))
    g.ConnectParent("root", "root/child")

    var out []string
    assert.NoError(
        t,
        g.RootFirstWalk(
            context.Background(),
            func(meta *node.Node) error {
                out = append(out, meta.ID)
                return nil
            },
        ),
    )

    assert.Equal(t, []string{"root", "root/child"}, out)
}

func TestRootFirstWalkSiblingDep(t *testing.T) {
    // the graph should resolve sibling dependencies before their dependers
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("root", nil))
    g.Add(node.New("root/child", nil))
    g.Add(node.New("root/sibling", nil))

    g.ConnectParent("root", "root/child")
    g.ConnectParent("root", "root/sibling")
    g.Connect("root/child", "root/sibling")

    var out []string
    assert.NoError(
        t,
        g.RootFirstWalk(
            context.Background(),
            func(meta *node.Node) error {
                out = append(out, meta.ID)
                return nil
            },
        ),
    )

    assert.Equal(
        t,
        []string{"root", "root/sibling", "root/child"},
        out,
    )
}

func TestRootFirstTransform(t *testing.T) {
    // transforming depth first should work
    defer logging.HideLogs(t)()

    g := graph.New()
    g.Add(node.New("int", 1))

    transformed, err := g.RootFirstTransform(
        context.Background(),
        func(meta *node.Node, dest *graph.Graph) error {
            dest.Add(meta.WithValue(2))

            return nil
        },
    )

    assert.NoError(t, err)
    meta, ok := transformed.Get("int")
    require.True(t, ok, "\"int\" was not present in graph")
    assert.Equal(t, 2, meta.Value().(int))
}

// TestIsNibling tests various scenarios where we want to know if a node is a
// nibling of the source node.
func TestIsNibling(t *testing.T) {
    t.Parallel()

    g := graph.New()
    g.Add(node.New("a", struct{}{}))
    g.Add(node.New("a/b", struct{}{}))
    g.ConnectParent("a", "a/b")
    g.Add(node.New("a/b/c", struct{}{}))
    g.ConnectParent("a/b", "a/b/c")
    g.Add(node.New("a/b/c/d", struct{}{}))
    g.ConnectParent("a/b/c", "a/b/c/d")
    g.Add(node.New("a/c", struct{}{}))
    g.ConnectParent("a", "a/c")
    g.Add(node.New("a/c/d", struct{}{}))
    g.ConnectParent("a/c", "a/c/d")
    g.Add(node.New("a/c/d/e", struct{}{}))
    g.ConnectParent("a/c/d", "a/c/d/e")
    g.Add(node.New("x", struct{}{}))
    g.Add(node.New("x/c", struct{}{}))
    g.ConnectParent("x", "x/c")

    t.Run("are siblings", func(t *testing.T) {
        assert.True(t, g.IsNibling("a/b", "a/c"))
    })
    t.Run("is direct nibling", func(t *testing.T) {
        assert.True(t, g.IsNibling("a/b", "a/c/d"))
    })
    t.Run("is nibling child of nibling", func(t *testing.T) {
        assert.True(t, g.IsNibling("a/b", "a/c/d/e"))
    })
    t.Run("child", func(t *testing.T) {
        assert.False(t, g.IsNibling("a/b", "a/b/c"))
    })
    t.Run("grandchild", func(t *testing.T) {
        assert.False(t, g.IsNibling("a/b", "a/b/c/d"))
    })
    t.Run("unrelated", func(t *testing.T) {
        assert.False(t, g.IsNibling("a/b", "x/c"))
    })
    t.Run("cousins", func(t *testing.T) {
        assert.False(t, g.IsNibling("a/b/c", "a/x"))
    })
    t.Run("parent", func(t *testing.T) {
        assert.False(t, g.IsNibling("a/b/c", "a/b"))
    })
}

func idsInOrderOfExecution(g *graph.Graph) ([]string, error) {
    lock := new(sync.Mutex)
    out := []string{}

    err := g.Walk(
        context.Background(),
        func(meta *node.Node) error {
            lock.Lock()
            defer lock.Unlock()

            out = append(out, meta.ID)

            return nil
        },
    )

    return out, err
}

func invalidGraph() *graph.Graph {
    g := graph.New()
    g.Connect("Bad", "Nodes")
    return g
}

func newGroupNode(id, group string, val interface{}) *node.Node {
    n := node.New(id, val)
    n.Group = group
    return n
}