[clang-format][NFC] Replace deque with vector

[HazardyKnusperkeks]

Summary

I think the deque was chosen because of a better push_front, but in combination with llvm::reverse the push_back'ed vector should be the better choice.

[curdeius]

Deque, contrary to the vector, doesn't need to move the elements when growing. I'm not sure if that's relevant here though.
Have you checked what's on average the maximum size of Path on some larger repo?
Maybe using llvm::SmallVector with some well-thought (data-based) static number of elements would be better here, WDYT?

[MyDeveloperDay]

This seems reasonable its as if we only ever push_back and iterate backwards?

[HazardyKnusperkeks]

In D115064#3170615, @curdeius wrote:

Deque, contrary to the vector, doesn't need to move the elements when growing. I'm not sure if that's relevant here though.
Have you checked what's on average the maximum size of Path on some larger repo?
Maybe using llvm::SmallVector with some well-thought (data-based) static number of elements would be better here, WDYT?

I have not checked what the sizes are. But I have thought about reserving the upper bound (all visited states) so there is only one allocation.
The moving of the content shouldn't be problematic, since we only have pointers.

[HazardyKnusperkeks]

Formatting fixed.

[owenpan]

In D115064#3170615, @curdeius wrote:

Maybe using llvm::SmallVector with some well-thought (data-based) static number of elements would be better here, WDYT?

I tend to agree as LLVM style prefers SmallVector to vector.

[HazardyKnusperkeks]

In D115064#3171950, @owenpan wrote:

In D115064#3170615, @curdeius wrote:

Maybe using llvm::SmallVector with some well-thought (data-based) static number of elements would be better here, WDYT?

I tend to agree as LLVM style prefers SmallVector to vector.

Okay, didn't know I can use it without a number. Will update.

[MyDeveloperDay]

Even if you choose a number, beyond that number it behaves like a vector (just without the data being on the stack), its really good for small vectors but its not bad for large ones. I'm not sure what the default N is if you don't specify a number? (0?)

[HazardyKnusperkeks]

In D115064#3172860, @MyDeveloperDay wrote:

Even if you choose a number, beyond that number it behaves like a vector (just without the data being on the stack), its really good for small vectors but its not bad for large ones. I'm not sure what the default N is if you don't specify a number? (0?)

Yeah I know what this is. On the link ownpan provided it says it chooses a good number for the stack.

My initial take on it was since I don't know how many states we mostly have, I don't try to guess and waste space on the stack if there is a chance we always go to the heap anyway.

[HazardyKnusperkeks]

Now with SmallVector.

clang/lib/Format/UnwrappedLineFormatter.cpp

void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
 
     Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
     ++(*Count);
   }
 
   /// Applies the best formatting by reconstructing the path in the
   /// solution space that leads to \c Best.
   void reconstructPath(LineState &State, StateNode *Best) {
-    std::deque<StateNode *> Path;
+    llvm::SmallVector<StateNode *> Path;
     // We do not need a break before the initial token.
     while (Best->Previous) {
-      Path.push_front(Best);
+      Path.push_back(Best);
       Best = Best->Previous;
     }
-    for (auto I = Path.begin(), E = Path.end(); I != E; ++I) {
+    for (const auto &Node : llvm::reverse(Path)) {
       unsigned Penalty = 0;
-      formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
-      Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
+      formatChildren(State, Node->NewLine, /*DryRun=*/false, Penalty);
+      Penalty += Indenter->addTokenToState(State, Node->NewLine, false);
 
       LLVM_DEBUG({
-        printLineState((*I)->Previous->State);
-        if ((*I)->NewLine) {
+        printLineState(Node->Previous->State);
+        if (Node->NewLine) {
           llvm::dbgs() << "Penalty for placing "
-                       << (*I)->Previous->State.NextToken->Tok.getName()
+                       << Node->Previous->State.NextToken->Tok.getName()
                        << " on a new line: " << Penalty << "\n";
         }
       });
     }
   }
 
   llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
 };