Since the Behavior of the passenger can be described independently of how the traversal is performed, this allows us to write an implementation for it that will work with *any* Traversal we can think of. Therefore, let’s create our first reference finder class: `PathTracer`.
Since we have the class `PathTracer` as the first brush stroke on our canvas, we can easily think of the following class message:
PathTracer class>>pathsTo: anObject using: aStreamClass ^self new pathsTo: anObject using: aStreamClass
Now let’s consider how we could implement the instance side message sent above. Since it seems that the newly created instance will have to remember some objects by name, we must give some consideration to what instance names it will need to do so. As a passenger, the path tracer should know what shop it is looking for, which we will refer to as its `target` object.
And since we are talking about things the passenger needs in order to perform its duties, it should have some way to remember all the places it has visited, which we will refer to as its `storage`. So, at first, we could provide the following implementation for `pathsTo:using:`.
PathTracer>>pathsTo: anObject using: aStreamClass self target: anObject. self initializeStorage. self traverseWith: aStreamClass
This is great, but since our passenger will also take note of the ways in which the target can be found, it also needs a way to answer results. Let’s consider this carefully. To begin with, all paths to our target would start at Smalltalk. In particular, it may be that some references have a common street block other than Smalltalk. When that is the case, it would be nice to merge these paths so that their common roots are listed only once in our results.
How could we do this with ease? Well, one could use a dictionary plus the at:ifAbsentPut: message. This would be a quite straightforward use of the standard Smalltalk class library. But. . . we have already seen how much better we can do and how much more expressive we can be. It may be invisible at first, but it is so obvious once we think of it. We could simply let the results be an instance of Form.
Of course! The axiom regarding the repeated use of a name fits this perfectly. To me, at least, it is quite beautiful to first see the Smalltalk image in terms of forms and distictions, and then provide answers in the same frame of mind. But, besides the fact that it is indeed pretty, there are more advantages to this approach. In particular, it will save us from writing code to map one point of view into the other. We can have the cake and eat it too. Therefore,
PathTracer>>pathsTo: anObject using: aStreamClass self target: anObject. self form: Form new. self initializeStorage. self traverseWith: aStreamClass. ^self form
~
Re: `Form` ⇒ The Smalltalk Space, Laws of Form Objects
Form>>distinguish: aName ^(self distinctionNamed: aName) ifNil: [ | distinction | distinction := Dictinction named: aName. distinction form: self. self distinctions add: distinction. distinction ]
[…]
~
Let’s continue painting. The next thing to do is to initialize the object storage. What could be difficult about that?
Many things. Here we find a technical issue we must handle carefully. Ideally, since we will remember visited objects in terms of their identity, we would just write something along the lines of
PathTracer>>initializeStorage self storage: IdentitySet new
Some of you may be familiar with this already, but instances of IdentitySet rely on sending the message identityHash to access and manage their contents efficiently. And the speed with which they can do this relies heavily on the values of identityHash being pretty much unique across the objects they contain.
In VisualWorks, there are 14 bits dedicated to the values of identityHash. This means that we will see, at most, 16, 384 different identityHash values. But clearly, there are way many more objects than that in a Smalltalk image, and thus instances of IdentitySet will become inefficient very quickly. While refusing to go over the details at this time, our handy Smalltalk mentor tells us that the performance impact can be quite significant. Let’s assume that it is so, at least for the time being. What to do?
This turns out to be a rather thorny problem. But perhaps we are lucky. Browsing the hierarchy of `IdentitySet` reveals that it has a subclass called `ObjectRegistry`. Reviewing its implementation, one can get the impression that it refines IdentitySet with speed in mind. We could use it for now, but let’s keep a note to ourselves: we really need to review exactly what is this business of hashing objects.
**Note**: What is hashing objects all about?
Therefore, feeling a bit of discomfort from doing something we are not sure about, we write:
PathTracer>>initializeStorage self storage: ObjectRegistry new
Since this object registry will hopefully behave like any other identity set, at least we seem to have a temporary excuse to pretend there is no performance issue while we implement the rest of the path tracer. If nothing else, we have quite a bit to do yet, and execution speed will only be a problem once we get this thing working.
When there are plenty of issues, more often than not the best thing to do is to tackle them one at a time while forgetting about the rest. This helps keeping our stress level down and our best intellectual abilities intact.
It is a well-documented fact that fear progressively and literally blocks our intellectual abilities. When in panic, people frequently cause their situation to become worse as a result of irrational decisions.
So. . . after staring at the implementation of initializeStorage for a while, perhaps we start wondering if it is correct to begin with. The easiest check is to pretend the implementation is done, and then to make up some mock example to see if it does what we think it should. Let’s say we start our traversal with an empty storage, which will fill up as we visit objects. That seems fine until we consider the special cases. What if our traversal took us back to Smalltalk? Then we would not recognize it as an already seen object and waste our time wondering why is this taxi driver taking us to all these places we already know. So we should add Smalltalk to the storage to begin with, and then we would save ourselves a bunch of trouble. As we will make reference to Smalltalk from other methods, let’s give it a name in the form of a selector.
PathTracer>>scanRoot ^Smalltalk
With this convenient message, now we can refine initializeStorage to send the message scanRoot instead of referencing Smalltalk directly.
[…]
Note how this time the form is an instance of ObjectForm, while the results held by the passenger are stored in instances of Form instead. This reflects the deliciously subtle and meaningful change in point of view between the passenger and the driver. In fact, it is time to cross that boundary ourselves. The next message we need to paint is drive:.