Prevent stack overflow while crawling inside objects via reflection in c#

Question

I have this method called MatchNodes: IEnumerable<bool> MatchNodes<T>(T n1, T n2)

Which basically gets every property and field from both T objects (via reflection, and not including properties/fields from base classes) and compares them, returning the result as a IEnumerable of bools.

When it finds a primitive type or string, if just returns the == between them.

When it finds a type derived from a collection, it iterates each member and calls MatchNodes for each of them (ouch).

When it finds any other type, it calls MatchNodes for each property/field.

My solution is obviously asking for a stack overflow exception, but I don't have a clue on how make it better, because I have no idea how deep the objects will go.

Code (try not to cry please, it's ugly as hell):

public static IEnumerable<bool> MatchNodes<T>(T n1, T n2)
    {
        Func<PropertyInfo, bool> func= null;

        if (typeof(T) == typeof(String))
        {
            String str1 = n1 as String;
            String str2 = n2 as String;
            func = new Func<PropertyInfo, bool>((property) => str1 == str2);
        }
        else if (typeof(System.Collections.IEnumerable).IsAssignableFrom(typeof(T)))
        {
            System.Collections.IEnumerable e1 = (System.Collections.IEnumerable)n1;
            System.Collections.IEnumerable e2 = (System.Collections.IEnumerable)n2;
            func = new Func<PropertyInfo, bool>((property) =>
            {
                foreach (var v1 in e1)
                {
                    if (e2.GetEnumerator().MoveNext())
                    {
                        var v2 = e2.GetEnumerator().Current;
                        if (((IEnumerable<bool>)MatchNodes(v1, v2)).All(b => b == true))
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
                if (e2.GetEnumerator().MoveNext())
                {
                    return false;
                }
                else return true;
            });
        }
        else if (typeof(T).IsPrimitive || typeof(T) == typeof(Decimal))
        {
            func = new Func<PropertyInfo, bool>((property) => property.GetValue(n1, null) == property.GetValue(n2, null)); 
        }
        else
        {
            func = new Func<PropertyInfo, bool>((property) =>
                    ((IEnumerable<bool>)MatchNodes(property.GetValue(n1, null),
                    property.GetValue(n2, null))).All(b => b == true));
        }

        foreach (PropertyInfo property in typeof(T).GetProperties().Where((property) => property.DeclaringType == typeof(T)))
        {
            bool result =func(property);
            yield return result;
        }

    }

What I'm looking at is a way to crawl into the objects without calling my method recursively.

EDIT

To clarify, example:

public class Class1 : RandomClassWithMoreProperties{
    public string Str1{get;set;}
    public int Int1{get;set;}
}

public class Class2{
    public List<Class1> MyClassProp1 {get;set;}
    public Class1 MyClassProp2 {get;set;}
    public string MyStr {get;set;}
}

MatchNodes(n1,n2) where n1.GetType() and n2.GetType() are Class2 would return true if:

Every Class1 object inside MyClassProp1 has the same Str1,Int1 for both objects
MyClassProp2 has the same Str1,Int1 for both objects
MyStr is equal for both objects

And I won't compare any properties from RandomClassWithMoreProperties.

Without rewriting the method myself, any method that can be written as recursive can also be written as a loop. The difficulty of which can be non-trivial, but it's a known CS fundamental and one I've employed myself. — user978122
– user978122, Commented Dec 22, 2011 at 18:17
Even as a loop, you would still need to watch out for cycles in the object graph. Also, your recursive calls use object as the T generic parameter - this is probably not what you want since you check that DeclaringType == typeof(T). What exactly are you trying to do? There is probably a better way. — default.kramer
– default.kramer, Commented Dec 22, 2011 at 18:28
Also, look what happens if you give it two strings: foreach property in typeof(String).GetProperties() it's going to call func, which is str1 == str2. This is probably not what you meant to do. — default.kramer
– default.kramer, Commented Dec 22, 2011 at 18:33
@default.kramer Yeah, T ends up being always of type object, unless I cast the objects to dynamic before calling MatchNodes. I have no clue of what problem casting to dynamic could cause, though. — Conrad Clark
– Conrad Clark, Commented Dec 22, 2011 at 18:39
The problem you need to solve is avoiding an infinite loop, not avoiding a stack overflow (the stack overflow is just a symptom of the disease). If any object has a property which is a class that has a parent property pointing back to it, you've got an infinite loop. That's just the simplest form of course. You could have a much less obvious cycle involving more than two objects. You're going to have to store a table of objects you've already started processing so you can avoid these loops. — Igby Largeman
– Igby Largeman, Commented Dec 22, 2011 at 18:56

ChrisWue · Accepted Answer · 2011-12-23 19:12:57Z

1

You can use a stack or queue to store the properties you want to compare. It goes along these lines:

 var stack = new Stack<Tuple<object, object>>();

 // prime the stack
 foreach (var prop in n1.GetType().GetProperties())
 {
     stack.Push(Tuple.Create(prop.GetValue(n1), prop.GetValue(n2));
 }

 while (stack.Count > 0)
 {
     var current = stack.Pop();

     // if current is promitive: compare
     // if current is enumerable: push all elements as Tuples on the stack
     // else: push all properties as tuples on the stack
 }

If you use a Queue instead of a Stack you get a BFS instead of a DFS. Also you should probably keep track of already visited nodes in a HashSet. You also might want to add a check to make sure the types of n1 and n2 are the same.

edited Dec 23, 2011 at 19:12

answered Dec 22, 2011 at 19:08

ChrisWue

19.1k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Conrad Clark Over a year ago

Thanks, it solves my problem. I'll accept as answer, but I think I overcomplicated my solution. I may just compare each object manually since I'll only have to do it for 20~30 classes.

Chris Shain · Accepted Answer · 2011-12-22 18:55:18Z

0

A good approach here is to keep a breadcrumb trail of objects that you've touched, and passing that forward as you delve deeper. For each new object, check to see whether it is in the graph of objects that you have already seen, and if it is, short circuit and bail out (you've already seen that node). A stack is probably appropriate.

You are not likely to get stack overflows by comparing an acyclic object graph- it's when you end up with loops that things blow up.

answered Dec 22, 2011 at 18:55

Chris Shain

51.5k7 gold badges95 silver badges124 bronze badges

Comments

Daniel Mošmondor · Accepted Answer · 2011-12-22 19:14:16Z

0

Just keep track of the objects you already visited, in a List<object> for example (or Set<> or anything like that)...

Also, any recursion can be un-recursed using the stack that you'll control manually.

edited Dec 22, 2011 at 19:14

answered Dec 22, 2011 at 19:00

Daniel Mošmondor

20k12 gold badges61 silver badges104 bronze badges

Collectives™ on Stack Overflow

Prevent stack overflow while crawling inside objects via reflection in c#

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related