diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Rewrite')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/CMakeLists.txt | 9 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp | 475 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/HTMLRewrite.cpp | 580 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/Makefile | 21 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/RewriteRope.cpp | 808 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/Rewriter.cpp | 230 | ||||
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Rewrite/TokenRewriter.cpp | 99 |
7 files changed, 2222 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Rewrite/CMakeLists.txt b/contrib/llvm/tools/clang/lib/Rewrite/CMakeLists.txt new file mode 100644 index 0000000..ce9e1ed --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/CMakeLists.txt @@ -0,0 +1,9 @@ +set(LLVM_NO_RTTI 1) + +add_clang_library(clangRewrite + DeltaTree.cpp + HTMLRewrite.cpp + RewriteRope.cpp + Rewriter.cpp + TokenRewriter.cpp + ) diff --git a/contrib/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp b/contrib/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp new file mode 100644 index 0000000..35e888b --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp @@ -0,0 +1,475 @@ +//===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the DeltaTree and related classes. +// +//===----------------------------------------------------------------------===// + +#include "clang/Rewrite/DeltaTree.h" +#include "llvm/Support/Casting.h" +#include <cstring> +#include <cstdio> +using namespace clang; +using llvm::cast; +using llvm::dyn_cast; + +/// 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; + + /// 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; + public: + DeltaTreeNode(bool isLeaf = true) + : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {} + + 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(); + + static inline bool classof(const DeltaTreeNode *) { return true; } + }; +} // end anonymous namespace + +namespace { + /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. + /// This class tracks them. + class DeltaTreeInteriorNode : public DeltaTreeNode { + DeltaTreeNode *Children[2*WidthFactor]; + ~DeltaTreeInteriorNode() { + for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) + Children[i]->Destroy(); + } + friend class DeltaTreeNode; + public: + DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} + + DeltaTreeInteriorNode(DeltaTreeNode *FirstChild) + : DeltaTreeNode(false /*nonleaf*/) { + FullDelta = FirstChild->FullDelta; + Children[0] = FirstChild; + } + + 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 inline bool classof(const DeltaTreeInteriorNode *) { return true; } + static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } + }; +} + + +/// 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 (DeltaTreeInteriorNode *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, 0 /*can't fail*/); + else + InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/); + return true; + } + + // Otherwise, this is an interior node. Send the request down the tree. + DeltaTreeInteriorNode *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 (DeltaTreeInteriorNode *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 DeltaTreeInteriorNode *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 (1) { + // 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 DeltaTreeInteriorNode *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 = MyRoot = new DeltaTreeInteriorNode(InsertRes); + } + +#ifdef VERIFY_TREE + VerifyTree(MyRoot); +#endif +} + diff --git a/contrib/llvm/tools/clang/lib/Rewrite/HTMLRewrite.cpp b/contrib/llvm/tools/clang/lib/Rewrite/HTMLRewrite.cpp new file mode 100644 index 0000000..5fe0649 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/HTMLRewrite.cpp @@ -0,0 +1,580 @@ +//== HTMLRewrite.cpp - Translate source code into prettified HTML --*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the HTMLRewriter clas, which is used to translate the +// text of a source file into prettified HTML. +// +//===----------------------------------------------------------------------===// + +#include "clang/Lex/Preprocessor.h" +#include "clang/Rewrite/Rewriter.h" +#include "clang/Rewrite/HTMLRewrite.h" +#include "clang/Lex/TokenConcatenation.h" +#include "clang/Lex/Preprocessor.h" +#include "clang/Basic/SourceManager.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/raw_ostream.h" +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) { + SourceManager &SM = R.getSourceMgr(); + B = SM.getInstantiationLoc(B); + E = SM.getInstantiationLoc(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. + 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) { + + const llvm::MemoryBuffer *Buf = R.getSourceMgr().getBuffer(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, " "); + ++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, + llvm::StringRef(" " + " ", 6*NumSpaces)); + else + RB.ReplaceText(FilePos, 1, llvm::StringRef(" ", NumSpaces)); + ColNo += NumSpaces; + break; + } + case '<': + RB.ReplaceText(FilePos, 1, "<"); + ++ColNo; + break; + + case '>': + RB.ReplaceText(FilePos, 1, ">"); + ++ColNo; + break; + + case '&': + RB.ReplaceText(FilePos, 1, "&"); + ++ColNo; + break; + } + } +} + +std::string html::EscapeText(const std::string& 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 << " "; + else os << ' '; + break; + + case '\t': + if (ReplaceTabs) { + if (EscapeSpaces) + for (unsigned i = 0; i < 4; ++i) + os << " "; + else + for (unsigned i = 0; i < 4; ++i) + os << " "; + } + else + os << c; + + break; + + case '<': os << "<"; break; + case '>': os << ">"; break; + case '&': os << "&"; break; + } + } + + return os.str(); +} + +static void AddLineNumber(RewriteBuffer &RB, unsigned LineNo, + unsigned B, unsigned E) { + llvm::SmallString<256> Str; + llvm::raw_svector_ostream OS(Str); + + OS << "<tr><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) { + + const llvm::MemoryBuffer *Buf = R.getSourceMgr().getBuffer(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. + RB.InsertTextBefore(0, "<table class=\"code\">\n"); + RB.InsertTextAfter(FileEnd - FileBeg, "</table>"); +} + +void html::AddHeaderFooterInternalBuiltinCSS(Rewriter& R, FileID FID, + const char *title) { + + const llvm::MemoryBuffer *Buf = R.getSourceMgr().getBuffer(FID); + const char* FileStart = Buf->getBufferStart(); + const char* FileEnd = Buf->getBufferEnd(); + + SourceLocation StartLoc = R.getSourceMgr().getLocForStartOfFile(FID); + SourceLocation EndLoc = StartLoc.getFileLocWithOffset(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) + os << "<title>" << html::EscapeText(title) << "</title>\n"; + + os << "<style type=\"text/css\">\n" + " body { color:#000000; background-color:#ffffff }\n" + " body { font-family:Helvetica, sans-serif; font-size:10pt }\n" + " h1 { font-size:14pt }\n" + " .code { border-collapse:collapse; width:100%; }\n" + " .code { font-family: \"Andale Mono\", monospace; font-size:10pt }\n" + " .code { line-height: 1.2em }\n" + " .comment { color: green; font-style: oblique }\n" + " .keyword { color: blue }\n" + " .string_literal { color: red }\n" + " .directive { color: darkmagenta }\n" + // Macro expansions. + " .expansion { display: none; }\n" + " .macro:hover .expansion { display: block; border: 2px solid #FF0000; " + "padding: 2px; background-color:#FFF0F0; font-weight: normal; " + " -webkit-border-radius:5px; -webkit-box-shadow:1px 1px 7px #000; " + "position: absolute; top: -1em; left:10em; z-index: 1 } \n" + " .macro { color: darkmagenta; background-color:LemonChiffon;" + // Macros are position: relative to provide base for expansions. + " position: relative }\n" + " .num { width:2.5em; padding-right:2ex; background-color:#eeeeee }\n" + " .num { text-align:right; font-size:8pt }\n" + " .num { color:#444444 }\n" + " .line { padding-left: 1ex; border-left: 3px solid #ccc }\n" + " .line { white-space: pre }\n" + " .msg { -webkit-box-shadow:1px 1px 7px #000 }\n" + " .msg { -webkit-border-radius:5px }\n" + " .msg { font-family:Helvetica, sans-serif; font-size:8pt }\n" + " .msg { float:left }\n" + " .msg { padding:0.25em 1ex 0.25em 1ex }\n" + " .msg { margin-top:10px; margin-bottom:10px }\n" + " .msg { font-weight:bold }\n" + " .msg { max-width:60em; word-wrap: break-word; white-space: pre-wrap }\n" + " .msgT { padding:0x; spacing:0x }\n" + " .msgEvent { background-color:#fff8b4; color:#000000 }\n" + " .msgControl { background-color:#bbbbbb; color:#000000 }\n" + " .mrange { background-color:#dfddf3 }\n" + " .mrange { border-bottom:1px solid #6F9DBE }\n" + " .PathIndex { font-weight: bold; padding:0px 5px 0px 5px; " + "margin-right:5px; }\n" + " .PathIndex { -webkit-border-radius:8px }\n" + " .PathIndexEvent { background-color:#bfba87 }\n" + " .PathIndexControl { background-color:#8c8c8c }\n" + " .CodeInsertionHint { font-weight: bold; background-color: #10dd10 }\n" + " .CodeRemovalHint { background-color:#de1010 }\n" + " .CodeRemovalHint { border-bottom:1px solid #6F9DBE }\n" + " table.simpletable {\n" + " padding: 5px;\n" + " font-size:12pt;\n" + " margin:20px;\n" + " border-collapse: collapse; border-spacing: 0px;\n" + " }\n" + " td.rowname {\n" + " text-align:right; font-weight:bold; color:#444444;\n" + " padding-right:2ex; }\n" + "</style>\n</head>\n<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(); + const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID); + Lexer L(FID, FromFile, SM, PP.getLangOptions()); + const char *BufferStart = L.getBufferStart(); + + // 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: { + // Fill in Result.IdentifierInfo, looking up the identifier in the + // identifier table. + const IdentifierInfo *II = + PP.LookUpIdentifierInfo(Tok, BufferStart+TokOffs); + + // If this is a pp-identifier, for a keyword, highlight it as such. + if (II->getTokenID() != 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::wide_string_literal: + // Chop off the L prefix + ++TokOffs; + --TokLen; + // FALL THROUGH. + case tok::string_literal: + 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); + } +} + +namespace { +/// IgnoringDiagClient - This is a diagnostic client that just ignores all +/// diags. +class IgnoringDiagClient : public DiagnosticClient { + void HandleDiagnostic(Diagnostic::Level DiagLevel, + const DiagnosticInfo &Info) { + // Just ignore it. + } +}; +} + +/// 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; + + const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID); + Lexer L(FID, FromFile, SM, PP.getLangOptions()); + + // Lex all the tokens in raw mode, to avoid entering #includes or expanding + // macros. + while (1) { + 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::identifier)) { + // Change the kind of this identifier to the appropriate token kind, e.g. + // turning "for" into a keyword. + Tok.setKind(PP.LookUpIdentifierInfo(Tok)->getTokenID()); + } + + 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. + IgnoringDiagClient TmpDC; + Diagnostic TmpDiags(&TmpDC); + + // 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); + Diagnostic *OldDiags = &TmpPP.getDiagnostics(); + TmpPP.setDiagnostics(TmpDiags); + + // Inform the preprocessor that we don't want comments. + TmpPP.SetCommentRetentionState(false, 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[0], TokenStream.size(), false, 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 + // instantiation by inserting a start tag before the macro instantiation and + // end tag after it. + std::pair<SourceLocation, SourceLocation> LLoc = + SM.getInstantiationRange(Tok.getLocation()); + + // Ignore tokens whose instantiation location was not the main file. + if (SM.getFileID(LLoc.first) != FID) { + TmpPP.Lex(Tok); + continue; + } + + assert(SM.getFileID(LLoc.second) == 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.getInstantiationLoc(Tok.getLocation()) == LLoc.first) { + // 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 expansion as the end tag, so that multi-line macros all get + // highlighted. + Expansion = "<span class='expansion'>" + Expansion + "</span></span>"; + + HighlightRange(R, LLoc.first, LLoc.second, + "<span class='macro'>", Expansion.c_str()); + } + + // Restore diagnostics object back to its own thing. + TmpPP.setDiagnostics(*OldDiags); +} diff --git a/contrib/llvm/tools/clang/lib/Rewrite/Makefile b/contrib/llvm/tools/clang/lib/Rewrite/Makefile new file mode 100644 index 0000000..04c3530 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/Makefile @@ -0,0 +1,21 @@ +##===- clang/lib/Rewrite/Makefile --------------------------*- Makefile -*-===## +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +##===----------------------------------------------------------------------===## +# +# This implements code transformation / rewriting facilities. +# +##===----------------------------------------------------------------------===## + +LEVEL = ../../../.. +LIBRARYNAME := clangRewrite +BUILD_ARCHIVE = 1 + +CPP.Flags += -I$(PROJ_SRC_DIR)/../../include -I$(PROJ_OBJ_DIR)/../../include + +include $(LEVEL)/Makefile.common + diff --git a/contrib/llvm/tools/clang/lib/Rewrite/RewriteRope.cpp b/contrib/llvm/tools/clang/lib/Rewrite/RewriteRope.cpp new file mode 100644 index 0000000..fdb6fc3 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/RewriteRope.cpp @@ -0,0 +1,808 @@ +//===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the RewriteRope class, which is a powerful string. +// +//===----------------------------------------------------------------------===// + +#include "clang/Rewrite/RewriteRope.h" +#include "llvm/Support/Casting.h" +#include <algorithm> +using namespace clang; +using llvm::dyn_cast; +using llvm::cast; + +/// 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 contatenated. +/// RopePieceBTreeInterior - An interior node in the B+ Tree, which manages +/// up to '2*WidthFactor' other nodes in the tree. + + +//===----------------------------------------------------------------------===// +// RopePieceBTreeNode Class +//===----------------------------------------------------------------------===// + +namespace { + /// 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; + + /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it + /// is an instance of RopePieceBTreeInterior. + bool IsLeaf; + + RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {} + ~RopePieceBTreeNode() {} + 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); + + static inline bool classof(const RopePieceBTreeNode *) { return true; } + + }; +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// RopePieceBTreeLeaf Class +//===----------------------------------------------------------------------===// + +namespace { + /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece + /// nodes. This directly represents a chunk of the string with those + /// RopePieces contatenated. 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; + + /// 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, *NextLeaf; + public: + RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0), + PrevLeaf(0), NextLeaf(0) {} + ~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 == 0 && NextLeaf == 0 && "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 = 0; + } + } + + /// 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 inline bool classof(const RopePieceBTreeLeaf *) { return true; } + static inline bool classof(const RopePieceBTreeNode *N) { + return N->isLeaf(); + } + }; +} // end anonymous 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 0; + } + + // 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 0; + + // 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 0; + } + + // 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; + RopePieceBTreeNode *Children[2*WidthFactor]; + public: + RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {} + + RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS) + : RopePieceBTreeNode(false) { + Children[0] = LHS; + Children[1] = RHS; + NumChildren = 2; + Size = LHS->size() + RHS->size(); + } + + 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 inline bool classof(const RopePieceBTreeInterior *) { return true; } + static inline bool classof(const RopePieceBTreeNode *N) { + return !N->isLeaf(); + } + }; +} // end anonymous 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 0; // 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 0; + + // Otherwise, recursively split the child. + if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset)) + return HandleChildPiece(i, RHS); + return 0; // 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 0; +} + +/// 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 false; + } + + // 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 (RopePieceBTreeLeaf *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 (RopePieceBTreeLeaf *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 (RopePieceBTreeLeaf *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 (RopePieceBTreeLeaf *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 RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n); + + // Walk down the left side of the tree until we get to a leaf. + while (const RopePieceBTreeInterior *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 != 0) + CurPiece = &getCN(CurNode)->getPiece(0); + else // Empty tree, this is an end() iterator. + CurPiece = 0; + 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 != 0) + CurPiece = &getCN(CurNode)->getPiece(0); + else // Hit end(). + CurPiece = 0; + 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 (RopePieceBTreeLeaf *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; + RopeRefCountString *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. + + // If we had an old allocation, drop our reference to it. + if (AllocBuffer && --AllocBuffer->RefCount == 0) + delete [] (char*)AllocBuffer; + + unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize; + AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]); + AllocBuffer->RefCount = 0; + memcpy(AllocBuffer->Data, Start, Len); + AllocOffs = Len; + + // Start out the new allocation with a refcount of 1, since we have an + // internal reference to it. + AllocBuffer->addRef(); + return RopePiece(AllocBuffer, 0, Len); +} + + diff --git a/contrib/llvm/tools/clang/lib/Rewrite/Rewriter.cpp b/contrib/llvm/tools/clang/lib/Rewrite/Rewriter.cpp new file mode 100644 index 0000000..376678a --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/Rewriter.cpp @@ -0,0 +1,230 @@ +//===--- Rewriter.cpp - Code rewriting interface --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the Rewriter class, which is used for code +// transformations. +// +//===----------------------------------------------------------------------===// + +#include "clang/Rewrite/Rewriter.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/Decl.h" +#include "clang/Lex/Lexer.h" +#include "clang/Basic/SourceManager.h" +#include "llvm/Support/raw_ostream.h" +using namespace clang; + +llvm::raw_ostream &RewriteBuffer::write(llvm::raw_ostream &os) const { + // FIXME: eliminate the copy by writing out each chunk at a time + os << std::string(begin(), end()); + return os; +} + +void RewriteBuffer::RemoveText(unsigned OrigOffset, unsigned Size) { + // 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); +} + +void RewriteBuffer::InsertText(unsigned OrigOffset, const llvm::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, + const llvm::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(SourceRange Range) const { + if (!isRewritable(Range.getBegin()) || + !isRewritable(Range.getEnd())) return -1; + + FileID StartFileID, EndFileID; + unsigned StartOff, EndOff; + + StartOff = getLocationOffsetAndFileID(Range.getBegin(), StartFileID); + 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, 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. + EndOff += Lexer::MeasureTokenLength(Range.getEnd(), *SourceMgr, *LangOpts); + + return EndOff-StartOff; +} + +/// 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(SourceRange 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. + 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. + 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; + 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())); + + llvm::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, const llvm::StringRef &Str, + bool InsertAfter) { + if (!isRewritable(Loc)) return true; + FileID FID; + unsigned StartOffs = getLocationOffsetAndFileID(Loc, FID); + getEditBuffer(FID).InsertText(StartOffs, Str, InsertAfter); + return false; +} + +/// RemoveText - Remove the specified text region. +bool Rewriter::RemoveText(SourceLocation Start, unsigned Length) { + if (!isRewritable(Start)) return true; + FileID FID; + unsigned StartOffs = getLocationOffsetAndFileID(Start, FID); + getEditBuffer(FID).RemoveText(StartOffs, Length); + 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, + const llvm::StringRef &NewStr) { + if (!isRewritable(Start)) return true; + FileID StartFileID; + unsigned StartOffs = getLocationOffsetAndFileID(Start, StartFileID); + + getEditBuffer(StartFileID).ReplaceText(StartOffs, OrigLength, NewStr); + return false; +} + +/// ReplaceStmt - This replaces a Stmt/Expr with another, using the pretty +/// printer to generate the replacement code. This returns true if the input +/// could not be rewritten, or false if successful. +bool Rewriter::ReplaceStmt(Stmt *From, Stmt *To) { + // Measaure the old text. + int Size = getRangeSize(From->getSourceRange()); + if (Size == -1) + return true; + + // Get the new text. + std::string SStr; + llvm::raw_string_ostream S(SStr); + To->printPretty(S, 0, PrintingPolicy(*LangOpts)); + const std::string &Str = S.str(); + + ReplaceText(From->getLocStart(), Size, Str); + return false; +} diff --git a/contrib/llvm/tools/clang/lib/Rewrite/TokenRewriter.cpp b/contrib/llvm/tools/clang/lib/Rewrite/TokenRewriter.cpp new file mode 100644 index 0000000..789d53f --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Rewrite/TokenRewriter.cpp @@ -0,0 +1,99 @@ +//===--- TokenRewriter.cpp - Token-based code rewriting interface ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the TokenRewriter class, which is used for code +// transformations. +// +//===----------------------------------------------------------------------===// + +#include "clang/Rewrite/TokenRewriter.h" +#include "clang/Lex/Lexer.h" +#include "clang/Lex/ScratchBuffer.h" +#include "clang/Basic/SourceManager.h" +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. + const llvm::MemoryBuffer *FromFile = SM.getBuffer(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::identifier)) { + // Look up the identifier info for the token. This should use + // IdentifierTable directly instead of PP. + Tok.setIdentifierInfo(PP.LookUpIdentifierInfo(Tok)); + } +#endif + + AddToken(RawTok, TokenList.end()); + RawLex.LexFromRawLexer(RawTok); + } +} + +TokenRewriter::~TokenRewriter() { +} + + +/// 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!"); + InsertSuccess = 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)); +} + |
