https://github.com/jpienaar updated
https://github.com/llvm/llvm-project/pull/99770
>From ee91900dd42321ce1344a70df5f1baddf36bde9f Mon Sep 17 00:00:00 2001
From: Jacques Pienaar <jpien...@google.com>
Date: Sat, 20 Jul 2024 16:25:14 +0000
Subject: [PATCH] [llvm][clang] Move RewriterBuffer to ADT.
These classes are not specific to clang and useful for other rewriter tools.
---
clang/include/clang/Rewrite/Core/DeltaTree.h | 50 --
.../include/clang/Rewrite/Core/HTMLRewrite.h | 11 +-
.../include/clang/Rewrite/Core/RewriteRope.h | 223 --------
clang/include/clang/Rewrite/Core/Rewriter.h | 19 +-
clang/lib/ARCMigrate/ARCMT.cpp | 2 +-
clang/lib/ARCMigrate/ObjCMT.cpp | 1 +
clang/lib/Frontend/Rewrite/FixItRewriter.cpp | 3 +-
clang/lib/Frontend/Rewrite/HTMLPrint.cpp | 2 +
clang/lib/Frontend/Rewrite/RewriteMacros.cpp | 4 +-
.../Frontend/Rewrite/RewriteModernObjC.cpp | 3 +-
clang/lib/Frontend/Rewrite/RewriteObjC.cpp | 1 +
clang/lib/Rewrite/CMakeLists.txt | 2 -
clang/lib/Rewrite/HTMLRewrite.cpp | 1 +
clang/lib/Rewrite/Rewriter.cpp | 109 +---
.../StaticAnalyzer/Core/HTMLDiagnostics.cpp | 2 +
clang/lib/Tooling/Core/Replacement.cpp | 2 +-
clang/unittests/Rewrite/CMakeLists.txt | 1 -
llvm/include/llvm/ADT/DeltaTree.h | 50 ++
.../include/llvm/ADT}/RewriteBuffer.h | 40 +-
llvm/include/llvm/ADT/RewriteRope.h | 223 ++++++++
llvm/lib/Support/CMakeLists.txt | 3 +
.../lib/Support}/DeltaTree.cpp | 265 +++++----
llvm/lib/Support/RewriteBuffer.cpp | 107 ++++
.../lib/Support}/RewriteRope.cpp | 507 +++++++++---------
llvm/unittests/ADT/CMakeLists.txt | 1 +
.../unittests/ADT}/RewriteBufferTest.cpp | 5 +-
26 files changed, 825 insertions(+), 812 deletions(-)
delete mode 100644 clang/include/clang/Rewrite/Core/DeltaTree.h
delete mode 100644 clang/include/clang/Rewrite/Core/RewriteRope.h
create mode 100644 llvm/include/llvm/ADT/DeltaTree.h
rename {clang/include/clang/Rewrite/Core =>
llvm/include/llvm/ADT}/RewriteBuffer.h (82%)
create mode 100644 llvm/include/llvm/ADT/RewriteRope.h
rename {clang/lib/Rewrite => llvm/lib/Support}/DeltaTree.cpp (68%)
create mode 100644 llvm/lib/Support/RewriteBuffer.cpp
rename {clang/lib/Rewrite => llvm/lib/Support}/RewriteRope.cpp (63%)
rename {clang/unittests/Rewrite => llvm/unittests/ADT}/RewriteBufferTest.cpp
(96%)
diff --git a/clang/include/clang/Rewrite/Core/DeltaTree.h
b/clang/include/clang/Rewrite/Core/DeltaTree.h
deleted file mode 100644
index e566c92aaff91a..00000000000000
--- a/clang/include/clang/Rewrite/Core/DeltaTree.h
+++ /dev/null
@@ -1,50 +0,0 @@
-//===- DeltaTree.h - B-Tree for Rewrite Delta tracking ----------*- 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 DeltaTree class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_REWRITE_CORE_DELTATREE_H
-#define LLVM_CLANG_REWRITE_CORE_DELTATREE_H
-
-namespace clang {
-
- /// DeltaTree - 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. This
- /// implements a key/value mapping from index to delta, and allows fast
lookup
- /// on index. 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.
- class DeltaTree {
- void *Root; // "DeltaTreeNode *"
-
- public:
- DeltaTree();
-
- // Note: Currently we only support copying when the RHS is empty.
- DeltaTree(const DeltaTree &RHS);
-
- DeltaTree &operator=(const DeltaTree &) = delete;
- ~DeltaTree();
-
- /// getDeltaAt - Return the accumulated delta at the specified file offset.
- /// This includes all insertions or delections that occurred *before* the
- /// specified file index.
- int getDeltaAt(unsigned FileIndex) const;
-
- /// 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 AddDelta(unsigned FileIndex, int Delta);
- };
-
-} // namespace clang
-
-#endif // LLVM_CLANG_REWRITE_CORE_DELTATREE_H
diff --git a/clang/include/clang/Rewrite/Core/HTMLRewrite.h
b/clang/include/clang/Rewrite/Core/HTMLRewrite.h
index eecf589632746c..9edb514d566b9c 100644
--- a/clang/include/clang/Rewrite/Core/HTMLRewrite.h
+++ b/clang/include/clang/Rewrite/Core/HTMLRewrite.h
@@ -17,10 +17,13 @@
#include "clang/Basic/SourceLocation.h"
#include <string>
+namespace llvm {
+class RewriteBuffer;
+} // namespace llvm
+
namespace clang {
class Rewriter;
-class RewriteBuffer;
class Preprocessor;
namespace html {
@@ -53,9 +56,9 @@ namespace html {
/// HighlightRange - This is the same as the above method, but takes
/// decomposed file locations.
- void HighlightRange(RewriteBuffer &RB, unsigned B, unsigned E,
- const char *BufferStart,
- const char *StartTag, const char *EndTag);
+ void HighlightRange(llvm::RewriteBuffer &RB, unsigned B, unsigned E,
+ const char *BufferStart, const char *StartTag,
+ const char *EndTag);
/// EscapeText - HTMLize a specified file so that special characters are
/// are translated so that they are not interpreted as HTML tags.
diff --git a/clang/include/clang/Rewrite/Core/RewriteRope.h
b/clang/include/clang/Rewrite/Core/RewriteRope.h
deleted file mode 100644
index 73e66e111f5743..00000000000000
--- a/clang/include/clang/Rewrite/Core/RewriteRope.h
+++ /dev/null
@@ -1,223 +0,0 @@
-//===- RewriteRope.h - Rope specialized for rewriter ------------*- 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 RewriteRope class, which is a powerful string class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
-#define LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
-
-#include "llvm/ADT/IntrusiveRefCntPtr.h"
-#include "llvm/ADT/StringRef.h"
-#include <cassert>
-#include <cstddef>
-#include <iterator>
-#include <utility>
-
-namespace clang {
-
-
//===--------------------------------------------------------------------===//
- // RopeRefCountString Class
-
//===--------------------------------------------------------------------===//
-
- /// RopeRefCountString - This struct is allocated with 'new char[]' from the
- /// heap, and represents a reference counted chunk of string data. When its
- /// ref count drops to zero, it is delete[]'d. This is primarily managed
- /// through the RopePiece class below.
- struct RopeRefCountString {
- unsigned RefCount;
- char Data[1]; // Variable sized.
-
- void Retain() { ++RefCount; }
-
- void Release() {
- assert(RefCount > 0 && "Reference count is already zero.");
- if (--RefCount == 0)
- delete [] (char*)this;
- }
- };
-
-
//===--------------------------------------------------------------------===//
- // RopePiece Class
-
//===--------------------------------------------------------------------===//
-
- /// RopePiece - This class represents a view into a RopeRefCountString
object.
- /// This allows references to string data to be efficiently chopped up and
- /// moved around without having to push around the string data itself.
- ///
- /// For example, we could have a 1M RopePiece and want to insert something
- /// into the middle of it. To do this, we split it into two RopePiece
objects
- /// that both refer to the same underlying RopeRefCountString (just with
- /// different offsets) which is a nice constant time operation.
- struct RopePiece {
- llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData;
- unsigned StartOffs = 0;
- unsigned EndOffs = 0;
-
- RopePiece() = default;
- RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
- unsigned End)
- : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
-
- const char &operator[](unsigned Offset) const {
- return StrData->Data[Offset+StartOffs];
- }
- char &operator[](unsigned Offset) {
- return StrData->Data[Offset+StartOffs];
- }
-
- unsigned size() const { return EndOffs-StartOffs; }
- };
-
-
//===--------------------------------------------------------------------===//
- // RopePieceBTreeIterator Class
-
//===--------------------------------------------------------------------===//
-
- /// RopePieceBTreeIterator - This class provides read-only forward iteration
- /// over bytes that are in a RopePieceBTree. This first iterates over bytes
- /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
- /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
- class RopePieceBTreeIterator {
- /// CurNode - The current B+Tree node that we are inspecting.
- const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;
-
- /// CurPiece - The current RopePiece in the B+Tree node that we're
- /// inspecting.
- const RopePiece *CurPiece = nullptr;
-
- /// CurChar - The current byte in the RopePiece we are pointing to.
- unsigned CurChar = 0;
-
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = const char;
- using difference_type = std::ptrdiff_t;
- using pointer = value_type *;
- using reference = value_type &;
-
- RopePieceBTreeIterator() = default;
- RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
-
- char operator*() const {
- return (*CurPiece)[CurChar];
- }
-
- bool operator==(const RopePieceBTreeIterator &RHS) const {
- return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
- }
- bool operator!=(const RopePieceBTreeIterator &RHS) const {
- return !operator==(RHS);
- }
-
- RopePieceBTreeIterator& operator++() { // Preincrement
- if (CurChar+1 < CurPiece->size())
- ++CurChar;
- else
- MoveToNextPiece();
- return *this;
- }
-
- RopePieceBTreeIterator operator++(int) { // Postincrement
- RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
- }
-
- llvm::StringRef piece() const {
- return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
- }
-
- void MoveToNextPiece();
- };
-
-
//===--------------------------------------------------------------------===//
- // RopePieceBTree Class
-
//===--------------------------------------------------------------------===//
-
- class RopePieceBTree {
- void /*RopePieceBTreeNode*/ *Root;
-
- public:
- RopePieceBTree();
- RopePieceBTree(const RopePieceBTree &RHS);
- RopePieceBTree &operator=(const RopePieceBTree &) = delete;
- ~RopePieceBTree();
-
- using iterator = RopePieceBTreeIterator;
-
- iterator begin() const { return iterator(Root); }
- iterator end() const { return iterator(); }
- unsigned size() const;
- unsigned empty() const { return size() == 0; }
-
- void clear();
-
- void insert(unsigned Offset, const RopePiece &R);
-
- void erase(unsigned Offset, unsigned NumBytes);
- };
-
-
//===--------------------------------------------------------------------===//
- // RewriteRope Class
-
//===--------------------------------------------------------------------===//
-
-/// RewriteRope - A powerful string class. This class supports extremely
-/// efficient insertions and deletions into the middle of it, even for
-/// ridiculously long strings.
-class RewriteRope {
- RopePieceBTree Chunks;
-
- /// We allocate space for string data out of a buffer of size AllocChunkSize.
- /// This keeps track of how much space is left.
- llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;
- enum { AllocChunkSize = 4080 };
- unsigned AllocOffs = AllocChunkSize;
-
-public:
- RewriteRope() = default;
- RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
-
- // The copy assignment operator is defined as deleted pending further
- // motivation.
- RewriteRope &operator=(const RewriteRope &) = delete;
-
- using iterator = RopePieceBTree::iterator;
- using const_iterator = RopePieceBTree::iterator;
-
- iterator begin() const { return Chunks.begin(); }
- iterator end() const { return Chunks.end(); }
- unsigned size() const { return Chunks.size(); }
-
- void clear() {
- Chunks.clear();
- }
-
- void assign(const char *Start, const char *End) {
- clear();
- if (Start != End)
- Chunks.insert(0, MakeRopeString(Start, End));
- }
-
- void insert(unsigned Offset, const char *Start, const char *End) {
- assert(Offset <= size() && "Invalid position to insert!");
- if (Start == End) return;
- Chunks.insert(Offset, MakeRopeString(Start, End));
- }
-
- void erase(unsigned Offset, unsigned NumBytes) {
- assert(Offset+NumBytes <= size() && "Invalid region to erase!");
- if (NumBytes == 0) return;
- Chunks.erase(Offset, NumBytes);
- }
-
-private:
- RopePiece MakeRopeString(const char *Start, const char *End);
-};
-
-} // namespace clang
-
-#endif // LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
diff --git a/clang/include/clang/Rewrite/Core/Rewriter.h
b/clang/include/clang/Rewrite/Core/Rewriter.h
index c89015e4055820..4e96f6fcca919c 100644
--- a/clang/include/clang/Rewrite/Core/Rewriter.h
+++ b/clang/include/clang/Rewrite/Core/Rewriter.h
@@ -16,7 +16,7 @@
#include "clang/Basic/LLVM.h"
#include "clang/Basic/SourceLocation.h"
-#include "clang/Rewrite/Core/RewriteBuffer.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/ADT/StringRef.h"
#include <map>
#include <string>
@@ -32,7 +32,7 @@ class SourceManager;
class Rewriter {
SourceManager *SourceMgr = nullptr;
const LangOptions *LangOpts = nullptr;
- std::map<FileID, RewriteBuffer> RewriteBuffers;
+ std::map<FileID, llvm::RewriteBuffer> RewriteBuffers;
public:
struct RewriteOptions {
@@ -49,7 +49,7 @@ class Rewriter {
///
/// FIXME: This sometimes corrupts the file's rewrite buffer due to
/// incorrect indexing in the implementation (see the FIXME in
- /// clang::RewriteBuffer::RemoveText). Moreover, it's inefficient because
+ /// llvm::RewriteBuffer::RemoveText). Moreover, it's inefficient because
/// it must scan the buffer from the beginning to find the start of the
/// line. When feasible, it's better for the caller to check for a blank
/// line and then, if found, expand the removal range to include it.
@@ -62,8 +62,9 @@ class Rewriter {
RewriteOptions() {}
};
- using buffer_iterator = std::map<FileID, RewriteBuffer>::iterator;
- using const_buffer_iterator = std::map<FileID,
RewriteBuffer>::const_iterator;
+ using buffer_iterator = std::map<FileID, llvm::RewriteBuffer>::iterator;
+ using const_buffer_iterator =
+ std::map<FileID, llvm::RewriteBuffer>::const_iterator;
explicit Rewriter() = default;
explicit Rewriter(SourceManager &SM, const LangOptions &LO)
@@ -191,13 +192,13 @@ class Rewriter {
/// buffer, and allows you to write on it directly. This is useful if you
/// want efficient low-level access to apis for scribbling on one specific
/// FileID's buffer.
- RewriteBuffer &getEditBuffer(FileID FID);
+ llvm::RewriteBuffer &getEditBuffer(FileID FID);
/// getRewriteBufferFor - Return the rewrite buffer for the specified FileID.
/// If no modification has been made to it, return null.
- const RewriteBuffer *getRewriteBufferFor(FileID FID) const {
- std::map<FileID, RewriteBuffer>::const_iterator I =
- RewriteBuffers.find(FID);
+ const llvm::RewriteBuffer *getRewriteBufferFor(FileID FID) const {
+ std::map<FileID, llvm::RewriteBuffer>::const_iterator I =
+ RewriteBuffers.find(FID);
return I == RewriteBuffers.end() ? nullptr : &I->second;
}
diff --git a/clang/lib/ARCMigrate/ARCMT.cpp b/clang/lib/ARCMigrate/ARCMT.cpp
index 5835559bff6b72..1a8a200f2fc194 100644
--- a/clang/lib/ARCMigrate/ARCMT.cpp
+++ b/clang/lib/ARCMigrate/ARCMT.cpp
@@ -596,7 +596,7 @@ bool MigrationProcess::applyTransform(TransformFn trans,
for (Rewriter::buffer_iterator
I = rewriter.buffer_begin(), E = rewriter.buffer_end(); I != E; ++I) {
FileID FID = I->first;
- RewriteBuffer &buf = I->second;
+ llvm::RewriteBuffer &buf = I->second;
OptionalFileEntryRef file =
Ctx.getSourceManager().getFileEntryRefForID(FID);
assert(file);
diff --git a/clang/lib/ARCMigrate/ObjCMT.cpp b/clang/lib/ARCMigrate/ObjCMT.cpp
index 4357c8e3f09a55..c1bc7c762088f2 100644
--- a/clang/lib/ARCMigrate/ObjCMT.cpp
+++ b/clang/lib/ARCMigrate/ObjCMT.cpp
@@ -36,6 +36,7 @@
using namespace clang;
using namespace arcmt;
using namespace ento;
+using llvm::RewriteBuffer;
namespace {
diff --git a/clang/lib/Frontend/Rewrite/FixItRewriter.cpp
b/clang/lib/Frontend/Rewrite/FixItRewriter.cpp
index 567bac576adb40..44dfaf20eae73f 100644
--- a/clang/lib/Frontend/Rewrite/FixItRewriter.cpp
+++ b/clang/lib/Frontend/Rewrite/FixItRewriter.cpp
@@ -21,8 +21,8 @@
#include "clang/Edit/Commit.h"
#include "clang/Edit/EditsReceiver.h"
#include "clang/Frontend/FrontendDiagnostic.h"
-#include "clang/Rewrite/Core/RewriteBuffer.h"
#include "clang/Rewrite/Core/Rewriter.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/raw_ostream.h"
@@ -33,6 +33,7 @@
#include <utility>
using namespace clang;
+using llvm::RewriteBuffer;
FixItRewriter::FixItRewriter(DiagnosticsEngine &Diags, SourceManager
&SourceMgr,
const LangOptions &LangOpts,
diff --git a/clang/lib/Frontend/Rewrite/HTMLPrint.cpp
b/clang/lib/Frontend/Rewrite/HTMLPrint.cpp
index 69baa8f591088c..5cce193ed1c4f3 100644
--- a/clang/lib/Frontend/Rewrite/HTMLPrint.cpp
+++ b/clang/lib/Frontend/Rewrite/HTMLPrint.cpp
@@ -20,8 +20,10 @@
#include "clang/Rewrite/Core/HTMLRewrite.h"
#include "clang/Rewrite/Core/Rewriter.h"
#include "clang/Rewrite/Frontend/ASTConsumers.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/Support/raw_ostream.h"
using namespace clang;
+using llvm::RewriteBuffer;
//===----------------------------------------------------------------------===//
// Functional HTML pretty-printing.
diff --git a/clang/lib/Frontend/Rewrite/RewriteMacros.cpp
b/clang/lib/Frontend/Rewrite/RewriteMacros.cpp
index 5701b271aff103..b533cabe97f5e9 100644
--- a/clang/lib/Frontend/Rewrite/RewriteMacros.cpp
+++ b/clang/lib/Frontend/Rewrite/RewriteMacros.cpp
@@ -11,16 +11,18 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Rewrite/Frontend/Rewriters.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Lex/Preprocessor.h"
#include "clang/Rewrite/Core/Rewriter.h"
+#include "clang/Rewrite/Frontend/Rewriters.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/raw_ostream.h"
#include <cstdio>
#include <memory>
using namespace clang;
+using llvm::RewriteBuffer;
/// isSameToken - Return true if the two specified tokens start have the same
/// content.
diff --git a/clang/lib/Frontend/Rewrite/RewriteModernObjC.cpp
b/clang/lib/Frontend/Rewrite/RewriteModernObjC.cpp
index 3849e4040b53a1..f618c536b5f3c6 100644
--- a/clang/lib/Frontend/Rewrite/RewriteModernObjC.cpp
+++ b/clang/lib/Frontend/Rewrite/RewriteModernObjC.cpp
@@ -10,7 +10,6 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Rewrite/Frontend/ASTConsumers.h"
#include "clang/AST/AST.h"
#include "clang/AST/ASTConsumer.h"
#include "clang/AST/Attr.h"
@@ -23,6 +22,7 @@
#include "clang/Config/config.h"
#include "clang/Lex/Lexer.h"
#include "clang/Rewrite/Core/Rewriter.h"
+#include "clang/Rewrite/Frontend/ASTConsumers.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
@@ -34,6 +34,7 @@
#if CLANG_ENABLE_OBJC_REWRITER
using namespace clang;
+using llvm::RewriteBuffer;
using llvm::utostr;
namespace {
diff --git a/clang/lib/Frontend/Rewrite/RewriteObjC.cpp
b/clang/lib/Frontend/Rewrite/RewriteObjC.cpp
index bf5176a2b6fb2e..9db6ddbf0b8908 100644
--- a/clang/lib/Frontend/Rewrite/RewriteObjC.cpp
+++ b/clang/lib/Frontend/Rewrite/RewriteObjC.cpp
@@ -32,6 +32,7 @@
#if CLANG_ENABLE_OBJC_REWRITER
using namespace clang;
+using llvm::RewriteBuffer;
using llvm::utostr;
namespace {
diff --git a/clang/lib/Rewrite/CMakeLists.txt b/clang/lib/Rewrite/CMakeLists.txt
index 16550b1b710ef9..93ecb3c835260f 100644
--- a/clang/lib/Rewrite/CMakeLists.txt
+++ b/clang/lib/Rewrite/CMakeLists.txt
@@ -3,9 +3,7 @@ set(LLVM_LINK_COMPONENTS
)
add_clang_library(clangRewrite
- DeltaTree.cpp
HTMLRewrite.cpp
- RewriteRope.cpp
Rewriter.cpp
TokenRewriter.cpp
diff --git a/clang/lib/Rewrite/HTMLRewrite.cpp
b/clang/lib/Rewrite/HTMLRewrite.cpp
index a96ca0764ae73d..c75835df2c98ee 100644
--- a/clang/lib/Rewrite/HTMLRewrite.cpp
+++ b/clang/lib/Rewrite/HTMLRewrite.cpp
@@ -16,6 +16,7 @@
#include "clang/Lex/Preprocessor.h"
#include "clang/Lex/TokenConcatenation.h"
#include "clang/Rewrite/Core/Rewriter.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MemoryBuffer.h"
diff --git a/clang/lib/Rewrite/Rewriter.cpp b/clang/lib/Rewrite/Rewriter.cpp
index 0e6ae365064463..68cf797f97905b 100644
--- a/clang/lib/Rewrite/Rewriter.cpp
+++ b/clang/lib/Rewrite/Rewriter.cpp
@@ -17,8 +17,8 @@
#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/RewriteBuffer.h"
+#include "llvm/ADT/RewriteRope.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Error.h"
@@ -29,113 +29,18 @@
#include <utility>
using namespace clang;
+using llvm::RewriteBuffer;
-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;
-}
+//===----------------------------------------------------------------------===//
+// Rewriter class
+//===----------------------------------------------------------------------===//
/// 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;
- }
+ return c == ' ' || c == '\t' || c == '\f' || c == '\v' || c == '\r';
}
-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,
diff --git a/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
b/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
index fb5030d373c2f1..28d9de2973b01f 100644
--- a/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
+++ b/clang/lib/StaticAnalyzer/Core/HTMLDiagnostics.cpp
@@ -27,6 +27,7 @@
#include "clang/Rewrite/Core/Rewriter.h"
#include "clang/StaticAnalyzer/Core/PathDiagnosticConsumers.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallString.h"
@@ -52,6 +53,7 @@
using namespace clang;
using namespace ento;
+using llvm::RewriteBuffer;
//===----------------------------------------------------------------------===//
// Boilerplate.
diff --git a/clang/lib/Tooling/Core/Replacement.cpp
b/clang/lib/Tooling/Core/Replacement.cpp
index 269f17a6db4cfc..9acf00263b5a8c 100644
--- a/clang/lib/Tooling/Core/Replacement.cpp
+++ b/clang/lib/Tooling/Core/Replacement.cpp
@@ -19,9 +19,9 @@
#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/Rewriter.h"
#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Error.h"
diff --git a/clang/unittests/Rewrite/CMakeLists.txt
b/clang/unittests/Rewrite/CMakeLists.txt
index 6594d8cc5897f3..3c5e2f8e5354be 100644
--- a/clang/unittests/Rewrite/CMakeLists.txt
+++ b/clang/unittests/Rewrite/CMakeLists.txt
@@ -3,7 +3,6 @@ set(LLVM_LINK_COMPONENTS
)
add_clang_unittest(RewriteTests
- RewriteBufferTest.cpp
RewriterTest.cpp
)
clang_target_link_libraries(RewriteTests
diff --git a/llvm/include/llvm/ADT/DeltaTree.h
b/llvm/include/llvm/ADT/DeltaTree.h
new file mode 100644
index 00000000000000..5db9d74d9d5296
--- /dev/null
+++ b/llvm/include/llvm/ADT/DeltaTree.h
@@ -0,0 +1,50 @@
+//===- DeltaTree.h - B-Tree for Rewrite Delta tracking ----------*- 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 DeltaTree class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_DELTATREE_H
+#define LLVM_ADT_DELTATREE_H
+
+namespace llvm {
+
+/// DeltaTree - 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. This
+/// implements a key/value mapping from index to delta, and allows fast lookup
+/// on index. 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.
+class DeltaTree {
+ void *Root; // "DeltaTreeNode *"
+
+public:
+ DeltaTree();
+
+ // Note: Currently we only support copying when the RHS is empty.
+ DeltaTree(const DeltaTree &RHS);
+
+ DeltaTree &operator=(const DeltaTree &) = delete;
+ ~DeltaTree();
+
+ /// getDeltaAt - Return the accumulated delta at the specified file offset.
+ /// This includes all insertions or delections that occurred *before* the
+ /// specified file index.
+ int getDeltaAt(unsigned FileIndex) const;
+
+ /// 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 AddDelta(unsigned FileIndex, int Delta);
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_DELTATREE_H
diff --git a/clang/include/clang/Rewrite/Core/RewriteBuffer.h
b/llvm/include/llvm/ADT/RewriteBuffer.h
similarity index 82%
rename from clang/include/clang/Rewrite/Core/RewriteBuffer.h
rename to llvm/include/llvm/ADT/RewriteBuffer.h
index b8f34174b71566..8197a06f882c1a 100644
--- a/clang/include/clang/Rewrite/Core/RewriteBuffer.h
+++ b/llvm/include/llvm/ADT/RewriteBuffer.h
@@ -6,15 +6,20 @@
//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_CLANG_REWRITE_CORE_REWRITEBUFFER_H
-#define LLVM_CLANG_REWRITE_CORE_REWRITEBUFFER_H
+#ifndef LLVM_ADT_REWRITEBUFFER_H
+#define LLVM_ADT_REWRITEBUFFER_H
-#include "clang/Basic/LLVM.h"
-#include "clang/Rewrite/Core/DeltaTree.h"
-#include "clang/Rewrite/Core/RewriteRope.h"
+#include "llvm/ADT/DeltaTree.h"
+#include "llvm/ADT/RewriteRope.h"
#include "llvm/ADT/StringRef.h"
namespace clang {
+class Rewriter;
+} // namespace clang
+
+namespace llvm {
+
+class raw_ostream;
/// RewriteBuffer - As code is rewritten, SourceBuffer's from the original
/// input with modifications get a new RewriteBuffer associated with them. The
@@ -23,7 +28,7 @@ namespace clang {
/// RewriteBuffer. For example, if text is inserted into the buffer, any
/// locations after the insertion point have to be mapped.
class RewriteBuffer {
- friend class Rewriter;
+ friend class clang::Rewriter;
/// Deltas - Keep track of all the deltas in the source code due to
insertions
/// and deletions.
@@ -43,9 +48,7 @@ class RewriteBuffer {
void Initialize(const char *BufStart, const char *BufEnd) {
Buffer.assign(BufStart, BufEnd);
}
- void Initialize(StringRef Input) {
- Initialize(Input.begin(), Input.end());
- }
+ void Initialize(StringRef Input) { Initialize(Input.begin(), Input.end()); }
/// Write to \p Stream the result of applying all changes to the
/// original buffer.
@@ -63,9 +66,7 @@ class RewriteBuffer {
/// InsertText - Insert some text at the specified point, where the offset in
/// the buffer is specified relative to the original SourceBuffer. The
/// text is inserted after the specified location.
- void InsertText(unsigned OrigOffset, StringRef Str,
- bool InsertAfter = true);
-
+ void InsertText(unsigned OrigOffset, StringRef Str, bool InsertAfter = true);
/// InsertTextBefore - Insert some text before the specified point, where the
/// offset in the buffer is specified relative to the original
@@ -85,8 +86,7 @@ class RewriteBuffer {
/// 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 ReplaceText(unsigned OrigOffset, unsigned OrigLength,
- StringRef NewStr);
+ void ReplaceText(unsigned OrigOffset, unsigned OrigLength, StringRef NewStr);
private:
/// getMappedOffset - Given an offset into the original SourceBuffer that
this
@@ -95,23 +95,23 @@ class RewriteBuffer {
/// position where text is inserted, the location returned will be after any
/// inserted text at the position.
unsigned getMappedOffset(unsigned OrigOffset,
- bool AfterInserts = false) const{
- return Deltas.getDeltaAt(2*OrigOffset+AfterInserts)+OrigOffset;
+ bool AfterInserts = false) const {
+ return Deltas.getDeltaAt(2 * OrigOffset + AfterInserts) + OrigOffset;
}
/// AddInsertDelta - When an insertion is made at a position, this
/// method is used to record that information.
void AddInsertDelta(unsigned OrigOffset, int Change) {
- return Deltas.AddDelta(2*OrigOffset, Change);
+ return Deltas.AddDelta(2 * OrigOffset, Change);
}
/// AddReplaceDelta - When a replacement/deletion is made at a position, this
/// method is used to record that information.
void AddReplaceDelta(unsigned OrigOffset, int Change) {
- return Deltas.AddDelta(2*OrigOffset+1, Change);
+ return Deltas.AddDelta(2 * OrigOffset + 1, Change);
}
};
-} // namespace clang
+} // namespace llvm
-#endif // LLVM_CLANG_REWRITE_CORE_REWRITEBUFFER_H
+#endif // LLVM_ADT_REWRITEBUFFER_H
diff --git a/llvm/include/llvm/ADT/RewriteRope.h
b/llvm/include/llvm/ADT/RewriteRope.h
new file mode 100644
index 00000000000000..784f3c07eaa62b
--- /dev/null
+++ b/llvm/include/llvm/ADT/RewriteRope.h
@@ -0,0 +1,223 @@
+//===- RewriteRope.h - Rope specialized for rewriter ------------*- 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 RewriteRope class, which is a powerful string class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_REWRITEROPE_H
+#define LLVM_ADT_REWRITEROPE_H
+
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+#include <utility>
+
+namespace llvm {
+
+//===--------------------------------------------------------------------===//
+// RopeRefCountString Class
+//===--------------------------------------------------------------------===//
+
+/// RopeRefCountString - This struct is allocated with 'new char[]' from the
+/// heap, and represents a reference counted chunk of string data. When its
+/// ref count drops to zero, it is delete[]'d. This is primarily managed
+/// through the RopePiece class below.
+struct RopeRefCountString {
+ unsigned RefCount;
+ char Data[1]; // Variable sized.
+
+ void Retain() { ++RefCount; }
+
+ void Release() {
+ assert(RefCount > 0 && "Reference count is already zero.");
+ if (--RefCount == 0)
+ delete[] (char *)this;
+ }
+};
+
+//===--------------------------------------------------------------------===//
+// RopePiece Class
+//===--------------------------------------------------------------------===//
+
+/// RopePiece - This class represents a view into a RopeRefCountString object.
+/// This allows references to string data to be efficiently chopped up and
+/// moved around without having to push around the string data itself.
+///
+/// For example, we could have a 1M RopePiece and want to insert something
+/// into the middle of it. To do this, we split it into two RopePiece objects
+/// that both refer to the same underlying RopeRefCountString (just with
+/// different offsets) which is a nice constant time operation.
+struct RopePiece {
+ llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData;
+ unsigned StartOffs = 0;
+ unsigned EndOffs = 0;
+
+ RopePiece() = default;
+ RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
+ unsigned End)
+ : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
+
+ const char &operator[](unsigned Offset) const {
+ return StrData->Data[Offset + StartOffs];
+ }
+ char &operator[](unsigned Offset) {
+ return StrData->Data[Offset + StartOffs];
+ }
+
+ unsigned size() const { return EndOffs - StartOffs; }
+};
+
+//===--------------------------------------------------------------------===//
+// RopePieceBTreeIterator Class
+//===--------------------------------------------------------------------===//
+
+/// RopePieceBTreeIterator - This class provides read-only forward iteration
+/// over bytes that are in a RopePieceBTree. This first iterates over bytes
+/// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
+/// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
+class RopePieceBTreeIterator {
+ /// CurNode - The current B+Tree node that we are inspecting.
+ const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;
+
+ /// CurPiece - The current RopePiece in the B+Tree node that we're
+ /// inspecting.
+ const RopePiece *CurPiece = nullptr;
+
+ /// CurChar - The current byte in the RopePiece we are pointing to.
+ unsigned CurChar = 0;
+
+public:
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = const char;
+ using difference_type = std::ptrdiff_t;
+ using pointer = value_type *;
+ using reference = value_type &;
+
+ RopePieceBTreeIterator() = default;
+ RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
+
+ char operator*() const { return (*CurPiece)[CurChar]; }
+
+ bool operator==(const RopePieceBTreeIterator &RHS) const {
+ return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
+ }
+ bool operator!=(const RopePieceBTreeIterator &RHS) const {
+ return !operator==(RHS);
+ }
+
+ RopePieceBTreeIterator &operator++() { // Preincrement
+ if (CurChar + 1 < CurPiece->size())
+ ++CurChar;
+ else
+ MoveToNextPiece();
+ return *this;
+ }
+
+ RopePieceBTreeIterator operator++(int) { // Postincrement
+ RopePieceBTreeIterator tmp = *this;
+ ++*this;
+ return tmp;
+ }
+
+ llvm::StringRef piece() const {
+ return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
+ }
+
+ void MoveToNextPiece();
+};
+
+//===--------------------------------------------------------------------===//
+// RopePieceBTree Class
+//===--------------------------------------------------------------------===//
+
+class RopePieceBTree {
+ void /*RopePieceBTreeNode*/ *Root;
+
+public:
+ RopePieceBTree();
+ RopePieceBTree(const RopePieceBTree &RHS);
+ RopePieceBTree &operator=(const RopePieceBTree &) = delete;
+ ~RopePieceBTree();
+
+ using iterator = RopePieceBTreeIterator;
+
+ iterator begin() const { return iterator(Root); }
+ iterator end() const { return iterator(); }
+ unsigned size() const;
+ unsigned empty() const { return size() == 0; }
+
+ void clear();
+
+ void insert(unsigned Offset, const RopePiece &R);
+
+ void erase(unsigned Offset, unsigned NumBytes);
+};
+
+//===--------------------------------------------------------------------===//
+// RewriteRope Class
+//===--------------------------------------------------------------------===//
+
+/// RewriteRope - A powerful string class. This class supports extremely
+/// efficient insertions and deletions into the middle of it, even for
+/// ridiculously long strings.
+class RewriteRope {
+ RopePieceBTree Chunks;
+
+ /// We allocate space for string data out of a buffer of size AllocChunkSize.
+ /// This keeps track of how much space is left.
+ llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;
+ enum { AllocChunkSize = 4080 };
+ unsigned AllocOffs = AllocChunkSize;
+
+public:
+ RewriteRope() = default;
+ RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
+
+ // The copy assignment operator is defined as deleted pending further
+ // motivation.
+ RewriteRope &operator=(const RewriteRope &) = delete;
+
+ using iterator = RopePieceBTree::iterator;
+ using const_iterator = RopePieceBTree::iterator;
+
+ iterator begin() const { return Chunks.begin(); }
+ iterator end() const { return Chunks.end(); }
+ unsigned size() const { return Chunks.size(); }
+
+ void clear() { Chunks.clear(); }
+
+ void assign(const char *Start, const char *End) {
+ clear();
+ if (Start != End)
+ Chunks.insert(0, MakeRopeString(Start, End));
+ }
+
+ void insert(unsigned Offset, const char *Start, const char *End) {
+ assert(Offset <= size() && "Invalid position to insert!");
+ if (Start == End)
+ return;
+ Chunks.insert(Offset, MakeRopeString(Start, End));
+ }
+
+ void erase(unsigned Offset, unsigned NumBytes) {
+ assert(Offset + NumBytes <= size() && "Invalid region to erase!");
+ if (NumBytes == 0)
+ return;
+ Chunks.erase(Offset, NumBytes);
+ }
+
+private:
+ RopePiece MakeRopeString(const char *Start, const char *End);
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_REWRITEROPE_H
diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt
index f653379e303349..a73ac54a01c5a5 100644
--- a/llvm/lib/Support/CMakeLists.txt
+++ b/llvm/lib/Support/CMakeLists.txt
@@ -168,6 +168,7 @@ add_llvm_component_library(LLVMSupport
Debug.cpp
DebugCounter.cpp
DeltaAlgorithm.cpp
+ DeltaTree.cpp
DivisionByConstantInfo.cpp
DAGDeltaAlgorithm.cpp
DJB.cpp
@@ -216,6 +217,8 @@ add_llvm_component_library(LLVMSupport
PrettyStackTrace.cpp
RandomNumberGenerator.cpp
Regex.cpp
+ RewriteBuffer.cpp
+ RewriteRope.cpp
RISCVAttributes.cpp
RISCVAttributeParser.cpp
RISCVISAUtils.cpp
diff --git a/clang/lib/Rewrite/DeltaTree.cpp b/llvm/lib/Support/DeltaTree.cpp
similarity index 68%
rename from clang/lib/Rewrite/DeltaTree.cpp
rename to llvm/lib/Support/DeltaTree.cpp
index 61467f84928f2a..2eb642ffd1df6c 100644
--- a/clang/lib/Rewrite/DeltaTree.cpp
+++ b/llvm/lib/Support/DeltaTree.cpp
@@ -10,13 +10,12 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Rewrite/Core/DeltaTree.h"
-#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DeltaTree.h"
#include "llvm/Support/Casting.h"
#include <cassert>
#include <cstring>
-using namespace clang;
+using namespace llvm;
/// The DeltaTree class is a multiway search tree (BTree) structure with some
/// fancy features. B-Trees are generally more memory and cache efficient
@@ -35,125 +34,125 @@ using namespace clang;
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;
- }
+/// 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;
};
- /// 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;
+private:
+ friend class DeltaTreeInteriorNode;
- public:
- DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}
+ /// 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 };
- bool isLeaf() const { return IsLeaf; }
- int getFullDelta() const { return FullDelta; }
- bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
+ /// Values - This tracks the SourceDelta's currently in this node.
+ SourceDelta Values[2 * WidthFactor - 1];
- unsigned getNumValuesUsed() const { return NumValuesUsed; }
+ /// NumValuesUsed - This tracks the number of values this node currently
+ /// holds.
+ unsigned char NumValuesUsed = 0;
- const SourceDelta &getValue(unsigned i) const {
- assert(i < NumValuesUsed && "Invalid value #");
- return Values[i];
- }
+ /// 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;
- SourceDelta &getValue(unsigned i) {
- assert(i < NumValuesUsed && "Invalid value #");
- return Values[i];
- }
+ /// FullDelta - This is the full delta of all the values in this node and
+ /// all children nodes.
+ int FullDelta = 0;
- /// 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);
+public:
+ DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}
- void DoSplit(InsertResult &InsertRes);
+ bool isLeaf() const { return IsLeaf; }
+ int getFullDelta() const { return FullDelta; }
+ bool isFull() const { return NumValuesUsed == 2 * WidthFactor - 1; }
+ unsigned getNumValuesUsed() const { return NumValuesUsed; }
- /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
- /// local walk over our contained deltas.
- void RecomputeFullDeltaLocally();
+ const SourceDelta &getValue(unsigned i) const {
+ assert(i < NumValuesUsed && "Invalid value #");
+ return Values[i];
+ }
- void Destroy();
- };
+ SourceDelta &getValue(unsigned i) {
+ assert(i < NumValuesUsed && "Invalid value #");
+ return Values[i];
+ }
- /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
- /// This class tracks them.
- class DeltaTreeInteriorNode : public DeltaTreeNode {
- friend class DeltaTreeNode;
+ /// 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);
- DeltaTreeNode *Children[2*WidthFactor];
+ void DoSplit(InsertResult &InsertRes);
- ~DeltaTreeInteriorNode() {
- for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
- Children[i]->Destroy();
- }
+ /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
+ /// local walk over our contained deltas.
+ void RecomputeFullDeltaLocally();
- public:
- DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
+ void Destroy();
+};
- 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;
- }
+/// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
+/// This class tracks them.
+class DeltaTreeInteriorNode : public DeltaTreeNode {
+ friend class DeltaTreeNode;
- const DeltaTreeNode *getChild(unsigned i) const {
- assert(i < getNumValuesUsed()+1 && "Invalid child");
- return Children[i];
- }
+ DeltaTreeNode *Children[2 * WidthFactor];
- DeltaTreeNode *getChild(unsigned i) {
- assert(i < getNumValuesUsed()+1 && "Invalid child");
- return Children[i];
- }
+ ~DeltaTreeInteriorNode() {
+ for (unsigned i = 0, e = NumValuesUsed + 1; i != e; ++i)
+ Children[i]->Destroy();
+ }
- static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
- };
+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
@@ -172,7 +171,7 @@ void DeltaTreeNode::RecomputeFullDeltaLocally() {
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)
+ for (unsigned i = 0, e = getNumValuesUsed() + 1; i != e; ++i)
NewFullDelta += IN->getChild(i)->getFullDelta();
FullDelta = NewFullDelta;
}
@@ -209,7 +208,7 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int
Delta,
// 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));
+ memmove(&Values[i + 1], &Values[i], sizeof(Values[0]) * (e - i));
Values[i] = SourceDelta::get(FileIndex, Delta);
++NumValuesUsed;
return false;
@@ -239,13 +238,13 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int
Delta,
// 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]));
+ 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;
+ IN->Children[i + 1] = InsertRes->RHS;
if (e != i)
- memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
+ memmove(&Values[i + 1], &Values[i], (e - i) * sizeof(Values[0]));
Values[i] = InsertRes->Split;
++NumValuesUsed;
return false;
@@ -272,20 +271,21 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int
Delta,
// 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();
+ 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;
+ 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]));
+ 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();
@@ -310,7 +310,7 @@ void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
// into the new node.
DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
memcpy(&New->Children[0], &IN->Children[WidthFactor],
- WidthFactor*sizeof(IN->Children[0]));
+ WidthFactor * sizeof(IN->Children[0]));
NewNode = New;
} else {
// Just create the new leaf node.
@@ -319,10 +319,10 @@ void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
// Move over the last 'WidthFactor-1' values from here to NewNode.
memcpy(&NewNode->Values[0], &Values[WidthFactor],
- (WidthFactor-1)*sizeof(Values[0]));
+ (WidthFactor - 1) * sizeof(Values[0]));
// Decrease the number of values in the two nodes.
- NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
+ NewNode->NumValuesUsed = NumValuesUsed = WidthFactor - 1;
// Recompute the two nodes' full delta.
NewNode->RecomputeFullDeltaLocally();
@@ -330,14 +330,14 @@ void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
InsertRes.LHS = this;
InsertRes.RHS = NewNode;
- InsertRes.Split = Values[WidthFactor-1];
+ InsertRes.Split = Values[WidthFactor - 1];
}
//===----------------------------------------------------------------------===//
// DeltaTree Implementation
//===----------------------------------------------------------------------===//
-//#define VERIFY_TREE
+// #define VERIFY_TREE
#ifdef VERIFY_TREE
/// VerifyTree - Walk the btree performing assertions on various properties to
@@ -350,7 +350,7 @@ static void VerifyTree(const DeltaTreeNode *N) {
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);
+ assert(N->getValue(i - 1).FileLoc < N->getValue(i).FileLoc);
FullDelta += N->getValue(i).Delta;
}
assert(FullDelta == N->getFullDelta());
@@ -364,16 +364,16 @@ static void VerifyTree(const DeltaTreeNode *N) {
const SourceDelta &IVal = N->getValue(i);
const DeltaTreeNode *IChild = IN->getChild(i);
if (i)
- assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
+ 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 <
+ 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);
+ assert(IN->getChild(i + 1)->getValue(0).FileLoc > IVal.FileLoc);
VerifyTree(IChild);
}
@@ -381,15 +381,11 @@ static void VerifyTree(const DeltaTreeNode *N) {
assert(FullDelta == N->getFullDelta());
}
-#endif // VERIFY_TREE
+#endif // VERIFY_TREE
-static DeltaTreeNode *getRoot(void *Root) {
- return (DeltaTreeNode*)Root;
-}
+static DeltaTreeNode *getRoot(void *Root) { return (DeltaTreeNode *)Root; }
-DeltaTree::DeltaTree() {
- Root = new DeltaTreeNode();
-}
+DeltaTree::DeltaTree() { Root = new DeltaTreeNode(); }
DeltaTree::DeltaTree(const DeltaTree &RHS) {
// Currently we only support copying when the RHS is empty.
@@ -398,9 +394,7 @@ DeltaTree::DeltaTree(const DeltaTree &RHS) {
Root = new DeltaTreeNode();
}
-DeltaTree::~DeltaTree() {
- getRoot(Root)->Destroy();
-}
+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
@@ -428,7 +422,8 @@ int DeltaTree::getDeltaAt(unsigned FileIndex) const {
// 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;
+ if (!IN)
+ return Result;
// Include any children to the left of the values we skipped, all of
// their deltas should be included as well.
@@ -440,7 +435,7 @@ int DeltaTree::getDeltaAt(unsigned FileIndex) const {
// partial results.
if (NumValsGreater != Node->getNumValuesUsed() &&
Node->getValue(NumValsGreater).FileLoc == FileIndex)
- return Result+IN->getChild(NumValsGreater)->getFullDelta();
+ return Result + IN->getChild(NumValsGreater)->getFullDelta();
// Otherwise, traverse down the tree. The selected subtree may be
// partially included in the range.
diff --git a/llvm/lib/Support/RewriteBuffer.cpp
b/llvm/lib/Support/RewriteBuffer.cpp
new file mode 100644
index 00000000000000..cc6ba7e97b1a7f
--- /dev/null
+++ b/llvm/lib/Support/RewriteBuffer.cpp
@@ -0,0 +1,107 @@
+//===- RewriteBuffer.h - Buffer 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/RewriteBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+raw_ostream &RewriteBuffer::write(raw_ostream &Stream) const {
+ // Walk RewriteRope chunks efficiently using MoveToNextPiece() instead of the
+ // character iterator.
+ for (RopePieceBTreeIterator I = begin(), E = end(); I != E;
+ I.MoveToNextPiece())
+ Stream << I.piece();
+ return Stream;
+}
+
+/// Return true if this character is non-new-line whitespace:
+/// ' ', '\\t', '\\f', '\\v', '\\r'.
+static inline bool isWhitespaceExceptNL(unsigned char c) {
+ return c == ' ' || c == '\t' || c == '\f' || c == '\v' || c == '\r';
+}
+
+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);
+}
diff --git a/clang/lib/Rewrite/RewriteRope.cpp
b/llvm/lib/Support/RewriteRope.cpp
similarity index 63%
rename from clang/lib/Rewrite/RewriteRope.cpp
rename to llvm/lib/Support/RewriteRope.cpp
index 980d0f01e277c4..7440aa6ab501e7 100644
--- a/clang/lib/Rewrite/RewriteRope.cpp
+++ b/llvm/lib/Support/RewriteRope.cpp
@@ -10,14 +10,13 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Rewrite/Core/RewriteRope.h"
-#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/RewriteRope.h"
#include "llvm/Support/Casting.h"
#include <algorithm>
#include <cassert>
#include <cstring>
-using namespace clang;
+using namespace llvm;
/// RewriteRope is a "strong" string class, designed to make insertions and
/// deletions in the middle of the string nearly constant time (really, they
are
@@ -68,162 +67,160 @@ 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);
- };
+/// 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();
- }
+/// 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; }
+ bool isFull() const { return NumPieces == 2 * WidthFactor; }
- /// clear - Remove all rope pieces from this leaf.
- void clear() {
- while (NumPieces)
- Pieces[--NumPieces] = RopePiece();
- Size = 0;
- }
+ /// clear - Remove all rope pieces from this leaf.
+ void clear() {
+ while (NumPieces)
+ Pieces[--NumPieces] = RopePiece();
+ Size = 0;
+ }
- unsigned getNumPieces() const { return NumPieces; }
+ unsigned getNumPieces() const { return NumPieces; }
- const RopePiece &getPiece(unsigned i) const {
- assert(i < getNumPieces() && "Invalid piece ID");
- return Pieces[i];
- }
+ const RopePiece &getPiece(unsigned i) const {
+ assert(i < getNumPieces() && "Invalid piece ID");
+ return Pieces[i];
+ }
- const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
+ const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
- void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
- assert(!PrevLeaf && !NextLeaf && "Already in ordering");
+ void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
+ assert(!PrevLeaf && !NextLeaf && "Already in ordering");
- NextLeaf = Node->NextLeaf;
- if (NextLeaf)
- NextLeaf->PrevLeaf = &NextLeaf;
- PrevLeaf = &Node->NextLeaf;
- Node->NextLeaf = this;
- }
+ 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;
- }
+ 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();
- }
+ /// 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();
- }
- };
+ /// 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
@@ -244,7 +241,7 @@ RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned
Offset) {
// Find the piece that this offset lands in.
unsigned PieceOffs = 0;
unsigned i = 0;
- while (Offset >= PieceOffs+Pieces[i].size()) {
+ while (Offset >= PieceOffs + Pieces[i].size()) {
PieceOffs += Pieces[i].size();
++i;
}
@@ -256,13 +253,13 @@ RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned
Offset) {
// Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset
// to being Piece relative.
- unsigned IntraPieceOffset = Offset-PieceOffs;
+ 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,
+ RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs + IntraPieceOffset,
Pieces[i].EndOffs);
Size -= Pieces[i].size();
- Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
+ Pieces[i].EndOffs = Pieces[i].StartOffs + IntraPieceOffset;
Size += Pieces[i].size();
return insert(Offset, Tail);
@@ -293,7 +290,7 @@ RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned
Offset,
// 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[e] = Pieces[e - 1];
Pieces[i] = R;
++NumPieces;
Size += R.size();
@@ -309,10 +306,10 @@ RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned
Offset,
RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
// Move over the last 'WidthFactor' values from here to NewNode.
- std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
+ 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());
+ std::fill(&Pieces[WidthFactor], &Pieces[2 * WidthFactor], RopePiece());
// Decrease the number of values in the two nodes.
NewNode->NumPieces = NumPieces = WidthFactor;
@@ -347,33 +344,34 @@ void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned
NumBytes) {
// Figure out how many pieces completely cover 'NumBytes'. We want to remove
// all of them.
- for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
+ 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()) {
+ 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;
+ unsigned NumDeleted = i - StartPiece;
for (; i != getNumPieces(); ++i)
- Pieces[i-NumDeleted] = Pieces[i];
+ Pieces[i - NumDeleted] = Pieces[i];
// Drop references to dead rope pieces.
- std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
+ std::fill(&Pieces[getNumPieces() - NumDeleted], &Pieces[getNumPieces()],
RopePiece());
NumPieces -= NumDeleted;
- unsigned CoverBytes = PieceOffs-Offset;
+ unsigned CoverBytes = PieceOffs - Offset;
NumBytes -= CoverBytes;
Size -= CoverBytes;
}
// If we completely removed some stuff, we could be done.
- if (NumBytes == 0) return;
+ 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.
@@ -390,81 +388,79 @@ void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned
NumBytes) {
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;
+/// 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];
+ RopePieceBTreeNode *Children[2 * WidthFactor];
- public:
- RopePieceBTreeInterior() : RopePieceBTreeNode(false) {}
+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(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();
- }
+ ~RopePieceBTreeInterior() {
+ for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+ Children[i]->Destroy();
+ }
- bool isFull() const { return NumChildren == 2*WidthFactor; }
+ bool isFull() const { return NumChildren == 2 * WidthFactor; }
- unsigned getNumChildren() const { return NumChildren; }
+ unsigned getNumChildren() const { return NumChildren; }
- const RopePieceBTreeNode *getChild(unsigned i) const {
- assert(i < NumChildren && "invalid child #");
- return Children[i];
- }
+ 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];
- }
+ 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();
- }
+ /// 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();
- }
- };
+ /// 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
@@ -481,7 +477,7 @@ RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned
Offset) {
unsigned ChildOffset = 0;
unsigned i = 0;
- for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
+ for (; Offset >= ChildOffset + getChild(i)->size(); ++i)
ChildOffset += getChild(i)->size();
// If already split there, we're done.
@@ -489,7 +485,7 @@ RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned
Offset) {
return nullptr;
// Otherwise, recursively split the child.
- if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
+ if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset - ChildOffset))
return HandleChildPiece(i, RHS);
return nullptr; // Done!
}
@@ -509,17 +505,17 @@ RopePieceBTreeNode
*RopePieceBTreeInterior::insert(unsigned Offset,
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();
+ i = e - 1;
+ ChildOffs = size() - getChild(i)->size();
} else {
- for (; Offset > ChildOffs+getChild(i)->size(); ++i)
+ 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))
+ if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset - ChildOffs, R))
return HandleChildPiece(i, RHS);
return nullptr;
@@ -534,9 +530,9 @@ RopePieceBTreeInterior::HandleChildPiece(unsigned i,
RopePieceBTreeNode *RHS) {
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;
+ memmove(&Children[i + 2], &Children[i + 1],
+ (getNumChildren() - i - 1) * sizeof(Children[0]));
+ Children[i + 1] = RHS;
++NumChildren;
return nullptr;
}
@@ -549,7 +545,7 @@ RopePieceBTreeInterior::HandleChildPiece(unsigned i,
RopePieceBTreeNode *RHS) {
// Move over the last 'WidthFactor' values from here to NewNode.
memcpy(&NewNode->Children[0], &Children[WidthFactor],
- WidthFactor*sizeof(Children[0]));
+ WidthFactor * sizeof(Children[0]));
// Decrease the number of values in the two nodes.
NewNode->NumChildren = NumChildren = WidthFactor;
@@ -559,7 +555,7 @@ RopePieceBTreeInterior::HandleChildPiece(unsigned i,
RopePieceBTreeNode *RHS) {
if (i < WidthFactor)
this->HandleChildPiece(i, RHS);
else
- NewNode->HandleChildPiece(i-WidthFactor, RHS);
+ NewNode->HandleChildPiece(i - WidthFactor, RHS);
// Recompute the two nodes' size.
NewNode->FullRecomputeSizeLocally();
@@ -585,7 +581,7 @@ void RopePieceBTreeInterior::erase(unsigned Offset,
unsigned NumBytes) {
// If we are deleting something contained entirely in the child, pass on
the
// request.
- if (Offset+NumBytes < CurChild->size()) {
+ if (Offset + NumBytes < CurChild->size()) {
CurChild->erase(Offset, NumBytes);
return;
}
@@ -593,7 +589,7 @@ void RopePieceBTreeInterior::erase(unsigned Offset,
unsigned NumBytes) {
// 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;
+ unsigned BytesFromChild = CurChild->size() - Offset;
CurChild->erase(Offset, BytesFromChild);
NumBytes -= BytesFromChild;
// Start at the beginning of the next child.
@@ -608,8 +604,8 @@ void RopePieceBTreeInterior::erase(unsigned Offset,
unsigned NumBytes) {
CurChild->Destroy();
--NumChildren;
if (i != getNumChildren())
- memmove(&Children[i], &Children[i+1],
- (getNumChildren()-i)*sizeof(Children[0]));
+ memmove(&Children[i], &Children[i + 1],
+ (getNumChildren() - i) * sizeof(Children[0]));
}
}
@@ -654,7 +650,7 @@ RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned
Offset,
/// 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!");
+ 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);
@@ -665,7 +661,7 @@ void RopePieceBTreeNode::erase(unsigned Offset, unsigned
NumBytes) {
//===----------------------------------------------------------------------===//
static const RopePieceBTreeLeaf *getCN(const void *P) {
- return static_cast<const RopePieceBTreeLeaf*>(P);
+ return static_cast<const RopePieceBTreeLeaf *>(P);
}
// begin iterator.
@@ -686,13 +682,14 @@ RopePieceBTreeIterator::RopePieceBTreeIterator(const void
*n) {
if (CurNode)
CurPiece = &getCN(CurNode)->getPiece(0);
- else // Empty tree, this is an end() iterator.
+ else // Empty tree, this is an end() iterator.
CurPiece = nullptr;
CurChar = 0;
}
void RopePieceBTreeIterator::MoveToNextPiece() {
- if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1))
{
+ if (CurPiece !=
+ &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces() - 1)) {
CurChar = 0;
++CurPiece;
return;
@@ -715,25 +712,19 @@ void RopePieceBTreeIterator::MoveToNextPiece() {
//===----------------------------------------------------------------------===//
static RopePieceBTreeNode *getRoot(void *P) {
- return static_cast<RopePieceBTreeNode*>(P);
+ return static_cast<RopePieceBTreeNode *>(P);
}
-RopePieceBTree::RopePieceBTree() {
- Root = new RopePieceBTreeLeaf();
-}
+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();
-}
+RopePieceBTree::~RopePieceBTree() { getRoot(Root)->Destroy(); }
-unsigned RopePieceBTree::size() const {
- return getRoot(Root)->size();
-}
+unsigned RopePieceBTree::size() const { return getRoot(Root)->size(); }
void RopePieceBTree::clear() {
if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
@@ -772,24 +763,24 @@ void RopePieceBTree::erase(unsigned Offset, unsigned
NumBytes) {
/// 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;
+ 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);
+ if (AllocOffs + Len <= AllocChunkSize) {
+ memcpy(AllocBuffer->Data + AllocOffs, Start, Len);
AllocOffs += Len;
- return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
+ 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;
+ 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);
+ 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
diff --git a/llvm/unittests/ADT/CMakeLists.txt
b/llvm/unittests/ADT/CMakeLists.txt
index f48d840a105952..745e4d9fb74a4a 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -63,6 +63,7 @@ add_llvm_unittest(ADTTests
PostOrderIteratorTest.cpp
PriorityWorklistTest.cpp
RangeAdapterTest.cpp
+ RewriteBufferTest.cpp
SCCIteratorTest.cpp
STLExtrasTest.cpp
STLForwardCompatTest.cpp
diff --git a/clang/unittests/Rewrite/RewriteBufferTest.cpp
b/llvm/unittests/ADT/RewriteBufferTest.cpp
similarity index 96%
rename from clang/unittests/Rewrite/RewriteBufferTest.cpp
rename to llvm/unittests/ADT/RewriteBufferTest.cpp
index bf29c0ff928304..3b367daa7806e7 100644
--- a/clang/unittests/Rewrite/RewriteBufferTest.cpp
+++ b/llvm/unittests/ADT/RewriteBufferTest.cpp
@@ -6,11 +6,10 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Rewrite/Core/RewriteBuffer.h"
+#include "llvm/ADT/RewriteBuffer.h"
#include "gtest/gtest.h"
using namespace llvm;
-using namespace clang;
namespace {
@@ -32,7 +31,7 @@ static void tagRange(unsigned Offset, unsigned Len, StringRef
tagName,
raw_string_ostream(EndTag) << "</" << tagName << '>';
Buf.InsertTextAfter(Offset, BeginTag);
- Buf.InsertTextBefore(Offset+Len, EndTag);
+ Buf.InsertTextBefore(Offset + Len, EndTag);
}
TEST(RewriteBuffer, TagRanges) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
