My question is as simple as the title says -- should I implement AST with parent or not?
Currently I implemented it with parent -- the benefit of that approach is, that whatever I use, I can go up or down without any problem, all I need is some node. And modifications to the tree are also easy, because they are local to given branch.
However... when I look at the profiles, I see, that over 40% of the time is spent on cloning nodes. Clone is necessary, because with parent I cannot attach given node to multiple parents.
The opposite -- no parent -- would eliminate the need for cloning (at least such heavy usage), the tree would be more compact (actually it would be no tree no more, because of shared nodes), but would force me to use some kind navigator class to keep track of nodes when traversing them, and will add a little burden to modifying branches (first I would have to make a local clone :-) and then modify it).
It is hard for me to estimate which approach is better. Oh well, maybe there is some third way? Thank you in advance for help.