pickled 2.0.0-alpha5

// Copyright (c) 2015-2021 Georg Brandl.  Licensed under the Apache License,
// Version 2.0 <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0>
// or the MIT license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at
// your option. This file may not be copied, modified, or distributed except
// according to those terms.

//! # Pickle deserialization
//!
//! Note: Serde's interface doesn't support all of Python's primitive types.  In
//! order to deserialize a pickle stream to `value::Value`, use the
//! `value_from_*` functions exported here, not the generic `from_*` functions.

use byteorder::BigEndian;
use byteorder::ByteOrder;
use byteorder::LittleEndian;
use iter_read::IterRead;
use iter_read::IterReadItem;
use num_bigint::BigInt;
use num_bigint::Sign;
use num_traits::ToPrimitive;
use serde::de;
use serde::de::Visitor;
use serde::forward_to_deserialize_any;
use std::borrow::Cow;
use std::char;
use std::collections::BTreeMap;
use std::collections::HashMap;
use std::convert::TryFrom;
use std::fmt;
use std::io;
use std::io::BufRead;
use std::io::BufReader;
use std::io::Read;
use std::iter::FusedIterator;
use std::mem;
use std::str;
use std::str::FromStr;
use std::vec;

use crate::object::DictObject;
use crate::object::ObjectFactory;
use crate::object::PickleObject;
use crate::value::RawHashableValue;
use crate::value::Shared;
use crate::value::SharedFrozen;

use super::consts::*;
use super::error::Error;
use super::error::ErrorCode;
use super::error::Result;
use super::value;

const MEMO_REF_COUNTING: bool = false;

type MemoId = u32;

#[derive(Clone, Debug, Eq, PartialEq)]
enum Global {
    Set,           // builtins/__builtin__.set
    Frozenset,     // builtins/__builtin__.frozenset
    Bytearray,     // builtins/__builtin__.bytearray
    List,          // builtins/__builtin__.list
    Int,           // builtins/__builtin__.int
    Encode,        // _codecs.encode
    Reconstructor, // copy_reg._reconstructor
    // anything else (may be a classobj that is later discarded)
    Other {
        modname: Cow<'static, str>,
        globname: Cow<'static, str>,
    },
}

/// Our intermediate representation of a value.
///
/// The most striking difference to `value::Value` is that it contains a variant
/// for `MemoRef`, which references values put into the "memo" map, and a variant
/// for module globals that we support.
///
/// We also don't use sets and maps at the Rust level, since they are not
/// needed: nothing is ever looked up in them at this stage, and Vecs are much
/// tighter in memory.
#[derive(Debug)]
enum Value {
    MemoRef(MemoId),
    Global(Global),
    None,
    Bool(bool),
    I64(i64),
    Int(BigInt),
    F64(f64),
    Bytes(SharedFrozen<Vec<u8>>),
    String(SharedFrozen<String>),
    List(Shared<Vec<Value>>),
    Tuple(SharedFrozen<Vec<Value>>),
    Set(Shared<Vec<Value>>),
    FrozenSet(SharedFrozen<Vec<Value>>),
    Dict(Shared<Vec<(Value, Value)>>),
    Object(Box<dyn PickleObject>),
}

impl Clone for Value {
    fn clone(&self) -> Self {
        match self {
            Value::MemoRef(id) => Value::MemoRef(*id),
            Value::Global(g) => Value::Global(g.clone()),
            Value::None => Value::None,
            Value::Bool(b) => Value::Bool(*b),
            Value::I64(i) => Value::I64(*i),
            Value::Int(i) => Value::Int(i.clone()),
            Value::F64(f) => Value::F64(*f),
            Value::Bytes(b) => Value::Bytes(b.clone()),
            Value::String(s) => Value::String(s.clone()),
            Value::List(l) => Value::List(l.clone()),
            Value::Tuple(t) => Value::Tuple(t.clone()),
            Value::Set(s) => Value::Set(s.clone()),
            Value::FrozenSet(s) => Value::FrozenSet(s.clone()),
            Value::Dict(d) => Value::Dict(d.clone()),
            Value::Object(o) => Value::Object(o.clone_dyn()),
        }
    }
}

impl PartialEq for Value {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Value::MemoRef(a), Value::MemoRef(b)) => a == b,
            (Value::Global(a), Value::Global(b)) => a == b,
            (Value::None, Value::None) => true,
            (Value::Bool(a), Value::Bool(b)) => a == b,
            (Value::I64(a), Value::I64(b)) => a == b,
            (Value::Int(a), Value::Int(b)) => a == b,
            (Value::F64(a), Value::F64(b)) => a == b,
            (Value::Bytes(a), Value::Bytes(b)) => a == b,
            (Value::String(a), Value::String(b)) => a == b,
            (Value::List(a), Value::List(b)) => a == b,
            (Value::Tuple(a), Value::Tuple(b)) => a == b,
            (Value::Set(a), Value::Set(b)) => a == b,
            (Value::FrozenSet(a), Value::FrozenSet(b)) => a == b,
            (Value::Dict(a), Value::Dict(b)) => a == b,
            (Value::Object(a), Value::Object(b)) => a.eq_dyn(b.as_ref()),
            _ => false,
        }
    }
}

impl Eq for Value {}

/// Options for deserializing.
#[derive(Default)]
pub struct DeOptions {
    decode_strings: bool,
    replace_unresolved_globals: bool,
    replace_recursive_structures: bool,
    replace_reconstructor_objects_with_dict: bool,
    object_factory: Option<ObjectFactory>,
}

impl fmt::Debug for DeOptions {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("DeOptions")
            .field("decode_strings", &self.decode_strings)
            .field(
                "replace_unresolved_globals",
                &self.replace_unresolved_globals,
            )
            .field(
                "replace_recursive_structures",
                &self.replace_recursive_structures,
            )
            .field(
                "replace_reconstructor_objects_with_dict",
                &self.replace_reconstructor_objects_with_dict,
            )
            .field(
                "object_factory",
                &self.object_factory.as_ref().map(|_| "..."),
            )
            .finish()
    }
}

impl DeOptions {
    /// Construct with default options:
    ///
    /// - don't decode strings saved as STRING opcodes (only protocols 0-2) as UTF-8
    /// - don't replace unresolvable globals by `None`
    pub fn new() -> Self {
        Default::default()
    }

    /// Activate decoding strings saved as STRING.
    pub fn decode_strings(mut self) -> Self {
        self.decode_strings = true;
        self
    }

    /// Activate replacing unresolved globals by `None`.
    pub fn replace_unresolved_globals(mut self) -> Self {
        self.replace_unresolved_globals = true;
        self
    }

    /// Activate replacing recursive structures by `None`, instead of erroring out.
    pub fn replace_recursive_structures(mut self) -> Self {
        self.replace_recursive_structures = true;
        self
    }

    /// Activate replacing reconstructor objects with a best-attempt dictionary, instead of erroring out.
    pub fn replace_reconstructor_objects_structures(mut self) -> Self {
        self.replace_reconstructor_objects_with_dict = true;
        self
    }

    /// Set a custom object factory for constructing Python objects during deserialization.
    ///
    /// The factory receives an `ObjectConstructionInfo` with the module and class name,
    /// and should return `Some(object)` for classes it handles, or `None` to fall back
    /// to the default `DictObject` behavior.
    pub fn object_factory(mut self, factory: ObjectFactory) -> Self {
        self.object_factory = Some(factory);
        self
    }
}

/// Decodes pickle streams into values.
pub struct Deserializer<R: Read> {
    rdr: BufReader<R>,
    options: DeOptions,
    pos: usize,
    value: Option<Value>,                     // next value to deserialize
    memo: BTreeMap<MemoId, (Value, i32)>,     // pickle memo (value, number of refs)
    stack: Vec<Value>,                        // topmost items on the stack
    stacks: Vec<Vec<Value>>,                  // items further down the stack, between MARKs
    converted_rc: HashMap<u64, value::Value>, // shared items that have already been converted
    strings_rc: HashMap<Vec<u8>, Value>,
    tuple_rc: BTreeMap<Vec<value::RawHashableValue>, Value>,
}

impl<R: Read> Deserializer<R> {
    /// Construct a new Deserializer.
    pub fn new(rdr: R, options: DeOptions) -> Deserializer<R> {
        Deserializer {
            rdr: BufReader::new(rdr),
            pos: 0,
            value: None,
            memo: BTreeMap::new(),
            stack: Vec::with_capacity(128),
            stacks: Vec::with_capacity(16),
            options,
            converted_rc: Default::default(),
            strings_rc: Default::default(),
            tuple_rc: Default::default(),
        }
    }

    /// Reset internal state, allowing reading multiple pickle dump calls from
    /// a single stream.
    ///
    /// By default `(value_)from_reader` closes the input stream. It is possible
    /// to deserialize multiple pickle objects from a single stream by
    /// implementing a custom reader and resetting the internal state before
    /// reading the next value.
    ///
    /// # Example
    ///
    /// Using `reset_memo` inside a custom deserializer to deserialize multiple
    /// objects from a single stream.
    ///
    /// ```
    /// # use std::io::Read;
    /// # use pickled::{Deserializer, Result, DeOptions};
    /// # use serde::Deserialize;
    /// struct PickleReader<R: Read + Sized>
    /// {
    ///     de: Deserializer<R>,
    /// }
    ///
    /// impl<R: Read + Sized> PickleReader<R>
    /// {
    ///    fn new(reader: R) -> PickleReader<R> {
    ///        PickleReader {
    ///            de: Deserializer::new(reader, DeOptions::new()),
    ///        }
    ///    }
    ///
    ///    pub fn read_object<'de, T: Deserialize<'de>>(&mut self) -> Result<T> {
    ///        self.de.reset_memo();
    ///        let value = Deserialize::deserialize(&mut self.de)?;
    ///        Ok(value)
    ///    }
    /// }
    ///
    /// let input = vec![0x80, 0x04, 0x95, 0x09, 0x00, 0x00, 0x00, 0x00,
    ///                  0x00, 0x00, 0x00, 0x8c, 0x05, 0x48, 0x65, 0x6c,
    ///                  0x6c, 0x6f, 0x94, 0x2e, 0x80, 0x04, 0x95, 0x0a,
    ///                  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x8c,
    ///                  0x06, 0x70, 0x69, 0x63, 0x6b, 0x6c, 0x65, 0x94,
    ///                  0x2e, 0x00];
    /// let mut reader = PickleReader::new(std::io::Cursor::new(input.as_slice()));
    /// let string1: String = reader.read_object().unwrap();
    /// let string2: String = reader.read_object().unwrap();
    /// assert_eq!(&string1, "Hello");
    /// assert_eq!(&string2, "pickle");
    /// ```
    pub fn reset_memo(&mut self) {
        self.memo.clear();
    }

    /// Decode a Value from this pickle.  This is different from going through
    /// the generic serde `deserialize`, since it preserves some types that are
    /// not in the serde data model, such as big integers.
    pub fn deserialize_value(&mut self) -> Result<value::Value> {
        let internal_value = self.parse_value()?;
        self.convert_value(internal_value)
    }

    /// Get the next value to deserialize, either by parsing the pickle stream
    /// or from `self.value`.
    fn get_next_value(&mut self) -> Result<Value> {
        match self.value.take() {
            Some(v) => Ok(v),
            None => self.parse_value(),
        }
    }

    fn tuple_from_items(&mut self, items: Vec<Value>) -> Value {
        let hashable_items = items
            .iter()
            .cloned()
            .map(|de_value| {
                let converted = self.convert_value(de_value)?;
                converted.into_raw_hashable()
            })
            .collect::<Result<Vec<RawHashableValue>>>();

        if let Ok(hashable_items) = hashable_items {
            if let Some(cached) = self.tuple_rc.get(&hashable_items) {
                cached.clone()
            } else {
                let value = Value::Tuple(SharedFrozen::new(items.clone()));
                self.tuple_rc.insert(hashable_items, value.clone());

                value
            }
        } else {
            Value::Tuple(SharedFrozen::new(items))
        }
    }

    fn list_from_items(&mut self, items: Vec<Value>) -> Value {
        Value::List(Shared::new(items))
    }

    fn dict_from_items(&mut self, items: Vec<Value>) -> Value {
        let mut dict = Vec::with_capacity(items.len() / 2);
        Self::extend_dict(&mut dict, items);

        Value::Dict(Shared::new(dict))
    }

    /// Parse a value from the underlying stream.  This will consume the whole
    /// pickle until the STOP opcode.
    fn parse_value(&mut self) -> Result<Value> {
        loop {
            let value = self.read_byte()?;
            let opcode = Opcode::try_from(value).map_err(|code| self.inner_error(code))?;

            match opcode {
                // Specials
                Opcode::Proto => {
                    // Ignore this, as it is only important for instances (read
                    // the version byte).
                    self.read_byte()?;
                }
                Opcode::Frame => {
                    // We'll ignore framing. But we still have to gobble up the length.
                    self.read_fixed_8_bytes()?;
                }
                Opcode::Stop => return self.pop(),
                Opcode::Mark => {
                    let stack = mem::replace(&mut self.stack, Vec::with_capacity(128));
                    self.stacks.push(stack);
                }
                Opcode::Pop => {
                    if self.stack.is_empty() {
                        self.pop_mark()?;
                    } else {
                        self.pop()?;
                    }
                }
                Opcode::PopMark => {
                    self.pop_mark()?;
                }
                Opcode::Dup => {
                    let top = self.top()?.clone();
                    self.stack.push(top);
                }

                // Memo saving ops
                Opcode::Put => {
                    let bytes = self.read_line()?;
                    let memo_id = self.parse_ascii(bytes)?;
                    self.memoize_next(memo_id)?;
                }
                Opcode::BinPut => {
                    let memo_id = self.read_byte()?;
                    self.memoize_next(memo_id.into())?;
                }
                Opcode::LongBinPut => {
                    let bytes = self.read_fixed_4_bytes()?;
                    let memo_id = LittleEndian::read_u32(&bytes);
                    self.memoize_next(memo_id)?;
                }
                Opcode::Memoize => {
                    let memo_id = self.memo.len();
                    self.memoize_next(memo_id as MemoId)?;
                }

                // Memo getting ops
                Opcode::Get => {
                    let bytes = self.read_line()?;
                    let memo_id = self.parse_ascii(bytes)?;
                    self.push_memo_ref(memo_id)?;
                }
                Opcode::BinGet => {
                    let memo_id = self.read_byte()?;
                    self.push_memo_ref(memo_id.into())?;
                }
                Opcode::LongBinGet => {
                    let bytes = self.read_fixed_4_bytes()?;
                    let memo_id = LittleEndian::read_u32(&bytes);
                    self.push_memo_ref(memo_id)?;
                }

                // Singletons
                Opcode::None => self.stack.push(Value::None),
                Opcode::NewFalse => self.stack.push(Value::Bool(false)),
                Opcode::NewTrue => self.stack.push(Value::Bool(true)),

                // ASCII-formatted numbers
                Opcode::Int => {
                    let line = self.read_line()?;
                    let val = self.decode_text_int(line)?;
                    self.stack.push(val);
                }
                Opcode::Long => {
                    let line = self.read_line()?;
                    let long = self.decode_text_long(line)?;
                    self.stack.push(long);
                }
                Opcode::Float => {
                    let line = self.read_line()?;
                    let f = self.parse_ascii(line)?;
                    self.stack.push(Value::F64(f));
                }

                // ASCII-formatted strings
                Opcode::String => {
                    let line = self.read_line()?;
                    let string = if let Some(cached_str) = self.strings_rc.get(&line) {
                        cached_str.clone()
                    } else {
                        let string = self.decode_escaped_string(&line)?;
                        self.strings_rc.insert(line, string.clone());

                        string
                    };
                    self.stack.push(string);
                }
                Opcode::Unicode => {
                    let line = self.read_line()?;
                    let string = if let Some(cached_str) = self.strings_rc.get(&line) {
                        cached_str.clone()
                    } else {
                        let string = self.decode_escaped_unicode(&line)?;
                        self.strings_rc.insert(line, string.clone());

                        string
                    };
                    self.stack.push(string);
                }

                // Binary-coded numbers
                Opcode::BinFloat => {
                    let bytes = self.read_fixed_8_bytes()?;
                    self.stack.push(Value::F64(BigEndian::read_f64(&bytes)));
                }
                Opcode::BinInt => {
                    let bytes = self.read_fixed_4_bytes()?;
                    self.stack
                        .push(Value::I64(LittleEndian::read_i32(&bytes).into()));
                }
                Opcode::BinInt1 => {
                    let byte = self.read_byte()?;
                    self.stack.push(Value::I64(byte.into()));
                }
                Opcode::BinInt2 => {
                    let bytes = self.read_fixed_2_bytes()?;
                    self.stack
                        .push(Value::I64(LittleEndian::read_u16(&bytes).into()));
                }
                Opcode::Long1 => {
                    let bytes = self.read_u8_prefixed_bytes()?;
                    let long = self.decode_binary_long(bytes);
                    self.stack.push(long);
                }
                Opcode::Long4 => {
                    let bytes = self.read_i32_prefixed_bytes()?;
                    let long = self.decode_binary_long(bytes);
                    self.stack.push(long);
                }

                // Length-prefixed (byte)strings
                Opcode::ShortBinBytes => {
                    let string = self.read_u8_prefixed_bytes()?;
                    self.stack.push(Value::Bytes(SharedFrozen::new(string)));
                }
                Opcode::BinBytes => {
                    let string = self.read_u32_prefixed_bytes()?;
                    self.stack.push(Value::Bytes(SharedFrozen::new(string)));
                }
                Opcode::BinBytes8 => {
                    let string = self.read_u64_prefixed_bytes()?;
                    self.stack.push(Value::Bytes(SharedFrozen::new(string)));
                }
                Opcode::ShortBinString => {
                    let string = self.read_u8_prefixed_bytes()?;
                    let decoded = self.decode_string(string)?;
                    self.stack.push(decoded);
                }
                Opcode::BinString => {
                    let string = self.read_i32_prefixed_bytes()?;
                    let decoded = self.decode_string(string)?;
                    self.stack.push(decoded);
                }
                Opcode::ShortBinUnicode => {
                    let string = self.read_u8_prefixed_bytes()?;
                    let decoded = self.decode_unicode(string)?;
                    self.stack.push(decoded);
                }
                Opcode::BinUnicode => {
                    let string = self.read_u32_prefixed_bytes()?;
                    let decoded = self.decode_unicode(string)?;
                    self.stack.push(decoded);
                }
                Opcode::BinUnicode8 => {
                    let string = self.read_u64_prefixed_bytes()?;
                    let decoded = self.decode_unicode(string)?;
                    self.stack.push(decoded);
                }
                Opcode::ByteArray8 => {
                    let string = self.read_u64_prefixed_bytes()?;
                    self.stack.push(Value::Bytes(SharedFrozen::new(string)));
                }

                // Tuples
                Opcode::EmptyTuple => {
                    let tuple = self.tuple_from_items(Vec::new());
                    self.stack.push(tuple)
                }
                Opcode::Tuple1 => {
                    let item = self.pop()?;
                    let tuple = self.tuple_from_items(vec![item]);
                    self.stack.push(tuple);
                }
                Opcode::Tuple2 => {
                    let item2 = self.pop()?;
                    let item1 = self.pop()?;
                    let tuple = self.tuple_from_items(vec![item1, item2]);
                    self.stack.push(tuple);
                }
                Opcode::Tuple3 => {
                    let item3 = self.pop()?;
                    let item2 = self.pop()?;
                    let item1 = self.pop()?;
                    let tuple = self.tuple_from_items(vec![item1, item2, item3]);
                    self.stack.push(tuple);
                }
                Opcode::Tuple => {
                    let items = self.pop_mark()?;
                    let tuple = self.tuple_from_items(items);
                    self.stack.push(tuple);
                }

                // Lists
                Opcode::EmptyList => self.stack.push(Value::List(Shared::new(Vec::new()))),
                Opcode::List => {
                    let items = self.pop_mark()?;
                    let list = self.list_from_items(items);
                    self.stack.push(list);
                }
                Opcode::Append => {
                    let value = self.pop()?;
                    self.modify_list(|list| list.push(value))?;
                }
                Opcode::Appends => {
                    let items = self.pop_mark()?;
                    self.modify_list(|list| list.extend(items))?;
                }

                // Dicts
                Opcode::EmptyDict => self.stack.push(Value::Dict(Shared::new(Vec::new()))),
                Opcode::Dict => {
                    let items = self.pop_mark()?;

                    let dict = self.dict_from_items(items);

                    self.stack.push(dict);
                }
                Opcode::SetItem => {
                    let value = self.pop()?;
                    let key = self.pop()?;
                    self.modify_dict(|dict| dict.push((key, value)))?;
                }
                Opcode::SetItems => {
                    let items = self.pop_mark()?;
                    self.modify_dict(|dict| Self::extend_dict(dict, items))?;
                }

                // Sets and frozensets
                Opcode::EmptySet => self.stack.push(Value::Set(Shared::new(Vec::new()))),
                Opcode::FrozenSet => {
                    let items = self.pop_mark()?;
                    self.stack.push(Value::FrozenSet(SharedFrozen::new(items)));
                }
                Opcode::AddItems => {
                    let items = self.pop_mark()?;
                    self.modify_set(|set| set.extend(items))?;
                }

                // Arbitrary module globals, used here for unpickling set and frozenset
                // from protocols < 4
                Opcode::Global => {
                    let modname = self.read_line()?;
                    let globname = self.read_line()?;
                    let value = self.decode_global(modname, globname)?;
                    self.stack.push(value);
                }
                Opcode::StackGlobal => {
                    let globname = match self.pop_resolve()? {
                        Value::String(string) => string.into_raw_or_cloned().into_bytes(),
                        other => return Self::stack_error("string", &other, self.pos),
                    };
                    let modname = match self.pop_resolve()? {
                        Value::String(string) => string.into_raw_or_cloned().into_bytes(),
                        other => return Self::stack_error("string", &other, self.pos),
                    };
                    let value = self.decode_global(modname, globname)?;
                    self.stack.push(value);
                }
                Opcode::Reduce => {
                    let argtuple = match self.pop_resolve()? {
                        Value::Tuple(args) => args,
                        other => return Self::stack_error("tuple", &other, self.pos),
                    };
                    let global = self.pop_resolve()?;
                    self.reduce_global(global, argtuple)?;
                }

                // Arbitrary classes - make a best effort attempt to recover some data
                Opcode::Inst => {
                    let modname = self.read_line()?;
                    let globname = self.read_line()?;
                    let _args = self.pop_mark()?;
                    let modname = String::from_utf8(modname)
                        .map_err(|_| self.inner_error(ErrorCode::StringNotUTF8))?;
                    let globname = String::from_utf8(globname)
                        .map_err(|_| self.inner_error(ErrorCode::StringNotUTF8))?;
                    let obj = self.make_object(&modname, &globname);
                    self.stack.push(obj);
                }
                Opcode::Obj => {
                    let mut args = self.pop_mark()?;
                    let cls = if args.is_empty() {
                        self.pop()?
                    } else {
                        args.remove(0)
                    };
                    let cls = self.resolve(Some(cls));
                    let (modname, globname) = match &cls {
                        Some(Value::Global(Global::Other { modname, globname })) => {
                            (modname.as_ref(), globname.as_ref())
                        }
                        _ => {
                            return Self::stack_error(
                                "global reference",
                                cls.as_ref().unwrap_or(&Value::None),
                                self.pos,
                            );
                        }
                    };
                    let obj = self.make_object(modname, globname);
                    self.stack.push(obj);
                }
                Opcode::NewObj => {
                    let _args = self.pop()?;
                    let cls = self.pop_resolve()?;
                    let (modname, globname) = match &cls {
                        Value::Global(Global::Other { modname, globname }) => {
                            (modname.as_ref(), globname.as_ref())
                        }
                        _ => return Self::stack_error("global reference", &cls, self.pos),
                    };
                    let obj = self.make_object(modname, globname);
                    self.stack.push(obj);
                }
                Opcode::NewObjEx => {
                    let _kwargs = self.pop()?;
                    let _args = self.pop()?;
                    let cls = self.pop_resolve()?;
                    let (modname, globname) = match &cls {
                        Value::Global(Global::Other { modname, globname }) => {
                            (modname.as_ref(), globname.as_ref())
                        }
                        _ => return Self::stack_error("global reference", &cls, self.pos),
                    };
                    let obj = self.make_object(modname, globname);
                    self.stack.push(obj);
                }
                Opcode::Build => {
                    let state = self.pop()?;
                    let obj = self.pop()?;

                    let _standin = self.resolve(Some(obj.clone()));

                    // Resolve state if it's a MemoRef
                    let resolved_state = self.resolve(Some(state.clone())).unwrap_or(state.clone());

                    match obj {
                        Value::MemoRef(id) => {
                            // Check if the memo'd value is an Object
                            let is_object =
                                matches!(self.memo.get(&id), Some((Value::Object(_), _)));
                            if is_object {
                                // Convert state before mutably borrowing memo
                                let public_state = self.de_value_to_public_value(resolved_state);
                                if let Some((Value::Object(o), _)) = self.memo.get_mut(&id) {
                                    o.__setstate__(public_state);
                                }
                                let updated = self.memo.get(&id).unwrap().0.clone();
                                self.stack.push(updated);
                            } else {
                                self.memoize(id, state.clone())?;
                                self.stack.push(state);
                            }
                        }
                        Value::Object(mut o) => {
                            o.__setstate__(self.de_value_to_public_value(resolved_state));
                            self.stack.push(Value::Object(o));
                        }
                        _ => {
                            // Legacy behavior: replace standin with state
                            self.stack.push(state);
                        }
                    }
                }
            }
        }
    }

    // Pop the stack top item.
    fn pop(&mut self) -> Result<Value> {
        match self.stack.pop() {
            Some(v) => Ok(v),
            None => self.error(ErrorCode::StackUnderflow),
        }
    }

    // Pop the stack top item, and resolve it if it is a memo reference.
    fn pop_resolve(&mut self) -> Result<Value> {
        let top = self.stack.pop();
        match self.resolve(top) {
            Some(v) => Ok(v),
            None => self.error(ErrorCode::StackUnderflow),
        }
    }

    // Pop all topmost stack items until the next MARK.
    fn pop_mark(&mut self) -> Result<Vec<Value>> {
        match self.stacks.pop() {
            Some(new) => Ok(mem::replace(&mut self.stack, new)),
            None => self.error(ErrorCode::StackUnderflow),
        }
    }

    // Mutably view the stack top item.
    fn top(&mut self) -> Result<&mut Value> {
        match self.stack.last_mut() {
            // Since some operations like APPEND do things to the stack top, we
            // need to provide the reference to the "real" object here, not the
            // MemoRef variant.
            Some(&mut Value::MemoRef(n)) => self
                .memo
                .get_mut(&n)
                .map(|&mut (ref mut v, _)| v)
                .ok_or(Error::Syntax(ErrorCode::MissingMemo(n))),
            Some(other_value) => Ok(other_value),
            None => Err(Error::Eval(ErrorCode::StackUnderflow, self.pos)),
        }
    }

    // Pushes a memo reference on the stack, and increases the usage counter.
    fn push_memo_ref(&mut self, memo_id: MemoId) -> Result<()> {
        self.stack.push(Value::MemoRef(memo_id));
        match self.memo.get_mut(&memo_id) {
            Some(&mut (_, ref mut count)) => {
                if MEMO_REF_COUNTING {
                    *count += 1;
                }
                Ok(())
            }
            None => Err(Error::Eval(ErrorCode::MissingMemo(memo_id), self.pos)),
        }
    }

    // Memoize the current stack top with the given ID.  Moves the actual
    // object into the memo, and saves a reference on the stack instead.
    fn memoize_next(&mut self, memo_id: MemoId) -> Result<()> {
        let item = self.pop()?;
        self.memoize(memo_id, item)?;
        self.stack.push(Value::MemoRef(memo_id));
        Ok(())
    }

    fn memoize(&mut self, memo_id: MemoId, mut item: Value) -> Result<()> {
        if let Value::MemoRef(id) = item {
            // TODO: is this even possible?
            item = match self.memo.get(&id) {
                Some((v, _)) => v.clone(),
                None => return Err(Error::Eval(ErrorCode::MissingMemo(id), self.pos)),
            };
        }
        self.memo.insert(memo_id, (item, 1));
        Ok(())
    }

    // Resolve memo reference during stream decoding.
    fn resolve(&mut self, maybe_memo: Option<Value>) -> Option<Value> {
        match maybe_memo {
            Some(Value::MemoRef(id)) => {
                self.memo.get_mut(&id).map(|&mut (ref val, ref mut count)| {
                    if MEMO_REF_COUNTING {
                        // We can't remove it from the memo here, since we haven't
                        // decoded the whole stream yet and there may be further
                        // references to the value.
                        *count -= 1;
                    }
                    val.clone()
                })
            }
            other => other,
        }
    }

    // Resolve memo reference during Value deserializing.
    fn resolve_recursive<T, U, F>(&mut self, id: MemoId, u: U, f: F) -> Result<T>
    where
        F: FnOnce(&mut Self, U, Value) -> Result<T>,
    {
        // Take the value from the memo while visiting it.  This prevents us
        // from trying to depickle recursive structures, which we can't do
        // because our Values aren't references.
        let (value, mut count) = match self.memo.remove(&id) {
            Some(entry) => entry,
            None => {
                return if self.options.replace_recursive_structures {
                    f(self, u, Value::None)
                } else {
                    Err(Error::Syntax(ErrorCode::Recursive))
                };
            }
        };
        if MEMO_REF_COUNTING {
            count -= 1;
        }
        if count <= 0 && MEMO_REF_COUNTING {
            f(self, u, value)
            // No need to put it back.
        } else {
            let result = f(self, u, value.clone());
            assert!(self.memo.insert(id, (value, count)).is_none());
            result
        }
    }

    /// Assert that we reached the end of the stream.
    pub fn end(&mut self) -> Result<()> {
        let mut buf = [0];
        match self.rdr.read(&mut buf) {
            Err(err) => Err(Error::Io(err)),
            Ok(1) => self.error(ErrorCode::TrailingBytes),
            _ => Ok(()),
        }
    }

    fn read_line(&mut self) -> Result<Vec<u8>> {
        let mut buf = Vec::with_capacity(16);
        match self.rdr.read_until(b'\n', &mut buf) {
            Ok(_) => {
                self.pos += buf.len();
                buf.pop(); // remove newline
                if buf.last() == Some(&b'\r') {
                    buf.pop();
                }
                Ok(buf)
            }
            Err(err) => Err(Error::Io(err)),
        }
    }

    #[inline]
    fn read_byte(&mut self) -> Result<u8> {
        let mut buf = [0];
        match self.rdr.read(&mut buf) {
            Ok(1) => {
                self.pos += 1;
                Ok(buf[0])
            }
            Ok(_) => self.error(ErrorCode::EOFWhileParsing),
            Err(err) => Err(Error::Io(err)),
        }
    }

    #[inline]
    fn read_bytes(&mut self, n: usize) -> Result<Vec<u8>> {
        let mut buf = Vec::new();
        match self.rdr.by_ref().take(n as u64).read_to_end(&mut buf) {
            Ok(m) if n == m => {
                self.pos += n;
                Ok(buf)
            }
            Ok(_) => self.error(ErrorCode::EOFWhileParsing),
            Err(err) => Err(Error::Io(err)),
        }
    }

    #[inline]
    fn read_fixed_2_bytes(&mut self) -> Result<[u8; 2]> {
        let mut buf = [0; 2];
        match self.rdr.by_ref().take(2).read_exact(&mut buf) {
            Ok(()) => {
                self.pos += 2;
                Ok(buf)
            }
            Err(err) => {
                if err.kind() == std::io::ErrorKind::UnexpectedEof {
                    self.error(ErrorCode::EOFWhileParsing)
                } else {
                    Err(Error::Io(err))
                }
            }
        }
    }

    #[inline]
    fn read_fixed_4_bytes(&mut self) -> Result<[u8; 4]> {
        let mut buf = [0; 4];
        match self.rdr.by_ref().take(4).read_exact(&mut buf) {
            Ok(()) => {
                self.pos += 4;
                Ok(buf)
            }
            Err(err) => {
                if err.kind() == std::io::ErrorKind::UnexpectedEof {
                    self.error(ErrorCode::EOFWhileParsing)
                } else {
                    Err(Error::Io(err))
                }
            }
        }
    }

    #[inline]
    fn read_fixed_8_bytes(&mut self) -> Result<[u8; 8]> {
        let mut buf = [0; 8];
        match self.rdr.by_ref().take(8).read_exact(&mut buf) {
            Ok(()) => {
                self.pos += 8;
                Ok(buf)
            }
            Err(err) => {
                if err.kind() == std::io::ErrorKind::UnexpectedEof {
                    self.error(ErrorCode::EOFWhileParsing)
                } else {
                    Err(Error::Io(err))
                }
            }
        }
    }

    fn read_i32_prefixed_bytes(&mut self) -> Result<Vec<u8>> {
        let lenbytes = self.read_fixed_4_bytes()?;
        match LittleEndian::read_i32(&lenbytes) {
            0 => Ok(vec![]),
            l if l < 0 => self.error(ErrorCode::NegativeLength),
            l => self.read_bytes(l as usize),
        }
    }

    fn read_u64_prefixed_bytes(&mut self) -> Result<Vec<u8>> {
        let lenbytes = self.read_fixed_8_bytes()?;
        self.read_bytes(LittleEndian::read_u64(&lenbytes) as usize)
    }

    fn read_u32_prefixed_bytes(&mut self) -> Result<Vec<u8>> {
        let lenbytes = self.read_fixed_4_bytes()?;
        self.read_bytes(LittleEndian::read_u32(&lenbytes) as usize)
    }

    fn read_u8_prefixed_bytes(&mut self) -> Result<Vec<u8>> {
        let lenbyte = self.read_byte()?;
        self.read_bytes(lenbyte as usize)
    }

    // Parse an expected ASCII literal from the stream or raise an error.
    fn parse_ascii<T: FromStr>(&self, bytes: Vec<u8>) -> Result<T> {
        match str::from_utf8(&bytes).unwrap_or("").parse() {
            Ok(v) => Ok(v),
            Err(_) => self.error(ErrorCode::InvalidLiteral(bytes)),
        }
    }

    // Decode a text-encoded integer.
    fn decode_text_int(&self, line: Vec<u8>) -> Result<Value> {
        // Handle protocol 1 way of spelling true/false
        Ok(if line == b"00" {
            Value::Bool(false)
        } else if line == b"01" {
            Value::Bool(true)
        } else {
            let i = self.parse_ascii(line)?;
            Value::I64(i)
        })
    }

    // Decode a text-encoded long integer.
    fn decode_text_long(&self, mut line: Vec<u8>) -> Result<Value> {
        // Remove "L" suffix.
        if line.last() == Some(&b'L') {
            line.pop();
        }
        match BigInt::parse_bytes(&line, 10) {
            Some(i) => Ok(Value::Int(i)),
            None => self.error(ErrorCode::InvalidLiteral(line)),
        }
    }

    // Decode an escaped string.  These are encoded with "normal" Python string
    // escape rules.
    fn decode_escaped_string(&self, slice: &[u8]) -> Result<Value> {
        // Remove quotes if they appear.
        let slice = if (slice.len() >= 2)
            && (slice[0] == slice[slice.len() - 1])
            && (slice[0] == b'"' || slice[0] == b'\'')
        {
            &slice[1..slice.len() - 1]
        } else {
            slice
        };
        let mut result = Vec::with_capacity(slice.len());
        let mut iter = slice.iter();
        while let Some(&b) = iter.next() {
            match b {
                b'\\' => match iter.next() {
                    Some(&b'\\') => result.push(b'\\'),
                    Some(&b'a') => result.push(b'\x07'),
                    Some(&b'b') => result.push(b'\x08'),
                    Some(&b't') => result.push(b'\x09'),
                    Some(&b'n') => result.push(b'\x0a'),
                    Some(&b'v') => result.push(b'\x0b'),
                    Some(&b'f') => result.push(b'\x0c'),
                    Some(&b'r') => result.push(b'\x0d'),
                    Some(&b'x') => {
                        match iter
                            .next()
                            .and_then(|&ch1| (ch1 as char).to_digit(16))
                            .and_then(|v1| {
                                iter.next()
                                    .and_then(|&ch2| (ch2 as char).to_digit(16))
                                    .map(|v2| 16 * (v1 as u8) + (v2 as u8))
                            }) {
                            Some(v) => result.push(v),
                            None => return self.error(ErrorCode::InvalidLiteral(slice.into())),
                        }
                    }
                    _ => return self.error(ErrorCode::InvalidLiteral(slice.into())),
                },
                _ => result.push(b),
            }
        }
        self.decode_string(result)
    }

    // Decode escaped Unicode strings. These are encoded with "raw-unicode-escape",
    // which only knows the \uXXXX and \UYYYYYYYY escapes. The backslash is escaped
    // in this way, too.
    fn decode_escaped_unicode(&self, s: &[u8]) -> Result<Value> {
        let mut result = String::with_capacity(s.len());
        let mut iter = s.iter();
        while let Some(&b) = iter.next() {
            match b {
                b'\\' => {
                    let nescape = match iter.next() {
                        Some(&b'u') => 4,
                        Some(&b'U') => 8,
                        _ => return self.error(ErrorCode::InvalidLiteral(s.into())),
                    };
                    let mut accum = 0;
                    for _i in 0..nescape {
                        accum *= 16;
                        match iter.next().and_then(|&ch| (ch as char).to_digit(16)) {
                            Some(v) => accum += v,
                            None => return self.error(ErrorCode::InvalidLiteral(s.into())),
                        }
                    }
                    match char::from_u32(accum) {
                        Some(v) => result.push(v),
                        None => return self.error(ErrorCode::InvalidLiteral(s.into())),
                    }
                }
                _ => result.push(b as char),
            }
        }
        Ok(Value::String(SharedFrozen::new(result)))
    }

    // Decode a string - either as Unicode or as bytes.
    fn decode_string(&self, string: Vec<u8>) -> Result<Value> {
        if self.options.decode_strings {
            self.decode_unicode(string)
        } else {
            Ok(Value::Bytes(SharedFrozen::new(string)))
        }
    }

    // Decode a Unicode string from UTF-8.
    fn decode_unicode(&self, string: Vec<u8>) -> Result<Value> {
        match String::from_utf8(string) {
            Ok(v) => Ok(Value::String(SharedFrozen::new(v))),
            Err(_) => self.error(ErrorCode::StringNotUTF8),
        }
    }

    // Decode a binary-encoded long integer.
    fn decode_binary_long(&self, bytes: Vec<u8>) -> Value {
        // BigInt::from_bytes_le doesn't like a sign bit in the bytes, therefore
        // we have to extract that ourselves and do the two-s complement.
        let negative = !bytes.is_empty() && (bytes[bytes.len() - 1] & 0x80 != 0);
        let mut val = BigInt::from_bytes_le(Sign::Plus, &bytes);
        if negative {
            val -= BigInt::from(1) << (bytes.len() * 8);
        }
        Value::Int(val)
    }

    /// Create an object using the factory callback, or fall back to DictObject.
    fn make_object(&self, modname: &str, globname: &str) -> Value {
        let info = crate::object::ObjectConstructionInfo {
            module: modname,
            class: globname,
        };
        // Try user factory first
        if let Some(ref factory) = self.options.object_factory
            && let Some(obj) = factory(info)
        {
            return Value::Object(obj);
        }
        // Fall back to DictObject
        Value::Object(Box::new(DictObject::new(
            modname.to_owned(),
            globname.to_owned(),
        )))
    }

    /// Convert internal de::Value to public value::Value for passing to PickleObject methods.
    /// Resolves MemoRefs using the deserializer's memo table.
    fn de_value_to_public_value(&mut self, v: Value) -> value::Value {
        // Resolve MemoRef first
        let v = match v {
            Value::MemoRef(id) => match self.memo.get(&id) {
                Some((val, _)) => val.clone(),
                None => return value::Value::None,
            },
            other => other,
        };
        match v {
            Value::None => value::Value::None,
            Value::Bool(b) => value::Value::Bool(b),
            Value::I64(i) => value::Value::I64(i),
            Value::Int(i) => {
                if let Some(i) = i.to_i64() {
                    value::Value::I64(i)
                } else {
                    value::Value::Int(i)
                }
            }
            Value::F64(f) => value::Value::F64(f),
            Value::Bytes(b) => value::Value::Bytes(b),
            Value::String(s) => value::Value::String(s),
            Value::Tuple(t) => {
                let id = t.stable_id();
                if let Some(v) = self.converted_rc.get(&id) {
                    return v.clone();
                }
                let converted = t
                    .inner()
                    .iter()
                    .cloned()
                    .map(|v| self.de_value_to_public_value(v))
                    .collect();
                let val = value::Value::Tuple(SharedFrozen::new(converted));
                self.converted_rc.insert(id, val.clone());
                val
            }
            Value::List(l) => {
                let id = l.stable_id();
                if let Some(v) = self.converted_rc.get(&id) {
                    return v.clone();
                }
                let converted = l
                    .inner()
                    .iter()
                    .cloned()
                    .map(|v| self.de_value_to_public_value(v))
                    .collect();
                let val = value::Value::List(Shared::new(converted));
                self.converted_rc.insert(id, val.clone());
                val
            }
            Value::Dict(d) => {
                let id = d.stable_id();
                if let Some(v) = self.converted_rc.get(&id) {
                    return v.clone();
                }
                let mut map = BTreeMap::new();
                for (k, v) in d.inner().iter() {
                    if let Ok(hk) = self.de_value_to_public_value(k.clone()).into_hashable() {
                        map.insert(hk, self.de_value_to_public_value(v.clone()));
                    }
                }
                let val = value::Value::Dict(Shared::new(map));
                self.converted_rc.insert(id, val.clone());
                val
            }
            Value::Set(s) => {
                let id = s.stable_id();
                if let Some(v) = self.converted_rc.get(&id) {
                    return v.clone();
                }
                let converted = s
                    .inner()
                    .iter()
                    .cloned()
                    .filter_map(|v| self.de_value_to_public_value(v).into_hashable().ok())
                    .collect();
                let val = value::Value::Set(Shared::new(converted));
                self.converted_rc.insert(id, val.clone());
                val
            }
            Value::FrozenSet(s) => {
                let id = s.stable_id();
                if let Some(v) = self.converted_rc.get(&id) {
                    return v.clone();
                }
                let converted = s
                    .inner()
                    .iter()
                    .cloned()
                    .filter_map(|v| self.de_value_to_public_value(v).into_hashable().ok())
                    .collect();
                let val = value::Value::FrozenSet(SharedFrozen::new(converted));
                self.converted_rc.insert(id, val.clone());
                val
            }
            Value::Object(o) => value::Value::Object(o),
            Value::MemoRef(_) => unreachable!("already resolved above"),
            Value::Global(_) => value::Value::None,
        }
    }

    // Modify the stack-top list.
    fn modify_list<F>(&mut self, f: F) -> Result<()>
    where
        F: FnOnce(&mut Vec<Value>),
    {
        let pos = self.pos;
        let top = self.top()?;

        match *top {
            Value::List(ref list) => {
                let mut list = list.inner_mut();
                f(&mut list);
                return Ok(());
            }
            _ => {
                // Fallthrough to error
            }
        }

        Self::stack_error("list", top, pos)
    }

    // Push items from a (key, value, key, value) flattened list onto a (key, value) vec.
    fn extend_dict(dict: &mut Vec<(Value, Value)>, items: Vec<Value>) {
        let mut key = None;
        for value in items {
            match key.take() {
                None => key = Some(value),
                Some(key) => dict.push((key, value)),
            }
        }
    }

    // Modify the stack-top dict, or call __setitem__ on an Object.
    fn modify_dict<F>(&mut self, f: F) -> Result<()>
    where
        F: FnOnce(&mut Vec<(Value, Value)>),
    {
        let pos = self.pos;
        let top = self.top()?;
        match *top {
            Value::Dict(ref dict) => {
                let mut dict = dict.inner_mut();
                f(&mut dict);
                return Ok(());
            }
            Value::Object(_) => {
                // Collect items via the closure, then convert and dispatch to __setitem__
                let mut items = Vec::new();
                f(&mut items);
                let converted: Vec<_> = items
                    .into_iter()
                    .map(|(k, v)| {
                        (
                            self.de_value_to_public_value(k),
                            self.de_value_to_public_value(v),
                        )
                    })
                    .collect();
                // Re-borrow top to get the Object
                let top = self.top()?;
                if let Value::Object(ref mut obj) = *top {
                    for (key, value) in converted {
                        obj.__setitem__(key, value);
                    }
                }
                return Ok(());
            }
            _ => {
                // Fallthrough to error
            }
        }

        Self::stack_error("dict", top, pos)
    }

    // Modify the stack-top set.
    fn modify_set<F>(&mut self, f: F) -> Result<()>
    where
        F: FnOnce(&mut Vec<Value>),
    {
        let pos = self.pos;
        let top = self.top()?;
        if let Value::Set(ref set) = *top {
            let mut set = set.inner_mut();
            f(&mut set);
            Ok(())
        } else {
            Self::stack_error("set", top, pos)
        }
    }

    // Push the Value::Global referenced by modname and globname.
    fn decode_global(&mut self, modname: Vec<u8>, globname: Vec<u8>) -> Result<Value> {
        let value = match (&*modname, &*globname) {
            (b"_codecs", b"encode") => Value::Global(Global::Encode),
            (b"__builtin__", b"set") | (b"builtins", b"set") => Value::Global(Global::Set),
            (b"__builtin__", b"frozenset") | (b"builtins", b"frozenset") => {
                Value::Global(Global::Frozenset)
            }
            (b"__builtin__", b"list") | (b"builtins", b"list") => Value::Global(Global::List),
            (b"__builtin__", b"bytearray") | (b"builtins", b"bytearray") => {
                Value::Global(Global::Bytearray)
            }
            (b"__builtin__", b"int") | (b"builtins", b"int") => Value::Global(Global::Int),
            (b"copy_reg", b"_reconstructor") => Value::Global(Global::Reconstructor),
            _ => {
                let modname = String::from_utf8(modname)
                    .map_err(|_| self.inner_error(ErrorCode::StringNotUTF8))?;
                let globname = String::from_utf8(globname)
                    .map_err(|_| self.inner_error(ErrorCode::StringNotUTF8))?;

                Value::Global(Global::Other {
                    modname: Cow::Owned(modname),
                    globname: Cow::Owned(globname),
                })
            }
        };
        Ok(value)
    }

    // Handle the REDUCE opcode for the few Global objects we support.
    fn reduce_global(&mut self, global: Value, argtuple: SharedFrozen<Vec<Value>>) -> Result<()> {
        let mut argtuple = argtuple.into_raw_or_cloned();
        match global {
            Value::Global(Global::Set) => match self.resolve(argtuple.pop()) {
                Some(Value::List(items)) => {
                    self.stack.push(Value::Set(items));
                    Ok(())
                }
                _ => self.error(ErrorCode::InvalidValue("set() arg".into())),
            },
            Value::Global(Global::Frozenset) => match self.resolve(argtuple.pop()) {
                Some(Value::List(items)) => {
                    self.stack.push(Value::FrozenSet(items.into()));
                    Ok(())
                }
                _ => self.error(ErrorCode::InvalidValue("frozenset() arg".into())),
            },
            Value::Global(Global::Bytearray) => {
                // On Py2, the call is encoded as bytearray(u"foo", "latin-1").
                argtuple.truncate(1);
                match self.resolve(argtuple.pop()) {
                    Some(Value::Bytes(bytes)) => {
                        self.stack.push(Value::Bytes(bytes));
                        Ok(())
                    }
                    Some(Value::String(string)) => {
                        // The code points in the string are actually bytes values.
                        // So we need to collect them individually.
                        self.stack.push(Value::Bytes(SharedFrozen::new(
                            string.inner().chars().map(|ch| ch as u32 as u8).collect(),
                        )));
                        Ok(())
                    }
                    _ => self.error(ErrorCode::InvalidValue("bytearray() arg".into())),
                }
            }
            Value::Global(Global::List) => match self.resolve(argtuple.pop()) {
                Some(Value::List(items)) => {
                    self.stack.push(Value::List(items));
                    Ok(())
                }
                _ => self.error(ErrorCode::InvalidValue("list() arg".into())),
            },
            Value::Global(Global::Int) => match self.resolve(argtuple.pop()) {
                Some(Value::Int(integer)) => {
                    self.stack.push(Value::Int(integer));
                    Ok(())
                }
                _ => self.error(ErrorCode::InvalidValue("int() arg".into())),
            },
            Value::Global(Global::Encode) => {
                // Byte object encoded as _codecs.encode(x, 'latin1')
                match self.resolve(argtuple.pop()) {
                    // Encoding, always latin1
                    Some(Value::String(_)) => {}
                    _ => return self.error(ErrorCode::InvalidValue("encode() arg".into())),
                }
                match self.resolve(argtuple.pop()) {
                    Some(Value::String(s)) => {
                        // Now we have to convert the string to latin-1
                        // encoded bytes.  It never contains codepoints
                        // above 0xff.
                        let bytes = s.inner().chars().map(|ch| ch as u8).collect();
                        self.stack.push(Value::Bytes(SharedFrozen::new(bytes)));
                        Ok(())
                    }
                    _ => self.error(ErrorCode::InvalidValue("encode() arg".into())),
                }
            }
            Value::Global(Global::Reconstructor) => {
                let _state = self.resolve(argtuple.pop());
                let _base_cls = self.resolve(argtuple.pop());
                let cls = self.resolve(argtuple.pop());

                if self.options.object_factory.is_some()
                    || self.options.replace_reconstructor_objects_with_dict
                {
                    let (modname, globname) = match &cls {
                        Some(Value::Global(Global::Other { modname, globname })) => {
                            (modname.as_ref(), globname.as_ref())
                        }
                        _ => {
                            return Self::stack_error(
                                "global reference",
                                cls.as_ref().unwrap_or(&Value::None),
                                self.pos,
                            );
                        }
                    };
                    let obj = self.make_object(modname, globname);
                    self.stack.push(obj);
                } else {
                    // If the user doesn't want to replace reconstructor objects, transition this to an unresolved global
                    // so that we can bubble up unresolved global errors.
                    self.stack.push(Value::Global(Global::Other {
                        modname: Cow::Borrowed("copy_reg"),
                        globname: Cow::Borrowed("_reconstructor"),
                    }));
                }
                Ok(())
            }
            Value::Global(Global::Other { modname, globname }) => {
                // Anything else; just keep it on the stack as an opaque object.
                // If it is a class object, it will get replaced later when the
                // class is instantiated.
                self.stack
                    .push(Value::Global(Global::Other { modname, globname }));
                Ok(())
            }
            other => Self::stack_error("global reference", &other, self.pos),
        }
    }

    fn stack_error<T>(what: &'static str, value: &Value, pos: usize) -> Result<T> {
        let it = format!("{value:?}");
        Err(Error::Eval(ErrorCode::InvalidStackTop(what, it), pos))
    }

    fn error<T>(&self, reason: ErrorCode) -> Result<T> {
        Err(self.inner_error(reason))
    }

    fn inner_error(&self, reason: ErrorCode) -> Error {
        Error::Eval(reason, self.pos)
    }

    fn convert_value(&mut self, value: Value) -> Result<value::Value> {
        match value {
            Value::None => Ok(value::Value::None),
            Value::Bool(v) => Ok(value::Value::Bool(v)),
            Value::I64(v) => Ok(value::Value::I64(v)),
            Value::Int(v) => {
                if let Some(i) = v.to_i64() {
                    Ok(value::Value::I64(i))
                } else {
                    Ok(value::Value::Int(v))
                }
            }
            Value::F64(v) => Ok(value::Value::F64(v)),
            Value::Bytes(v) => Ok(value::Value::Bytes(v)),
            Value::String(v) => Ok(value::Value::String(v)),
            Value::List(v) => {
                let id = v.stable_id();

                if let Some(converted) = self.converted_rc.get(&id) {
                    return Ok(converted.clone());
                }

                let new = v
                    .inner()
                    .iter()
                    .map(|v| self.convert_value(v.clone()))
                    .collect::<Result<_>>();

                let new_shared = Shared::new(new?);

                let new_value = value::Value::List(new_shared.clone());
                self.converted_rc.insert(id, new_value.clone());

                Ok(new_value)
            }
            Value::Tuple(v) => {
                let id = v.stable_id();

                if let Some(converted) = self.converted_rc.get(&id) {
                    return Ok(converted.clone());
                }

                let new = v
                    .inner()
                    .iter()
                    .map(|v| self.convert_value(v.clone()))
                    .collect::<Result<Vec<_>>>()?;

                let new_shared = SharedFrozen::new(new);

                let new_value = value::Value::Tuple(new_shared.clone());
                self.converted_rc.insert(id, new_value.clone());

                Ok(new_value)
            }
            Value::Set(v) => {
                let new = v
                    .inner()
                    .iter()
                    .cloned()
                    .map(|v| self.convert_value(v).and_then(|rv| rv.into_hashable()))
                    .collect::<Result<_>>();
                Ok(value::Value::Set(Shared::new(new?)))
            }
            Value::FrozenSet(v) => {
                let new = v
                    .inner()
                    .iter()
                    .cloned()
                    .map(|v| self.convert_value(v).and_then(|rv| rv.into_hashable()))
                    .collect::<Result<_>>();

                Ok(value::Value::FrozenSet(SharedFrozen::new(new?)))
            }
            Value::Dict(v) => {
                let id = v.stable_id();

                if let Some(converted) = self.converted_rc.get(&id) {
                    return Ok(converted.clone());
                }

                let mut map = BTreeMap::new();
                let v = v.inner();
                for (key, value) in v.iter() {
                    let real_key = self
                        .convert_value(key.clone())
                        .and_then(|rv| rv.into_hashable())?;

                    let real_value = self.convert_value(value.clone())?;
                    map.insert(real_key, real_value);
                }

                let new_shared = Shared::new(map);

                let new_value = value::Value::Dict(new_shared.clone());
                self.converted_rc.insert(id, new_value.clone());

                Ok(new_value)
            }
            Value::Object(o) => Ok(value::Value::Object(o)),
            Value::MemoRef(memo_id) => {
                self.resolve_recursive(memo_id, (), |slf, (), value| slf.convert_value(value))
            }
            Value::Global(Global::Reconstructor) => {
                if self.options.object_factory.is_some()
                    || self.options.replace_reconstructor_objects_with_dict
                {
                    let obj = self.make_object("copy_reg", "_reconstructor");
                    Ok(value::Value::Object(match obj {
                        Value::Object(o) => o,
                        _ => unreachable!(),
                    }))
                } else {
                    Err(Error::Syntax(ErrorCode::UnresolvedGlobal))
                }
            }
            Value::Global(_) => {
                if self.options.replace_unresolved_globals {
                    Ok(value::Value::None)
                } else {
                    Err(Error::Syntax(ErrorCode::UnresolvedGlobal))
                }
            }
        }
    }
}

impl<'de: 'a, 'a, R: Read> de::Deserializer<'de> for &'a mut Deserializer<R> {
    type Error = Error;

    fn deserialize_any<V: Visitor<'de>>(self, visitor: V) -> Result<V::Value> {
        let value = self.get_next_value()?;
        match value {
            Value::None => visitor.visit_unit(),
            Value::Bool(v) => visitor.visit_bool(v),
            Value::I64(v) => visitor.visit_i64(v),
            Value::Int(v) => {
                if let Some(i) = v.to_i64() {
                    visitor.visit_i64(i)
                } else {
                    Err(Error::Syntax(ErrorCode::InvalidValue(
                        "integer too large".into(),
                    )))
                }
            }
            Value::F64(v) => visitor.visit_f64(v),
            Value::Bytes(v) => {
                let v = v.into_raw_or_cloned();
                visitor.visit_byte_buf(v)
            }
            Value::String(v) => {
                let v = v.into_raw_or_cloned();
                visitor.visit_string(v)
            }
            Value::List(v) => {
                let v = v.into_raw_or_cloned();
                let len = v.len();
                visitor.visit_seq(SeqAccess {
                    de: self,
                    iter: v.into_iter(),
                    len,
                })
            }
            Value::Tuple(v) => {
                let v = v.into_raw_or_cloned();
                visitor.visit_seq(SeqAccess {
                    len: v.len(),
                    iter: v.into_iter(),
                    de: self,
                })
            }
            Value::Set(v) => {
                let v = v.into_raw_or_cloned();
                visitor.visit_seq(SeqAccess {
                    de: self,
                    len: v.len(),
                    iter: v.into_iter(),
                })
            }
            Value::FrozenSet(v) => {
                let v = v.into_raw_or_cloned();
                visitor.visit_seq(SeqAccess {
                    de: self,
                    len: v.len(),
                    iter: v.into_iter(),
                })
            }
            Value::Dict(v) => {
                let v = v.into_raw_or_cloned();
                let len = v.len();
                visitor.visit_map(MapAccess {
                    de: self,
                    iter: v.into_iter(),
                    value: None,
                    len,
                })
            }
            Value::MemoRef(memo_id) => {
                self.resolve_recursive(memo_id, visitor, |slf, visitor, value| {
                    slf.value = Some(value);
                    slf.deserialize_any(visitor)
                })
            }
            Value::Object(o) => {
                // Convert to public Value, then use value_impls Deserializer
                let public_val = o.__reduce__().state_or_none();
                let mut de = crate::value_impls::Deserializer::new(public_val);
                serde::de::Deserializer::deserialize_any(&mut de, visitor)
            }
            Value::Global(_) => {
                if self.options.replace_unresolved_globals {
                    visitor.visit_unit()
                } else {
                    Err(Error::Syntax(ErrorCode::UnresolvedGlobal))
                }
            }
        }
    }

    #[inline]
    fn deserialize_option<V: Visitor<'de>>(self, visitor: V) -> Result<V::Value> {
        let value = self.get_next_value()?;
        match value {
            Value::None => visitor.visit_none(),
            _ => {
                self.value = Some(value);
                visitor.visit_some(self)
            }
        }
    }

    #[inline]
    fn deserialize_newtype_struct<V: Visitor<'de>>(
        self,
        _name: &'static str,
        visitor: V,
    ) -> Result<V::Value> {
        visitor.visit_newtype_struct(self)
    }

    #[inline]
    fn deserialize_enum<V: Visitor<'de>>(
        self,
        _name: &'static str,
        _variants: &'static [&'static str],
        visitor: V,
    ) -> Result<V::Value> {
        visitor.visit_enum(VariantAccess { de: self })
    }

    forward_to_deserialize_any! {
        bool u8 u16 u32 u64 i8 i16 i32 i64 f32 f64 char str string unit seq
        bytes byte_buf map tuple_struct struct identifier
        tuple ignored_any unit_struct
    }
}

struct VariantAccess<'a, R: Read + 'a> {
    de: &'a mut Deserializer<R>,
}

impl<'de: 'a, 'a, R: Read + 'a> de::EnumAccess<'de> for VariantAccess<'a, R> {
    type Error = Error;
    type Variant = Self;

    fn variant_seed<V: de::DeserializeSeed<'de>>(self, seed: V) -> Result<(V::Value, Self)> {
        let value = self.de.get_next_value()?;
        match value {
            Value::Tuple(v) => {
                let mut v = v.into_raw_or_cloned();

                if v.len() == 2 {
                    let args = v.pop();
                    self.de.value = v.pop();
                    let val = seed.deserialize(&mut *self.de)?;
                    self.de.value = args;
                    Ok((val, self))
                } else {
                    self.de.value = v.pop();
                    let val = seed.deserialize(&mut *self.de)?;
                    Ok((val, self))
                }
            }
            Value::Dict(v) => {
                let mut v = v.into_raw_or_cloned();

                if v.len() != 1 {
                    Err(Error::Syntax(ErrorCode::Structure(
                        "enum variants must \
                                                            have one dict entry"
                            .into(),
                    )))
                } else {
                    let (name, args) = v.pop().unwrap();
                    self.de.value = Some(name);
                    let val = seed.deserialize(&mut *self.de)?;
                    self.de.value = Some(args);
                    Ok((val, self))
                }
            }
            Value::MemoRef(memo_id) => {
                self.de.resolve_recursive(memo_id, (), |slf, (), value| {
                    slf.value = Some(value);
                    Ok(())
                })?;
                // retry with memo resolved
                self.variant_seed(seed)
            }
            s @ Value::String(_) => {
                self.de.value = Some(s);
                let val = seed.deserialize(&mut *self.de)?;
                Ok((val, self))
            }
            _ => Err(Error::Syntax(ErrorCode::Structure(
                "enums must be represented as \
                                                         dicts or tuples"
                    .into(),
            ))),
        }
    }
}

impl<'de: 'a, 'a, R: Read + 'a> de::VariantAccess<'de> for VariantAccess<'a, R> {
    type Error = Error;

    fn unit_variant(self) -> Result<()> {
        Ok(())
    }

    fn newtype_variant_seed<T: de::DeserializeSeed<'de>>(self, seed: T) -> Result<T::Value> {
        seed.deserialize(self.de)
    }

    fn tuple_variant<V: Visitor<'de>>(self, _len: usize, visitor: V) -> Result<V::Value> {
        de::Deserializer::deserialize_any(self.de, visitor)
    }

    fn struct_variant<V: Visitor<'de>>(
        self,
        _fields: &'static [&'static str],
        visitor: V,
    ) -> Result<V::Value> {
        de::Deserializer::deserialize_any(self.de, visitor)
    }
}

struct SeqAccess<'a, R: Read + 'a> {
    de: &'a mut Deserializer<R>,
    iter: vec::IntoIter<Value>,
    len: usize,
}

impl<'de: 'a, 'a, R: Read> de::SeqAccess<'de> for SeqAccess<'a, R> {
    type Error = Error;

    fn next_element_seed<T: de::DeserializeSeed<'de>>(
        &mut self,
        seed: T,
    ) -> Result<Option<T::Value>> {
        match self.iter.next() {
            Some(value) => {
                self.len -= 1;
                self.de.value = Some(value);
                Ok(Some(seed.deserialize(&mut *self.de)?))
            }
            None => Ok(None),
        }
    }

    fn size_hint(&self) -> Option<usize> {
        Some(self.len)
    }
}

struct MapAccess<'a, R: Read + 'a> {
    de: &'a mut Deserializer<R>,
    iter: vec::IntoIter<(Value, Value)>,
    value: Option<Value>,
    len: usize,
}

impl<'de: 'a, 'a, R: Read> de::MapAccess<'de> for MapAccess<'a, R> {
    type Error = Error;

    fn next_key_seed<T: de::DeserializeSeed<'de>>(&mut self, seed: T) -> Result<Option<T::Value>> {
        match self.iter.next() {
            Some((key, value)) => {
                self.len -= 1;
                self.value = Some(value);
                self.de.value = Some(key);
                Ok(Some(seed.deserialize(&mut *self.de)?))
            }
            None => Ok(None),
        }
    }

    fn next_value_seed<T: de::DeserializeSeed<'de>>(&mut self, seed: T) -> Result<T::Value> {
        let value = self.value.take().unwrap();
        self.de.value = Some(value);
        seed.deserialize(&mut *self.de)
    }

    fn size_hint(&self) -> Option<usize> {
        Some(self.len)
    }
}

/// Decodes a value from a `std::io::Read`.
pub fn from_reader<'de, R: io::Read, T: de::Deserialize<'de>>(
    rdr: R,
    options: DeOptions,
) -> Result<T> {
    let mut de = Deserializer::new(rdr, options);
    let value = de::Deserialize::deserialize(&mut de)?;
    // Make sure the whole stream has been consumed.
    de.end()?;
    Ok(value)
}

/// Decodes a value from a byte slice `&[u8]`.
pub fn from_slice<'de, T: de::Deserialize<'de>>(v: &[u8], options: DeOptions) -> Result<T> {
    from_reader(io::Cursor::new(v), options)
}

/// Decodes a value from any iterator supported as a reader.
pub fn from_iter<'de, E, I, T>(it: I, options: DeOptions) -> Result<T>
where
    E: IterReadItem,
    I: FusedIterator<Item = E>,
    T: de::Deserialize<'de>,
{
    from_reader(IterRead::new(it), options)
}

/// Decodes a value from a `std::io::Read`.
pub fn value_from_reader<R: io::Read>(rdr: R, options: DeOptions) -> Result<value::Value> {
    let mut de = Deserializer::new(rdr, options);
    let value = de.deserialize_value()?;
    de.end()?;
    Ok(value)
}

/// Decodes a value from a byte slice `&[u8]`.
pub fn value_from_slice(v: &[u8], options: DeOptions) -> Result<value::Value> {
    value_from_reader(io::Cursor::new(v), options)
}

/// Decodes a value from any iterator supported as a reader.
pub fn value_from_iter<E, I>(it: I, options: DeOptions) -> Result<value::Value>
where
    E: IterReadItem,
    I: FusedIterator<Item = E>,
{
    value_from_reader(IterRead::new(it), options)
}