ROSE  0.9.9.139
TreeEditDistance.h
1 #ifndef ROSE_EditDistance_TreeEditDistance_H
2 #define ROSE_EditDistance_TreeEditDistance_H
3 
4 #include "Diagnostics.h"
5 
6 #include <boost/graph/adjacency_list.hpp>
7 #include <boost/graph/graph_traits.hpp>
8 
9 #include <map>
10 #include <string>
11 #include <vector>
12 
13 namespace Rose {
14 namespace EditDistance { // documented elsewhere
15 
45 namespace TreeEditDistance {
46 
47 // Any header that #defines words that are this common is just plain stupid!
48 #if defined(INSERT) || defined(DELETE) || defined(SUBSTITUTE)
49 # ifdef _MSC_VER
50 # pragma message("Undefining common words from the global namespace: INSERT DELETE SUBSTITUTE")
51 # else
52 # warning "Undefining common words from the global namespace: INSERT DELETE SUBSTITUTE"
53 # endif
54 # undef INSERT
55 # undef DELETE
56 # undef SUBSTITUTE
57 #endif
58 
60 enum EditType {
64 };
65 
67 struct Edit {
71  double cost;
72  Edit(EditType editType, SgNode *sourceNode, SgNode *targetNode, double cost)
73  : editType(editType), sourceNode(sourceNode), targetNode(targetNode), cost(cost) {}
74  void print(std::ostream&) const;
75 };
76 
78 typedef std::vector<Edit> Edits;
79 
84 public:
85  virtual ~SubstitutionPredicate() {}
86 
88  virtual bool operator()(SgNode *source, SgNode *target) = 0;
89 };
90 
95 class Analysis {
96  // Graph used for computing Dijkstra's shortest path (DSP).
97  typedef boost::property<boost::edge_weight_t, double> EdgeProperty;
98  typedef boost::adjacency_list<boost::listS, // edge representation
99  boost::vecS, // vertex representation
100  boost::directedS, // edges are directed
101  boost::no_property, // vertex values
102  EdgeProperty // edge values
103  > Graph;
104  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
105  typedef std::pair<size_t, size_t> Edge; // source and target vertex IDs
106 
107  double insertionCost_; // non-negative cost for insertion edit
108  double deletionCost_; // non-negative cost for deletion edit
109  double substitutionCost_; // non-negative cost for substitution edit
110 
111  SgNode *ast1_, *ast2_; // trees being compared
112  std::vector<SgNode*> nodes1_, nodes2_; // list of nodes from parts of trees being compared
113  std::vector<size_t> depths1_, depths2_; // subtree depths for nodes1_ and nodes2_
114  Graph graph_; // graph connectivity and edge weights
115  std::vector<double> totalCost_; // total cost of minimal-cost path from origin to each vertex
116  std::vector<Vertex> predecessors_; // predecessor vertex for each node in minimal-cost path from origin
117  SubstitutionPredicate *substitutionPredicate_; // determines whether one node can be substituted for another
118 
119 public:
122  : insertionCost_(1.0), deletionCost_(1.0), substitutionCost_(1.0), ast1_(NULL), ast2_(NULL),
123  substitutionPredicate_(NULL) {}
124 
130  ast1_ = ast2_ = NULL;
131  nodes1_.clear(), nodes2_.clear();
132  depths1_.clear(), depths2_.clear();
133  graph_ = Graph();
134  totalCost_.clear(), predecessors_.clear();
135  return *this;
136  }
137 
143  double insertionCost() const {
144  return insertionCost_;
145  }
146  Analysis& insertionCost(double weight) {
147  ASSERT_require(weight >= 0.0);
148  insertionCost_ = weight;
149  return *this;
150  }
158  double deletionCost() const {
159  return deletionCost_;
160  }
161  Analysis& deletionCost(double weight) {
162  ASSERT_require(weight >= 0.0);
163  deletionCost_ = weight;
164  return *this;
165  }
173  double substitutionCost() const {
174  return substitutionCost_;
175  }
176  Analysis& substitutionCost(double weight) {
177  ASSERT_require(weight >= 0.0);
178  substitutionCost_ = weight;
179  return *this;
180  }
191  return substitutionPredicate_;
192  }
194  substitutionPredicate_ = predicate;
195  return *this;
196  }
232  Analysis& compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL);
233  Analysis& compute(SgNode *target, SgFile *targetFile=NULL);
234  Analysis& compute();
241  double cost() const;
242 
247  double relativeCost() const;
248 
250  Edits edits() const;
251 
253  std::pair<SgNode*, SgNode*> trees() const {
254  return std::make_pair(ast1_, ast2_);
255  }
256 
260  const std::vector<SgNode*>& sourceTreeNodes() const {
261  return nodes1_;
262  }
263  const std::vector<SgNode*>& targetTreeNodes() const {
264  return nodes2_;
265  }
272  std::pair<size_t, size_t> graphSize() const;
273 
285  void emitGraphViz(std::ostream&) const;
286 
292  Analysis& setTree1(SgNode *ast, SgFile *file=NULL);
293  Analysis& setTree2(SgNode *ast, SgFile *file=NULL);
295 };
296 
297 std::ostream& operator<<(std::ostream&, const TreeEditDistance::Edit&);
298 
299 } // namespace
300 } // namespace
301 } // namespace
302 
303 #endif
Insert a node from another tree.
double cost() const
Total cost for making one tree the same shape as the other.
This class represents a source file for a project (which may contian many source files and or directo...
double relativeCost() const
Relative cost.
Analysis & setTree2(SgNode *ast, SgFile *file=NULL)
Change one tree or the other.
std::pair< SgNode *, SgNode * > trees() const
The two trees that were compared.
double deletionCost() const
Property: deletion cost.
Analysis & substitutionPredicate(SubstitutionPredicate *predicate)
Property: substitution predicate.
EditType editType
Type of operation performed.
virtual bool operator()(SgNode *source, SgNode *target)=0
Returns true if target can be substituted for source.
SubstitutionPredicate * substitutionPredicate() const
Property: substitution predicate.
double insertionCost() const
Property: insertion cost.
Main namespace for the ROSE library.
Analysis & insertionCost(double weight)
Property: insertion cost.
Edits edits() const
Edit operations to make one path look like another.
Analysis object for tree edit distance.
Analysis()
Construct an analysis with default values.
const std::vector< SgNode * > & targetTreeNodes() const
List of nodes in the trees.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
void emitGraphViz(std::ostream &) const
Emit a GraphViz file.
Analysis & clear()
Forget calculated results.
std::pair< size_t, size_t > graphSize() const
Number of vertices and edges in the graph.
SgNode * targetNode
Node in target tree for replacement or insertion.
Substitute a node; same as an insert-delete pair.
double substitutionCost() const
Property: substitution cost.
Analysis & deletionCost(double weight)
Property: deletion cost.
Analysis & compute()
Compute tree edit distances.
const std::vector< SgNode * > & sourceTreeNodes() const
List of nodes in the trees.
SgNode * sourceNode
Node in source tree to be replaced or deleted.
Analysis & setTree1(SgNode *ast, SgFile *file=NULL)
Change one tree or the other.
double cost
Cost for this operation.
std::vector< Edit > Edits
List of edit operations.
Analysis & substitutionCost(double weight)
Property: substitution cost.