<commit_before>// Copyright © 2012-2013, <NAME>. All rights reserved.
// Use of this source code is governed by a BSD-style license that can
// be found in the LICENSE.txt file.

package dag

import (
	"bytes"
	"errors"
	"reflect"
	"strconv"
	"testing"

	"code.google.com/p/go-bit/bit"
	"github.com/stretchrcom/testify/assert"

	"fubsy/testutils"
	"fubsy/types"
)

func Test_DAG_add_lookup(t *testing.T) {
	dag := NewDAG()
	outnode := dag.lookup("foo")
	assert.Nil(t, outnode)

	innode := NewStubNode("foo")
	_, outnode = dag.addNode(innode)
	assert.True(t, outnode == innode)
	assert.True(t, innode == dag.nodes[0].(*StubNode))

	outnode = dag.lookup("foo")
	assert.True(t, outnode.(*StubNode) == innode)

	assert.Nil(t, dag.lookup("bar"))
}

func Test_DAG_FindFinalTargets(t *testing.T) {
	dag := makeSimpleGraph()
	targets := (*bit.Set)(dag.FindFinalTargets())
	assert.Equal(t, "{0, 1}", targets.String())
}

func Test_DAG_DFS(t *testing.T) {
	// 0: a -> {c, f, h}
	// 1: b -> {d, f, g, h}
	// 2: c -> {b, e}
	// 3: d -> {g}
	// 4: e -> {}
	// 5: f -> {g}
	// 6: g -> {}
	// 7: h -> {}
	// original sources: {e, g, h} = {4, 6, 7}
	// final targets:    {a} = {0}

	tdag := newtestdag()
	tdag.add("a", "c", "f", "h")
	tdag.add("b", "d", "f", "g", "h")
	tdag.add("c", "b", "e")
	tdag.add("d", "g")
	tdag.add("e")
	tdag.add("f", "g")
	tdag.add("g")
	tdag.add("h")
	dag := tdag.finish()

	actual := []string{}
	visit := func(id int) error {
		actual = append(actual, dag.nodes[id].Name())
		return nil
	}

	assertDFS := func(start *bit.Set, expect []string) {
		actual = actual[0:0]
		dag.DFS(start, visit)
		assert.Equal(t, expect, actual)
	}

	start := bit.New()
	start.AddRange(0, 7)
	expect := []string{"g", "d", "f", "h", "b", "e", "c", "a"}
	assertDFS(start, expect)

	// start nodes: {c, f}
	start = bit.New(2, 5)
	expect = []string{"g", "d", "f", "h", "b", "e", "c"}
	assertDFS(start, expect)

	// start nodes: {d, f}
	start = bit.New(3, 5)
	expect = []string{"g", "d", "f"}
	assertDFS(start, expect)
}

func Test_DAG_DFS_cycle(t *testing.T) {
	var tdag *testdag
	var dag *DAG
	var err error

	visit := func(id int) error { return nil }

	tdag = newtestdag()
	tdag.add("0", "1")
	tdag.add("1", "0")
	dag = tdag.finish()
	err = dag.DFS(NodeSet(bit.New(0, 1)), visit)
	assert.Equal(t, "found 1 dependency cycles:\n  0 -> 1 -> 0", err.Error())

	// degenerate case
	tdag = newtestdag()
	tdag.add("0", "0")
	dag = tdag.finish()
	err = dag.DFS(NodeSet(bit.New(0)), visit)
	assert.Equal(t, "found 1 dependency cycles:\n  0 -> 0", err.Error())

	// weird case: two disconnected isomorphic graphs stuck in the
	// same data structure; each has two discernible cycles:
	//   0 -> 2 -> 4 -> 6 -> 2
	//   0 -> 2 -> 4 -> 8 -> 0
	//   1 -> 3 -> 5 -> 7 -> 3
	//   1 -> 3 -> 5 -> 9 -> 1
	tdag = newtestdag()
	tdag.add("0", "2", "4")
	tdag.add("1", "3", "5")
	tdag.add("2", "4")
	tdag.add("3", "5")
	tdag.add("4", "6", "8")
	tdag.add("5", "7", "9")
	tdag.add("6", "2")
	tdag.add("7", "3")
	tdag.add("8", "0")
	tdag.add("9", "1")
	dag = tdag.finish()
	start := bit.New()
	start.AddRange(0, 9)
	err = dag.DFS(NodeSet(start), visit)
	cycerr := err.(CycleError)
	assert.Equal(t, 4, len(cycerr.cycles))
	assert.Equal(t, []int{0, 2, 4, 6, 2}, cycerr.cycles[0])
	assert.Equal(t, []int{0, 2, 4, 8, 0}, cycerr.cycles[1])
	assert.Equal(t, []int{1, 3, 5, 7, 3}, cycerr.cycles[2])
	assert.Equal(t, []int{1, 3, 5, 9, 1}, cycerr.cycles[3])
}

func Test_DAG_DFS_error(t *testing.T) {
	tdag := newtestdag()
	tdag.add("0", "2", "4")
	tdag.add("1", "3", "5")
	tdag.add("2", "4")
	tdag.add("3", "5")
	tdag.add("4", "3", "2") // dependency cycle goes unreported
	tdag.add("5")
	dag := tdag.finish()

	visited := make([]int, 0)
	visit := func(id int) error {
		visited = append(visited, id)
		if id == 4 {
			return errors.New("bite me")
		}
		return nil
	}

	err := dag.DFS(bit.New(0), visit)
	assert.Equal(t, "bite me", err.Error())
	assert.Equal(t, []int{5, 3, 4}, visited)
}

func Test_DAG_FindRelevantNodes(t *testing.T) {
	dag := makeSimpleGraph()
	goal := bit.New(0, 1) // all final targets: tool1, tool2
	relevant := dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{0,1,2,3,4,5,6,7,8,9,10,11}", setToString(relevant))

	// goal = {tool1} ==>
	// sources = {tool1.c, misc.h, misc.c, util.h, util.c}
	goal = bit.New(0)
	relevant = dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{0,2,3,4,6,7,8,9,10}", setToString(relevant))

	// goal = {tool2} ==>
	// sources = {util.h, util.c, tool2.c}
	goal = bit.New(1)
	relevant = dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{1,4,5,9,10,11}", setToString(relevant))
}

func Test_DAG_MarkSources(t *testing.T) {
	dag := makeSimpleGraph()

	// initial sanity check
	assert.Equal(t, UNKNOWN, dag.lookup("tool1.c").State())
	assert.Equal(t, UNKNOWN, dag.lookup("tool1.o").State())<commit_msg>dag: add missing unit test for DAG.AddManyParents()<commit_after>// Copyright © 2012-2013, <NAME>. All rights reserved.
// Use of this source code is governed by a BSD-style license that can
// be found in the LICENSE.txt file.

package dag

import (
	"bytes"
	"errors"
	"reflect"
	"strconv"
	"testing"

	"code.google.com/p/go-bit/bit"
	"github.com/stretchrcom/testify/assert"

	"fubsy/testutils"
	"fubsy/types"
)

func Test_DAG_add_lookup(t *testing.T) {
	dag := NewDAG()
	outnode := dag.lookup("foo")
	assert.Nil(t, outnode)

	innode := NewStubNode("foo")
	_, outnode = dag.addNode(innode)
	assert.True(t, outnode == innode)
	assert.True(t, innode == dag.nodes[0].(*StubNode))

	outnode = dag.lookup("foo")
	assert.True(t, outnode.(*StubNode) == innode)

	assert.Nil(t, dag.lookup("bar"))
}

func Test_DAG_FindFinalTargets(t *testing.T) {
	dag := makeSimpleGraph()
	targets := (*bit.Set)(dag.FindFinalTargets())
	assert.Equal(t, "{0, 1}", targets.String())
}

func Test_DAG_DFS(t *testing.T) {
	// 0: a -> {c, f, h}
	// 1: b -> {d, f, g, h}
	// 2: c -> {b, e}
	// 3: d -> {g}
	// 4: e -> {}
	// 5: f -> {g}
	// 6: g -> {}
	// 7: h -> {}
	// original sources: {e, g, h} = {4, 6, 7}
	// final targets:    {a} = {0}

	tdag := newtestdag()
	tdag.add("a", "c", "f", "h")
	tdag.add("b", "d", "f", "g", "h")
	tdag.add("c", "b", "e")
	tdag.add("d", "g")
	tdag.add("e")
	tdag.add("f", "g")
	tdag.add("g")
	tdag.add("h")
	dag := tdag.finish()

	actual := []string{}
	visit := func(id int) error {
		actual = append(actual, dag.nodes[id].Name())
		return nil
	}

	assertDFS := func(start *bit.Set, expect []string) {
		actual = actual[0:0]
		dag.DFS(start, visit)
		assert.Equal(t, expect, actual)
	}

	start := bit.New()
	start.AddRange(0, 7)
	expect := []string{"g", "d", "f", "h", "b", "e", "c", "a"}
	assertDFS(start, expect)

	// start nodes: {c, f}
	start = bit.New(2, 5)
	expect = []string{"g", "d", "f", "h", "b", "e", "c"}
	assertDFS(start, expect)

	// start nodes: {d, f}
	start = bit.New(3, 5)
	expect = []string{"g", "d", "f"}
	assertDFS(start, expect)
}

func Test_DAG_DFS_cycle(t *testing.T) {
	var tdag *testdag
	var dag *DAG
	var err error

	visit := func(id int) error { return nil }

	tdag = newtestdag()
	tdag.add("0", "1")
	tdag.add("1", "0")
	dag = tdag.finish()
	err = dag.DFS(NodeSet(bit.New(0, 1)), visit)
	assert.Equal(t, "found 1 dependency cycles:\n  0 -> 1 -> 0", err.Error())

	// degenerate case
	tdag = newtestdag()
	tdag.add("0", "0")
	dag = tdag.finish()
	err = dag.DFS(NodeSet(bit.New(0)), visit)
	assert.Equal(t, "found 1 dependency cycles:\n  0 -> 0", err.Error())

	// weird case: two disconnected isomorphic graphs stuck in the
	// same data structure; each has two discernible cycles:
	//   0 -> 2 -> 4 -> 6 -> 2
	//   0 -> 2 -> 4 -> 8 -> 0
	//   1 -> 3 -> 5 -> 7 -> 3
	//   1 -> 3 -> 5 -> 9 -> 1
	tdag = newtestdag()
	tdag.add("0", "2", "4")
	tdag.add("1", "3", "5")
	tdag.add("2", "4")
	tdag.add("3", "5")
	tdag.add("4", "6", "8")
	tdag.add("5", "7", "9")
	tdag.add("6", "2")
	tdag.add("7", "3")
	tdag.add("8", "0")
	tdag.add("9", "1")
	dag = tdag.finish()
	start := bit.New()
	start.AddRange(0, 9)
	err = dag.DFS(NodeSet(start), visit)
	cycerr := err.(CycleError)
	assert.Equal(t, 4, len(cycerr.cycles))
	assert.Equal(t, []int{0, 2, 4, 6, 2}, cycerr.cycles[0])
	assert.Equal(t, []int{0, 2, 4, 8, 0}, cycerr.cycles[1])
	assert.Equal(t, []int{1, 3, 5, 7, 3}, cycerr.cycles[2])
	assert.Equal(t, []int{1, 3, 5, 9, 1}, cycerr.cycles[3])
}

func Test_DAG_DFS_error(t *testing.T) {
	tdag := newtestdag()
	tdag.add("0", "2", "4")
	tdag.add("1", "3", "5")
	tdag.add("2", "4")
	tdag.add("3", "5")
	tdag.add("4", "3", "2") // dependency cycle goes unreported
	tdag.add("5")
	dag := tdag.finish()

	visited := make([]int, 0)
	visit := func(id int) error {
		visited = append(visited, id)
		if id == 4 {
			return errors.New("bite me")
		}
		return nil
	}

	err := dag.DFS(bit.New(0), visit)
	assert.Equal(t, "bite me", err.Error())
	assert.Equal(t, []int{5, 3, 4}, visited)
}

func Test_DAG_AddManyParents(t *testing.T) {
	dag := NewDAG()
	node0 := MakeStubNode(dag, "0")
	node1 := MakeStubNode(dag, "1")
	node2 := MakeStubNode(dag, "2")
	node3 := MakeStubNode(dag, "3")

	dag.AddManyParents([]Node{node0}, []Node{node1, node2, node3})
	dag.AddManyParents([]Node{node1, node2}, []Node{node3})
	buf := &bytes.Buffer{}
	dag.Dump(buf, "")
	expect := `0000: 0 (StubNode, state UNKNOWN)
  parents:
    0001: 1
    0002: 2
    0003: 3
0001: 1 (StubNode, state UNKNOWN)
  parents:
    0003: 3
0002: 2 (StubNode, state UNKNOWN)
  parents:
    0003: 3
0003: 3 (StubNode, state UNKNOWN)
`
	actual := string(buf.Bytes())
	assert.Equal(t, expect, actual,
		"expected:\n%s\nbut got:\n%s", expect, actual)
}

func Test_DAG_FindRelevantNodes(t *testing.T) {
	dag := makeSimpleGraph()
	goal := bit.New(0, 1) // all final targets: tool1, tool2
	relevant := dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{0,1,2,3,4,5,6,7,8,9,10,11}", setToString(relevant))

	// goal = {tool1} ==>
	// sources = {tool1.c, misc.h, misc.c, util.h, util.c}
	goal = bit.New(0)
	relevant = dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{0,2,3,4,6,7,8,9,10}", setToString(relevant))

	// goal = {tool2} ==>
	// sources = {util.h, util.c, tool2.c}
	goal = bit.New(1)
	relevant = dag.FindRelevantNodes(NodeSet(goal))
	assert.Equal(t, "{1,4,5,9,10,11}", setToString(relevant))
}

func Test_DAG_MarkSources(t *testing.T) {
	dag := makeSimpleGraph()

	// initial sanity check
	assert.Equal(t, UNKNOWN, dag.lookup("tool1.c").State())
	assert.Equal(t, UNKNOWN, dag.lookup("tool1.o").State())
{'fraction_non_alphanumeric': 0.2314121037463977, 'fraction_numerical': 0.040730067243035545, 'mean_word_length': 3.65608228980322, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5493112', 'n_tokens_mistral': 4842, 'n_tokens_neox': 4552, 'n_words': 1049}