LinearEditDistance.h

#ifndef ROSE_EditDistance_LinearEditDistance_H
#define ROSE_EditDistance_LinearEditDistance_H

#include <EditDistance/Levenshtein.h>

namespace Rose {
namespace EditDistance {

namespace LinearEditDistance {

class Node {
    unsigned first_, second_;
public:
    explicit Node(SgNode *node) {
        ASSERT_not_null(node);
        first_ = node->variantT();
        if (SgAsmInstruction *insn = isSgAsmInstruction(node)) {
            second_ = insn->get_anyKind();
        } else {
            second_ = 0;
        }
    }

    bool operator==(const Node &other) const {
        return first_==other.first_ && second_==other.second_;
    }
};

// Used internally to build a list of nodes over which edit distance is computed. The list of nodes is constructed by visiting
// certain nodes of an AST.
template<class NodeType>
class NodeSelector: public SgTopDownBottomUpProcessing<size_t, Sawyer::Nothing> {
    std::vector<NodeType> &nodes_;                      // edit distance nodes constructed from AST nodes
    SgFile *containingFile_;                            // optional constraint: node must belong to this file
    size_t minDepth_, maxDepth_;                        // constraints: limits nodes by their depth under the subtree

public:
    NodeSelector(std::vector<NodeType> &nodes /*out*/, SgFile *containingFile, size_t minDepth, size_t maxDepth)
        : nodes_(nodes), containingFile_(containingFile), minDepth_(minDepth), maxDepth_(maxDepth) {
        ASSERT_require(minDepth <= maxDepth);
    }

    size_t evaluateInheritedAttribute(SgNode *node, size_t depth) override {
        Sg_File_Info *nodeInfo = node->get_file_info();
        bool isSelected = (depth >= minDepth_ && depth <= maxDepth_ &&
                           (!containingFile_ || (nodeInfo && nodeInfo->isSameFile(containingFile_))));
        if (isSelected)
            nodes_.push_back(NodeType(node));
        return depth+1;
    }

    Sawyer::Nothing evaluateSynthesizedAttribute(SgNode*, size_t depth, SubTreeSynthesizedAttributes) override {
        return Sawyer::Nothing();
    }
};
    
template<typename NodeType = Node>
class Analysis {
    SgNode *ast1_, *ast2_;
    std::vector<NodeType> nodes1_, nodes2_;
    size_t cost_;
public:
    Analysis(): ast1_(NULL), ast2_(NULL), cost_(0) {}

    Analysis& setTree1(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1)) {
        return setTree(ast1_=ast, file, minDepth, maxDepth, nodes1_/*out*/);
    }
    Analysis& setTree2(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1)) {
        return setTree(ast2_=ast, file, minDepth, maxDepth, nodes2_/*out*/);
    }
    Analysis& compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL) {
        setTree1(source, sourceFile);
        return compute(target, targetFile);
    }
    Analysis& compute(SgNode *target, SgFile *targetFile=NULL) {
        setTree2(target, targetFile);
        return compute();
    }
    Analysis& compute() {
        cost_ = levenshteinDistance(nodes1_, nodes2_);
        return *this;
    }
    size_t cost() const {
        return cost_;
    }

    double relativeCost() const {
        size_t n = std::max(nodes1_.size(), nodes2_.size());
        return n ? 1.0 * cost_ / n : 1.0 * cost_;
    }

private:
    // Does the actual work for setTree1 and setTree2
    Analysis& setTree(SgNode *ast, SgFile *file, size_t minDepth, size_t maxDepth, std::vector<NodeType> &nodes /*out*/) {
        nodes.clear();
        NodeSelector<NodeType> nodeSelector(nodes /*out*/, file, minDepth, maxDepth);
        nodeSelector.traverse(ast, 0);
        return *this;
    }
};

} // namespace
} // namespace
} // namespace

#endif