sammccall added a comment.
It occurs to me that `claim` is `O(node_tokens + log total_tokens)` which is
bad when the nodes are large.
Indeed for an input like `namespace { namespace { namespace { ... } } }` time
is quadratic.
I think this is probably fine in practice. Against adversarial input clang
certainly can take exponential time, and easily crash too.
If we do need to fix it my best idea is to give each "uninteresting" TokInfo
(that is, !selected || claimed) a pointer to the next TokInfo with different
flags. This would allow iteration to quickly skip over contiguous ranges one
they had been traversed once.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D65486/new/
https://reviews.llvm.org/D65486
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
