| //===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the DeltaTree and related classes. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "clang/Rewrite/Core/DeltaTree.h" |
| #include "clang/Basic/LLVM.h" |
| #include "llvm/Support/Casting.h" |
| #include <cassert> |
| #include <cstring> |
| |
| using namespace clang; |
| |
| /// The DeltaTree class is a multiway search tree (BTree) structure with some |
| /// fancy features. B-Trees are generally more memory and cache efficient |
| /// than binary trees, because they store multiple keys/values in each node. |
| /// |
| /// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing |
| /// fast lookup by FileIndex. However, an added (important) bonus is that it |
| /// can also efficiently tell us the full accumulated delta for a specific |
| /// file offset as well, without traversing the whole tree. |
| /// |
| /// The nodes of the tree are made up of instances of two classes: |
| /// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the |
| /// former and adds children pointers. Each node knows the full delta of all |
| /// entries (recursively) contained inside of it, which allows us to get the |
| /// full delta implied by a whole subtree in constant time. |
| |
| namespace { |
| |
| /// SourceDelta - As code in the original input buffer is added and deleted, |
| /// SourceDelta records are used to keep track of how the input SourceLocation |
| /// object is mapped into the output buffer. |
| struct SourceDelta { |
| unsigned FileLoc; |
| int Delta; |
| |
| static SourceDelta get(unsigned Loc, int D) { |
| SourceDelta Delta; |
| Delta.FileLoc = Loc; |
| Delta.Delta = D; |
| return Delta; |
| } |
| }; |
| |
| /// DeltaTreeNode - The common part of all nodes. |
| /// |
| class DeltaTreeNode { |
| public: |
| struct InsertResult { |
| DeltaTreeNode *LHS, *RHS; |
| SourceDelta Split; |
| }; |
| |
| private: |
| friend class DeltaTreeInteriorNode; |
| |
| /// WidthFactor - This controls the number of K/V slots held in the BTree: |
| /// how wide it is. Each level of the BTree is guaranteed to have at least |
| /// WidthFactor-1 K/V pairs (except the root) and may have at most |
| /// 2*WidthFactor-1 K/V pairs. |
| enum { WidthFactor = 8 }; |
| |
| /// Values - This tracks the SourceDelta's currently in this node. |
| SourceDelta Values[2*WidthFactor-1]; |
| |
| /// NumValuesUsed - This tracks the number of values this node currently |
| /// holds. |
| unsigned char NumValuesUsed = 0; |
| |
| /// IsLeaf - This is true if this is a leaf of the btree. If false, this is |
| /// an interior node, and is actually an instance of DeltaTreeInteriorNode. |
| bool IsLeaf; |
| |
| /// FullDelta - This is the full delta of all the values in this node and |
| /// all children nodes. |
| int FullDelta = 0; |
| |
| public: |
| DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {} |
| |
| bool isLeaf() const { return IsLeaf; } |
| int getFullDelta() const { return FullDelta; } |
| bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; } |
| |
| unsigned getNumValuesUsed() const { return NumValuesUsed; } |
| |
| const SourceDelta &getValue(unsigned i) const { |
| assert(i < NumValuesUsed && "Invalid value #"); |
| return Values[i]; |
| } |
| |
| SourceDelta &getValue(unsigned i) { |
| assert(i < NumValuesUsed && "Invalid value #"); |
| return Values[i]; |
| } |
| |
| /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into |
| /// this node. If insertion is easy, do it and return false. Otherwise, |
| /// split the node, populate InsertRes with info about the split, and return |
| /// true. |
| bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); |
| |
| void DoSplit(InsertResult &InsertRes); |
| |
| |
| /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a |
| /// local walk over our contained deltas. |
| void RecomputeFullDeltaLocally(); |
| |
| void Destroy(); |
| }; |
| |
| /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. |
| /// This class tracks them. |
| class DeltaTreeInteriorNode : public DeltaTreeNode { |
| friend class DeltaTreeNode; |
| |
| DeltaTreeNode *Children[2*WidthFactor]; |
| |
| ~DeltaTreeInteriorNode() { |
| for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) |
| Children[i]->Destroy(); |
| } |
| |
| public: |
| DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} |
| |
| DeltaTreeInteriorNode(const InsertResult &IR) |
| : DeltaTreeNode(false /*nonleaf*/) { |
| Children[0] = IR.LHS; |
| Children[1] = IR.RHS; |
| Values[0] = IR.Split; |
| FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta; |
| NumValuesUsed = 1; |
| } |
| |
| const DeltaTreeNode *getChild(unsigned i) const { |
| assert(i < getNumValuesUsed()+1 && "Invalid child"); |
| return Children[i]; |
| } |
| |
| DeltaTreeNode *getChild(unsigned i) { |
| assert(i < getNumValuesUsed()+1 && "Invalid child"); |
| return Children[i]; |
| } |
| |
| static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } |
| }; |
| |
| } // namespace |
| |
| /// Destroy - A 'virtual' destructor. |
| void DeltaTreeNode::Destroy() { |
| if (isLeaf()) |
| delete this; |
| else |
| delete cast<DeltaTreeInteriorNode>(this); |
| } |
| |
| /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a |
| /// local walk over our contained deltas. |
| void DeltaTreeNode::RecomputeFullDeltaLocally() { |
| int NewFullDelta = 0; |
| for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) |
| NewFullDelta += Values[i].Delta; |
| if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) |
| for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) |
| NewFullDelta += IN->getChild(i)->getFullDelta(); |
| FullDelta = NewFullDelta; |
| } |
| |
| /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into |
| /// this node. If insertion is easy, do it and return false. Otherwise, |
| /// split the node, populate InsertRes with info about the split, and return |
| /// true. |
| bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, |
| InsertResult *InsertRes) { |
| // Maintain full delta for this node. |
| FullDelta += Delta; |
| |
| // Find the insertion point, the first delta whose index is >= FileIndex. |
| unsigned i = 0, e = getNumValuesUsed(); |
| while (i != e && FileIndex > getValue(i).FileLoc) |
| ++i; |
| |
| // If we found an a record for exactly this file index, just merge this |
| // value into the pre-existing record and finish early. |
| if (i != e && getValue(i).FileLoc == FileIndex) { |
| // NOTE: Delta could drop to zero here. This means that the delta entry is |
| // useless and could be removed. Supporting erases is more complex than |
| // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in |
| // the tree. |
| Values[i].Delta += Delta; |
| return false; |
| } |
| |
| // Otherwise, we found an insertion point, and we know that the value at the |
| // specified index is > FileIndex. Handle the leaf case first. |
| if (isLeaf()) { |
| if (!isFull()) { |
| // For an insertion into a non-full leaf node, just insert the value in |
| // its sorted position. This requires moving later values over. |
| if (i != e) |
| memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); |
| Values[i] = SourceDelta::get(FileIndex, Delta); |
| ++NumValuesUsed; |
| return false; |
| } |
| |
| // Otherwise, if this is leaf is full, split the node at its median, insert |
| // the value into one of the children, and return the result. |
| assert(InsertRes && "No result location specified"); |
| DoSplit(*InsertRes); |
| |
| if (InsertRes->Split.FileLoc > FileIndex) |
| InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); |
| else |
| InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); |
| return true; |
| } |
| |
| // Otherwise, this is an interior node. Send the request down the tree. |
| auto *IN = cast<DeltaTreeInteriorNode>(this); |
| if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) |
| return false; // If there was space in the child, just return. |
| |
| // Okay, this split the subtree, producing a new value and two children to |
| // insert here. If this node is non-full, we can just insert it directly. |
| if (!isFull()) { |
| // Now that we have two nodes and a new element, insert the perclated value |
| // into ourself by moving all the later values/children down, then inserting |
| // the new one. |
| if (i != e) |
| memmove(&IN->Children[i+2], &IN->Children[i+1], |
| (e-i)*sizeof(IN->Children[0])); |
| IN->Children[i] = InsertRes->LHS; |
| IN->Children[i+1] = InsertRes->RHS; |
| |
| if (e != i) |
| memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0])); |
| Values[i] = InsertRes->Split; |
| ++NumValuesUsed; |
| return false; |
| } |
| |
| // Finally, if this interior node was full and a node is percolated up, split |
| // ourself and return that up the chain. Start by saving all our info to |
| // avoid having the split clobber it. |
| IN->Children[i] = InsertRes->LHS; |
| DeltaTreeNode *SubRHS = InsertRes->RHS; |
| SourceDelta SubSplit = InsertRes->Split; |
| |
| // Do the split. |
| DoSplit(*InsertRes); |
| |
| // Figure out where to insert SubRHS/NewSplit. |
| DeltaTreeInteriorNode *InsertSide; |
| if (SubSplit.FileLoc < InsertRes->Split.FileLoc) |
| InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS); |
| else |
| InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS); |
| |
| // We now have a non-empty interior node 'InsertSide' to insert |
| // SubRHS/SubSplit into. Find out where to insert SubSplit. |
| |
| // Find the insertion point, the first delta whose index is >SubSplit.FileLoc. |
| i = 0; e = InsertSide->getNumValuesUsed(); |
| while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) |
| ++i; |
| |
| // Now we know that i is the place to insert the split value into. Insert it |
| // and the child right after it. |
| if (i != e) |
| memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1], |
| (e-i)*sizeof(IN->Children[0])); |
| InsertSide->Children[i+1] = SubRHS; |
| |
| if (e != i) |
| memmove(&InsertSide->Values[i+1], &InsertSide->Values[i], |
| (e-i)*sizeof(Values[0])); |
| InsertSide->Values[i] = SubSplit; |
| ++InsertSide->NumValuesUsed; |
| InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta(); |
| return true; |
| } |
| |
| /// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values) |
| /// into two subtrees each with "WidthFactor-1" values and a pivot value. |
| /// Return the pieces in InsertRes. |
| void DeltaTreeNode::DoSplit(InsertResult &InsertRes) { |
| assert(isFull() && "Why split a non-full node?"); |
| |
| // Since this node is full, it contains 2*WidthFactor-1 values. We move |
| // the first 'WidthFactor-1' values to the LHS child (which we leave in this |
| // node), propagate one value up, and move the last 'WidthFactor-1' values |
| // into the RHS child. |
| |
| // Create the new child node. |
| DeltaTreeNode *NewNode; |
| if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { |
| // If this is an interior node, also move over 'WidthFactor' children |
| // into the new node. |
| DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); |
| memcpy(&New->Children[0], &IN->Children[WidthFactor], |
| WidthFactor*sizeof(IN->Children[0])); |
| NewNode = New; |
| } else { |
| // Just create the new leaf node. |
| NewNode = new DeltaTreeNode(); |
| } |
| |
| // Move over the last 'WidthFactor-1' values from here to NewNode. |
| memcpy(&NewNode->Values[0], &Values[WidthFactor], |
| (WidthFactor-1)*sizeof(Values[0])); |
| |
| // Decrease the number of values in the two nodes. |
| NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; |
| |
| // Recompute the two nodes' full delta. |
| NewNode->RecomputeFullDeltaLocally(); |
| RecomputeFullDeltaLocally(); |
| |
| InsertRes.LHS = this; |
| InsertRes.RHS = NewNode; |
| InsertRes.Split = Values[WidthFactor-1]; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // DeltaTree Implementation |
| //===----------------------------------------------------------------------===// |
| |
| //#define VERIFY_TREE |
| |
| #ifdef VERIFY_TREE |
| /// VerifyTree - Walk the btree performing assertions on various properties to |
| /// verify consistency. This is useful for debugging new changes to the tree. |
| static void VerifyTree(const DeltaTreeNode *N) { |
| const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N); |
| if (IN == 0) { |
| // Verify leaves, just ensure that FullDelta matches up and the elements |
| // are in proper order. |
| int FullDelta = 0; |
| for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { |
| if (i) |
| assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); |
| FullDelta += N->getValue(i).Delta; |
| } |
| assert(FullDelta == N->getFullDelta()); |
| return; |
| } |
| |
| // Verify interior nodes: Ensure that FullDelta matches up and the |
| // elements are in proper order and the children are in proper order. |
| int FullDelta = 0; |
| for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { |
| const SourceDelta &IVal = N->getValue(i); |
| const DeltaTreeNode *IChild = IN->getChild(i); |
| if (i) |
| assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); |
| FullDelta += IVal.Delta; |
| FullDelta += IChild->getFullDelta(); |
| |
| // The largest value in child #i should be smaller than FileLoc. |
| assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < |
| IVal.FileLoc); |
| |
| // The smallest value in child #i+1 should be larger than FileLoc. |
| assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); |
| VerifyTree(IChild); |
| } |
| |
| FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); |
| |
| assert(FullDelta == N->getFullDelta()); |
| } |
| #endif // VERIFY_TREE |
| |
| static DeltaTreeNode *getRoot(void *Root) { |
| return (DeltaTreeNode*)Root; |
| } |
| |
| DeltaTree::DeltaTree() { |
| Root = new DeltaTreeNode(); |
| } |
| |
| DeltaTree::DeltaTree(const DeltaTree &RHS) { |
| // Currently we only support copying when the RHS is empty. |
| assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && |
| "Can only copy empty tree"); |
| Root = new DeltaTreeNode(); |
| } |
| |
| DeltaTree::~DeltaTree() { |
| getRoot(Root)->Destroy(); |
| } |
| |
| /// getDeltaAt - Return the accumulated delta at the specified file offset. |
| /// This includes all insertions or delections that occurred *before* the |
| /// specified file index. |
| int DeltaTree::getDeltaAt(unsigned FileIndex) const { |
| const DeltaTreeNode *Node = getRoot(Root); |
| |
| int Result = 0; |
| |
| // Walk down the tree. |
| while (true) { |
| // For all nodes, include any local deltas before the specified file |
| // index by summing them up directly. Keep track of how many were |
| // included. |
| unsigned NumValsGreater = 0; |
| for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; |
| ++NumValsGreater) { |
| const SourceDelta &Val = Node->getValue(NumValsGreater); |
| |
| if (Val.FileLoc >= FileIndex) |
| break; |
| Result += Val.Delta; |
| } |
| |
| // If we have an interior node, include information about children and |
| // recurse. Otherwise, if we have a leaf, we're done. |
| const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node); |
| if (!IN) return Result; |
| |
| // Include any children to the left of the values we skipped, all of |
| // their deltas should be included as well. |
| for (unsigned i = 0; i != NumValsGreater; ++i) |
| Result += IN->getChild(i)->getFullDelta(); |
| |
| // If we found exactly the value we were looking for, break off the |
| // search early. There is no need to search the RHS of the value for |
| // partial results. |
| if (NumValsGreater != Node->getNumValuesUsed() && |
| Node->getValue(NumValsGreater).FileLoc == FileIndex) |
| return Result+IN->getChild(NumValsGreater)->getFullDelta(); |
| |
| // Otherwise, traverse down the tree. The selected subtree may be |
| // partially included in the range. |
| Node = IN->getChild(NumValsGreater); |
| } |
| // NOT REACHED. |
| } |
| |
| /// AddDelta - When a change is made that shifts around the text buffer, |
| /// this method is used to record that info. It inserts a delta of 'Delta' |
| /// into the current DeltaTree at offset FileIndex. |
| void DeltaTree::AddDelta(unsigned FileIndex, int Delta) { |
| assert(Delta && "Adding a noop?"); |
| DeltaTreeNode *MyRoot = getRoot(Root); |
| |
| DeltaTreeNode::InsertResult InsertRes; |
| if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { |
| Root = MyRoot = new DeltaTreeInteriorNode(InsertRes); |
| } |
| |
| #ifdef VERIFY_TREE |
| VerifyTree(MyRoot); |
| #endif |
| } |