ROSE  0.11.96.11
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) 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
Sawyer::Nothing
Represents no value.
Definition: Optional.h:32
SgNode::get_file_info
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:7417
Rose::EditDistance::LinearEditDistance::Analysis::compute
Analysis & compute()
Compute edit distance.
Definition: LinearEditDistance.h:150
Rose::EditDistance::LinearEditDistance::Analysis
Edit distance analysis.
Definition: LinearEditDistance.h:104
Rose::EditDistance::LinearEditDistance::NodeSelector
Definition: LinearEditDistance.h:71
Rose::EditDistance::LinearEditDistance::Analysis::cost
size_t cost() const
Edit distance.
Definition: LinearEditDistance.h:160
SgFile
This class represents a source file for a project (which may contian many source files and or directo...
Definition: Cxx_Grammar.h:21163
Rose::EditDistance::LinearEditDistance::NodeSelector::evaluateSynthesizedAttribute
Sawyer::Nothing evaluateSynthesizedAttribute(SgNode *, size_t depth, SubTreeSynthesizedAttributes) override
pure virtual function which must be implemented to compute the synthesized attribute at a node.
Definition: LinearEditDistance.h:91
Rose::EditDistance::LinearEditDistance::Node
Type for comparing two AST nodes.
Definition: LinearEditDistance.h:44
Rose::EditDistance::levenshteinDistance
size_t levenshteinDistance(const std::vector< T > &src, const std::vector< T > &tgt)
Levenshtein edit distance.
Definition: Levenshtein.h:38
Rose::EditDistance::LinearEditDistance::Analysis::relativeCost
double relativeCost() const
Relative edit distance.
Definition: LinearEditDistance.h:169
Rose::EditDistance::LinearEditDistance::Analysis::setTree1
Analysis & setTree1(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1))
Associate an AST with this analysis.
Definition: LinearEditDistance.h:122
Rose::EditDistance::LinearEditDistance::Analysis::compute
Analysis & compute(SgNode *source, SgNode *target, SgFile *sourceFile=NULL, SgFile *targetFile=NULL)
Compute edit distance.
Definition: LinearEditDistance.h:142
Sg_File_Info
This class represents the location of the code associated with the IR node in the original source cod...
Definition: Cxx_Grammar.h:20337
Rose::EditDistance::LinearEditDistance::Analysis::setTree2
Analysis & setTree2(SgNode *ast, SgFile *file=NULL, size_t minDepth=0, size_t maxDepth=size_t(-1))
Associate an AST with this analysis.
Definition: LinearEditDistance.h:125
SgNode
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:6739
Rose
Main namespace for the ROSE library.
Definition: BinaryTutorial.dox:3
Rose::EditDistance::LinearEditDistance::Node::Node
Node(SgNode *node)
Construct a list node from an AST node.
Definition: LinearEditDistance.h:48
Rose::EditDistance::LinearEditDistance::Analysis::compute
Analysis & compute(SgNode *target, SgFile *targetFile=NULL)
Compute edit distance.
Definition: LinearEditDistance.h:146
StackFrameVector
Definition: StackFrameVector.h:43
Rose::EditDistance::LinearEditDistance::Analysis::Analysis
Analysis()
Constructs an analysis object with no associated trees.
Definition: LinearEditDistance.h:110
Rose::EditDistance::LinearEditDistance::NodeSelector::evaluateInheritedAttribute
size_t evaluateInheritedAttribute(SgNode *node, size_t depth) override
pure virtual function which must be implemented to compute the inherited attribute at a node
Definition: LinearEditDistance.h:82
Rose::EditDistance::LinearEditDistance::Node::operator==
bool operator==(const Node &other) const
Test two list nodes for equality.
Definition: LinearEditDistance.h:63
SgTopDownBottomUpProcessing
Definition: AstProcessing.h:358
SgNode::variantT
virtual VariantT variantT() const
returns new style SageIII enum values