Traversing graphs with DeepTraverser

Objects can form complicated graphs. To understand graphs, you need to traverse them.

Indeed, this need is often observed in traversal methods directly written inside the domain classes. For example, to get all subclasses of a given class we have Behavior>>#allSubclassesDo: allSubclassesDo: aBlock "Evaluate the argument, aBlock, for each of the receiver's subclasses." self subclassesDo: [:cl | aBlock value: cl. cl allSubclassesDo: aBlock] . For traversing the children of an element we have BlElement>>#allChildrenDepthFirstDo: allChildrenDepthFirstDo: aBlock self childrenDo: [ :each | each allChildrenDepthFirstDo: aBlock ]. self childrenDo: aBlock . These are great, but what do we do when we don't have these?

Enter DeepTraverser, a scriptable traversal engine.

For example, to get all subclasses of Collection Object subclass: #Collection instanceVariableNames: '' classVariableNames: '' package: 'Collections-Abstract-Base' , we can do:

all := OrderedCollection new.
Collection 
	deep: [:class | class subclasses ] 
	do: [ :class | all add: class ].
all
  

The Object>>#deep:do: deep: aTraversalBlock do: anObjectActionBlock "traverses all objects starting with the receiver using aTraversalBlock, and for each triggers anObjectActionBlock. For example: Number deep: #subclasses do: [:each | Transcript show: each; cr]" (DeepTraverserWithoutEdges new onNodeTraverse: aTraversalBlock; onNodeAction: anObjectActionBlock; on: self startWithout: self; yourself) run is a generic traversal that can be applied to any object and specifices two parts:

The way to go from one object to the next objects in the graph, and

What to do for each traversed object.

Example: getting the object graph

Say we have a Bloc element:

element := BlElement new
  

What objects is it made of? To find this out, we can traverse all objects reachable from this object that are part of packages named Bloc and collect them in a collection. For this we use Object>>#withDeepCollect: withDeepCollect: aTraversalBlock "traverses all objects starting with and including the receiver using aTraversalBlock, and returns an OrderedCollection containing each traversed object. For example: Number withDeepCollect: #subclasses" | result | result := OrderedCollection new. self withDeep: aTraversalBlock do: [ :each | result add: each ]. ^ result :

BlElement new
	withDeepCollect: [ :each | 
		each class instVarNames 
			collect: [:iv | each instVarNamed: iv]
			thenSelect: [:object | object class package name beginsWith: 'Bloc' ] ]
  

Having the list is nice. But, how are the objects composed? A graph would be better. For this we need both to get the nodes and the edges using yet another traversal Object>>#withDeep:do:relationDo: withDeep: aTraversalBlock do: anObjectActionBlock relationDo: aRelationBlock "traverses all objects starting with and including the receiver using aTraversalBlock, and for each triggers anObjectActionBlock, and for each relation between two traversed objects triggers aRelationBlock. For example: Number withDeep: #subclasses do: [:each | Transcript show: each; cr ] relationDo: [ :from :to | Transcript show: from; show: ' <-- '; show: to; cr ]" (DeepTraverser new onNodeTraverse: aTraversalBlock; onNodeAction: anObjectActionBlock; onEdgeAction: aRelationBlock; on: self startWith: self; yourself) run . To build the actual graph we use Mondrian:

m := GtMondrian new.
BlElement new
	withDeep: [ :each | 
		each class instVarNames
			collect: [ :iv | each instVarNamed: iv ]
			thenSelect: [ :object | object class package name beginsWith: 'Bloc' ] ]
	do: [ :each | m nodes with: {each} ]
	relationDo: [ :from :to | m edges connectAssociations: {from -> to} ].
m layout horizontalDominanceTree.
m
  

Of course, once we have the basic graph in place, we can extend the visualization with more embellishments:

m := GtMondrian new.
BlElement new
	withDeep: [ :each | 
		each class instVarNames
			collect: [ :iv | each instVarNamed: iv ]
			thenSelect: [ :object | object class package name beginsWith: 'Bloc' ] ]
	do: [ :each | 
		m nodes
			stencil: [ :x | 
				BrVerticalPane new
					fitContent;
					addChild: (BrLabel new
							text: x class name;
							aptitude: (BrGlamorousLabelAptitude new
									foreground: Color gray;
									fontSize: 10));
					addChild: (BrLabel new
							text: x gtDisplayString;
							aptitude: BrGlamorousLabelAptitude new) ];
			with: {each} ]
	relationDo: [ :from :to | 
		m edges
			fromRightCenter;
			toLeftCenter;
			stencil: [ :x | 
				BlParabollaArcElement new
					zIndex: 0;
					curvatureFraction: 0.3;
					border: (BlBorder paint: (Color gray alpha: 0.2) width: 2);
					toHead: (BlArrowheadSimpleArrow new
							border: (BlBorder builder
									paint: (Color gray alpha: 0.2);
									width: 4;
									build)) ];
			connectAssociations: {from -> to} ].
m layout horizontalDominanceTree
	levelDistance: 50;
	nodeDistance: 20.
m
  

Traversal API

The main class is DeepTraverser DeepTraverserWithoutEdges subclass: #DeepTraverser instanceVariableNames: 'onEdgeAction edgesToAction' classVariableNames: '' package: 'DeepTraverser' . It can be configured in several ways. But the more convenient API is found directly Object ProtoObject subclass: #Object instanceVariableNames: '' classVariableNames: 'DependentsFields' package: 'Kernel-Objects' . Look for methods starting with deep:.