bencode.gno
12.71 Kb · 480 lines
1// Package bencode implements bencoding, the serialization format BitTorrent
2// uses for .torrent files and tracker responses, as a pure reusable package.
3//
4// Four types, and that is the whole format: integers (i42e), byte strings
5// (5:hello), lists (l...e) and dictionaries (d...e). There is no float, no
6// boolean and no null, which is most of why the format fits in one file.
7//
8// The reason to reach for it over JSON is that bencode is CANONICAL: one value
9// has exactly one encoding. Dictionary keys are sorted bytewise, integers carry
10// no leading zeros and no negative zero, and strings carry their length instead
11// of an escape syntax. An infohash is the digest of a re-encoded sub-dictionary,
12// so a decoder that accepts a sloppy encoding and re-emits a tidy one silently
13// changes the identity of the thing it parsed.
14//
15// This decoder is therefore strict: it REJECTS non-canonical input rather than
16// normalizing it, so for every input it accepts, Decode followed by Encode
17// returns the original bytes unchanged.
18//
19// A live demo of this package is at
20// [r/moul/x/daily/bencodedemo](/r/moul/x/daily/bencodedemo/v0).
21package bencode
22
23import (
24 "errors"
25 "strconv"
26 "strings"
27)
28
29// Limits, so a decode stays bounded on chain.
30const (
31 // MaxLen is the longest input Decode will look at.
32 MaxLen = 8192
33 // MaxDepth is how deeply lists and dictionaries may nest.
34 MaxDepth = 16
35)
36
37// Kind is the type of a [Value]: one of the four bencode types.
38type Kind int
39
40// The four bencode types, plus the zero value.
41const (
42 KindInvalid Kind = iota
43 KindInt
44 KindString
45 KindList
46 KindDict
47)
48
49// String names the kind, for rendering and error messages.
50func (k Kind) String() string {
51 switch k {
52 case KindInt:
53 return "int"
54 case KindString:
55 return "string"
56 case KindList:
57 return "list"
58 case KindDict:
59 return "dict"
60 default:
61 return "invalid"
62 }
63}
64
65// Errors returned by [Decode]. They are distinguishable on purpose: a caller
66// feeding the decoder a user-pasted torrent wants to say which of the four
67// strictness rules the paste broke.
68var (
69 // ErrTooLong is returned when input is longer than [MaxLen].
70 ErrTooLong = errors.New("bencode: input too long")
71 // ErrSyntax is returned when input is not bencode at all.
72 ErrSyntax = errors.New("bencode: malformed input")
73 // ErrNotCanonical is returned for input that is parseable but could never
74 // have been produced by an encoder: a leading zero, a negative zero, or
75 // dictionary keys that are unsorted or duplicated.
76 ErrNotCanonical = errors.New("bencode: input is not canonical")
77 // ErrTrailingData is returned when bytes follow the top-level value.
78 ErrTrailingData = errors.New("bencode: trailing data after top-level value")
79 // ErrTooDeep is returned when nesting exceeds [MaxDepth].
80 ErrTooDeep = errors.New("bencode: nesting too deep")
81)
82
83// Value is one bencode value. Build one with [NewInt], [NewString], [NewList]
84// or [NewDict], or get one from [Decode]. Accessors that do not match the
85// value's kind return the zero value rather than panicking, so a chain of
86// lookups through a document of unknown shape never aborts a realm call.
87type Value struct {
88 kind Kind
89 num int64
90 text string
91 elems []*Value
92 keys []string
93 vals []*Value
94}
95
96// NewInt returns an integer value.
97func NewInt(n int64) *Value { return &Value{kind: KindInt, num: n} }
98
99// NewString returns a byte-string value.
100func NewString(s string) *Value { return &Value{kind: KindString, text: s} }
101
102// NewList returns a list of the given items, in order. A nil item, and the
103// zero Value, are dropped: both encode to nothing, which would turn a three
104// item list into a two item encoding that still reports a length of three.
105func NewList(items ...*Value) *Value {
106 l := &Value{kind: KindList, elems: []*Value{}}
107 for _, it := range items {
108 if it.Kind() == KindInvalid {
109 continue
110 }
111 l.elems = append(l.elems, it)
112 }
113 return l
114}
115
116// NewDict returns an empty dictionary. Fill it with [Value.Set], in any order:
117// the encoding sorts.
118func NewDict() *Value {
119 return &Value{kind: KindDict, keys: []string{}, vals: []*Value{}}
120}
121
122// Kind reports the value's type. A nil value is [KindInvalid].
123func (v *Value) Kind() Kind {
124 if v == nil {
125 return KindInvalid
126 }
127 return v.kind
128}
129
130// Int returns the integer, or 0 for any other kind.
131func (v *Value) Int() int64 {
132 if v == nil || v.kind != KindInt {
133 return 0
134 }
135 return v.num
136}
137
138// Text returns the byte string, or "" for any other kind.
139func (v *Value) Text() string {
140 if v == nil || v.kind != KindString {
141 return ""
142 }
143 return v.text
144}
145
146// Len returns the number of list items or dictionary entries, 0 otherwise.
147func (v *Value) Len() int {
148 if v == nil {
149 return 0
150 }
151 switch v.kind {
152 case KindList:
153 return len(v.elems)
154 case KindDict:
155 return len(v.keys)
156 default:
157 return 0
158 }
159}
160
161// At returns the i-th list item, or the i-th dictionary value in key order.
162// Out of range, or any other kind, returns nil.
163func (v *Value) At(i int) *Value {
164 if v == nil || i < 0 {
165 return nil
166 }
167 switch v.kind {
168 case KindList:
169 if i >= len(v.elems) {
170 return nil
171 }
172 return v.elems[i]
173 case KindDict:
174 if i >= len(v.vals) {
175 return nil
176 }
177 return v.vals[i]
178 default:
179 return nil
180 }
181}
182
183// Get returns the dictionary entry for key, or nil when it is absent or the
184// value is not a dictionary.
185func (v *Value) Get(key string) *Value {
186 if v == nil || v.kind != KindDict {
187 return nil
188 }
189 i, found := v.find(key)
190 if !found {
191 return nil
192 }
193 return v.vals[i]
194}
195
196// Keys returns the dictionary's keys in bytewise order, nil for other kinds.
197func (v *Value) Keys() []string {
198 if v == nil || v.kind != KindDict {
199 return nil
200 }
201 out := make([]string, len(v.keys))
202 copy(out, v.keys)
203 return out
204}
205
206// Set inserts or replaces a dictionary entry and returns the dictionary, so
207// calls chain. Four things are refused rather than stored, each because it
208// would make the encoding disagree with the structure: a receiver that is not
209// a dictionary, a nil value, the zero Value, and the dictionary itself. The
210// first three encode to nothing, which would emit a key with no value and
211// produce a dictionary this package's own Decode rejects; the fourth is a
212// cycle. Removing an entry is deliberately not spelled "set it to nil",
213// because nothing here removes.
214//
215// An indirect cycle (two dictionaries holding each other) is not detectable
216// here without walking the whole structure on every insert, so it is caught by
217// [Value.Encode] instead, which is depth-bounded and returns "".
218//
219// It never writes through the slices a previous Set produced. gno lets a
220// caller copy the struct behind the pointer, and two copies sharing a backing
221// array would see each other's replacements but not each other's insertions.
222func (v *Value) Set(key string, val *Value) *Value {
223 if v == nil || v.kind != KindDict || val.Kind() == KindInvalid || val == v {
224 return v
225 }
226 i, found := v.find(key)
227 rest := i
228 if found {
229 rest = i + 1
230 }
231 keys := make([]string, 0, len(v.keys)+1)
232 vals := make([]*Value, 0, len(v.vals)+1)
233 keys = append(append(append(keys, v.keys[:i]...), key), v.keys[rest:]...)
234 vals = append(append(append(vals, v.vals[:i]...), val), v.vals[rest:]...)
235 v.keys, v.vals = keys, vals
236 return v
237}
238
239// find returns the index of key, or where it would be inserted.
240func (v *Value) find(key string) (int, bool) {
241 lo, hi := 0, len(v.keys)
242 for lo < hi {
243 mid := (lo + hi) / 2
244 if v.keys[mid] < key {
245 lo = mid + 1
246 } else {
247 hi = mid
248 }
249 }
250 return lo, lo < len(v.keys) && v.keys[lo] == key
251}
252
253// Encode returns the canonical bencoding of the value, or "" for a value that
254// has no canonical encoding: a nil, the zero Value, anything nested deeper
255// than [MaxDepth], and therefore any cycle a caller assembled by hand. "" is
256// not a legal bencode document, so a caller can test for it.
257//
258// Encode has no error to return and is called from a realm's Render, so it is
259// total by construction: the depth bound is what keeps a structure the decoder
260// could never have produced from aborting the call that encodes it.
261func (v *Value) Encode() string {
262 var b strings.Builder
263 if !v.writeTo(&b, 0) {
264 return ""
265 }
266 return b.String()
267}
268
269// writeTo reports whether the whole value fit within MaxDepth. The bound is
270// counted on containers only, exactly as the decoder counts it, so the two
271// agree about which structures exist. A false leaves b holding a partial
272// encoding, which is why Encode discards it.
273func (v *Value) writeTo(b *strings.Builder, depth int) bool {
274 if v == nil {
275 return true
276 }
277 switch v.kind {
278 case KindInt:
279 b.WriteString("i")
280 b.WriteString(strconv.FormatInt(v.num, 10))
281 b.WriteString("e")
282 case KindString:
283 b.WriteString(strconv.Itoa(len(v.text)))
284 b.WriteString(":")
285 b.WriteString(v.text)
286 case KindList:
287 if depth >= MaxDepth {
288 return false
289 }
290 b.WriteString("l")
291 for _, e := range v.elems {
292 if !e.writeTo(b, depth+1) {
293 return false
294 }
295 }
296 b.WriteString("e")
297 case KindDict:
298 if depth >= MaxDepth {
299 return false
300 }
301 b.WriteString("d")
302 for i, k := range v.keys {
303 b.WriteString(strconv.Itoa(len(k)))
304 b.WriteString(":")
305 b.WriteString(k)
306 if !v.vals[i].writeTo(b, depth+1) {
307 return false
308 }
309 }
310 b.WriteString("e")
311 }
312 return true
313}
314
315// Decode parses one bencode value and rejects anything after it. It also
316// rejects input that is parseable but not canonical, which is the whole point:
317// see the package doc.
318func Decode(s string) (*Value, error) {
319 if len(s) > MaxLen {
320 return nil, ErrTooLong
321 }
322 v, next, err := decodeValue(s, 0, 0)
323 if err != nil {
324 return nil, err
325 }
326 if next != len(s) {
327 return nil, ErrTrailingData
328 }
329 return v, nil
330}
331
332func decodeValue(s string, i, depth int) (*Value, int, error) {
333 if i >= len(s) {
334 return nil, i, ErrSyntax
335 }
336 switch c := s[i]; {
337 case c == 'i':
338 return decodeInt(s, i)
339 case c == 'l':
340 return decodeList(s, i, depth)
341 case c == 'd':
342 return decodeDict(s, i, depth)
343 case c >= '0' && c <= '9':
344 return decodeString(s, i)
345 default:
346 return nil, i, ErrSyntax
347 }
348}
349
350func decodeInt(s string, i int) (*Value, int, error) {
351 end := strings.IndexByte(s[i:], 'e')
352 if end < 0 {
353 return nil, i, ErrSyntax
354 }
355 end += i
356 body := s[i+1 : end]
357 if err := checkIntLiteral(body); err != nil {
358 return nil, i, err
359 }
360 n, err := strconv.ParseInt(body, 10, 64)
361 if err != nil {
362 return nil, i, ErrSyntax
363 }
364 return NewInt(n), end + 1, nil
365}
366
367// checkIntLiteral enforces the canonical integer grammar: optional '-', then
368// digits, with no leading zero and no negative zero.
369func checkIntLiteral(body string) error {
370 digits := body
371 neg := false
372 if strings.HasPrefix(digits, "-") {
373 neg = true
374 digits = digits[1:]
375 }
376 if digits == "" {
377 return ErrSyntax
378 }
379 for k := 0; k < len(digits); k++ {
380 if digits[k] < '0' || digits[k] > '9' {
381 return ErrSyntax
382 }
383 }
384 if len(digits) > 1 && digits[0] == '0' {
385 return ErrNotCanonical
386 }
387 if neg && digits == "0" {
388 return ErrNotCanonical
389 }
390 return nil
391}
392
393func decodeString(s string, i int) (*Value, int, error) {
394 colon := strings.IndexByte(s[i:], ':')
395 if colon < 0 {
396 return nil, i, ErrSyntax
397 }
398 colon += i
399 lit := s[i:colon]
400 for k := 0; k < len(lit); k++ {
401 if lit[k] < '0' || lit[k] > '9' {
402 return nil, i, ErrSyntax
403 }
404 }
405 if len(lit) > 1 && lit[0] == '0' {
406 return nil, i, ErrNotCanonical
407 }
408 n, err := strconv.Atoi(lit)
409 if err != nil || n < 0 {
410 return nil, i, ErrSyntax
411 }
412 start := colon + 1
413 // Compare against what is left rather than computing start+n: the length
414 // literal is bounded only by MaxLen, so a 19-digit length fits in the
415 // input and in an int64, and the sum would wrap to a negative slice bound.
416 if n > len(s)-start {
417 return nil, i, ErrSyntax
418 }
419 return NewString(s[start : start+n]), start + n, nil
420}
421
422func decodeList(s string, i, depth int) (*Value, int, error) {
423 if depth+1 > MaxDepth {
424 return nil, i, ErrTooDeep
425 }
426 l := NewList()
427 j := i + 1
428 for {
429 if j >= len(s) {
430 return nil, j, ErrSyntax
431 }
432 if s[j] == 'e' {
433 return l, j + 1, nil
434 }
435 item, next, err := decodeValue(s, j, depth+1)
436 if err != nil {
437 return nil, next, err
438 }
439 l.elems = append(l.elems, item)
440 j = next
441 }
442}
443
444func decodeDict(s string, i, depth int) (*Value, int, error) {
445 if depth+1 > MaxDepth {
446 return nil, i, ErrTooDeep
447 }
448 d := NewDict()
449 j := i + 1
450 last := ""
451 for {
452 if j >= len(s) {
453 return nil, j, ErrSyntax
454 }
455 if s[j] == 'e' {
456 return d, j + 1, nil
457 }
458 if s[j] < '0' || s[j] > '9' {
459 // A key is always a byte string. Anything else is not a dict.
460 return nil, j, ErrSyntax
461 }
462 kv, next, err := decodeString(s, j)
463 if err != nil {
464 return nil, next, err
465 }
466 key := kv.Text()
467 if len(d.keys) > 0 && key <= last {
468 // Unsorted or duplicated: parseable, but no encoder emits it.
469 return nil, next, ErrNotCanonical
470 }
471 val, next2, err := decodeValue(s, next, depth+1)
472 if err != nil {
473 return nil, next2, err
474 }
475 d.keys = append(d.keys, key)
476 d.vals = append(d.vals, val)
477 last = key
478 j = next2
479 }
480}
