Bug Summary

File:include/llvm/ADT/IntrusiveRefCntPtr.h
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 ClangTidyDiagnosticConsumer.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~svn338205/build-llvm/tools/clang/tools/extra/clang-tidy -I /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy -I /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/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/lib/gcc/x86_64-linux-gnu/8/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-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/tools/clang/tools/extra/clang-tidy -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp

1//===--- tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp ----------=== //
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/// \file This file implements ClangTidyDiagnosticConsumer, ClangTidyContext
11/// and ClangTidyError classes.
12///
13/// This tool uses the Clang Tooling infrastructure, see
14/// http://clang.llvm.org/docs/HowToSetupToolingForLLVM.html
15/// for details on setting it up with LLVM source tree.
16///
17//===----------------------------------------------------------------------===//
18
19#include "ClangTidyDiagnosticConsumer.h"
20#include "ClangTidyOptions.h"
21#include "clang/AST/ASTDiagnostic.h"
22#include "clang/Basic/DiagnosticOptions.h"
23#include "clang/Frontend/DiagnosticRenderer.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SmallString.h"
26#include <tuple>
27#include <vector>
28using namespace clang;
29using namespace tidy;
30
31namespace {
32class ClangTidyDiagnosticRenderer : public DiagnosticRenderer {
33public:
34 ClangTidyDiagnosticRenderer(const LangOptions &LangOpts,
35 DiagnosticOptions *DiagOpts,
36 ClangTidyError &Error)
37 : DiagnosticRenderer(LangOpts, DiagOpts), Error(Error) {}
38
39protected:
40 void emitDiagnosticMessage(FullSourceLoc Loc, PresumedLoc PLoc,
41 DiagnosticsEngine::Level Level, StringRef Message,
42 ArrayRef<CharSourceRange> Ranges,
43 DiagOrStoredDiag Info) override {
44 // Remove check name from the message.
45 // FIXME: Remove this once there's a better way to pass check names than
46 // appending the check name to the message in ClangTidyContext::diag and
47 // using getCustomDiagID.
48 std::string CheckNameInMessage = " [" + Error.DiagnosticName + "]";
49 if (Message.endswith(CheckNameInMessage))
50 Message = Message.substr(0, Message.size() - CheckNameInMessage.size());
51
52 auto TidyMessage =
53 Loc.isValid()
54 ? tooling::DiagnosticMessage(Message, Loc.getManager(), Loc)
55 : tooling::DiagnosticMessage(Message);
56 if (Level == DiagnosticsEngine::Note) {
57 Error.Notes.push_back(TidyMessage);
58 return;
59 }
60 assert(Error.Message.Message.empty() && "Overwriting a diagnostic message")(static_cast <bool> (Error.Message.Message.empty() &&
"Overwriting a diagnostic message") ? void (0) : __assert_fail
("Error.Message.Message.empty() && \"Overwriting a diagnostic message\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 60, __extension__ __PRETTY_FUNCTION__))
;
61 Error.Message = TidyMessage;
62 }
63
64 void emitDiagnosticLoc(FullSourceLoc Loc, PresumedLoc PLoc,
65 DiagnosticsEngine::Level Level,
66 ArrayRef<CharSourceRange> Ranges) override {}
67
68 void emitCodeContext(FullSourceLoc Loc, DiagnosticsEngine::Level Level,
69 SmallVectorImpl<CharSourceRange> &Ranges,
70 ArrayRef<FixItHint> Hints) override {
71 assert(Loc.isValid())(static_cast <bool> (Loc.isValid()) ? void (0) : __assert_fail
("Loc.isValid()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 71, __extension__ __PRETTY_FUNCTION__))
;
72 for (const auto &FixIt : Hints) {
73 CharSourceRange Range = FixIt.RemoveRange;
74 assert(Range.getBegin().isValid() && Range.getEnd().isValid() &&(static_cast <bool> (Range.getBegin().isValid() &&
Range.getEnd().isValid() && "Invalid range in the fix-it hint."
) ? void (0) : __assert_fail ("Range.getBegin().isValid() && Range.getEnd().isValid() && \"Invalid range in the fix-it hint.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 75, __extension__ __PRETTY_FUNCTION__))
75 "Invalid range in the fix-it hint.")(static_cast <bool> (Range.getBegin().isValid() &&
Range.getEnd().isValid() && "Invalid range in the fix-it hint."
) ? void (0) : __assert_fail ("Range.getBegin().isValid() && Range.getEnd().isValid() && \"Invalid range in the fix-it hint.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 75, __extension__ __PRETTY_FUNCTION__))
;
76 assert(Range.getBegin().isFileID() && Range.getEnd().isFileID() &&(static_cast <bool> (Range.getBegin().isFileID() &&
Range.getEnd().isFileID() && "Only file locations supported in fix-it hints."
) ? void (0) : __assert_fail ("Range.getBegin().isFileID() && Range.getEnd().isFileID() && \"Only file locations supported in fix-it hints.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 77, __extension__ __PRETTY_FUNCTION__))
77 "Only file locations supported in fix-it hints.")(static_cast <bool> (Range.getBegin().isFileID() &&
Range.getEnd().isFileID() && "Only file locations supported in fix-it hints."
) ? void (0) : __assert_fail ("Range.getBegin().isFileID() && Range.getEnd().isFileID() && \"Only file locations supported in fix-it hints.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 77, __extension__ __PRETTY_FUNCTION__))
;
78
79 tooling::Replacement Replacement(Loc.getManager(), Range,
80 FixIt.CodeToInsert);
81 llvm::Error Err = Error.Fix[Replacement.getFilePath()].add(Replacement);
82 // FIXME: better error handling (at least, don't let other replacements be
83 // applied).
84 if (Err) {
85 llvm::errs() << "Fix conflicts with existing fix! "
86 << llvm::toString(std::move(Err)) << "\n";
87 assert(false && "Fix conflicts with existing fix!")(static_cast <bool> (false && "Fix conflicts with existing fix!"
) ? void (0) : __assert_fail ("false && \"Fix conflicts with existing fix!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 87, __extension__ __PRETTY_FUNCTION__))
;
88 }
89 }
90 }
91
92 void emitIncludeLocation(FullSourceLoc Loc, PresumedLoc PLoc) override {}
93
94 void emitImportLocation(FullSourceLoc Loc, PresumedLoc PLoc,
95 StringRef ModuleName) override {}
96
97 void emitBuildingModuleLocation(FullSourceLoc Loc, PresumedLoc PLoc,
98 StringRef ModuleName) override {}
99
100 void endDiagnostic(DiagOrStoredDiag D,
101 DiagnosticsEngine::Level Level) override {
102 assert(!Error.Message.Message.empty() && "Message has not been set")(static_cast <bool> (!Error.Message.Message.empty() &&
"Message has not been set") ? void (0) : __assert_fail ("!Error.Message.Message.empty() && \"Message has not been set\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 102, __extension__ __PRETTY_FUNCTION__))
;
103 }
104
105private:
106 ClangTidyError &Error;
107};
108} // end anonymous namespace
109
110ClangTidyError::ClangTidyError(StringRef CheckName,
111 ClangTidyError::Level DiagLevel,
112 StringRef BuildDirectory, bool IsWarningAsError)
113 : tooling::Diagnostic(CheckName, DiagLevel, BuildDirectory),
114 IsWarningAsError(IsWarningAsError) {}
115
116// Returns true if GlobList starts with the negative indicator ('-'), removes it
117// from the GlobList.
118static bool ConsumeNegativeIndicator(StringRef &GlobList) {
119 GlobList = GlobList.trim(" \r\n");
120 if (GlobList.startswith("-")) {
121 GlobList = GlobList.substr(1);
122 return true;
123 }
124 return false;
125}
126// Converts first glob from the comma-separated list of globs to Regex and
127// removes it and the trailing comma from the GlobList.
128static llvm::Regex ConsumeGlob(StringRef &GlobList) {
129 StringRef UntrimmedGlob = GlobList.substr(0, GlobList.find(','));
130 StringRef Glob = UntrimmedGlob.trim(' ');
131 GlobList = GlobList.substr(UntrimmedGlob.size() + 1);
132 SmallString<128> RegexText("^");
133 StringRef MetaChars("()^$|*+?.[]\\{}");
134 for (char C : Glob) {
135 if (C == '*')
136 RegexText.push_back('.');
137 else if (MetaChars.find(C) != StringRef::npos)
138 RegexText.push_back('\\');
139 RegexText.push_back(C);
140 }
141 RegexText.push_back('$');
142 return llvm::Regex(RegexText);
143}
144
145GlobList::GlobList(StringRef Globs)
146 : Positive(!ConsumeNegativeIndicator(Globs)), Regex(ConsumeGlob(Globs)),
147 NextGlob(Globs.empty() ? nullptr : new GlobList(Globs)) {}
148
149bool GlobList::contains(StringRef S, bool Contains) {
150 if (Regex.match(S))
151 Contains = Positive;
152
153 if (NextGlob)
154 Contains = NextGlob->contains(S, Contains);
155 return Contains;
156}
157
158class ClangTidyContext::CachedGlobList {
159public:
160 CachedGlobList(StringRef Globs) : Globs(Globs) {}
161
162 bool contains(StringRef S) {
163 switch (auto &Result = Cache[S]) {
164 case Yes: return true;
165 case No: return false;
166 case None:
167 Result = Globs.contains(S) ? Yes : No;
168 return Result == Yes;
169 }
170 llvm_unreachable("invalid enum")::llvm::llvm_unreachable_internal("invalid enum", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 170)
;
171 }
172
173private:
174 GlobList Globs;
175 enum Tristate { None, Yes, No };
176 llvm::StringMap<Tristate> Cache;
177};
178
179ClangTidyContext::ClangTidyContext(
180 std::unique_ptr<ClangTidyOptionsProvider> OptionsProvider,
181 bool AllowEnablingAnalyzerAlphaCheckers)
182 : DiagEngine(nullptr), OptionsProvider(std::move(OptionsProvider)),
183 Profile(false),
184 AllowEnablingAnalyzerAlphaCheckers(AllowEnablingAnalyzerAlphaCheckers) {
185 // Before the first translation unit we can get errors related to command-line
186 // parsing, use empty string for the file name in this case.
187 setCurrentFile("");
188}
189
190ClangTidyContext::~ClangTidyContext() = default;
191
192DiagnosticBuilder ClangTidyContext::diag(
193 StringRef CheckName, SourceLocation Loc, StringRef Description,
194 DiagnosticIDs::Level Level /* = DiagnosticIDs::Warning*/) {
195 assert(Loc.isValid())(static_cast <bool> (Loc.isValid()) ? void (0) : __assert_fail
("Loc.isValid()", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 195, __extension__ __PRETTY_FUNCTION__))
;
196 unsigned ID = DiagEngine->getDiagnosticIDs()->getCustomDiagID(
197 Level, (Description + " [" + CheckName + "]").str());
198 CheckNamesByDiagnosticID.try_emplace(ID, CheckName);
199 return DiagEngine->Report(Loc, ID);
200}
201
202void ClangTidyContext::setDiagnosticsEngine(DiagnosticsEngine *Engine) {
203 DiagEngine = Engine;
204}
205
206void ClangTidyContext::setSourceManager(SourceManager *SourceMgr) {
207 DiagEngine->setSourceManager(SourceMgr);
208}
209
210void ClangTidyContext::setCurrentFile(StringRef File) {
211 CurrentFile = File;
212 CurrentOptions = getOptionsForFile(CurrentFile);
213 CheckFilter = llvm::make_unique<CachedGlobList>(*getOptions().Checks);
214 WarningAsErrorFilter =
215 llvm::make_unique<CachedGlobList>(*getOptions().WarningsAsErrors);
216}
217
218void ClangTidyContext::setASTContext(ASTContext *Context) {
219 DiagEngine->SetArgToStringFn(&FormatASTNodeDiagnosticArgument, Context);
220 LangOpts = Context->getLangOpts();
221}
222
223const ClangTidyGlobalOptions &ClangTidyContext::getGlobalOptions() const {
224 return OptionsProvider->getGlobalOptions();
225}
226
227const ClangTidyOptions &ClangTidyContext::getOptions() const {
228 return CurrentOptions;
229}
230
231ClangTidyOptions ClangTidyContext::getOptionsForFile(StringRef File) const {
232 // Merge options on top of getDefaults() as a safeguard against options with
233 // unset values.
234 return ClangTidyOptions::getDefaults().mergeWith(
235 OptionsProvider->getOptions(File));
236}
237
238void ClangTidyContext::setEnableProfiling(bool P) { Profile = P; }
239
240void ClangTidyContext::setProfileStoragePrefix(StringRef Prefix) {
241 ProfilePrefix = Prefix;
242}
243
244llvm::Optional<ClangTidyProfiling::StorageParams>
245ClangTidyContext::getProfileStorageParams() const {
246 if (ProfilePrefix.empty())
247 return llvm::None;
248
249 return ClangTidyProfiling::StorageParams(ProfilePrefix, CurrentFile);
250}
251
252bool ClangTidyContext::isCheckEnabled(StringRef CheckName) const {
253 assert(CheckFilter != nullptr)(static_cast <bool> (CheckFilter != nullptr) ? void (0)
: __assert_fail ("CheckFilter != nullptr", "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 253, __extension__ __PRETTY_FUNCTION__))
;
254 return CheckFilter->contains(CheckName);
255}
256
257bool ClangTidyContext::treatAsError(StringRef CheckName) const {
258 assert(WarningAsErrorFilter != nullptr)(static_cast <bool> (WarningAsErrorFilter != nullptr) ?
void (0) : __assert_fail ("WarningAsErrorFilter != nullptr",
"/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 258, __extension__ __PRETTY_FUNCTION__))
;
259 return WarningAsErrorFilter->contains(CheckName);
260}
261
262/// \brief Store a \c ClangTidyError.
263void ClangTidyContext::storeError(const ClangTidyError &Error) {
264 Errors.push_back(Error);
265}
266
267StringRef ClangTidyContext::getCheckName(unsigned DiagnosticID) const {
268 llvm::DenseMap<unsigned, std::string>::const_iterator I =
269 CheckNamesByDiagnosticID.find(DiagnosticID);
270 if (I != CheckNamesByDiagnosticID.end())
271 return I->second;
272 return "";
273}
274
275ClangTidyDiagnosticConsumer::ClangTidyDiagnosticConsumer(
276 ClangTidyContext &Ctx, bool RemoveIncompatibleErrors)
277 : Context(Ctx), RemoveIncompatibleErrors(RemoveIncompatibleErrors),
278 LastErrorRelatesToUserCode(false), LastErrorPassesLineFilter(false),
279 LastErrorWasIgnored(false) {
280 IntrusiveRefCntPtr<DiagnosticOptions> DiagOpts = new DiagnosticOptions();
281 Diags = llvm::make_unique<DiagnosticsEngine>(
2
Calling 'make_unique<clang::DiagnosticsEngine, llvm::IntrusiveRefCntPtr<clang::DiagnosticIDs>, clang::DiagnosticOptions *, clang::tidy::ClangTidyDiagnosticConsumer *, bool>'
282 IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs), &*DiagOpts, this,
1
Memory is allocated
283 /*ShouldOwnClient=*/false);
284 Context.setDiagnosticsEngine(Diags.get());
285}
286
287void ClangTidyDiagnosticConsumer::finalizeLastError() {
288 if (!Errors.empty()) {
289 ClangTidyError &Error = Errors.back();
290 if (!Context.isCheckEnabled(Error.DiagnosticName) &&
291 Error.DiagLevel != ClangTidyError::Error) {
292 ++Context.Stats.ErrorsIgnoredCheckFilter;
293 Errors.pop_back();
294 } else if (!LastErrorRelatesToUserCode) {
295 ++Context.Stats.ErrorsIgnoredNonUserCode;
296 Errors.pop_back();
297 } else if (!LastErrorPassesLineFilter) {
298 ++Context.Stats.ErrorsIgnoredLineFilter;
299 Errors.pop_back();
300 } else {
301 ++Context.Stats.ErrorsDisplayed;
302 }
303 }
304 LastErrorRelatesToUserCode = false;
305 LastErrorPassesLineFilter = false;
306}
307
308static bool IsNOLINTFound(StringRef NolintDirectiveText, StringRef Line,
309 unsigned DiagID, const ClangTidyContext &Context) {
310 const size_t NolintIndex = Line.find(NolintDirectiveText);
311 if (NolintIndex == StringRef::npos)
312 return false;
313
314 size_t BracketIndex = NolintIndex + NolintDirectiveText.size();
315 // Check if the specific checks are specified in brackets.
316 if (BracketIndex < Line.size() && Line[BracketIndex] == '(') {
317 ++BracketIndex;
318 const size_t BracketEndIndex = Line.find(')', BracketIndex);
319 if (BracketEndIndex != StringRef::npos) {
320 StringRef ChecksStr =
321 Line.substr(BracketIndex, BracketEndIndex - BracketIndex);
322 // Allow disabling all the checks with "*".
323 if (ChecksStr != "*") {
324 StringRef CheckName = Context.getCheckName(DiagID);
325 // Allow specifying a few check names, delimited with comma.
326 SmallVector<StringRef, 1> Checks;
327 ChecksStr.split(Checks, ',', -1, false);
328 llvm::transform(Checks, Checks.begin(),
329 [](StringRef S) { return S.trim(); });
330 return llvm::find(Checks, CheckName) != Checks.end();
331 }
332 }
333 }
334 return true;
335}
336
337static bool LineIsMarkedWithNOLINT(SourceManager &SM, SourceLocation Loc,
338 unsigned DiagID,
339 const ClangTidyContext &Context) {
340 bool Invalid;
341 const char *CharacterData = SM.getCharacterData(Loc, &Invalid);
342 if (Invalid)
343 return false;
344
345 // Check if there's a NOLINT on this line.
346 const char *P = CharacterData;
347 while (*P != '\0' && *P != '\r' && *P != '\n')
348 ++P;
349 StringRef RestOfLine(CharacterData, P - CharacterData + 1);
350 if (IsNOLINTFound("NOLINT", RestOfLine, DiagID, Context))
351 return true;
352
353 // Check if there's a NOLINTNEXTLINE on the previous line.
354 const char *BufBegin =
355 SM.getCharacterData(SM.getLocForStartOfFile(SM.getFileID(Loc)), &Invalid);
356 if (Invalid || P == BufBegin)
357 return false;
358
359 // Scan backwards over the current line.
360 P = CharacterData;
361 while (P != BufBegin && *P != '\n')
362 --P;
363
364 // If we reached the begin of the file there is no line before it.
365 if (P == BufBegin)
366 return false;
367
368 // Skip over the newline.
369 --P;
370 const char *LineEnd = P;
371
372 // Now we're on the previous line. Skip to the beginning of it.
373 while (P != BufBegin && *P != '\n')
374 --P;
375
376 RestOfLine = StringRef(P, LineEnd - P + 1);
377 if (IsNOLINTFound("NOLINTNEXTLINE", RestOfLine, DiagID, Context))
378 return true;
379
380 return false;
381}
382
383static bool LineIsMarkedWithNOLINTinMacro(SourceManager &SM, SourceLocation Loc,
384 unsigned DiagID,
385 const ClangTidyContext &Context) {
386 while (true) {
387 if (LineIsMarkedWithNOLINT(SM, Loc, DiagID, Context))
388 return true;
389 if (!Loc.isMacroID())
390 return false;
391 Loc = SM.getImmediateExpansionRange(Loc).getBegin();
392 }
393 return false;
394}
395
396void ClangTidyDiagnosticConsumer::HandleDiagnostic(
397 DiagnosticsEngine::Level DiagLevel, const Diagnostic &Info) {
398 if (LastErrorWasIgnored && DiagLevel == DiagnosticsEngine::Note)
399 return;
400
401 if (Info.getLocation().isValid() && DiagLevel != DiagnosticsEngine::Error &&
402 DiagLevel != DiagnosticsEngine::Fatal &&
403 LineIsMarkedWithNOLINTinMacro(Diags->getSourceManager(),
404 Info.getLocation(), Info.getID(),
405 Context)) {
406 ++Context.Stats.ErrorsIgnoredNOLINT;
407 // Ignored a warning, should ignore related notes as well
408 LastErrorWasIgnored = true;
409 return;
410 }
411
412 LastErrorWasIgnored = false;
413 // Count warnings/errors.
414 DiagnosticConsumer::HandleDiagnostic(DiagLevel, Info);
415
416 if (DiagLevel == DiagnosticsEngine::Note) {
417 assert(!Errors.empty() &&(static_cast <bool> (!Errors.empty() && "A diagnostic note can only be appended to a message."
) ? void (0) : __assert_fail ("!Errors.empty() && \"A diagnostic note can only be appended to a message.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 418, __extension__ __PRETTY_FUNCTION__))
418 "A diagnostic note can only be appended to a message.")(static_cast <bool> (!Errors.empty() && "A diagnostic note can only be appended to a message."
) ? void (0) : __assert_fail ("!Errors.empty() && \"A diagnostic note can only be appended to a message.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 418, __extension__ __PRETTY_FUNCTION__))
;
419 } else {
420 finalizeLastError();
421 StringRef WarningOption =
422 Context.DiagEngine->getDiagnosticIDs()->getWarningOptionForDiag(
423 Info.getID());
424 std::string CheckName = !WarningOption.empty()
425 ? ("clang-diagnostic-" + WarningOption).str()
426 : Context.getCheckName(Info.getID()).str();
427
428 if (CheckName.empty()) {
429 // This is a compiler diagnostic without a warning option. Assign check
430 // name based on its level.
431 switch (DiagLevel) {
432 case DiagnosticsEngine::Error:
433 case DiagnosticsEngine::Fatal:
434 CheckName = "clang-diagnostic-error";
435 break;
436 case DiagnosticsEngine::Warning:
437 CheckName = "clang-diagnostic-warning";
438 break;
439 default:
440 CheckName = "clang-diagnostic-unknown";
441 break;
442 }
443 }
444
445 ClangTidyError::Level Level = ClangTidyError::Warning;
446 if (DiagLevel == DiagnosticsEngine::Error ||
447 DiagLevel == DiagnosticsEngine::Fatal) {
448 // Force reporting of Clang errors regardless of filters and non-user
449 // code.
450 Level = ClangTidyError::Error;
451 LastErrorRelatesToUserCode = true;
452 LastErrorPassesLineFilter = true;
453 }
454 bool IsWarningAsError = DiagLevel == DiagnosticsEngine::Warning &&
455 Context.treatAsError(CheckName);
456 Errors.emplace_back(CheckName, Level, Context.getCurrentBuildDirectory(),
457 IsWarningAsError);
458 }
459
460 ClangTidyDiagnosticRenderer Converter(
461 Context.getLangOpts(), &Context.DiagEngine->getDiagnosticOptions(),
462 Errors.back());
463 SmallString<100> Message;
464 Info.FormatDiagnostic(Message);
465 FullSourceLoc Loc =
466 (Info.getLocation().isInvalid())
467 ? FullSourceLoc()
468 : FullSourceLoc(Info.getLocation(), Info.getSourceManager());
469 Converter.emitDiagnostic(Loc, DiagLevel, Message, Info.getRanges(),
470 Info.getFixItHints());
471
472 checkFilters(Info.getLocation());
473}
474
475bool ClangTidyDiagnosticConsumer::passesLineFilter(StringRef FileName,
476 unsigned LineNumber) const {
477 if (Context.getGlobalOptions().LineFilter.empty())
478 return true;
479 for (const FileFilter &Filter : Context.getGlobalOptions().LineFilter) {
480 if (FileName.endswith(Filter.Name)) {
481 if (Filter.LineRanges.empty())
482 return true;
483 for (const FileFilter::LineRange &Range : Filter.LineRanges) {
484 if (Range.first <= LineNumber && LineNumber <= Range.second)
485 return true;
486 }
487 return false;
488 }
489 }
490 return false;
491}
492
493void ClangTidyDiagnosticConsumer::checkFilters(SourceLocation Location) {
494 // Invalid location may mean a diagnostic in a command line, don't skip these.
495 if (!Location.isValid()) {
496 LastErrorRelatesToUserCode = true;
497 LastErrorPassesLineFilter = true;
498 return;
499 }
500
501 const SourceManager &Sources = Diags->getSourceManager();
502 if (!*Context.getOptions().SystemHeaders &&
503 Sources.isInSystemHeader(Location))
504 return;
505
506 // FIXME: We start with a conservative approach here, but the actual type of
507 // location needed depends on the check (in particular, where this check wants
508 // to apply fixes).
509 FileID FID = Sources.getDecomposedExpansionLoc(Location).first;
510 const FileEntry *File = Sources.getFileEntryForID(FID);
511
512 // -DMACRO definitions on the command line have locations in a virtual buffer
513 // that doesn't have a FileEntry. Don't skip these as well.
514 if (!File) {
515 LastErrorRelatesToUserCode = true;
516 LastErrorPassesLineFilter = true;
517 return;
518 }
519
520 StringRef FileName(File->getName());
521 LastErrorRelatesToUserCode = LastErrorRelatesToUserCode ||
522 Sources.isInMainFile(Location) ||
523 getHeaderFilter()->match(FileName);
524
525 unsigned LineNumber = Sources.getExpansionLineNumber(Location);
526 LastErrorPassesLineFilter =
527 LastErrorPassesLineFilter || passesLineFilter(FileName, LineNumber);
528}
529
530llvm::Regex *ClangTidyDiagnosticConsumer::getHeaderFilter() {
531 if (!HeaderFilter)
532 HeaderFilter =
533 llvm::make_unique<llvm::Regex>(*Context.getOptions().HeaderFilterRegex);
534 return HeaderFilter.get();
535}
536
537void ClangTidyDiagnosticConsumer::removeIncompatibleErrors(
538 SmallVectorImpl<ClangTidyError> &Errors) const {
539 // Each error is modelled as the set of intervals in which it applies
540 // replacements. To detect overlapping replacements, we use a sweep line
541 // algorithm over these sets of intervals.
542 // An event here consists of the opening or closing of an interval. During the
543 // process, we maintain a counter with the amount of open intervals. If we
544 // find an endpoint of an interval and this counter is different from 0, it
545 // means that this interval overlaps with another one, so we set it as
546 // inapplicable.
547 struct Event {
548 // An event can be either the begin or the end of an interval.
549 enum EventType {
550 ET_Begin = 1,
551 ET_End = -1,
552 };
553
554 Event(unsigned Begin, unsigned End, EventType Type, unsigned ErrorId,
555 unsigned ErrorSize)
556 : Type(Type), ErrorId(ErrorId) {
557 // The events are going to be sorted by their position. In case of draw:
558 //
559 // * If an interval ends at the same position at which other interval
560 // begins, this is not an overlapping, so we want to remove the ending
561 // interval before adding the starting one: end events have higher
562 // priority than begin events.
563 //
564 // * If we have several begin points at the same position, we will mark as
565 // inapplicable the ones that we process later, so the first one has to
566 // be the one with the latest end point, because this one will contain
567 // all the other intervals. For the same reason, if we have several end
568 // points in the same position, the last one has to be the one with the
569 // earliest begin point. In both cases, we sort non-increasingly by the
570 // position of the complementary.
571 //
572 // * In case of two equal intervals, the one whose error is bigger can
573 // potentially contain the other one, so we want to process its begin
574 // points before and its end points later.
575 //
576 // * Finally, if we have two equal intervals whose errors have the same
577 // size, none of them will be strictly contained inside the other.
578 // Sorting by ErrorId will guarantee that the begin point of the first
579 // one will be processed before, disallowing the second one, and the
580 // end point of the first one will also be processed before,
581 // disallowing the first one.
582 if (Type == ET_Begin)
583 Priority = std::make_tuple(Begin, Type, -End, -ErrorSize, ErrorId);
584 else
585 Priority = std::make_tuple(End, Type, -Begin, ErrorSize, ErrorId);
586 }
587
588 bool operator<(const Event &Other) const {
589 return Priority < Other.Priority;
590 }
591
592 // Determines if this event is the begin or the end of an interval.
593 EventType Type;
594 // The index of the error to which the interval that generated this event
595 // belongs.
596 unsigned ErrorId;
597 // The events will be sorted based on this field.
598 std::tuple<unsigned, EventType, int, int, unsigned> Priority;
599 };
600
601 // Compute error sizes.
602 std::vector<int> Sizes;
603 for (const auto &Error : Errors) {
604 int Size = 0;
605 for (const auto &FileAndReplaces : Error.Fix) {
606 for (const auto &Replace : FileAndReplaces.second)
607 Size += Replace.getLength();
608 }
609 Sizes.push_back(Size);
610 }
611
612 // Build events from error intervals.
613 std::map<std::string, std::vector<Event>> FileEvents;
614 for (unsigned I = 0; I < Errors.size(); ++I) {
615 for (const auto &FileAndReplace : Errors[I].Fix) {
616 for (const auto &Replace : FileAndReplace.second) {
617 unsigned Begin = Replace.getOffset();
618 unsigned End = Begin + Replace.getLength();
619 const std::string &FilePath = Replace.getFilePath();
620 // FIXME: Handle empty intervals, such as those from insertions.
621 if (Begin == End)
622 continue;
623 auto &Events = FileEvents[FilePath];
624 Events.emplace_back(Begin, End, Event::ET_Begin, I, Sizes[I]);
625 Events.emplace_back(Begin, End, Event::ET_End, I, Sizes[I]);
626 }
627 }
628 }
629
630 std::vector<bool> Apply(Errors.size(), true);
631 for (auto &FileAndEvents : FileEvents) {
632 std::vector<Event> &Events = FileAndEvents.second;
633 // Sweep.
634 std::sort(Events.begin(), Events.end());
635 int OpenIntervals = 0;
636 for (const auto &Event : Events) {
637 if (Event.Type == Event::ET_End)
638 --OpenIntervals;
639 // This has to be checked after removing the interval from the count if it
640 // is an end event, or before adding it if it is a begin event.
641 if (OpenIntervals != 0)
642 Apply[Event.ErrorId] = false;
643 if (Event.Type == Event::ET_Begin)
644 ++OpenIntervals;
645 }
646 assert(OpenIntervals == 0 && "Amount of begin/end points doesn't match")(static_cast <bool> (OpenIntervals == 0 && "Amount of begin/end points doesn't match"
) ? void (0) : __assert_fail ("OpenIntervals == 0 && \"Amount of begin/end points doesn't match\""
, "/build/llvm-toolchain-snapshot-7~svn338205/tools/clang/tools/extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp"
, 646, __extension__ __PRETTY_FUNCTION__))
;
647 }
648
649 for (unsigned I = 0; I < Errors.size(); ++I) {
650 if (!Apply[I]) {
651 Errors[I].Fix.clear();
652 Errors[I].Notes.emplace_back(
653 "this fix will not be applied because it overlaps with another fix");
654 }
655 }
656}
657
658namespace {
659struct LessClangTidyError {
660 bool operator()(const ClangTidyError &LHS, const ClangTidyError &RHS) const {
661 const tooling::DiagnosticMessage &M1 = LHS.Message;
662 const tooling::DiagnosticMessage &M2 = RHS.Message;
663
664 return std::tie(M1.FilePath, M1.FileOffset, M1.Message) <
665 std::tie(M2.FilePath, M2.FileOffset, M2.Message);
666 }
667};
668struct EqualClangTidyError {
669 bool operator()(const ClangTidyError &LHS, const ClangTidyError &RHS) const {
670 LessClangTidyError Less;
671 return !Less(LHS, RHS) && !Less(RHS, LHS);
672 }
673};
674} // end anonymous namespace
675
676// Flushes the internal diagnostics buffer to the ClangTidyContext.
677void ClangTidyDiagnosticConsumer::finish() {
678 finalizeLastError();
679
680 std::sort(Errors.begin(), Errors.end(), LessClangTidyError());
681 Errors.erase(std::unique(Errors.begin(), Errors.end(), EqualClangTidyError()),
682 Errors.end());
683
684 if (RemoveIncompatibleErrors)
685 removeIncompatibleErrors(Errors);
686
687 for (const ClangTidyError &Error : Errors)
688 Context.storeError(Error);
689 Errors.clear();
690}

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

/build/llvm-toolchain-snapshot-7~svn338205/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~svn338205/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~svn338205/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(); }
4
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