merkledag_test.go 13.9 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
	"errors"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
7
	"fmt"
8 9
	"io"
	"io/ioutil"
10
	"math/rand"
11
	"strings"
12
	"sync"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
13
	"testing"
14
	"time"
15

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

Steven Allen's avatar
Steven Allen committed
22
	u "gx/ipfs/QmNiJuT8Ja3hMVpBHXv3Q6dwmperaQ6JjLtpMQgMCD7xvx/go-ipfs-util"
23
	offline "gx/ipfs/QmWM5HhdG5ZQNyHQ5XhMdGmV9CvLpFynQfGpTxN2MEM7Lc/go-ipfs-exchange-offline"
Steven Allen's avatar
Steven Allen committed
24
	cid "gx/ipfs/QmcZfnkapfECQGcLZaf9B79NRg7cRa9EnZh4LSbkCzwNvY/go-cid"
25
	ipld "gx/ipfs/Qme5bWv7wtjUNGsK2BNGVUFPKiuxWrsqrtvYwCLRw8YFES/go-ipld-format"
26
	blocks "gx/ipfs/Qmej7nf81hi2x2tvjRBF3mcp74sQyuDH4VMYDGd1YtXjb2/go-block-format"
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
27 28 29 30
)

func TestNode(t *testing.T) {

31 32 33
	n1 := NodeWithData([]byte("beep"))
	n2 := NodeWithData([]byte("boop"))
	n3 := NodeWithData([]byte("beep boop"))
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
34 35 36 37 38 39 40
	if err := n3.AddNodeLink("beep-link", n1); err != nil {
		t.Error(err)
	}
	if err := n3.AddNodeLink("boop-link", n2); err != nil {
		t.Error(err)
	}

41
	printn := func(name string, n *ProtoNode) {
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
42
		fmt.Println(">", name)
43
		fmt.Println("data:", string(n.Data()))
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
44 45

		fmt.Println("links:")
46 47
		for _, l := range n.Links() {
			fmt.Println("-", l.Name, l.Size, l.Cid)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
48 49
		}

50
		e, err := n.EncodeProtobuf(false)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
51 52 53 54 55 56
		if err != nil {
			t.Error(err)
		} else {
			fmt.Println("encoded:", e)
		}

Jeromy's avatar
Jeromy committed
57
		h := n.Multihash()
Jeromy's avatar
Jeromy committed
58 59
		k := n.Cid().Hash()
		if k.String() != h.String() {
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
60 61 62 63
			t.Error("Key is not equivalent to multihash")
		} else {
			fmt.Println("key: ", k)
		}
64 65

		SubtestNodeStat(t, n)
Juan Batiz-Benet's avatar
Juan Batiz-Benet committed
66 67 68 69 70 71
	}

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

73
func SubtestNodeStat(t *testing.T, n *ProtoNode) {
74
	enc, err := n.EncodeProtobuf(true)
75
	if err != nil {
76
		t.Error("n.EncodeProtobuf(true) failed")
77 78 79 80 81 82 83 84 85
		return
	}

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

Jeromy's avatar
Jeromy committed
86
	k := n.Cid()
87

88
	expected := ipld.NodeStat{
89
		NumLinks:       len(n.Links()),
90
		BlockSize:      len(enc),
91 92
		LinksSize:      len(enc) - len(n.Data()), // includes framing.
		DataSize:       len(n.Data()),
93
		CumulativeSize: int(cumSize),
Jeromy's avatar
Jeromy committed
94
		Hash:           k.String(),
95 96 97 98 99 100 101 102
	}

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

103
	if expected != *actual {
104
		t.Errorf("n.Stat incorrect.\nexpect: %s\nactual: %s", expected, actual)
105 106 107 108 109
	} else {
		fmt.Printf("n.Stat correct: %s\n", actual)
	}
}

110 111 112
type devZero struct{}

func (_ devZero) Read(b []byte) (int, error) {
rht's avatar
rht committed
113
	for i := range b {
114 115 116 117 118
		b[i] = 0
	}
	return len(b), nil
}

119
func TestBatchFetch(t *testing.T) {
Jeromy's avatar
Jeromy committed
120 121
	read := io.LimitReader(u.NewTimeSeededRand(), 1024*32)
	runBatchFetchTest(t, read)
122
}
123 124

func TestBatchFetchDupBlock(t *testing.T) {
Jeromy's avatar
Jeromy committed
125 126
	read := io.LimitReader(devZero{}, 1024*32)
	runBatchFetchTest(t, read)
127 128
}

129 130 131 132 133 134 135
// 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{}
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150

	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")
		}

151 152 153 154 155 156 157 158 159 160 161 162 163 164
		protoNode := NodeWithData(p)
		nodes = append(nodes, protoNode)
	}

	ctx := context.Background()
	// Add a root referencing all created nodes
	root := NodeWithData(nil)
	for _, n := range nodes {
		root.AddNodeLink(n.Cid().String(), n)
		err := ds.Add(ctx, n)
		if err != nil {
			t.Fatal(err)
		}
	}
165
	err := ds.Add(ctx, root)
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
	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
191
func runBatchFetchTest(t *testing.T, read io.Reader) {
192
	ctx := context.Background()
193
	var dagservs []ipld.DAGService
194
	for _, bsi := range bstest.Mocks(5) {
195 196
		dagservs = append(dagservs, NewDAGService(bsi))
	}
Jeromy's avatar
Jeromy committed
197

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

200 201
	t.Log("finished setup.")

202
	dagr := makeTestDAGReader(t, root, dagservs[0])
Jeromy's avatar
Jeromy committed
203 204

	expected, err := ioutil.ReadAll(dagr)
205 206 207 208
	if err != nil {
		t.Fatal(err)
	}

209
	err = dagservs[0].Add(ctx, root)
210 211 212 213 214 215
	if err != nil {
		t.Fatal(err)
	}

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

Jeromy's avatar
Jeromy committed
216
	c := root.Cid()
217

218
	wg := sync.WaitGroup{}
219 220
	errs := make(chan error)

221
	for i := 1; i < len(dagservs); i++ {
222
		wg.Add(1)
223
		go func(i int) {
224
			defer wg.Done()
Jeromy's avatar
Jeromy committed
225
			first, err := dagservs[i].Get(ctx, c)
226
			if err != nil {
227
				errs <- err
228 229 230
			}
			fmt.Println("Got first node back.")

231 232 233 234
			firstpb, ok := first.(*ProtoNode)
			if !ok {
				errs <- ErrNotProtobuf
			}
235
			read := makeTestDAGReader(t, firstpb, dagservs[i])
236 237
			datagot, err := ioutil.ReadAll(read)
			if err != nil {
238
				errs <- err
239 240 241
			}

			if !bytes.Equal(datagot, expected) {
Łukasz Magiera's avatar
Łukasz Magiera committed
242
				errs <- errors.New("got bad data back")
243 244 245 246
			}
		}(i)
	}

247 248 249 250 251 252 253 254 255 256
	go func() {
		wg.Wait()
		close(errs)
	}()

	for err := range errs {
		if err != nil {
			t.Fatal(err)
		}
	}
257
}
258 259

func TestCantGet(t *testing.T) {
260
	ds := dstest.Mock()
261
	a := NodeWithData([]byte("A"))
262

Jeromy's avatar
Jeromy committed
263 264
	c := a.Cid()
	_, err := ds.Get(context.Background(), c)
265 266 267 268
	if !strings.Contains(err.Error(), "not found") {
		t.Fatal("expected err not found, got: ", err)
	}
}
269 270

func TestFetchGraph(t *testing.T) {
271
	var dservs []ipld.DAGService
272
	bsis := bstest.Mocks(2)
Jeromy's avatar
Jeromy committed
273 274 275
	for _, bsi := range bsis {
		dservs = append(dservs, NewDAGService(bsi))
	}
276 277

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

280
	err := FetchGraph(context.TODO(), root.Cid(), dservs[1])
281 282 283 284
	if err != nil {
		t.Fatal(err)
	}

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

288
	offlineDS := NewDAGService(bs)
Jeromy's avatar
Jeromy committed
289

290
	err = EnumerateChildren(context.Background(), offlineDS.GetLinks, root.Cid(), func(_ *cid.Cid) bool { return true })
291 292 293 294 295 296
	if err != nil {
		t.Fatal(err)
	}
}

func TestEnumerateChildren(t *testing.T) {
297
	bsi := bstest.Mocks(1)
298 299 300
	ds := NewDAGService(bsi[0])

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

Jeromy's avatar
Jeromy committed
303
	set := cid.NewSet()
304

305
	err := EnumerateChildren(context.Background(), ds.GetLinks, root.Cid(), set.Visit)
306 307 308 309
	if err != nil {
		t.Fatal(err)
	}

310 311
	var traverse func(n ipld.Node)
	traverse = func(n ipld.Node) {
312
		// traverse dag and check
313 314
		for _, lnk := range n.Links() {
			c := lnk.Cid
Jeromy's avatar
Jeromy committed
315
			if !set.Has(c) {
316
				t.Fatal("missing key in set! ", lnk.Cid.String())
317
			}
Jeromy's avatar
Jeromy committed
318
			child, err := ds.Get(context.Background(), c)
319 320 321 322 323 324 325 326 327
			if err != nil {
				t.Fatal(err)
			}
			traverse(child)
		}
	}

	traverse(root)
}
328 329

func TestFetchFailure(t *testing.T) {
330 331
	ctx := context.Background()

332 333 334
	ds := dstest.Mock()
	ds_bad := dstest.Mock()

335
	top := new(ProtoNode)
336
	for i := 0; i < 10; i++ {
337
		nd := NodeWithData([]byte{byte('a' + i)})
338
		err := ds.Add(ctx, nd)
339 340 341 342 343 344 345 346 347 348 349
		if err != nil {
			t.Fatal(err)
		}

		err = top.AddNodeLinkClean(fmt.Sprintf("AA%d", i), nd)
		if err != nil {
			t.Fatal(err)
		}
	}

	for i := 0; i < 10; i++ {
350
		nd := NodeWithData([]byte{'f', 'a' + byte(i)})
351
		err := ds_bad.Add(ctx, nd)
352 353 354 355 356 357 358 359 360 361
		if err != nil {
			t.Fatal(err)
		}

		err = top.AddNodeLinkClean(fmt.Sprintf("BB%d", i), nd)
		if err != nil {
			t.Fatal(err)
		}
	}

362
	getters := ipld.GetDAG(ctx, ds, top)
363
	for i, getter := range getters {
364
		_, err := getter.Get(ctx)
365 366 367 368 369 370 371 372
		if err != nil && i < 10 {
			t.Fatal(err)
		}
		if err == nil && i >= 10 {
			t.Fatal("should have failed request")
		}
	}
}
373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393

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")
	}

394
	n := &ProtoNode{}
395 396
	n.Marshal()
}
Jeromy's avatar
Jeromy committed
397 398

func TestBasicAddGet(t *testing.T) {
399 400
	ctx := context.Background()

Jeromy's avatar
Jeromy committed
401
	ds := dstest.Mock()
402
	nd := new(ProtoNode)
Jeromy's avatar
Jeromy committed
403

404
	err := ds.Add(ctx, nd)
Jeromy's avatar
Jeromy committed
405 406 407 408
	if err != nil {
		t.Fatal(err)
	}

409
	out, err := ds.Get(ctx, nd.Cid())
Jeromy's avatar
Jeromy committed
410 411 412 413 414 415 416 417
	if err != nil {
		t.Fatal(err)
	}

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

func TestGetRawNodes(t *testing.T) {
420 421
	ctx := context.Background()

422 423 424 425
	rn := NewRawNode([]byte("test"))

	ds := dstest.Mock()

426
	err := ds.Add(ctx, rn)
427 428 429 430
	if err != nil {
		t.Fatal(err)
	}

431
	if !rn.Cid().Equals(rn.Cid()) {
432 433 434
		t.Fatal("output cids didnt match")
	}

435
	out, err := ds.Get(ctx, rn.Cid())
436 437 438 439 440 441 442 443 444 445 446 447
	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")
	}

448
	if out.Tree("", -1) != nil {
449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
		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)
478
	nd.SetLinks([]*ipld.Link{{Name: "foo"}})
479

480
	lnk, left, err := nd.ResolveLink([]string{"foo", "bar"})
481 482 483 484 485 486 487 488 489 490 491 492
	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?")
	}

493
	tvals := nd.Tree("", -1)
494 495 496 497
	if len(tvals) != 1 || tvals[0] != "foo" {
		t.Fatal("expected tree to return []{\"foo\"}")
	}
}
498 499

func TestCidRetention(t *testing.T) {
500 501
	ctx := context.Background()

502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
	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()
519
	err = bs.AddBlock(blk)
520 521 522 523 524
	if err != nil {
		t.Fatal(err)
	}

	ds := NewDAGService(bs)
525
	out, err := ds.Get(ctx, c2)
526 527 528 529 530 531 532 533
	if err != nil {
		t.Fatal(err)
	}

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

func TestCidRawDoesnNeedData(t *testing.T) {
536
	srv := NewDAGService(dstest.Bserv())
537 538 539 540 541 542 543 544 545 546 547 548 549 550 551
	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")
	}
}
552

Steven Allen's avatar
Steven Allen committed
553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582
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)
	}
	nds := srv.GetMany(ctx, []*cid.Cid{nd.Cid(), nd.Cid(), nd.Cid()})
	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")
		}
	}
}

583
func TestEnumerateAsyncFailsNotFound(t *testing.T) {
584 585
	ctx := context.Background()

586 587 588 589 590 591
	a := NodeWithData([]byte("foo1"))
	b := NodeWithData([]byte("foo2"))
	c := NodeWithData([]byte("foo3"))
	d := NodeWithData([]byte("foo4"))

	ds := dstest.Mock()
592
	for _, n := range []ipld.Node{a, b, c} {
593
		err := ds.Add(ctx, n)
594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
		if err != nil {
			t.Fatal(err)
		}
	}

	parent := new(ProtoNode)
	if err := parent.AddNodeLinkClean("a", a); err != nil {
		t.Fatal(err)
	}

	if err := parent.AddNodeLinkClean("b", b); err != nil {
		t.Fatal(err)
	}

	if err := parent.AddNodeLinkClean("c", c); err != nil {
		t.Fatal(err)
	}

	if err := parent.AddNodeLinkClean("d", d); err != nil {
		t.Fatal(err)
	}

616
	err := ds.Add(ctx, parent)
617 618 619 620 621
	if err != nil {
		t.Fatal(err)
	}

	cset := cid.NewSet()
622
	err = EnumerateChildrenAsync(ctx, GetLinksDirect(ds), parent.Cid(), cset.Visit)
623 624 625 626
	if err == nil {
		t.Fatal("this should have failed")
	}
}
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654

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())
	}
}

655
func mkDag(ds ipld.DAGService, depth int) (*cid.Cid, int) {
656 657
	ctx := context.Background()

658 659 660 661 662 663 664
	totalChildren := 0
	f := func() *ProtoNode {
		p := new(ProtoNode)
		buf := make([]byte, 16)
		rand.Read(buf)

		p.SetData(buf)
665
		err := ds.Add(ctx, p)
666 667 668 669 670 671 672 673 674 675
		if err != nil {
			panic(err)
		}
		return p
	}

	for i := 0; i < depth; i++ {
		thisf := f
		f = func() *ProtoNode {
			pn := mkNodeWithChildren(thisf, 10)
676
			err := ds.Add(ctx, pn)
677 678 679 680 681 682 683 684 685
			if err != nil {
				panic(err)
			}
			totalChildren += 10
			return pn
		}
	}

	nd := f()
686
	err := ds.Add(ctx, nd)
687 688 689 690
	if err != nil {
		panic(err)
	}

691
	return nd.Cid(), totalChildren
692 693 694 695 696 697 698 699 700 701 702 703 704 705
}

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

	for i := 0; i < width; i++ {
		c := getChild()
		if err := cur.AddNodeLinkClean(fmt.Sprint(i), c); err != nil {
			panic(err)
		}
	}

	return cur
}