javalang
javalang copied to clipboard
getCommonAncestor is potentially slow
https://github.com/rpau/javalang/blob/cacae3667dec88f9c2955858fa2a0fe1d73bc0d3/src/main/java/org/walkmod/javalang/ast/Node.java#L353-L367
Right now it is O(N^2) for the worst case where N is the nesting level. You can reduce one order of magnitude O(3*N)
in the worst case.
You just have to calculate the nesting level. Just go to the root node for both nodes, so you have the depth. Once you have it, get the deepest node and go until the level matches the other one. Then move upwards both nodes until you reach the common node.