Bug Summary

File:tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp
Warning:line 317, column 1
Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ASTDiff.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/lib/Tooling/ASTDiff -I /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff -I /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/clang/lib/Tooling/ASTDiff -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp

/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp

1//===- ASTDiff.cpp - AST differencing implementation-----------*- C++ -*- -===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains definitons for the AST differencing interface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Tooling/ASTDiff/ASTDiff.h"
15
16#include "clang/AST/RecursiveASTVisitor.h"
17#include "clang/Lex/Lexer.h"
18#include "llvm/ADT/PriorityQueue.h"
19
20#include <limits>
21#include <memory>
22#include <unordered_set>
23
24using namespace llvm;
25using namespace clang;
26
27namespace clang {
28namespace diff {
29
30namespace {
31/// Maps nodes of the left tree to ones on the right, and vice versa.
32class Mapping {
33public:
34 Mapping() = default;
35 Mapping(Mapping &&Other) = default;
36 Mapping &operator=(Mapping &&Other) = default;
37
38 Mapping(size_t Size) {
39 SrcToDst = llvm::make_unique<NodeId[]>(Size);
40 DstToSrc = llvm::make_unique<NodeId[]>(Size);
41 }
42
43 void link(NodeId Src, NodeId Dst) {
44 SrcToDst[Src] = Dst, DstToSrc[Dst] = Src;
45 }
46
47 NodeId getDst(NodeId Src) const { return SrcToDst[Src]; }
48 NodeId getSrc(NodeId Dst) const { return DstToSrc[Dst]; }
49 bool hasSrc(NodeId Src) const { return getDst(Src).isValid(); }
50 bool hasDst(NodeId Dst) const { return getSrc(Dst).isValid(); }
51
52private:
53 std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
54};
55} // end anonymous namespace
56
57class ASTDiff::Impl {
58public:
59 SyntaxTree::Impl &T1, &T2;
60 Mapping TheMapping;
61
62 Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
63 const ComparisonOptions &Options);
64
65 /// Matches nodes one-by-one based on their similarity.
66 void computeMapping();
67
68 // Compute Change for each node based on similarity.
69 void computeChangeKinds(Mapping &M);
70
71 NodeId getMapped(const std::unique_ptr<SyntaxTree::Impl> &Tree,
72 NodeId Id) const {
73 if (&*Tree == &T1)
74 return TheMapping.getDst(Id);
75 assert(&*Tree == &T2 && "Invalid tree.")(static_cast <bool> (&*Tree == &T2 && "Invalid tree."
) ? void (0) : __assert_fail ("&*Tree == &T2 && \"Invalid tree.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 75, __extension__ __PRETTY_FUNCTION__))
;
76 return TheMapping.getSrc(Id);
77 }
78
79private:
80 // Returns true if the two subtrees are identical.
81 bool identical(NodeId Id1, NodeId Id2) const;
82
83 // Returns false if the nodes must not be mached.
84 bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
85
86 // Returns true if the nodes' parents are matched.
87 bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
88
89 // Uses an optimal albeit slow algorithm to compute a mapping between two
90 // subtrees, but only if both have fewer nodes than MaxSize.
91 void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
92
93 // Computes the ratio of common descendants between the two nodes.
94 // Descendants are only considered to be equal when they are mapped in M.
95 double getJaccardSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
96
97 // Returns the node that has the highest degree of similarity.
98 NodeId findCandidate(const Mapping &M, NodeId Id1) const;
99
100 // Returns a mapping of identical subtrees.
101 Mapping matchTopDown() const;
102
103 // Tries to match any yet unmapped nodes, in a bottom-up fashion.
104 void matchBottomUp(Mapping &M) const;
105
106 const ComparisonOptions &Options;
107
108 friend class ZhangShashaMatcher;
109};
110
111/// Represents the AST of a TranslationUnit.
112class SyntaxTree::Impl {
113public:
114 Impl(SyntaxTree *Parent, ASTContext &AST);
115 /// Constructs a tree from an AST node.
116 Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST);
117 Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST);
118 template <class T>
119 Impl(SyntaxTree *Parent,
120 typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
121 ASTContext &AST)
122 : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
123 template <class T>
124 Impl(SyntaxTree *Parent,
125 typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
126 ASTContext &AST)
127 : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
128
129 SyntaxTree *Parent;
130 ASTContext &AST;
131 PrintingPolicy TypePP;
132 /// Nodes in preorder.
133 std::vector<Node> Nodes;
134 std::vector<NodeId> Leaves;
135 // Maps preorder indices to postorder ones.
136 std::vector<int> PostorderIds;
137 std::vector<NodeId> NodesBfs;
138
139 int getSize() const { return Nodes.size(); }
140 NodeId getRootId() const { return 0; }
141 PreorderIterator begin() const { return getRootId(); }
142 PreorderIterator end() const { return getSize(); }
143
144 const Node &getNode(NodeId Id) const { return Nodes[Id]; }
145 Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
146 bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
147 void addNode(Node &N) { Nodes.push_back(N); }
148 int getNumberOfDescendants(NodeId Id) const;
149 bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
150 int findPositionInParent(NodeId Id, bool Shifted = false) const;
151
152 std::string getRelativeName(const NamedDecl *ND,
153 const DeclContext *Context) const;
154 std::string getRelativeName(const NamedDecl *ND) const;
155
156 std::string getNodeValue(NodeId Id) const;
157 std::string getNodeValue(const Node &Node) const;
158 std::string getDeclValue(const Decl *D) const;
159 std::string getStmtValue(const Stmt *S) const;
160
161private:
162 void initTree();
163 void setLeftMostDescendants();
164};
165
166static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
167static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
168static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) {
169 return !I->isWritten();
170}
171
172template <class T>
173static bool isNodeExcluded(const SourceManager &SrcMgr, T *N) {
174 if (!N)
175 return true;
176 SourceLocation SLoc = N->getSourceRange().getBegin();
177 if (SLoc.isValid()) {
178 // Ignore everything from other files.
179 if (!SrcMgr.isInMainFile(SLoc))
180 return true;
181 // Ignore macros.
182 if (SLoc != SrcMgr.getSpellingLoc(SLoc))
183 return true;
184 }
185 return isSpecializedNodeExcluded(N);
186}
187
188namespace {
189// Sets Height, Parent and Children for each node.
190struct PreorderVisitor : public RecursiveASTVisitor<PreorderVisitor> {
191 int Id = 0, Depth = 0;
192 NodeId Parent;
193 SyntaxTree::Impl &Tree;
194
195 PreorderVisitor(SyntaxTree::Impl &Tree) : Tree(Tree) {}
196
197 template <class T> std::tuple<NodeId, NodeId> PreTraverse(T *ASTNode) {
198 NodeId MyId = Id;
199 Tree.Nodes.emplace_back();
200 Node &N = Tree.getMutableNode(MyId);
201 N.Parent = Parent;
202 N.Depth = Depth;
203 N.ASTNode = DynTypedNode::create(*ASTNode);
204 assert(!N.ASTNode.getNodeKind().isNone() &&(static_cast <bool> (!N.ASTNode.getNodeKind().isNone() &&
"Expected nodes to have a valid kind.") ? void (0) : __assert_fail
("!N.ASTNode.getNodeKind().isNone() && \"Expected nodes to have a valid kind.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 205, __extension__ __PRETTY_FUNCTION__))
205 "Expected nodes to have a valid kind.")(static_cast <bool> (!N.ASTNode.getNodeKind().isNone() &&
"Expected nodes to have a valid kind.") ? void (0) : __assert_fail
("!N.ASTNode.getNodeKind().isNone() && \"Expected nodes to have a valid kind.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 205, __extension__ __PRETTY_FUNCTION__))
;
206 if (Parent.isValid()) {
207 Node &P = Tree.getMutableNode(Parent);
208 P.Children.push_back(MyId);
209 }
210 Parent = MyId;
211 ++Id;
212 ++Depth;
213 return std::make_tuple(MyId, Tree.getNode(MyId).Parent);
214 }
215 void PostTraverse(std::tuple<NodeId, NodeId> State) {
216 NodeId MyId, PreviousParent;
217 std::tie(MyId, PreviousParent) = State;
218 assert(MyId.isValid() && "Expecting to only traverse valid nodes.")(static_cast <bool> (MyId.isValid() && "Expecting to only traverse valid nodes."
) ? void (0) : __assert_fail ("MyId.isValid() && \"Expecting to only traverse valid nodes.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 218, __extension__ __PRETTY_FUNCTION__))
;
219 Parent = PreviousParent;
220 --Depth;
221 Node &N = Tree.getMutableNode(MyId);
222 N.RightMostDescendant = Id - 1;
223 assert(N.RightMostDescendant >= 0 &&(static_cast <bool> (N.RightMostDescendant >= 0 &&
N.RightMostDescendant < Tree.getSize() && "Rightmost descendant must be a valid tree node."
) ? void (0) : __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 225, __extension__ __PRETTY_FUNCTION__))
224 N.RightMostDescendant < Tree.getSize() &&(static_cast <bool> (N.RightMostDescendant >= 0 &&
N.RightMostDescendant < Tree.getSize() && "Rightmost descendant must be a valid tree node."
) ? void (0) : __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 225, __extension__ __PRETTY_FUNCTION__))
225 "Rightmost descendant must be a valid tree node.")(static_cast <bool> (N.RightMostDescendant >= 0 &&
N.RightMostDescendant < Tree.getSize() && "Rightmost descendant must be a valid tree node."
) ? void (0) : __assert_fail ("N.RightMostDescendant >= 0 && N.RightMostDescendant < Tree.getSize() && \"Rightmost descendant must be a valid tree node.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 225, __extension__ __PRETTY_FUNCTION__))
;
226 if (N.isLeaf())
227 Tree.Leaves.push_back(MyId);
228 N.Height = 1;
229 for (NodeId Child : N.Children)
230 N.Height = std::max(N.Height, 1 + Tree.getNode(Child).Height);
231 }
232 bool TraverseDecl(Decl *D) {
233 if (isNodeExcluded(Tree.AST.getSourceManager(), D))
234 return true;
235 auto SavedState = PreTraverse(D);
236 RecursiveASTVisitor<PreorderVisitor>::TraverseDecl(D);
237 PostTraverse(SavedState);
238 return true;
239 }
240 bool TraverseStmt(Stmt *S) {
241 if (S)
242 S = S->IgnoreImplicit();
243 if (isNodeExcluded(Tree.AST.getSourceManager(), S))
244 return true;
245 auto SavedState = PreTraverse(S);
246 RecursiveASTVisitor<PreorderVisitor>::TraverseStmt(S);
247 PostTraverse(SavedState);
248 return true;
249 }
250 bool TraverseType(QualType T) { return true; }
251 bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
252 if (isNodeExcluded(Tree.AST.getSourceManager(), Init))
253 return true;
254 auto SavedState = PreTraverse(Init);
255 RecursiveASTVisitor<PreorderVisitor>::TraverseConstructorInitializer(Init);
256 PostTraverse(SavedState);
257 return true;
258 }
259};
260} // end anonymous namespace
261
262SyntaxTree::Impl::Impl(SyntaxTree *Parent, ASTContext &AST)
263 : Parent(Parent), AST(AST), TypePP(AST.getLangOpts()) {
264 TypePP.AnonymousTagLocations = false;
265}
266
267SyntaxTree::Impl::Impl(SyntaxTree *Parent, Decl *N, ASTContext &AST)
268 : Impl(Parent, AST) {
269 PreorderVisitor PreorderWalker(*this);
270 PreorderWalker.TraverseDecl(N);
271 initTree();
3
Calling 'Impl::initTree'
272}
273
274SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTContext &AST)
275 : Impl(Parent, AST) {
276 PreorderVisitor PreorderWalker(*this);
277 PreorderWalker.TraverseStmt(N);
278 initTree();
279}
280
281static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
282 NodeId Root) {
283 std::vector<NodeId> Postorder;
284 std::function<void(NodeId)> Traverse = [&](NodeId Id) {
285 const Node &N = Tree.getNode(Id);
286 for (NodeId Child : N.Children)
287 Traverse(Child);
288 Postorder.push_back(Id);
289 };
290 Traverse(Root);
291 return Postorder;
292}
293
294static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
295 NodeId Root) {
296 std::vector<NodeId> Ids;
297 size_t Expanded = 0;
298 Ids.push_back(Root);
299 while (Expanded < Ids.size())
300 for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
301 Ids.push_back(Child);
302 return Ids;
303}
304
305void SyntaxTree::Impl::initTree() {
306 setLeftMostDescendants();
307 int PostorderId = 0;
308 PostorderIds.resize(getSize());
309 std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
4
Calling constructor for 'function'
11
Returning from constructor for 'function'
310 for (NodeId Child : getNode(Id).Children)
311 PostorderTraverse(Child);
312 PostorderIds[Id] = PostorderId;
313 ++PostorderId;
314 };
315 PostorderTraverse(getRootId());
316 NodesBfs = getSubtreeBfs(*this, getRootId());
317}
12
Potential memory leak
318
319void SyntaxTree::Impl::setLeftMostDescendants() {
320 for (NodeId Leaf : Leaves) {
321 getMutableNode(Leaf).LeftMostDescendant = Leaf;
322 NodeId Parent, Cur = Leaf;
323 while ((Parent = getNode(Cur).Parent).isValid() &&
324 getNode(Parent).Children[0] == Cur) {
325 Cur = Parent;
326 getMutableNode(Cur).LeftMostDescendant = Leaf;
327 }
328 }
329}
330
331int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
332 return getNode(Id).RightMostDescendant - Id + 1;
333}
334
335bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
336 return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
337}
338
339int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
340 NodeId Parent = getNode(Id).Parent;
341 if (Parent.isInvalid())
342 return 0;
343 const auto &Siblings = getNode(Parent).Children;
344 int Position = 0;
345 for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
346 if (Shifted)
347 Position += getNode(Siblings[I]).Shift;
348 if (Siblings[I] == Id) {
349 Position += I;
350 return Position;
351 }
352 }
353 llvm_unreachable("Node not found in parent's children.")::llvm::llvm_unreachable_internal("Node not found in parent's children."
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 353)
;
354}
355
356// Returns the qualified name of ND. If it is subordinate to Context,
357// then the prefix of the latter is removed from the returned value.
358std::string
359SyntaxTree::Impl::getRelativeName(const NamedDecl *ND,
360 const DeclContext *Context) const {
361 std::string Val = ND->getQualifiedNameAsString();
362 std::string ContextPrefix;
363 if (!Context)
364 return Val;
365 if (auto *Namespace = dyn_cast<NamespaceDecl>(Context))
366 ContextPrefix = Namespace->getQualifiedNameAsString();
367 else if (auto *Record = dyn_cast<RecordDecl>(Context))
368 ContextPrefix = Record->getQualifiedNameAsString();
369 else if (AST.getLangOpts().CPlusPlus11)
370 if (auto *Tag = dyn_cast<TagDecl>(Context))
371 ContextPrefix = Tag->getQualifiedNameAsString();
372 // Strip the qualifier, if Val refers to something in the current scope.
373 // But leave one leading ':' in place, so that we know that this is a
374 // relative path.
375 if (!ContextPrefix.empty() && StringRef(Val).startswith(ContextPrefix))
376 Val = Val.substr(ContextPrefix.size() + 1);
377 return Val;
378}
379
380std::string SyntaxTree::Impl::getRelativeName(const NamedDecl *ND) const {
381 return getRelativeName(ND, ND->getDeclContext());
382}
383
384static const DeclContext *getEnclosingDeclContext(ASTContext &AST,
385 const Stmt *S) {
386 while (S) {
387 const auto &Parents = AST.getParents(*S);
388 if (Parents.empty())
389 return nullptr;
390 const auto &P = Parents[0];
391 if (const auto *D = P.get<Decl>())
392 return D->getDeclContext();
393 S = P.get<Stmt>();
394 }
395 return nullptr;
396}
397
398static std::string getInitializerValue(const CXXCtorInitializer *Init,
399 const PrintingPolicy &TypePP) {
400 if (Init->isAnyMemberInitializer())
401 return Init->getAnyMember()->getName();
402 if (Init->isBaseInitializer())
403 return QualType(Init->getBaseClass(), 0).getAsString(TypePP);
404 if (Init->isDelegatingInitializer())
405 return Init->getTypeSourceInfo()->getType().getAsString(TypePP);
406 llvm_unreachable("Unknown initializer type")::llvm::llvm_unreachable_internal("Unknown initializer type",
"/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 406)
;
407}
408
409std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
410 return getNodeValue(getNode(Id));
411}
412
413std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
414 const DynTypedNode &DTN = N.ASTNode;
415 if (auto *S = DTN.get<Stmt>())
416 return getStmtValue(S);
417 if (auto *D = DTN.get<Decl>())
418 return getDeclValue(D);
419 if (auto *Init = DTN.get<CXXCtorInitializer>())
420 return getInitializerValue(Init, TypePP);
421 llvm_unreachable("Fatal: unhandled AST node.\n")::llvm::llvm_unreachable_internal("Fatal: unhandled AST node.\n"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 421)
;
422}
423
424std::string SyntaxTree::Impl::getDeclValue(const Decl *D) const {
425 std::string Value;
426 if (auto *V = dyn_cast<ValueDecl>(D))
427 return getRelativeName(V) + "(" + V->getType().getAsString(TypePP) + ")";
428 if (auto *N = dyn_cast<NamedDecl>(D))
429 Value += getRelativeName(N) + ";";
430 if (auto *T = dyn_cast<TypedefNameDecl>(D))
431 return Value + T->getUnderlyingType().getAsString(TypePP) + ";";
432 if (auto *T = dyn_cast<TypeDecl>(D))
433 if (T->getTypeForDecl())
434 Value +=
435 T->getTypeForDecl()->getCanonicalTypeInternal().getAsString(TypePP) +
436 ";";
437 if (auto *U = dyn_cast<UsingDirectiveDecl>(D))
438 return U->getNominatedNamespace()->getName();
439 if (auto *A = dyn_cast<AccessSpecDecl>(D)) {
440 CharSourceRange Range(A->getSourceRange(), false);
441 return Lexer::getSourceText(Range, AST.getSourceManager(),
442 AST.getLangOpts());
443 }
444 return Value;
445}
446
447std::string SyntaxTree::Impl::getStmtValue(const Stmt *S) const {
448 if (auto *U = dyn_cast<UnaryOperator>(S))
449 return UnaryOperator::getOpcodeStr(U->getOpcode());
450 if (auto *B = dyn_cast<BinaryOperator>(S))
451 return B->getOpcodeStr();
452 if (auto *M = dyn_cast<MemberExpr>(S))
453 return getRelativeName(M->getMemberDecl());
454 if (auto *I = dyn_cast<IntegerLiteral>(S)) {
455 SmallString<256> Str;
456 I->getValue().toString(Str, /*Radix=*/10, /*Signed=*/false);
457 return Str.str();
458 }
459 if (auto *F = dyn_cast<FloatingLiteral>(S)) {
460 SmallString<256> Str;
461 F->getValue().toString(Str);
462 return Str.str();
463 }
464 if (auto *D = dyn_cast<DeclRefExpr>(S))
465 return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
466 if (auto *String = dyn_cast<StringLiteral>(S))
467 return String->getString();
468 if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
469 return B->getValue() ? "true" : "false";
470 return "";
471}
472
473/// Identifies a node in a subtree by its postorder offset, starting at 1.
474struct SNodeId {
475 int Id = 0;
476
477 explicit SNodeId(int Id) : Id(Id) {}
478 explicit SNodeId() = default;
479
480 operator int() const { return Id; }
481 SNodeId &operator++() { return ++Id, *this; }
482 SNodeId &operator--() { return --Id, *this; }
483 SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
484};
485
486class Subtree {
487private:
488 /// The parent tree.
489 const SyntaxTree::Impl &Tree;
490 /// Maps SNodeIds to original ids.
491 std::vector<NodeId> RootIds;
492 /// Maps subtree nodes to their leftmost descendants wtihin the subtree.
493 std::vector<SNodeId> LeftMostDescendants;
494
495public:
496 std::vector<SNodeId> KeyRoots;
497
498 Subtree(const SyntaxTree::Impl &Tree, NodeId SubtreeRoot) : Tree(Tree) {
499 RootIds = getSubtreePostorder(Tree, SubtreeRoot);
500 int NumLeaves = setLeftMostDescendants();
501 computeKeyRoots(NumLeaves);
502 }
503 int getSize() const { return RootIds.size(); }
504 NodeId getIdInRoot(SNodeId Id) const {
505 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.")(static_cast <bool> (Id > 0 && Id <= getSize
() && "Invalid subtree node index.") ? void (0) : __assert_fail
("Id > 0 && Id <= getSize() && \"Invalid subtree node index.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 505, __extension__ __PRETTY_FUNCTION__))
;
506 return RootIds[Id - 1];
507 }
508 const Node &getNode(SNodeId Id) const {
509 return Tree.getNode(getIdInRoot(Id));
510 }
511 SNodeId getLeftMostDescendant(SNodeId Id) const {
512 assert(Id > 0 && Id <= getSize() && "Invalid subtree node index.")(static_cast <bool> (Id > 0 && Id <= getSize
() && "Invalid subtree node index.") ? void (0) : __assert_fail
("Id > 0 && Id <= getSize() && \"Invalid subtree node index.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 512, __extension__ __PRETTY_FUNCTION__))
;
513 return LeftMostDescendants[Id - 1];
514 }
515 /// Returns the postorder index of the leftmost descendant in the subtree.
516 NodeId getPostorderOffset() const {
517 return Tree.PostorderIds[getIdInRoot(SNodeId(1))];
518 }
519 std::string getNodeValue(SNodeId Id) const {
520 return Tree.getNodeValue(getIdInRoot(Id));
521 }
522
523private:
524 /// Returns the number of leafs in the subtree.
525 int setLeftMostDescendants() {
526 int NumLeaves = 0;
527 LeftMostDescendants.resize(getSize());
528 for (int I = 0; I < getSize(); ++I) {
529 SNodeId SI(I + 1);
530 const Node &N = getNode(SI);
531 NumLeaves += N.isLeaf();
532 assert(I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() &&(static_cast <bool> (I == Tree.PostorderIds[getIdInRoot
(SI)] - getPostorderOffset() && "Postorder traversal in subtree should correspond to traversal in "
"the root tree by a constant offset.") ? void (0) : __assert_fail
("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 534, __extension__ __PRETTY_FUNCTION__))
533 "Postorder traversal in subtree should correspond to traversal in "(static_cast <bool> (I == Tree.PostorderIds[getIdInRoot
(SI)] - getPostorderOffset() && "Postorder traversal in subtree should correspond to traversal in "
"the root tree by a constant offset.") ? void (0) : __assert_fail
("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 534, __extension__ __PRETTY_FUNCTION__))
534 "the root tree by a constant offset.")(static_cast <bool> (I == Tree.PostorderIds[getIdInRoot
(SI)] - getPostorderOffset() && "Postorder traversal in subtree should correspond to traversal in "
"the root tree by a constant offset.") ? void (0) : __assert_fail
("I == Tree.PostorderIds[getIdInRoot(SI)] - getPostorderOffset() && \"Postorder traversal in subtree should correspond to traversal in \" \"the root tree by a constant offset.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 534, __extension__ __PRETTY_FUNCTION__))
;
535 LeftMostDescendants[I] = SNodeId(Tree.PostorderIds[N.LeftMostDescendant] -
536 getPostorderOffset());
537 }
538 return NumLeaves;
539 }
540 void computeKeyRoots(int Leaves) {
541 KeyRoots.resize(Leaves);
542 std::unordered_set<int> Visited;
543 int K = Leaves - 1;
544 for (SNodeId I(getSize()); I > 0; --I) {
545 SNodeId LeftDesc = getLeftMostDescendant(I);
546 if (Visited.count(LeftDesc))
547 continue;
548 assert(K >= 0 && "K should be non-negative")(static_cast <bool> (K >= 0 && "K should be non-negative"
) ? void (0) : __assert_fail ("K >= 0 && \"K should be non-negative\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 548, __extension__ __PRETTY_FUNCTION__))
;
549 KeyRoots[K] = I;
550 Visited.insert(LeftDesc);
551 --K;
552 }
553 }
554};
555
556/// Implementation of Zhang and Shasha's Algorithm for tree edit distance.
557/// Computes an optimal mapping between two trees using only insertion,
558/// deletion and update as edit actions (similar to the Levenshtein distance).
559class ZhangShashaMatcher {
560 const ASTDiff::Impl &DiffImpl;
561 Subtree S1;
562 Subtree S2;
563 std::unique_ptr<std::unique_ptr<double[]>[]> TreeDist, ForestDist;
564
565public:
566 ZhangShashaMatcher(const ASTDiff::Impl &DiffImpl, const SyntaxTree::Impl &T1,
567 const SyntaxTree::Impl &T2, NodeId Id1, NodeId Id2)
568 : DiffImpl(DiffImpl), S1(T1, Id1), S2(T2, Id2) {
569 TreeDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
570 size_t(S1.getSize()) + 1);
571 ForestDist = llvm::make_unique<std::unique_ptr<double[]>[]>(
572 size_t(S1.getSize()) + 1);
573 for (int I = 0, E = S1.getSize() + 1; I < E; ++I) {
574 TreeDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
575 ForestDist[I] = llvm::make_unique<double[]>(size_t(S2.getSize()) + 1);
576 }
577 }
578
579 std::vector<std::pair<NodeId, NodeId>> getMatchingNodes() {
580 std::vector<std::pair<NodeId, NodeId>> Matches;
581 std::vector<std::pair<SNodeId, SNodeId>> TreePairs;
582
583 computeTreeDist();
584
585 bool RootNodePair = true;
586
587 TreePairs.emplace_back(SNodeId(S1.getSize()), SNodeId(S2.getSize()));
588
589 while (!TreePairs.empty()) {
590 SNodeId LastRow, LastCol, FirstRow, FirstCol, Row, Col;
591 std::tie(LastRow, LastCol) = TreePairs.back();
592 TreePairs.pop_back();
593
594 if (!RootNodePair) {
595 computeForestDist(LastRow, LastCol);
596 }
597
598 RootNodePair = false;
599
600 FirstRow = S1.getLeftMostDescendant(LastRow);
601 FirstCol = S2.getLeftMostDescendant(LastCol);
602
603 Row = LastRow;
604 Col = LastCol;
605
606 while (Row > FirstRow || Col > FirstCol) {
607 if (Row > FirstRow &&
608 ForestDist[Row - 1][Col] + 1 == ForestDist[Row][Col]) {
609 --Row;
610 } else if (Col > FirstCol &&
611 ForestDist[Row][Col - 1] + 1 == ForestDist[Row][Col]) {
612 --Col;
613 } else {
614 SNodeId LMD1 = S1.getLeftMostDescendant(Row);
615 SNodeId LMD2 = S2.getLeftMostDescendant(Col);
616 if (LMD1 == S1.getLeftMostDescendant(LastRow) &&
617 LMD2 == S2.getLeftMostDescendant(LastCol)) {
618 NodeId Id1 = S1.getIdInRoot(Row);
619 NodeId Id2 = S2.getIdInRoot(Col);
620 assert(DiffImpl.isMatchingPossible(Id1, Id2) &&(static_cast <bool> (DiffImpl.isMatchingPossible(Id1, Id2
) && "These nodes must not be matched.") ? void (0) :
__assert_fail ("DiffImpl.isMatchingPossible(Id1, Id2) && \"These nodes must not be matched.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 621, __extension__ __PRETTY_FUNCTION__))
621 "These nodes must not be matched.")(static_cast <bool> (DiffImpl.isMatchingPossible(Id1, Id2
) && "These nodes must not be matched.") ? void (0) :
__assert_fail ("DiffImpl.isMatchingPossible(Id1, Id2) && \"These nodes must not be matched.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 621, __extension__ __PRETTY_FUNCTION__))
;
622 Matches.emplace_back(Id1, Id2);
623 --Row;
624 --Col;
625 } else {
626 TreePairs.emplace_back(Row, Col);
627 Row = LMD1;
628 Col = LMD2;
629 }
630 }
631 }
632 }
633 return Matches;
634 }
635
636private:
637 /// We use a simple cost model for edit actions, which seems good enough.
638 /// Simple cost model for edit actions. This seems to make the matching
639 /// algorithm perform reasonably well.
640 /// The values range between 0 and 1, or infinity if this edit action should
641 /// always be avoided.
642 static constexpr double DeletionCost = 1;
643 static constexpr double InsertionCost = 1;
644
645 double getUpdateCost(SNodeId Id1, SNodeId Id2) {
646 if (!DiffImpl.isMatchingPossible(S1.getIdInRoot(Id1), S2.getIdInRoot(Id2)))
647 return std::numeric_limits<double>::max();
648 return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
649 }
650
651 void computeTreeDist() {
652 for (SNodeId Id1 : S1.KeyRoots)
653 for (SNodeId Id2 : S2.KeyRoots)
654 computeForestDist(Id1, Id2);
655 }
656
657 void computeForestDist(SNodeId Id1, SNodeId Id2) {
658 assert(Id1 > 0 && Id2 > 0 && "Expecting offsets greater than 0.")(static_cast <bool> (Id1 > 0 && Id2 > 0 &&
"Expecting offsets greater than 0.") ? void (0) : __assert_fail
("Id1 > 0 && Id2 > 0 && \"Expecting offsets greater than 0.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 658, __extension__ __PRETTY_FUNCTION__))
;
659 SNodeId LMD1 = S1.getLeftMostDescendant(Id1);
660 SNodeId LMD2 = S2.getLeftMostDescendant(Id2);
661
662 ForestDist[LMD1][LMD2] = 0;
663 for (SNodeId D1 = LMD1 + 1; D1 <= Id1; ++D1) {
664 ForestDist[D1][LMD2] = ForestDist[D1 - 1][LMD2] + DeletionCost;
665 for (SNodeId D2 = LMD2 + 1; D2 <= Id2; ++D2) {
666 ForestDist[LMD1][D2] = ForestDist[LMD1][D2 - 1] + InsertionCost;
667 SNodeId DLMD1 = S1.getLeftMostDescendant(D1);
668 SNodeId DLMD2 = S2.getLeftMostDescendant(D2);
669 if (DLMD1 == LMD1 && DLMD2 == LMD2) {
670 double UpdateCost = getUpdateCost(D1, D2);
671 ForestDist[D1][D2] =
672 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
673 ForestDist[D1][D2 - 1] + InsertionCost,
674 ForestDist[D1 - 1][D2 - 1] + UpdateCost});
675 TreeDist[D1][D2] = ForestDist[D1][D2];
676 } else {
677 ForestDist[D1][D2] =
678 std::min({ForestDist[D1 - 1][D2] + DeletionCost,
679 ForestDist[D1][D2 - 1] + InsertionCost,
680 ForestDist[DLMD1][DLMD2] + TreeDist[D1][D2]});
681 }
682 }
683 }
684 }
685};
686
687ast_type_traits::ASTNodeKind Node::getType() const {
688 return ASTNode.getNodeKind();
689}
690
691StringRef Node::getTypeLabel() const { return getType().asStringRef(); }
692
693llvm::Optional<std::string> Node::getQualifiedIdentifier() const {
694 if (auto *ND = ASTNode.get<NamedDecl>()) {
695 if (ND->getDeclName().isIdentifier())
696 return ND->getQualifiedNameAsString();
697 }
698 return llvm::None;
699}
700
701llvm::Optional<StringRef> Node::getIdentifier() const {
702 if (auto *ND = ASTNode.get<NamedDecl>()) {
703 if (ND->getDeclName().isIdentifier())
704 return ND->getName();
705 }
706 return llvm::None;
707}
708
709namespace {
710// Compares nodes by their depth.
711struct HeightLess {
712 const SyntaxTree::Impl &Tree;
713 HeightLess(const SyntaxTree::Impl &Tree) : Tree(Tree) {}
714 bool operator()(NodeId Id1, NodeId Id2) const {
715 return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
716 }
717};
718} // end anonymous namespace
719
720namespace {
721// Priority queue for nodes, sorted descendingly by their height.
722class PriorityList {
723 const SyntaxTree::Impl &Tree;
724 HeightLess Cmp;
725 std::vector<NodeId> Container;
726 PriorityQueue<NodeId, std::vector<NodeId>, HeightLess> List;
727
728public:
729 PriorityList(const SyntaxTree::Impl &Tree)
730 : Tree(Tree), Cmp(Tree), List(Cmp, Container) {}
731
732 void push(NodeId id) { List.push(id); }
733
734 std::vector<NodeId> pop() {
735 int Max = peekMax();
736 std::vector<NodeId> Result;
737 if (Max == 0)
738 return Result;
739 while (peekMax() == Max) {
740 Result.push_back(List.top());
741 List.pop();
742 }
743 // TODO this is here to get a stable output, not a good heuristic
744 llvm::sort(Result.begin(), Result.end());
745 return Result;
746 }
747 int peekMax() const {
748 if (List.empty())
749 return 0;
750 return Tree.getNode(List.top()).Height;
751 }
752 void open(NodeId Id) {
753 for (NodeId Child : Tree.getNode(Id).Children)
754 push(Child);
755 }
756};
757} // end anonymous namespace
758
759bool ASTDiff::Impl::identical(NodeId Id1, NodeId Id2) const {
760 const Node &N1 = T1.getNode(Id1);
761 const Node &N2 = T2.getNode(Id2);
762 if (N1.Children.size() != N2.Children.size() ||
763 !isMatchingPossible(Id1, Id2) ||
764 T1.getNodeValue(Id1) != T2.getNodeValue(Id2))
765 return false;
766 for (size_t Id = 0, E = N1.Children.size(); Id < E; ++Id)
767 if (!identical(N1.Children[Id], N2.Children[Id]))
768 return false;
769 return true;
770}
771
772bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
773 return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
774}
775
776bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
777 NodeId Id2) const {
778 NodeId P1 = T1.getNode(Id1).Parent;
779 NodeId P2 = T2.getNode(Id2).Parent;
780 return (P1.isInvalid() && P2.isInvalid()) ||
781 (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
782}
783
784void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
785 NodeId Id2) const {
786 if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
787 Options.MaxSize)
788 return;
789 ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
790 std::vector<std::pair<NodeId, NodeId>> R = Matcher.getMatchingNodes();
791 for (const auto Tuple : R) {
792 NodeId Src = Tuple.first;
793 NodeId Dst = Tuple.second;
794 if (!M.hasSrc(Src) && !M.hasDst(Dst))
795 M.link(Src, Dst);
796 }
797}
798
799double ASTDiff::Impl::getJaccardSimilarity(const Mapping &M, NodeId Id1,
800 NodeId Id2) const {
801 int CommonDescendants = 0;
802 const Node &N1 = T1.getNode(Id1);
803 // Count the common descendants, excluding the subtree root.
804 for (NodeId Src = Id1 + 1; Src <= N1.RightMostDescendant; ++Src) {
805 NodeId Dst = M.getDst(Src);
806 CommonDescendants += int(Dst.isValid() && T2.isInSubtree(Dst, Id2));
807 }
808 // We need to subtract 1 to get the number of descendants excluding the root.
809 double Denominator = T1.getNumberOfDescendants(Id1) - 1 +
810 T2.getNumberOfDescendants(Id2) - 1 - CommonDescendants;
811 // CommonDescendants is less than the size of one subtree.
812 assert(Denominator >= 0 && "Expected non-negative denominator.")(static_cast <bool> (Denominator >= 0 && "Expected non-negative denominator."
) ? void (0) : __assert_fail ("Denominator >= 0 && \"Expected non-negative denominator.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/lib/Tooling/ASTDiff/ASTDiff.cpp"
, 812, __extension__ __PRETTY_FUNCTION__))
;
813 if (Denominator == 0)
814 return 0;
815 return CommonDescendants / Denominator;
816}
817
818NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
819 NodeId Candidate;
820 double HighestSimilarity = 0.0;
821 for (NodeId Id2 : T2) {
822 if (!isMatchingPossible(Id1, Id2))
823 continue;
824 if (M.hasDst(Id2))
825 continue;
826 double Similarity = getJaccardSimilarity(M, Id1, Id2);
827 if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
828 HighestSimilarity = Similarity;
829 Candidate = Id2;
830 }
831 }
832 return Candidate;
833}
834
835void ASTDiff::Impl::matchBottomUp(Mapping &M) const {
836 std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
837 for (NodeId Id1 : Postorder) {
838 if (Id1 == T1.getRootId() && !M.hasSrc(T1.getRootId()) &&
839 !M.hasDst(T2.getRootId())) {
840 if (isMatchingPossible(T1.getRootId(), T2.getRootId())) {
841 M.link(T1.getRootId(), T2.getRootId());
842 addOptimalMapping(M, T1.getRootId(), T2.getRootId());
843 }
844 break;
845 }
846 bool Matched = M.hasSrc(Id1);
847 const Node &N1 = T1.getNode(Id1);
848 bool MatchedChildren =
849 std::any_of(N1.Children.begin(), N1.Children.end(),
850 [&](NodeId Child) { return M.hasSrc(Child); });
851 if (Matched || !MatchedChildren)
852 continue;
853 NodeId Id2 = findCandidate(M, Id1);
854 if (Id2.isValid()) {
855 M.link(Id1, Id2);
856 addOptimalMapping(M, Id1, Id2);
857 }
858 }
859}
860
861Mapping ASTDiff::Impl::matchTopDown() const {
862 PriorityList L1(T1);
863 PriorityList L2(T2);
864
865 Mapping M(T1.getSize() + T2.getSize());
866
867 L1.push(T1.getRootId());
868 L2.push(T2.getRootId());
869
870 int Max1, Max2;
871 while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
872 Options.MinHeight) {
873 if (Max1 > Max2) {
874 for (NodeId Id : L1.pop())
875 L1.open(Id);
876 continue;
877 }
878 if (Max2 > Max1) {
879 for (NodeId Id : L2.pop())
880 L2.open(Id);
881 continue;
882 }
883 std::vector<NodeId> H1, H2;
884 H1 = L1.pop();
885 H2 = L2.pop();
886 for (NodeId Id1 : H1) {
887 for (NodeId Id2 : H2) {
888 if (identical(Id1, Id2) && !M.hasSrc(Id1) && !M.hasDst(Id2)) {
889 for (int I = 0, E = T1.getNumberOfDescendants(Id1); I < E; ++I)
890 M.link(Id1 + I, Id2 + I);
891 }
892 }
893 }
894 for (NodeId Id1 : H1) {
895 if (!M.hasSrc(Id1))
896 L1.open(Id1);
897 }
898 for (NodeId Id2 : H2) {
899 if (!M.hasDst(Id2))
900 L2.open(Id2);
901 }
902 }
903 return M;
904}
905
906ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
907 const ComparisonOptions &Options)
908 : T1(T1), T2(T2), Options(Options) {
909 computeMapping();
910 computeChangeKinds(TheMapping);
911}
912
913void ASTDiff::Impl::computeMapping() {
914 TheMapping = matchTopDown();
915 if (Options.StopAfterTopDown)
916 return;
917 matchBottomUp(TheMapping);
918}
919
920void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
921 for (NodeId Id1 : T1) {
922 if (!M.hasSrc(Id1)) {
923 T1.getMutableNode(Id1).Change = Delete;
924 T1.getMutableNode(Id1).Shift -= 1;
925 }
926 }
927 for (NodeId Id2 : T2) {
928 if (!M.hasDst(Id2)) {
929 T2.getMutableNode(Id2).Change = Insert;
930 T2.getMutableNode(Id2).Shift -= 1;
931 }
932 }
933 for (NodeId Id1 : T1.NodesBfs) {
934 NodeId Id2 = M.getDst(Id1);
935 if (Id2.isInvalid())
936 continue;
937 if (!haveSameParents(M, Id1, Id2) ||
938 T1.findPositionInParent(Id1, true) !=
939 T2.findPositionInParent(Id2, true)) {
940 T1.getMutableNode(Id1).Shift -= 1;
941 T2.getMutableNode(Id2).Shift -= 1;
942 }
943 }
944 for (NodeId Id2 : T2.NodesBfs) {
945 NodeId Id1 = M.getSrc(Id2);
946 if (Id1.isInvalid())
947 continue;
948 Node &N1 = T1.getMutableNode(Id1);
949 Node &N2 = T2.getMutableNode(Id2);
950 if (Id1.isInvalid())
951 continue;
952 if (!haveSameParents(M, Id1, Id2) ||
953 T1.findPositionInParent(Id1, true) !=
954 T2.findPositionInParent(Id2, true)) {
955 N1.Change = N2.Change = Move;
956 }
957 if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
958 N1.Change = N2.Change = (N1.Change == Move ? UpdateMove : Update);
959 }
960 }
961}
962
963ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
964 const ComparisonOptions &Options)
965 : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
966
967ASTDiff::~ASTDiff() = default;
968
969NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
970 return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
971}
972
973SyntaxTree::SyntaxTree(ASTContext &AST)
974 : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
1
Calling 'make_unique'
975 this, AST.getTranslationUnitDecl(), AST)) {}
976
977SyntaxTree::~SyntaxTree() = default;
978
979const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
980
981const Node &SyntaxTree::getNode(NodeId Id) const {
982 return TreeImpl->getNode(Id);
983}
984
985int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
986NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
987SyntaxTree::PreorderIterator SyntaxTree::begin() const {
988 return TreeImpl->begin();
989}
990SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
991
992int SyntaxTree::findPositionInParent(NodeId Id) const {
993 return TreeImpl->findPositionInParent(Id);
994}
995
996std::pair<unsigned, unsigned>
997SyntaxTree::getSourceRangeOffsets(const Node &N) const {
998 const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
999 SourceRange Range = N.ASTNode.getSourceRange();
1000 SourceLocation BeginLoc = Range.getBegin();
1001 SourceLocation EndLoc = Lexer::getLocForEndOfToken(
1002 Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
1003 if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
1004 if (ThisExpr->isImplicit())
1005 EndLoc = BeginLoc;
1006 }
1007 unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
1008 unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
1009 return {Begin, End};
1010}
1011
1012std::string SyntaxTree::getNodeValue(NodeId Id) const {
1013 return TreeImpl->getNodeValue(Id);
1014}
1015
1016std::string SyntaxTree::getNodeValue(const Node &N) const {
1017 return TreeImpl->getNodeValue(N);
1018}
1019
1020} // end namespace diff
1021} // end namespace clang

/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains some templates that are useful if you are working with the
11// STL at all.
12//
13// No library is required when using these functions.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator.h"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42
43namespace llvm {
44
45// Only used by compiler if both template types are the same. Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48
49namespace detail {
50
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56 *std::begin(std::declval<RangeT &>()))>::type;
57
58} // end namespace detail
59
60//===----------------------------------------------------------------------===//
61// Extra additions to <functional>
62//===----------------------------------------------------------------------===//
63
64template <class Ty> struct identity {
65 using argument_type = Ty;
66
67 Ty &operator()(Ty &self) const {
68 return self;
69 }
70 const Ty &operator()(const Ty &self) const {
71 return self;
72 }
73};
74
75template <class Ty> struct less_ptr {
76 bool operator()(const Ty* left, const Ty* right) const {
77 return *left < *right;
78 }
79};
80
81template <class Ty> struct greater_ptr {
82 bool operator()(const Ty* left, const Ty* right) const {
83 return *right < *left;
84 }
85};
86
87/// An efficient, type-erasing, non-owning reference to a callable. This is
88/// intended for use as the type of a function parameter that is not used
89/// after the function in question returns.
90///
91/// This class does not own the callable, so it is not in general safe to store
92/// a function_ref.
93template<typename Fn> class function_ref;
94
95template<typename Ret, typename ...Params>
96class function_ref<Ret(Params...)> {
97 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
98 intptr_t callable;
99
100 template<typename Callable>
101 static Ret callback_fn(intptr_t callable, Params ...params) {
102 return (*reinterpret_cast<Callable*>(callable))(
103 std::forward<Params>(params)...);
104 }
105
106public:
107 function_ref() = default;
108 function_ref(std::nullptr_t) {}
109
110 template <typename Callable>
111 function_ref(Callable &&callable,
112 typename std::enable_if<
113 !std::is_same<typename std::remove_reference<Callable>::type,
114 function_ref>::value>::type * = nullptr)
115 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
116 callable(reinterpret_cast<intptr_t>(&callable)) {}
117
118 Ret operator()(Params ...params) const {
119 return callback(callable, std::forward<Params>(params)...);
120 }
121
122 operator bool() const { return callback; }
123};
124
125// deleter - Very very very simple method that is used to invoke operator
126// delete on something. It is used like this:
127//
128// for_each(V.begin(), B.end(), deleter<Interval>);
129template <class T>
130inline void deleter(T *Ptr) {
131 delete Ptr;
132}
133
134//===----------------------------------------------------------------------===//
135// Extra additions to <iterator>
136//===----------------------------------------------------------------------===//
137
138namespace adl_detail {
139
140using std::begin;
141
142template <typename ContainerTy>
143auto adl_begin(ContainerTy &&container)
144 -> decltype(begin(std::forward<ContainerTy>(container))) {
145 return begin(std::forward<ContainerTy>(container));
146}
147
148using std::end;
149
150template <typename ContainerTy>
151auto adl_end(ContainerTy &&container)
152 -> decltype(end(std::forward<ContainerTy>(container))) {
153 return end(std::forward<ContainerTy>(container));
154}
155
156using std::swap;
157
158template <typename T>
159void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
160 std::declval<T>()))) {
161 swap(std::forward<T>(lhs), std::forward<T>(rhs));
162}
163
164} // end namespace adl_detail
165
166template <typename ContainerTy>
167auto adl_begin(ContainerTy &&container)
168 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
169 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
170}
171
172template <typename ContainerTy>
173auto adl_end(ContainerTy &&container)
174 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
175 return adl_detail::adl_end(std::forward<ContainerTy>(container));
176}
177
178template <typename T>
179void adl_swap(T &&lhs, T &&rhs) noexcept(
180 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
181 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
182}
183
184// mapped_iterator - This is a simple iterator adapter that causes a function to
185// be applied whenever operator* is invoked on the iterator.
186
187template <typename ItTy, typename FuncTy,
188 typename FuncReturnTy =
189 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
190class mapped_iterator
191 : public iterator_adaptor_base<
192 mapped_iterator<ItTy, FuncTy>, ItTy,
193 typename std::iterator_traits<ItTy>::iterator_category,
194 typename std::remove_reference<FuncReturnTy>::type> {
195public:
196 mapped_iterator(ItTy U, FuncTy F)
197 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
198
199 ItTy getCurrent() { return this->I; }
200
201 FuncReturnTy operator*() { return F(*this->I); }
202
203private:
204 FuncTy F;
205};
206
207// map_iterator - Provide a convenient way to create mapped_iterators, just like
208// make_pair is useful for creating pairs...
209template <class ItTy, class FuncTy>
210inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
211 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
212}
213
214/// Helper to determine if type T has a member called rbegin().
215template <typename Ty> class has_rbegin_impl {
216 using yes = char[1];
217 using no = char[2];
218
219 template <typename Inner>
220 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
221
222 template <typename>
223 static no& test(...);
224
225public:
226 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
227};
228
229/// Metafunction to determine if T& or T has a member called rbegin().
230template <typename Ty>
231struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
232};
233
234// Returns an iterator_range over the given container which iterates in reverse.
235// Note that the container must have rbegin()/rend() methods for this to work.
236template <typename ContainerTy>
237auto reverse(ContainerTy &&C,
238 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
239 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
240 return make_range(C.rbegin(), C.rend());
241}
242
243// Returns a std::reverse_iterator wrapped around the given iterator.
244template <typename IteratorTy>
245std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
246 return std::reverse_iterator<IteratorTy>(It);
247}
248
249// Returns an iterator_range over the given container which iterates in reverse.
250// Note that the container must have begin()/end() methods which return
251// bidirectional iterators for this to work.
252template <typename ContainerTy>
253auto reverse(
254 ContainerTy &&C,
255 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
256 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
257 llvm::make_reverse_iterator(std::begin(C)))) {
258 return make_range(llvm::make_reverse_iterator(std::end(C)),
259 llvm::make_reverse_iterator(std::begin(C)));
260}
261
262/// An iterator adaptor that filters the elements of given inner iterators.
263///
264/// The predicate parameter should be a callable object that accepts the wrapped
265/// iterator's reference type and returns a bool. When incrementing or
266/// decrementing the iterator, it will call the predicate on each element and
267/// skip any where it returns false.
268///
269/// \code
270/// int A[] = { 1, 2, 3, 4 };
271/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
272/// // R contains { 1, 3 }.
273/// \endcode
274template <typename WrappedIteratorT, typename PredicateT>
275class filter_iterator
276 : public iterator_adaptor_base<
277 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
278 typename std::common_type<
279 std::forward_iterator_tag,
280 typename std::iterator_traits<
281 WrappedIteratorT>::iterator_category>::type> {
282 using BaseT = iterator_adaptor_base<
283 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
284 typename std::common_type<
285 std::forward_iterator_tag,
286 typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
287 type>;
288
289 struct PayloadType {
290 WrappedIteratorT End;
291 PredicateT Pred;
292 };
293
294 Optional<PayloadType> Payload;
295
296 void findNextValid() {
297 assert(Payload && "Payload should be engaged when findNextValid is called")(static_cast <bool> (Payload && "Payload should be engaged when findNextValid is called"
) ? void (0) : __assert_fail ("Payload && \"Payload should be engaged when findNextValid is called\""
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 297, __extension__ __PRETTY_FUNCTION__))
;
298 while (this->I != Payload->End && !Payload->Pred(*this->I))
299 BaseT::operator++();
300 }
301
302 // Construct the begin iterator. The begin iterator requires to know where end
303 // is, so that it can properly stop when it hits end.
304 filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
305 : BaseT(std::move(Begin)),
306 Payload(PayloadType{std::move(End), std::move(Pred)}) {
307 findNextValid();
308 }
309
310 // Construct the end iterator. It's not incrementable, so Payload doesn't
311 // have to be engaged.
312 filter_iterator(WrappedIteratorT End) : BaseT(End) {}
313
314public:
315 using BaseT::operator++;
316
317 filter_iterator &operator++() {
318 BaseT::operator++();
319 findNextValid();
320 return *this;
321 }
322
323 template <typename RT, typename PT>
324 friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
325 make_filter_range(RT &&, PT);
326};
327
328/// Convenience function that takes a range of elements and a predicate,
329/// and return a new filter_iterator range.
330///
331/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
332/// lifetime of that temporary is not kept by the returned range object, and the
333/// temporary is going to be dropped on the floor after the make_iterator_range
334/// full expression that contains this function call.
335template <typename RangeT, typename PredicateT>
336iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
337make_filter_range(RangeT &&Range, PredicateT Pred) {
338 using FilterIteratorT =
339 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
340 return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
341 std::end(std::forward<RangeT>(Range)),
342 std::move(Pred)),
343 FilterIteratorT(std::end(std::forward<RangeT>(Range))));
344}
345
346// forward declarations required by zip_shortest/zip_first
347template <typename R, typename UnaryPredicate>
348bool all_of(R &&range, UnaryPredicate P);
349
350template <size_t... I> struct index_sequence;
351
352template <class... Ts> struct index_sequence_for;
353
354namespace detail {
355
356using std::declval;
357
358// We have to alias this since inlining the actual type at the usage site
359// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
360template<typename... Iters> struct ZipTupleType {
361 using type = std::tuple<decltype(*declval<Iters>())...>;
362};
363
364template <typename ZipType, typename... Iters>
365using zip_traits = iterator_facade_base<
366 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
367 typename std::iterator_traits<
368 Iters>::iterator_category...>::type,
369 // ^ TODO: Implement random access methods.
370 typename ZipTupleType<Iters...>::type,
371 typename std::iterator_traits<typename std::tuple_element<
372 0, std::tuple<Iters...>>::type>::difference_type,
373 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
374 // inner iterators have the same difference_type. It would fail if, for
375 // instance, the second field's difference_type were non-numeric while the
376 // first is.
377 typename ZipTupleType<Iters...>::type *,
378 typename ZipTupleType<Iters...>::type>;
379
380template <typename ZipType, typename... Iters>
381struct zip_common : public zip_traits<ZipType, Iters...> {
382 using Base = zip_traits<ZipType, Iters...>;
383 using value_type = typename Base::value_type;
384
385 std::tuple<Iters...> iterators;
386
387protected:
388 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
389 return value_type(*std::get<Ns>(iterators)...);
390 }
391
392 template <size_t... Ns>
393 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
394 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
395 }
396
397 template <size_t... Ns>
398 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
399 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
400 }
401
402public:
403 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
404
405 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
406
407 const value_type operator*() const {
408 return deref(index_sequence_for<Iters...>{});
409 }
410
411 ZipType &operator++() {
412 iterators = tup_inc(index_sequence_for<Iters...>{});
413 return *reinterpret_cast<ZipType *>(this);
414 }
415
416 ZipType &operator--() {
417 static_assert(Base::IsBidirectional,
418 "All inner iterators must be at least bidirectional.");
419 iterators = tup_dec(index_sequence_for<Iters...>{});
420 return *reinterpret_cast<ZipType *>(this);
421 }
422};
423
424template <typename... Iters>
425struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
426 using Base = zip_common<zip_first<Iters...>, Iters...>;
427
428 bool operator==(const zip_first<Iters...> &other) const {
429 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
430 }
431
432 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
433};
434
435template <typename... Iters>
436class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
437 template <size_t... Ns>
438 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
439 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
440 std::get<Ns>(other.iterators)...},
441 identity<bool>{});
442 }
443
444public:
445 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
446
447 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
448
449 bool operator==(const zip_shortest<Iters...> &other) const {
450 return !test(other, index_sequence_for<Iters...>{});
451 }
452};
453
454template <template <typename...> class ItType, typename... Args> class zippy {
455public:
456 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
457 using iterator_category = typename iterator::iterator_category;
458 using value_type = typename iterator::value_type;
459 using difference_type = typename iterator::difference_type;
460 using pointer = typename iterator::pointer;
461 using reference = typename iterator::reference;
462
463private:
464 std::tuple<Args...> ts;
465
466 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
467 return iterator(std::begin(std::get<Ns>(ts))...);
468 }
469 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
470 return iterator(std::end(std::get<Ns>(ts))...);
471 }
472
473public:
474 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
475
476 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
477 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
478};
479
480} // end namespace detail
481
482/// zip iterator for two or more iteratable types.
483template <typename T, typename U, typename... Args>
484detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
485 Args &&... args) {
486 return detail::zippy<detail::zip_shortest, T, U, Args...>(
487 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
488}
489
490/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
491/// be the shortest.
492template <typename T, typename U, typename... Args>
493detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
494 Args &&... args) {
495 return detail::zippy<detail::zip_first, T, U, Args...>(
496 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
497}
498
499/// Iterator wrapper that concatenates sequences together.
500///
501/// This can concatenate different iterators, even with different types, into
502/// a single iterator provided the value types of all the concatenated
503/// iterators expose `reference` and `pointer` types that can be converted to
504/// `ValueT &` and `ValueT *` respectively. It doesn't support more
505/// interesting/customized pointer or reference types.
506///
507/// Currently this only supports forward or higher iterator categories as
508/// inputs and always exposes a forward iterator interface.
509template <typename ValueT, typename... IterTs>
510class concat_iterator
511 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
512 std::forward_iterator_tag, ValueT> {
513 using BaseT = typename concat_iterator::iterator_facade_base;
514
515 /// We store both the current and end iterators for each concatenated
516 /// sequence in a tuple of pairs.
517 ///
518 /// Note that something like iterator_range seems nice at first here, but the
519 /// range properties are of little benefit and end up getting in the way
520 /// because we need to do mutation on the current iterators.
521 std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
522
523 /// Attempts to increment a specific iterator.
524 ///
525 /// Returns true if it was able to increment the iterator. Returns false if
526 /// the iterator is already at the end iterator.
527 template <size_t Index> bool incrementHelper() {
528 auto &IterPair = std::get<Index>(IterPairs);
529 if (IterPair.first == IterPair.second)
530 return false;
531
532 ++IterPair.first;
533 return true;
534 }
535
536 /// Increments the first non-end iterator.
537 ///
538 /// It is an error to call this with all iterators at the end.
539 template <size_t... Ns> void increment(index_sequence<Ns...>) {
540 // Build a sequence of functions to increment each iterator if possible.
541 bool (concat_iterator::*IncrementHelperFns[])() = {
542 &concat_iterator::incrementHelper<Ns>...};
543
544 // Loop over them, and stop as soon as we succeed at incrementing one.
545 for (auto &IncrementHelperFn : IncrementHelperFns)
546 if ((this->*IncrementHelperFn)())
547 return;
548
549 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 549)
;
550 }
551
552 /// Returns null if the specified iterator is at the end. Otherwise,
553 /// dereferences the iterator and returns the address of the resulting
554 /// reference.
555 template <size_t Index> ValueT *getHelper() const {
556 auto &IterPair = std::get<Index>(IterPairs);
557 if (IterPair.first == IterPair.second)
558 return nullptr;
559
560 return &*IterPair.first;
561 }
562
563 /// Finds the first non-end iterator, dereferences, and returns the resulting
564 /// reference.
565 ///
566 /// It is an error to call this with all iterators at the end.
567 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
568 // Build a sequence of functions to get from iterator if possible.
569 ValueT *(concat_iterator::*GetHelperFns[])() const = {
570 &concat_iterator::getHelper<Ns>...};
571
572 // Loop over them, and return the first result we find.
573 for (auto &GetHelperFn : GetHelperFns)
574 if (ValueT *P = (this->*GetHelperFn)())
575 return *P;
576
577 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 577)
;
578 }
579
580public:
581 /// Constructs an iterator from a squence of ranges.
582 ///
583 /// We need the full range to know how to switch between each of the
584 /// iterators.
585 template <typename... RangeTs>
586 explicit concat_iterator(RangeTs &&... Ranges)
587 : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
588
589 using BaseT::operator++;
590
591 concat_iterator &operator++() {
592 increment(index_sequence_for<IterTs...>());
593 return *this;
594 }
595
596 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
597
598 bool operator==(const concat_iterator &RHS) const {
599 return IterPairs == RHS.IterPairs;
600 }
601};
602
603namespace detail {
604
605/// Helper to store a sequence of ranges being concatenated and access them.
606///
607/// This is designed to facilitate providing actual storage when temporaries
608/// are passed into the constructor such that we can use it as part of range
609/// based for loops.
610template <typename ValueT, typename... RangeTs> class concat_range {
611public:
612 using iterator =
613 concat_iterator<ValueT,
614 decltype(std::begin(std::declval<RangeTs &>()))...>;
615
616private:
617 std::tuple<RangeTs...> Ranges;
618
619 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
620 return iterator(std::get<Ns>(Ranges)...);
621 }
622 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
623 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
624 std::end(std::get<Ns>(Ranges)))...);
625 }
626
627public:
628 concat_range(RangeTs &&... Ranges)
629 : Ranges(std::forward<RangeTs>(Ranges)...) {}
630
631 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
632 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
633};
634
635} // end namespace detail
636
637/// Concatenated range across two or more ranges.
638///
639/// The desired value type must be explicitly specified.
640template <typename ValueT, typename... RangeTs>
641detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
642 static_assert(sizeof...(RangeTs) > 1,
643 "Need more than one range to concatenate!");
644 return detail::concat_range<ValueT, RangeTs...>(
645 std::forward<RangeTs>(Ranges)...);
646}
647
648//===----------------------------------------------------------------------===//
649// Extra additions to <utility>
650//===----------------------------------------------------------------------===//
651
652/// \brief Function object to check whether the first component of a std::pair
653/// compares less than the first component of another std::pair.
654struct less_first {
655 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
656 return lhs.first < rhs.first;
657 }
658};
659
660/// \brief Function object to check whether the second component of a std::pair
661/// compares less than the second component of another std::pair.
662struct less_second {
663 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
664 return lhs.second < rhs.second;
665 }
666};
667
668// A subset of N3658. More stuff can be added as-needed.
669
670/// \brief Represents a compile-time sequence of integers.
671template <class T, T... I> struct integer_sequence {
672 using value_type = T;
673
674 static constexpr size_t size() { return sizeof...(I); }
675};
676
677/// \brief Alias for the common case of a sequence of size_ts.
678template <size_t... I>
679struct index_sequence : integer_sequence<std::size_t, I...> {};
680
681template <std::size_t N, std::size_t... I>
682struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
683template <std::size_t... I>
684struct build_index_impl<0, I...> : index_sequence<I...> {};
685
686/// \brief Creates a compile-time integer sequence for a parameter pack.
687template <class... Ts>
688struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
689
690/// Utility type to build an inheritance chain that makes it easy to rank
691/// overload candidates.
692template <int N> struct rank : rank<N - 1> {};
693template <> struct rank<0> {};
694
695/// \brief traits class for checking whether type T is one of any of the given
696/// types in the variadic list.
697template <typename T, typename... Ts> struct is_one_of {
698 static const bool value = false;
699};
700
701template <typename T, typename U, typename... Ts>
702struct is_one_of<T, U, Ts...> {
703 static const bool value =
704 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
705};
706
707/// \brief traits class for checking whether type T is a base class for all
708/// the given types in the variadic list.
709template <typename T, typename... Ts> struct are_base_of {
710 static const bool value = true;
711};
712
713template <typename T, typename U, typename... Ts>
714struct are_base_of<T, U, Ts...> {
715 static const bool value =
716 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
717};
718
719//===----------------------------------------------------------------------===//
720// Extra additions for arrays
721//===----------------------------------------------------------------------===//
722
723/// Find the length of an array.
724template <class T, std::size_t N>
725constexpr inline size_t array_lengthof(T (&)[N]) {
726 return N;
727}
728
729/// Adapt std::less<T> for array_pod_sort.
730template<typename T>
731inline int array_pod_sort_comparator(const void *P1, const void *P2) {
732 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
733 *reinterpret_cast<const T*>(P2)))
734 return -1;
735 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
736 *reinterpret_cast<const T*>(P1)))
737 return 1;
738 return 0;
739}
740
741/// get_array_pod_sort_comparator - This is an internal helper function used to
742/// get type deduction of T right.
743template<typename T>
744inline int (*get_array_pod_sort_comparator(const T &))
745 (const void*, const void*) {
746 return array_pod_sort_comparator<T>;
747}
748
749/// array_pod_sort - This sorts an array with the specified start and end
750/// extent. This is just like std::sort, except that it calls qsort instead of
751/// using an inlined template. qsort is slightly slower than std::sort, but
752/// most sorts are not performance critical in LLVM and std::sort has to be
753/// template instantiated for each type, leading to significant measured code
754/// bloat. This function should generally be used instead of std::sort where
755/// possible.
756///
757/// This function assumes that you have simple POD-like types that can be
758/// compared with std::less and can be moved with memcpy. If this isn't true,
759/// you should use std::sort.
760///
761/// NOTE: If qsort_r were portable, we could allow a custom comparator and
762/// default to std::less.
763template<class IteratorTy>
764inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
765 // Don't inefficiently call qsort with one element or trigger undefined
766 // behavior with an empty sequence.
767 auto NElts = End - Start;
768 if (NElts <= 1) return;
769#ifdef EXPENSIVE_CHECKS
770 std::mt19937 Generator(std::random_device{}());
771 std::shuffle(Start, End, Generator);
772#endif
773 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
774}
775
776template <class IteratorTy>
777inline void array_pod_sort(
778 IteratorTy Start, IteratorTy End,
779 int (*Compare)(
780 const typename std::iterator_traits<IteratorTy>::value_type *,
781 const typename std::iterator_traits<IteratorTy>::value_type *)) {
782 // Don't inefficiently call qsort with one element or trigger undefined
783 // behavior with an empty sequence.
784 auto NElts = End - Start;
785 if (NElts <= 1) return;
786#ifdef EXPENSIVE_CHECKS
787 std::mt19937 Generator(std::random_device{}());
788 std::shuffle(Start, End, Generator);
789#endif
790 qsort(&*Start, NElts, sizeof(*Start),
791 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
792}
793
794// Provide wrappers to std::sort which shuffle the elements before sorting
795// to help uncover non-deterministic behavior (PR35135).
796template <typename IteratorTy>
797inline void sort(IteratorTy Start, IteratorTy End) {
798#ifdef EXPENSIVE_CHECKS
799 std::mt19937 Generator(std::random_device{}());
800 std::shuffle(Start, End, Generator);
801#endif
802 std::sort(Start, End);
803}
804
805template <typename IteratorTy, typename Compare>
806inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
807#ifdef EXPENSIVE_CHECKS
808 std::mt19937 Generator(std::random_device{}());
809 std::shuffle(Start, End, Generator);
810#endif
811 std::sort(Start, End, Comp);
812}
813
814//===----------------------------------------------------------------------===//
815// Extra additions to <algorithm>
816//===----------------------------------------------------------------------===//
817
818/// For a container of pointers, deletes the pointers and then clears the
819/// container.
820template<typename Container>
821void DeleteContainerPointers(Container &C) {
822 for (auto V : C)
823 delete V;
824 C.clear();
825}
826
827/// In a container of pairs (usually a map) whose second element is a pointer,
828/// deletes the second elements and then clears the container.
829template<typename Container>
830void DeleteContainerSeconds(Container &C) {
831 for (auto &V : C)
832 delete V.second;
833 C.clear();
834}
835
836/// Provide wrappers to std::for_each which take ranges instead of having to
837/// pass begin/end explicitly.
838template <typename R, typename UnaryPredicate>
839UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
840 return std::for_each(adl_begin(Range), adl_end(Range), P);
841}
842
843/// Provide wrappers to std::all_of which take ranges instead of having to pass
844/// begin/end explicitly.
845template <typename R, typename UnaryPredicate>
846bool all_of(R &&Range, UnaryPredicate P) {
847 return std::all_of(adl_begin(Range), adl_end(Range), P);
848}
849
850/// Provide wrappers to std::any_of which take ranges instead of having to pass
851/// begin/end explicitly.
852template <typename R, typename UnaryPredicate>
853bool any_of(R &&Range, UnaryPredicate P) {
854 return std::any_of(adl_begin(Range), adl_end(Range), P);
855}
856
857/// Provide wrappers to std::none_of which take ranges instead of having to pass
858/// begin/end explicitly.
859template <typename R, typename UnaryPredicate>
860bool none_of(R &&Range, UnaryPredicate P) {
861 return std::none_of(adl_begin(Range), adl_end(Range), P);
862}
863
864/// Provide wrappers to std::find which take ranges instead of having to pass
865/// begin/end explicitly.
866template <typename R, typename T>
867auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
868 return std::find(adl_begin(Range), adl_end(Range), Val);
869}
870
871/// Provide wrappers to std::find_if which take ranges instead of having to pass
872/// begin/end explicitly.
873template <typename R, typename UnaryPredicate>
874auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
875 return std::find_if(adl_begin(Range), adl_end(Range), P);
876}
877
878template <typename R, typename UnaryPredicate>
879auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
880 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
881}
882
883/// Provide wrappers to std::remove_if which take ranges instead of having to
884/// pass begin/end explicitly.
885template <typename R, typename UnaryPredicate>
886auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
887 return std::remove_if(adl_begin(Range), adl_end(Range), P);
888}
889
890/// Provide wrappers to std::copy_if which take ranges instead of having to
891/// pass begin/end explicitly.
892template <typename R, typename OutputIt, typename UnaryPredicate>
893OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
894 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
895}
896
897template <typename R, typename OutputIt>
898OutputIt copy(R &&Range, OutputIt Out) {
899 return std::copy(adl_begin(Range), adl_end(Range), Out);
900}
901
902/// Wrapper function around std::find to detect if an element exists
903/// in a container.
904template <typename R, typename E>
905bool is_contained(R &&Range, const E &Element) {
906 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
907}
908
909/// Wrapper function around std::count to count the number of times an element
910/// \p Element occurs in the given range \p Range.
911template <typename R, typename E>
912auto count(R &&Range, const E &Element) ->
913 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
914 return std::count(adl_begin(Range), adl_end(Range), Element);
915}
916
917/// Wrapper function around std::count_if to count the number of times an
918/// element satisfying a given predicate occurs in a range.
919template <typename R, typename UnaryPredicate>
920auto count_if(R &&Range, UnaryPredicate P) ->
921 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
922 return std::count_if(adl_begin(Range), adl_end(Range), P);
923}
924
925/// Wrapper function around std::transform to apply a function to a range and
926/// store the result elsewhere.
927template <typename R, typename OutputIt, typename UnaryPredicate>
928OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
929 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
930}
931
932/// Provide wrappers to std::partition which take ranges instead of having to
933/// pass begin/end explicitly.
934template <typename R, typename UnaryPredicate>
935auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
936 return std::partition(adl_begin(Range), adl_end(Range), P);
937}
938
939/// Provide wrappers to std::lower_bound which take ranges instead of having to
940/// pass begin/end explicitly.
941template <typename R, typename ForwardIt>
942auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
943 return std::lower_bound(adl_begin(Range), adl_end(Range), I);
944}
945
946/// \brief Given a range of type R, iterate the entire range and return a
947/// SmallVector with elements of the vector. This is useful, for example,
948/// when you want to iterate a range and then sort the results.
949template <unsigned Size, typename R>
950SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
951to_vector(R &&Range) {
952 return {adl_begin(Range), adl_end(Range)};
953}
954
955/// Provide a container algorithm similar to C++ Library Fundamentals v2's
956/// `erase_if` which is equivalent to:
957///
958/// C.erase(remove_if(C, pred), C.end());
959///
960/// This version works for any container with an erase method call accepting
961/// two iterators.
962template <typename Container, typename UnaryPredicate>
963void erase_if(Container &C, UnaryPredicate P) {
964 C.erase(remove_if(C, P), C.end());
965}
966
967//===----------------------------------------------------------------------===//
968// Extra additions to <memory>
969//===----------------------------------------------------------------------===//
970
971// Implement make_unique according to N3656.
972
973/// \brief Constructs a `new T()` with the given args and returns a
974/// `unique_ptr<T>` which owns the object.
975///
976/// Example:
977///
978/// auto p = make_unique<int>();
979/// auto p = make_unique<std::tuple<int, int>>(0, 1);
980template <class T, class... Args>
981typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
982make_unique(Args &&... args) {
983 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
2
Calling constructor for 'Impl'
984}
985
986/// \brief Constructs a `new T[n]` with the given args and returns a
987/// `unique_ptr<T[]>` which owns the object.
988///
989/// \param n size of the new array.
990///
991/// Example:
992///
993/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
994template <class T>
995typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
996 std::unique_ptr<T>>::type
997make_unique(size_t n) {
998 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
999}
1000
1001/// This function isn't used and is only here to provide better compile errors.
1002template <class T, class... Args>
1003typename std::enable_if<std::extent<T>::value != 0>::type
1004make_unique(Args &&...) = delete;
1005
1006struct FreeDeleter {
1007 void operator()(void* v) {
1008 ::free(v);
1009 }
1010};
1011
1012template<typename First, typename Second>
1013struct pair_hash {
1014 size_t operator()(const std::pair<First, Second> &P) const {
1015 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1016 }
1017};
1018
1019/// A functor like C++14's std::less<void> in its absence.
1020struct less {
1021 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1022 return std::forward<A>(a) < std::forward<B>(b);
1023 }
1024};
1025
1026/// A functor like C++14's std::equal<void> in its absence.
1027struct equal {
1028 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1029 return std::forward<A>(a) == std::forward<B>(b);
1030 }
1031};
1032
1033/// Binary functor that adapts to any other binary functor after dereferencing
1034/// operands.
1035template <typename T> struct deref {
1036 T func;
1037
1038 // Could be further improved to cope with non-derivable functors and
1039 // non-binary functors (should be a variadic template member function
1040 // operator()).
1041 template <typename A, typename B>
1042 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1043 assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 1043, __extension__ __PRETTY_FUNCTION__))
;
1044 assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 1044, __extension__ __PRETTY_FUNCTION__))
;
1045 return func(*lhs, *rhs);
1046 }
1047};
1048
1049namespace detail {
1050
1051template <typename R> class enumerator_iter;
1052
1053template <typename R> struct result_pair {
1054 friend class enumerator_iter<R>;
1055
1056 result_pair() = default;
1057 result_pair(std::size_t Index, IterOfRange<R> Iter)
1058 : Index(Index), Iter(Iter) {}
1059
1060 result_pair<R> &operator=(const result_pair<R> &Other) {
1061 Index = Other.Index;
1062 Iter = Other.Iter;
1063 return *this;
1064 }
1065
1066 std::size_t index() const { return Index; }
1067 const ValueOfRange<R> &value() const { return *Iter; }
1068 ValueOfRange<R> &value() { return *Iter; }
1069
1070private:
1071 std::size_t Index = std::numeric_limits<std::size_t>::max();
1072 IterOfRange<R> Iter;
1073};
1074
1075template <typename R>
1076class enumerator_iter
1077 : public iterator_facade_base<
1078 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1079 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1080 typename std::iterator_traits<IterOfRange<R>>::pointer,
1081 typename std::iterator_traits<IterOfRange<R>>::reference> {
1082 using result_type = result_pair<R>;
1083
1084public:
1085 explicit enumerator_iter(IterOfRange<R> EndIter)
1086 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1087
1088 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1089 : Result(Index, Iter) {}
1090
1091 result_type &operator*() { return Result; }
1092 const result_type &operator*() const { return Result; }
1093
1094 enumerator_iter<R> &operator++() {
1095 assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h"
, 1095, __extension__ __PRETTY_FUNCTION__))
;
1096 ++Result.Iter;
1097 ++Result.Index;
1098 return *this;
1099 }
1100
1101 bool operator==(const enumerator_iter<R> &RHS) const {
1102 // Don't compare indices here, only iterators. It's possible for an end
1103 // iterator to have different indices depending on whether it was created
1104 // by calling std::end() versus incrementing a valid iterator.
1105 return Result.Iter == RHS.Result.Iter;
1106 }
1107
1108 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1109 Result = Other.Result;
1110 return *this;
1111 }
1112
1113private:
1114 result_type Result;
1115};
1116
1117template <typename R> class enumerator {
1118public:
1119 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1120
1121 enumerator_iter<R> begin() {
1122 return enumerator_iter<R>(0, std::begin(TheRange));
1123 }
1124
1125 enumerator_iter<R> end() {
1126 return enumerator_iter<R>(std::end(TheRange));
1127 }
1128
1129private:
1130 R TheRange;
1131};
1132
1133} // end namespace detail
1134
1135/// Given an input range, returns a new range whose values are are pair (A,B)
1136/// such that A is the 0-based index of the item in the sequence, and B is
1137/// the value from the original sequence. Example:
1138///
1139/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1140/// for (auto X : enumerate(Items)) {
1141/// printf("Item %d - %c\n", X.index(), X.value());
1142/// }
1143///
1144/// Output:
1145/// Item 0 - A
1146/// Item 1 - B
1147/// Item 2 - C
1148/// Item 3 - D
1149///
1150template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1151 return detail::enumerator<R>(std::forward<R>(TheRange));
1152}
1153
1154namespace detail {
1155
1156template <typename F, typename Tuple, std::size_t... I>
1157auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1158 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1159 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1160}
1161
1162} // end namespace detail
1163
1164/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1165/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1166/// return the result.
1167template <typename F, typename Tuple>
1168auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1169 std::forward<F>(f), std::forward<Tuple>(t),
1170 build_index_impl<
1171 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1172 using Indices = build_index_impl<
1173 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1174
1175 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1176 Indices{});
1177}
1178
1179} // end namespace llvm
1180
1181#endif // LLVM_ADT_STLEXTRAS_H

/usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/bits/std_function.h

1// Implementation of std::function -*- C++ -*-
2
3// Copyright (C) 2004-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file include/bits/function.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{functional}
28 */
29
30#ifndef _GLIBCXX_STD_FUNCTION_H1
31#define _GLIBCXX_STD_FUNCTION_H1 1
32
33#pragma GCC system_header
34
35#if __cplusplus201103L < 201103L
36# include <bits/c++0x_warning.h>
37#else
38
39#if __cpp_rtti199711
40# include <typeinfo>
41#endif
42#include <bits/stl_function.h>
43#include <bits/invoke.h>
44#include <bits/refwrap.h>
45#include <bits/functexcept.h>
46
47namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
48{
49_GLIBCXX_BEGIN_NAMESPACE_VERSION
50
51 /**
52 * Derives from @c unary_function or @c binary_function, or perhaps
53 * nothing, depending on the number of arguments provided. The
54 * primary template is the basis case, which derives nothing.
55 */
56 template<typename _Res, typename... _ArgTypes>
57 struct _Maybe_unary_or_binary_function { };
58
59 /// Derives from @c unary_function, as appropriate.
60 template<typename _Res, typename _T1>
61 struct _Maybe_unary_or_binary_function<_Res, _T1>
62 : std::unary_function<_T1, _Res> { };
63
64 /// Derives from @c binary_function, as appropriate.
65 template<typename _Res, typename _T1, typename _T2>
66 struct _Maybe_unary_or_binary_function<_Res, _T1, _T2>
67 : std::binary_function<_T1, _T2, _Res> { };
68
69
70 /**
71 * @brief Exception class thrown when class template function's
72 * operator() is called with an empty target.
73 * @ingroup exceptions
74 */
75 class bad_function_call : public std::exception
76 {
77 public:
78 virtual ~bad_function_call() noexcept;
79
80 const char* what() const noexcept;
81 };
82
83 /**
84 * Trait identifying "location-invariant" types, meaning that the
85 * address of the object (or any of its members) will not escape.
86 * Trivially copyable types are location-invariant and users can
87 * specialize this trait for other types.
88 */
89 template<typename _Tp>
90 struct __is_location_invariant
91 : is_trivially_copyable<_Tp>::type
92 { };
93
94 class _Undefined_class;
95
96 union _Nocopy_types
97 {
98 void* _M_object;
99 const void* _M_const_object;
100 void (*_M_function_pointer)();
101 void (_Undefined_class::*_M_member_pointer)();
102 };
103
104 union [[gnu::may_alias]] _Any_data
105 {
106 void* _M_access() { return &_M_pod_data[0]; }
107 const void* _M_access() const { return &_M_pod_data[0]; }
108
109 template<typename _Tp>
110 _Tp&
111 _M_access()
112 { return *static_cast<_Tp*>(_M_access()); }
113
114 template<typename _Tp>
115 const _Tp&
116 _M_access() const
117 { return *static_cast<const _Tp*>(_M_access()); }
118
119 _Nocopy_types _M_unused;
120 char _M_pod_data[sizeof(_Nocopy_types)];
121 };
122
123 enum _Manager_operation
124 {
125 __get_type_info,
126 __get_functor_ptr,
127 __clone_functor,
128 __destroy_functor
129 };
130
131 // Simple type wrapper that helps avoid annoying const problems
132 // when casting between void pointers and pointers-to-pointers.
133 template<typename _Tp>
134 struct _Simple_type_wrapper
135 {
136 _Simple_type_wrapper(_Tp __value) : __value(__value) { }
137
138 _Tp __value;
139 };
140
141 template<typename _Tp>
142 struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
143 : __is_location_invariant<_Tp>
144 { };
145
146 template<typename _Signature>
147 class function;
148
149 /// Base class of all polymorphic function object wrappers.
150 class _Function_base
151 {
152 public:
153 static const std::size_t _M_max_size = sizeof(_Nocopy_types);
154 static const std::size_t _M_max_align = __alignof__(_Nocopy_types);
155
156 template<typename _Functor>
157 class _Base_manager
158 {
159 protected:
160 static const bool __stored_locally =
161 (__is_location_invariant<_Functor>::value
162 && sizeof(_Functor) <= _M_max_size
163 && __alignof__(_Functor) <= _M_max_align
164 && (_M_max_align % __alignof__(_Functor) == 0));
165
166 typedef integral_constant<bool, __stored_locally> _Local_storage;
167
168 // Retrieve a pointer to the function object
169 static _Functor*
170 _M_get_pointer(const _Any_data& __source)
171 {
172 const _Functor* __ptr =
173 __stored_locally? std::__addressof(__source._M_access<_Functor>())
174 /* have stored a pointer */ : __source._M_access<_Functor*>();
175 return const_cast<_Functor*>(__ptr);
176 }
177
178 // Clone a location-invariant function object that fits within
179 // an _Any_data structure.
180 static void
181 _M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
182 {
183 ::new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
184 }
185
186 // Clone a function object that is not location-invariant or
187 // that cannot fit into an _Any_data structure.
188 static void
189 _M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
190 {
191 __dest._M_access<_Functor*>() =
192 new _Functor(*__source._M_access<_Functor*>());
193 }
194
195 // Destroying a location-invariant object may still require
196 // destruction.
197 static void
198 _M_destroy(_Any_data& __victim, true_type)
199 {
200 __victim._M_access<_Functor>().~_Functor();
201 }
202
203 // Destroying an object located on the heap.
204 static void
205 _M_destroy(_Any_data& __victim, false_type)
206 {
207 delete __victim._M_access<_Functor*>();
208 }
209
210 public:
211 static bool
212 _M_manager(_Any_data& __dest, const _Any_data& __source,
213 _Manager_operation __op)
214 {
215 switch (__op)
216 {
217#if __cpp_rtti199711
218 case __get_type_info:
219 __dest._M_access<const type_info*>() = &typeid(_Functor);
220 break;
221#endif
222 case __get_functor_ptr:
223 __dest._M_access<_Functor*>() = _M_get_pointer(__source);
224 break;
225
226 case __clone_functor:
227 _M_clone(__dest, __source, _Local_storage());
228 break;
229
230 case __destroy_functor:
231 _M_destroy(__dest, _Local_storage());
232 break;
233 }
234 return false;
235 }
236
237 static void
238 _M_init_functor(_Any_data& __functor, _Functor&& __f)
239 { _M_init_functor(__functor, std::move(__f), _Local_storage()); }
7
Calling '_Base_manager::_M_init_functor'
9
Returned allocated memory
240
241 template<typename _Signature>
242 static bool
243 _M_not_empty_function(const function<_Signature>& __f)
244 { return static_cast<bool>(__f); }
245
246 template<typename _Tp>
247 static bool
248 _M_not_empty_function(_Tp* __fp)
249 { return __fp != nullptr; }
250
251 template<typename _Class, typename _Tp>
252 static bool
253 _M_not_empty_function(_Tp _Class::* __mp)
254 { return __mp != nullptr; }
255
256 template<typename _Tp>
257 static bool
258 _M_not_empty_function(const _Tp&)
259 { return true; }
260
261 private:
262 static void
263 _M_init_functor(_Any_data& __functor, _Functor&& __f, true_type)
264 { ::new (__functor._M_access()) _Functor(std::move(__f)); }
265
266 static void
267 _M_init_functor(_Any_data& __functor, _Functor&& __f, false_type)
268 { __functor._M_access<_Functor*>() = new _Functor(std::move(__f)); }
8
Memory is allocated
269 };
270
271 _Function_base() : _M_manager(nullptr) { }
272
273 ~_Function_base()
274 {
275 if (_M_manager)
276 _M_manager(_M_functor, _M_functor, __destroy_functor);
277 }
278
279 bool _M_empty() const { return !_M_manager; }
280
281 typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
282 _Manager_operation);
283
284 _Any_data _M_functor;
285 _Manager_type _M_manager;
286 };
287
288 template<typename _Signature, typename _Functor>
289 class _Function_handler;
290
291 template<typename _Res, typename _Functor, typename... _ArgTypes>
292 class _Function_handler<_Res(_ArgTypes...), _Functor>
293 : public _Function_base::_Base_manager<_Functor>
294 {
295 typedef _Function_base::_Base_manager<_Functor> _Base;
296
297 public:
298 static _Res
299 _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
300 {
301 return (*_Base::_M_get_pointer(__functor))(
302 std::forward<_ArgTypes>(__args)...);
303 }
304 };
305
306 template<typename _Functor, typename... _ArgTypes>
307 class _Function_handler<void(_ArgTypes...), _Functor>
308 : public _Function_base::_Base_manager<_Functor>
309 {
310 typedef _Function_base::_Base_manager<_Functor> _Base;
311
312 public:
313 static void
314 _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
315 {
316 (*_Base::_M_get_pointer(__functor))(
317 std::forward<_ArgTypes>(__args)...);
318 }
319 };
320
321 template<typename _Class, typename _Member, typename _Res,
322 typename... _ArgTypes>
323 class _Function_handler<_Res(_ArgTypes...), _Member _Class::*>
324 : public _Function_handler<void(_ArgTypes...), _Member _Class::*>
325 {
326 typedef _Function_handler<void(_ArgTypes...), _Member _Class::*>
327 _Base;
328
329 public:
330 static _Res
331 _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
332 {
333 return std::__invoke(_Base::_M_get_pointer(__functor)->__value,
334 std::forward<_ArgTypes>(__args)...);
335 }
336 };
337
338 template<typename _Class, typename _Member, typename... _ArgTypes>
339 class _Function_handler<void(_ArgTypes...), _Member _Class::*>
340 : public _Function_base::_Base_manager<
341 _Simple_type_wrapper< _Member _Class::* > >
342 {
343 typedef _Member _Class::* _Functor;
344 typedef _Simple_type_wrapper<_Functor> _Wrapper;
345 typedef _Function_base::_Base_manager<_Wrapper> _Base;
346
347 public:
348 static bool
349 _M_manager(_Any_data& __dest, const _Any_data& __source,
350 _Manager_operation __op)
351 {
352 switch (__op)
353 {
354#if __cpp_rtti199711
355 case __get_type_info:
356 __dest._M_access<const type_info*>() = &typeid(_Functor);
357 break;
358#endif
359 case __get_functor_ptr:
360 __dest._M_access<_Functor*>() =
361 &_Base::_M_get_pointer(__source)->__value;
362 break;
363
364 default:
365 _Base::_M_manager(__dest, __source, __op);
366 }
367 return false;
368 }
369
370 static void
371 _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
372 {
373 std::__invoke(_Base::_M_get_pointer(__functor)->__value,
374 std::forward<_ArgTypes>(__args)...);
375 }
376 };
377
378 template<typename _From, typename _To>
379 using __check_func_return_type
380 = __or_<is_void<_To>, is_same<_From, _To>, is_convertible<_From, _To>>;
381
382 /**
383 * @brief Primary class template for std::function.
384 * @ingroup functors
385 *
386 * Polymorphic function wrapper.
387 */
388 template<typename _Res, typename... _ArgTypes>
389 class function<_Res(_ArgTypes...)>
390 : public _Maybe_unary_or_binary_function<_Res, _ArgTypes...>,
391 private _Function_base
392 {
393 template<typename _Func,
394 typename _Res2 = typename result_of<_Func&(_ArgTypes...)>::type>
395 struct _Callable : __check_func_return_type<_Res2, _Res> { };
396
397 // Used so the return type convertibility checks aren't done when
398 // performing overload resolution for copy construction/assignment.
399 template<typename _Tp>
400 struct _Callable<function, _Tp> : false_type { };
401
402 template<typename _Cond, typename _Tp>
403 using _Requires = typename enable_if<_Cond::value, _Tp>::type;
404
405 public:
406 typedef _Res result_type;
407
408 // [3.7.2.1] construct/copy/destroy
409
410 /**
411 * @brief Default construct creates an empty function call wrapper.
412 * @post @c !(bool)*this
413 */
414 function() noexcept
415 : _Function_base() { }
416
417 /**
418 * @brief Creates an empty function call wrapper.
419 * @post @c !(bool)*this
420 */
421 function(nullptr_t) noexcept
422 : _Function_base() { }
423
424 /**
425 * @brief %Function copy constructor.
426 * @param __x A %function object with identical call signature.
427 * @post @c bool(*this) == bool(__x)
428 *
429 * The newly-created %function contains a copy of the target of @a
430 * __x (if it has one).
431 */
432 function(const function& __x);
433
434 /**
435 * @brief %Function move constructor.
436 * @param __x A %function object rvalue with identical call signature.
437 *
438 * The newly-created %function contains the target of @a __x
439 * (if it has one).
440 */
441 function(function&& __x) noexcept : _Function_base()
442 {
443 __x.swap(*this);
444 }
445
446 /**
447 * @brief Builds a %function that targets a copy of the incoming
448 * function object.
449 * @param __f A %function object that is callable with parameters of
450 * type @c T1, @c T2, ..., @c TN and returns a value convertible
451 * to @c Res.
452 *
453 * The newly-created %function object will target a copy of
454 * @a __f. If @a __f is @c reference_wrapper<F>, then this function
455 * object will contain a reference to the function object @c
456 * __f.get(). If @a __f is a NULL function pointer or NULL
457 * pointer-to-member, the newly-created object will be empty.
458 *
459 * If @a __f is a non-NULL function pointer or an object of type @c
460 * reference_wrapper<F>, this function will not throw.
461 */
462 template<typename _Functor,
463 typename = _Requires<__not_<is_same<_Functor, function>>, void>,
464 typename = _Requires<_Callable<_Functor>, void>>
465 function(_Functor);
466
467 /**
468 * @brief %Function assignment operator.
469 * @param __x A %function with identical call signature.
470 * @post @c (bool)*this == (bool)x
471 * @returns @c *this
472 *
473 * The target of @a __x is copied to @c *this. If @a __x has no
474 * target, then @c *this will be empty.
475 *
476 * If @a __x targets a function pointer or a reference to a function
477 * object, then this operation will not throw an %exception.
478 */
479 function&
480 operator=(const function& __x)
481 {
482 function(__x).swap(*this);
483 return *this;
484 }
485
486 /**
487 * @brief %Function move-assignment operator.
488 * @param __x A %function rvalue with identical call signature.
489 * @returns @c *this
490 *
491 * The target of @a __x is moved to @c *this. If @a __x has no
492 * target, then @c *this will be empty.
493 *
494 * If @a __x targets a function pointer or a reference to a function
495 * object, then this operation will not throw an %exception.
496 */
497 function&
498 operator=(function&& __x) noexcept
499 {
500 function(std::move(__x)).swap(*this);
501 return *this;
502 }
503
504 /**
505 * @brief %Function assignment to zero.
506 * @post @c !(bool)*this
507 * @returns @c *this
508 *
509 * The target of @c *this is deallocated, leaving it empty.
510 */
511 function&
512 operator=(nullptr_t) noexcept
513 {
514 if (_M_manager)
515 {
516 _M_manager(_M_functor, _M_functor, __destroy_functor);
517 _M_manager = nullptr;
518 _M_invoker = nullptr;
519 }
520 return *this;
521 }
522
523 /**
524 * @brief %Function assignment to a new target.
525 * @param __f A %function object that is callable with parameters of
526 * type @c T1, @c T2, ..., @c TN and returns a value convertible
527 * to @c Res.
528 * @return @c *this
529 *
530 * This %function object wrapper will target a copy of @a
531 * __f. If @a __f is @c reference_wrapper<F>, then this function
532 * object will contain a reference to the function object @c
533 * __f.get(). If @a __f is a NULL function pointer or NULL
534 * pointer-to-member, @c this object will be empty.
535 *
536 * If @a __f is a non-NULL function pointer or an object of type @c
537 * reference_wrapper<F>, this function will not throw.
538 */
539 template<typename _Functor>
540 _Requires<_Callable<typename decay<_Functor>::type>, function&>
541 operator=(_Functor&& __f)
542 {
543 function(std::forward<_Functor>(__f)).swap(*this);
544 return *this;
545 }
546
547 /// @overload
548 template<typename _Functor>
549 function&
550 operator=(reference_wrapper<_Functor> __f) noexcept
551 {
552 function(__f).swap(*this);
553 return *this;
554 }
555
556 // [3.7.2.2] function modifiers
557
558 /**
559 * @brief Swap the targets of two %function objects.
560 * @param __x A %function with identical call signature.
561 *
562 * Swap the targets of @c this function object and @a __f. This
563 * function will not throw an %exception.
564 */
565 void swap(function& __x) noexcept
566 {
567 std::swap(_M_functor, __x._M_functor);
568 std::swap(_M_manager, __x._M_manager);
569 std::swap(_M_invoker, __x._M_invoker);
570 }
571
572 // [3.7.2.3] function capacity
573
574 /**
575 * @brief Determine if the %function wrapper has a target.
576 *
577 * @return @c true when this %function object contains a target,
578 * or @c false when it is empty.
579 *
580 * This function will not throw an %exception.
581 */
582 explicit operator bool() const noexcept
583 { return !_M_empty(); }
584
585 // [3.7.2.4] function invocation
586
587 /**
588 * @brief Invokes the function targeted by @c *this.
589 * @returns the result of the target.
590 * @throws bad_function_call when @c !(bool)*this
591 *
592 * The function call operator invokes the target function object
593 * stored by @c this.
594 */
595 _Res operator()(_ArgTypes... __args) const;
596
597#if __cpp_rtti199711
598 // [3.7.2.5] function target access
599 /**
600 * @brief Determine the type of the target of this function object
601 * wrapper.
602 *
603 * @returns the type identifier of the target function object, or
604 * @c typeid(void) if @c !(bool)*this.
605 *
606 * This function will not throw an %exception.
607 */
608 const type_info& target_type() const noexcept;
609
610 /**
611 * @brief Access the stored target function object.
612 *
613 * @return Returns a pointer to the stored target function object,
614 * if @c typeid(_Functor).equals(target_type()); otherwise, a NULL
615 * pointer.
616 *
617 * This function does not throw exceptions.
618 *
619 * @{
620 */
621 template<typename _Functor> _Functor* target() noexcept;
622
623 template<typename _Functor> const _Functor* target() const noexcept;
624 // @}
625#endif
626
627 private:
628 using _Invoker_type = _Res (*)(const _Any_data&, _ArgTypes&&...);
629 _Invoker_type _M_invoker;
630 };
631
632#if __cpp_deduction_guides >= 201606
633 template<typename>
634 struct __function_guide_helper
635 { };
636
637 template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
638 struct __function_guide_helper<
639 _Res (_Tp::*) (_Args...) noexcept(_Nx)
640 >
641 { using type = _Res(_Args...); };
642
643 template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
644 struct __function_guide_helper<
645 _Res (_Tp::*) (_Args...) & noexcept(_Nx)
646 >
647 { using type = _Res(_Args...); };
648
649 template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
650 struct __function_guide_helper<
651 _Res (_Tp::*) (_Args...) const noexcept(_Nx)
652 >
653 { using type = _Res(_Args...); };
654
655 template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
656 struct __function_guide_helper<
657 _Res (_Tp::*) (_Args...) const & noexcept(_Nx)
658 >
659 { using type = _Res(_Args...); };
660
661 template<typename _Res, typename... _ArgTypes>
662 function(_Res(*)(_ArgTypes...)) -> function<_Res(_ArgTypes...)>;
663
664 template<typename _Functor, typename _Signature = typename
665 __function_guide_helper<decltype(&_Functor::operator())>::type>
666 function(_Functor) -> function<_Signature>;
667#endif
668
669 // Out-of-line member definitions.
670 template<typename _Res, typename... _ArgTypes>
671 function<_Res(_ArgTypes...)>::
672 function(const function& __x)
673 : _Function_base()
674 {
675 if (static_cast<bool>(__x))
676 {
677 __x._M_manager(_M_functor, __x._M_functor, __clone_functor);
678 _M_invoker = __x._M_invoker;
679 _M_manager = __x._M_manager;
680 }
681 }
682
683 template<typename _Res, typename... _ArgTypes>
684 template<typename _Functor, typename, typename>
685 function<_Res(_ArgTypes...)>::
686 function(_Functor __f)
687 : _Function_base()
688 {
689 typedef _Function_handler<_Res(_ArgTypes...), _Functor> _My_handler;
690
691 if (_My_handler::_M_not_empty_function(__f))
5
Taking true branch
692 {
693 _My_handler::_M_init_functor(_M_functor, std::move(__f));
6
Calling '_Base_manager::_M_init_functor'
10
Returned allocated memory
694 _M_invoker = &_My_handler::_M_invoke;
695 _M_manager = &_My_handler::_M_manager;
696 }
697 }
698
699 template<typename _Res, typename... _ArgTypes>
700 _Res
701 function<_Res(_ArgTypes...)>::
702 operator()(_ArgTypes... __args) const
703 {
704 if (_M_empty())
705 __throw_bad_function_call();
706 return _M_invoker(_M_functor, std::forward<_ArgTypes>(__args)...);
707 }
708
709#if __cpp_rtti199711
710 template<typename _Res, typename... _ArgTypes>
711 const type_info&
712 function<_Res(_ArgTypes...)>::
713 target_type() const noexcept
714 {
715 if (_M_manager)
716 {
717 _Any_data __typeinfo_result;
718 _M_manager(__typeinfo_result, _M_functor, __get_type_info);
719 return *__typeinfo_result._M_access<const type_info*>();
720 }
721 else
722 return typeid(void);
723 }
724
725 template<typename _Res, typename... _ArgTypes>
726 template<typename _Functor>
727 _Functor*
728 function<_Res(_ArgTypes...)>::
729 target() noexcept
730 {
731 const function* __const_this = this;
732 const _Functor* __func = __const_this->template target<_Functor>();
733 return const_cast<_Functor*>(__func);
734 }
735
736 template<typename _Res, typename... _ArgTypes>
737 template<typename _Functor>
738 const _Functor*
739 function<_Res(_ArgTypes...)>::
740 target() const noexcept
741 {
742 if (typeid(_Functor) == target_type() && _M_manager)
743 {
744 _Any_data __ptr;
745 _M_manager(__ptr, _M_functor, __get_functor_ptr);
746 return __ptr._M_access<const _Functor*>();
747 }
748 else
749 return nullptr;
750 }
751#endif
752
753 // [20.7.15.2.6] null pointer comparisons
754
755 /**
756 * @brief Compares a polymorphic function object wrapper against 0
757 * (the NULL pointer).
758 * @returns @c true if the wrapper has no target, @c false otherwise
759 *
760 * This function will not throw an %exception.
761 */
762 template<typename _Res, typename... _Args>
763 inline bool
764 operator==(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
765 { return !static_cast<bool>(__f); }
766
767 /// @overload
768 template<typename _Res, typename... _Args>
769 inline bool
770 operator==(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
771 { return !static_cast<bool>(__f); }
772
773 /**
774 * @brief Compares a polymorphic function object wrapper against 0
775 * (the NULL pointer).
776 * @returns @c false if the wrapper has no target, @c true otherwise
777 *
778 * This function will not throw an %exception.
779 */
780 template<typename _Res, typename... _Args>
781 inline bool
782 operator!=(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
783 { return static_cast<bool>(__f); }
784
785 /// @overload
786 template<typename _Res, typename... _Args>
787 inline bool
788 operator!=(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
789 { return static_cast<bool>(__f); }
790
791
792 // [20.7.15.2.7] specialized algorithms
793
794 /**
795 * @brief Swap the targets of two polymorphic function object wrappers.
796 *
797 * This function will not throw an %exception.
798 */
799 // _GLIBCXX_RESOLVE_LIB_DEFECTS
800 // 2062. Effect contradictions w/o no-throw guarantee of std::function swaps
801 template<typename _Res, typename... _Args>
802 inline void
803 swap(function<_Res(_Args...)>& __x, function<_Res(_Args...)>& __y) noexcept
804 { __x.swap(__y); }
805
806_GLIBCXX_END_NAMESPACE_VERSION
807} // namespace std
808
809#endif // C++11
810
811#endif // _GLIBCXX_STD_FUNCTION_H