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

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~++20210903100615+fd66b44ec19e/build-llvm/lib/WindowsManifest -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -isystem /usr/include/libxml2 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/WindowsManifest -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/WindowsManifest -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D 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~++20210903100615+fd66b44ec19e/build-llvm/lib/WindowsManifest -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -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-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/WindowsManifest/WindowsManifestMerger.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/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//===---------------------------------------------------------------------===//
12
13#include "llvm/WindowsManifest/WindowsManifestMerger.h"
14#include "llvm/Config/config.h"
15#include "llvm/Support/MemoryBuffer.h"
16
17#include <map>
18
19#if LLVM_ENABLE_LIBXML21
20#include <libxml/xmlreader.h>
21#endif
22
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)
25
26using namespace llvm;
27using namespace windows_manifest;
28
29char WindowsManifestError::ID = 0;
30
31WindowsManifestError::WindowsManifestError(const Twine &Msg) : Msg(Msg.str()) {}
32
33void WindowsManifestError::log(raw_ostream &OS) const { OS << Msg; }
34
35class WindowsManifestMerger::WindowsManifestMergerImpl {
36public:
37 ~WindowsManifestMergerImpl();
38 Error merge(MemoryBufferRef Manifest);
39 std::unique_ptr<MemoryBuffer> getMergedManifest();
40
41private:
42 static void errorCallback(void *Ctx, const char *Format, ...);
43 Error getParseError();
44#if LLVM_ENABLE_LIBXML21
45 xmlDocPtr CombinedDoc = nullptr;
46 std::vector<xmlDocPtr> MergedDocs;
47
48 bool Merged = false;
49 struct XmlDeleter {
50 void operator()(xmlChar *Ptr) { xmlFree(Ptr); }
51 void operator()(xmlDoc *Ptr) { xmlFreeDoc(Ptr); }
52 };
53 int BufferSize = 0;
54 std::unique_ptr<xmlChar, XmlDeleter> Buffer;
55#endif
56 bool ParseErrorOccurred = false;
57};
58
59#if LLVM_ENABLE_LIBXML21
60
61static constexpr std::pair<StringLiteral, StringLiteral> MtNsHrefsPrefixes[] = {
62 {"urn:schemas-microsoft-com:asm.v1", "ms_asmv1"},
63 {"urn:schemas-microsoft-com:asm.v2", "ms_asmv2"},
64 {"urn:schemas-microsoft-com:asm.v3", "ms_asmv3"},
65 {"http://schemas.microsoft.com/SMI/2005/WindowsSettings",
66 "ms_windowsSettings"},
67 {"urn:schemas-microsoft-com:compatibility.v1", "ms_compatibilityv1"}};
68
69static bool xmlStringsEqual(const unsigned char *A, const unsigned char *B) {
70 // Handle null pointers. Comparison of 2 null pointers returns true because
71 // this indicates the prefix of a default namespace.
72 if (!A || !B)
73 return A == B;
74 return strcmp(FROM_XML_CHAR(A)reinterpret_cast<const char *>(A), FROM_XML_CHAR(B)reinterpret_cast<const char *>(B)) == 0;
75}
76
77static bool isMergeableElement(const unsigned char *ElementName) {
78 for (StringRef S : {"application", "assembly", "assemblyIdentity",
79 "compatibility", "noInherit", "requestedExecutionLevel",
80 "requestedPrivileges", "security", "trustInfo"}) {
81 if (S == FROM_XML_CHAR(ElementName)reinterpret_cast<const char *>(ElementName)) {
82 return true;
83 }
84 }
85 return false;
86}
87
88static xmlNodePtr getChildWithName(xmlNodePtr Parent,
89 const unsigned char *ElementName) {
90 for (xmlNodePtr Child = Parent->children; Child; Child = Child->next) {
91 if (xmlStringsEqual(Child->name, ElementName)) {
92 return Child;
93 }
94 }
95 return nullptr;
96}
97
98static xmlAttrPtr getAttribute(xmlNodePtr Node,
99 const unsigned char *AttributeName) {
100 for (xmlAttrPtr Attribute = Node->properties; Attribute != nullptr;
101 Attribute = Attribute->next) {
102 if (xmlStringsEqual(Attribute->name, AttributeName)) {
103 return Attribute;
104 }
105 }
106 return nullptr;
107}
108
109// Check if namespace specified by HRef1 overrides that of HRef2.
110static bool namespaceOverrides(const unsigned char *HRef1,
111 const unsigned char *HRef2) {
112 auto HRef1Position = llvm::find_if(
113 MtNsHrefsPrefixes, [=](const std::pair<StringRef, StringRef> &Element) {
114 return xmlStringsEqual(HRef1, TO_XML_CHAR(Element.first.data())reinterpret_cast<const unsigned char *>(Element.first.data
())
);
115 });
116 auto HRef2Position = llvm::find_if(
117 MtNsHrefsPrefixes, [=](const std::pair<StringRef, StringRef> &Element) {
118 return xmlStringsEqual(HRef2, TO_XML_CHAR(Element.first.data())reinterpret_cast<const unsigned char *>(Element.first.data
())
);
119 });
120 return HRef1Position < HRef2Position;
121}
122
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) {
127 for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
128 if (Def->prefix && xmlStringsEqual(Def->href, HRef)) {
129 return Def;
130 }
131 }
132 if (Node->parent) {
133 return search(HRef, Node->parent);
134 }
135 return nullptr;
136}
137
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) {
141 for (auto &Ns : MtNsHrefsPrefixes) {
142 if (xmlStringsEqual(HRef, TO_XML_CHAR(Ns.first.data())reinterpret_cast<const unsigned char *>(Ns.first.data()
)
)) {
143 return TO_XML_CHAR(Ns.second.data())reinterpret_cast<const unsigned char *>(Ns.second.data(
))
;
144 }
145 }
146 return HRef;
147}
148
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,
154 xmlNodePtr Node) {
155 if (xmlNsPtr Def = search(HRef, Node))
156 return Def;
157 if (xmlNsPtr Def = xmlNewNs(Node, HRef, getPrefixForHref(HRef)))
158 return Def;
159 return make_error<WindowsManifestError>("failed to create new namespace");
160}
161
162// Set the namespace of OrigionalAttribute on OriginalNode to be that of
163// AdditionalAttribute's.
164static Error copyAttributeNamespace(xmlAttrPtr OriginalAttribute,
165 xmlNodePtr OriginalNode,
166 xmlAttrPtr AdditionalAttribute) {
167
168 Expected<xmlNsPtr> ExplicitOrError =
169 searchOrDefine(AdditionalAttribute->ns->href, OriginalNode);
170 if (!ExplicitOrError)
171 return ExplicitOrError.takeError();
172 OriginalAttribute->ns = std::move(ExplicitOrError.get());
173 return Error::success();
174}
175
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,
179 xmlNodePtr Node) {
180 if (Node == nullptr)
181 return nullptr;
182 for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
183 if (xmlStringsEqual(Def->prefix, Prefix)) {
184 return Def;
185 }
186 }
187 return nullptr;
188}
189
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) {
194 if (xmlNsPtr Ret = getNamespaceWithPrefix(nullptr, Node))
195 return Ret;
196 if (Node->parent == nullptr)
197 return nullptr;
198 return getClosestDefault(Node->parent);
199}
200
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,
208 xmlNodePtr AdditionalNode) {
209 xmlNsPtr ClosestDefault = getClosestDefault(OriginalNode);
210 for (xmlAttrPtr Attribute = AdditionalNode->properties; Attribute;
211 Attribute = Attribute->next) {
212 if (xmlAttrPtr OriginalAttribute =
213 getAttribute(OriginalNode, Attribute->name)) {
214 if (!xmlStringsEqual(OriginalAttribute->children->content,
215 Attribute->children->content)) {
216 return make_error<WindowsManifestError>(
217 Twine("conflicting attributes for ") +
218 FROM_XML_CHAR(OriginalNode->name)reinterpret_cast<const char *>(OriginalNode->name));
219 }
220 if (!Attribute->ns) {
221 continue;
222 }
223 if (!OriginalAttribute->ns) {
224 if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
225 Attribute)) {
226 return E;
227 }
228 continue;
229 }
230 if (namespaceOverrides(OriginalAttribute->ns->href,
231 Attribute->ns->href)) {
232 // In this case, the original attribute has a higher priority namespace
233 // than the incomiing attribute, however the namespace definition of
234 // the lower priority namespace occurs first traveling upwards in the
235 // tree. Therefore the lower priority namespace is applied.
236 if (!OriginalAttribute->ns->prefix && !Attribute->ns->prefix &&
237 ClosestDefault &&
238 xmlStringsEqual(Attribute->ns->href, ClosestDefault->href)) {
239 if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
240 Attribute)) {
241 return E;
242 }
243 continue;
244 }
245 continue;
246 // This covers the case where the incoming attribute has the higher
247 // priority. The higher priority namespace is applied in all cases
248 // EXCEPT when both of the namespaces are default inherited, and the
249 // closest inherited default is the lower priority one.
250 }
251 if (Attribute->ns->prefix || OriginalAttribute->ns->prefix ||
252 (ClosestDefault && !xmlStringsEqual(OriginalAttribute->ns->href,
253 ClosestDefault->href))) {
254 if (auto E = copyAttributeNamespace(OriginalAttribute, OriginalNode,
255 Attribute)) {
256 return E;
257 }
258 continue;
259 }
260 continue;
261 }
262 // If the incoming attribute is not already found on the node, append it
263 // to the end of the properties list. Also explicitly apply its
264 // namespace as a prefix because it might be contained in a separate
265 // namespace that doesn't use the attribute.
266 xmlAttrPtr NewProp =
267 xmlNewProp(OriginalNode, Attribute->name, Attribute->children->content);
268 Expected<xmlNsPtr> ExplicitOrError =
269 searchOrDefine(Attribute->ns->href, OriginalNode);
270 if (!ExplicitOrError)
271 return ExplicitOrError.takeError();
272 NewProp->ns = std::move(ExplicitOrError.get());
273 }
274 return Error::success();
275}
276
277// Given two nodes, return the one with the higher priority namespace.
278static xmlNodePtr getDominantNode(xmlNodePtr Node1, xmlNodePtr Node2) {
279
280 if (!Node1 || !Node1->ns)
281 return Node2;
282 if (!Node2 || !Node2->ns)
283 return Node1;
284 if (namespaceOverrides(Node1->ns->href, Node2->ns->href))
285 return Node1;
286 return Node2;
287}
288
289// Checks if this Node's namespace is inherited or one it defined itself.
290static bool hasInheritedNs(xmlNodePtr Node) {
291 return Node->ns && Node->ns != getNamespaceWithPrefix(Node->ns->prefix, Node);
292}
293
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) {
297 return hasInheritedNs(Node) && Node->ns->prefix == nullptr;
298}
299
300// Check if this Node's namespace is a default namespace it defined itself.
301static bool hasDefinedDefaultNamespace(xmlNodePtr Node) {
302 return Node->ns && (Node->ns == getNamespaceWithPrefix(nullptr, Node));
303}
304
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) {
311 // If a node as its own default namespace definition it clearly cannot have
312 // inherited the given default namespace, and neither will any of its
313 // children.
314 if (hasDefinedDefaultNamespace(Node))
315 return;
316 if (Node->ns && xmlStringsEqual(Node->ns->href, PrefixDef->href) &&
317 hasInheritedDefaultNs(Node))
318 Node->ns = PrefixDef;
319 for (xmlAttrPtr Attribute = Node->properties; Attribute;
320 Attribute = Attribute->next) {
321 if (Attribute->ns &&
322 xmlStringsEqual(Attribute->ns->href, PrefixDef->href)) {
323 Attribute->ns = PrefixDef;
324 }
325 }
326 for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
327 explicateNamespace(PrefixDef, Child);
328 }
329}
330
331// Perform the namespace merge between two nodes.
332static Error mergeNamespaces(xmlNodePtr OriginalNode,
333 xmlNodePtr AdditionalNode) {
334 // Save the original default namespace definition in case the incoming node
335 // overrides it.
336 const unsigned char *OriginalDefinedDefaultHref = nullptr;
337 if (xmlNsPtr OriginalDefinedDefaultNs =
338 getNamespaceWithPrefix(nullptr, OriginalNode)) {
339 OriginalDefinedDefaultHref = xmlStrdup(OriginalDefinedDefaultNs->href);
340 }
341 const unsigned char *NewDefinedDefaultHref = nullptr;
342 // Copy all namespace definitions. There can only be one default namespace
343 // definition per node, so the higher priority one takes precedence in the
344 // case of collision.
345 for (xmlNsPtr Def = AdditionalNode->nsDef; Def; Def = Def->next) {
346 if (xmlNsPtr OriginalNsDef =
347 getNamespaceWithPrefix(Def->prefix, OriginalNode)) {
348 if (!Def->prefix) {
349 if (namespaceOverrides(Def->href, OriginalNsDef->href)) {
350 NewDefinedDefaultHref = TO_XML_CHAR(strdup(FROM_XML_CHAR(Def->href)))reinterpret_cast<const unsigned char *>(strdup(reinterpret_cast
<const char *>(Def->href)))
;
351 }
352 } else if (!xmlStringsEqual(OriginalNsDef->href, Def->href)) {
353 return make_error<WindowsManifestError>(
354 Twine("conflicting namespace definitions for ") +
355 FROM_XML_CHAR(Def->prefix)reinterpret_cast<const char *>(Def->prefix));
356 }
357 } else {
358 xmlNsPtr NewDef = xmlCopyNamespace(Def);
359 NewDef->next = OriginalNode->nsDef;
360 OriginalNode->nsDef = NewDef;
361 }
362 }
363
364 // Check whether the original node or the incoming node has the higher
365 // priority namespace. Depending on which one is dominant, we will have
366 // to recursively apply namespace changes down to children of the original
367 // node.
368 xmlNodePtr DominantNode = getDominantNode(OriginalNode, AdditionalNode);
369 xmlNodePtr NonDominantNode =
370 DominantNode == OriginalNode ? AdditionalNode : OriginalNode;
371 if (DominantNode == OriginalNode) {
372 if (OriginalDefinedDefaultHref) {
373 xmlNsPtr NonDominantDefinedDefault =
374 getNamespaceWithPrefix(nullptr, NonDominantNode);
375 // In this case, both the nodes defined a default namespace. However
376 // the lower priority node ended up having a higher priority default
377 // definition. This can occur if the higher priority node is prefix
378 // namespace defined. In this case we have to define an explicit
379 // prefix for the overridden definition and apply it to all children
380 // who relied on that definition.
381 if (NonDominantDefinedDefault &&
382 namespaceOverrides(NonDominantDefinedDefault->href,
383 OriginalDefinedDefaultHref)) {
384 Expected<xmlNsPtr> EC =
385 searchOrDefine(OriginalDefinedDefaultHref, DominantNode);
386 if (!EC) {
387 return EC.takeError();
388 }
389 xmlNsPtr PrefixDominantDefinedDefault = std::move(EC.get());
390 explicateNamespace(PrefixDominantDefinedDefault, DominantNode);
391 }
392 // In this case the node with a higher priority namespace did not have a
393 // default namespace definition, but the lower priority node did. In this
394 // case the new default namespace definition is copied. A side effect of
395 // this is that all children will suddenly find themselves in a different
396 // default namespace. To maintain correctness we need to ensure that all
397 // children now explicitly refer to the namespace that they had previously
398 // implicitly inherited.
399 } else if (getNamespaceWithPrefix(nullptr, NonDominantNode)) {
400 if (DominantNode->parent) {
401 xmlNsPtr ClosestDefault = getClosestDefault(DominantNode->parent);
402 Expected<xmlNsPtr> EC =
403 searchOrDefine(ClosestDefault->href, DominantNode);
404 if (!EC) {
405 return EC.takeError();
406 }
407 xmlNsPtr ExplicitDefault = std::move(EC.get());
408 explicateNamespace(ExplicitDefault, DominantNode);
409 }
410 }
411 } else {
412 // Covers case where the incoming node has a default namespace definition
413 // that overrides the original node's namespace. This always leads to
414 // the original node receiving that new default namespace.
415 if (hasDefinedDefaultNamespace(DominantNode)) {
416 NonDominantNode->ns = getNamespaceWithPrefix(nullptr, NonDominantNode);
417 } else {
418 // This covers the case where the incoming node either has a prefix
419 // namespace, or an inherited default namespace. Since the namespace
420 // may not yet be defined in the original tree we do a searchOrDefine
421 // for it, and then set the namespace equal to it.
422 Expected<xmlNsPtr> EC =
423 searchOrDefine(DominantNode->ns->href, NonDominantNode);
424 if (!EC) {
425 return EC.takeError();
426 }
427 xmlNsPtr Explicit = std::move(EC.get());
428 NonDominantNode->ns = Explicit;
429 }
430 // This covers cases where the incoming dominant node HAS a default
431 // namespace definition, but MIGHT NOT NECESSARILY be in that namespace.
432 if (xmlNsPtr DominantDefaultDefined =
433 getNamespaceWithPrefix(nullptr, DominantNode)) {
434 if (OriginalDefinedDefaultHref) {
435 if (namespaceOverrides(DominantDefaultDefined->href,
436 OriginalDefinedDefaultHref)) {
437 // In this case, the incoming node's default definition overrides
438 // the original default definition, all children who relied on that
439 // definition must be updated accordingly.
440 Expected<xmlNsPtr> EC =
441 searchOrDefine(OriginalDefinedDefaultHref, NonDominantNode);
442 if (!EC) {
443 return EC.takeError();
444 }
445 xmlNsPtr ExplicitDefault = std::move(EC.get());
446 explicateNamespace(ExplicitDefault, NonDominantNode);
447 }
448 } else {
449 // The original did not define a default definition, however the new
450 // default definition still applies to all children, so they must be
451 // updated to explicitly refer to the namespace they had previously
452 // been inheriting implicitly.
453 xmlNsPtr ClosestDefault = getClosestDefault(NonDominantNode);
454 Expected<xmlNsPtr> EC =
455 searchOrDefine(ClosestDefault->href, NonDominantNode);
456 if (!EC) {
457 return EC.takeError();
458 }
459 xmlNsPtr ExplicitDefault = std::move(EC.get());
460 explicateNamespace(ExplicitDefault, NonDominantNode);
461 }
462 }
463 }
464 if (NewDefinedDefaultHref) {
465 xmlNsPtr OriginalNsDef = getNamespaceWithPrefix(nullptr, OriginalNode);
466 xmlFree(const_cast<unsigned char *>(OriginalNsDef->href));
467 OriginalNsDef->href = NewDefinedDefaultHref;
468 }
469 xmlFree(const_cast<unsigned char *>(OriginalDefinedDefaultHref));
470 return Error::success();
471}
472
473static bool isRecognizedNamespace(const unsigned char *NsHref) {
474 for (auto &Ns : MtNsHrefsPrefixes) {
475 if (xmlStringsEqual(NsHref, TO_XML_CHAR(Ns.first.data())reinterpret_cast<const unsigned char *>(Ns.first.data()
)
)) {
476 return true;
477 }
478 }
479 return false;
480}
481
482static bool hasRecognizedNamespace(xmlNodePtr Node) {
483 return isRecognizedNamespace(Node->ns->href);
484}
485
486// Ensure a node's inherited namespace is actually defined in the tree it
487// resides in.
488static Error reconcileNamespaces(xmlNodePtr Node) {
489 if (!Node) {
490 return Error::success();
491 }
492 if (hasInheritedNs(Node)) {
493 Expected<xmlNsPtr> ExplicitOrError = searchOrDefine(Node->ns->href, Node);
494 if (!ExplicitOrError) {
495 return ExplicitOrError.takeError();
496 }
497 xmlNsPtr Explicit = std::move(ExplicitOrError.get());
498 Node->ns = Explicit;
499 }
500 for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
501 if (auto E = reconcileNamespaces(Child)) {
502 return E;
503 }
504 }
505 return Error::success();
506}
507
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) {
512 if (auto E = mergeAttributes(OriginalRoot, AdditionalRoot))
513 return E;
514 if (auto E = mergeNamespaces(OriginalRoot, AdditionalRoot))
515 return E;
516 xmlNodePtr AdditionalFirstChild = AdditionalRoot->children;
517 xmlNode StoreNext;
518 for (xmlNodePtr Child = AdditionalFirstChild; Child; Child = Child->next) {
519 xmlNodePtr OriginalChildWithName;
520 if (!isMergeableElement(Child->name) ||
521 !(OriginalChildWithName =
522 getChildWithName(OriginalRoot, Child->name)) ||
523 !hasRecognizedNamespace(Child)) {
524 StoreNext.next = Child->next;
525 xmlUnlinkNode(Child);
526 if (!xmlAddChild(OriginalRoot, Child)) {
527 return make_error<WindowsManifestError>(Twine("could not merge ") +
528 FROM_XML_CHAR(Child->name)reinterpret_cast<const char *>(Child->name));
529 }
530 if (auto E = reconcileNamespaces(Child)) {
531 return E;
532 }
533 Child = &StoreNext;
534 } else if (auto E = treeMerge(OriginalChildWithName, Child)) {
535 return E;
536 }
537 }
538 return Error::success();
539}
540
541static void stripComments(xmlNodePtr Root) {
542 xmlNode StoreNext;
543 for (xmlNodePtr Child = Root->children; Child; Child = Child->next) {
544 if (!xmlStringsEqual(Child->name, TO_XML_CHAR("comment")reinterpret_cast<const unsigned char *>("comment"))) {
545 stripComments(Child);
546 continue;
547 }
548 StoreNext.next = Child->next;
549 xmlNodePtr Remove = Child;
550 Child = &StoreNext;
551 xmlUnlinkNode(Remove);
552 xmlFreeNode(Remove);
553 }
554}
555
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) {
560 for (xmlAttrPtr Attribute = Node->properties; Attribute;
561 Attribute = Attribute->next) {
562 if (!Attribute->ns) {
563 Attribute->ns = getClosestDefault(Node);
564 }
565 }
566 for (xmlNodePtr Child = Node->children; Child; Child = Child->next) {
567 setAttributeNamespaces(Child);
568 }
569}
570
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,
574 std::vector<xmlNsPtr> &RequiredPrefixes) {
575 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
576 checkAndStripPrefixes(Child, RequiredPrefixes);
8
Calling 'checkAndStripPrefixes'
10
Calling 'checkAndStripPrefixes'
12
Calling 'checkAndStripPrefixes'
577 }
578 if (Node->ns && Node->ns->prefix != nullptr) {
13
Assuming field 'ns' is null
579 xmlNsPtr ClosestDefault = getClosestDefault(Node);
580 if (ClosestDefault &&
581 xmlStringsEqual(ClosestDefault->href, Node->ns->href)) {
582 Node->ns = ClosestDefault;
583 } else if (!llvm::is_contained(RequiredPrefixes, Node->ns)) {
584 RequiredPrefixes.push_back(Node->ns);
585 }
586 }
587 for (xmlAttrPtr Attribute = Node->properties; Attribute;
14
Loop condition is false. Execution continues on line 599
588 Attribute = Attribute->next) {
589 if (Attribute->ns && Attribute->ns->prefix != nullptr) {
590 xmlNsPtr ClosestDefault = getClosestDefault(Node);
591 if (ClosestDefault &&
592 xmlStringsEqual(ClosestDefault->href, Attribute->ns->href)) {
593 Attribute->ns = ClosestDefault;
594 } else if (!llvm::is_contained(RequiredPrefixes, Node->ns)) {
595 RequiredPrefixes.push_back(Attribute->ns);
596 }
597 }
598 }
599 xmlNsPtr Prev;
15
'Prev' declared without an initial value
600 xmlNs Temp;
601 for (xmlNsPtr Def = Node->nsDef; Def; Def = Def->next) {
602 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
603 Prev = Def;
604 continue;
605 }
606 if (Def == Node->nsDef) {
25
Assuming 'Def' is not equal to field 'nsDef'
26
Taking false branch
607 Node->nsDef = Def->next;
608 } else {
609 Prev->next = Def->next;
27
Access to field 'next' results in a dereference of an undefined pointer value (loaded from variable 'Prev')
610 }
611 Temp.next = Def->next;
612 xmlFreeNs(Def);
613 Def = &Temp;
614 }
615}
616
617WindowsManifestMerger::WindowsManifestMergerImpl::~WindowsManifestMergerImpl() {
618 for (auto &Doc : MergedDocs)
619 xmlFreeDoc(Doc);
620}
621
622Error WindowsManifestMerger::WindowsManifestMergerImpl::merge(
623 MemoryBufferRef Manifest) {
624 if (Merged)
625 return make_error<WindowsManifestError>(
626 "merge after getMergedManifest is not supported");
627 if (Manifest.getBufferSize() == 0)
628 return make_error<WindowsManifestError>(
629 "attempted to merge empty manifest");
630 xmlSetGenericErrorFunc((void *)this,
631 WindowsManifestMergerImpl::errorCallback);
632 xmlDocPtr ManifestXML = xmlReadMemory(
633 Manifest.getBufferStart(), Manifest.getBufferSize(), "manifest.xml",
634 nullptr, XML_PARSE_NOBLANKS | XML_PARSE_NODICT);
635 xmlSetGenericErrorFunc(nullptr, nullptr);
636 if (auto E = getParseError())
637 return E;
638 xmlNodePtr AdditionalRoot = xmlDocGetRootElement(ManifestXML);
639 stripComments(AdditionalRoot);
640 setAttributeNamespaces(AdditionalRoot);
641 if (CombinedDoc == nullptr) {
642 CombinedDoc = ManifestXML;
643 } else {
644 xmlNodePtr CombinedRoot = xmlDocGetRootElement(CombinedDoc);
645 if (!xmlStringsEqual(CombinedRoot->name, AdditionalRoot->name) ||
646 !isMergeableElement(AdditionalRoot->name) ||
647 !hasRecognizedNamespace(AdditionalRoot)) {
648 return make_error<WindowsManifestError>("multiple root nodes");
649 }
650 if (auto E = treeMerge(CombinedRoot, AdditionalRoot)) {
651 return E;
652 }
653 }
654 MergedDocs.push_back(ManifestXML);
655 return Error::success();
656}
657
658std::unique_ptr<MemoryBuffer>
659WindowsManifestMerger::WindowsManifestMergerImpl::getMergedManifest() {
660 if (!Merged) {
2
Assuming field 'Merged' is false
3
Taking true branch
661 Merged = true;
662
663 if (!CombinedDoc)
4
Assuming field 'CombinedDoc' is non-null
5
Taking false branch
664 return nullptr;
665
666 xmlNodePtr CombinedRoot = xmlDocGetRootElement(CombinedDoc);
667 std::vector<xmlNsPtr> RequiredPrefixes;
668 checkAndStripPrefixes(CombinedRoot, RequiredPrefixes);
6
Calling 'checkAndStripPrefixes'
669 std::unique_ptr<xmlDoc, XmlDeleter> OutputDoc(
670 xmlNewDoc((const unsigned char *)"1.0"));
671 xmlDocSetRootElement(OutputDoc.get(), CombinedRoot);
672 assert(0 == xmlDocGetRootElement(CombinedDoc))(static_cast<void> (0));
673
674 xmlKeepBlanksDefault(0);
675 xmlChar *Buff = nullptr;
676 xmlDocDumpFormatMemoryEnc(OutputDoc.get(), &Buff, &BufferSize, "UTF-8", 1);
677 Buffer.reset(Buff);
678 }
679
680 return BufferSize ? MemoryBuffer::getMemBufferCopy(StringRef(
681 FROM_XML_CHAR(Buffer.get())reinterpret_cast<const char *>(Buffer.get()), (size_t)BufferSize))
682 : nullptr;
683}
684
685bool windows_manifest::isAvailable() { return true; }
686
687#else
688
689WindowsManifestMerger::WindowsManifestMergerImpl::~WindowsManifestMergerImpl() {
690}
691
692Error WindowsManifestMerger::WindowsManifestMergerImpl::merge(
693 MemoryBufferRef Manifest) {
694 return make_error<WindowsManifestError>("no libxml2");
695}
696
697std::unique_ptr<MemoryBuffer>
698WindowsManifestMerger::WindowsManifestMergerImpl::getMergedManifest() {
699 return nullptr;
700}
701
702bool windows_manifest::isAvailable() { return false; }
703
704#endif
705
706WindowsManifestMerger::WindowsManifestMerger()
707 : Impl(std::make_unique<WindowsManifestMergerImpl>()) {}
708
709WindowsManifestMerger::~WindowsManifestMerger() {}
710
711Error WindowsManifestMerger::merge(MemoryBufferRef Manifest) {
712 return Impl->merge(Manifest);
713}
714
715std::unique_ptr<MemoryBuffer> WindowsManifestMerger::getMergedManifest() {
716 return Impl->getMergedManifest();
1
Calling 'WindowsManifestMergerImpl::getMergedManifest'
717}
718
719void WindowsManifestMerger::WindowsManifestMergerImpl::errorCallback(
720 void *Ctx, const char *Format, ...) {
721 auto *Merger = (WindowsManifestMergerImpl *)Ctx;
722 Merger->ParseErrorOccurred = true;
723}
724
725Error WindowsManifestMerger::WindowsManifestMergerImpl::getParseError() {
726 if (!ParseErrorOccurred)
727 return Error::success();
728 return make_error<WindowsManifestError>("invalid xml document");
729}

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/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_CHECKS0
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_CHECKS0
534 assert(!IsEarlyIncremented && "Cannot dereference twice!")(static_cast<void> (0));
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_CHECKS0
543 assert(IsEarlyIncremented && "Cannot increment before dereferencing!")(static_cast<void> (0));
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_CHECKS0
552 assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!")(static_cast<void> (0));
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!")__builtin_unreachable();
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!")__builtin_unreachable();
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<void> (0));
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<void> (0));
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<void> (0));
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<void> (0));
1127 return (*this)[0];
1128 }
1129 ReferenceT back() const {
1130 assert(!empty() && "expected non-empty range")(static_cast<void> (0));
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<void> (0));
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<void> (0));
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<void> (0));
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<void> (0));
1865 assert(rhs)(static_cast<void> (0));
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<void> (0));
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<void> (0));
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++ -*-
2
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.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_iterator.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{iterator}
54 *
55 * This file implements reverse_iterator, back_insert_iterator,
56 * front_insert_iterator, insert_iterator, __normal_iterator, and their
57 * supporting functions and overloaded operators.
58 */
59
60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1
62
63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>
67
68#if __cplusplus201402L >= 201103L
69# include <type_traits>
70#endif
71
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
78
79#if __cplusplus201402L > 201703L
80# include <compare>
81# include <new>
82# include <bits/iterator_concepts.h>
83#endif
84
85namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION
88
89 /**
90 * @addtogroup iterators
91 * @{
92 */
93
94#if __cplusplus201402L > 201703L && __cpp_lib_concepts
95 namespace __detail
96 {
97 // Weaken iterator_category _Cat to _Limit if it is derived from that,
98 // otherwise use _Otherwise.
99 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
100 using __clamp_iter_cat
101 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
102 }
103#endif
104
105 // 24.4.1 Reverse iterators
106 /**
107 * Bidirectional and random access iterators have corresponding reverse
108 * %iterator adaptors that iterate through the data structure in the
109 * opposite direction. They have the same signatures as the corresponding
110 * iterators. The fundamental relation between a reverse %iterator and its
111 * corresponding %iterator @c i is established by the identity:
112 * @code
113 * &*(reverse_iterator(i)) == &*(i - 1)
114 * @endcode
115 *
116 * <em>This mapping is dictated by the fact that while there is always a
117 * pointer past the end of an array, there might not be a valid pointer
118 * before the beginning of an array.</em> [24.4.1]/1,2
119 *
120 * Reverse iterators can be tricky and surprising at first. Their
121 * semantics make sense, however, and the trickiness is a side effect of
122 * the requirement that the iterators must be safe.
123 */
124 template<typename _Iterator>
125 class reverse_iterator
126 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
127 typename iterator_traits<_Iterator>::value_type,
128 typename iterator_traits<_Iterator>::difference_type,
129 typename iterator_traits<_Iterator>::pointer,
130 typename iterator_traits<_Iterator>::reference>
131 {
132 protected:
133 _Iterator current;
134
135 typedef iterator_traits<_Iterator> __traits_type;
136
137 public:
138 typedef _Iterator iterator_type;
139 typedef typename __traits_type::difference_type difference_type;
140 typedef typename __traits_type::pointer pointer;
141 typedef typename __traits_type::reference reference;
142
143#if __cplusplus201402L > 201703L && __cpp_lib_concepts
144 using iterator_concept
145 = conditional_t<random_access_iterator<_Iterator>,
146 random_access_iterator_tag,
147 bidirectional_iterator_tag>;
148 using iterator_category
149 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
150 random_access_iterator_tag>;
151#endif
152
153 /**
154 * The default constructor value-initializes member @p current.
155 * If it is a pointer, that means it is zero-initialized.
156 */
157 // _GLIBCXX_RESOLVE_LIB_DEFECTS
158 // 235 No specification of default ctor for reverse_iterator
159 // 1012. reverse_iterator default ctor should value initialize
160 _GLIBCXX17_CONSTEXPR
161 reverse_iterator() : current() { }
162
163 /**
164 * This %iterator will move in the opposite direction that @p x does.
165 */
166 explicit _GLIBCXX17_CONSTEXPR
167 reverse_iterator(iterator_type __x) : current(__x) { }
168
169 /**
170 * The copy constructor is normal.
171 */
172 _GLIBCXX17_CONSTEXPR
173 reverse_iterator(const reverse_iterator& __x)
174 : current(__x.current) { }
175
176#if __cplusplus201402L >= 201103L
177 reverse_iterator& operator=(const reverse_iterator&) = default;
178#endif
179
180 /**
181 * A %reverse_iterator across other types can be copied if the
182 * underlying %iterator can be converted to the type of @c current.
183 */
184 template<typename _Iter>
185 _GLIBCXX17_CONSTEXPR
186 reverse_iterator(const reverse_iterator<_Iter>& __x)
187 : current(__x.base()) { }
188
189 /**
190 * @return @c current, the %iterator used for underlying work.
191 */
192 _GLIBCXX17_CONSTEXPR iterator_type
193 base() const
194 { return current; }
195
196 /**
197 * @return A reference to the value at @c --current
198 *
199 * This requires that @c --current is dereferenceable.
200 *
201 * @warning This implementation requires that for an iterator of the
202 * underlying iterator type, @c x, a reference obtained by
203 * @c *x remains valid after @c x has been modified or
204 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
205 */
206 _GLIBCXX17_CONSTEXPR reference
207 operator*() const
208 {
209 _Iterator __tmp = current;
210 return *--__tmp;
211 }
212
213 /**
214 * @return A pointer to the value at @c --current
215 *
216 * This requires that @c --current is dereferenceable.
217 */
218 _GLIBCXX17_CONSTEXPR pointer
219 operator->() const
220#if __cplusplus201402L > 201703L && __cpp_concepts >= 201907L
221 requires is_pointer_v<_Iterator>
222 || requires(const _Iterator __i) { __i.operator->(); }
223#endif
224 {
225 // _GLIBCXX_RESOLVE_LIB_DEFECTS
226 // 1052. operator-> should also support smart pointers
227 _Iterator __tmp = current;
228 --__tmp;
229 return _S_to_pointer(__tmp);
230 }
231
232 /**
233 * @return @c *this
234 *
235 * Decrements the underlying iterator.
236 */
237 _GLIBCXX17_CONSTEXPR reverse_iterator&
238 operator++()
239 {
240 --current;
241 return *this;
242 }
243
244 /**
245 * @return The original value of @c *this
246 *
247 * Decrements the underlying iterator.
248 */
249 _GLIBCXX17_CONSTEXPR reverse_iterator
250 operator++(int)
251 {
252 reverse_iterator __tmp = *this;
253 --current;
254 return __tmp;
255 }
256
257 /**
258 * @return @c *this
259 *
260 * Increments the underlying iterator.
261 */
262 _GLIBCXX17_CONSTEXPR reverse_iterator&
263 operator--()
264 {
265 ++current;
266 return *this;
267 }
268
269 /**
270 * @return A reverse_iterator with the previous value of @c *this
271 *
272 * Increments the underlying iterator.
273 */
274 _GLIBCXX17_CONSTEXPR reverse_iterator
275 operator--(int)
276 {
277 reverse_iterator __tmp = *this;
278 ++current;
279 return __tmp;
280 }
281
282 /**
283 * @return A reverse_iterator that refers to @c current - @a __n
284 *
285 * The underlying iterator must be a Random Access Iterator.
286 */
287 _GLIBCXX17_CONSTEXPR reverse_iterator
288 operator+(difference_type __n) const
289 { return reverse_iterator(current - __n); }
290
291 /**
292 * @return *this
293 *
294 * Moves the underlying iterator backwards @a __n steps.
295 * The underlying iterator must be a Random Access Iterator.
296 */
297 _GLIBCXX17_CONSTEXPR reverse_iterator&
298 operator+=(difference_type __n)
299 {
300 current -= __n;
301 return *this;
302 }
303
304 /**
305 * @return A reverse_iterator that refers to @c current - @a __n
306 *
307 * The underlying iterator must be a Random Access Iterator.
308 */
309 _GLIBCXX17_CONSTEXPR reverse_iterator
310 operator-(difference_type __n) const
311 { return reverse_iterator(current + __n); }
312
313 /**
314 * @return *this
315 *
316 * Moves the underlying iterator forwards @a __n steps.
317 * The underlying iterator must be a Random Access Iterator.
318 */
319 _GLIBCXX17_CONSTEXPR reverse_iterator&
320 operator-=(difference_type __n)
321 {
322 current += __n;
323 return *this;
324 }
325
326 /**
327 * @return The value at @c current - @a __n - 1
328 *
329 * The underlying iterator must be a Random Access Iterator.
330 */
331 _GLIBCXX17_CONSTEXPR reference
332 operator[](difference_type __n) const
333 { return *(*this + __n); }
334
335#if __cplusplus201402L > 201703L && __cpp_lib_concepts
336 friend constexpr iter_rvalue_reference_t<_Iterator>
337 iter_move(const reverse_iterator& __i)
338 noexcept(is_nothrow_copy_constructible_v<_Iterator>
339 && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
340 {
341 auto __tmp = __i.base();
342 return ranges::iter_move(--__tmp);
343 }
344
345 template<indirectly_swappable<_Iterator> _Iter2>
346 friend constexpr void
347 iter_swap(const reverse_iterator& __x,
348 const reverse_iterator<_Iter2>& __y)
349 noexcept(is_nothrow_copy_constructible_v<_Iterator>
350 && is_nothrow_copy_constructible_v<_Iter2>
351 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
352 --std::declval<_Iter2&>())))
353 {
354 auto __xtmp = __x.base();
355 auto __ytmp = __y.base();
356 ranges::iter_swap(--__xtmp, --__ytmp);
357 }
358#endif
359
360 private:
361 template<typename _Tp>
362 static _GLIBCXX17_CONSTEXPR _Tp*
363 _S_to_pointer(_Tp* __p)
364 { return __p; }
365
366 template<typename _Tp>
367 static _GLIBCXX17_CONSTEXPR pointer
368 _S_to_pointer(_Tp __t)
369 { return __t.operator->(); }
370 };
371
372 //@{
373 /**
374 * @param __x A %reverse_iterator.
375 * @param __y A %reverse_iterator.
376 * @return A simple bool.
377 *
378 * Reverse iterators forward comparisons to their underlying base()
379 * iterators.
380 *
381 */
382#if __cplusplus201402L <= 201703L || ! defined __cpp_lib_concepts
383 template<typename _Iterator>
384 inline _GLIBCXX17_CONSTEXPR bool
385 operator==(const reverse_iterator<_Iterator>& __x,
386 const reverse_iterator<_Iterator>& __y)
387 { return __x.base() == __y.base(); }
388
389 template<typename _Iterator>
390 inline _GLIBCXX17_CONSTEXPR bool
391 operator<(const reverse_iterator<_Iterator>& __x,
392 const reverse_iterator<_Iterator>& __y)
393 { return __y.base() < __x.base(); }
394
395 template<typename _Iterator>
396 inline _GLIBCXX17_CONSTEXPR bool
397 operator!=(const reverse_iterator<_Iterator>& __x,
398 const reverse_iterator<_Iterator>& __y)
399 { return !(__x == __y); }
400
401 template<typename _Iterator>
402 inline _GLIBCXX17_CONSTEXPR bool
403 operator>(const reverse_iterator<_Iterator>& __x,
404 const reverse_iterator<_Iterator>& __y)
405 { return __y < __x; }
406
407 template<typename _Iterator>
408 inline _GLIBCXX17_CONSTEXPR bool
409 operator<=(const reverse_iterator<_Iterator>& __x,
410 const reverse_iterator<_Iterator>& __y)
411 { return !(__y < __x); }
412
413 template<typename _Iterator>
414 inline _GLIBCXX17_CONSTEXPR bool
415 operator>=(const reverse_iterator<_Iterator>& __x,
416 const reverse_iterator<_Iterator>& __y)
417 { return !(__x < __y); }
418
419 // _GLIBCXX_RESOLVE_LIB_DEFECTS
420 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
421 template<typename _IteratorL, typename _IteratorR>
422 inline _GLIBCXX17_CONSTEXPR bool
423 operator==(const reverse_iterator<_IteratorL>& __x,
424 const reverse_iterator<_IteratorR>& __y)
425 { return __x.base() == __y.base(); }
426
427 template<typename _IteratorL, typename _IteratorR>
428 inline _GLIBCXX17_CONSTEXPR bool
429 operator<(const reverse_iterator<_IteratorL>& __x,
430 const reverse_iterator<_IteratorR>& __y)
431 { return __y.base() < __x.base(); }
432
433 template<typename _IteratorL, typename _IteratorR>
434 inline _GLIBCXX17_CONSTEXPR bool
435 operator!=(const reverse_iterator<_IteratorL>& __x,
436 const reverse_iterator<_IteratorR>& __y)
437 { return !(__x == __y); }
438
439 template<typename _IteratorL, typename _IteratorR>
440 inline _GLIBCXX17_CONSTEXPR bool
441 operator>(const reverse_iterator<_IteratorL>& __x,
442 const reverse_iterator<_IteratorR>& __y)
443 { return __y < __x; }
444
445 template<typename _IteratorL, typename _IteratorR>
446 inline _GLIBCXX17_CONSTEXPR bool
447 operator<=(const reverse_iterator<_IteratorL>& __x,
448 const reverse_iterator<_IteratorR>& __y)
449 { return !(__y < __x); }
450
451 template<typename _IteratorL, typename _IteratorR>
452 inline _GLIBCXX17_CONSTEXPR bool
453 operator>=(const reverse_iterator<_IteratorL>& __x,
454 const reverse_iterator<_IteratorR>& __y)
455 { return !(__x < __y); }
456#else // C++20
457 template<typename _IteratorL, typename _IteratorR>
458 constexpr bool
459 operator==(const reverse_iterator<_IteratorL>& __x,
460 const reverse_iterator<_IteratorR>& __y)
461 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
462 { return __x.base() == __y.base(); }
463
464 template<typename _IteratorL, typename _IteratorR>
465 constexpr bool
466 operator!=(const reverse_iterator<_IteratorL>& __x,
467 const reverse_iterator<_IteratorR>& __y)
468 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
469 { return __x.base() != __y.base(); }
470
471 template<typename _IteratorL, typename _IteratorR>
472 constexpr bool
473 operator<(const reverse_iterator<_IteratorL>& __x,
474 const reverse_iterator<_IteratorR>& __y)
475 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
476 { return __x.base() > __y.base(); }
477
478 template<typename _IteratorL, typename _IteratorR>
479 constexpr bool
480 operator>(const reverse_iterator<_IteratorL>& __x,
481 const reverse_iterator<_IteratorR>& __y)
482 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
483 { return __x.base() < __y.base(); }
484
485 template<typename _IteratorL, typename _IteratorR>
486 constexpr bool
487 operator<=(const reverse_iterator<_IteratorL>& __x,
488 const reverse_iterator<_IteratorR>& __y)
489 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
490 { return __x.base() >= __y.base(); }
491
492 template<typename _IteratorL, typename _IteratorR>
493 constexpr bool
494 operator>=(const reverse_iterator<_IteratorL>& __x,
495 const reverse_iterator<_IteratorR>& __y)
496 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
497 { return __x.base() <= __y.base(); }
498
499 template<typename _IteratorL,
500 three_way_comparable_with<_IteratorL> _IteratorR>
501 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
502 operator<=>(const reverse_iterator<_IteratorL>& __x,
503 const reverse_iterator<_IteratorR>& __y)
504 { return __y.base() <=> __x.base(); }
505#endif // C++20
506 //@}
507
508#if __cplusplus201402L < 201103L
509 template<typename _Iterator>
510 inline typename reverse_iterator<_Iterator>::difference_type
511 operator-(const reverse_iterator<_Iterator>& __x,
512 const reverse_iterator<_Iterator>& __y)
513 { return __y.base() - __x.base(); }
514
515 template<typename _IteratorL, typename _IteratorR>
516 inline typename reverse_iterator<_IteratorL>::difference_type
517 operator-(const reverse_iterator<_IteratorL>& __x,
518 const reverse_iterator<_IteratorR>& __y)
519 { return __y.base() - __x.base(); }
520#else
521 // _GLIBCXX_RESOLVE_LIB_DEFECTS
522 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
523 template<typename _IteratorL, typename _IteratorR>
524 inline _GLIBCXX17_CONSTEXPR auto
525 operator-(const reverse_iterator<_IteratorL>& __x,
526 const reverse_iterator<_IteratorR>& __y)
527 -> decltype(__y.base() - __x.base())
528 { return __y.base() - __x.base(); }
529#endif
530
531 template<typename _Iterator>
532 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
533 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
534 const reverse_iterator<_Iterator>& __x)
535 { return reverse_iterator<_Iterator>(__x.base() - __n); }
536
537#if __cplusplus201402L >= 201103L
538 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
539 template<typename _Iterator>
540 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
541 __make_reverse_iterator(_Iterator __i)
542 { return reverse_iterator<_Iterator>(__i); }
543
544# if __cplusplus201402L >= 201402L
545# define __cpp_lib_make_reverse_iterator201402 201402
546
547 // _GLIBCXX_RESOLVE_LIB_DEFECTS
548 // DR 2285. make_reverse_iterator
549 /// Generator function for reverse_iterator.
550 template<typename _Iterator>
551 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
552 make_reverse_iterator(_Iterator __i)
553 { return reverse_iterator<_Iterator>(__i); }
554
555# if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
556 template<typename _Iterator1, typename _Iterator2>
557 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
558 inline constexpr bool
559 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
560 reverse_iterator<_Iterator2>> = true;
561# endif // C++20
562# endif // C++14
563
564 template<typename _Iterator>
565 _GLIBCXX20_CONSTEXPR
566 auto
567 __niter_base(reverse_iterator<_Iterator> __it)
568 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
569 { return __make_reverse_iterator(__niter_base(__it.base())); }
570
571 template<typename _Iterator>
572 struct __is_move_iterator<reverse_iterator<_Iterator> >
573 : __is_move_iterator<_Iterator>
574 { };
575
576 template<typename _Iterator>
577 _GLIBCXX20_CONSTEXPR
578 auto
579 __miter_base(reverse_iterator<_Iterator> __it)
580 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
581 { return __make_reverse_iterator(__miter_base(__it.base())); }
582#endif // C++11
583
584 // 24.4.2.2.1 back_insert_iterator
585 /**
586 * @brief Turns assignment into insertion.
587 *
588 * These are output iterators, constructed from a container-of-T.
589 * Assigning a T to the iterator appends it to the container using
590 * push_back.
591 *
592 * Tip: Using the back_inserter function to create these iterators can
593 * save typing.
594 */
595 template<typename _Container>
596 class back_insert_iterator
597 : public iterator<output_iterator_tag, void, void, void, void>
598 {
599 protected:
600 _Container* container;
601
602 public:
603 /// A nested typedef for the type of whatever container you used.
604 typedef _Container container_type;
605#if __cplusplus201402L > 201703L
606 using difference_type = ptrdiff_t;
607
608 constexpr back_insert_iterator() noexcept : container(nullptr) { }
609#endif
610
611 /// The only way to create this %iterator is with a container.
612 explicit _GLIBCXX20_CONSTEXPR
613 back_insert_iterator(_Container& __x)
614 : container(std::__addressof(__x)) { }
615
616 /**
617 * @param __value An instance of whatever type
618 * container_type::const_reference is; presumably a
619 * reference-to-const T for container<T>.
620 * @return This %iterator, for chained operations.
621 *
622 * This kind of %iterator doesn't really have a @a position in the
623 * container (you can think of the position as being permanently at
624 * the end, if you like). Assigning a value to the %iterator will
625 * always append the value to the end of the container.
626 */
627#if __cplusplus201402L < 201103L
628 back_insert_iterator&
629 operator=(typename _Container::const_reference __value)
630 {
631 container->push_back(__value);
632 return *this;
633 }
634#else
635 _GLIBCXX20_CONSTEXPR
636 back_insert_iterator&
637 operator=(const typename _Container::value_type& __value)
638 {
639 container->push_back(__value);
640 return *this;
641 }
642
643 _GLIBCXX20_CONSTEXPR
644 back_insert_iterator&
645 operator=(typename _Container::value_type&& __value)
646 {
647 container->push_back(std::move(__value));
648 return *this;
649 }
650#endif
651
652 /// Simply returns *this.
653 _GLIBCXX20_CONSTEXPR
654 back_insert_iterator&
655 operator*()
656 { return *this; }
657
658 /// Simply returns *this. (This %iterator does not @a move.)
659 _GLIBCXX20_CONSTEXPR
660 back_insert_iterator&
661 operator++()
662 { return *this; }
663
664 /// Simply returns *this. (This %iterator does not @a move.)
665 _GLIBCXX20_CONSTEXPR
666 back_insert_iterator
667 operator++(int)
668 { return *this; }
669 };
670
671 /**
672 * @param __x A container of arbitrary type.
673 * @return An instance of back_insert_iterator working on @p __x.
674 *
675 * This wrapper function helps in creating back_insert_iterator instances.
676 * Typing the name of the %iterator requires knowing the precise full
677 * type of the container, which can be tedious and impedes generic
678 * programming. Using this function lets you take advantage of automatic
679 * template parameter deduction, making the compiler match the correct
680 * types for you.
681 */
682 template<typename _Container>
683 _GLIBCXX20_CONSTEXPR
684 inline back_insert_iterator<_Container>
685 back_inserter(_Container& __x)
686 { return back_insert_iterator<_Container>(__x); }
687
688 /**
689 * @brief Turns assignment into insertion.
690 *
691 * These are output iterators, constructed from a container-of-T.
692 * Assigning a T to the iterator prepends it to the container using
693 * push_front.
694 *
695 * Tip: Using the front_inserter function to create these iterators can
696 * save typing.
697 */
698 template<typename _Container>
699 class front_insert_iterator
700 : public iterator<output_iterator_tag, void, void, void, void>
701 {
702 protected:
703 _Container* container;
704
705 public:
706 /// A nested typedef for the type of whatever container you used.
707 typedef _Container container_type;
708#if __cplusplus201402L > 201703L
709 using difference_type = ptrdiff_t;
710
711 constexpr front_insert_iterator() noexcept : container(nullptr) { }
712#endif
713
714 /// The only way to create this %iterator is with a container.
715 explicit _GLIBCXX20_CONSTEXPR
716 front_insert_iterator(_Container& __x)
717 : container(std::__addressof(__x)) { }
718
719 /**
720 * @param __value An instance of whatever type
721 * container_type::const_reference is; presumably a
722 * reference-to-const T for container<T>.
723 * @return This %iterator, for chained operations.
724 *
725 * This kind of %iterator doesn't really have a @a position in the
726 * container (you can think of the position as being permanently at
727 * the front, if you like). Assigning a value to the %iterator will
728 * always prepend the value to the front of the container.
729 */
730#if __cplusplus201402L < 201103L
731 front_insert_iterator&
732 operator=(typename _Container::const_reference __value)
733 {
734 container->push_front(__value);
735 return *this;
736 }
737#else
738 _GLIBCXX20_CONSTEXPR
739 front_insert_iterator&
740 operator=(const typename _Container::value_type& __value)
741 {
742 container->push_front(__value);
743 return *this;
744 }
745
746 _GLIBCXX20_CONSTEXPR
747 front_insert_iterator&
748 operator=(typename _Container::value_type&& __value)
749 {
750 container->push_front(std::move(__value));
751 return *this;
752 }
753#endif
754
755 /// Simply returns *this.
756 _GLIBCXX20_CONSTEXPR
757 front_insert_iterator&
758 operator*()
759 { return *this; }
760
761 /// Simply returns *this. (This %iterator does not @a move.)
762 _GLIBCXX20_CONSTEXPR
763 front_insert_iterator&
764 operator++()
765 { return *this; }
766
767 /// Simply returns *this. (This %iterator does not @a move.)
768 _GLIBCXX20_CONSTEXPR
769 front_insert_iterator
770 operator++(int)
771 { return *this; }
772 };
773
774 /**
775 * @param __x A container of arbitrary type.
776 * @return An instance of front_insert_iterator working on @p x.
777 *
778 * This wrapper function helps in creating front_insert_iterator instances.
779 * Typing the name of the %iterator requires knowing the precise full
780 * type of the container, which can be tedious and impedes generic
781 * programming. Using this function lets you take advantage of automatic
782 * template parameter deduction, making the compiler match the correct
783 * types for you.
784 */
785 template<typename _Container>
786 _GLIBCXX20_CONSTEXPR
787 inline front_insert_iterator<_Container>
788 front_inserter(_Container& __x)
789 { return front_insert_iterator<_Container>(__x); }
790
791 /**
792 * @brief Turns assignment into insertion.
793 *
794 * These are output iterators, constructed from a container-of-T.
795 * Assigning a T to the iterator inserts it in the container at the
796 * %iterator's position, rather than overwriting the value at that
797 * position.
798 *
799 * (Sequences will actually insert a @e copy of the value before the
800 * %iterator's position.)
801 *
802 * Tip: Using the inserter function to create these iterators can
803 * save typing.
804 */
805 template<typename _Container>
806 class insert_iterator
807 : public iterator<output_iterator_tag, void, void, void, void>
808 {
809#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
810 using _Iter = std::__detail::__range_iter_t<_Container>;
811
812 protected:
813 _Container* container = nullptr;
814 _Iter iter = _Iter();
815#else
816 typedef typename _Container::iterator _Iter;
817
818 protected:
819 _Container* container;
820 _Iter iter;
821#endif
822
823 public:
824 /// A nested typedef for the type of whatever container you used.
825 typedef _Container container_type;
826
827#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
828 using difference_type = ptrdiff_t;
829
830 insert_iterator() = default;
831#endif
832
833 /**
834 * The only way to create this %iterator is with a container and an
835 * initial position (a normal %iterator into the container).
836 */
837 _GLIBCXX20_CONSTEXPR
838 insert_iterator(_Container& __x, _Iter __i)
839 : container(std::__addressof(__x)), iter(__i) {}
840
841 /**
842 * @param __value An instance of whatever type
843 * container_type::const_reference is; presumably a
844 * reference-to-const T for container<T>.
845 * @return This %iterator, for chained operations.
846 *
847 * This kind of %iterator maintains its own position in the
848 * container. Assigning a value to the %iterator will insert the
849 * value into the container at the place before the %iterator.
850 *
851 * The position is maintained such that subsequent assignments will
852 * insert values immediately after one another. For example,
853 * @code
854 * // vector v contains A and Z
855 *
856 * insert_iterator i (v, ++v.begin());
857 * i = 1;
858 * i = 2;
859 * i = 3;
860 *
861 * // vector v contains A, 1, 2, 3, and Z
862 * @endcode
863 */
864#if __cplusplus201402L < 201103L
865 insert_iterator&
866 operator=(typename _Container::const_reference __value)
867 {
868 iter = container->insert(iter, __value);
869 ++iter;
870 return *this;
871 }
872#else
873 _GLIBCXX20_CONSTEXPR
874 insert_iterator&
875 operator=(const typename _Container::value_type& __value)
876 {
877 iter = container->insert(iter, __value);
878 ++iter;
879 return *this;
880 }
881
882 _GLIBCXX20_CONSTEXPR
883 insert_iterator&
884 operator=(typename _Container::value_type&& __value)
885 {
886 iter = container->insert(iter, std::move(__value));
887 ++iter;
888 return *this;
889 }
890#endif
891
892 /// Simply returns *this.
893 _GLIBCXX20_CONSTEXPR
894 insert_iterator&
895 operator*()
896 { return *this; }
897
898 /// Simply returns *this. (This %iterator does not @a move.)
899 _GLIBCXX20_CONSTEXPR
900 insert_iterator&
901 operator++()
902 { return *this; }
903
904 /// Simply returns *this. (This %iterator does not @a move.)
905 _GLIBCXX20_CONSTEXPR
906 insert_iterator&
907 operator++(int)
908 { return *this; }
909 };
910
911 /**
912 * @param __x A container of arbitrary type.
913 * @param __i An iterator into the container.
914 * @return An instance of insert_iterator working on @p __x.
915 *
916 * This wrapper function helps in creating insert_iterator instances.
917 * Typing the name of the %iterator requires knowing the precise full
918 * type of the container, which can be tedious and impedes generic
919 * programming. Using this function lets you take advantage of automatic
920 * template parameter deduction, making the compiler match the correct
921 * types for you.
922 */
923#if __cplusplus201402L > 201703L && defined __cpp_lib_concepts
924 template<typename _Container>
925 constexpr insert_iterator<_Container>
926 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
927 { return insert_iterator<_Container>(__x, __i); }
928#else
929 template<typename _Container, typename _Iterator>
930 inline insert_iterator<_Container>
931 inserter(_Container& __x, _Iterator __i)
932 {
933 return insert_iterator<_Container>(__x,
934 typename _Container::iterator(__i));
935 }
936#endif
937
938 // @} group iterators
939
940_GLIBCXX_END_NAMESPACE_VERSION
941} // namespace
942
943namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
944{
945_GLIBCXX_BEGIN_NAMESPACE_VERSION
946
947 // This iterator adapter is @a normal in the sense that it does not
948 // change the semantics of any of the operators of its iterator
949 // parameter. Its primary purpose is to convert an iterator that is
950 // not a class, e.g. a pointer, into an iterator that is a class.
951 // The _Container parameter exists solely so that different containers
952 // using this template can instantiate different types, even if the
953 // _Iterator parameter is the same.
954 template<typename _Iterator, typename _Container>
955 class __normal_iterator
956 {
957 protected:
958 _Iterator _M_current;
959
960 typedef std::iterator_traits<_Iterator> __traits_type;
961
962 public:
963 typedef _Iterator iterator_type;
964 typedef typename __traits_type::iterator_category iterator_category;
965 typedef typename __traits_type::value_type value_type;
966 typedef typename __traits_type::difference_type difference_type;
967 typedef typename __traits_type::reference reference;
968 typedef typename __traits_type::pointer pointer;
969
970#if __cplusplus201402L > 201703L && __cpp_lib_concepts
971 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
972#endif
973
974 _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
975 : _M_current(_Iterator()) { }
976
977 explicit _GLIBCXX20_CONSTEXPR
978 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
979 : _M_current(__i) { }
980
981 // Allow iterator to const_iterator conversion
982 template<typename _Iter>
983 _GLIBCXX20_CONSTEXPR
984 __normal_iterator(const __normal_iterator<_Iter,
985 typename __enable_if<
986 (std::__are_same<_Iter, typename _Container::pointer>::__value),
987 _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
988 : _M_current(__i.base()) { }
989
990 // Forward iterator requirements
991 _GLIBCXX20_CONSTEXPR
992 reference
993 operator*() const _GLIBCXX_NOEXCEPTnoexcept
994 { return *_M_current; }
995
996 _GLIBCXX20_CONSTEXPR
997 pointer
998 operator->() const _GLIBCXX_NOEXCEPTnoexcept
999 { return _M_current; }
1000
1001 _GLIBCXX20_CONSTEXPR
1002 __normal_iterator&
1003 operator++() _GLIBCXX_NOEXCEPTnoexcept
1004 {
1005 ++_M_current;
1006 return *this;
1007 }
1008
1009 _GLIBCXX20_CONSTEXPR
1010 __normal_iterator
1011 operator++(int) _GLIBCXX_NOEXCEPTnoexcept
1012 { return __normal_iterator(_M_current++); }
1013
1014 // Bidirectional iterator requirements
1015 _GLIBCXX20_CONSTEXPR
1016 __normal_iterator&
1017 operator--() _GLIBCXX_NOEXCEPTnoexcept
1018 {
1019 --_M_current;
1020 return *this;
1021 }
1022
1023 _GLIBCXX20_CONSTEXPR
1024 __normal_iterator
1025 operator--(int) _GLIBCXX_NOEXCEPTnoexcept
1026 { return __normal_iterator(_M_current--); }
1027
1028 // Random access iterator requirements
1029 _GLIBCXX20_CONSTEXPR
1030 reference
1031 operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1032 { return _M_current[__n]; }
1033
1034 _GLIBCXX20_CONSTEXPR
1035 __normal_iterator&
1036 operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
1037 { _M_current += __n; return *this; }
1038
1039 _GLIBCXX20_CONSTEXPR
1040 __normal_iterator
1041 operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1042 { return __normal_iterator(_M_current + __n); }
1043
1044 _GLIBCXX20_CONSTEXPR
1045 __normal_iterator&
1046 operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
1047 { _M_current -= __n; return *this; }
1048
1049 _GLIBCXX20_CONSTEXPR
1050 __normal_iterator
1051 operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
1052 { return __normal_iterator(_M_current - __n); }
1053
1054 _GLIBCXX20_CONSTEXPR
1055 const _Iterator&
1056 base() const _GLIBCXX_NOEXCEPTnoexcept
1057 { return _M_current; }
1058 };
1059
1060 // Note: In what follows, the left- and right-hand-side iterators are
1061 // allowed to vary in types (conceptually in cv-qualification) so that
1062 // comparison between cv-qualified and non-cv-qualified iterators be
1063 // valid. However, the greedy and unfriendly operators in std::rel_ops
1064 // will make overload resolution ambiguous (when in scope) if we don't
1065 // provide overloads whose operands are of the same type. Can someone
1066 // remind me what generic programming is about? -- Gaby
1067
1068#if __cpp_lib_three_way_comparison
1069 template<typename _IteratorL, typename _IteratorR, typename _Container>
1070 requires requires (_IteratorL __lhs, _IteratorR __rhs)
1071 { { __lhs == __rhs } -> std::convertible_to<bool>; }
1072 constexpr bool
1073 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1074 const __normal_iterator<_IteratorR, _Container>& __rhs)
1075 noexcept(noexcept(__lhs.base() == __rhs.base()))
1076 { return __lhs.base() == __rhs.base(); }
1077
1078 template<typename _IteratorL, typename _IteratorR, typename _Container>
1079 constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1080 operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1081 const __normal_iterator<_IteratorR, _Container>& __rhs)
1082 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1083 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1084#else
1085 // Forward iterator requirements
1086 template<typename _IteratorL, typename _IteratorR, typename _Container>
1087 _GLIBCXX20_CONSTEXPR
1088 inline bool
1089 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1090 const __normal_iterator<_IteratorR, _Container>& __rhs)
1091 _GLIBCXX_NOEXCEPTnoexcept
1092 { return __lhs.base() == __rhs.base(); }
1093
1094 template<typename _Iterator, typename _Container>
1095 _GLIBCXX20_CONSTEXPR
1096 inline bool
1097 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1098 const __normal_iterator<_Iterator, _Container>& __rhs)
1099 _GLIBCXX_NOEXCEPTnoexcept
1100 { return __lhs.base() == __rhs.base(); }
1101
1102 template<typename _IteratorL, typename _IteratorR, typename _Container>
1103 _GLIBCXX20_CONSTEXPR
1104 inline bool
1105 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1106 const __normal_iterator<_IteratorR, _Container>& __rhs)
1107 _GLIBCXX_NOEXCEPTnoexcept
1108 { return __lhs.base() != __rhs.base(); }
1109
1110 template<typename _Iterator, typename _Container>
1111 _GLIBCXX20_CONSTEXPR
1112 inline bool
1113 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1114 const __normal_iterator<_Iterator, _Container>& __rhs)
1115 _GLIBCXX_NOEXCEPTnoexcept
1116 { return __lhs.base() != __rhs.base(); }
19
Assuming the condition is false
20
Returning zero, which participates in a condition later
1117
1118 // Random access iterator requirements
1119 template<typename _IteratorL, typename _IteratorR, typename _Container>
1120 inline bool
1121 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1122 const __normal_iterator<_IteratorR, _Container>& __rhs)
1123 _GLIBCXX_NOEXCEPTnoexcept
1124 { return __lhs.base() < __rhs.base(); }
1125
1126 template<typename _Iterator, typename _Container>
1127 _GLIBCXX20_CONSTEXPR
1128 inline bool
1129 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1130 const __normal_iterator<_Iterator, _Container>& __rhs)
1131 _GLIBCXX_NOEXCEPTnoexcept
1132 { return __lhs.base() < __rhs.base(); }
1133
1134 template<typename _IteratorL, typename _IteratorR, typename _Container>
1135 inline bool
1136 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1137 const __normal_iterator<_IteratorR, _Container>& __rhs)
1138 _GLIBCXX_NOEXCEPTnoexcept
1139 { return __lhs.base() > __rhs.base(); }
1140
1141 template<typename _Iterator, typename _Container>
1142 _GLIBCXX20_CONSTEXPR
1143 inline bool
1144 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1145 const __normal_iterator<_Iterator, _Container>& __rhs)
1146 _GLIBCXX_NOEXCEPTnoexcept
1147 { return __lhs.base() > __rhs.base(); }
1148
1149 template<typename _IteratorL, typename _IteratorR, typename _Container>
1150 inline bool
1151 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1152 const __normal_iterator<_IteratorR, _Container>& __rhs)
1153 _GLIBCXX_NOEXCEPTnoexcept
1154 { return __lhs.base() <= __rhs.base(); }
1155
1156 template<typename _Iterator, typename _Container>
1157 _GLIBCXX20_CONSTEXPR
1158 inline bool
1159 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1160 const __normal_iterator<_Iterator, _Container>& __rhs)
1161 _GLIBCXX_NOEXCEPTnoexcept
1162 { return __lhs.base() <= __rhs.base(); }
1163
1164 template<typename _IteratorL, typename _IteratorR, typename _Container>
1165 inline bool
1166 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1167 const __normal_iterator<_IteratorR, _Container>& __rhs)
1168 _GLIBCXX_NOEXCEPTnoexcept
1169 { return __lhs.base() >= __rhs.base(); }
1170
1171 template<typename _Iterator, typename _Container>
1172 _GLIBCXX20_CONSTEXPR
1173 inline bool
1174 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1175 const __normal_iterator<_Iterator, _Container>& __rhs)
1176 _GLIBCXX_NOEXCEPTnoexcept
1177 { return __lhs.base() >= __rhs.base(); }
1178#endif // three-way comparison
1179
1180 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1181 // According to the resolution of DR179 not only the various comparison
1182 // operators but also operator- must accept mixed iterator/const_iterator
1183 // parameters.
1184 template<typename _IteratorL, typename _IteratorR, typename _Container>
1185#if __cplusplus201402L >= 201103L
1186 // DR 685.
1187 _GLIBCXX20_CONSTEXPR
1188 inline auto
1189 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1190 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1191 -> decltype(__lhs.base() - __rhs.base())
1192#else
1193 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1194 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1195 const __normal_iterator<_IteratorR, _Container>& __rhs)
1196#endif
1197 { return __lhs.base() - __rhs.base(); }
1198
1199 template<typename _Iterator, typename _Container>
1200 _GLIBCXX20_CONSTEXPR
1201 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1202 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1203 const __normal_iterator<_Iterator, _Container>& __rhs)
1204 _GLIBCXX_NOEXCEPTnoexcept
1205 { return __lhs.base() - __rhs.base(); }
1206
1207 template<typename _Iterator, typename _Container>
1208 _GLIBCXX20_CONSTEXPR
1209 inline __normal_iterator<_Iterator, _Container>
1210 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1211 __n, const __normal_iterator<_Iterator, _Container>& __i)
1212 _GLIBCXX_NOEXCEPTnoexcept
1213 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1214
1215_GLIBCXX_END_NAMESPACE_VERSION
1216} // namespace
1217
1218namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
1219{
1220_GLIBCXX_BEGIN_NAMESPACE_VERSION
1221
1222 template<typename _Iterator, typename _Container>
1223 _GLIBCXX20_CONSTEXPR
1224 _Iterator
1225 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1226 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)noexcept(std::is_nothrow_copy_constructible<_Iterator>::
value)
1227 { return __it.base(); }
1228
1229#if __cplusplus201402L >= 201103L
1230 /**
1231 * @addtogroup iterators
1232 * @{
1233 */
1234
1235#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1236 template<semiregular _Sent>
1237 class move_sentinel
1238 {
1239 public:
1240 constexpr
1241 move_sentinel()
1242 noexcept(is_nothrow_default_constructible_v<_Sent>)
1243 : _M_last() { }
1244
1245 constexpr explicit
1246 move_sentinel(_Sent __s)
1247 noexcept(is_nothrow_move_constructible_v<_Sent>)
1248 : _M_last(std::move(__s)) { }
1249
1250 template<typename _S2> requires convertible_to<const _S2&, _Sent>
1251 constexpr
1252 move_sentinel(const move_sentinel<_S2>& __s)
1253 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1254 : _M_last(__s.base())
1255 { }
1256
1257 template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1258 constexpr move_sentinel&
1259 operator=(const move_sentinel<_S2>& __s)
1260 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1261 {
1262 _M_last = __s.base();
1263 return *this;
1264 }
1265
1266 constexpr _Sent
1267 base() const
1268 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1269 { return _M_last; }
1270
1271 private:
1272 _Sent _M_last;
1273 };
1274#endif // C++20
1275
1276 // 24.4.3 Move iterators
1277 /**
1278 * Class template move_iterator is an iterator adapter with the same
1279 * behavior as the underlying iterator except that its dereference
1280 * operator implicitly converts the value returned by the underlying
1281 * iterator's dereference operator to an rvalue reference. Some
1282 * generic algorithms can be called with move iterators to replace
1283 * copying with moving.
1284 */
1285 template<typename _Iterator>
1286 class move_iterator
1287 {
1288 _Iterator _M_current;
1289
1290 using __traits_type = iterator_traits<_Iterator>;
1291#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1292 using __base_cat = typename __traits_type::iterator_category;
1293#else
1294 using __base_ref = typename __traits_type::reference;
1295#endif
1296
1297 public:
1298 using iterator_type = _Iterator;
1299
1300#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1301 using iterator_concept = input_iterator_tag;
1302 using iterator_category
1303 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1304 using value_type = iter_value_t<_Iterator>;
1305 using difference_type = iter_difference_t<_Iterator>;
1306 using pointer = _Iterator;
1307 using reference = iter_rvalue_reference_t<_Iterator>;
1308#else
1309 typedef typename __traits_type::iterator_category iterator_category;
1310 typedef typename __traits_type::value_type value_type;
1311 typedef typename __traits_type::difference_type difference_type;
1312 // NB: DR 680.
1313 typedef _Iterator pointer;
1314 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1315 // 2106. move_iterator wrapping iterators returning prvalues
1316 typedef typename conditional<is_reference<__base_ref>::value,
1317 typename remove_reference<__base_ref>::type&&,
1318 __base_ref>::type reference;
1319#endif
1320
1321 _GLIBCXX17_CONSTEXPR
1322 move_iterator()
1323 : _M_current() { }
1324
1325 explicit _GLIBCXX17_CONSTEXPR
1326 move_iterator(iterator_type __i)
1327 : _M_current(std::move(__i)) { }
1328
1329 template<typename _Iter>
1330 _GLIBCXX17_CONSTEXPR
1331 move_iterator(const move_iterator<_Iter>& __i)
1332 : _M_current(__i.base()) { }
1333
1334#if __cplusplus201402L <= 201703L
1335 _GLIBCXX17_CONSTEXPR iterator_type
1336 base() const
1337 { return _M_current; }
1338#else
1339 constexpr iterator_type
1340 base() const &
1341#if __cpp_lib_concepts
1342 requires copy_constructible<iterator_type>
1343#endif
1344 { return _M_current; }
1345
1346 constexpr iterator_type
1347 base() &&
1348 { return std::move(_M_current); }
1349#endif
1350
1351 _GLIBCXX17_CONSTEXPR reference
1352 operator*() const
1353#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1354 { return ranges::iter_move(_M_current); }
1355#else
1356 { return static_cast<reference>(*_M_current); }
1357#endif
1358
1359 _GLIBCXX17_CONSTEXPR pointer
1360 operator->() const
1361 { return _M_current; }
1362
1363 _GLIBCXX17_CONSTEXPR move_iterator&
1364 operator++()
1365 {
1366 ++_M_current;
1367 return *this;
1368 }
1369
1370 _GLIBCXX17_CONSTEXPR move_iterator
1371 operator++(int)
1372 {
1373 move_iterator __tmp = *this;
1374 ++_M_current;
1375 return __tmp;
1376 }
1377
1378#if __cpp_lib_concepts
1379 constexpr void
1380 operator++(int) requires (!forward_iterator<_Iterator>)
1381 { ++_M_current; }
1382#endif
1383
1384 _GLIBCXX17_CONSTEXPR move_iterator&
1385 operator--()
1386 {
1387 --_M_current;
1388 return *this;
1389 }
1390
1391 _GLIBCXX17_CONSTEXPR move_iterator
1392 operator--(int)
1393 {
1394 move_iterator __tmp = *this;
1395 --_M_current;
1396 return __tmp;
1397 }
1398
1399 _GLIBCXX17_CONSTEXPR move_iterator
1400 operator+(difference_type __n) const
1401 { return move_iterator(_M_current + __n); }
1402
1403 _GLIBCXX17_CONSTEXPR move_iterator&
1404 operator+=(difference_type __n)
1405 {
1406 _M_current += __n;
1407 return *this;
1408 }
1409
1410 _GLIBCXX17_CONSTEXPR move_iterator
1411 operator-(difference_type __n) const
1412 { return move_iterator(_M_current - __n); }
1413
1414 _GLIBCXX17_CONSTEXPR move_iterator&
1415 operator-=(difference_type __n)
1416 {
1417 _M_current -= __n;
1418 return *this;
1419 }
1420
1421 _GLIBCXX17_CONSTEXPR reference
1422 operator[](difference_type __n) const
1423#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1424 { return ranges::iter_move(_M_current + __n); }
1425#else
1426 { return std::move(_M_current[__n]); }
1427#endif
1428
1429#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1430 template<sentinel_for<_Iterator> _Sent>
1431 friend constexpr bool
1432 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1433 { return __x.base() == __y.base(); }
1434
1435 template<sized_sentinel_for<_Iterator> _Sent>
1436 friend constexpr iter_difference_t<_Iterator>
1437 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1438 { return __x.base() - __y.base(); }
1439
1440 template<sized_sentinel_for<_Iterator> _Sent>
1441 friend constexpr iter_difference_t<_Iterator>
1442 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1443 { return __x.base() - __y.base(); }
1444
1445 friend constexpr iter_rvalue_reference_t<_Iterator>
1446 iter_move(const move_iterator& __i)
1447 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1448 { return ranges::iter_move(__i._M_current); }
1449
1450 template<indirectly_swappable<_Iterator> _Iter2>
1451 friend constexpr void
1452 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1453 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1454 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1455#endif // C++20
1456 };
1457
1458 template<typename _IteratorL, typename _IteratorR>
1459 inline _GLIBCXX17_CONSTEXPR bool
1460 operator==(const move_iterator<_IteratorL>& __x,
1461 const move_iterator<_IteratorR>& __y)
1462#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1463 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1464#endif
1465 { return __x.base() == __y.base(); }
1466
1467#if __cpp_lib_three_way_comparison
1468 template<typename _IteratorL,
1469 three_way_comparable_with<_IteratorL> _IteratorR>
1470 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1471 operator<=>(const move_iterator<_IteratorL>& __x,
1472 const move_iterator<_IteratorR>& __y)
1473 { return __x.base() <=> __y.base(); }
1474#else
1475 template<typename _IteratorL, typename _IteratorR>
1476 inline _GLIBCXX17_CONSTEXPR bool
1477 operator!=(const move_iterator<_IteratorL>& __x,
1478 const move_iterator<_IteratorR>& __y)
1479 { return !(__x == __y); }
1480#endif
1481
1482 template<typename _IteratorL, typename _IteratorR>
1483 inline _GLIBCXX17_CONSTEXPR bool
1484 operator<(const move_iterator<_IteratorL>& __x,
1485 const move_iterator<_IteratorR>& __y)
1486#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1487 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1488#endif
1489 { return __x.base() < __y.base(); }
1490
1491 template<typename _IteratorL, typename _IteratorR>
1492 inline _GLIBCXX17_CONSTEXPR bool
1493 operator<=(const move_iterator<_IteratorL>& __x,
1494 const move_iterator<_IteratorR>& __y)
1495#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1496 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1497#endif
1498 { return !(__y < __x); }
1499
1500 template<typename _IteratorL, typename _IteratorR>
1501 inline _GLIBCXX17_CONSTEXPR bool
1502 operator>(const move_iterator<_IteratorL>& __x,
1503 const move_iterator<_IteratorR>& __y)
1504#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1505 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1506#endif
1507 { return __y < __x; }
1508
1509 template<typename _IteratorL, typename _IteratorR>
1510 inline _GLIBCXX17_CONSTEXPR bool
1511 operator>=(const move_iterator<_IteratorL>& __x,
1512 const move_iterator<_IteratorR>& __y)
1513#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1514 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1515#endif
1516 { return !(__x < __y); }
1517
1518#if ! (__cplusplus201402L > 201703L && __cpp_lib_concepts)
1519 // Note: See __normal_iterator operators note from Gaby to understand
1520 // why we have these extra overloads for some move_iterator operators.
1521
1522 // These extra overloads are not needed in C++20, because the ones above
1523 // are constrained with a requires-clause and so overload resolution will
1524 // prefer them to greedy unconstrained function templates.
1525
1526 template<typename _Iterator>
1527 inline _GLIBCXX17_CONSTEXPR bool
1528 operator==(const move_iterator<_Iterator>& __x,
1529 const move_iterator<_Iterator>& __y)
1530 { return __x.base() == __y.base(); }
1531
1532 template<typename _Iterator>
1533 inline _GLIBCXX17_CONSTEXPR bool
1534 operator!=(const move_iterator<_Iterator>& __x,
1535 const move_iterator<_Iterator>& __y)
1536 { return !(__x == __y); }
1537
1538 template<typename _Iterator>
1539 inline _GLIBCXX17_CONSTEXPR bool
1540 operator<(const move_iterator<_Iterator>& __x,
1541 const move_iterator<_Iterator>& __y)
1542 { return __x.base() < __y.base(); }
1543
1544 template<typename _Iterator>
1545 inline _GLIBCXX17_CONSTEXPR bool
1546 operator<=(const move_iterator<_Iterator>& __x,
1547 const move_iterator<_Iterator>& __y)
1548 { return !(__y < __x); }
1549
1550 template<typename _Iterator>
1551 inline _GLIBCXX17_CONSTEXPR bool
1552 operator>(const move_iterator<_Iterator>& __x,
1553 const move_iterator<_Iterator>& __y)
1554 { return __y < __x; }
1555
1556 template<typename _Iterator>
1557 inline _GLIBCXX17_CONSTEXPR bool
1558 operator>=(const move_iterator<_Iterator>& __x,
1559 const move_iterator<_Iterator>& __y)
1560 { return !(__x < __y); }
1561#endif // ! C++20
1562
1563 // DR 685.
1564 template<typename _IteratorL, typename _IteratorR>
1565 inline _GLIBCXX17_CONSTEXPR auto
1566 operator-(const move_iterator<_IteratorL>& __x,
1567 const move_iterator<_IteratorR>& __y)
1568 -> decltype(__x.base() - __y.base())
1569 { return __x.base() - __y.base(); }
1570
1571 template<typename _Iterator>
1572 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1573 operator+(typename move_iterator<_Iterator>::difference_type __n,
1574 const move_iterator<_Iterator>& __x)
1575 { return __x + __n; }
1576
1577 template<typename _Iterator>
1578 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1579 make_move_iterator(_Iterator __i)
1580 { return move_iterator<_Iterator>(std::move(__i)); }
1581
1582 template<typename _Iterator, typename _ReturnType
1583 = typename conditional<__move_if_noexcept_cond
1584 <typename iterator_traits<_Iterator>::value_type>::value,
1585 _Iterator, move_iterator<_Iterator>>::type>
1586 inline _GLIBCXX17_CONSTEXPR _ReturnType
1587 __make_move_if_noexcept_iterator(_Iterator __i)
1588 { return _ReturnType(__i); }
1589
1590 // Overload for pointers that matches std::move_if_noexcept more closely,
1591 // returning a constant iterator when we don't want to move.
1592 template<typename _Tp, typename _ReturnType
1593 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1594 const _Tp*, move_iterator<_Tp*>>::type>
1595 inline _GLIBCXX17_CONSTEXPR _ReturnType
1596 __make_move_if_noexcept_iterator(_Tp* __i)
1597 { return _ReturnType(__i); }
1598
1599#if __cplusplus201402L > 201703L && __cpp_lib_concepts
1600 // [iterators.common] Common iterators
1601
1602 namespace __detail
1603 {
1604 template<typename _It>
1605 concept __common_iter_has_arrow = indirectly_readable<const _It>
1606 && (requires(const _It& __it) { __it.operator->(); }
1607 || is_reference_v<iter_reference_t<_It>>
1608 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1609
1610 } // namespace __detail
1611
1612 /// An iterator/sentinel adaptor for representing a non-common range.
1613 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1614 requires (!same_as<_It, _Sent>) && copyable<_It>
1615 class common_iterator
1616 {
1617 template<typename _Tp, typename _Up>
1618 static constexpr bool
1619 _S_noexcept1()
1620 {
1621 if constexpr (is_trivially_default_constructible_v<_Tp>)
1622 return is_nothrow_assignable_v<_Tp, _Up>;
1623 else
1624 return is_nothrow_constructible_v<_Tp, _Up>;
1625 }
1626
1627 template<typename _It2, typename _Sent2>
1628 static constexpr bool
1629 _S_noexcept()
1630 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1631
1632 class _Proxy
1633 {
1634 iter_value_t<_It> _M_keep;
1635
1636 _Proxy(iter_reference_t<_It>&& __x)
1637 : _M_keep(std::move(__x)) { }
1638
1639 friend class common_iterator;
1640
1641 public:
1642 const iter_value_t<_It>*
1643 operator->() const
1644 { return std::__addressof(_M_keep); }
1645 };
1646
1647 public:
1648 constexpr
1649 common_iterator()
1650 noexcept(is_nothrow_default_constructible_v<_It>)
1651 : _M_it(), _M_index(0)
1652 { }
1653
1654 constexpr
1655 common_iterator(_It __i)
1656 noexcept(is_nothrow_move_constructible_v<_It>)
1657 : _M_it(std::move(__i)), _M_index(0)
1658 { }
1659
1660 constexpr
1661 common_iterator(_Sent __s)
1662 noexcept(is_nothrow_move_constructible_v<_Sent>)
1663 : _M_sent(std::move(__s)), _M_index(1)
1664 { }
1665
1666 template<typename _It2, typename _Sent2>
1667 requires convertible_to<const _It2&, _It>
1668 && convertible_to<const _Sent2&, _Sent>
1669 constexpr
1670 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1671 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1672 : _M_valueless(), _M_index(__x._M_index)
1673 {
1674 if (_M_index == 0)
1675 {
1676 if constexpr (is_trivially_default_constructible_v<_It>)
1677 _M_it = std::move(__x._M_it);
1678 else
1679 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1680 }
1681 else if (_M_index == 1)
1682 {
1683 if constexpr (is_trivially_default_constructible_v<_Sent>)
1684 _M_sent = std::move(__x._M_sent);
1685 else
1686 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1687 }
1688 }
1689
1690 constexpr
1691 common_iterator(const common_iterator& __x)
1692 noexcept(_S_noexcept<const _It&, const _Sent&>())
1693 : _M_valueless(), _M_index(__x._M_index)
1694 {
1695 if (_M_index == 0)
1696 {
1697 if constexpr (is_trivially_default_constructible_v<_It>)
1698 _M_it = std::move(__x._M_it);
1699 else
1700 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1701 }
1702 else if (_M_index == 1)
1703 {
1704 if constexpr (is_trivially_default_constructible_v<_Sent>)
1705 _M_sent = std::move(__x._M_sent);
1706 else
1707 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1708 }
1709 }
1710
1711 common_iterator&
1712 operator=(const common_iterator& __x)
1713 noexcept(is_nothrow_copy_assignable_v<_It>
1714 && is_nothrow_copy_assignable_v<_Sent>
1715 && is_nothrow_copy_constructible_v<_It>
1716 && is_nothrow_copy_constructible_v<_Sent>)
1717 {
1718 return this->operator=<_It, _Sent>(__x);
1719 }
1720
1721 template<typename _It2, typename _Sent2>
1722 requires convertible_to<const _It2&, _It>
1723 && convertible_to<const _Sent2&, _Sent>
1724 && assignable_from<_It&, const _It2&>
1725 && assignable_from<_Sent&, const _Sent2&>
1726 common_iterator&
1727 operator=(const common_iterator<_It2, _Sent2>& __x)
1728 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1729 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1730 && is_nothrow_assignable_v<_It, const _It2&>
1731 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1732 {
1733 switch(_M_index << 2 | __x._M_index)
1734 {
1735 case 0b0000:
1736 _M_it = __x._M_it;
1737 break;
1738 case 0b0101:
1739 _M_sent = __x._M_sent;
1740 break;
1741 case 0b0001:
1742 _M_it.~_It();
1743 _M_index = -1;
1744 [[fallthrough]];
1745 case 0b1001:
1746 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1747 _M_index = 1;
1748 break;
1749 case 0b0100:
1750 _M_sent.~_Sent();
1751 _M_index = -1;
1752 [[fallthrough]];
1753 case 0b1000:
1754 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1755 _M_index = 0;
1756 break;
1757 default:
1758 __glibcxx_assert(__x._M_has_value());
1759 __builtin_unreachable();
1760 }
1761 return *this;
1762 }
1763
1764 ~common_iterator()
1765 {
1766 switch (_M_index)
1767 {
1768 case 0:
1769 _M_it.~_It();
1770 break;
1771 case 1:
1772 _M_sent.~_Sent();
1773 break;
1774 }
1775 }
1776
1777 decltype(auto)
1778 operator*()
1779 {
1780 __glibcxx_assert(_M_index == 0);
1781 return *_M_it;
1782 }
1783
1784 decltype(auto)
1785 operator*() const requires __detail::__dereferenceable<const _It>
1786 {
1787 __glibcxx_assert(_M_index == 0);
1788 return *_M_it;
1789 }
1790
1791 decltype(auto)
1792 operator->() const requires __detail::__common_iter_has_arrow<_It>
1793 {
1794 __glibcxx_assert(_M_index == 0);
1795 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1796 return _M_it;
1797 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1798 {
1799 auto&& __tmp = *_M_it;
1800 return std::__addressof(__tmp);
1801 }
1802 else
1803 return _Proxy{*_M_it};
1804 }
1805
1806 common_iterator&
1807 operator++()
1808 {
1809 __glibcxx_assert(_M_index == 0);
1810 ++_M_it;
1811 return *this;
1812 }
1813
1814 decltype(auto)
1815 operator++(int)
1816 {
1817 __glibcxx_assert(_M_index == 0);
1818 if constexpr (forward_iterator<_It>)
1819 {
1820 common_iterator __tmp = *this;
1821 ++*this;
1822 return __tmp;
1823 }
1824 else
1825 return _M_it++;
1826 }
1827
1828 template<typename _It2, sentinel_for<_It> _Sent2>
1829 requires sentinel_for<_Sent, _It2>
1830 friend bool
1831 operator==(const common_iterator& __x,
1832 const common_iterator<_It2, _Sent2>& __y)
1833 {
1834 switch(__x._M_index << 2 | __y._M_index)
1835 {
1836 case 0b0000:
1837 case 0b0101:
1838 return true;
1839 case 0b0001:
1840 return __x._M_it == __y._M_sent;
1841 case 0b0100:
1842 return __x._M_sent == __y._M_it;
1843 default:
1844 __glibcxx_assert(__x._M_has_value());
1845 __glibcxx_assert(__y._M_has_value());
1846 __builtin_unreachable();
1847 }
1848 }
1849
1850 template<typename _It2, sentinel_for<_It> _Sent2>
1851 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1852 friend bool
1853 operator==(const common_iterator& __x,
1854 const common_iterator<_It2, _Sent2>& __y)
1855 {
1856 switch(__x._M_index << 2 | __y._M_index)
1857 {
1858 case 0b0101:
1859 return true;
1860 case 0b0000:
1861 return __x._M_it == __y._M_it;
1862 case 0b0001:
1863 return __x._M_it == __y._M_sent;
1864 case 0b0100:
1865 return __x._M_sent == __y._M_it;
1866 default:
1867 __glibcxx_assert(__x._M_has_value());
1868 __glibcxx_assert(__y._M_has_value());
1869 __builtin_unreachable();
1870 }
1871 }
1872
1873 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1874 requires sized_sentinel_for<_Sent, _It2>
1875 friend iter_difference_t<_It2>
1876 operator-(const common_iterator& __x,
1877 const common_iterator<_It2, _Sent2>& __y)
1878 {
1879 switch(__x._M_index << 2 | __y._M_index)
1880 {
1881 case 0b0101:
1882 return 0;
1883 case 0b0000:
1884 return __x._M_it - __y._M_it;
1885 case 0b0001:
1886 return __x._M_it - __y._M_sent;
1887 case 0b0100:
1888 return __x._M_sent - __y._M_it;
1889 default:
1890 __glibcxx_assert(__x._M_has_value());
1891 __glibcxx_assert(__y._M_has_value());
1892 __builtin_unreachable();
1893 }
1894 }
1895
1896 friend iter_rvalue_reference_t<_It>
1897 iter_move(const common_iterator& __i)
1898 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1899 requires input_iterator<_It>
1900 {
1901 __glibcxx_assert(__i._M_index == 0);
1902 return ranges::iter_move(__i._M_it);
1903 }
1904
1905 template<indirectly_swappable<_It> _It2, typename _Sent2>
1906 friend void
1907 iter_swap(const common_iterator& __x,
1908 const common_iterator<_It2, _Sent2>& __y)
1909 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1910 std::declval<const _It2&>())))
1911 {
1912 __glibcxx_assert(__x._M_index == 0);
1913 __glibcxx_assert(__y._M_index == 0);
1914 return ranges::iter_swap(__x._M_it, __y._M_it);
1915 }
1916
1917 private:
1918 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1919 friend class common_iterator;
1920
1921 bool _M_has_value() const noexcept { return _M_index < 2; }
1922
1923 union
1924 {
1925 _It _M_it;
1926 _Sent _M_sent;
1927 unsigned char _M_valueless;
1928 };
1929 unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
1930 };
1931
1932 template<typename _It, typename _Sent>
1933 struct incrementable_traits<common_iterator<_It, _Sent>>
1934 {
1935 using difference_type = iter_difference_t<_It>;
1936 };
1937
1938 template<input_iterator _It, typename _Sent>
1939 struct iterator_traits<common_iterator<_It, _Sent>>
1940 {
1941 private:
1942 template<typename _Iter>
1943 struct __ptr
1944 {
1945 using type = void;
1946 };
1947
1948 template<typename _Iter>
1949 requires __detail::__common_iter_has_arrow<_Iter>
1950 struct __ptr<_Iter>
1951 {
1952 using _CIter = common_iterator<_Iter, _Sent>;
1953 using type = decltype(std::declval<const _CIter&>().operator->());
1954 };
1955
1956 public:
1957 using iterator_concept = conditional_t<forward_iterator<_It>,
1958 forward_iterator_tag, input_iterator_tag>;
1959 using iterator_category = __detail::__clamp_iter_cat<
1960 typename iterator_traits<_It>::iterator_category,
1961 forward_iterator_tag, input_iterator_tag>;
1962 using value_type = iter_value_t<_It>;
1963 using difference_type = iter_difference_t<_It>;
1964 using pointer = typename __ptr<_It>::type;
1965 using reference = iter_reference_t<_It>;
1966 };
1967
1968 // [iterators.counted] Counted iterators
1969
1970 /// An iterator adaptor that keeps track of the distance to the end.
1971 template<input_or_output_iterator _It>
1972 class counted_iterator
1973 {
1974 public:
1975 using iterator_type = _It;
1976
1977 constexpr counted_iterator() = default;
1978
1979 constexpr
1980 counted_iterator(_It __i, iter_difference_t<_It> __n)
1981 : _M_current(std::move(__i)), _M_length(__n)
1982 { __glibcxx_assert(__n >= 0); }
1983
1984 template<typename _It2>
1985 requires convertible_to<const _It2&, _It>
1986 constexpr
1987 counted_iterator(const counted_iterator<_It2>& __x)
1988 : _M_current(__x._M_current), _M_length(__x._M_length)
1989 { }
1990
1991 template<typename _It2>
1992 requires assignable_from<_It&, const _It2&>
1993 constexpr counted_iterator&
1994 operator=(const counted_iterator<_It2>& __x)
1995 {
1996 _M_current = __x._M_current;
1997 _M_length = __x._M_length;
1998 return *this;
1999 }
2000
2001 constexpr _It
2002 base() const &
2003 noexcept(is_nothrow_copy_constructible_v<_It>)
2004 requires copy_constructible<_It>
2005 { return _M_current; }
2006
2007 constexpr _It
2008 base() &&
2009 noexcept(is_nothrow_move_constructible_v<_It>)
2010 { return std::move(_M_current); }
2011
2012 constexpr iter_difference_t<_It>
2013 count() const noexcept { return _M_length; }
2014
2015 constexpr decltype(auto)
2016 operator*()
2017 noexcept(noexcept(*_M_current))
2018 { return *_M_current; }
2019
2020 constexpr decltype(auto)
2021 operator*() const
2022 noexcept(noexcept(*_M_current))
2023 requires __detail::__dereferenceable<const _It>
2024 { return *_M_current; }
2025
2026 constexpr counted_iterator&
2027 operator++()
2028 {
2029 __glibcxx_assert(_M_length > 0);
2030 ++_M_current;
2031 --_M_length;
2032 return *this;
2033 }
2034
2035 decltype(auto)
2036 operator++(int)
2037 {
2038 __glibcxx_assert(_M_length > 0);
2039 --_M_length;
2040 __tryif (true)
2041 {
2042 return _M_current++;
2043 } __catch(...)if (false) {
2044 ++_M_length;
2045 __throw_exception_again;
2046 }
2047
2048 }
2049
2050 constexpr counted_iterator
2051 operator++(int) requires forward_iterator<_It>
2052 {
2053 auto __tmp = *this;
2054 ++*this;
2055 return __tmp;
2056 }
2057
2058 constexpr counted_iterator&
2059 operator--() requires bidirectional_iterator<_It>
2060 {
2061 --_M_current;
2062 ++_M_length;
2063 return *this;
2064 }
2065
2066 constexpr counted_iterator
2067 operator--(int) requires bidirectional_iterator<_It>
2068 {
2069 auto __tmp = *this;
2070 --*this;
2071 return __tmp;
2072 }
2073
2074 constexpr counted_iterator
2075 operator+(iter_difference_t<_It> __n) const
2076 requires random_access_iterator<_It>
2077 { return counted_iterator(_M_current + __n, _M_length - __n); }
2078
2079 friend constexpr counted_iterator
2080 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2081 requires random_access_iterator<_It>
2082 { return __x + __n; }
2083
2084 constexpr counted_iterator&
2085 operator+=(iter_difference_t<_It> __n)
2086 requires random_access_iterator<_It>
2087 {
2088 __glibcxx_assert(__n <= _M_length);
2089 _M_current += __n;
2090 _M_length -= __n;
2091 return *this;
2092 }
2093
2094 constexpr counted_iterator
2095 operator-(iter_difference_t<_It> __n) const
2096 requires random_access_iterator<_It>
2097 { return counted_iterator(_M_current - __n, _M_length + __n); }
2098
2099 template<common_with<_It> _It2>
2100 friend constexpr iter_difference_t<_It2>
2101 operator-(const counted_iterator& __x,
2102 const counted_iterator<_It2>& __y)
2103 { return __y._M_length - __x._M_length; }
2104
2105 friend constexpr iter_difference_t<_It>
2106 operator-(const counted_iterator& __x, default_sentinel_t)
2107 { return -__x._M_length; }
2108
2109 friend constexpr iter_difference_t<_It>
2110 operator-(default_sentinel_t, const counted_iterator& __y)
2111 { return __y._M_length; }
2112
2113 constexpr counted_iterator&
2114 operator-=(iter_difference_t<_It> __n)
2115 requires random_access_iterator<_It>
2116 {
2117 __glibcxx_assert(-__n <= _M_length);
2118 _M_current -= __n;
2119 _M_length += __n;
2120 return *this;
2121 }
2122
2123 constexpr decltype(auto)
2124 operator[](iter_difference_t<_It> __n) const
2125 noexcept(noexcept(_M_current[__n]))
2126 requires random_access_iterator<_It>
2127 {
2128 __glibcxx_assert(__n < _M_length);
2129 return _M_current[__n];
2130 }
2131
2132 template<common_with<_It> _It2>
2133 friend constexpr bool
2134 operator==(const counted_iterator& __x,
2135 const counted_iterator<_It2>& __y)
2136 { return __x._M_length == __y._M_length; }
2137
2138 friend constexpr bool
2139 operator==(const counted_iterator& __x, default_sentinel_t)
2140 { return __x._M_length == 0; }
2141
2142 template<common_with<_It> _It2>
2143 friend constexpr strong_ordering
2144 operator<=>(const counted_iterator& __x,
2145 const counted_iterator<_It2>& __y)
2146 { return __y._M_length <=> __x._M_length; }
2147
2148 friend constexpr iter_rvalue_reference_t<_It>
2149 iter_move(const counted_iterator& __i)
2150 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2151 requires input_iterator<_It>
2152 { return ranges::iter_move(__i._M_current); }
2153
2154 template<indirectly_swappable<_It> _It2>
2155 friend constexpr void
2156 iter_swap(const counted_iterator& __x,
2157 const counted_iterator<_It2>& __y)
2158 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2159 { ranges::iter_swap(__x._M_current, __y._M_current); }
2160
2161 private:
2162 template<input_or_output_iterator _It2> friend class counted_iterator;
2163
2164 _It _M_current = _It();
2165 iter_difference_t<_It> _M_length = 0;
2166 };
2167
2168 template<typename _It>
2169 struct incrementable_traits<counted_iterator<_It>>
2170 {
2171 using difference_type = iter_difference_t<_It>;
2172 };
2173
2174 template<input_iterator _It>
2175 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2176 {
2177 using pointer = void;
2178 };
2179#endif // C++20
2180
2181 // @} group iterators
2182
2183 template<typename _Iterator>
2184 auto
2185 __niter_base(move_iterator<_Iterator> __it)
2186 -> decltype(make_move_iterator(__niter_base(__it.base())))
2187 { return make_move_iterator(__niter_base(__it.base())); }
2188
2189 template<typename _Iterator>
2190 struct __is_move_iterator<move_iterator<_Iterator> >
2191 {
2192 enum { __value = 1 };
2193 typedef __true_type __type;
2194 };
2195
2196 template<typename _Iterator>
2197 auto
2198 __miter_base(move_iterator<_Iterator> __it)
2199 -> decltype(__miter_base(__it.base()))
2200 { return __miter_base(__it.base()); }
2201
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) \
2204 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
2209
2210#if __cpp_deduction_guides >= 201606
2211 // These helper traits are used for deduction guides
2212 // of associative containers.
2213 template<typename _InputIterator>
2214 using __iter_key_t = remove_const_t<
2215 typename iterator_traits<_InputIterator>::value_type::first_type>;
2216
2217 template<typename _InputIterator>
2218 using __iter_val_t =
2219 typename iterator_traits<_InputIterator>::value_type::second_type;
2220
2221 template<typename _T1, typename _T2>
2222 struct pair;
2223
2224 template<typename _InputIterator>
2225 using __iter_to_alloc_t =
2226 pair<add_const_t<__iter_key_t<_InputIterator>>,
2227 __iter_val_t<_InputIterator>>;
2228#endif // __cpp_deduction_guides
2229
2230_GLIBCXX_END_NAMESPACE_VERSION
2231} // namespace
2232
2233#ifdef _GLIBCXX_DEBUG
2234# include <debug/stl_iterator.h>
2235#endif
2236
2237#endif