Bug Summary

File:tools/clang/tools/clang-import-test/clang-import-test.cpp
Warning:line 157, column 38
Potential leak of memory pointed to by field 'Obj'

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 clang-import-test.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/tools/clang-import-test -I /build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test -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/tools/clang-import-test -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/tools/clang-import-test/clang-import-test.cpp

/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test/clang-import-test.cpp

1//===-- import-test.cpp - ASTImporter/ExternalASTSource testbed -----------===//
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#include "clang/AST/ASTContext.h"
11#include "clang/AST/ASTImporter.h"
12#include "clang/AST/DeclObjC.h"
13#include "clang/AST/ExternalASTMerger.h"
14#include "clang/Basic/Builtins.h"
15#include "clang/Basic/IdentifierTable.h"
16#include "clang/Basic/SourceLocation.h"
17#include "clang/Basic/TargetInfo.h"
18#include "clang/Basic/TargetOptions.h"
19#include "clang/CodeGen/ModuleBuilder.h"
20#include "clang/Driver/Types.h"
21#include "clang/Frontend/ASTConsumers.h"
22#include "clang/Frontend/CompilerInstance.h"
23#include "clang/Frontend/MultiplexConsumer.h"
24#include "clang/Frontend/TextDiagnosticBuffer.h"
25#include "clang/Lex/Lexer.h"
26#include "clang/Lex/Preprocessor.h"
27#include "clang/Parse/ParseAST.h"
28
29#include "llvm/IR/LLVMContext.h"
30#include "llvm/IR/Module.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Error.h"
33#include "llvm/Support/Host.h"
34#include "llvm/Support/Signals.h"
35
36#include <memory>
37#include <string>
38
39using namespace clang;
40
41static llvm::cl::opt<std::string> Expression(
42 "expression", llvm::cl::Required,
43 llvm::cl::desc("Path to a file containing the expression to parse"));
44
45static llvm::cl::list<std::string>
46 Imports("import", llvm::cl::ZeroOrMore,
47 llvm::cl::desc("Path to a file containing declarations to import"));
48
49static llvm::cl::opt<bool>
50 Direct("direct", llvm::cl::Optional,
51 llvm::cl::desc("Use the parsed declarations without indirection"));
52
53static llvm::cl::opt<bool> UseOrigins(
54 "use-origins", llvm::cl::Optional,
55 llvm::cl::desc(
56 "Use DeclContext origin information for more accurate lookups"));
57
58static llvm::cl::list<std::string>
59 ClangArgs("Xcc", llvm::cl::ZeroOrMore,
60 llvm::cl::desc("Argument to pass to the CompilerInvocation"),
61 llvm::cl::CommaSeparated);
62
63static llvm::cl::opt<std::string>
64 Input("x", llvm::cl::Optional,
65 llvm::cl::desc("The language to parse (default: c++)"),
66 llvm::cl::init("c++"));
67
68static llvm::cl::opt<bool> DumpAST("dump-ast", llvm::cl::init(false),
69 llvm::cl::desc("Dump combined AST"));
70
71static llvm::cl::opt<bool> DumpIR("dump-ir", llvm::cl::init(false),
72 llvm::cl::desc("Dump IR from final parse"));
73
74namespace init_convenience {
75class TestDiagnosticConsumer : public DiagnosticConsumer {
76private:
77 std::unique_ptr<TextDiagnosticBuffer> Passthrough;
78 const LangOptions *LangOpts = nullptr;
79
80public:
81 TestDiagnosticConsumer()
82 : Passthrough(llvm::make_unique<TextDiagnosticBuffer>()) {}
83
84 virtual void BeginSourceFile(const LangOptions &LangOpts,
85 const Preprocessor *PP = nullptr) override {
86 this->LangOpts = &LangOpts;
87 return Passthrough->BeginSourceFile(LangOpts, PP);
88 }
89
90 virtual void EndSourceFile() override {
91 this->LangOpts = nullptr;
92 Passthrough->EndSourceFile();
93 }
94
95 virtual bool IncludeInDiagnosticCounts() const override {
96 return Passthrough->IncludeInDiagnosticCounts();
97 }
98
99private:
100 static void PrintSourceForLocation(const SourceLocation &Loc,
101 SourceManager &SM) {
102 const char *LocData = SM.getCharacterData(Loc, /*Invalid=*/nullptr);
103 unsigned LocColumn =
104 SM.getSpellingColumnNumber(Loc, /*Invalid=*/nullptr) - 1;
105 FileID FID = SM.getFileID(Loc);
106 llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, Loc, /*Invalid=*/nullptr);
107
108 assert(LocData >= Buffer->getBufferStart() &&(static_cast <bool> (LocData >= Buffer->getBufferStart
() && LocData < Buffer->getBufferEnd()) ? void (
0) : __assert_fail ("LocData >= Buffer->getBufferStart() && LocData < Buffer->getBufferEnd()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test/clang-import-test.cpp"
, 109, __extension__ __PRETTY_FUNCTION__))
109 LocData < Buffer->getBufferEnd())(static_cast <bool> (LocData >= Buffer->getBufferStart
() && LocData < Buffer->getBufferEnd()) ? void (
0) : __assert_fail ("LocData >= Buffer->getBufferStart() && LocData < Buffer->getBufferEnd()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test/clang-import-test.cpp"
, 109, __extension__ __PRETTY_FUNCTION__))
;
110
111 const char *LineBegin = LocData - LocColumn;
112
113 assert(LineBegin >= Buffer->getBufferStart())(static_cast <bool> (LineBegin >= Buffer->getBufferStart
()) ? void (0) : __assert_fail ("LineBegin >= Buffer->getBufferStart()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test/clang-import-test.cpp"
, 113, __extension__ __PRETTY_FUNCTION__))
;
114
115 const char *LineEnd = nullptr;
116
117 for (LineEnd = LineBegin; *LineEnd != '\n' && *LineEnd != '\r' &&
118 LineEnd < Buffer->getBufferEnd();
119 ++LineEnd)
120 ;
121
122 llvm::StringRef LineString(LineBegin, LineEnd - LineBegin);
123
124 llvm::errs() << LineString << '\n';
125 llvm::errs().indent(LocColumn);
126 llvm::errs() << '^';
127 llvm::errs() << '\n';
128 }
129
130 virtual void HandleDiagnostic(DiagnosticsEngine::Level DiagLevel,
131 const Diagnostic &Info) override {
132 if (Info.hasSourceManager() && LangOpts) {
133 SourceManager &SM = Info.getSourceManager();
134
135 if (Info.getLocation().isValid()) {
136 Info.getLocation().print(llvm::errs(), SM);
137 llvm::errs() << ": ";
138 }
139
140 SmallString<16> DiagText;
141 Info.FormatDiagnostic(DiagText);
142 llvm::errs() << DiagText << '\n';
143
144 if (Info.getLocation().isValid()) {
145 PrintSourceForLocation(Info.getLocation(), SM);
146 }
147
148 for (const CharSourceRange &Range : Info.getRanges()) {
149 bool Invalid = true;
150 StringRef Ref = Lexer::getSourceText(Range, SM, *LangOpts, &Invalid);
151 if (!Invalid) {
152 llvm::errs() << Ref << '\n';
153 }
154 }
155 }
156 DiagnosticConsumer::HandleDiagnostic(DiagLevel, Info);
157 }
158};
159
160std::unique_ptr<CompilerInstance> BuildCompilerInstance() {
161 auto Ins = llvm::make_unique<CompilerInstance>();
162 auto DC = llvm::make_unique<TestDiagnosticConsumer>();
163 const bool ShouldOwnClient = true;
164 Ins->createDiagnostics(DC.release(), ShouldOwnClient);
165
166 auto Inv = llvm::make_unique<CompilerInvocation>();
167
168 std::vector<const char *> ClangArgv(ClangArgs.size());
169 std::transform(ClangArgs.begin(), ClangArgs.end(), ClangArgv.begin(),
170 [](const std::string &s) -> const char * { return s.data(); });
171 CompilerInvocation::CreateFromArgs(*Inv, ClangArgv.data(),
172 &ClangArgv.data()[ClangArgv.size()],
173 Ins->getDiagnostics());
174
175 {
176 using namespace driver::types;
177 ID Id = lookupTypeForTypeSpecifier(Input.c_str());
178 assert(Id != TY_INVALID)(static_cast <bool> (Id != TY_INVALID) ? void (0) : __assert_fail
("Id != TY_INVALID", "/build/llvm-toolchain-snapshot-7~svn329677/tools/clang/tools/clang-import-test/clang-import-test.cpp"
, 178, __extension__ __PRETTY_FUNCTION__))
;
179 if (isCXX(Id)) {
180 Inv->getLangOpts()->CPlusPlus = true;
181 Inv->getLangOpts()->CPlusPlus11 = true;
182 Inv->getHeaderSearchOpts().UseLibcxx = true;
183 }
184 if (isObjC(Id)) {
185 Inv->getLangOpts()->ObjC1 = 1;
186 Inv->getLangOpts()->ObjC2 = 1;
187 }
188 }
189 Inv->getLangOpts()->Bool = true;
190 Inv->getLangOpts()->WChar = true;
191 Inv->getLangOpts()->Blocks = true;
192 Inv->getLangOpts()->DebuggerSupport = true;
193 Inv->getLangOpts()->SpellChecking = false;
194 Inv->getLangOpts()->ThreadsafeStatics = false;
195 Inv->getLangOpts()->AccessControl = false;
196 Inv->getLangOpts()->DollarIdents = true;
197 Inv->getCodeGenOpts().setDebugInfo(codegenoptions::FullDebugInfo);
198 Inv->getTargetOpts().Triple = llvm::sys::getDefaultTargetTriple();
199
200 Ins->setInvocation(std::move(Inv));
201
202 TargetInfo *TI = TargetInfo::CreateTargetInfo(
203 Ins->getDiagnostics(), Ins->getInvocation().TargetOpts);
204 Ins->setTarget(TI);
205 Ins->getTarget().adjust(Ins->getLangOpts());
206 Ins->createFileManager();
207 Ins->createSourceManager(Ins->getFileManager());
208 Ins->createPreprocessor(TU_Complete);
209
210 return Ins;
211}
212
213std::unique_ptr<ASTContext>
214BuildASTContext(CompilerInstance &CI, SelectorTable &ST, Builtin::Context &BC) {
215 auto AST = llvm::make_unique<ASTContext>(
216 CI.getLangOpts(), CI.getSourceManager(),
217 CI.getPreprocessor().getIdentifierTable(), ST, BC);
218 AST->InitBuiltinTypes(CI.getTarget());
219 return AST;
220}
221
222std::unique_ptr<CodeGenerator> BuildCodeGen(CompilerInstance &CI,
223 llvm::LLVMContext &LLVMCtx) {
224 StringRef ModuleName("$__module");
225 return std::unique_ptr<CodeGenerator>(CreateLLVMCodeGen(
226 CI.getDiagnostics(), ModuleName, CI.getHeaderSearchOpts(),
227 CI.getPreprocessorOpts(), CI.getCodeGenOpts(), LLVMCtx));
228}
229} // namespace init_convenience
230
231namespace {
232
233/// A container for a CompilerInstance (possibly with an ExternalASTMerger
234/// attached to its ASTContext).
235///
236/// Provides an accessor for the DeclContext origins associated with the
237/// ExternalASTMerger (or an empty list of origins if no ExternalASTMerger is
238/// attached).
239///
240/// This is the main unit of parsed source code maintained by clang-import-test.
241struct CIAndOrigins {
242 using OriginMap = clang::ExternalASTMerger::OriginMap;
243 std::unique_ptr<CompilerInstance> CI;
244
245 ASTContext &getASTContext() { return CI->getASTContext(); }
246 FileManager &getFileManager() { return CI->getFileManager(); }
247 const OriginMap &getOriginMap() {
248 static const OriginMap EmptyOriginMap{};
249 if (ExternalASTSource *Source = CI->getASTContext().getExternalSource())
250 return static_cast<ExternalASTMerger *>(Source)->GetOrigins();
251 return EmptyOriginMap;
252 }
253 DiagnosticConsumer &getDiagnosticClient() {
254 return CI->getDiagnosticClient();
255 }
256 CompilerInstance &getCompilerInstance() { return *CI; }
257};
258
259void AddExternalSource(CIAndOrigins &CI,
260 llvm::MutableArrayRef<CIAndOrigins> Imports) {
261 ExternalASTMerger::ImporterTarget Target(
262 {CI.getASTContext(), CI.getFileManager()});
263 llvm::SmallVector<ExternalASTMerger::ImporterSource, 3> Sources;
264 for (CIAndOrigins &Import : Imports)
1
Assuming '__begin1' is equal to '__end1'
265 Sources.push_back({Import.getASTContext(), Import.getFileManager(),
266 Import.getOriginMap()});
267 auto ES = llvm::make_unique<ExternalASTMerger>(Target, Sources);
2
Calling 'make_unique'
4
Returned allocated memory
268 CI.getASTContext().setExternalSource(ES.release());
5
Calling '~IntrusiveRefCntPtr'
269 CI.getASTContext().getTranslationUnitDecl()->setHasExternalVisibleStorage();
270}
271
272CIAndOrigins BuildIndirect(CIAndOrigins &CI) {
273 CIAndOrigins IndirectCI{init_convenience::BuildCompilerInstance()};
274 auto ST = llvm::make_unique<SelectorTable>();
275 auto BC = llvm::make_unique<Builtin::Context>();
276 std::unique_ptr<ASTContext> AST = init_convenience::BuildASTContext(
277 IndirectCI.getCompilerInstance(), *ST, *BC);
278 IndirectCI.getCompilerInstance().setASTContext(AST.release());
279 AddExternalSource(IndirectCI, CI);
280 return IndirectCI;
281}
282
283llvm::Error ParseSource(const std::string &Path, CompilerInstance &CI,
284 ASTConsumer &Consumer) {
285 SourceManager &SM = CI.getSourceManager();
286 const FileEntry *FE = CI.getFileManager().getFile(Path);
287 if (!FE) {
288 return llvm::make_error<llvm::StringError>(
289 llvm::Twine("Couldn't open ", Path), std::error_code());
290 }
291 SM.setMainFileID(SM.createFileID(FE, SourceLocation(), SrcMgr::C_User));
292 ParseAST(CI.getPreprocessor(), &Consumer, CI.getASTContext());
293 return llvm::Error::success();
294}
295
296llvm::Expected<CIAndOrigins> Parse(const std::string &Path,
297 llvm::MutableArrayRef<CIAndOrigins> Imports,
298 bool ShouldDumpAST, bool ShouldDumpIR) {
299 CIAndOrigins CI{init_convenience::BuildCompilerInstance()};
300 auto ST = llvm::make_unique<SelectorTable>();
301 auto BC = llvm::make_unique<Builtin::Context>();
302 std::unique_ptr<ASTContext> AST =
303 init_convenience::BuildASTContext(CI.getCompilerInstance(), *ST, *BC);
304 CI.getCompilerInstance().setASTContext(AST.release());
305 if (Imports.size())
306 AddExternalSource(CI, Imports);
307
308 std::vector<std::unique_ptr<ASTConsumer>> ASTConsumers;
309
310 auto LLVMCtx = llvm::make_unique<llvm::LLVMContext>();
311 ASTConsumers.push_back(
312 init_convenience::BuildCodeGen(CI.getCompilerInstance(), *LLVMCtx));
313 auto &CG = *static_cast<CodeGenerator *>(ASTConsumers.back().get());
314
315 if (ShouldDumpAST)
316 ASTConsumers.push_back(CreateASTDumper(nullptr /*Dump to stdout.*/,
317 "", true, false, false));
318
319 CI.getDiagnosticClient().BeginSourceFile(
320 CI.getCompilerInstance().getLangOpts(),
321 &CI.getCompilerInstance().getPreprocessor());
322 MultiplexConsumer Consumers(std::move(ASTConsumers));
323 Consumers.Initialize(CI.getASTContext());
324
325 if (llvm::Error PE = ParseSource(Path, CI.getCompilerInstance(), Consumers))
326 return std::move(PE);
327 CI.getDiagnosticClient().EndSourceFile();
328 if (ShouldDumpIR)
329 CG.GetModule()->print(llvm::outs(), nullptr);
330 if (CI.getDiagnosticClient().getNumErrors())
331 return llvm::make_error<llvm::StringError>(
332 "Errors occurred while parsing the expression.", std::error_code());
333 return std::move(CI);
334}
335
336void Forget(CIAndOrigins &CI, llvm::MutableArrayRef<CIAndOrigins> Imports) {
337 llvm::SmallVector<ExternalASTMerger::ImporterSource, 3> Sources;
338 for (CIAndOrigins &Import : Imports)
339 Sources.push_back({Import.getASTContext(), Import.getFileManager(),
340 Import.getOriginMap()});
341 ExternalASTSource *Source = CI.CI->getASTContext().getExternalSource();
342 auto *Merger = static_cast<ExternalASTMerger *>(Source);
343 Merger->RemoveSources(Sources);
344}
345
346} // end namespace
347
348int main(int argc, const char **argv) {
349 const bool DisableCrashReporting = true;
350 llvm::sys::PrintStackTraceOnErrorSignal(argv[0], DisableCrashReporting);
351 llvm::cl::ParseCommandLineOptions(argc, argv);
352 std::vector<CIAndOrigins> ImportCIs;
353 for (auto I : Imports) {
354 llvm::Expected<CIAndOrigins> ImportCI = Parse(I, {}, false, false);
355 if (auto E = ImportCI.takeError()) {
356 llvm::errs() << llvm::toString(std::move(E));
357 exit(-1);
358 }
359 ImportCIs.push_back(std::move(*ImportCI));
360 }
361 std::vector<CIAndOrigins> IndirectCIs;
362 if (!Direct || UseOrigins) {
363 for (auto &ImportCI : ImportCIs) {
364 CIAndOrigins IndirectCI = BuildIndirect(ImportCI);
365 IndirectCIs.push_back(std::move(IndirectCI));
366 }
367 }
368 if (UseOrigins)
369 for (auto &ImportCI : ImportCIs)
370 IndirectCIs.push_back(std::move(ImportCI));
371 llvm::Expected<CIAndOrigins> ExpressionCI =
372 Parse(Expression, (Direct && !UseOrigins) ? ImportCIs : IndirectCIs,
373 DumpAST, DumpIR);
374 if (auto E = ExpressionCI.takeError()) {
375 llvm::errs() << llvm::toString(std::move(E));
376 exit(-1);
377 }
378 Forget(*ExpressionCI, (Direct && !UseOrigins) ? ImportCIs : IndirectCIs);
379 return 0;
380}

/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)...));
3
Memory is allocated
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

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

1//==- llvm/ADT/IntrusiveRefCntPtr.h - Smart Refcounting Pointer --*- 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 defines the RefCountedBase, ThreadSafeRefCountedBase, and
11// IntrusiveRefCntPtr classes.
12//
13// IntrusiveRefCntPtr is a smart pointer to an object which maintains a
14// reference count. (ThreadSafe)RefCountedBase is a mixin class that adds a
15// refcount member variable and methods for updating the refcount. An object
16// that inherits from (ThreadSafe)RefCountedBase deletes itself when its
17// refcount hits zero.
18//
19// For example:
20//
21// class MyClass : public RefCountedBase<MyClass> {};
22//
23// void foo() {
24// // Constructing an IntrusiveRefCntPtr increases the pointee's refcount by
25// // 1 (from 0 in this case).
26// IntrusiveRefCntPtr<MyClass> Ptr1(new MyClass());
27//
28// // Copying an IntrusiveRefCntPtr increases the pointee's refcount by 1.
29// IntrusiveRefCntPtr<MyClass> Ptr2(Ptr1);
30//
31// // Constructing an IntrusiveRefCntPtr has no effect on the object's
32// // refcount. After a move, the moved-from pointer is null.
33// IntrusiveRefCntPtr<MyClass> Ptr3(std::move(Ptr1));
34// assert(Ptr1 == nullptr);
35//
36// // Clearing an IntrusiveRefCntPtr decreases the pointee's refcount by 1.
37// Ptr2.reset();
38//
39// // The object deletes itself when we return from the function, because
40// // Ptr3's destructor decrements its refcount to 0.
41// }
42//
43// You can use IntrusiveRefCntPtr with isa<T>(), dyn_cast<T>(), etc.:
44//
45// IntrusiveRefCntPtr<MyClass> Ptr(new MyClass());
46// OtherClass *Other = dyn_cast<OtherClass>(Ptr); // Ptr.get() not required
47//
48// IntrusiveRefCntPtr works with any class that
49//
50// - inherits from (ThreadSafe)RefCountedBase,
51// - has Retain() and Release() methods, or
52// - specializes IntrusiveRefCntPtrInfo.
53//
54//===----------------------------------------------------------------------===//
55
56#ifndef LLVM_ADT_INTRUSIVEREFCNTPTR_H
57#define LLVM_ADT_INTRUSIVEREFCNTPTR_H
58
59#include <atomic>
60#include <cassert>
61#include <cstddef>
62
63namespace llvm {
64
65/// A CRTP mixin class that adds reference counting to a type.
66///
67/// The lifetime of an object which inherits from RefCountedBase is managed by
68/// calls to Release() and Retain(), which increment and decrement the object's
69/// refcount, respectively. When a Release() call decrements the refcount to 0,
70/// the object deletes itself.
71template <class Derived> class RefCountedBase {
72 mutable unsigned RefCount = 0;
73
74public:
75 RefCountedBase() = default;
76 RefCountedBase(const RefCountedBase &) {}
77
78 void Retain() const { ++RefCount; }
79
80 void Release() const {
81 assert(RefCount > 0 && "Reference count is already zero.")(static_cast <bool> (RefCount > 0 && "Reference count is already zero."
) ? void (0) : __assert_fail ("RefCount > 0 && \"Reference count is already zero.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/IntrusiveRefCntPtr.h"
, 81, __extension__ __PRETTY_FUNCTION__))
;
82 if (--RefCount == 0)
83 delete static_cast<const Derived *>(this);
84 }
85};
86
87/// A thread-safe version of \c RefCountedBase.
88template <class Derived> class ThreadSafeRefCountedBase {
89 mutable std::atomic<int> RefCount;
90
91protected:
92 ThreadSafeRefCountedBase() : RefCount(0) {}
93
94public:
95 void Retain() const { RefCount.fetch_add(1, std::memory_order_relaxed); }
96
97 void Release() const {
98 int NewRefCount = RefCount.fetch_sub(1, std::memory_order_acq_rel) - 1;
99 assert(NewRefCount >= 0 && "Reference count was already zero.")(static_cast <bool> (NewRefCount >= 0 && "Reference count was already zero."
) ? void (0) : __assert_fail ("NewRefCount >= 0 && \"Reference count was already zero.\""
, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/IntrusiveRefCntPtr.h"
, 99, __extension__ __PRETTY_FUNCTION__))
;
100 if (NewRefCount == 0)
101 delete static_cast<const Derived *>(this);
102 }
103};
104
105/// Class you can specialize to provide custom retain/release functionality for
106/// a type.
107///
108/// Usually specializing this class is not necessary, as IntrusiveRefCntPtr
109/// works with any type which defines Retain() and Release() functions -- you
110/// can define those functions yourself if RefCountedBase doesn't work for you.
111///
112/// One case when you might want to specialize this type is if you have
113/// - Foo.h defines type Foo and includes Bar.h, and
114/// - Bar.h uses IntrusiveRefCntPtr<Foo> in inline functions.
115///
116/// Because Foo.h includes Bar.h, Bar.h can't include Foo.h in order to pull in
117/// the declaration of Foo. Without the declaration of Foo, normally Bar.h
118/// wouldn't be able to use IntrusiveRefCntPtr<Foo>, which wants to call
119/// T::Retain and T::Release.
120///
121/// To resolve this, Bar.h could include a third header, FooFwd.h, which
122/// forward-declares Foo and specializes IntrusiveRefCntPtrInfo<Foo>. Then
123/// Bar.h could use IntrusiveRefCntPtr<Foo>, although it still couldn't call any
124/// functions on Foo itself, because Foo would be an incomplete type.
125template <typename T> struct IntrusiveRefCntPtrInfo {
126 static void retain(T *obj) { obj->Retain(); }
127 static void release(T *obj) { obj->Release(); }
128};
129
130/// A smart pointer to a reference-counted object that inherits from
131/// RefCountedBase or ThreadSafeRefCountedBase.
132///
133/// This class increments its pointee's reference count when it is created, and
134/// decrements its refcount when it's destroyed (or is changed to point to a
135/// different object).
136template <typename T> class IntrusiveRefCntPtr {
137 T *Obj = nullptr;
138
139public:
140 using element_type = T;
141
142 explicit IntrusiveRefCntPtr() = default;
143 IntrusiveRefCntPtr(T *obj) : Obj(obj) { retain(); }
144 IntrusiveRefCntPtr(const IntrusiveRefCntPtr &S) : Obj(S.Obj) { retain(); }
145 IntrusiveRefCntPtr(IntrusiveRefCntPtr &&S) : Obj(S.Obj) { S.Obj = nullptr; }
146
147 template <class X>
148 IntrusiveRefCntPtr(IntrusiveRefCntPtr<X> &&S) : Obj(S.get()) {
149 S.Obj = nullptr;
150 }
151
152 template <class X>
153 IntrusiveRefCntPtr(const IntrusiveRefCntPtr<X> &S) : Obj(S.get()) {
154 retain();
155 }
156
157 ~IntrusiveRefCntPtr() { release(); }
6
Potential leak of memory pointed to by field 'Obj'
158
159 IntrusiveRefCntPtr &operator=(IntrusiveRefCntPtr S) {
160 swap(S);
161 return *this;
162 }
163
164 T &operator*() const { return *Obj; }
165 T *operator->() const { return Obj; }
166 T *get() const { return Obj; }
167 explicit operator bool() const { return Obj; }
168
169 void swap(IntrusiveRefCntPtr &other) {
170 T *tmp = other.Obj;
171 other.Obj = Obj;
172 Obj = tmp;
173 }
174
175 void reset() {
176 release();
177 Obj = nullptr;
178 }
179
180 void resetWithoutRelease() { Obj = nullptr; }
181
182private:
183 void retain() {
184 if (Obj)
185 IntrusiveRefCntPtrInfo<T>::retain(Obj);
186 }
187
188 void release() {
189 if (Obj)
190 IntrusiveRefCntPtrInfo<T>::release(Obj);
191 }
192
193 template <typename X> friend class IntrusiveRefCntPtr;
194};
195
196template <class T, class U>
197inline bool operator==(const IntrusiveRefCntPtr<T> &A,
198 const IntrusiveRefCntPtr<U> &B) {
199 return A.get() == B.get();
200}
201
202template <class T, class U>
203inline bool operator!=(const IntrusiveRefCntPtr<T> &A,
204 const IntrusiveRefCntPtr<U> &B) {
205 return A.get() != B.get();
206}
207
208template <class T, class U>
209inline bool operator==(const IntrusiveRefCntPtr<T> &A, U *B) {
210 return A.get() == B;
211}
212
213template <class T, class U>
214inline bool operator!=(const IntrusiveRefCntPtr<T> &A, U *B) {
215 return A.get() != B;
216}
217
218template <class T, class U>
219inline bool operator==(T *A, const IntrusiveRefCntPtr<U> &B) {
220 return A == B.get();
221}
222
223template <class T, class U>
224inline bool operator!=(T *A, const IntrusiveRefCntPtr<U> &B) {
225 return A != B.get();
226}
227
228template <class T>
229bool operator==(std::nullptr_t A, const IntrusiveRefCntPtr<T> &B) {
230 return !B;
231}
232
233template <class T>
234bool operator==(const IntrusiveRefCntPtr<T> &A, std::nullptr_t B) {
235 return B == A;
236}
237
238template <class T>
239bool operator!=(std::nullptr_t A, const IntrusiveRefCntPtr<T> &B) {
240 return !(A == B);
241}
242
243template <class T>
244bool operator!=(const IntrusiveRefCntPtr<T> &A, std::nullptr_t B) {
245 return !(A == B);
246}
247
248// Make IntrusiveRefCntPtr work with dyn_cast, isa, and the other idioms from
249// Casting.h.
250template <typename From> struct simplify_type;
251
252template <class T> struct simplify_type<IntrusiveRefCntPtr<T>> {
253 using SimpleType = T *;
254
255 static SimpleType getSimplifiedValue(IntrusiveRefCntPtr<T> &Val) {
256 return Val.get();
257 }
258};
259
260template <class T> struct simplify_type<const IntrusiveRefCntPtr<T>> {
261 using SimpleType = /*const*/ T *;
262
263 static SimpleType getSimplifiedValue(const IntrusiveRefCntPtr<T> &Val) {
264 return Val.get();
265 }
266};
267
268} // end namespace llvm
269
270#endif // LLVM_ADT_INTRUSIVEREFCNTPTR_H