marshal.go 4.24 KB
Newer Older
Rod Vagg's avatar
Rod Vagg committed
1 2 3 4
package dagpb

import (
	"io"
Rod Vagg's avatar
Rod Vagg committed
5 6
	math_bits "math/bits"
	"sort"
Rod Vagg's avatar
Rod Vagg committed
7

Rod Vagg's avatar
Rod Vagg committed
8
	"github.com/ipfs/go-cid"
Rod Vagg's avatar
Rod Vagg committed
9 10
	ipld "github.com/ipld/go-ipld-prime"
	cidlink "github.com/ipld/go-ipld-prime/linking/cid"
11
	"golang.org/x/xerrors"
Rod Vagg's avatar
Rod Vagg committed
12 13
)

Rod Vagg's avatar
Rod Vagg committed
14 15 16 17 18 19 20 21
type pbLink struct {
	hash     cid.Cid
	name     string
	hasName  bool
	tsize    uint64
	hasTsize bool
}

Rod Vagg's avatar
Rod Vagg committed
22
func Marshal(inNode ipld.Node, out io.Writer) error {
Rod Vagg's avatar
Rod Vagg committed
23
	// Wrap in a typed node for some basic schema form checking
Rod Vagg's avatar
Rod Vagg committed
24 25 26 27 28 29
	builder := Type.PBNode.NewBuilder()
	if err := builder.AssignNode(inNode); err != nil {
		return err
	}
	node := builder.Build()

Rod Vagg's avatar
Rod Vagg committed
30 31 32 33 34 35 36
	links, err := node.LookupByString("Links")
	if err != nil {
		return err
	}
	if links.Length() > 0 {
		// collect links into a slice so we can properly sort for encoding
		pbLinks := make([]pbLink, links.Length())
Rod Vagg's avatar
Rod Vagg committed
37

Rod Vagg's avatar
Rod Vagg committed
38 39 40
		linksIter := links.ListIterator()
		for !linksIter.Done() {
			ii, link, err := linksIter.Next()
Rod Vagg's avatar
Rod Vagg committed
41
			if err != nil {
Rod Vagg's avatar
Rod Vagg committed
42
				return err
Rod Vagg's avatar
Rod Vagg committed
43 44
			}

Rod Vagg's avatar
Rod Vagg committed
45
			{ // Hash
Rod Vagg's avatar
Rod Vagg committed
46 47
				d, err := link.LookupByString("Hash")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
48
					return err
Rod Vagg's avatar
Rod Vagg committed
49 50 51
				}
				l, err := d.AsLink()
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
52
					return err
Rod Vagg's avatar
Rod Vagg committed
53
				}
Rod Vagg's avatar
Rod Vagg committed
54 55
				if err != nil {
					return err
Rod Vagg's avatar
Rod Vagg committed
56
				}
Rod Vagg's avatar
Rod Vagg committed
57 58
				cl, ok := l.(cidlink.Link)
				if !ok {
59 60
					// this _should_ be taken care of by the Typed conversion above "missing required fields: Hash"
					return xerrors.Errorf("invalid DAG-PB form (link must have a Hash)")
Rod Vagg's avatar
Rod Vagg committed
61 62
				}
				pbLinks[ii].hash = cl.Cid
Rod Vagg's avatar
Rod Vagg committed
63 64
			}

Rod Vagg's avatar
Rod Vagg committed
65
			{ // Name
Rod Vagg's avatar
Rod Vagg committed
66 67
				nameNode, err := link.LookupByString("Name")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
68
					return err
Rod Vagg's avatar
Rod Vagg committed
69 70 71 72
				}
				if !nameNode.IsAbsent() {
					name, err := nameNode.AsString()
					if err != nil {
Rod Vagg's avatar
Rod Vagg committed
73
						return err
Rod Vagg's avatar
Rod Vagg committed
74
					}
Rod Vagg's avatar
Rod Vagg committed
75 76
					pbLinks[ii].name = name
					pbLinks[ii].hasName = true
Rod Vagg's avatar
Rod Vagg committed
77 78 79
				}
			}

Rod Vagg's avatar
Rod Vagg committed
80
			{ // Tsize
Rod Vagg's avatar
Rod Vagg committed
81 82
				tsizeNode, err := link.LookupByString("Tsize")
				if err != nil {
Rod Vagg's avatar
Rod Vagg committed
83
					return err
Rod Vagg's avatar
Rod Vagg committed
84 85 86 87
				}
				if !tsizeNode.IsAbsent() {
					tsize, err := tsizeNode.AsInt()
					if err != nil {
Rod Vagg's avatar
Rod Vagg committed
88
						return err
Rod Vagg's avatar
Rod Vagg committed
89 90
					}
					if tsize < 0 {
91
						return xerrors.Errorf("Link has negative Tsize value [%v]", tsize)
Rod Vagg's avatar
Rod Vagg committed
92
					}
Rod Vagg's avatar
Rod Vagg committed
93 94 95
					utsize := uint64(tsize)
					pbLinks[ii].tsize = utsize
					pbLinks[ii].hasTsize = true
Rod Vagg's avatar
Rod Vagg committed
96 97
				}
			}
Rod Vagg's avatar
Rod Vagg committed
98 99 100 101 102 103 104 105 106 107 108
		} // for

		sortLinks(pbLinks)
		for _, link := range pbLinks {
			size := link.encodedSize()
			chunk := make([]byte, size+sizeOfVarint(uint64(size))+1)
			chunk[0] = 0x12
			offset := encodeVarint(chunk, 1, uint64(size))
			wrote, err := link.marshal(chunk, offset)
			if err != nil {
				return err
Rod Vagg's avatar
Rod Vagg committed
109
			}
Rod Vagg's avatar
Rod Vagg committed
110
			if wrote != size {
111
				return xerrors.Errorf("bad PBLink marshal, wrote wrong number of bytes")
Rod Vagg's avatar
Rod Vagg committed
112
			}
Rod Vagg's avatar
Rod Vagg committed
113 114 115 116 117 118 119 120 121 122 123 124
			out.Write(chunk)
		}
	} // if links

	data, err := node.LookupByString("Data")
	if err != nil {
		return err
	}
	if !data.IsAbsent() {
		byts, err := data.AsBytes()
		if err != nil {
			return err
Rod Vagg's avatar
Rod Vagg committed
125
		}
Rod Vagg's avatar
Rod Vagg committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
		size := uint64(len(byts))
		lead := make([]byte, sizeOfVarint(size)+1)
		lead[0] = 0xa
		encodeVarint(lead, 1, size)
		out.Write(lead)
		out.Write(byts)
	}

	return nil
}

func (link pbLink) encodedSize() (n int) {
	l := link.hash.ByteLen()
	n += 1 + l + sizeOfVarint(uint64(l))
	if link.hasName {
		l = len(link.name)
		n += 1 + l + sizeOfVarint(uint64(l))
	}
	if link.hasTsize {
		n += 1 + sizeOfVarint(uint64(link.tsize))
	}
	return n
}

func (link pbLink) marshal(data []byte, offset int) (int, error) {
	base := offset
	data[offset] = 0xa
	byts := link.hash.Bytes()
	offset = encodeVarint(data, offset+1, uint64(len(byts)))
	copy(data[offset:], byts)
	offset += len(byts)
	if link.hasName {
		data[offset] = 0x12
		offset = encodeVarint(data, offset+1, uint64(len(link.name)))
		copy(data[offset:], link.name)
		offset += len(link.name)
Rod Vagg's avatar
Rod Vagg committed
162
	}
Rod Vagg's avatar
Rod Vagg committed
163 164 165 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 191 192
	if link.hasTsize {
		data[offset] = 0x18
		offset = encodeVarint(data, offset+1, uint64(link.tsize))
	}
	return offset - base, nil
}

func encodeVarint(data []byte, offset int, v uint64) int {
	for v >= 1<<7 {
		data[offset] = uint8(v&0x7f | 0x80)
		v >>= 7
		offset++
	}
	data[offset] = uint8(v)
	return offset + 1
}

func sortLinks(links []pbLink) {
	sort.Stable(pbLinkSlice(links))
}

type pbLinkSlice []pbLink

func (ls pbLinkSlice) Len() int           { return len(ls) }
func (ls pbLinkSlice) Swap(a, b int)      { ls[a], ls[b] = ls[b], ls[a] }
func (ls pbLinkSlice) Less(a, b int) bool { return pbLinkLess(ls[a], ls[b]) }

func pbLinkLess(a pbLink, b pbLink) bool {
	return a.name < b.name
}
Rod Vagg's avatar
Rod Vagg committed
193

Rod Vagg's avatar
Rod Vagg committed
194 195
func sizeOfVarint(x uint64) (n int) {
	return (math_bits.Len64(x|1) + 6) / 7
Rod Vagg's avatar
Rod Vagg committed
196
}