[antlr-interest] Leaks in doubly-linked trees: implementing 'getParent'

[Paul Johnson]

Some time ago there was a discussion about the need to occasionally look 
up trees to find your current context (starting at
<http://www.antlr.org/pipermail/antlr-interest/2005-June/012822.html>, 
through the threading on the website doesn't work well).

There was a school of thought that this is important in some situations, 
and that it should be implemented with 'getParent', and over-riding 
various other methods, which I suspect various people have done 
independently (including myself).

However, there's a problem with the obvious implementation, which is:

class myAST : public antlr::CommonAST {
private:
  RefAST up;                //!< Parent node
...
};

The problem is that this leaks. The assignment 'up = parent' will 
increase the parent's reference count. The problem comes when you 
attempt to delete a branch of a tree:

  // remove oldnode and its descendents, replace with newnode
  newnode->setNextSibling(oldnode->getNextSibling());
  previous->setNextSibling(newnode); // orphans oldnode

This orphans oldnode, but it won't delete it since the 'setNextSibling' 
op doesn't reduce its reference count to zero (because oldnode's 
children still reference it).

Does anyone have a bidirectional tree implementation that avoids this 
problem? At first sight, one obvious fix may be to modify the library 
code so that the reference count decrementing routines ignore references 
from children.

Paul