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); ...