Objects form complicated graphs. Understanding complicated graphs requires a broader perspective on these graphs. Yet, developers are most often exposed to only one node at a time, and there are limited tools available to navigating and slicing these graphs.
To understand graphs, you need to traverse them. 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 Object>>#allSubclasses
. The current implementation is less readable because it does not use recursion, but a possible implementation would look like:
Object>>allSubclasses | all | all := OrderedCollection new. self allSubclassesDo: [:each | all add: each ]. ^ all
Object>>allSubclassesDo: aBlock self subclasses do: [:each | aBlock value: each. each allSubclassesDo: aBlock ]
This method has two components:
#subclasses
to each traversed object, andInteresting enough, in the Moose image, we have four allSubclasses
methods in different hierarchies, and all of them essentially work in the same way only with different types of objects.
Traversing structures is a general pattern and it can be seen in other occasions as well. For example:
Morph>>allMorphsDo: aBlock submorphs do: [:m | m allMorphsDo: aBlock]. aBlock value: self
Hardcoding the traversal inside the code is a possibility but it requires tedious construction of the traversal code. A different way of approaching this problem is to model a generic traversal that can be parameterized. This idea was coined by Lieberherr etal (see Traversals of Object Structures: Specification and Efficient Implementation). If we take this way, the solution consists in modeling a traversal as a first class object.
DeepTraverser== is a small package that provides this solution. Using ==DeepTraverser== finding all subclasses of Object requires a simple instruction:
Object deepCollect: #subclasses
How does this work?
The code above starts at Object
and traverses all objects retrieved by sending #subclasses
to each traversed object. The implementation is available by default in the Moose image and it can be loaded in a fresh Pharo 3.0 image by executing:
Gofer new url: 'http://www.smalltalkhub.com/mc/Moose/DeepTraverser/main'; package: ‘ConfigurationOfDeepTraverser’; load. (Smalltalk globals at: #ConfigurationOfDeepTraverser) loadDevelopment.
The main class is the DeepTraverser
and it has three responsibilities:
Traversing objects is delegated to a DeepTraversal
, and the action triggering is delegated to DeepActionStrategy
.
To provide a more concrete idea, here is an example that traverses the class hierarchy starting with Number
and displays on the transcript each class and each inheritance relationship. The example shows how to create a full instance of a DeepTraverser
and how to trigger it on an input object:
traversal := DeepCustomTraversal new traversalBlock: [ :each | each subclasses ]. action := DeepCustomActionStrategy new objectAction: [ :each | Transcript show: each ; cr ]; relationAction: [ :from :to | Transcript show: from; show: ‘ <-- '; show: to; cr ]. DeepTraverser new traversal: traversal; action: action; traverse: Number
To make the API more fluent, the implementation comes with several Object
extensions. The above snippet is equivalent to saying:
Number deep: #subclasses do: [ :each | Transcript show: each ; cr ] relationDo: [ :from :to | Transcript show: from; show: ' <-- '; show: to; cr ]
The do:
block is triggered on every traversed object, while the relationDo:
block is triggered on every relation specified by the traversal between two traversed objects. In our case, the transcript will print every subclass of Number
and every inheritance relationship between these classes.
The examples above referred to trees of objects. What happens when we start dealing with graphs that contain cycles?
The DeepTraverser
can traverse any kind of graphs due to a simple cycle detection in the traversal algorithm (this solution was inspired by a first implementation by Mariano Martinez Peck).
For example, PetitParser parsers can potentially form cyclic graphs. For example, if we want to draw a graph of the PPSmalltalkGrammar
, we can easily map the traversal to a Roassal visualization (this code is executable in a Moose image):
view := ROMondrianViewBuilder new. PPSmalltalkGrammar new deep: [:each | each children ] do: [ :each | view node: each ] relationDo: [ :from :to | view edge: from->to from: from to: to ]. view forceBasedLayout. view open
There are several utility methods in Object that come with the existing implementation:
deep:collect:
deep:collect:as:
deep:do:
deep:do:relationDo:
deep:flatCollect:
deep:flatCollect:as:
deepCollect:
deepCollectAsSet:
withDeep:do:
withDeep:do:relationDo:
Perhaps having all these methods in Object can be seen as expensive given that all subclasses inherit them. But, traversing objects is a recurring requirement. On the one hand, we have all existing hardcoded traversals that essentially implement the same thing over and over again. On the other hand, when traversals become directly available all the time, you can craft advanced analyses during inspection time more cheaply. And this is at the very heart of humane assessment.