]> Sergey Matveev's repositories - btrtrc.git/blob - bencode/decode.go
Fix test failure using missinggo filecache on Windows
[btrtrc.git] / bencode / decode.go
1 package bencode
2
3 import (
4         "bytes"
5         "errors"
6         "fmt"
7         "io"
8         "math/big"
9         "reflect"
10         "runtime"
11         "strconv"
12         "sync"
13 )
14
15 // The default bencode string length limit. This is a poor attempt to prevent excessive memory
16 // allocation when parsing, but also leaves the window open to implement a better solution.
17 const DefaultDecodeMaxStrLen = 1<<27 - 1 // ~128MiB
18
19 type MaxStrLen = int64
20
21 type Decoder struct {
22         // Maximum parsed bencode string length. Defaults to DefaultMaxStrLen if zero.
23         MaxStrLen MaxStrLen
24
25         r interface {
26                 io.ByteScanner
27                 io.Reader
28         }
29         // Sum of bytes used to Decode values.
30         Offset int64
31         buf    bytes.Buffer
32 }
33
34 func (d *Decoder) Decode(v interface{}) (err error) {
35         defer func() {
36                 if err != nil {
37                         return
38                 }
39                 r := recover()
40                 if r == nil {
41                         return
42                 }
43                 _, ok := r.(runtime.Error)
44                 if ok {
45                         panic(r)
46                 }
47                 if err, ok = r.(error); !ok {
48                         panic(r)
49                 }
50                 // Errors thrown from deeper in parsing are unexpected. At value boundaries, errors should
51                 // be returned directly (at least until all the panic nonsense is removed entirely).
52                 if err == io.EOF {
53                         err = io.ErrUnexpectedEOF
54                 }
55         }()
56
57         pv := reflect.ValueOf(v)
58         if pv.Kind() != reflect.Ptr || pv.IsNil() {
59                 return &UnmarshalInvalidArgError{reflect.TypeOf(v)}
60         }
61
62         ok, err := d.parseValue(pv.Elem())
63         if err != nil {
64                 return
65         }
66         if !ok {
67                 d.throwSyntaxError(d.Offset-1, errors.New("unexpected 'e'"))
68         }
69         return
70 }
71
72 func checkForUnexpectedEOF(err error, offset int64) {
73         if err == io.EOF {
74                 panic(&SyntaxError{
75                         Offset: offset,
76                         What:   io.ErrUnexpectedEOF,
77                 })
78         }
79 }
80
81 func (d *Decoder) readByte() byte {
82         b, err := d.r.ReadByte()
83         if err != nil {
84                 checkForUnexpectedEOF(err, d.Offset)
85                 panic(err)
86         }
87
88         d.Offset++
89         return b
90 }
91
92 // reads data writing it to 'd.buf' until 'sep' byte is encountered, 'sep' byte
93 // is consumed, but not included into the 'd.buf'
94 func (d *Decoder) readUntil(sep byte) {
95         for {
96                 b := d.readByte()
97                 if b == sep {
98                         return
99                 }
100                 d.buf.WriteByte(b)
101         }
102 }
103
104 func checkForIntParseError(err error, offset int64) {
105         if err != nil {
106                 panic(&SyntaxError{
107                         Offset: offset,
108                         What:   err,
109                 })
110         }
111 }
112
113 func (d *Decoder) throwSyntaxError(offset int64, err error) {
114         panic(&SyntaxError{
115                 Offset: offset,
116                 What:   err,
117         })
118 }
119
120 // Assume the 'i' is already consumed. Read and validate the rest of an int into the buffer.
121 func (d *Decoder) readInt() error {
122         // start := d.Offset - 1
123         d.readUntil('e')
124         if err := d.checkBufferedInt(); err != nil {
125                 return err
126         }
127         // if d.buf.Len() == 0 {
128         //      panic(&SyntaxError{
129         //              Offset: start,
130         //              What:   errors.New("empty integer value"),
131         //      })
132         // }
133         return nil
134 }
135
136 // called when 'i' was consumed, for the integer type in v.
137 func (d *Decoder) parseInt(v reflect.Value) error {
138         start := d.Offset - 1
139
140         if err := d.readInt(); err != nil {
141                 return err
142         }
143         s := bytesAsString(d.buf.Bytes())
144
145         switch v.Kind() {
146         case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
147                 n, err := strconv.ParseInt(s, 10, 64)
148                 checkForIntParseError(err, start)
149
150                 if v.OverflowInt(n) {
151                         return &UnmarshalTypeError{
152                                 BencodeTypeName:     "int",
153                                 UnmarshalTargetType: v.Type(),
154                         }
155                 }
156                 v.SetInt(n)
157         case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
158                 n, err := strconv.ParseUint(s, 10, 64)
159                 checkForIntParseError(err, start)
160
161                 if v.OverflowUint(n) {
162                         return &UnmarshalTypeError{
163                                 BencodeTypeName:     "int",
164                                 UnmarshalTargetType: v.Type(),
165                         }
166                 }
167                 v.SetUint(n)
168         case reflect.Bool:
169                 v.SetBool(s != "0")
170         default:
171                 return &UnmarshalTypeError{
172                         BencodeTypeName:     "int",
173                         UnmarshalTargetType: v.Type(),
174                 }
175         }
176         d.buf.Reset()
177         return nil
178 }
179
180 func (d *Decoder) checkBufferedInt() error {
181         b := d.buf.Bytes()
182         if len(b) <= 1 {
183                 return nil
184         }
185         if b[0] == '-' {
186                 b = b[1:]
187         }
188         if b[0] < '1' || b[0] > '9' {
189                 return errors.New("invalid leading digit")
190         }
191         return nil
192 }
193
194 func (d *Decoder) parseStringLength() (int, error) {
195         // We should have already consumed the first byte of the length into the Decoder buf.
196         start := d.Offset - 1
197         d.readUntil(':')
198         if err := d.checkBufferedInt(); err != nil {
199                 return 0, err
200         }
201         // Really the limit should be the uint size for the platform. But we can't pass in an allocator,
202         // or limit total memory use in Go, the best we might hope to do is limit the size of a single
203         // decoded value (by reading it in in-place and then operating on a view).
204         length, err := strconv.ParseInt(bytesAsString(d.buf.Bytes()), 10, 0)
205         checkForIntParseError(err, start)
206         if int64(length) > d.getMaxStrLen() {
207                 err = fmt.Errorf("parsed string length %v exceeds limit (%v)", length, DefaultDecodeMaxStrLen)
208         }
209         d.buf.Reset()
210         return int(length), err
211 }
212
213 func (d *Decoder) parseString(v reflect.Value) error {
214         length, err := d.parseStringLength()
215         if err != nil {
216                 return err
217         }
218         defer d.buf.Reset()
219         read := func(b []byte) {
220                 n, err := io.ReadFull(d.r, b)
221                 d.Offset += int64(n)
222                 if err != nil {
223                         checkForUnexpectedEOF(err, d.Offset)
224                         panic(&SyntaxError{
225                                 Offset: d.Offset,
226                                 What:   errors.New("unexpected I/O error: " + err.Error()),
227                         })
228                 }
229         }
230
231         switch v.Kind() {
232         case reflect.String:
233                 b := make([]byte, length)
234                 read(b)
235                 v.SetString(bytesAsString(b))
236                 return nil
237         case reflect.Slice:
238                 if v.Type().Elem().Kind() != reflect.Uint8 {
239                         break
240                 }
241                 b := make([]byte, length)
242                 read(b)
243                 v.SetBytes(b)
244                 return nil
245         case reflect.Array:
246                 if v.Type().Elem().Kind() != reflect.Uint8 {
247                         break
248                 }
249                 d.buf.Grow(length)
250                 b := d.buf.Bytes()[:length]
251                 read(b)
252                 reflect.Copy(v, reflect.ValueOf(b))
253                 return nil
254         case reflect.Bool:
255                 d.buf.Grow(length)
256                 b := d.buf.Bytes()[:length]
257                 read(b)
258                 x, err := strconv.ParseBool(bytesAsString(b))
259                 if err != nil {
260                         x = length != 0
261                 }
262                 v.SetBool(x)
263                 return nil
264         }
265         // Can't move this into default clause because some cases above fail through to here after
266         // additional checks.
267         d.buf.Grow(length)
268         read(d.buf.Bytes()[:length])
269         // I believe we return here to support "ignore_unmarshal_type_error".
270         return &UnmarshalTypeError{
271                 BencodeTypeName:     "string",
272                 UnmarshalTargetType: v.Type(),
273         }
274 }
275
276 // Info for parsing a dict value.
277 type dictField struct {
278         Type reflect.Type
279         Get  func(value reflect.Value) func(reflect.Value)
280         Tags tag
281 }
282
283 // Returns specifics for parsing a dict field value.
284 func getDictField(dict reflect.Type, key string) (_ dictField, err error) {
285         // get valuev as a map value or as a struct field
286         switch k := dict.Kind(); k {
287         case reflect.Map:
288                 return dictField{
289                         Type: dict.Elem(),
290                         Get: func(mapValue reflect.Value) func(reflect.Value) {
291                                 return func(value reflect.Value) {
292                                         if mapValue.IsNil() {
293                                                 mapValue.Set(reflect.MakeMap(dict))
294                                         }
295                                         // Assigns the value into the map.
296                                         // log.Printf("map type: %v", mapValue.Type())
297                                         mapValue.SetMapIndex(reflect.ValueOf(key).Convert(dict.Key()), value)
298                                 }
299                         },
300                 }, nil
301         case reflect.Struct:
302                 return getStructFieldForKey(dict, key), nil
303                 // if sf.r.PkgPath != "" {
304                 //      panic(&UnmarshalFieldError{
305                 //              Key:   key,
306                 //              Type:  dict.Type(),
307                 //              Field: sf.r,
308                 //      })
309                 // }
310         default:
311                 err = fmt.Errorf("can't assign bencode dict items into a %v", k)
312                 return
313         }
314 }
315
316 var (
317         structFieldsMu sync.Mutex
318         structFields   = map[reflect.Type]map[string]dictField{}
319 )
320
321 func parseStructFields(struct_ reflect.Type, each func(key string, df dictField)) {
322         for _i, n := 0, struct_.NumField(); _i < n; _i++ {
323                 i := _i
324                 f := struct_.Field(i)
325                 if f.Anonymous {
326                         t := f.Type
327                         if t.Kind() == reflect.Ptr {
328                                 t = t.Elem()
329                         }
330                         parseStructFields(t, func(key string, df dictField) {
331                                 innerGet := df.Get
332                                 df.Get = func(value reflect.Value) func(reflect.Value) {
333                                         anonPtr := value.Field(i)
334                                         if anonPtr.Kind() == reflect.Ptr && anonPtr.IsNil() {
335                                                 anonPtr.Set(reflect.New(f.Type.Elem()))
336                                                 anonPtr = anonPtr.Elem()
337                                         }
338                                         return innerGet(anonPtr)
339                                 }
340                                 each(key, df)
341                         })
342                         continue
343                 }
344                 tagStr := f.Tag.Get("bencode")
345                 if tagStr == "-" {
346                         continue
347                 }
348                 tag := parseTag(tagStr)
349                 key := tag.Key()
350                 if key == "" {
351                         key = f.Name
352                 }
353                 each(key, dictField{f.Type, func(value reflect.Value) func(reflect.Value) {
354                         return value.Field(i).Set
355                 }, tag})
356         }
357 }
358
359 func saveStructFields(struct_ reflect.Type) {
360         m := make(map[string]dictField)
361         parseStructFields(struct_, func(key string, sf dictField) {
362                 m[key] = sf
363         })
364         structFields[struct_] = m
365 }
366
367 func getStructFieldForKey(struct_ reflect.Type, key string) (f dictField) {
368         structFieldsMu.Lock()
369         if _, ok := structFields[struct_]; !ok {
370                 saveStructFields(struct_)
371         }
372         f, ok := structFields[struct_][key]
373         structFieldsMu.Unlock()
374         if !ok {
375                 var discard interface{}
376                 return dictField{
377                         Type: reflect.TypeOf(discard),
378                         Get:  func(reflect.Value) func(reflect.Value) { return func(reflect.Value) {} },
379                         Tags: nil,
380                 }
381         }
382         return
383 }
384
385 func (d *Decoder) parseDict(v reflect.Value) error {
386         // At this point 'd' byte was consumed, now read key/value pairs
387         for {
388                 var keyStr string
389                 keyValue := reflect.ValueOf(&keyStr).Elem()
390                 ok, err := d.parseValue(keyValue)
391                 if err != nil {
392                         return fmt.Errorf("error parsing dict key: %w", err)
393                 }
394                 if !ok {
395                         return nil
396                 }
397
398                 df, err := getDictField(v.Type(), keyStr)
399                 if err != nil {
400                         return fmt.Errorf("parsing bencode dict into %v: %w", v.Type(), err)
401                 }
402
403                 // now we need to actually parse it
404                 if df.Type == nil {
405                         // Discard the value, there's nowhere to put it.
406                         var if_ interface{}
407                         if_, ok = d.parseValueInterface()
408                         if if_ == nil {
409                                 return fmt.Errorf("error parsing value for key %q", keyStr)
410                         }
411                         if !ok {
412                                 return fmt.Errorf("missing value for key %q", keyStr)
413                         }
414                         continue
415                 }
416                 setValue := reflect.New(df.Type).Elem()
417                 // log.Printf("parsing into %v", setValue.Type())
418                 ok, err = d.parseValue(setValue)
419                 if err != nil {
420                         var target *UnmarshalTypeError
421                         if !(errors.As(err, &target) && df.Tags.IgnoreUnmarshalTypeError()) {
422                                 return fmt.Errorf("parsing value for key %q: %w", keyStr, err)
423                         }
424                 }
425                 if !ok {
426                         return fmt.Errorf("missing value for key %q", keyStr)
427                 }
428                 df.Get(v)(setValue)
429         }
430 }
431
432 func (d *Decoder) parseList(v reflect.Value) error {
433         switch v.Kind() {
434         default:
435                 // If the list is a singleton of the expected type, use that value. See
436                 // https://github.com/anacrolix/torrent/issues/297.
437                 l := reflect.New(reflect.SliceOf(v.Type()))
438                 if err := d.parseList(l.Elem()); err != nil {
439                         return err
440                 }
441                 if l.Elem().Len() != 1 {
442                         return &UnmarshalTypeError{
443                                 BencodeTypeName:     "list",
444                                 UnmarshalTargetType: v.Type(),
445                         }
446                 }
447                 v.Set(l.Elem().Index(0))
448                 return nil
449         case reflect.Array, reflect.Slice:
450                 // We can work with this. Normal case, fallthrough.
451         }
452
453         i := 0
454         for ; ; i++ {
455                 if v.Kind() == reflect.Slice && i >= v.Len() {
456                         v.Set(reflect.Append(v, reflect.Zero(v.Type().Elem())))
457                 }
458
459                 if i < v.Len() {
460                         ok, err := d.parseValue(v.Index(i))
461                         if err != nil {
462                                 return err
463                         }
464                         if !ok {
465                                 break
466                         }
467                 } else {
468                         _, ok := d.parseValueInterface()
469                         if !ok {
470                                 break
471                         }
472                 }
473         }
474
475         if i < v.Len() {
476                 if v.Kind() == reflect.Array {
477                         z := reflect.Zero(v.Type().Elem())
478                         for n := v.Len(); i < n; i++ {
479                                 v.Index(i).Set(z)
480                         }
481                 } else {
482                         v.SetLen(i)
483                 }
484         }
485
486         if i == 0 && v.Kind() == reflect.Slice {
487                 v.Set(reflect.MakeSlice(v.Type(), 0, 0))
488         }
489         return nil
490 }
491
492 func (d *Decoder) readOneValue() bool {
493         b, err := d.r.ReadByte()
494         if err != nil {
495                 panic(err)
496         }
497         if b == 'e' {
498                 d.r.UnreadByte()
499                 return false
500         } else {
501                 d.Offset++
502                 d.buf.WriteByte(b)
503         }
504
505         switch b {
506         case 'd', 'l':
507                 // read until there is nothing to read
508                 for d.readOneValue() {
509                 }
510                 // consume 'e' as well
511                 b = d.readByte()
512                 d.buf.WriteByte(b)
513         case 'i':
514                 d.readUntil('e')
515                 d.buf.WriteString("e")
516         default:
517                 if b >= '0' && b <= '9' {
518                         start := d.buf.Len() - 1
519                         d.readUntil(':')
520                         length, err := strconv.ParseInt(bytesAsString(d.buf.Bytes()[start:]), 10, 64)
521                         checkForIntParseError(err, d.Offset-1)
522
523                         d.buf.WriteString(":")
524                         n, err := io.CopyN(&d.buf, d.r, length)
525                         d.Offset += n
526                         if err != nil {
527                                 checkForUnexpectedEOF(err, d.Offset)
528                                 panic(&SyntaxError{
529                                         Offset: d.Offset,
530                                         What:   errors.New("unexpected I/O error: " + err.Error()),
531                                 })
532                         }
533                         break
534                 }
535
536                 d.raiseUnknownValueType(b, d.Offset-1)
537         }
538
539         return true
540 }
541
542 func (d *Decoder) parseUnmarshaler(v reflect.Value) bool {
543         if !v.Type().Implements(unmarshalerType) {
544                 if v.Addr().Type().Implements(unmarshalerType) {
545                         v = v.Addr()
546                 } else {
547                         return false
548                 }
549         }
550         d.buf.Reset()
551         if !d.readOneValue() {
552                 return false
553         }
554         m := v.Interface().(Unmarshaler)
555         err := m.UnmarshalBencode(d.buf.Bytes())
556         if err != nil {
557                 panic(&UnmarshalerError{v.Type(), err})
558         }
559         return true
560 }
561
562 // Returns true if there was a value and it's now stored in 'v', otherwise
563 // there was an end symbol ("e") and no value was stored.
564 func (d *Decoder) parseValue(v reflect.Value) (bool, error) {
565         // we support one level of indirection at the moment
566         if v.Kind() == reflect.Ptr {
567                 // if the pointer is nil, allocate a new element of the type it
568                 // points to
569                 if v.IsNil() {
570                         v.Set(reflect.New(v.Type().Elem()))
571                 }
572                 v = v.Elem()
573         }
574
575         if d.parseUnmarshaler(v) {
576                 return true, nil
577         }
578
579         // common case: interface{}
580         if v.Kind() == reflect.Interface && v.NumMethod() == 0 {
581                 iface, _ := d.parseValueInterface()
582                 v.Set(reflect.ValueOf(iface))
583                 return true, nil
584         }
585
586         b, err := d.r.ReadByte()
587         if err != nil {
588                 return false, err
589         }
590         d.Offset++
591
592         switch b {
593         case 'e':
594                 return false, nil
595         case 'd':
596                 return true, d.parseDict(v)
597         case 'l':
598                 return true, d.parseList(v)
599         case 'i':
600                 return true, d.parseInt(v)
601         default:
602                 if b >= '0' && b <= '9' {
603                         // It's a string.
604                         d.buf.Reset()
605                         // Write the first digit of the length to the buffer.
606                         d.buf.WriteByte(b)
607                         return true, d.parseString(v)
608                 }
609
610                 d.raiseUnknownValueType(b, d.Offset-1)
611         }
612         panic("unreachable")
613 }
614
615 // An unknown bencode type character was encountered.
616 func (d *Decoder) raiseUnknownValueType(b byte, offset int64) {
617         panic(&SyntaxError{
618                 Offset: offset,
619                 What:   fmt.Errorf("unknown value type %+q", b),
620         })
621 }
622
623 func (d *Decoder) parseValueInterface() (interface{}, bool) {
624         b, err := d.r.ReadByte()
625         if err != nil {
626                 panic(err)
627         }
628         d.Offset++
629
630         switch b {
631         case 'e':
632                 return nil, false
633         case 'd':
634                 return d.parseDictInterface(), true
635         case 'l':
636                 return d.parseListInterface(), true
637         case 'i':
638                 return d.parseIntInterface(), true
639         default:
640                 if b >= '0' && b <= '9' {
641                         // string
642                         // append first digit of the length to the buffer
643                         d.buf.WriteByte(b)
644                         return d.parseStringInterface(), true
645                 }
646
647                 d.raiseUnknownValueType(b, d.Offset-1)
648                 panic("unreachable")
649         }
650 }
651
652 // Called after 'i', for an arbitrary integer size.
653 func (d *Decoder) parseIntInterface() (ret interface{}) {
654         start := d.Offset - 1
655
656         if err := d.readInt(); err != nil {
657                 panic(err)
658         }
659         n, err := strconv.ParseInt(d.buf.String(), 10, 64)
660         if ne, ok := err.(*strconv.NumError); ok && ne.Err == strconv.ErrRange {
661                 i := new(big.Int)
662                 _, ok := i.SetString(d.buf.String(), 10)
663                 if !ok {
664                         panic(&SyntaxError{
665                                 Offset: start,
666                                 What:   errors.New("failed to parse integer"),
667                         })
668                 }
669                 ret = i
670         } else {
671                 checkForIntParseError(err, start)
672                 ret = n
673         }
674
675         d.buf.Reset()
676         return
677 }
678
679 func (d *Decoder) readBytes(length int) []byte {
680         b, err := io.ReadAll(io.LimitReader(d.r, int64(length)))
681         if err != nil {
682                 panic(err)
683         }
684         if len(b) != length {
685                 panic(fmt.Errorf("read %v bytes expected %v", len(b), length))
686         }
687         return b
688 }
689
690 func (d *Decoder) parseStringInterface() string {
691         length, err := d.parseStringLength()
692         if err != nil {
693                 panic(err)
694         }
695         b := d.readBytes(int(length))
696         d.Offset += int64(len(b))
697         if err != nil {
698                 panic(&SyntaxError{Offset: d.Offset, What: err})
699         }
700         return bytesAsString(b)
701 }
702
703 func (d *Decoder) parseDictInterface() interface{} {
704         dict := make(map[string]interface{})
705         var lastKey string
706         lastKeyOk := false
707         for {
708                 start := d.Offset
709                 keyi, ok := d.parseValueInterface()
710                 if !ok {
711                         break
712                 }
713
714                 key, ok := keyi.(string)
715                 if !ok {
716                         panic(&SyntaxError{
717                                 Offset: d.Offset,
718                                 What:   errors.New("non-string key in a dict"),
719                         })
720                 }
721                 if lastKeyOk && key <= lastKey {
722                         d.throwSyntaxError(start, fmt.Errorf("dict keys unsorted: %q <= %q", key, lastKey))
723                 }
724                 start = d.Offset
725                 valuei, ok := d.parseValueInterface()
726                 if !ok {
727                         d.throwSyntaxError(start, fmt.Errorf("dict elem missing value [key=%v]", key))
728                 }
729
730                 lastKey = key
731                 lastKeyOk = true
732                 dict[key] = valuei
733         }
734         return dict
735 }
736
737 func (d *Decoder) parseListInterface() (list []interface{}) {
738         list = []interface{}{}
739         valuei, ok := d.parseValueInterface()
740         for ok {
741                 list = append(list, valuei)
742                 valuei, ok = d.parseValueInterface()
743         }
744         return
745 }
746
747 func (d *Decoder) getMaxStrLen() int64 {
748         if d.MaxStrLen == 0 {
749                 return DefaultDecodeMaxStrLen
750         }
751         return d.MaxStrLen
752 }