ROSE  0.9.9.139
LinearEditDistance.h
1 #ifndef ROSE_EditDistance_LinearEditDistance_H
2 #define ROSE_EditDistance_LinearEditDistance_H
3 
4 #include <EditDistance/Levenshtein.h>
5 
6 namespace Rose {
7 namespace EditDistance {
8 
38 namespace LinearEditDistance {
39 
44 class Node {
45  unsigned first_, second_;
46 public:
48  explicit Node(SgNode *node) {
49  ASSERT_not_null(node);
50  first_ = node->variantT();
51  if (SgAsmInstruction *insn = isSgAsmInstruction(node)) {
52  second_ = insn->get_anyKind();
53  } else {
54  second_ = 0;
55  }
56  }
57 
63  bool operator==(const Node &other) const {
64  return first_==other.first_ && second_==other.second_;
65  }
66 };
67 
68 // Used internally to build a list of nodes over which edit distance is computed. The list of nodes is constructed by visiting
69 // certain nodes of an AST.
70 template<class NodeType>
71 class NodeSelector: public SgTopDownBottomUpProcessing<size_t, Sawyer::Nothing> {
72  std::vector<NodeType> &nodes_; // edit distance nodes constructed from AST nodes
73  SgFile *containingFile_; // optional constraint: node must belong to this file
74  size_t minDepth_, maxDepth_; // constraints: limits nodes by their depth under the subtree
75 
76 public:
77  NodeSelector(std::vector<NodeType> &nodes /*out*/, SgFile *containingFile, size_t minDepth, size_t maxDepth)
78  : nodes_(nodes), containingFile_(containingFile), minDepth_(minDepth), maxDepth_(maxDepth) {
79  ASSERT_require(minDepth <= maxDepth);
80  }
81 
82  size_t evaluateInheritedAttribute(SgNode *node, size_t depth) ROSE_OVERRIDE {
83  Sg_File_Info *nodeInfo = node->get_file_info();
84  bool isSelected = (depth >= minDepth_ && depth <= maxDepth_ &&
85  (!containingFile_ || (nodeInfo && nodeInfo->isSameFile(containingFile_))));
86  if (isSelected)
87  nodes_.push_back(NodeType(node));
88  return depth+1;
89  }
90 
92  return Sawyer::Nothing();
93  }
94 };
95 
103 template<typename NodeType = Node>
104 class Analysis {
105  SgNode *ast1_, *ast2_;
106  std::vector<NodeType> nodes1_, nodes2_;
107  size_t cost_;
108 public:
110  Analysis(): ast1_(NULL), ast2_(NULL), cost_(0) {}
111 
122  Analysis& setTree1(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1)) {
123  return setTree(ast1_=ast, file, minDepth, maxDepth, nodes1_/*out*/);
124  }
125  Analysis& setTree2(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1)) {
126  return setTree(ast2_=ast, file, minDepth, maxDepth, nodes2_/*out*/);
127  }
142  Analysis& compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL) {
143  setTree1(source, sourceFile);
144  return compute(target, targetFile);
145  }
146  Analysis& compute(SgNode *target, SgFile *targetFile=NULL) {
147  setTree2(target, targetFile);
148  return compute();
149  }
151  cost_ = levenshteinDistance(nodes1_, nodes2_);
152  return *this;
153  }
160  size_t cost() const {
161  return cost_;
162  }
163 
169  double relativeCost() const {
170  size_t n = std::max(nodes1_.size(), nodes2_.size());
171  return n ? 1.0 * cost_ / n : 1.0 * cost_;
172  }
173 
174 private:
175  // Does the actual work for setTree1 and setTree2
176  Analysis& setTree(SgNode *ast, SgFile *file, size_t minDepth, size_t maxDepth, std::vector<NodeType> &nodes /*out*/) {
177  nodes.clear();
178  NodeSelector<NodeType> nodeSelector(nodes /*out*/, file, minDepth, maxDepth);
179  nodeSelector.traverse(ast, 0);
180  return *this;
181  }
182 };
183 
184 } // namespace
185 } // namespace
186 } // namespace
187 
188 #endif
double relativeCost() const
Relative edit distance.
Analysis & setTree2(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1))
Associate an AST with this analysis.
This class represents a source file for a project (which may contian many source files and or directo...
Base class for machine instructions.
This class represents the location of the code associated with the IR node in the original source cod...
virtual Sg_File_Info * get_file_info(void) const
File information containing filename, line number, column number, and if the SgNode is a part of a ne...
Definition: Cxx_Grammar.h:9012
size_t levenshteinDistance(const std::vector< T > &src, const std::vector< T > &tgt)
Levenshtein edit distance.
Definition: Levenshtein.h:38
Analysis & compute()
Compute edit distance.
Main namespace for the ROSE library.
virtual VariantT variantT() const
returns new style SageIII enum values
Sawyer::Nothing evaluateSynthesizedAttribute(SgNode *, size_t depth, SubTreeSynthesizedAttributes) ROSE_OVERRIDE
pure virtual function which must be implemented to compute the synthesized attribute at a node...
Node(SgNode *node)
Construct a list node from an AST node.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
Analysis & setTree1(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1))
Associate an AST with this analysis.
bool operator==(const Node &other) const
Test two list nodes for equality.
Analysis & compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL)
Compute edit distance.
Analysis()
Constructs an analysis object with no associated trees.
size_t evaluateInheritedAttribute(SgNode *node, size_t depth) ROSE_OVERRIDE
pure virtual function which must be implemented to compute the inherited attribute at a node ...
Analysis & compute(SgNode *target, SgFile *targetFile=NULL)
Compute edit distance.
Type for comparing two AST nodes.
Represents no value.
Definition: Optional.h:32