Detecting Recursion - JSON.Net Stack Overflow

December 05, 2014

Trying to save the game class of a game that I’m working on, I got a Stack Overflow error. I’m using MVVMCross, and my code looked like this:



        public void Save()
        {
            var jsonConv = Mvx.Resolve<IMvxJsonConverter>();
            string text = jsonConv.SerializeObject(this);
            FileHelper.SaveGameFile(text);
        }

The problem was that I got this error:

An unhandled exception of type ‘System.StackOverflowException’ occurred in mscorlib.dll

I had a pretty good idea why. My game features a large population of “people”. Some of these people relate to each other; for example, they are parents, children, employers, etc. My guess was that I’d somehow messed up the creation routine and ended up with a recursive reference. (As it happened, far from messing it up, I hadn’t considered that a spouse relationship is recursive by definition!)

The Problem

The problem was that I had a starting population of 10,000 people. There are other ways to solve this: representing the reference between the classes as some kind of index, debugging the creation code, etc… However, I wanted to see if I could write a program to detect this.

My test program looks like this:



    class MyData
    {
        public MyData recursiveRef { get; set; }
        public string test { get;set; }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<MyData> data = new List<MyData>()
            {
                new MyData() {recursiveRef = null, test="non-recursive" },
                new MyData() {recursiveRef = null, test="recursive ref 1" },
                new MyData() {recursiveRef = null, test="recursive ref 2" },
                new MyData() {recursiveRef = null, test="recursive ref 3" },
                new MyData() {recursiveRef = null, test="recursive ref back to 1" }
            };
            data[1].recursiveRef = data[2];
            data[2].recursiveRef = data[3];
            data[3].recursiveRef = data[4];
            data[4].recursiveRef = data[1];

            SerialiseData(data);

            Console.ReadLine();
        }

        private static void SerialiseData(List<MyData> data)
        {
            JsonSerializerSettings settings = new JsonSerializerSettings()
            {
                ReferenceLoopHandling = Newtonsoft.Json.ReferenceLoopHandling.Serialize,
                DateFormatHandling = DateFormatHandling.IsoDateFormat,
            };

            var ser = JsonConvert.SerializeObject(data, Formatting.None, settings);
            Console.Write(ser);
        }

Quickly running this will error with a stack overflow (to clarify, slowly running it will result in the same error!).

Detection Routine

Here’s the functions that I wrote to detect recursion:




        /// Itterate the list and call method CheckElement to analyse each element
        private static bool DetectRecursion<T>(IEnumerable<T> data)
        {
            Type typeT = typeof(T);

            foreach (T element in data)
            {
                if (CheckElement<T>(typeT, element, typeT, element))
                {
                    Console.WriteLine("Recursion found - exiting");
                    Console.ReadLine();
                    return true;
                }
            }

            return false;
        }

        private static List<object> recursionChain;

        /// Method recursively traverses the object to determine if there are any recursove references
        private static bool CheckElement<T>(Type baseType, T baseElement, Type checkType, object checkElement)
        {
            PropertyInfo[] piArr = checkType.GetProperties();
            foreach (PropertyInfo pi in piArr)
            {
                Console.WriteLine("Checking {0}, type {1}", pi.Name, pi.PropertyType);
                if (pi.PropertyType != baseType)
                    continue;

                var val = pi.GetValue(checkElement);
                if (val == null) continue;

                Console.WriteLine("Value for {0} is {1}", pi.Name, val.ToString());

                Type piType = val.GetType();

                if (piType == baseType && val.Equals(baseElement))
                {
                    return true;
                }

                if (CheckRecursionChain(val, piType)) return true;

                if (CheckElement<T>(baseType, baseElement, piType, val))
                {
                    Console.WriteLine("Successfully found recursive element {0}, {1}", piType.ToString(), val.ToString());
                    return true;
                }
            }

            return false;
        }

        /// Check the static recursion chain for a match
        private static bool CheckRecursionChain(object val, Type piType)
        {            
            if (Program.recursionChain != null && Program.recursionChain.Contains(val))
            {
                Console.WriteLine("Successfully found recursive element {0}, {1}", piType.ToString(), val.ToString());
                return true;
            }

            if (Program.recursionChain == null)
                Program.recursionChain = new List<object>();

            Program.recursionChain.Add(val);
            
            return false;
        }

This is, admittedly, not a simple or short piece of code; having said that, it doesn’t do anything complex, once you’re happy with the reflection, the rest is just a recursive tree.

To use this, simply call `DetectRecursion` in the above test program before calling serialize (or instead of).



...
DetectRecursion(data);

//SerialiseData(data);

...