/build/source/clang/lib/Tooling/Transformer/RewriteRule.cpp

Bug Summary

File:	build/source/clang/lib/Tooling/Transformer/RewriteRule.cpp
Warning:	line 362, column 5 Potential leak of memory pointed to by field '_M_pi'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name RewriteRule.cpp -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 -relaxed-aliasing -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D CLANG_REPOSITORY_STRING="++20230329111212+81358e9193a9-1~exp1~20230329111325.1193" -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/clang/lib/Tooling/Transformer -I /build/source/clang/lib/Tooling/Transformer -I /build/source/clang/include -I tools/clang/include -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/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 -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1680088406 -O2 -Wno-unused-command-line-argument -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 -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -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-2023-03-29-134735-16347-1 -x c++ /build/source/clang/lib/Tooling/Transformer/RewriteRule.cpp

/build/source/clang/lib/Tooling/Transformer/RewriteRule.cpp

→

1//===--- Transformer.cpp - Transformer library implementation ---*- 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#include "clang/Tooling/Transformer/RewriteRule.h"
10#include "clang/AST/ASTTypeTraits.h"
11#include "clang/AST/Stmt.h"
12#include "clang/ASTMatchers/ASTMatchFinder.h"
13#include "clang/ASTMatchers/ASTMatchers.h"
14#include "clang/Basic/SourceLocation.h"
15#include "clang/Tooling/Transformer/SourceCode.h"
16#include "llvm/ADT/StringRef.h"
17#include "llvm/Support/Errc.h"
18#include "llvm/Support/Error.h"
19#include <map>
20#include <string>
21#include <utility>
22#include <vector>
23 
24using namespace clang;
25using namespace transformer;
26 
27using ast_matchers::MatchFinder;
28using ast_matchers::internal::DynTypedMatcher;
29 
30using MatchResult = MatchFinder::MatchResult;
31 
32const char transformer::RootID[] = "___root___";
33 
34static Expected<SmallVector<transformer::Edit, 1>>
35translateEdits(const MatchResult &Result, ArrayRef<ASTEdit> ASTEdits) {
36  SmallVector<transformer::Edit, 1> Edits;
37  for (const auto &E : ASTEdits) {
38    Expected<CharSourceRange> Range = E.TargetRange(Result);
39    if (!Range)
40      return Range.takeError();
41    std::optional<CharSourceRange> EditRange =
42        tooling::getFileRangeForEdit(*Range, *Result.Context);
43    // FIXME: let user specify whether to treat this case as an error or ignore
44    // it as is currently done. This behavior is problematic in that it hides
45    // failures from bad ranges. Also, the behavior here differs from
46    // `flatten`. Here, we abort (without error), whereas flatten, if it hits an
47    // empty list, does not abort. As a result, `editList({A,B})` is not
48    // equivalent to `flatten(edit(A), edit(B))`. The former will abort if `A`
49    // produces a bad range, whereas the latter will simply ignore A.
50    if (!EditRange)
51      return SmallVector<Edit, 0>();
52    transformer::Edit T;
53    T.Kind = E.Kind;
54    T.Range = *EditRange;
55    if (E.Replacement) {
56      auto Replacement = E.Replacement->eval(Result);
57      if (!Replacement)
58        return Replacement.takeError();
59      T.Replacement = std::move(*Replacement);
60    }
61    if (E.Note) {
62      auto Note = E.Note->eval(Result);
63      if (!Note)
64        return Note.takeError();
65      T.Note = std::move(*Note);
66    }
67    if (E.Metadata) {
68      auto Metadata = E.Metadata(Result);
69      if (!Metadata)
70        return Metadata.takeError();
71      T.Metadata = std::move(*Metadata);
72    }
73    Edits.push_back(std::move(T));
74  }
75  return Edits;
76}
77 
78EditGenerator transformer::editList(SmallVector<ASTEdit, 1> Edits) {
79  return [Edits = std::move(Edits)](const MatchResult &Result) {
80    return translateEdits(Result, Edits);
81  };
82}
83 
84EditGenerator transformer::edit(ASTEdit Edit) {
85  return [Edit = std::move(Edit)](const MatchResult &Result) {
86    return translateEdits(Result, {Edit});
87  };
88}
89 
90EditGenerator transformer::noopEdit(RangeSelector Anchor) {
91  return [Anchor = std::move(Anchor)](const MatchResult &Result)
92             -> Expected<SmallVector<transformer::Edit, 1>> {
93    Expected<CharSourceRange> Range = Anchor(Result);
94    if (!Range)
95      return Range.takeError();
96    // In case the range is inside a macro expansion, map the location back to a
97    // "real" source location.
98    SourceLocation Begin =
99        Result.SourceManager->getSpellingLoc(Range->getBegin());
100    Edit E;
101    // Implicitly, leave `E.Replacement` as the empty string.
102    E.Kind = EditKind::Range;
103    E.Range = CharSourceRange::getCharRange(Begin, Begin);
104    return SmallVector<Edit, 1>{E};
105  };
106}
107 
108EditGenerator
109transformer::flattenVector(SmallVector<EditGenerator, 2> Generators) {
110  if (Generators.size() == 1)
111    return std::move(Generators[0]);
112  return
113      [Gs = std::move(Generators)](
114          const MatchResult &Result) -> llvm::Expected<SmallVector<Edit, 1>> {
115        SmallVector<Edit, 1> AllEdits;
116        for (const auto &G : Gs) {
117          llvm::Expected<SmallVector<Edit, 1>> Edits = G(Result);
118          if (!Edits)
119            return Edits.takeError();
120          AllEdits.append(Edits->begin(), Edits->end());
121        }
122        return AllEdits;
123      };
124}
125 
126ASTEdit transformer::changeTo(RangeSelector Target, TextGenerator Replacement) {
127  ASTEdit E;
128  E.TargetRange = std::move(Target);
129  E.Replacement = std::move(Replacement);
130  return E;
131}
132 
133ASTEdit transformer::note(RangeSelector Anchor, TextGenerator Note) {
134  ASTEdit E;
135  E.TargetRange = transformer::before(Anchor);
136  E.Note = std::move(Note);
137  return E;
138}
139 
140namespace {
141/// A \c TextGenerator that always returns a fixed string.
142class SimpleTextGenerator : public MatchComputation<std::string> {
143  std::string S;
144 
145public:
146  SimpleTextGenerator(std::string S) : S(std::move(S)) {}
147  llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &,
148                   std::string *Result) const override {
149    Result->append(S);
150    return llvm::Error::success();
151  }
152  std::string toString() const override {
153    return (llvm::Twine("text(\"") + S + "\")").str();
154  }
155};
156} // namespace
157 
158static TextGenerator makeText(std::string S) {
159  return std::make_shared<SimpleTextGenerator>(std::move(S));
5
←
Calling 'make_shared<(anonymous namespace)::SimpleTextGenerator, std::basic_string<char>>'→
23
←
Returned allocated memory→
160}
161 
162ASTEdit transformer::remove(RangeSelector S) {
163  return change(std::move(S), makeText(""));
164}
165 
166static std::string formatHeaderPath(StringRef Header, IncludeFormat Format) {
167  switch (Format) {
168  case transformer::IncludeFormat::Quoted:
169    return Header.str();
170  case transformer::IncludeFormat::Angled:
171    return ("<" + Header + ">").str();
172  }
173  llvm_unreachable("Unknown transformer::IncludeFormat enum")::llvm::llvm_unreachable_internal("Unknown transformer::IncludeFormat enum"
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 173);
174}
175 
176ASTEdit transformer::addInclude(RangeSelector Target, StringRef Header,
177                                IncludeFormat Format) {
178  ASTEdit E;
179  E.Kind = EditKind::AddInclude;
180  E.TargetRange = Target;
181  E.Replacement = makeText(formatHeaderPath(Header, Format));
4
←
Calling 'makeText'→
24
←
Returned allocated memory→
182  return E;
183}
184 
185EditGenerator
186transformer::detail::makeEditGenerator(llvm::SmallVector<ASTEdit, 1> Edits) {
187  return editList(std::move(Edits));
188}
189 
190EditGenerator transformer::detail::makeEditGenerator(ASTEdit Edit) {
191  return edit(std::move(Edit));
192}
193 
194RewriteRule transformer::detail::makeRule(DynTypedMatcher M,
195                                          EditGenerator Edits) {
196  RewriteRule R;
197  R.Cases = {{std::move(M), std::move(Edits)}};
198  return R;
199}
200 
201RewriteRule transformer::makeRule(ast_matchers::internal::DynTypedMatcher M,
202                                  std::initializer_list<ASTEdit> Edits) {
203  return detail::makeRule(std::move(M),
204                          detail::makeEditGenerator(std::move(Edits)));
205}
206 
207namespace {
208 
209/// Unconditionally binds the given node set before trying `InnerMatcher` and
210/// keeps the bound nodes on a successful match.
211template <typename T>
212class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> {
213  ast_matchers::BoundNodes Nodes;
214  const ast_matchers::internal::Matcher<T> InnerMatcher;
215 
216public:
217  explicit BindingsMatcher(ast_matchers::BoundNodes Nodes,
218                           ast_matchers::internal::Matcher<T> InnerMatcher)
219      : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {}
220 
221  bool matches(
222      const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
223      ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
224    ast_matchers::internal::BoundNodesTreeBuilder Result(*Builder);
225    for (const auto &N : Nodes.getMap())
226      Result.setBinding(N.first, N.second);
227    if (InnerMatcher.matches(Node, Finder, &Result)) {
228      *Builder = std::move(Result);
229      return true;
230    }
231    return false;
232  }
233};
234 
235/// Matches nodes of type T that have at least one descendant node for which the
236/// given inner matcher matches.  Will match for each descendant node that
237/// matches.  Based on ForEachDescendantMatcher, but takes a dynamic matcher,
238/// instead of a static one, because it is used by RewriteRule, which carries
239/// (only top-level) dynamic matchers.
240template <typename T>
241class DynamicForEachDescendantMatcher
242    : public ast_matchers::internal::MatcherInterface<T> {
243  const DynTypedMatcher DescendantMatcher;
244 
245public:
246  explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)
247      : DescendantMatcher(std::move(DescendantMatcher)) {}
248 
249  bool matches(
250      const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
251      ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
252    return Finder->matchesDescendantOf(
253        Node, this->DescendantMatcher, Builder,
254        ast_matchers::internal::ASTMatchFinder::BK_All);
255  }
256};
257 
258template <typename T>
259ast_matchers::internal::Matcher<T>
260forEachDescendantDynamically(ast_matchers::BoundNodes Nodes,
261                             DynTypedMatcher M) {
262  return ast_matchers::internal::makeMatcher(new BindingsMatcher<T>(
263      std::move(Nodes),
264      ast_matchers::internal::makeMatcher(
265          new DynamicForEachDescendantMatcher<T>(std::move(M)))));
266}
267 
268class ApplyRuleCallback : public MatchFinder::MatchCallback {
269public:
270  ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {}
271 
272  template <typename T>
273  void registerMatchers(const ast_matchers::BoundNodes &Nodes,
274                        MatchFinder *MF) {
275    for (auto &Matcher : transformer::detail::buildMatchers(Rule))
276      MF->addMatcher(forEachDescendantDynamically<T>(Nodes, Matcher), this);
277  }
278 
279  void run(const MatchFinder::MatchResult &Result) override {
280    if (!Edits)
281      return;
282    size_t I = transformer::detail::findSelectedCase(Result, Rule);
283    auto Transformations = Rule.Cases[I].Edits(Result);
284    if (!Transformations) {
285      Edits = Transformations.takeError();
286      return;
287    }
288    Edits->append(Transformations->begin(), Transformations->end());
289  }
290 
291  RewriteRule Rule;
292 
293  // Initialize to a non-error state.
294  Expected<SmallVector<Edit, 1>> Edits = SmallVector<Edit, 1>();
295};
296} // namespace
297 
298template <typename T>
299llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
300rewriteDescendantsImpl(const T &Node, RewriteRule Rule,
301                       const MatchResult &Result) {
302  ApplyRuleCallback Callback(std::move(Rule));
303  MatchFinder Finder;
304  Callback.registerMatchers<T>(Result.Nodes, &Finder);
305  Finder.match(Node, *Result.Context);
306  return std::move(Callback.Edits);
307}
308 
309llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
310transformer::detail::rewriteDescendants(const Decl &Node, RewriteRule Rule,
311                                        const MatchResult &Result) {
312  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
313}
314 
315llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
316transformer::detail::rewriteDescendants(const Stmt &Node, RewriteRule Rule,
317                                        const MatchResult &Result) {
318  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
319}
320 
321llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
322transformer::detail::rewriteDescendants(const TypeLoc &Node, RewriteRule Rule,
323                                        const MatchResult &Result) {
324  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
325}
326 
327llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
328transformer::detail::rewriteDescendants(const DynTypedNode &DNode,
329                                        RewriteRule Rule,
330                                        const MatchResult &Result) {
331  if (const auto *Node = DNode.get<Decl>())
332    return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
333  if (const auto *Node = DNode.get<Stmt>())
334    return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
335  if (const auto *Node = DNode.get<TypeLoc>())
336    return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
337 
338  return llvm::make_error<llvm::StringError>(
339      llvm::errc::invalid_argument,
340      "type unsupported for recursive rewriting, Kind=" +
341          DNode.getNodeKind().asStringRef());
342}
343 
344EditGenerator transformer::rewriteDescendants(std::string NodeId,
345                                              RewriteRule Rule) {
346  return [NodeId = std::move(NodeId),
347          Rule = std::move(Rule)](const MatchResult &Result)
348             -> llvm::Expected<SmallVector<clang::transformer::Edit, 1>> {
349    const ast_matchers::BoundNodes::IDToNodeMap &NodesMap =
350        Result.Nodes.getMap();
351    auto It = NodesMap.find(NodeId);
352    if (It == NodesMap.end())
353      return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument,
354                                                 "ID not bound: " + NodeId);
355    return detail::rewriteDescendants(It->second, std::move(Rule), Result);
356  };
357}
358 
359void transformer::addInclude(RewriteRuleBase &Rule, StringRef Header,
360                             IncludeFormat Format) {
361  for (auto &Case : Rule.Cases)
1
Assuming '__begin1' is not equal to '__end1'→
362    Case.Edits = flatten(std::move(Case.Edits), addInclude(Header, Format));
2
←
Calling 'addInclude'→
26
←
Returned allocated memory→
27
←
Potential leak of memory pointed to by field '_M_pi'
363}
364 
365#ifndef NDEBUG
366// Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds
367// (all node matcher types except for `QualType` and `Type`), rather than just
368// banning `QualType` and `Type`.
369static bool hasValidKind(const DynTypedMatcher &M) {
370  return !M.canConvertTo<QualType>();
371}
372#endif
373 
374// Binds each rule's matcher to a unique (and deterministic) tag based on
375// `TagBase` and the id paired with the case. All of the returned matchers have
376// their traversal kind explicitly set, either based on a pre-set kind or to the
377// provided `DefaultTraversalKind`.
378static std::vector<DynTypedMatcher> taggedMatchers(
379    StringRef TagBase,
380    const SmallVectorImpl<std::pair<size_t, RewriteRule::Case>> &Cases,
381    TraversalKind DefaultTraversalKind) {
382  std::vector<DynTypedMatcher> Matchers;
383  Matchers.reserve(Cases.size());
384  for (const auto &Case : Cases) {
385    std::string Tag = (TagBase + Twine(Case.first)).str();
386    // HACK: Many matchers are not bindable, so ensure that tryBind will work.
387    DynTypedMatcher BoundMatcher(Case.second.Matcher);
388    BoundMatcher.setAllowBind(true);
389    auto M = *BoundMatcher.tryBind(Tag);
390    Matchers.push_back(!M.getTraversalKind()
391                           ? M.withTraversalKind(DefaultTraversalKind)
392                           : std::move(M));
393  }
394  return Matchers;
395}
396 
397// Simply gathers the contents of the various rules into a single rule. The
398// actual work to combine these into an ordered choice is deferred to matcher
399// registration.
400template <>
401RewriteRuleWith<void>
402transformer::applyFirst(ArrayRef<RewriteRuleWith<void>> Rules) {
403  RewriteRule R;
404  for (auto &Rule : Rules)
405    R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
406  return R;
407}
408 
409std::vector<DynTypedMatcher>
410transformer::detail::buildMatchers(const RewriteRuleBase &Rule) {
411  // Map the cases into buckets of matchers -- one for each "root" AST kind,
412  // which guarantees that they can be combined in a single anyOf matcher. Each
413  // case is paired with an identifying number that is converted to a string id
414  // in `taggedMatchers`.
415  std::map<ASTNodeKind,
416           SmallVector<std::pair<size_t, RewriteRuleBase::Case>, 1>>
417      Buckets;
418  const SmallVectorImpl<RewriteRule::Case> &Cases = Rule.Cases;
419  for (int I = 0, N = Cases.size(); I < N; ++I) {
420    assert(hasValidKind(Cases[I].Matcher) &&(static_cast <bool> (hasValidKind(Cases[I].Matcher) &&
 "Matcher must be non-(Qual)Type node matcher") ? void (0) : __assert_fail
 ("hasValidKind(Cases[I].Matcher) && \"Matcher must be non-(Qual)Type node matcher\""
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 421, __extension__
 __PRETTY_FUNCTION__))
421           "Matcher must be non-(Qual)Type node matcher")(static_cast <bool> (hasValidKind(Cases[I].Matcher) &&
 "Matcher must be non-(Qual)Type node matcher") ? void (0) : __assert_fail
 ("hasValidKind(Cases[I].Matcher) && \"Matcher must be non-(Qual)Type node matcher\""
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 421, __extension__
 __PRETTY_FUNCTION__));
422    Buckets[Cases[I].Matcher.getSupportedKind()].emplace_back(I, Cases[I]);
423  }
424 
425  // Each anyOf explicitly controls the traversal kind. The anyOf itself is set
426  // to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to the kind
427  // of the branches. Then, each branch is either left as is, if the kind is
428  // already set, or explicitly set to `TK_AsIs`. We choose this setting because
429  // it is the default interpretation of matchers.
430  std::vector<DynTypedMatcher> Matchers;
431  for (const auto &Bucket : Buckets) {
432    DynTypedMatcher M = DynTypedMatcher::constructVariadic(
433        DynTypedMatcher::VO_AnyOf, Bucket.first,
434        taggedMatchers("Tag", Bucket.second, TK_AsIs));
435    M.setAllowBind(true);
436    // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
437    Matchers.push_back(M.tryBind(RootID)->withTraversalKind(TK_AsIs));
438  }
439  return Matchers;
440}
441 
442DynTypedMatcher transformer::detail::buildMatcher(const RewriteRuleBase &Rule) {
443  std::vector<DynTypedMatcher> Ms = buildMatchers(Rule);
444  assert(Ms.size() == 1 && "Cases must have compatible matchers.")(static_cast <bool> (Ms.size() == 1 && "Cases must have compatible matchers."
) ? void (0) : __assert_fail ("Ms.size() == 1 && \"Cases must have compatible matchers.\""
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 444, __extension__
 __PRETTY_FUNCTION__));
445  return Ms[0];
446}
447 
448SourceLocation transformer::detail::getRuleMatchLoc(const MatchResult &Result) {
449  auto &NodesMap = Result.Nodes.getMap();
450  auto Root = NodesMap.find(RootID);
451  assert(Root != NodesMap.end() && "Transformation failed: missing root node.")(static_cast <bool> (Root != NodesMap.end() && "Transformation failed: missing root node."
) ? void (0) : __assert_fail ("Root != NodesMap.end() && \"Transformation failed: missing root node.\""
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 451, __extension__
 __PRETTY_FUNCTION__));
452  std::optional<CharSourceRange> RootRange = tooling::getFileRangeForEdit(
453      CharSourceRange::getTokenRange(Root->second.getSourceRange()),
454      *Result.Context);
455  if (RootRange)
456    return RootRange->getBegin();
457  // The match doesn't have a coherent range, so fall back to the expansion
458  // location as the "beginning" of the match.
459  return Result.SourceManager->getExpansionLoc(
460      Root->second.getSourceRange().getBegin());
461}
462 
463// Finds the case that was "selected" -- that is, whose matcher triggered the
464// `MatchResult`.
465size_t transformer::detail::findSelectedCase(const MatchResult &Result,
466                                             const RewriteRuleBase &Rule) {
467  if (Rule.Cases.size() == 1)
468    return 0;
469 
470  auto &NodesMap = Result.Nodes.getMap();
471  for (size_t i = 0, N = Rule.Cases.size(); i < N; ++i) {
472    std::string Tag = ("Tag" + Twine(i)).str();
473    if (NodesMap.find(Tag) != NodesMap.end())
474      return i;
475  }
476  llvm_unreachable("No tag found for this rule.")::llvm::llvm_unreachable_internal("No tag found for this rule."
, "clang/lib/Tooling/Transformer/RewriteRule.cpp", 476);
477}

←

/build/source/clang/include/clang/Tooling/Transformer/RewriteRule.h

→

1//===--- RewriteRule.h - RewriteRule class ----------------------*- 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///  \file
10///  Defines the RewriteRule class and related functions for creating,
11///  modifying and interpreting RewriteRules.
12///
13//===----------------------------------------------------------------------===//
14 
15#ifndef LLVM_CLANG_TOOLING_TRANSFORMER_REWRITERULE_H
16#define LLVM_CLANG_TOOLING_TRANSFORMER_REWRITERULE_H
17 
18#include "clang/ASTMatchers/ASTMatchFinder.h"
19#include "clang/ASTMatchers/ASTMatchers.h"
20#include "clang/ASTMatchers/ASTMatchersInternal.h"
21#include "clang/Tooling/Refactoring/AtomicChange.h"
22#include "clang/Tooling/Transformer/MatchConsumer.h"
23#include "clang/Tooling/Transformer/RangeSelector.h"
24#include "llvm/ADT/Any.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/Support/Error.h"
28#include <functional>
29#include <string>
30#include <utility>
31 
32namespace clang {
33namespace transformer {
34// Specifies how to interpret an edit.
35enum class EditKind {
36  // Edits a source range in the file.
37  Range,
38  // Inserts an include in the file. The `Replacement` field is the name of the
39  // newly included file.
40  AddInclude,
41};
42 
43/// A concrete description of a source edit, represented by a character range in
44/// the source to be replaced and a corresponding replacement string.
45struct Edit {
46  EditKind Kind = EditKind::Range;
47  CharSourceRange Range;
48  std::string Replacement;
49  std::string Note;
50  llvm::Any Metadata;
51};
52 
53/// Format of the path in an include directive -- angle brackets or quotes.
54enum class IncludeFormat {
55  Quoted,
56  Angled,
57};
58 
59/// Maps a match result to a list of concrete edits (with possible
60/// failure). This type is a building block of rewrite rules, but users will
61/// generally work in terms of `ASTEdit`s (below) rather than directly in terms
62/// of `EditGenerator`.
63using EditGenerator = MatchConsumer<llvm::SmallVector<Edit, 1>>;
64 
65template <typename T> using Generator = std::shared_ptr<MatchComputation<T>>;
66 
67using TextGenerator = Generator<std::string>;
68 
69using AnyGenerator = MatchConsumer<llvm::Any>;
70 
71// Description of a source-code edit, expressed in terms of an AST node.
72// Includes: an ID for the (bound) node, a selector for source related to the
73// node, a replacement and, optionally, an explanation for the edit.
74//
75// * Target: the source code impacted by the rule. This identifies an AST node,
76//   or part thereof (\c Part), whose source range indicates the extent of the
77//   replacement applied by the replacement term.  By default, the extent is the
78//   node matched by the pattern term (\c NodePart::Node). Target's are typed
79//   (\c Kind), which guides the determination of the node extent.
80//
81// * Replacement: a function that produces a replacement string for the target,
82//   based on the match result.
83//
84// * Note: (optional) a note specifically for this edit, potentially referencing
85//   elements of the match.  This will be displayed to the user, where possible;
86//   for example, in clang-tidy diagnostics.  Use of notes should be rare --
87//   explanations of the entire rewrite should be set in the rule
88//   (`RewriteRule::Explanation`) instead.  Notes serve the rare cases wherein
89//   edit-specific diagnostics are required.
90//
91// `ASTEdit` should be built using the `change` convenience functions. For
92// example,
93// \code
94//   changeTo(name(fun), cat("Frodo"))
95// \endcode
96// Or, if we use Stencil for the TextGenerator:
97// \code
98//   using stencil::cat;
99//   changeTo(statement(thenNode), cat("{", thenNode, "}"))
100//   changeTo(callArgs(call), cat(x, ",", y))
101// \endcode
102// Or, if you are changing the node corresponding to the rule's matcher, you can
103// use the single-argument override of \c change:
104// \code
105//   changeTo(cat("different_expr"))
106// \endcode
107struct ASTEdit {
108  EditKind Kind = EditKind::Range;
109  RangeSelector TargetRange;
110  TextGenerator Replacement;
111  TextGenerator Note;
112  // Not all transformations will want or need to attach metadata and therefore
113  // should not be required to do so.
114  AnyGenerator Metadata = [](const ast_matchers::MatchFinder::MatchResult &)
115      -> llvm::Expected<llvm::Any> {
116    return llvm::Expected<llvm::Any>(llvm::Any());
117  };
118};
119 
120/// Generates a single (specified) edit.
121EditGenerator edit(ASTEdit E);
122 
123/// Lifts a list of `ASTEdit`s into an `EditGenerator`.
124///
125/// The `EditGenerator` will return an empty vector if any of the edits apply to
126/// portions of the source that are ineligible for rewriting (certain
127/// interactions with macros, for example) and it will fail if any invariants
128/// are violated relating to bound nodes in the match.  However, it does not
129/// fail in the case of conflicting edits -- conflict handling is left to
130/// clients.  We recommend use of the \c AtomicChange or \c Replacements classes
131/// for assistance in detecting such conflicts.
132EditGenerator editList(llvm::SmallVector<ASTEdit, 1> Edits);
133 
134/// Generates no edits.
135inline EditGenerator noEdits() { return editList({}); }
136 
137/// Generates a single, no-op edit anchored at the start location of the
138/// specified range. A `noopEdit` may be preferred over `noEdits` to associate a
139/// diagnostic `Explanation` with the rule.
140EditGenerator noopEdit(RangeSelector Anchor);
141 
142/// Generates a single, no-op edit with the associated note anchored at the
143/// start location of the specified range.
144ASTEdit note(RangeSelector Anchor, TextGenerator Note);
145 
146/// Version of `ifBound` specialized to `ASTEdit`.
147inline EditGenerator ifBound(std::string ID, ASTEdit TrueEdit,
148                             ASTEdit FalseEdit) {
149  return ifBound(std::move(ID), edit(std::move(TrueEdit)),
150                 edit(std::move(FalseEdit)));
151}
152 
153/// Version of `ifBound` that has no "False" branch. If the node is not bound,
154/// then no edits are produced.
155inline EditGenerator ifBound(std::string ID, ASTEdit TrueEdit) {
156  return ifBound(std::move(ID), edit(std::move(TrueEdit)), noEdits());
157}
158 
159/// Flattens a list of generators into a single generator whose elements are the
160/// concatenation of the results of the argument generators.
161EditGenerator flattenVector(SmallVector<EditGenerator, 2> Generators);
162 
163namespace detail {
164/// Helper function to construct an \c EditGenerator. Overloaded for common
165/// cases so that user doesn't need to specify which factory function to
166/// use. This pattern gives benefits similar to implicit constructors, while
167/// maintaing a higher degree of explicitness.
168inline EditGenerator injectEdits(ASTEdit E) { return edit(std::move(E)); }
169inline EditGenerator injectEdits(EditGenerator G) { return G; }
170} // namespace detail
171 
172template <typename... Ts> EditGenerator flatten(Ts &&...Edits) {
173  return flattenVector({detail::injectEdits(std::forward<Ts>(Edits))...});
174}
175 
176// Every rewrite rule is triggered by a match against some AST node.
177// Transformer guarantees that this ID is bound to the triggering node whenever
178// a rewrite rule is applied.
179extern const char RootID[];
180 
181/// Replaces a portion of the source text with \p Replacement.
182ASTEdit changeTo(RangeSelector Target, TextGenerator Replacement);
183/// DEPRECATED: use \c changeTo.
184inline ASTEdit change(RangeSelector Target, TextGenerator Replacement) {
185  return changeTo(std::move(Target), std::move(Replacement));
186}
187 
188/// Replaces the entirety of a RewriteRule's match with \p Replacement.  For
189/// example, to replace a function call, one could write:
190/// \code
191///   makeRule(callExpr(callee(functionDecl(hasName("foo")))),
192///            changeTo(cat("bar()")))
193/// \endcode
194inline ASTEdit changeTo(TextGenerator Replacement) {
195  return changeTo(node(RootID), std::move(Replacement));
196}
197/// DEPRECATED: use \c changeTo.
198inline ASTEdit change(TextGenerator Replacement) {
199  return changeTo(std::move(Replacement));
200}
201 
202/// Inserts \p Replacement before \p S, leaving the source selected by \S
203/// unchanged.
204inline ASTEdit insertBefore(RangeSelector S, TextGenerator Replacement) {
205  return changeTo(before(std::move(S)), std::move(Replacement));
206}
207 
208/// Inserts \p Replacement after \p S, leaving the source selected by \S
209/// unchanged.
210inline ASTEdit insertAfter(RangeSelector S, TextGenerator Replacement) {
211  return changeTo(after(std::move(S)), std::move(Replacement));
212}
213 
214/// Removes the source selected by \p S.
215ASTEdit remove(RangeSelector S);
216 
217/// Adds an include directive for the given header to the file of `Target`. The
218/// particular location specified by `Target` is ignored.
219ASTEdit addInclude(RangeSelector Target, StringRef Header,
220                   IncludeFormat Format = IncludeFormat::Quoted);
221 
222/// Adds an include directive for the given header to the file associated with
223/// `RootID`. If `RootID` matches inside a macro expansion, will add the
224/// directive to the file in which the macro was expanded (as opposed to the
225/// file in which the macro is defined).
226inline ASTEdit addInclude(StringRef Header,
227                          IncludeFormat Format = IncludeFormat::Quoted) {
228  return addInclude(expansion(node(RootID)), Header, Format);
3
←
Calling 'addInclude'→
25
←
Returned allocated memory→
229}
230 
231// FIXME: If `Metadata` returns an `llvm::Expected<T>` the `AnyGenerator` will
232// construct an `llvm::Expected<llvm::Any>` where no error is present but the
233// `llvm::Any` holds the error. This is unlikely but potentially surprising.
234// Perhaps the `llvm::Expected` should be unwrapped, or perhaps this should be a
235// compile-time error. No solution here is perfect.
236//
237// Note: This function template accepts any type callable with a MatchResult
238// rather than a `std::function` because the return-type needs to be deduced. If
239// it accepted a `std::function<R(MatchResult)>`, lambdas or other callable
240// types would not be able to deduce `R`, and users would be forced to specify
241// explicitly the type they intended to return by wrapping the lambda at the
242// call-site.
243template <typename Callable>
244inline ASTEdit withMetadata(ASTEdit Edit, Callable Metadata) {
245  Edit.Metadata =
246      [Gen = std::move(Metadata)](
247          const ast_matchers::MatchFinder::MatchResult &R) -> llvm::Any {
248    return Gen(R);
249  };
250 
251  return Edit;
252}
253 
254/// Assuming that the inner range is enclosed by the outer range, creates
255/// precision edits to remove the parts of the outer range that are not included
256/// in the inner range.
257inline EditGenerator shrinkTo(RangeSelector outer, RangeSelector inner) {
258  return editList({remove(enclose(before(outer), before(inner))),
259                   remove(enclose(after(inner), after(outer)))});
260}
261 
262/// Description of a source-code transformation.
263//
264// A *rewrite rule* describes a transformation of source code. A simple rule
265// contains each of the following components:
266//
267// * Matcher: the pattern term, expressed as clang matchers (with Transformer
268//   extensions).
269//
270// * Edits: a set of Edits to the source code, described with ASTEdits.
271//
272// However, rules can also consist of (sub)rules, where the first that matches
273// is applied and the rest are ignored.  So, the above components together form
274// a logical "case" and a rule is a sequence of cases.
275//
276// Rule cases have an additional, implicit, component: the parameters. These are
277// portions of the pattern which are left unspecified, yet bound in the pattern
278// so that we can reference them in the edits.
279//
280// The \c Transformer class can be used to apply the rewrite rule and obtain the
281// corresponding replacements.
282struct RewriteRuleBase {
283  struct Case {
284    ast_matchers::internal::DynTypedMatcher Matcher;
285    EditGenerator Edits;
286  };
287  // We expect RewriteRules will most commonly include only one case.
288  SmallVector<Case, 1> Cases;
289};
290 
291/// A source-code transformation with accompanying metadata.
292///
293/// When a case of the rule matches, the \c Transformer invokes the
294/// corresponding metadata generator and provides it alongside the edits.
295template <typename MetadataT> struct RewriteRuleWith : RewriteRuleBase {
296  SmallVector<Generator<MetadataT>, 1> Metadata;
297};
298 
299template <> struct RewriteRuleWith<void> : RewriteRuleBase {};
300 
301using RewriteRule = RewriteRuleWith<void>;
302 
303namespace detail {
304 
305RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
306                     EditGenerator Edits);
307 
308template <typename MetadataT>
309RewriteRuleWith<MetadataT> makeRule(ast_matchers::internal::DynTypedMatcher M,
310                                    EditGenerator Edits,
311                                    Generator<MetadataT> Metadata) {
312  RewriteRuleWith<MetadataT> R;
313  R.Cases = {{std::move(M), std::move(Edits)}};
314  R.Metadata = {std::move(Metadata)};
315  return R;
316}
317 
318inline EditGenerator makeEditGenerator(EditGenerator Edits) { return Edits; }
319EditGenerator makeEditGenerator(llvm::SmallVector<ASTEdit, 1> Edits);
320EditGenerator makeEditGenerator(ASTEdit Edit);
321 
322} // namespace detail
323 
324/// Constructs a simple \c RewriteRule. \c Edits can be an \c EditGenerator,
325/// multiple \c ASTEdits, or a single \c ASTEdit.
326/// @{
327template <int &..., typename EditsT>
328RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
329                     EditsT &&Edits) {
330  return detail::makeRule(
331      std::move(M), detail::makeEditGenerator(std::forward<EditsT>(Edits)));
332}
333 
334RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
335                     std::initializer_list<ASTEdit> Edits);
336/// @}
337 
338/// Overloads of \c makeRule that also generate metadata when matching.
339/// @{
340template <typename MetadataT, int &..., typename EditsT>
341RewriteRuleWith<MetadataT> makeRule(ast_matchers::internal::DynTypedMatcher M,
342                                    EditsT &&Edits,
343                                    Generator<MetadataT> Metadata) {
344  return detail::makeRule(
345      std::move(M), detail::makeEditGenerator(std::forward<EditsT>(Edits)),
346      std::move(Metadata));
347}
348 
349template <typename MetadataT>
350RewriteRuleWith<MetadataT> makeRule(ast_matchers::internal::DynTypedMatcher M,
351                                    std::initializer_list<ASTEdit> Edits,
352                                    Generator<MetadataT> Metadata) {
353  return detail::makeRule(std::move(M),
354                          detail::makeEditGenerator(std::move(Edits)),
355                          std::move(Metadata));
356}
357/// @}
358 
359/// For every case in Rule, adds an include directive for the given header. The
360/// common use is assumed to be a rule with only one case. For example, to
361/// replace a function call and add headers corresponding to the new code, one
362/// could write:
363/// \code
364///   auto R = makeRule(callExpr(callee(functionDecl(hasName("foo")))),
365///            changeTo(cat("bar()")));
366///   addInclude(R, "path/to/bar_header.h");
367///   addInclude(R, "vector", IncludeFormat::Angled);
368/// \endcode
369void addInclude(RewriteRuleBase &Rule, llvm::StringRef Header,
370                IncludeFormat Format = IncludeFormat::Quoted);
371 
372/// Applies the first rule whose pattern matches; other rules are ignored.  If
373/// the matchers are independent then order doesn't matter. In that case,
374/// `applyFirst` is simply joining the set of rules into one.
375//
376// `applyFirst` is like an `anyOf` matcher with an edit action attached to each
377// of its cases. Anywhere you'd use `anyOf(m1.bind("id1"), m2.bind("id2"))` and
378// then dispatch on those ids in your code for control flow, `applyFirst` lifts
379// that behavior to the rule level.  So, you can write `applyFirst({makeRule(m1,
380// action1), makeRule(m2, action2), ...});`
381//
382// For example, consider a type `T` with a deterministic serialization function,
383// `serialize()`.  For performance reasons, we would like to make it
384// non-deterministic.  Therefore, we want to drop the expectation that
385// `a.serialize() = b.serialize() iff a = b` (although we'll maintain
386// `deserialize(a.serialize()) = a`).
387//
388// We have three cases to consider (for some equality function, `eq`):
389// ```
390// eq(a.serialize(), b.serialize()) --> eq(a,b)
391// eq(a, b.serialize())             --> eq(deserialize(a), b)
392// eq(a.serialize(), b)             --> eq(a, deserialize(b))
393// ```
394//
395// `applyFirst` allows us to specify each independently:
396// ```
397// auto eq_fun = functionDecl(...);
398// auto method_call = cxxMemberCallExpr(...);
399//
400// auto two_calls = callExpr(callee(eq_fun), hasArgument(0, method_call),
401//                           hasArgument(1, method_call));
402// auto left_call =
403//     callExpr(callee(eq_fun), callExpr(hasArgument(0, method_call)));
404// auto right_call =
405//     callExpr(callee(eq_fun), callExpr(hasArgument(1, method_call)));
406//
407// RewriteRule R = applyFirst({makeRule(two_calls, two_calls_action),
408//                             makeRule(left_call, left_call_action),
409//                             makeRule(right_call, right_call_action)});
410// ```
411/// @{
412template <typename MetadataT>
413RewriteRuleWith<MetadataT>
414applyFirst(ArrayRef<RewriteRuleWith<MetadataT>> Rules) {
415  RewriteRuleWith<MetadataT> R;
416  for (auto &Rule : Rules) {
417    assert(Rule.Cases.size() == Rule.Metadata.size() &&(static_cast <bool> (Rule.Cases.size() == Rule.Metadata
.size() && "mis-match in case and metadata array size"
) ? void (0) : __assert_fail ("Rule.Cases.size() == Rule.Metadata.size() && \"mis-match in case and metadata array size\""
, "clang/include/clang/Tooling/Transformer/RewriteRule.h", 418
, __extension__ __PRETTY_FUNCTION__))
418           "mis-match in case and metadata array size")(static_cast <bool> (Rule.Cases.size() == Rule.Metadata
.size() && "mis-match in case and metadata array size"
) ? void (0) : __assert_fail ("Rule.Cases.size() == Rule.Metadata.size() && \"mis-match in case and metadata array size\""
, "clang/include/clang/Tooling/Transformer/RewriteRule.h", 418
, __extension__ __PRETTY_FUNCTION__));
419    R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
420    R.Metadata.append(Rule.Metadata.begin(), Rule.Metadata.end());
421  }
422  return R;
423}
424 
425template <>
426RewriteRuleWith<void> applyFirst(ArrayRef<RewriteRuleWith<void>> Rules);
427 
428template <typename MetadataT>
429RewriteRuleWith<MetadataT>
430applyFirst(const std::vector<RewriteRuleWith<MetadataT>> &Rules) {
431  return applyFirst(llvm::ArrayRef(Rules));
432}
433 
434template <typename MetadataT>
435RewriteRuleWith<MetadataT>
436applyFirst(std::initializer_list<RewriteRuleWith<MetadataT>> Rules) {
437  return applyFirst(llvm::ArrayRef(Rules.begin(), Rules.end()));
438}
439/// @}
440 
441/// Converts a \c RewriteRuleWith<T> to a \c RewriteRule by stripping off the
442/// metadata generators.
443template <int &..., typename MetadataT>
444std::enable_if_t<!std::is_same<MetadataT, void>::value, RewriteRule>
445stripMetadata(RewriteRuleWith<MetadataT> Rule) {
446  RewriteRule R;
447  R.Cases = std::move(Rule.Cases);
448  return R;
449}
450 
451/// Applies `Rule` to all descendants of the node bound to `NodeId`. `Rule` can
452/// refer to nodes bound by the calling rule. `Rule` is not applied to the node
453/// itself.
454///
455/// For example,
456/// ```
457/// auto InlineX =
458///     makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
459/// makeRule(functionDecl(hasName("f"), hasBody(stmt().bind("body"))).bind("f"),
460///          flatten(
461///            changeTo(name("f"), cat("newName")),
462///            rewriteDescendants("body", InlineX)));
463/// ```
464/// Here, we find the function `f`, change its name to `newName` and change all
465/// appearances of `x` in its body to `3`.
466EditGenerator rewriteDescendants(std::string NodeId, RewriteRule Rule);
467 
468/// The following three functions are a low-level part of the RewriteRule
469/// API. We expose them for use in implementing the fixtures that interpret
470/// RewriteRule, like Transformer and TransfomerTidy, or for more advanced
471/// users.
472//
473// FIXME: These functions are really public, if advanced, elements of the
474// RewriteRule API.  Recast them as such.  Or, just declare these functions
475// public and well-supported and move them out of `detail`.
476namespace detail {
477/// The following overload set is a version of `rewriteDescendants` that
478/// operates directly on the AST, rather than generating a Transformer
479/// combinator. It applies `Rule` to all descendants of `Node`, although not
480/// `Node` itself. `Rule` can refer to nodes bound in `Result`.
481///
482/// For example, assuming that "body" is bound to a function body in MatchResult
483/// `Results`, this will produce edits to change all appearances of `x` in that
484/// body to `3`.
485/// ```
486/// auto InlineX =
487///     makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
488/// const auto *Node = Results.Nodes.getNodeAs<Stmt>("body");
489/// auto Edits = rewriteDescendants(*Node, InlineX, Results);
490/// ```
491/// @{
492llvm::Expected<SmallVector<Edit, 1>>
493rewriteDescendants(const Decl &Node, RewriteRule Rule,
494                   const ast_matchers::MatchFinder::MatchResult &Result);
495 
496llvm::Expected<SmallVector<Edit, 1>>
497rewriteDescendants(const Stmt &Node, RewriteRule Rule,
498                   const ast_matchers::MatchFinder::MatchResult &Result);
499 
500llvm::Expected<SmallVector<Edit, 1>>
501rewriteDescendants(const TypeLoc &Node, RewriteRule Rule,
502                   const ast_matchers::MatchFinder::MatchResult &Result);
503 
504llvm::Expected<SmallVector<Edit, 1>>
505rewriteDescendants(const DynTypedNode &Node, RewriteRule Rule,
506                   const ast_matchers::MatchFinder::MatchResult &Result);
507/// @}
508 
509/// Builds a single matcher for the rule, covering all of the rule's cases.
510/// Only supports Rules whose cases' matchers share the same base "kind"
511/// (`Stmt`, `Decl`, etc.)  Deprecated: use `buildMatchers` instead, which
512/// supports mixing matchers of different kinds.
513ast_matchers::internal::DynTypedMatcher
514buildMatcher(const RewriteRuleBase &Rule);
515 
516/// Builds a set of matchers that cover the rule.
517///
518/// One matcher is built for each distinct node matcher base kind: Stmt, Decl,
519/// etc. Node-matchers for `QualType` and `Type` are not permitted, since such
520/// nodes carry no source location information and are therefore not relevant
521/// for rewriting. If any such matchers are included, will return an empty
522/// vector.
523std::vector<ast_matchers::internal::DynTypedMatcher>
524buildMatchers(const RewriteRuleBase &Rule);
525 
526/// Gets the beginning location of the source matched by a rewrite rule. If the
527/// match occurs within a macro expansion, returns the beginning of the
528/// expansion point. `Result` must come from the matching of a rewrite rule.
529SourceLocation
530getRuleMatchLoc(const ast_matchers::MatchFinder::MatchResult &Result);
531 
532/// Returns the index of the \c Case of \c Rule that was selected in the match
533/// result. Assumes a matcher built with \c buildMatcher.
534size_t findSelectedCase(const ast_matchers::MatchFinder::MatchResult &Result,
535                        const RewriteRuleBase &Rule);
536} // namespace detail
537} // namespace transformer
538} // namespace clang
539 
540#endif // LLVM_CLANG_TOOLING_TRANSFORMER_REWRITERULE_H

←

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

→

1// shared_ptr and weak_ptr implementation -*- C++ -*-

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

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

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

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

25// GCC Note: Based on files from version 1.32.0 of the Boost library.

27//  shared_count.hpp
28//  Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

30//  shared_ptr.hpp
31//  Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
32//  Copyright (C) 2001, 2002, 2003 Peter Dimov

34//  weak_ptr.hpp
35//  Copyright (C) 2001, 2002, 2003 Peter Dimov

37//  enable_shared_from_this.hpp
38//  Copyright (C) 2002 Peter Dimov

40// Distributed under the Boost Software License, Version 1.0. (See
41// accompanying file LICENSE_1_0.txt or copy at
42// http://www.boost.org/LICENSE_1_0.txt)

44/** @file
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

49#ifndef _SHARED_PTR_H1
50#define _SHARED_PTR_H1 1

52#include <bits/shared_ptr_base.h>

54namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
55{
56_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * @addtogroup pointer_abstractions
 * @{
 */

// 20.7.2.2.11 shared_ptr I/O

/// Write the stored pointer to an ostream.
/// @relates shared_ptr
template<typename _Ch, typename _Tr, typename _Tp, _Lock_policy _Lp>
  inline std::basic_ostream<_Ch, _Tr>&
  operator<<(std::basic_ostream<_Ch, _Tr>& __os,
      const __shared_ptr<_Tp, _Lp>& __p)
  {
    __os << __p.get();
    return __os;
  }

template<typename _Del, typename _Tp, _Lock_policy _Lp>
  inline _Del*
  get_deleter(const __shared_ptr<_Tp, _Lp>& __p) noexcept
  {
80#if __cpp_rtti199711L
    return static_cast<_Del*>(__p._M_get_deleter(typeid(_Del)));
82#else
    return 0;
84#endif
  }

/// 20.7.2.2.10 shared_ptr get_deleter

/// If `__p` has a deleter of type `_Del`, return a pointer to it.
/// @relates shared_ptr
template<typename _Del, typename _Tp>
  inline _Del*
  get_deleter(const shared_ptr<_Tp>& __p) noexcept
  {
95#if __cpp_rtti199711L
    return static_cast<_Del*>(__p._M_get_deleter(typeid(_Del)));
97#else
    return 0;
99#endif
  }

/**
 *  @brief  A smart pointer with reference-counted copy semantics.
 *
 * A `shared_ptr` object is either empty or _owns_ a pointer passed
 * to the constructor. Copies of a `shared_ptr` share ownership of
 * the same pointer. When the last `shared_ptr` that owns the pointer
 * is destroyed or reset, the owned pointer is freed (either by `delete`
 * or by invoking a custom deleter that was passed to the constructor).
 *
 * A `shared_ptr` also stores another pointer, which is usually
 * (but not always) the same pointer as it owns. The stored pointer
 * can be retrieved by calling the `get()` member function.
 *
 * The equality and relational operators for `shared_ptr` only compare
 * the stored pointer returned by `get()`, not the owned pointer.
 * To test whether two `shared_ptr` objects share ownership of the same
 * pointer see `std::shared_ptr::owner_before` and `std::owner_less`.
*/
template<typename _Tp>
  class shared_ptr : public __shared_ptr<_Tp>
  {
    template<typename... _Args>
using _Constructible = typename enable_if<
 is_constructible<__shared_ptr<_Tp>, _Args...>::value
>::type;

    template<typename _Arg>
using _Assignable = typename enable_if<
 is_assignable<__shared_ptr<_Tp>&, _Arg>::value, shared_ptr&
>::type;

  public:

    /// The type pointed to by the stored pointer, remove_extent_t<_Tp>
    using element_type = typename __shared_ptr<_Tp>::element_type;

138#if __cplusplus201703L >= 201703L
139# define __cpp_lib_shared_ptr_weak_type201606 201606
    /// The corresponding weak_ptr type for this shared_ptr
    using weak_type = weak_ptr<_Tp>;
142#endif
    /**
     *  @brief  Construct an empty %shared_ptr.
     *  @post   use_count()==0 && get()==0
     */
    constexpr shared_ptr() noexcept : __shared_ptr<_Tp>() { }

    shared_ptr(const shared_ptr&) noexcept = default; ///< Copy constructor

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p.
     *  @param  __p  A pointer that is convertible to element_type*.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @c delete @a __p is called.
     */
    template<typename _Yp, typename = _Constructible<_Yp*>>
explicit
shared_ptr(_Yp* __p) : __shared_ptr<_Tp>(__p) { }

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p
     *          and the deleter @a __d.
     *  @param  __p  A pointer.
     *  @param  __d  A deleter.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw
     *
     *  __shared_ptr will release __p by calling __d(__p)
     */
    template<typename _Yp, typename _Deleter,
      typename = _Constructible<_Yp*, _Deleter>>
shared_ptr(_Yp* __p, _Deleter __d)
      : __shared_ptr<_Tp>(__p, std::move(__d)) { }

    /**
     *  @brief  Construct a %shared_ptr that owns a null pointer
     *          and the deleter @a __d.
     *  @param  __p  A null pointer constant.
     *  @param  __d  A deleter.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw
     *
     *  The last owner will call __d(__p)
     */
    template<typename _Deleter>
shared_ptr(nullptr_t __p, _Deleter __d)
      : __shared_ptr<_Tp>(__p, std::move(__d)) { }

    /**
     *  @brief  Construct a %shared_ptr that owns the pointer @a __p
     *          and the deleter @a __d.
     *  @param  __p  A pointer.
     *  @param  __d  A deleter.
     *  @param  __a  An allocator.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw _Alloc's copy constructor and destructor must not
     *  throw.
     *
     *  __shared_ptr will release __p by calling __d(__p)
     */
    template<typename _Yp, typename _Deleter, typename _Alloc,
      typename = _Constructible<_Yp*, _Deleter, _Alloc>>
shared_ptr(_Yp* __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, std::move(__d), std::move(__a)) { }

    /**
     *  @brief  Construct a %shared_ptr that owns a null pointer
     *          and the deleter @a __d.
     *  @param  __p  A null pointer constant.
     *  @param  __d  A deleter.
     *  @param  __a  An allocator.
     *  @post   use_count() == 1 && get() == __p
     *  @throw  std::bad_alloc, in which case @a __d(__p) is called.
     *
     *  Requirements: _Deleter's copy constructor and destructor must
     *  not throw _Alloc's copy constructor and destructor must not
     *  throw.
     *
     *  The last owner will call __d(__p)
     */
    template<typename _Deleter, typename _Alloc>
shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: __shared_ptr<_Tp>(__p, std::move(__d), std::move(__a)) { }

    // Aliasing constructor

    /**
     *  @brief  Constructs a `shared_ptr` instance that stores `__p`
     *          and shares ownership with `__r`.
     *  @param  __r  A `shared_ptr`.
     *  @param  __p  A pointer that will remain valid while `*__r` is valid.
     *  @post   `get() == __p && use_count() == __r.use_count()`
     *
     *  This can be used to construct a `shared_ptr` to a sub-object
     *  of an object managed by an existing `shared_ptr`. The complete
     *  object will remain valid while any `shared_ptr` owns it, even
     *  if they don't store a pointer to the complete object.
     *
     * @code
     * shared_ptr<pair<int,int>> pii(new pair<int,int>());
     * shared_ptr<int> pi(pii, &pii->first);
     * assert(pii.use_count() == 2);
     * @endcode
     */
    template<typename _Yp>
shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) noexcept
: __shared_ptr<_Tp>(__r, __p) { }

259#if __cplusplus201703L > 201703L
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2996. Missing rvalue overloads for shared_ptr operations
    /**
     *  @brief  Constructs a `shared_ptr` instance that stores `__p`
     *          and shares ownership with `__r`.
     *  @param  __r  A `shared_ptr`.
     *  @param  __p  A pointer that will remain valid while `*__r` is valid.
     *  @post   `get() == __p && !__r.use_count() && !__r.get()`
     *
     *  This can be used to construct a `shared_ptr` to a sub-object
     *  of an object managed by an existing `shared_ptr`. The complete
     *  object will remain valid while any `shared_ptr` owns it, even
     *  if they don't store a pointer to the complete object.
     *
     * @code
     * shared_ptr<pair<int,int>> pii(new pair<int,int>());
     * shared_ptr<int> pi1(pii, &pii->first);
     * assert(pii.use_count() == 2);
     * shared_ptr<int> pi2(std::move(pii), &pii->second);
     * assert(pii.use_count() == 0);
     * @endcode
     */
    template<typename _Yp>
shared_ptr(shared_ptr<_Yp>&& __r, element_type* __p) noexcept
: __shared_ptr<_Tp>(std::move(__r), __p) { }
285#endif
    /**
     *  @brief  If @a __r is empty, constructs an empty %shared_ptr;
     *          otherwise construct a %shared_ptr that shares ownership
     *          with @a __r.
     *  @param  __r  A %shared_ptr.
     *  @post   get() == __r.get() && use_count() == __r.use_count()
     */
    template<typename _Yp,
      typename = _Constructible<const shared_ptr<_Yp>&>>
shared_ptr(const shared_ptr<_Yp>& __r) noexcept
      : __shared_ptr<_Tp>(__r) { }

    /**
     *  @brief  Move-constructs a %shared_ptr instance from @a __r.
     *  @param  __r  A %shared_ptr rvalue.
     *  @post   *this contains the old value of @a __r, @a __r is empty.
     */
    shared_ptr(shared_ptr&& __r) noexcept
    : __shared_ptr<_Tp>(std::move(__r)) { }

    /**
     *  @brief  Move-constructs a %shared_ptr instance from @a __r.
     *  @param  __r  A %shared_ptr rvalue.
     *  @post   *this contains the old value of @a __r, @a __r is empty.
     */
    template<typename _Yp, typename = _Constructible<shared_ptr<_Yp>>>
shared_ptr(shared_ptr<_Yp>&& __r) noexcept
: __shared_ptr<_Tp>(std::move(__r)) { }

    /**
     *  @brief  Constructs a %shared_ptr that shares ownership with @a __r
     *          and stores a copy of the pointer stored in @a __r.
     *  @param  __r  A weak_ptr.
     *  @post   use_count() == __r.use_count()
     *  @throw  bad_weak_ptr when __r.expired(),
     *          in which case the constructor has no effect.
     */
    template<typename _Yp, typename = _Constructible<const weak_ptr<_Yp>&>>
explicit shared_ptr(const weak_ptr<_Yp>& __r)
: __shared_ptr<_Tp>(__r) { }

327#if _GLIBCXX_USE_DEPRECATED1
328#pragma GCC diagnostic push
329#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
    template<typename _Yp, typename = _Constructible<auto_ptr<_Yp>>>
shared_ptr(auto_ptr<_Yp>&& __r);
332#pragma GCC diagnostic pop
333#endif

    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2399. shared_ptr's constructor from unique_ptr should be constrained
    template<typename _Yp, typename _Del,
      typename = _Constructible<unique_ptr<_Yp, _Del>>>
shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: __shared_ptr<_Tp>(std::move(__r)) { }

342#if __cplusplus201703L <= 201402L && _GLIBCXX_USE_DEPRECATED1
    // This non-standard constructor exists to support conversions that
    // were possible in C++11 and C++14 but are ill-formed in C++17.
    // If an exception is thrown this constructor has no effect.
    template<typename _Yp, typename _Del,
_Constructible<unique_ptr<_Yp, _Del>, __sp_array_delete>* = 0>
shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: __shared_ptr<_Tp>(std::move(__r), __sp_array_delete()) { }
350#endif

    /**
     *  @brief  Construct an empty %shared_ptr.
     *  @post   use_count() == 0 && get() == nullptr
     */
    constexpr shared_ptr(nullptr_t) noexcept : shared_ptr() { }

    shared_ptr& operator=(const shared_ptr&) noexcept = default;

    template<typename _Yp>
_Assignable<const shared_ptr<_Yp>&>
operator=(const shared_ptr<_Yp>& __r) noexcept
{
 this->__shared_ptr<_Tp>::operator=(__r);
 return *this;
}

368#if _GLIBCXX_USE_DEPRECATED1
369#pragma GCC diagnostic push
370#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
    template<typename _Yp>
_Assignable<auto_ptr<_Yp>>
operator=(auto_ptr<_Yp>&& __r)
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}
378#pragma GCC diagnostic pop
379#endif

    shared_ptr&
    operator=(shared_ptr&& __r) noexcept
    {
this->__shared_ptr<_Tp>::operator=(std::move(__r));
return *this;
    }

    template<class _Yp>
_Assignable<shared_ptr<_Yp>>
operator=(shared_ptr<_Yp>&& __r) noexcept
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

    template<typename _Yp, typename _Del>
_Assignable<unique_ptr<_Yp, _Del>>
operator=(unique_ptr<_Yp, _Del>&& __r)
{
 this->__shared_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

  private:
    // This constructor is non-standard, it is used by allocate_shared.
    template<typename _Alloc, typename... _Args>
shared_ptr(_Sp_alloc_shared_tag<_Alloc> __tag, _Args&&... __args)
: __shared_ptr<_Tp>(__tag, std::forward<_Args>(__args)...)
8
←
Calling constructor for '__shared_ptr<(anonymous namespace)::SimpleTextGenerator, __gnu_cxx::_S_atomic>'→
20
←
Returning from constructor for '__shared_ptr<(anonymous namespace)::SimpleTextGenerator, __gnu_cxx::_S_atomic>'→
{ }

    template<typename _Yp, typename _Alloc, typename... _Args>
friend shared_ptr<_Yp>
allocate_shared(const _Alloc& __a, _Args&&... __args);

    // This constructor is non-standard, it is used by weak_ptr::lock().
    shared_ptr(const weak_ptr<_Tp>& __r, std::nothrow_t)
    : __shared_ptr<_Tp>(__r, std::nothrow) { }

    friend class weak_ptr<_Tp>;
  };

422#if __cpp_deduction_guides201703L >= 201606
template<typename _Tp>
  shared_ptr(weak_ptr<_Tp>) ->  shared_ptr<_Tp>;
template<typename _Tp, typename _Del>
  shared_ptr(unique_ptr<_Tp, _Del>) ->  shared_ptr<_Tp>;
427#endif

// 20.7.2.2.7 shared_ptr comparisons

/// @relates shared_ptr @{

/// Equality operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator==(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  { return __a.get() == __b.get(); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator==(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !__a; }

445#ifdef __cpp_lib_three_way_comparison
template<typename _Tp, typename _Up>
  inline strong_ordering
  operator<=>(const shared_ptr<_Tp>& __a,
const shared_ptr<_Up>& __b) noexcept
  { return compare_three_way()(__a.get(), __b.get()); }

template<typename _Tp>
  inline strong_ordering
  operator<=>(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  {
    using pointer = typename shared_ptr<_Tp>::element_type*;
    return compare_three_way()(__a.get(), static_cast<pointer>(nullptr));
  }
459#else
/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator==(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !__a; }

/// Inequality operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator!=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  { return __a.get() != __b.get(); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator!=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return (bool)__a; }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator!=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return (bool)__a; }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  {
    using _Tp_elt = typename shared_ptr<_Tp>::element_type;
    using _Up_elt = typename shared_ptr<_Up>::element_type;
    using _Vp = typename common_type<_Tp_elt*, _Up_elt*>::type;
    return less<_Vp>()(__a.get(), __b.get());
  }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  {
    using _Tp_elt = typename shared_ptr<_Tp>::element_type;
    return less<_Tp_elt*>()(__a.get(), nullptr);
  }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  {
    using _Tp_elt = typename shared_ptr<_Tp>::element_type;
    return less<_Tp_elt*>()(nullptr, __a.get());
  }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  { return !(__b < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !(nullptr < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator<=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !(__a < nullptr); }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  { return (__b < __a); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return nullptr < __a; }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return __a < nullptr; }

/// Relational operator for shared_ptr objects, compares the stored pointers
template<typename _Tp, typename _Up>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>=(const shared_ptr<_Tp>& __a, const shared_ptr<_Up>& __b) noexcept
  { return !(__a < __b); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>=(const shared_ptr<_Tp>& __a, nullptr_t) noexcept
  { return !(__a < nullptr); }

/// shared_ptr comparison with nullptr
template<typename _Tp>
  _GLIBCXX_NODISCARD[[__nodiscard__]] inline bool
  operator>=(nullptr_t, const shared_ptr<_Tp>& __a) noexcept
  { return !(nullptr < __a); }
566#endif

// 20.7.2.2.8 shared_ptr specialized algorithms.

/// Swap overload for shared_ptr
template<typename _Tp>
  inline void
  swap(shared_ptr<_Tp>& __a, shared_ptr<_Tp>& __b) noexcept
  { __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts.

/// Convert type of `shared_ptr`, via `static_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  static_pointer_cast(const shared_ptr<_Up>& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(__r, static_cast<typename _Sp::element_type*>(__r.get()));
  }

/// Convert type of `shared_ptr`, via `const_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  const_pointer_cast(const shared_ptr<_Up>& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(__r, const_cast<typename _Sp::element_type*>(__r.get()));
  }

/// Convert type of `shared_ptr`, via `dynamic_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  dynamic_pointer_cast(const shared_ptr<_Up>& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(__r, __p);
    return _Sp();
  }

607#if __cplusplus201703L >= 201703L
/// Convert type of `shared_ptr`, via `reinterpret_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  reinterpret_pointer_cast(const shared_ptr<_Up>& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(__r, reinterpret_cast<typename _Sp::element_type*>(__r.get()));
  }

617#if __cplusplus201703L > 201703L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2996. Missing rvalue overloads for shared_ptr operations

/// Convert type of `shared_ptr` rvalue, via `static_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  static_pointer_cast(shared_ptr<_Up>&& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(std::move(__r),
 static_cast<typename _Sp::element_type*>(__r.get()));
  }

/// Convert type of `shared_ptr` rvalue, via `const_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  const_pointer_cast(shared_ptr<_Up>&& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(std::move(__r),
 const_cast<typename _Sp::element_type*>(__r.get()));
  }

/// Convert type of `shared_ptr` rvalue, via `dynamic_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  dynamic_pointer_cast(shared_ptr<_Up>&& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(std::move(__r), __p);
    return _Sp();
  }

/// Convert type of `shared_ptr` rvalue, via `reinterpret_cast`
template<typename _Tp, typename _Up>
  inline shared_ptr<_Tp>
  reinterpret_pointer_cast(shared_ptr<_Up>&& __r) noexcept
  {
    using _Sp = shared_ptr<_Tp>;
    return _Sp(std::move(__r),
 reinterpret_cast<typename _Sp::element_type*>(__r.get()));
  }
661#endif // C++20
662#endif // C++17

// @}

/**
 * @brief  A non-owning observer for a pointer owned by a shared_ptr
 *
 * A weak_ptr provides a safe alternative to a raw pointer when you want
 * a non-owning reference to an object that is managed by a shared_ptr.
 *
 * Unlike a raw pointer, a weak_ptr can be converted to a new shared_ptr
 * that shares ownership with every other shared_ptr that already owns
 * the pointer. In other words you can upgrade from a non-owning "weak"
 * reference to an owning shared_ptr, without having access to any of
 * the existing shared_ptr objects.
 *
 * Also unlike a raw pointer, a weak_ptr does not become "dangling" after
 * the object it points to has been destroyed. Instead, a weak_ptr
 * becomes _expired_ and can no longer be converted to a shared_ptr that
 * owns the freed pointer, so you cannot accidentally access the pointed-to
 * object after it has been destroyed.
 */
template<typename _Tp>
  class weak_ptr : public __weak_ptr<_Tp>
  {
    template<typename _Arg>
using _Constructible = typename enable_if<
 is_constructible<__weak_ptr<_Tp>, _Arg>::value
>::type;

    template<typename _Arg>
using _Assignable = typename enable_if<
 is_assignable<__weak_ptr<_Tp>&, _Arg>::value, weak_ptr&
>::type;

  public:
    constexpr weak_ptr() noexcept = default;

    template<typename _Yp,
      typename = _Constructible<const shared_ptr<_Yp>&>>
weak_ptr(const shared_ptr<_Yp>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

    weak_ptr(const weak_ptr&) noexcept = default;

    template<typename _Yp, typename = _Constructible<const weak_ptr<_Yp>&>>
weak_ptr(const weak_ptr<_Yp>& __r) noexcept
: __weak_ptr<_Tp>(__r) { }

    weak_ptr(weak_ptr&&) noexcept = default;

    template<typename _Yp, typename = _Constructible<weak_ptr<_Yp>>>
weak_ptr(weak_ptr<_Yp>&& __r) noexcept
: __weak_ptr<_Tp>(std::move(__r)) { }

    weak_ptr&
    operator=(const weak_ptr& __r) noexcept = default;

    template<typename _Yp>
_Assignable<const weak_ptr<_Yp>&>
operator=(const weak_ptr<_Yp>& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(__r);
 return *this;
}

    template<typename _Yp>
_Assignable<const shared_ptr<_Yp>&>
operator=(const shared_ptr<_Yp>& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(__r);
 return *this;
}

    weak_ptr&
    operator=(weak_ptr&& __r) noexcept = default;

    template<typename _Yp>
_Assignable<weak_ptr<_Yp>>
operator=(weak_ptr<_Yp>&& __r) noexcept
{
 this->__weak_ptr<_Tp>::operator=(std::move(__r));
 return *this;
}

    shared_ptr<_Tp>
    lock() const noexcept
    { return shared_ptr<_Tp>(*this, std::nothrow); }
  };

752#if __cpp_deduction_guides201703L >= 201606
template<typename _Tp>
  weak_ptr(shared_ptr<_Tp>) ->  weak_ptr<_Tp>;
755#endif

// 20.7.2.3.6 weak_ptr specialized algorithms.
/// Swap overload for weak_ptr
/// @relates weak_ptr
template<typename _Tp>
  inline void
  swap(weak_ptr<_Tp>& __a, weak_ptr<_Tp>& __b) noexcept
  { __a.swap(__b); }


/// Primary template owner_less
template<typename _Tp = void>
  struct owner_less;

/// Void specialization of owner_less compares either shared_ptr or weak_ptr
template<>
  struct owner_less<void> : _Sp_owner_less<void, void>
  { };

/// Partial specialization of owner_less for shared_ptr.
template<typename _Tp>
  struct owner_less<shared_ptr<_Tp>>
  : public _Sp_owner_less<shared_ptr<_Tp>, weak_ptr<_Tp>>
  { };

/// Partial specialization of owner_less for weak_ptr.
template<typename _Tp>
  struct owner_less<weak_ptr<_Tp>>
  : public _Sp_owner_less<weak_ptr<_Tp>, shared_ptr<_Tp>>
  { };

/**
 *  @brief Base class allowing use of member function shared_from_this.
 */
template<typename _Tp>
  class enable_shared_from_this
  {
  protected:
    constexpr enable_shared_from_this() noexcept { }

    enable_shared_from_this(const enable_shared_from_this&) noexcept { }

    enable_shared_from_this&
    operator=(const enable_shared_from_this&) noexcept
    { return *this; }

    ~enable_shared_from_this() { }

  public:
    shared_ptr<_Tp>
    shared_from_this()
    { return shared_ptr<_Tp>(this->_M_weak_this); }

    shared_ptr<const _Tp>
    shared_from_this() const
    { return shared_ptr<const _Tp>(this->_M_weak_this); }

813#if __cplusplus201703L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
814#define __cpp_lib_enable_shared_from_this201603 201603
    weak_ptr<_Tp>
    weak_from_this() noexcept
    { return this->_M_weak_this; }

    weak_ptr<const _Tp>
    weak_from_this() const noexcept
    { return this->_M_weak_this; }
822#endif

  private:
    template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

    // Found by ADL when this is an associated class.
    friend const enable_shared_from_this*
    __enable_shared_from_this_base(const __shared_count<>&,
		     const enable_shared_from_this* __p)
    { return __p; }

    template<typename, _Lock_policy>
friend class __shared_ptr;

    mutable weak_ptr<_Tp>  _M_weak_this;
  };

/// @relates shared_ptr @{

/**
 *  @brief  Create an object that is owned by a shared_ptr.
 *  @param  __a     An allocator.
 *  @param  __args  Arguments for the @a _Tp object's constructor.
 *  @return A shared_ptr that owns the newly created object.
 *  @throw  An exception thrown from @a _Alloc::allocate or from the
 *          constructor of @a _Tp.
 *
 *  A copy of @a __a will be used to allocate memory for the shared_ptr
 *  and the new object.
 */
template<typename _Tp, typename _Alloc, typename... _Args>
  inline shared_ptr<_Tp>
  allocate_shared(const _Alloc& __a, _Args&&... __args)
  {
    return shared_ptr<_Tp>(_Sp_alloc_shared_tag<_Alloc>{__a},
7
←
Calling constructor for 'shared_ptr<(anonymous namespace)::SimpleTextGenerator>'→
21
←
Returning from constructor for 'shared_ptr<(anonymous namespace)::SimpleTextGenerator>'→
	     std::forward<_Args>(__args)...);
  }

/**
 *  @brief  Create an object that is owned by a shared_ptr.
 *  @param  __args  Arguments for the @a _Tp object's constructor.
 *  @return A shared_ptr that owns the newly created object.
 *  @throw  std::bad_alloc, or an exception thrown from the
 *          constructor of @a _Tp.
 */
template<typename _Tp, typename... _Args>
  inline shared_ptr<_Tp>
  make_shared(_Args&&... __args)
  {
    typedef typename std::remove_cv<_Tp>::type _Tp_nc;
    return std::allocate_shared<_Tp>(std::allocator<_Tp_nc>(),
6
←
Calling 'allocate_shared<(anonymous namespace)::SimpleTextGenerator, std::allocator<(anonymous namespace)::SimpleTextGenerator>, std::basic_string<char>>'→
22
←
Returned allocated memory→
		       std::forward<_Args>(__args)...);
  }

/// std::hash specialization for shared_ptr.
template<typename _Tp>
  struct hash<shared_ptr<_Tp>>
  : public __hash_base<size_t, shared_ptr<_Tp>>
  {
    size_t
    operator()(const shared_ptr<_Tp>& __s) const noexcept
    {
return std::hash<typename shared_ptr<_Tp>::element_type*>()(__s.get());
    }
  };

// @} relates shared_ptr
// @} group pointer_abstractions

894#if __cplusplus201703L >= 201703L
namespace __detail::__variant
{
  template<typename> struct _Never_valueless_alt; // see <variant>

  // Provide the strong exception-safety guarantee when emplacing a
  // shared_ptr into a variant.
  template<typename _Tp>
    struct _Never_valueless_alt<std::shared_ptr<_Tp>>
    : std::true_type
    { };

  // Provide the strong exception-safety guarantee when emplacing a
  // weak_ptr into a variant.
  template<typename _Tp>
    struct _Never_valueless_alt<std::weak_ptr<_Tp>>
    : std::true_type
    { };
}  // namespace __detail::__variant
913#endif // C++17

915_GLIBCXX_END_NAMESPACE_VERSION
916} // namespace

918#endif // _SHARED_PTR_H

←

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

→

1// shared_ptr and weak_ptr implementation details -*- C++ -*-

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

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

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

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

25// GCC Note: Based on files from version 1.32.0 of the Boost library.

27//  shared_count.hpp
28//  Copyright (c) 2001, 2002, 2003 Peter Dimov and Multi Media Ltd.

30//  shared_ptr.hpp
31//  Copyright (C) 1998, 1999 Greg Colvin and Beman Dawes.
32//  Copyright (C) 2001, 2002, 2003 Peter Dimov

34//  weak_ptr.hpp
35//  Copyright (C) 2001, 2002, 2003 Peter Dimov

37//  enable_shared_from_this.hpp
38//  Copyright (C) 2002 Peter Dimov

40// Distributed under the Boost Software License, Version 1.0. (See
41// accompanying file LICENSE_1_0.txt or copy at
42// http://www.boost.org/LICENSE_1_0.txt)

44/** @file bits/shared_ptr_base.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

49#ifndef _SHARED_PTR_BASE_H1
50#define _SHARED_PTR_BASE_H1 1

52#include <typeinfo>
53#include <bits/allocated_ptr.h>
54#include <bits/refwrap.h>
55#include <bits/stl_function.h>
56#include <ext/aligned_buffer.h>
57#if __cplusplus201703L > 201703L
58# include <compare>
59#endif

61namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
62{
63_GLIBCXX_BEGIN_NAMESPACE_VERSION

65#if _GLIBCXX_USE_DEPRECATED1
66#pragma GCC diagnostic push
67#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template<typename> class auto_ptr;
69#pragma GCC diagnostic pop
70#endif

/**
 *  @brief  Exception possibly thrown by @c shared_ptr.
 *  @ingroup exceptions
 */
class bad_weak_ptr : public std::exception
{
public:
  virtual char const* what() const noexcept;

  virtual ~bad_weak_ptr() noexcept;
};

// Substitute for bad_weak_ptr object in the case of -fno-exceptions.
inline void
__throw_bad_weak_ptr()
{ _GLIBCXX_THROW_OR_ABORT(bad_weak_ptr())(__builtin_abort()); }

using __gnu_cxx::_Lock_policy;
using __gnu_cxx::__default_lock_policy;
using __gnu_cxx::_S_single;
using __gnu_cxx::_S_mutex;
using __gnu_cxx::_S_atomic;

// Empty helper class except when the template argument is _S_mutex.
template<_Lock_policy _Lp>
  class _Mutex_base
  {
  protected:
    // The atomic policy uses fully-fenced builtins, single doesn't care.
    enum { _S_need_barriers = 0 };
  };

template<>
  class _Mutex_base<_S_mutex>
  : public __gnu_cxx::__mutex
  {
  protected:
    // This policy is used when atomic builtins are not available.
    // The replacement atomic operations might not have the necessary
    // memory barriers.
    enum { _S_need_barriers = 1 };
  };

template<_Lock_policy _Lp = __default_lock_policy>
  class _Sp_counted_base
  : public _Mutex_base<_Lp>
  {
  public:
    _Sp_counted_base() noexcept
    : _M_use_count(1), _M_weak_count(1) { }

    virtual
    ~_Sp_counted_base() noexcept
    { }

    // Called when _M_use_count drops to zero, to release the resources
    // managed by *this.
    virtual void
    _M_dispose() noexcept = 0;

    // Called when _M_weak_count drops to zero.
    virtual void
    _M_destroy() noexcept
    { delete this; }

    virtual void*
    _M_get_deleter(const std::type_info&) noexcept = 0;

    void
    _M_add_ref_copy()
    { __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

    void
    _M_add_ref_lock();

    bool
    _M_add_ref_lock_nothrow();

    void
    _M_release() noexcept
    {
      // Be race-detector-friendly.  For more info see bits/c++config.
      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
 {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
   _M_dispose();
   // There must be a memory barrier between dispose() and destroy()
   // to ensure that the effects of dispose() are observed in the
   // thread that runs destroy().
   // See http://gcc.gnu.org/ml/libstdc++/2005-11/msg00136.html
   if (_Mutex_base<_Lp>::_S_need_barriers)
     {
__atomic_thread_fence (__ATOMIC_ACQ_REL4);
     }

          // Be race-detector-friendly.  For more info see bits/c++config.
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
   if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count,
				       -1) == 1)
            {
              _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
       _M_destroy();
            }
 }
    }

    void
    _M_weak_add_ref() noexcept
    { __gnu_cxx::__atomic_add_dispatch(&_M_weak_count, 1); }

    void
    _M_weak_release() noexcept
    {
      // Be race-detector-friendly. For more info see bits/c++config.
      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_weak_count);
if (__gnu_cxx::__exchange_and_add_dispatch(&_M_weak_count, -1) == 1)
 {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_weak_count);
   if (_Mutex_base<_Lp>::_S_need_barriers)
     {
       // See _M_release(),
       // destroy() must observe results of dispose()
__atomic_thread_fence (__ATOMIC_ACQ_REL4);
     }
   _M_destroy();
 }
    }

    long
    _M_get_use_count() const noexcept
    {
      // No memory barrier is used here so there is no synchronization
      // with other threads.
      return __atomic_load_n(&_M_use_count, __ATOMIC_RELAXED0);
    }

  private:
    _Sp_counted_base(_Sp_counted_base const&) = delete;
    _Sp_counted_base& operator=(_Sp_counted_base const&) = delete;

    _Atomic_word  _M_use_count;     // #shared
    _Atomic_word  _M_weak_count;    // #weak + (#shared != 0)
  };

template<>
  inline void
  _Sp_counted_base<_S_single>::
  _M_add_ref_lock()
  {
    if (_M_use_count == 0)
__throw_bad_weak_ptr();
    ++_M_use_count;
  }

template<>
  inline void
  _Sp_counted_base<_S_mutex>::
  _M_add_ref_lock()
  {
    __gnu_cxx::__scoped_lock sentry(*this);
    if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, 1) == 0)
{
 _M_use_count = 0;
 __throw_bad_weak_ptr();
}
  }

template<>
  inline void
  _Sp_counted_base<_S_atomic>::
  _M_add_ref_lock()
  {
    // Perform lock-free add-if-not-zero operation.
    _Atomic_word __count = _M_get_use_count();
    do
{
 if (__count == 0)
   __throw_bad_weak_ptr();
 // Replace the current counter value with the old value + 1, as
 // long as it's not changed meanwhile.
}
    while (!__atomic_compare_exchange_n(&_M_use_count, &__count, __count + 1,
			  true, __ATOMIC_ACQ_REL4,
			  __ATOMIC_RELAXED0));
  }

template<>
  inline bool
  _Sp_counted_base<_S_single>::
  _M_add_ref_lock_nothrow()
  {
    if (_M_use_count == 0)
return false;
    ++_M_use_count;
    return true;
  }

template<>
  inline bool
  _Sp_counted_base<_S_mutex>::
  _M_add_ref_lock_nothrow()
  {
    __gnu_cxx::__scoped_lock sentry(*this);
    if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, 1) == 0)
{
 _M_use_count = 0;
 return false;
}
    return true;
  }

template<>
  inline bool
  _Sp_counted_base<_S_atomic>::
  _M_add_ref_lock_nothrow()
  {
    // Perform lock-free add-if-not-zero operation.
    _Atomic_word __count = _M_get_use_count();
    do
{
 if (__count == 0)
   return false;
 // Replace the current counter value with the old value + 1, as
 // long as it's not changed meanwhile.
}
    while (!__atomic_compare_exchange_n(&_M_use_count, &__count, __count + 1,
			  true, __ATOMIC_ACQ_REL4,
			  __ATOMIC_RELAXED0));
    return true;
  }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_add_ref_copy()
  { ++_M_use_count; }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_release() noexcept
  {
    if (--_M_use_count == 0)
      {
        _M_dispose();
        if (--_M_weak_count == 0)
          _M_destroy();
      }
  }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_weak_add_ref() noexcept
  { ++_M_weak_count; }

template<>
  inline void
  _Sp_counted_base<_S_single>::_M_weak_release() noexcept
  {
    if (--_M_weak_count == 0)
      _M_destroy();
  }

template<>
  inline long
  _Sp_counted_base<_S_single>::_M_get_use_count() const noexcept
  { return _M_use_count; }


// Forward declarations.
template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __shared_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __weak_ptr;

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy>
  class __enable_shared_from_this;

template<typename _Tp>
  class shared_ptr;

template<typename _Tp>
  class weak_ptr;

template<typename _Tp>
  struct owner_less;

template<typename _Tp>
  class enable_shared_from_this;

template<_Lock_policy _Lp = __default_lock_policy>
  class __weak_count;

template<_Lock_policy _Lp = __default_lock_policy>
  class __shared_count;


// Counted ptr with no deleter or allocator support
template<typename _Ptr, _Lock_policy _Lp>
  class _Sp_counted_ptr final : public _Sp_counted_base<_Lp>
  {
  public:
    explicit
    _Sp_counted_ptr(_Ptr __p) noexcept
    : _M_ptr(__p) { }

    virtual void
    _M_dispose() noexcept
    { delete _M_ptr; }

    virtual void
    _M_destroy() noexcept
    { delete this; }

    virtual void*
    _M_get_deleter(const std::type_info&) noexcept
    { return nullptr; }

    _Sp_counted_ptr(const _Sp_counted_ptr&) = delete;
    _Sp_counted_ptr& operator=(const _Sp_counted_ptr&) = delete;

  private:
    _Ptr             _M_ptr;
  };

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_single>::_M_dispose() noexcept { }

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_mutex>::_M_dispose() noexcept { }

template<>
  inline void
  _Sp_counted_ptr<nullptr_t, _S_atomic>::_M_dispose() noexcept { }

template<int _Nm, typename _Tp,
  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
  struct _Sp_ebo_helper;

/// Specialization using EBO.
template<int _Nm, typename _Tp>
  struct _Sp_ebo_helper<_Nm, _Tp, true> : private _Tp
  {
    explicit _Sp_ebo_helper(const _Tp& __tp) : _Tp(__tp) { }
    explicit _Sp_ebo_helper(_Tp&& __tp) : _Tp(std::move(__tp)) { }

    static _Tp&
    _S_get(_Sp_ebo_helper& __eboh) { return static_cast<_Tp&>(__eboh); }
  };

/// Specialization not using EBO.
template<int _Nm, typename _Tp>
  struct _Sp_ebo_helper<_Nm, _Tp, false>
  {
    explicit _Sp_ebo_helper(const _Tp& __tp) : _M_tp(__tp) { }
    explicit _Sp_ebo_helper(_Tp&& __tp) : _M_tp(std::move(__tp)) { }

    static _Tp&
    _S_get(_Sp_ebo_helper& __eboh)
    { return __eboh._M_tp; }

  private:
    _Tp _M_tp;
  };

// Support for custom deleter and/or allocator
template<typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp>
  class _Sp_counted_deleter final : public _Sp_counted_base<_Lp>
  {
    class _Impl : _Sp_ebo_helper<0, _Deleter>, _Sp_ebo_helper<1, _Alloc>
    {
typedef _Sp_ebo_helper<0, _Deleter>	_Del_base;
typedef _Sp_ebo_helper<1, _Alloc>	_Alloc_base;

    public:
_Impl(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
: _M_ptr(__p), _Del_base(std::move(__d)), _Alloc_base(__a)
{ }

_Deleter& _M_del() noexcept { return _Del_base::_S_get(*this); }
_Alloc& _M_alloc() noexcept { return _Alloc_base::_S_get(*this); }

_Ptr _M_ptr;
    };

  public:
    using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_deleter>;

    // __d(__p) must not throw.
    _Sp_counted_deleter(_Ptr __p, _Deleter __d) noexcept
    : _M_impl(__p, std::move(__d), _Alloc()) { }

    // __d(__p) must not throw.
    _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a) noexcept
    : _M_impl(__p, std::move(__d), __a) { }

    ~_Sp_counted_deleter() noexcept { }

    virtual void
    _M_dispose() noexcept
    { _M_impl._M_del()(_M_impl._M_ptr); }

    virtual void
    _M_destroy() noexcept
    {
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_deleter();
    }

    virtual void*
    _M_get_deleter(const std::type_info& __ti) noexcept
    {
487#if __cpp_rtti199711L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2400. shared_ptr's get_deleter() should use addressof()
      return __ti == typeid(_Deleter)
 ? std::__addressof(_M_impl._M_del())
 : nullptr;
493#else
      return nullptr;
495#endif
    }

  private:
    _Impl _M_impl;
  };

// helpers for make_shared / allocate_shared

struct _Sp_make_shared_tag
{
private:
  template<typename _Tp, typename _Alloc, _Lock_policy _Lp>
    friend class _Sp_counted_ptr_inplace;

  static const type_info&
  _S_ti() noexcept _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
  {
    alignas(type_info) static constexpr char __tag[sizeof(type_info)] = { };
    return reinterpret_cast<const type_info&>(__tag);
  }

  static bool _S_eq(const type_info&) noexcept;
};

template<typename _Alloc>
  struct _Sp_alloc_shared_tag
  {
    const _Alloc& _M_a;
  };

template<typename _Tp, typename _Alloc, _Lock_policy _Lp>
  class _Sp_counted_ptr_inplace final : public _Sp_counted_base<_Lp>
  {
    class _Impl : _Sp_ebo_helper<0, _Alloc>
    {
typedef _Sp_ebo_helper<0, _Alloc>	_A_base;

    public:
explicit _Impl(_Alloc __a) noexcept : _A_base(__a) { }

_Alloc& _M_alloc() noexcept { return _A_base::_S_get(*this); }

__gnu_cxx::__aligned_buffer<_Tp> _M_storage;
    };

  public:
    using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_ptr_inplace>;

    // Alloc parameter is not a reference so doesn't alias anything in __args
    template<typename... _Args>
_Sp_counted_ptr_inplace(_Alloc __a, _Args&&... __args)
: _M_impl(__a)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2070.  allocate_shared should use allocator_traits<A>::construct
 allocator_traits<_Alloc>::construct(__a, _M_ptr(),
     std::forward<_Args>(__args)...); // might throw
}

    ~_Sp_counted_ptr_inplace() noexcept { }

    virtual void
    _M_dispose() noexcept
    {
allocator_traits<_Alloc>::destroy(_M_impl._M_alloc(), _M_ptr());
    }

    // Override because the allocator needs to know the dynamic type
    virtual void
    _M_destroy() noexcept
    {
__allocator_type __a(_M_impl._M_alloc());
__allocated_ptr<__allocator_type> __guard_ptr{ __a, this };
this->~_Sp_counted_ptr_inplace();
    }

  private:
    friend class __shared_count<_Lp>; // To be able to call _M_ptr().

    // No longer used, but code compiled against old libstdc++ headers
    // might still call it from __shared_ptr ctor to get the pointer out.
    virtual void*
    _M_get_deleter(const std::type_info& __ti) noexcept override
    {
auto __ptr = const_cast<typename remove_cv<_Tp>::type*>(_M_ptr());
// Check for the fake type_info first, so we don't try to access it
// as a real type_info object. Otherwise, check if it's the real
// type_info for this class. With RTTI enabled we can check directly,
// or call a library function to do it.
if (&__ti == &_Sp_make_shared_tag::_S_ti()
   ||
587#if __cpp_rtti199711L
   __ti == typeid(_Sp_make_shared_tag)
589#else
   _Sp_make_shared_tag::_S_eq(__ti)
591#endif
  )
 return __ptr;
return nullptr;
    }

    _Tp* _M_ptr() noexcept { return _M_impl._M_storage._M_ptr(); }

    _Impl _M_impl;
  };

// The default deleter for shared_ptr<T[]> and shared_ptr<T[N]>.
struct __sp_array_delete
{
  template<typename _Yp>
    void operator()(_Yp* __p) const { delete[] __p; }
};

template<_Lock_policy _Lp>
  class __shared_count
  {
    template<typename _Tp>
struct __not_alloc_shared_tag { using type = void; };

    template<typename _Tp>
struct __not_alloc_shared_tag<_Sp_alloc_shared_tag<_Tp>> { };

  public:
    constexpr __shared_count() noexcept : _M_pi(0)
    { }

    template<typename _Ptr>
      explicit
__shared_count(_Ptr __p) : _M_pi(0)
{
 __tryif (true)
   {
     _M_pi = new _Sp_counted_ptr<_Ptr, _Lp>(__p);
   }
 __catch(...)if (false)
   {
     delete __p;
     __throw_exception_again;
   }
}

    template<typename _Ptr>
__shared_count(_Ptr __p, /* is_array = */ false_type)
: __shared_count(__p)
{ }

    template<typename _Ptr>
__shared_count(_Ptr __p, /* is_array = */ true_type)
: __shared_count(__p, __sp_array_delete{}, allocator<void>())
{ }

    template<typename _Ptr, typename _Deleter,
      typename = typename __not_alloc_shared_tag<_Deleter>::type>
__shared_count(_Ptr __p, _Deleter __d)
: __shared_count(__p, std::move(__d), allocator<void>())
{ }

    template<typename _Ptr, typename _Deleter, typename _Alloc,
      typename = typename __not_alloc_shared_tag<_Deleter>::type>
__shared_count(_Ptr __p, _Deleter __d, _Alloc __a) : _M_pi(0)
{
 typedef _Sp_counted_deleter<_Ptr, _Deleter, _Alloc, _Lp> _Sp_cd_type;
 __tryif (true)
   {
     typename _Sp_cd_type::__allocator_type __a2(__a);
     auto __guard = std::__allocate_guarded(__a2);
     _Sp_cd_type* __mem = __guard.get();
     ::new (__mem) _Sp_cd_type(__p, std::move(__d), std::move(__a));
     _M_pi = __mem;
     __guard = nullptr;
   }
 __catch(...)if (false)
   {
     __d(__p); // Call _Deleter on __p.
     __throw_exception_again;
   }
}

    template<typename _Tp, typename _Alloc, typename... _Args>
__shared_count(_Tp*& __p, _Sp_alloc_shared_tag<_Alloc> __a,
       _Args&&... __args)
{
 typedef _Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp> _Sp_cp_type;
 typename _Sp_cp_type::__allocator_type __a2(__a._M_a);
 auto __guard = std::__allocate_guarded(__a2);
10
←
Calling '__allocate_guarded<std::allocator<std::_Sp_counted_ptr_inplace<(anonymous namespace)::SimpleTextGenerator, std::allocator<(anonymous namespace)::SimpleTextGenerator>, __gnu_cxx::_S_atomic>>>'→
18
←
Returned allocated memory→
 _Sp_cp_type* __mem = __guard.get();
 auto __pi = ::new (__mem)
   _Sp_cp_type(__a._M_a, std::forward<_Args>(__args)...);
 __guard = nullptr;
 _M_pi = __pi;
 __p = __pi->_M_ptr();
}

689#if _GLIBCXX_USE_DEPRECATED1
690#pragma GCC diagnostic push
691#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
    // Special case for auto_ptr<_Tp> to provide the strong guarantee.
    template<typename _Tp>
      explicit
__shared_count(std::auto_ptr<_Tp>&& __r);
696#pragma GCC diagnostic pop
697#endif

    // Special case for unique_ptr<_Tp,_Del> to provide the strong guarantee.
    template<typename _Tp, typename _Del>
      explicit
__shared_count(std::unique_ptr<_Tp, _Del>&& __r) : _M_pi(0)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2415. Inconsistency between unique_ptr and shared_ptr
 if (__r.get() == nullptr)
   return;

 using _Ptr = typename unique_ptr<_Tp, _Del>::pointer;
 using _Del2 = typename conditional<is_reference<_Del>::value,
     reference_wrapper<typename remove_reference<_Del>::type>,
     _Del>::type;
 using _Sp_cd_type
   = _Sp_counted_deleter<_Ptr, _Del2, allocator<void>, _Lp>;
 using _Alloc = allocator<_Sp_cd_type>;
 using _Alloc_traits = allocator_traits<_Alloc>;
 _Alloc __a;
 _Sp_cd_type* __mem = _Alloc_traits::allocate(__a, 1);
 _Alloc_traits::construct(__a, __mem, __r.release(),
		   __r.get_deleter());  // non-throwing
 _M_pi = __mem;
}

    // Throw bad_weak_ptr when __r._M_get_use_count() == 0.
    explicit __shared_count(const __weak_count<_Lp>& __r);

    // Does not throw if __r._M_get_use_count() == 0, caller must check.
    explicit __shared_count(const __weak_count<_Lp>& __r, std::nothrow_t);

    ~__shared_count() noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_release();
    }

    __shared_count(const __shared_count& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != 0)
 _M_pi->_M_add_ref_copy();
    }

    __shared_count&
    operator=(const __shared_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != _M_pi)
 {
   if (__tmp != 0)
     __tmp->_M_add_ref_copy();
   if (_M_pi != 0)
     _M_pi->_M_release();
   _M_pi = __tmp;
 }
return *this;
    }

    void
    _M_swap(__shared_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
    }

    long
    _M_get_use_count() const noexcept
    { return _M_pi != 0 ? _M_pi->_M_get_use_count() : 0; }

    bool
    _M_unique() const noexcept
    { return this->_M_get_use_count() == 1; }

    void*
    _M_get_deleter(const std::type_info& __ti) const noexcept
    { return _M_pi ? _M_pi->_M_get_deleter(__ti) : nullptr; }

    bool
    _M_less(const __shared_count& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    bool
    _M_less(const __weak_count<_Lp>& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    // Friend function injected into enclosing namespace and found by ADL
    friend inline bool
    operator==(const __shared_count& __a, const __shared_count& __b) noexcept
    { return __a._M_pi == __b._M_pi; }

  private:
    friend class __weak_count<_Lp>;

    _Sp_counted_base<_Lp>*  _M_pi;
  };


template<_Lock_policy _Lp>
  class __weak_count
  {
  public:
    constexpr __weak_count() noexcept : _M_pi(nullptr)
    { }

    __weak_count(const __shared_count<_Lp>& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_add_ref();
    }

    __weak_count(const __weak_count& __r) noexcept
    : _M_pi(__r._M_pi)
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_add_ref();
    }

    __weak_count(__weak_count&& __r) noexcept
    : _M_pi(__r._M_pi)
    { __r._M_pi = nullptr; }

    ~__weak_count() noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
    }

    __weak_count&
    operator=(const __shared_count<_Lp>& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
 __tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
    }

    __weak_count&
    operator=(const __weak_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
if (__tmp != nullptr)
 __tmp->_M_weak_add_ref();
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __tmp;
return *this;
    }

    __weak_count&
    operator=(__weak_count&& __r) noexcept
    {
if (_M_pi != nullptr)
 _M_pi->_M_weak_release();
_M_pi = __r._M_pi;
      __r._M_pi = nullptr;
return *this;
    }

    void
    _M_swap(__weak_count& __r) noexcept
    {
_Sp_counted_base<_Lp>* __tmp = __r._M_pi;
__r._M_pi = _M_pi;
_M_pi = __tmp;
    }

    long
    _M_get_use_count() const noexcept
    { return _M_pi != nullptr ? _M_pi->_M_get_use_count() : 0; }

    bool
    _M_less(const __weak_count& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    bool
    _M_less(const __shared_count<_Lp>& __rhs) const noexcept
    { return std::less<_Sp_counted_base<_Lp>*>()(this->_M_pi, __rhs._M_pi); }

    // Friend function injected into enclosing namespace and found by ADL
    friend inline bool
    operator==(const __weak_count& __a, const __weak_count& __b) noexcept
    { return __a._M_pi == __b._M_pi; }

  private:
    friend class __shared_count<_Lp>;

    _Sp_counted_base<_Lp>*  _M_pi;
  };

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
  inline
  __shared_count<_Lp>::__shared_count(const __weak_count<_Lp>& __r)
  : _M_pi(__r._M_pi)
  {
    if (_M_pi != nullptr)
_M_pi->_M_add_ref_lock();
    else
__throw_bad_weak_ptr();
  }

// Now that __weak_count is defined we can define this constructor:
template<_Lock_policy _Lp>
  inline
  __shared_count<_Lp>::
  __shared_count(const __weak_count<_Lp>& __r, std::nothrow_t)
  : _M_pi(__r._M_pi)
  {
    if (_M_pi != nullptr)
if (!_M_pi->_M_add_ref_lock_nothrow())
 _M_pi = nullptr;
  }

918#define __cpp_lib_shared_ptr_arrays201611L 201611L

// Helper traits for shared_ptr of array:

// A pointer type Y* is said to be compatible with a pointer type T* when
// either Y* is convertible to T* or Y is U[N] and T is U cv [].
template<typename _Yp_ptr, typename _Tp_ptr>
  struct __sp_compatible_with
  : false_type
  { };

template<typename _Yp, typename _Tp>
  struct __sp_compatible_with<_Yp*, _Tp*>
  : is_convertible<_Yp*, _Tp*>::type
  { };

template<typename _Up, size_t _Nm>
  struct __sp_compatible_with<_Up(*)[_Nm], _Up(*)[]>
  : true_type
  { };

template<typename _Up, size_t _Nm>
  struct __sp_compatible_with<_Up(*)[_Nm], const _Up(*)[]>
  : true_type
  { };

template<typename _Up, size_t _Nm>
  struct __sp_compatible_with<_Up(*)[_Nm], volatile _Up(*)[]>
  : true_type
  { };

template<typename _Up, size_t _Nm>
  struct __sp_compatible_with<_Up(*)[_Nm], const volatile _Up(*)[]>
  : true_type
  { };

// Test conversion from Y(*)[N] to U(*)[N] without forming invalid type Y[N].
template<typename _Up, size_t _Nm, typename _Yp, typename = void>
  struct __sp_is_constructible_arrN
  : false_type
  { };

template<typename _Up, size_t _Nm, typename _Yp>
  struct __sp_is_constructible_arrN<_Up, _Nm, _Yp, __void_t<_Yp[_Nm]>>
  : is_convertible<_Yp(*)[_Nm], _Up(*)[_Nm]>::type
  { };

// Test conversion from Y(*)[] to U(*)[] without forming invalid type Y[].
template<typename _Up, typename _Yp, typename = void>
  struct __sp_is_constructible_arr
  : false_type
  { };

template<typename _Up, typename _Yp>
  struct __sp_is_constructible_arr<_Up, _Yp, __void_t<_Yp[]>>
  : is_convertible<_Yp(*)[], _Up(*)[]>::type
  { };

// Trait to check if shared_ptr<T> can be constructed from Y*.
template<typename _Tp, typename _Yp>
  struct __sp_is_constructible;

// When T is U[N], Y(*)[N] shall be convertible to T*;
template<typename _Up, size_t _Nm, typename _Yp>
  struct __sp_is_constructible<_Up[_Nm], _Yp>
  : __sp_is_constructible_arrN<_Up, _Nm, _Yp>::type
  { };

// when T is U[], Y(*)[] shall be convertible to T*;
template<typename _Up, typename _Yp>
  struct __sp_is_constructible<_Up[], _Yp>
  : __sp_is_constructible_arr<_Up, _Yp>::type
  { };

// otherwise, Y* shall be convertible to T*.
template<typename _Tp, typename _Yp>
  struct __sp_is_constructible
  : is_convertible<_Yp*, _Tp*>::type
  { };


// Define operator* and operator-> for shared_ptr<T>.
template<typename _Tp, _Lock_policy _Lp,
  bool = is_array<_Tp>::value, bool = is_void<_Tp>::value>
  class __shared_ptr_access
  {
  public:
    using element_type = _Tp;

    element_type&
    operator*() const noexcept
    {
__glibcxx_assert(_M_get() != nullptr)do { if (! (_M_get() != nullptr)) std::__replacement_assert("/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/shared_ptr_base.h"
, 1010, __PRETTY_FUNCTION__, "_M_get() != nullptr"); } while (
false);
return *_M_get();
    }

    element_type*
    operator->() const noexcept
    {
_GLIBCXX_DEBUG_PEDASSERT(_M_get() != nullptr);
return _M_get();
    }

  private:
    element_type*
    _M_get() const noexcept
    { return static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get(); }
  };

// Define operator-> for shared_ptr<cv void>.
template<typename _Tp, _Lock_policy _Lp>
  class __shared_ptr_access<_Tp, _Lp, false, true>
  {
  public:
    using element_type = _Tp;

    element_type*
    operator->() const noexcept
    {
auto __ptr = static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get();
_GLIBCXX_DEBUG_PEDASSERT(__ptr != nullptr);
return __ptr;
    }
  };

// Define operator[] for shared_ptr<T[]> and shared_ptr<T[N]>.
template<typename _Tp, _Lock_policy _Lp>
  class __shared_ptr_access<_Tp, _Lp, true, false>
  {
  public:
    using element_type = typename remove_extent<_Tp>::type;

1050#if __cplusplus201703L <= 201402L
    [[__deprecated__("shared_ptr<T[]>::operator* is absent from C++17")]]
    element_type&
    operator*() const noexcept
    {
__glibcxx_assert(_M_get() != nullptr)do { if (! (_M_get() != nullptr)) std::__replacement_assert("/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/shared_ptr_base.h"
, 1055, __PRETTY_FUNCTION__, "_M_get() != nullptr"); } while (
false);
return *_M_get();
    }

    [[__deprecated__("shared_ptr<T[]>::operator-> is absent from C++17")]]
    element_type*
    operator->() const noexcept
    {
_GLIBCXX_DEBUG_PEDASSERT(_M_get() != nullptr);
return _M_get();
    }
1066#endif

    element_type&
    operator[](ptrdiff_t __i) const
    {
__glibcxx_assert(_M_get() != nullptr)do { if (! (_M_get() != nullptr)) std::__replacement_assert("/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/shared_ptr_base.h"
, 1071, __PRETTY_FUNCTION__, "_M_get() != nullptr"); } while (
false);
__glibcxx_assert(!extent<_Tp>::value || __i < extent<_Tp>::value)do { if (! (!extent<_Tp>::value || __i < extent<_Tp
>::value)) std::__replacement_assert("/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/shared_ptr_base.h"
, 1072, __PRETTY_FUNCTION__, "!extent<_Tp>::value || __i < extent<_Tp>::value"
); } while (false);
return _M_get()[__i];
    }

  private:
    element_type*
    _M_get() const noexcept
    { return static_cast<const __shared_ptr<_Tp, _Lp>*>(this)->get(); }
  };

template<typename _Tp, _Lock_policy _Lp>
  class __shared_ptr
  : public __shared_ptr_access<_Tp, _Lp>
  {
  public:
    using element_type = typename remove_extent<_Tp>::type;

  private:
    // Constraint for taking ownership of a pointer of type _Yp*:
    template<typename _Yp>
using _SafeConv
 = typename enable_if<__sp_is_constructible<_Tp, _Yp>::value>::type;

    // Constraint for construction from shared_ptr and weak_ptr:
    template<typename _Yp, typename _Res = void>
using _Compatible = typename
 enable_if<__sp_compatible_with<_Yp*, _Tp*>::value, _Res>::type;

    // Constraint for assignment from shared_ptr and weak_ptr:
    template<typename _Yp>
using _Assignable = _Compatible<_Yp, __shared_ptr&>;

    // Constraint for construction from unique_ptr:
    template<typename _Yp, typename _Del, typename _Res = void,
      typename _Ptr = typename unique_ptr<_Yp, _Del>::pointer>
using _UniqCompatible = typename enable_if<__and_<
 __sp_compatible_with<_Yp*, _Tp*>, is_convertible<_Ptr, element_type*>
 >::value, _Res>::type;

    // Constraint for assignment from unique_ptr:
    template<typename _Yp, typename _Del>
using _UniqAssignable = _UniqCompatible<_Yp, _Del, __shared_ptr&>;

  public:

1117#if __cplusplus201703L > 201402L
    using weak_type = __weak_ptr<_Tp, _Lp>;
1119#endif

    constexpr __shared_ptr() noexcept
    : _M_ptr(0), _M_refcount()
    { }

    template<typename _Yp, typename = _SafeConv<_Yp>>
explicit
__shared_ptr(_Yp* __p)
: _M_ptr(__p), _M_refcount(__p, typename is_array<_Tp>::type())
{
 static_assert( !is_void<_Yp>::value, "incomplete type" );
 static_assert( sizeof(_Yp) > 0, "incomplete type" );
 _M_enable_shared_from_this_with(__p);
}

    template<typename _Yp, typename _Deleter, typename = _SafeConv<_Yp>>
__shared_ptr(_Yp* __p, _Deleter __d)
: _M_ptr(__p), _M_refcount(__p, std::move(__d))
{
 static_assert(__is_invocable<_Deleter&, _Yp*&>::value,
     "deleter expression d(p) is well-formed");
 _M_enable_shared_from_this_with(__p);
}

    template<typename _Yp, typename _Deleter, typename _Alloc,
      typename = _SafeConv<_Yp>>
__shared_ptr(_Yp* __p, _Deleter __d, _Alloc __a)
: _M_ptr(__p), _M_refcount(__p, std::move(__d), std::move(__a))
{
 static_assert(__is_invocable<_Deleter&, _Yp*&>::value,
     "deleter expression d(p) is well-formed");
 _M_enable_shared_from_this_with(__p);
}

    template<typename _Deleter>
__shared_ptr(nullptr_t __p, _Deleter __d)
: _M_ptr(0), _M_refcount(__p, std::move(__d))
{ }

    template<typename _Deleter, typename _Alloc>
      __shared_ptr(nullptr_t __p, _Deleter __d, _Alloc __a)
: _M_ptr(0), _M_refcount(__p, std::move(__d), std::move(__a))
{ }

    // Aliasing constructor
    template<typename _Yp>
__shared_ptr(const __shared_ptr<_Yp, _Lp>& __r,
     element_type* __p) noexcept
: _M_ptr(__p), _M_refcount(__r._M_refcount) // never throws
{ }

    // Aliasing constructor
    template<typename _Yp>
__shared_ptr(__shared_ptr<_Yp, _Lp>&& __r,
     element_type* __p) noexcept
: _M_ptr(__p), _M_refcount()
{
 _M_refcount._M_swap(__r._M_refcount);
 __r._M_ptr = 0;
}

    __shared_ptr(const __shared_ptr&) noexcept = default;
    __shared_ptr& operator=(const __shared_ptr&) noexcept = default;
    ~__shared_ptr() = default;

    template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(const __shared_ptr<_Yp, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

    __shared_ptr(__shared_ptr&& __r) noexcept
    : _M_ptr(__r._M_ptr), _M_refcount()
    {
_M_refcount._M_swap(__r._M_refcount);
__r._M_ptr = 0;
    }

    template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(__shared_ptr<_Yp, _Lp>&& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount()
{
 _M_refcount._M_swap(__r._M_refcount);
 __r._M_ptr = 0;
}

    template<typename _Yp, typename = _Compatible<_Yp>>
explicit __shared_ptr(const __weak_ptr<_Yp, _Lp>& __r)
: _M_refcount(__r._M_refcount) // may throw
{
 // It is now safe to copy __r._M_ptr, as
 // _M_refcount(__r._M_refcount) did not throw.
 _M_ptr = __r._M_ptr;
}

    // If an exception is thrown this constructor has no effect.
    template<typename _Yp, typename _Del,
      typename = _UniqCompatible<_Yp, _Del>>
__shared_ptr(unique_ptr<_Yp, _Del>&& __r)
: _M_ptr(__r.get()), _M_refcount()
{
 auto __raw = __to_address(__r.get());
 _M_refcount = __shared_count<_Lp>(std::move(__r));
 _M_enable_shared_from_this_with(__raw);
}

1225#if __cplusplus201703L <= 201402L && _GLIBCXX_USE_DEPRECATED1
  protected:
    // If an exception is thrown this constructor has no effect.
    template<typename _Tp1, typename _Del,
      typename enable_if<__and_<
 __not_<is_array<_Tp>>, is_array<_Tp1>,
        is_convertible<typename unique_ptr<_Tp1, _Del>::pointer, _Tp*>
      >::value, bool>::type = true>
__shared_ptr(unique_ptr<_Tp1, _Del>&& __r, __sp_array_delete)
: _M_ptr(__r.get()), _M_refcount()
{
 auto __raw = __to_address(__r.get());
 _M_refcount = __shared_count<_Lp>(std::move(__r));
 _M_enable_shared_from_this_with(__raw);
}
  public:
1241#endif

1243#if _GLIBCXX_USE_DEPRECATED1
1244#pragma GCC diagnostic push
1245#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
    // Postcondition: use_count() == 1 and __r.get() == 0
    template<typename _Yp, typename = _Compatible<_Yp>>
__shared_ptr(auto_ptr<_Yp>&& __r);
1249#pragma GCC diagnostic pop
1250#endif

    constexpr __shared_ptr(nullptr_t) noexcept : __shared_ptr() { }

    template<typename _Yp>
_Assignable<_Yp>
operator=(const __shared_ptr<_Yp, _Lp>& __r) noexcept
{
 _M_ptr = __r._M_ptr;
 _M_refcount = __r._M_refcount; // __shared_count::op= doesn't throw
 return *this;
}

1263#if _GLIBCXX_USE_DEPRECATED1
1264#pragma GCC diagnostic push
1265#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
    template<typename _Yp>
_Assignable<_Yp>
operator=(auto_ptr<_Yp>&& __r)
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}
1273#pragma GCC diagnostic pop
1274#endif

    __shared_ptr&
    operator=(__shared_ptr&& __r) noexcept
    {
__shared_ptr(std::move(__r)).swap(*this);
return *this;
    }

    template<class _Yp>
_Assignable<_Yp>
operator=(__shared_ptr<_Yp, _Lp>&& __r) noexcept
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}

    template<typename _Yp, typename _Del>
_UniqAssignable<_Yp, _Del>
operator=(unique_ptr<_Yp, _Del>&& __r)
{
 __shared_ptr(std::move(__r)).swap(*this);
 return *this;
}

    void
    reset() noexcept
    { __shared_ptr().swap(*this); }

    template<typename _Yp>
_SafeConv<_Yp>
reset(_Yp* __p) // _Yp must be complete.
{
 // Catch self-reset errors.
 __glibcxx_assert(__p == 0 || __p != _M_ptr)do { if (! (__p == 0 || __p != _M_ptr)) std::__replacement_assert
("/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/shared_ptr_base.h"
, 1308, __PRETTY_FUNCTION__, "__p == 0 || __p != _M_ptr"); } while
 (false);
 __shared_ptr(__p).swap(*this);
}

    template<typename _Yp, typename _Deleter>
_SafeConv<_Yp>
reset(_Yp* __p, _Deleter __d)
{ __shared_ptr(__p, std::move(__d)).swap(*this); }

    template<typename _Yp, typename _Deleter, typename _Alloc>
_SafeConv<_Yp>
reset(_Yp* __p, _Deleter __d, _Alloc __a)
      { __shared_ptr(__p, std::move(__d), std::move(__a)).swap(*this); }

    /// Return the stored pointer.
    element_type*
    get() const noexcept
    { return _M_ptr; }

    /// Return true if the stored pointer is not null.
    explicit operator bool() const // never throws
    { return _M_ptr == 0 ? false : true; }

    /// Return true if use_count() == 1.
    bool
    unique() const noexcept
    { return _M_refcount._M_unique(); }

    /// If *this owns a pointer, return the number of owners, otherwise zero.
    long
    use_count() const noexcept
    { return _M_refcount._M_get_use_count(); }

    /// Exchange both the owned pointer and the stored pointer.
    void
    swap(__shared_ptr<_Tp, _Lp>& __other) noexcept
    {
std::swap(_M_ptr, __other._M_ptr);
_M_refcount._M_swap(__other._M_refcount);
    }

    /** @brief Define an ordering based on ownership.
     *
     * This function defines a strict weak ordering between two shared_ptr
     * or weak_ptr objects, such that one object is less than the other
     * unless they share ownership of the same pointer, or are both empty.
     * @{
    */
    template<typename _Tp1>
bool
owner_before(__shared_ptr<_Tp1, _Lp> const& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

    template<typename _Tp1>
bool
owner_before(__weak_ptr<_Tp1, _Lp> const& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }
    // @}

  protected:
    // This constructor is non-standard, it is used by allocate_shared.
    template<typename _Alloc, typename... _Args>
__shared_ptr(_Sp_alloc_shared_tag<_Alloc> __tag, _Args&&... __args)
: _M_ptr(), _M_refcount(_M_ptr, __tag, std::forward<_Args>(__args)...)
9
←
Calling constructor for '__shared_count<__gnu_cxx::_S_atomic>'→
19
←
Returning from constructor for '__shared_count<__gnu_cxx::_S_atomic>'→
{ _M_enable_shared_from_this_with(_M_ptr); }

    template<typename _Tp1, _Lock_policy _Lp1, typename _Alloc,
      typename... _Args>
friend __shared_ptr<_Tp1, _Lp1>
__allocate_shared(const _Alloc& __a, _Args&&... __args);

    // This constructor is used by __weak_ptr::lock() and
    // shared_ptr::shared_ptr(const weak_ptr&, std::nothrow_t).
    __shared_ptr(const __weak_ptr<_Tp, _Lp>& __r, std::nothrow_t)
    : _M_refcount(__r._M_refcount, std::nothrow)
    {
_M_ptr = _M_refcount._M_get_use_count() ? __r._M_ptr : nullptr;
    }

    friend class __weak_ptr<_Tp, _Lp>;

  private:

    template<typename _Yp>
using __esft_base_t = decltype(__enable_shared_from_this_base(
     std::declval<const __shared_count<_Lp>&>(),
     std::declval<_Yp*>()));

    // Detect an accessible and unambiguous enable_shared_from_this base.
    template<typename _Yp, typename = void>
struct __has_esft_base
: false_type { };

    template<typename _Yp>
struct __has_esft_base<_Yp, __void_t<__esft_base_t<_Yp>>>
: __not_<is_array<_Tp>> { }; // No enable shared_from_this for arrays

    template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
typename enable_if<__has_esft_base<_Yp2>::value>::type
_M_enable_shared_from_this_with(_Yp* __p) noexcept
{
 if (auto __base = __enable_shared_from_this_base(_M_refcount, __p))
   __base->_M_weak_assign(const_cast<_Yp2*>(__p), _M_refcount);
}

    template<typename _Yp, typename _Yp2 = typename remove_cv<_Yp>::type>
typename enable_if<!__has_esft_base<_Yp2>::value>::type
_M_enable_shared_from_this_with(_Yp*) noexcept
{ }

    void*
    _M_get_deleter(const std::type_info& __ti) const noexcept
    { return _M_refcount._M_get_deleter(__ti); }

    template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
    template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;

    template<typename _Del, typename _Tp1, _Lock_policy _Lp1>
friend _Del* get_deleter(const __shared_ptr<_Tp1, _Lp1>&) noexcept;

    template<typename _Del, typename _Tp1>
friend _Del* get_deleter(const shared_ptr<_Tp1>&) noexcept;

    element_type*	   _M_ptr;         // Contained pointer.
    __shared_count<_Lp>  _M_refcount;    // Reference counter.
  };


// 20.7.2.2.7 shared_ptr comparisons
template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator==(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return __a.get() == __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator==(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !__a; }

1448#ifdef __cpp_lib_three_way_comparison
template<typename _Tp, typename _Up, _Lock_policy _Lp>
  inline strong_ordering
  operator<=>(const __shared_ptr<_Tp, _Lp>& __a,
const __shared_ptr<_Up, _Lp>& __b) noexcept
  { return compare_three_way()(__a.get(), __b.get()); }

template<typename _Tp, _Lock_policy _Lp>
  inline strong_ordering
  operator<=>(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  {
    using pointer = typename __shared_ptr<_Tp, _Lp>::element_type*;
    return compare_three_way()(__a.get(), static_cast<pointer>(nullptr));
  }
1462#else
template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator==(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !__a; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator!=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return __a.get() != __b.get(); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator!=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return (bool)__a; }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator!=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return (bool)__a; }

template<typename _Tp, typename _Up, _Lock_policy _Lp>
  inline bool
  operator<(const __shared_ptr<_Tp, _Lp>& __a,
     const __shared_ptr<_Up, _Lp>& __b) noexcept
  {
    using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
    using _Up_elt = typename __shared_ptr<_Up, _Lp>::element_type;
    using _Vp = typename common_type<_Tp_elt*, _Up_elt*>::type;
    return less<_Vp>()(__a.get(), __b.get());
  }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  {
    using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
    return less<_Tp_elt*>()(__a.get(), nullptr);
  }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  {
    using _Tp_elt = typename __shared_ptr<_Tp, _Lp>::element_type;
    return less<_Tp_elt*>()(nullptr, __a.get());
  }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator<=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return !(__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !(nullptr < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator<=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !(__a < nullptr); }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator>(const __shared_ptr<_Tp1, _Lp>& __a,
     const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return (__b < __a); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return nullptr < __a; }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return __a < nullptr; }

template<typename _Tp1, typename _Tp2, _Lock_policy _Lp>
  inline bool
  operator>=(const __shared_ptr<_Tp1, _Lp>& __a,
      const __shared_ptr<_Tp2, _Lp>& __b) noexcept
  { return !(__a < __b); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>=(const __shared_ptr<_Tp, _Lp>& __a, nullptr_t) noexcept
  { return !(__a < nullptr); }

template<typename _Tp, _Lock_policy _Lp>
  inline bool
  operator>=(nullptr_t, const __shared_ptr<_Tp, _Lp>& __a) noexcept
  { return !(nullptr < __a); }
1558#endif // three-way comparison

// 20.7.2.2.8 shared_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
  inline void
  swap(__shared_ptr<_Tp, _Lp>& __a, __shared_ptr<_Tp, _Lp>& __b) noexcept
  { __a.swap(__b); }

// 20.7.2.2.9 shared_ptr casts

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(static_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// static_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  static_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  {
    using _Sp = __shared_ptr<_Tp, _Lp>;
    return _Sp(__r, static_cast<typename _Sp::element_type*>(__r.get()));
  }

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(const_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// const_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  const_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  {
    using _Sp = __shared_ptr<_Tp, _Lp>;
    return _Sp(__r, const_cast<typename _Sp::element_type*>(__r.get()));
  }

// The seemingly equivalent code:
// shared_ptr<_Tp, _Lp>(dynamic_cast<_Tp*>(__r.get()))
// will eventually result in undefined behaviour, attempting to
// delete the same object twice.
/// dynamic_pointer_cast
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  dynamic_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  {
    using _Sp = __shared_ptr<_Tp, _Lp>;
    if (auto* __p = dynamic_cast<typename _Sp::element_type*>(__r.get()))
return _Sp(__r, __p);
    return _Sp();
  }

1609#if __cplusplus201703L > 201402L
template<typename _Tp, typename _Tp1, _Lock_policy _Lp>
  inline __shared_ptr<_Tp, _Lp>
  reinterpret_pointer_cast(const __shared_ptr<_Tp1, _Lp>& __r) noexcept
  {
    using _Sp = __shared_ptr<_Tp, _Lp>;
    return _Sp(__r, reinterpret_cast<typename _Sp::element_type*>(__r.get()));
  }
1617#endif

template<typename _Tp, _Lock_policy _Lp>
  class __weak_ptr
  {
    template<typename _Yp, typename _Res = void>
using _Compatible = typename
 enable_if<__sp_compatible_with<_Yp*, _Tp*>::value, _Res>::type;

    // Constraint for assignment from shared_ptr and weak_ptr:
    template<typename _Yp>
using _Assignable = _Compatible<_Yp, __weak_ptr&>;

  public:
    using element_type = typename remove_extent<_Tp>::type;

    constexpr __weak_ptr() noexcept
    : _M_ptr(nullptr), _M_refcount()
    { }

    __weak_ptr(const __weak_ptr&) noexcept = default;

    ~__weak_ptr() = default;

    // The "obvious" converting constructor implementation:
    //
    //  template<typename _Tp1>
    //    __weak_ptr(const __weak_ptr<_Tp1, _Lp>& __r)
    //    : _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount) // never throws
    //    { }
    //
    // has a serious problem.
    //
    //  __r._M_ptr may already have been invalidated. The _M_ptr(__r._M_ptr)
    //  conversion may require access to *__r._M_ptr (virtual inheritance).
    //
    // It is not possible to avoid spurious access violations since
    // in multithreaded programs __r._M_ptr may be invalidated at any point.
    template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(const __weak_ptr<_Yp, _Lp>& __r) noexcept
: _M_refcount(__r._M_refcount)
      { _M_ptr = __r.lock().get(); }

    template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(const __shared_ptr<_Yp, _Lp>& __r) noexcept
: _M_ptr(__r._M_ptr), _M_refcount(__r._M_refcount)
{ }

    __weak_ptr(__weak_ptr&& __r) noexcept
    : _M_ptr(__r._M_ptr), _M_refcount(std::move(__r._M_refcount))
    { __r._M_ptr = nullptr; }

    template<typename _Yp, typename = _Compatible<_Yp>>
__weak_ptr(__weak_ptr<_Yp, _Lp>&& __r) noexcept
: _M_ptr(__r.lock().get()), _M_refcount(std::move(__r._M_refcount))
      { __r._M_ptr = nullptr; }

    __weak_ptr&
    operator=(const __weak_ptr& __r) noexcept = default;

    template<typename _Yp>
_Assignable<_Yp>
operator=(const __weak_ptr<_Yp, _Lp>& __r) noexcept
{
 _M_ptr = __r.lock().get();
 _M_refcount = __r._M_refcount;
 return *this;
}

    template<typename _Yp>
_Assignable<_Yp>
operator=(const __shared_ptr<_Yp, _Lp>& __r) noexcept
{
 _M_ptr = __r._M_ptr;
 _M_refcount = __r._M_refcount;
 return *this;
}

    __weak_ptr&
    operator=(__weak_ptr&& __r) noexcept
    {
_M_ptr = __r._M_ptr;
_M_refcount = std::move(__r._M_refcount);
__r._M_ptr = nullptr;
return *this;
    }

    template<typename _Yp>
_Assignable<_Yp>
operator=(__weak_ptr<_Yp, _Lp>&& __r) noexcept
{
 _M_ptr = __r.lock().get();
 _M_refcount = std::move(__r._M_refcount);
 __r._M_ptr = nullptr;
 return *this;
}

    __shared_ptr<_Tp, _Lp>
    lock() const noexcept
    { return __shared_ptr<element_type, _Lp>(*this, std::nothrow); }

    long
    use_count() const noexcept
    { return _M_refcount._M_get_use_count(); }

    bool
    expired() const noexcept
    { return _M_refcount._M_get_use_count() == 0; }

    template<typename _Tp1>
bool
owner_before(const __shared_ptr<_Tp1, _Lp>& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

    template<typename _Tp1>
bool
owner_before(const __weak_ptr<_Tp1, _Lp>& __rhs) const noexcept
{ return _M_refcount._M_less(__rhs._M_refcount); }

    void
    reset() noexcept
    { __weak_ptr().swap(*this); }

    void
    swap(__weak_ptr& __s) noexcept
    {
std::swap(_M_ptr, __s._M_ptr);
_M_refcount._M_swap(__s._M_refcount);
    }

  private:
    // Used by __enable_shared_from_this.
    void
    _M_assign(_Tp* __ptr, const __shared_count<_Lp>& __refcount) noexcept
    {
if (use_count() == 0)
 {
   _M_ptr = __ptr;
   _M_refcount = __refcount;
 }
    }

    template<typename _Tp1, _Lock_policy _Lp1> friend class __shared_ptr;
    template<typename _Tp1, _Lock_policy _Lp1> friend class __weak_ptr;
    friend class __enable_shared_from_this<_Tp, _Lp>;
    friend class enable_shared_from_this<_Tp>;

    element_type*	 _M_ptr;         // Contained pointer.
    __weak_count<_Lp>  _M_refcount;    // Reference counter.
  };

// 20.7.2.3.6 weak_ptr specialized algorithms.
template<typename _Tp, _Lock_policy _Lp>
  inline void
  swap(__weak_ptr<_Tp, _Lp>& __a, __weak_ptr<_Tp, _Lp>& __b) noexcept
  { __a.swap(__b); }

template<typename _Tp, typename _Tp1>
  struct _Sp_owner_less : public binary_function<_Tp, _Tp, bool>
  {
    bool
    operator()(const _Tp& __lhs, const _Tp& __rhs) const noexcept
    { return __lhs.owner_before(__rhs); }

    bool
    operator()(const _Tp& __lhs, const _Tp1& __rhs) const noexcept
    { return __lhs.owner_before(__rhs); }

    bool
    operator()(const _Tp1& __lhs, const _Tp& __rhs) const noexcept
    { return __lhs.owner_before(__rhs); }
  };

template<>
  struct _Sp_owner_less<void, void>
  {
    template<typename _Tp, typename _Up>
auto
operator()(const _Tp& __lhs, const _Up& __rhs) const noexcept
-> decltype(__lhs.owner_before(__rhs))
{ return __lhs.owner_before(__rhs); }

    using is_transparent = void;
  };

template<typename _Tp, _Lock_policy _Lp>
  struct owner_less<__shared_ptr<_Tp, _Lp>>
  : public _Sp_owner_less<__shared_ptr<_Tp, _Lp>, __weak_ptr<_Tp, _Lp>>
  { };

template<typename _Tp, _Lock_policy _Lp>
  struct owner_less<__weak_ptr<_Tp, _Lp>>
  : public _Sp_owner_less<__weak_ptr<_Tp, _Lp>, __shared_ptr<_Tp, _Lp>>
  { };


template<typename _Tp, _Lock_policy _Lp>
  class __enable_shared_from_this
  {
  protected:
    constexpr __enable_shared_from_this() noexcept { }

    __enable_shared_from_this(const __enable_shared_from_this&) noexcept { }

    __enable_shared_from_this&
    operator=(const __enable_shared_from_this&) noexcept
    { return *this; }

    ~__enable_shared_from_this() { }

  public:
    __shared_ptr<_Tp, _Lp>
    shared_from_this()
    { return __shared_ptr<_Tp, _Lp>(this->_M_weak_this); }

    __shared_ptr<const _Tp, _Lp>
    shared_from_this() const
    { return __shared_ptr<const _Tp, _Lp>(this->_M_weak_this); }

1836#if __cplusplus201703L > 201402L || !defined(__STRICT_ANSI__1) // c++1z or gnu++11
    __weak_ptr<_Tp, _Lp>
    weak_from_this() noexcept
    { return this->_M_weak_this; }

    __weak_ptr<const _Tp, _Lp>
    weak_from_this() const noexcept
    { return this->_M_weak_this; }
1844#endif

  private:
    template<typename _Tp1>
void
_M_weak_assign(_Tp1* __p, const __shared_count<_Lp>& __n) const noexcept
{ _M_weak_this._M_assign(__p, __n); }

    friend const __enable_shared_from_this*
    __enable_shared_from_this_base(const __shared_count<_Lp>&,
		     const __enable_shared_from_this* __p)
    { return __p; }

    template<typename, _Lock_policy>
friend class __shared_ptr;

    mutable __weak_ptr<_Tp, _Lp>  _M_weak_this;
  };

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy,
  typename _Alloc, typename... _Args>
  inline __shared_ptr<_Tp, _Lp>
  __allocate_shared(const _Alloc& __a, _Args&&... __args)
  {
    return __shared_ptr<_Tp, _Lp>(_Sp_alloc_shared_tag<_Alloc>{__a},
		    std::forward<_Args>(__args)...);
  }

template<typename _Tp, _Lock_policy _Lp = __default_lock_policy,
  typename... _Args>
  inline __shared_ptr<_Tp, _Lp>
  __make_shared(_Args&&... __args)
  {
    typedef typename std::remove_const<_Tp>::type _Tp_nc;
    return std::__allocate_shared<_Tp, _Lp>(std::allocator<_Tp_nc>(),
			      std::forward<_Args>(__args)...);
  }

/// std::hash specialization for __shared_ptr.
template<typename _Tp, _Lock_policy _Lp>
  struct hash<__shared_ptr<_Tp, _Lp>>
  : public __hash_base<size_t, __shared_ptr<_Tp, _Lp>>
  {
    size_t
    operator()(const __shared_ptr<_Tp, _Lp>& __s) const noexcept
    {
return hash<typename __shared_ptr<_Tp, _Lp>::element_type*>()(
   __s.get());
    }
  };

1895_GLIBCXX_END_NAMESPACE_VERSION
1896} // namespace

1898#endif // _SHARED_PTR_BASE_H

←

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

→

1// Guarded Allocation -*- C++ -*-
2 
3// Copyright (C) 2014-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/** @file bits/allocated_ptr.h
26 *  This is an internal header file, included by other library headers.
27 *  Do not attempt to use it directly. @headername{memory}
28 */
29 
30#ifndef _ALLOCATED_PTR_H1
31#define _ALLOCATED_PTR_H1 1
32 
33#if __cplusplus201703L < 201103L
34# include <bits/c++0xwarning.h>
35#else
36# include <type_traits>
37# include <bits/ptr_traits.h>
38# include <bits/alloc_traits.h>
39 
40namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
41{
42_GLIBCXX_BEGIN_NAMESPACE_VERSION
43 
44  /// Non-standard RAII type for managing pointers obtained from allocators.
45  template<typename _Alloc>
46    struct __allocated_ptr
47    {
48      using pointer = typename allocator_traits<_Alloc>::pointer;
49      using value_type = typename allocator_traits<_Alloc>::value_type;
50 
51      /// Take ownership of __ptr
52      __allocated_ptr(_Alloc& __a, pointer __ptr) noexcept
53      : _M_alloc(std::__addressof(__a)), _M_ptr(__ptr)
54      { }
55 
56      /// Convert __ptr to allocator's pointer type and take ownership of it
57      template<typename _Ptr,
58	       typename _Req = _Require<is_same<_Ptr, value_type*>>>
59      __allocated_ptr(_Alloc& __a, _Ptr __ptr)
60      : _M_alloc(std::__addressof(__a)),
61	_M_ptr(pointer_traits<pointer>::pointer_to(*__ptr))
62      { }
63 
64      /// Transfer ownership of the owned pointer
65      __allocated_ptr(__allocated_ptr&& __gd) noexcept
66      : _M_alloc(__gd._M_alloc), _M_ptr(__gd._M_ptr)
67      { __gd._M_ptr = nullptr; }
68 
69      /// Deallocate the owned pointer
70      ~__allocated_ptr()
71      {
72	if (_M_ptr != nullptr)
73	  std::allocator_traits<_Alloc>::deallocate(*_M_alloc, _M_ptr, 1);
74      }
75 
76      /// Release ownership of the owned pointer
77      __allocated_ptr&
78      operator=(std::nullptr_t) noexcept
79      {
80	_M_ptr = nullptr;
81	return *this;
82      }
83 
84      /// Get the address that the owned pointer refers to.
85      value_type* get() { return std::__to_address(_M_ptr); }
86 
87    private:
88      _Alloc* _M_alloc;
89      pointer _M_ptr;
90    };
91 
92  /// Allocate space for a single object using __a
93  template<typename _Alloc>
94    __allocated_ptr<_Alloc>
95    __allocate_guarded(_Alloc& __a)
96    {
97      return { __a, std::allocator_traits<_Alloc>::allocate(__a, 1) };
11
←
Calling 'allocator_traits::allocate'→
17
←
Returned allocated memory→
98    }
99 
100_GLIBCXX_END_NAMESPACE_VERSION
101} // namespace std
102 
103#endif
104#endif

←

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

→

1// Allocator traits -*- C++ -*-

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

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

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

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

25/** @file bits/alloc_traits.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{memory}
*/

30#ifndef _ALLOC_TRAITS_H1
31#define _ALLOC_TRAITS_H1 1

33#include <bits/stl_construct.h>
34#include <bits/memoryfwd.h>
35#if __cplusplus201703L >= 201103L
36# include <bits/allocator.h>
37# include <bits/ptr_traits.h>
38# include <ext/numeric_traits.h>
39#endif

41namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
42{
43_GLIBCXX_BEGIN_NAMESPACE_VERSION

45#if __cplusplus201703L >= 201103L
46#define __cpp_lib_allocator_traits_is_always_equal201411 201411

struct __allocator_traits_base
{
  template<typename _Tp, typename _Up, typename = void>
    struct __rebind : __replace_first_arg<_Tp, _Up> { };

  template<typename _Tp, typename _Up>
    struct __rebind<_Tp, _Up,
      __void_t<typename _Tp::template rebind<_Up>::other>>
    { using type = typename _Tp::template rebind<_Up>::other; };

protected:
  template<typename _Tp>
    using __pointer = typename _Tp::pointer;
  template<typename _Tp>
    using __c_pointer = typename _Tp::const_pointer;
  template<typename _Tp>
    using __v_pointer = typename _Tp::void_pointer;
  template<typename _Tp>
    using __cv_pointer = typename _Tp::const_void_pointer;
  template<typename _Tp>
    using __pocca = typename _Tp::propagate_on_container_copy_assignment;
  template<typename _Tp>
    using __pocma = typename _Tp::propagate_on_container_move_assignment;
  template<typename _Tp>
    using __pocs = typename _Tp::propagate_on_container_swap;
  template<typename _Tp>
    using __equal = typename _Tp::is_always_equal;
};

template<typename _Alloc, typename _Up>
  using __alloc_rebind
    = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;

/**
 * @brief  Uniform interface to all allocator types.
 * @ingroup allocators
*/
template<typename _Alloc>
  struct allocator_traits : __allocator_traits_base
  {
    /// The allocator type
    typedef _Alloc allocator_type;
    /// The allocated type
    typedef typename _Alloc::value_type value_type;

    /**
     * @brief   The allocator's pointer type.
     *
     * @c Alloc::pointer if that type exists, otherwise @c value_type*
    */
    using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;

  private:
    // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
    template<template<typename> class _Func, typename _Tp, typename = void>
struct _Ptr
{
 using type = typename pointer_traits<pointer>::template rebind<_Tp>;
};

    template<template<typename> class _Func, typename _Tp>
struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
{
 using type = _Func<_Alloc>;
};

    // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
    template<typename _A2, typename _PtrT, typename = void>
struct _Diff
{ using type = typename pointer_traits<_PtrT>::difference_type; };

    template<typename _A2, typename _PtrT>
struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
{ using type = typename _A2::difference_type; };

    // Select _A2::size_type or make_unsigned<_DiffT>::type
    template<typename _A2, typename _DiffT, typename = void>
struct _Size : make_unsigned<_DiffT> { };

    template<typename _A2, typename _DiffT>
struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
{ using type = typename _A2::size_type; };

  public:
    /**
     * @brief   The allocator's const pointer type.
     *
     * @c Alloc::const_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
    */
    using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;

    /**
     * @brief   The allocator's void pointer type.
     *
     * @c Alloc::void_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<void> </tt>
    */
    using void_pointer = typename _Ptr<__v_pointer, void>::type;

    /**
     * @brief   The allocator's const void pointer type.
     *
     * @c Alloc::const_void_pointer if that type exists, otherwise
     * <tt> pointer_traits<pointer>::rebind<const void> </tt>
    */
    using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;

    /**
     * @brief   The allocator's difference type
     *
     * @c Alloc::difference_type if that type exists, otherwise
     * <tt> pointer_traits<pointer>::difference_type </tt>
    */
    using difference_type = typename _Diff<_Alloc, pointer>::type;

    /**
     * @brief   The allocator's size type
     *
     * @c Alloc::size_type if that type exists, otherwise
     * <tt> make_unsigned<difference_type>::type </tt>
    */
    using size_type = typename _Size<_Alloc, difference_type>::type;

    /**
     * @brief   How the allocator is propagated on copy assignment
     *
     * @c Alloc::propagate_on_container_copy_assignment if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_copy_assignment
= __detected_or_t<false_type, __pocca, _Alloc>;

    /**
     * @brief   How the allocator is propagated on move assignment
     *
     * @c Alloc::propagate_on_container_move_assignment if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_move_assignment
= __detected_or_t<false_type, __pocma, _Alloc>;

    /**
     * @brief   How the allocator is propagated on swap
     *
     * @c Alloc::propagate_on_container_swap if that type exists,
     * otherwise @c false_type
    */
    using propagate_on_container_swap
= __detected_or_t<false_type, __pocs, _Alloc>;

    /**
     * @brief   Whether all instances of the allocator type compare equal.
     *
     * @c Alloc::is_always_equal if that type exists,
     * otherwise @c is_empty<Alloc>::type
    */
    using is_always_equal
= __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>;

    template<typename _Tp>
using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
    template<typename _Tp>
using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;

  private:
    template<typename _Alloc2>
static constexpr auto
_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
-> decltype(__a.allocate(__n, __hint))
{ return __a.allocate(__n, __hint); }

    template<typename _Alloc2>
static constexpr pointer
_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
{ return __a.allocate(__n); }

    template<typename _Tp, typename... _Args>
struct __construct_helper
{
 template<typename _Alloc2,
   typename = decltype(std::declval<_Alloc2*>()->construct(
  std::declval<_Tp*>(), std::declval<_Args>()...))>
   static true_type __test(int);

 template<typename>
   static false_type __test(...);

 using type = decltype(__test<_Alloc>(0));
};

    template<typename _Tp, typename... _Args>
using __has_construct
 = typename __construct_helper<_Tp, _Args...>::type;

    template<typename _Tp, typename... _Args>
static _GLIBCXX14_CONSTEXPRconstexpr _Require<__has_construct<_Tp, _Args...>>
_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
{ __a.construct(__p, std::forward<_Args>(__args)...); }

    template<typename _Tp, typename... _Args>
static _GLIBCXX14_CONSTEXPRconstexpr
_Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
	       is_constructible<_Tp, _Args...>>>
_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
noexcept(std::is_nothrow_constructible<_Tp, _Args...>::value)
{
256#if __cplusplus201703L <= 201703L
 ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
258#else
 std::construct_at(__p, std::forward<_Args>(__args)...);
260#endif
}

    template<typename _Alloc2, typename _Tp>
static _GLIBCXX14_CONSTEXPRconstexpr auto
_S_destroy(_Alloc2& __a, _Tp* __p, int)
noexcept(noexcept(__a.destroy(__p)))
-> decltype(__a.destroy(__p))
{ __a.destroy(__p); }

    template<typename _Alloc2, typename _Tp>
static _GLIBCXX14_CONSTEXPRconstexpr void
_S_destroy(_Alloc2&, _Tp* __p, ...)
noexcept(std::is_nothrow_destructible<_Tp>::value)
{ std::_Destroy(__p); }

    template<typename _Alloc2>
static constexpr auto
_S_max_size(_Alloc2& __a, int)
-> decltype(__a.max_size())
{ return __a.max_size(); }

    template<typename _Alloc2>
static constexpr size_type
_S_max_size(_Alloc2&, ...)
{
 // _GLIBCXX_RESOLVE_LIB_DEFECTS
 // 2466. allocator_traits::max_size() default behavior is incorrect
 return __gnu_cxx::__numeric_traits<size_type>::__max
   / sizeof(value_type);
}

    template<typename _Alloc2>
static constexpr auto
_S_select(_Alloc2& __a, int)
-> decltype(__a.select_on_container_copy_construction())
{ return __a.select_on_container_copy_construction(); }

    template<typename _Alloc2>
static constexpr _Alloc2
_S_select(_Alloc2& __a, ...)
{ return __a; }

  public:

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *
     *  Calls @c a.allocate(n)
    */
    _GLIBCXX_NODISCARD[[__nodiscard__]] static _GLIBCXX20_CONSTEXPR pointer
    allocate(_Alloc& __a, size_type __n)
    { return __a.allocate(__n); }

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *  @param  __hint Aid to locality.
     *  @return Memory of suitable size and alignment for @a n objects
     *          of type @c value_type
     *
     *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
     *  well-formed, otherwise returns @c a.allocate(n)
    */
    _GLIBCXX_NODISCARD[[__nodiscard__]] static _GLIBCXX20_CONSTEXPR pointer
    allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
    { return _S_allocate(__a, __n, __hint, 0); }

    /**
     *  @brief  Deallocate memory.
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the memory to deallocate.
     *  @param  __n  The number of objects space was allocated for.
     *
     *  Calls <tt> a.deallocate(p, n) </tt>
    */
    static _GLIBCXX20_CONSTEXPR void
    deallocate(_Alloc& __a, pointer __p, size_type __n)
    { __a.deallocate(__p, __n); }

    /**
     *  @brief  Construct an object of type @a _Tp
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to memory of suitable size and alignment for Tp
     *  @param  __args Constructor arguments.
     *
     *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
     *  if that expression is well-formed, otherwise uses placement-new
     *  to construct an object of type @a _Tp at location @a __p from the
     *  arguments @a __args...
    */
    template<typename _Tp, typename... _Args>
static _GLIBCXX20_CONSTEXPR auto
construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
noexcept(noexcept(_S_construct(__a, __p,
		       std::forward<_Args>(__args)...)))
-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }

    /**
     *  @brief  Destroy an object of type @a _Tp
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the object to destroy
     *
     *  Calls @c __a.destroy(__p) if that expression is well-formed,
     *  otherwise calls @c __p->~_Tp()
    */
    template<typename _Tp>
static _GLIBCXX20_CONSTEXPR void
destroy(_Alloc& __a, _Tp* __p)
noexcept(noexcept(_S_destroy(__a, __p, 0)))
{ _S_destroy(__a, __p, 0); }

    /**
     *  @brief  The maximum supported allocation size
     *  @param  __a  An allocator.
     *  @return @c __a.max_size() or @c numeric_limits<size_type>::max()
     *
     *  Returns @c __a.max_size() if that expression is well-formed,
     *  otherwise returns @c numeric_limits<size_type>::max()
    */
    static _GLIBCXX20_CONSTEXPR size_type
    max_size(const _Alloc& __a) noexcept
    { return _S_max_size(__a, 0); }

    /**
     *  @brief  Obtain an allocator to use when copying a container.
     *  @param  __rhs  An allocator.
     *  @return @c __rhs.select_on_container_copy_construction() or @a __rhs
     *
     *  Returns @c __rhs.select_on_container_copy_construction() if that
     *  expression is well-formed, otherwise returns @a __rhs
    */
    static _GLIBCXX20_CONSTEXPR _Alloc
    select_on_container_copy_construction(const _Alloc& __rhs)
    { return _S_select(__rhs, 0); }
  };

401#if __cplusplus201703L > 201703L
402# define __cpp_lib_constexpr_dynamic_alloc 201907L
403#endif

/// Partial specialization for std::allocator.
template<typename _Tp>
  struct allocator_traits<allocator<_Tp>>
  {
    /// The allocator type
    using allocator_type = allocator<_Tp>;

    /// The allocated type
    using value_type = _Tp;

    /// The allocator's pointer type.
    using pointer = _Tp*;

    /// The allocator's const pointer type.
    using const_pointer = const _Tp*;

    /// The allocator's void pointer type.
    using void_pointer = void*;

    /// The allocator's const void pointer type.
    using const_void_pointer = const void*;

    /// The allocator's difference type
    using difference_type = std::ptrdiff_t;

    /// The allocator's size type
    using size_type = std::size_t;

    /// How the allocator is propagated on copy assignment
    using propagate_on_container_copy_assignment = false_type;

    /// How the allocator is propagated on move assignment
    using propagate_on_container_move_assignment = true_type;

    /// How the allocator is propagated on swap
    using propagate_on_container_swap = false_type;

    /// Whether all instances of the allocator type compare equal.
    using is_always_equal = true_type;

    template<typename _Up>
using rebind_alloc = allocator<_Up>;

    template<typename _Up>
using rebind_traits = allocator_traits<allocator<_Up>>;

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *
     *  Calls @c a.allocate(n)
    */
    _GLIBCXX_NODISCARD[[__nodiscard__]] static _GLIBCXX20_CONSTEXPR pointer
    allocate(allocator_type& __a, size_type __n)
    { return __a.allocate(__n); }
12
←
Calling 'new_allocator::allocate'→
16
←
Returned allocated memory→

    /**
     *  @brief  Allocate memory.
     *  @param  __a  An allocator.
     *  @param  __n  The number of objects to allocate space for.
     *  @param  __hint Aid to locality.
     *  @return Memory of suitable size and alignment for @a n objects
     *          of type @c value_type
     *
     *  Returns <tt> a.allocate(n, hint) </tt>
    */
    _GLIBCXX_NODISCARD[[__nodiscard__]] static _GLIBCXX20_CONSTEXPR pointer
    allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
    {
475#if __cplusplus201703L <= 201703L
return __a.allocate(__n, __hint);
477#else
return __a.allocate(__n);
479#endif
    }

    /**
     *  @brief  Deallocate memory.
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the memory to deallocate.
     *  @param  __n  The number of objects space was allocated for.
     *
     *  Calls <tt> a.deallocate(p, n) </tt>
    */
    static _GLIBCXX20_CONSTEXPR void
    deallocate(allocator_type& __a, pointer __p, size_type __n)
    { __a.deallocate(__p, __n); }

    /**
     *  @brief  Construct an object of type `_Up`
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to memory of suitable size and alignment for
     *	       an object of type `_Up`.
     *  @param  __args Constructor arguments.
     *
     *  Calls `__a.construct(__p, std::forward<_Args>(__args)...)`
     *  in C++11, C++14 and C++17. Changed in C++20 to call
     *  `std::construct_at(__p, std::forward<_Args>(__args)...)` instead.
    */
    template<typename _Up, typename... _Args>
static _GLIBCXX20_CONSTEXPR void
construct(allocator_type& __a __attribute__((__unused__)), _Up* __p,
  _Args&&... __args)
noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
{
511#if __cplusplus201703L <= 201703L
 __a.construct(__p, std::forward<_Args>(__args)...);
513#else
 std::construct_at(__p, std::forward<_Args>(__args)...);
515#endif
}

    /**
     *  @brief  Destroy an object of type @a _Up
     *  @param  __a  An allocator.
     *  @param  __p  Pointer to the object to destroy
     *
     *  Calls @c __a.destroy(__p).
    */
    template<typename _Up>
static _GLIBCXX20_CONSTEXPR void
destroy(allocator_type& __a __attribute__((__unused__)), _Up* __p)
noexcept(is_nothrow_destructible<_Up>::value)
{
530#if __cplusplus201703L <= 201703L
 __a.destroy(__p);
532#else
 std::destroy_at(__p);
534#endif
}

    /**
     *  @brief  The maximum supported allocation size
     *  @param  __a  An allocator.
     *  @return @c __a.max_size()
    */
    static _GLIBCXX20_CONSTEXPR size_type
    max_size(const allocator_type& __a __attribute__((__unused__))) noexcept
    {
545#if __cplusplus201703L <= 201703L
return __a.max_size();
547#else
return size_t(-1) / sizeof(value_type);
549#endif
    }

    /**
     *  @brief  Obtain an allocator to use when copying a container.
     *  @param  __rhs  An allocator.
     *  @return @c __rhs
    */
    static _GLIBCXX20_CONSTEXPR allocator_type
    select_on_container_copy_construction(const allocator_type& __rhs)
    { return __rhs; }
  };

562#if __cplusplus201703L < 201703L
template<typename _Alloc>
  inline void
  __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
  { __one = __two; }

template<typename _Alloc>
  inline void
  __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
  { }
572#endif

template<typename _Alloc>
  _GLIBCXX14_CONSTEXPRconstexpr inline void
  __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_copy_assignment __pocca;
580#if __cplusplus201703L >= 201703L
    if constexpr (__pocca::value)
__one = __two;
583#else
    __do_alloc_on_copy(__one, __two, __pocca());
585#endif
  }

template<typename _Alloc>
  constexpr _Alloc
  __alloc_on_copy(const _Alloc& __a)
  {
    typedef allocator_traits<_Alloc> __traits;
    return __traits::select_on_container_copy_construction(__a);
  }

596#if __cplusplus201703L < 201703L
template<typename _Alloc>
  inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
  { __one = std::move(__two); }

template<typename _Alloc>
  inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
  { }
604#endif

template<typename _Alloc>
  _GLIBCXX14_CONSTEXPRconstexpr inline void
  __alloc_on_move(_Alloc& __one, _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_move_assignment __pocma;
612#if __cplusplus201703L >= 201703L
    if constexpr (__pocma::value)
__one = std::move(__two);
615#else
    __do_alloc_on_move(__one, __two, __pocma());
617#endif
  }

620#if __cplusplus201703L < 201703L
template<typename _Alloc>
  inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
  {
    using std::swap;
    swap(__one, __two);
  }

template<typename _Alloc>
  inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
  { }
631#endif

template<typename _Alloc>
  _GLIBCXX14_CONSTEXPRconstexpr inline void
  __alloc_on_swap(_Alloc& __one, _Alloc& __two)
  {
    typedef allocator_traits<_Alloc> __traits;
    typedef typename __traits::propagate_on_container_swap __pocs;
639#if __cplusplus201703L >= 201703L
    if constexpr (__pocs::value)
{
 using std::swap;
 swap(__one, __two);
}
645#else
    __do_alloc_on_swap(__one, __two, __pocs());
647#endif
  }

template<typename _Alloc, typename _Tp,
  typename _ValueT = __remove_cvref_t<typename _Alloc::value_type>,
  typename = void>
  struct __is_alloc_insertable_impl
  : false_type
  { };

template<typename _Alloc, typename _Tp, typename _ValueT>
  struct __is_alloc_insertable_impl<_Alloc, _Tp, _ValueT,
    __void_t<decltype(allocator_traits<_Alloc>::construct(
   std::declval<_Alloc&>(), std::declval<_ValueT*>(),
   std::declval<_Tp>()))>>
  : true_type
  { };

// true if _Alloc::value_type is CopyInsertable into containers using _Alloc
// (might be wrong if _Alloc::construct exists but is not constrained,
// i.e. actually trying to use it would still be invalid. Use with caution.)
template<typename _Alloc>
  struct __is_copy_insertable
  : __is_alloc_insertable_impl<_Alloc,
		 typename _Alloc::value_type const&>::type
  { };

// std::allocator<_Tp> just requires CopyConstructible
template<typename _Tp>
  struct __is_copy_insertable<allocator<_Tp>>
  : is_copy_constructible<_Tp>
  { };

// true if _Alloc::value_type is MoveInsertable into containers using _Alloc
// (might be wrong if _Alloc::construct exists but is not constrained,
// i.e. actually trying to use it would still be invalid. Use with caution.)
template<typename _Alloc>
  struct __is_move_insertable
  : __is_alloc_insertable_impl<_Alloc, typename _Alloc::value_type>::type
  { };

// std::allocator<_Tp> just requires MoveConstructible
template<typename _Tp>
  struct __is_move_insertable<allocator<_Tp>>
  : is_move_constructible<_Tp>
  { };

// Trait to detect Allocator-like types.
template<typename _Alloc, typename = void>
  struct __is_allocator : false_type { };

template<typename _Alloc>
  struct __is_allocator<_Alloc,
    __void_t<typename _Alloc::value_type,
      decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
  : true_type { };

template<typename _Alloc>
  using _RequireAllocator
    = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;

template<typename _Alloc>
  using _RequireNotAllocator
    = typename enable_if<!__is_allocator<_Alloc>::value, _Alloc>::type;
711#endif // C++11

/**
 * Destroy a range of objects using the supplied allocator.  For
 * non-default allocators we do not optimize away invocation of
 * destroy() even if _Tp has a trivial destructor.
 */

template<typename _ForwardIterator, typename _Allocator>
  void
  _Destroy(_ForwardIterator __first, _ForwardIterator __last,
    _Allocator& __alloc)
  {
    for (; __first != __last; ++__first)
725#if __cplusplus201703L < 201103L
__alloc.destroy(std::__addressof(*__first));
727#else
allocator_traits<_Allocator>::destroy(__alloc,
			      std::__addressof(*__first));
730#endif
  }

template<typename _ForwardIterator, typename _Tp>
  inline void
  _Destroy(_ForwardIterator __first, _ForwardIterator __last,
    allocator<_Tp>&)
  {
    _Destroy(__first, __last);
  }

741_GLIBCXX_END_NAMESPACE_VERSION
742} // namespace std
743#endif // _ALLOC_TRAITS_H

←

/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/ext/new_allocator.h

→

1// Allocator that wraps operator new -*- 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/** @file ext/new_allocator.h
26 *  This file is a GNU extension to the Standard C++ Library.
27 */
28 
29#ifndef _NEW_ALLOCATOR_H1
30#define _NEW_ALLOCATOR_H1 1
31 
32#include <bits/c++config.h>
33#include <new>
34#include <bits/functexcept.h>
35#include <bits/move.h>
36#if __cplusplus201703L >= 201103L
37#include <type_traits>
38#endif
39 
40namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
41{
42_GLIBCXX_BEGIN_NAMESPACE_VERSION
43 
44  /**
45   *  @brief  An allocator that uses global new, as per [20.4].
46   *  @ingroup allocators
47   *
48   *  This is precisely the allocator defined in the C++ Standard.
49   *    - all allocation calls operator new
50   *    - all deallocation calls operator delete
51   *
52   *  @tparam  _Tp  Type of allocated object.
53   */
54  template<typename _Tp>
55    class new_allocator
56    {
57    public:
58      typedef _Tp        value_type;
59      typedef std::size_t     size_type;
60      typedef std::ptrdiff_t  difference_type;
61#if __cplusplus201703L <= 201703L
62      typedef _Tp*       pointer;
63      typedef const _Tp* const_pointer;
64      typedef _Tp&       reference;
65      typedef const _Tp& const_reference;
66 
67      template<typename _Tp1>
68	struct rebind
69	{ typedef new_allocator<_Tp1> other; };
70#endif
71 
72#if __cplusplus201703L >= 201103L
73      // _GLIBCXX_RESOLVE_LIB_DEFECTS
74      // 2103. propagate_on_container_move_assignment
75      typedef std::true_type propagate_on_container_move_assignment;
76#endif
77 
78      _GLIBCXX20_CONSTEXPR
79      new_allocator() _GLIBCXX_USE_NOEXCEPTnoexcept { }
80 
81      _GLIBCXX20_CONSTEXPR
82      new_allocator(const new_allocator&) _GLIBCXX_USE_NOEXCEPTnoexcept { }
83 
84      template<typename _Tp1>
85	_GLIBCXX20_CONSTEXPR
86	new_allocator(const new_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPTnoexcept { }
87 
88#if __cplusplus201703L <= 201703L
89      ~new_allocator() _GLIBCXX_USE_NOEXCEPTnoexcept { }
90 
91      pointer
92      address(reference __x) const _GLIBCXX_NOEXCEPTnoexcept
93      { return std::__addressof(__x); }
94 
95      const_pointer
96      address(const_reference __x) const _GLIBCXX_NOEXCEPTnoexcept
97      { return std::__addressof(__x); }
98#endif
99 
100      // NB: __n is permitted to be 0.  The C++ standard says nothing
101      // about what the return value is when __n == 0.
102      _GLIBCXX_NODISCARD[[__nodiscard__]] _Tp*
103      allocate(size_type __n, const void* = static_cast<const void*>(0))
104      {
105	if (__n > this->_M_max_size())
13
←
Taking false branch→
106	  std::__throw_bad_alloc();
107 
108#if __cpp_aligned_new201606L
109	if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__16UL)
14
←
Taking false branch→
110	  {
111	    std::align_val_t __al = std::align_val_t(alignof(_Tp));
112	    return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), __al));
113	  }
114#endif
115	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
15
←
Memory is allocated→
116      }
117 
118      // __p is not permitted to be a null pointer.
119      void
120      deallocate(_Tp* __p, size_type __t)
121      {
122#if __cpp_aligned_new201606L
123	if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__16UL)
124	  {
125	    ::operator delete(__p,
126# if __cpp_sized_deallocation
127			      __t * sizeof(_Tp),
128# endif
129			      std::align_val_t(alignof(_Tp)));
130	    return;
131	  }
132#endif
133	::operator delete(__p
134#if __cpp_sized_deallocation
135			  , __t * sizeof(_Tp)
136#endif
137			 );
138      }
139 
140#if __cplusplus201703L <= 201703L
141      size_type
142      max_size() const _GLIBCXX_USE_NOEXCEPTnoexcept
143      { return _M_max_size(); }
144 
145#if __cplusplus201703L >= 201103L
146      template<typename _Up, typename... _Args>
147	void
148	construct(_Up* __p, _Args&&... __args)
149	noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
150	{ ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
151 
152      template<typename _Up>
153	void
154	destroy(_Up* __p)
155	noexcept(std::is_nothrow_destructible<_Up>::value)
156	{ __p->~_Up(); }
157#else
158      // _GLIBCXX_RESOLVE_LIB_DEFECTS
159      // 402. wrong new expression in [some_] allocator::construct
160      void
161      construct(pointer __p, const _Tp& __val)
162      { ::new((void *)__p) _Tp(__val); }
163 
164      void
165      destroy(pointer __p) { __p->~_Tp(); }
166#endif
167#endif // ! C++20
168 
169      template<typename _Up>
170	friend _GLIBCXX20_CONSTEXPR bool
171	operator==(const new_allocator&, const new_allocator<_Up>&)
172	_GLIBCXX_NOTHROWnoexcept
173	{ return true; }
174 
175#if __cpp_impl_three_way_comparison < 201907L
176      template<typename _Up>
177	friend _GLIBCXX20_CONSTEXPR bool
178	operator!=(const new_allocator&, const new_allocator<_Up>&)
179	_GLIBCXX_NOTHROWnoexcept
180	{ return false; }
181#endif
182 
183    private:
184      _GLIBCXX_CONSTEXPRconstexpr size_type
185      _M_max_size() const _GLIBCXX_USE_NOEXCEPTnoexcept
186      {
187#if __PTRDIFF_MAX__9223372036854775807L < __SIZE_MAX__18446744073709551615UL
188	return std::size_t(__PTRDIFF_MAX__9223372036854775807L) / sizeof(_Tp);
189#else
190	return std::size_t(-1) / sizeof(_Tp);
191#endif
192      }
193    };
194 
195_GLIBCXX_END_NAMESPACE_VERSION
196} // namespace
197 
198#endif

←

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

1	// Components for manipulating sequences of characters -- C++ --
2
3	// Copyright (C) 1997-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	/** @file bits/basic_string.h
26	* This is an internal header file, included by other library headers.
27	* Do not attempt to use it directly. @headername{string}
28	*/
29
30	//
31	// ISO C++ 14882: 21 Strings library
32	//
33
34	#ifndef _BASIC_STRING_H1
35	#define _BASIC_STRING_H1 1
36
37	#pragma GCC system_header
38
39	#include <ext/atomicity.h>
40	#include <ext/alloc_traits.h>
41	#include <debug/debug.h>
42
43	#if __cplusplus201703L >= 201103L
44	#include <initializer_list>
45	#endif
46
47	#if __cplusplus201703L >= 201703L
48	# include <string_view>
49	#endif
50
51
52	namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
53	{
54	_GLIBCXX_BEGIN_NAMESPACE_VERSION
55
56	#if _GLIBCXX_USE_CXX11_ABI1
57	_GLIBCXX_BEGIN_NAMESPACE_CXX11namespace __cxx11 {
58	/**
59	* @class basic_string basic_string.h <string>
60	* @brief Managing sequences of characters and character-like objects.
61	*
62	* @ingroup strings
63	* @ingroup sequences
64	*
65	* @tparam _CharT Type of character
66	* @tparam _Traits Traits for character type, defaults to
67	* char_traits<_CharT>.
68	* @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
69	*
70	* Meets the requirements of a <a href="tables.html#65">container</a>, a
71	* <a href="tables.html#66">reversible container</a>, and a
72	* <a href="tables.html#67">sequence</a>. Of the
73	* <a href="tables.html#68">optional sequence requirements</a>, only
74	* @c push_back, @c at, and @c %array access are supported.
75	*/
76	template<typename _CharT, typename _Traits, typename _Alloc>
77	class basic_string
78	{
79	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
80	rebind<_CharT>::other _Char_alloc_type;
81	typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
82
83	// Types:
84	public:
85	typedef _Traits traits_type;
86	typedef typename _Traits::char_type value_type;
87	typedef _Char_alloc_type allocator_type;
88	typedef typename _Alloc_traits::size_type size_type;
89	typedef typename _Alloc_traits::difference_type difference_type;
90	typedef typename _Alloc_traits::reference reference;
91	typedef typename _Alloc_traits::const_reference const_reference;
92	typedef typename _Alloc_traits::pointer pointer;
93	typedef typename _Alloc_traits::const_pointer const_pointer;
94	typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
95	typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
96	const_iterator;
97	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
98	typedef std::reverse_iterator<iterator> reverse_iterator;
99
100	/// Value returned by various member functions when they fail.
101	static const size_type npos = static_cast<size_type>(-1);
102
103	protected:
104	// type used for positions in insert, erase etc.
105	#if __cplusplus201703L < 201103L
106	typedef iterator __const_iterator;
107	#else
108	typedef const_iterator __const_iterator;
109	#endif
110
111	private:
112	#if __cplusplus201703L >= 201703L
113	// A helper type for avoiding boiler-plate.
114	typedef basic_string_view<_CharT, _Traits> __sv_type;
115
116	template<typename _Tp, typename _Res>
117	using _If_sv = enable_if_t<
118	__and_<is_convertible<const _Tp&, __sv_type>,
119	__not_<is_convertible<const _Tp, const basic_string>>,
120	__not_<is_convertible<const _Tp&, const _CharT*>>>::value,
121	_Res>;
122
123	// Allows an implicit conversion to __sv_type.
124	static __sv_type
125	_S_to_string_view(__sv_type __svt) noexcept
126	{ return __svt; }
127
128	// Wraps a string_view by explicit conversion and thus
129	// allows to add an internal constructor that does not
130	// participate in overload resolution when a string_view
131	// is provided.
132	struct __sv_wrapper
133	{
134	explicit __sv_wrapper(__sv_type __sv) noexcept : _M_sv(__sv) { }
135	__sv_type _M_sv;
136	};
137
138	/**
139	* @brief Only internally used: Construct string from a string view
140	* wrapper.
141	* @param __svw string view wrapper.
142	* @param __a Allocator to use.
143	*/
144	explicit
145	basic_string(__sv_wrapper __svw, const _Alloc& __a)
146	: basic_string(__svw._M_sv.data(), __svw._M_sv.size(), __a) { }
147	#endif
148
149	// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
150	struct _Alloc_hider : allocator_type // TODO check __is_final
151	{
152	#if __cplusplus201703L < 201103L
153	_Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
154	: allocator_type(__a), _M_p(__dat) { }
155	#else
156	_Alloc_hider(pointer __dat, const _Alloc& __a)
157	: allocator_type(__a), _M_p(__dat) { }
158
159	_Alloc_hider(pointer __dat, _Alloc&& __a = _Alloc())
160	: allocator_type(std::move(__a)), _M_p(__dat) { }
161	#endif
162
163	pointer _M_p; // The actual data.
164	};
165
166	_Alloc_hider _M_dataplus;
167	size_type _M_string_length;
168
169	enum { _S_local_capacity = 15 / sizeof(_CharT) };
170
171	union
172	{
173	_CharT _M_local_buf[_S_local_capacity + 1];
174	size_type _M_allocated_capacity;
175	};
176
177	void
178	_M_data(pointer __p)
179	{ _M_dataplus._M_p = __p; }
180
181	void
182	_M_length(size_type __length)
183	{ _M_string_length = __length; }
184
185	pointer
186	_M_data() const
187	{ return _M_dataplus._M_p; }
188
189	pointer
190	_M_local_data()
191	{
192	#if __cplusplus201703L >= 201103L
193	return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
194	#else
195	return pointer(_M_local_buf);
196	#endif
197	}
198
199	const_pointer
200	_M_local_data() const
201	{
202	#if __cplusplus201703L >= 201103L
203	return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
204	#else
205	return const_pointer(_M_local_buf);
206	#endif
207	}
208
209	void
210	_M_capacity(size_type __capacity)
211	{ _M_allocated_capacity = __capacity; }
212
213	void
214	_M_set_length(size_type __n)
215	{
216	_M_length(__n);
217	traits_type::assign(_M_data()[__n], _CharT());
218	}
219
220	bool
221	_M_is_local() const
222	{ return _M_data() == _M_local_data(); }
223
224	// Create & Destroy
225	pointer
226	_M_create(size_type&, size_type);
227
228	void
229	_M_dispose()
230	{
231	if (!_M_is_local())
232	_M_destroy(_M_allocated_capacity);
233	}
234
235	void
236	_M_destroy(size_type __size) throw()
237	{ _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + 1); }
238
239	// _M_construct_aux is used to implement the 21.3.1 para 15 which
240	// requires special behaviour if _InIterator is an integral type
241	template<typename _InIterator>
242	void
243	_M_construct_aux(_InIterator __beg, _InIterator __end,
244	std::__false_type)
245	{
246	typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
247	_M_construct(__beg, __end, _Tag());
248	}
249
250	// _GLIBCXX_RESOLVE_LIB_DEFECTS
251	// 438. Ambiguity in the "do the right thing" clause
252	template<typename _Integer>
253	void
254	_M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
255	{ _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
256
257	void
258	_M_construct_aux_2(size_type __req, _CharT __c)
259	{ _M_construct(__req, __c); }
260
261	template<typename _InIterator>
262	void
263	_M_construct(_InIterator __beg, _InIterator __end)
264	{
265	typedef typename std::__is_integer<_InIterator>::__type _Integral;
266	_M_construct_aux(__beg, __end, _Integral());
267	}
268
269	// For Input Iterators, used in istreambuf_iterators, etc.
270	template<typename _InIterator>
271	void
272	_M_construct(_InIterator __beg, _InIterator __end,
273	std::input_iterator_tag);
274
275	// For forward_iterators up to random_access_iterators, used for
276	// string::iterator, _CharT*, etc.
277	template<typename _FwdIterator>
278	void
279	_M_construct(_FwdIterator __beg, _FwdIterator __end,
280	std::forward_iterator_tag);
281
282	void
283	_M_construct(size_type __req, _CharT __c);
284
285	allocator_type&
286	_M_get_allocator()
287	{ return _M_dataplus; }
288
289	const allocator_type&
290	_M_get_allocator() const
291	{ return _M_dataplus; }
292
293	private:
294
295	#ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
296	// The explicit instantiations in misc-inst.cc require this due to
297	// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063
298	template<typename _Tp, bool _Requires =
299	!__are_same<_Tp, _CharT*>::__value
300	&& !__are_same<_Tp, const _CharT*>::__value
301	&& !__are_same<_Tp, iterator>::__value
302	&& !__are_same<_Tp, const_iterator>::__value>
303	struct __enable_if_not_native_iterator
304	{ typedef basic_string& __type; };
305	template<typename _Tp>
306	struct __enable_if_not_native_iterator<_Tp, false> { };
307	#endif
308
309	size_type
310	_M_check(size_type __pos, const char* __s) const
311	{
312	if (__pos > this->size())
313	__throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "("%s: __pos (which is %zu) > " "this->size() (which is %zu)" )
314	"this->size() (which is %zu)")("%s: __pos (which is %zu) > " "this->size() (which is %zu)" ),
315	__s, __pos, this->size());
316	return __pos;
317	}
318
319	void
320	_M_check_length(size_type __n1, size_type __n2, const char* __s) const
321	{
322	if (this->max_size() - (this->size() - __n1) < __n2)
323	__throw_length_error(__N(__s)(__s));
324	}
325
326
327	// NB: _M_limit doesn't check for a bad __pos value.
328	size_type
329	_M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPTnoexcept
330	{
331	const bool __testoff = __off < this->size() - __pos;
332	return __testoff ? __off : this->size() - __pos;
333	}
334
335	// True if _Rep and source do not overlap.
336	bool
337	_M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPTnoexcept
338	{
339	return (less<const _CharT*>()(__s, _M_data())
340	\|\| less<const _CharT*>()(_M_data() + this->size(), __s));
341	}
342
343	// When __n = 1 way faster than the general multichar
344	// traits_type::copy/move/assign.
345	static void
346	_S_copy(_CharT* __d, const _CharT* __s, size_type __n)
347	{
348	if (__n == 1)
349	traits_type::assign(__d, __s);
350	else
351	traits_type::copy(__d, __s, __n);
352	}
353
354	static void
355	_S_move(_CharT* __d, const _CharT* __s, size_type __n)
356	{
357	if (__n == 1)
358	traits_type::assign(__d, __s);
359	else
360	traits_type::move(__d, __s, __n);
361	}
362
363	static void
364	_S_assign(_CharT* __d, size_type __n, _CharT __c)
365	{
366	if (__n == 1)
367	traits_type::assign(*__d, __c);
368	else
369	traits_type::assign(__d, __n, __c);
370	}
371
372	// _S_copy_chars is a separate template to permit specialization
373	// to optimize for the common case of pointers as iterators.
374	template<class _Iterator>
375	static void
376	_S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
377	{
378	for (; __k1 != __k2; ++__k1, (void)++__p)
379	traits_type::assign(__p, __k1); // These types are off.
380	}
381
382	static void
383	_S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPTnoexcept
384	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
385
386	static void
387	_S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
388	_GLIBCXX_NOEXCEPTnoexcept
389	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
390
391	static void
392	_S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPTnoexcept
393	{ _S_copy(__p, __k1, __k2 - __k1); }
394
395	static void
396	_S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
397	_GLIBCXX_NOEXCEPTnoexcept
398	{ _S_copy(__p, __k1, __k2 - __k1); }
399
400	static int
401	_S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPTnoexcept
402	{
403	const difference_type __d = difference_type(__n1 - __n2);
404
405	if (__d > __gnu_cxx::__numeric_traits<int>::__max)
406	return __gnu_cxx::__numeric_traits<int>::__max;
407	else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
408	return __gnu_cxx::__numeric_traits<int>::__min;
409	else
410	return int(__d);
411	}
412
413	void
414	_M_assign(const basic_string&);
415
416	void
417	_M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
418	size_type __len2);
419
420	void
421	_M_erase(size_type __pos, size_type __n);
422
423	public:
424	// Construct/copy/destroy:
425	// NB: We overload ctors in some cases instead of using default
426	// arguments, per 17.4.4.4 para. 2 item 2.
427
428	/**
429	* @brief Default constructor creates an empty string.
430	*/
431	basic_string()
432	_GLIBCXX_NOEXCEPT_IF(is_nothrow_default_constructible<_Alloc>::value)noexcept(is_nothrow_default_constructible<_Alloc>::value )
433	: _M_dataplus(_M_local_data())
434	{ _M_set_length(0); }
435
436	/**
437	* @brief Construct an empty string using allocator @a a.
438	*/
439	explicit
440	basic_string(const _Alloc& __a) _GLIBCXX_NOEXCEPTnoexcept
441	: _M_dataplus(_M_local_data(), __a)
442	{ _M_set_length(0); }
443
444	/**
445	* @brief Construct string with copy of value of @a __str.
446	* @param __str Source string.
447	*/
448	basic_string(const basic_string& __str)
449	: _M_dataplus(_M_local_data(),
450	_Alloc_traits::_S_select_on_copy(__str._M_get_allocator()))
451	{ _M_construct(__str._M_data(), __str._M_data() + __str.length()); }
452
453	// _GLIBCXX_RESOLVE_LIB_DEFECTS
454	// 2583. no way to supply an allocator for basic_string(str, pos)
455	/**
456	* @brief Construct string as copy of a substring.
457	* @param __str Source string.
458	* @param __pos Index of first character to copy from.
459	* @param __a Allocator to use.
460	*/
461	basic_string(const basic_string& __str, size_type __pos,
462	const _Alloc& __a = _Alloc())
463	: _M_dataplus(_M_local_data(), __a)
464	{
465	const _CharT* __start = __str._M_data()
466	+ __str._M_check(__pos, "basic_string::basic_string");
467	_M_construct(__start, __start + __str._M_limit(__pos, npos));
468	}
469
470	/**
471	* @brief Construct string as copy of a substring.
472	* @param __str Source string.
473	* @param __pos Index of first character to copy from.
474	* @param __n Number of characters to copy.
475	*/
476	basic_string(const basic_string& __str, size_type __pos,
477	size_type __n)
478	: _M_dataplus(_M_local_data())
479	{
480	const _CharT* __start = __str._M_data()
481	+ __str._M_check(__pos, "basic_string::basic_string");
482	_M_construct(__start, __start + __str._M_limit(__pos, __n));
483	}
484
485	/**
486	* @brief Construct string as copy of a substring.
487	* @param __str Source string.
488	* @param __pos Index of first character to copy from.
489	* @param __n Number of characters to copy.
490	* @param __a Allocator to use.
491	*/
492	basic_string(const basic_string& __str, size_type __pos,
493	size_type __n, const _Alloc& __a)
494	: _M_dataplus(_M_local_data(), __a)
495	{
496	const _CharT* __start
497	= __str._M_data() + __str._M_check(__pos, "string::string");
498	_M_construct(__start, __start + __str._M_limit(__pos, __n));
499	}
500
501	/**
502	* @brief Construct string initialized by a character %array.
503	* @param __s Source character %array.
504	* @param __n Number of characters to copy.
505	* @param __a Allocator to use (default is default allocator).
506	*
507	* NB: @a __s must have at least @a __n characters, '\\0'
508	* has no special meaning.
509	*/
510	basic_string(const _CharT* __s, size_type __n,
511	const _Alloc& __a = _Alloc())
512	: _M_dataplus(_M_local_data(), __a)
513	{ _M_construct(__s, __s + __n); }
514
515	/**
516	* @brief Construct string as copy of a C string.
517	* @param __s Source C string.
518	* @param __a Allocator to use (default is default allocator).
519	*/
520	#if __cpp_deduction_guides201703L && ! defined _GLIBCXX_DEFINING_STRING_INSTANTIATIONS
521	// _GLIBCXX_RESOLVE_LIB_DEFECTS
522	// 3076. basic_string CTAD ambiguity
523	template<typename = _RequireAllocator<_Alloc>>
524	#endif
525	basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
526	: _M_dataplus(_M_local_data(), __a)
527	{ _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
528
529	/**
530	* @brief Construct string as multiple characters.
531	* @param __n Number of characters.
532	* @param __c Character to use.
533	* @param __a Allocator to use (default is default allocator).
534	*/
535	#if __cpp_deduction_guides201703L && ! defined _GLIBCXX_DEFINING_STRING_INSTANTIATIONS
536	// _GLIBCXX_RESOLVE_LIB_DEFECTS
537	// 3076. basic_string CTAD ambiguity
538	template<typename = _RequireAllocator<_Alloc>>
539	#endif
540	basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
541	: _M_dataplus(_M_local_data(), __a)
542	{ _M_construct(__n, __c); }
543
544	#if __cplusplus201703L >= 201103L
545	/**
546	* @brief Move construct string.
547	* @param __str Source string.
548	*
549	* The newly-created string contains the exact contents of @a __str.
550	* @a __str is a valid, but unspecified string.
551	**/
552	basic_string(basic_string&& __str) noexcept
553	: _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
554	{
555	if (__str._M_is_local())
556	{
557	traits_type::copy(_M_local_buf, __str._M_local_buf,
558	_S_local_capacity + 1);
559	}
560	else
561	{
562	_M_data(__str._M_data());
563	_M_capacity(__str._M_allocated_capacity);
564	}
565
566	// Must use _M_length() here not _M_set_length() because
567	// basic_stringbuf relies on writing into unallocated capacity so
568	// we mess up the contents if we put a '\0' in the string.
569	_M_length(__str.length());
570	__str._M_data(__str._M_local_data());
571	__str._M_set_length(0);
572	}
573
574	/**
575	* @brief Construct string from an initializer %list.
576	* @param __l std::initializer_list of characters.
577	* @param __a Allocator to use (default is default allocator).
578	*/
579	basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
580	: _M_dataplus(_M_local_data(), __a)
581	{ _M_construct(__l.begin(), __l.end()); }
582
583	basic_string(const basic_string& __str, const _Alloc& __a)
584	: _M_dataplus(_M_local_data(), __a)
585	{ _M_construct(__str.begin(), __str.end()); }
586
587	basic_string(basic_string&& __str, const _Alloc& __a)
588	noexcept(_Alloc_traits::_S_always_equal())
589	: _M_dataplus(_M_local_data(), __a)
590	{
591	if (__str._M_is_local())
592	{
593	traits_type::copy(_M_local_buf, __str._M_local_buf,
594	_S_local_capacity + 1);
595	_M_length(__str.length());
596	__str._M_set_length(0);
597	}
598	else if (_Alloc_traits::_S_always_equal()
599	\|\| __str.get_allocator() == __a)
600	{
601	_M_data(__str._M_data());
602	_M_length(__str.length());
603	_M_capacity(__str._M_allocated_capacity);
604	__str._M_data(__str._M_local_buf);
605	__str._M_set_length(0);
606	}
607	else
608	_M_construct(__str.begin(), __str.end());
609	}
610
611	#endif // C++11
612
613	/**
614	* @brief Construct string as copy of a range.
615	* @param __beg Start of range.
616	* @param __end End of range.
617	* @param __a Allocator to use (default is default allocator).
618	*/
619	#if __cplusplus201703L >= 201103L
620	template<typename _InputIterator,
621	typename = std::_RequireInputIter<_InputIterator>>
622	#else
623	template<typename _InputIterator>
624	#endif
625	basic_string(_InputIterator __beg, _InputIterator __end,
626	const _Alloc& __a = _Alloc())
627	: _M_dataplus(_M_local_data(), __a)
628	{ _M_construct(__beg, __end); }
629
630	#if __cplusplus201703L >= 201703L
631	/**
632	* @brief Construct string from a substring of a string_view.
633	* @param __t Source object convertible to string view.
634	* @param __pos The index of the first character to copy from __t.
635	* @param __n The number of characters to copy from __t.
636	* @param __a Allocator to use.
637	*/
638	template<typename _Tp, typename = _If_sv<_Tp, void>>
639	basic_string(const _Tp& __t, size_type __pos, size_type __n,
640	const _Alloc& __a = _Alloc())
641	: basic_string(_S_to_string_view(__t).substr(__pos, __n), __a) { }
642
643	/**
644	* @brief Construct string from a string_view.
645	* @param __t Source object convertible to string view.
646	* @param __a Allocator to use (default is default allocator).
647	*/
648	template<typename _Tp, typename = _If_sv<_Tp, void>>
649	explicit
650	basic_string(const _Tp& __t, const _Alloc& __a = _Alloc())
651	: basic_string(__sv_wrapper(_S_to_string_view(__t)), __a) { }
652	#endif // C++17
653
654	/**
655	* @brief Destroy the string instance.
656	*/
657	~basic_string()
658	{ _M_dispose(); }
659
660	/**
661	* @brief Assign the value of @a str to this string.
662	* @param __str Source string.
663	*/
664	basic_string&
665	operator=(const basic_string& __str)
666	{
667	return this->assign(__str);
668	}
669
670	/**
671	* @brief Copy contents of @a s into this string.
672	* @param __s Source null-terminated string.
673	*/
674	basic_string&
675	operator=(const _CharT* __s)
676	{ return this->assign(__s); }
677
678	/**
679	* @brief Set value to string of length 1.
680	* @param __c Source character.
681	*
682	* Assigning to a character makes this string length 1 and
683	* (*this)[0] == @a c.
684	*/
685	basic_string&
686	operator=(_CharT __c)
687	{
688	this->assign(1, __c);
689	return *this;
690	}
691
692	#if __cplusplus201703L >= 201103L
693	/**
694	* @brief Move assign the value of @a str to this string.
695	* @param __str Source string.
696	*
697	* The contents of @a str are moved into this string (without copying).
698	* @a str is a valid, but unspecified string.
699	**/
700	// _GLIBCXX_RESOLVE_LIB_DEFECTS
701	// 2063. Contradictory requirements for string move assignment
702	basic_string&
703	operator=(basic_string&& __str)
704	noexcept(_Alloc_traits::_S_nothrow_move())
705	{
706	if (!_M_is_local() && _Alloc_traits::_S_propagate_on_move_assign()
707	&& !_Alloc_traits::_S_always_equal()
708	&& _M_get_allocator() != __str._M_get_allocator())
709	{
710	// Destroy existing storage before replacing allocator.
711	_M_destroy(_M_allocated_capacity);
712	_M_data(_M_local_data());
713	_M_set_length(0);
714	}
715	// Replace allocator if POCMA is true.
716	std::__alloc_on_move(_M_get_allocator(), __str._M_get_allocator());
717
718	if (__str._M_is_local())
719	{
720	// We've always got room for a short string, just copy it.
721	if (__str.size())
722	this->_S_copy(_M_data(), __str._M_data(), __str.size());
723	_M_set_length(__str.size());
724	}
725	else if (_Alloc_traits::_S_propagate_on_move_assign()
726	\|\| _Alloc_traits::_S_always_equal()
727	\|\| _M_get_allocator() == __str._M_get_allocator())
728	{
729	// Just move the allocated pointer, our allocator can free it.
730	pointer __data = nullptr;
731	size_type __capacity;
732	if (!_M_is_local())
733	{
734	if (_Alloc_traits::_S_always_equal())
735	{
736	// __str can reuse our existing storage.
737	__data = _M_data();
738	__capacity = _M_allocated_capacity;
739	}
740	else // __str can't use it, so free it.
741	_M_destroy(_M_allocated_capacity);
742	}
743
744	_M_data(__str._M_data());
745	_M_length(__str.length());
746	_M_capacity(__str._M_allocated_capacity);
747	if (__data)
748	{
749	__str._M_data(__data);
750	__str._M_capacity(__capacity);
751	}
752	else
753	__str._M_data(__str._M_local_buf);
754	}
755	else // Need to do a deep copy
756	assign(__str);
757	__str.clear();
758	return *this;
759	}
760
761	/**
762	* @brief Set value to string constructed from initializer %list.
763	* @param __l std::initializer_list.
764	*/
765	basic_string&
766	operator=(initializer_list<_CharT> __l)
767	{
768	this->assign(__l.begin(), __l.size());
769	return *this;
770	}
771	#endif // C++11
772
773	#if __cplusplus201703L >= 201703L
774	/**
775	* @brief Set value to string constructed from a string_view.
776	* @param __svt An object convertible to string_view.
777	*/
778	template<typename _Tp>
779	_If_sv<_Tp, basic_string&>
780	operator=(const _Tp& __svt)
781	{ return this->assign(__svt); }
782
783	/**
784	* @brief Convert to a string_view.
785	* @return A string_view.
786	*/
787	operator __sv_type() const noexcept
788	{ return __sv_type(data(), size()); }
789	#endif // C++17
790
791	// Iterators:
792	/**
793	* Returns a read/write iterator that points to the first character in
794	* the %string.
795	*/
796	iterator
797	begin() _GLIBCXX_NOEXCEPTnoexcept
798	{ return iterator(_M_data()); }
799
800	/**
801	* Returns a read-only (constant) iterator that points to the first
802	* character in the %string.
803	*/
804	const_iterator
805	begin() const _GLIBCXX_NOEXCEPTnoexcept
806	{ return const_iterator(_M_data()); }
807
808	/**
809	* Returns a read/write iterator that points one past the last
810	* character in the %string.
811	*/
812	iterator
813	end() _GLIBCXX_NOEXCEPTnoexcept
814	{ return iterator(_M_data() + this->size()); }
815
816	/**
817	* Returns a read-only (constant) iterator that points one past the
818	* last character in the %string.
819	*/
820	const_iterator
821	end() const _GLIBCXX_NOEXCEPTnoexcept
822	{ return const_iterator(_M_data() + this->size()); }
823
824	/**
825	* Returns a read/write reverse iterator that points to the last
826	* character in the %string. Iteration is done in reverse element
827	* order.
828	*/
829	reverse_iterator
830	rbegin() _GLIBCXX_NOEXCEPTnoexcept
831	{ return reverse_iterator(this->end()); }
832
833	/**
834	* Returns a read-only (constant) reverse iterator that points
835	* to the last character in the %string. Iteration is done in
836	* reverse element order.
837	*/
838	const_reverse_iterator
839	rbegin() const _GLIBCXX_NOEXCEPTnoexcept
840	{ return const_reverse_iterator(this->end()); }
841
842	/**
843	* Returns a read/write reverse iterator that points to one before the
844	* first character in the %string. Iteration is done in reverse
845	* element order.
846	*/
847	reverse_iterator
848	rend() _GLIBCXX_NOEXCEPTnoexcept
849	{ return reverse_iterator(this->begin()); }
850
851	/**
852	* Returns a read-only (constant) reverse iterator that points
853	* to one before the first character in the %string. Iteration
854	* is done in reverse element order.
855	*/
856	const_reverse_iterator
857	rend() const _GLIBCXX_NOEXCEPTnoexcept
858	{ return const_reverse_iterator(this->begin()); }
859
860	#if __cplusplus201703L >= 201103L
861	/**
862	* Returns a read-only (constant) iterator that points to the first
863	* character in the %string.
864	*/
865	const_iterator
866	cbegin() const noexcept
867	{ return const_iterator(this->_M_data()); }
868
869	/**
870	* Returns a read-only (constant) iterator that points one past the
871	* last character in the %string.
872	*/
873	const_iterator
874	cend() const noexcept
875	{ return const_iterator(this->_M_data() + this->size()); }
876
877	/**
878	* Returns a read-only (constant) reverse iterator that points
879	* to the last character in the %string. Iteration is done in
880	* reverse element order.
881	*/
882	const_reverse_iterator
883	crbegin() const noexcept
884	{ return const_reverse_iterator(this->end()); }
885
886	/**
887	* Returns a read-only (constant) reverse iterator that points
888	* to one before the first character in the %string. Iteration
889	* is done in reverse element order.
890	*/
891	const_reverse_iterator
892	crend() const noexcept
893	{ return const_reverse_iterator(this->begin()); }
894	#endif
895
896	public:
897	// Capacity:
898	/// Returns the number of characters in the string, not including any
899	/// null-termination.
900	size_type
901	size() const _GLIBCXX_NOEXCEPTnoexcept
902	{ return _M_string_length; }
903
904	/// Returns the number of characters in the string, not including any
905	/// null-termination.
906	size_type
907	length() const _GLIBCXX_NOEXCEPTnoexcept
908	{ return _M_string_length; }
909
910	/// Returns the size() of the largest possible %string.
911	size_type
912	max_size() const _GLIBCXX_NOEXCEPTnoexcept
913	{ return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
914
915	/**
916	* @brief Resizes the %string to the specified number of characters.
917	* @param __n Number of characters the %string should contain.
918	* @param __c Character to fill any new elements.
919	*
920	* This function will %resize the %string to the specified
921	* number of characters. If the number is smaller than the
922	* %string's current size the %string is truncated, otherwise
923	* the %string is extended and new elements are %set to @a __c.
924	*/
925	void
926	resize(size_type __n, _CharT __c);
927
928	/**
929	* @brief Resizes the %string to the specified number of characters.
930	* @param __n Number of characters the %string should contain.
931	*
932	* This function will resize the %string to the specified length. If
933	* the new size is smaller than the %string's current size the %string
934	* is truncated, otherwise the %string is extended and new characters
935	* are default-constructed. For basic types such as char, this means
936	* setting them to 0.
937	*/
938	void
939	resize(size_type __n)
940	{ this->resize(__n, _CharT()); }
941
942	#if __cplusplus201703L >= 201103L
943	/// A non-binding request to reduce capacity() to size().
944	void
945	shrink_to_fit() noexcept
946	{
947	#if __cpp_exceptions
948	if (capacity() > size())
949	{
950	try
951	{ reserve(0); }
952	catch(...)
953	{ }
954	}
955	#endif
956	}
957	#endif
958
959	/**
960	* Returns the total number of characters that the %string can hold
961	* before needing to allocate more memory.
962	*/
963	size_type
964	capacity() const _GLIBCXX_NOEXCEPTnoexcept
965	{
966	return _M_is_local() ? size_type(_S_local_capacity)
967	: _M_allocated_capacity;
968	}
969
970	/**
971	* @brief Attempt to preallocate enough memory for specified number of
972	* characters.
973	* @param __res_arg Number of characters required.
974	* @throw std::length_error If @a __res_arg exceeds @c max_size().
975	*
976	* This function attempts to reserve enough memory for the
977	* %string to hold the specified number of characters. If t