Export clang-format16 via ydblib project

6e6be3a95868fde888d801b7590af4044049563f

6 files changed, 2556 insertions, 0 deletions

diff --git a/contrib/libs/clang16/lib/Rewrite/DeltaTree.cpp b/contrib/libs/clang16/lib/Rewrite/DeltaTree.cpp
new file mode 100644
index 0000000000..61467f8492
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/DeltaTree.cpp
@@ -0,0 +1,470 @@
+//===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the DeltaTree and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/Core/DeltaTree.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+#include <cstring>
+
+using namespace clang;
+
+/// The DeltaTree class is a multiway search tree (BTree) structure with some
+/// fancy features.  B-Trees are generally more memory and cache efficient
+/// than binary trees, because they store multiple keys/values in each node.
+///
+/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
+/// fast lookup by FileIndex.  However, an added (important) bonus is that it
+/// can also efficiently tell us the full accumulated delta for a specific
+/// file offset as well, without traversing the whole tree.
+///
+/// The nodes of the tree are made up of instances of two classes:
+/// DeltaTreeNode and DeltaTreeInteriorNode.  The later subclasses the
+/// former and adds children pointers.  Each node knows the full delta of all
+/// entries (recursively) contained inside of it, which allows us to get the
+/// full delta implied by a whole subtree in constant time.
+
+namespace {
+
+  /// SourceDelta - As code in the original input buffer is added and deleted,
+  /// SourceDelta records are used to keep track of how the input SourceLocation
+  /// object is mapped into the output buffer.
+  struct SourceDelta {
+    unsigned FileLoc;
+    int Delta;
+
+    static SourceDelta get(unsigned Loc, int D) {
+      SourceDelta Delta;
+      Delta.FileLoc = Loc;
+      Delta.Delta = D;
+      return Delta;
+    }
+  };
+
+  /// DeltaTreeNode - The common part of all nodes.
+  ///
+  class DeltaTreeNode {
+  public:
+    struct InsertResult {
+      DeltaTreeNode *LHS, *RHS;
+      SourceDelta Split;
+    };
+
+  private:
+    friend class DeltaTreeInteriorNode;
+
+    /// WidthFactor - This controls the number of K/V slots held in the BTree:
+    /// how wide it is.  Each level of the BTree is guaranteed to have at least
+    /// WidthFactor-1 K/V pairs (except the root) and may have at most
+    /// 2*WidthFactor-1 K/V pairs.
+    enum { WidthFactor = 8 };
+
+    /// Values - This tracks the SourceDelta's currently in this node.
+    SourceDelta Values[2*WidthFactor-1];
+
+    /// NumValuesUsed - This tracks the number of values this node currently
+    /// holds.
+    unsigned char NumValuesUsed = 0;
+
+    /// IsLeaf - This is true if this is a leaf of the btree.  If false, this is
+    /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
+    bool IsLeaf;
+
+    /// FullDelta - This is the full delta of all the values in this node and
+    /// all children nodes.
+    int FullDelta = 0;
+
+  public:
+    DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}
+
+    bool isLeaf() const { return IsLeaf; }
+    int getFullDelta() const { return FullDelta; }
+    bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
+
+    unsigned getNumValuesUsed() const { return NumValuesUsed; }
+
+    const SourceDelta &getValue(unsigned i) const {
+      assert(i < NumValuesUsed && "Invalid value #");
+      return Values[i];
+    }
+
+    SourceDelta &getValue(unsigned i) {
+      assert(i < NumValuesUsed && "Invalid value #");
+      return Values[i];
+    }
+
+    /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
+    /// this node.  If insertion is easy, do it and return false.  Otherwise,
+    /// split the node, populate InsertRes with info about the split, and return
+    /// true.
+    bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
+
+    void DoSplit(InsertResult &InsertRes);
+
+
+    /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
+    /// local walk over our contained deltas.
+    void RecomputeFullDeltaLocally();
+
+    void Destroy();
+  };
+
+  /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
+  /// This class tracks them.
+  class DeltaTreeInteriorNode : public DeltaTreeNode {
+    friend class DeltaTreeNode;
+
+    DeltaTreeNode *Children[2*WidthFactor];
+
+    ~DeltaTreeInteriorNode() {
+      for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
+        Children[i]->Destroy();
+    }
+
+  public:
+    DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
+
+    DeltaTreeInteriorNode(const InsertResult &IR)
+        : DeltaTreeNode(false /*nonleaf*/) {
+      Children[0] = IR.LHS;
+      Children[1] = IR.RHS;
+      Values[0] = IR.Split;
+      FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
+      NumValuesUsed = 1;
+    }
+
+    const DeltaTreeNode *getChild(unsigned i) const {
+      assert(i < getNumValuesUsed()+1 && "Invalid child");
+      return Children[i];
+    }
+
+    DeltaTreeNode *getChild(unsigned i) {
+      assert(i < getNumValuesUsed()+1 && "Invalid child");
+      return Children[i];
+    }
+
+    static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
+  };
+
+} // namespace
+
+/// Destroy - A 'virtual' destructor.
+void DeltaTreeNode::Destroy() {
+  if (isLeaf())
+    delete this;
+  else
+    delete cast<DeltaTreeInteriorNode>(this);
+}
+
+/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
+/// local walk over our contained deltas.
+void DeltaTreeNode::RecomputeFullDeltaLocally() {
+  int NewFullDelta = 0;
+  for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
+    NewFullDelta += Values[i].Delta;
+  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this))
+    for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
+      NewFullDelta += IN->getChild(i)->getFullDelta();
+  FullDelta = NewFullDelta;
+}
+
+/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
+/// this node.  If insertion is easy, do it and return false.  Otherwise,
+/// split the node, populate InsertRes with info about the split, and return
+/// true.
+bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
+                                InsertResult *InsertRes) {
+  // Maintain full delta for this node.
+  FullDelta += Delta;
+
+  // Find the insertion point, the first delta whose index is >= FileIndex.
+  unsigned i = 0, e = getNumValuesUsed();
+  while (i != e && FileIndex > getValue(i).FileLoc)
+    ++i;
+
+  // If we found an a record for exactly this file index, just merge this
+  // value into the pre-existing record and finish early.
+  if (i != e && getValue(i).FileLoc == FileIndex) {
+    // NOTE: Delta could drop to zero here.  This means that the delta entry is
+    // useless and could be removed.  Supporting erases is more complex than
+    // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
+    // the tree.
+    Values[i].Delta += Delta;
+    return false;
+  }
+
+  // Otherwise, we found an insertion point, and we know that the value at the
+  // specified index is > FileIndex.  Handle the leaf case first.
+  if (isLeaf()) {
+    if (!isFull()) {
+      // For an insertion into a non-full leaf node, just insert the value in
+      // its sorted position.  This requires moving later values over.
+      if (i != e)
+        memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
+      Values[i] = SourceDelta::get(FileIndex, Delta);
+      ++NumValuesUsed;
+      return false;
+    }
+
+    // Otherwise, if this is leaf is full, split the node at its median, insert
+    // the value into one of the children, and return the result.
+    assert(InsertRes && "No result location specified");
+    DoSplit(*InsertRes);
+
+    if (InsertRes->Split.FileLoc > FileIndex)
+      InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
+    else
+      InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
+    return true;
+  }
+
+  // Otherwise, this is an interior node.  Send the request down the tree.
+  auto *IN = cast<DeltaTreeInteriorNode>(this);
+  if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
+    return false; // If there was space in the child, just return.
+
+  // Okay, this split the subtree, producing a new value and two children to
+  // insert here.  If this node is non-full, we can just insert it directly.
+  if (!isFull()) {
+    // Now that we have two nodes and a new element, insert the perclated value
+    // into ourself by moving all the later values/children down, then inserting
+    // the new one.
+    if (i != e)
+      memmove(&IN->Children[i+2], &IN->Children[i+1],
+              (e-i)*sizeof(IN->Children[0]));
+    IN->Children[i] = InsertRes->LHS;
+    IN->Children[i+1] = InsertRes->RHS;
+
+    if (e != i)
+      memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
+    Values[i] = InsertRes->Split;
+    ++NumValuesUsed;
+    return false;
+  }
+
+  // Finally, if this interior node was full and a node is percolated up, split
+  // ourself and return that up the chain.  Start by saving all our info to
+  // avoid having the split clobber it.
+  IN->Children[i] = InsertRes->LHS;
+  DeltaTreeNode *SubRHS = InsertRes->RHS;
+  SourceDelta SubSplit = InsertRes->Split;
+
+  // Do the split.
+  DoSplit(*InsertRes);
+
+  // Figure out where to insert SubRHS/NewSplit.
+  DeltaTreeInteriorNode *InsertSide;
+  if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
+    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
+  else
+    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
+
+  // We now have a non-empty interior node 'InsertSide' to insert
+  // SubRHS/SubSplit into.  Find out where to insert SubSplit.
+
+  // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
+  i = 0; e = InsertSide->getNumValuesUsed();
+  while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
+    ++i;
+
+  // Now we know that i is the place to insert the split value into.  Insert it
+  // and the child right after it.
+  if (i != e)
+    memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
+            (e-i)*sizeof(IN->Children[0]));
+  InsertSide->Children[i+1] = SubRHS;
+
+  if (e != i)
+    memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
+            (e-i)*sizeof(Values[0]));
+  InsertSide->Values[i] = SubSplit;
+  ++InsertSide->NumValuesUsed;
+  InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
+  return true;
+}
+
+/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
+/// into two subtrees each with "WidthFactor-1" values and a pivot value.
+/// Return the pieces in InsertRes.
+void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
+  assert(isFull() && "Why split a non-full node?");
+
+  // Since this node is full, it contains 2*WidthFactor-1 values.  We move
+  // the first 'WidthFactor-1' values to the LHS child (which we leave in this
+  // node), propagate one value up, and move the last 'WidthFactor-1' values
+  // into the RHS child.
+
+  // Create the new child node.
+  DeltaTreeNode *NewNode;
+  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
+    // If this is an interior node, also move over 'WidthFactor' children
+    // into the new node.
+    DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
+    memcpy(&New->Children[0], &IN->Children[WidthFactor],
+           WidthFactor*sizeof(IN->Children[0]));
+    NewNode = New;
+  } else {
+    // Just create the new leaf node.
+    NewNode = new DeltaTreeNode();
+  }
+
+  // Move over the last 'WidthFactor-1' values from here to NewNode.
+  memcpy(&NewNode->Values[0], &Values[WidthFactor],
+         (WidthFactor-1)*sizeof(Values[0]));
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
+
+  // Recompute the two nodes' full delta.
+  NewNode->RecomputeFullDeltaLocally();
+  RecomputeFullDeltaLocally();
+
+  InsertRes.LHS = this;
+  InsertRes.RHS = NewNode;
+  InsertRes.Split = Values[WidthFactor-1];
+}
+
+//===----------------------------------------------------------------------===//
+//                        DeltaTree Implementation
+//===----------------------------------------------------------------------===//
+
+//#define VERIFY_TREE
+
+#ifdef VERIFY_TREE
+/// VerifyTree - Walk the btree performing assertions on various properties to
+/// verify consistency.  This is useful for debugging new changes to the tree.
+static void VerifyTree(const DeltaTreeNode *N) {
+  const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N);
+  if (IN == 0) {
+    // Verify leaves, just ensure that FullDelta matches up and the elements
+    // are in proper order.
+    int FullDelta = 0;
+    for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
+      if (i)
+        assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
+      FullDelta += N->getValue(i).Delta;
+    }
+    assert(FullDelta == N->getFullDelta());
+    return;
+  }
+
+  // Verify interior nodes: Ensure that FullDelta matches up and the
+  // elements are in proper order and the children are in proper order.
+  int FullDelta = 0;
+  for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
+    const SourceDelta &IVal = N->getValue(i);
+    const DeltaTreeNode *IChild = IN->getChild(i);
+    if (i)
+      assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
+    FullDelta += IVal.Delta;
+    FullDelta += IChild->getFullDelta();
+
+    // The largest value in child #i should be smaller than FileLoc.
+    assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
+           IVal.FileLoc);
+
+    // The smallest value in child #i+1 should be larger than FileLoc.
+    assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
+    VerifyTree(IChild);
+  }
+
+  FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
+
+  assert(FullDelta == N->getFullDelta());
+}
+#endif  // VERIFY_TREE
+
+static DeltaTreeNode *getRoot(void *Root) {
+  return (DeltaTreeNode*)Root;
+}
+
+DeltaTree::DeltaTree() {
+  Root = new DeltaTreeNode();
+}
+
+DeltaTree::DeltaTree(const DeltaTree &RHS) {
+  // Currently we only support copying when the RHS is empty.
+  assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
+         "Can only copy empty tree");
+  Root = new DeltaTreeNode();
+}
+
+DeltaTree::~DeltaTree() {
+  getRoot(Root)->Destroy();
+}
+
+/// getDeltaAt - Return the accumulated delta at the specified file offset.
+/// This includes all insertions or delections that occurred *before* the
+/// specified file index.
+int DeltaTree::getDeltaAt(unsigned FileIndex) const {
+  const DeltaTreeNode *Node = getRoot(Root);
+
+  int Result = 0;
+
+  // Walk down the tree.
+  while (true) {
+    // For all nodes, include any local deltas before the specified file
+    // index by summing them up directly.  Keep track of how many were
+    // included.
+    unsigned NumValsGreater = 0;
+    for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
+         ++NumValsGreater) {
+      const SourceDelta &Val = Node->getValue(NumValsGreater);
+
+      if (Val.FileLoc >= FileIndex)
+        break;
+      Result += Val.Delta;
+    }
+
+    // If we have an interior node, include information about children and
+    // recurse.  Otherwise, if we have a leaf, we're done.
+    const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
+    if (!IN) return Result;
+
+    // Include any children to the left of the values we skipped, all of
+    // their deltas should be included as well.
+    for (unsigned i = 0; i != NumValsGreater; ++i)
+      Result += IN->getChild(i)->getFullDelta();
+
+    // If we found exactly the value we were looking for, break off the
+    // search early.  There is no need to search the RHS of the value for
+    // partial results.
+    if (NumValsGreater != Node->getNumValuesUsed() &&
+        Node->getValue(NumValsGreater).FileLoc == FileIndex)
+      return Result+IN->getChild(NumValsGreater)->getFullDelta();
+
+    // Otherwise, traverse down the tree.  The selected subtree may be
+    // partially included in the range.
+    Node = IN->getChild(NumValsGreater);
+  }
+  // NOT REACHED.
+}
+
+/// AddDelta - When a change is made that shifts around the text buffer,
+/// this method is used to record that info.  It inserts a delta of 'Delta'
+/// into the current DeltaTree at offset FileIndex.
+void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
+  assert(Delta && "Adding a noop?");
+  DeltaTreeNode *MyRoot = getRoot(Root);
+
+  DeltaTreeNode::InsertResult InsertRes;
+  if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
+    Root = new DeltaTreeInteriorNode(InsertRes);
+#ifdef VERIFY_TREE
+    MyRoot = Root;
+#endif
+  }
+
+#ifdef VERIFY_TREE
+  VerifyTree(MyRoot);
+#endif
+}
diff --git a/contrib/libs/clang16/lib/Rewrite/HTMLRewrite.cpp b/contrib/libs/clang16/lib/Rewrite/HTMLRewrite.cpp
new file mode 100644
index 0000000000..083a9c0929
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/HTMLRewrite.cpp
@@ -0,0 +1,669 @@
+//== HTMLRewrite.cpp - Translate source code into prettified HTML --*- C++ -*-//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the HTMLRewriter class, which is used to translate the
+//  text of a source file into prettified HTML.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/Core/HTMLRewrite.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Lex/Preprocessor.h"
+#include "clang/Lex/TokenConcatenation.h"
+#include "clang/Rewrite/Core/Rewriter.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+using namespace clang;
+
+
+/// HighlightRange - Highlight a range in the source code with the specified
+/// start/end tags.  B/E must be in the same file.  This ensures that
+/// start/end tags are placed at the start/end of each line if the range is
+/// multiline.
+void html::HighlightRange(Rewriter &R, SourceLocation B, SourceLocation E,
+                          const char *StartTag, const char *EndTag,
+                          bool IsTokenRange) {
+  SourceManager &SM = R.getSourceMgr();
+  B = SM.getExpansionLoc(B);
+  E = SM.getExpansionLoc(E);
+  FileID FID = SM.getFileID(B);
+  assert(SM.getFileID(E) == FID && "B/E not in the same file!");
+
+  unsigned BOffset = SM.getFileOffset(B);
+  unsigned EOffset = SM.getFileOffset(E);
+
+  // Include the whole end token in the range.
+  if (IsTokenRange)
+    EOffset += Lexer::MeasureTokenLength(E, R.getSourceMgr(), R.getLangOpts());
+
+  bool Invalid = false;
+  const char *BufferStart = SM.getBufferData(FID, &Invalid).data();
+  if (Invalid)
+    return;
+
+  HighlightRange(R.getEditBuffer(FID), BOffset, EOffset,
+                 BufferStart, StartTag, EndTag);
+}
+
+/// HighlightRange - This is the same as the above method, but takes
+/// decomposed file locations.
+void html::HighlightRange(RewriteBuffer &RB, unsigned B, unsigned E,
+                          const char *BufferStart,
+                          const char *StartTag, const char *EndTag) {
+  // Insert the tag at the absolute start/end of the range.
+  RB.InsertTextAfter(B, StartTag);
+  RB.InsertTextBefore(E, EndTag);
+
+  // Scan the range to see if there is a \r or \n.  If so, and if the line is
+  // not blank, insert tags on that line as well.
+  bool HadOpenTag = true;
+
+  unsigned LastNonWhiteSpace = B;
+  for (unsigned i = B; i != E; ++i) {
+    switch (BufferStart[i]) {
+    case '\r':
+    case '\n':
+      // Okay, we found a newline in the range.  If we have an open tag, we need
+      // to insert a close tag at the first non-whitespace before the newline.
+      if (HadOpenTag)
+        RB.InsertTextBefore(LastNonWhiteSpace+1, EndTag);
+
+      // Instead of inserting an open tag immediately after the newline, we
+      // wait until we see a non-whitespace character.  This prevents us from
+      // inserting tags around blank lines, and also allows the open tag to
+      // be put *after* whitespace on a non-blank line.
+      HadOpenTag = false;
+      break;
+    case '\0':
+    case ' ':
+    case '\t':
+    case '\f':
+    case '\v':
+      // Ignore whitespace.
+      break;
+
+    default:
+      // If there is no tag open, do it now.
+      if (!HadOpenTag) {
+        RB.InsertTextAfter(i, StartTag);
+        HadOpenTag = true;
+      }
+
+      // Remember this character.
+      LastNonWhiteSpace = i;
+      break;
+    }
+  }
+}
+
+void html::EscapeText(Rewriter &R, FileID FID,
+                      bool EscapeSpaces, bool ReplaceTabs) {
+
+  llvm::MemoryBufferRef Buf = R.getSourceMgr().getBufferOrFake(FID);
+  const char* C = Buf.getBufferStart();
+  const char* FileEnd = Buf.getBufferEnd();
+
+  assert (C <= FileEnd);
+
+  RewriteBuffer &RB = R.getEditBuffer(FID);
+
+  unsigned ColNo = 0;
+  for (unsigned FilePos = 0; C != FileEnd ; ++C, ++FilePos) {
+    switch (*C) {
+    default: ++ColNo; break;
+    case '\n':
+    case '\r':
+      ColNo = 0;
+      break;
+
+    case ' ':
+      if (EscapeSpaces)
+        RB.ReplaceText(FilePos, 1, "&nbsp;");
+      ++ColNo;
+      break;
+    case '\f':
+      RB.ReplaceText(FilePos, 1, "<hr>");
+      ColNo = 0;
+      break;
+
+    case '\t': {
+      if (!ReplaceTabs)
+        break;
+      unsigned NumSpaces = 8-(ColNo&7);
+      if (EscapeSpaces)
+        RB.ReplaceText(FilePos, 1,
+                       StringRef("&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"
+                                       "&nbsp;&nbsp;&nbsp;", 6*NumSpaces));
+      else
+        RB.ReplaceText(FilePos, 1, StringRef("        ", NumSpaces));
+      ColNo += NumSpaces;
+      break;
+    }
+    case '<':
+      RB.ReplaceText(FilePos, 1, "&lt;");
+      ++ColNo;
+      break;
+
+    case '>':
+      RB.ReplaceText(FilePos, 1, "&gt;");
+      ++ColNo;
+      break;
+
+    case '&':
+      RB.ReplaceText(FilePos, 1, "&amp;");
+      ++ColNo;
+      break;
+    }
+  }
+}
+
+std::string html::EscapeText(StringRef s, bool EscapeSpaces, bool ReplaceTabs) {
+
+  unsigned len = s.size();
+  std::string Str;
+  llvm::raw_string_ostream os(Str);
+
+  for (unsigned i = 0 ; i < len; ++i) {
+
+    char c = s[i];
+    switch (c) {
+    default:
+      os << c; break;
+
+    case ' ':
+      if (EscapeSpaces) os << "&nbsp;";
+      else os << ' ';
+      break;
+
+    case '\t':
+      if (ReplaceTabs) {
+        if (EscapeSpaces)
+          for (unsigned i = 0; i < 4; ++i)
+            os << "&nbsp;";
+        else
+          for (unsigned i = 0; i < 4; ++i)
+            os << " ";
+      }
+      else
+        os << c;
+
+      break;
+
+    case '<': os << "&lt;"; break;
+    case '>': os << "&gt;"; break;
+    case '&': os << "&amp;"; break;
+    }
+  }
+
+  return Str;
+}
+
+static void AddLineNumber(RewriteBuffer &RB, unsigned LineNo,
+                          unsigned B, unsigned E) {
+  SmallString<256> Str;
+  llvm::raw_svector_ostream OS(Str);
+
+  OS << "<tr class=\"codeline\" data-linenumber=\"" << LineNo << "\">"
+     << "<td class=\"num\" id=\"LN" << LineNo << "\">" << LineNo
+     << "</td><td class=\"line\">";
+
+  if (B == E) { // Handle empty lines.
+    OS << " </td></tr>";
+    RB.InsertTextBefore(B, OS.str());
+  } else {
+    RB.InsertTextBefore(B, OS.str());
+    RB.InsertTextBefore(E, "</td></tr>");
+  }
+}
+
+void html::AddLineNumbers(Rewriter& R, FileID FID) {
+
+  llvm::MemoryBufferRef Buf = R.getSourceMgr().getBufferOrFake(FID);
+  const char* FileBeg = Buf.getBufferStart();
+  const char* FileEnd = Buf.getBufferEnd();
+  const char* C = FileBeg;
+  RewriteBuffer &RB = R.getEditBuffer(FID);
+
+  assert (C <= FileEnd);
+
+  unsigned LineNo = 0;
+  unsigned FilePos = 0;
+
+  while (C != FileEnd) {
+
+    ++LineNo;
+    unsigned LineStartPos = FilePos;
+    unsigned LineEndPos = FileEnd - FileBeg;
+
+    assert (FilePos <= LineEndPos);
+    assert (C < FileEnd);
+
+    // Scan until the newline (or end-of-file).
+
+    while (C != FileEnd) {
+      char c = *C;
+      ++C;
+
+      if (c == '\n') {
+        LineEndPos = FilePos++;
+        break;
+      }
+
+      ++FilePos;
+    }
+
+    AddLineNumber(RB, LineNo, LineStartPos, LineEndPos);
+  }
+
+  // Add one big table tag that surrounds all of the code.
+  std::string s;
+  llvm::raw_string_ostream os(s);
+  os << "<table class=\"code\" data-fileid=\"" << FID.getHashValue() << "\">\n";
+  RB.InsertTextBefore(0, os.str());
+  RB.InsertTextAfter(FileEnd - FileBeg, "</table>");
+}
+
+void html::AddHeaderFooterInternalBuiltinCSS(Rewriter &R, FileID FID,
+                                             StringRef title) {
+
+  llvm::MemoryBufferRef Buf = R.getSourceMgr().getBufferOrFake(FID);
+  const char* FileStart = Buf.getBufferStart();
+  const char* FileEnd = Buf.getBufferEnd();
+
+  SourceLocation StartLoc = R.getSourceMgr().getLocForStartOfFile(FID);
+  SourceLocation EndLoc = StartLoc.getLocWithOffset(FileEnd-FileStart);
+
+  std::string s;
+  llvm::raw_string_ostream os(s);
+  os << "<!doctype html>\n" // Use HTML 5 doctype
+        "<html>\n<head>\n";
+
+  if (!title.empty())
+    os << "<title>" << html::EscapeText(title) << "</title>\n";
+
+  os << R"<<<(
+<style type="text/css">
+body { color:#000000; background-color:#ffffff }
+body { font-family:Helvetica, sans-serif; font-size:10pt }
+h1 { font-size:14pt }
+.FileName { margin-top: 5px; margin-bottom: 5px; display: inline; }
+.FileNav { margin-left: 5px; margin-right: 5px; display: inline; }
+.FileNav a { text-decoration:none; font-size: larger; }
+.divider { margin-top: 30px; margin-bottom: 30px; height: 15px; }
+.divider { background-color: gray; }
+.code { border-collapse:collapse; width:100%; }
+.code { font-family: "Monospace", monospace; font-size:10pt }
+.code { line-height: 1.2em }
+.comment { color: green; font-style: oblique }
+.keyword { color: blue }
+.string_literal { color: red }
+.directive { color: darkmagenta }
+
+/* Macros and variables could have pop-up notes hidden by default.
+  - Macro pop-up:    expansion of the macro
+  - Variable pop-up: value (table) of the variable */
+.macro_popup, .variable_popup { display: none; }
+
+/* Pop-up appears on mouse-hover event. */
+.macro:hover .macro_popup, .variable:hover .variable_popup {
+  display: block;
+  padding: 2px;
+  -webkit-border-radius:5px;
+  -webkit-box-shadow:1px 1px 7px #000;
+  border-radius:5px;
+  box-shadow:1px 1px 7px #000;
+  position: absolute;
+  top: -1em;
+  left:10em;
+  z-index: 1
+}
+
+.macro_popup {
+  border: 2px solid red;
+  background-color:#FFF0F0;
+  font-weight: normal;
+}
+
+.variable_popup {
+  border: 2px solid blue;
+  background-color:#F0F0FF;
+  font-weight: bold;
+  font-family: Helvetica, sans-serif;
+  font-size: 9pt;
+}
+
+/* Pop-up notes needs a relative position as a base where they pops up. */
+.macro, .variable {
+  background-color: PaleGoldenRod;
+  position: relative;
+}
+.macro { color: DarkMagenta; }
+
+#tooltiphint {
+  position: fixed;
+  width: 50em;
+  margin-left: -25em;
+  left: 50%;
+  padding: 10px;
+  border: 1px solid #b0b0b0;
+  border-radius: 2px;
+  box-shadow: 1px 1px 7px black;
+  background-color: #c0c0c0;
+  z-index: 2;
+}
+
+.num { width:2.5em; padding-right:2ex; background-color:#eeeeee }
+.num { text-align:right; font-size:8pt }
+.num { color:#444444 }
+.line { padding-left: 1ex; border-left: 3px solid #ccc }
+.line { white-space: pre }
+.msg { -webkit-box-shadow:1px 1px 7px #000 }
+.msg { box-shadow:1px 1px 7px #000 }
+.msg { -webkit-border-radius:5px }
+.msg { border-radius:5px }
+.msg { font-family:Helvetica, sans-serif; font-size:8pt }
+.msg { float:left }
+.msg { position:relative }
+.msg { padding:0.25em 1ex 0.25em 1ex }
+.msg { margin-top:10px; margin-bottom:10px }
+.msg { font-weight:bold }
+.msg { max-width:60em; word-wrap: break-word; white-space: pre-wrap }
+.msgT { padding:0x; spacing:0x }
+.msgEvent { background-color:#fff8b4; color:#000000 }
+.msgControl { background-color:#bbbbbb; color:#000000 }
+.msgNote { background-color:#ddeeff; color:#000000 }
+.mrange { background-color:#dfddf3 }
+.mrange { border-bottom:1px solid #6F9DBE }
+.PathIndex { font-weight: bold; padding:0px 5px; margin-right:5px; }
+.PathIndex { -webkit-border-radius:8px }
+.PathIndex { border-radius:8px }
+.PathIndexEvent { background-color:#bfba87 }
+.PathIndexControl { background-color:#8c8c8c }
+.PathIndexPopUp { background-color: #879abc; }
+.PathNav a { text-decoration:none; font-size: larger }
+.CodeInsertionHint { font-weight: bold; background-color: #10dd10 }
+.CodeRemovalHint { background-color:#de1010 }
+.CodeRemovalHint { border-bottom:1px solid #6F9DBE }
+.msg.selected{ background-color:orange !important; }
+
+table.simpletable {
+  padding: 5px;
+  font-size:12pt;
+  margin:20px;
+  border-collapse: collapse; border-spacing: 0px;
+}
+td.rowname {
+  text-align: right;
+  vertical-align: top;
+  font-weight: bold;
+  color:#444444;
+  padding-right:2ex;
+}
+
+/* Hidden text. */
+input.spoilerhider + label {
+  cursor: pointer;
+  text-decoration: underline;
+  display: block;
+}
+input.spoilerhider {
+ display: none;
+}
+input.spoilerhider ~ .spoiler {
+  overflow: hidden;
+  margin: 10px auto 0;
+  height: 0;
+  opacity: 0;
+}
+input.spoilerhider:checked + label + .spoiler{
+  height: auto;
+  opacity: 1;
+}
+</style>
+</head>
+<body>)<<<";
+
+  // Generate header
+  R.InsertTextBefore(StartLoc, os.str());
+  // Generate footer
+
+  R.InsertTextAfter(EndLoc, "</body></html>\n");
+}
+
+/// SyntaxHighlight - Relex the specified FileID and annotate the HTML with
+/// information about keywords, macro expansions etc.  This uses the macro
+/// table state from the end of the file, so it won't be perfectly perfect,
+/// but it will be reasonably close.
+void html::SyntaxHighlight(Rewriter &R, FileID FID, const Preprocessor &PP) {
+  RewriteBuffer &RB = R.getEditBuffer(FID);
+
+  const SourceManager &SM = PP.getSourceManager();
+  llvm::MemoryBufferRef FromFile = SM.getBufferOrFake(FID);
+  Lexer L(FID, FromFile, SM, PP.getLangOpts());
+  const char *BufferStart = L.getBuffer().data();
+
+  // Inform the preprocessor that we want to retain comments as tokens, so we
+  // can highlight them.
+  L.SetCommentRetentionState(true);
+
+  // Lex all the tokens in raw mode, to avoid entering #includes or expanding
+  // macros.
+  Token Tok;
+  L.LexFromRawLexer(Tok);
+
+  while (Tok.isNot(tok::eof)) {
+    // Since we are lexing unexpanded tokens, all tokens are from the main
+    // FileID.
+    unsigned TokOffs = SM.getFileOffset(Tok.getLocation());
+    unsigned TokLen = Tok.getLength();
+    switch (Tok.getKind()) {
+    default: break;
+    case tok::identifier:
+      llvm_unreachable("tok::identifier in raw lexing mode!");
+    case tok::raw_identifier: {
+      // Fill in Result.IdentifierInfo and update the token kind,
+      // looking up the identifier in the identifier table.
+      PP.LookUpIdentifierInfo(Tok);
+
+      // If this is a pp-identifier, for a keyword, highlight it as such.
+      if (Tok.isNot(tok::identifier))
+        HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                       "<span class='keyword'>", "</span>");
+      break;
+    }
+    case tok::comment:
+      HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                     "<span class='comment'>", "</span>");
+      break;
+    case tok::utf8_string_literal:
+      // Chop off the u part of u8 prefix
+      ++TokOffs;
+      --TokLen;
+      // FALL THROUGH to chop the 8
+      [[fallthrough]];
+    case tok::wide_string_literal:
+    case tok::utf16_string_literal:
+    case tok::utf32_string_literal:
+      // Chop off the L, u, U or 8 prefix
+      ++TokOffs;
+      --TokLen;
+      [[fallthrough]];
+    case tok::string_literal:
+      // FIXME: Exclude the optional ud-suffix from the highlighted range.
+      HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                     "<span class='string_literal'>", "</span>");
+      break;
+    case tok::hash: {
+      // If this is a preprocessor directive, all tokens to end of line are too.
+      if (!Tok.isAtStartOfLine())
+        break;
+
+      // Eat all of the tokens until we get to the next one at the start of
+      // line.
+      unsigned TokEnd = TokOffs+TokLen;
+      L.LexFromRawLexer(Tok);
+      while (!Tok.isAtStartOfLine() && Tok.isNot(tok::eof)) {
+        TokEnd = SM.getFileOffset(Tok.getLocation())+Tok.getLength();
+        L.LexFromRawLexer(Tok);
+      }
+
+      // Find end of line.  This is a hack.
+      HighlightRange(RB, TokOffs, TokEnd, BufferStart,
+                     "<span class='directive'>", "</span>");
+
+      // Don't skip the next token.
+      continue;
+    }
+    }
+
+    L.LexFromRawLexer(Tok);
+  }
+}
+
+/// HighlightMacros - This uses the macro table state from the end of the
+/// file, to re-expand macros and insert (into the HTML) information about the
+/// macro expansions.  This won't be perfectly perfect, but it will be
+/// reasonably close.
+void html::HighlightMacros(Rewriter &R, FileID FID, const Preprocessor& PP) {
+  // Re-lex the raw token stream into a token buffer.
+  const SourceManager &SM = PP.getSourceManager();
+  std::vector<Token> TokenStream;
+
+  llvm::MemoryBufferRef FromFile = SM.getBufferOrFake(FID);
+  Lexer L(FID, FromFile, SM, PP.getLangOpts());
+
+  // Lex all the tokens in raw mode, to avoid entering #includes or expanding
+  // macros.
+  while (true) {
+    Token Tok;
+    L.LexFromRawLexer(Tok);
+
+    // If this is a # at the start of a line, discard it from the token stream.
+    // We don't want the re-preprocess step to see #defines, #includes or other
+    // preprocessor directives.
+    if (Tok.is(tok::hash) && Tok.isAtStartOfLine())
+      continue;
+
+    // If this is a ## token, change its kind to unknown so that repreprocessing
+    // it will not produce an error.
+    if (Tok.is(tok::hashhash))
+      Tok.setKind(tok::unknown);
+
+    // If this raw token is an identifier, the raw lexer won't have looked up
+    // the corresponding identifier info for it.  Do this now so that it will be
+    // macro expanded when we re-preprocess it.
+    if (Tok.is(tok::raw_identifier))
+      PP.LookUpIdentifierInfo(Tok);
+
+    TokenStream.push_back(Tok);
+
+    if (Tok.is(tok::eof)) break;
+  }
+
+  // Temporarily change the diagnostics object so that we ignore any generated
+  // diagnostics from this pass.
+  DiagnosticsEngine TmpDiags(PP.getDiagnostics().getDiagnosticIDs(),
+                             &PP.getDiagnostics().getDiagnosticOptions(),
+                      new IgnoringDiagConsumer);
+
+  // FIXME: This is a huge hack; we reuse the input preprocessor because we want
+  // its state, but we aren't actually changing it (we hope). This should really
+  // construct a copy of the preprocessor.
+  Preprocessor &TmpPP = const_cast<Preprocessor&>(PP);
+  DiagnosticsEngine *OldDiags = &TmpPP.getDiagnostics();
+  TmpPP.setDiagnostics(TmpDiags);
+
+  // Inform the preprocessor that we don't want comments.
+  TmpPP.SetCommentRetentionState(false, false);
+
+  // We don't want pragmas either. Although we filtered out #pragma, removing
+  // _Pragma and __pragma is much harder.
+  bool PragmasPreviouslyEnabled = TmpPP.getPragmasEnabled();
+  TmpPP.setPragmasEnabled(false);
+
+  // Enter the tokens we just lexed.  This will cause them to be macro expanded
+  // but won't enter sub-files (because we removed #'s).
+  TmpPP.EnterTokenStream(TokenStream, false, /*IsReinject=*/false);
+
+  TokenConcatenation ConcatInfo(TmpPP);
+
+  // Lex all the tokens.
+  Token Tok;
+  TmpPP.Lex(Tok);
+  while (Tok.isNot(tok::eof)) {
+    // Ignore non-macro tokens.
+    if (!Tok.getLocation().isMacroID()) {
+      TmpPP.Lex(Tok);
+      continue;
+    }
+
+    // Okay, we have the first token of a macro expansion: highlight the
+    // expansion by inserting a start tag before the macro expansion and
+    // end tag after it.
+    CharSourceRange LLoc = SM.getExpansionRange(Tok.getLocation());
+
+    // Ignore tokens whose instantiation location was not the main file.
+    if (SM.getFileID(LLoc.getBegin()) != FID) {
+      TmpPP.Lex(Tok);
+      continue;
+    }
+
+    assert(SM.getFileID(LLoc.getEnd()) == FID &&
+           "Start and end of expansion must be in the same ultimate file!");
+
+    std::string Expansion = EscapeText(TmpPP.getSpelling(Tok));
+    unsigned LineLen = Expansion.size();
+
+    Token PrevPrevTok;
+    Token PrevTok = Tok;
+    // Okay, eat this token, getting the next one.
+    TmpPP.Lex(Tok);
+
+    // Skip all the rest of the tokens that are part of this macro
+    // instantiation.  It would be really nice to pop up a window with all the
+    // spelling of the tokens or something.
+    while (!Tok.is(tok::eof) &&
+           SM.getExpansionLoc(Tok.getLocation()) == LLoc.getBegin()) {
+      // Insert a newline if the macro expansion is getting large.
+      if (LineLen > 60) {
+        Expansion += "<br>";
+        LineLen = 0;
+      }
+
+      LineLen -= Expansion.size();
+
+      // If the tokens were already space separated, or if they must be to avoid
+      // them being implicitly pasted, add a space between them.
+      if (Tok.hasLeadingSpace() ||
+          ConcatInfo.AvoidConcat(PrevPrevTok, PrevTok, Tok))
+        Expansion += ' ';
+
+      // Escape any special characters in the token text.
+      Expansion += EscapeText(TmpPP.getSpelling(Tok));
+      LineLen += Expansion.size();
+
+      PrevPrevTok = PrevTok;
+      PrevTok = Tok;
+      TmpPP.Lex(Tok);
+    }
+
+    // Insert the 'macro_popup' as the end tag, so that multi-line macros all
+    // get highlighted.
+    Expansion = "<span class='macro_popup'>" + Expansion + "</span></span>";
+
+    HighlightRange(R, LLoc.getBegin(), LLoc.getEnd(), "<span class='macro'>",
+                   Expansion.c_str(), LLoc.isTokenRange());
+  }
+
+  // Restore the preprocessor's old state.
+  TmpPP.setDiagnostics(*OldDiags);
+  TmpPP.setPragmasEnabled(PragmasPreviouslyEnabled);
+}
diff --git a/contrib/libs/clang16/lib/Rewrite/RewriteRope.cpp b/contrib/libs/clang16/lib/Rewrite/RewriteRope.cpp
new file mode 100644
index 0000000000..980d0f01e2
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/RewriteRope.cpp
@@ -0,0 +1,806 @@
+//===- RewriteRope.cpp - Rope specialized for rewriter --------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file implements the RewriteRope class, which is a powerful string.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/Core/RewriteRope.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/Support/Casting.h"
+#include <algorithm>
+#include <cassert>
+#include <cstring>
+
+using namespace clang;
+
+/// RewriteRope is a "strong" string class, designed to make insertions and
+/// deletions in the middle of the string nearly constant time (really, they are
+/// O(log N), but with a very low constant factor).
+///
+/// The implementation of this datastructure is a conceptual linear sequence of
+/// RopePiece elements.  Each RopePiece represents a view on a separately
+/// allocated and reference counted string.  This means that splitting a very
+/// long string can be done in constant time by splitting a RopePiece that
+/// references the whole string into two rope pieces that reference each half.
+/// Once split, another string can be inserted in between the two halves by
+/// inserting a RopePiece in between the two others.  All of this is very
+/// inexpensive: it takes time proportional to the number of RopePieces, not the
+/// length of the strings they represent.
+///
+/// While a linear sequences of RopePieces is the conceptual model, the actual
+/// implementation captures them in an adapted B+ Tree.  Using a B+ tree (which
+/// is a tree that keeps the values in the leaves and has where each node
+/// contains a reasonable number of pointers to children/values) allows us to
+/// maintain efficient operation when the RewriteRope contains a *huge* number
+/// of RopePieces.  The basic idea of the B+ Tree is that it allows us to find
+/// the RopePiece corresponding to some offset very efficiently, and it
+/// automatically balances itself on insertions of RopePieces (which can happen
+/// for both insertions and erases of string ranges).
+///
+/// The one wrinkle on the theory is that we don't attempt to keep the tree
+/// properly balanced when erases happen.  Erases of string data can both insert
+/// new RopePieces (e.g. when the middle of some other rope piece is deleted,
+/// which results in two rope pieces, which is just like an insert) or it can
+/// reduce the number of RopePieces maintained by the B+Tree.  In the case when
+/// the number of RopePieces is reduced, we don't attempt to maintain the
+/// standard 'invariant' that each node in the tree contains at least
+/// 'WidthFactor' children/values.  For our use cases, this doesn't seem to
+/// matter.
+///
+/// The implementation below is primarily implemented in terms of three classes:
+///   RopePieceBTreeNode - Common base class for:
+///
+///     RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
+///          nodes.  This directly represents a chunk of the string with those
+///          RopePieces concatenated.
+///     RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
+///          up to '2*WidthFactor' other nodes in the tree.
+
+namespace {
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeNode Class
+//===----------------------------------------------------------------------===//
+
+  /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
+  /// RopePieceBTreeInterior.  This provides some 'virtual' dispatching methods
+  /// and a flag that determines which subclass the instance is.  Also
+  /// important, this node knows the full extend of the node, including any
+  /// children that it has.  This allows efficient skipping over entire subtrees
+  /// when looking for an offset in the BTree.
+  class RopePieceBTreeNode {
+  protected:
+    /// WidthFactor - This controls the number of K/V slots held in the BTree:
+    /// how wide it is.  Each level of the BTree is guaranteed to have at least
+    /// 'WidthFactor' elements in it (either ropepieces or children), (except
+    /// the root, which may have less) and may have at most 2*WidthFactor
+    /// elements.
+    enum { WidthFactor = 8 };
+
+    /// Size - This is the number of bytes of file this node (including any
+    /// potential children) covers.
+    unsigned Size = 0;
+
+    /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
+    /// is an instance of RopePieceBTreeInterior.
+    bool IsLeaf;
+
+    RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {}
+    ~RopePieceBTreeNode() = default;
+
+  public:
+    bool isLeaf() const { return IsLeaf; }
+    unsigned size() const { return Size; }
+
+    void Destroy();
+
+    /// split - Split the range containing the specified offset so that we are
+    /// guaranteed that there is a place to do an insertion at the specified
+    /// offset.  The offset is relative, so "0" is the start of the node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *split(unsigned Offset);
+
+    /// insert - Insert the specified ropepiece into this tree node at the
+    /// specified offset.  The offset is relative, so "0" is the start of the
+    /// node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
+
+    /// erase - Remove NumBytes from this node at the specified offset.  We are
+    /// guaranteed that there is a split at Offset.
+    void erase(unsigned Offset, unsigned NumBytes);
+  };
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeLeaf Class
+//===----------------------------------------------------------------------===//
+
+  /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
+  /// nodes.  This directly represents a chunk of the string with those
+  /// RopePieces concatenated.  Since this is a B+Tree, all values (in this case
+  /// instances of RopePiece) are stored in leaves like this.  To make iteration
+  /// over the leaves efficient, they maintain a singly linked list through the
+  /// NextLeaf field.  This allows the B+Tree forward iterator to be constant
+  /// time for all increments.
+  class RopePieceBTreeLeaf : public RopePieceBTreeNode {
+    /// NumPieces - This holds the number of rope pieces currently active in the
+    /// Pieces array.
+    unsigned char NumPieces = 0;
+
+    /// Pieces - This tracks the file chunks currently in this leaf.
+    RopePiece Pieces[2*WidthFactor];
+
+    /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
+    /// efficient in-order forward iteration of the tree without traversal.
+    RopePieceBTreeLeaf **PrevLeaf = nullptr;
+    RopePieceBTreeLeaf *NextLeaf = nullptr;
+
+  public:
+    RopePieceBTreeLeaf() : RopePieceBTreeNode(true) {}
+
+    ~RopePieceBTreeLeaf() {
+      if (PrevLeaf || NextLeaf)
+        removeFromLeafInOrder();
+      clear();
+    }
+
+    bool isFull() const { return NumPieces == 2*WidthFactor; }
+
+    /// clear - Remove all rope pieces from this leaf.
+    void clear() {
+      while (NumPieces)
+        Pieces[--NumPieces] = RopePiece();
+      Size = 0;
+    }
+
+    unsigned getNumPieces() const { return NumPieces; }
+
+    const RopePiece &getPiece(unsigned i) const {
+      assert(i < getNumPieces() && "Invalid piece ID");
+      return Pieces[i];
+    }
+
+    const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
+
+    void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
+      assert(!PrevLeaf && !NextLeaf && "Already in ordering");
+
+      NextLeaf = Node->NextLeaf;
+      if (NextLeaf)
+        NextLeaf->PrevLeaf = &NextLeaf;
+      PrevLeaf = &Node->NextLeaf;
+      Node->NextLeaf = this;
+    }
+
+    void removeFromLeafInOrder() {
+      if (PrevLeaf) {
+        *PrevLeaf = NextLeaf;
+        if (NextLeaf)
+          NextLeaf->PrevLeaf = PrevLeaf;
+      } else if (NextLeaf) {
+        NextLeaf->PrevLeaf = nullptr;
+      }
+    }
+
+    /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
+    /// summing the size of all RopePieces.
+    void FullRecomputeSizeLocally() {
+      Size = 0;
+      for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
+        Size += getPiece(i).size();
+    }
+
+    /// split - Split the range containing the specified offset so that we are
+    /// guaranteed that there is a place to do an insertion at the specified
+    /// offset.  The offset is relative, so "0" is the start of the node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *split(unsigned Offset);
+
+    /// insert - Insert the specified ropepiece into this tree node at the
+    /// specified offset.  The offset is relative, so "0" is the start of the
+    /// node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
+
+    /// erase - Remove NumBytes from this node at the specified offset.  We are
+    /// guaranteed that there is a split at Offset.
+    void erase(unsigned Offset, unsigned NumBytes);
+
+    static bool classof(const RopePieceBTreeNode *N) {
+      return N->isLeaf();
+    }
+  };
+
+} // namespace
+
+/// split - Split the range containing the specified offset so that we are
+/// guaranteed that there is a place to do an insertion at the specified
+/// offset.  The offset is relative, so "0" is the start of the node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
+  // Find the insertion point.  We are guaranteed that there is a split at the
+  // specified offset so find it.
+  if (Offset == 0 || Offset == size()) {
+    // Fastpath for a common case.  There is already a splitpoint at the end.
+    return nullptr;
+  }
+
+  // Find the piece that this offset lands in.
+  unsigned PieceOffs = 0;
+  unsigned i = 0;
+  while (Offset >= PieceOffs+Pieces[i].size()) {
+    PieceOffs += Pieces[i].size();
+    ++i;
+  }
+
+  // If there is already a split point at the specified offset, just return
+  // success.
+  if (PieceOffs == Offset)
+    return nullptr;
+
+  // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
+  // to being Piece relative.
+  unsigned IntraPieceOffset = Offset-PieceOffs;
+
+  // We do this by shrinking the RopePiece and then doing an insert of the tail.
+  RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
+                 Pieces[i].EndOffs);
+  Size -= Pieces[i].size();
+  Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
+  Size += Pieces[i].size();
+
+  return insert(Offset, Tail);
+}
+
+/// insert - Insert the specified RopePiece into this tree node at the
+/// specified offset.  The offset is relative, so "0" is the start of the node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
+                                               const RopePiece &R) {
+  // If this node is not full, insert the piece.
+  if (!isFull()) {
+    // Find the insertion point.  We are guaranteed that there is a split at the
+    // specified offset so find it.
+    unsigned i = 0, e = getNumPieces();
+    if (Offset == size()) {
+      // Fastpath for a common case.
+      i = e;
+    } else {
+      unsigned SlotOffs = 0;
+      for (; Offset > SlotOffs; ++i)
+        SlotOffs += getPiece(i).size();
+      assert(SlotOffs == Offset && "Split didn't occur before insertion!");
+    }
+
+    // For an insertion into a non-full leaf node, just insert the value in
+    // its sorted position.  This requires moving later values over.
+    for (; i != e; --e)
+      Pieces[e] = Pieces[e-1];
+    Pieces[i] = R;
+    ++NumPieces;
+    Size += R.size();
+    return nullptr;
+  }
+
+  // Otherwise, if this is leaf is full, split it in two halves.  Since this
+  // node is full, it contains 2*WidthFactor values.  We move the first
+  // 'WidthFactor' values to the LHS child (which we leave in this node) and
+  // move the last 'WidthFactor' values into the RHS child.
+
+  // Create the new node.
+  RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
+
+  // Move over the last 'WidthFactor' values from here to NewNode.
+  std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
+            &NewNode->Pieces[0]);
+  // Replace old pieces with null RopePieces to drop refcounts.
+  std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumPieces = NumPieces = WidthFactor;
+
+  // Recompute the two nodes' size.
+  NewNode->FullRecomputeSizeLocally();
+  FullRecomputeSizeLocally();
+
+  // Update the list of leaves.
+  NewNode->insertAfterLeafInOrder(this);
+
+  // These insertions can't fail.
+  if (this->size() >= Offset)
+    this->insert(Offset, R);
+  else
+    NewNode->insert(Offset - this->size(), R);
+  return NewNode;
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
+  // Since we are guaranteed that there is a split at Offset, we start by
+  // finding the Piece that starts there.
+  unsigned PieceOffs = 0;
+  unsigned i = 0;
+  for (; Offset > PieceOffs; ++i)
+    PieceOffs += getPiece(i).size();
+  assert(PieceOffs == Offset && "Split didn't occur before erase!");
+
+  unsigned StartPiece = i;
+
+  // Figure out how many pieces completely cover 'NumBytes'.  We want to remove
+  // all of them.
+  for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
+    PieceOffs += getPiece(i).size();
+
+  // If we exactly include the last one, include it in the region to delete.
+  if (Offset+NumBytes == PieceOffs+getPiece(i).size()) {
+    PieceOffs += getPiece(i).size();
+    ++i;
+  }
+
+  // If we completely cover some RopePieces, erase them now.
+  if (i != StartPiece) {
+    unsigned NumDeleted = i-StartPiece;
+    for (; i != getNumPieces(); ++i)
+      Pieces[i-NumDeleted] = Pieces[i];
+
+    // Drop references to dead rope pieces.
+    std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
+              RopePiece());
+    NumPieces -= NumDeleted;
+
+    unsigned CoverBytes = PieceOffs-Offset;
+    NumBytes -= CoverBytes;
+    Size -= CoverBytes;
+  }
+
+  // If we completely removed some stuff, we could be done.
+  if (NumBytes == 0) return;
+
+  // Okay, now might be erasing part of some Piece.  If this is the case, then
+  // move the start point of the piece.
+  assert(getPiece(StartPiece).size() > NumBytes);
+  Pieces[StartPiece].StartOffs += NumBytes;
+
+  // The size of this node just shrunk by NumBytes.
+  Size -= NumBytes;
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeInterior Class
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+  /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
+  /// which holds up to 2*WidthFactor pointers to child nodes.
+  class RopePieceBTreeInterior : public RopePieceBTreeNode {
+    /// NumChildren - This holds the number of children currently active in the
+    /// Children array.
+    unsigned char NumChildren = 0;
+
+    RopePieceBTreeNode *Children[2*WidthFactor];
+
+  public:
+    RopePieceBTreeInterior() : RopePieceBTreeNode(false) {}
+
+    RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
+        : RopePieceBTreeNode(false) {
+      Children[0] = LHS;
+      Children[1] = RHS;
+      NumChildren = 2;
+      Size = LHS->size() + RHS->size();
+    }
+
+    ~RopePieceBTreeInterior() {
+      for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+        Children[i]->Destroy();
+    }
+
+    bool isFull() const { return NumChildren == 2*WidthFactor; }
+
+    unsigned getNumChildren() const { return NumChildren; }
+
+    const RopePieceBTreeNode *getChild(unsigned i) const {
+      assert(i < NumChildren && "invalid child #");
+      return Children[i];
+    }
+
+    RopePieceBTreeNode *getChild(unsigned i) {
+      assert(i < NumChildren && "invalid child #");
+      return Children[i];
+    }
+
+    /// FullRecomputeSizeLocally - Recompute the Size field of this node by
+    /// summing up the sizes of the child nodes.
+    void FullRecomputeSizeLocally() {
+      Size = 0;
+      for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+        Size += getChild(i)->size();
+    }
+
+    /// split - Split the range containing the specified offset so that we are
+    /// guaranteed that there is a place to do an insertion at the specified
+    /// offset.  The offset is relative, so "0" is the start of the node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *split(unsigned Offset);
+
+    /// insert - Insert the specified ropepiece into this tree node at the
+    /// specified offset.  The offset is relative, so "0" is the start of the
+    /// node.
+    ///
+    /// If there is no space in this subtree for the extra piece, the extra tree
+    /// node is returned and must be inserted into a parent.
+    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
+
+    /// HandleChildPiece - A child propagated an insertion result up to us.
+    /// Insert the new child, and/or propagate the result further up the tree.
+    RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
+
+    /// erase - Remove NumBytes from this node at the specified offset.  We are
+    /// guaranteed that there is a split at Offset.
+    void erase(unsigned Offset, unsigned NumBytes);
+
+    static bool classof(const RopePieceBTreeNode *N) {
+      return !N->isLeaf();
+    }
+  };
+
+} // namespace
+
+/// split - Split the range containing the specified offset so that we are
+/// guaranteed that there is a place to do an insertion at the specified
+/// offset.  The offset is relative, so "0" is the start of the node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
+  // Figure out which child to split.
+  if (Offset == 0 || Offset == size())
+    return nullptr; // If we have an exact offset, we're already split.
+
+  unsigned ChildOffset = 0;
+  unsigned i = 0;
+  for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
+    ChildOffset += getChild(i)->size();
+
+  // If already split there, we're done.
+  if (ChildOffset == Offset)
+    return nullptr;
+
+  // Otherwise, recursively split the child.
+  if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
+    return HandleChildPiece(i, RHS);
+  return nullptr; // Done!
+}
+
+/// insert - Insert the specified ropepiece into this tree node at the
+/// specified offset.  The offset is relative, so "0" is the start of the
+/// node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
+                                                   const RopePiece &R) {
+  // Find the insertion point.  We are guaranteed that there is a split at the
+  // specified offset so find it.
+  unsigned i = 0, e = getNumChildren();
+
+  unsigned ChildOffs = 0;
+  if (Offset == size()) {
+    // Fastpath for a common case.  Insert at end of last child.
+    i = e-1;
+    ChildOffs = size()-getChild(i)->size();
+  } else {
+    for (; Offset > ChildOffs+getChild(i)->size(); ++i)
+      ChildOffs += getChild(i)->size();
+  }
+
+  Size += R.size();
+
+  // Insert at the end of this child.
+  if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
+    return HandleChildPiece(i, RHS);
+
+  return nullptr;
+}
+
+/// HandleChildPiece - A child propagated an insertion result up to us.
+/// Insert the new child, and/or propagate the result further up the tree.
+RopePieceBTreeNode *
+RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
+  // Otherwise the child propagated a subtree up to us as a new child.  See if
+  // we have space for it here.
+  if (!isFull()) {
+    // Insert RHS after child 'i'.
+    if (i + 1 != getNumChildren())
+      memmove(&Children[i+2], &Children[i+1],
+              (getNumChildren()-i-1)*sizeof(Children[0]));
+    Children[i+1] = RHS;
+    ++NumChildren;
+    return nullptr;
+  }
+
+  // Okay, this node is full.  Split it in half, moving WidthFactor children to
+  // a newly allocated interior node.
+
+  // Create the new node.
+  RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
+
+  // Move over the last 'WidthFactor' values from here to NewNode.
+  memcpy(&NewNode->Children[0], &Children[WidthFactor],
+         WidthFactor*sizeof(Children[0]));
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumChildren = NumChildren = WidthFactor;
+
+  // Finally, insert the two new children in the side the can (now) hold them.
+  // These insertions can't fail.
+  if (i < WidthFactor)
+    this->HandleChildPiece(i, RHS);
+  else
+    NewNode->HandleChildPiece(i-WidthFactor, RHS);
+
+  // Recompute the two nodes' size.
+  NewNode->FullRecomputeSizeLocally();
+  FullRecomputeSizeLocally();
+  return NewNode;
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
+  // This will shrink this node by NumBytes.
+  Size -= NumBytes;
+
+  // Find the first child that overlaps with Offset.
+  unsigned i = 0;
+  for (; Offset >= getChild(i)->size(); ++i)
+    Offset -= getChild(i)->size();
+
+  // Propagate the delete request into overlapping children, or completely
+  // delete the children as appropriate.
+  while (NumBytes) {
+    RopePieceBTreeNode *CurChild = getChild(i);
+
+    // If we are deleting something contained entirely in the child, pass on the
+    // request.
+    if (Offset+NumBytes < CurChild->size()) {
+      CurChild->erase(Offset, NumBytes);
+      return;
+    }
+
+    // If this deletion request starts somewhere in the middle of the child, it
+    // must be deleting to the end of the child.
+    if (Offset) {
+      unsigned BytesFromChild = CurChild->size()-Offset;
+      CurChild->erase(Offset, BytesFromChild);
+      NumBytes -= BytesFromChild;
+      // Start at the beginning of the next child.
+      Offset = 0;
+      ++i;
+      continue;
+    }
+
+    // If the deletion request completely covers the child, delete it and move
+    // the rest down.
+    NumBytes -= CurChild->size();
+    CurChild->Destroy();
+    --NumChildren;
+    if (i != getNumChildren())
+      memmove(&Children[i], &Children[i+1],
+              (getNumChildren()-i)*sizeof(Children[0]));
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeNode Implementation
+//===----------------------------------------------------------------------===//
+
+void RopePieceBTreeNode::Destroy() {
+  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    delete Leaf;
+  else
+    delete cast<RopePieceBTreeInterior>(this);
+}
+
+/// split - Split the range containing the specified offset so that we are
+/// guaranteed that there is a place to do an insertion at the specified
+/// offset.  The offset is relative, so "0" is the start of the node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
+  assert(Offset <= size() && "Invalid offset to split!");
+  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->split(Offset);
+  return cast<RopePieceBTreeInterior>(this)->split(Offset);
+}
+
+/// insert - Insert the specified ropepiece into this tree node at the
+/// specified offset.  The offset is relative, so "0" is the start of the
+/// node.
+///
+/// If there is no space in this subtree for the extra piece, the extra tree
+/// node is returned and must be inserted into a parent.
+RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
+                                               const RopePiece &R) {
+  assert(Offset <= size() && "Invalid offset to insert!");
+  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->insert(Offset, R);
+  return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
+  assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
+  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->erase(Offset, NumBytes);
+  return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeIterator Implementation
+//===----------------------------------------------------------------------===//
+
+static const RopePieceBTreeLeaf *getCN(const void *P) {
+  return static_cast<const RopePieceBTreeLeaf*>(P);
+}
+
+// begin iterator.
+RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
+  const auto *N = static_cast<const RopePieceBTreeNode *>(n);
+
+  // Walk down the left side of the tree until we get to a leaf.
+  while (const auto *IN = dyn_cast<RopePieceBTreeInterior>(N))
+    N = IN->getChild(0);
+
+  // We must have at least one leaf.
+  CurNode = cast<RopePieceBTreeLeaf>(N);
+
+  // If we found a leaf that happens to be empty, skip over it until we get
+  // to something full.
+  while (CurNode && getCN(CurNode)->getNumPieces() == 0)
+    CurNode = getCN(CurNode)->getNextLeafInOrder();
+
+  if (CurNode)
+    CurPiece = &getCN(CurNode)->getPiece(0);
+  else  // Empty tree, this is an end() iterator.
+    CurPiece = nullptr;
+  CurChar = 0;
+}
+
+void RopePieceBTreeIterator::MoveToNextPiece() {
+  if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
+    CurChar = 0;
+    ++CurPiece;
+    return;
+  }
+
+  // Find the next non-empty leaf node.
+  do
+    CurNode = getCN(CurNode)->getNextLeafInOrder();
+  while (CurNode && getCN(CurNode)->getNumPieces() == 0);
+
+  if (CurNode)
+    CurPiece = &getCN(CurNode)->getPiece(0);
+  else // Hit end().
+    CurPiece = nullptr;
+  CurChar = 0;
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTree Implementation
+//===----------------------------------------------------------------------===//
+
+static RopePieceBTreeNode *getRoot(void *P) {
+  return static_cast<RopePieceBTreeNode*>(P);
+}
+
+RopePieceBTree::RopePieceBTree() {
+  Root = new RopePieceBTreeLeaf();
+}
+
+RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
+  assert(RHS.empty() && "Can't copy non-empty tree yet");
+  Root = new RopePieceBTreeLeaf();
+}
+
+RopePieceBTree::~RopePieceBTree() {
+  getRoot(Root)->Destroy();
+}
+
+unsigned RopePieceBTree::size() const {
+  return getRoot(Root)->size();
+}
+
+void RopePieceBTree::clear() {
+  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
+    Leaf->clear();
+  else {
+    getRoot(Root)->Destroy();
+    Root = new RopePieceBTreeLeaf();
+  }
+}
+
+void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
+  // #1. Split at Offset.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+
+  // #2. Do the insertion.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+}
+
+void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
+  // #1. Split at Offset.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+
+  // #2. Do the erasing.
+  getRoot(Root)->erase(Offset, NumBytes);
+}
+
+//===----------------------------------------------------------------------===//
+// RewriteRope Implementation
+//===----------------------------------------------------------------------===//
+
+/// MakeRopeString - This copies the specified byte range into some instance of
+/// RopeRefCountString, and return a RopePiece that represents it.  This uses
+/// the AllocBuffer object to aggregate requests for small strings into one
+/// allocation instead of doing tons of tiny allocations.
+RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
+  unsigned Len = End-Start;
+  assert(Len && "Zero length RopePiece is invalid!");
+
+  // If we have space for this string in the current alloc buffer, use it.
+  if (AllocOffs+Len <= AllocChunkSize) {
+    memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
+    AllocOffs += Len;
+    return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
+  }
+
+  // If we don't have enough room because this specific allocation is huge,
+  // just allocate a new rope piece for it alone.
+  if (Len > AllocChunkSize) {
+    unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
+    auto *Res = reinterpret_cast<RopeRefCountString *>(new char[Size]);
+    Res->RefCount = 0;
+    memcpy(Res->Data, Start, End-Start);
+    return RopePiece(Res, 0, End-Start);
+  }
+
+  // Otherwise, this was a small request but we just don't have space for it
+  // Make a new chunk and share it with later allocations.
+
+  unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
+  auto *Res = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
+  Res->RefCount = 0;
+  memcpy(Res->Data, Start, Len);
+  AllocBuffer = Res;
+  AllocOffs = Len;
+
+  return RopePiece(AllocBuffer, 0, Len);
+}
diff --git a/contrib/libs/clang16/lib/Rewrite/Rewriter.cpp b/contrib/libs/clang16/lib/Rewrite/Rewriter.cpp
new file mode 100644
index 0000000000..8950bfb7c4
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/Rewriter.cpp
@@ -0,0 +1,478 @@
+//===- Rewriter.cpp - Code rewriting interface ----------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the Rewriter class, which is used for code
+//  transformations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/Core/Rewriter.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/DiagnosticIDs.h"
+#include "clang/Basic/FileManager.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Rewrite/Core/RewriteBuffer.h"
+#include "clang/Rewrite/Core/RewriteRope.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <iterator>
+#include <map>
+#include <memory>
+#include <system_error>
+#include <utility>
+
+using namespace clang;
+
+raw_ostream &RewriteBuffer::write(raw_ostream &os) const {
+  // Walk RewriteRope chunks efficiently using MoveToNextPiece() instead of the
+  // character iterator.
+  for (RopePieceBTreeIterator I = begin(), E = end(); I != E;
+       I.MoveToNextPiece())
+    os << I.piece();
+  return os;
+}
+
+/// Return true if this character is non-new-line whitespace:
+/// ' ', '\\t', '\\f', '\\v', '\\r'.
+static inline bool isWhitespaceExceptNL(unsigned char c) {
+  switch (c) {
+  case ' ':
+  case '\t':
+  case '\f':
+  case '\v':
+  case '\r':
+    return true;
+  default:
+    return false;
+  }
+}
+
+void RewriteBuffer::RemoveText(unsigned OrigOffset, unsigned Size,
+                               bool removeLineIfEmpty) {
+  // Nothing to remove, exit early.
+  if (Size == 0) return;
+
+  unsigned RealOffset = getMappedOffset(OrigOffset, true);
+  assert(RealOffset+Size <= Buffer.size() && "Invalid location");
+
+  // Remove the dead characters.
+  Buffer.erase(RealOffset, Size);
+
+  // Add a delta so that future changes are offset correctly.
+  AddReplaceDelta(OrigOffset, -Size);
+
+  if (removeLineIfEmpty) {
+    // Find the line that the remove occurred and if it is completely empty
+    // remove the line as well.
+
+    iterator curLineStart = begin();
+    unsigned curLineStartOffs = 0;
+    iterator posI = begin();
+    for (unsigned i = 0; i != RealOffset; ++i) {
+      if (*posI == '\n') {
+        curLineStart = posI;
+        ++curLineStart;
+        curLineStartOffs = i + 1;
+      }
+      ++posI;
+    }
+
+    unsigned lineSize = 0;
+    posI = curLineStart;
+    while (posI != end() && isWhitespaceExceptNL(*posI)) {
+      ++posI;
+      ++lineSize;
+    }
+    if (posI != end() && *posI == '\n') {
+      Buffer.erase(curLineStartOffs, lineSize + 1/* + '\n'*/);
+      // FIXME: Here, the offset of the start of the line is supposed to be
+      // expressed in terms of the original input not the "real" rewrite
+      // buffer.  How do we compute that reliably?  It might be tempting to use
+      // curLineStartOffs + OrigOffset - RealOffset, but that assumes the
+      // difference between the original and real offset is the same at the
+      // removed text and at the start of the line, but that's not true if
+      // edits were previously made earlier on the line.  This bug is also
+      // documented by a FIXME on the definition of
+      // clang::Rewriter::RewriteOptions::RemoveLineIfEmpty.  A reproducer for
+      // the implementation below is the test RemoveLineIfEmpty in
+      // clang/unittests/Rewrite/RewriteBufferTest.cpp.
+      AddReplaceDelta(curLineStartOffs, -(lineSize + 1/* + '\n'*/));
+    }
+  }
+}
+
+void RewriteBuffer::InsertText(unsigned OrigOffset, StringRef Str,
+                               bool InsertAfter) {
+  // Nothing to insert, exit early.
+  if (Str.empty()) return;
+
+  unsigned RealOffset = getMappedOffset(OrigOffset, InsertAfter);
+  Buffer.insert(RealOffset, Str.begin(), Str.end());
+
+  // Add a delta so that future changes are offset correctly.
+  AddInsertDelta(OrigOffset, Str.size());
+}
+
+/// ReplaceText - This method replaces a range of characters in the input
+/// buffer with a new string.  This is effectively a combined "remove+insert"
+/// operation.
+void RewriteBuffer::ReplaceText(unsigned OrigOffset, unsigned OrigLength,
+                                StringRef NewStr) {
+  unsigned RealOffset = getMappedOffset(OrigOffset, true);
+  Buffer.erase(RealOffset, OrigLength);
+  Buffer.insert(RealOffset, NewStr.begin(), NewStr.end());
+  if (OrigLength != NewStr.size())
+    AddReplaceDelta(OrigOffset, NewStr.size() - OrigLength);
+}
+
+//===----------------------------------------------------------------------===//
+// Rewriter class
+//===----------------------------------------------------------------------===//
+
+/// getRangeSize - Return the size in bytes of the specified range if they
+/// are in the same file.  If not, this returns -1.
+int Rewriter::getRangeSize(const CharSourceRange &Range,
+                           RewriteOptions opts) const {
+  if (!isRewritable(Range.getBegin()) ||
+      !isRewritable(Range.getEnd())) return -1;
+
+  FileID StartFileID, EndFileID;
+  unsigned StartOff = getLocationOffsetAndFileID(Range.getBegin(), StartFileID);
+  unsigned EndOff = getLocationOffsetAndFileID(Range.getEnd(), EndFileID);
+
+  if (StartFileID != EndFileID)
+    return -1;
+
+  // If edits have been made to this buffer, the delta between the range may
+  // have changed.
+  std::map<FileID, RewriteBuffer>::const_iterator I =
+    RewriteBuffers.find(StartFileID);
+  if (I != RewriteBuffers.end()) {
+    const RewriteBuffer &RB = I->second;
+    EndOff = RB.getMappedOffset(EndOff, opts.IncludeInsertsAtEndOfRange);
+    StartOff = RB.getMappedOffset(StartOff, !opts.IncludeInsertsAtBeginOfRange);
+  }
+
+  // Adjust the end offset to the end of the last token, instead of being the
+  // start of the last token if this is a token range.
+  if (Range.isTokenRange())
+    EndOff += Lexer::MeasureTokenLength(Range.getEnd(), *SourceMgr, *LangOpts);
+
+  return EndOff-StartOff;
+}
+
+int Rewriter::getRangeSize(SourceRange Range, RewriteOptions opts) const {
+  return getRangeSize(CharSourceRange::getTokenRange(Range), opts);
+}
+
+/// getRewrittenText - Return the rewritten form of the text in the specified
+/// range.  If the start or end of the range was unrewritable or if they are
+/// in different buffers, this returns an empty string.
+///
+/// Note that this method is not particularly efficient.
+std::string Rewriter::getRewrittenText(CharSourceRange Range) const {
+  if (!isRewritable(Range.getBegin()) ||
+      !isRewritable(Range.getEnd()))
+    return {};
+
+  FileID StartFileID, EndFileID;
+  unsigned StartOff, EndOff;
+  StartOff = getLocationOffsetAndFileID(Range.getBegin(), StartFileID);
+  EndOff   = getLocationOffsetAndFileID(Range.getEnd(), EndFileID);
+
+  if (StartFileID != EndFileID)
+    return {}; // Start and end in different buffers.
+
+  // If edits have been made to this buffer, the delta between the range may
+  // have changed.
+  std::map<FileID, RewriteBuffer>::const_iterator I =
+    RewriteBuffers.find(StartFileID);
+  if (I == RewriteBuffers.end()) {
+    // If the buffer hasn't been rewritten, just return the text from the input.
+    const char *Ptr = SourceMgr->getCharacterData(Range.getBegin());
+
+    // Adjust the end offset to the end of the last token, instead of being the
+    // start of the last token.
+    if (Range.isTokenRange())
+      EndOff +=
+          Lexer::MeasureTokenLength(Range.getEnd(), *SourceMgr, *LangOpts);
+    return std::string(Ptr, Ptr+EndOff-StartOff);
+  }
+
+  const RewriteBuffer &RB = I->second;
+  EndOff = RB.getMappedOffset(EndOff, true);
+  StartOff = RB.getMappedOffset(StartOff);
+
+  // Adjust the end offset to the end of the last token, instead of being the
+  // start of the last token.
+  if (Range.isTokenRange())
+    EndOff += Lexer::MeasureTokenLength(Range.getEnd(), *SourceMgr, *LangOpts);
+
+  // Advance the iterators to the right spot, yay for linear time algorithms.
+  RewriteBuffer::iterator Start = RB.begin();
+  std::advance(Start, StartOff);
+  RewriteBuffer::iterator End = Start;
+  assert(EndOff >= StartOff && "Invalid iteration distance");
+  std::advance(End, EndOff-StartOff);
+
+  return std::string(Start, End);
+}
+
+unsigned Rewriter::getLocationOffsetAndFileID(SourceLocation Loc,
+                                              FileID &FID) const {
+  assert(Loc.isValid() && "Invalid location");
+  std::pair<FileID, unsigned> V = SourceMgr->getDecomposedLoc(Loc);
+  FID = V.first;
+  return V.second;
+}
+
+/// getEditBuffer - Get or create a RewriteBuffer for the specified FileID.
+RewriteBuffer &Rewriter::getEditBuffer(FileID FID) {
+  std::map<FileID, RewriteBuffer>::iterator I =
+    RewriteBuffers.lower_bound(FID);
+  if (I != RewriteBuffers.end() && I->first == FID)
+    return I->second;
+  I = RewriteBuffers.insert(I, std::make_pair(FID, RewriteBuffer()));
+
+  StringRef MB = SourceMgr->getBufferData(FID);
+  I->second.Initialize(MB.begin(), MB.end());
+
+  return I->second;
+}
+
+/// InsertText - Insert the specified string at the specified location in the
+/// original buffer.
+bool Rewriter::InsertText(SourceLocation Loc, StringRef Str,
+                          bool InsertAfter, bool indentNewLines) {
+  if (!isRewritable(Loc)) return true;
+  FileID FID;
+  unsigned StartOffs = getLocationOffsetAndFileID(Loc, FID);
+
+  SmallString<128> indentedStr;
+  if (indentNewLines && Str.contains('\n')) {
+    StringRef MB = SourceMgr->getBufferData(FID);
+
+    unsigned lineNo = SourceMgr->getLineNumber(FID, StartOffs) - 1;
+    const SrcMgr::ContentCache *Content =
+        &SourceMgr->getSLocEntry(FID).getFile().getContentCache();
+    unsigned lineOffs = Content->SourceLineCache[lineNo];
+
+    // Find the whitespace at the start of the line.
+    StringRef indentSpace;
+    {
+      unsigned i = lineOffs;
+      while (isWhitespaceExceptNL(MB[i]))
+        ++i;
+      indentSpace = MB.substr(lineOffs, i-lineOffs);
+    }
+
+    SmallVector<StringRef, 4> lines;
+    Str.split(lines, "\n");
+
+    for (unsigned i = 0, e = lines.size(); i != e; ++i) {
+      indentedStr += lines[i];
+      if (i < e-1) {
+        indentedStr += '\n';
+        indentedStr += indentSpace;
+      }
+    }
+    Str = indentedStr.str();
+  }
+
+  getEditBuffer(FID).InsertText(StartOffs, Str, InsertAfter);
+  return false;
+}
+
+bool Rewriter::InsertTextAfterToken(SourceLocation Loc, StringRef Str) {
+  if (!isRewritable(Loc)) return true;
+  FileID FID;
+  unsigned StartOffs = getLocationOffsetAndFileID(Loc, FID);
+  RewriteOptions rangeOpts;
+  rangeOpts.IncludeInsertsAtBeginOfRange = false;
+  StartOffs += getRangeSize(SourceRange(Loc, Loc), rangeOpts);
+  getEditBuffer(FID).InsertText(StartOffs, Str, /*InsertAfter*/true);
+  return false;
+}
+
+/// RemoveText - Remove the specified text region.
+bool Rewriter::RemoveText(SourceLocation Start, unsigned Length,
+                          RewriteOptions opts) {
+  if (!isRewritable(Start)) return true;
+  FileID FID;
+  unsigned StartOffs = getLocationOffsetAndFileID(Start, FID);
+  getEditBuffer(FID).RemoveText(StartOffs, Length, opts.RemoveLineIfEmpty);
+  return false;
+}
+
+/// ReplaceText - This method replaces a range of characters in the input
+/// buffer with a new string.  This is effectively a combined "remove/insert"
+/// operation.
+bool Rewriter::ReplaceText(SourceLocation Start, unsigned OrigLength,
+                           StringRef NewStr) {
+  if (!isRewritable(Start)) return true;
+  FileID StartFileID;
+  unsigned StartOffs = getLocationOffsetAndFileID(Start, StartFileID);
+
+  getEditBuffer(StartFileID).ReplaceText(StartOffs, OrigLength, NewStr);
+  return false;
+}
+
+bool Rewriter::ReplaceText(SourceRange range, SourceRange replacementRange) {
+  if (!isRewritable(range.getBegin())) return true;
+  if (!isRewritable(range.getEnd())) return true;
+  if (replacementRange.isInvalid()) return true;
+  SourceLocation start = range.getBegin();
+  unsigned origLength = getRangeSize(range);
+  unsigned newLength = getRangeSize(replacementRange);
+  FileID FID;
+  unsigned newOffs = getLocationOffsetAndFileID(replacementRange.getBegin(),
+                                                FID);
+  StringRef MB = SourceMgr->getBufferData(FID);
+  return ReplaceText(start, origLength, MB.substr(newOffs, newLength));
+}
+
+bool Rewriter::IncreaseIndentation(CharSourceRange range,
+                                   SourceLocation parentIndent) {
+  if (range.isInvalid()) return true;
+  if (!isRewritable(range.getBegin())) return true;
+  if (!isRewritable(range.getEnd())) return true;
+  if (!isRewritable(parentIndent)) return true;
+
+  FileID StartFileID, EndFileID, parentFileID;
+  unsigned StartOff, EndOff, parentOff;
+
+  StartOff = getLocationOffsetAndFileID(range.getBegin(), StartFileID);
+  EndOff   = getLocationOffsetAndFileID(range.getEnd(), EndFileID);
+  parentOff = getLocationOffsetAndFileID(parentIndent, parentFileID);
+
+  if (StartFileID != EndFileID || StartFileID != parentFileID)
+    return true;
+  if (StartOff > EndOff)
+    return true;
+
+  FileID FID = StartFileID;
+  StringRef MB = SourceMgr->getBufferData(FID);
+
+  unsigned parentLineNo = SourceMgr->getLineNumber(FID, parentOff) - 1;
+  unsigned startLineNo = SourceMgr->getLineNumber(FID, StartOff) - 1;
+  unsigned endLineNo = SourceMgr->getLineNumber(FID, EndOff) - 1;
+
+  const SrcMgr::ContentCache *Content =
+      &SourceMgr->getSLocEntry(FID).getFile().getContentCache();
+
+  // Find where the lines start.
+  unsigned parentLineOffs = Content->SourceLineCache[parentLineNo];
+  unsigned startLineOffs = Content->SourceLineCache[startLineNo];
+
+  // Find the whitespace at the start of each line.
+  StringRef parentSpace, startSpace;
+  {
+    unsigned i = parentLineOffs;
+    while (isWhitespaceExceptNL(MB[i]))
+      ++i;
+    parentSpace = MB.substr(parentLineOffs, i-parentLineOffs);
+
+    i = startLineOffs;
+    while (isWhitespaceExceptNL(MB[i]))
+      ++i;
+    startSpace = MB.substr(startLineOffs, i-startLineOffs);
+  }
+  if (parentSpace.size() >= startSpace.size())
+    return true;
+  if (!startSpace.startswith(parentSpace))
+    return true;
+
+  StringRef indent = startSpace.substr(parentSpace.size());
+
+  // Indent the lines between start/end offsets.
+  RewriteBuffer &RB = getEditBuffer(FID);
+  for (unsigned lineNo = startLineNo; lineNo <= endLineNo; ++lineNo) {
+    unsigned offs = Content->SourceLineCache[lineNo];
+    unsigned i = offs;
+    while (isWhitespaceExceptNL(MB[i]))
+      ++i;
+    StringRef origIndent = MB.substr(offs, i-offs);
+    if (origIndent.startswith(startSpace))
+      RB.InsertText(offs, indent, /*InsertAfter=*/false);
+  }
+
+  return false;
+}
+
+namespace {
+
+// A wrapper for a file stream that atomically overwrites the target.
+//
+// Creates a file output stream for a temporary file in the constructor,
+// which is later accessible via getStream() if ok() return true.
+// Flushes the stream and moves the temporary file to the target location
+// in the destructor.
+class AtomicallyMovedFile {
+public:
+  AtomicallyMovedFile(DiagnosticsEngine &Diagnostics, StringRef Filename,
+                      bool &AllWritten)
+      : Diagnostics(Diagnostics), Filename(Filename), AllWritten(AllWritten) {
+    TempFilename = Filename;
+    TempFilename += "-%%%%%%%%";
+    int FD;
+    if (llvm::sys::fs::createUniqueFile(TempFilename, FD, TempFilename)) {
+      AllWritten = false;
+      Diagnostics.Report(clang::diag::err_unable_to_make_temp)
+        << TempFilename;
+    } else {
+      FileStream.reset(new llvm::raw_fd_ostream(FD, /*shouldClose=*/true));
+    }
+  }
+
+  ~AtomicallyMovedFile() {
+    if (!ok()) return;
+
+    // Close (will also flush) theFileStream.
+    FileStream->close();
+    if (std::error_code ec = llvm::sys::fs::rename(TempFilename, Filename)) {
+      AllWritten = false;
+      Diagnostics.Report(clang::diag::err_unable_to_rename_temp)
+        << TempFilename << Filename << ec.message();
+      // If the remove fails, there's not a lot we can do - this is already an
+      // error.
+      llvm::sys::fs::remove(TempFilename);
+    }
+  }
+
+  bool ok() { return (bool)FileStream; }
+  raw_ostream &getStream() { return *FileStream; }
+
+private:
+  DiagnosticsEngine &Diagnostics;
+  StringRef Filename;
+  SmallString<128> TempFilename;
+  std::unique_ptr<llvm::raw_fd_ostream> FileStream;
+  bool &AllWritten;
+};
+
+} // namespace
+
+bool Rewriter::overwriteChangedFiles() {
+  bool AllWritten = true;
+  for (buffer_iterator I = buffer_begin(), E = buffer_end(); I != E; ++I) {
+    const FileEntry *Entry =
+        getSourceMgr().getFileEntryForID(I->first);
+    AtomicallyMovedFile File(getSourceMgr().getDiagnostics(), Entry->getName(),
+                             AllWritten);
+    if (File.ok()) {
+      I->second.write(File.getStream());
+    }
+  }
+  return !AllWritten;
+}
diff --git a/contrib/libs/clang16/lib/Rewrite/TokenRewriter.cpp b/contrib/libs/clang16/lib/Rewrite/TokenRewriter.cpp
new file mode 100644
index 0000000000..b1f4bd2515
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/TokenRewriter.cpp
@@ -0,0 +1,99 @@
+//===- TokenRewriter.cpp - Token-based code rewriting interface -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file implements the TokenRewriter class, which is used for code
+//  transformations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/Core/TokenRewriter.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Lex/ScratchBuffer.h"
+#include "clang/Lex/Token.h"
+#include <cassert>
+#include <cstring>
+#include <map>
+#include <utility>
+
+using namespace clang;
+
+TokenRewriter::TokenRewriter(FileID FID, SourceManager &SM,
+                             const LangOptions &LangOpts) {
+  ScratchBuf.reset(new ScratchBuffer(SM));
+
+  // Create a lexer to lex all the tokens of the main file in raw mode.
+  llvm::MemoryBufferRef FromFile = SM.getBufferOrFake(FID);
+  Lexer RawLex(FID, FromFile, SM, LangOpts);
+
+  // Return all comments and whitespace as tokens.
+  RawLex.SetKeepWhitespaceMode(true);
+
+  // Lex the file, populating our datastructures.
+  Token RawTok;
+  RawLex.LexFromRawLexer(RawTok);
+  while (RawTok.isNot(tok::eof)) {
+#if 0
+    if (Tok.is(tok::raw_identifier)) {
+      // Look up the identifier info for the token.  This should use
+      // IdentifierTable directly instead of PP.
+      PP.LookUpIdentifierInfo(Tok);
+    }
+#endif
+
+    AddToken(RawTok, TokenList.end());
+    RawLex.LexFromRawLexer(RawTok);
+  }
+}
+
+TokenRewriter::~TokenRewriter() = default;
+
+/// RemapIterator - Convert from token_iterator (a const iterator) to
+/// TokenRefTy (a non-const iterator).
+TokenRewriter::TokenRefTy TokenRewriter::RemapIterator(token_iterator I) {
+  if (I == token_end()) return TokenList.end();
+
+  // FIXME: This is horrible, we should use our own list or something to avoid
+  // this.
+  std::map<SourceLocation, TokenRefTy>::iterator MapIt =
+    TokenAtLoc.find(I->getLocation());
+  assert(MapIt != TokenAtLoc.end() && "iterator not in rewriter?");
+  return MapIt->second;
+}
+
+/// AddToken - Add the specified token into the Rewriter before the other
+/// position.
+TokenRewriter::TokenRefTy
+TokenRewriter::AddToken(const Token &T, TokenRefTy Where) {
+  Where = TokenList.insert(Where, T);
+
+  bool InsertSuccess = TokenAtLoc.insert(std::make_pair(T.getLocation(),
+                                                        Where)).second;
+  assert(InsertSuccess && "Token location already in rewriter!");
+  (void)InsertSuccess;
+  return Where;
+}
+
+TokenRewriter::token_iterator
+TokenRewriter::AddTokenBefore(token_iterator I, const char *Val) {
+  unsigned Len = strlen(Val);
+
+  // Plop the string into the scratch buffer, then create a token for this
+  // string.
+  Token Tok;
+  Tok.startToken();
+  const char *Spelling;
+  Tok.setLocation(ScratchBuf->getToken(Val, Len, Spelling));
+  Tok.setLength(Len);
+
+  // TODO: Form a whole lexer around this and relex the token!  For now, just
+  // set kind to tok::unknown.
+  Tok.setKind(tok::unknown);
+
+  return AddToken(Tok, RemapIterator(I));
+}
diff --git a/contrib/libs/clang16/lib/Rewrite/ya.make b/contrib/libs/clang16/lib/Rewrite/ya.make
new file mode 100644
index 0000000000..f05430c157
--- /dev/null
+++ b/contrib/libs/clang16/lib/Rewrite/ya.make
@@ -0,0 +1,34 @@
+# Generated by devtools/yamaker.
+
+LIBRARY()
+
+LICENSE(Apache-2.0 WITH LLVM-exception)
+
+LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
+
+PEERDIR(
+    contrib/libs/clang16
+    contrib/libs/clang16/include
+    contrib/libs/clang16/lib/Basic
+    contrib/libs/clang16/lib/Lex
+    contrib/libs/llvm16
+    contrib/libs/llvm16/lib/Support
+)
+
+ADDINCL(
+    contrib/libs/clang16/lib/Rewrite
+)
+
+NO_COMPILER_WARNINGS()
+
+NO_UTIL()
+
+SRCS(
+    DeltaTree.cpp
+    HTMLRewrite.cpp
+    RewriteRope.cpp
+    Rewriter.cpp
+    TokenRewriter.cpp
+)
+
+END()