Possible Node.cloneList() bug in sablecc3.2

[Andrew Sweet]

Hi.

I believe there is a bug in Sablecc3.2 concerning the cloning of lists.
The code for the function currently reads as:

    protected <T> List<T> cloneList(List<T> list)
    {
        List<T> clone = new LinkedList<T>();

        for(T n : list)
        {
            clone.add(n);
        }

        return clone;
    }

However, inside the for loop, 'T' is of type Node and the Node n is an
element of a LinkedList already (say as part of an AST node that has a
child with a list type) then this operation will remove n from its
current LinkedList and add it to the new one, according to the Java
specification of LinkedList. This violates the intuitive 'cloning'
behaviour.

I believe the following code would be a suitable replacement:

    protected <T> List<T> cloneList(List<T> list)
    {
        List<T> clone = new LinkedList<T>();

        for(T n : list)
          if (n instanceof Node)
                  clone.add((T)((Node)n).clone());
              else
                  clone.add(n);

        return clone;
    }

Thanks,

Andrew

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Niklas Matthies]

On Sat 2008-02-02 at 01:42h, Andrew Sweet wrote on sablecc-discussion:
:

> I believe there is a bug in Sablecc3.2 concerning the cloning of lists.
> The code for the function currently reads as:
>
>     protected <T> List<T> cloneList(List<T> list)
>     {
>         List<T> clone = new LinkedList<T>();
>
>         for(T n : list)
>         {
>             clone.add(n);
>         }
>
>         return clone;
>     }
>
> However, inside the for loop, 'T' is of type Node and the Node n is an
> element of a LinkedList already (say as part of an AST node that has a
> child with a list type) then this operation will remove n from its
> current LinkedList

I don't think so. The newly instantiated LinkedList doesn't know about
the other list; adding to the new list does not cause removal from the
other list. After the "cloning", both lists refer to the same objects
(which may or may not be a bug).

Incidentally, the above method could be written more simply as:

    protected <T> List<T> cloneList(List<T> list)
    {
        return new LinkedList<T>(list);
    }

-- Niklas Matthies

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Etienne M. Gagnon]

SableCC 3.2 was meant, primarily, as a quick transition of SableCC 3.x to Java with genericity (i.e. parametric types). SableCC 4 will provide a cleaner implementation.

I agree that it is highly desirable that all AST components enforce the strict "tree" (e.g. not "dag") property of the AST.

Etienne

Niklas Matthies a écrit :

On Sat 2008-02-02 at 01:42h, Andrew Sweet wrote on sablecc-discussion:
:
  

I believe there is a bug in Sablecc3.2 concerning the cloning of lists. 
The code for the function currently reads as:

    protected <T> List<T> cloneList(List<T> list)
    {
        List<T> clone = new LinkedList<T>();

        for(T n : list)
        {
            clone.add(n);
        }

        return clone;
    }

However, inside the for loop, 'T' is of type Node and the Node n is an 
element of a LinkedList already (say as part of an AST node that has a 
child with a list type) then this operation will remove n from its 
current LinkedList
    

I don't think so. The newly instantiated LinkedList doesn't know about
the other list; adding to the new list does not cause removal from the
other list. After the "cloning", both lists refer to the same objects
(which may or may not be a bug).

Incidentally, the above method could be written more simply as:

    protected <T> List<T> cloneList(List<T> list)
    {
        return new LinkedList<T>(list);
    }
  

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Jon Shapcott]

On Wed, Feb 13, 2008 at 02:58:57PM -0500, Etienne M. Gagnon wrote:
> SableCC 3.2 was meant, primarily, as a quick transition of SableCC 3.x
> to Java with genericity (i.e. parametric types). SableCC 4 will provide
> a cleaner implementation.
>
> I agree that it is highly desirable that all AST components enforce the
> strict "tree" (e.g. not "dag") property of the AST.
>
> Etienne

I'm wondering if I understand you correctly here.

When a node is cloned, it performs a deep copy, and since it is no
longer in the original AST, the parent of the cloned node is set to
null.

It is also possible to clone lists in an AST. Should this also perform
a deep copy of each node in the list, setting all their parents to null?

I'm not refering to the internal cloneList() method, but to the public
clone() method defined by LinkedList. For example, given the following
definition in the AST,

    script = [body]:statement*;
   
and the following Java code,

    AScript script = ... ;

    LinkedList<PStatement> clonedBody =
        (LinkedList<PStatement>) script.getBody().clone();

My feeling is that, for consistency, it should also violate the usual
understanding of the clone() method. I'm not referring to the
transitional SableCC 3.2, but what we want to happen in SableCC 4.

There is a last problem here. In earlier ersions of SableCC, when you
removed a simple node from another node, the parent was set to null,
but when a node was removed from a list, then the parent remained set
to the node that contains the list.

In fairness, You could always use the replaceBy() method with a null
argument to make sure that the parent was set to null, but one of the
joys of SableCC is the ability to use all of the methods defined by
LinkedList. It strikes me that a subclass should be created that
always sets the parent to null when a node is removed.

--
Jon Shapcott <eden@...>
"This is the Space Age, and we are Here To Go" - William S. Burroughs

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Etienne M. Gagnon]

Hi Jon,

The SableCC 2&3 model for lists is broken. The parent of a node, in a
list, should be the list, not the parent of the list.

As SableCC 4 is not Java-centric, anymore, it makes no sense to make
SableCC generated code dependent of the Java API (such as the definition
of clone()). On the other hand, it also means that ASTs should have
their own List node type. For Java, it would allow us to enforce strict
typing (even dynamically) for list elements, even though the Java
compiler erases parametric types.

In any case, SableCC 4 will need various such utility (usually hidden)
classes for supporting the new, more flexible ASTs, such as:

identifier_list = (identifier Separator comma)+;

The above production matches: identifier [comma identifier [comma
identifier [...]]] It requires some special node type (unaccessible to
the programmer) so that AST walkers can visit the subtree.

Etienne

> When a node is cloned, it performs a deep copy, and since it is no
> longer in the original AST, the parent of the cloned node is set to
> null.
> [...]
> I'm not refering to the internal cloneList() method, but to the public
> clone() method defined by LinkedList. For example, given the following
> definition in the AST,
> [...]
> My feeling is that, for consistency, it should also violate the usual
> understanding of the clone() method. I'm not referring to the
> transitional SableCC 3.2, but what we want to happen in SableCC 4.
> [...]
>  

--
Etienne M. Gagnon, Ph.D.
SableCC:                                            http://sablecc.org
SableVM:                                            http://sablevm.org




_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Jon Shapcott]

On Sat, Apr 05, 2008 at 04:46:46PM -0400, Etienne M. Gagnon wrote:

> The SableCC 2&3 model for lists is broken. The parent of a node, in a
> list, should be the list, not the parent of the list.
>
> As SableCC 4 is not Java-centric, anymore, it makes no sense to make
> SableCC generated code dependent of the Java API (such as the definition
> of clone()). On the other hand, it also means that ASTs should have
> their own List node type. For Java, it would allow us to enforce strict
> typing (even dynamically) for list elements, even though the Java
> compiler erases parametric types.
>
> In any case, SableCC 4 will need various such utility (usually hidden)
> classes for supporting the new, more flexible ASTs, such as:
>
> identifier_list = (identifier Separator comma)+;
>
> The above production matches: identifier [comma identifier [comma
> identifier [...]]] It requires some special node type (unaccessible to
> the programmer) so that AST walkers can visit the subtree.

I've just posted a message about the solution I've come up with for
the tree invariant and concurrent modification problems with the
lists, but I thought I'd keep the discussion on cloning them separate.

Whilst I was interested in node list behaviour in SableCC 4, as far as I
can tell, they are going to dissappear completely, leaving the tree
walkers as the only way of iterating though them. Is something like
the replaceBy() method going to be the only way of modifying these
lists? Please correct me if I'm mistaken.

On a last note, and I don't mean to rude, "replace by" is problematic
English. You would usually say "replace X with Y" when asking somebody
to replace something, and use "by" only in the past tense, "X was
replaced by Y". Unfortunately that's not the whole story. It is also
permissable to say "X was replaced with Y". I quite often find myself
using the nonexistsent replaceWith() method, and having to go back and
fix it later.

--
Jon Shapcott <eden@...>
"This is the Space Age, and we are Here To Go" - William S. Burroughs





_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Etienne M. Gagnon]

Hi Jon,

See below.

Whilst I was interested in node list behaviour in SableCC 4, as far as I
can tell, they are going to dissappear completely, leaving the tree
walkers as the only way of iterating though them. Is something like
the replaceBy() method going to be the only way of modifying these
lists? Please correct me if I'm mistaken.
  

(1) Yes. Allowing for adding/removing nodes, in a list, causes problems. In Java, they have opted to throw an exception on "concurrent" modifications. So, if you look in the generated tree walkers of SableCC 2/3, you'll see that to visit a list, the code first copies list elements into an array, then iterates over that array. This leads to undesirable object creation for every walk of the AST.

In SableCC 4, if you want to add a node to a list, you'll have to create a new list. This does imply that all children are passed as argument to the constructor, as with other nodes. In can be done in various ways; we'll try to pick the best way for each target language.

On a last note, and I don't mean to rude, "replace by" is problematic
English. You would usually say "replace X with Y" when asking somebody
to replace something, and use "by" only in the past tense, "X was
replaced by Y". Unfortunately that's not the whole story. It is also
permissable to say "X was replaced with Y". I quite often find myself
using the nonexistsent replaceWith() method, and having to go back and
fix it later.
  

(2) My apologies; English is not my mother tongue. I do my best to name things as intuitively as possible. Thanks for helping me fix these little discrepancies. :-)

In SableCC 4, it will be called "replaceWith".

Etienne



_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Jon Shapcott]

On Tue, Apr 08, 2008 at 06:19:48PM -0400, Etienne M. Gagnon wrote:

> >On a last note, and I don't mean to rude, "replace by" is problematic
> >English. You would usually say "replace X with Y" when asking somebody
> >to replace something, and use "by" only in the past tense, "X was
> >replaced by Y". Unfortunately that's not the whole story. It is also
> >permissable to say "X was replaced with Y". I quite often find myself
> >using the nonexistsent replaceWith() method, and having to go back and
> >fix it later.
> >  
> (2) My apologies; English is not my mother tongue. I do my best to name
> things as intuitively as possible. Thanks for helping me fix these
> little discrepancies. :-)
>
> In SableCC 4, it will be called "replaceWith".

Excellent. I'm aware that you're not a native speaker, which is why I
stressed my intention of not being rude, especially as most native
English speakers, the British and North Americans (except Native
Americans and those from Quebec) almost never bother to learn another
language.

Oddly enough though, I discussed this usage with some of my flatmates
last night. They thought I was wrong, and that you would only use "by"
to indicate the agent that did the replacement, such as "X was
replaced by Jon" or "X is to be replaced by the government". This is
one of those examples of native speakers not being good at reasoning
about their language, even when they feel that something isn't quite
right.

--
Jon Shapcott <eden@...>
"This is the Space Age, and we are Here To Go" - William S. Burroughs

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Etienne M. Gagnon]

Hi Jon,

I'm genuinely confused now. Should it be "replaceWith" or "replaceBy"? Is there some reliable reference material to verify such stuff? I have an old Webster's Dictionary including Thesaurus and I haven't found an answer in it.

Etienne

Jon Shapcott wrote:

Oddly enough though, I discussed this usage with some of my flatmates
last night. They thought I was wrong, and that you would only use "by"
to indicate the agent that did the replacement, such as "X was
replaced by Jon" or "X is to be replaced by the government". This is
one of those examples of native speakers not being good at reasoning
about their language, even when they feel that something isn't quite
right.
  

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Niklas Matthies]

On Wed 2008-04-09 at 14:18h, Etienne M. Gagnon wrote on sablecc-discussion:
> Hi Jon,
>
> I'm genuinely confused now. Should it be "replaceWith" or "replaceBy"?
> Is there some reliable reference material to verify such stuff? I have
> an old /Webster's Dictionary including Thesaurus/ and I haven't found an
> answer in it.

I believe "by" is not incorrect, though "with" arguably reads better.
For example http://www.thefreedictionary.com/replaced has several
examples of "replace ... by".
The "by" is probably more common when used with "replaceD".

A quick Google search turns up significantly more hits for "replacewith"
than for "replaceby", but also significantly more hits for "replaceD-by"
than for "replaceD-with".

FWIW, java.nio.charset.CharsetEncoder has a replaceWith() method.

-- Niklas Matthies

_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Stephen P Spackman-2]

>> I'm genuinely confused now. Should it be "replaceWith" or "replaceBy"?
>> Is there some reliable reference material to verify such stuff? I have
>> an old /Webster's Dictionary including Thesaurus/ and I haven't found an
>> answer in it.
>
> I believe "by" is not incorrect, though "with" arguably reads better.
> For example http://www.thefreedictionary.com/replaced has several
> examples of "replace ... by".
> The "by" is probably more common when used with "replaceD".
>
> A quick Google search turns up significantly more hits for "replacewith"
> than for "replaceby", but also significantly more hits for "replaceD-by"
> than for "replaceD-with".
>
> FWIW, java.nio.charset.CharsetEncoder has a replaceWith() method.

Hi all.

I *suspect* what is going on is that 'replace with' preferentially refers
to a change, while 'replace by' refers to a state, making 'replace by'
sound strange as a command. I would definitely agree that, for me,
'replace with' is more comfortable, and leaps faster to the fingers,
though it seems that this is one of those places where not everyone uses
the words in quite the same way.

I will, however, send a quick note to my brother, who happens to be a
professional lexicographer (which, if nothing else, means that he is
likely to have better reference books on his desk than any of us ;) ) -
and see if he has an opinion.

Regards
Stephen P Spackman


_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Stephen P Spackman-2]

Niklas Matthies wrote:

> On Wed 2008-04-09 at 14:18h, Etienne M. Gagnon wrote on
> sablecc-discussion:
>> Hi Jon,
>>
>> I'm genuinely confused now. Should it be "replaceWith" or "replaceBy"?
>> Is there some reliable reference material to verify such stuff? I have
>> an old /Webster's Dictionary including Thesaurus/ and I haven't found an
>> answer in it.
>
> I believe "by" is not incorrect, though "with" arguably reads better.
> For example http://www.thefreedictionary.com/replaced has several
> examples of "replace ... by".
> The "by" is probably more common when used with "replaceD".
>
> A quick Google search turns up significantly more hits for "replacewith"
> than for "replaceby", but also significantly more hits for "replaceD-by"
> than for "replaceD-with".
>
> FWIW, java.nio.charset.CharsetEncoder has a replaceWith() method.

My brother, who is a lexicographer, observes that 'replace' is often used
in the passive; we might say 'this attribute is replaced by this function'
or 'this attribute is replaced with this function', and it's only the
preposition that tells us whether the function does the work, or gets
stored (a less technical example is 'the whole department was replaced
with/by a single manager'). Although the imperative is not ambiguous -
it's "function, replace this" as opposed to "replace this with function",
the preference for 'with' carries over.

So there is a good, if subtle, reason that replaceWith() sounds better to
native speakers. It will also make clear documentation easier to write!

(Oh, and the disclaimer: he also says that this is his quick guess, and
not an official, researched opinion.)

Regards
Stephen P Spackman


_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Etienne M. Gagnon]

Hi Stephen,

Let me see if I get this right... In the following code fragment:

node.replaceWith(otherNode);

we are asking node to replace itself with otherNode in the AST. After
executing this code, node will have been replaced with otherNode by the
method call.

If I am right, then it was wrong to call the method replaceBy in the
first place. SableCC 4 will be better, even in its use of the English
language. Cool!

Thanks to you brother (and you!),

Etienne
PS: This mailing list has such a great membership. I enjoy these
discussions! I do love learning about subtle details.

> My brother, who is a lexicographer, observes that 'replace' is often used
> in the passive; we might say 'this attribute is replaced by this function'
> or 'this attribute is replaced with this function', and it's only the
> preposition that tells us whether the function does the work, or gets
> stored (a less technical example is 'the whole department was replaced
> with/by a single manager'). Although the imperative is not ambiguous -
> it's "function, replace this" as opposed to "replace this with function",
> the preference for 'with' carries over.
>
> So there is a good, if subtle, reason that replaceWith() sounds better to
> native speakers. It will also make clear documentation easier to write!
>
> (Oh, and the disclaimer: he also says that this is his quick guess, and
> not an official, researched opinion.)
>  

--
Etienne M. Gagnon, Ph.D.
SableCC:                                            http://sablecc.org
SableVM:                                            http://sablevm.org




_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion

[Jon Shapcott]

On Wed, Apr 09, 2008 at 07:50:02PM -0400, Etienne M. Gagnon wrote:

> Hi Stephen,
>
> Let me see if I get this right... In the following code fragment:
>
> node.replaceWith(otherNode);
>
> we are asking node to replace itself with otherNode in the AST. After
> executing this code, node will have been replaced with otherNode by the
> method call.
>
> If I am right, then it was wrong to call the method replaceBy in the
> first place. SableCC 4 will be better, even in its use of the English
> language. Cool!
>
> Thanks to you brother (and you!),
>
> Etienne
> PS: This mailing list has such a great membership. I enjoy these
> discussions! I do love learning about subtle details.

Yikes! It's odd how renaming a method opened such a can of worms, but
I do think that replaceWith() would be better. To get a more complete
sense of it, consider "X should be replaced with Y by Z". X is the
original, Y is the replacement, and Z is the agent that is proposed to
perform the replacement.

My linguist flatmate (the kind of British liguist that studies
languages, but can only speak English, Latin and ancient Greek)
infroms me that he didn't realise that "replace" is such a peculiar
verb before this discussion. Nearly, but not quite, a transitive
locative verb ("lean the broom against the wall" is the usual
example). I always ask him for suggestions When I'm worried about the
best name for a method.

--
Jon Shapcott <eden@...>
"This is the Space Age, and we are Here To Go" - William S. Burroughs




_______________________________________________
SableCC-Discussion mailing list
SableCC-Discussion@...
http://lists.sablecc.org/listinfo/sablecc-discussion