TreeEditDistance.h

#ifndef ROSE_EditDistance_TreeEditDistance_H
#define ROSE_EditDistance_TreeEditDistance_H

#include <Rose/Diagnostics.h>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>

#include <map>
#include <string>
#include <vector>

namespace Rose {
namespace EditDistance {                                // documented elsewhere

namespace TreeEditDistance {

// Any header that #defines words that are this common is just plain stupid!
#if defined(INSERT) || defined(DELETE) || defined(SUBSTITUTE)
# ifdef _MSC_VER
#  pragma message("Undefining common words from the global namespace: INSERT DELETE SUBSTITUTE")
# else
#  warning "Undefining common words from the global namespace: INSERT DELETE SUBSTITUTE"
# endif
# undef INSERT
# undef DELETE
# undef SUBSTITUTE
#endif

enum EditType {
    INSERT,                                         
    DELETE,                                         
    SUBSTITUTE,                                     
};

struct Edit {
    EditType editType;                              
    SgNode *sourceNode;                             
    SgNode *targetNode;                             
    double cost;                                    
    Edit(EditType editType, SgNode *sourceNode, SgNode *targetNode, double cost)
        : editType(editType), sourceNode(sourceNode), targetNode(targetNode), cost(cost) {}
    void print(std::ostream&) const;
};

typedef std::vector<Edit> Edits;

class SubstitutionPredicate {
public:
    virtual ~SubstitutionPredicate() {}

    virtual bool operator()(SgNode *source, SgNode *target) = 0;
};

class Analysis {
    // Graph used for computing Dijkstra's shortest path (DSP).
    typedef boost::property<boost::edge_weight_t, double> EdgeProperty;
    typedef boost::adjacency_list<boost::listS,         // edge representation
                                  boost::vecS,          // vertex representation
                                  boost::directedS,     // edges are directed
                                  boost::no_property,   // vertex values
                                  EdgeProperty          // edge values
                                 > Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
    typedef std::pair<size_t, size_t> Edge;             // source and target vertex IDs

    double insertionCost_;                              // non-negative cost for insertion edit
    double deletionCost_;                               // non-negative cost for deletion edit
    double substitutionCost_;                           // non-negative cost for substitution edit

    SgNode *ast1_, *ast2_;                              // trees being compared
    std::vector<SgNode*> nodes1_, nodes2_;              // list of nodes from parts of trees being compared
    std::vector<size_t> depths1_, depths2_;             // subtree depths for nodes1_ and nodes2_
    Graph graph_;                                       // graph connectivity and edge weights
    std::vector<double> totalCost_;                     // total cost of minimal-cost path from origin to each vertex
    std::vector<Vertex> predecessors_;                  // predecessor vertex for each node in minimal-cost path from origin
    SubstitutionPredicate *substitutionPredicate_;      // determines whether one node can be substituted for another

public:
    Analysis()
        : insertionCost_(1.0), deletionCost_(1.0), substitutionCost_(1.0), ast1_(NULL), ast2_(NULL),
          substitutionPredicate_(NULL)  {}

    Analysis& clear() {
        ast1_ = ast2_ = NULL;
        nodes1_.clear(), nodes2_.clear();
        depths1_.clear(), depths2_.clear();
        graph_ = Graph();
        totalCost_.clear(), predecessors_.clear();
        return *this;
    }
    
    double insertionCost() const {
        return insertionCost_;
    }
    Analysis& insertionCost(double weight) {
        ASSERT_require(weight >= 0.0);
        insertionCost_ = weight;
        return *this;
    }
    double deletionCost() const {
        return deletionCost_;
    }
    Analysis& deletionCost(double weight) {
        ASSERT_require(weight >= 0.0);
        deletionCost_ = weight;
        return *this;
    }
    double substitutionCost() const {
        return substitutionCost_;
    }
    Analysis& substitutionCost(double weight) {
        ASSERT_require(weight >= 0.0);
        substitutionCost_ = weight;
        return *this;
    }
    SubstitutionPredicate* substitutionPredicate() const {
        return substitutionPredicate_;
    }
    Analysis& substitutionPredicate(SubstitutionPredicate *predicate) {
        substitutionPredicate_ = predicate;
        return *this;
    }
    Analysis& compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL);
    Analysis& compute(SgNode *target, SgFile *targetFile=NULL);
    Analysis& compute();
    double cost() const;

    double relativeCost() const;

    Edits edits() const;

    std::pair<SgNode*, SgNode*> trees() const {
        return std::make_pair(ast1_, ast2_);
    }

    const std::vector<SgNode*>& sourceTreeNodes() const {
        return nodes1_;
    }
    const std::vector<SgNode*>& targetTreeNodes() const {
        return nodes2_;
    }
    std::pair<size_t, size_t> graphSize() const;

    void emitGraphViz(std::ostream&) const;

    Analysis& setTree1(SgNode *ast, SgFile *file=NULL);
    Analysis& setTree2(SgNode *ast, SgFile *file=NULL);
};

std::ostream& operator<<(std::ostream&, const TreeEditDistance::Edit&);

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

#endif