The Apex Describe API can be used to get information about various components of the Force.com platform. Prior to the Summer ’14 release, there were governor limits that limited the number of describe calls that could be made in one transaction context. With the Summer ’14 release, all limits on describe calls have been removed.
Use Cases
One common use case for describe calls is to check for field level security in ISV code to comply with the requirements necessary to pass the security review. Another use case is to get information dynamically based on some sort of user input/config (e.g., get field sets dynamically). One more use case is to provide a useful view of the describe information to users (e.g., ERD, etc.).
In this article I detail code for a Visualforce page that makes use of the unlimited describe calls to create a directed graph of sObject nodes, to find paths between nodes, and to represent all of the paths as a directed graph drawn on a canvas element. All code is available on GitHub.
Finished Page
The Graph
The graph is represented by a Graph class which internally represents the graph as an adjacency list of Node objects. Each Node is a map key that is mapped to its list of adjacent Nodes. A directed edge from a Node ‘a’ to Node ‘b’ is represented by the existence of a value of ‘b’ in the list of adjacent Nodes for ‘a’. For simplicity’s sake there is no Edge class, because there was no need to store any information at the Edge level for this use case; however, the code could be easily altered to accommodate one.
The graph is built as part of the construction of the Controller. The graph represents all child to parent relationships. That is, each edge represents a child object with a lookup or master-detail relationship to a parent.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
for (Schema.SObjectType objType : Schema.getGlobalDescribe().values()) { Schema.DescribeSObjectResult objDesc = objType.getDescribe(); Graph.Node parentNode = new Graph.Node(objDesc.getName()); theGraph.addNode(parentNode); for (Schema.ChildRelationship child : objDesc.getChildRelationShips()) { Schema.DescribeSObjectResult childDesc = child.getChildSObject().getDescribe(); Graph.Node childNode = new Graph.Node(childDesc.getName()); theGraph.addEdge(childNode, parentNode); } } |
Each sObject is processed by adding it to the graph and adding any lookup or master-detail relationships to it as edges from the child to it (the parent). The code could be altered to only process a subset of sObjects based on filtering. For example, it could be altered to exclude Feed and History objects or could be altered to only include specified objects.
Finding Paths
Once the graph has been constructed the page is displayed and allows the user to select a source and a destination sObject for which to find all paths. Once the user clicks the ‘Get Paths’ button the controller’s action method is called and the paths and directed graph section of the page is reRendered.
The action method generates all paths from the source to the destination and then formats them in the expected JSON format.
1 2 3 4 5 6 7 8 9 |
public PageReference generatePaths() { GraphSearcher searcher = new GraphSearcher(theGraph); paths = searcher.findPaths( new Graph.Node(sourceNodeStr), new Graph.Node(destNodeStr) ); GraphFormatter formatter = new GraphFormatter(theGraph); json = formatter.getJson(paths); return null; } |
The path finding is implemented as a depth first search which uses recursion. It could be altered to use a non-recursive, stack based algorithm instead.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public List findPaths(Graph.Node sourceNode, Graph.Node destNode) { this.destNode = destNode; this.paths = new List(); GraphPath currentPath = new GraphPath(); search(sourceNode, currentPath); return paths; } private void search(Graph.Node currentNode, GraphPath currentPath) { currentPath.add(currentNode); Set adjacentNodes = g.getAdjacentNodes(currentNode); // Check if the adjNode is the destNode. // If so, a path has been found for (Graph.Node adjNode : adjacentNodes) { if (adjNode.equals(destNode)) { currentPath.add(adjNode); paths.add(new GraphPath(currentPath)); // remove the destGraph.Node in case there is another // way to get to the destGraph.Node currentPath.removeLast(); break; } } // Search the unvisited adjacent nodes for (Graph.Node adjNode : adjacentNodes) { if (!currentPath.contains(adjNode) && !adjNode.equals(destNode)) { search(adjNode, currentPath); currentPath.removeLast(); } } } |
The search first checks to see if a path has been found with the current node’s adjacent nodes (i.e., is the destination adjacent to the current node). If it has it is added to the result list of GraphPaths. It then processes all adjacent nodes (the recursive step).
Once all paths have been found they are then passed to a formatter that generates JSON for the page to draw a directed graph on a canvas element, using the springy.js framework.
The Page
Once all of the paths have been generated they are rendered on the page as a list and as a directed graph.
1 2 3 4 5 6 7 8 9 10 |
<ol> <apex:repeat value="{!paths}" var="path"> <li> ({!path.length}) <apex:repeat value="{!path.nodes}" var="node"> {!node.value} </apex:repeat> </li> </apex:repeat> </ol> |
The graph is drawn using springy.js which has a method to create a graph from JSON.
1 2 3 4 5 6 7 8 9 10 11 12 |
<script> graph = new Springy.Graph(); graph.loadJSON({!json}); var layout = new Springy.Graph(); jQuery('#container').empty(); jQuery('#container').append('<canvas id="objectGraph" width="800" height="600"></canvas>'); var springy = window.springy = jQuery('#objectGraph').springy({ graph: graph }); </script> |
Analysis
The algorithm performed fairly well. In some non-structured testing, I was able to generate lists with 400+ paths without issue. The only downside was that the springy.js graph became a bit unwieldy with many nodes. This could be addressed by using a different type of node (e.g., image node with small images), by using a different framework such as d3.js, or by performing some sort of scaling.
Quick Note on Caching
A common pattern with describe calls prior to Summer ’14 was to cache their results to avoid the limits. You may be wondering if your code still needs to cache for performance reasons. The answer is no, caching is not necessary. See this article by Dan Appleman that details benchmarking he did to show that caching is unnecessary.
Conclusion
The removal of the describe limits in Summer ’14 has given developers the ability to create applications that would have previously been not possible (or at least less straightforward). This article described one such application that gives users the ability to map paths between sObjects in their org. See the Apex Developer’s Guide’s documentation on the Schema namespace and on Understanding Apex Describe Information.
All code is available on GitHub.
Thanks 🙂