Re: Double-traversal with List (HW#4)

Subject: Re: Double-traversal with List (HW#4)
From: Doug Orleans (
Date: Sat Oct 28 2000 - 22:36:39 EDT

Bud and Lori Grise writes:
> Hi Doug, Stelios,
> I've been trying to fix this bug in my HW#4 filesystem
> project for the past few hours without any luck. I'm not
> sure if what I'm seeing is a demeterj bug or if I'm just
> confused (always a possibility :).

It's not exactly a bug, but it's an artifact of the rough interface
between DJ and DemeterJ, which is still very new and has some kinks to
be worked out.

> The problem occurs is when I traverse the filesystem looking
> for directories. The filesystem is this (which was given):
> FileSystem = <root> CompoundFile EOF.
> File : SimpleFile | CompoundFile common <f> FileName.
> SimpleFile = "simple".
> CompoundFile = "compound" <contents> PList(File) [<parent> CompoundFile
> ].
> I create a traversal to reach all files from the current directory:
> TraversalGraph allFiles = new TraversalGraph(
> "from File_PList bypassing -> *,parent,* to CompoundFile",;
> allFiles.traverse(Main.cdir.get_contents(), new FileVisitor());
> The problem is that when the traversal is being done, the
> last directory (aka CompoundFile) in each directory is traversed
> *twice*. Here's a trivial input and the corresponding output:
> >mkdir dir1
> >du .
> Created directory dir1
> .
> ./dir1
> ./dir1
> I looked at the generated java files, and I think what is happening
> is related to the fact that File_PList has two member fields of
> type Nonempty_File_PList:
> protected Nonempty_File_PList first;
> private Nonempty_File_PList tail;
> When an element is added to a File_PList, it is added to the
> of the Nonempty_File_PList, *and* the File_PList tail field
> is set to this element. I am sure that both the fields "first"
> and "tail" are being traversed.

Yep, your diagnosis is correct. The "tail" part was added for
efficiency when adding to the end of a list with the addElement()
method that is generated for each repetition class. (This predates
the Java 2 Collections framework, otherwise it would be called add()
to conform to the Collection interface.)

> One thing I'm confused about is why this doesn't seem to happen
> with a statically defined traversal, such as this one for
> PrintVisitor:
> FileSystem {
> void display()
> bypassing -> *,parent,* to * (PrintVisitor);
> }
> The output from this traversal on the above trivial input is
> as expected:
> compound(compound()dir1)root

The "tail" field is generated in the Java code, but is not actually
added to the class graph that DemeterJ uses when computing traversal
graphs. However, DJ has no way of knowing that this field is not
meant to be part of the class graph. There are two ways to get
around this:

One is to bypass it in your traversals, the same way that
you bypass the "parent" edge:

   TraversalGraph allFiles = new TraversalGraph(
     "from File_PList bypassing { -> *,parent,* , -> *,tail,* }"
     + " to CompoundFile",;

The other way is to remove this edge from the ClassGraph object.
Well, currently there's no way to directly remove edges from
ClassGraphs, but what you can do is create a new ClassGraph from the
existing ClassGraph and a TraversalGraph that specifies the subgraph
you want to keep:

    ClassGraph cgWithoutTail = new ClassGraph(
        new TraversalGraph("from * bypassing -> *,tail,* to *",;

Actually, you can do this directly with a special constructor for

    ClassGraph cgWithoutTail = new ClassGraph(,
        "from * bypassing -> *,tail,* to *");

Then you can use this ClassGraph object for all of your traversals
rather than modifying all your strategies.

> Could there be a problem with non-statically defined traversals?
> Are they supposed to treat edges that are private fields? Or
> have I just specified my traversal incorrectly? I've spent
> about 4 hours on just this bug (ulp!) and have run out of
> ideas. Any help is appreciated.
> Thanks,
> Ed Grise'

I apologize for the inconvenience... Feel free to send us mail as
soon as you get stuck, so if it turns out to be a problem with the
Demeter software then you don't have to spin your wheels. Of course,
if it turns out to be a bug in your own code, we might just tell you
you'll have to figure it out for yourself! But it can't hurt to ask.


This archive was generated by hypermail 2b28 : Sat Oct 28 2000 - 22:37:27 EDT