<commit_before>/// XXX add licence
//

#ifndef _BBLOCK_H_
#define _BBLOCK_H_

#include <cassert>
#include <list>

#include "ADT/DGContainer.h"
#include "analysis/Analysis.h"

#ifndef ENABLE_CFG
#error "BBlock.h needs be included with ENABLE_CFG"
#endif // ENABLE_CFG

namespace dg {

/// ------------------------------------------------------------------
// - BBlock
//     Basic block structure for dependence graph
/// ------------------------------------------------------------------
template <typename NodeT>
class BBlock
{
public:
    typedef typename NodeT::KeyType KeyT;
    typedef typename NodeT::DependenceGraphType DependenceGraphT;

    struct BBlockEdge {
        BBlockEdge(BBlock<NodeT>* t, uint8_t label = 0)
            : target(t), label(label) {}

        BBlock<NodeT> *target;
        // we'll have just numbers as labels now.
        // We can change it if there's a need
        uint8_t label;

        bool operator==(const BBlockEdge& oth) const
        {
            return target == oth.target && label == oth.label;
        }

        bool operator!=(const BBlockEdge& oth) const
        {
            return operator==(oth);
        }

        bool operator<(const BBlockEdge& oth) const
        {
            return target == oth.target ?
                        label < oth.label : target < oth.target;
        }
    };

    BBlock<NodeT>(NodeT *head = nullptr, DependenceGraphT *dg = nullptr)
        : key(KeyT()), dg(dg), ipostdom(nullptr), slice_id(0)
    {
        if (head) {
            append(head);
            assert(!dg || head->getDG() == nullptr || dg == head->getDG());
        }
    }

    typedef EdgesContainer<BBlock<NodeT>> BBlockContainerT;
    // we don't need labels with predecessors
    typedef EdgesContainer<BBlock<NodeT>> PredContainerT;
    typedef DGContainer<BBlockEdge> SuccContainerT;

    SuccContainerT& successors() { return nextBBs; }
    const SuccContainerT& successors() const { return nextBBs; }

    PredContainerT& predecessors() { return prevBBs; }
    const PredContainerT& predecessors() const { return prevBBs; }

    const BBlockContainerT& controlDependence() const { return controlDeps; }
    const BBlockContainerT& revControlDependence() const { return revControlDeps; }

    // similary to nodes, basic blocks can have keys
    // they are not stored anywhere, it is more due to debugging
    void setKey(const KeyT& k) { key = k; }
    const KeyT& getKey() const { return key; }

    // XXX we should do it a common base with node
    // to not duplicate this - something like
    // GraphElement that would contain these attributes
    void setDG(DependenceGraphT *d) { dg = d; }
    DependenceGraphT *getDG() const { return dg; }

    const std::list<NodeT *>& getNodes() const { return nodes; }
    std::list<NodeT *>& getNodes() { return nodes; }
    bool empty() const { return nodes.empty(); }
    size_t size() const { return nodes.size(); }

    void append(NodeT *n)
    {
        assert(n && "Cannot add null node to BBlock");

        n->setBasicBlock(this);
        nodes.push_back(n);
    }

    void prepend(NodeT *n)
    {
        assert(n && "Cannot add null node to BBlock");

        n->setBasicBlock(this);
        nodes.push_front(n);
    }

    bool hasControlDependence() const
    {
        return !controlDeps.empty();
    }

    // return true if all successors point
    // to the same basic block (not considering labels,
    // just the targets)
    bool successorsAreSame() const
    {
        if (nextBBs.size() < 2)
            return true;

        typename SuccContainerT::const_iterator start, iter, end;
        iter = nextBBs.begin();
        end = nextBBs.end();

        BBlock<NodeT> *block = iter->target;
        // iterate over all successor and
        // check if they are all the same
        for (++iter; iter != end; ++iter)
            if (iter->target != block)
                return false;

        return true;
    }

    // remove all edges from/to this BB and reconnect them to
    // other nodes
    void isolate()
    {
        // take every predecessor and reconnect edges from it
        // to successors
        for (auto pred : prevBBs) {
            // find the edge that is going to this node
            // and create new edges to all successors. The new edges
            // will have the same label as the found one
            DGContainer<BBlockEdge> new_edges;
            for (auto I = pred->nextBBs.begin(),E = pred->nextBBs.end(); I != E;) {
                auto cur = I++;
                if (cur->target == this) {
                    // create edges that will go from the predecessor
                    // to every successor of this node
                    for (const BBlockEdge& succ : nextBBs) {
                        // we cannot create an edge to this bblock (we're isolating _this_ bblock),
                        // that would be incorrect. It can occur when we're isolatin a bblock
                        // with self-loop
                        if (succ.target != this)
                            new_edges.insert(BBlockEdge(succ.target, cur->label));
                    }

                    // remove the edge from predecessor
                    pred->nextBBs.erase(*cur);
                }
            }

            // add newly created edges to predecessor
            for (const BBlockEdge& edge : new_edges) {
                assert(edge.target != this
                       && "Adding an edge to a block that is being isolated");
                pred->addSuccessor(edge);
            }
        }

        removeSuccessors();

        // we reconnected and deleted edges from other
        // BBs, but we still have edges from this to other BBs
        // NOTE: nextBBs were cleared in removeSuccessors()
        prevBBs.clear();

        // remove reverse edges to this BB
        for (auto B : controlDeps) {
            // we don't want to corrupt the iterator
            // if this block is control dependent on itself.
            // We're gonna clear it anyway
            if (B == this)
                continue;

            B->revControlDeps.erase(this);
        }

        controlDeps.clear();
    }

    void remove(bool with_nodes = true)
    {
        // do not leave any dangling reference
        isolate();

        if (dg)
            dg->removeBlock(key);

        // XXX what to do when this is entry block?

        if (with_nodes) {
            for (NodeT *n : nodes) {
                // we must set basic block to nullptr
                // otherwise the node will try to remove the
                // basic block again if it is of size 1
                n->setBasicBlock(nullptr);

                // remove dependency edges, let be CFG edges
                // as we'll destroy all the nodes
                n->removeCDs();
                n->removeDDs();
                // remove the node from dg
                n->removeFromDG();
<commit_msg>BBlock: fix isolate()<commit_after>/// XXX add licence
//

#ifndef _BBLOCK_H_
#define _BBLOCK_H_

#include <cassert>
#include <list>

#include "ADT/DGContainer.h"
#include "analysis/Analysis.h"

#ifndef ENABLE_CFG
#error "BBlock.h needs be included with ENABLE_CFG"
#endif // ENABLE_CFG

namespace dg {

/// ------------------------------------------------------------------
// - BBlock
//     Basic block structure for dependence graph
/// ------------------------------------------------------------------
template <typename NodeT>
class BBlock
{
public:
    typedef typename NodeT::KeyType KeyT;
    typedef typename NodeT::DependenceGraphType DependenceGraphT;

    struct BBlockEdge {
        BBlockEdge(BBlock<NodeT>* t, uint8_t label = 0)
            : target(t), label(label) {}

        BBlock<NodeT> *target;
        // we'll have just numbers as labels now.
        // We can change it if there's a need
        uint8_t label;

        bool operator==(const BBlockEdge& oth) const
        {
            return target == oth.target && label == oth.label;
        }

        bool operator!=(const BBlockEdge& oth) const
        {
            return operator==(oth);
        }

        bool operator<(const BBlockEdge& oth) const
        {
            return target == oth.target ?
                        label < oth.label : target < oth.target;
        }
    };

    BBlock<NodeT>(NodeT *head = nullptr, DependenceGraphT *dg = nullptr)
        : key(KeyT()), dg(dg), ipostdom(nullptr), slice_id(0)
    {
        if (head) {
            append(head);
            assert(!dg || head->getDG() == nullptr || dg == head->getDG());
        }
    }

    typedef EdgesContainer<BBlock<NodeT>> BBlockContainerT;
    // we don't need labels with predecessors
    typedef EdgesContainer<BBlock<NodeT>> PredContainerT;
    typedef DGContainer<BBlockEdge> SuccContainerT;

    SuccContainerT& successors() { return nextBBs; }
    const SuccContainerT& successors() const { return nextBBs; }

    PredContainerT& predecessors() { return prevBBs; }
    const PredContainerT& predecessors() const { return prevBBs; }

    const BBlockContainerT& controlDependence() const { return controlDeps; }
    const BBlockContainerT& revControlDependence() const { return revControlDeps; }

    // similary to nodes, basic blocks can have keys
    // they are not stored anywhere, it is more due to debugging
    void setKey(const KeyT& k) { key = k; }
    const KeyT& getKey() const { return key; }

    // XXX we should do it a common base with node
    // to not duplicate this - something like
    // GraphElement that would contain these attributes
    void setDG(DependenceGraphT *d) { dg = d; }
    DependenceGraphT *getDG() const { return dg; }

    const std::list<NodeT *>& getNodes() const { return nodes; }
    std::list<NodeT *>& getNodes() { return nodes; }
    bool empty() const { return nodes.empty(); }
    size_t size() const { return nodes.size(); }

    void append(NodeT *n)
    {
        assert(n && "Cannot add null node to BBlock");

        n->setBasicBlock(this);
        nodes.push_back(n);
    }

    void prepend(NodeT *n)
    {
        assert(n && "Cannot add null node to BBlock");

        n->setBasicBlock(this);
        nodes.push_front(n);
    }

    bool hasControlDependence() const
    {
        return !controlDeps.empty();
    }

    // return true if all successors point
    // to the same basic block (not considering labels,
    // just the targets)
    bool successorsAreSame() const
    {
        if (nextBBs.size() < 2)
            return true;

        typename SuccContainerT::const_iterator start, iter, end;
        iter = nextBBs.begin();
        end = nextBBs.end();

        BBlock<NodeT> *block = iter->target;
        // iterate over all successor and
        // check if they are all the same
        for (++iter; iter != end; ++iter)
            if (iter->target != block)
                return false;

        return true;
    }

    // remove all edges from/to this BB and reconnect them to
    // other nodes
    void isolate()
    {
        // take every predecessor and reconnect edges from it
        // to successors
        for (auto pred : prevBBs) {
            // find the edge that is going to this node
            // and create new edges to all successors. The new edges
            // will have the same label as the found one
            DGContainer<BBlockEdge> new_edges;
            for (auto I = pred->nextBBs.begin(),E = pred->nextBBs.end(); I != E;) {
                auto cur = I++;
                if (cur->target == this) {
                    // create edges that will go from the predecessor
                    // to every successor of this node
                    for (const BBlockEdge& succ : nextBBs) {
                        // we cannot create an edge to this bblock (we're isolating _this_ bblock),
                        // that would be incorrect. It can occur when we're isolatin a bblock
                        // with self-loop
                        if (succ.target != this)
                            new_edges.insert(BBlockEdge(succ.target, cur->label));
                    }

                    // remove the edge from predecessor
                    pred->nextBBs.erase(*cur);
                }
            }

            // add newly created edges to predecessor
            for (const BBlockEdge& edge : new_edges) {
                assert(edge.target != this
                       && "Adding an edge to a block that is being isolated");
                pred->addSuccessor(edge);
            }
        }

        removeSuccessors();

        // NOTE: nextBBs were cleared in removeSuccessors()
        prevBBs.clear();

        // remove reverse edges to this BB
        for (auto B : controlDeps) {
            // we don't want to corrupt the iterator
            // if this block is control dependent on itself.
            // We're gonna clear it anyway
            if (B == this)
                continue;

            B->revControlDeps.erase(this);
        }

        // clear also cd edges that blocks have
        // to this block
        for (auto B : revControlDeps) {
            if (B == this)
                continue;

            B->controlDeps.erase(this);
        }

        revControlDeps.clear();
        controlDeps.clear();
    }

    void remove(bool with_nodes = true)
    {
        // do not leave any dangling reference
        isolate();

        if (dg)
            dg->removeBlock(key);

        // XXX what to do when this is entry block?

        if (with_nodes) {
            for (NodeT *n : nodes) {
                // we must set basic block to nullptr
                // otherwise the node will try to remove the
                // basic block again if it is of size 1
                n->setBasicBlock(nullptr);

                // remove dependency edges, let be CFG edges
                // as we'll destroy all the nodes
                n->removeCDs();
                n->removeDDs();
                // remove the node from dg
                n->removeFromDG();

{'fraction_non_alphanumeric': 0.11512736587448413, 'fraction_numerical': 0.0008538494378824534, 'mean_word_length': 1.6669829222011385, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 70, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '563160', 'n_tokens_mistral': 3927, 'n_tokens_neox': 3715, 'n_words': 1278}