diff options
author | Johannes Altmanninger <aclopte@gmail.com> | 2017-08-18 21:26:34 +0000 |
---|---|---|
committer | Johannes Altmanninger <aclopte@gmail.com> | 2017-08-18 21:26:34 +0000 |
commit | ee444f1e76dacd6593a5924b4f15bbec471010f7 (patch) | |
tree | 0391d87750fc0f2a8b96bd84bd99eca8231fb20b /lib/Tooling/ASTDiff | |
parent | 5ce0ae8c6ac9dc99e4807f2989be4c6c50975c5e (diff) |
[clang-diff] Move printing of matches and changes to clang-diff
Summary:
This also changes the output order of the changes. Now the matches are
printed in pre-order, intertwined with insertions, updates, and moves.
Deletions are printed afterwards.
Reviewers: arphaman
Subscribers: klimek
Differential Revision: https://reviews.llvm.org/D36179
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@311200 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Tooling/ASTDiff')
-rw-r--r-- | lib/Tooling/ASTDiff/ASTDiff.cpp | 324 |
1 files changed, 143 insertions, 181 deletions
diff --git a/lib/Tooling/ASTDiff/ASTDiff.cpp b/lib/Tooling/ASTDiff/ASTDiff.cpp index 0441dbc78d..b0dd6012bd 100644 --- a/lib/Tooling/ASTDiff/ASTDiff.cpp +++ b/lib/Tooling/ASTDiff/ASTDiff.cpp @@ -82,26 +82,24 @@ private: class ASTDiff::Impl { public: SyntaxTree::Impl &T1, &T2; - bool IsMappingDone = false; Mapping TheMapping; Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, - const ComparisonOptions &Options) - : T1(T1), T2(T2), Options(Options) {} + const ComparisonOptions &Options); /// Matches nodes one-by-one based on their similarity. void computeMapping(); - std::vector<Match> getMatches(Mapping &M); + // Compute ChangeKind for each node based on similarity. + void computeChangeKinds(Mapping &M); - /// Finds an edit script that converts T1 to T2. - std::vector<Change> computeChanges(Mapping &M); - - void printChangeImpl(raw_ostream &OS, const Change &Chg) const; - void printMatchImpl(raw_ostream &OS, const Match &M) const; - - // Returns a mapping of identical subtrees. - Mapping matchTopDown() const; + NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree, + NodeId Id) const { + if (&*Tree == &T1) + return TheMapping.getDst(Id); + assert(&*Tree == &T2 && "Invalid tree."); + return TheMapping.getSrc(Id); + } private: // Returns true if the two subtrees are identical. @@ -112,6 +110,9 @@ private: // Returns false if the nodes must not be mached. bool isMatchingPossible(NodeId Id1, NodeId Id2) const; + // Returns true if the nodes' parents are matched. + bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const; + // Uses an optimal albeit slow algorithm to compute a mapping between two // subtrees, but only if both have fewer nodes than MaxSize. void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const; @@ -123,6 +124,9 @@ private: // Returns the node that has the highest degree of similarity. NodeId findCandidate(const Mapping &M, NodeId Id1) const; + // Returns a mapping of identical subtrees. + Mapping matchTopDown() const; + // Tries to match any yet unmapped nodes, in a bottom-up fashion. void matchBottomUp(Mapping &M) const; @@ -155,9 +159,12 @@ public: std::vector<NodeId> Leaves; // Maps preorder indices to postorder ones. std::vector<int> PostorderIds; + std::vector<NodeId> NodesBfs; int getSize() const { return Nodes.size(); } NodeId getRootId() const { return 0; } + PreorderIterator begin() const { return getRootId(); } + PreorderIterator end() const { return getSize(); } const Node &getNode(NodeId Id) const { return Nodes[Id]; } Node &getMutableNode(NodeId Id) { return Nodes[Id]; } @@ -165,16 +172,10 @@ public: void addNode(Node &N) { Nodes.push_back(N); } int getNumberOfDescendants(NodeId Id) const; bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const; + int findPositionInParent(NodeId Id, bool Shifted = false) const; std::string getNodeValue(NodeId Id) const; - std::string getNodeValue(const DynTypedNode &DTN) const; - /// Prints the node as "<type>[: <value>](<postorder-id)" - void printNode(NodeId Id) const { printNode(llvm::outs(), Id); } - void printNode(raw_ostream &OS, NodeId Id) const; - - void printTree() const; - void printTree(NodeId Root) const; - void printTree(raw_ostream &OS, NodeId Root) const; + std::string getNodeValue(const Node &Node) const; private: /// Nodes in preorder. @@ -302,6 +303,30 @@ SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, const ASTContext &AST) initTree(); } +static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree, + NodeId Root) { + std::vector<NodeId> Postorder; + std::function<void(NodeId)> Traverse = [&](NodeId Id) { + const Node &N = Tree.getNode(Id); + for (NodeId Child : N.Children) + Traverse(Child); + Postorder.push_back(Id); + }; + Traverse(Root); + return Postorder; +} + +static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree, + NodeId Root) { + std::vector<NodeId> Ids; + size_t Expanded = 0; + Ids.push_back(Root); + while (Expanded < Ids.size()) + for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children) + Ids.push_back(Child); + return Ids; +} + void SyntaxTree::Impl::initTree() { setLeftMostDescendants(); int PostorderId = 0; @@ -313,6 +338,7 @@ void SyntaxTree::Impl::initTree() { ++PostorderId; }; PostorderTraverse(getRootId()); + NodesBfs = getSubtreeBfs(*this, getRootId()); } void SyntaxTree::Impl::setLeftMostDescendants() { @@ -327,30 +353,6 @@ void SyntaxTree::Impl::setLeftMostDescendants() { } } -static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree, - NodeId Root) { - std::vector<NodeId> Postorder; - std::function<void(NodeId)> Traverse = [&](NodeId Id) { - const Node &N = Tree.getNode(Id); - for (NodeId Child : N.Children) - Traverse(Child); - Postorder.push_back(Id); - }; - Traverse(Root); - return Postorder; -} - -static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree, - NodeId Root) { - std::vector<NodeId> Ids; - size_t Expanded = 0; - Ids.push_back(Root); - while (Expanded < Ids.size()) - for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children) - Ids.push_back(Child); - return Ids; -} - int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const { return getNode(Id).RightMostDescendant - Id + 1; } @@ -359,11 +361,29 @@ bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const { return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant; } +int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const { + NodeId Parent = getNode(Id).Parent; + if (Parent.isInvalid()) + return 0; + const auto &Siblings = getNode(Parent).Children; + int Position = 0; + for (size_t I = 0, E = Siblings.size(); I < E; ++I) { + if (Shifted) + Position += getNode(Siblings[I]).Shift; + if (Siblings[I] == Id) { + Position += I; + return Position; + } + } + llvm_unreachable("Node not found in parent's children."); +} + std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const { - return getNodeValue(getNode(Id).ASTNode); + return getNodeValue(getNode(Id)); } -std::string SyntaxTree::Impl::getNodeValue(const DynTypedNode &DTN) const { +std::string SyntaxTree::Impl::getNodeValue(const Node &N) const { + const DynTypedNode &DTN = N.ASTNode; if (auto *X = DTN.get<BinaryOperator>()) return X->getOpcodeStr(); if (auto *X = DTN.get<AccessSpecDecl>()) { @@ -409,32 +429,6 @@ std::string SyntaxTree::Impl::getNodeValue(const DynTypedNode &DTN) const { llvm_unreachable("Fatal: unhandled AST node.\n"); } -void SyntaxTree::Impl::printTree() const { printTree(getRootId()); } -void SyntaxTree::Impl::printTree(NodeId Root) const { - printTree(llvm::outs(), Root); -} - -void SyntaxTree::Impl::printTree(raw_ostream &OS, NodeId Root) const { - const Node &N = getNode(Root); - for (int I = 0; I < N.Depth; ++I) - OS << " "; - printNode(OS, Root); - OS << "\n"; - for (NodeId Child : N.Children) - printTree(OS, Child); -} - -void SyntaxTree::Impl::printNode(raw_ostream &OS, NodeId Id) const { - if (Id.isInvalid()) { - OS << "None"; - return; - } - OS << getNode(Id).getTypeLabel(); - if (getNodeValue(Id) != "") - OS << ": " << getNodeValue(Id); - OS << "(" << PostorderIds[Id] << ")"; -} - /// Identifies a node in a subtree by its postorder offset, starting at 1. struct SNodeId { int Id = 0; @@ -736,8 +730,15 @@ bool ASTDiff::Impl::canBeAddedToMapping(const Mapping &M, NodeId Id1, } bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const { - return Options.isMatchingAllowed(T1.getNode(Id1).ASTNode, - T2.getNode(Id2).ASTNode); + return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2)); +} + +bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1, + NodeId Id2) const { + NodeId P1 = T1.getNode(Id1).Parent; + NodeId P2 = T2.getNode(Id2).Parent; + return (P1.isInvalid() && P2.isInvalid()) || + (P1.isValid() && P2.isValid() && M.getDst(P1) == P2); } void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1, @@ -770,7 +771,7 @@ double ASTDiff::Impl::getSimilarity(const Mapping &M, NodeId Id1, NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const { NodeId Candidate; double HighestSimilarity = 0.0; - for (NodeId Id2 = 0, E = T2.getSize(); Id2 < E; ++Id2) { + for (NodeId Id2 : T2) { if (!isMatchingPossible(Id1, Id2)) continue; if (M.hasDst(Id2)) @@ -855,99 +856,60 @@ Mapping ASTDiff::Impl::matchTopDown() const { return M; } +ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2, + const ComparisonOptions &Options) + : T1(T1), T2(T2), Options(Options) { + computeMapping(); + computeChangeKinds(TheMapping); +} + void ASTDiff::Impl::computeMapping() { - if (IsMappingDone) - return; TheMapping = matchTopDown(); matchBottomUp(TheMapping); - IsMappingDone = true; } -std::vector<Match> ASTDiff::Impl::getMatches(Mapping &M) { - std::vector<Match> Matches; - for (NodeId Id1 = 0, Id2, E = T1.getSize(); Id1 < E; ++Id1) - if ((Id2 = M.getDst(Id1)).isValid()) - Matches.push_back({Id1, Id2}); - return Matches; -} - -std::vector<Change> ASTDiff::Impl::computeChanges(Mapping &M) { - std::vector<Change> Changes; - for (NodeId Id2 : getSubtreeBfs(T2, T2.getRootId())) { - const Node &N2 = T2.getNode(Id2); - NodeId Id1 = M.getSrc(Id2); - if (Id1.isValid()) { - assert(isMatchingPossible(Id1, Id2) && "Invalid matching."); - if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) { - Changes.emplace_back(Update, Id1, Id2); - } - continue; +void ASTDiff::Impl::computeChangeKinds(Mapping &M) { + for (NodeId Id1 : T1) { + if (!M.hasSrc(Id1)) { + T1.getMutableNode(Id1).ChangeKind = Delete; + T1.getMutableNode(Id1).Shift -= 1; + } + } + for (NodeId Id2 : T2) { + if (!M.hasDst(Id2)) { + T2.getMutableNode(Id2).ChangeKind = Insert; + T2.getMutableNode(Id2).Shift -= 1; } - NodeId P2 = N2.Parent; - NodeId P1 = M.getSrc(P2); - assert(P1.isValid() && - "Parents must be matched for determining the change type."); - Node &Parent1 = T1.getMutableNode(P1); - const Node &Parent2 = T2.getNode(P2); - auto &Siblings1 = Parent1.Children; - const auto &Siblings2 = Parent2.Children; - size_t Position; - for (Position = 0; Position < Siblings2.size(); ++Position) - if (Siblings2[Position] == Id2 || Position >= Siblings1.size()) - break; - Changes.emplace_back(Insert, Id2, P2, Position); - Node PatchNode; - PatchNode.Parent = P1; - PatchNode.LeftMostDescendant = N2.LeftMostDescendant; - PatchNode.RightMostDescendant = N2.RightMostDescendant; - PatchNode.Depth = N2.Depth; - PatchNode.ASTNode = N2.ASTNode; - // TODO update Depth if needed - NodeId PatchNodeId = T1.getSize(); - // TODO maybe choose a different data structure for Children. - Siblings1.insert(Siblings1.begin() + Position, PatchNodeId); - T1.addNode(PatchNode); - M.link(PatchNodeId, Id2); - } - for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) { + } + for (NodeId Id1 : T1.NodesBfs) { NodeId Id2 = M.getDst(Id1); if (Id2.isInvalid()) - Changes.emplace_back(Delete, Id1, Id2); - } - return Changes; -} - -void ASTDiff::Impl::printChangeImpl(raw_ostream &OS, const Change &Chg) const { - switch (Chg.Kind) { - case Delete: - OS << "Delete "; - T1.printNode(OS, Chg.Src); - OS << "\n"; - break; - case Update: - OS << "Update "; - T1.printNode(OS, Chg.Src); - OS << " to " << T2.getNodeValue(Chg.Dst) << "\n"; - break; - case Insert: - OS << "Insert "; - T2.printNode(OS, Chg.Src); - OS << " into "; - T2.printNode(OS, Chg.Dst); - OS << " at " << Chg.Position << "\n"; - break; - case Move: - llvm_unreachable("TODO"); - break; - }; -} - -void ASTDiff::Impl::printMatchImpl(raw_ostream &OS, const Match &M) const { - OS << "Match "; - T1.printNode(OS, M.Src); - OS << " to "; - T2.printNode(OS, M.Dst); - OS << "\n"; + continue; + if (!haveSameParents(M, Id1, Id2) || + T1.findPositionInParent(Id1, true) != + T2.findPositionInParent(Id2, true)) { + T1.getMutableNode(Id1).Shift -= 1; + T2.getMutableNode(Id2).Shift -= 1; + } + } + for (NodeId Id2 : T2.NodesBfs) { + NodeId Id1 = M.getSrc(Id2); + if (Id1.isInvalid()) + continue; + Node &N1 = T1.getMutableNode(Id1); + Node &N2 = T2.getMutableNode(Id2); + if (Id1.isInvalid()) + continue; + if (!haveSameParents(M, Id1, Id2) || + T1.findPositionInParent(Id1, true) != + T2.findPositionInParent(Id2, true)) { + N1.ChangeKind = N2.ChangeKind = Move; + } + if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) { + N1.ChangeKind = N2.ChangeKind = + (N1.ChangeKind == Move ? UpdateMove : Update); + } + } } ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2, @@ -956,28 +918,14 @@ ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2, ASTDiff::~ASTDiff() = default; +NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const { + return DiffImpl->getMapped(SourceTree.TreeImpl, Id); +} + SyntaxTree::SyntaxTree(const ASTContext &AST) : TreeImpl(llvm::make_unique<SyntaxTree::Impl>( this, AST.getTranslationUnitDecl(), AST)) {} -std::vector<Match> ASTDiff::getMatches() { - DiffImpl->computeMapping(); - return DiffImpl->getMatches(DiffImpl->TheMapping); -} - -std::vector<Change> ASTDiff::getChanges() { - DiffImpl->computeMapping(); - return DiffImpl->computeChanges(DiffImpl->TheMapping); -} - -void ASTDiff::printChange(raw_ostream &OS, const Change &Chg) const { - DiffImpl->printChangeImpl(OS, Chg); -} - -void ASTDiff::printMatch(raw_ostream &OS, const Match &M) const { - DiffImpl->printMatchImpl(OS, M); -} - SyntaxTree::~SyntaxTree() = default; const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; } @@ -986,9 +934,19 @@ const Node &SyntaxTree::getNode(NodeId Id) const { return TreeImpl->getNode(Id); } +int SyntaxTree::getSize() const { return TreeImpl->getSize(); } NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); } +SyntaxTree::PreorderIterator SyntaxTree::begin() const { + return TreeImpl->begin(); +} +SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); } -std::pair<unsigned, unsigned> SyntaxTree::getSourceRangeOffsets(const Node &N) const { +int SyntaxTree::findPositionInParent(NodeId Id) const { + return TreeImpl->findPositionInParent(Id); +} + +std::pair<unsigned, unsigned> +SyntaxTree::getSourceRangeOffsets(const Node &N) const { const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager(); SourceRange Range = N.ASTNode.getSourceRange(); SourceLocation BeginLoc = Range.getBegin(); @@ -1003,8 +961,12 @@ std::pair<unsigned, unsigned> SyntaxTree::getSourceRangeOffsets(const Node &N) c return {Begin, End}; } -std::string SyntaxTree::getNodeValue(const DynTypedNode &DTN) const { - return TreeImpl->getNodeValue(DTN); +std::string SyntaxTree::getNodeValue(NodeId Id) const { + return TreeImpl->getNodeValue(Id); +} + +std::string SyntaxTree::getNodeValue(const Node &N) const { + return TreeImpl->getNodeValue(N); } } // end namespace diff |