merkledag_test.go 16.5 KB
Newer Older
1
package merkledag_test
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
2 3

import (
4
	"bytes"
Jeromy's avatar
Jeromy committed
5
	"context"
6
	"encoding/json"
7
	"errors"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
8
	"fmt"
9 10
	"io"
	"io/ioutil"
11
	"math/rand"
12
	"strings"
13
	"sync"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
14
	"testing"
15
	"time"
16

Jeromy's avatar
Jeromy committed
17 18 19
	. "github.com/ipfs/go-merkledag"
	mdpb "github.com/ipfs/go-merkledag/pb"
	dstest "github.com/ipfs/go-merkledag/test"
Jeromy's avatar
Jeromy committed
20

Jeromy's avatar
Jeromy committed
21 22 23 24 25 26 27
	blocks "github.com/ipfs/go-block-format"
	bserv "github.com/ipfs/go-blockservice"
	bstest "github.com/ipfs/go-blockservice/test"
	cid "github.com/ipfs/go-cid"
	offline "github.com/ipfs/go-ipfs-exchange-offline"
	u "github.com/ipfs/go-ipfs-util"
	ipld "github.com/ipfs/go-ipld-format"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
28 29
)

30 31
// makeDepthTestingGraph makes a small DAG with two levels. The level-two
// nodes are both children of the root and of one of the level 1 nodes.
32
// This is meant to test the Walk*Depth functions.
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
func makeDepthTestingGraph(t *testing.T, ds ipld.DAGService) ipld.Node {
	root := NodeWithData(nil)
	l11 := NodeWithData([]byte("leve1_node1"))
	l12 := NodeWithData([]byte("leve1_node2"))
	l21 := NodeWithData([]byte("leve2_node1"))
	l22 := NodeWithData([]byte("leve2_node2"))
	l23 := NodeWithData([]byte("leve2_node3"))

	l11.AddNodeLink(l21.Cid().String(), l21)
	l11.AddNodeLink(l22.Cid().String(), l22)
	l11.AddNodeLink(l23.Cid().String(), l23)

	root.AddNodeLink(l11.Cid().String(), l11)
	root.AddNodeLink(l12.Cid().String(), l12)
	root.AddNodeLink(l23.Cid().String(), l23)

	ctx := context.Background()
	for _, n := range []ipld.Node{l23, l22, l21, l12, l11, root} {
		err := ds.Add(ctx, n)
		if err != nil {
			t.Fatal(err)
		}
	}

	return root
}

// Check that all children of root are in the given set and in the datastore
61
func traverseAndCheck(t *testing.T, root ipld.Node, ds ipld.DAGService, hasF func(c cid.Cid) bool) {
62 63 64 65 66 67 68 69 70 71 72 73 74 75
	// traverse dag and check
	for _, lnk := range root.Links() {
		c := lnk.Cid
		if !hasF(c) {
			t.Fatal("missing key in set! ", lnk.Cid.String())
		}
		child, err := ds.Get(context.Background(), c)
		if err != nil {
			t.Fatal(err)
		}
		traverseAndCheck(t, child, ds, hasF)
	}
}

Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
76 77
func TestNode(t *testing.T) {

78 79 80
	n1 := NodeWithData([]byte("beep"))
	n2 := NodeWithData([]byte("boop"))
	n3 := NodeWithData([]byte("beep boop"))
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
81 82 83 84 85 86 87
	if err := n3.AddNodeLink("beep-link", n1); err != nil {
		t.Error(err)
	}
	if err := n3.AddNodeLink("boop-link", n2); err != nil {
		t.Error(err)
	}

88
	printn := func(name string, n *ProtoNode) {
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
89
		fmt.Println(">", name)
90
		fmt.Println("data:", string(n.Data()))
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
91 92

		fmt.Println("links:")
93 94
		for _, l := range n.Links() {
			fmt.Println("-", l.Name, l.Size, l.Cid)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
95 96
		}

97
		e, err := n.EncodeProtobuf(false)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
98 99 100 101 102 103
		if err != nil {
			t.Error(err)
		} else {
			fmt.Println("encoded:", e)
		}

Jeromy's avatar
Jeromy committed
104
		h := n.Multihash()
Jeromy's avatar
Jeromy committed
105 106
		k := n.Cid().Hash()
		if k.String() != h.String() {
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
107 108 109 110
			t.Error("Key is not equivalent to multihash")
		} else {
			fmt.Println("key: ", k)
		}
111 112

		SubtestNodeStat(t, n)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
113 114 115 116 117 118
	}

	printn("beep", n1)
	printn("boop", n2)
	printn("beep boop", n3)
}
119

120
func SubtestNodeStat(t *testing.T, n *ProtoNode) {
121
	enc, err := n.EncodeProtobuf(true)
122
	if err != nil {
123
		t.Error("n.EncodeProtobuf(true) failed")
124 125 126 127 128 129 130 131 132
		return
	}

	cumSize, err := n.Size()
	if err != nil {
		t.Error("n.Size() failed")
		return
	}

Jeromy's avatar
Jeromy committed
133
	k := n.Cid()
134

135
	expected := ipld.NodeStat{
136
		NumLinks:       len(n.Links()),
137
		BlockSize:      len(enc),
138 139
		LinksSize:      len(enc) - len(n.Data()), // includes framing.
		DataSize:       len(n.Data()),
140
		CumulativeSize: int(cumSize),
Jeromy's avatar
Jeromy committed
141
		Hash:           k.String(),
142 143 144 145 146 147 148 149
	}

	actual, err := n.Stat()
	if err != nil {
		t.Error("n.Stat() failed")
		return
	}

150
	if expected != *actual {
151
		t.Errorf("n.Stat incorrect.\nexpect: %s\nactual: %s", expected, actual)
152 153 154 155 156
	} else {
		fmt.Printf("n.Stat correct: %s\n", actual)
	}
}

157 158 159
type devZero struct{}

func (_ devZero) Read(b []byte) (int, error) {
rht's avatar
rht committed
160
	for i := range b {
161 162 163 164 165
		b[i] = 0
	}
	return len(b), nil
}

166
func TestBatchFetch(t *testing.T) {
Jeromy's avatar
Jeromy committed
167 168
	read := io.LimitReader(u.NewTimeSeededRand(), 1024*32)
	runBatchFetchTest(t, read)
169
}
170 171

func TestBatchFetchDupBlock(t *testing.T) {
Jeromy's avatar
Jeromy committed
172 173
	read := io.LimitReader(devZero{}, 1024*32)
	runBatchFetchTest(t, read)
174 175
}

176 177 178 179 180 181 182
// makeTestDAG creates a simple DAG from the data in a reader.
// First, a node is created from each 512 bytes of data from the reader
// (like a the Size chunker would do). Then all nodes are added as children
// to a root node, which is returned.
func makeTestDAG(t *testing.T, read io.Reader, ds ipld.DAGService) ipld.Node {
	p := make([]byte, 512)
	nodes := []*ProtoNode{}
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197

	for {
		n, err := io.ReadFull(read, p)
		if err == io.EOF {
			break
		}

		if err != nil {
			t.Fatal(err)
		}

		if n != len(p) {
			t.Fatal("should have read 512 bytes from the reader")
		}

198 199 200 201 202 203 204 205
		protoNode := NodeWithData(p)
		nodes = append(nodes, protoNode)
	}

	ctx := context.Background()
	// Add a root referencing all created nodes
	root := NodeWithData(nil)
	for _, n := range nodes {
206 207 208 209 210
		err := root.AddNodeLink(n.Cid().String(), n)
		if err != nil {
			t.Fatal(err)
		}
		err = ds.Add(ctx, n)
211 212 213 214
		if err != nil {
			t.Fatal(err)
		}
	}
215
	err := ds.Add(ctx, root)
216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
	if err != nil {
		t.Fatal(err)
	}
	return root
}

// makeTestDAGReader takes the root node as returned by makeTestDAG and
// provides a reader that reads all the RawData from that node and its children.
func makeTestDAGReader(t *testing.T, root ipld.Node, ds ipld.DAGService) io.Reader {
	ctx := context.Background()
	buf := new(bytes.Buffer)
	buf.Write(root.RawData())
	for _, l := range root.Links() {
		n, err := ds.Get(ctx, l.Cid)
		if err != nil {
			t.Fatal(err)
		}
		_, err = buf.Write(n.RawData())
		if err != nil {
			t.Fatal(err)
		}
	}
	return buf
}

Jeromy's avatar
Jeromy committed
241
func runBatchFetchTest(t *testing.T, read io.Reader) {
242
	ctx := context.Background()
243
	var dagservs []ipld.DAGService
244
	for _, bsi := range bstest.Mocks(5) {
245 246
		dagservs = append(dagservs, NewDAGService(bsi))
	}
Jeromy's avatar
Jeromy committed
247

248
	root := makeTestDAG(t, read, dagservs[0])
Jeromy's avatar
Jeromy committed
249

250 251
	t.Log("finished setup.")

252
	dagr := makeTestDAGReader(t, root, dagservs[0])
Jeromy's avatar
Jeromy committed
253 254

	expected, err := ioutil.ReadAll(dagr)
255 256 257 258
	if err != nil {
		t.Fatal(err)
	}

259
	err = dagservs[0].Add(ctx, root)
260 261 262 263 264 265
	if err != nil {
		t.Fatal(err)
	}

	t.Log("Added file to first node.")

Jeromy's avatar
Jeromy committed
266
	c := root.Cid()
267

268
	wg := sync.WaitGroup{}
269 270
	errs := make(chan error)

271
	for i := 1; i < len(dagservs); i++ {
272
		wg.Add(1)
273
		go func(i int) {
274
			defer wg.Done()
Jeromy's avatar
Jeromy committed
275
			first, err := dagservs[i].Get(ctx, c)
276
			if err != nil {
277
				errs <- err
278 279 280
			}
			fmt.Println("Got first node back.")

281 282 283 284
			firstpb, ok := first.(*ProtoNode)
			if !ok {
				errs <- ErrNotProtobuf
			}
285
			read := makeTestDAGReader(t, firstpb, dagservs[i])
286 287
			datagot, err := ioutil.ReadAll(read)
			if err != nil {
288
				errs <- err
289 290 291
			}

			if !bytes.Equal(datagot, expected) {
Łukasz Magiera's avatar
Łukasz Magiera committed
292
				errs <- errors.New("got bad data back")
293 294 295 296
			}
		}(i)
	}

297 298 299 300 301 302 303 304 305 306
	go func() {
		wg.Wait()
		close(errs)
	}()

	for err := range errs {
		if err != nil {
			t.Fatal(err)
		}
	}
307
}
308 309

func TestCantGet(t *testing.T) {
310
	ds := dstest.Mock()
311
	a := NodeWithData([]byte("A"))
312

Jeromy's avatar
Jeromy committed
313 314
	c := a.Cid()
	_, err := ds.Get(context.Background(), c)
315 316 317 318
	if !strings.Contains(err.Error(), "not found") {
		t.Fatal("expected err not found, got: ", err)
	}
}
319 320

func TestFetchGraph(t *testing.T) {
321
	var dservs []ipld.DAGService
322
	bsis := bstest.Mocks(2)
Jeromy's avatar
Jeromy committed
323 324 325
	for _, bsi := range bsis {
		dservs = append(dservs, NewDAGService(bsi))
	}
326 327

	read := io.LimitReader(u.NewTimeSeededRand(), 1024*32)
328
	root := makeTestDAG(t, read, dservs[0])
329

330
	err := FetchGraph(context.TODO(), root.Cid(), dservs[1])
331 332 333 334
	if err != nil {
		t.Fatal(err)
	}

Jeromy's avatar
Jeromy committed
335
	// create an offline dagstore and ensure all blocks were fetched
336
	bs := bserv.New(bsis[1].Blockstore(), offline.Exchange(bsis[1].Blockstore()))
337

338
	offlineDS := NewDAGService(bs)
Jeromy's avatar
Jeromy committed
339

340
	err = Walk(context.Background(), offlineDS.GetLinks, root.Cid(), func(_ cid.Cid) bool { return true })
341 342 343 344 345
	if err != nil {
		t.Fatal(err)
	}
}

346 347 348 349 350 351 352
func TestFetchGraphWithDepthLimit(t *testing.T) {
	type testcase struct {
		depthLim int
		setLen   int
	}

	tests := []testcase{
353 354 355 356 357
		testcase{1, 4},
		testcase{0, 1},
		testcase{-1, 6},
		testcase{2, 6},
		testcase{3, 6},
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
	}

	testF := func(t *testing.T, tc testcase) {
		var dservs []ipld.DAGService
		bsis := bstest.Mocks(2)
		for _, bsi := range bsis {
			dservs = append(dservs, NewDAGService(bsi))
		}

		root := makeDepthTestingGraph(t, dservs[0])

		err := FetchGraphWithDepthLimit(context.TODO(), root.Cid(), tc.depthLim, dservs[1])
		if err != nil {
			t.Fatal(err)
		}

		// create an offline dagstore and ensure all blocks were fetched
		bs := bserv.New(bsis[1].Blockstore(), offline.Exchange(bsis[1].Blockstore()))

		offlineDS := NewDAGService(bs)

		set := make(map[string]int)
380
		visitF := func(c cid.Cid, depth int) bool {
381 382 383 384 385 386 387 388
			if tc.depthLim < 0 || depth <= tc.depthLim {
				set[string(c.Bytes())] = depth
				return true
			}
			return false

		}

389
		err = WalkDepth(context.Background(), offlineDS.GetLinks, root.Cid(), visitF)
390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405
		if err != nil {
			t.Fatal(err)
		}

		if len(set) != tc.setLen {
			t.Fatalf("expected %d nodes but visited %d", tc.setLen, len(set))
		}
	}

	for _, tc := range tests {
		t.Run(fmt.Sprintf("depth limit %d", tc.depthLim), func(t *testing.T) {
			testF(t, tc)
		})
	}
}

406
func TestWalk(t *testing.T) {
407
	bsi := bstest.Mocks(1)
408 409 410
	ds := NewDAGService(bsi[0])

	read := io.LimitReader(u.NewTimeSeededRand(), 1024*1024)
411
	root := makeTestDAG(t, read, ds)
412

Jeromy's avatar
Jeromy committed
413
	set := cid.NewSet()
414

415
	err := Walk(context.Background(), ds.GetLinks, root.Cid(), set.Visit)
416 417 418 419
	if err != nil {
		t.Fatal(err)
	}

420
	traverseAndCheck(t, root, ds, set.Has)
421
}
422 423

func TestFetchFailure(t *testing.T) {
424 425
	ctx := context.Background()

426 427 428
	ds := dstest.Mock()
	ds_bad := dstest.Mock()

429
	top := new(ProtoNode)
430
	for i := 0; i < 10; i++ {
431
		nd := NodeWithData([]byte{byte('a' + i)})
432
		err := ds.Add(ctx, nd)
433 434 435 436
		if err != nil {
			t.Fatal(err)
		}

Hector Sanjuan's avatar
Hector Sanjuan committed
437
		err = top.AddNodeLink(fmt.Sprintf("AA%d", i), nd)
438 439 440 441 442 443
		if err != nil {
			t.Fatal(err)
		}
	}

	for i := 0; i < 10; i++ {
444
		nd := NodeWithData([]byte{'f', 'a' + byte(i)})
445
		err := ds_bad.Add(ctx, nd)
446 447 448 449
		if err != nil {
			t.Fatal(err)
		}

Hector Sanjuan's avatar
Hector Sanjuan committed
450
		err = top.AddNodeLink(fmt.Sprintf("BB%d", i), nd)
451 452 453 454 455
		if err != nil {
			t.Fatal(err)
		}
	}

456
	getters := ipld.GetDAG(ctx, ds, top)
457
	for i, getter := range getters {
458
		_, err := getter.Get(ctx)
459 460 461 462 463 464 465 466
		if err != nil && i < 10 {
			t.Fatal(err)
		}
		if err == nil && i >= 10 {
			t.Fatal("should have failed request")
		}
	}
}
467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487

func TestUnmarshalFailure(t *testing.T) {
	badData := []byte("hello world")

	_, err := DecodeProtobuf(badData)
	if err == nil {
		t.Fatal("shouldnt succeed to parse this")
	}

	// now with a bad link
	pbn := &mdpb.PBNode{Links: []*mdpb.PBLink{{Hash: []byte("not a multihash")}}}
	badlink, err := pbn.Marshal()
	if err != nil {
		t.Fatal(err)
	}

	_, err = DecodeProtobuf(badlink)
	if err == nil {
		t.Fatal("should have failed to parse node with bad link")
	}

488
	n := &ProtoNode{}
489 490
	n.Marshal()
}
Jeromy's avatar
Jeromy committed
491 492

func TestBasicAddGet(t *testing.T) {
493 494
	ctx := context.Background()

Jeromy's avatar
Jeromy committed
495
	ds := dstest.Mock()
496
	nd := new(ProtoNode)
Jeromy's avatar
Jeromy committed
497

498
	err := ds.Add(ctx, nd)
Jeromy's avatar
Jeromy committed
499 500 501 502
	if err != nil {
		t.Fatal(err)
	}

503
	out, err := ds.Get(ctx, nd.Cid())
Jeromy's avatar
Jeromy committed
504 505 506 507 508 509 510 511
	if err != nil {
		t.Fatal(err)
	}

	if !nd.Cid().Equals(out.Cid()) {
		t.Fatal("output didnt match input")
	}
}
512 513

func TestGetRawNodes(t *testing.T) {
514 515
	ctx := context.Background()

516 517 518 519
	rn := NewRawNode([]byte("test"))

	ds := dstest.Mock()

520
	err := ds.Add(ctx, rn)
521 522 523 524
	if err != nil {
		t.Fatal(err)
	}

525
	if !rn.Cid().Equals(rn.Cid()) {
526 527 528
		t.Fatal("output cids didnt match")
	}

529
	out, err := ds.Get(ctx, rn.Cid())
530 531 532 533 534 535 536 537 538 539 540 541
	if err != nil {
		t.Fatal(err)
	}

	if !bytes.Equal(out.RawData(), []byte("test")) {
		t.Fatal("raw block should match input data")
	}

	if out.Links() != nil {
		t.Fatal("raw blocks shouldnt have links")
	}

542
	if out.Tree("", -1) != nil {
543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571
		t.Fatal("tree should return no paths in a raw block")
	}

	size, err := out.Size()
	if err != nil {
		t.Fatal(err)
	}
	if size != 4 {
		t.Fatal("expected size to be 4")
	}

	ns, err := out.Stat()
	if err != nil {
		t.Fatal(err)
	}

	if ns.DataSize != 4 {
		t.Fatal("expected size to be 4, got: ", ns.DataSize)
	}

	_, _, err = out.Resolve([]string{"foo"})
	if err != ErrLinkNotFound {
		t.Fatal("shouldnt find links under raw blocks")
	}
}

func TestProtoNodeResolve(t *testing.T) {

	nd := new(ProtoNode)
572
	nd.SetLinks([]*ipld.Link{{Name: "foo"}})
573

574
	lnk, left, err := nd.ResolveLink([]string{"foo", "bar"})
575 576 577 578 579 580 581 582 583 584 585 586
	if err != nil {
		t.Fatal(err)
	}

	if len(left) != 1 || left[0] != "bar" {
		t.Fatal("expected the single path element 'bar' to remain")
	}

	if lnk.Name != "foo" {
		t.Fatal("how did we get anything else?")
	}

587
	tvals := nd.Tree("", -1)
588 589 590 591
	if len(tvals) != 1 || tvals[0] != "foo" {
		t.Fatal("expected tree to return []{\"foo\"}")
	}
}
592 593

func TestCidRetention(t *testing.T) {
594 595
	ctx := context.Background()

596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612
	nd := new(ProtoNode)
	nd.SetData([]byte("fooooo"))

	pref := nd.Cid().Prefix()
	pref.Version = 1

	c2, err := pref.Sum(nd.RawData())
	if err != nil {
		t.Fatal(err)
	}

	blk, err := blocks.NewBlockWithCid(nd.RawData(), c2)
	if err != nil {
		t.Fatal(err)
	}

	bs := dstest.Bserv()
613
	err = bs.AddBlock(blk)
614 615 616 617 618
	if err != nil {
		t.Fatal(err)
	}

	ds := NewDAGService(bs)
619
	out, err := ds.Get(ctx, c2)
620 621 622 623 624 625 626 627
	if err != nil {
		t.Fatal(err)
	}

	if !out.Cid().Equals(c2) {
		t.Fatal("output cid didnt match")
	}
}
628 629

func TestCidRawDoesnNeedData(t *testing.T) {
630
	srv := NewDAGService(dstest.Bserv())
631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
	nd := NewRawNode([]byte("somedata"))

	ctx, cancel := context.WithTimeout(context.Background(), 10*time.Second)
	defer cancel()

	// there is no data for this node in the blockservice
	// so dag service can't load it
	links, err := srv.GetLinks(ctx, nd.Cid())
	if err != nil {
		t.Fatal(err)
	}
	if len(links) != 0 {
		t.Fatal("raw node shouldn't have any links")
	}
}
646

647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667
func TestRawToJson(t *testing.T) {
	rawData := []byte{1, 2, 3, 4}
	nd := NewRawNode(rawData)
	encoded, err := nd.MarshalJSON()
	if err != nil {
		t.Fatal(err)
	}
	var res interface{}
	err = json.Unmarshal(encoded, &res)
	if err != nil {
		t.Fatal(err)
	}
	resBytes, ok := res.(string)
	if !ok {
		t.Fatal("expected to marshal to a string")
	}
	if string(rawData) != resBytes {
		t.Fatal("failed to round-trip bytes")
	}
}

Steven Allen's avatar
Steven Allen committed
668 669 670 671 672 673 674 675 676
func TestGetManyDuplicate(t *testing.T) {
	ctx := context.Background()

	srv := NewDAGService(dstest.Bserv())

	nd := NodeWithData([]byte("foo"))
	if err := srv.Add(ctx, nd); err != nil {
		t.Fatal(err)
	}
677
	nds := srv.GetMany(ctx, []cid.Cid{nd.Cid(), nd.Cid(), nd.Cid()})
Steven Allen's avatar
Steven Allen committed
678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697
	out, ok := <-nds
	if !ok {
		t.Fatal("expecting node foo")
	}
	if out.Err != nil {
		t.Fatal(out.Err)
	}
	if !out.Node.Cid().Equals(nd.Cid()) {
		t.Fatal("got wrong node")
	}
	out, ok = <-nds
	if ok {
		if out.Err != nil {
			t.Fatal(out.Err)
		} else {
			t.Fatal("expecting no more nodes")
		}
	}
}

698
func TestEnumerateAsyncFailsNotFound(t *testing.T) {
699 700
	ctx := context.Background()

701 702 703 704
	a := NodeWithData([]byte("foo1"))
	b := NodeWithData([]byte("foo2"))
	c := NodeWithData([]byte("foo3"))
	d := NodeWithData([]byte("foo4"))
Steven Allen's avatar
Steven Allen committed
705
	e := NodeWithData([]byte("foo5"))
706 707

	ds := dstest.Mock()
708
	for _, n := range []ipld.Node{a, b, c} {
709
		err := ds.Add(ctx, n)
710 711 712 713 714 715
		if err != nil {
			t.Fatal(err)
		}
	}

	parent := new(ProtoNode)
Hector Sanjuan's avatar
Hector Sanjuan committed
716
	if err := parent.AddNodeLink("a", a); err != nil {
717 718 719
		t.Fatal(err)
	}

Hector Sanjuan's avatar
Hector Sanjuan committed
720
	if err := parent.AddNodeLink("b", b); err != nil {
721 722 723
		t.Fatal(err)
	}

Hector Sanjuan's avatar
Hector Sanjuan committed
724
	if err := parent.AddNodeLink("c", c); err != nil {
725 726 727
		t.Fatal(err)
	}

Hector Sanjuan's avatar
Hector Sanjuan committed
728
	if err := parent.AddNodeLink("d", d); err != nil {
729 730 731
		t.Fatal(err)
	}

Steven Allen's avatar
Steven Allen committed
732 733 734 735
	if err := parent.AddNodeLink("e", e); err != nil {
		t.Fatal(err)
	}

736
	err := ds.Add(ctx, parent)
737 738 739 740 741
	if err != nil {
		t.Fatal(err)
	}

	cset := cid.NewSet()
742
	err = Walk(ctx, GetLinksDirect(ds), parent.Cid(), cset.Visit)
743 744 745 746
	if err == nil {
		t.Fatal("this should have failed")
	}
}
747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774

func TestProgressIndicator(t *testing.T) {
	testProgressIndicator(t, 5)
}

func TestProgressIndicatorNoChildren(t *testing.T) {
	testProgressIndicator(t, 0)
}

func testProgressIndicator(t *testing.T, depth int) {
	ds := dstest.Mock()

	top, numChildren := mkDag(ds, depth)

	v := new(ProgressTracker)
	ctx := v.DeriveContext(context.Background())

	err := FetchGraph(ctx, top, ds)
	if err != nil {
		t.Fatal(err)
	}

	if v.Value() != numChildren+1 {
		t.Errorf("wrong number of children reported in progress indicator, expected %d, got %d",
			numChildren+1, v.Value())
	}
}

775
func mkDag(ds ipld.DAGService, depth int) (cid.Cid, int) {
776 777
	ctx := context.Background()

778 779 780 781 782 783 784
	totalChildren := 0
	f := func() *ProtoNode {
		p := new(ProtoNode)
		buf := make([]byte, 16)
		rand.Read(buf)

		p.SetData(buf)
785
		err := ds.Add(ctx, p)
786 787 788 789 790 791 792 793 794 795
		if err != nil {
			panic(err)
		}
		return p
	}

	for i := 0; i < depth; i++ {
		thisf := f
		f = func() *ProtoNode {
			pn := mkNodeWithChildren(thisf, 10)
796
			err := ds.Add(ctx, pn)
797 798 799 800 801 802 803 804 805
			if err != nil {
				panic(err)
			}
			totalChildren += 10
			return pn
		}
	}

	nd := f()
806
	err := ds.Add(ctx, nd)
807 808 809 810
	if err != nil {
		panic(err)
	}

811
	return nd.Cid(), totalChildren
812 813 814 815 816 817 818
}

func mkNodeWithChildren(getChild func() *ProtoNode, width int) *ProtoNode {
	cur := new(ProtoNode)

	for i := 0; i < width; i++ {
		c := getChild()
Hector Sanjuan's avatar
Hector Sanjuan committed
819
		if err := cur.AddNodeLink(fmt.Sprint(i), c); err != nil {
820 821 822 823 824 825
			panic(err)
		}
	}

	return cur
}