Parsing NAV Object Dependencies – Part 2

Introduction

I recently had the privilege of being interviewed by Linda Rosencrance from MSDynamicsWorld.com about how my employer has adopted Dynamics NAV and my experiences with customization and development. The topic of source control came up, which I thought would make an interesting two-part series for my blog. My coworker has already started a great series on our custom source control solution, so rather than rehash his excellent overview, I want to focus specifically on one of the challenges we faced: parsing and sorting nav object dependencies. This series will cover the following:

1. Part 1 – Parsing NAV object dependencies
2. Part 2 – Sorting NAV object dependencies (this post)

Sorting NAV Object Dependencies

In part 1 of this series, we covered parsing NAV objects in text file format in order to get a list of their dependencies. If you haven’t gone through that part yet, I suggest reading it first.

Once we have a list of object dependencies, the next step is to sort them to ensure they are compiled in the proper order (and compiled only once, since some objects may have been imported multiple times from multiple changesets; we only need to compile the final version of the object). We will cover a dependency sorting strategy in this post.

Dependency Graph

Before we can get into the actual sorting details, we first need something to sort. While we did cover how to parse out NAV object dependencies in the previous post, we glossed over the dependency graph. This is what actually gets sorted.

I will try to show the main classes required to link everything together, but there may be some that I leave out for brevity (basically other noise related to our tool that is more of a distraction). I’m hoping this will still be detailed enough to give you the gist of everything.

NAV Object Nodes

In order to build the dependency graph, we need a Node class that represents each NAV object and a Collection of Nodes that represent all of the NAV objects that the current object depends on. I believe this is equivalent to a directed acyclic graph (DAG), where the Node class represents vertices and the Collection of Nodes that the NAV object depends on is the directed edges connecting the vertices. Caveat: I am not an expert on graph theory, so please don’t chase me down with a torch and pitchfork if I’m incorrect on my terminology etc. (but please do let me know in the comments!).

One issue with this approach, is that a table object sometimes makes a self reference (I suppose other objects could also make a reference to themselves via a variable declaration, but tables seem to be the most common offenders). This violates the rules of directed acyclic graphs where

…it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.^[1]

This is something to keep in mind in the Node implementation, which I shall now show (we’re going to call it a NavObjectNode):

Things to note:

• We store the object type and id (both together are required to form a unique object). They are stored as integers, but some of the code I have omitted contains enumerations and conversion logic between the two.
• The composition list (accessed publicly via the ComposedOf property) is a collection of objects that the current object has a dependency on (In hindsight, I supposed we could have called the property DependsOn).
• When we add a NAV object to our composition list, we do two things:
  1. Ensure we avoid adding a self-reference
  2. We only add an object to the list if it hasn’t already been added (avoids compiling the same object multiple times if it is referenced multiple times in our current object).

Object Dependency Manager

The other important piece to our dependency graph is the ObjectDependencyManager class. The purpose of this class is to keep the list of NavObjectNode instances (list of objects to compile) and to expose the sorting function (i.e. it manages the object dependency references). The class looks like this:

The things to note:

• You can access NAV objects via the GetNavObject property (asking via type and id).
• You can add objects to the list of objects to compile.
• You can ask for the sorted compile list, which is delegated to an extension method we’ll cover shortly.

Putting It Together So Far

I’ll try to give some context here combining what we learned in part 1, with what we have covered so far in part 2:

1. The entire process starts when we iterate over a list of files to import from our list of changesets (each file is an object).
2. Import the files and build a list of those objects.
3. Iterate that list and parse each file.
4. As we parse the file we get the current object from the header (via the ObjectHeaderState parser class).
5. The ObjectHeaderState has a reference to the Parser (the main context or driver class for the parser state machine from part 1). It sets the CurrentObject property (which is a NavObjectNode) of the Parser class.
6. The Parser class has a reference to our ObjectDependencyManager class. In the setter for the CurrentObject property, it calls the AddNavObjectToCompile method, which adds the object to the list of objects to compile stored in the object dependency manager.
7. As the file continues to be parsed, any variable declarations (references to other objects) are checked for existence in the import list. If that object is found, the current object has the referenced object added to its ComposedOf list via the AddCompositionNavObject method (if we haven’t already added it from a previous reference in the current object).
8. Once all files are completed, we have a list of NavObjectNodes (some of which contain other nodes). This is our dependency graph, which then needs to be sorted.

The Sort Algorithm

To the best of my knowledge, one of the best ways to sort a dependency graph is via a Topological Sort algorithm. It is probably easiest to show the implementation first. NOTE: If you’re not very familiar with C#, you may need to do some research on generics, delegates and lamba expressions, but I’ll try to explain things briefly:

If we look at the Sort algorithm signature, it takes an enumerable collection of any object type (in our case it will be list of NavObjectNodes), a Func delegate that returns an enumerable collection of the same type of object (in our case the list of NavObjectNodes that the current object depends on; the ComposedOf property) and it returns a new enumerable collection of the same type of object (our sorted list of NavObjectNodes).

So how does the sort actually work? It is fairly simple actually.

• Iterate the collection of unsorted objects.
• For each object, visit it.
• If the object hasn’t been visited, mark it as visited (add it to the visited Hashset)
• If the object has any references to other objects, recursively visit those objects (mark as visited etc.).
• Once you reach the deepest level of recursion for the current object and its references, begin adding those items to the sorted list (it will add them from deepest first, then unwind back up).
• Any objects that were already added to the sorted list previously will not be added again later (or have its references visited), because those objects that have already been visited will be skipped.

Sort Example

I’ll give an example of Sort and Visit to try to make it clearer. First we need a dependency graph. We’ll say the following items were in the list of imported objects.

Any objects inside of other objects are references (the outer object depends on the inner object). Only those objects that are included in the list of imported objects (which means they need to be compiled) are listed. In other words, if Codeunit 50000 also referenced Table 27, but Table 27 was not imported, it is not listed and does not require sorting and compiling.

When sorting these objects, the final order does not matter so much. What I mean is, it doesn’t matter if codeunit 90 is sorted before or after codeunit 50030, because neither of these objects are referencing another object on the list. However, we do require objects that are referenced by other objects on the list to be compiled first.

Based on our dependencies, the following conditions must be met:

• Table 50010 is compiled before Codeunit 50000
• Table 50010 is compiled before Page 50005
• Codeunit 90 is compiled before Codeunit 50000
• Codeunit 50000 is compiled before Page 50005
• Codeunit 50030 is compiled before Page 50020.

This is our initial unsorted list:

1. Codeunit 50000
2. Table 50010
3. Page 50005
4. Codeunit 90
5. Page 50020
6. Codeunit 50030

Stepping through the sort algorithm looks like so:

1. Sort our list, beginning with Codeunit 50000.
   1. Visit Codeunit 50000.
   2. Add Codeunit 50000 to the visited collection.
   3. Visit Codeunit 50000 dependencies.
      1. Visit Table 50010.
      2. Add Table 50010 to the visited collection.
      3. Table 50010 has no dependencies.
      4. Add Table 50010 to the sorted list (1st sorted element).
      5. Visit Codeunit 90.
      6. Add Codeunit 90 to the visited collection.
      7. Codeunit 90 has no dependencies.
      8. Add Codeunit 90 to the sorted list (2nd sorted element).
   4. Codeunit 50000 has no more dependencies.
   5. Add Codeunit 50000 to the sorted list (3rd sorted element).
2. Next object on the list in the Sort function is Table 50010.
   1. Visit Table 50010.
   2. Table 50010 has already been visited.
3. Next object on the list in the Sort function is Page 50005.
   1. Visit Page 50005.
   2. Add Page 50005 to the visited collection.
   3. Visit Page 50005 dependencies.
      1. Visit Codeunit 50000.
      2. Codeunit 50000 has already been visited.
      3. Visit Table 50010.
      4. Table 50010 has already been visited.
   4. Page 50005 has no more dependencies.
   5. Add Page 50005 to the sorted list (4th sorted element).
4. Next object on the list in the Sort function is Codeunit 90.
   1. Visit Codeunit 90.
   2. Codeunit 90 has already been visited.
5. Next object on the list in the Sort function is Page 50020.
   1. Visit Page 50020.
   2. Add Page 50020 to the visited collection.
   3. Visit Page 50020 dependencies.
      1. Visit Codeunit 50030.
      2. Add Codeunit 50030 to the visited collection.
      3. Codeunit 50030 has no dependencies.
      4. Add Codeunit 50030 to the sorted list (5th sorted element).
   4. Page 50020 has no more dependencies.
   5. Add Page 50020 to the sorted list (6th sorted element).
6. Next object on the list in the Sort function is Codeunit 50030.
   1. Visit Codeunit 50030.
   2. Codeunit 50030 has already been visited.
7. No more objects, return the sorted list.

Looking at our final sort order, we end up with:

1. Table 50010
2. Codeunit 90
3. Codeunit 50000
4. Page 50005
5. Codeunit 50030
6. Page 50020

To save your from scrolling up, here is the sorting requirements again:

• Table 50010 is compiled before Codeunit 50000 (yes)
• Table 50010 is compiled before Page 50005 (yes)
• Codeunit 90 is compiled before Codeunit 50000 (yes)
• Codeunit 50000 is compiled before Page 50005 (yes)
• Codeunit 50030 is compiled before Page 50020 (yes)

Success!

And that brings this two-part series on parsing and sorting NAV object dependencies to conclusion. Hopefully you found the information interesting and useful. There are ways in which to expand this functionality. I do have some ideas and plan to do just that in the near future. I will blog about those as I explore them.

Citations

1. ^Directed acyclic graph. n.d. In Wikipedia. Retrieved May 27, 2015, from http://en.wikipedia.org/wiki/Directed_acyclic_graph