Class tree traversal

Introduction

In the past few years, many technologies tend to use classes to describe data elements to simplify data structure building and maintaining. In such frameworks, the user provides his own classes in a clear declarative way, and expects the framework to build, maintain and provide the necessary functionality to data objects.

A good example of such framework is Microsoft Entity Framework.

Inspired by that idea, I am trying to build a framework to store and retrieve graphics assets (textures, 3D models, fonts, etc.) on a remote server in a shared environment. The framework is abstract and gives the user the freedom to store his own classes along with the related resources; and it is up to the framework to inspect user’s classes, detect resource members and manipulate them.

The mission

We need to inspect the root class and all descendant classes recursively, looking for public properties that meet specific criteria (implementing IResource in my case) and cache the way we can access such properties from the root class. Later we can use these cached methods to retrieve resource properties for any instance of the root class.

The code

Looping through object's public properties

The following block of code shows how easily we can go through object's public properties.

var properties = propertyType.GetProperties(BindingFlags.Instance | BindingFlags.Public);
foreach (PropertyInfo property in properties)
{
    //Check each property
}

Accessing directly descendent classes

Using PropertyInfo, we can easly evaluate a descendant object from its parent object:

_getMethod = propertyInfo.GetGetMethod();
var obj = _getMethod.Invoke(parentObj, new object[] { });

In my code, I'm wrapping PropertyInfo into a new class (PropertyAccessor) which cache property’s get method, plus some other information to determine whether the property is a simple object or a list of objects

Accessing even deeper descendant classes

By chaining PropertyAccessor(s), we can define how to access properties in much deeper classes. Chaining means let each PropertyAccessor knows about the next PropertyAccessor to call while going to next deeper layer in classes tree

The following code shows a simplified version of PropertyAccessor:

public class PropertyAccessor
{
    public PropertyInfo Property { get; private set; }
    public PropertyAccessor NextAccessor { get; private set; }
    private MethodInfo _getMethod;

    public PropertyAccessor(PropertyInfo property, PropertyAccessor nextAccessor)
    {
        Property = property;
        NextAccessor = nextAccessor;
        _getMethod = Property.GetGetMethod();
    }

    public void GetObjects<T>(object parentObj, List<T> results)
    {
        var obj = _getMethod.Invoke(parentObj, new object[] { });
        if (obj is T)
        {
            results.Add((T)obj);
        }
        if (NextAccessor != null)
        {
            NextAccessor.GetObjects(obj, results);
        }
    }
}

Every group of PropertyAccessor is wrapped into a new class (TreeAccessor) which show the way through classes tree to reach a property that matchs our criteria.

The following code shows a simplified version of TreeAccessor:

public class TreeAccessor
{
    public List<PropertyAccessor> Accessors { get; set; }

    public TreeAccessor()
    {
        Accessors = new List<PropertyAccessor>();
    }

    public TreeAccessor(TreeAccessor parentTreeAccessors, PropertyAccessor propAccessor)
    {
        Accessors = new List<PropertyAccessor>(parentTreeAccessors.Accessors.Count + 1);
        Accessors.AddRange(parentTreeAccessors.Accessors);
        Accessors.Add(propAccessor);
    }

    public void GetObjects<T>(object obj, List<T> results)
    {
        if (Accessors.Count > 0)
        {
            Accessors[0].GetObjects(obj, results);
        }
    }
}

Traversing classes' tree recursively:

Traversing is done by calling a single function recursively for each property type in the following steps:

1. We simply loop through all public properties of the underlying type.
2. If property's type matchs our criteria, then store its tree accessor.
3. Send property type as a parameter to step 1.

The core functionality is represented by the class ClassTreeTraversal, and here is a simplified version of it:

public class ClassTreeTraversal
{
    private readonly Type _classType;
    private readonly Predicate<Type> _typeFilter;
    public List<TreeAccessor> MatchedAccessors { get; set; }

    public ClassTreeTraversal(Type classType, Predicate<Type> typeFilter)
    {
        _classType = classType;
        _typeFilter = typeFilter;
        MatchedAccessors = new List<TreeAccessor>();
        var rootAccessor = new TreeAccessor();
        FindMembers(rootAccessor, _classType);
    }

    private void FindMembers(TreeAccessor parentPropertyTreeAccessor, Type parentPropertyType)
    {
        var childProperties = parentPropertyType.GetProperties(BindingFlags.Instance 
            | BindingFlags.Public);
        //Loop through all public properties of the class in the current level
        foreach (var childProperty in childProperties)
        {
            //Here we can early exclude a complete branch of the tree
            //if it not likelly to contain any interesting results
            if (!childProperty.PropertyType.IsClass)
                continue;

            //Create property accessor of the child property
            var childPropertyAccessor = new PropertyAccessor(childProperty);
            //Create tree accessor of the child property
            var childPropertyTreeAccessor = new TreeAccessor(parentPropertyTreeAccessor
                , childPropertyAccessor);
            //If the property matchs our criteria, store it
            if (_typeFilter.Invoke(childProperty.PropertyType))
            {
                MatchedAccessors.Add(childPropertyTreeAccessor);
            }
            //Here, we go down to the next level in the tree to check
            //all properties of the class represented by the current property
            FindMembers(childPropertyTreeAccessor, childPropertyAccessor.Property.PropertyType);
        }
    }

    public void GetObjects<T>(object obj, List<T> results)
    {
        foreach (var accessor in MatchedAccessors)
        {
            accessor.GetObjects(obj, results);
        }
    }

    public List<T> GetObjects<T>(object obj)
    {
        var results = new List<T>();
        GetObjects(obj, results);
        return results;
    }
}

As you may notice, the criteria is provided as a Predict<Type> which is a flexible way to customize of search within the tree.

Using the code

Let's assume that we have an object of type Scene3D and we need to collect all objects that implement IResource interface found in that Scene3D class, The following code shows the minimum code required to achieve that:

var myScene = new Scene3D();
.
.
.
var classTreeTraversal = new ClassTreeTraversal(typeof(Scene3D ))
    .UsingClassFilter((type) => type.IsClass && type.GetInterfaces().Contains(typeof(IResource)))
    .Prepare();
var resources = classTreeTraversal.GetObjects<IResource>(myScene);

Another way to do it with more options:

var myScene = new Scene3D();
.
.
.
var classTreeTraversal = new ClassTreeTraversal(typeof(Scene3D ))
    .UsingClassFilter((type) => type.IsClass && type.GetInterfaces().Contains(typeof(IResource)))
    .ExcludingTypes(typeof(DownloadElementResourcesJob), typeof(Exception))
    .WithOption(ClassTreeTraversalOptions.SkipValues | ClassTreeTraversalOptions.SkipInterfaces)
    .Prepare();
var resources = classTreeTraversal.GetObjects<IResource>(myScene);

Usage Notices:

• Calling .UsingClassFilter is mandatory, at least until we have another way to locate objects in the tree (i.e. .UsingAttribute)
• calling .Prepare() is optional, but that will postpond tree traversal until .GetObjects is called for the first time.
• The full code provides a set of methods to exclude branches from the traversing process, i.e. .ExcludingTypes, SkipValue types option, SkipInterfaces option.
• Reflection is known to be slow, but the overhead of tree traversing is done once per type, so it is a good idea to save ClassTreeTraversal instance for future use for objects of the same type.
• Infinit loop might occur if the class is referenced in descendent classes (Circular Branshing). In the current version I'm avoiding this by making sure no two PropertyAccessor(s) share the same type in one sequence.

One final note, this utility class is working fine for my specific scenario, but that doesn't mean that it is bug free, any suggestion to improve this work is welcomed.

I enjoyed writing this code; I hope you'll enjoy using it as well.

Points of Interest

I'm so much involved in programing that I forgot my interests, ohh, I remembered, politics and Syrian disaster...nothing fun.

History

No history so far, stay tuned...