/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h

Bug Summary

File:	include/llvm/Support/Error.h
Warning:	line 201, column 5 Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name dsymutil.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/dsymutil -I /build/llvm-toolchain-snapshot-8~svn345461/tools/dsymutil -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.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-8~svn345461/build-llvm/tools/dsymutil -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/tools/dsymutil/dsymutil.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn345461/tools/dsymutil/dsymutil.cpp

→

1//===- dsymutil.cpp - Debug info dumping utility for llvm -----------------===//
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 program is a utility that aims to be a dropin replacement for Darwin's
11// dsymutil.
12//===----------------------------------------------------------------------===//

14#include "dsymutil.h"
15#include "BinaryHolder.h"
16#include "CFBundle.h"
17#include "DebugMap.h"
18#include "LinkUtils.h"
19#include "MachOUtils.h"
20#include "llvm/ADT/SmallString.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/StringExtras.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/Triple.h"
25#include "llvm/DebugInfo/DIContext.h"
26#include "llvm/DebugInfo/DWARF/DWARFContext.h"
27#include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
28#include "llvm/Object/Binary.h"
29#include "llvm/Object/MachO.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/FileSystem.h"
32#include "llvm/Support/InitLLVM.h"
33#include "llvm/Support/ManagedStatic.h"
34#include "llvm/Support/Path.h"
35#include "llvm/Support/TargetSelect.h"
36#include "llvm/Support/ThreadPool.h"
37#include "llvm/Support/WithColor.h"
38#include "llvm/Support/raw_ostream.h"
39#include "llvm/Support/thread.h"
40#include <algorithm>
41#include <cstdint>
42#include <cstdlib>
43#include <string>
44#include <system_error>

46using namespace llvm;
47using namespace llvm::cl;
48using namespace llvm::dsymutil;
49using namespace object;

51static OptionCategory DsymCategory("Specific Options");
52static opt<bool> Help("h", desc("Alias for -help"), Hidden);
53static opt<bool> Version("v", desc("Alias for -version"), Hidden);

55static list<std::string> InputFiles(Positional, OneOrMore,
                                  desc("<input files>"), cat(DsymCategory));

58static opt<std::string>
  OutputFileOpt("o",
                desc("Specify the output file. default: <input file>.dwarf"),
                value_desc("filename"), cat(DsymCategory));

63static opt<std::string> OsoPrependPath(
  "oso-prepend-path",
  desc("Specify a directory to prepend to the paths of object files."),
  value_desc("path"), cat(DsymCategory));

68static opt<bool> Assembly(
  "S",
  desc("Output textual assembly instead of a binary dSYM companion file."),
  init(false), cat(DsymCategory), cl::Hidden);

73static opt<bool> DumpStab(
  "symtab",
  desc("Dumps the symbol table found in executable or object file(s) and\n"
       "exits."),
  init(false), cat(DsymCategory));
78static alias DumpStabA("s", desc("Alias for --symtab"), aliasopt(DumpStab));

80static opt<bool> FlatOut("flat",
                       desc("Produce a flat dSYM file (not a bundle)."),
                       init(false), cat(DsymCategory));
83static alias FlatOutA("f", desc("Alias for --flat"), aliasopt(FlatOut));

85static opt<bool> Minimize(
  "minimize",
  desc("When used when creating a dSYM file with Apple accelerator tables,\n"
       "this option will suppress the emission of the .debug_inlines, \n"
       ".debug_pubnames, and .debug_pubtypes sections since dsymutil \n"
       "has better equivalents: .apple_names and .apple_types. When used in\n"
       "conjunction with --update option, this option will cause redundant\n"
       "accelerator tables to be removed."),
  init(false), cat(DsymCategory));
94static alias MinimizeA("z", desc("Alias for --minimize"), aliasopt(Minimize));

96static opt<bool> Update(
  "update",
  desc("Updates existing dSYM files to contain the latest accelerator\n"
       "tables and other DWARF optimizations."),
  init(false), cat(DsymCategory));
101static alias UpdateA("u", desc("Alias for --update"), aliasopt(Update));

103static cl::opt<AccelTableKind> AcceleratorTable(
  "accelerator", cl::desc("Output accelerator tables."),
  cl::values(clEnumValN(AccelTableKind::Default, "Default",llvm::cl::OptionEnumValue { "Default", int(AccelTableKind::Default
), "Default for input." }
                        "Default for input.")llvm::cl::OptionEnumValue { "Default", int(AccelTableKind::Default
), "Default for input." },
             clEnumValN(AccelTableKind::Apple, "Apple", "Apple")llvm::cl::OptionEnumValue { "Apple", int(AccelTableKind::Apple
), "Apple" },
             clEnumValN(AccelTableKind::Dwarf, "Dwarf", "DWARF")llvm::cl::OptionEnumValue { "Dwarf", int(AccelTableKind::Dwarf
), "DWARF" }),
  cl::init(AccelTableKind::Default), cat(DsymCategory));

111static opt<unsigned> NumThreads(
  "num-threads",
  desc("Specifies the maximum number (n) of simultaneous threads to use\n"
       "when linking multiple architectures."),
  value_desc("n"), init(0), cat(DsymCategory));
116static alias NumThreadsA("j", desc("Alias for --num-threads"),
                       aliasopt(NumThreads));

119static opt<bool> Verbose("verbose", desc("Verbosity level"), init(false),
                       cat(DsymCategory));

122static opt<bool>
  NoOutput("no-output",
           desc("Do the link in memory, but do not emit the result file."),
           init(false), cat(DsymCategory));

127static opt<bool>
  NoTimestamp("no-swiftmodule-timestamp",
              desc("Don't check timestamp for swiftmodule files."),
              init(false), cat(DsymCategory));

132static list<std::string> ArchFlags(
  "arch",
  desc("Link DWARF debug information only for specified CPU architecture\n"
       "types. This option can be specified multiple times, once for each\n"
       "desired architecture. All CPU architectures will be linked by\n"
       "default."),
  value_desc("arch"), ZeroOrMore, cat(DsymCategory));

140static opt<bool>
  NoODR("no-odr",
        desc("Do not use ODR (One Definition Rule) for type uniquing."),
        init(false), cat(DsymCategory));

145static opt<bool> DumpDebugMap(
  "dump-debug-map",
  desc("Parse and dump the debug map to standard output. Not DWARF link "
       "will take place."),
  init(false), cat(DsymCategory));

151static opt<bool> InputIsYAMLDebugMap(
  "y", desc("Treat the input file is a YAML debug map rather than a binary."),
  init(false), cat(DsymCategory));

155static opt<bool> Verify("verify", desc("Verify the linked DWARF debug info."),
                      cat(DsymCategory));

158static opt<std::string>
  Toolchain("toolchain", desc("Embed toolchain information in dSYM bundle."),
            cat(DsymCategory));

162static opt<bool>
  PaperTrailWarnings("papertrail",
                     desc("Embed warnings in the linked DWARF debug info."),
                     cat(DsymCategory));

167static Error createPlistFile(llvm::StringRef Bin, llvm::StringRef BundleRoot) {
if (NoOutput)
  return Error::success();

// Create plist file to write to.
llvm::SmallString<128> InfoPlist(BundleRoot);
llvm::sys::path::append(InfoPlist, "Contents/Info.plist");
std::error_code EC;
llvm::raw_fd_ostream PL(InfoPlist, EC, llvm::sys::fs::F_Text);
if (EC)
  return make_error<StringError>(
      "cannot create Plist: " + toString(errorCodeToError(EC)), EC);

CFBundleInfo BI = getBundleInfo(Bin);

if (BI.IDStr.empty()) {
  llvm::StringRef BundleID = *llvm::sys::path::rbegin(BundleRoot);
  if (llvm::sys::path::extension(BundleRoot) == ".dSYM")
    BI.IDStr = llvm::sys::path::stem(BundleID);
  else
    BI.IDStr = BundleID;
}

// Print out information to the plist file.
PL << "<?xml version=\"1.0\" encoding=\"UTF-8\"\?>\n"
   << "<!DOCTYPE plist PUBLIC \"-//Apple Computer//DTD PLIST 1.0//EN\" "
   << "\"http://www.apple.com/DTDs/PropertyList-1.0.dtd\">\n"
   << "<plist version=\"1.0\">\n"
   << "\t<dict>\n"
   << "\t\t<key>CFBundleDevelopmentRegion</key>\n"
   << "\t\t<string>English</string>\n"
   << "\t\t<key>CFBundleIdentifier</key>\n"
   << "\t\t<string>com.apple.xcode.dsym." << BI.IDStr << "</string>\n"
   << "\t\t<key>CFBundleInfoDictionaryVersion</key>\n"
   << "\t\t<string>6.0</string>\n"
   << "\t\t<key>CFBundlePackageType</key>\n"
   << "\t\t<string>dSYM</string>\n"
   << "\t\t<key>CFBundleSignature</key>\n"
   << "\t\t<string>\?\?\?\?</string>\n";

if (!BI.OmitShortVersion()) {
  PL << "\t\t<key>CFBundleShortVersionString</key>\n";
  PL << "\t\t<string>";
  printHTMLEscaped(BI.ShortVersionStr, PL);
  PL << "</string>\n";
}

PL << "\t\t<key>CFBundleVersion</key>\n";
PL << "\t\t<string>";
printHTMLEscaped(BI.VersionStr, PL);
PL << "</string>\n";

if (!Toolchain.empty()) {
  PL << "\t\t<key>Toolchain</key>\n";
  PL << "\t\t<string>";
  printHTMLEscaped(Toolchain, PL);
  PL << "</string>\n";
}

PL << "\t</dict>\n"
   << "</plist>\n";

PL.close();
return Error::success();
231}

233static Error createBundleDir(llvm::StringRef BundleBase) {
if (NoOutput)
  return Error::success();

llvm::SmallString<128> Bundle(BundleBase);
llvm::sys::path::append(Bundle, "Contents", "Resources", "DWARF");
if (std::error_code EC =
        create_directories(Bundle.str(), true, llvm::sys::fs::perms::all_all))
  return make_error<StringError>(
      "cannot create bundle: " + toString(errorCodeToError(EC)), EC);

return Error::success();
245}

247static bool verify(llvm::StringRef OutputFile, llvm::StringRef Arch) {
if (OutputFile == "-") {
  WithColor::warning() << "verification skipped for " << Arch
                       << "because writing to stdout.\n";
  return true;
}

Expected<OwningBinary<Binary>> BinOrErr = createBinary(OutputFile);
if (!BinOrErr) {
  WithColor::error() << OutputFile << ": " << toString(BinOrErr.takeError());
  return false;
}

Binary &Binary = *BinOrErr.get().getBinary();
if (auto *Obj = dyn_cast<MachOObjectFile>(&Binary)) {
  raw_ostream &os = Verbose ? errs() : nulls();
  os << "Verifying DWARF for architecture: " << Arch << "\n";
  std::unique_ptr<DWARFContext> DICtx = DWARFContext::create(*Obj);
  DIDumpOptions DumpOpts;
  bool success = DICtx->verify(os, DumpOpts.noImplicitRecursion());
  if (!success)
    WithColor::error() << "verification failed for " << Arch << '\n';
  return success;
}

return false;
273}

275static Expected<std::string> getOutputFileName(llvm::StringRef InputFile) {
// When updating, do in place replacement.
if (OutputFileOpt.empty() && Update)
  return InputFile;

// If a flat dSYM has been requested, things are pretty simple.
if (FlatOut) {
  if (OutputFileOpt.empty()) {
    if (InputFile == "-")
      return "a.out.dwarf";
    return (InputFile + ".dwarf").str();
  }

  return OutputFileOpt;
}

// We need to create/update a dSYM bundle.
// A bundle hierarchy looks like this:
//   <bundle name>.dSYM/
//       Contents/
//          Info.plist
//          Resources/
//             DWARF/
//                <DWARF file(s)>
std::string DwarfFile =
    InputFile == "-" ? llvm::StringRef("a.out") : InputFile;
llvm::SmallString<128> BundleDir(OutputFileOpt);
if (BundleDir.empty())
  BundleDir = DwarfFile + ".dSYM";
if (auto E = createBundleDir(BundleDir))
  return std::move(E);
if (auto E = createPlistFile(DwarfFile, BundleDir))
  return std::move(E);

llvm::sys::path::append(BundleDir, "Contents", "Resources", "DWARF",
                        llvm::sys::path::filename(DwarfFile));
return BundleDir.str();
312}

314/// Parses the command line options into the LinkOptions struct and performs
315/// some sanity checking. Returns an error in case the latter fails.
316static Expected<LinkOptions> getOptions() {
LinkOptions Options;

Options.Verbose = Verbose;
Options.NoOutput = NoOutput;
Options.NoODR = NoODR;
Options.Minimize = Minimize;
Options.Update = Update;
Options.NoTimestamp = NoTimestamp;
Options.PrependPath = OsoPrependPath;
Options.TheAccelTableKind = AcceleratorTable;

if (Assembly)
  Options.FileType = OutputFileType::Assembly;

if (Options.Update && std::find(InputFiles.begin(), InputFiles.end(), "-") !=
                          InputFiles.end()) {
  // FIXME: We cannot use stdin for an update because stdin will be
  // consumed by the BinaryHolder during the debugmap parsing, and
  // then we will want to consume it again in DwarfLinker. If we
  // used a unique BinaryHolder object that could cache multiple
  // binaries this restriction would go away.
  return make_error<StringError>(
      "standard input cannot be used as input for a dSYM update.",
      inconvertibleErrorCode());
}

if (NumThreads == 0)
  Options.Threads = llvm::thread::hardware_concurrency();
if (DumpDebugMap || Verbose)
  Options.Threads = 1;

return Options;
349}

351/// Return a list of input files. This function has logic for dealing with the
352/// special case where we might have dSYM bundles as input. The function
353/// returns an error when the directory structure doesn't match that of a dSYM
354/// bundle.
355static Expected<std::vector<std::string>> getInputs(bool DsymAsInput) {
if (!DsymAsInput)
7
←
Assuming 'DsymAsInput' is not equal to 0→
8
←
Taking false branch→
  return InputFiles;

// If we are updating, we might get dSYM bundles as input.
std::vector<std::string> Inputs;
for (const auto &Input : InputFiles) {
  if (!llvm::sys::fs::is_directory(Input)) {
9
←
Assuming the condition is false→
10
←
Taking false branch→
    Inputs.push_back(Input);
    continue;
  }

  // Make sure that we're dealing with a dSYM bundle.
  SmallString<256> BundlePath(Input);
  sys::path::append(BundlePath, "Contents", "Resources", "DWARF");
  if (!llvm::sys::fs::is_directory(BundlePath))
11
←
Taking true branch→
    return make_error<StringError>(
12
←
Calling 'make_error<llvm::StringError, std::__cxx11::basic_string<char>, std::error_code>'→
        Input + " is a directory, but doesn't look like a dSYM bundle.",
        inconvertibleErrorCode());

  // Create a directory iterator to iterate over all the entries in the
  // bundle.
  std::error_code EC;
  llvm::sys::fs::directory_iterator DirIt(BundlePath, EC);
  llvm::sys::fs::directory_iterator DirEnd;
  if (EC)
    return errorCodeToError(EC);

  // Add each entry to the list of inputs.
  while (DirIt != DirEnd) {
    Inputs.push_back(DirIt->path());
    DirIt.increment(EC);
    if (EC)
      return errorCodeToError(EC);
  }
}
return Inputs;
392}

394int main(int argc, char **argv) {
InitLLVM X(argc, argv);

void *P = (void *)(intptr_t)getOutputFileName;
std::string SDKPath = llvm::sys::fs::getMainExecutable(argv[0], P);
SDKPath = llvm::sys::path::parent_path(SDKPath);

HideUnrelatedOptions({&DsymCategory, &ColorCategory});
llvm::cl::ParseCommandLineOptions(
    argc, argv,
    "manipulate archived DWARF debug symbol files.\n\n"
    "dsymutil links the DWARF debug information found in the object files\n"
    "for the executable <input file> by using debug symbols information\n"
    "contained in its symbol table.\n");

if (Help) {
1
Assuming the condition is false→
2
←
Taking false branch→
  PrintHelpMessage();
  return 0;
}

if (Version) {
3
←
Assuming the condition is false→
4
←
Taking false branch→
  llvm::cl::PrintVersionMessage();
  return 0;
}

auto OptionsOrErr = getOptions();
if (!OptionsOrErr) {
5
←
Taking false branch→
  WithColor::error() << toString(OptionsOrErr.takeError());
  return 1;
}

llvm::InitializeAllTargetInfos();
llvm::InitializeAllTargetMCs();
llvm::InitializeAllTargets();
llvm::InitializeAllAsmPrinters();

auto InputsOrErr = getInputs(OptionsOrErr->Update);
6
←
Calling 'getInputs'→
if (!InputsOrErr) {
  WithColor::error() << toString(InputsOrErr.takeError()) << '\n';
  return 1;
}

if (!FlatOut && OutputFileOpt == "-") {
  WithColor::error() << "cannot emit to standard output without --flat\n";
  return 1;
}

if (InputsOrErr->size() > 1 && FlatOut && !OutputFileOpt.empty()) {
  WithColor::error() << "cannot use -o with multiple inputs in flat mode\n";
  return 1;
}

if (getenv("RC_DEBUG_OPTIONS"))
  PaperTrailWarnings = true;

if (PaperTrailWarnings && InputIsYAMLDebugMap)
  WithColor::warning()
      << "Paper trail warnings are not supported for YAML input";

for (const auto &Arch : ArchFlags)
  if (Arch != "*" && Arch != "all" &&
      !llvm::object::MachOObjectFile::isValidArch(Arch)) {
    WithColor::error() << "unsupported cpu architecture: '" << Arch << "'\n";
    return 1;
  }

for (auto &InputFile : *InputsOrErr) {
  // Dump the symbol table for each input file and requested arch
  if (DumpStab) {
    if (!dumpStab(InputFile, ArchFlags, OsoPrependPath))
      return 1;
    continue;
  }

  auto DebugMapPtrsOrErr =
      parseDebugMap(InputFile, ArchFlags, OsoPrependPath, PaperTrailWarnings,
                    Verbose, InputIsYAMLDebugMap);

  if (auto EC = DebugMapPtrsOrErr.getError()) {
    WithColor::error() << "cannot parse the debug map for '" << InputFile
                       << "': " << EC.message() << '\n';
    return 1;
  }

  if (OptionsOrErr->Update) {
    // The debug map should be empty. Add one object file corresponding to
    // the input file.
    for (auto &Map : *DebugMapPtrsOrErr)
      Map->addDebugMapObject(InputFile,
                             llvm::sys::TimePoint<std::chrono::seconds>());
  }

  // Ensure that the debug map is not empty (anymore).
  if (DebugMapPtrsOrErr->empty()) {
    WithColor::error() << "no architecture to link\n";
    return 1;
  }

  // Shared a single binary holder for all the link steps.
  BinaryHolder BinHolder;

  NumThreads =
      std::min<unsigned>(OptionsOrErr->Threads, DebugMapPtrsOrErr->size());
  llvm::ThreadPool Threads(NumThreads);

  // If there is more than one link to execute, we need to generate
  // temporary files.
  bool NeedsTempFiles =
      !DumpDebugMap && (OutputFileOpt != "-") &&
      (DebugMapPtrsOrErr->size() != 1 || OptionsOrErr->Update);

  llvm::SmallVector<MachOUtils::ArchAndFile, 4> TempFiles;
  std::atomic_char AllOK(1);
  for (auto &Map : *DebugMapPtrsOrErr) {
    if (Verbose || DumpDebugMap)
      Map->print(llvm::outs());

    if (DumpDebugMap)
      continue;

    if (Map->begin() == Map->end())
      WithColor::warning()
          << "no debug symbols in executable (-arch "
          << MachOUtils::getArchName(Map->getTriple().getArchName()) << ")\n";

    // Using a std::shared_ptr rather than std::unique_ptr because move-only
    // types don't work with std::bind in the ThreadPool implementation.
    std::shared_ptr<raw_fd_ostream> OS;

    Expected<std::string> OutputFileOrErr = getOutputFileName(InputFile);
    if (!OutputFileOrErr) {
      WithColor::error() << toString(OutputFileOrErr.takeError());
      return 1;
    }

    std::string OutputFile = *OutputFileOrErr;
    if (NeedsTempFiles) {
      TempFiles.emplace_back(Map->getTriple().getArchName().str());

      auto E = TempFiles.back().createTempFile();
      if (E) {
        WithColor::error() << toString(std::move(E));
        return 1;
      }

      auto &TempFile = *(TempFiles.back().File);
      OS = std::make_shared<raw_fd_ostream>(TempFile.FD,
                                            /*shouldClose*/ false);
      OutputFile = TempFile.TmpName;
    } else {
      std::error_code EC;
      OS = std::make_shared<raw_fd_ostream>(NoOutput ? "-" : OutputFile, EC,
                                            sys::fs::F_None);
      if (EC) {
        WithColor::error() << OutputFile << ": " << EC.message();
        return 1;
      }
    }

    auto LinkLambda = [&,
                       OutputFile](std::shared_ptr<raw_fd_ostream> Stream) {
      AllOK.fetch_and(linkDwarf(*Stream, BinHolder, *Map, *OptionsOrErr));
      Stream->flush();
      if (Verify && !NoOutput)
        AllOK.fetch_and(verify(OutputFile, Map->getTriple().getArchName()));
    };

    // FIXME: The DwarfLinker can have some very deep recursion that can max
    // out the (significantly smaller) stack when using threads. We don't
    // want this limitation when we only have a single thread.
    if (NumThreads == 1)
      LinkLambda(OS);
    else
      Threads.async(LinkLambda, OS);
  }

  Threads.wait();

  if (!AllOK)
    return 1;

  if (NeedsTempFiles) {
    Expected<std::string> OutputFileOrErr = getOutputFileName(InputFile);
    if (!OutputFileOrErr) {
      WithColor::error() << toString(OutputFileOrErr.takeError());
      return 1;
    }
    if (!MachOUtils::generateUniversalBinary(TempFiles, *OutputFileOrErr,
                                             *OptionsOrErr, SDKPath))
      return 1;
  }
}

return 0;
588}

←

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h

→

1//===- llvm/Support/Error.h - Recoverable error handling --------*- 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 an API used to report recoverable errors.
11//
12//===----------------------------------------------------------------------===//
13 
14#ifndef LLVM_SUPPORT_ERROR_H
15#define LLVM_SUPPORT_ERROR_H
16 
17#include "llvm-c/Error.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StringExtras.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/Config/abi-breaking.h"
23#include "llvm/Support/AlignOf.h"
24#include "llvm/Support/Compiler.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/ErrorOr.h"
28#include "llvm/Support/Format.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31#include <cassert>
32#include <cstdint>
33#include <cstdlib>
34#include <functional>
35#include <memory>
36#include <new>
37#include <string>
38#include <system_error>
39#include <type_traits>
40#include <utility>
41#include <vector>
42 
43namespace llvm {
44 
45class ErrorSuccess;
46 
47/// Base class for error info classes. Do not extend this directly: Extend
48/// the ErrorInfo template subclass instead.
49class ErrorInfoBase {
50public:
51  virtual ~ErrorInfoBase() = default;
52 
53  /// Print an error message to an output stream.
54  virtual void log(raw_ostream &OS) const = 0;
55 
56  /// Return the error message as a string.
57  virtual std::string message() const {
58    std::string Msg;
59    raw_string_ostream OS(Msg);
60    log(OS);
61    return OS.str();
62  }
63 
64  /// Convert this error to a std::error_code.
65  ///
66  /// This is a temporary crutch to enable interaction with code still
67  /// using std::error_code. It will be removed in the future.
68  virtual std::error_code convertToErrorCode() const = 0;
69 
70  // Returns the class ID for this type.
71  static const void *classID() { return &ID; }
72 
73  // Returns the class ID for the dynamic type of this ErrorInfoBase instance.
74  virtual const void *dynamicClassID() const = 0;
75 
76  // Check whether this instance is a subclass of the class identified by
77  // ClassID.
78  virtual bool isA(const void *const ClassID) const {
79    return ClassID == classID();
80  }
81 
82  // Check whether this instance is a subclass of ErrorInfoT.
83  template <typename ErrorInfoT> bool isA() const {
84    return isA(ErrorInfoT::classID());
85  }
86 
87private:
88  virtual void anchor();
89 
90  static char ID;
91};
92 
93/// Lightweight error class with error context and mandatory checking.
94///
95/// Instances of this class wrap a ErrorInfoBase pointer. Failure states
96/// are represented by setting the pointer to a ErrorInfoBase subclass
97/// instance containing information describing the failure. Success is
98/// represented by a null pointer value.
99///
100/// Instances of Error also contains a 'Checked' flag, which must be set
101/// before the destructor is called, otherwise the destructor will trigger a
102/// runtime error. This enforces at runtime the requirement that all Error
103/// instances be checked or returned to the caller.
104///
105/// There are two ways to set the checked flag, depending on what state the
106/// Error instance is in. For Error instances indicating success, it
107/// is sufficient to invoke the boolean conversion operator. E.g.:
108///
109///   @code{.cpp}
110///   Error foo(<...>);
111///
112///   if (auto E = foo(<...>))
113///     return E; // <- Return E if it is in the error state.
114///   // We have verified that E was in the success state. It can now be safely
115///   // destroyed.
116///   @endcode
117///
118/// A success value *can not* be dropped. For example, just calling 'foo(<...>)'
119/// without testing the return value will raise a runtime error, even if foo
120/// returns success.
121///
122/// For Error instances representing failure, you must use either the
123/// handleErrors or handleAllErrors function with a typed handler. E.g.:
124///
125///   @code{.cpp}
126///   class MyErrorInfo : public ErrorInfo<MyErrorInfo> {
127///     // Custom error info.
128///   };
129///
130///   Error foo(<...>) { return make_error<MyErrorInfo>(...); }
131///
132///   auto E = foo(<...>); // <- foo returns failure with MyErrorInfo.
133///   auto NewE =
134///     handleErrors(E,
135///       [](const MyErrorInfo &M) {
136///         // Deal with the error.
137///       },
138///       [](std::unique_ptr<OtherError> M) -> Error {
139///         if (canHandle(*M)) {
140///           // handle error.
141///           return Error::success();
142///         }
143///         // Couldn't handle this error instance. Pass it up the stack.
144///         return Error(std::move(M));
145///       );
146///   // Note - we must check or return NewE in case any of the handlers
147///   // returned a new error.
148///   @endcode
149///
150/// The handleAllErrors function is identical to handleErrors, except
151/// that it has a void return type, and requires all errors to be handled and
152/// no new errors be returned. It prevents errors (assuming they can all be
153/// handled) from having to be bubbled all the way to the top-level.
154///
155/// *All* Error instances must be checked before destruction, even if
156/// they're moved-assigned or constructed from Success values that have already
157/// been checked. This enforces checking through all levels of the call stack.
158class LLVM_NODISCARD[[clang::warn_unused_result]] Error {
159  // Both ErrorList and FileError need to be able to yank ErrorInfoBase
160  // pointers out of this class to add to the error list.
161  friend class ErrorList;
162  friend class FileError;
163 
164  // handleErrors needs to be able to set the Checked flag.
165  template <typename... HandlerTs>
166  friend Error handleErrors(Error E, HandlerTs &&... Handlers);
167 
168  // Expected<T> needs to be able to steal the payload when constructed from an
169  // error.
170  template <typename T> friend class Expected;
171 
172  // wrap needs to be able to steal the payload.
173  friend LLVMErrorRef wrap(Error);
174 
175protected:
176  /// Create a success value. Prefer using 'Error::success()' for readability
177  Error() {
178    setPtr(nullptr);
179    setChecked(false);
180  }
181 
182public:
183  /// Create a success value.
184  static ErrorSuccess success();
185 
186  // Errors are not copy-constructable.
187  Error(const Error &Other) = delete;
188 
189  /// Move-construct an error value. The newly constructed error is considered
190  /// unchecked, even if the source error had been checked. The original error
191  /// becomes a checked Success value, regardless of its original state.
192  Error(Error &&Other) {
193    setChecked(true);
194    *this = std::move(Other);
195  }
196 
197  /// Create an error value. Prefer using the 'make_error' function, but
198  /// this constructor can be useful when "re-throwing" errors from handlers.
199  Error(std::unique_ptr<ErrorInfoBase> Payload) {
200    setPtr(Payload.release());
201    setChecked(false);
17
←
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'
202  }
203 
204  // Errors are not copy-assignable.
205  Error &operator=(const Error &Other) = delete;
206 
207  /// Move-assign an error value. The current error must represent success, you
208  /// you cannot overwrite an unhandled error. The current error is then
209  /// considered unchecked. The source error becomes a checked success value,
210  /// regardless of its original state.
211  Error &operator=(Error &&Other) {
212    // Don't allow overwriting of unchecked values.
213    assertIsChecked();
214    setPtr(Other.getPtr());
215 
216    // This Error is unchecked, even if the source error was checked.
217    setChecked(false);
218 
219    // Null out Other's payload and set its checked bit.
220    Other.setPtr(nullptr);
221    Other.setChecked(true);
222 
223    return *this;
224  }
225 
226  /// Destroy a Error. Fails with a call to abort() if the error is
227  /// unchecked.
228  ~Error() {
229    assertIsChecked();
230    delete getPtr();
231  }
232 
233  /// Bool conversion. Returns true if this Error is in a failure state,
234  /// and false if it is in an accept state. If the error is in a Success state
235  /// it will be considered checked.
236  explicit operator bool() {
237    setChecked(getPtr() == nullptr);
238    return getPtr() != nullptr;
239  }
240 
241  /// Check whether one error is a subclass of another.
242  template <typename ErrT> bool isA() const {
243    return getPtr() && getPtr()->isA(ErrT::classID());
244  }
245 
246  /// Returns the dynamic class id of this error, or null if this is a success
247  /// value.
248  const void* dynamicClassID() const {
249    if (!getPtr())
250      return nullptr;
251    return getPtr()->dynamicClassID();
252  }
253 
254private:
255#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
256  // assertIsChecked() happens very frequently, but under normal circumstances
257  // is supposed to be a no-op.  So we want it to be inlined, but having a bunch
258  // of debug prints can cause the function to be too large for inlining.  So
259  // it's important that we define this function out of line so that it can't be
260  // inlined.
261  LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
262  void fatalUncheckedError() const;
263#endif
264 
265  void assertIsChecked() {
266#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
267    if (LLVM_UNLIKELY(!getChecked() || getPtr())__builtin_expect((bool)(!getChecked() || getPtr()), false))
268      fatalUncheckedError();
269#endif
270  }
271 
272  ErrorInfoBase *getPtr() const {
273    return reinterpret_cast<ErrorInfoBase*>(
274             reinterpret_cast<uintptr_t>(Payload) &
275             ~static_cast<uintptr_t>(0x1));
276  }
277 
278  void setPtr(ErrorInfoBase *EI) {
279#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
280    Payload = reinterpret_cast<ErrorInfoBase*>(
281                (reinterpret_cast<uintptr_t>(EI) &
282                 ~static_cast<uintptr_t>(0x1)) |
283                (reinterpret_cast<uintptr_t>(Payload) & 0x1));
284#else
285    Payload = EI;
286#endif
287  }
288 
289  bool getChecked() const {
290#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
291    return (reinterpret_cast<uintptr_t>(Payload) & 0x1) == 0;
292#else
293    return true;
294#endif
295  }
296 
297  void setChecked(bool V) {
298    Payload = reinterpret_cast<ErrorInfoBase*>(
299                (reinterpret_cast<uintptr_t>(Payload) &
300                  ~static_cast<uintptr_t>(0x1)) |
301                  (V ? 0 : 1));
302  }
303 
304  std::unique_ptr<ErrorInfoBase> takePayload() {
305    std::unique_ptr<ErrorInfoBase> Tmp(getPtr());
306    setPtr(nullptr);
307    setChecked(true);
308    return Tmp;
309  }
310 
311  friend raw_ostream &operator<<(raw_ostream &OS, const Error &E) {
312    if (auto P = E.getPtr())
313      P->log(OS);
314    else
315      OS << "success";
316    return OS;
317  }
318 
319  ErrorInfoBase *Payload = nullptr;
320};
321 
322/// Subclass of Error for the sole purpose of identifying the success path in
323/// the type system. This allows to catch invalid conversion to Expected<T> at
324/// compile time.
325class ErrorSuccess final : public Error {};
326 
327inline ErrorSuccess Error::success() { return ErrorSuccess(); }
328 
329/// Make a Error instance representing failure using the given error info
330/// type.
331template <typename ErrT, typename... ArgTs> Error make_error(ArgTs &&... Args) {
332  return Error(llvm::make_unique<ErrT>(std::forward<ArgTs>(Args)...));
13
←
Calling 'make_unique<llvm::StringError, std::__cxx11::basic_string<char>, std::error_code>'→
15
←
Returned allocated memory→
16
←
Calling constructor for 'Error'→
333}
334 
335/// Base class for user error types. Users should declare their error types
336/// like:
337///
338/// class MyError : public ErrorInfo<MyError> {
339///   ....
340/// };
341///
342/// This class provides an implementation of the ErrorInfoBase::kind
343/// method, which is used by the Error RTTI system.
344template <typename ThisErrT, typename ParentErrT = ErrorInfoBase>
345class ErrorInfo : public ParentErrT {
346public:
347  using ParentErrT::ParentErrT; // inherit constructors
348 
349  static const void *classID() { return &ThisErrT::ID; }
350 
351  const void *dynamicClassID() const override { return &ThisErrT::ID; }
352 
353  bool isA(const void *const ClassID) const override {
354    return ClassID == classID() || ParentErrT::isA(ClassID);
355  }
356};
357 
358/// Special ErrorInfo subclass representing a list of ErrorInfos.
359/// Instances of this class are constructed by joinError.
360class ErrorList final : public ErrorInfo<ErrorList> {
361  // handleErrors needs to be able to iterate the payload list of an
362  // ErrorList.
363  template <typename... HandlerTs>
364  friend Error handleErrors(Error E, HandlerTs &&... Handlers);
365 
366  // joinErrors is implemented in terms of join.
367  friend Error joinErrors(Error, Error);
368 
369public:
370  void log(raw_ostream &OS) const override {
371    OS << "Multiple errors:\n";
372    for (auto &ErrPayload : Payloads) {
373      ErrPayload->log(OS);
374      OS << "\n";
375    }
376  }
377 
378  std::error_code convertToErrorCode() const override;
379 
380  // Used by ErrorInfo::classID.
381  static char ID;
382 
383private:
384  ErrorList(std::unique_ptr<ErrorInfoBase> Payload1,
385            std::unique_ptr<ErrorInfoBase> Payload2) {
386    assert(!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() &&((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 387, __PRETTY_FUNCTION__))
387           "ErrorList constructor payloads should be singleton errors")((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 387, __PRETTY_FUNCTION__));
388    Payloads.push_back(std::move(Payload1));
389    Payloads.push_back(std::move(Payload2));
390  }
391 
392  static Error join(Error E1, Error E2) {
393    if (!E1)
394      return E2;
395    if (!E2)
396      return E1;
397    if (E1.isA<ErrorList>()) {
398      auto &E1List = static_cast<ErrorList &>(*E1.getPtr());
399      if (E2.isA<ErrorList>()) {
400        auto E2Payload = E2.takePayload();
401        auto &E2List = static_cast<ErrorList &>(*E2Payload);
402        for (auto &Payload : E2List.Payloads)
403          E1List.Payloads.push_back(std::move(Payload));
404      } else
405        E1List.Payloads.push_back(E2.takePayload());
406 
407      return E1;
408    }
409    if (E2.isA<ErrorList>()) {
410      auto &E2List = static_cast<ErrorList &>(*E2.getPtr());
411      E2List.Payloads.insert(E2List.Payloads.begin(), E1.takePayload());
412      return E2;
413    }
414    return Error(std::unique_ptr<ErrorList>(
415        new ErrorList(E1.takePayload(), E2.takePayload())));
416  }
417 
418  std::vector<std::unique_ptr<ErrorInfoBase>> Payloads;
419};
420 
421/// Concatenate errors. The resulting Error is unchecked, and contains the
422/// ErrorInfo(s), if any, contained in E1, followed by the
423/// ErrorInfo(s), if any, contained in E2.
424inline Error joinErrors(Error E1, Error E2) {
425  return ErrorList::join(std::move(E1), std::move(E2));
426}
427 
428/// Tagged union holding either a T or a Error.
429///
430/// This class parallels ErrorOr, but replaces error_code with Error. Since
431/// Error cannot be copied, this class replaces getError() with
432/// takeError(). It also adds an bool errorIsA<ErrT>() method for testing the
433/// error class type.
434template <class T> class LLVM_NODISCARD[[clang::warn_unused_result]] Expected {
435  template <class T1> friend class ExpectedAsOutParameter;
436  template <class OtherT> friend class Expected;
437 
438  static const bool isRef = std::is_reference<T>::value;
439 
440  using wrap = std::reference_wrapper<typename std::remove_reference<T>::type>;
441 
442  using error_type = std::unique_ptr<ErrorInfoBase>;
443 
444public:
445  using storage_type = typename std::conditional<isRef, wrap, T>::type;
446  using value_type = T;
447 
448private:
449  using reference = typename std::remove_reference<T>::type &;
450  using const_reference = const typename std::remove_reference<T>::type &;
451  using pointer = typename std::remove_reference<T>::type *;
452  using const_pointer = const typename std::remove_reference<T>::type *;
453 
454public:
455  /// Create an Expected<T> error value from the given Error.
456  Expected(Error Err)
457      : HasError(true)
458#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
459        // Expected is unchecked upon construction in Debug builds.
460        , Unchecked(true)
461#endif
462  {
463    assert(Err && "Cannot create Expected<T> from Error success value.")((Err && "Cannot create Expected<T> from Error success value."
) ? static_cast<void> (0) : __assert_fail ("Err && \"Cannot create Expected<T> from Error success value.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 463, __PRETTY_FUNCTION__));
464    new (getErrorStorage()) error_type(Err.takePayload());
465  }
466 
467  /// Forbid to convert from Error::success() implicitly, this avoids having
468  /// Expected<T> foo() { return Error::success(); } which compiles otherwise
469  /// but triggers the assertion above.
470  Expected(ErrorSuccess) = delete;
471 
472  /// Create an Expected<T> success value from the given OtherT value, which
473  /// must be convertible to T.
474  template <typename OtherT>
475  Expected(OtherT &&Val,
476           typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
477               * = nullptr)
478      : HasError(false)
479#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
480        // Expected is unchecked upon construction in Debug builds.
481        , Unchecked(true)
482#endif
483  {
484    new (getStorage()) storage_type(std::forward<OtherT>(Val));
485  }
486 
487  /// Move construct an Expected<T> value.
488  Expected(Expected &&Other) { moveConstruct(std::move(Other)); }
489 
490  /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
491  /// must be convertible to T.
492  template <class OtherT>
493  Expected(Expected<OtherT> &&Other,
494           typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
495               * = nullptr) {
496    moveConstruct(std::move(Other));
497  }
498 
499  /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
500  /// isn't convertible to T.
501  template <class OtherT>
502  explicit Expected(
503      Expected<OtherT> &&Other,
504      typename std::enable_if<!std::is_convertible<OtherT, T>::value>::type * =
505          nullptr) {
506    moveConstruct(std::move(Other));
507  }
508 
509  /// Move-assign from another Expected<T>.
510  Expected &operator=(Expected &&Other) {
511    moveAssign(std::move(Other));
512    return *this;
513  }
514 
515  /// Destroy an Expected<T>.
516  ~Expected() {
517    assertIsChecked();
518    if (!HasError)
519      getStorage()->~storage_type();
520    else
521      getErrorStorage()->~error_type();
522  }
523 
524  /// Return false if there is an error.
525  explicit operator bool() {
526#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
527    Unchecked = HasError;
528#endif
529    return !HasError;
530  }
531 
532  /// Returns a reference to the stored T value.
533  reference get() {
534    assertIsChecked();
535    return *getStorage();
536  }
537 
538  /// Returns a const reference to the stored T value.
539  const_reference get() const {
540    assertIsChecked();
541    return const_cast<Expected<T> *>(this)->get();
542  }
543 
544  /// Check that this Expected<T> is an error of type ErrT.
545  template <typename ErrT> bool errorIsA() const {
546    return HasError && (*getErrorStorage())->template isA<ErrT>();
547  }
548 
549  /// Take ownership of the stored error.
550  /// After calling this the Expected<T> is in an indeterminate state that can
551  /// only be safely destructed. No further calls (beside the destructor) should
552  /// be made on the Expected<T> vaule.
553  Error takeError() {
554#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
555    Unchecked = false;
556#endif
557    return HasError ? Error(std::move(*getErrorStorage())) : Error::success();
558  }
559 
560  /// Returns a pointer to the stored T value.
561  pointer operator->() {
562    assertIsChecked();
563    return toPointer(getStorage());
564  }
565 
566  /// Returns a const pointer to the stored T value.
567  const_pointer operator->() const {
568    assertIsChecked();
569    return toPointer(getStorage());
570  }
571 
572  /// Returns a reference to the stored T value.
573  reference operator*() {
574    assertIsChecked();
575    return *getStorage();
576  }
577 
578  /// Returns a const reference to the stored T value.
579  const_reference operator*() const {
580    assertIsChecked();
581    return *getStorage();
582  }
583 
584private:
585  template <class T1>
586  static bool compareThisIfSameType(const T1 &a, const T1 &b) {
587    return &a == &b;
588  }
589 
590  template <class T1, class T2>
591  static bool compareThisIfSameType(const T1 &a, const T2 &b) {
592    return false;
593  }
594 
595  template <class OtherT> void moveConstruct(Expected<OtherT> &&Other) {
596    HasError = Other.HasError;
597#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
598    Unchecked = true;
599    Other.Unchecked = false;
600#endif
601 
602    if (!HasError)
603      new (getStorage()) storage_type(std::move(*Other.getStorage()));
604    else
605      new (getErrorStorage()) error_type(std::move(*Other.getErrorStorage()));
606  }
607 
608  template <class OtherT> void moveAssign(Expected<OtherT> &&Other) {
609    assertIsChecked();
610 
611    if (compareThisIfSameType(*this, Other))
612      return;
613 
614    this->~Expected();
615    new (this) Expected(std::move(Other));
616  }
617 
618  pointer toPointer(pointer Val) { return Val; }
619 
620  const_pointer toPointer(const_pointer Val) const { return Val; }
621 
622  pointer toPointer(wrap *Val) { return &Val->get(); }
623 
624  const_pointer toPointer(const wrap *Val) const { return &Val->get(); }
625 
626  storage_type *getStorage() {
627    assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 627, __PRETTY_FUNCTION__));
628    return reinterpret_cast<storage_type *>(TStorage.buffer);
629  }
630 
631  const storage_type *getStorage() const {
632    assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 632, __PRETTY_FUNCTION__));
633    return reinterpret_cast<const storage_type *>(TStorage.buffer);
634  }
635 
636  error_type *getErrorStorage() {
637    assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 637, __PRETTY_FUNCTION__));
638    return reinterpret_cast<error_type *>(ErrorStorage.buffer);
639  }
640 
641  const error_type *getErrorStorage() const {
642    assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 642, __PRETTY_FUNCTION__));
643    return reinterpret_cast<const error_type *>(ErrorStorage.buffer);
644  }
645 
646  // Used by ExpectedAsOutParameter to reset the checked flag.
647  void setUnchecked() {
648#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
649    Unchecked = true;
650#endif
651  }
652 
653#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
654  LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
655  LLVM_ATTRIBUTE_NOINLINE__attribute__((noinline))
656  void fatalUncheckedExpected() const {
657    dbgs() << "Expected<T> must be checked before access or destruction.\n";
658    if (HasError) {
659      dbgs() << "Unchecked Expected<T> contained error:\n";
660      (*getErrorStorage())->log(dbgs());
661    } else
662      dbgs() << "Expected<T> value was in success state. (Note: Expected<T> "
663                "values in success mode must still be checked prior to being "
664                "destroyed).\n";
665    abort();
666  }
667#endif
668 
669  void assertIsChecked() {
670#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
671    if (LLVM_UNLIKELY(Unchecked)__builtin_expect((bool)(Unchecked), false))
672      fatalUncheckedExpected();
673#endif
674  }
675 
676  union {
677    AlignedCharArrayUnion<storage_type> TStorage;
678    AlignedCharArrayUnion<error_type> ErrorStorage;
679  };
680  bool HasError : 1;
681#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
682  bool Unchecked : 1;
683#endif
684};
685 
686/// Report a serious error, calling any installed error handler. See
687/// ErrorHandling.h.
688LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void report_fatal_error(Error Err,
689                                                bool gen_crash_diag = true);
690 
691/// Report a fatal error if Err is a failure value.
692///
693/// This function can be used to wrap calls to fallible functions ONLY when it
694/// is known that the Error will always be a success value. E.g.
695///
696///   @code{.cpp}
697///   // foo only attempts the fallible operation if DoFallibleOperation is
698///   // true. If DoFallibleOperation is false then foo always returns
699///   // Error::success().
700///   Error foo(bool DoFallibleOperation);
701///
702///   cantFail(foo(false));
703///   @endcode
704inline void cantFail(Error Err, const char *Msg = nullptr) {
705  if (Err) {
706    if (!Msg)
707      Msg = "Failure value returned from cantFail wrapped call";
708    llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 708);
709  }
710}
711 
712/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
713/// returns the contained value.
714///
715/// This function can be used to wrap calls to fallible functions ONLY when it
716/// is known that the Error will always be a success value. E.g.
717///
718///   @code{.cpp}
719///   // foo only attempts the fallible operation if DoFallibleOperation is
720///   // true. If DoFallibleOperation is false then foo always returns an int.
721///   Expected<int> foo(bool DoFallibleOperation);
722///
723///   int X = cantFail(foo(false));
724///   @endcode
725template <typename T>
726T cantFail(Expected<T> ValOrErr, const char *Msg = nullptr) {
727  if (ValOrErr)
728    return std::move(*ValOrErr);
729  else {
730    if (!Msg)
731      Msg = "Failure value returned from cantFail wrapped call";
732    llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 732);
733  }
734}
735 
736/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
737/// returns the contained reference.
738///
739/// This function can be used to wrap calls to fallible functions ONLY when it
740/// is known that the Error will always be a success value. E.g.
741///
742///   @code{.cpp}
743///   // foo only attempts the fallible operation if DoFallibleOperation is
744///   // true. If DoFallibleOperation is false then foo always returns a Bar&.
745///   Expected<Bar&> foo(bool DoFallibleOperation);
746///
747///   Bar &X = cantFail(foo(false));
748///   @endcode
749template <typename T>
750T& cantFail(Expected<T&> ValOrErr, const char *Msg = nullptr) {
751  if (ValOrErr)
752    return *ValOrErr;
753  else {
754    if (!Msg)
755      Msg = "Failure value returned from cantFail wrapped call";
756    llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 756);
757  }
758}
759 
760/// Helper for testing applicability of, and applying, handlers for
761/// ErrorInfo types.
762template <typename HandlerT>
763class ErrorHandlerTraits
764    : public ErrorHandlerTraits<decltype(
765          &std::remove_reference<HandlerT>::type::operator())> {};
766 
767// Specialization functions of the form 'Error (const ErrT&)'.
768template <typename ErrT> class ErrorHandlerTraits<Error (&)(ErrT &)> {
769public:
770  static bool appliesTo(const ErrorInfoBase &E) {
771    return E.template isA<ErrT>();
772  }
773 
774  template <typename HandlerT>
775  static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
776    assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 776, __PRETTY_FUNCTION__));
777    return H(static_cast<ErrT &>(*E));
778  }
779};
780 
781// Specialization functions of the form 'void (const ErrT&)'.
782template <typename ErrT> class ErrorHandlerTraits<void (&)(ErrT &)> {
783public:
784  static bool appliesTo(const ErrorInfoBase &E) {
785    return E.template isA<ErrT>();
786  }
787 
788  template <typename HandlerT>
789  static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
790    assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 790, __PRETTY_FUNCTION__));
791    H(static_cast<ErrT &>(*E));
792    return Error::success();
793  }
794};
795 
796/// Specialization for functions of the form 'Error (std::unique_ptr<ErrT>)'.
797template <typename ErrT>
798class ErrorHandlerTraits<Error (&)(std::unique_ptr<ErrT>)> {
799public:
800  static bool appliesTo(const ErrorInfoBase &E) {
801    return E.template isA<ErrT>();
802  }
803 
804  template <typename HandlerT>
805  static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
806    assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 806, __PRETTY_FUNCTION__));
807    std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
808    return H(std::move(SubE));
809  }
810};
811 
812/// Specialization for functions of the form 'void (std::unique_ptr<ErrT>)'.
813template <typename ErrT>
814class ErrorHandlerTraits<void (&)(std::unique_ptr<ErrT>)> {
815public:
816  static bool appliesTo(const ErrorInfoBase &E) {
817    return E.template isA<ErrT>();
818  }
819 
820  template <typename HandlerT>
821  static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
822    assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 822, __PRETTY_FUNCTION__));
823    std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
824    H(std::move(SubE));
825    return Error::success();
826  }
827};
828 
829// Specialization for member functions of the form 'RetT (const ErrT&)'.
830template <typename C, typename RetT, typename ErrT>
831class ErrorHandlerTraits<RetT (C::*)(ErrT &)>
832    : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
833 
834// Specialization for member functions of the form 'RetT (const ErrT&) const'.
835template <typename C, typename RetT, typename ErrT>
836class ErrorHandlerTraits<RetT (C::*)(ErrT &) const>
837    : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
838 
839// Specialization for member functions of the form 'RetT (const ErrT&)'.
840template <typename C, typename RetT, typename ErrT>
841class ErrorHandlerTraits<RetT (C::*)(const ErrT &)>
842    : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
843 
844// Specialization for member functions of the form 'RetT (const ErrT&) const'.
845template <typename C, typename RetT, typename ErrT>
846class ErrorHandlerTraits<RetT (C::*)(const ErrT &) const>
847    : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
848 
849/// Specialization for member functions of the form
850/// 'RetT (std::unique_ptr<ErrT>)'.
851template <typename C, typename RetT, typename ErrT>
852class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>)>
853    : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
854 
855/// Specialization for member functions of the form
856/// 'RetT (std::unique_ptr<ErrT>) const'.
857template <typename C, typename RetT, typename ErrT>
858class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>) const>
859    : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
860 
861inline Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload) {
862  return Error(std::move(Payload));
863}
864 
865template <typename HandlerT, typename... HandlerTs>
866Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload,
867                      HandlerT &&Handler, HandlerTs &&... Handlers) {
868  if (ErrorHandlerTraits<HandlerT>::appliesTo(*Payload))
869    return ErrorHandlerTraits<HandlerT>::apply(std::forward<HandlerT>(Handler),
870                                               std::move(Payload));
871  return handleErrorImpl(std::move(Payload),
872                         std::forward<HandlerTs>(Handlers)...);
873}
874 
875/// Pass the ErrorInfo(s) contained in E to their respective handlers. Any
876/// unhandled errors (or Errors returned by handlers) are re-concatenated and
877/// returned.
878/// Because this function returns an error, its result must also be checked
879/// or returned. If you intend to handle all errors use handleAllErrors
880/// (which returns void, and will abort() on unhandled errors) instead.
881template <typename... HandlerTs>
882Error handleErrors(Error E, HandlerTs &&... Hs) {
883  if (!E)
884    return Error::success();
885 
886  std::unique_ptr<ErrorInfoBase> Payload = E.takePayload();
887 
888  if (Payload->isA<ErrorList>()) {
889    ErrorList &List = static_cast<ErrorList &>(*Payload);
890    Error R;
891    for (auto &P : List.Payloads)
892      R = ErrorList::join(
893          std::move(R),
894          handleErrorImpl(std::move(P), std::forward<HandlerTs>(Hs)...));
895    return R;
896  }
897 
898  return handleErrorImpl(std::move(Payload), std::forward<HandlerTs>(Hs)...);
899}
900 
901/// Behaves the same as handleErrors, except that by contract all errors
902/// *must* be handled by the given handlers (i.e. there must be no remaining
903/// errors after running the handlers, or llvm_unreachable is called).
904template <typename... HandlerTs>
905void handleAllErrors(Error E, HandlerTs &&... Handlers) {
906  cantFail(handleErrors(std::move(E), std::forward<HandlerTs>(Handlers)...));
907}
908 
909/// Check that E is a non-error, then drop it.
910/// If E is an error, llvm_unreachable will be called.
911inline void handleAllErrors(Error E) {
912  cantFail(std::move(E));
913}
914 
915/// Handle any errors (if present) in an Expected<T>, then try a recovery path.
916///
917/// If the incoming value is a success value it is returned unmodified. If it
918/// is a failure value then it the contained error is passed to handleErrors.
919/// If handleErrors is able to handle the error then the RecoveryPath functor
920/// is called to supply the final result. If handleErrors is not able to
921/// handle all errors then the unhandled errors are returned.
922///
923/// This utility enables the follow pattern:
924///
925///   @code{.cpp}
926///   enum FooStrategy { Aggressive, Conservative };
927///   Expected<Foo> foo(FooStrategy S);
928///
929///   auto ResultOrErr =
930///     handleExpected(
931///       foo(Aggressive),
932///       []() { return foo(Conservative); },
933///       [](AggressiveStrategyError&) {
934///         // Implicitly conusme this - we'll recover by using a conservative
935///         // strategy.
936///       });
937///
938///   @endcode
939template <typename T, typename RecoveryFtor, typename... HandlerTs>
940Expected<T> handleExpected(Expected<T> ValOrErr, RecoveryFtor &&RecoveryPath,
941                           HandlerTs &&... Handlers) {
942  if (ValOrErr)
943    return ValOrErr;
944 
945  if (auto Err = handleErrors(ValOrErr.takeError(),
946                              std::forward<HandlerTs>(Handlers)...))
947    return std::move(Err);
948 
949  return RecoveryPath();
950}
951 
952/// Log all errors (if any) in E to OS. If there are any errors, ErrorBanner
953/// will be printed before the first one is logged. A newline will be printed
954/// after each error.
955///
956/// This is useful in the base level of your program to allow clean termination
957/// (allowing clean deallocation of resources, etc.), while reporting error
958/// information to the user.
959void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner);
960 
961/// Write all error messages (if any) in E to a string. The newline character
962/// is used to separate error messages.
963inline std::string toString(Error E) {
964  SmallVector<std::string, 2> Errors;
965  handleAllErrors(std::move(E), [&Errors](const ErrorInfoBase &EI) {
966    Errors.push_back(EI.message());
967  });
968  return join(Errors.begin(), Errors.end(), "\n");
969}
970 
971/// Consume a Error without doing anything. This method should be used
972/// only where an error can be considered a reasonable and expected return
973/// value.
974///
975/// Uses of this method are potentially indicative of design problems: If it's
976/// legitimate to do nothing while processing an "error", the error-producer
977/// might be more clearly refactored to return an Optional<T>.
978inline void consumeError(Error Err) {
979  handleAllErrors(std::move(Err), [](const ErrorInfoBase &) {});
980}
981 
982/// Helper for converting an Error to a bool.
983///
984/// This method returns true if Err is in an error state, or false if it is
985/// in a success state.  Puts Err in a checked state in both cases (unlike
986/// Error::operator bool(), which only does this for success states).
987inline bool errorToBool(Error Err) {
988  bool IsError = static_cast<bool>(Err);
989  if (IsError)
990    consumeError(std::move(Err));
991  return IsError;
992}
993 
994/// Helper for Errors used as out-parameters.
995///
996/// This helper is for use with the Error-as-out-parameter idiom, where an error
997/// is passed to a function or method by reference, rather than being returned.
998/// In such cases it is helpful to set the checked bit on entry to the function
999/// so that the error can be written to (unchecked Errors abort on assignment)
1000/// and clear the checked bit on exit so that clients cannot accidentally forget
1001/// to check the result. This helper performs these actions automatically using
1002/// RAII:
1003///
1004///   @code{.cpp}
1005///   Result foo(Error &Err) {
1006///     ErrorAsOutParameter ErrAsOutParam(&Err); // 'Checked' flag set
1007///     // <body of foo>
1008///     // <- 'Checked' flag auto-cleared when ErrAsOutParam is destructed.
1009///   }
1010///   @endcode
1011///
1012/// ErrorAsOutParameter takes an Error* rather than Error& so that it can be
1013/// used with optional Errors (Error pointers that are allowed to be null). If
1014/// ErrorAsOutParameter took an Error reference, an instance would have to be
1015/// created inside every condition that verified that Error was non-null. By
1016/// taking an Error pointer we can just create one instance at the top of the
1017/// function.
1018class ErrorAsOutParameter {
1019public:
1020  ErrorAsOutParameter(Error *Err) : Err(Err) {
1021    // Raise the checked bit if Err is success.
1022    if (Err)
1023      (void)!!*Err;
1024  }
1025 
1026  ~ErrorAsOutParameter() {
1027    // Clear the checked bit.
1028    if (Err && !*Err)
1029      *Err = Error::success();
1030  }
1031 
1032private:
1033  Error *Err;
1034};
1035 
1036/// Helper for Expected<T>s used as out-parameters.
1037///
1038/// See ErrorAsOutParameter.
1039template <typename T>
1040class ExpectedAsOutParameter {
1041public:
1042  ExpectedAsOutParameter(Expected<T> *ValOrErr)
1043    : ValOrErr(ValOrErr) {
1044    if (ValOrErr)
1045      (void)!!*ValOrErr;
1046  }
1047 
1048  ~ExpectedAsOutParameter() {
1049    if (ValOrErr)
1050      ValOrErr->setUnchecked();
1051  }
1052 
1053private:
1054  Expected<T> *ValOrErr;
1055};
1056 
1057/// This class wraps a std::error_code in a Error.
1058///
1059/// This is useful if you're writing an interface that returns a Error
1060/// (or Expected) and you want to call code that still returns
1061/// std::error_codes.
1062class ECError : public ErrorInfo<ECError> {
1063  friend Error errorCodeToError(std::error_code);
1064 
1065public:
1066  void setErrorCode(std::error_code EC) { this->EC = EC; }
1067  std::error_code convertToErrorCode() const override { return EC; }
1068  void log(raw_ostream &OS) const override { OS << EC.message(); }
1069 
1070  // Used by ErrorInfo::classID.
1071  static char ID;
1072 
1073protected:
1074  ECError() = default;
1075  ECError(std::error_code EC) : EC(EC) {}
1076 
1077  std::error_code EC;
1078};
1079 
1080/// The value returned by this function can be returned from convertToErrorCode
1081/// for Error values where no sensible translation to std::error_code exists.
1082/// It should only be used in this situation, and should never be used where a
1083/// sensible conversion to std::error_code is available, as attempts to convert
1084/// to/from this error will result in a fatal error. (i.e. it is a programmatic
1085///error to try to convert such a value).
1086std::error_code inconvertibleErrorCode();
1087 
1088/// Helper for converting an std::error_code to a Error.
1089Error errorCodeToError(std::error_code EC);
1090 
1091/// Helper for converting an ECError to a std::error_code.
1092///
1093/// This method requires that Err be Error() or an ECError, otherwise it
1094/// will trigger a call to abort().
1095std::error_code errorToErrorCode(Error Err);
1096 
1097/// Convert an ErrorOr<T> to an Expected<T>.
1098template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> &&EO) {
1099  if (auto EC = EO.getError())
1100    return errorCodeToError(EC);
1101  return std::move(*EO);
1102}
1103 
1104/// Convert an Expected<T> to an ErrorOr<T>.
1105template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> &&E) {
1106  if (auto Err = E.takeError())
1107    return errorToErrorCode(std::move(Err));
1108  return std::move(*E);
1109}
1110 
1111/// This class wraps a string in an Error.
1112///
1113/// StringError is useful in cases where the client is not expected to be able
1114/// to consume the specific error message programmatically (for example, if the
1115/// error message is to be presented to the user).
1116///
1117/// StringError can also be used when additional information is to be printed
1118/// along with a error_code message. Depending on the constructor called, this
1119/// class can either display:
1120///    1. the error_code message (ECError behavior)
1121///    2. a string
1122///    3. the error_code message and a string
1123///
1124/// These behaviors are useful when subtyping is required; for example, when a
1125/// specific library needs an explicit error type. In the example below,
1126/// PDBError is derived from StringError:
1127///
1128///   @code{.cpp}
1129///   Expected<int> foo() {
1130///      return llvm::make_error<PDBError>(pdb_error_code::dia_failed_loading,
1131///                                        "Additional information");
1132///   }
1133///   @endcode
1134///
1135class StringError : public ErrorInfo<StringError> {
1136public:
1137  static char ID;
1138 
1139  // Prints EC + S and converts to EC
1140  StringError(std::error_code EC, const Twine &S = Twine());
1141 
1142  // Prints S and converts to EC
1143  StringError(const Twine &S, std::error_code EC);
1144 
1145  void log(raw_ostream &OS) const override;
1146  std::error_code convertToErrorCode() const override;
1147 
1148  const std::string &getMessage() const { return Msg; }
1149 
1150private:
1151  std::string Msg;
1152  std::error_code EC;
1153  const bool PrintMsgOnly = false;
1154};
1155 
1156/// Create formatted StringError object.
1157template <typename... Ts>
1158Error createStringError(std::error_code EC, char const *Fmt,
1159                        const Ts &... Vals) {
1160  std::string Buffer;
1161  raw_string_ostream Stream(Buffer);
1162  Stream << format(Fmt, Vals...);
1163  return make_error<StringError>(Stream.str(), EC);
1164}
1165 
1166Error createStringError(std::error_code EC, char const *Msg);
1167 
1168/// This class wraps a filename and another Error.
1169///
1170/// In some cases, an error needs to live along a 'source' name, in order to
1171/// show more detailed information to the user.
1172class FileError final : public ErrorInfo<FileError> {
1173 
1174  friend Error createFileError(std::string, Error);
1175 
1176public:
1177  void log(raw_ostream &OS) const override {
1178    assert(Err && !FileName.empty() && "Trying to log after takeError().")((Err && !FileName.empty() && "Trying to log after takeError()."
) ? static_cast<void> (0) : __assert_fail ("Err && !FileName.empty() && \"Trying to log after takeError().\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 1178, __PRETTY_FUNCTION__));
1179    OS << "'" << FileName << "': ";
1180    Err->log(OS);
1181  }
1182 
1183  Error takeError() { return Error(std::move(Err)); }
1184 
1185  std::error_code convertToErrorCode() const override;
1186 
1187  // Used by ErrorInfo::classID.
1188  static char ID;
1189 
1190private:
1191  FileError(std::string F, std::unique_ptr<ErrorInfoBase> E) {
1192    assert(E && "Cannot create FileError from Error success value.")((E && "Cannot create FileError from Error success value."
) ? static_cast<void> (0) : __assert_fail ("E && \"Cannot create FileError from Error success value.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 1192, __PRETTY_FUNCTION__));
1193    assert(!F.empty() &&((!F.empty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.empty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 1194, __PRETTY_FUNCTION__))
1194           "The file name provided to FileError must not be empty.")((!F.empty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.empty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/Error.h"
, 1194, __PRETTY_FUNCTION__));
1195    FileName = F;
1196    Err = std::move(E);
1197  }
1198 
1199  static Error build(std::string F, Error E) {
1200    return Error(std::unique_ptr<FileError>(new FileError(F, E.takePayload())));
1201  }
1202 
1203  std::string FileName;
1204  std::unique_ptr<ErrorInfoBase> Err;
1205};
1206 
1207/// Concatenate a source file path and/or name with an Error. The resulting
1208/// Error is unchecked.
1209inline Error createFileError(std::string F, Error E) {
1210  return FileError::build(F, std::move(E));
1211}
1212 
1213Error createFileError(std::string F, ErrorSuccess) = delete;
1214 
1215/// Helper for check-and-exit error handling.
1216///
1217/// For tool use only. NOT FOR USE IN LIBRARY CODE.
1218///
1219class ExitOnError {
1220public:
1221  /// Create an error on exit helper.
1222  ExitOnError(std::string Banner = "", int DefaultErrorExitCode = 1)
1223      : Banner(std::move(Banner)),
1224        GetExitCode([=](const Error &) { return DefaultErrorExitCode; }) {}
1225 
1226  /// Set the banner string for any errors caught by operator().
1227  void setBanner(std::string Banner) { this->Banner = std::move(Banner); }
1228 
1229  /// Set the exit-code mapper function.
1230  void setExitCodeMapper(std::function<int(const Error &)> GetExitCode) {
1231    this->GetExitCode = std::move(GetExitCode);
1232  }
1233 
1234  /// Check Err. If it's in a failure state log the error(s) and exit.
1235  void operator()(Error Err) const { checkError(std::move(Err)); }
1236 
1237  /// Check E. If it's in a success state then return the contained value. If
1238  /// it's in a failure state log the error(s) and exit.
1239  template <typename T> T operator()(Expected<T> &&E) const {
1240    checkError(E.takeError());
1241    return std::move(*E);
1242  }
1243 
1244  /// Check E. If it's in a success state then return the contained reference. If
1245  /// it's in a failure state log the error(s) and exit.
1246  template <typename T> T& operator()(Expected<T&> &&E) const {
1247    checkError(E.takeError());
1248    return *E;
1249  }
1250 
1251private:
1252  void checkError(Error Err) const {
1253    if (Err) {
1254      int ExitCode = GetExitCode(Err);
1255      logAllUnhandledErrors(std::move(Err), errs(), Banner);
1256      exit(ExitCode);
1257    }
1258  }
1259 
1260  std::string Banner;
1261  std::function<int(const Error &)> GetExitCode;
1262};
1263 
1264/// Conversion from Error to LLVMErrorRef for C error bindings.
1265inline LLVMErrorRef wrap(Error Err) {
1266  return reinterpret_cast<LLVMErrorRef>(Err.takePayload().release());
1267}
1268 
1269/// Conversion from LLVMErrorRef to Error for C error bindings.
1270inline Error unwrap(LLVMErrorRef ErrRef) {
1271  return Error(std::unique_ptr<ErrorInfoBase>(
1272      reinterpret_cast<ErrorInfoBase *>(ErrRef)));
1273}
1274 
1275} // end namespace llvm
1276 
1277#endif // LLVM_SUPPORT_ERROR_H

←

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