Revamp of the basic layouting algorithm in clang-format.
In order to end up with good solutions, clang-format needs to try
"all" combinations of line breaks, evaluate them and select the
best one. Before, we have done this using a DFS with memoization
and cut-off conditions. However, this approach is very limited
as shown by the huge static initializer in the attachment of
llvm.org/PR14959.
Instead, this new implementation uses a variant of Dijkstra's
algorithm to do a prioritized BFS over the solution space.
Some numbers:
lib/Format/TokenAnnotator.cpp: 1.5s -> 0.15s
Attachment of PR14959: 10min+ (didn't finish) -> 10s
No functional changes intended.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@174166 91177308-0d34-0410-b5e6-96231b3b80d8
1 file changed