/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/WindowsManifest/WindowsManifestMerger.cpp

Bug Summary

File:	llvm/lib/WindowsManifest/WindowsManifestMerger.cpp
Warning:	line 609, column 18 Access to field 'next' results in a dereference of an undefined pointer value (loaded from variable 'Prev')

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name WindowsManifestMerger.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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/WindowsManifest -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -isystem /usr/include/libxml2 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/WindowsManifest -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/WindowsManifest -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/WindowsManifest -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-08-28-193554-24367-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/WindowsManifest/WindowsManifestMerger.cpp

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/WindowsManifest/WindowsManifestMerger.cpp

→

1//===-- WindowsManifestMerger.cpp ------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===---------------------------------------------------------------------===//
8//
9// This file implements the .manifest merger class.
10//
11//===---------------------------------------------------------------------===//

13#include "llvm/WindowsManifest/WindowsManifestMerger.h"
14#include "llvm/Config/config.h"
15#include "llvm/Support/MemoryBuffer.h"

17#include <map>

19#if LLVM_ENABLE_LIBXML21
20#include <libxml/xmlreader.h>
21#endif

23#define TO_XML_CHAR(X)reinterpret_cast<const unsigned char *>(X) reinterpret_cast<const unsigned char *>(X)
24#define FROM_XML_CHAR(X)reinterpret_cast<const char *>(X) reinterpret_cast<const char *>(X)

26using namespace llvm;
27using namespace windows_manifest;

29char WindowsManifestError::ID = 0;

31WindowsManifestError::WindowsManifestError(const Twine &Msg) : Msg(Msg.str()) {}

33void WindowsManifestError::log(raw_ostream &OS) const { OS << Msg; }

35class WindowsManifestMerger::WindowsManifestMergerImpl {
36public:
~WindowsManifestMergerImpl();
Error merge(MemoryBufferRef Manifest);
std::unique_ptr<MemoryBuffer> getMergedManifest();

41private:
static void errorCallback(void *Ctx, const char *Format, ...);
Error getParseError();
44#if LLVM_ENABLE_LIBXML21
xmlDocPtr CombinedDoc = nullptr;
std::vector<xmlDocPtr> MergedDocs;

bool Merged = false;
struct XmlDeleter {
  void operator()(xmlChar *Ptr) { xmlFree(Ptr); }
  void operator()(xmlDoc *Ptr) { xmlFreeDoc(Ptr); }
};
int BufferSize = 0;
std::unique_ptr<xmlChar, XmlDeleter> Buffer;
55#endif
bool ParseErrorOccurred = false;
57};

59#if LLVM_ENABLE_LIBXML21

61static constexpr std::pair<StringLiteral, StringLiteral> MtNsHrefsPrefixes[] = {
  {"urn:schemas-microsoft-com:asm.v1", "ms_asmv1"},
  {"urn:schemas-microsoft-com:asm.v2", "ms_asmv2"},
  {"urn:schemas-microsoft-com:asm.v3", "ms_asmv3"},
  {"http://schemas.microsoft.com/SMI/2005/WindowsSettings",
   "ms_windowsSettings"},
  {"urn:schemas-microsoft-com:compatibility.v1", "ms_compatibilityv1"}};

69static bool xmlStringsEqual(const unsigned char *A, const unsigned char *B) {
// Handle null pointers.  Comparison of 2 null pointers returns true because
// this indicates the prefix of a default namespace.
if (!A || !B)
  return A == B;
return strcmp(FROM_XML_CHAR(A)reinterpret_cast<const char *>(A), FROM_XML_CHAR(B)reinterpret_cast<const char *>(B)) == 0;
75}

77static bool isMergeableElement(const unsigned char *ElementName) {
for (StringRef S : {"application", "assembly", "assemblyIdentity",
                    "compatibility", "noInherit", "requestedExecutionLevel",
                    "requestedPrivileges", "security", "trustInfo"}) {
  if (S == FROM_XML_CHAR(ElementName)reinterpret_cast<const char *>(ElementName)) {
    return true;
  }
}
return false;
86}

88static xmlNodePtr getChildWithName(xmlNodePtr Parent,
                                 const unsigned char *ElementName) {
for (xmlNodePtr Child = Parent->children; Child; Child = Child->next) {
  if (xmlStringsEqual(Child->name, ElementName)) {
    return Child;
  }
}
return nullptr;
96}

98static xmlAttrPtr getAttribute(xmlNodePtr Node,
                             const unsigned char *AttributeName) {
for (xmlAttrPtr Attribute = Node->properties; Attribute != nullptr;
     Attribute = Attribute->next) {
  if (xmlStringsEqual(Attribute->name, AttributeName)) {
    return Attribute;
  }
}
return nullptr;
107}

109// Check if namespace specified by HRef1 overrides that of HRef2.
110static bool namespaceOverrides(const unsigned char *HRef1,
                             const unsigned char *HRef2) {
auto HRef1Position = llvm::find_if(
    MtNsHrefsPrefixes, [=](const std::pair<StringRef, StringRef> &Element) {
      return xmlStringsEqual(HRef1, TO_XML_CHAR(Element.first.data())reinterpret_cast<const unsigned char *>(Element.first.data
()));
    });
auto HRef2Position = llvm::find_if(
    MtNsHrefsPrefixes, [=](const std::pair<StringRef, StringRef> &Element) {
      return xmlStringsEqual(HRef2, TO_XML_CHAR(Element.first.data())reinterpret_cast<const unsigned char *>(Element.first.data
()));
    });
return HRef1Position < HRef2Position;
121}

123// Search for prefix-defined namespace specified by HRef, starting on Node and
124// continuing recursively upwards.  Returns the namespace or nullptr if not
125// found.
126static xmlNsPtr search(const unsigned char *HRef, xmlNodePtr Node) {
for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
  if (Def->prefix && xmlStringsEqual(Def->href, HRef)) {
    return Def;
  }
}
if (Node->parent) {
  return search(HRef, Node->parent);
}
return nullptr;
136}

138// Return the prefix that corresponds to the HRef.  If HRef is not a recognized
139// URI, then just return the HRef itself to use as the prefix.
140static const unsigned char *getPrefixForHref(const unsigned char *HRef) {
for (auto &Ns : MtNsHrefsPrefixes) {
  if (xmlStringsEqual(HRef, TO_XML_CHAR(Ns.first.data())reinterpret_cast<const unsigned char *>(Ns.first.data()
))) {
    return TO_XML_CHAR(Ns.second.data())reinterpret_cast<const unsigned char *>(Ns.second.data(
));
  }
}
return HRef;
147}

149// Search for prefix-defined namespace specified by HRef, starting on Node and
150// continuing recursively upwards.  If it is found, then return it.  If it is
151// not found, then prefix-define that namespace on the node and return a
152// reference to it.
153static Expected<xmlNsPtr> searchOrDefine(const unsigned char *HRef,
                                       xmlNodePtr Node) {
if (xmlNsPtr Def = search(HRef, Node))
  return Def;
if (xmlNsPtr Def = xmlNewNs(Node, HRef, getPrefixForHref(HRef)))
  return Def;
return make_error<WindowsManifestError>("failed to create new namespace");
160}

162// Set the namespace of OrigionalAttribute on OriginalNode to be that of
163// AdditionalAttribute's.
164static Error copyAttributeNamespace(xmlAttrPtr OriginalAttribute,
                                  xmlNodePtr OriginalNode,
                                  xmlAttrPtr AdditionalAttribute) {

Expected<xmlNsPtr> ExplicitOrError =
    searchOrDefine(AdditionalAttribute->ns->href, OriginalNode);
if (!ExplicitOrError)
  return ExplicitOrError.takeError();
OriginalAttribute->ns = std::move(ExplicitOrError.get());
return Error::success();
174}

176// Return the corresponding namespace definition for the prefix, defined on the
177// given Node.  Returns nullptr if there is no such definition.
178static xmlNsPtr getNamespaceWithPrefix(const unsigned char *Prefix,
                                     xmlNodePtr Node) {
if (Node == nullptr)
  return nullptr;
for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
  if (xmlStringsEqual(Def->prefix, Prefix)) {
    return Def;
  }
}
return nullptr;
188}

190// Search for the closest inheritable default namespace, starting on (and
191// including) the Node and traveling upwards through parent nodes.  Returns
192// nullptr if there are no inheritable default namespaces.
193static xmlNsPtr getClosestDefault(xmlNodePtr Node) {
if (xmlNsPtr Ret = getNamespaceWithPrefix(nullptr, Node))
  return Ret;
if (Node->parent == nullptr)
  return nullptr;
return getClosestDefault(Node->parent);
199}

201// Merge the attributes of AdditionalNode into OriginalNode.  If attributes
202// with identical types are present, they are not duplicated but rather if
203// their values are not consistent and error is thrown.  In addition, the
204// higher priority namespace is used for each attribute, EXCEPT in the case
205// of merging two default namespaces and the lower priority namespace
206// definition occurs closer than the higher priority one.
207static Error mergeAttributes(xmlNodePtr OriginalNode,
                           xmlNodePtr AdditionalNode) {
xmlNsPtr ClosestDefault = getClosestDefault(OriginalNode);
for (xmlAttrPtr Attribute = AdditionalNode->properties; Attribute;
     Attribute = Attribute->next) {
  if (xmlAttrPtr OriginalAttribute =
          getAttribute(OriginalNode, Attribute->name)) {
    if (!xmlStringsEqual(OriginalAttribute->children->content,
                         Attribute->children->content)) {
      return make_error<WindowsManifestError>(
          Twine("conflicting attributes for ") +
          FROM_XML_CHAR(OriginalNode->name)reinterpret_cast<const char *>(OriginalNode->name));
    }
    if (!Attribute->ns) {
      continue;
    }
    if (!OriginalAttribute->ns) {
      if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
                                          Attribute)) {
        return E;
      }
      continue;
    }
    if (namespaceOverrides(OriginalAttribute->ns->href,
                           Attribute->ns->href)) {
      // In this case, the original attribute has a higher priority namespace
      // than the incomiing attribute, however the namespace definition of
      // the lower priority namespace occurs first traveling upwards in the
      // tree.  Therefore the lower priority namespace is applied.
      if (!OriginalAttribute->ns->prefix && !Attribute->ns->prefix &&
          ClosestDefault &&
          xmlStringsEqual(Attribute->ns->href, ClosestDefault->href)) {
        if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
                                            Attribute)) {
          return E;
        }
        continue;
      }
      continue;
      // This covers the case where the incoming attribute has the higher
      // priority.  The higher priority namespace is applied in all cases
      // EXCEPT when both of the namespaces are default inherited, and the
      // closest inherited default is the lower priority one.
    }
    if (Attribute->ns->prefix || OriginalAttribute->ns->prefix ||
        (ClosestDefault && !xmlStringsEqual(OriginalAttribute->ns->href,
                                            ClosestDefault->href))) {
      if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
                                          Attribute)) {
        return E;
      }
      continue;
    }
    continue;
  }
  // If the incoming attribute is not already found on the node, append it
  // to the end of the properties list.  Also explicitly apply its
  // namespace as a prefix because it might be contained in a separate
  // namespace that doesn't use the attribute.
  xmlAttrPtr NewProp =
      xmlNewProp(OriginalNode, Attribute->name, Attribute->children->content);
  Expected<xmlNsPtr> ExplicitOrError =
      searchOrDefine(Attribute->ns->href, OriginalNode);
  if (!ExplicitOrError)
    return ExplicitOrError.takeError();
  NewProp->ns = std::move(ExplicitOrError.get());
}
return Error::success();
275}

277// Given two nodes, return the one with the higher priority namespace.
278static xmlNodePtr getDominantNode(xmlNodePtr Node1, xmlNodePtr Node2) {

if (!Node1 || !Node1->ns)
  return Node2;
if (!Node2 || !Node2->ns)
  return Node1;
if (namespaceOverrides(Node1->ns->href, Node2->ns->href))
  return Node1;
return Node2;
287}

289// Checks if this Node's namespace is inherited or one it defined itself.
290static bool hasInheritedNs(xmlNodePtr Node) {
return Node->ns && Node->ns != getNamespaceWithPrefix(Node->ns->prefix, Node);
292}

294// Check if this Node's namespace is a default namespace that it inherited, as
295// opposed to defining itself.
296static bool hasInheritedDefaultNs(xmlNodePtr Node) {
return hasInheritedNs(Node) && Node->ns->prefix == nullptr;
298}

300// Check if this Node's namespace is a default namespace it defined itself.
301static bool hasDefinedDefaultNamespace(xmlNodePtr Node) {
return Node->ns && (Node->ns == getNamespaceWithPrefix(nullptr, Node));
303}

305// For the given explicit prefix-definition of a namespace, travel downwards
306// from a node recursively, and for every implicit, inherited default usage of
307// that namespace replace it with that explicit prefix use.  This is important
308// when namespace overriding occurs when merging, so that elements unique to a
309// namespace will still stay in that namespace.
310static void explicateNamespace(xmlNsPtr PrefixDef, xmlNodePtr Node) {
// If a node as its own default namespace definition it clearly cannot have
// inherited the given default namespace, and neither will any of its
// children.
if (hasDefinedDefaultNamespace(Node))
  return;
if (Node->ns && xmlStringsEqual(Node->ns->href, PrefixDef->href) &&
    hasInheritedDefaultNs(Node))
  Node->ns = PrefixDef;
for (xmlAttrPtr Attribute = Node->properties; Attribute;
     Attribute = Attribute->next) {
  if (Attribute->ns &&
      xmlStringsEqual(Attribute->ns->href, PrefixDef->href)) {
    Attribute->ns = PrefixDef;
  }
}
for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
  explicateNamespace(PrefixDef, Child);
}
329}

331// Perform the namespace merge between two nodes.
332static Error mergeNamespaces(xmlNodePtr OriginalNode,
                           xmlNodePtr AdditionalNode) {
// Save the original default namespace definition in case the incoming node
// overrides it.
const unsigned char *OriginalDefinedDefaultHref = nullptr;
if (xmlNsPtr OriginalDefinedDefaultNs =
        getNamespaceWithPrefix(nullptr, OriginalNode)) {
  OriginalDefinedDefaultHref = xmlStrdup(OriginalDefinedDefaultNs->href);
}
const unsigned char *NewDefinedDefaultHref = nullptr;
// Copy all namespace definitions.  There can only be one default namespace
// definition per node, so the higher priority one takes precedence in the
// case of collision.
for (xmlNsPtr Def = AdditionalNode->nsDef; Def; Def = Def->next) {
  if (xmlNsPtr OriginalNsDef =
          getNamespaceWithPrefix(Def->prefix, OriginalNode)) {
    if (!Def->prefix) {
      if (namespaceOverrides(Def->href, OriginalNsDef->href)) {
        NewDefinedDefaultHref = TO_XML_CHAR(strdup(FROM_XML_CHAR(Def->href)))reinterpret_cast<const unsigned char *>(strdup(reinterpret_cast
<const char *>(Def->href)));
      }
    } else if (!xmlStringsEqual(OriginalNsDef->href, Def->href)) {
      return make_error<WindowsManifestError>(
          Twine("conflicting namespace definitions for ") +
          FROM_XML_CHAR(Def->prefix)reinterpret_cast<const char *>(Def->prefix));
    }
  } else {
    xmlNsPtr NewDef = xmlCopyNamespace(Def);
    NewDef->next = OriginalNode->nsDef;
    OriginalNode->nsDef = NewDef;
  }
}

// Check whether the original node or the incoming node has the higher
// priority namespace.  Depending on which one is dominant, we will have
// to recursively apply namespace changes down to children of the original
// node.
xmlNodePtr DominantNode = getDominantNode(OriginalNode, AdditionalNode);
xmlNodePtr NonDominantNode =
    DominantNode == OriginalNode ? AdditionalNode : OriginalNode;
if (DominantNode == OriginalNode) {
  if (OriginalDefinedDefaultHref) {
    xmlNsPtr NonDominantDefinedDefault =
        getNamespaceWithPrefix(nullptr, NonDominantNode);
    // In this case, both the nodes defined a default namespace.  However
    // the lower priority node ended up having a higher priority default
    // definition.  This can occur if the higher priority node is prefix
    // namespace defined.  In this case we have to define an explicit
    // prefix for the overridden definition and apply it to all children
    // who relied on that definition.
    if (NonDominantDefinedDefault &&
        namespaceOverrides(NonDominantDefinedDefault->href,
                           OriginalDefinedDefaultHref)) {
      Expected<xmlNsPtr> EC =
          searchOrDefine(OriginalDefinedDefaultHref, DominantNode);
      if (!EC) {
        return EC.takeError();
      }
      xmlNsPtr PrefixDominantDefinedDefault = std::move(EC.get());
      explicateNamespace(PrefixDominantDefinedDefault, DominantNode);
    }
    // In this case the node with a higher priority namespace did not have a
    // default namespace definition, but the lower priority node did.  In this
    // case the new default namespace definition is copied.  A side effect of
    // this is that all children will suddenly find themselves in a different
    // default namespace.  To maintain correctness we need to ensure that all
    // children now explicitly refer to the namespace that they had previously
    // implicitly inherited.
  } else if (getNamespaceWithPrefix(nullptr, NonDominantNode)) {
    if (DominantNode->parent) {
      xmlNsPtr ClosestDefault = getClosestDefault(DominantNode->parent);
      Expected<xmlNsPtr> EC =
          searchOrDefine(ClosestDefault->href, DominantNode);
      if (!EC) {
        return EC.takeError();
      }
      xmlNsPtr ExplicitDefault = std::move(EC.get());
      explicateNamespace(ExplicitDefault, DominantNode);
    }
  }
} else {
  // Covers case where the incoming node has a default namespace definition
  // that overrides the original node's namespace.  This always leads to
  // the original node receiving that new default namespace.
  if (hasDefinedDefaultNamespace(DominantNode)) {
    NonDominantNode->ns = getNamespaceWithPrefix(nullptr, NonDominantNode);
  } else {
    // This covers the case where the incoming node either has a prefix
    // namespace, or an inherited default namespace.  Since the namespace
    // may not yet be defined in the original tree we do a searchOrDefine
    // for it, and then set the namespace equal to it.
    Expected<xmlNsPtr> EC =
        searchOrDefine(DominantNode->ns->href, NonDominantNode);
    if (!EC) {
      return EC.takeError();
    }
    xmlNsPtr Explicit = std::move(EC.get());
    NonDominantNode->ns = Explicit;
  }
  // This covers cases where the incoming dominant node HAS a default
  // namespace definition, but MIGHT NOT NECESSARILY be in that namespace.
  if (xmlNsPtr DominantDefaultDefined =
          getNamespaceWithPrefix(nullptr, DominantNode)) {
    if (OriginalDefinedDefaultHref) {
      if (namespaceOverrides(DominantDefaultDefined->href,
                             OriginalDefinedDefaultHref)) {
        // In this case, the incoming node's default definition overrides
        // the original default definition, all children who relied on that
        // definition must be updated accordingly.
        Expected<xmlNsPtr> EC =
            searchOrDefine(OriginalDefinedDefaultHref, NonDominantNode);
        if (!EC) {
          return EC.takeError();
        }
        xmlNsPtr ExplicitDefault = std::move(EC.get());
        explicateNamespace(ExplicitDefault, NonDominantNode);
      }
    } else {
      // The original did not define a default definition, however the new
      // default definition still applies to all children, so they must be
      // updated to explicitly refer to the namespace they had previously
      // been inheriting implicitly.
      xmlNsPtr ClosestDefault = getClosestDefault(NonDominantNode);
      Expected<xmlNsPtr> EC =
          searchOrDefine(ClosestDefault->href, NonDominantNode);
      if (!EC) {
        return EC.takeError();
      }
      xmlNsPtr ExplicitDefault = std::move(EC.get());
      explicateNamespace(ExplicitDefault, NonDominantNode);
    }
  }
}
if (NewDefinedDefaultHref) {
  xmlNsPtr OriginalNsDef = getNamespaceWithPrefix(nullptr, OriginalNode);
  xmlFree(const_cast<unsigned char *>(OriginalNsDef->href));
  OriginalNsDef->href = NewDefinedDefaultHref;
}
xmlFree(const_cast<unsigned char *>(OriginalDefinedDefaultHref));
return Error::success();
471}

473static bool isRecognizedNamespace(const unsigned char *NsHref) {
for (auto &Ns : MtNsHrefsPrefixes) {
  if (xmlStringsEqual(NsHref, TO_XML_CHAR(Ns.first.data())reinterpret_cast<const unsigned char *>(Ns.first.data()
))) {
    return true;
  }
}
return false;
480}

482static bool hasRecognizedNamespace(xmlNodePtr Node) {
return isRecognizedNamespace(Node->ns->href);
484}

486// Ensure a node's inherited namespace is actually defined in the tree it
487// resides in.
488static Error reconcileNamespaces(xmlNodePtr Node) {
if (!Node) {
  return Error::success();
}
if (hasInheritedNs(Node)) {
  Expected<xmlNsPtr> ExplicitOrError = searchOrDefine(Node->ns->href, Node);
  if (!ExplicitOrError) {
    return ExplicitOrError.takeError();
  }
  xmlNsPtr Explicit = std::move(ExplicitOrError.get());
  Node->ns = Explicit;
}
for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
  if (auto E = reconcileNamespaces(Child)) {
    return E;
  }
}
return Error::success();
506}

508// Recursively merge the two given manifest trees, depending on which elements
509// are of a mergeable type, and choose namespaces according to which have
510// higher priority.
511static Error treeMerge(xmlNodePtr OriginalRoot, xmlNodePtr AdditionalRoot) {
if (auto E = mergeAttributes(OriginalRoot, AdditionalRoot))
  return E;
if (auto E = mergeNamespaces(OriginalRoot, AdditionalRoot))
  return E;
xmlNodePtr AdditionalFirstChild = AdditionalRoot->children;
xmlNode StoreNext;
for (xmlNodePtr Child = AdditionalFirstChild; Child; Child = Child->next) {
  xmlNodePtr OriginalChildWithName;
  if (!isMergeableElement(Child->name) ||
      !(OriginalChildWithName =
            getChildWithName(OriginalRoot, Child->name)) ||
      !hasRecognizedNamespace(Child)) {
    StoreNext.next = Child->next;
    xmlUnlinkNode(Child);
    if (!xmlAddChild(OriginalRoot, Child)) {
      return make_error<WindowsManifestError>(Twine("could not merge ") +
                                              FROM_XML_CHAR(Child->name)reinterpret_cast<const char *>(Child->name));
    }
    if (auto E = reconcileNamespaces(Child)) {
      return E;
    }
    Child = &StoreNext;
  } else if (auto E = treeMerge(OriginalChildWithName, Child)) {
    return E;
  }
}
return Error::success();
539}

541static void stripComments(xmlNodePtr Root) {
xmlNode StoreNext;
for (xmlNodePtr Child = Root->children; Child; Child = Child->next) {
  if (!xmlStringsEqual(Child->name, TO_XML_CHAR("comment")reinterpret_cast<const unsigned char *>("comment"))) {
    stripComments(Child);
    continue;
  }
  StoreNext.next = Child->next;
  xmlNodePtr Remove = Child;
  Child = &StoreNext;
  xmlUnlinkNode(Remove);
  xmlFreeNode(Remove);
}
554}

556// libxml2 assumes that attributes do not inherit default namespaces, whereas
557// the original  mt.exe does make this assumption.  This function reconciles
558// this by setting all attributes to have the inherited default namespace.
559static void setAttributeNamespaces(xmlNodePtr Node) {
for (xmlAttrPtr Attribute = Node->properties; Attribute;
     Attribute = Attribute->next) {
  if (!Attribute->ns) {
    Attribute->ns = getClosestDefault(Node);
  }
}
for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
  setAttributeNamespaces(Child);
}
569}

571// The merging process may create too many prefix defined namespaces.  This
572// function removes all unnecessary ones from the tree.
573static void checkAndStripPrefixes(xmlNodePtr Node,
                                std::vector<xmlNsPtr> &RequiredPrefixes) {
for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
7
←
Loop condition is true.  Entering loop body→
9
←
Loop condition is true.  Entering loop body→
11
←
Loop condition is true.  Entering loop body→
  checkAndStripPrefixes(Child, RequiredPrefixes);
8
←
Calling 'checkAndStripPrefixes'→
10
←
Calling 'checkAndStripPrefixes'→
12
←
Calling 'checkAndStripPrefixes'→
}
if (Node->ns && Node->ns->prefix != nullptr) {
13
←
Assuming field 'ns' is null→
  xmlNsPtr ClosestDefault = getClosestDefault(Node);
  if (ClosestDefault &&
      xmlStringsEqual(ClosestDefault->href, Node->ns->href)) {
    Node->ns = ClosestDefault;
  } else if (!llvm::is_contained(RequiredPrefixes, Node->ns)) {
    RequiredPrefixes.push_back(Node->ns);
  }
}
for (xmlAttrPtr Attribute = Node->properties; Attribute;
14
←
Loop condition is false. Execution continues on line 599→
     Attribute = Attribute->next) {
  if (Attribute->ns && Attribute->ns->prefix != nullptr) {
    xmlNsPtr ClosestDefault = getClosestDefault(Node);
    if (ClosestDefault &&
        xmlStringsEqual(ClosestDefault->href, Attribute->ns->href)) {
      Attribute->ns = ClosestDefault;
    } else if (!llvm::is_contained(RequiredPrefixes, Node->ns)) {
      RequiredPrefixes.push_back(Attribute->ns);
    }
  }
}
xmlNsPtr Prev;
15
←
'Prev' declared without an initial value→
xmlNs Temp;
for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
  if (!Def->prefix || llvm::is_contained(RequiredPrefixes, Def)) {
16
←
Assuming field 'prefix' is non-null→
17
←
Calling 'is_contained<std::vector<_xmlNs *> &, _xmlNs *>'→
23
←
Returning from 'is_contained<std::vector<_xmlNs *> &, _xmlNs *>'→
24
←
Taking false branch→
    Prev = Def;
    continue;
  }
  if (Def == Node->nsDef) {
25
←
Assuming 'Def' is not equal to field 'nsDef'→
26
←
Taking false branch→
    Node->nsDef = Def->next;
  } else {
    Prev->next = Def->next;
27
←
Access to field 'next' results in a dereference of an undefined pointer value (loaded from variable 'Prev')
  }
  Temp.next = Def->next;
  xmlFreeNs(Def);
  Def = &Temp;
}
615}

617WindowsManifestMerger::WindowsManifestMergerImpl::~WindowsManifestMergerImpl() {
for (auto &Doc : MergedDocs)
  xmlFreeDoc(Doc);
620}

622Error WindowsManifestMerger::WindowsManifestMergerImpl::merge(
  MemoryBufferRef Manifest) {
if (Merged)
  return make_error<WindowsManifestError>(
      "merge after getMergedManifest is not supported");
if (Manifest.getBufferSize() == 0)
  return make_error<WindowsManifestError>(
      "attempted to merge empty manifest");
xmlSetGenericErrorFunc((void *)this,
                       WindowsManifestMergerImpl::errorCallback);
xmlDocPtr ManifestXML = xmlReadMemory(
    Manifest.getBufferStart(), Manifest.getBufferSize(), "manifest.xml",
    nullptr, XML_PARSE_NOBLANKS | XML_PARSE_NODICT);
xmlSetGenericErrorFunc(nullptr, nullptr);
if (auto E = getParseError())
  return E;
xmlNodePtr AdditionalRoot = xmlDocGetRootElement(ManifestXML);
stripComments(AdditionalRoot);
setAttributeNamespaces(AdditionalRoot);
if (CombinedDoc == nullptr) {
  CombinedDoc = ManifestXML;
} else {
  xmlNodePtr CombinedRoot = xmlDocGetRootElement(CombinedDoc);
  if (!xmlStringsEqual(CombinedRoot->name, AdditionalRoot->name) ||
      !isMergeableElement(AdditionalRoot->name) ||
      !hasRecognizedNamespace(AdditionalRoot)) {
    return make_error<WindowsManifestError>("multiple root nodes");
  }
  if (auto E = treeMerge(CombinedRoot, AdditionalRoot)) {
    return E;
  }
}
MergedDocs.push_back(ManifestXML);
return Error::success();
656}

658std::unique_ptr<MemoryBuffer>
659WindowsManifestMerger::WindowsManifestMergerImpl::getMergedManifest() {
if (!Merged) {
2
←
Assuming field 'Merged' is false→
3
←
Taking true branch→
  Merged = true;

  if (!CombinedDoc)
4
←
Assuming field 'CombinedDoc' is non-null→
5
←
Taking false branch→
    return nullptr;

  xmlNodePtr CombinedRoot = xmlDocGetRootElement(CombinedDoc);
  std::vector<xmlNsPtr> RequiredPrefixes;
  checkAndStripPrefixes(CombinedRoot, RequiredPrefixes);
6
←
Calling 'checkAndStripPrefixes'→
  std::unique_ptr<xmlDoc, XmlDeleter> OutputDoc(
      xmlNewDoc((const unsigned char *)"1.0"));
  xmlDocSetRootElement(OutputDoc.get(), CombinedRoot);
  assert(0 == xmlDocGetRootElement(CombinedDoc))(static_cast <bool> (0 == xmlDocGetRootElement(CombinedDoc
)) ? void (0) : __assert_fail ("0 == xmlDocGetRootElement(CombinedDoc)"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/WindowsManifest/WindowsManifestMerger.cpp"
, 672, __extension__ __PRETTY_FUNCTION__));

  xmlKeepBlanksDefault(0);
  xmlChar *Buff = nullptr;
  xmlDocDumpFormatMemoryEnc(OutputDoc.get(), &Buff, &BufferSize, "UTF-8", 1);
  Buffer.reset(Buff);
}

return BufferSize ? MemoryBuffer::getMemBufferCopy(StringRef(
                        FROM_XML_CHAR(Buffer.get())reinterpret_cast<const char *>(Buffer.get()), (size_t)BufferSize))
                  : nullptr;
683}

685bool windows_manifest::isAvailable() { return true; }

687#else

689WindowsManifestMerger::WindowsManifestMergerImpl::~WindowsManifestMergerImpl() {
690}

692Error WindowsManifestMerger::WindowsManifestMergerImpl::merge(
  MemoryBufferRef Manifest) {
return make_error<WindowsManifestError>("no libxml2");
695}

697std::unique_ptr<MemoryBuffer>
698WindowsManifestMerger::WindowsManifestMergerImpl::getMergedManifest() {
return nullptr;
700}

702bool windows_manifest::isAvailable() { return false; }

704#endif

706WindowsManifestMerger::WindowsManifestMerger()
  : Impl(std::make_unique<WindowsManifestMergerImpl>()) {}

709WindowsManifestMerger::~WindowsManifestMerger() {}

711Error WindowsManifestMerger::merge(MemoryBufferRef Manifest) {
return Impl->merge(Manifest);
713}

715std::unique_ptr<MemoryBuffer> WindowsManifestMerger::getMergedManifest() {
return Impl->getMergedManifest();
1
Calling 'WindowsManifestMergerImpl::getMergedManifest'→
717}

719void WindowsManifestMerger::WindowsManifestMergerImpl::errorCallback(
  void *Ctx, const char *Format, ...) {
auto *Merger = (WindowsManifestMergerImpl *)Ctx;
Merger->ParseErrorOccurred = true;
723}

725Error WindowsManifestMerger::WindowsManifestMergerImpl::getParseError() {
if (!ParseErrorOccurred)
  return Error::success();
return make_error<WindowsManifestError>("invalid xml document");
729}

←

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h

→

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some templates that are useful if you are working with the
10// STL at all.
11//
12// No library is required when using these functions.
13//
14//===----------------------------------------------------------------------===//
15 
16#ifndef LLVM_ADT_STLEXTRAS_H
17#define LLVM_ADT_STLEXTRAS_H
18 
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLForwardCompat.h"
21#include "llvm/ADT/iterator.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Config/abi-breaking.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38 
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42 
43namespace llvm {
44 
45// Only used by compiler if both template types are the same.  Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48 
49namespace detail {
50 
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53 
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56    *std::begin(std::declval<RangeT &>()))>::type;
57 
58} // end namespace detail
59 
60//===----------------------------------------------------------------------===//
61//     Extra additions to <type_traits>
62//===----------------------------------------------------------------------===//
63 
64template <typename T> struct make_const_ptr {
65  using type =
66      typename std::add_pointer<typename std::add_const<T>::type>::type;
67};
68 
69template <typename T> struct make_const_ref {
70  using type = typename std::add_lvalue_reference<
71      typename std::add_const<T>::type>::type;
72};
73 
74namespace detail {
75template <typename...> using void_t = void;
76template <class, template <class...> class Op, class... Args> struct detector {
77  using value_t = std::false_type;
78};
79template <template <class...> class Op, class... Args>
80struct detector<void_t<Op<Args...>>, Op, Args...> {
81  using value_t = std::true_type;
82};
83} // end namespace detail
84 
85/// Detects if a given trait holds for some set of arguments 'Args'.
86/// For example, the given trait could be used to detect if a given type
87/// has a copy assignment operator:
88///   template<class T>
89///   using has_copy_assign_t = decltype(std::declval<T&>()
90///                                                 = std::declval<const T&>());
91///   bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
92template <template <class...> class Op, class... Args>
93using is_detected = typename detail::detector<void, Op, Args...>::value_t;
94 
95namespace detail {
96template <typename Callable, typename... Args>
97using is_invocable =
98    decltype(std::declval<Callable &>()(std::declval<Args>()...));
99} // namespace detail
100 
101/// Check if a Callable type can be invoked with the given set of arg types.
102template <typename Callable, typename... Args>
103using is_invocable = is_detected<detail::is_invocable, Callable, Args...>;
104 
105/// This class provides various trait information about a callable object.
106///   * To access the number of arguments: Traits::num_args
107///   * To access the type of an argument: Traits::arg_t<Index>
108///   * To access the type of the result:  Traits::result_t
109template <typename T, bool isClass = std::is_class<T>::value>
110struct function_traits : public function_traits<decltype(&T::operator())> {};
111 
112/// Overload for class function types.
113template <typename ClassType, typename ReturnType, typename... Args>
114struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
115  /// The number of arguments to this function.
116  enum { num_args = sizeof...(Args) };
117 
118  /// The result type of this function.
119  using result_t = ReturnType;
120 
121  /// The type of an argument to this function.
122  template <size_t Index>
123  using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
124};
125/// Overload for class function types.
126template <typename ClassType, typename ReturnType, typename... Args>
127struct function_traits<ReturnType (ClassType::*)(Args...), false>
128    : function_traits<ReturnType (ClassType::*)(Args...) const> {};
129/// Overload for non-class function types.
130template <typename ReturnType, typename... Args>
131struct function_traits<ReturnType (*)(Args...), false> {
132  /// The number of arguments to this function.
133  enum { num_args = sizeof...(Args) };
134 
135  /// The result type of this function.
136  using result_t = ReturnType;
137 
138  /// The type of an argument to this function.
139  template <size_t i>
140  using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
141};
142/// Overload for non-class function type references.
143template <typename ReturnType, typename... Args>
144struct function_traits<ReturnType (&)(Args...), false>
145    : public function_traits<ReturnType (*)(Args...)> {};
146 
147//===----------------------------------------------------------------------===//
148//     Extra additions to <functional>
149//===----------------------------------------------------------------------===//
150 
151template <class Ty> struct identity {
152  using argument_type = Ty;
153 
154  Ty &operator()(Ty &self) const {
155    return self;
156  }
157  const Ty &operator()(const Ty &self) const {
158    return self;
159  }
160};
161 
162/// An efficient, type-erasing, non-owning reference to a callable. This is
163/// intended for use as the type of a function parameter that is not used
164/// after the function in question returns.
165///
166/// This class does not own the callable, so it is not in general safe to store
167/// a function_ref.
168template<typename Fn> class function_ref;
169 
170template<typename Ret, typename ...Params>
171class function_ref<Ret(Params...)> {
172  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
173  intptr_t callable;
174 
175  template<typename Callable>
176  static Ret callback_fn(intptr_t callable, Params ...params) {
177    return (*reinterpret_cast<Callable*>(callable))(
178        std::forward<Params>(params)...);
179  }
180 
181public:
182  function_ref() = default;
183  function_ref(std::nullptr_t) {}
184 
185  template <typename Callable>
186  function_ref(
187      Callable &&callable,
188      // This is not the copy-constructor.
189      std::enable_if_t<!std::is_same<remove_cvref_t<Callable>,
190                                     function_ref>::value> * = nullptr,
191      // Functor must be callable and return a suitable type.
192      std::enable_if_t<std::is_void<Ret>::value ||
193                       std::is_convertible<decltype(std::declval<Callable>()(
194                                               std::declval<Params>()...)),
195                                           Ret>::value> * = nullptr)
196      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
197        callable(reinterpret_cast<intptr_t>(&callable)) {}
198 
199  Ret operator()(Params ...params) const {
200    return callback(callable, std::forward<Params>(params)...);
201  }
202 
203  explicit operator bool() const { return callback; }
204};
205 
206//===----------------------------------------------------------------------===//
207//     Extra additions to <iterator>
208//===----------------------------------------------------------------------===//
209 
210namespace adl_detail {
211 
212using std::begin;
213 
214template <typename ContainerTy>
215decltype(auto) adl_begin(ContainerTy &&container) {
216  return begin(std::forward<ContainerTy>(container));
217}
218 
219using std::end;
220 
221template <typename ContainerTy>
222decltype(auto) adl_end(ContainerTy &&container) {
223  return end(std::forward<ContainerTy>(container));
224}
225 
226using std::swap;
227 
228template <typename T>
229void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
230                                                       std::declval<T>()))) {
231  swap(std::forward<T>(lhs), std::forward<T>(rhs));
232}
233 
234} // end namespace adl_detail
235 
236template <typename ContainerTy>
237decltype(auto) adl_begin(ContainerTy &&container) {
238  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
239}
240 
241template <typename ContainerTy>
242decltype(auto) adl_end(ContainerTy &&container) {
243  return adl_detail::adl_end(std::forward<ContainerTy>(container));
244}
245 
246template <typename T>
247void adl_swap(T &&lhs, T &&rhs) noexcept(
248    noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
249  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
250}
251 
252/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
253template <typename T>
254constexpr bool empty(const T &RangeOrContainer) {
255  return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
256}
257 
258/// Returns true if the given container only contains a single element.
259template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
260  auto B = std::begin(C), E = std::end(C);
261  return B != E && std::next(B) == E;
262}
263 
264/// Return a range covering \p RangeOrContainer with the first N elements
265/// excluded.
266template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {
267  return make_range(std::next(adl_begin(RangeOrContainer), N),
268                    adl_end(RangeOrContainer));
269}
270 
271// mapped_iterator - This is a simple iterator adapter that causes a function to
272// be applied whenever operator* is invoked on the iterator.
273 
274template <typename ItTy, typename FuncTy,
275          typename FuncReturnTy =
276            decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
277class mapped_iterator
278    : public iterator_adaptor_base<
279             mapped_iterator<ItTy, FuncTy>, ItTy,
280             typename std::iterator_traits<ItTy>::iterator_category,
281             typename std::remove_reference<FuncReturnTy>::type> {
282public:
283  mapped_iterator(ItTy U, FuncTy F)
284    : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
285 
286  ItTy getCurrent() { return this->I; }
287 
288  FuncReturnTy operator*() const { return F(*this->I); }
289 
290private:
291  FuncTy F;
292};
293 
294// map_iterator - Provide a convenient way to create mapped_iterators, just like
295// make_pair is useful for creating pairs...
296template <class ItTy, class FuncTy>
297inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
298  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
299}
300 
301template <class ContainerTy, class FuncTy>
302auto map_range(ContainerTy &&C, FuncTy F) {
303  return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
304}
305 
306/// Helper to determine if type T has a member called rbegin().
307template <typename Ty> class has_rbegin_impl {
308  using yes = char[1];
309  using no = char[2];
310 
311  template <typename Inner>
312  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
313 
314  template <typename>
315  static no& test(...);
316 
317public:
318  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
319};
320 
321/// Metafunction to determine if T& or T has a member called rbegin().
322template <typename Ty>
323struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
324};
325 
326// Returns an iterator_range over the given container which iterates in reverse.
327// Note that the container must have rbegin()/rend() methods for this to work.
328template <typename ContainerTy>
329auto reverse(ContainerTy &&C,
330             std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
331  return make_range(C.rbegin(), C.rend());
332}
333 
334// Returns a std::reverse_iterator wrapped around the given iterator.
335template <typename IteratorTy>
336std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
337  return std::reverse_iterator<IteratorTy>(It);
338}
339 
340// Returns an iterator_range over the given container which iterates in reverse.
341// Note that the container must have begin()/end() methods which return
342// bidirectional iterators for this to work.
343template <typename ContainerTy>
344auto reverse(ContainerTy &&C,
345             std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
346  return make_range(llvm::make_reverse_iterator(std::end(C)),
347                    llvm::make_reverse_iterator(std::begin(C)));
348}
349 
350/// An iterator adaptor that filters the elements of given inner iterators.
351///
352/// The predicate parameter should be a callable object that accepts the wrapped
353/// iterator's reference type and returns a bool. When incrementing or
354/// decrementing the iterator, it will call the predicate on each element and
355/// skip any where it returns false.
356///
357/// \code
358///   int A[] = { 1, 2, 3, 4 };
359///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
360///   // R contains { 1, 3 }.
361/// \endcode
362///
363/// Note: filter_iterator_base implements support for forward iteration.
364/// filter_iterator_impl exists to provide support for bidirectional iteration,
365/// conditional on whether the wrapped iterator supports it.
366template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
367class filter_iterator_base
368    : public iterator_adaptor_base<
369          filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
370          WrappedIteratorT,
371          typename std::common_type<
372              IterTag, typename std::iterator_traits<
373                           WrappedIteratorT>::iterator_category>::type> {
374  using BaseT = iterator_adaptor_base<
375      filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
376      WrappedIteratorT,
377      typename std::common_type<
378          IterTag, typename std::iterator_traits<
379                       WrappedIteratorT>::iterator_category>::type>;
380 
381protected:
382  WrappedIteratorT End;
383  PredicateT Pred;
384 
385  void findNextValid() {
386    while (this->I != End && !Pred(*this->I))
387      BaseT::operator++();
388  }
389 
390  // Construct the iterator. The begin iterator needs to know where the end
391  // is, so that it can properly stop when it gets there. The end iterator only
392  // needs the predicate to support bidirectional iteration.
393  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
394                       PredicateT Pred)
395      : BaseT(Begin), End(End), Pred(Pred) {
396    findNextValid();
397  }
398 
399public:
400  using BaseT::operator++;
401 
402  filter_iterator_base &operator++() {
403    BaseT::operator++();
404    findNextValid();
405    return *this;
406  }
407};
408 
409/// Specialization of filter_iterator_base for forward iteration only.
410template <typename WrappedIteratorT, typename PredicateT,
411          typename IterTag = std::forward_iterator_tag>
412class filter_iterator_impl
413    : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
414  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
415 
416public:
417  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
418                       PredicateT Pred)
419      : BaseT(Begin, End, Pred) {}
420};
421 
422/// Specialization of filter_iterator_base for bidirectional iteration.
423template <typename WrappedIteratorT, typename PredicateT>
424class filter_iterator_impl<WrappedIteratorT, PredicateT,
425                           std::bidirectional_iterator_tag>
426    : public filter_iterator_base<WrappedIteratorT, PredicateT,
427                                  std::bidirectional_iterator_tag> {
428  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
429                                     std::bidirectional_iterator_tag>;
430  void findPrevValid() {
431    while (!this->Pred(*this->I))
432      BaseT::operator--();
433  }
434 
435public:
436  using BaseT::operator--;
437 
438  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
439                       PredicateT Pred)
440      : BaseT(Begin, End, Pred) {}
441 
442  filter_iterator_impl &operator--() {
443    BaseT::operator--();
444    findPrevValid();
445    return *this;
446  }
447};
448 
449namespace detail {
450 
451template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
452  using type = std::forward_iterator_tag;
453};
454 
455template <> struct fwd_or_bidi_tag_impl<true> {
456  using type = std::bidirectional_iterator_tag;
457};
458 
459/// Helper which sets its type member to forward_iterator_tag if the category
460/// of \p IterT does not derive from bidirectional_iterator_tag, and to
461/// bidirectional_iterator_tag otherwise.
462template <typename IterT> struct fwd_or_bidi_tag {
463  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
464      std::bidirectional_iterator_tag,
465      typename std::iterator_traits<IterT>::iterator_category>::value>::type;
466};
467 
468} // namespace detail
469 
470/// Defines filter_iterator to a suitable specialization of
471/// filter_iterator_impl, based on the underlying iterator's category.
472template <typename WrappedIteratorT, typename PredicateT>
473using filter_iterator = filter_iterator_impl<
474    WrappedIteratorT, PredicateT,
475    typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
476 
477/// Convenience function that takes a range of elements and a predicate,
478/// and return a new filter_iterator range.
479///
480/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
481/// lifetime of that temporary is not kept by the returned range object, and the
482/// temporary is going to be dropped on the floor after the make_iterator_range
483/// full expression that contains this function call.
484template <typename RangeT, typename PredicateT>
485iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
486make_filter_range(RangeT &&Range, PredicateT Pred) {
487  using FilterIteratorT =
488      filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
489  return make_range(
490      FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
491                      std::end(std::forward<RangeT>(Range)), Pred),
492      FilterIteratorT(std::end(std::forward<RangeT>(Range)),
493                      std::end(std::forward<RangeT>(Range)), Pred));
494}
495 
496/// A pseudo-iterator adaptor that is designed to implement "early increment"
497/// style loops.
498///
499/// This is *not a normal iterator* and should almost never be used directly. It
500/// is intended primarily to be used with range based for loops and some range
501/// algorithms.
502///
503/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
504/// somewhere between them. The constraints of these iterators are:
505///
506/// - On construction or after being incremented, it is comparable and
507///   dereferencable. It is *not* incrementable.
508/// - After being dereferenced, it is neither comparable nor dereferencable, it
509///   is only incrementable.
510///
511/// This means you can only dereference the iterator once, and you can only
512/// increment it once between dereferences.
513template <typename WrappedIteratorT>
514class early_inc_iterator_impl
515    : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
516                                   WrappedIteratorT, std::input_iterator_tag> {
517  using BaseT =
518      iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
519                            WrappedIteratorT, std::input_iterator_tag>;
520 
521  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
522 
523protected:
524#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
525  bool IsEarlyIncremented = false;
526#endif
527 
528public:
529  early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
530 
531  using BaseT::operator*;
532  decltype(*std::declval<WrappedIteratorT>()) operator*() {
533#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
534    assert(!IsEarlyIncremented && "Cannot dereference twice!")(static_cast <bool> (!IsEarlyIncremented && "Cannot dereference twice!"
) ? void (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot dereference twice!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 534, __extension__ __PRETTY_FUNCTION__));
535    IsEarlyIncremented = true;
536#endif
537    return *(this->I)++;
538  }
539 
540  using BaseT::operator++;
541  early_inc_iterator_impl &operator++() {
542#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
543    assert(IsEarlyIncremented && "Cannot increment before dereferencing!")(static_cast <bool> (IsEarlyIncremented && "Cannot increment before dereferencing!"
) ? void (0) : __assert_fail ("IsEarlyIncremented && \"Cannot increment before dereferencing!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 543, __extension__ __PRETTY_FUNCTION__));
544    IsEarlyIncremented = false;
545#endif
546    return *this;
547  }
548 
549  friend bool operator==(const early_inc_iterator_impl &LHS,
550                         const early_inc_iterator_impl &RHS) {
551#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
552    assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!")(static_cast <bool> (!LHS.IsEarlyIncremented &&
 "Cannot compare after dereferencing!") ? void (0) : __assert_fail
 ("!LHS.IsEarlyIncremented && \"Cannot compare after dereferencing!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 552, __extension__ __PRETTY_FUNCTION__));
553#endif
554    return (const BaseT &)LHS == (const BaseT &)RHS;
555  }
556};
557 
558/// Make a range that does early increment to allow mutation of the underlying
559/// range without disrupting iteration.
560///
561/// The underlying iterator will be incremented immediately after it is
562/// dereferenced, allowing deletion of the current node or insertion of nodes to
563/// not disrupt iteration provided they do not invalidate the *next* iterator --
564/// the current iterator can be invalidated.
565///
566/// This requires a very exact pattern of use that is only really suitable to
567/// range based for loops and other range algorithms that explicitly guarantee
568/// to dereference exactly once each element, and to increment exactly once each
569/// element.
570template <typename RangeT>
571iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
572make_early_inc_range(RangeT &&Range) {
573  using EarlyIncIteratorT =
574      early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
575  return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
576                    EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
577}
578 
579// forward declarations required by zip_shortest/zip_first/zip_longest
580template <typename R, typename UnaryPredicate>
581bool all_of(R &&range, UnaryPredicate P);
582template <typename R, typename UnaryPredicate>
583bool any_of(R &&range, UnaryPredicate P);
584 
585namespace detail {
586 
587using std::declval;
588 
589// We have to alias this since inlining the actual type at the usage site
590// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
591template<typename... Iters> struct ZipTupleType {
592  using type = std::tuple<decltype(*declval<Iters>())...>;
593};
594 
595template <typename ZipType, typename... Iters>
596using zip_traits = iterator_facade_base<
597    ZipType, typename std::common_type<std::bidirectional_iterator_tag,
598                                       typename std::iterator_traits<
599                                           Iters>::iterator_category...>::type,
600    // ^ TODO: Implement random access methods.
601    typename ZipTupleType<Iters...>::type,
602    typename std::iterator_traits<typename std::tuple_element<
603        0, std::tuple<Iters...>>::type>::difference_type,
604    // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
605    // inner iterators have the same difference_type. It would fail if, for
606    // instance, the second field's difference_type were non-numeric while the
607    // first is.
608    typename ZipTupleType<Iters...>::type *,
609    typename ZipTupleType<Iters...>::type>;
610 
611template <typename ZipType, typename... Iters>
612struct zip_common : public zip_traits<ZipType, Iters...> {
613  using Base = zip_traits<ZipType, Iters...>;
614  using value_type = typename Base::value_type;
615 
616  std::tuple<Iters...> iterators;
617 
618protected:
619  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
620    return value_type(*std::get<Ns>(iterators)...);
621  }
622 
623  template <size_t... Ns>
624  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
625    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
626  }
627 
628  template <size_t... Ns>
629  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
630    return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
631  }
632 
633  template <size_t... Ns>
634  bool test_all_equals(const zip_common &other,
635            std::index_sequence<Ns...>) const {
636    return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) ==
637                                              std::get<Ns>(other.iterators)...},
638                  identity<bool>{});
639  }
640 
641public:
642  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
643 
644  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
645 
646  const value_type operator*() const {
647    return deref(std::index_sequence_for<Iters...>{});
648  }
649 
650  ZipType &operator++() {
651    iterators = tup_inc(std::index_sequence_for<Iters...>{});
652    return *reinterpret_cast<ZipType *>(this);
653  }
654 
655  ZipType &operator--() {
656    static_assert(Base::IsBidirectional,
657                  "All inner iterators must be at least bidirectional.");
658    iterators = tup_dec(std::index_sequence_for<Iters...>{});
659    return *reinterpret_cast<ZipType *>(this);
660  }
661 
662  /// Return true if all the iterator are matching `other`'s iterators.
663  bool all_equals(zip_common &other) {
664    return test_all_equals(other, std::index_sequence_for<Iters...>{});
665  }
666};
667 
668template <typename... Iters>
669struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
670  using Base = zip_common<zip_first<Iters...>, Iters...>;
671 
672  bool operator==(const zip_first<Iters...> &other) const {
673    return std::get<0>(this->iterators) == std::get<0>(other.iterators);
674  }
675 
676  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
677};
678 
679template <typename... Iters>
680class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
681  template <size_t... Ns>
682  bool test(const zip_shortest<Iters...> &other,
683            std::index_sequence<Ns...>) const {
684    return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
685                                              std::get<Ns>(other.iterators)...},
686                  identity<bool>{});
687  }
688 
689public:
690  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
691 
692  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
693 
694  bool operator==(const zip_shortest<Iters...> &other) const {
695    return !test(other, std::index_sequence_for<Iters...>{});
696  }
697};
698 
699template <template <typename...> class ItType, typename... Args> class zippy {
700public:
701  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
702  using iterator_category = typename iterator::iterator_category;
703  using value_type = typename iterator::value_type;
704  using difference_type = typename iterator::difference_type;
705  using pointer = typename iterator::pointer;
706  using reference = typename iterator::reference;
707 
708private:
709  std::tuple<Args...> ts;
710 
711  template <size_t... Ns>
712  iterator begin_impl(std::index_sequence<Ns...>) const {
713    return iterator(std::begin(std::get<Ns>(ts))...);
714  }
715  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
716    return iterator(std::end(std::get<Ns>(ts))...);
717  }
718 
719public:
720  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
721 
722  iterator begin() const {
723    return begin_impl(std::index_sequence_for<Args...>{});
724  }
725  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
726};
727 
728} // end namespace detail
729 
730/// zip iterator for two or more iteratable types.
731template <typename T, typename U, typename... Args>
732detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
733                                                       Args &&... args) {
734  return detail::zippy<detail::zip_shortest, T, U, Args...>(
735      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
736}
737 
738/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
739/// be the shortest.
740template <typename T, typename U, typename... Args>
741detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
742                                                          Args &&... args) {
743  return detail::zippy<detail::zip_first, T, U, Args...>(
744      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
745}
746 
747namespace detail {
748template <typename Iter>
749Iter next_or_end(const Iter &I, const Iter &End) {
750  if (I == End)
751    return End;
752  return std::next(I);
753}
754 
755template <typename Iter>
756auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
757    std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
758  if (I == End)
759    return None;
760  return *I;
761}
762 
763template <typename Iter> struct ZipLongestItemType {
764  using type =
765      llvm::Optional<typename std::remove_const<typename std::remove_reference<
766          decltype(*std::declval<Iter>())>::type>::type>;
767};
768 
769template <typename... Iters> struct ZipLongestTupleType {
770  using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
771};
772 
773template <typename... Iters>
774class zip_longest_iterator
775    : public iterator_facade_base<
776          zip_longest_iterator<Iters...>,
777          typename std::common_type<
778              std::forward_iterator_tag,
779              typename std::iterator_traits<Iters>::iterator_category...>::type,
780          typename ZipLongestTupleType<Iters...>::type,
781          typename std::iterator_traits<typename std::tuple_element<
782              0, std::tuple<Iters...>>::type>::difference_type,
783          typename ZipLongestTupleType<Iters...>::type *,
784          typename ZipLongestTupleType<Iters...>::type> {
785public:
786  using value_type = typename ZipLongestTupleType<Iters...>::type;
787 
788private:
789  std::tuple<Iters...> iterators;
790  std::tuple<Iters...> end_iterators;
791 
792  template <size_t... Ns>
793  bool test(const zip_longest_iterator<Iters...> &other,
794            std::index_sequence<Ns...>) const {
795    return llvm::any_of(
796        std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
797                                    std::get<Ns>(other.iterators)...},
798        identity<bool>{});
799  }
800 
801  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
802    return value_type(
803        deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
804  }
805 
806  template <size_t... Ns>
807  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
808    return std::tuple<Iters...>(
809        next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
810  }
811 
812public:
813  zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
814      : iterators(std::forward<Iters>(ts.first)...),
815        end_iterators(std::forward<Iters>(ts.second)...) {}
816 
817  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
818 
819  value_type operator*() const {
820    return deref(std::index_sequence_for<Iters...>{});
821  }
822 
823  zip_longest_iterator<Iters...> &operator++() {
824    iterators = tup_inc(std::index_sequence_for<Iters...>{});
825    return *this;
826  }
827 
828  bool operator==(const zip_longest_iterator<Iters...> &other) const {
829    return !test(other, std::index_sequence_for<Iters...>{});
830  }
831};
832 
833template <typename... Args> class zip_longest_range {
834public:
835  using iterator =
836      zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
837  using iterator_category = typename iterator::iterator_category;
838  using value_type = typename iterator::value_type;
839  using difference_type = typename iterator::difference_type;
840  using pointer = typename iterator::pointer;
841  using reference = typename iterator::reference;
842 
843private:
844  std::tuple<Args...> ts;
845 
846  template <size_t... Ns>
847  iterator begin_impl(std::index_sequence<Ns...>) const {
848    return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
849                                   adl_end(std::get<Ns>(ts)))...);
850  }
851 
852  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
853    return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
854                                   adl_end(std::get<Ns>(ts)))...);
855  }
856 
857public:
858  zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
859 
860  iterator begin() const {
861    return begin_impl(std::index_sequence_for<Args...>{});
862  }
863  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
864};
865} // namespace detail
866 
867/// Iterate over two or more iterators at the same time. Iteration continues
868/// until all iterators reach the end. The llvm::Optional only contains a value
869/// if the iterator has not reached the end.
870template <typename T, typename U, typename... Args>
871detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
872                                                     Args &&... args) {
873  return detail::zip_longest_range<T, U, Args...>(
874      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
875}
876 
877/// Iterator wrapper that concatenates sequences together.
878///
879/// This can concatenate different iterators, even with different types, into
880/// a single iterator provided the value types of all the concatenated
881/// iterators expose `reference` and `pointer` types that can be converted to
882/// `ValueT &` and `ValueT *` respectively. It doesn't support more
883/// interesting/customized pointer or reference types.
884///
885/// Currently this only supports forward or higher iterator categories as
886/// inputs and always exposes a forward iterator interface.
887template <typename ValueT, typename... IterTs>
888class concat_iterator
889    : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
890                                  std::forward_iterator_tag, ValueT> {
891  using BaseT = typename concat_iterator::iterator_facade_base;
892 
893  /// We store both the current and end iterators for each concatenated
894  /// sequence in a tuple of pairs.
895  ///
896  /// Note that something like iterator_range seems nice at first here, but the
897  /// range properties are of little benefit and end up getting in the way
898  /// because we need to do mutation on the current iterators.
899  std::tuple<IterTs...> Begins;
900  std::tuple<IterTs...> Ends;
901 
902  /// Attempts to increment a specific iterator.
903  ///
904  /// Returns true if it was able to increment the iterator. Returns false if
905  /// the iterator is already at the end iterator.
906  template <size_t Index> bool incrementHelper() {
907    auto &Begin = std::get<Index>(Begins);
908    auto &End = std::get<Index>(Ends);
909    if (Begin == End)
910      return false;
911 
912    ++Begin;
913    return true;
914  }
915 
916  /// Increments the first non-end iterator.
917  ///
918  /// It is an error to call this with all iterators at the end.
919  template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
920    // Build a sequence of functions to increment each iterator if possible.
921    bool (concat_iterator::*IncrementHelperFns[])() = {
922        &concat_iterator::incrementHelper<Ns>...};
923 
924    // Loop over them, and stop as soon as we succeed at incrementing one.
925    for (auto &IncrementHelperFn : IncrementHelperFns)
926      if ((this->*IncrementHelperFn)())
927        return;
928 
929    llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 929);
930  }
931 
932  /// Returns null if the specified iterator is at the end. Otherwise,
933  /// dereferences the iterator and returns the address of the resulting
934  /// reference.
935  template <size_t Index> ValueT *getHelper() const {
936    auto &Begin = std::get<Index>(Begins);
937    auto &End = std::get<Index>(Ends);
938    if (Begin == End)
939      return nullptr;
940 
941    return &*Begin;
942  }
943 
944  /// Finds the first non-end iterator, dereferences, and returns the resulting
945  /// reference.
946  ///
947  /// It is an error to call this with all iterators at the end.
948  template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
949    // Build a sequence of functions to get from iterator if possible.
950    ValueT *(concat_iterator::*GetHelperFns[])() const = {
951        &concat_iterator::getHelper<Ns>...};
952 
953    // Loop over them, and return the first result we find.
954    for (auto &GetHelperFn : GetHelperFns)
955      if (ValueT *P = (this->*GetHelperFn)())
956        return *P;
957 
958    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-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 958);
959  }
960 
961public:
962  /// Constructs an iterator from a sequence of ranges.
963  ///
964  /// We need the full range to know how to switch between each of the
965  /// iterators.
966  template <typename... RangeTs>
967  explicit concat_iterator(RangeTs &&... Ranges)
968      : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
969 
970  using BaseT::operator++;
971 
972  concat_iterator &operator++() {
973    increment(std::index_sequence_for<IterTs...>());
974    return *this;
975  }
976 
977  ValueT &operator*() const {
978    return get(std::index_sequence_for<IterTs...>());
979  }
980 
981  bool operator==(const concat_iterator &RHS) const {
982    return Begins == RHS.Begins && Ends == RHS.Ends;
983  }
984};
985 
986namespace detail {
987 
988/// Helper to store a sequence of ranges being concatenated and access them.
989///
990/// This is designed to facilitate providing actual storage when temporaries
991/// are passed into the constructor such that we can use it as part of range
992/// based for loops.
993template <typename ValueT, typename... RangeTs> class concat_range {
994public:
995  using iterator =
996      concat_iterator<ValueT,
997                      decltype(std::begin(std::declval<RangeTs &>()))...>;
998 
999private:
1000  std::tuple<RangeTs...> Ranges;
1001 
1002  template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
1003    return iterator(std::get<Ns>(Ranges)...);
1004  }
1005  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
1006    return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1007                               std::end(std::get<Ns>(Ranges)))...);
1008  }
1009 
1010public:
1011  concat_range(RangeTs &&... Ranges)
1012      : Ranges(std::forward<RangeTs>(Ranges)...) {}
1013 
1014  iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
1015  iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
1016};
1017 
1018} // end namespace detail
1019 
1020/// Concatenated range across two or more ranges.
1021///
1022/// The desired value type must be explicitly specified.
1023template <typename ValueT, typename... RangeTs>
1024detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1025  static_assert(sizeof...(RangeTs) > 1,
1026                "Need more than one range to concatenate!");
1027  return detail::concat_range<ValueT, RangeTs...>(
1028      std::forward<RangeTs>(Ranges)...);
1029}
1030 
1031/// A utility class used to implement an iterator that contains some base object
1032/// and an index. The iterator moves the index but keeps the base constant.
1033template <typename DerivedT, typename BaseT, typename T,
1034          typename PointerT = T *, typename ReferenceT = T &>
1035class indexed_accessor_iterator
1036    : public llvm::iterator_facade_base<DerivedT,
1037                                        std::random_access_iterator_tag, T,
1038                                        std::ptrdiff_t, PointerT, ReferenceT> {
1039public:
1040  ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
1041    assert(base == rhs.base && "incompatible iterators")(static_cast <bool> (base == rhs.base && "incompatible iterators"
) ? void (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1041, __extension__ __PRETTY_FUNCTION__));
1042    return index - rhs.index;
1043  }
1044  bool operator==(const indexed_accessor_iterator &rhs) const {
1045    return base == rhs.base && index == rhs.index;
1046  }
1047  bool operator<(const indexed_accessor_iterator &rhs) const {
1048    assert(base == rhs.base && "incompatible iterators")(static_cast <bool> (base == rhs.base && "incompatible iterators"
) ? void (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1048, __extension__ __PRETTY_FUNCTION__));
1049    return index < rhs.index;
1050  }
1051 
1052  DerivedT &operator+=(ptrdiff_t offset) {
1053    this->index += offset;
1054    return static_cast<DerivedT &>(*this);
1055  }
1056  DerivedT &operator-=(ptrdiff_t offset) {
1057    this->index -= offset;
1058    return static_cast<DerivedT &>(*this);
1059  }
1060 
1061  /// Returns the current index of the iterator.
1062  ptrdiff_t getIndex() const { return index; }
1063 
1064  /// Returns the current base of the iterator.
1065  const BaseT &getBase() const { return base; }
1066 
1067protected:
1068  indexed_accessor_iterator(BaseT base, ptrdiff_t index)
1069      : base(base), index(index) {}
1070  BaseT base;
1071  ptrdiff_t index;
1072};
1073 
1074namespace detail {
1075/// The class represents the base of a range of indexed_accessor_iterators. It
1076/// provides support for many different range functionalities, e.g.
1077/// drop_front/slice/etc.. Derived range classes must implement the following
1078/// static methods:
1079///   * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1080///     - Dereference an iterator pointing to the base object at the given
1081///       index.
1082///   * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1083///     - Return a new base that is offset from the provide base by 'index'
1084///       elements.
1085template <typename DerivedT, typename BaseT, typename T,
1086          typename PointerT = T *, typename ReferenceT = T &>
1087class indexed_accessor_range_base {
1088public:
1089  using RangeBaseT =
1090      indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT>;
1091 
1092  /// An iterator element of this range.
1093  class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1094                                                    PointerT, ReferenceT> {
1095  public:
1096    // Index into this iterator, invoking a static method on the derived type.
1097    ReferenceT operator*() const {
1098      return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1099    }
1100 
1101  private:
1102    iterator(BaseT owner, ptrdiff_t curIndex)
1103        : indexed_accessor_iterator<iterator, BaseT, T, PointerT, ReferenceT>(
1104              owner, curIndex) {}
1105 
1106    /// Allow access to the constructor.
1107    friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1108                                       ReferenceT>;
1109  };
1110 
1111  indexed_accessor_range_base(iterator begin, iterator end)
1112      : base(offset_base(begin.getBase(), begin.getIndex())),
1113        count(end.getIndex() - begin.getIndex()) {}
1114  indexed_accessor_range_base(const iterator_range<iterator> &range)
1115      : indexed_accessor_range_base(range.begin(), range.end()) {}
1116  indexed_accessor_range_base(BaseT base, ptrdiff_t count)
1117      : base(base), count(count) {}
1118 
1119  iterator begin() const { return iterator(base, 0); }
1120  iterator end() const { return iterator(base, count); }
1121  ReferenceT operator[](size_t Index) const {
1122    assert(Index < size() && "invalid index for value range")(static_cast <bool> (Index < size() && "invalid index for value range"
) ? void (0) : __assert_fail ("Index < size() && \"invalid index for value range\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1122, __extension__ __PRETTY_FUNCTION__));
1123    return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index));
1124  }
1125  ReferenceT front() const {
1126    assert(!empty() && "expected non-empty range")(static_cast <bool> (!empty() && "expected non-empty range"
) ? void (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1126, __extension__ __PRETTY_FUNCTION__));
1127    return (*this)[0];
1128  }
1129  ReferenceT back() const {
1130    assert(!empty() && "expected non-empty range")(static_cast <bool> (!empty() && "expected non-empty range"
) ? void (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1130, __extension__ __PRETTY_FUNCTION__));
1131    return (*this)[size() - 1];
1132  }
1133 
1134  /// Compare this range with another.
1135  template <typename OtherT> bool operator==(const OtherT &other) const {
1136    return size() ==
1137               static_cast<size_t>(std::distance(other.begin(), other.end())) &&
1138           std::equal(begin(), end(), other.begin());
1139  }
1140  template <typename OtherT> bool operator!=(const OtherT &other) const {
1141    return !(*this == other);
1142  }
1143 
1144  /// Return the size of this range.
1145  size_t size() const { return count; }
1146 
1147  /// Return if the range is empty.
1148  bool empty() const { return size() == 0; }
1149 
1150  /// Drop the first N elements, and keep M elements.
1151  DerivedT slice(size_t n, size_t m) const {
1152    assert(n + m <= size() && "invalid size specifiers")(static_cast <bool> (n + m <= size() && "invalid size specifiers"
) ? void (0) : __assert_fail ("n + m <= size() && \"invalid size specifiers\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1152, __extension__ __PRETTY_FUNCTION__));
1153    return DerivedT(offset_base(base, n), m);
1154  }
1155 
1156  /// Drop the first n elements.
1157  DerivedT drop_front(size_t n = 1) const {
1158    assert(size() >= n && "Dropping more elements than exist")(static_cast <bool> (size() >= n && "Dropping more elements than exist"
) ? void (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1158, __extension__ __PRETTY_FUNCTION__));
1159    return slice(n, size() - n);
1160  }
1161  /// Drop the last n elements.
1162  DerivedT drop_back(size_t n = 1) const {
1163    assert(size() >= n && "Dropping more elements than exist")(static_cast <bool> (size() >= n && "Dropping more elements than exist"
) ? void (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1163, __extension__ __PRETTY_FUNCTION__));
1164    return DerivedT(base, size() - n);
1165  }
1166 
1167  /// Take the first n elements.
1168  DerivedT take_front(size_t n = 1) const {
1169    return n < size() ? drop_back(size() - n)
1170                      : static_cast<const DerivedT &>(*this);
1171  }
1172 
1173  /// Take the last n elements.
1174  DerivedT take_back(size_t n = 1) const {
1175    return n < size() ? drop_front(size() - n)
1176                      : static_cast<const DerivedT &>(*this);
1177  }
1178 
1179  /// Allow conversion to any type accepting an iterator_range.
1180  template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1181                                 RangeT, iterator_range<iterator>>::value>>
1182  operator RangeT() const {
1183    return RangeT(iterator_range<iterator>(*this));
1184  }
1185 
1186  /// Returns the base of this range.
1187  const BaseT &getBase() const { return base; }
1188 
1189private:
1190  /// Offset the given base by the given amount.
1191  static BaseT offset_base(const BaseT &base, size_t n) {
1192    return n == 0 ? base : DerivedT::offset_base(base, n);
1193  }
1194 
1195protected:
1196  indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
1197  indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
1198  indexed_accessor_range_base &
1199  operator=(const indexed_accessor_range_base &) = default;
1200 
1201  /// The base that owns the provided range of values.
1202  BaseT base;
1203  /// The size from the owning range.
1204  ptrdiff_t count;
1205};
1206} // end namespace detail
1207 
1208/// This class provides an implementation of a range of
1209/// indexed_accessor_iterators where the base is not indexable. Ranges with
1210/// bases that are offsetable should derive from indexed_accessor_range_base
1211/// instead. Derived range classes are expected to implement the following
1212/// static method:
1213///   * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1214///     - Dereference an iterator pointing to a parent base at the given index.
1215template <typename DerivedT, typename BaseT, typename T,
1216          typename PointerT = T *, typename ReferenceT = T &>
1217class indexed_accessor_range
1218    : public detail::indexed_accessor_range_base<
1219          DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1220public:
1221  indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
1222      : detail::indexed_accessor_range_base<
1223            DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1224            std::make_pair(base, startIndex), count) {}
1225  using detail::indexed_accessor_range_base<
1226      DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1227      ReferenceT>::indexed_accessor_range_base;
1228 
1229  /// Returns the current base of the range.
1230  const BaseT &getBase() const { return this->base.first; }
1231 
1232  /// Returns the current start index of the range.
1233  ptrdiff_t getStartIndex() const { return this->base.second; }
1234 
1235  /// See `detail::indexed_accessor_range_base` for details.
1236  static std::pair<BaseT, ptrdiff_t>
1237  offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1238    // We encode the internal base as a pair of the derived base and a start
1239    // index into the derived base.
1240    return std::make_pair(base.first, base.second + index);
1241  }
1242  /// See `detail::indexed_accessor_range_base` for details.
1243  static ReferenceT
1244  dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1245                       ptrdiff_t index) {
1246    return DerivedT::dereference(base.first, base.second + index);
1247  }
1248};
1249 
1250/// Given a container of pairs, return a range over the first elements.
1251template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
1252  return llvm::map_range(
1253      std::forward<ContainerTy>(c),
1254      [](decltype((*std::begin(c))) elt) -> decltype((elt.first)) {
1255        return elt.first;
1256      });
1257}
1258 
1259/// Given a container of pairs, return a range over the second elements.
1260template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1261  return llvm::map_range(
1262      std::forward<ContainerTy>(c),
1263      [](decltype((*std::begin(c))) elt) -> decltype((elt.second)) {
1264        return elt.second;
1265      });
1266}
1267 
1268//===----------------------------------------------------------------------===//
1269//     Extra additions to <utility>
1270//===----------------------------------------------------------------------===//
1271 
1272/// Function object to check whether the first component of a std::pair
1273/// compares less than the first component of another std::pair.
1274struct less_first {
1275  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1276    return std::less<>()(lhs.first, rhs.first);
1277  }
1278};
1279 
1280/// Function object to check whether the second component of a std::pair
1281/// compares less than the second component of another std::pair.
1282struct less_second {
1283  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1284    return std::less<>()(lhs.second, rhs.second);
1285  }
1286};
1287 
1288/// \brief Function object to apply a binary function to the first component of
1289/// a std::pair.
1290template<typename FuncTy>
1291struct on_first {
1292  FuncTy func;
1293 
1294  template <typename T>
1295  decltype(auto) operator()(const T &lhs, const T &rhs) const {
1296    return func(lhs.first, rhs.first);
1297  }
1298};
1299 
1300/// Utility type to build an inheritance chain that makes it easy to rank
1301/// overload candidates.
1302template <int N> struct rank : rank<N - 1> {};
1303template <> struct rank<0> {};
1304 
1305/// traits class for checking whether type T is one of any of the given
1306/// types in the variadic list.
1307template <typename T, typename... Ts>
1308using is_one_of = disjunction<std::is_same<T, Ts>...>;
1309 
1310/// traits class for checking whether type T is a base class for all
1311///  the given types in the variadic list.
1312template <typename T, typename... Ts>
1313using are_base_of = conjunction<std::is_base_of<T, Ts>...>;
1314 
1315namespace detail {
1316template <typename... Ts> struct Visitor;
1317 
1318template <typename HeadT, typename... TailTs>
1319struct Visitor<HeadT, TailTs...> : remove_cvref_t<HeadT>, Visitor<TailTs...> {
1320  explicit constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
1321      : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)),
1322        Visitor<TailTs...>(std::forward<TailTs>(Tail)...) {}
1323  using remove_cvref_t<HeadT>::operator();
1324  using Visitor<TailTs...>::operator();
1325};
1326 
1327template <typename HeadT> struct Visitor<HeadT> : remove_cvref_t<HeadT> {
1328  explicit constexpr Visitor(HeadT &&Head)
1329      : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)) {}
1330  using remove_cvref_t<HeadT>::operator();
1331};
1332} // namespace detail
1333 
1334/// Returns an opaquely-typed Callable object whose operator() overload set is
1335/// the sum of the operator() overload sets of each CallableT in CallableTs.
1336///
1337/// The type of the returned object derives from each CallableT in CallableTs.
1338/// The returned object is constructed by invoking the appropriate copy or move
1339/// constructor of each CallableT, as selected by overload resolution on the
1340/// corresponding argument to makeVisitor.
1341///
1342/// Example:
1343///
1344/// \code
1345/// auto visitor = makeVisitor([](auto) { return "unhandled type"; },
1346///                            [](int i) { return "int"; },
1347///                            [](std::string s) { return "str"; });
1348/// auto a = visitor(42);    // `a` is now "int".
1349/// auto b = visitor("foo"); // `b` is now "str".
1350/// auto c = visitor(3.14f); // `c` is now "unhandled type".
1351/// \endcode
1352///
1353/// Example of making a visitor with a lambda which captures a move-only type:
1354///
1355/// \code
1356/// std::unique_ptr<FooHandler> FH = /* ... */;
1357/// auto visitor = makeVisitor(
1358///     [FH{std::move(FH)}](Foo F) { return FH->handle(F); },
1359///     [](int i) { return i; },
1360///     [](std::string s) { return atoi(s); });
1361/// \endcode
1362template <typename... CallableTs>
1363constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) {
1364  return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...);
1365}
1366 
1367//===----------------------------------------------------------------------===//
1368//     Extra additions for arrays
1369//===----------------------------------------------------------------------===//
1370 
1371// We have a copy here so that LLVM behaves the same when using different
1372// standard libraries.
1373template <class Iterator, class RNG>
1374void shuffle(Iterator first, Iterator last, RNG &&g) {
1375  // It would be better to use a std::uniform_int_distribution,
1376  // but that would be stdlib dependent.
1377  typedef
1378      typename std::iterator_traits<Iterator>::difference_type difference_type;
1379  for (auto size = last - first; size > 1; ++first, (void)--size) {
1380    difference_type offset = g() % size;
1381    // Avoid self-assignment due to incorrect assertions in libstdc++
1382    // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
1383    if (offset != difference_type(0))
1384      std::iter_swap(first, first + offset);
1385  }
1386}
1387 
1388/// Find the length of an array.
1389template <class T, std::size_t N>
1390constexpr inline size_t array_lengthof(T (&)[N]) {
1391  return N;
1392}
1393 
1394/// Adapt std::less<T> for array_pod_sort.
1395template<typename T>
1396inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1397  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1398                     *reinterpret_cast<const T*>(P2)))
1399    return -1;
1400  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1401                     *reinterpret_cast<const T*>(P1)))
1402    return 1;
1403  return 0;
1404}
1405 
1406/// get_array_pod_sort_comparator - This is an internal helper function used to
1407/// get type deduction of T right.
1408template<typename T>
1409inline int (*get_array_pod_sort_comparator(const T &))
1410             (const void*, const void*) {
1411  return array_pod_sort_comparator<T>;
1412}
1413 
1414#ifdef EXPENSIVE_CHECKS
1415namespace detail {
1416 
1417inline unsigned presortShuffleEntropy() {
1418  static unsigned Result(std::random_device{}());
1419  return Result;
1420}
1421 
1422template <class IteratorTy>
1423inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1424  std::mt19937 Generator(presortShuffleEntropy());
1425  llvm::shuffle(Start, End, Generator);
1426}
1427 
1428} // end namespace detail
1429#endif
1430 
1431/// array_pod_sort - This sorts an array with the specified start and end
1432/// extent.  This is just like std::sort, except that it calls qsort instead of
1433/// using an inlined template.  qsort is slightly slower than std::sort, but
1434/// most sorts are not performance critical in LLVM and std::sort has to be
1435/// template instantiated for each type, leading to significant measured code
1436/// bloat.  This function should generally be used instead of std::sort where
1437/// possible.
1438///
1439/// This function assumes that you have simple POD-like types that can be
1440/// compared with std::less and can be moved with memcpy.  If this isn't true,
1441/// you should use std::sort.
1442///
1443/// NOTE: If qsort_r were portable, we could allow a custom comparator and
1444/// default to std::less.
1445template<class IteratorTy>
1446inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1447  // Don't inefficiently call qsort with one element or trigger undefined
1448  // behavior with an empty sequence.
1449  auto NElts = End - Start;
1450  if (NElts <= 1) return;
1451#ifdef EXPENSIVE_CHECKS
1452  detail::presortShuffle<IteratorTy>(Start, End);
1453#endif
1454  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1455}
1456 
1457template <class IteratorTy>
1458inline void array_pod_sort(
1459    IteratorTy Start, IteratorTy End,
1460    int (*Compare)(
1461        const typename std::iterator_traits<IteratorTy>::value_type *,
1462        const typename std::iterator_traits<IteratorTy>::value_type *)) {
1463  // Don't inefficiently call qsort with one element or trigger undefined
1464  // behavior with an empty sequence.
1465  auto NElts = End - Start;
1466  if (NElts <= 1) return;
1467#ifdef EXPENSIVE_CHECKS
1468  detail::presortShuffle<IteratorTy>(Start, End);
1469#endif
1470  qsort(&*Start, NElts, sizeof(*Start),
1471        reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1472}
1473 
1474namespace detail {
1475template <typename T>
1476// We can use qsort if the iterator type is a pointer and the underlying value
1477// is trivially copyable.
1478using sort_trivially_copyable = conjunction<
1479    std::is_pointer<T>,
1480    std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1481} // namespace detail
1482 
1483// Provide wrappers to std::sort which shuffle the elements before sorting
1484// to help uncover non-deterministic behavior (PR35135).
1485template <typename IteratorTy,
1486          std::enable_if_t<!detail::sort_trivially_copyable<IteratorTy>::value,
1487                           int> = 0>
1488inline void sort(IteratorTy Start, IteratorTy End) {
1489#ifdef EXPENSIVE_CHECKS
1490  detail::presortShuffle<IteratorTy>(Start, End);
1491#endif
1492  std::sort(Start, End);
1493}
1494 
1495// Forward trivially copyable types to array_pod_sort. This avoids a large
1496// amount of code bloat for a minor performance hit.
1497template <typename IteratorTy,
1498          std::enable_if_t<detail::sort_trivially_copyable<IteratorTy>::value,
1499                           int> = 0>
1500inline void sort(IteratorTy Start, IteratorTy End) {
1501  array_pod_sort(Start, End);
1502}
1503 
1504template <typename Container> inline void sort(Container &&C) {
1505  llvm::sort(adl_begin(C), adl_end(C));
1506}
1507 
1508template <typename IteratorTy, typename Compare>
1509inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1510#ifdef EXPENSIVE_CHECKS
1511  detail::presortShuffle<IteratorTy>(Start, End);
1512#endif
1513  std::sort(Start, End, Comp);
1514}
1515 
1516template <typename Container, typename Compare>
1517inline void sort(Container &&C, Compare Comp) {
1518  llvm::sort(adl_begin(C), adl_end(C), Comp);
1519}
1520 
1521//===----------------------------------------------------------------------===//
1522//     Extra additions to <algorithm>
1523//===----------------------------------------------------------------------===//
1524 
1525/// Get the size of a range. This is a wrapper function around std::distance
1526/// which is only enabled when the operation is O(1).
1527template <typename R>
1528auto size(R &&Range,
1529          std::enable_if_t<
1530              std::is_base_of<std::random_access_iterator_tag,
1531                              typename std::iterator_traits<decltype(
1532                                  Range.begin())>::iterator_category>::value,
1533              void> * = nullptr) {
1534  return std::distance(Range.begin(), Range.end());
1535}
1536 
1537/// Provide wrappers to std::for_each which take ranges instead of having to
1538/// pass begin/end explicitly.
1539template <typename R, typename UnaryFunction>
1540UnaryFunction for_each(R &&Range, UnaryFunction F) {
1541  return std::for_each(adl_begin(Range), adl_end(Range), F);
1542}
1543 
1544/// Provide wrappers to std::all_of which take ranges instead of having to pass
1545/// begin/end explicitly.
1546template <typename R, typename UnaryPredicate>
1547bool all_of(R &&Range, UnaryPredicate P) {
1548  return std::all_of(adl_begin(Range), adl_end(Range), P);
1549}
1550 
1551/// Provide wrappers to std::any_of which take ranges instead of having to pass
1552/// begin/end explicitly.
1553template <typename R, typename UnaryPredicate>
1554bool any_of(R &&Range, UnaryPredicate P) {
1555  return std::any_of(adl_begin(Range), adl_end(Range), P);
1556}
1557 
1558/// Provide wrappers to std::none_of which take ranges instead of having to pass
1559/// begin/end explicitly.
1560template <typename R, typename UnaryPredicate>
1561bool none_of(R &&Range, UnaryPredicate P) {
1562  return std::none_of(adl_begin(Range), adl_end(Range), P);
1563}
1564 
1565/// Provide wrappers to std::find which take ranges instead of having to pass
1566/// begin/end explicitly.
1567template <typename R, typename T> auto find(R &&Range, const T &Val) {
1568  return std::find(adl_begin(Range), adl_end(Range), Val);
1569}
1570 
1571/// Provide wrappers to std::find_if which take ranges instead of having to pass
1572/// begin/end explicitly.
1573template <typename R, typename UnaryPredicate>
1574auto find_if(R &&Range, UnaryPredicate P) {
1575  return std::find_if(adl_begin(Range), adl_end(Range), P);
1576}
1577 
1578template <typename R, typename UnaryPredicate>
1579auto find_if_not(R &&Range, UnaryPredicate P) {
1580  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1581}
1582 
1583/// Provide wrappers to std::remove_if which take ranges instead of having to
1584/// pass begin/end explicitly.
1585template <typename R, typename UnaryPredicate>
1586auto remove_if(R &&Range, UnaryPredicate P) {
1587  return std::remove_if(adl_begin(Range), adl_end(Range), P);
1588}
1589 
1590/// Provide wrappers to std::copy_if which take ranges instead of having to
1591/// pass begin/end explicitly.
1592template <typename R, typename OutputIt, typename UnaryPredicate>
1593OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1594  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1595}
1596 
1597template <typename R, typename OutputIt>
1598OutputIt copy(R &&Range, OutputIt Out) {
1599  return std::copy(adl_begin(Range), adl_end(Range), Out);
1600}
1601 
1602/// Provide wrappers to std::move which take ranges instead of having to
1603/// pass begin/end explicitly.
1604template <typename R, typename OutputIt>
1605OutputIt move(R &&Range, OutputIt Out) {
1606  return std::move(adl_begin(Range), adl_end(Range), Out);
1607}
1608 
1609/// Wrapper function around std::find to detect if an element exists
1610/// in a container.
1611template <typename R, typename E>
1612bool is_contained(R &&Range, const E &Element) {
1613  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
18
←
Calling 'operator!=<_xmlNs **, std::vector<_xmlNs *>>'→
21
←
Returning from 'operator!=<_xmlNs **, std::vector<_xmlNs *>>'→
22
←
Returning zero, which participates in a condition later→
1614}
1615 
1616/// Wrapper function around std::is_sorted to check if elements in a range \p R
1617/// are sorted with respect to a comparator \p C.
1618template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
1619  return std::is_sorted(adl_begin(Range), adl_end(Range), C);
1620}
1621 
1622/// Wrapper function around std::is_sorted to check if elements in a range \p R
1623/// are sorted in non-descending order.
1624template <typename R> bool is_sorted(R &&Range) {
1625  return std::is_sorted(adl_begin(Range), adl_end(Range));
1626}
1627 
1628/// Wrapper function around std::count to count the number of times an element
1629/// \p Element occurs in the given range \p Range.
1630template <typename R, typename E> auto count(R &&Range, const E &Element) {
1631  return std::count(adl_begin(Range), adl_end(Range), Element);
1632}
1633 
1634/// Wrapper function around std::count_if to count the number of times an
1635/// element satisfying a given predicate occurs in a range.
1636template <typename R, typename UnaryPredicate>
1637auto count_if(R &&Range, UnaryPredicate P) {
1638  return std::count_if(adl_begin(Range), adl_end(Range), P);
1639}
1640 
1641/// Wrapper function around std::transform to apply a function to a range and
1642/// store the result elsewhere.
1643template <typename R, typename OutputIt, typename UnaryFunction>
1644OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) {
1645  return std::transform(adl_begin(Range), adl_end(Range), d_first, F);
1646}
1647 
1648/// Provide wrappers to std::partition which take ranges instead of having to
1649/// pass begin/end explicitly.
1650template <typename R, typename UnaryPredicate>
1651auto partition(R &&Range, UnaryPredicate P) {
1652  return std::partition(adl_begin(Range), adl_end(Range), P);
1653}
1654 
1655/// Provide wrappers to std::lower_bound which take ranges instead of having to
1656/// pass begin/end explicitly.
1657template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
1658  return std::lower_bound(adl_begin(Range), adl_end(Range),
1659                          std::forward<T>(Value));
1660}
1661 
1662template <typename R, typename T, typename Compare>
1663auto lower_bound(R &&Range, T &&Value, Compare C) {
1664  return std::lower_bound(adl_begin(Range), adl_end(Range),
1665                          std::forward<T>(Value), C);
1666}
1667 
1668/// Provide wrappers to std::upper_bound which take ranges instead of having to
1669/// pass begin/end explicitly.
1670template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
1671  return std::upper_bound(adl_begin(Range), adl_end(Range),
1672                          std::forward<T>(Value));
1673}
1674 
1675template <typename R, typename T, typename Compare>
1676auto upper_bound(R &&Range, T &&Value, Compare C) {
1677  return std::upper_bound(adl_begin(Range), adl_end(Range),
1678                          std::forward<T>(Value), C);
1679}
1680 
1681template <typename R>
1682void stable_sort(R &&Range) {
1683  std::stable_sort(adl_begin(Range), adl_end(Range));
1684}
1685 
1686template <typename R, typename Compare>
1687void stable_sort(R &&Range, Compare C) {
1688  std::stable_sort(adl_begin(Range), adl_end(Range), C);
1689}
1690 
1691/// Binary search for the first iterator in a range where a predicate is false.
1692/// Requires that C is always true below some limit, and always false above it.
1693template <typename R, typename Predicate,
1694          typename Val = decltype(*adl_begin(std::declval<R>()))>
1695auto partition_point(R &&Range, Predicate P) {
1696  return std::partition_point(adl_begin(Range), adl_end(Range), P);
1697}
1698 
1699template<typename Range, typename Predicate>
1700auto unique(Range &&R, Predicate P) {
1701  return std::unique(adl_begin(R), adl_end(R), P);
1702}
1703 
1704/// Wrapper function around std::equal to detect if pair-wise elements between
1705/// two ranges are the same.
1706template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
1707  return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
1708                    adl_end(RRange));
1709}
1710 
1711/// Wrapper function around std::equal to detect if all elements
1712/// in a container are same.
1713template <typename R>
1714bool is_splat(R &&Range) {
1715  size_t range_size = size(Range);
1716  return range_size != 0 && (range_size == 1 ||
1717         std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1718}
1719 
1720/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1721/// `erase_if` which is equivalent to:
1722///
1723///   C.erase(remove_if(C, pred), C.end());
1724///
1725/// This version works for any container with an erase method call accepting
1726/// two iterators.
1727template <typename Container, typename UnaryPredicate>
1728void erase_if(Container &C, UnaryPredicate P) {
1729  C.erase(remove_if(C, P), C.end());
1730}
1731 
1732/// Wrapper function to remove a value from a container:
1733///
1734/// C.erase(remove(C.begin(), C.end(), V), C.end());
1735template <typename Container, typename ValueType>
1736void erase_value(Container &C, ValueType V) {
1737  C.erase(std::remove(C.begin(), C.end(), V), C.end());
1738}
1739 
1740/// Wrapper function to append a range to a container.
1741///
1742/// C.insert(C.end(), R.begin(), R.end());
1743template <typename Container, typename Range>
1744inline void append_range(Container &C, Range &&R) {
1745  C.insert(C.end(), R.begin(), R.end());
1746}
1747 
1748/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1749/// the range [ValIt, ValEnd) (which is not from the same container).
1750template<typename Container, typename RandomAccessIterator>
1751void replace(Container &Cont, typename Container::iterator ContIt,
1752             typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1753             RandomAccessIterator ValEnd) {
1754  while (true) {
1755    if (ValIt == ValEnd) {
1756      Cont.erase(ContIt, ContEnd);
1757      return;
1758    } else if (ContIt == ContEnd) {
1759      Cont.insert(ContIt, ValIt, ValEnd);
1760      return;
1761    }
1762    *ContIt++ = *ValIt++;
1763  }
1764}
1765 
1766/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1767/// the range R.
1768template<typename Container, typename Range = std::initializer_list<
1769                                 typename Container::value_type>>
1770void replace(Container &Cont, typename Container::iterator ContIt,
1771             typename Container::iterator ContEnd, Range R) {
1772  replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1773}
1774 
1775/// An STL-style algorithm similar to std::for_each that applies a second
1776/// functor between every pair of elements.
1777///
1778/// This provides the control flow logic to, for example, print a
1779/// comma-separated list:
1780/// \code
1781///   interleave(names.begin(), names.end(),
1782///              [&](StringRef name) { os << name; },
1783///              [&] { os << ", "; });
1784/// \endcode
1785template <typename ForwardIterator, typename UnaryFunctor,
1786          typename NullaryFunctor,
1787          typename = typename std::enable_if<
1788              !std::is_constructible<StringRef, UnaryFunctor>::value &&
1789              !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1790inline void interleave(ForwardIterator begin, ForwardIterator end,
1791                       UnaryFunctor each_fn, NullaryFunctor between_fn) {
1792  if (begin == end)
1793    return;
1794  each_fn(*begin);
1795  ++begin;
1796  for (; begin != end; ++begin) {
1797    between_fn();
1798    each_fn(*begin);
1799  }
1800}
1801 
1802template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
1803          typename = typename std::enable_if<
1804              !std::is_constructible<StringRef, UnaryFunctor>::value &&
1805              !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1806inline void interleave(const Container &c, UnaryFunctor each_fn,
1807                       NullaryFunctor between_fn) {
1808  interleave(c.begin(), c.end(), each_fn, between_fn);
1809}
1810 
1811/// Overload of interleave for the common case of string separator.
1812template <typename Container, typename UnaryFunctor, typename StreamT,
1813          typename T = detail::ValueOfRange<Container>>
1814inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
1815                       const StringRef &separator) {
1816  interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
1817}
1818template <typename Container, typename StreamT,
1819          typename T = detail::ValueOfRange<Container>>
1820inline void interleave(const Container &c, StreamT &os,
1821                       const StringRef &separator) {
1822  interleave(
1823      c, os, [&](const T &a) { os << a; }, separator);
1824}
1825 
1826template <typename Container, typename UnaryFunctor, typename StreamT,
1827          typename T = detail::ValueOfRange<Container>>
1828inline void interleaveComma(const Container &c, StreamT &os,
1829                            UnaryFunctor each_fn) {
1830  interleave(c, os, each_fn, ", ");
1831}
1832template <typename Container, typename StreamT,
1833          typename T = detail::ValueOfRange<Container>>
1834inline void interleaveComma(const Container &c, StreamT &os) {
1835  interleaveComma(c, os, [&](const T &a) { os << a; });
1836}
1837 
1838//===----------------------------------------------------------------------===//
1839//     Extra additions to <memory>
1840//===----------------------------------------------------------------------===//
1841 
1842struct FreeDeleter {
1843  void operator()(void* v) {
1844    ::free(v);
1845  }
1846};
1847 
1848template<typename First, typename Second>
1849struct pair_hash {
1850  size_t operator()(const std::pair<First, Second> &P) const {
1851    return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1852  }
1853};
1854 
1855/// Binary functor that adapts to any other binary functor after dereferencing
1856/// operands.
1857template <typename T> struct deref {
1858  T func;
1859 
1860  // Could be further improved to cope with non-derivable functors and
1861  // non-binary functors (should be a variadic template member function
1862  // operator()).
1863  template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
1864    assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1864, __extension__ __PRETTY_FUNCTION__));
1865    assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1865, __extension__ __PRETTY_FUNCTION__));
1866    return func(*lhs, *rhs);
1867  }
1868};
1869 
1870namespace detail {
1871 
1872template <typename R> class enumerator_iter;
1873 
1874template <typename R> struct result_pair {
1875  using value_reference =
1876      typename std::iterator_traits<IterOfRange<R>>::reference;
1877 
1878  friend class enumerator_iter<R>;
1879 
1880  result_pair() = default;
1881  result_pair(std::size_t Index, IterOfRange<R> Iter)
1882      : Index(Index), Iter(Iter) {}
1883 
1884  result_pair(const result_pair<R> &Other)
1885      : Index(Other.Index), Iter(Other.Iter) {}
1886  result_pair &operator=(const result_pair &Other) {
1887    Index = Other.Index;
1888    Iter = Other.Iter;
1889    return *this;
1890  }
1891 
1892  std::size_t index() const { return Index; }
1893  const value_reference value() const { return *Iter; }
1894  value_reference value() { return *Iter; }
1895 
1896private:
1897  std::size_t Index = std::numeric_limits<std::size_t>::max();
1898  IterOfRange<R> Iter;
1899};
1900 
1901template <typename R>
1902class enumerator_iter
1903    : public iterator_facade_base<
1904          enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1905          typename std::iterator_traits<IterOfRange<R>>::difference_type,
1906          typename std::iterator_traits<IterOfRange<R>>::pointer,
1907          typename std::iterator_traits<IterOfRange<R>>::reference> {
1908  using result_type = result_pair<R>;
1909 
1910public:
1911  explicit enumerator_iter(IterOfRange<R> EndIter)
1912      : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1913 
1914  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1915      : Result(Index, Iter) {}
1916 
1917  result_type &operator*() { return Result; }
1918  const result_type &operator*() const { return Result; }
1919 
1920  enumerator_iter &operator++() {
1921    assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 1921, __extension__ __PRETTY_FUNCTION__));
1922    ++Result.Iter;
1923    ++Result.Index;
1924    return *this;
1925  }
1926 
1927  bool operator==(const enumerator_iter &RHS) const {
1928    // Don't compare indices here, only iterators.  It's possible for an end
1929    // iterator to have different indices depending on whether it was created
1930    // by calling std::end() versus incrementing a valid iterator.
1931    return Result.Iter == RHS.Result.Iter;
1932  }
1933 
1934  enumerator_iter(const enumerator_iter &Other) : Result(Other.Result) {}
1935  enumerator_iter &operator=(const enumerator_iter &Other) {
1936    Result = Other.Result;
1937    return *this;
1938  }
1939 
1940private:
1941  result_type Result;
1942};
1943 
1944template <typename R> class enumerator {
1945public:
1946  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1947 
1948  enumerator_iter<R> begin() {
1949    return enumerator_iter<R>(0, std::begin(TheRange));
1950  }
1951 
1952  enumerator_iter<R> end() {
1953    return enumerator_iter<R>(std::end(TheRange));
1954  }
1955 
1956private:
1957  R TheRange;
1958};
1959 
1960} // end namespace detail
1961 
1962/// Given an input range, returns a new range whose values are are pair (A,B)
1963/// such that A is the 0-based index of the item in the sequence, and B is
1964/// the value from the original sequence.  Example:
1965///
1966/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1967/// for (auto X : enumerate(Items)) {
1968///   printf("Item %d - %c\n", X.index(), X.value());
1969/// }
1970///
1971/// Output:
1972///   Item 0 - A
1973///   Item 1 - B
1974///   Item 2 - C
1975///   Item 3 - D
1976///
1977template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1978  return detail::enumerator<R>(std::forward<R>(TheRange));
1979}
1980 
1981namespace detail {
1982 
1983template <typename F, typename Tuple, std::size_t... I>
1984decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) {
1985  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1986}
1987 
1988} // end namespace detail
1989 
1990/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1991/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1992/// return the result.
1993template <typename F, typename Tuple>
1994decltype(auto) apply_tuple(F &&f, Tuple &&t) {
1995  using Indices = std::make_index_sequence<
1996      std::tuple_size<typename std::decay<Tuple>::type>::value>;
1997 
1998  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1999                                  Indices{});
2000}
2001 
2002namespace detail {
2003 
2004template <typename Predicate, typename... Args>
2005bool all_of_zip_predicate_first(Predicate &&P, Args &&...args) {
2006  auto z = zip(args...);
2007  auto it = z.begin();
2008  auto end = z.end();
2009  while (it != end) {
2010    if (!apply_tuple([&](auto &&...args) { return P(args...); }, *it))
2011      return false;
2012    ++it;
2013  }
2014  return it.all_equals(end);
2015}
2016 
2017// Just an adaptor to switch the order of argument and have the predicate before
2018// the zipped inputs.
2019template <typename... ArgsThenPredicate, size_t... InputIndexes>
2020bool all_of_zip_predicate_last(
2021    std::tuple<ArgsThenPredicate...> argsThenPredicate,
2022    std::index_sequence<InputIndexes...>) {
2023  auto constexpr OutputIndex =
2024      std::tuple_size<decltype(argsThenPredicate)>::value - 1;
2025  return all_of_zip_predicate_first(std::get<OutputIndex>(argsThenPredicate),
2026                             std::get<InputIndexes>(argsThenPredicate)...);
2027}
2028 
2029} // end namespace detail
2030 
2031/// Compare two zipped ranges using the provided predicate (as last argument).
2032/// Return true if all elements satisfy the predicate and false otherwise.
2033//  Return false if the zipped iterator aren't all at end (size mismatch).
2034template <typename... ArgsAndPredicate>
2035bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) {
2036  return detail::all_of_zip_predicate_last(
2037      std::forward_as_tuple(argsAndPredicate...),
2038      std::make_index_sequence<sizeof...(argsAndPredicate) - 1>{});
2039}
2040 
2041/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
2042/// time. Not meant for use with random-access iterators.
2043/// Can optionally take a predicate to filter lazily some items.
2044template <typename IterTy,
2045          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2046bool hasNItems(
2047    IterTy &&Begin, IterTy &&End, unsigned N,
2048    Pred &&ShouldBeCounted =
2049        [](const decltype(*std::declval<IterTy>()) &) { return true; },
2050    std::enable_if_t<
2051        !std::is_base_of<std::random_access_iterator_tag,
2052                         typename std::iterator_traits<std::remove_reference_t<
2053                             decltype(Begin)>>::iterator_category>::value,
2054        void> * = nullptr) {
2055  for (; N; ++Begin) {
2056    if (Begin == End)
2057      return false; // Too few.
2058    N -= ShouldBeCounted(*Begin);
2059  }
2060  for (; Begin != End; ++Begin)
2061    if (ShouldBeCounted(*Begin))
2062      return false; // Too many.
2063  return true;
2064}
2065 
2066/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
2067/// time. Not meant for use with random-access iterators.
2068/// Can optionally take a predicate to lazily filter some items.
2069template <typename IterTy,
2070          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2071bool hasNItemsOrMore(
2072    IterTy &&Begin, IterTy &&End, unsigned N,
2073    Pred &&ShouldBeCounted =
2074        [](const decltype(*std::declval<IterTy>()) &) { return true; },
2075    std::enable_if_t<
2076        !std::is_base_of<std::random_access_iterator_tag,
2077                         typename std::iterator_traits<std::remove_reference_t<
2078                             decltype(Begin)>>::iterator_category>::value,
2079        void> * = nullptr) {
2080  for (; N; ++Begin) {
2081    if (Begin == End)
2082      return false; // Too few.
2083    N -= ShouldBeCounted(*Begin);
2084  }
2085  return true;
2086}
2087 
2088/// Returns true if the sequence [Begin, End) has N or less items. Can
2089/// optionally take a predicate to lazily filter some items.
2090template <typename IterTy,
2091          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2092bool hasNItemsOrLess(
2093    IterTy &&Begin, IterTy &&End, unsigned N,
2094    Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
2095      return true;
2096    }) {
2097  assert(N != std::numeric_limits<unsigned>::max())(static_cast <bool> (N != std::numeric_limits<unsigned
>::max()) ? void (0) : __assert_fail ("N != std::numeric_limits<unsigned>::max()"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/STLExtras.h"
, 2097, __extension__ __PRETTY_FUNCTION__));
2098  return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
2099}
2100 
2101/// Returns true if the given container has exactly N items
2102template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
2103  return hasNItems(std::begin(C), std::end(C), N);
2104}
2105 
2106/// Returns true if the given container has N or more items
2107template <typename ContainerTy>
2108bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
2109  return hasNItemsOrMore(std::begin(C), std::end(C), N);
2110}
2111 
2112/// Returns true if the given container has N or less items
2113template <typename ContainerTy>
2114bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
2115  return hasNItemsOrLess(std::begin(C), std::end(C), N);
2116}
2117 
2118/// Returns a raw pointer that represents the same address as the argument.
2119///
2120/// This implementation can be removed once we move to C++20 where it's defined
2121/// as std::to_address().
2122///
2123/// The std::pointer_traits<>::to_address(p) variations of these overloads has
2124/// not been implemented.
2125template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
2126template <class T> constexpr T *to_address(T *P) { return P; }
2127 
2128} // end namespace llvm
2129 
2130#endif // LLVM_ADT_STLEXTRAS_H

←

/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/stl_iterator.h

1// Iterators -*- C++ -*-

3// Copyright (C) 2001-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.

20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.

25/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996-1998
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*/

51/** @file bits/stl_iterator.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{iterator}
*
*  This file implements reverse_iterator, back_insert_iterator,
*  front_insert_iterator, insert_iterator, __normal_iterator, and their
*  supporting functions and overloaded operators.
*/

60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1

63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>

68#if __cplusplus201402L >= 201103L
69# include <type_traits>
70#endif

72#if __cplusplus201402L > 201703L
73# define __cpp_lib_array_constexpr 201811L
74# define __cpp_lib_constexpr_iterator 201811L
75#elif __cplusplus201402L == 201703L
76# define __cpp_lib_array_constexpr 201803L
77#endif

79#if __cplusplus201402L > 201703L
80# include <compare>
81# include <new>
82# include <bits/iterator_concepts.h>
83#endif

85namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * @addtogroup iterators
 * @{
 */

94#if __cplusplus201402L > 201703L && __cpp_lib_concepts
namespace __detail
{
  // Weaken iterator_category _Cat to _Limit if it is derived from that,
  // otherwise use _Otherwise.
  template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
    using __clamp_iter_cat
= conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
}
103#endif

// 24.4.1 Reverse iterators
/**
 *  Bidirectional and random access iterators have corresponding reverse
 *  %iterator adaptors that iterate through the data structure in the
 *  opposite direction.  They have the same signatures as the corresponding
 *  iterators.  The fundamental relation between a reverse %iterator and its
 *  corresponding %iterator @c i is established by the identity:
 *  @code
 *      &*(reverse_iterator(i)) == &*(i - 1)
 *  @endcode
 *
 *  <em>This mapping is dictated by the fact that while there is always a
 *  pointer past the end of an array, there might not be a valid pointer
 *  before the beginning of an array.</em> [24.4.1]/1,2
 *
 *  Reverse iterators can be tricky and surprising at first.  Their
 *  semantics make sense, however, and the trickiness is a side effect of
 *  the requirement that the iterators must be safe.
*/
template<typename _Iterator>
  class reverse_iterator
  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
      typename iterator_traits<_Iterator>::value_type,
      typename iterator_traits<_Iterator>::difference_type,
      typename iterator_traits<_Iterator>::pointer,
                    typename iterator_traits<_Iterator>::reference>
  {
  protected:
    _Iterator current;

    typedef iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::difference_type	difference_type;
    typedef typename __traits_type::pointer		pointer;
    typedef typename __traits_type::reference		reference;

143#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept
= conditional_t<random_access_iterator<_Iterator>,
	random_access_iterator_tag,
	bidirectional_iterator_tag>;
    using iterator_category
= __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
		     random_access_iterator_tag>;
151#endif

    /**
     *  The default constructor value-initializes member @p current.
     *  If it is a pointer, that means it is zero-initialized.
    */
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 235 No specification of default ctor for reverse_iterator
    // 1012. reverse_iterator default ctor should value initialize
    _GLIBCXX17_CONSTEXPR
    reverse_iterator() : current() { }

    /**
     *  This %iterator will move in the opposite direction that @p x does.
    */
    explicit _GLIBCXX17_CONSTEXPR
    reverse_iterator(iterator_type __x) : current(__x) { }

    /**
     *  The copy constructor is normal.
    */
    _GLIBCXX17_CONSTEXPR
    reverse_iterator(const reverse_iterator& __x)
    : current(__x.current) { }

176#if __cplusplus201402L >= 201103L
    reverse_iterator& operator=(const reverse_iterator&) = default;
178#endif

    /**
     *  A %reverse_iterator across other types can be copied if the
     *  underlying %iterator can be converted to the type of @c current.
    */
    template<typename _Iter>
_GLIBCXX17_CONSTEXPR
      reverse_iterator(const reverse_iterator<_Iter>& __x)
: current(__x.base()) { }

    /**
     *  @return  @c current, the %iterator used for underlying work.
    */
    _GLIBCXX17_CONSTEXPR iterator_type
    base() const
    { return current; }

    /**
     *  @return  A reference to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
     *
     *  @warning This implementation requires that for an iterator of the
     *           underlying iterator type, @c x, a reference obtained by
     *           @c *x remains valid after @c x has been modified or
     *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
    */
    _GLIBCXX17_CONSTEXPR reference
    operator*() const
    {
_Iterator __tmp = current;
return *--__tmp;
    }

    /**
     *  @return  A pointer to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
    */
    _GLIBCXX17_CONSTEXPR pointer
    operator->() const
220#if __cplusplus201402L > 201703L && __cpp_concepts >= 201907L
    requires is_pointer_v<_Iterator>
|| requires(const _Iterator __i) { __i.operator->(); }
223#endif
    {
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 1052. operator-> should also support smart pointers
_Iterator __tmp = current;
--__tmp;
return _S_to_pointer(__tmp);
    }

    /**
     *  @return  @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator++()
    {
--current;
return *this;
    }

    /**
     *  @return  The original value of @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator++(int)
    {
reverse_iterator __tmp = *this;
--current;
return __tmp;
    }

    /**
     *  @return  @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator--()
    {
++current;
return *this;
    }

    /**
     *  @return  A reverse_iterator with the previous value of @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator--(int)
    {
reverse_iterator __tmp = *this;
++current;
return __tmp;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator+(difference_type __n) const
    { return reverse_iterator(current - __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator backwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator+=(difference_type __n)
    {
current -= __n;
return *this;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator
    operator-(difference_type __n) const
    { return reverse_iterator(current + __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator forwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reverse_iterator&
    operator-=(difference_type __n)
    {
current += __n;
return *this;
    }

    /**
     *  @return  The value at @c current - @a __n - 1
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPR reference
    operator[](difference_type __n) const
    { return *(*this + __n); }

335#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    friend constexpr iter_rvalue_reference_t<_Iterator>
    iter_move(const reverse_iterator& __i)
    noexcept(is_nothrow_copy_constructible_v<_Iterator>
      && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
    {
auto __tmp = __i.base();
return ranges::iter_move(--__tmp);
    }

    template<indirectly_swappable<_Iterator> _Iter2>
friend constexpr void
iter_swap(const reverse_iterator& __x,
  const reverse_iterator<_Iter2>& __y)
noexcept(is_nothrow_copy_constructible_v<_Iterator>
 && is_nothrow_copy_constructible_v<_Iter2>
 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
			       --std::declval<_Iter2&>())))
{
 auto __xtmp = __x.base();
 auto __ytmp = __y.base();
 ranges::iter_swap(--__xtmp, --__ytmp);
}
358#endif

  private:
    template<typename _Tp>
static _GLIBCXX17_CONSTEXPR _Tp*
_S_to_pointer(_Tp* __p)
      { return __p; }

    template<typename _Tp>
static _GLIBCXX17_CONSTEXPR pointer
_S_to_pointer(_Tp __t)
      { return __t.operator->(); }
  };

//@{
/**
 *  @param  __x  A %reverse_iterator.
 *  @param  __y  A %reverse_iterator.
 *  @return  A simple bool.
 *
 *  Reverse iterators forward comparisons to their underlying base()
 *  iterators.
 *
*/
382#if __cplusplus201402L <= 201703L || ! defined __cpp_lib_concepts
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() < __x.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x == __y); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x < __y); }

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 280. Comparison of reverse_iterator to const reverse_iterator.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() < __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x == __y); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x < __y); }
456#else // C++20
template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
  { return __x.base() != __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
  { return __x.base() > __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
  { return __x.base() >= __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
  { return __x.base() <= __y.base(); }

template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const reverse_iterator<_IteratorL>& __x,
const reverse_iterator<_IteratorR>& __y)
  { return __y.base() <=> __x.base(); }
505#endif // C++20
//@}

508#if __cplusplus201402L < 201103L
template<typename _Iterator>
  inline typename reverse_iterator<_Iterator>::difference_type
  operator-(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() - __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline typename reverse_iterator<_IteratorL>::difference_type
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() - __x.base(); }
520#else
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 685. reverse_iterator/move_iterator difference has invalid signatures
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR auto
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  -> decltype(__y.base() - __x.base())
  { return __y.base() - __x.base(); }
529#endif

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     const reverse_iterator<_Iterator>& __x)
  { return reverse_iterator<_Iterator>(__x.base() - __n); }

537#if __cplusplus201402L >= 201103L
// Same as C++14 make_reverse_iterator but used in C++11 mode too.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  __make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

544# if __cplusplus201402L >= 201402L
545#  define __cpp_lib_make_reverse_iterator201402 201402

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 2285. make_reverse_iterator
/// Generator function for reverse_iterator.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
  make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

555#  if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
template<typename _Iterator1, typename _Iterator2>
  requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
  inline constexpr bool
  disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
	       reverse_iterator<_Iterator2>> = true;
561#  endif // C++20
562# endif // C++14

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __niter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
  { return __make_reverse_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<reverse_iterator<_Iterator> >
    : __is_move_iterator<_Iterator>
  { };

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __miter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
  { return __make_reverse_iterator(__miter_base(__it.base())); }
582#endif // C++11

// 24.4.2.2.1 back_insert_iterator
/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator appends it to the container using
 *  push_back.
 *
 *  Tip:  Using the back_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class back_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
605#if __cplusplus201402L > 201703L
    using difference_type = ptrdiff_t;

    constexpr back_insert_iterator() noexcept : container(nullptr) { }
609#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    back_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the end, if you like).  Assigning a value to the %iterator will
     *  always append the value to the end of the container.
    */
627#if __cplusplus201402L < 201103L
    back_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_back(__value);
return *this;
    }
634#else
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_back(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_back(std::move(__value));
return *this;
    }
650#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of back_insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating back_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline back_insert_iterator<_Container>
  back_inserter(_Container& __x)
  { return back_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator prepends it to the container using
 *  push_front.
 *
 *  Tip:  Using the front_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class front_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
708#if __cplusplus201402L > 201703L
    using difference_type = ptrdiff_t;

    constexpr front_insert_iterator() noexcept : container(nullptr) { }
712#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    front_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the front, if you like).  Assigning a value to the %iterator will
     *  always prepend the value to the front of the container.
    */
730#if __cplusplus201402L < 201103L
    front_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_front(__value);
return *this;
    }
737#else
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_front(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_front(std::move(__value));
return *this;
    }
753#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of front_insert_iterator working on @p x.
 *
 *  This wrapper function helps in creating front_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline front_insert_iterator<_Container>
  front_inserter(_Container& __x)
  { return front_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator inserts it in the container at the
 *  %iterator's position, rather than overwriting the value at that
 *  position.
 *
 *  (Sequences will actually insert a @e copy of the value before the
 *  %iterator's position.)
 *
 *  Tip:  Using the inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
809#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
    using _Iter = std::__detail::__range_iter_t<_Container>;

  protected:
    _Container* container = nullptr;
    _Iter iter = _Iter();
815#else
    typedef typename _Container::iterator		_Iter;

  protected:
    _Container* container;
    _Iter iter;
821#endif

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;

827#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
    using difference_type = ptrdiff_t;

    insert_iterator() = default;
831#endif

    /**
     *  The only way to create this %iterator is with a container and an
     *  initial position (a normal %iterator into the container).
    */
    _GLIBCXX20_CONSTEXPR
    insert_iterator(_Container& __x, _Iter __i)
    : container(std::__addressof(__x)), iter(__i) {}

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator maintains its own position in the
     *  container.  Assigning a value to the %iterator will insert the
     *  value into the container at the place before the %iterator.
     *
     *  The position is maintained such that subsequent assignments will
     *  insert values immediately after one another.  For example,
     *  @code
     *     // vector v contains A and Z
     *
     *     insert_iterator i (v, ++v.begin());
     *     i = 1;
     *     i = 2;
     *     i = 3;
     *
     *     // vector v contains A, 1, 2, 3, and Z
     *  @endcode
    */
864#if __cplusplus201402L < 201103L
    insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }
872#else
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
iter = container->insert(iter, std::move(__value));
++iter;
return *this;
    }
890#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++(int)
    { return *this; }
  };

/**
 *  @param __x  A container of arbitrary type.
 *  @param __i  An iterator into the container.
 *  @return  An instance of insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
923#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
template<typename _Container>
  constexpr insert_iterator<_Container>
  inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
  { return insert_iterator<_Container>(__x, __i); }
928#else
template<typename _Container, typename _Iterator>
  inline insert_iterator<_Container>
  inserter(_Container& __x, _Iterator __i)
  {
    return insert_iterator<_Container>(__x,
			 typename _Container::iterator(__i));
  }
936#endif

// @} group iterators

940_GLIBCXX_END_NAMESPACE_VERSION
941} // namespace

943namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
944{
945_GLIBCXX_BEGIN_NAMESPACE_VERSION

// This iterator adapter is @a normal in the sense that it does not
// change the semantics of any of the operators of its iterator
// parameter.  Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
template<typename _Iterator, typename _Container>
  class __normal_iterator
  {
  protected:
    _Iterator _M_current;

    typedef std::iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type 	difference_type;
    typedef typename __traits_type::reference 	reference;
    typedef typename __traits_type::pointer   	pointer;

970#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept = std::__detail::__iter_concept<_Iterator>;
972#endif

    _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(_Iterator()) { }

    explicit _GLIBCXX20_CONSTEXPR
    __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(__i) { }

    // Allow iterator to const_iterator conversion
    template<typename _Iter>
      _GLIBCXX20_CONSTEXPR
      __normal_iterator(const __normal_iterator<_Iter,
	  typename __enable_if<
    	       (std::__are_same<_Iter, typename _Container::pointer>::__value),
      _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
      : _M_current(__i.base()) { }

    // Forward iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator*() const _GLIBCXX_NOEXCEPTnoexcept
    { return *_M_current; }

    _GLIBCXX20_CONSTEXPR
    pointer
    operator->() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator++() _GLIBCXX_NOEXCEPTnoexcept
    {
++_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator++(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current++); }

    // Bidirectional iterator requirements
    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator--() _GLIBCXX_NOEXCEPTnoexcept
    {
--_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator--(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current--); }

    // Random access iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current[__n]; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current += __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current + __n); }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current -= __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current - __n); }

    _GLIBCXX20_CONSTEXPR
    const _Iterator&
    base() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }
  };

// Note: In what follows, the left- and right-hand-side iterators are
// allowed to vary in types (conceptually in cv-qualification) so that
// comparison between cv-qualified and non-cv-qualified iterators be
// valid.  However, the greedy and unfriendly operators in std::rel_ops
// will make overload resolution ambiguous (when in scope) if we don't
// provide overloads whose operands are of the same type.  Can someone
// remind me what generic programming is about? -- Gaby

1068#if __cpp_lib_three_way_comparison
template<typename _IteratorL, typename _IteratorR, typename _Container>
  requires requires (_IteratorL __lhs, _IteratorR __rhs)
  { { __lhs == __rhs } -> std::convertible_to<bool>; }
  constexpr bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(__lhs.base() == __rhs.base()))
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
  operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
  { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1084#else
 // Forward iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }
19
←
Assuming the condition is false→
20
←
Returning zero, which participates in a condition later→

// Random access iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }
1178#endif // three-way comparison

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// According to the resolution of DR179 not only the various comparison
// operators but also operator- must accept mixed iterator/const_iterator
// parameters.
template<typename _IteratorL, typename _IteratorR, typename _Container>
1185#if __cplusplus201402L >= 201103L
  // DR 685.
  _GLIBCXX20_CONSTEXPR
  inline auto
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
  -> decltype(__lhs.base() - __rhs.base())
1192#else
  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
1196#endif
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline typename __normal_iterator<_Iterator, _Container>::difference_type
  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline __normal_iterator<_Iterator, _Container>
  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
     __n, const __normal_iterator<_Iterator, _Container>& __i)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

1215_GLIBCXX_END_NAMESPACE_VERSION
1216} // namespace

1218namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
1219{
1220_GLIBCXX_BEGIN_NAMESPACE_VERSION

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  _Iterator
  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
  _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)noexcept(std::is_nothrow_copy_constructible<_Iterator>::
value)
  { return __it.base(); }

1229#if __cplusplus201402L >= 201103L
/**
 * @addtogroup iterators
 * @{
 */

1235#if __cplusplus201402L > 201703L && __cpp_lib_concepts
template<semiregular _Sent>
  class move_sentinel
  {
  public:
    constexpr
    move_sentinel()
    noexcept(is_nothrow_default_constructible_v<_Sent>)
    : _M_last() { }

    constexpr explicit
    move_sentinel(_Sent __s)
    noexcept(is_nothrow_move_constructible_v<_Sent>)
    : _M_last(std::move(__s)) { }

    template<typename _S2> requires convertible_to<const _S2&, _Sent>
constexpr
move_sentinel(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
: _M_last(__s.base())
{ }

    template<typename _S2> requires assignable_from<_Sent&, const _S2&>
constexpr move_sentinel&
operator=(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
{
 _M_last = __s.base();
 return *this;
}

    constexpr _Sent
    base() const
    noexcept(is_nothrow_copy_constructible_v<_Sent>)
    { return _M_last; }

  private:
    _Sent _M_last;
  };
1274#endif // C++20

// 24.4.3  Move iterators
/**
 *  Class template move_iterator is an iterator adapter with the same
 *  behavior as the underlying iterator except that its dereference
 *  operator implicitly converts the value returned by the underlying
 *  iterator's dereference operator to an rvalue reference.  Some
 *  generic algorithms can be called with move iterators to replace
 *  copying with moving.
 */
template<typename _Iterator>
  class move_iterator
  {
    _Iterator _M_current;

    using __traits_type = iterator_traits<_Iterator>;
1291#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using __base_cat = typename __traits_type::iterator_category;
1293#else
    using __base_ref = typename __traits_type::reference;
1295#endif

  public:
    using iterator_type = _Iterator;

1300#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    using iterator_concept = input_iterator_tag;
    using iterator_category
= __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
    using value_type = iter_value_t<_Iterator>;
    using difference_type = iter_difference_t<_Iterator>;
    using pointer = _Iterator;
    using reference = iter_rvalue_reference_t<_Iterator>;
1308#else
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type	difference_type;
    // NB: DR 680.
    typedef _Iterator					pointer;
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2106. move_iterator wrapping iterators returning prvalues
    typedef typename conditional<is_reference<__base_ref>::value,
	 typename remove_reference<__base_ref>::type&&,
	 __base_ref>::type		reference;
1319#endif

    _GLIBCXX17_CONSTEXPR
    move_iterator()
    : _M_current() { }

    explicit _GLIBCXX17_CONSTEXPR
    move_iterator(iterator_type __i)
    : _M_current(std::move(__i)) { }

    template<typename _Iter>
_GLIBCXX17_CONSTEXPR
move_iterator(const move_iterator<_Iter>& __i)
: _M_current(__i.base()) { }

1334#if __cplusplus201402L <= 201703L
    _GLIBCXX17_CONSTEXPR iterator_type
    base() const
    { return _M_current; }
1338#else
    constexpr iterator_type
    base() const &
1341#if __cpp_lib_concepts
requires copy_constructible<iterator_type>
1343#endif
    { return _M_current; }

    constexpr iterator_type
    base() &&
    { return std::move(_M_current); }
1349#endif

    _GLIBCXX17_CONSTEXPR reference
    operator*() const
1353#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    { return ranges::iter_move(_M_current); }
1355#else
    { return static_cast<reference>(*_M_current); }
1357#endif

    _GLIBCXX17_CONSTEXPR pointer
    operator->() const
    { return _M_current; }

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator++()
    {
++_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator++(int)
    {
move_iterator __tmp = *this;
++_M_current;
return __tmp;
    }

1378#if __cpp_lib_concepts
    constexpr void
    operator++(int) requires (!forward_iterator<_Iterator>)
    { ++_M_current; }
1382#endif

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator--()
    {
--_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator--(int)
    {
move_iterator __tmp = *this;
--_M_current;
return __tmp;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator+(difference_type __n) const
    { return move_iterator(_M_current + __n); }

    _GLIBCXX17_CONSTEXPR move_iterator&
    operator+=(difference_type __n)
    {
_M_current += __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPR move_iterator
    operator-(difference_type __n) const
    { return move_iterator(_M_current - __n); }
  
    _GLIBCXX17_CONSTEXPR move_iterator&
    operator-=(difference_type __n)
    { 
_M_current -= __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPR reference
    operator[](difference_type __n) const
1423#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    { return ranges::iter_move(_M_current + __n); }
1425#else
    { return std::move(_M_current[__n]); }
1427#endif

1429#if __cplusplus201402L > 201703L && __cpp_lib_concepts
    template<sentinel_for<_Iterator> _Sent>
friend constexpr bool
operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() == __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
{ return __x.base() - __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() - __y.base(); }

    friend constexpr iter_rvalue_reference_t<_Iterator>
    iter_move(const move_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_Iterator> _Iter2>
friend constexpr void
iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ return ranges::iter_swap(__x._M_current, __y._M_current); }
1455#endif // C++20
  };

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1462#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1464#endif
  { return __x.base() == __y.base(); }

1467#if __cpp_lib_three_way_comparison
template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const move_iterator<_IteratorL>& __x,
const move_iterator<_IteratorR>& __y)
  { return __x.base() <=> __y.base(); }
1474#else
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
  { return !(__x == __y); }
1480#endif

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1486#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1488#endif
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1495#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1497#endif
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1504#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1506#endif
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1513#if __cplusplus201402L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1515#endif
  { return !(__x < __y); }

1518#if ! (__cplusplus201402L > 201703L && __cpp_lib_concepts)
// Note: See __normal_iterator operators note from Gaby to understand
// why we have these extra overloads for some move_iterator operators.

// These extra overloads are not needed in C++20, because the ones above
// are constrained with a requires-clause and so overload resolution will
// prefer them to greedy unconstrained function templates.

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator==(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator!=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x == __y); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __x.base() < __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator<=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR bool
  operator>=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x < __y); }
1561#endif // ! C++20

// DR 685.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPR auto
  operator-(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
  -> decltype(__x.base() - __y.base())
  { return __x.base() - __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
  operator+(typename move_iterator<_Iterator>::difference_type __n,
     const move_iterator<_Iterator>& __x)
  { return __x + __n; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
  make_move_iterator(_Iterator __i)
  { return move_iterator<_Iterator>(std::move(__i)); }

template<typename _Iterator, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond
    <typename iterator_traits<_Iterator>::value_type>::value,
              _Iterator, move_iterator<_Iterator>>::type>
  inline _GLIBCXX17_CONSTEXPR _ReturnType
  __make_move_if_noexcept_iterator(_Iterator __i)
  { return _ReturnType(__i); }

// Overload for pointers that matches std::move_if_noexcept more closely,
// returning a constant iterator when we don't want to move.
template<typename _Tp, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
	   const _Tp*, move_iterator<_Tp*>>::type>
  inline _GLIBCXX17_CONSTEXPR _ReturnType
  __make_move_if_noexcept_iterator(_Tp* __i)
  { return _ReturnType(__i); }

1599#if __cplusplus201402L > 201703L && __cpp_lib_concepts
// [iterators.common] Common iterators

namespace __detail
{
  template<typename _It>
    concept __common_iter_has_arrow = indirectly_readable<const _It>
&& (requires(const _It& __it) { __it.operator->(); }
   || is_reference_v<iter_reference_t<_It>>
   || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);

} // namespace __detail

/// An iterator/sentinel adaptor for representing a non-common range.
template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
  requires (!same_as<_It, _Sent>) && copyable<_It>
class common_iterator
{
  template<typename _Tp, typename _Up>
    static constexpr bool
    _S_noexcept1()
    {
if constexpr (is_trivially_default_constructible_v<_Tp>)
 return is_nothrow_assignable_v<_Tp, _Up>;
else
 return is_nothrow_constructible_v<_Tp, _Up>;
    }

  template<typename _It2, typename _Sent2>
    static constexpr bool
    _S_noexcept()
    { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }

  class _Proxy
  {
    iter_value_t<_It> _M_keep;

    _Proxy(iter_reference_t<_It>&& __x)
    : _M_keep(std::move(__x)) { }

    friend class common_iterator;

  public:
    const iter_value_t<_It>*
    operator->() const
    { return std::__addressof(_M_keep); }
  };

public:
  constexpr
  common_iterator()
  noexcept(is_nothrow_default_constructible_v<_It>)
  : _M_it(), _M_index(0)
  { }

  constexpr
  common_iterator(_It __i)
  noexcept(is_nothrow_move_constructible_v<_It>)
  : _M_it(std::move(__i)), _M_index(0)
  { }

  constexpr
  common_iterator(_Sent __s)
  noexcept(is_nothrow_move_constructible_v<_Sent>)
  : _M_sent(std::move(__s)), _M_index(1)
  { }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
    constexpr
    common_iterator(const common_iterator<_It2, _Sent2>& __x)
    noexcept(_S_noexcept<const _It2&, const _Sent2&>())
    : _M_valueless(), _M_index(__x._M_index)
    {
if (_M_index == 0)
 {
   if constexpr (is_trivially_default_constructible_v<_It>)
     _M_it = std::move(__x._M_it);
   else
     ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
 }
else if (_M_index == 1)
 {
   if constexpr (is_trivially_default_constructible_v<_Sent>)
     _M_sent = std::move(__x._M_sent);
   else
     ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
 }
    }

  constexpr
  common_iterator(const common_iterator& __x)
  noexcept(_S_noexcept<const _It&, const _Sent&>())
  : _M_valueless(), _M_index(__x._M_index)
  {
    if (_M_index == 0)
{
 if constexpr (is_trivially_default_constructible_v<_It>)
   _M_it = std::move(__x._M_it);
 else
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
}
    else if (_M_index == 1)
{
 if constexpr (is_trivially_default_constructible_v<_Sent>)
   _M_sent = std::move(__x._M_sent);
 else
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
}
  }

  common_iterator&
  operator=(const common_iterator& __x)
  noexcept(is_nothrow_copy_assignable_v<_It>
    && is_nothrow_copy_assignable_v<_Sent>
    && is_nothrow_copy_constructible_v<_It>
    && is_nothrow_copy_constructible_v<_Sent>)
  {
    return this->operator=<_It, _Sent>(__x);
  }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
&& assignable_from<_It&, const _It2&>
&& assignable_from<_Sent&, const _Sent2&>
    common_iterator&
    operator=(const common_iterator<_It2, _Sent2>& __x)
    noexcept(is_nothrow_constructible_v<_It, const _It2&>
      && is_nothrow_constructible_v<_Sent, const _Sent2&>
      && is_nothrow_assignable_v<_It, const _It2&>
      && is_nothrow_assignable_v<_Sent, const _Sent2&>)
    {
switch(_M_index << 2 | __x._M_index)
 {
 case 0b0000:
   _M_it = __x._M_it;
   break;
 case 0b0101:
   _M_sent = __x._M_sent;
   break;
 case 0b0001:
   _M_it.~_It();
   _M_index = -1;
   [[fallthrough]];
 case 0b1001:
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
   _M_index = 1;
   break;
 case 0b0100:
   _M_sent.~_Sent();
   _M_index = -1;
   [[fallthrough]];
 case 0b1000:
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
   _M_index = 0;
   break;
 default:
   __glibcxx_assert(__x._M_has_value());
   __builtin_unreachable();
 }
return *this;
    }

  ~common_iterator()
  {
    switch (_M_index)
{
case 0:
 _M_it.~_It();
 break;
case 1:
 _M_sent.~_Sent();
 break;
}
  }

  decltype(auto)
  operator*()
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator*() const requires __detail::__dereferenceable<const _It>
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator->() const requires __detail::__common_iter_has_arrow<_It>
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
return _M_it;
    else if constexpr (is_reference_v<iter_reference_t<_It>>)
{
 auto&& __tmp = *_M_it;
 return std::__addressof(__tmp);
}
    else
return _Proxy{*_M_it};
  }

  common_iterator&
  operator++()
  {
    __glibcxx_assert(_M_index == 0);
    ++_M_it;
    return *this;
  }

  decltype(auto)
  operator++(int)
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (forward_iterator<_It>)
{
 common_iterator __tmp = *this;
 ++*this;
 return __tmp;
}
    else
return _M_it++;
  }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0000:
 case 0b0101:
   return true;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return true;
 case 0b0000:
   return __x._M_it == __y._M_it;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
    requires sized_sentinel_for<_Sent, _It2>
    friend iter_difference_t<_It2>
    operator-(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return 0;
 case 0b0000:
   return __x._M_it - __y._M_it;
 case 0b0001:
   return __x._M_it - __y._M_sent;
 case 0b0100:
   return __x._M_sent - __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  friend iter_rvalue_reference_t<_It>
  iter_move(const common_iterator& __i)
  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
  requires input_iterator<_It>
  {
    __glibcxx_assert(__i._M_index == 0);
    return ranges::iter_move(__i._M_it);
  }

  template<indirectly_swappable<_It> _It2, typename _Sent2>
    friend void
    iter_swap(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
			  std::declval<const _It2&>())))
    {
__glibcxx_assert(__x._M_index == 0);
__glibcxx_assert(__y._M_index == 0);
return ranges::iter_swap(__x._M_it, __y._M_it);
    }

private:
  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
    friend class common_iterator;

  bool _M_has_value() const noexcept { return _M_index < 2; }

  union
  {
    _It _M_it;
    _Sent _M_sent;
    unsigned char _M_valueless;
  };
  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
};

template<typename _It, typename _Sent>
  struct incrementable_traits<common_iterator<_It, _Sent>>
  {
    using difference_type = iter_difference_t<_It>;
  };

template<input_iterator _It, typename _Sent>
  struct iterator_traits<common_iterator<_It, _Sent>>
  {
  private:
    template<typename _Iter>
struct __ptr
{
 using type = void;
};

    template<typename _Iter>
requires __detail::__common_iter_has_arrow<_Iter>
struct __ptr<_Iter>
{
 using _CIter = common_iterator<_Iter, _Sent>;
 using type = decltype(std::declval<const _CIter&>().operator->());
};

  public:
    using iterator_concept = conditional_t<forward_iterator<_It>,
   forward_iterator_tag, input_iterator_tag>;
    using iterator_category = __detail::__clamp_iter_cat<
typename iterator_traits<_It>::iterator_category,
forward_iterator_tag, input_iterator_tag>;
    using value_type = iter_value_t<_It>;
    using difference_type = iter_difference_t<_It>;
    using pointer = typename __ptr<_It>::type;
    using reference = iter_reference_t<_It>;
  };

// [iterators.counted] Counted iterators

/// An iterator adaptor that keeps track of the distance to the end.
template<input_or_output_iterator _It>
  class counted_iterator
  {
  public:
    using iterator_type = _It;

    constexpr counted_iterator() = default;

    constexpr
    counted_iterator(_It __i, iter_difference_t<_It> __n)
    : _M_current(std::move(__i)), _M_length(__n)
    { __glibcxx_assert(__n >= 0); }

    template<typename _It2>
requires convertible_to<const _It2&, _It>
constexpr
counted_iterator(const counted_iterator<_It2>& __x)
: _M_current(__x._M_current), _M_length(__x._M_length)
{ }

    template<typename _It2>
requires assignable_from<_It&, const _It2&>
constexpr counted_iterator&
operator=(const counted_iterator<_It2>& __x)
{
 _M_current = __x._M_current;
 _M_length = __x._M_length;
 return *this;
}

    constexpr _It
    base() const &
    noexcept(is_nothrow_copy_constructible_v<_It>)
    requires copy_constructible<_It>
    { return _M_current; }

    constexpr _It
    base() &&
    noexcept(is_nothrow_move_constructible_v<_It>)
    { return std::move(_M_current); }

    constexpr iter_difference_t<_It>
    count() const noexcept { return _M_length; }

    constexpr decltype(auto)
    operator*()
    noexcept(noexcept(*_M_current))
    { return *_M_current; }

    constexpr decltype(auto)
    operator*() const
    noexcept(noexcept(*_M_current))
    requires __detail::__dereferenceable<const _It>
    { return *_M_current; }

    constexpr counted_iterator&
    operator++()
    {
__glibcxx_assert(_M_length > 0);
++_M_current;
--_M_length;
return *this;
    }

    decltype(auto)
    operator++(int)
    {
__glibcxx_assert(_M_length > 0);
--_M_length;
__tryif (true)
 {
   return _M_current++;
 } __catch(...)if (false) {
   ++_M_length;
   __throw_exception_again;
 }

    }

    constexpr counted_iterator
    operator++(int) requires forward_iterator<_It>
    {
auto __tmp = *this;
++*this;
return __tmp;
    }

    constexpr counted_iterator&
    operator--() requires bidirectional_iterator<_It>
    {
--_M_current;
++_M_length;
return *this;
    }

    constexpr counted_iterator
    operator--(int) requires bidirectional_iterator<_It>
    {
auto __tmp = *this;
--*this;
return __tmp;
    }

    constexpr counted_iterator
    operator+(iter_difference_t<_It> __n) const
requires random_access_iterator<_It>
    { return counted_iterator(_M_current + __n, _M_length - __n); }

    friend constexpr counted_iterator
    operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
    requires random_access_iterator<_It>
    { return __x + __n; }

    constexpr counted_iterator&
    operator+=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n <= _M_length);
_M_current += __n;
_M_length -= __n;
return *this;
    }

    constexpr counted_iterator
    operator-(iter_difference_t<_It> __n) const
    requires random_access_iterator<_It>
    { return counted_iterator(_M_current - __n, _M_length + __n); }

    template<common_with<_It> _It2>
friend constexpr iter_difference_t<_It2>
operator-(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
{ return __y._M_length - __x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(const counted_iterator& __x, default_sentinel_t)
    { return -__x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(default_sentinel_t, const counted_iterator& __y)
    { return __y._M_length; }

    constexpr counted_iterator&
    operator-=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(-__n <= _M_length);
_M_current -= __n;
_M_length += __n;
return *this;
    }

    constexpr decltype(auto)
    operator[](iter_difference_t<_It> __n) const
    noexcept(noexcept(_M_current[__n]))
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n < _M_length);
return _M_current[__n];
    }

    template<common_with<_It> _It2>
friend constexpr bool
operator==(const counted_iterator& __x,
   const counted_iterator<_It2>& __y)
{ return __x._M_length == __y._M_length; }

    friend constexpr bool
    operator==(const counted_iterator& __x, default_sentinel_t)
    { return __x._M_length == 0; }

    template<common_with<_It> _It2>
friend constexpr strong_ordering
operator<=>(const counted_iterator& __x,
    const counted_iterator<_It2>& __y)
{ return __y._M_length <=> __x._M_length; }

    friend constexpr iter_rvalue_reference_t<_It>
    iter_move(const counted_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    requires input_iterator<_It>
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_It> _It2>
friend constexpr void
iter_swap(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ ranges::iter_swap(__x._M_current, __y._M_current); }

  private:
    template<input_or_output_iterator _It2> friend class counted_iterator;

    _It _M_current = _It();
    iter_difference_t<_It> _M_length = 0;
  };

template<typename _It>
  struct incrementable_traits<counted_iterator<_It>>
  {
    using difference_type = iter_difference_t<_It>;
  };

template<input_iterator _It>
  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
  {
    using pointer = void;
  };
2179#endif // C++20

// @} group iterators

template<typename _Iterator>
  auto
  __niter_base(move_iterator<_Iterator> __it)
  -> decltype(make_move_iterator(__niter_base(__it.base())))
  { return make_move_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<move_iterator<_Iterator> >
  {
    enum { __value = 1 };
    typedef __true_type __type;
  };

template<typename _Iterator>
  auto
  __miter_base(move_iterator<_Iterator> __it)
  -> decltype(__miter_base(__it.base()))
  { return __miter_base(__it.base()); }

2202#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) std::make_move_iterator(_Iter)
2203#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) \
std::__make_move_if_noexcept_iterator(_Iter)
2205#else
2206#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) (_Iter)
2207#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) (_Iter)
2208#endif // C++11

2210#if __cpp_deduction_guides >= 201606
// These helper traits are used for deduction guides
// of associative containers.
template<typename _InputIterator>
  using __iter_key_t = remove_const_t<
  typename iterator_traits<_InputIterator>::value_type::first_type>;

template<typename _InputIterator>
  using __iter_val_t =
  typename iterator_traits<_InputIterator>::value_type::second_type;

template<typename _T1, typename _T2>
  struct pair;

template<typename _InputIterator>
  using __iter_to_alloc_t =
  pair<add_const_t<__iter_key_t<_InputIterator>>,
__iter_val_t<_InputIterator>>;
2228#endif // __cpp_deduction_guides

2230_GLIBCXX_END_NAMESPACE_VERSION
2231} // namespace

2233#ifdef _GLIBCXX_DEBUG
2234# include <debug/stl_iterator.h>
2235#endif

2237#endif