StackOverflowException when serializing large objects

[Darkar25]

First of all, thanks a lot for the amazing library.

When i was integrating MemoryPack in one of my projects i caught a StackOverflowException, but looking at the stacktrace i immediately knew what the problem was - my object had a very complex structure with a lot of interconnected and self-referenced instances so the MemoryPack had dug too deep into one of such instances and was stopped by SOE.

Here's a MRE for this issue:

using MemoryPack;

namespace MemoryPack_SOE_MRE
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Container container = new();
            Item? previous = null;
            for(int i = 0; i < 1_000_000; i++)
            {
                var item = new Item()
                {
                    Next = previous
                };
                container.Items.Add(item);
                previous = item;
            }
            container.Items = [.. container.Items.Reverse()]; // Artificially force MemoryPack to take the longer serialization path, but this could as well happen in the real life scenario.
            _ = MemoryPackSerializer.Serialize(container); // This WILL fail, so no need to store it anywhere
        }
    }

    [MemoryPackable(GenerateType.CircularReference)]
    public partial class Container
    {
        [MemoryPackOrder(0)]
        public ICollection<Item> Items { get; set; } = [];
    }

    [MemoryPackable(GenerateType.CircularReference)]
    public partial class Item
    {
        [MemoryPackOrder(0)]
        public Item? Next { get; set; }
    }
}

This is a very simple class structure but not so simple for the serializer.

Let's look at how the data looks like in the memory:

What path does the serializer take? Well, naturally it would want to take the following path(which MemoryPack is, in fact, following):

If we look at the diagram - each arrow is a method call, and therefore the serializer digs into the object eating through the precious call stack and eventually exceeding the limit.

Suggestions part. Do not read further if you already have a solution in your head.

"So, what is the better solution?" you might ask.
The current serialization algorithm is a depth-first. The better approach might be breadth-first algorithm. In the example above it would first go through all of the items of the container object and only then it would go inside each of those items.

Another solution might be adding a depth limit so it switches to a different branch of the object allowing it to possibly recover from overflowing the stack - it would work perfectly in this simple example that i have shown and even in much more complex scenarios. The only problem it poses is that with current serialization algorithm it would not really backtrack and fix those missing references that were not serialized correctly.

Of course this is an oversimplification of the problem, so it will need a bit more deep thinking than i did, but i believe that this is still a fixable issue.

[Darkar25]

I believe #149 is the same issue as mine, but it was closed and never elaborated on any further.

[Darkar25]

As a workaround i was able to cut some circular referencing paths using the MemoryPackIgnore attribute. This was possible in my case because i have a special handler layer that is able to restore missing references in the model after deserializing it. But for other people this might not be applicable.