File: ObjectWriter.cs
Web Access
Project: ..\..\..\src\CodeStyle\Core\Analyzers\Microsoft.CodeAnalysis.CodeStyle.csproj (Microsoft.CodeAnalysis.CodeStyle)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Reflection;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis;
using EncodingExtensions = Microsoft.CodeAnalysis.EncodingExtensions;
 
namespace Roslyn.Utilities
{
    using System.Collections.Immutable;
    using System.Threading.Tasks;
#if COMPILERCORE
    using Resources = CodeAnalysisResources;
#elif CODE_STYLE
    using Resources = CodeStyleResources;
#else
    using Resources = WorkspacesResources;
#endif
 
    /// <summary>
    /// An <see cref="ObjectWriter"/> that serializes objects to a byte stream.
    /// </summary>
    internal sealed partial class ObjectWriter : IDisposable
    {
        private readonly BinaryWriter _writer;
        private readonly CancellationToken _cancellationToken;
 
        /// <summary>
        /// Map of serialized object's reference ids.  The object-reference-map uses reference equality
        /// for performance.  While the string-reference-map uses value-equality for greater cache hits
        /// and reuse.
        ///
        /// These are not readonly because they're structs and we mutate them.
        ///
        /// When we write out objects/strings we give each successive, unique, item a monotonically
        /// increasing integral ID starting at 0.  I.e. the first object gets ID-0, the next gets
        /// ID-1 and so on and so forth.  We do *not* include these IDs with the object when it is
        /// written out.  We only include the ID if we hit the object *again* while writing.
        ///
        /// During reading, the reader knows to give each object it reads the same monotonically
        /// increasing integral value.  i.e. the first object it reads is put into an array at position
        /// 0, the next at position 1, and so on.  Then, when the reader reads in an object-reference
        /// it can just retrieved it directly from that array.
        ///
        /// In other words, writing and reading take advantage of the fact that they know they will
        /// write and read objects in the exact same order.  So they only need the IDs for references
        /// and not the objects themselves because the ID is inferred from the order the object is
        /// written or read in.
        /// </summary>
        private WriterReferenceMap _objectReferenceMap;
        private WriterReferenceMap _stringReferenceMap;
 
        /// <summary>
        /// Copy of the global binder data that maps from Types to the appropriate reading-function
        /// for that type.  Types register functions directly with <see cref="ObjectBinder"/>, but
        /// that means that <see cref="ObjectBinder"/> is both static and locked.  This gives us
        /// local copy we can work with without needing to worry about anyone else mutating.
        /// </summary>
        private readonly ObjectBinderSnapshot _binderSnapshot;
 
        private int _recursionDepth;
        internal const int MaxRecursionDepth = 50;
 
        /// <summary>
        /// Creates a new instance of a <see cref="ObjectWriter"/>.
        /// </summary>
        /// <param name="stream">The stream to write to.</param>
        /// <param name="leaveOpen">True to leave the <paramref name="stream"/> open after the <see cref="ObjectWriter"/> is disposed.</param>
        /// <param name="cancellationToken">Cancellation token.</param>
        public ObjectWriter(
            Stream stream,
            bool leaveOpen = false,
            CancellationToken cancellationToken = default)
        {
            // String serialization assumes both reader and writer to be of the same endianness.
            // It can be adjusted for BigEndian if needed.
            Debug.Assert(BitConverter.IsLittleEndian);
 
            _writer = new BinaryWriter(stream, Encoding.UTF8, leaveOpen);
            _objectReferenceMap = new WriterReferenceMap(valueEquality: false);
            _stringReferenceMap = new WriterReferenceMap(valueEquality: true);
            _cancellationToken = cancellationToken;
 
            // Capture a copy of the current static binder state.  That way we don't have to
            // access any locks while we're doing our processing.
            _binderSnapshot = ObjectBinder.GetSnapshot();
 
            WriteVersion();
        }
 
        private void WriteVersion()
        {
            _writer.Write(ObjectReader.VersionByte1);
            _writer.Write(ObjectReader.VersionByte2);
        }
 
        public void Dispose()
        {
            _writer.Dispose();
            _objectReferenceMap.Dispose();
            _stringReferenceMap.Dispose();
            _recursionDepth = 0;
        }
 
        public void WriteBoolean(bool value) => _writer.Write(value);
        public void WriteByte(byte value) => _writer.Write(value);
        // written as ushort because BinaryWriter fails on chars that are unicode surrogates
        public void WriteChar(char ch) => _writer.Write((ushort)ch);
        public void WriteDecimal(decimal value) => _writer.Write(value);
        public void WriteDouble(double value) => _writer.Write(value);
        public void WriteSingle(float value) => _writer.Write(value);
        public void WriteInt32(int value) => _writer.Write(value);
        public void WriteInt64(long value) => _writer.Write(value);
        public void WriteSByte(sbyte value) => _writer.Write(value);
        public void WriteInt16(short value) => _writer.Write(value);
        public void WriteUInt32(uint value) => _writer.Write(value);
        public void WriteUInt64(ulong value) => _writer.Write(value);
        public void WriteUInt16(ushort value) => _writer.Write(value);
        public void WriteString(string? value) => WriteStringValue(value);
 
        /// <summary>
        /// Used so we can easily grab the low/high 64bits of a guid for serialization.
        /// </summary>
        [StructLayout(LayoutKind.Explicit)]
        internal struct GuidAccessor
        {
            [FieldOffset(0)]
            public Guid Guid;
 
            [FieldOffset(0)]
            public long Low64;
            [FieldOffset(8)]
            public long High64;
        }
 
        public void WriteGuid(Guid guid)
        {
            var accessor = new GuidAccessor { Guid = guid };
            WriteInt64(accessor.Low64);
            WriteInt64(accessor.High64);
        }
 
        public void WriteValue(object? value)
        {
            Debug.Assert(value == null || !value.GetType().GetTypeInfo().IsEnum, "Enum should not be written with WriteValue.  Write them as ints instead.");
 
            if (value == null)
            {
                _writer.Write((byte)TypeCode.Null);
                return;
            }
 
            var type = value.GetType();
            var typeInfo = type.GetTypeInfo();
            Debug.Assert(!typeInfo.IsEnum, "Enums should not be written with WriteObject.  Write them out as integers instead.");
 
            // Perf: Note that JIT optimizes each expression value.GetType() == typeof(T) to a single register comparison.
            // Also the checks are sorted by commonality of the checked types.
 
            // The primitive types are
            // Boolean, Byte, SByte, Int16, UInt16, Int32, UInt32,
            // Int64, UInt64, IntPtr, UIntPtr, Char, Double, and Single.
            if (typeInfo.IsPrimitive)
            {
                // Note: int, double, bool, char, have been chosen to go first as they're they
                // common values of literals in code, and so would be the likely hits if we do
                // have a primitive type we're serializing out.
                if (value.GetType() == typeof(int))
                {
                    WriteEncodedInt32((int)value);
                }
                else if (value.GetType() == typeof(double))
                {
                    _writer.Write((byte)TypeCode.Float8);
                    _writer.Write((double)value);
                }
                else if (value.GetType() == typeof(bool))
                {
                    _writer.Write((byte)((bool)value ? TypeCode.Boolean_True : TypeCode.Boolean_False));
                }
                else if (value.GetType() == typeof(char))
                {
                    _writer.Write((byte)TypeCode.Char);
                    _writer.Write((ushort)(char)value);  // written as ushort because BinaryWriter fails on chars that are unicode surrogates
                }
                else if (value.GetType() == typeof(byte))
                {
                    _writer.Write((byte)TypeCode.UInt8);
                    _writer.Write((byte)value);
                }
                else if (value.GetType() == typeof(short))
                {
                    _writer.Write((byte)TypeCode.Int16);
                    _writer.Write((short)value);
                }
                else if (value.GetType() == typeof(long))
                {
                    _writer.Write((byte)TypeCode.Int64);
                    _writer.Write((long)value);
                }
                else if (value.GetType() == typeof(sbyte))
                {
                    _writer.Write((byte)TypeCode.Int8);
                    _writer.Write((sbyte)value);
                }
                else if (value.GetType() == typeof(float))
                {
                    _writer.Write((byte)TypeCode.Float4);
                    _writer.Write((float)value);
                }
                else if (value.GetType() == typeof(ushort))
                {
                    _writer.Write((byte)TypeCode.UInt16);
                    _writer.Write((ushort)value);
                }
                else if (value.GetType() == typeof(uint))
                {
                    WriteEncodedUInt32((uint)value);
                }
                else if (value.GetType() == typeof(ulong))
                {
                    _writer.Write((byte)TypeCode.UInt64);
                    _writer.Write((ulong)value);
                }
                else
                {
                    throw ExceptionUtilities.UnexpectedValue(value.GetType());
                }
            }
            else if (value.GetType() == typeof(decimal))
            {
                _writer.Write((byte)TypeCode.Decimal);
                _writer.Write((decimal)value);
            }
            else if (value.GetType() == typeof(DateTime))
            {
                _writer.Write((byte)TypeCode.DateTime);
                _writer.Write(((DateTime)value).ToBinary());
            }
            else if (value.GetType() == typeof(string))
            {
                WriteStringValue((string)value);
            }
            else if (type.IsArray)
            {
                var instance = (Array)value;
 
                if (instance.Rank > 1)
                {
                    throw new InvalidOperationException(Resources.Arrays_with_more_than_one_dimension_cannot_be_serialized);
                }
 
                WriteArray(instance);
            }
            else if (value is Encoding encoding)
            {
                WriteEncoding(encoding);
            }
            else
            {
                WriteObject(instance: value, instanceAsWritable: null);
            }
        }
 
        /// <summary>
        /// Write an array of bytes. The array data is provided as a
        /// <see cref="ReadOnlySpan{T}">ReadOnlySpan</see>&lt;<see cref="byte"/>&gt;, and deserialized to a byte array.
        /// </summary>
        /// <param name="span">The array data.</param>
        public void WriteValue(ReadOnlySpan<byte> span)
        {
            int length = span.Length;
            switch (length)
            {
                case 0:
                    _writer.Write((byte)TypeCode.Array_0);
                    break;
                case 1:
                    _writer.Write((byte)TypeCode.Array_1);
                    break;
                case 2:
                    _writer.Write((byte)TypeCode.Array_2);
                    break;
                case 3:
                    _writer.Write((byte)TypeCode.Array_3);
                    break;
                default:
                    _writer.Write((byte)TypeCode.Array);
                    WriteCompressedUInt((uint)length);
                    break;
            }
 
            var elementType = typeof(byte);
            Debug.Assert(s_typeMap[elementType] == TypeCode.UInt8);
 
            WritePrimitiveType(elementType, TypeCode.UInt8);
 
#if NETCOREAPP
            _writer.Write(span);
#else
            // BinaryWriter in .NET Framework does not support ReadOnlySpan<byte>, so we use a temporary buffer to write
            // arrays of data. The buffer is chosen to be no larger than 8K, which avoids allocations in the large
            // object heap.
            var buffer = new byte[Math.Min(length, 8192)];
            for (int offset = 0; offset < length; offset += buffer.Length)
            {
                var segmentLength = Math.Min(buffer.Length, length - offset);
                span.Slice(offset, segmentLength).CopyTo(buffer.AsSpan());
                _writer.Write(buffer, 0, segmentLength);
            }
#endif
        }
 
        public void WriteValue(IObjectWritable? value)
        {
            if (value == null)
            {
                _writer.Write((byte)TypeCode.Null);
                return;
            }
 
            WriteObject(instance: value, instanceAsWritable: value);
        }
 
        private void WriteEncodedInt32(int v)
        {
            if (v >= 0 && v <= 10)
            {
                _writer.Write((byte)((int)TypeCode.Int32_0 + v));
            }
            else if (v >= 0 && v < byte.MaxValue)
            {
                _writer.Write((byte)TypeCode.Int32_1Byte);
                _writer.Write((byte)v);
            }
            else if (v >= 0 && v < ushort.MaxValue)
            {
                _writer.Write((byte)TypeCode.Int32_2Bytes);
                _writer.Write((ushort)v);
            }
            else
            {
                _writer.Write((byte)TypeCode.Int32);
                _writer.Write(v);
            }
        }
 
        private void WriteEncodedUInt32(uint v)
        {
            if (v >= 0 && v <= 10)
            {
                _writer.Write((byte)((int)TypeCode.UInt32_0 + v));
            }
            else if (v >= 0 && v < byte.MaxValue)
            {
                _writer.Write((byte)TypeCode.UInt32_1Byte);
                _writer.Write((byte)v);
            }
            else if (v >= 0 && v < ushort.MaxValue)
            {
                _writer.Write((byte)TypeCode.UInt32_2Bytes);
                _writer.Write((ushort)v);
            }
            else
            {
                _writer.Write((byte)TypeCode.UInt32);
                _writer.Write(v);
            }
        }
 
        /// <summary>
        /// An object reference to reference-id map, that can share base data efficiently.
        /// </summary>
        private struct WriterReferenceMap
        {
            // PERF: Use segmented collection to avoid Large Object Heap allocations during serialization.
            // https://github.com/dotnet/roslyn/issues/43401
            private readonly SegmentedDictionary<object, int> _valueToIdMap;
            private readonly bool _valueEquality;
            private int _nextId;
 
            private static readonly ObjectPool<SegmentedDictionary<object, int>> s_referenceDictionaryPool =
                new(() => new SegmentedDictionary<object, int>(128, ReferenceEqualityComparer.Instance));
 
            private static readonly ObjectPool<SegmentedDictionary<object, int>> s_valueDictionaryPool =
                new(() => new SegmentedDictionary<object, int>(128));
 
            public WriterReferenceMap(bool valueEquality)
            {
                _valueEquality = valueEquality;
                _valueToIdMap = GetDictionaryPool(valueEquality).Allocate();
                _nextId = 0;
            }
 
            private static ObjectPool<SegmentedDictionary<object, int>> GetDictionaryPool(bool valueEquality)
                => valueEquality ? s_valueDictionaryPool : s_referenceDictionaryPool;
 
            public void Dispose()
            {
                var pool = GetDictionaryPool(_valueEquality);
 
                // If the map grew too big, don't return it to the pool.
                // When testing with the Roslyn solution, this dropped only 2.5% of requests.
                if (_valueToIdMap.Count > 1024)
                {
                    pool.ForgetTrackedObject(_valueToIdMap);
                }
                else
                {
                    _valueToIdMap.Clear();
                    pool.Free(_valueToIdMap);
                }
            }
 
            public bool TryGetReferenceId(object value, out int referenceId)
                => _valueToIdMap.TryGetValue(value, out referenceId);
 
            public void Add(object value, bool isReusable)
            {
                var id = _nextId++;
 
                if (isReusable)
                {
                    _valueToIdMap.Add(value, id);
                }
            }
        }
 
        internal void WriteCompressedUInt(uint value)
        {
            if (value <= (byte.MaxValue >> 2))
            {
                _writer.Write((byte)value);
            }
            else if (value <= (ushort.MaxValue >> 2))
            {
                byte byte0 = (byte)(((value >> 8) & 0xFFu) | Byte2Marker);
                byte byte1 = (byte)(value & 0xFFu);
 
                // high-bytes to low-bytes
                _writer.Write(byte0);
                _writer.Write(byte1);
            }
            else if (value <= (uint.MaxValue >> 2))
            {
                byte byte0 = (byte)(((value >> 24) & 0xFFu) | Byte4Marker);
                byte byte1 = (byte)((value >> 16) & 0xFFu);
                byte byte2 = (byte)((value >> 8) & 0xFFu);
                byte byte3 = (byte)(value & 0xFFu);
 
                // high-bytes to low-bytes
                _writer.Write(byte0);
                _writer.Write(byte1);
                _writer.Write(byte2);
                _writer.Write(byte3);
            }
            else
            {
                throw new ArgumentException(Resources.Value_too_large_to_be_represented_as_a_30_bit_unsigned_integer);
            }
        }
 
        private unsafe void WriteStringValue(string? value)
        {
            if (value == null)
            {
                _writer.Write((byte)TypeCode.Null);
            }
            else
            {
                if (_stringReferenceMap.TryGetReferenceId(value, out int id))
                {
                    Debug.Assert(id >= 0);
                    if (id <= byte.MaxValue)
                    {
                        _writer.Write((byte)TypeCode.StringRef_1Byte);
                        _writer.Write((byte)id);
                    }
                    else if (id <= ushort.MaxValue)
                    {
                        _writer.Write((byte)TypeCode.StringRef_2Bytes);
                        _writer.Write((ushort)id);
                    }
                    else
                    {
                        _writer.Write((byte)TypeCode.StringRef_4Bytes);
                        _writer.Write(id);
                    }
                }
                else
                {
                    _stringReferenceMap.Add(value, isReusable: true);
 
                    if (value.IsValidUnicodeString())
                    {
                        // Usual case - the string can be encoded as UTF-8:
                        // We can use the UTF-8 encoding of the binary writer.
 
                        _writer.Write((byte)TypeCode.StringUtf8);
                        _writer.Write(value);
                    }
                    else
                    {
                        _writer.Write((byte)TypeCode.StringUtf16);
 
                        // This is rare, just allocate UTF16 bytes for simplicity.
                        byte[] bytes = new byte[(uint)value.Length * sizeof(char)];
                        fixed (char* valuePtr = value)
                        {
                            Marshal.Copy((IntPtr)valuePtr, bytes, 0, bytes.Length);
                        }
 
                        WriteCompressedUInt((uint)value.Length);
                        _writer.Write(bytes);
                    }
                }
            }
        }
 
        private void WriteArray(Array array)
        {
            int length = array.GetLength(0);
 
            switch (length)
            {
                case 0:
                    _writer.Write((byte)TypeCode.Array_0);
                    break;
                case 1:
                    _writer.Write((byte)TypeCode.Array_1);
                    break;
                case 2:
                    _writer.Write((byte)TypeCode.Array_2);
                    break;
                case 3:
                    _writer.Write((byte)TypeCode.Array_3);
                    break;
                default:
                    _writer.Write((byte)TypeCode.Array);
                    this.WriteCompressedUInt((uint)length);
                    break;
            }
 
            var elementType = array.GetType().GetElementType()!;
 
            if (s_typeMap.TryGetValue(elementType, out var elementKind))
            {
                this.WritePrimitiveType(elementType, elementKind);
                this.WritePrimitiveTypeArrayElements(elementType, elementKind, array);
            }
            else
            {
                // emit header up front
                this.WriteKnownType(elementType);
 
                // recursive: write elements now
                var oldDepth = _recursionDepth;
                _recursionDepth++;
 
                if (_recursionDepth % MaxRecursionDepth == 0)
                {
                    _cancellationToken.ThrowIfCancellationRequested();
 
                    // If we're recursing too deep, move the work to another thread to do so we
                    // don't blow the stack.
                    var task = SerializationThreadPool.RunOnBackgroundThreadAsync(
                        a =>
                        {
                            WriteArrayValues((Array)a!);
                            return null;
                        },
                        array);
 
                    // We must not proceed until the additional task completes. After returning from a write, the underlying
                    // stream providing access to raw memory will be closed; if this occurs before the separate thread
                    // completes its write then an access violation can occur attempting to write to unmapped memory.
                    //
                    // CANCELLATION: If cancellation is required, DO NOT attempt to cancel the operation by cancelling this
                    // wait. Cancellation must only be implemented by modifying 'task' to cancel itself in a timely manner
                    // so the wait can complete.
                    task.GetAwaiter().GetResult();
                }
                else
                {
                    WriteArrayValues(array);
                }
 
                _recursionDepth--;
                Debug.Assert(_recursionDepth == oldDepth);
            }
        }
 
        private void WriteArrayValues(Array array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                this.WriteValue(array.GetValue(i));
            }
        }
 
        private void WritePrimitiveTypeArrayElements(Type type, TypeCode kind, Array instance)
        {
            Debug.Assert(s_typeMap[type] == kind);
 
            // optimization for type underlying binary writer knows about
            if (type == typeof(byte))
            {
                _writer.Write((byte[])instance);
            }
            else if (type == typeof(char))
            {
                _writer.Write((char[])instance);
            }
            else if (type == typeof(string))
            {
                // optimization for string which object writer has
                // its own optimization to reduce repeated string
                WriteStringArrayElements((string[])instance);
            }
            else if (type == typeof(bool))
            {
                // optimization for bool array
                WriteBooleanArrayElements((bool[])instance);
            }
            else
            {
                // otherwise, write elements directly to underlying binary writer
                switch (kind)
                {
                    case TypeCode.Int8:
                        WriteInt8ArrayElements((sbyte[])instance);
                        return;
                    case TypeCode.Int16:
                        WriteInt16ArrayElements((short[])instance);
                        return;
                    case TypeCode.Int32:
                        WriteInt32ArrayElements((int[])instance);
                        return;
                    case TypeCode.Int64:
                        WriteInt64ArrayElements((long[])instance);
                        return;
                    case TypeCode.UInt16:
                        WriteUInt16ArrayElements((ushort[])instance);
                        return;
                    case TypeCode.UInt32:
                        WriteUInt32ArrayElements((uint[])instance);
                        return;
                    case TypeCode.UInt64:
                        WriteUInt64ArrayElements((ulong[])instance);
                        return;
                    case TypeCode.Float4:
                        WriteFloat4ArrayElements((float[])instance);
                        return;
                    case TypeCode.Float8:
                        WriteFloat8ArrayElements((double[])instance);
                        return;
                    case TypeCode.Decimal:
                        WriteDecimalArrayElements((decimal[])instance);
                        return;
                    default:
                        throw ExceptionUtilities.UnexpectedValue(kind);
                }
            }
        }
 
        private void WriteBooleanArrayElements(bool[] array)
        {
            // convert bool array to bit array
            var bits = BitVector.Create(array.Length);
            for (var i = 0; i < array.Length; i++)
            {
                bits[i] = array[i];
            }
 
            // send over bit array
            foreach (var word in bits.Words())
            {
                _writer.Write(word);
            }
        }
 
        private void WriteStringArrayElements(string[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                WriteStringValue(array[i]);
            }
        }
 
        private void WriteInt8ArrayElements(sbyte[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteInt16ArrayElements(short[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteInt32ArrayElements(int[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteInt64ArrayElements(long[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteUInt16ArrayElements(ushort[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteUInt32ArrayElements(uint[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteUInt64ArrayElements(ulong[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteDecimalArrayElements(decimal[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteFloat4ArrayElements(float[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WriteFloat8ArrayElements(double[] array)
        {
            for (var i = 0; i < array.Length; i++)
            {
                _writer.Write(array[i]);
            }
        }
 
        private void WritePrimitiveType(Type type, TypeCode kind)
        {
            Debug.Assert(s_typeMap[type] == kind);
            _writer.Write((byte)kind);
        }
 
        public void WriteType(Type type)
        {
            _writer.Write((byte)TypeCode.Type);
            this.WriteString(type.AssemblyQualifiedName);
        }
 
        private void WriteKnownType(Type type)
        {
            _writer.Write((byte)TypeCode.Type);
            this.WriteInt32(_binderSnapshot.GetTypeId(type));
        }
 
        public void WriteEncoding(Encoding? encoding)
        {
            if (encoding == null)
            {
                WriteByte((byte)TypeCode.Null);
            }
            else if (encoding.TryGetEncodingKind(out var kind))
            {
                WriteByte((byte)ToTypeCode(kind));
            }
            else if (encoding.CodePage > 0)
            {
                WriteByte((byte)TypeCode.EncodingCodePage);
                WriteInt32(encoding.CodePage);
            }
            else
            {
                WriteByte((byte)TypeCode.EncodingName);
                WriteString(encoding.WebName);
            }
        }
 
        private void WriteObject(object instance, IObjectWritable? instanceAsWritable)
        {
            RoslynDebug.Assert(instance != null);
            RoslynDebug.Assert(instanceAsWritable == null || instance == instanceAsWritable);
 
            _cancellationToken.ThrowIfCancellationRequested();
 
            // write object ref if we already know this instance
            if (_objectReferenceMap.TryGetReferenceId(instance, out var id))
            {
                Debug.Assert(id >= 0);
                if (id <= byte.MaxValue)
                {
                    _writer.Write((byte)TypeCode.ObjectRef_1Byte);
                    _writer.Write((byte)id);
                }
                else if (id <= ushort.MaxValue)
                {
                    _writer.Write((byte)TypeCode.ObjectRef_2Bytes);
                    _writer.Write((ushort)id);
                }
                else
                {
                    _writer.Write((byte)TypeCode.ObjectRef_4Bytes);
                    _writer.Write(id);
                }
            }
            else
            {
                var writable = instanceAsWritable;
                if (writable == null)
                {
                    writable = instance as IObjectWritable;
                    if (writable == null)
                    {
                        throw NoSerializationWriterException($"{instance.GetType()} must implement {nameof(IObjectWritable)}");
                    }
                }
 
                var oldDepth = _recursionDepth;
                _recursionDepth++;
 
                if (_recursionDepth % MaxRecursionDepth == 0)
                {
                    _cancellationToken.ThrowIfCancellationRequested();
 
                    // If we're recursing too deep, move the work to another thread to do so we
                    // don't blow the stack.
                    var task = SerializationThreadPool.RunOnBackgroundThreadAsync(
                        obj =>
                        {
                            WriteObjectWorker((IObjectWritable)obj!);
                            return null;
                        },
                        writable);
 
                    // We must not proceed until the additional task completes. After returning from a write, the underlying
                    // stream providing access to raw memory will be closed; if this occurs before the separate thread
                    // completes its write then an access violation can occur attempting to write to unmapped memory.
                    //
                    // CANCELLATION: If cancellation is required, DO NOT attempt to cancel the operation by cancelling this
                    // wait. Cancellation must only be implemented by modifying 'task' to cancel itself in a timely manner
                    // so the wait can complete.
                    task.GetAwaiter().GetResult();
                }
                else
                {
                    WriteObjectWorker(writable);
                }
 
                _recursionDepth--;
                Debug.Assert(_recursionDepth == oldDepth);
            }
        }
 
        private void WriteObjectWorker(IObjectWritable writable)
        {
            _objectReferenceMap.Add(writable, writable.ShouldReuseInSerialization);
 
            // emit object header up front
            _writer.Write((byte)TypeCode.Object);
 
            // Directly write out the type-id for this object.  i.e. no need to write out the 'Type'
            // tag since we just wrote out the 'Object' tag
            this.WriteInt32(_binderSnapshot.GetTypeId(writable.GetType()));
            writable.WriteTo(this);
        }
 
        private static Exception NoSerializationTypeException(string typeName)
        {
            return new InvalidOperationException(string.Format(Resources.The_type_0_is_not_understood_by_the_serialization_binder, typeName));
        }
 
        private static Exception NoSerializationWriterException(string typeName)
        {
            return new InvalidOperationException(string.Format(Resources.Cannot_serialize_type_0, typeName));
        }
 
        // we have s_typeMap and s_reversedTypeMap since there is no bidirectional map in compiler
        // Note: s_typeMap is effectively immutable.  However, for maximum perf we use mutable types because
        // they are used in hotspots.
        internal static readonly Dictionary<Type, TypeCode> s_typeMap;
 
        /// <summary>
        /// Indexed by <see cref="TypeCode"/>.
        /// </summary>
        internal static readonly ImmutableArray<Type> s_reverseTypeMap;
 
        static ObjectWriter()
        {
            s_typeMap = new Dictionary<Type, TypeCode>
            {
                { typeof(bool), TypeCode.BooleanType },
                { typeof(char), TypeCode.Char },
                { typeof(string), TypeCode.StringType },
                { typeof(sbyte), TypeCode.Int8 },
                { typeof(short), TypeCode.Int16 },
                { typeof(int), TypeCode.Int32 },
                { typeof(long), TypeCode.Int64 },
                { typeof(byte), TypeCode.UInt8 },
                { typeof(ushort), TypeCode.UInt16 },
                { typeof(uint), TypeCode.UInt32 },
                { typeof(ulong), TypeCode.UInt64 },
                { typeof(float), TypeCode.Float4 },
                { typeof(double), TypeCode.Float8 },
                { typeof(decimal), TypeCode.Decimal },
            };
 
            var temp = new Type[(int)TypeCode.Last];
 
            foreach (var kvp in s_typeMap)
            {
                temp[(int)kvp.Value] = kvp.Key;
            }
 
            s_reverseTypeMap = ImmutableArray.Create(temp);
        }
 
        /// <summary>
        /// byte marker mask for encoding compressed uint
        /// </summary>
        internal const byte ByteMarkerMask = 3 << 6;
 
        /// <summary>
        /// byte marker bits for uint encoded in 1 byte.
        /// </summary>
        internal const byte Byte1Marker = 0;
 
        /// <summary>
        /// byte marker bits for uint encoded in 2 bytes.
        /// </summary>
        internal const byte Byte2Marker = 1 << 6;
 
        /// <summary>
        /// byte marker bits for uint encoded in 4 bytes.
        /// </summary>
        internal const byte Byte4Marker = 2 << 6;
 
        internal enum TypeCode : byte
        {
            /// <summary>
            /// The null value
            /// </summary>
            Null,
 
            /// <summary>
            /// A type
            /// </summary>
            Type,
 
            /// <summary>
            /// An object with member values encoded as variants
            /// </summary>
            Object,
 
            /// <summary>
            /// An object reference with the id encoded as 1 byte.
            /// </summary>
            ObjectRef_1Byte,
 
            /// <summary>
            /// An object reference with the id encode as 2 bytes.
            /// </summary>
            ObjectRef_2Bytes,
 
            /// <summary>
            /// An object reference with the id encoded as 4 bytes.
            /// </summary>
            ObjectRef_4Bytes,
 
            /// <summary>
            /// A string encoded as UTF-8 (using BinaryWriter.Write(string))
            /// </summary>
            StringUtf8,
 
            /// <summary>
            /// A string encoded as UTF16 (as array of UInt16 values)
            /// </summary>
            StringUtf16,
 
            /// <summary>
            /// A reference to a string with the id encoded as 1 byte.
            /// </summary>
            StringRef_1Byte,
 
            /// <summary>
            /// A reference to a string with the id encoded as 2 bytes.
            /// </summary>
            StringRef_2Bytes,
 
            /// <summary>
            /// A reference to a string with the id encoded as 4 bytes.
            /// </summary>
            StringRef_4Bytes,
 
            /// <summary>
            /// The boolean value true.
            /// </summary>
            Boolean_True,
 
            /// <summary>
            /// The boolean value char.
            /// </summary>
            Boolean_False,
 
            /// <summary>
            /// A character value encoded as 2 bytes.
            /// </summary>
            Char,
 
            /// <summary>
            /// An Int8 value encoded as 1 byte.
            /// </summary>
            Int8,
 
            /// <summary>
            /// An Int16 value encoded as 2 bytes.
            /// </summary>
            Int16,
 
            /// <summary>
            /// An Int32 value encoded as 4 bytes.
            /// </summary>
            Int32,
 
            /// <summary>
            /// An Int32 value encoded as 1 byte.
            /// </summary>
            Int32_1Byte,
 
            /// <summary>
            /// An Int32 value encoded as 2 bytes.
            /// </summary>
            Int32_2Bytes,
 
            /// <summary>
            /// The Int32 value 0
            /// </summary>
            Int32_0,
 
            /// <summary>
            /// The Int32 value 1
            /// </summary>
            Int32_1,
 
            /// <summary>
            /// The Int32 value 2
            /// </summary>
            Int32_2,
 
            /// <summary>
            /// The Int32 value 3
            /// </summary>
            Int32_3,
 
            /// <summary>
            /// The Int32 value 4
            /// </summary>
            Int32_4,
 
            /// <summary>
            /// The Int32 value 5
            /// </summary>
            Int32_5,
 
            /// <summary>
            /// The Int32 value 6
            /// </summary>
            Int32_6,
 
            /// <summary>
            /// The Int32 value 7
            /// </summary>
            Int32_7,
 
            /// <summary>
            /// The Int32 value 8
            /// </summary>
            Int32_8,
 
            /// <summary>
            /// The Int32 value 9
            /// </summary>
            Int32_9,
 
            /// <summary>
            /// The Int32 value 10
            /// </summary>
            Int32_10,
 
            /// <summary>
            /// An Int64 value encoded as 8 bytes
            /// </summary>
            Int64,
 
            /// <summary>
            /// A UInt8 value encoded as 1 byte.
            /// </summary>
            UInt8,
 
            /// <summary>
            /// A UIn16 value encoded as 2 bytes.
            /// </summary>
            UInt16,
 
            /// <summary>
            /// A UInt32 value encoded as 4 bytes.
            /// </summary>
            UInt32,
 
            /// <summary>
            /// A UInt32 value encoded as 1 byte.
            /// </summary>
            UInt32_1Byte,
 
            /// <summary>
            /// A UInt32 value encoded as 2 bytes.
            /// </summary>
            UInt32_2Bytes,
 
            /// <summary>
            /// The UInt32 value 0
            /// </summary>
            UInt32_0,
 
            /// <summary>
            /// The UInt32 value 1
            /// </summary>
            UInt32_1,
 
            /// <summary>
            /// The UInt32 value 2
            /// </summary>
            UInt32_2,
 
            /// <summary>
            /// The UInt32 value 3
            /// </summary>
            UInt32_3,
 
            /// <summary>
            /// The UInt32 value 4
            /// </summary>
            UInt32_4,
 
            /// <summary>
            /// The UInt32 value 5
            /// </summary>
            UInt32_5,
 
            /// <summary>
            /// The UInt32 value 6
            /// </summary>
            UInt32_6,
 
            /// <summary>
            /// The UInt32 value 7
            /// </summary>
            UInt32_7,
 
            /// <summary>
            /// The UInt32 value 8
            /// </summary>
            UInt32_8,
 
            /// <summary>
            /// The UInt32 value 9
            /// </summary>
            UInt32_9,
 
            /// <summary>
            /// The UInt32 value 10
            /// </summary>
            UInt32_10,
 
            /// <summary>
            /// A UInt64 value encoded as 8 bytes.
            /// </summary>
            UInt64,
 
            /// <summary>
            /// A float value encoded as 4 bytes.
            /// </summary>
            Float4,
 
            /// <summary>
            /// A double value encoded as 8 bytes.
            /// </summary>
            Float8,
 
            /// <summary>
            /// A decimal value encoded as 12 bytes.
            /// </summary>
            Decimal,
 
            /// <summary>
            /// A DateTime value
            /// </summary>
            DateTime,
 
            /// <summary>
            /// An array with length encoded as compressed uint
            /// </summary>
            Array,
 
            /// <summary>
            /// An array with zero elements
            /// </summary>
            Array_0,
 
            /// <summary>
            /// An array with one element
            /// </summary>
            Array_1,
 
            /// <summary>
            /// An array with 2 elements
            /// </summary>
            Array_2,
 
            /// <summary>
            /// An array with 3 elements
            /// </summary>
            Array_3,
 
            /// <summary>
            /// The boolean type
            /// </summary>
            BooleanType,
 
            /// <summary>
            /// The string type
            /// </summary>
            StringType,
 
            /// <summary>
            /// Encoding serialized as <see cref="Encoding.WebName"/>.
            /// </summary>
            EncodingName,
 
            /// <summary>
            /// Encoding serialized as <see cref="TextEncodingKind"/>.
            /// </summary>
            FirstWellKnownTextEncoding,
            LastWellKnownTextEncoding = FirstWellKnownTextEncoding + EncodingExtensions.LastTextEncodingKind - EncodingExtensions.FirstTextEncodingKind,
 
            /// <summary>
            /// Encoding serialized as <see cref="Encoding.CodePage"/>.
            /// </summary>
            EncodingCodePage,
 
            Last,
        }
 
        internal static TypeCode ToTypeCode(TextEncodingKind kind)
        {
            Debug.Assert(kind is >= EncodingExtensions.FirstTextEncodingKind and <= EncodingExtensions.LastTextEncodingKind);
            return TypeCode.FirstWellKnownTextEncoding + (byte)(kind - EncodingExtensions.FirstTextEncodingKind);
        }
 
        internal static TextEncodingKind ToEncodingKind(TypeCode code)
        {
            Debug.Assert(code is >= TypeCode.FirstWellKnownTextEncoding and <= TypeCode.LastWellKnownTextEncoding);
            return EncodingExtensions.FirstTextEncodingKind + (byte)(code - TypeCode.FirstWellKnownTextEncoding);
        }
    }
}