1 //===- TemplateDeduction.h - C++ template argument deduction ----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file provides types used with Sema's template argument deduction
10 // routines.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_SEMA_TEMPLATEDEDUCTION_H
15 #define LLVM_CLANG_SEMA_TEMPLATEDEDUCTION_H
16 
17 #include "clang/Sema/Ownership.h"
18 #include "clang/Sema/SemaConcept.h"
19 #include "clang/AST/ASTConcept.h"
20 #include "clang/AST/DeclAccessPair.h"
21 #include "clang/AST/DeclTemplate.h"
22 #include "clang/AST/TemplateBase.h"
23 #include "clang/Basic/PartialDiagnostic.h"
24 #include "clang/Basic/SourceLocation.h"
25 #include "llvm/ADT/Optional.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include <cassert>
28 #include <cstddef>
29 #include <utility>
30 
31 namespace clang {
32 
33 class Decl;
34 struct DeducedPack;
35 class Sema;
36 
37 namespace sema {
38 
39 /// Provides information about an attempted template argument
40 /// deduction, whose success or failure was described by a
41 /// TemplateDeductionResult value.
42 class TemplateDeductionInfo {
43   /// The deduced template argument list.
44   TemplateArgumentList *Deduced = nullptr;
45 
46   /// The source location at which template argument
47   /// deduction is occurring.
48   SourceLocation Loc;
49 
50   /// Have we suppressed an error during deduction?
51   bool HasSFINAEDiagnostic = false;
52 
53   /// The template parameter depth for which we're performing deduction.
54   unsigned DeducedDepth;
55 
56   /// The number of parameters with explicitly-specified template arguments,
57   /// up to and including the partially-specified pack (if any).
58   unsigned ExplicitArgs = 0;
59 
60   /// Warnings (and follow-on notes) that were suppressed due to
61   /// SFINAE while performing template argument deduction.
62   SmallVector<PartialDiagnosticAt, 4> SuppressedDiagnostics;
63 
64 public:
65   TemplateDeductionInfo(SourceLocation Loc, unsigned DeducedDepth = 0)
66       : Loc(Loc), DeducedDepth(DeducedDepth) {}
67   TemplateDeductionInfo(const TemplateDeductionInfo &) = delete;
68   TemplateDeductionInfo &operator=(const TemplateDeductionInfo &) = delete;
69 
70   enum ForBaseTag { ForBase };
71   /// Create temporary template deduction info for speculatively deducing
72   /// against a base class of an argument's type.
73   TemplateDeductionInfo(ForBaseTag, const TemplateDeductionInfo &Info)
74       : Deduced(Info.Deduced), Loc(Info.Loc), DeducedDepth(Info.DeducedDepth),
75         ExplicitArgs(Info.ExplicitArgs) {}
76 
77   /// Returns the location at which template argument is
78   /// occurring.
79   SourceLocation getLocation() const {
80     return Loc;
81   }
82 
83   /// The depth of template parameters for which deduction is being
84   /// performed.
85   unsigned getDeducedDepth() const {
86     return DeducedDepth;
87   }
88 
89   /// Get the number of explicitly-specified arguments.
90   unsigned getNumExplicitArgs() const {
91     return ExplicitArgs;
92   }
93 
94   /// Take ownership of the deduced template argument list.
95   TemplateArgumentList *take() {
96     TemplateArgumentList *Result = Deduced;
97     Deduced = nullptr;
98     return Result;
99   }
100 
101   /// Take ownership of the SFINAE diagnostic.
102   void takeSFINAEDiagnostic(PartialDiagnosticAt &PD) {
103     assert(HasSFINAEDiagnostic);
104     PD.first = SuppressedDiagnostics.front().first;
105     PD.second.swap(SuppressedDiagnostics.front().second);
106     clearSFINAEDiagnostic();
107   }
108 
109   /// Discard any SFINAE diagnostics.
110   void clearSFINAEDiagnostic() {
111     SuppressedDiagnostics.clear();
112     HasSFINAEDiagnostic = false;
113   }
114 
115   /// Peek at the SFINAE diagnostic.
116   const PartialDiagnosticAt &peekSFINAEDiagnostic() const {
117     assert(HasSFINAEDiagnostic);
118     return SuppressedDiagnostics.front();
119   }
120 
121   /// Provide an initial template argument list that contains the
122   /// explicitly-specified arguments.
123   void setExplicitArgs(TemplateArgumentList *NewDeduced) {
124     Deduced = NewDeduced;
125     ExplicitArgs = Deduced->size();
126   }
127 
128   /// Provide a new template argument list that contains the
129   /// results of template argument deduction.
130   void reset(TemplateArgumentList *NewDeduced) {
131     Deduced = NewDeduced;
132   }
133 
134   /// Is a SFINAE diagnostic available?
135   bool hasSFINAEDiagnostic() const {
136     return HasSFINAEDiagnostic;
137   }
138 
139   /// Set the diagnostic which caused the SFINAE failure.
140   void addSFINAEDiagnostic(SourceLocation Loc, PartialDiagnostic PD) {
141     // Only collect the first diagnostic.
142     if (HasSFINAEDiagnostic)
143       return;
144     SuppressedDiagnostics.clear();
145     SuppressedDiagnostics.emplace_back(Loc, std::move(PD));
146     HasSFINAEDiagnostic = true;
147   }
148 
149   /// Add a new diagnostic to the set of diagnostics
150   void addSuppressedDiagnostic(SourceLocation Loc,
151                                PartialDiagnostic PD) {
152     if (HasSFINAEDiagnostic)
153       return;
154     SuppressedDiagnostics.emplace_back(Loc, std::move(PD));
155   }
156 
157   /// Iterator over the set of suppressed diagnostics.
158   using diag_iterator = SmallVectorImpl<PartialDiagnosticAt>::const_iterator;
159 
160   /// Returns an iterator at the beginning of the sequence of suppressed
161   /// diagnostics.
162   diag_iterator diag_begin() const { return SuppressedDiagnostics.begin(); }
163 
164   /// Returns an iterator at the end of the sequence of suppressed
165   /// diagnostics.
166   diag_iterator diag_end() const { return SuppressedDiagnostics.end(); }
167 
168   /// The template parameter to which a template argument
169   /// deduction failure refers.
170   ///
171   /// Depending on the result of template argument deduction, this
172   /// template parameter may have different meanings:
173   ///
174   ///   TDK_Incomplete: this is the first template parameter whose
175   ///   corresponding template argument was not deduced.
176   ///
177   ///   TDK_IncompletePack: this is the expanded parameter pack for
178   ///   which we deduced too few arguments.
179   ///
180   ///   TDK_Inconsistent: this is the template parameter for which
181   ///   two different template argument values were deduced.
182   TemplateParameter Param;
183 
184   /// The first template argument to which the template
185   /// argument deduction failure refers.
186   ///
187   /// Depending on the result of the template argument deduction,
188   /// this template argument may have different meanings:
189   ///
190   ///   TDK_IncompletePack: this is the number of arguments we deduced
191   ///   for the pack.
192   ///
193   ///   TDK_Inconsistent: this argument is the first value deduced
194   ///   for the corresponding template parameter.
195   ///
196   ///   TDK_SubstitutionFailure: this argument is the template
197   ///   argument we were instantiating when we encountered an error.
198   ///
199   ///   TDK_DeducedMismatch: this is the parameter type, after substituting
200   ///   deduced arguments.
201   ///
202   ///   TDK_NonDeducedMismatch: this is the component of the 'parameter'
203   ///   of the deduction, directly provided in the source code.
204   TemplateArgument FirstArg;
205 
206   /// The second template argument to which the template
207   /// argument deduction failure refers.
208   ///
209   ///   TDK_Inconsistent: this argument is the second value deduced
210   ///   for the corresponding template parameter.
211   ///
212   ///   TDK_DeducedMismatch: this is the (adjusted) call argument type.
213   ///
214   ///   TDK_NonDeducedMismatch: this is the mismatching component of the
215   ///   'argument' of the deduction, from which we are deducing arguments.
216   ///
217   /// FIXME: Finish documenting this.
218   TemplateArgument SecondArg;
219 
220   /// The index of the function argument that caused a deduction
221   /// failure.
222   ///
223   ///   TDK_DeducedMismatch: this is the index of the argument that had a
224   ///   different argument type from its substituted parameter type.
225   unsigned CallArgIndex = 0;
226 
227   /// Information on packs that we're currently expanding.
228   ///
229   /// FIXME: This should be kept internal to SemaTemplateDeduction.
230   SmallVector<DeducedPack *, 8> PendingDeducedPacks;
231 
232   /// \brief The constraint satisfaction details resulting from the associated
233   /// constraints satisfaction tests.
234   ConstraintSatisfaction AssociatedConstraintsSatisfaction;
235 };
236 
237 } // namespace sema
238 
239 /// A structure used to record information about a failed
240 /// template argument deduction, for diagnosis.
241 struct DeductionFailureInfo {
242   /// A Sema::TemplateDeductionResult.
243   unsigned Result : 8;
244 
245   /// Indicates whether a diagnostic is stored in Diagnostic.
246   unsigned HasDiagnostic : 1;
247 
248   /// Opaque pointer containing additional data about
249   /// this deduction failure.
250   void *Data;
251 
252   /// A diagnostic indicating why deduction failed.
253   alignas(PartialDiagnosticAt) char Diagnostic[sizeof(PartialDiagnosticAt)];
254 
255   /// Retrieve the diagnostic which caused this deduction failure,
256   /// if any.
257   PartialDiagnosticAt *getSFINAEDiagnostic();
258 
259   /// Retrieve the template parameter this deduction failure
260   /// refers to, if any.
261   TemplateParameter getTemplateParameter();
262 
263   /// Retrieve the template argument list associated with this
264   /// deduction failure, if any.
265   TemplateArgumentList *getTemplateArgumentList();
266 
267   /// Return the first template argument this deduction failure
268   /// refers to, if any.
269   const TemplateArgument *getFirstArg();
270 
271   /// Return the second template argument this deduction failure
272   /// refers to, if any.
273   const TemplateArgument *getSecondArg();
274 
275   /// Return the index of the call argument that this deduction
276   /// failure refers to, if any.
277   llvm::Optional<unsigned> getCallArgIndex();
278 
279   /// Free any memory associated with this deduction failure.
280   void Destroy();
281 };
282 
283 /// TemplateSpecCandidate - This is a generalization of OverloadCandidate
284 /// which keeps track of template argument deduction failure info, when
285 /// handling explicit specializations (and instantiations) of templates
286 /// beyond function overloading.
287 /// For now, assume that the candidates are non-matching specializations.
288 /// TODO: In the future, we may need to unify/generalize this with
289 /// OverloadCandidate.
290 struct TemplateSpecCandidate {
291   /// The declaration that was looked up, together with its access.
292   /// Might be a UsingShadowDecl, but usually a FunctionTemplateDecl.
293   DeclAccessPair FoundDecl;
294 
295   /// Specialization - The actual specialization that this candidate
296   /// represents. When NULL, this may be a built-in candidate.
297   Decl *Specialization;
298 
299   /// Template argument deduction info
300   DeductionFailureInfo DeductionFailure;
301 
302   void set(DeclAccessPair Found, Decl *Spec, DeductionFailureInfo Info) {
303     FoundDecl = Found;
304     Specialization = Spec;
305     DeductionFailure = Info;
306   }
307 
308   /// Diagnose a template argument deduction failure.
309   void NoteDeductionFailure(Sema &S, bool ForTakingAddress);
310 };
311 
312 /// TemplateSpecCandidateSet - A set of generalized overload candidates,
313 /// used in template specializations.
314 /// TODO: In the future, we may need to unify/generalize this with
315 /// OverloadCandidateSet.
316 class TemplateSpecCandidateSet {
317   SmallVector<TemplateSpecCandidate, 16> Candidates;
318   SourceLocation Loc;
319 
320   // Stores whether we're taking the address of these candidates. This helps us
321   // produce better error messages when dealing with the pass_object_size
322   // attribute on parameters.
323   bool ForTakingAddress;
324 
325   void destroyCandidates();
326 
327 public:
328   TemplateSpecCandidateSet(SourceLocation Loc, bool ForTakingAddress = false)
329       : Loc(Loc), ForTakingAddress(ForTakingAddress) {}
330   TemplateSpecCandidateSet(const TemplateSpecCandidateSet &) = delete;
331   TemplateSpecCandidateSet &
332   operator=(const TemplateSpecCandidateSet &) = delete;
333   ~TemplateSpecCandidateSet() { destroyCandidates(); }
334 
335   SourceLocation getLocation() const { return Loc; }
336 
337   /// Clear out all of the candidates.
338   /// TODO: This may be unnecessary.
339   void clear();
340 
341   using iterator = SmallVector<TemplateSpecCandidate, 16>::iterator;
342 
343   iterator begin() { return Candidates.begin(); }
344   iterator end() { return Candidates.end(); }
345 
346   size_t size() const { return Candidates.size(); }
347   bool empty() const { return Candidates.empty(); }
348 
349   /// Add a new candidate with NumConversions conversion sequence slots
350   /// to the overload set.
351   TemplateSpecCandidate &addCandidate() {
352     Candidates.emplace_back();
353     return Candidates.back();
354   }
355 
356   void NoteCandidates(Sema &S, SourceLocation Loc);
357 
358   void NoteCandidates(Sema &S, SourceLocation Loc) const {
359     const_cast<TemplateSpecCandidateSet *>(this)->NoteCandidates(S, Loc);
360   }
361 };
362 
363 } // namespace clang
364 
365 #endif // LLVM_CLANG_SEMA_TEMPLATEDEDUCTION_H
366