path: root/decode.go

// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
//
// Some doc comments are
// copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//
// SPDX-License-Identifier: BSD-3-Clause

package lowmemjson

import (
	"bytes"
	"encoding"
	"fmt"
	"io"
	"reflect"
	"strconv"
	"strings"
	"unicode/utf16"
	"unicode/utf8"

	"git.lukeshu.com/go/lowmemjson/internal/base64dec"
	"git.lukeshu.com/go/lowmemjson/internal/fastio"
	"git.lukeshu.com/go/lowmemjson/internal/jsonparse"
	"git.lukeshu.com/go/lowmemjson/internal/jsonstruct"
)

// Decodable is the interface implemented by types that can decode a
// JSON representation of themselves.  Decodable is a
// low-memory-overhead replacement for the json.Unmarshaler interface.
//
// On the io.RuneScanner passed to DecodeJSON:
//
//   - .UnreadRune() will return ErrInvalidUnreadRune if the last
//     operation was not a successful .ReadRune() call.
//
//   - .ReadRune() will return io.EOF at the end of the JSON value; it
//     is not possible for .ReadRune() to read past the end of the
//     value in to another value.
//
//   - .ReadRune() will never return invalid JSON; if invalid JSON is
//     encountered, it will use a panic-based mechanism to transfer
//     control back to the Decoder.
//
//   - .ReadRune() never return an error other than io.EOF; if an I/O
//     error is encountered, it will use a panic-based mechanism to
//     transfer control back to the Decoder.
//
// DecodeJSON is expected to consume the entire scanner until io.EOF
// or another is encountered; if it does not, then the parent Decode
// call will return a *DecodeTypeError.
//
// DecodeJSON should return nil (not io.EOF) on success.
//
// Implementor's note: "withLimitingScanner" is the thing to search
// for in decode.go if you want to read up on that io.RuneScanner.
type Decodable interface {
	DecodeJSON(io.RuneScanner) error
}

type decodeStackItem struct {
	par reflect.Type
	idx any
}

// A Decoder reads and decodes values from an input stream of JSON
// elements.
//
// Decoder is analogous to, and has a similar API to the standard
// library's encoding/json.Decoder.  Differences are:
//
//   - lowmemjson.NewDecoder takes an io.RuneScanner, while
//     json.NewDecoder takes an io.Reader.
//
//   - lowmemjson.Decoder does not have a .Buffered() method, while
//     json.Decoder does.
//
//   - lowmemjson.Decoder does not have a .Token() method, while
//     json.Decoder does.
//
// If something more similar to a json.Decoder is desired,
// lowmemjson/compat/json.NewDecoder takes an io.Reader (and turns it
// into an io.RuneScanner by wrapping it in a bufio.Reader), and
// lowmemjson/compat/json.Decoder has a .Buffered() method; though
// lowmemjson/compat/json.Decoder also lacks the .Token() method.
type Decoder struct {
	io runeTypeScanner

	// config
	disallowUnknownFields bool
	useNumber             bool

	// state
	posStack    []int64
	structStack []decodeStackItem
	typeErr     *DecodeError
}

const maxNestingDepth = 10000

// NewDecoder returns a new Decoder that reads from r.
//
// NewDecoder is analogous to the standard library's
// encoding/json.NewDecoder, but takes an io.RuneScanner rather than
// an io.Reader.
func NewDecoder(r io.RuneScanner) *Decoder {
	return &Decoder{
		io: runeTypeScanner{
			inner: r,
			parser: jsonparse.Parser{
				MaxDepth: maxNestingDepth,
			},
		},
	}
}

// DisallowUnknownFields causes the Decoder to return an error when
// the destination is a struct and the input contains object keys
// which do not match any non-ignored, exported fields in the
// destination.
//
// This is identical to the standard library's
// encoding/json.Decoder.DisallowUnknownFields.
func (dec *Decoder) DisallowUnknownFields() { dec.disallowUnknownFields = true }

// UseNumber causes the Decoder to unmarshal a number into an
// interface{} as a Number instead of as a float64.
//
// This is identical to the standard library's
// encoding/json.Decoder.UseNumber.
func (dec *Decoder) UseNumber() { dec.useNumber = true }

// InputOffset returns the input stream byte offset of the current
// decoder position.  The offset gives the location of the rune that
// will be returned from the next call to .ReadRune().
//
// This is identical to the standard library's
// encoding/json.Decoder.InputOffset.
func (dec *Decoder) InputOffset() int64 { return dec.io.InputOffset() }

// More reports whether there is more to the stream of JSON elements,
// or if the Decoder has reached EOF or an error.
//
// More is identical to the standard library's
// encoding/json.Decoder.More.
func (dec *Decoder) More() bool {
	dec.io.Reset()
	_, _, t, e := dec.io.ReadRuneType()
	_ = dec.io.UnreadRune() // best effort
	return e == nil && t != jsonparse.RuneTypeEOF
}

func (dec *Decoder) posStackPush() {
	dec.posStack = append(dec.posStack, dec.InputOffset())
}

func (dec *Decoder) posStackPop() {
	dec.posStack = dec.posStack[:len(dec.posStack)-1]
}

func (dec *Decoder) structStackPush(par reflect.Type, idx any) {
	dec.structStack = append(dec.structStack, decodeStackItem{par, idx})
}

func (dec *Decoder) structStackPop() {
	dec.structStack = dec.structStack[:len(dec.structStack)-1]
}

func (dec *Decoder) structStackStr() string {
	var buf strings.Builder
	buf.WriteString("v")
	for _, item := range dec.structStack {
		fmt.Fprintf(&buf, "[%#v]", item.idx)
	}
	return buf.String()
}

func (dec *Decoder) structStackParent() string {
	last := len(dec.structStack) - 1
	if last > 0 && dec.structStack[last].par.Kind() != reflect.Struct && dec.structStack[last-1].par.Kind() == reflect.Struct {
		last--
	}
	if last >= 0 && dec.structStack[last].par.Kind() == reflect.Struct {
		return dec.structStack[last].par.Name()
	}
	return ""
}

func (dec *Decoder) structStackName() string {
	if dec.structStackParent() == "" {
		return ""
	}
	var fields []string
	for _, elem := range dec.structStack {
		if elem.par.Kind() == reflect.Struct {
			fields = append(fields, elem.idx.(string))
		}
	}
	return strings.Join(fields, ".")
}

// DecodeThenEOF is like Decode, but emits an error if there is extra
// data after the JSON.  A JSON document is specified to be a single
// JSON element; repeated calls to Decoder.Decode will happily decode
// a stream of multiple JSON elements.
func (dec *Decoder) DecodeThenEOF(ptr any) (err error) {
	if err := dec.Decode(ptr); err != nil {
		return err
	}
	_, _, t, err := dec.io.ReadRuneType()
	switch t {
	case jsonparse.RuneTypeError:
		return &DecodeError{
			Err: err,
		}
	case jsonparse.RuneTypeEOF:
		return nil
	default:
		panic(fmt.Errorf("should not happen: .ReadRuneType returned non-error non-EOF after decode without .Reset being called: '%v'", t))
	}
}

// Decode reads the next JSON element from the Decoder's input stream
// and stores it in the value pointed to by ptr.
//
// See the [documentation for encoding/json.Unmarshal] for details
// about the conversion of JSON into a Go value; Decode behaves
// identically to that, with the exception that in addition to the
// json.Unmarshaler interface it also checks for the Decodable
// interface.
//
// [documentation for encoding/json.Unmarshal]: https://pkg.go.dev/encoding/json@go1.20#Unmarshal
func (dec *Decoder) Decode(ptr any) (err error) {
	ptrVal := reflect.ValueOf(ptr)
	if ptrVal.Kind() != reflect.Pointer || ptrVal.IsNil() || !ptrVal.Elem().CanSet() {
		return &DecodeArgumentError{
			// don't use ptrVal.Type() because ptrVal might be invalid if ptr==nil
			Type: reflect.TypeOf(ptr),
		}
	}

	dec.typeErr = nil
	dec.io.Reset()
	dec.io.PushReadBarrier()
	if err := dec.decode(ptrVal.Elem(), false); err != nil {
		return err
	}
	dec.io.PopReadBarrier()
	if dec.typeErr != nil {
		return dec.typeErr
	}
	return nil
}

// io helpers //////////////////////////////////////////////////////////////////////////////////////

func (dec *Decoder) newTypeError(jTyp string, gTyp reflect.Type, err error) {
	if dec.typeErr != nil {
		return
	}
	dec.typeErr = &DecodeError{
		Field:       dec.structStackStr(),
		FieldParent: dec.structStackParent(),
		FieldName:   dec.structStackName(),
		Err: &DecodeTypeError{
			GoType:   gTyp,
			JSONType: jTyp,
			Err:      err,
			Offset:   dec.posStack[len(dec.posStack)-1],
		},
	}
}

func (dec *Decoder) readRune() (rune, jsonparse.RuneType, *DecodeError) {
	c, _, t, e := dec.io.ReadRuneType()
	if e != nil {
		return 0, 0, &DecodeError{
			Field:       dec.structStackStr(),
			FieldParent: dec.structStackParent(),
			FieldName:   dec.structStackName(),
			Err:         e,
		}
	}
	return c, t, nil
}

func (dec *Decoder) unreadRune() {
	if err := dec.io.UnreadRune(); err != nil {
		// .UnreadRune() must succeed if the previous call was
		// .ReadRune(), which it always is for this code.
		panic(fmt.Errorf("should not happen: UnreadRune: %w", err))
	}
}

func (dec *Decoder) peekRuneType() (jsonparse.RuneType, *DecodeError) {
	_, t, err := dec.readRune()
	if err != nil {
		return 0, err
	}
	dec.unreadRune()
	return t, nil
}

// expectRuneOrPanic is for when you *know* what the next
// non-whitespace rune is going to be; for it to be anything else
// would be a syntax error.  It will return an error for I/O errors
// and syntax errors, but panic if the result is not what was
// expected; as that would indicate a bug in the agreement between the
// parser and the decoder.
func (dec *Decoder) expectRuneOrPanic(ec rune, et jsonparse.RuneType) *DecodeError {
	ac, at, err := dec.readRune()
	if err != nil {
		return err
	}
	if ac != ec || at != et {
		panic(fmt.Errorf("should not happen: expected %q/%v but got %q/%v", ec, et, ac, at))
	}
	return nil
}

type decRuneScanner struct {
	dec *Decoder
	eof bool
}

type scannerPanic *DecodeError

func (sc *decRuneScanner) ReadRune() (rune, int, error) {
	if sc.eof {
		return 0, 0, io.EOF
	}
	c, s, t, e := sc.dec.io.ReadRuneType()
	if t == jsonparse.RuneTypeEOF {
		sc.eof = true
		sc.dec.io.PopReadBarrier()
		return 0, 0, io.EOF
	}
	if e != nil {
		panic(scannerPanic(&DecodeError{
			Field:       sc.dec.structStackStr(),
			FieldParent: sc.dec.structStackParent(),
			FieldName:   sc.dec.structStackName(),
			Err:         e,
		}))
	}
	return c, s, nil
}

func (sc *decRuneScanner) UnreadRune() error {
	return sc.dec.io.UnreadRune()
}

func (dec *Decoder) withLimitingScanner(gTyp reflect.Type, fn func(io.RuneScanner) error) (err *DecodeError) {
	t, err := dec.peekRuneType()
	if err != nil {
		return err
	}
	dec.io.PushReadBarrier()
	defer func() {
		if r := recover(); r != nil {
			if sp, ok := r.(scannerPanic); ok {
				err = (*DecodeError)(sp)
			} else {
				panic(r)
			}
		}
	}()
	l := &decRuneScanner{dec: dec}
	if err := fn(l); err != nil {
		dec.newTypeError(t.JSONType(), gTyp, err)
	}
	if _, _, err := l.ReadRune(); err != io.EOF {
		dec.newTypeError(t.JSONType(), gTyp, fmt.Errorf("did not consume entire %s", t.JSONType()))
		for err != io.EOF {
			_, _, err = l.ReadRune()
		}
	}
	return nil
}

// decoder main ////////////////////////////////////////////////////////////////////////////////////

var kind2bits = map[reflect.Kind]int{
	reflect.Int:   int(32 << (^uint(0) >> 63)),
	reflect.Int8:  8,
	reflect.Int16: 16,
	reflect.Int32: 32,
	reflect.Int64: 64,

	reflect.Uint:   int(32 << (^uint(0) >> 63)),
	reflect.Uint8:  8,
	reflect.Uint16: 16,
	reflect.Uint32: 32,
	reflect.Uint64: 64,

	reflect.Uintptr: int(32 << (^uintptr(0) >> 63)),

	reflect.Float32: 32,
	reflect.Float64: 64,
}

func (dec *Decoder) decode(val reflect.Value, nullOK bool) *DecodeError {
	dec.posStackPush()
	defer dec.posStackPop()
	typ := val.Type()
	switch {
	case val.CanAddr() && reflect.PointerTo(typ) == rawMessagePtrType:
		t, err := dec.peekRuneType()
		if err != nil {
			return err
		}
		var buf bytes.Buffer
		if err := dec.scan(&buf); err != nil {
			return err
		}
		if err := val.Addr().Interface().(*RawMessage).UnmarshalJSON(buf.Bytes()); err != nil {
			dec.newTypeError(t.JSONType(), reflect.PointerTo(typ), err)
		}
	case val.CanAddr() && reflect.PointerTo(typ).Implements(decodableType):
		obj := val.Addr().Interface().(Decodable)
		return dec.withLimitingScanner(reflect.PointerTo(typ), obj.DecodeJSON)
	case val.CanAddr() && reflect.PointerTo(typ).Implements(jsonUnmarshalerType):
		t, err := dec.peekRuneType()
		if err != nil {
			return err
		}
		var buf bytes.Buffer
		if err := dec.scan(&buf); err != nil {
			return err
		}
		obj := val.Addr().Interface().(jsonUnmarshaler)
		if err := obj.UnmarshalJSON(buf.Bytes()); err != nil {
			dec.newTypeError(t.JSONType(), reflect.PointerTo(typ), err)
		}
	case val.CanAddr() && reflect.PointerTo(typ).Implements(textUnmarshalerType):
		if ok, err := dec.maybeDecodeNull(nullOK); ok {
			return err
		}
		var buf bytes.Buffer
		if err := dec.decodeString(reflect.PointerTo(typ), &buf); err != nil {
			return err
		}
		obj := val.Addr().Interface().(encoding.TextUnmarshaler)
		if err := obj.UnmarshalText(buf.Bytes()); err != nil {
			dec.newTypeError("string", reflect.PointerTo(typ), err)
		}
	default:
		switch kind := typ.Kind(); kind {
		case reflect.Bool:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			b, err := dec.decodeBool(typ)
			if err != nil {
				return err
			}
			val.SetBool(b)
		case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			if t, err := dec.peekRuneType(); err != nil {
				return err
			} else if !t.IsNumber() {
				dec.newTypeError(t.JSONType(), typ, nil)
				return dec.scan(fastio.Discard)
			}
			var buf strings.Builder
			if err := dec.scan(&buf); err != nil {
				return err
			}
			n, err := strconv.ParseInt(buf.String(), 10, kind2bits[kind])
			if err != nil {
				dec.newTypeError("number "+buf.String(), typ, err)
				return nil
			}
			val.SetInt(n)
		case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			if t, err := dec.peekRuneType(); err != nil {
				return err
			} else if !t.IsNumber() {
				dec.newTypeError(t.JSONType(), typ, nil)
				return dec.scan(fastio.Discard)
			}
			var buf strings.Builder
			if err := dec.scan(&buf); err != nil {
				return err
			}
			n, err := strconv.ParseUint(buf.String(), 10, kind2bits[kind])
			if err != nil {
				dec.newTypeError("number "+buf.String(), typ, err)
				return nil
			}
			val.SetUint(n)
		case reflect.Float32, reflect.Float64:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			if t, err := dec.peekRuneType(); err != nil {
				return err
			} else if !t.IsNumber() {
				dec.newTypeError(t.JSONType(), typ, nil)
				return dec.scan(fastio.Discard)
			}
			var buf strings.Builder
			if err := dec.scan(&buf); err != nil {
				return err
			}
			n, err := strconv.ParseFloat(buf.String(), kind2bits[kind])
			if err != nil {
				dec.newTypeError("number "+buf.String(), typ, err)
				return nil
			}
			val.SetFloat(n)
		case reflect.String:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			var buf strings.Builder
			if typ == numberType {
				t, err := dec.peekRuneType()
				if err != nil {
					return err
				}
				if err := dec.scan(&buf); err != nil {
					return err
				}
				if !t.IsNumber() {
					dec.newTypeError(t.JSONType(), typ,
						fmt.Errorf("json: invalid number literal, trying to unmarshal %q into Number",
							buf.String()))
					return nil
				}
				val.SetString(buf.String())
			} else {
				if err := dec.decodeString(typ, &buf); err != nil {
					return err
				}
				val.SetString(buf.String())
			}
		case reflect.Interface:
			t, err := dec.peekRuneType()
			if err != nil {
				return err
			}
			if typ.NumMethod() > 0 {
				dec.newTypeError(t.JSONType(), typ, ErrDecodeNonEmptyInterface)
				return dec.scan(fastio.Discard)
			}
			// If the interface stores a pointer, try to use the type information of the pointer.
			if !val.IsNil() && val.Elem().Kind() == reflect.Pointer {
				// Follow a chain of pointers until we find the first settable
				// pointer (if any).
				ptr := val.Elem()
				for {
					if ptr.CanSet() || ptr.IsNil() || ptr.Elem().Kind() != reflect.Pointer {
						// We've reached the end of the line, good or bad.
						break
					}
					ptr = ptr.Elem()
				}
				// ptr.Elem() != val
				//
				//   Avoid the loop of an interface storing a pointer to its own
				//   address.  We only need to worry about this at the leaf (and not
				//   in the loop) because the only way it's possible is if there's
				//   an interface in there, which'd break from the loop on its own.
				//
				// ptr.CanSet() || t != jsonparse.RuneTypeNullN
				//
				//   We only need the pointer itself to be settable if we're
				//   decoding null.
				if ptr.Elem() != val && (ptr.CanSet() || t != jsonparse.RuneTypeNullN) {
					if err := dec.decode(ptr, false); err != nil {
						return err
					}
					break
				}
			}
			// Couldn't get type information from a pointer; fall back to untyped mode.
			switch t {
			case jsonparse.RuneTypeNullN:
				if err := dec.decodeNull(); err != nil {
					return err
				}
				val.Set(reflect.Zero(typ))
			default:
				v, err := dec.decodeAny()
				if err != nil {
					return err
				}
				if v != nil {
					val.Set(reflect.ValueOf(v))
				}
			}
		case reflect.Struct:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			index := jsonstruct.IndexStruct(typ)
			var nameBuf strings.Builder
			return dec.decodeObject(typ, func() *DecodeError {
				dec.posStackPush()
				defer dec.posStackPop()
				nameBuf.Reset()
				return dec.decodeString(nil, &nameBuf)
			}, func() *DecodeError {
				dec.posStackPush()
				defer dec.posStackPop()
				name := nameBuf.String()
				dec.structStackPush(typ, name)
				defer dec.structStackPop()
				idx, ok := index.ByName[name]
				if !ok {
					for oidx := range index.ByPos {
						if strings.EqualFold(name, index.ByPos[oidx].Name) {
							idx = oidx
							ok = true
							break
						}
					}
				}
				if !ok {
					if dec.disallowUnknownFields {
						dec.newTypeError("", typ, fmt.Errorf("json: unknown field %q", name))
					}
					return dec.scan(fastio.Discard)
				}
				field := index.ByPos[idx]
				fVal := val
				for _, idx := range field.Path {
					if fVal.Kind() == reflect.Pointer {
						if fVal.IsNil() && !fVal.CanSet() { // https://golang.org/issue/21357
							dec.newTypeError("", fVal.Type().Elem(),
								fmt.Errorf("json: cannot set embedded pointer to unexported struct: %v",
									fVal.Type().Elem()))
							return dec.scan(fastio.Discard)
						}
						t, err := dec.peekRuneType()
						if err != nil {
							return err
						}
						if t != jsonparse.RuneTypeNullN {
							if fVal.IsNil() {
								fVal.Set(reflect.New(fVal.Type().Elem()))
							}
							fVal = fVal.Elem()
						}
					}
					fVal = fVal.Field(idx)
				}
				if field.Quote {
					t, err := dec.peekRuneType()
					if err != nil {
						return err
					}
					switch t {
					case jsonparse.RuneTypeNullN:
						if err := dec.decodeNull(); err != nil {
							return err
						}
						switch fVal.Kind() {
						// XXX: I can't justify this list, other than "it's what encoding/json
						// does, but I don't understand their rationale".
						case reflect.Interface, reflect.Pointer, reflect.Map, reflect.Slice:
							fVal.Set(reflect.Zero(fVal.Type()))
						default:
							// do nothing???
						}
					case jsonparse.RuneTypeStringBeg:
						// TODO: Figure out how to do this without buffering, have correct offsets.
						var buf bytes.Buffer
						if err := dec.decodeString(nil, &buf); err != nil {
							return err
						}
						if err := NewDecoder(bytes.NewReader(buf.Bytes())).Decode(fVal.Addr().Interface()); err != nil {
							if str := buf.String(); str != "null" {
								dec.newTypeError("", fVal.Type(),
									fmt.Errorf("json: invalid use of ,string struct tag, trying to unmarshal %q into %v",
										str, fVal.Type()))
							}
						}
					default:
						dec.newTypeError(t.JSONType(), fVal.Type(),
							fmt.Errorf("json: invalid use of ,string struct tag, trying to unmarshal unquoted value into %v",
								fVal.Type()))
						return dec.scan(fastio.Discard)
					}
					return nil
				} else {
					return dec.decode(fVal, true)
				}
			})
		case reflect.Map:
			t, err := dec.peekRuneType()
			if err != nil {
				return err
			}
			switch t {
			case jsonparse.RuneTypeNullN:
				if err := dec.decodeNull(); err != nil {
					return err
				}
				val.Set(reflect.Zero(typ))
			case jsonparse.RuneTypeObjectBeg:
				if val.IsNil() {
					val.Set(reflect.MakeMap(typ))
				}
				var nameBuf bytes.Buffer
				var nameValPtr reflect.Value
				return dec.decodeObject(typ, func() *DecodeError {
					dec.posStackPush()
					defer dec.posStackPop()
					nameBuf.Reset()
					if err := dec.decodeString(nil, &nameBuf); err != nil {
						return err
					}
					nameValTyp := typ.Key()
					nameValPtr = reflect.New(nameValTyp)
					switch {
					case reflect.PointerTo(nameValTyp).Implements(textUnmarshalerType):
						obj := nameValPtr.Interface().(encoding.TextUnmarshaler)
						if err := obj.UnmarshalText(nameBuf.Bytes()); err != nil {
							dec.newTypeError("string", reflect.PointerTo(nameValTyp), err)
						}
					default:
						switch nameValTyp.Kind() {
						case reflect.String:
							nameValPtr.Elem().SetString(nameBuf.String())
						case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
							n, err := strconv.ParseInt(nameBuf.String(), 10, kind2bits[nameValTyp.Kind()])
							if err != nil {
								dec.newTypeError("number "+nameBuf.String(), nameValTyp, err)
								return nil
							}
							nameValPtr.Elem().SetInt(n)
						case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
							n, err := strconv.ParseUint(nameBuf.String(), 10, kind2bits[nameValTyp.Kind()])
							if err != nil {
								dec.newTypeError("number "+nameBuf.String(), nameValTyp, err)
								return nil
							}
							nameValPtr.Elem().SetUint(n)
						default:
							dec.newTypeError("object", typ, &DecodeArgumentError{Type: nameValTyp})
						}
					}
					return nil
				}, func() *DecodeError {
					dec.posStackPush()
					defer dec.posStackPop()
					dec.structStackPush(typ, nameValPtr.Elem())
					defer dec.structStackPop()

					fValPtr := reflect.New(typ.Elem())
					if err := dec.decode(fValPtr.Elem(), false); err != nil {
						return err
					}

					val.SetMapIndex(nameValPtr.Elem(), fValPtr.Elem())
					return nil
				})
			default:
				dec.newTypeError(t.JSONType(), typ, nil)
			}
		case reflect.Slice:
			t, err := dec.peekRuneType()
			if err != nil {
				return err
			}
			switch {
			case typ.Elem().Kind() == reflect.Uint8 && !(t == jsonparse.RuneTypeArrayBeg && (false ||
				reflect.PointerTo(typ.Elem()).Implements(decodableType) ||
				reflect.PointerTo(typ.Elem()).Implements(jsonUnmarshalerType) ||
				reflect.PointerTo(typ.Elem()).Implements(textUnmarshalerType))):
				switch t {
				case jsonparse.RuneTypeNullN:
					if err := dec.decodeNull(); err != nil {
						return err
					}
					val.Set(reflect.Zero(typ))
				case jsonparse.RuneTypeStringBeg:
					if typ.Elem() == byteType {
						var buf bytes.Buffer
						if err := dec.decodeString(typ, base64dec.NewBase64Decoder(&buf)); err != nil {
							return err
						}
						val.Set(reflect.ValueOf(buf.Bytes()))
					} else {
						// TODO: Surely there's a better way.  At the very least, we should
						// avoid buffering.
						var buf bytes.Buffer
						if err := dec.decodeString(typ, base64dec.NewBase64Decoder(&buf)); err != nil {
							return err
						}
						bs := buf.Bytes()
						val.Set(reflect.MakeSlice(typ, len(bs), len(bs)))
						for i := 0; i < len(bs); i++ {
							val.Index(i).Set(reflect.ValueOf(bs[i]).Convert(typ.Elem()))
						}
					}
				default:
					dec.newTypeError(t.JSONType(), typ, nil)
				}
			default:
				switch t {
				case jsonparse.RuneTypeNullN:
					if err := dec.decodeNull(); err != nil {
						return err
					}
					val.Set(reflect.Zero(typ))
				case jsonparse.RuneTypeArrayBeg:
					if val.IsNil() {
						val.Set(reflect.MakeSlice(typ, 0, 0))
					}
					if val.Len() > 0 {
						val.Set(val.Slice(0, 0))
					}
					i := 0
					return dec.decodeArray(typ, func() *DecodeError {
						dec.posStackPush()
						defer dec.posStackPop()
						dec.structStackPush(typ, i)
						defer dec.structStackPop()
						mValPtr := reflect.New(typ.Elem())
						if err := dec.decode(mValPtr.Elem(), false); err != nil {
							return err
						}
						val.Set(reflect.Append(val, mValPtr.Elem()))
						i++
						return nil
					})
				default:
					dec.newTypeError(t.JSONType(), typ, nil)
				}
			}
		case reflect.Array:
			if ok, err := dec.maybeDecodeNull(nullOK); ok {
				return err
			}
			i := 0
			n := val.Len()
			if err := dec.decodeArray(typ, func() *DecodeError {
				dec.posStackPush()
				defer dec.posStackPop()
				dec.structStackPush(typ, i)
				defer dec.structStackPop()
				if i < n {
					mValPtr := reflect.New(typ.Elem())
					if err := dec.decode(mValPtr.Elem(), false); err != nil {
						return err
					}
					val.Index(i).Set(mValPtr.Elem())
				} else {
					if err := dec.scan(fastio.Discard); err != nil {
						return err
					}
				}
				i++
				return nil
			}); err != nil {
				return err
			}
			for ; i < n; i++ {
				val.Index(i).Set(reflect.Zero(typ.Elem()))
			}
		case reflect.Pointer:
			t, err := dec.peekRuneType()
			if err != nil {
				return err
			}
			switch t {
			case jsonparse.RuneTypeNullN:
				if err := dec.decodeNull(); err != nil {
					return err
				}
				val.Set(reflect.Zero(typ))
			default:
				if val.IsNil() {
					val.Set(reflect.New(typ.Elem()))
				}
				return dec.decode(val.Elem(), false)
			}
		default:
			dec.newTypeError("", typ, fmt.Errorf("unsupported type (kind=%v)", typ.Kind()))
		}
	}
	return nil
}

func (dec *Decoder) scan(out fastio.RuneWriter) *DecodeError {
	dec.io.PushReadBarrier()
	for {
		c, t, err := dec.readRune()
		if err != nil {
			return err
		}
		if t == jsonparse.RuneTypeEOF {
			break
		}
		_, _ = out.WriteRune(c)
	}
	dec.io.PopReadBarrier()
	return nil
}

func (dec *Decoder) decodeAny() (any, *DecodeError) {
	t, err := dec.peekRuneType()
	if err != nil {
		return nil, err
	}
	switch t {
	case jsonparse.RuneTypeObjectBeg:
		ret := make(map[string]any)
		typ := reflect.TypeOf(ret)
		var nameBuf strings.Builder
		if err := dec.decodeObject(typ, func() *DecodeError {
			dec.posStackPush()
			defer dec.posStackPop()
			nameBuf.Reset()
			return dec.decodeString(nil, &nameBuf)
		}, func() *DecodeError {
			dec.posStackPush()
			defer dec.posStackPop()
			name := nameBuf.String()
			dec.structStackPush(typ, name)
			defer dec.structStackPop()
			v, err := dec.decodeAny()
			if err != nil {
				return err
			}
			ret[name] = v
			return nil
		}); err != nil {
			return nil, err
		}
		return ret, nil
	case jsonparse.RuneTypeArrayBeg:
		ret := []any{}
		typ := reflect.TypeOf(ret)
		if err := dec.decodeArray(typ, func() *DecodeError {
			dec.posStackPush()
			defer dec.posStackPop()
			dec.structStackPush(typ, len(ret))
			defer dec.structStackPop()
			v, err := dec.decodeAny()
			if err != nil {
				return err
			}
			ret = append(ret, v)
			return nil
		}); err != nil {
			return nil, err
		}
		return ret, nil
	case jsonparse.RuneTypeStringBeg:
		var buf strings.Builder
		if err := dec.decodeString(nil, &buf); err != nil {
			return nil, err
		}
		return buf.String(), nil
	case jsonparse.RuneTypeNumberIntNeg, jsonparse.RuneTypeNumberIntZero, jsonparse.RuneTypeNumberIntDig:
		var buf strings.Builder
		if err := dec.scan(&buf); err != nil {
			return nil, err
		}
		num := Number(buf.String())
		if dec.useNumber {
			return num, nil
		}
		f64, err := num.Float64()
		if err != nil {
			dec.newTypeError("number "+buf.String(), float64Type, err)
			return nil, nil
		}
		return f64, nil
	case jsonparse.RuneTypeTrueT, jsonparse.RuneTypeFalseF:
		return dec.decodeBool(nil)
	case jsonparse.RuneTypeNullN:
		return nil, dec.decodeNull()
	default:
		panic(fmt.Errorf("should not happen: unexpected runeType at beginning of value: %v", t))
	}
}

// DecodeObject is a helper function to ease implementing the
// Decodable interface; allowing the lowmemjson package to handle
// decoding the object syntax, while the Decodable only needs to
// handle decoding the keys and values within the object.
//
// Outside of implementing Decodable.DecodeJSON methods, callers
// should instead simply use NewDecoder(r).Decode(&val) rather than
// attempting to call DecodeObject directly.
func DecodeObject(r io.RuneScanner, decodeKey, decodeVal func(io.RuneScanner) error) error {
	var dec *Decoder
	if dr, ok := r.(*decRuneScanner); ok {
		dec = dr.dec
	} else {
		dec = NewDecoder(r)
	}
	if dec.typeErr != nil {
		oldTypeErr := dec.typeErr
		dec.typeErr = nil
		defer func() { dec.typeErr = oldTypeErr }()
	}
	dec.posStackPush()
	defer dec.posStackPop()
	// TODO Find a better Go type to use than `nil`.
	if err := dec.decodeObject(nil,
		func() *DecodeError {
			dec.posStackPush()
			defer dec.posStackPop()
			// TODO: Find a better Go type to use than `nil`.
			return dec.withLimitingScanner(nil, decodeKey)
		},
		func() *DecodeError {
			dec.posStackPush()
			defer dec.posStackPop()
			// TODO: Find a better Go type to use than `nil`.
			return dec.withLimitingScanner(nil, decodeVal)
		}); err != nil {
		return err
	}
	if dec.typeErr != nil {
		return dec.typeErr
	}
	return nil
}

func (dec *Decoder) decodeObject(gTyp reflect.Type, decodeKey, decodeVal func() *DecodeError) *DecodeError {
	if _, t, err := dec.readRune(); err != nil {
		return err
	} else if t != jsonparse.RuneTypeObjectBeg {
		dec.newTypeError(t.JSONType(), gTyp, nil)
		dec.unreadRune()
		return dec.scan(fastio.Discard)
	}
	_, t, err := dec.readRune()
	if err != nil {
		return err
	}
	switch t {
	case jsonparse.RuneTypeObjectEnd:
		return nil
	case jsonparse.RuneTypeStringBeg:
	decodeMember:
		dec.unreadRune()
		if err := decodeKey(); err != nil {
			return err
		}
		if err := dec.expectRuneOrPanic(':', jsonparse.RuneTypeObjectColon); err != nil {
			return err
		}
		if err := decodeVal(); err != nil {
			return err
		}
		_, t, err := dec.readRune()
		if err != nil {
			return err
		}
		switch t {
		case jsonparse.RuneTypeObjectComma:
			if err := dec.expectRuneOrPanic('"', jsonparse.RuneTypeStringBeg); err != nil {
				return err
			}
			goto decodeMember
		case jsonparse.RuneTypeObjectEnd:
			return nil
		default:
			panic(fmt.Errorf("should not happen: unexpected runeType after k/v pair in object: %v", t))
		}
	default:
		panic(fmt.Errorf("should not happen: unexpected runeType after opening '{' of object: %v", t))
	}
}

// DecodeArray is a helper function to ease implementing the Decoder
// interface; allowing the lowmemjson package to handle decoding the
// array syntax, while the Decodable only needs to handle decoding
// members within the array.
//
// Outside of implementing Decodable.DecodeJSON methods, callers
// should instead simply use NewDecoder(r).Decode(&val) rather than
// attempting to call DecodeArray directly.
func DecodeArray(r io.RuneScanner, decodeMember func(r io.RuneScanner) error) error {
	var dec *Decoder
	if dr, ok := r.(*decRuneScanner); ok {
		dec = dr.dec
	} else {
		dec = NewDecoder(r)
	}
	if dec.typeErr != nil {
		oldTypeErr := dec.typeErr
		dec.typeErr = nil
		defer func() { dec.typeErr = oldTypeErr }()
	}
	dec.posStackPush()
	defer dec.posStackPop()
	// TODO Find a better Go type to use than `nil`.
	if err := dec.decodeArray(nil, func() *DecodeError {
		dec.posStackPush()
		defer dec.posStackPop()
		// TODO: Find a better Go type to use than `nil`.
		return dec.withLimitingScanner(nil, decodeMember)
	}); err != nil {
		return err
	}
	if dec.typeErr != nil {
		return dec.typeErr
	}
	return nil
}

func (dec *Decoder) decodeArray(gTyp reflect.Type, decodeMember func() *DecodeError) *DecodeError {
	if _, t, err := dec.readRune(); err != nil {
		return err
	} else if t != jsonparse.RuneTypeArrayBeg {
		dec.newTypeError(t.JSONType(), gTyp, nil)
		dec.unreadRune()
		return dec.scan(fastio.Discard)
	}
	_, t, err := dec.readRune()
	if err != nil {
		return err
	}
	switch t {
	case jsonparse.RuneTypeArrayEnd:
		return nil
	default:
		dec.unreadRune()
	decodeNextMember:
		if err := decodeMember(); err != nil {
			return err
		}
		_, t, err := dec.readRune()
		if err != nil {
			return err
		}
		switch t {
		case jsonparse.RuneTypeArrayComma:
			goto decodeNextMember
		case jsonparse.RuneTypeArrayEnd:
			return nil
		default:
			panic(fmt.Errorf("should not happen: unexpected runeType after array item: %v", t))
		}
	}
}

// DecodeString is a helper function to eas implementing the Decodable
// interface; allowing the lowmemjson package to handle decoding
// character escapes and such, while the Decodable only needs to
// handle what to do with the decoded runes.
//
// Outside of implementing Decodable.DecodeJSON methods, callers
// should instead simply use NewDecoder(r).Decode(&val) rather than
// attempting to call DecodeString directly.
func DecodeString(in io.RuneScanner, out fastio.RuneWriter) error {
	var dec *Decoder
	if dr, ok := in.(*decRuneScanner); ok {
		dec = dr.dec
	} else {
		dec = NewDecoder(in)
	}
	if dec.typeErr != nil {
		oldTypeErr := dec.typeErr
		dec.typeErr = nil
		defer func() { dec.typeErr = oldTypeErr }()
	}
	dec.posStackPush()
	defer dec.posStackPop()
	// TODO Find a better Go type to use than `nil`.
	if err := dec.decodeString(nil, out); err != nil {
		return err
	}
	if dec.typeErr != nil {
		return dec.typeErr
	}
	return nil
}

func (dec *Decoder) decodeString(gTyp reflect.Type, out fastio.RuneWriter) *DecodeError {
	if _, t, err := dec.readRune(); err != nil {
		return err
	} else if t != jsonparse.RuneTypeStringBeg {
		dec.newTypeError(t.JSONType(), gTyp, nil)
		dec.unreadRune()
		return dec.scan(fastio.Discard)
	}
	var uhex [3]byte
	for {
		c, t, err := dec.readRune()
		if err != nil {
			return err
		}
		switch t {
		case jsonparse.RuneTypeStringChar:
			if _, err := out.WriteRune(c); err != nil {
				dec.newTypeError("string", gTyp, err)
			}
		case jsonparse.RuneTypeStringEsc, jsonparse.RuneTypeStringEscU:
			// do nothing
		case jsonparse.RuneTypeStringEsc1:
			switch c {
			case '"', '\\', '/':
				// self
			case 'b':
				c = '\b'
			case 'f':
				c = '\f'
			case 'n':
				c = '\n'
			case 'r':
				c = '\r'
			case 't':
				c = '\t'
			default:
				panic(fmt.Errorf("should not happen: rune %q is not a RuneTypeStringEsc1", c))
			}
			if _, err := out.WriteRune(c); err != nil {
				dec.newTypeError("string", gTyp, err)
			}
		case jsonparse.RuneTypeStringEscUA:
			uhex[0] = byte(c)
		case jsonparse.RuneTypeStringEscUB:
			uhex[1] = byte(c)
		case jsonparse.RuneTypeStringEscUC:
			uhex[2] = byte(c)
		case jsonparse.RuneTypeStringEscUD:
			c = hexToRune(uhex[0], uhex[1], uhex[2], byte(c))
		handleUnicode:
			if utf16.IsSurrogate(c) {
				t, err := dec.peekRuneType()
				if err != nil {
					return err
				}
				if t != jsonparse.RuneTypeStringEsc {
					if _, err := out.WriteRune(utf8.RuneError); err != nil {
						dec.newTypeError("string", gTyp, err)
					}
					break
				}
				if err := dec.expectRuneOrPanic('\\', jsonparse.RuneTypeStringEsc); err != nil {
					return err
				}
				t, err = dec.peekRuneType()
				if err != nil {
					return err
				}
				if t != jsonparse.RuneTypeStringEscU {
					if _, err := out.WriteRune(utf8.RuneError); err != nil {
						dec.newTypeError("string", gTyp, err)
					}
					break
				}
				if err := dec.expectRuneOrPanic('u', jsonparse.RuneTypeStringEscU); err != nil {
					return err
				}

				b, _, err := dec.readRune()
				if err != nil {
					return err
				}
				uhex[0] = byte(b)
				b, _, err = dec.readRune()
				if err != nil {
					return err
				}
				uhex[1] = byte(b)
				b, _, err = dec.readRune()
				if err != nil {
					return err
				}
				uhex[2] = byte(b)
				b, _, err = dec.readRune()
				if err != nil {
					return err
				}
				c2 := hexToRune(uhex[0], uhex[1], uhex[2], byte(b))
				d := utf16.DecodeRune(c, c2)
				if d == utf8.RuneError {
					if _, err := out.WriteRune(utf8.RuneError); err != nil {
						dec.newTypeError("string", gTyp, err)
					}
					c = c2
					goto handleUnicode
				}
				if _, err := out.WriteRune(d); err != nil {
					dec.newTypeError("string", gTyp, err)
				}
			} else {
				if _, err := out.WriteRune(c); err != nil {
					dec.newTypeError("string", gTyp, err)
				}
			}
		case jsonparse.RuneTypeStringEnd:
			return nil
		default:
			panic(fmt.Errorf("should not happen: unexpected runeType in string: %v", t))
		}
	}
}

func (dec *Decoder) decodeBool(gTyp reflect.Type) (bool, *DecodeError) {
	c, t, err := dec.readRune()
	if err != nil {
		return false, err
	}
	switch c {
	case 't':
		if err := dec.expectRuneOrPanic('r', jsonparse.RuneTypeTrueR); err != nil {
			return false, err
		}
		if err := dec.expectRuneOrPanic('u', jsonparse.RuneTypeTrueU); err != nil {
			return false, err
		}
		if err := dec.expectRuneOrPanic('e', jsonparse.RuneTypeTrueE); err != nil {
			return false, err
		}
		return true, nil
	case 'f':
		if err := dec.expectRuneOrPanic('a', jsonparse.RuneTypeFalseA); err != nil {
			return false, err
		}
		if err := dec.expectRuneOrPanic('l', jsonparse.RuneTypeFalseL); err != nil {
			return false, err
		}
		if err := dec.expectRuneOrPanic('s', jsonparse.RuneTypeFalseS); err != nil {
			return false, err
		}
		if err := dec.expectRuneOrPanic('e', jsonparse.RuneTypeFalseE); err != nil {
			return false, err
		}
		return false, nil
	default:
		dec.newTypeError(t.JSONType(), gTyp, nil)
		return false, nil
	}
}

func (dec *Decoder) decodeNull() *DecodeError {
	if err := dec.expectRuneOrPanic('n', jsonparse.RuneTypeNullN); err != nil {
		return err
	}
	if err := dec.expectRuneOrPanic('u', jsonparse.RuneTypeNullU); err != nil {
		return err
	}
	if err := dec.expectRuneOrPanic('l', jsonparse.RuneTypeNullL1); err != nil {
		return err
	}
	if err := dec.expectRuneOrPanic('l', jsonparse.RuneTypeNullL2); err != nil {
		return err
	}
	return nil
}

func (dec *Decoder) maybeDecodeNull(nullOK bool) (ok bool, err *DecodeError) {
	if nullOK {
		t, err := dec.peekRuneType()
		if err != nil {
			return true, err
		}
		if t == jsonparse.RuneTypeNullN {
			return true, dec.decodeNull()
		}
	}
	return false, nil
}