Page MenuHomePhabricator

[SyntaxTree] Add reverse links to syntax Nodes.

Authored by eduucaldas on Oct 27 2020, 8:27 AM.



Children of a syntax tree had forward links only, because there was no need for reverse links.

This need appeared when we started mutating the syntax tree.
On a forward list, to remove a target node in O(1) we need a pointer to the node before the target. If we don't have this "before" pointer, we have to find it, and that requires O(n).

So in order to remove a syntax node from a tree, we would similarly need to find the node before to then remove. This is both not ergonomic nor does it have a good complexity.

Diff Detail

Event Timeline

eduucaldas created this revision.Oct 27 2020, 8:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 27 2020, 8:27 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
eduucaldas requested review of this revision.Oct 27 2020, 8:27 AM
eduucaldas edited the summary of this revision. (Show Details)Oct 27 2020, 8:28 AM
eduucaldas added a subscriber: sammccall.
eduucaldas added inline comments.

Should we provide an appendChildLowLevel as well?

That has one use inside foldChildren in BuildTree.cpp.
Currently this function does a reverse iteration prepending children. We could change that into a forward iteration appending. There is no impact in time-complexity. This change would just improve readability inside this function.

gribozavr2 added inline comments.Oct 27 2020, 8:59 AM

There is some awkwardness in foldChildren because we can only go in reverse -- maybe append is indeed more natural.


Do you plan to remove BeforeBegin argument (in a follow-up if you prefer, but you could also change it here)


I think you could fold this check into the for loop below.

sammccall added inline comments.Oct 27 2020, 9:12 AM

(Not something to change in this patch...)
Since adding the "get" prefixes, getNextSibling() and now getPreviousSibling() are pretty verbose, we might consider getNext()/getPrevious()


Consider insert(Node *Child, const Node *Before) where Before=Null means append.

This is fairly ergonomic for common cases:

  • append: insert(N, null)
  • prepend: insert(N, N->firstChild())
  • insert-before: insert(N, M)
  • insert-after: insert(N, M->nextSibling())

(Either before or after works fine, before matches STL insert better)

eduucaldas marked 3 inline comments as done.
  • replaceChildRangeLowLevel now takes Begin instead of BeforeBegin
  • appendChildLowLevel
eduucaldas marked 2 inline comments as done.Oct 28 2020, 2:10 AM
eduucaldas added inline comments.

I agree


That is great, but we have even a superset of this:
replaceChildRangeLowLevel(Node* BeforeBegin, Node* End, Node* New)
insert(Child, Before) = replaceChildRangeLowLevel(Before, Before->getNextSibling(), Child)

I think the point of having append and prepend is that until now that's what builders need, and such a specialization carries more semantics.

For the mutations API, where we need this kind of capability we provide replaceChildRangeLowLevel.


I replace every place where we did a reverse iteration prepending for a normal iteration appending, and now there are no more users of prepend ^^.

I propose we keep it anyways, we have bidirection list, makes sense to have both.

LG from my side.


I'm not sure this is the right set of operations, but as long as it's private it's probably not worth worrying too much about.
(By the same token, I think unused functions should be dropped, but up to you).

Let's revisit if we add a public mutation API.

gribozavr2 added inline comments.Oct 28 2020, 5:29 AM

I like having the word "sibling" in the name -- getNext() makes me wonder, "next what?"

If this was an iterator abstraction where next/previous are core to the meaning, sure, but a tree node is more complex.


This is a complete nitpick, but could you put append before prepend? I think a lot more people are interested in append. Same in the two overloads below.


That is great, but we have even a superset of this:

I mean, if we intend to provide a convenient API, adding insert would make sense even if it is not needed right now. From the industry experience with containers, we know that replace, insert, append, prepend are all common operations, and even though all of them can be expressed with just replace, people like to use specialized operations as that expresses the intent better.

OTOH, it seems like the design here is that mutations are provided by the MutationsImpl class, so any such convenience operation needs to be implemented there.


It would be great to document that nullptr in Begin or End mean the one-past-end position.


Remove the comment?


Use a range-based for loop?


Seems like Begin==nullptr is only allowed when this subtree has no children. I'd think that Begin==End==nullptr is a valid way to append children even to non-empty trees.

Do we have tests for this function? Would be really good to add that case.


Thinking about the semantics of this operation, do we need to break the sibling links in the range that is being removed? We expect the sibling links to be established in the new range. That's a suspicious asymmetry.


Rebase to include ChildIterator patch.

This comment was removed by eduucaldas.
eduucaldas marked 9 inline comments as done.

Answered all comments but:

  • Add tests for replaceChildRangeLowLevel
  • Asymmetry of replaceChildRangeLowLevel, do we need to separate children of the replaced range?

As we discussed offline we will probably not provide replaceChildRange in the public mutations API anymore.

As a result I don't think we should be chaining changes related to replaceChildRange in this patch, and thus it should be ready to go.

gribozavr2 accepted this revision.Nov 5 2020, 1:25 AM
This revision is now accepted and ready to land.Nov 5 2020, 1:25 AM
This revision was landed with ongoing or failed builds.Nov 5 2020, 1:54 AM
This revision was automatically updated to reflect the committed changes.