#remove, TreeModel problems

Hi

Could anyone shed some light on what is going on in the following code (from
a workspace). I've created a TreeModel and associated TreePresenter and
added some nodes.
I then want to remove a node with #remove but get a walkback saying the node
isn't found.

Help!

As a newbie I'm probably doing something sooo stupid, so I apologise in
advance :) and also for the silly node names. When you gotta learn you gotta
learn!


Best wishes


Scott
-----------------------

"1. Evaluate all code below and 'Crufts' is removed OK.
 2. Evaluate all but last line - THEN last line individually, a walkback
occurs (Not found: Crufts)."

t := TreeModel new.
t add: 'Cats' asChildOf: nil.
t add: 'Dogs' asChildOf: nil.
t add: 'Meow' asChildOf: 'Cats'.
t add: 'Bark' asChildOf: 'Dogs'.
t add: 'Whiskas' asChildOf: 'Cats'.
t add: 'Crufts' asChildOf: 'Bark'.
t add: 'Humans' asChildOf: nil.
t add: 'Hands' asChildOf: 'Humans'.
t add: 'Fingers' asChildOf: 'Hands'.
t add: 'NotFurry' asChildOf: 'Humans'.
tp := TreePresenter showOn: t.
tp view viewMode: #largeIcons.

t remove: 'Crufts'.

Scott

You wrote in message news:98bd7n$1achg$[hidden email]...
>
> Could anyone shed some light on what is going on in the following code
(from
> a workspace). I've created a TreeModel and associated TreePresenter and
> added some nodes.
> I then want to remove a node with #remove but get a walkback saying the
node
> isn't found.
> ...

The problem is that TreeModel's use an 'identity' search to locate matching
nodes. Although the two 'Crufts' strings are equal objects, they are not the
same identical object, and so the TreeModel reports that the second 'Crufts'
is not found.

Although using an identity search may seem odd, and it is certainly
inconvenient for strings, it often does match the behaviour one wants in
practice. Where it doesn't it is easy to create an EqualityTreeModel by
subclassing and adding two methods. I've attached some code below. If you
file it in and re-run your example replacing TreeModel with
EqualityTreeModel you will find it works.

Actually I'm glad you've brought this up because it highlights an
inconsistency between TreeModels and ListModels. The latter support a
pluggable "search policy" so that subclassing is not required just to get
different lookup behaviour. The system includes search policies that perform
identity, equality, case-insensitive, etc, search policies, and also a
SearchPolicy which is itself pluggable to allow specification of the search
characteristics with blocks. TreeModel ought to be enhanced to support a
pluggable SearchPolicy just like ListModel does, so we will certainly
implement that in a future release.

Regards

Blair McGlashan
Object Arts Ltd
-------------------------------------------------
TreeModel subclass: #EqualityTreeModel

instanceVariableNames: ''

classVariableNames: ''

poolDictionaries: ''

classInstanceVariableNames: ''!

!EqualityTreeModel methodsFor!

mapClass

"Private - Answer the class of <LookupTable> to use to map the values

in the receiver to their nodes."

^LookupTable!

searchPolicy

"Answer the <searchPolicy> used to compare and search for elements by the
receiver."

^SearchPolicy equality! !

!EqualityTreeModel categoriesFor: #searchPolicy!accessing!public! !

!EqualityTreeModel categoriesFor: #mapClass!constants!private! !

Scott Deans wrote:

> Could anyone shed some light on what is going on in the following code
> [...]

What's happening is to do with the identity condition on Strings, and is a
bit subtle.

Under normal circumstances, two strings which have the same characters, but
which were created separately, will be two different objects.  However, in
Dolphin, if they are created in one go by the compiler -- for instance if
the same string appears twice in a method -- then it only creates *one*
String object to represent both literals.

One case where this applies is in workspaces.  For instance try the
following: evaluate the following lines one at a time.

s1 := 'Hi Scott!'.
s2 := 'Hi Scott!'.
s1 == s2.

The final expression evaluates to false.  Now try it again, but this time
select the first two lines and evaluate them both in one go; the last line
will now evaluate to true.

So what happens when you select and evaluate all 15 lines at once is that
all the occurrences of 'Crufts' are represented by the *same* object (this
applies to 'Cats', etc, too).  But, if you execute the lines one at a time
then each string is compiled into a unique object.  It'll be equal to the
other occurrence of 'Crufts' (in the sense that #= will be true), but it
won't be the same object.

That is what breaks the TreeModel.  It uses an IdentityDictionary internally
to map the objects in the tree ('Crufts', 'Dogs', etc) to the TreeNodes
which are used internally to hold the tree structure.  So if you execute all
the lines together, then it'll be attempting to find the same object,
'Crufts', in the IdentityDictionary as it originally put there.  If you
execute the lines one-at-a-time, then it'll trying to remove a different,
albeit equal, object, so the IdentityDictionary (which uses #== internally,
by definition) will throw a NotFound exception.

If you want to continue using Strings for your exploration then I suggest
you switch to Symbols (#Crufts, #Dog, etc), which do have the property that
all #= instances are also #==.

BTW, I don't -- personally -- think that this String optimisation in Dolphin
is a very good idea.  I can't think of any cases where it makes much
difference in reducing memory use, but it is definitely likely to cause
confusion in unwary programmers.  Worse, it can make a naively coded unit
test work, where real code would fail.  To be fair, though, I don't know
that it is a conscious attempt at optimisation; it may well just be a side
effect of the way the Dolphin parser works.

    -- chris

Chris,

> BTW, I don't -- personally -- think that this String optimisation in
Dolphin
> is a very good idea.  I can't think of any cases where it makes much
> difference in reducing memory use, but it is definitely likely to cause
> confusion in unwary programmers.  Worse, it can make a naively coded unit
> test work, where real code would fail.  To be fair, though, I don't know
> that it is a conscious attempt at optimisation; it may well just be a side
> effect of the way the Dolphin parser works.

Hmmm... well it is a conscious attempt at optimisation. When we were
implementing the original Dolphin compiler we heard that the VisualAge
compiler did the same so we decided to follow suit.

Best Regards,

Andy Bower
Dolphin Support
http://www.object-arts.com

---
Visit the Dolphin Smalltalk WikiWeb
http://www.object-arts.com/wiki/html/Dolphin/FrontPage.htm
---

"Scott Deans" <[hidden email]> wrote in message
news:98bd7n$1achg$[hidden email]...

Thanks for the help guys!

Scott

> > BTW, I don't -- personally -- think that this String optimisation in
> Dolphin
> > is a very good idea.  I can't think of any cases where it makes much
> > difference in reducing memory use, but it is definitely likely to cause
> > confusion in unwary programmers.  Worse, it can make a naively coded
unit
> > test work, where real code would fail.  To be fair, though, I don't know
> > that it is a conscious attempt at optimisation; it may well just be a
side
> > effect of the way the Dolphin parser works.
>
> Hmmm... well it is a conscious attempt at optimisation. When we were
> implementing the original Dolphin compiler we heard that the VisualAge
> compiler did the same so we decided to follow suit.

I agree with Chris in a way. This is confusing. I have to explain it to
everyone I teach VA. It also leads to the inability to store into compiler
(parser?) created Strings, while you can store into other Strings. You can't
see a difference in the inspector.

On the other hand, it pays to keep in mind that when comparing literal type
objects (i.e., literally creatable), you use equality, unless you're dealing
with Symbols or Atoms, which are specifically designed to be compared by
their references (at the cost of interning them).

If you happen to know that Strings, Integers and Characters may be interned
identity objects, don't let that lead you astray from the basic comparison
principles, and you won't get in trouble with any optimizations.

I do recommend, on a related note, that component distributors make a point
of being explicit about whether objects or references are being compared in
particular situations. So, in examples with Sets, which are invariably
touted in tutorials as removing 'duplicates', it would be made explicit what
'duplicate' actually means.

In that exposition, it would also be made clear that the name Set is
actually short for EqualitySet, that there is also a class IdentitySet, and
that it is completely arbitrary that Set is an equality set. And that the
default implementation for equality testing is to test for identity, so that
it may look as if you're doing identity comparisons when you aren't.

Incidentally. Eiffel deals with this issue in a very simple and elegant way.
Every collection has a comparison criterion, and you can ask it if it
compares objects or references. Many collections have a changeable
comparison criterion. Very simple and clear way of dealing with this
head-on.

Regards,

Peter van Rooijen

Peter

You wrote in message news:98dsm3$2tt$[hidden email]...
>...[it should] also be made clear that the name Set is
> actually short for EqualitySet, that there is also a class IdentitySet,
and
> that it is completely arbitrary that Set is an equality set. And that the
> default implementation for equality testing is to test for identity, so
that
> it may look as if you're doing identity comparisons when you aren't.
>
> Incidentally. Eiffel deals with this issue in a very simple and elegant
way.
> Every collection has a comparison criterion, and you can ask it if it
> compares objects or references. Many collections have a changeable
> comparison criterion. Very simple and clear way of dealing with this
> head-on.

In Dolphin 4.0 the various types of Dictionaries implement a #searchPolicy
method that answers an object which conforms to our <searchPolicy> protocol
(hmmm, why isn't this implemented on Set?). <searchPolicy> defines the
messages #compare:with:, #hash:, #hash:max:, #keyAtValue:in:ifAbsent:, and
#nextIndexOf:in:from:to:, I'm sure you can guess what they do - the most
important ones are the hash and compare methods, the others being sequential
searches that are generally implemented in terms of #compare:with:, but
which are included because some types of search policy (identity) have much
faster ways to do scans. Do you think it would be useful if <searchPolicy>
included a #name (or similar) message which allowed one to query the
symbolic name of the type of policy it represents?

In practice the <searchPolicy> conforming object will be a sub-instance of
the SearchPolicy class. SearchPolicy has subclasses:
    EqualitySearchPolicy
    IdentitySearchPolicy
    PluggableSearchPolicy

and a few others with specialist uses (CaseInsensitiveSearchPolicy,
CompiledMethodSearchPolicy and AssociationsSearchPolicy).

PluggableSearchPolicy allows one to create a specialist <searchPolicy>
without subclassing (one specifies a pair of blocks to perform hashing and
comparison operations when instantiating the object).

The <searchPolicy> of Dictionary, LookupTable and IdentityDictionary can be
queried, but not set. However we also have PluggableSet and
PluggableLookupTable that allow one to set the <searchPolicy> when creating
the collection.

If we are going to adopt the notion of "pluggable" collections into
Smalltalk in general, then I would argue strongly for using a <searchPolicy>
object as the pluggable policy rather than a set of blocks (or other
valuables).

Regards

Blair McGlashan
Object Arts Ltd