//===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file implements the DeltaTree and related classes.

//

//===----------------------------------------------------------------------===//

#include "clang/Rewrite/Core/DeltaTree.h"

#include "clang/Basic/LLVM.h"

#include "llvm/Support/Casting.h"

#include <cassert>

#include <cstring>

using namespace clang;

/// The DeltaTree class is a multiway search tree (BTree) structure with some

/// fancy features.  B-Trees are generally more memory and cache efficient

/// than binary trees, because they store multiple keys/values in each node.

///

/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing

/// fast lookup by FileIndex.  However, an added (important) bonus is that it

/// can also efficiently tell us the full accumulated delta for a specific

/// file offset as well, without traversing the whole tree.

///

/// The nodes of the tree are made up of instances of two classes:

/// DeltaTreeNode and DeltaTreeInteriorNode.  The later subclasses the

/// former and adds children pointers.  Each node knows the full delta of all

/// entries (recursively) contained inside of it, which allows us to get the

/// full delta implied by a whole subtree in constant time.

namespace {

  /// SourceDelta - As code in the original input buffer is added and deleted,

  /// SourceDelta records are used to keep track of how the input SourceLocation

  /// object is mapped into the output buffer.

  struct SourceDelta {

    unsigned FileLoc;

    int Delta;

    static SourceDelta get(unsigned Loc, int D) {

      SourceDelta Delta;

      Delta.FileLoc = Loc;

      Delta.Delta = D;

      return Delta;

    }

  };

  /// DeltaTreeNode - The common part of all nodes.

  ///

  class DeltaTreeNode {

  public:

    struct InsertResult {

      DeltaTreeNode *LHS, *RHS;

      SourceDelta Split;

    };

  private:

    friend class DeltaTreeInteriorNode;

    /// WidthFactor - This controls the number of K/V slots held in the BTree:

    /// how wide it is.  Each level of the BTree is guaranteed to have at least

    /// WidthFactor-1 K/V pairs (except the root) and may have at most

    /// 2*WidthFactor-1 K/V pairs.

    enum { WidthFactor = 8 };

    /// Values - This tracks the SourceDelta's currently in this node.

    SourceDelta Values[2*WidthFactor-1];

    /// NumValuesUsed - This tracks the number of values this node currently

    /// holds.

    unsigned char NumValuesUsed = 0;

    /// IsLeaf - This is true if this is a leaf of the btree.  If false, this is

    /// an interior node, and is actually an instance of DeltaTreeInteriorNode.

    bool IsLeaf;

    /// FullDelta - This is the full delta of all the values in this node and

    /// all children nodes.

    int FullDelta = 0;

  public:

    DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}

    bool isLeaf() const { return IsLeaf; }

    int getFullDelta() const { return FullDelta; }

    bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }

    unsigned getNumValuesUsed() const { return NumValuesUsed; }

    const SourceDelta &getValue(unsigned i) const {

      assert(i < NumValuesUsed && "Invalid value #");

      return Values[i];

    }

    SourceDelta &getValue(unsigned i) {

      assert(i < NumValuesUsed && "Invalid value #");

      return Values[i];

    }

    /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into

    /// this node.  If insertion is easy, do it and return false.  Otherwise,

    /// split the node, populate InsertRes with info about the split, and return

    /// true.

    bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);

    void DoSplit(InsertResult &InsertRes);

    /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a

    /// local walk over our contained deltas.

    void RecomputeFullDeltaLocally();

    void Destroy();

  };

  /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.

  /// This class tracks them.

  class DeltaTreeInteriorNode : public DeltaTreeNode {

    friend class DeltaTreeNode;

    DeltaTreeNode *Children[2*WidthFactor];

    ~DeltaTreeInteriorNode() {

      for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)

        Children[i]->Destroy();

    }

  public:

    DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}

    DeltaTreeInteriorNode(const InsertResult &IR)

        : DeltaTreeNode(false /*nonleaf*/) {

      Children[0] = IR.LHS;

      Children[1] = IR.RHS;

      Values[0] = IR.Split;

      FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;

      NumValuesUsed = 1;

    }

    const DeltaTreeNode *getChild(unsigned i) const {

      assert(i < getNumValuesUsed()+1 && "Invalid child");

      return Children[i];

    }

    DeltaTreeNode *getChild(unsigned i) {

      assert(i < getNumValuesUsed()+1 && "Invalid child");

      return Children[i];

    }

    static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }

  };

} // namespace

/// Destroy - A 'virtual' destructor.

void DeltaTreeNode::Destroy() {

  if (isLeaf())

    delete this;

  else

    delete cast<DeltaTreeInteriorNode>(this);

}

/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a

/// local walk over our contained deltas.

void DeltaTreeNode::RecomputeFullDeltaLocally() {

  int NewFullDelta = 0;

  for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)

    NewFullDelta += Values[i].Delta;

  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this))

    for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)

      NewFullDelta += IN->getChild(i)->getFullDelta();

  FullDelta = NewFullDelta;

}

/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into

/// this node.  If insertion is easy, do it and return false.  Otherwise,

/// split the node, populate InsertRes with info about the split, and return

/// true.

bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,

                                InsertResult *InsertRes) {

  // Maintain full delta for this node.

  FullDelta += Delta;

  // Find the insertion point, the first delta whose index is >= FileIndex.

  unsigned i = 0, e = getNumValuesUsed();

  while (i != e && FileIndex > getValue(i).FileLoc)

    ++i;

  // If we found an a record for exactly this file index, just merge this

  // value into the pre-existing record and finish early.

  if (i != e && getValue(i).FileLoc == FileIndex) {

    // NOTE: Delta could drop to zero here.  This means that the delta entry is

    // useless and could be removed.  Supporting erases is more complex than

    // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in

    // the tree.

    Values[i].Delta += Delta;

    return false;

  }

  // Otherwise, we found an insertion point, and we know that the value at the

  // specified index is > FileIndex.  Handle the leaf case first.

  if (isLeaf()) {

    if (!isFull()) {

      // For an insertion into a non-full leaf node, just insert the value in

      // its sorted position.  This requires moving later values over.

      if (i != e)

        memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));

      Values[i] = SourceDelta::get(FileIndex, Delta);

      ++NumValuesUsed;

      return false;

    }

    // Otherwise, if this is leaf is full, split the node at its median, insert

    // the value into one of the children, and return the result.

    assert(InsertRes && "No result location specified");

    DoSplit(*InsertRes);

    if (InsertRes->Split.FileLoc > FileIndex)

      InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);

    else

      InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);

    return true;

  }

  // Otherwise, this is an interior node.  Send the request down the tree.

  auto *IN = cast<DeltaTreeInteriorNode>(this);

  if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))

    return false; // If there was space in the child, just return.

  // Okay, this split the subtree, producing a new value and two children to

  // insert here.  If this node is non-full, we can just insert it directly.

  if (!isFull()) {

    // Now that we have two nodes and a new element, insert the perclated value

    // into ourself by moving all the later values/children down, then inserting

    // the new one.

    if (i != e)

      memmove(&IN->Children[i+2], &IN->Children[i+1],

              (e-i)*sizeof(IN->Children[0]));

    IN->Children[i] = InsertRes->LHS;

    IN->Children[i+1] = InsertRes->RHS;

    if (e != i)

      memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));

    Values[i] = InsertRes->Split;

    ++NumValuesUsed;

    return false;

  }

  // Finally, if this interior node was full and a node is percolated up, split

  // ourself and return that up the chain.  Start by saving all our info to

  // avoid having the split clobber it.

  IN->Children[i] = InsertRes->LHS;

  DeltaTreeNode *SubRHS = InsertRes->RHS;

  SourceDelta SubSplit = InsertRes->Split;

  // Do the split.

  DoSplit(*InsertRes);

  // Figure out where to insert SubRHS/NewSplit.

  DeltaTreeInteriorNode *InsertSide;

  if (SubSplit.FileLoc < InsertRes->Split.FileLoc)

    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);

  else

    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);

  // We now have a non-empty interior node 'InsertSide' to insert

  // SubRHS/SubSplit into.  Find out where to insert SubSplit.

  // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.

  i = 0; e = InsertSide->getNumValuesUsed();

  while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)

    ++i;

  // Now we know that i is the place to insert the split value into.  Insert it

  // and the child right after it.

  if (i != e)

    memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],

            (e-i)*sizeof(IN->Children[0]));

  InsertSide->Children[i+1] = SubRHS;

  if (e != i)

    memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],

            (e-i)*sizeof(Values[0]));

  InsertSide->Values[i] = SubSplit;

  ++InsertSide->NumValuesUsed;

  InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();

  return true;

}

/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)

/// into two subtrees each with "WidthFactor-1" values and a pivot value.

/// Return the pieces in InsertRes.

void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {

  assert(isFull() && "Why split a non-full node?");

  // Since this node is full, it contains 2*WidthFactor-1 values.  We move

  // the first 'WidthFactor-1' values to the LHS child (which we leave in this

  // node), propagate one value up, and move the last 'WidthFactor-1' values

  // into the RHS child.

  // Create the new child node.

  DeltaTreeNode *NewNode;

  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {

    // If this is an interior node, also move over 'WidthFactor' children

    // into the new node.

    DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();

    memcpy(&New->Children[0], &IN->Children[WidthFactor],

           WidthFactor*sizeof(IN->Children[0]));

    NewNode = New;

  } else {

    // Just create the new leaf node.

    NewNode = new DeltaTreeNode();

  }

  // Move over the last 'WidthFactor-1' values from here to NewNode.

  memcpy(&NewNode->Values[0], &Values[WidthFactor],

         (WidthFactor-1)*sizeof(Values[0]));

  // Decrease the number of values in the two nodes.

  NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;

  // Recompute the two nodes' full delta.

  NewNode->RecomputeFullDeltaLocally();

  RecomputeFullDeltaLocally();

  InsertRes.LHS = this;

  InsertRes.RHS = NewNode;

  InsertRes.Split = Values[WidthFactor-1];

}

//===----------------------------------------------------------------------===//

//                        DeltaTree Implementation

//===----------------------------------------------------------------------===//

//#define VERIFY_TREE

#ifdef VERIFY_TREE

/// VerifyTree - Walk the btree performing assertions on various properties to

/// verify consistency.  This is useful for debugging new changes to the tree.

static void VerifyTree(const DeltaTreeNode *N) {

  const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N);

  if (IN == 0) {

    // Verify leaves, just ensure that FullDelta matches up and the elements

    // are in proper order.

    int FullDelta = 0;

    for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {

      if (i)

        assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);

      FullDelta += N->getValue(i).Delta;

    }

    assert(FullDelta == N->getFullDelta());

    return;

  }

  // Verify interior nodes: Ensure that FullDelta matches up and the

  // elements are in proper order and the children are in proper order.

  int FullDelta = 0;

  for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {

    const SourceDelta &IVal = N->getValue(i);

    const DeltaTreeNode *IChild = IN->getChild(i);

    if (i)

      assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);

    FullDelta += IVal.Delta;

    FullDelta += IChild->getFullDelta();

    // The largest value in child #i should be smaller than FileLoc.

    assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <

           IVal.FileLoc);

    // The smallest value in child #i+1 should be larger than FileLoc.

    assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);

    VerifyTree(IChild);

  }

  FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();

  assert(FullDelta == N->getFullDelta());

}

#endif  // VERIFY_TREE

static DeltaTreeNode *getRoot(void *Root) {

  return (DeltaTreeNode*)Root;

}

DeltaTree::DeltaTree() {

  Root = new DeltaTreeNode();

}

DeltaTree::DeltaTree(const DeltaTree &RHS) {

  // Currently we only support copying when the RHS is empty.

  assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&

         "Can only copy empty tree");

  Root = new DeltaTreeNode();

}

DeltaTree::~DeltaTree() {

  getRoot(Root)->Destroy();

}

/// getDeltaAt - Return the accumulated delta at the specified file offset.

/// This includes all insertions or delections that occurred *before* the

/// specified file index.

int DeltaTree::getDeltaAt(unsigned FileIndex) const {

  const DeltaTreeNode *Node = getRoot(Root);

  int Result = 0;

  // Walk down the tree.

  while (true) {

    // For all nodes, include any local deltas before the specified file

    // index by summing them up directly.  Keep track of how many were

    // included.

    unsigned NumValsGreater = 0;

    for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;

         ++NumValsGreater) {

      const SourceDelta &Val = Node->getValue(NumValsGreater);

      if (Val.FileLoc >= FileIndex)

        break;

      Result += Val.Delta;

    }

    // If we have an interior node, include information about children and

    // recurse.  Otherwise, if we have a leaf, we're done.

    const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node);

    if (!IN) return Result;

    // Include any children to the left of the values we skipped, all of

    // their deltas should be included as well.

    for (unsigned i = 0; i != NumValsGreater; ++i)

      Result += IN->getChild(i)->getFullDelta();

    // If we found exactly the value we were looking for, break off the

    // search early.  There is no need to search the RHS of the value for

    // partial results.

    if (NumValsGreater != Node->getNumValuesUsed() &&

        Node->getValue(NumValsGreater).FileLoc == FileIndex)

      return Result+IN->getChild(NumValsGreater)->getFullDelta();

    // Otherwise, traverse down the tree.  The selected subtree may be

    // partially included in the range.

    Node = IN->getChild(NumValsGreater);

  }

  // NOT REACHED.

}

/// AddDelta - When a change is made that shifts around the text buffer,

/// this method is used to record that info.  It inserts a delta of 'Delta'

/// into the current DeltaTree at offset FileIndex.

void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {

  assert(Delta && "Adding a noop?");

  DeltaTreeNode *MyRoot = getRoot(Root);

  DeltaTreeNode::InsertResult InsertRes;

  if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {

    Root = new DeltaTreeInteriorNode(InsertRes);

#ifdef VERIFY_TREE

    MyRoot = Root;

#endif

  }

#ifdef VERIFY_TREE

  VerifyTree(MyRoot);

#endif

}