7 files changed, 2488 insertions, 0 deletions

diff --git a/lib/Rewrite/Core/CMakeLists.txt b/lib/Rewrite/Core/CMakeLists.txt
new file mode 100644
index 0000000000..07978187ff
--- /dev/null
+++ b/lib/Rewrite/Core/CMakeLists.txt
@@ -0,0 +1,24 @@
+add_clang_library(clangRewriteCore
+  DeltaTree.cpp
+  HTMLRewrite.cpp
+  RewriteRope.cpp
+  Rewriter.cpp
+  TokenRewriter.cpp
+  )
+
+add_dependencies(clangRewriteCore
+  ClangAttrClasses
+  ClangAttrList
+  ClangAttrParsedAttrList
+  ClangCommentNodes
+  ClangDeclNodes
+  ClangDiagnosticCommon
+  ClangDiagnosticFrontend
+  ClangStmtNodes
+  )
+
+target_link_libraries(clangRewriteCore
+  clangBasic
+  clangAST
+  clangParse
+  )
diff --git a/lib/Rewrite/Core/DeltaTree.cpp b/lib/Rewrite/Core/DeltaTree.cpp
new file mode 100644
index 0000000000..dff621d206
--- /dev/null
+++ b/lib/Rewrite/Core/DeltaTree.cpp
@@ -0,0 +1,467 @@
+//===--- 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/Core/DeltaTree.h"
+#include "clang/Basic/LLVM.h"
+#include <cstring>
+#include <cstdio>
+using namespace clang;
+
+/// The DeltaTree class is a multiway search tree (BTree) structure with some
+/// fancy features.  B-Trees are generally more memory and cache efficient
+/// than binary trees, because they store multiple keys/values in each node.
+///
+/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
+/// fast lookup by FileIndex.  However, an added (important) bonus is that it
+/// can also efficiently tell us the full accumulated delta for a specific
+/// file offset as well, without traversing the whole tree.
+///
+/// The nodes of the tree are made up of instances of two classes:
+/// DeltaTreeNode and DeltaTreeInteriorNode.  The later subclasses the
+/// former and adds children pointers.  Each node knows the full delta of all
+/// entries (recursively) contained inside of it, which allows us to get the
+/// full delta implied by a whole subtree in constant time.
+
+namespace {
+  /// SourceDelta - As code in the original input buffer is added and deleted,
+  /// SourceDelta records are used to keep track of how the input SourceLocation
+  /// object is mapped into the output buffer.
+  struct SourceDelta {
+    unsigned FileLoc;
+    int Delta;
+
+    static SourceDelta get(unsigned Loc, int D) {
+      SourceDelta Delta;
+      Delta.FileLoc = Loc;
+      Delta.Delta = D;
+      return Delta;
+    }
+  };
+  
+  /// DeltaTreeNode - The common part of all nodes.
+  ///
+  class DeltaTreeNode {
+  public:
+    struct InsertResult {
+      DeltaTreeNode *LHS, *RHS;
+      SourceDelta Split;
+    };
+    
+  private:
+    friend class DeltaTreeInteriorNode;
+
+    /// WidthFactor - This controls the number of K/V slots held in the BTree:
+    /// how wide it is.  Each level of the BTree is guaranteed to have at least
+    /// WidthFactor-1 K/V pairs (except the root) and may have at most
+    /// 2*WidthFactor-1 K/V pairs.
+    enum { WidthFactor = 8 };
+
+    /// Values - This tracks the SourceDelta's currently in this node.
+    ///
+    SourceDelta Values[2*WidthFactor-1];
+
+    /// NumValuesUsed - This tracks the number of values this node currently
+    /// holds.
+    unsigned char NumValuesUsed;
+
+    /// 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(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/lib/Rewrite/Core/HTMLRewrite.cpp b/lib/Rewrite/Core/HTMLRewrite.cpp
new file mode 100644
index 0000000000..3deb90e632
--- /dev/null
+++ b/lib/Rewrite/Core/HTMLRewrite.cpp
@@ -0,0 +1,583 @@
+//== 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/Core/Rewriter.h"
+#include "clang/Rewrite/Core/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/ErrorHandling.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.getExpansionLoc(B);
+  E = SM.getExpansionLoc(E);
+  FileID FID = SM.getFileID(B);
+  assert(SM.getFileID(E) == FID && "B/E not in the same file!");
+
+  unsigned BOffset = SM.getFileOffset(B);
+  unsigned EOffset = SM.getFileOffset(E);
+
+  // Include the whole end token in the range.
+  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, "&nbsp;");
+      ++ColNo;
+      break;
+    case '\f':
+      RB.ReplaceText(FilePos, 1, "<hr>");
+      ColNo = 0;
+      break;
+
+    case '\t': {
+      if (!ReplaceTabs)
+        break;
+      unsigned NumSpaces = 8-(ColNo&7);
+      if (EscapeSpaces)
+        RB.ReplaceText(FilePos, 1,
+                       StringRef("&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"
+                                       "&nbsp;&nbsp;&nbsp;", 6*NumSpaces));
+      else
+        RB.ReplaceText(FilePos, 1, StringRef("        ", NumSpaces));
+      ColNo += NumSpaces;
+      break;
+    }
+    case '<':
+      RB.ReplaceText(FilePos, 1, "&lt;");
+      ++ColNo;
+      break;
+
+    case '>':
+      RB.ReplaceText(FilePos, 1, "&gt;");
+      ++ColNo;
+      break;
+
+    case '&':
+      RB.ReplaceText(FilePos, 1, "&amp;");
+      ++ColNo;
+      break;
+    }
+  }
+}
+
+std::string html::EscapeText(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 << "&nbsp;";
+      else os << ' ';
+      break;
+
+    case '\t':
+      if (ReplaceTabs) {
+        if (EscapeSpaces)
+          for (unsigned i = 0; i < 4; ++i)
+            os << "&nbsp;";
+        else
+          for (unsigned i = 0; i < 4; ++i)
+            os << " ";
+      }
+      else
+        os << c;
+
+      break;
+
+    case '<': os << "&lt;"; break;
+    case '>': os << "&gt;"; break;
+    case '&': os << "&amp;"; break;
+    }
+  }
+
+  return os.str();
+}
+
+static void AddLineNumber(RewriteBuffer &RB, unsigned LineNo,
+                          unsigned B, unsigned E) {
+  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.getLocWithOffset(FileEnd-FileStart);
+
+  std::string s;
+  llvm::raw_string_ostream os(s);
+  os << "<!doctype html>\n" // Use HTML 5 doctype
+        "<html>\n<head>\n";
+
+  if (title)
+    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: \"Monospace\", 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; "
+        "margin-right:5px; }\n"
+      " .PathIndex { -webkit-border-radius:8px }\n"
+      " .PathIndexEvent { background-color:#bfba87 }\n"
+      " .PathIndexControl { background-color:#8c8c8c }\n"
+      " .PathNav a { text-decoration:none; font-size: larger }\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.getLangOpts());
+  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:
+      llvm_unreachable("tok::identifier in raw lexing mode!");
+    case tok::raw_identifier: {
+      // Fill in Result.IdentifierInfo and update the token kind,
+      // looking up the identifier in the identifier table.
+      PP.LookUpIdentifierInfo(Tok);
+
+      // If this is a pp-identifier, for a keyword, highlight it as such.
+      if (Tok.isNot(tok::identifier))
+        HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                       "<span class='keyword'>", "</span>");
+      break;
+    }
+    case tok::comment:
+      HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                     "<span class='comment'>", "</span>");
+      break;
+    case tok::utf8_string_literal:
+      // Chop off the u part of u8 prefix
+      ++TokOffs;
+      --TokLen;
+      // FALL THROUGH to chop the 8
+    case tok::wide_string_literal:
+    case tok::utf16_string_literal:
+    case tok::utf32_string_literal:
+      // Chop off the L, u, U or 8 prefix
+      ++TokOffs;
+      --TokLen;
+      // FALL THROUGH.
+    case tok::string_literal:
+      // FIXME: Exclude the optional ud-suffix from the highlighted range.
+      HighlightRange(RB, TokOffs, TokOffs+TokLen, BufferStart,
+                     "<span class='string_literal'>", "</span>");
+      break;
+    case tok::hash: {
+      // If this is a preprocessor directive, all tokens to end of line are too.
+      if (!Tok.isAtStartOfLine())
+        break;
+
+      // Eat all of the tokens until we get to the next one at the start of
+      // line.
+      unsigned TokEnd = TokOffs+TokLen;
+      L.LexFromRawLexer(Tok);
+      while (!Tok.isAtStartOfLine() && Tok.isNot(tok::eof)) {
+        TokEnd = SM.getFileOffset(Tok.getLocation())+Tok.getLength();
+        L.LexFromRawLexer(Tok);
+      }
+
+      // Find end of line.  This is a hack.
+      HighlightRange(RB, TokOffs, TokEnd, BufferStart,
+                     "<span class='directive'>", "</span>");
+
+      // Don't skip the next token.
+      continue;
+    }
+    }
+
+    L.LexFromRawLexer(Tok);
+  }
+}
+
+/// HighlightMacros - This uses the macro table state from the end of the
+/// file, to re-expand macros and insert (into the HTML) information about the
+/// macro expansions.  This won't be perfectly perfect, but it will be
+/// reasonably close.
+void html::HighlightMacros(Rewriter &R, FileID FID, const Preprocessor& PP) {
+  // Re-lex the raw token stream into a token buffer.
+  const SourceManager &SM = PP.getSourceManager();
+  std::vector<Token> TokenStream;
+
+  const llvm::MemoryBuffer *FromFile = SM.getBuffer(FID);
+  Lexer L(FID, FromFile, SM, PP.getLangOpts());
+
+  // 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