File indexing completed on 2024-05-12 04:38:09

 /*
     SPDX-FileCopyrightText: 2007 David Nolden <david.nolden.kdevelop@art-master.de>
 
     SPDX-License-Identifier: GPL-2.0-or-later
 */
 
 #include "setrepository.h"
 #include <debug.h>
 #include <list>
 #include <util/kdevvarlengtharray.h>
 #include <iostream>
 #include <limits>
 #include <serialization/itemrepository.h>
 #include <serialization/indexedstring.h>
 #include <QString>
 #include <QMutex>
 #include <algorithm>
 
 //#define DEBUG_SETREPOSITORY
 
 #ifdef DEBUG_SETREPOSITORY
 #define ifDebug(X) X
 #else
 #define ifDebug(x)
 #undef Q_ASSERT
 #define Q_ASSERT(x)
 #endif
 
 #ifndef DEBUG_SETREPOSITORY
 #define CHECK_SPLIT_POSITION(Node)
 #else
 #define CHECK_SPLIT_POSITION(node) Q_ASSERT(!(node).leftNode || \
                                             (getLeftNode(&node)->end() <= \
                                              splitPositionForRange((node).start, \
                                                                    (node).end) && \
                                              getRightNode(&node)->start() >= \
                                              splitPositionForRange((node).start, (node).end)))
 #endif
 
 namespace Utils {
 /**
  * To achieve a maximum re-usage of nodes, we make sure that sub-nodes of a node always split at specific boundaries.
  * For each range we can compute a position where that range should be split into its child-nodes.
  * When creating a new node with 2 sub-nodes, we re-create those child-nodes if their boundaries don't represent those split-positions.
  *
  * We pick the split-positions deterministically, they are in order of priority:
  * ((1<<31)*n, n = [0,...]
  * ((1<<30)*n, n = [0,...]
  * ((1<<29)*n, n = [0,...]
  * ((1<<...)*n, n = [0,...]
  * ...
  * */
 
 using Index = BasicSetRepository::Index;
 
 ///The returned split position shall be the end of the first sub-range, and the start of the second
 ///@param splitBit should be initialized with 31, unless you know better. The value can then be used on while computing child split positions.
 ///In the end, it will contain the bit used to split the range. It will also contain zero if no split-position exists(length 1)
 uint splitPositionForRange(uint start, uint end, uchar& splitBit)
 {
     if (end - start == 1) {
         splitBit = 0;
         return 0;
     }
 
     while (true) {
         uint position = ((end - 1) >> splitBit) << splitBit; //Round to the split-position in this interval that is smaller than end
         if (position > start && position < end)
             return position;
         Q_ASSERT(splitBit != 0);
         --splitBit;
     }
 
     return 0;
 }
 
 uint splitPositionForRange(uint start, uint end)
 {
     uchar splitBit = 31;
     return splitPositionForRange(start, end, splitBit);
 }
 
 class SetNodeDataRequest;
 
     #define getLeftNode(node) repository.itemFromIndex(node->leftNode())
     #define getRightNode(node) repository.itemFromIndex(node->rightNode())
     #define nodeFromIndex(index) repository.itemFromIndex(index)
 struct SetRepositoryAlgorithms
 {
     SetRepositoryAlgorithms(SetDataRepository& _repository,
                             BasicSetRepository* _setRepository) : repository(_repository)
         , setRepository(_setRepository)
     {
     }
 
     ///Expensive
     Index count(const SetNodeData* node) const;
 
     void localCheck(const SetNodeData* node);
 
     void check(uint node);
 
     void check(const SetNodeData* node);
 
     QString shortLabel(const SetNodeData& node) const;
 
     uint set_union(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second,
                    uchar splitBit = 31);
     uint createSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left = nullptr,
                             const SetNodeData* right = nullptr);
     uint computeSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left, const SetNodeData* right,
                              uchar splitBit);
     uint set_intersect(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second,
                        uchar splitBit = 31);
     bool set_contains(const SetNodeData* node, Index index);
     uint set_subtract(uint firstNode, uint secondNode, const SetNodeData* first, const SetNodeData* second,
                       uchar splitBit = 31);
 
     //Required both nodes to be split correctly
     bool set_equals(const SetNodeData* lhs, const SetNodeData* rhs);
 
     QString dumpDotGraph(uint node) const;
 
     ///Finds or inserts the given ranges into the repository, and returns the set-index that represents them
     uint setForIndices(std::vector<uint>::const_iterator begin, std::vector<uint>::const_iterator end,
                        uchar splitBit = 31)
     {
         Q_ASSERT(begin != end);
 
         uint startIndex = *begin;
         uint endIndex = *(end - 1) + 1;
 
         if (endIndex == startIndex + 1) {
             SetNodeData data(startIndex, endIndex);
 
             return repository.index(SetNodeDataRequest(&data, repository, setRepository));
         }
 
         uint split = splitPositionForRange(startIndex, endIndex, splitBit);
         Q_ASSERT(split);
 
         auto splitIterator = std::lower_bound(begin, end, split);
         Q_ASSERT(*splitIterator >= split);
         Q_ASSERT(splitIterator > begin);
         Q_ASSERT(*(splitIterator - 1) < split);
 
         return createSetFromNodes(setForIndices(begin, splitIterator, splitBit),
                                   setForIndices(splitIterator, end, splitBit));
     }
 
 private:
     QString dumpDotGraphInternal(uint node, bool master = false) const;
 
     SetDataRepository& repository;
     BasicSetRepository* setRepository;
 };
 
 void SetNodeDataRequest::destroy(SetNodeData* data, KDevelop::AbstractItemRepository& _repository)
 {
     auto& repository(static_cast<SetDataRepository&>(_repository));
 
     if (repository.setRepository->delayedDeletion()) {
         if (data->leftNode()) {
             SetDataRepositoryBase::MyDynamicItem left = repository.dynamicItemFromIndex(data->leftNode());
             SetDataRepositoryBase::MyDynamicItem right = repository.dynamicItemFromIndex(data->rightNode());
             Q_ASSERT(left->m_refCount > 0);
             --left->m_refCount;
             Q_ASSERT(right->m_refCount > 0);
             --right->m_refCount;
         } else {
             //Deleting a leaf
             Q_ASSERT(data->end() - data->start() == 1);
             repository.setRepository->itemRemovedFromSets(data->start());
         }
     }
 }
 
 SetNodeDataRequest::SetNodeDataRequest(const SetNodeData* _data, SetDataRepository& _repository,
                                        BasicSetRepository* _setRepository) : data(*_data)
     , m_hash(_data->hash())
     , repository(_repository)
     , setRepository(_setRepository)
     , m_created(false)
 {
     ifDebug(SetRepositoryAlgorithms alg(repository); alg.check(_data));
 }
 
 SetNodeDataRequest::~SetNodeDataRequest()
 {
     //Eventually increase the reference-count of direct children
     if (m_created) {
         if (data.leftNode())
             ++repository.dynamicItemFromIndex(data.leftNode())->m_refCount;
         if (data.rightNode())
             ++repository.dynamicItemFromIndex(data.rightNode())->m_refCount;
     }
 }
 
 //Should create an item where the information of the requested item is permanently stored. The pointer
 //@param item equals an allocated range with the size of itemSize().
 void SetNodeDataRequest::createItem(SetNodeData* item) const
 {
     Q_ASSERT((data.rightNode() && data.leftNode()) || (!data.rightNode() && !data.leftNode()));
 
     m_created = true;
 
     *item = data;
 
     Q_ASSERT((item->rightNode() && item->leftNode()) || (!item->rightNode() && !item->leftNode()));
 
 #ifdef DEBUG_SETREPOSITORY
     //Make sure we split at the correct split position
     if (item->hasSlaves()) {
         uint split = splitPositionForRange(data.start, data.end);
         const SetNodeData* left = repository.itemFromIndex(item->leftNode());
         const SetNodeData* right = repository.itemFromIndex(item->rightNode());
         Q_ASSERT(split >= left->end() && split <= right->start());
     }
 #endif
     if (!data.leftNode() && setRepository) {
         for (uint a = item->start(); a < item->end(); ++a)
             setRepository->itemAddedToSets(a);
     }
 }
 
 bool SetNodeDataRequest::equals(const SetNodeData* item) const
 {
     Q_ASSERT((item->rightNode() && item->leftNode()) || (!item->rightNode() && !item->leftNode()));
     //Just compare child nodes, since data must be correctly split, this is perfectly ok
     //Since this happens in very tight loops, we don't call an additional function here, but just do the check.
     return item->leftNode() == data.leftNode() && item->rightNode() == data.rightNode() &&
            item->start() == data.start() && item->end() == data.end();
 }
 
 Set::Set()
 {
 }
 
 Set::~Set()
 {
 }
 
 unsigned int Set::count() const
 {
     if (!m_repository || !m_tree)
         return 0;
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
     return alg.count(m_repository->m_dataRepository.itemFromIndex(m_tree));
 }
 
 Set::Set(uint treeNode, BasicSetRepository* repository) : m_tree(treeNode)
     , m_repository(repository)
 {
 }
 
 Set::Set(const Set& rhs)
 {
     m_repository = rhs.m_repository;
     m_tree = rhs.m_tree;
 }
 
 Set& Set::operator=(const Set& rhs)
 {
     m_repository = rhs.m_repository;
     m_tree = rhs.m_tree;
     return *this;
 }
 
 QString Set::dumpDotGraph() const
 {
     if (!m_repository || !m_tree)
         return QString();
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
     return alg.dumpDotGraph(m_tree);
 }
 
 Index SetRepositoryAlgorithms::count(const SetNodeData* node) const
 {
     if (node->leftNode() && node->rightNode())
         return count(getLeftNode(node)) + count(getRightNode(node));
     else
         return node->end() - node->start();
 }
 
 void SetRepositoryAlgorithms::localCheck(const SetNodeData* ifDebug(node))
 {
 //   Q_ASSERT(node->start() > 0);
     Q_ASSERT(node->start() < node->end());
     Q_ASSERT((node->leftNode() && node->rightNode()) || (!node->leftNode() && !node->rightNode()));
     Q_ASSERT(!node->leftNode() ||
              (getLeftNode(node())->start() == node->start() && getRightNode(node)->end() == node->end()));
     Q_ASSERT(!node->leftNode() || (getLeftNode(node())->end() <= getRightNode(node)->start()));
 }
 
 void SetRepositoryAlgorithms::check(uint node)
 {
     if (!node)
         return;
 
     check(nodeFromIndex(node));
 }
 
 void SetRepositoryAlgorithms::check(const SetNodeData* node)
 {
     localCheck(node);
     if (node->leftNode())
         check(getLeftNode(node));
     if (node->rightNode())
         check(getRightNode(node));
 //  CHECK_SPLIT_POSITION(*node); Re-enable this
 }
 
 QString SetRepositoryAlgorithms::shortLabel(const SetNodeData& node) const
 {
     return QStringLiteral("n%1_%2").arg(node.start()).arg(node.end());
 }
 
 QString SetRepositoryAlgorithms::dumpDotGraphInternal(uint nodeIndex, bool master) const
 {
     if (!nodeIndex)
         return QStringLiteral("empty node");
 
     const SetNodeData& node(*repository.itemFromIndex(nodeIndex));
 
     QString color = QStringLiteral("blue");
     if (master)
         color = QStringLiteral("red");
 
     QString label = QStringLiteral("%1 -> %2").arg(node.start()).arg(node.end());
     if (!node.contiguous())
         label += QLatin1String(", with gaps");
 
     QString ret = QStringLiteral("%1[label=\"%2\", color=\"%3\"];\n").arg(shortLabel(node), label, color);
 
     if (node.leftNode()) {
         const SetNodeData& left(*repository.itemFromIndex(node.leftNode()));
         const SetNodeData& right(*repository.itemFromIndex(node.rightNode()));
         Q_ASSERT(node.rightNode());
         ret += QStringLiteral("%1 -> %2;\n").arg(shortLabel(node), shortLabel(left));
         ret += QStringLiteral("%1 -> %2;\n").arg(shortLabel(node), shortLabel(right));
         ret += dumpDotGraphInternal(node.leftNode());
         ret += dumpDotGraphInternal(node.rightNode());
     }
 
     return ret;
 }
 
 QString SetRepositoryAlgorithms::dumpDotGraph(uint nodeIndex) const
 {
     QString ret = QStringLiteral("digraph Repository {\n");
     ret += dumpDotGraphInternal(nodeIndex, true);
     ret += QLatin1String("}\n");
     return ret;
 }
 
 const int nodeStackAlloc = 500;
 
 class Set::IteratorPrivate
 {
 public:
     IteratorPrivate()
     {
         nodeStackData.resize(nodeStackAlloc);
         nodeStack = nodeStackData.data();
     }
 
     IteratorPrivate(const Set::IteratorPrivate& rhs)
         : nodeStackData(rhs.nodeStackData)
         , nodeStackSize(rhs.nodeStackSize)
         , currentIndex(rhs.currentIndex)
         , repository(rhs.repository)
     {
         nodeStack = nodeStackData.data();
     }
 
     Set::IteratorPrivate& operator=(const Set::IteratorPrivate& rhs)
     {
         nodeStackData = rhs.nodeStackData;
         nodeStackSize = rhs.nodeStackSize;
         currentIndex = rhs.currentIndex;
         repository = rhs.repository;
         nodeStack = nodeStackData.data();
 
         return *this;
     }
 
     void resizeNodeStack()
     {
         nodeStackData.resize(nodeStackSize + 1);
         nodeStack = nodeStackData.data();
     }
 
     KDevVarLengthArray<const SetNodeData*, nodeStackAlloc> nodeStackData;
     const SetNodeData** nodeStack;
     int nodeStackSize = 0;
     Index currentIndex = 0;
     BasicSetRepository* repository = nullptr;
 
     /**
      * Pushes the noed on top of the stack, changes currentIndex, and goes as deep as necessary for iteration.
      * */
     void startAtNode(const SetNodeData* node)
     {
         Q_ASSERT(node->start() != node->end());
         currentIndex = node->start();
 
         do {
             nodeStack[nodeStackSize++] = node;
 
             if (nodeStackSize >= nodeStackAlloc)
                 resizeNodeStack();
 
             if (node->contiguous())
                 break; //We need no finer granularity, because the range is contiguous
             node = Set::Iterator::getDataRepository(repository).itemFromIndex(node->leftNode());
         } while (node);
         Q_ASSERT(currentIndex >= nodeStack[0]->start());
     }
 };
 
 std::set<Index> Set::stdSet() const
 {
     Set::Iterator it = iterator();
     std::set<Index> ret;
 
     while (it) {
         Q_ASSERT(ret.find(*it) == ret.end());
         ret.insert(*it);
         ++it;
     }
 
     return ret;
 }
 
 Set::Iterator::Iterator(const Iterator& rhs)
     : d_ptr(new Set::IteratorPrivate(*rhs.d_ptr))
 {
 }
 
 Set::Iterator& Set::Iterator::operator=(const Iterator& rhs)
 {
     *d_ptr = *rhs.d_ptr;
     return *this;
 }
 
 Set::Iterator::Iterator()
     : d_ptr(new Set::IteratorPrivate)
 {
 }
 
 Set::Iterator::~Iterator() = default;
 
 Set::Iterator::operator bool() const
 {
     Q_D(const Iterator);
 
     return d->nodeStackSize;
 }
 
 Set::Iterator& Set::Iterator::operator++()
 {
     Q_D(Iterator);
 
     Q_ASSERT(d->nodeStackSize);
 
     if (d->repository->m_mutex)
         d->repository->m_mutex->lock();
 
     ++d->currentIndex;
 
     //const SetNodeData** currentNode = &d->nodeStack[d->nodeStackSize - 1];
     if (d->currentIndex >= d->nodeStack[d->nodeStackSize - 1]->end()) {
         //Advance to the next node
         while (d->nodeStackSize && d->currentIndex >= d->nodeStack[d->nodeStackSize - 1]->end()) {
             --d->nodeStackSize;
         }
 
         if (!d->nodeStackSize) {
             //ready
         } else {
             //++d->nodeStackSize;
             //We were iterating the left slave of the node, now continue with the right.
             ifDebug(const SetNodeData& left =
                         *d->repository->m_dataRepository.itemFromIndex(
                             d->nodeStack[d->nodeStackSize - 1]->leftNode()); Q_ASSERT(left.end == d->currentIndex); )
 
             const SetNodeData& right = *d->repository->m_dataRepository.itemFromIndex(
                 d->nodeStack[d->nodeStackSize - 1]->rightNode());
 
             d->startAtNode(&right);
         }
     }
 
     Q_ASSERT(d->nodeStackSize == 0 || d->currentIndex < d->nodeStack[0]->end());
 
     if (d->repository->m_mutex)
         d->repository->m_mutex->unlock();
 
     return *this;
 }
 
 BasicSetRepository::Index Set::Iterator::operator*() const
 {
     Q_D(const Iterator);
 
     return d->currentIndex;
 }
 
 Set::Iterator Set::iterator() const
 {
     if (!m_tree || !m_repository)
         return Iterator();
 
     QMutexLocker lock(m_repository->m_mutex);
 
     Iterator ret;
     ret.d_ptr->repository = m_repository;
 
     if (m_tree)
         ret.d_ptr->startAtNode(m_repository->m_dataRepository.itemFromIndex(m_tree));
     return ret;
 }
 
 //Creates a set item with the given children., they must be valid, and they must be split around their split-position.
 uint SetRepositoryAlgorithms::createSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left,
                                                  const SetNodeData* right)
 {
     if (!left)
         left = nodeFromIndex(leftNode);
     if (!right)
         right = nodeFromIndex(rightNode);
 
     Q_ASSERT(left->end() <= right->start());
 
     SetNodeData set(left->start(), right->end(), leftNode, rightNode);
 
     Q_ASSERT(set.start() < set.end());
 
     uint ret = repository.index(SetNodeDataRequest(&set, repository, setRepository));
     Q_ASSERT(set.leftNode() >= 0x10000);
     Q_ASSERT(set.rightNode() >= 0x10000);
     Q_ASSERT(ret == repository.findIndex(SetNodeDataRequest(&set, repository, setRepository)));
     ifDebug(check(ret));
     return ret;
 }
 
 //Constructs a set node from the given two sub-nodes. Those must be valid, they must not intersect, and they must have a correct split-hierarchy.
 //The do not need to be split around their computed split-position.
 uint SetRepositoryAlgorithms::computeSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left,
                                                   const SetNodeData* right, uchar splitBit)
 {
     Q_ASSERT(left->end() <= right->start());
     uint splitPosition = splitPositionForRange(left->start(), right->end(), splitBit);
 
     Q_ASSERT(splitPosition);
 
     if (splitPosition < left->end()) {
         //The split-position intersects the left node
         uint leftLeftNode = left->leftNode();
         uint leftRightNode = left->rightNode();
 
         const SetNodeData* leftLeft = this->getLeftNode(left);
         const SetNodeData* leftRight = this->getRightNode(left);
 
         Q_ASSERT(splitPosition >= leftLeft->end() && splitPosition <= leftRight->start());
 
         //Create a new set from leftLeft, and from leftRight + right. That set will have the correct split-position.
         uint newRightNode = computeSetFromNodes(leftRightNode, rightNode, leftRight, right, splitBit);
 
         return createSetFromNodes(leftLeftNode, newRightNode, leftLeft);
     } else if (splitPosition > right->start()) {
         //The split-position intersects the right node
         uint rightLeftNode = right->leftNode();
         uint rightRightNode = right->rightNode();
 
         const SetNodeData* rightLeft = this->getLeftNode(right);
         const SetNodeData* rightRight = this->getRightNode(right);
 
         Q_ASSERT(splitPosition >= rightLeft->end() && splitPosition <= rightRight->start());
 
         //Create a new set from left + rightLeft, and from rightRight. That set will have the correct split-position.
         uint newLeftNode = computeSetFromNodes(leftNode, rightLeftNode, left, rightLeft, splitBit);
 
         return createSetFromNodes(newLeftNode, rightRightNode, nullptr, rightRight);
     } else {
         return createSetFromNodes(leftNode, rightNode, left, right);
     }
 }
 
 uint SetRepositoryAlgorithms::set_union(uint firstNode, uint secondNode, const SetNodeData* first,
                                         const SetNodeData* second, uchar splitBit)
 {
     if (firstNode == secondNode)
         return firstNode;
 
     uint firstStart = first->start(), secondEnd = second->end();
 
     if (firstStart >= secondEnd)
         return computeSetFromNodes(secondNode, firstNode, second, first, splitBit);
 
     uint firstEnd = first->end(), secondStart = second->start();
 
     if (secondStart >= firstEnd)
         return computeSetFromNodes(firstNode, secondNode, first, second, splitBit);
 
     //The ranges of first and second do intersect
 
     uint newStart = firstStart < secondStart ? firstStart : secondStart;
     uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd;
 
     //Compute the split-position for the resulting merged node
     uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit);
 
     //Since the ranges overlap, we can be sure that either first or second contain splitPosition.
     //The node that contains it, will also be split by it.
 
     if (splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart &&
         splitPosition < secondEnd) {
         //The split-position intersect with both first and second. Continue the union on both sides of the split-position, and merge it.
 
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         return createSetFromNodes(set_union(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit),
                                   set_union(firstRightNode, secondRightNode, firstRight, secondRight, splitBit));
     } else if (splitPosition > firstStart && splitPosition < firstEnd) {
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
 
         Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
 
         //splitPosition does not intersect second. That means that second is completely on one side of it.
         //So we only need to union that side of first with second.
 
         if (secondEnd <= splitPosition) {
             return createSetFromNodes(set_union(firstLeftNode, secondNode, firstLeft, second,
                                                 splitBit), firstRightNode, nullptr, firstRight);
         } else {
             Q_ASSERT(secondStart >= splitPosition);
             return createSetFromNodes(firstLeftNode, set_union(firstRightNode, secondNode, firstRight, second,
                                                                splitBit), firstLeft);
         }
     } else if (splitPosition > secondStart && splitPosition < secondEnd) {
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         if (firstEnd <= splitPosition) {
             return createSetFromNodes(set_union(secondLeftNode, firstNode, secondLeft, first,
                                                 splitBit), secondRightNode, nullptr, secondRight);
         } else {
             Q_ASSERT(firstStart >= splitPosition);
             return createSetFromNodes(secondLeftNode, set_union(secondRightNode, firstNode, secondRight, first,
                                                                 splitBit), secondLeft);
         }
     } else {
         //We would have stopped earlier of first and second don't intersect
         ifDebug(uint test = repository.findIndex(SetNodeDataRequest(first, repository, setRepository)); qCDebug(
                     LANGUAGE) << "found index:" << test; )
         Q_ASSERT(0);
         return 0;
     }
 }
 
 bool SetRepositoryAlgorithms::set_equals(const SetNodeData* lhs, const SetNodeData* rhs)
 {
     if (lhs->leftNode() != rhs->leftNode() || lhs->rightNode() != rhs->rightNode())
         return false;
     else
         return true;
 }
 
 uint SetRepositoryAlgorithms::set_intersect(uint firstNode, uint secondNode, const SetNodeData* first,
                                             const SetNodeData* second, uchar splitBit)
 {
     if (firstNode == secondNode)
         return firstNode;
 
     if (first->start() >= second->end())
         return 0;
 
     if (second->start() >= first->end())
         return 0;
 
     //The ranges of first and second do intersect
     uint firstStart = first->start(), firstEnd = first->end(), secondStart = second->start(), secondEnd = second->end();
 
     uint newStart = firstStart < secondStart ? firstStart : secondStart;
     uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd;
 
     //Compute the split-position for the resulting merged node
     uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit);
 
     //Since the ranges overlap, we can be sure that either first or second contain splitPosition.
     //The node that contains it, will also be split by it.
 
     if (splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart &&
         splitPosition < secondEnd) {
         //The split-position intersect with both first and second. Continue the intersection on both sides
 
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
 
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         uint newLeftNode = set_intersect(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit);
         uint newRightNode = set_intersect(firstRightNode, secondRightNode, firstRight, secondRight, splitBit);
 
         if (newLeftNode && newRightNode)
             return createSetFromNodes(newLeftNode, newRightNode);
         else if (newLeftNode)
             return newLeftNode;
         else
             return newRightNode;
     } else if (splitPosition > firstStart && splitPosition < firstEnd) {
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
 
         Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
 
         //splitPosition does not intersect second. That means that second is completely on one side of it.
         //So we can completely ignore the other side of first.
 
         if (secondEnd <= splitPosition) {
             return set_intersect(firstLeftNode, secondNode, firstLeft, second, splitBit);
         } else {
             Q_ASSERT(secondStart >= splitPosition);
             return set_intersect(firstRightNode, secondNode, firstRight, second, splitBit);
         }
     } else if (splitPosition > secondStart && splitPosition < secondEnd) {
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         if (firstEnd <= splitPosition) {
             return set_intersect(secondLeftNode, firstNode, secondLeft, first, splitBit);
         } else {
             Q_ASSERT(firstStart >= splitPosition);
             return set_intersect(secondRightNode, firstNode, secondRight, first, splitBit);
         }
     } else {
         //We would have stopped earlier of first and second don't intersect
         Q_ASSERT(0);
         return 0;
     }
     Q_ASSERT(0);
 }
 
 bool SetRepositoryAlgorithms::set_contains(const SetNodeData* node, Index index)
 {
     while (true) {
         if (node->start() > index || node->end() <= index)
             return false;
 
         if (node->contiguous())
             return true;
 
         const SetNodeData* leftNode = nodeFromIndex(node->leftNode());
 
         if (index < leftNode->end())
             node = leftNode;
         else {
             const SetNodeData* rightNode = nodeFromIndex(node->rightNode());
             node = rightNode;
         }
     }
 
     return false;
 }
 
 uint SetRepositoryAlgorithms::set_subtract(uint firstNode, uint secondNode, const SetNodeData* first,
                                            const SetNodeData* second, uchar splitBit)
 {
     if (firstNode == secondNode)
         return 0;
 
     if (first->start() >= second->end() || second->start() >= first->end())
         return firstNode;
 
     //The ranges of first and second do intersect
     uint firstStart = first->start(), firstEnd = first->end(), secondStart = second->start(), secondEnd = second->end();
 
     uint newStart = firstStart < secondStart ? firstStart : secondStart;
     uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd;
 
     //Compute the split-position for the resulting merged node
     uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit);
 
     //Since the ranges overlap, we can be sure that either first or second contain splitPosition.
     //The node that contains it, will also be split by it.
 
     if (splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart &&
         splitPosition < secondEnd) {
         //The split-position intersect with both first and second. Continue the subtract on both sides of the split-position, and merge it.
 
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
 
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         uint newLeftNode = set_subtract(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit);
         uint newRightNode = set_subtract(firstRightNode, secondRightNode, firstRight, secondRight, splitBit);
 
         if (newLeftNode && newRightNode)
             return createSetFromNodes(newLeftNode, newRightNode);
         else if (newLeftNode)
             return newLeftNode;
         else
             return newRightNode;
     } else if (splitPosition > firstStart && splitPosition < firstEnd) {
 //    Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
 
         uint firstLeftNode = first->leftNode();
         uint firstRightNode = first->rightNode();
 
         const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
         const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
 
         //splitPosition does not intersect second. That means that second is completely on one side of it.
         //So we only need to subtract that side of first with second.
 
         uint newLeftNode = firstLeftNode, newRightNode = firstRightNode;
 
         if (secondEnd <= splitPosition) {
             newLeftNode = set_subtract(firstLeftNode, secondNode, firstLeft, second, splitBit);
         } else {
             Q_ASSERT(secondStart >= splitPosition);
             newRightNode = set_subtract(firstRightNode, secondNode, firstRight, second, splitBit);
         }
 
         if (newLeftNode && newRightNode)
             return createSetFromNodes(newLeftNode, newRightNode);
         else if (newLeftNode)
             return newLeftNode;
         else
             return newRightNode;
     } else if (splitPosition > secondStart && splitPosition < secondEnd) {
         uint secondLeftNode = second->leftNode();
         uint secondRightNode = second->rightNode();
 
         const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
         const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);
 
         Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());
 
         if (firstEnd <= splitPosition) {
             return set_subtract(firstNode, secondLeftNode, first, secondLeft, splitBit);
         } else {
             Q_ASSERT(firstStart >= splitPosition);
             return set_subtract(firstNode, secondRightNode, first, secondRight, splitBit);
         }
     } else {
         //We would have stopped earlier of first and second don't intersect
         Q_ASSERT(0);
         return 0;
     }
     Q_ASSERT(0);
 }
 
 Set BasicSetRepository::createSetFromIndices(const std::vector<Index>& indices)
 {
     QMutexLocker lock(m_mutex);
 
     if (indices.empty())
         return Set();
 
     SetRepositoryAlgorithms alg(m_dataRepository, this);
 
     return Set(alg.setForIndices(indices.begin(), indices.end()), this);
 }
 
 Set BasicSetRepository::createSet(Index i)
 {
     QMutexLocker lock(m_mutex);
     SetNodeData data(i, i + 1);
 
     return Set(m_dataRepository.index(SetNodeDataRequest(&data, m_dataRepository, this)), this);
 }
 
 Set BasicSetRepository::createSet(const std::set<Index>& indices)
 {
     if (indices.empty())
         return Set();
 
     QMutexLocker lock(m_mutex);
 
     std::vector<Index> indicesVector;
     indicesVector.reserve(indices.size());
 
     for (unsigned int index : indices) {
         indicesVector.push_back(index);
     }
 
     return createSetFromIndices(indicesVector);
 }
 
 BasicSetRepository::BasicSetRepository(const QString& name, QRecursiveMutex* mutex,
                                        KDevelop::ItemRepositoryRegistry* registry, bool delayedDeletion)
     : m_dataRepository(this, name, registry, mutex)
     , m_mutex(nullptr)
     , m_delayedDeletion(delayedDeletion)
 {
     m_mutex = m_dataRepository.mutex();
 }
 
 struct StatisticsVisitor
 {
     explicit StatisticsVisitor(const SetDataRepository& _rep) : nodeCount(0)
         , badSplitNodeCount(0)
         , zeroRefCountNodes(0)
         , rep(_rep)
     {
     }
     bool operator()(const SetNodeData* item)
     {
         if (item->m_refCount == 0)
             ++zeroRefCountNodes;
         ++nodeCount;
         uint split = splitPositionForRange(item->start(), item->end());
         if (item->hasSlaves())
             if (split < rep.itemFromIndex(item->leftNode())->end() ||
                 split > rep.itemFromIndex(item->rightNode())->start())
                 ++badSplitNodeCount;
         return true;
     }
     uint nodeCount;
     uint badSplitNodeCount;
     uint zeroRefCountNodes;
     const SetDataRepository& rep;
 };
 
 void BasicSetRepository::printStatistics() const
 {
     StatisticsVisitor stats(m_dataRepository);
     m_dataRepository.visitAllItems<StatisticsVisitor>(stats);
     qCDebug(LANGUAGE) << "count of nodes:" << stats.nodeCount << "count of nodes with bad split:" <<
         stats.badSplitNodeCount << "count of nodes with zero reference-count:" << stats.zeroRefCountNodes;
 }
 
 BasicSetRepository::~BasicSetRepository() = default;
 
 void BasicSetRepository::itemRemovedFromSets(uint /*index*/)
 {
 }
 
 void BasicSetRepository::itemAddedToSets(uint /*index*/)
 {
 }
 
 ////////////Set convenience functions//////////////////
 
 bool Set::contains(Index index) const
 {
     if (!m_tree || !m_repository)
         return false;
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
     return alg.set_contains(m_repository->m_dataRepository.itemFromIndex(m_tree), index);
 }
 
 Set Set::operator +(const Set& first) const
 {
     if (!first.m_tree)
         return *this;
     else if (!m_tree || !m_repository)
         return first;
 
     Q_ASSERT(m_repository == first.m_repository);
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     uint retNode = alg.set_union(m_tree, first.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                      m_tree), m_repository->m_dataRepository.itemFromIndex(first.m_tree));
 
     ifDebug(alg.check(retNode));
 
     return Set(retNode, m_repository);
 }
 
 Set& Set::operator +=(const Set& first)
 {
     if (!first.m_tree)
         return *this;
     else if (!m_tree || !m_repository) {
         m_tree = first.m_tree;
         m_repository = first.m_repository;
         return *this;
     }
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     m_tree = alg.set_union(m_tree, first.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                m_tree), m_repository->m_dataRepository.itemFromIndex(first.m_tree));
 
     ifDebug(alg.check(m_tree));
     return *this;
 }
 
 Set Set::operator &(const Set& first) const
 {
     if (!first.m_tree || !m_tree)
         return Set();
 
     Q_ASSERT(m_repository);
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     Set ret(alg.set_intersect(m_tree, first.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                   m_tree), m_repository->m_dataRepository.itemFromIndex(first.m_tree)), m_repository);
 
     ifDebug(alg.check(ret.m_tree));
 
     return ret;
 }
 
 Set& Set::operator &=(const Set& first)
 {
     if (!first.m_tree || !m_tree) {
         m_tree = 0;
         return *this;
     }
 
     Q_ASSERT(m_repository);
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     m_tree = alg.set_intersect(m_tree, first.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                    m_tree), m_repository->m_dataRepository.itemFromIndex(first.m_tree));
     ifDebug(alg.check(m_tree));
     return *this;
 }
 
 Set Set::operator -(const Set& rhs) const
 {
     if (!m_tree || !rhs.m_tree)
         return *this;
 
     Q_ASSERT(m_repository);
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     Set ret(alg.set_subtract(m_tree, rhs.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                  m_tree), m_repository->m_dataRepository.itemFromIndex(rhs.m_tree)), m_repository);
     ifDebug(alg.check(ret.m_tree));
     return ret;
 }
 
 Set& Set::operator -=(const Set& rhs)
 {
     if (!m_tree || !rhs.m_tree)
         return *this;
 
     Q_ASSERT(m_repository);
 
     QMutexLocker lock(m_repository->m_mutex);
 
     SetRepositoryAlgorithms alg(m_repository->m_dataRepository, m_repository);
 
     m_tree = alg.set_subtract(m_tree, rhs.m_tree, m_repository->m_dataRepository.itemFromIndex(
                                   m_tree), m_repository->m_dataRepository.itemFromIndex(rhs.m_tree));
 
     ifDebug(alg.check(m_tree));
     return *this;
 }
 
 BasicSetRepository* Set::repository() const
 {
     return m_repository;
 }
 
 void Set::staticRef()
 {
     if (!m_tree)
         return;
 
     QMutexLocker lock(m_repository->m_mutex);
     SetNodeData* data = m_repository->m_dataRepository.dynamicItemFromIndexSimple(m_tree);
     ++data->m_refCount;
 }
 
 ///Mutex must be locked
 void Set::unrefNode(uint current)
 {
     SetNodeData* data = m_repository->m_dataRepository.dynamicItemFromIndexSimple(current);
     Q_ASSERT(data->m_refCount);
     --data->m_refCount;
     if (!m_repository->delayedDeletion()) {
         if (data->m_refCount == 0) {
             if (data->leftNode()) {
                 Q_ASSERT(data->rightNode());
                 unrefNode(data->rightNode());
                 unrefNode(data->leftNode());
             } else {
                 //Deleting a leaf
                 Q_ASSERT(data->end() - data->start() == 1);
                 m_repository->itemRemovedFromSets(data->start());
             }
 
             m_repository->m_dataRepository.deleteItem(current);
         }
     }
 }
 
 ///Decrease the static reference-count of this set by one. This set must have a reference-count > 1.
 ///If this set reaches the reference-count zero, it will be deleted, and all sub-nodes that also reach the reference-count zero
 ///will be deleted as well. @warning Either protect ALL your sets by using reference-counting, or don't use it at all.
 void Set::staticUnref()
 {
     if (!m_tree)
         return;
 
     QMutexLocker lock(m_repository->m_mutex);
 
     unrefNode(m_tree);
 }
 
 StringSetRepository::StringSetRepository(const QString& name, QRecursiveMutex* mutex)
     : Utils::BasicSetRepository(name, mutex)
 {
 }
 
 void StringSetRepository::itemRemovedFromSets(uint index)
 {
     ///Call the IndexedString destructor with enabled reference-counting
     KDevelop::IndexedString string = KDevelop::IndexedString::fromIndex(index);
 
     const KDevelop::DUChainReferenceCountingEnabler rcEnabler(&string, sizeof(KDevelop::IndexedString));
     string.~IndexedString(); //Call destructor with enabled reference-counting
 }
 
 void StringSetRepository::itemAddedToSets(uint index)
 {
     ///Call the IndexedString constructor with enabled reference-counting
 
     KDevelop::IndexedString string = KDevelop::IndexedString::fromIndex(index);
 
     char data[sizeof(KDevelop::IndexedString)] = {};
 
     const KDevelop::DUChainReferenceCountingEnabler rcEnabler(data, sizeof(KDevelop::IndexedString));
     new (data) KDevelop::IndexedString(string); //Call constructor with enabled reference-counting
 }
 }