func readHdr(n *merkledag.Node) (*pb.Set, []byte, error) {
	hdrLenRaw, consumed := binary.Uvarint(n.Data())
	if consumed <= 0 {
		return nil, nil, errors.New("invalid Set header length")
	}
	buf := n.Data()[consumed:]
	if hdrLenRaw > uint64(len(buf)) {
		return nil, nil, errors.New("impossibly large Set header length")
	}
	// as hdrLenRaw was <= an int, we now know it fits in an int
	hdrLen := int(hdrLenRaw)
	var hdr pb.Set
	if err := proto.Unmarshal(buf[:hdrLen], &hdr); err != nil {
		return nil, nil, err
	}
	buf = buf[hdrLen:]

	if v := hdr.GetVersion(); v != 1 {
		return nil, nil, fmt.Errorf("unsupported Set version: %d", v)
	}
	if uint64(hdr.GetFanout()) > uint64(len(n.Links)) {
		return nil, nil, errors.New("impossibly large Fanout")
	}
	return &hdr, buf, nil
}

func (rw *RefWriter) writeRefsSingle(n *dag.Node) (int, error) {
	nkey, err := n.Key()
	if err != nil {
		return 0, err
	}

	if rw.skip(nkey) {
		return 0, nil
	}

	count := 0
	for _, l := range n.Links {
		lk := key.Key(l.Hash)

		if rw.skip(lk) {
			continue
		}

		if err := rw.WriteEdge(nkey, lk, l.Name); err != nil {
			return count, err
		}
		count++
	}
	return count, nil
}

// NewDagReader creates a new reader object that reads the data represented by
// the given node, using the passed in DAGService for data retreival
func NewDagReader(ctx context.Context, n *mdag.Node, serv mdag.DAGService) (*DagReader, error) {
	pb := new(ftpb.Data)
	if err := proto.Unmarshal(n.Data(), pb); err != nil {
		return nil, err
	}

	switch pb.GetType() {
	case ftpb.Data_Directory:
		// Dont allow reading directories
		return nil, ErrIsDir
	case ftpb.Data_Raw:
		fallthrough
	case ftpb.Data_File:
		return NewDataFileReader(ctx, n, pb, serv), nil
	case ftpb.Data_Metadata:
		if len(n.Links) == 0 {
			return nil, errors.New("incorrectly formatted metadata object")
		}
		child, err := n.Links[0].GetNode(ctx, serv)
		if err != nil {
			return nil, err
		}
		return NewDagReader(ctx, child, serv)
	case ftpb.Data_Symlink:
		return nil, ErrCantReadSymlinks
	default:
		return nil, ft.ErrUnrecognizedType
	}
}

//search serches nearest and bigger than stamp and update all DAG after calling func f if needed.
func (t *Thread) search(root *merkledag.Node, stamp time.Time,
	f func(bool, *merkledag.Node) (bool, error)) (*merkledag.Node, error) {
	link, err := getLinkName(root)
	if log.If(err) {
		return nil, err
	}
	var eq bool
	if link != nil {
		eq = link.stamp.Equal(stamp)
	}
	if link == nil || (eq || link.stamp.Before(stamp)) {
		updated, errr := f(eq, root)
		log.If(errr)
		if updated {
			return root, errr
		}
		return nil, errr
	}
	n, err := t.self.GetLinkedNode(root, link.string())
	if log.If(err) {
		return nil, err
	}
	updated, err := t.search(n, stamp, f)
	if err != nil {
		return nil, err
	}
	if updated != nil {
		root, err = root.UpdateNodeLink(link.string(), updated)
		log.If(err)
		return root, err
	}
	return nil, err
}

func randNode() (*mdag.Node, key.Key) {
	nd := new(mdag.Node)
	nd.Data = make([]byte, 32)
	util.NewTimeSeededRand().Read(nd.Data)
	k, _ := nd.Key()
	return nd, k
}

func (rw *RefWriter) writeRefsRecursive(n *dag.Node) (int, error) {
	nkey, err := n.Key()
	if err != nil {
		return 0, err
	}

	var count int
	for i, ng := range rw.DAG.GetDAG(rw.Ctx, n) {
		lk := key.Key(n.Links[i].Hash)
		if rw.skip(lk) {
			continue
		}

		if err := rw.WriteEdge(nkey, lk, n.Links[i].Name); err != nil {
			return count, err
		}

		nd, err := ng.Get(rw.Ctx)
		if err != nil {
			return count, err
		}

		c, err := rw.writeRefsRecursive(nd)
		count += c
		if err != nil {
			return count, err
		}
	}
	return count, nil
}

func randNode() (*merkledag.Node, key.Key) {
	node := new(merkledag.Node)
	node.Data = make([]byte, 32)
	util.NewTimeSeededRand().Read(node.Data)
	k, _ := node.Key()
	return node, k
}

// converts the Node object into a real dag.Node
func deserializeNode(node *Node, dataFieldEncoding string) (*dag.Node, error) {
	dagnode := new(dag.Node)
	switch dataFieldEncoding {
	case "text":
		dagnode.Data = []byte(node.Data)
	case "base64":
		dagnode.Data, _ = base64.StdEncoding.DecodeString(node.Data)
	default:
		return nil, fmt.Errorf("Unkown data field encoding")
	}

	dagnode.Links = make([]*dag.Link, len(node.Links))
	for i, link := range node.Links {
		hash, err := mh.FromB58String(link.Hash)
		if err != nil {
			return nil, err
		}
		dagnode.Links[i] = &dag.Link{
			Name: link.Name,
			Size: link.Size,
			Hash: hash,
		}
	}

	return dagnode, nil
}

//FromDAGNode creates Records from  links of merkledag n and retuns it.
//links must contain "Stamp" and "Thread"
func FromDAGNode(self *peer.Self, n *merkledag.Node, sign []byte) (*Record, error) {
	r := &Record{
		self:     self,
		Stamp:    time.Unix(0, 0),
		Sign:     sign,
		Contents: make(map[string][]byte),
	}
	var err error
	r.Key, err = n.Key()
	if log.If(err) {
		return nil, err
	}
	for _, l := range n.Links {
		nn, err := r.self.GetLinkedNode(n, l.Name)
		if log.If(err) {
			return nil, err
		}
		r.Contents[l.Name] = nn.Data
		switch l.Name {
		case "thread":
			r.Thread = string(nn.Data)
		case "stamp":
			stamp := binary.BigEndian.Uint64(nn.Data)
			r.Stamp = time.Unix(0, int64(stamp))
		}
	}
	if err := r.check(false); log.If(err) {
		return nil, err
	}
	return r, nil
}

func AddMetadataTo(n *core.IpfsNode, skey string, m *ft.Metadata) (string, error) {
	ukey := key.B58KeyDecode(skey)

	nd, err := n.DAG.Get(n.Context(), ukey)
	if err != nil {
		return "", err
	}

	mdnode := new(dag.Node)
	mdata, err := ft.BytesForMetadata(m)
	if err != nil {
		return "", err
	}

	mdnode.Data = mdata
	if err := mdnode.AddNodeLinkClean("file", nd); err != nil {
		return "", err
	}

	nk, err := n.DAG.Add(mdnode)
	if err != nil {
		return "", err
	}

	return nk.B58String(), nil
}

func (d *Directory) Mkdir(name string) (*Directory, error) {
	d.lock.Lock()
	defer d.lock.Unlock()

	fsn, err := d.childUnsync(name)
	if err == nil {
		switch fsn := fsn.(type) {
		case *Directory:
			return fsn, os.ErrExist
		case *File:
			return nil, os.ErrExist
		default:
			return nil, fmt.Errorf("unrecognized type: %#v", fsn)
		}
	}

	ndir := new(dag.Node)
	ndir.SetData(ft.FolderPBData())

	_, err = d.dserv.Add(ndir)
	if err != nil {
		return nil, err
	}

	err = d.node.AddNodeLinkClean(name, ndir)
	if err != nil {
		return nil, err
	}

	dirobj := NewDirectory(d.ctx, name, ndir, d, d.dserv)
	d.childDirs[name] = dirobj
	return dirobj, nil
}

func (adder *Adder) addNode(node *dag.Node, path string) error {
	// patch it into the root
	if path == "" {
		key, err := node.Key()
		if err != nil {
			return err
		}

		path = key.Pretty()
	}

	dir := gopath.Dir(path)
	if dir != "." {
		if err := mfs.Mkdir(adder.mr, dir, true, false); err != nil {
			return err
		}
	}

	if err := mfs.PutNode(adder.mr, path, node); err != nil {
		return err
	}

	if !adder.Silent {
		return outputDagnode(adder.out, path, node)
	}
	return nil
}

func printDag(nd *mdag.Node, ds mdag.DAGService, indent int) {
	pbd, err := ft.FromBytes(nd.Data())
	if err != nil {
		panic(err)
	}

	for i := 0; i < indent; i++ {
		fmt.Print(" ")
	}
	fmt.Printf("{size = %d, type = %s, children = %d", pbd.GetFilesize(), pbd.GetType().String(), len(pbd.GetBlocksizes()))
	if len(nd.Links) > 0 {
		fmt.Println()
	}
	for _, lnk := range nd.Links {
		child, err := lnk.GetNode(context.Background(), ds)
		if err != nil {
			panic(err)
		}
		printDag(child, ds, indent+1)
	}
	if len(nd.Links) > 0 {
		for i := 0; i < indent; i++ {
			fmt.Print(" ")
		}
	}
	fmt.Println("}")
}

func (t *Thread) updateLink(n *merkledag.Node, stamp time.Time) func(bool, *merkledag.Node) (bool, error) {
	return func(exist bool, prev *merkledag.Node) (bool, error) {
		if exist {
			return false, nil
		}
		pren, err := getLinkName(prev)
		if log.If(err) {
			return false, err
		}
		if pren != nil {
			log.Println(pren.stamp)
			pn := pren.string()
			raw, errr := prev.GetNodeLink(pn)
			if log.If(errr) {
				return false, errr
			}
			if errr := n.AddRawLink(pn, raw); log.If(errr) {
				return false, errr
			}
			if errr := prev.RemoveNodeLink(pn); log.If(errr) {
				return false, errr
			}
		}
		name := &linkName{stamp: stamp}
		log.Println(name.stamp)

		if err := prev.AddNodeLink(name.string(), n); log.If(err) {
			return false, err
		}
		log.If(err)
		return true, err
	}
}

func addLink(ctx context.Context, ds dag.DAGService, root *dag.Node, childname string, childnd *dag.Node) (*dag.Node, error) {
	if childname == "" {
		return nil, errors.New("cannot create link with no name!")
	}

	// ensure that the node we are adding is in the dagservice
	_, err := ds.Add(childnd)
	if err != nil {
		return nil, err
	}

	_ = ds.Remove(root)

	// ensure no link with that name already exists
	_ = root.RemoveNodeLink(childname) // ignore error, only option is ErrNotFound

	if err := root.AddNodeLinkClean(childname, childnd); err != nil {
		return nil, err
	}

	if _, err := ds.Add(root); err != nil {
		return nil, err
	}
	return root, nil
}

func NewDagModifier(ctx context.Context, from *mdag.Node, serv mdag.DAGService, spl chunk.SplitterGen) (*DagModifier, error) {
	return &DagModifier{
		curNode:  from.Copy(),
		dagserv:  serv,
		splitter: spl,
		ctx:      ctx,
	}, nil
}

// nodeType returns the record node's type link value.
func nodeType(nd *dag.Node) ([]byte, error) {
	tl, err := nd.GetNodeLink(linkType)
	if err != nil {
		return nil, fmt.Errorf("invalid record. failed to get link %s (%s)", linkType, err)
	}

	return tl.Hash, nil
}

// Recursive call for verifying the structure of a trickledag
func verifyTDagRec(nd *dag.Node, depth, direct, layerRepeat int, ds dag.DAGService) error {
	if depth == 0 {
		// zero depth dag is raw data block
		if len(nd.Links) > 0 {
			return errors.New("expected direct block")
		}

		pbn, err := ft.FromBytes(nd.Data())
		if err != nil {
			return err
		}

		if pbn.GetType() != ft.TRaw {
			return errors.New("Expected raw block")
		}
		return nil
	}

	// Verify this is a branch node
	pbn, err := ft.FromBytes(nd.Data())
	if err != nil {
		return err
	}

	if pbn.GetType() != ft.TFile {
		return errors.New("expected file as branch node")
	}

	if len(pbn.Data) > 0 {
		return errors.New("branch node should not have data")
	}

	for i := 0; i < len(nd.Links); i++ {
		child, err := nd.Links[i].GetNode(context.TODO(), ds)
		if err != nil {
			return err
		}

		if i < direct {
			// Direct blocks
			err := verifyTDagRec(child, 0, direct, layerRepeat, ds)
			if err != nil {
				return err
			}
		} else {
			// Recursive trickle dags
			rdepth := ((i - direct) / layerRepeat) + 1
			if rdepth >= depth && depth > 0 {
				return errors.New("Child dag was too deep!")
			}
			err := verifyTDagRec(child, rdepth, direct, layerRepeat, ds)
			if err != nil {
				return err
			}
		}
	}
	return nil
}

func (p *pinner) pinIndirectRecurse(ctx context.Context, node *mdag.Node) error {
	k, err := node.Key()
	if err != nil {
		return err
	}

	p.indirPin.Increment(k)
	return p.pinLinks(ctx, node)
}

func NewDagModifier(ctx context.Context, from *mdag.Node, serv mdag.DAGService, mp pin.ManualPinner, spl chunk.BlockSplitter) (*DagModifier, error) {
	return &DagModifier{
		curNode:  from.Copy(),
		dagserv:  serv,
		splitter: spl,
		ctx:      ctx,
		mp:       mp,
	}, nil
}