1 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
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 implement StructuralEquivalenceContext class and helper functions
10 //  for layout matching.
11 //
12 // The structural equivalence check could have been implemented as a parallel
13 // BFS on a pair of graphs.  That must have been the original approach at the
14 // beginning.
15 // Let's consider this simple BFS algorithm from the `s` source:
16 // ```
17 // void bfs(Graph G, int s)
18 // {
19 //   Queue<Integer> queue = new Queue<Integer>();
20 //   marked[s] = true; // Mark the source
21 //   queue.enqueue(s); // and put it on the queue.
22 //   while (!q.isEmpty()) {
23 //     int v = queue.dequeue(); // Remove next vertex from the queue.
24 //     for (int w : G.adj(v))
25 //       if (!marked[w]) // For every unmarked adjacent vertex,
26 //       {
27 //         marked[w] = true;
28 //         queue.enqueue(w);
29 //       }
30 //   }
31 // }
32 // ```
33 // Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
34 // this is the `DeclsToCheck` and it's pair is in `TentativeEquivalences`.
35 // `TentativeEquivalences` also plays the role of the marking (`marked`)
36 // functionality above, we use it to check whether we've already seen a pair of
37 // nodes.
38 //
39 // We put in the elements into the queue only in the toplevel decl check
40 // function:
41 // ```
42 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
43 //                                      Decl *D1, Decl *D2);
44 // ```
45 // The `while` loop where we iterate over the children is implemented in
46 // `Finish()`.  And `Finish` is called only from the two **member** functions
47 // which check the equivalency of two Decls or two Types. ASTImporter (and
48 // other clients) call only these functions.
49 //
50 // The `static` implementation functions are called from `Finish`, these push
51 // the children nodes to the queue via `static bool
52 // IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
53 // Decl *D2)`.  So far so good, this is almost like the BFS.  However, if we
54 // let a static implementation function to call `Finish` via another **member**
55 // function that means we end up with two nested while loops each of them
56 // working on the same queue. This is wrong and nobody can reason about it's
57 // doing. Thus, static implementation functions must not call the **member**
58 // functions.
59 //
60 // So, now `TentativeEquivalences` plays two roles. It is used to store the
61 // second half of the decls which we want to compare, plus it plays a role in
62 // closing the recursion. On a long term, we could refactor structural
63 // equivalency to be more alike to the traditional BFS.
64 //
65 //===----------------------------------------------------------------------===//
66 
67 #include "clang/AST/ASTStructuralEquivalence.h"
68 #include "clang/AST/ASTContext.h"
69 #include "clang/AST/ASTDiagnostic.h"
70 #include "clang/AST/Decl.h"
71 #include "clang/AST/DeclBase.h"
72 #include "clang/AST/DeclCXX.h"
73 #include "clang/AST/DeclFriend.h"
74 #include "clang/AST/DeclObjC.h"
75 #include "clang/AST/DeclTemplate.h"
76 #include "clang/AST/NestedNameSpecifier.h"
77 #include "clang/AST/TemplateBase.h"
78 #include "clang/AST/TemplateName.h"
79 #include "clang/AST/Type.h"
80 #include "clang/Basic/ExceptionSpecificationType.h"
81 #include "clang/Basic/IdentifierTable.h"
82 #include "clang/Basic/LLVM.h"
83 #include "clang/Basic/SourceLocation.h"
84 #include "llvm/ADT/APInt.h"
85 #include "llvm/ADT/APSInt.h"
86 #include "llvm/ADT/None.h"
87 #include "llvm/ADT/Optional.h"
88 #include "llvm/Support/Casting.h"
89 #include "llvm/Support/Compiler.h"
90 #include "llvm/Support/ErrorHandling.h"
91 #include <cassert>
92 #include <utility>
93 
94 using namespace clang;
95 
96 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
97                                      QualType T1, QualType T2);
98 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
99                                      Decl *D1, Decl *D2);
100 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
101                                      const TemplateArgument &Arg1,
102                                      const TemplateArgument &Arg2);
103 
104 /// Determine structural equivalence of two expressions.
105 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
106                                      const Expr *E1, const Expr *E2) {
107   if (!E1 || !E2)
108     return E1 == E2;
109 
110   // FIXME: Actually perform a structural comparison!
111   return true;
112 }
113 
114 /// Determine whether two identifiers are equivalent.
115 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
116                                      const IdentifierInfo *Name2) {
117   if (!Name1 || !Name2)
118     return Name1 == Name2;
119 
120   return Name1->getName() == Name2->getName();
121 }
122 
123 /// Determine whether two nested-name-specifiers are equivalent.
124 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
125                                      NestedNameSpecifier *NNS1,
126                                      NestedNameSpecifier *NNS2) {
127   if (NNS1->getKind() != NNS2->getKind())
128     return false;
129 
130   NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
131                       *Prefix2 = NNS2->getPrefix();
132   if ((bool)Prefix1 != (bool)Prefix2)
133     return false;
134 
135   if (Prefix1)
136     if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
137       return false;
138 
139   switch (NNS1->getKind()) {
140   case NestedNameSpecifier::Identifier:
141     return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
142                                     NNS2->getAsIdentifier());
143   case NestedNameSpecifier::Namespace:
144     return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
145                                     NNS2->getAsNamespace());
146   case NestedNameSpecifier::NamespaceAlias:
147     return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
148                                     NNS2->getAsNamespaceAlias());
149   case NestedNameSpecifier::TypeSpec:
150   case NestedNameSpecifier::TypeSpecWithTemplate:
151     return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
152                                     QualType(NNS2->getAsType(), 0));
153   case NestedNameSpecifier::Global:
154     return true;
155   case NestedNameSpecifier::Super:
156     return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
157                                     NNS2->getAsRecordDecl());
158   }
159   return false;
160 }
161 
162 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
163                                      const TemplateName &N1,
164                                      const TemplateName &N2) {
165   if (N1.getKind() != N2.getKind())
166     return false;
167   switch (N1.getKind()) {
168   case TemplateName::Template:
169     return IsStructurallyEquivalent(Context, N1.getAsTemplateDecl(),
170                                     N2.getAsTemplateDecl());
171 
172   case TemplateName::OverloadedTemplate: {
173     OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
174                               *OS2 = N2.getAsOverloadedTemplate();
175     OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
176                                         E1 = OS1->end(), E2 = OS2->end();
177     for (; I1 != E1 && I2 != E2; ++I1, ++I2)
178       if (!IsStructurallyEquivalent(Context, *I1, *I2))
179         return false;
180     return I1 == E1 && I2 == E2;
181   }
182 
183   case TemplateName::QualifiedTemplate: {
184     QualifiedTemplateName *QN1 = N1.getAsQualifiedTemplateName(),
185                           *QN2 = N2.getAsQualifiedTemplateName();
186     return IsStructurallyEquivalent(Context, QN1->getDecl(), QN2->getDecl()) &&
187            IsStructurallyEquivalent(Context, QN1->getQualifier(),
188                                     QN2->getQualifier());
189   }
190 
191   case TemplateName::DependentTemplate: {
192     DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
193                           *DN2 = N2.getAsDependentTemplateName();
194     if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
195                                   DN2->getQualifier()))
196       return false;
197     if (DN1->isIdentifier() && DN2->isIdentifier())
198       return IsStructurallyEquivalent(DN1->getIdentifier(),
199                                       DN2->getIdentifier());
200     else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
201       return DN1->getOperator() == DN2->getOperator();
202     return false;
203   }
204 
205   case TemplateName::SubstTemplateTemplateParm: {
206     SubstTemplateTemplateParmStorage *TS1 = N1.getAsSubstTemplateTemplateParm(),
207                                      *TS2 = N2.getAsSubstTemplateTemplateParm();
208     return IsStructurallyEquivalent(Context, TS1->getParameter(),
209                                     TS2->getParameter()) &&
210            IsStructurallyEquivalent(Context, TS1->getReplacement(),
211                                     TS2->getReplacement());
212   }
213 
214   case TemplateName::SubstTemplateTemplateParmPack: {
215     SubstTemplateTemplateParmPackStorage
216         *P1 = N1.getAsSubstTemplateTemplateParmPack(),
217         *P2 = N2.getAsSubstTemplateTemplateParmPack();
218     return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
219                                     P2->getArgumentPack()) &&
220            IsStructurallyEquivalent(Context, P1->getParameterPack(),
221                                     P2->getParameterPack());
222   }
223   }
224   return false;
225 }
226 
227 /// Determine whether two template arguments are equivalent.
228 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
229                                      const TemplateArgument &Arg1,
230                                      const TemplateArgument &Arg2) {
231   if (Arg1.getKind() != Arg2.getKind())
232     return false;
233 
234   switch (Arg1.getKind()) {
235   case TemplateArgument::Null:
236     return true;
237 
238   case TemplateArgument::Type:
239     return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
240 
241   case TemplateArgument::Integral:
242     if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
243                                           Arg2.getIntegralType()))
244       return false;
245 
246     return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
247                                      Arg2.getAsIntegral());
248 
249   case TemplateArgument::Declaration:
250     return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
251 
252   case TemplateArgument::NullPtr:
253     return true; // FIXME: Is this correct?
254 
255   case TemplateArgument::Template:
256     return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
257                                     Arg2.getAsTemplate());
258 
259   case TemplateArgument::TemplateExpansion:
260     return IsStructurallyEquivalent(Context,
261                                     Arg1.getAsTemplateOrTemplatePattern(),
262                                     Arg2.getAsTemplateOrTemplatePattern());
263 
264   case TemplateArgument::Expression:
265     return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
266                                     Arg2.getAsExpr());
267 
268   case TemplateArgument::Pack:
269     if (Arg1.pack_size() != Arg2.pack_size())
270       return false;
271 
272     for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
273       if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
274                                     Arg2.pack_begin()[I]))
275         return false;
276 
277     return true;
278   }
279 
280   llvm_unreachable("Invalid template argument kind");
281 }
282 
283 /// Determine structural equivalence for the common part of array
284 /// types.
285 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
286                                           const ArrayType *Array1,
287                                           const ArrayType *Array2) {
288   if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
289                                 Array2->getElementType()))
290     return false;
291   if (Array1->getSizeModifier() != Array2->getSizeModifier())
292     return false;
293   if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
294     return false;
295 
296   return true;
297 }
298 
299 /// Determine structural equivalence based on the ExtInfo of functions. This
300 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
301 /// conventions bits but must not compare some other bits.
302 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
303                                      FunctionType::ExtInfo EI1,
304                                      FunctionType::ExtInfo EI2) {
305   // Compatible functions must have compatible calling conventions.
306   if (EI1.getCC() != EI2.getCC())
307     return false;
308 
309   // Regparm is part of the calling convention.
310   if (EI1.getHasRegParm() != EI2.getHasRegParm())
311     return false;
312   if (EI1.getRegParm() != EI2.getRegParm())
313     return false;
314 
315   if (EI1.getProducesResult() != EI2.getProducesResult())
316     return false;
317   if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
318     return false;
319   if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
320     return false;
321 
322   return true;
323 }
324 
325 /// Determine structural equivalence of two types.
326 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
327                                      QualType T1, QualType T2) {
328   if (T1.isNull() || T2.isNull())
329     return T1.isNull() && T2.isNull();
330 
331   QualType OrigT1 = T1;
332   QualType OrigT2 = T2;
333 
334   if (!Context.StrictTypeSpelling) {
335     // We aren't being strict about token-to-token equivalence of types,
336     // so map down to the canonical type.
337     T1 = Context.FromCtx.getCanonicalType(T1);
338     T2 = Context.ToCtx.getCanonicalType(T2);
339   }
340 
341   if (T1.getQualifiers() != T2.getQualifiers())
342     return false;
343 
344   Type::TypeClass TC = T1->getTypeClass();
345 
346   if (T1->getTypeClass() != T2->getTypeClass()) {
347     // Compare function types with prototypes vs. without prototypes as if
348     // both did not have prototypes.
349     if (T1->getTypeClass() == Type::FunctionProto &&
350         T2->getTypeClass() == Type::FunctionNoProto)
351       TC = Type::FunctionNoProto;
352     else if (T1->getTypeClass() == Type::FunctionNoProto &&
353              T2->getTypeClass() == Type::FunctionProto)
354       TC = Type::FunctionNoProto;
355     else
356       return false;
357   }
358 
359   switch (TC) {
360   case Type::Builtin:
361     // FIXME: Deal with Char_S/Char_U.
362     if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
363       return false;
364     break;
365 
366   case Type::Complex:
367     if (!IsStructurallyEquivalent(Context,
368                                   cast<ComplexType>(T1)->getElementType(),
369                                   cast<ComplexType>(T2)->getElementType()))
370       return false;
371     break;
372 
373   case Type::Adjusted:
374   case Type::Decayed:
375     if (!IsStructurallyEquivalent(Context,
376                                   cast<AdjustedType>(T1)->getOriginalType(),
377                                   cast<AdjustedType>(T2)->getOriginalType()))
378       return false;
379     break;
380 
381   case Type::Pointer:
382     if (!IsStructurallyEquivalent(Context,
383                                   cast<PointerType>(T1)->getPointeeType(),
384                                   cast<PointerType>(T2)->getPointeeType()))
385       return false;
386     break;
387 
388   case Type::BlockPointer:
389     if (!IsStructurallyEquivalent(Context,
390                                   cast<BlockPointerType>(T1)->getPointeeType(),
391                                   cast<BlockPointerType>(T2)->getPointeeType()))
392       return false;
393     break;
394 
395   case Type::LValueReference:
396   case Type::RValueReference: {
397     const auto *Ref1 = cast<ReferenceType>(T1);
398     const auto *Ref2 = cast<ReferenceType>(T2);
399     if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
400       return false;
401     if (Ref1->isInnerRef() != Ref2->isInnerRef())
402       return false;
403     if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
404                                   Ref2->getPointeeTypeAsWritten()))
405       return false;
406     break;
407   }
408 
409   case Type::MemberPointer: {
410     const auto *MemPtr1 = cast<MemberPointerType>(T1);
411     const auto *MemPtr2 = cast<MemberPointerType>(T2);
412     if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
413                                   MemPtr2->getPointeeType()))
414       return false;
415     if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
416                                   QualType(MemPtr2->getClass(), 0)))
417       return false;
418     break;
419   }
420 
421   case Type::ConstantArray: {
422     const auto *Array1 = cast<ConstantArrayType>(T1);
423     const auto *Array2 = cast<ConstantArrayType>(T2);
424     if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
425       return false;
426 
427     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
428       return false;
429     break;
430   }
431 
432   case Type::IncompleteArray:
433     if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
434                                        cast<ArrayType>(T2)))
435       return false;
436     break;
437 
438   case Type::VariableArray: {
439     const auto *Array1 = cast<VariableArrayType>(T1);
440     const auto *Array2 = cast<VariableArrayType>(T2);
441     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
442                                   Array2->getSizeExpr()))
443       return false;
444 
445     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
446       return false;
447 
448     break;
449   }
450 
451   case Type::DependentSizedArray: {
452     const auto *Array1 = cast<DependentSizedArrayType>(T1);
453     const auto *Array2 = cast<DependentSizedArrayType>(T2);
454     if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
455                                   Array2->getSizeExpr()))
456       return false;
457 
458     if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
459       return false;
460 
461     break;
462   }
463 
464   case Type::DependentAddressSpace: {
465     const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
466     const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
467     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
468                                   DepAddressSpace2->getAddrSpaceExpr()))
469       return false;
470     if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
471                                   DepAddressSpace2->getPointeeType()))
472       return false;
473 
474     break;
475   }
476 
477   case Type::DependentSizedExtVector: {
478     const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
479     const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
480     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
481                                   Vec2->getSizeExpr()))
482       return false;
483     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
484                                   Vec2->getElementType()))
485       return false;
486     break;
487   }
488 
489   case Type::DependentVector: {
490     const auto *Vec1 = cast<DependentVectorType>(T1);
491     const auto *Vec2 = cast<DependentVectorType>(T2);
492     if (Vec1->getVectorKind() != Vec2->getVectorKind())
493       return false;
494     if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
495                                   Vec2->getSizeExpr()))
496       return false;
497     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
498                                   Vec2->getElementType()))
499       return false;
500     break;
501   }
502 
503   case Type::Vector:
504   case Type::ExtVector: {
505     const auto *Vec1 = cast<VectorType>(T1);
506     const auto *Vec2 = cast<VectorType>(T2);
507     if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
508                                   Vec2->getElementType()))
509       return false;
510     if (Vec1->getNumElements() != Vec2->getNumElements())
511       return false;
512     if (Vec1->getVectorKind() != Vec2->getVectorKind())
513       return false;
514     break;
515   }
516 
517   case Type::FunctionProto: {
518     const auto *Proto1 = cast<FunctionProtoType>(T1);
519     const auto *Proto2 = cast<FunctionProtoType>(T2);
520 
521     if (Proto1->getNumParams() != Proto2->getNumParams())
522       return false;
523     for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
524       if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
525                                     Proto2->getParamType(I)))
526         return false;
527     }
528     if (Proto1->isVariadic() != Proto2->isVariadic())
529       return false;
530 
531     if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
532       return false;
533 
534     // Check exceptions, this information is lost in canonical type.
535     const auto *OrigProto1 =
536         cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
537     const auto *OrigProto2 =
538         cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
539     auto Spec1 = OrigProto1->getExceptionSpecType();
540     auto Spec2 = OrigProto2->getExceptionSpecType();
541 
542     if (Spec1 != Spec2)
543       return false;
544     if (Spec1 == EST_Dynamic) {
545       if (OrigProto1->getNumExceptions() != OrigProto2->getNumExceptions())
546         return false;
547       for (unsigned I = 0, N = OrigProto1->getNumExceptions(); I != N; ++I) {
548         if (!IsStructurallyEquivalent(Context, OrigProto1->getExceptionType(I),
549                                       OrigProto2->getExceptionType(I)))
550           return false;
551       }
552     } else if (isComputedNoexcept(Spec1)) {
553       if (!IsStructurallyEquivalent(Context, OrigProto1->getNoexceptExpr(),
554                                     OrigProto2->getNoexceptExpr()))
555         return false;
556     }
557 
558     // Fall through to check the bits common with FunctionNoProtoType.
559     LLVM_FALLTHROUGH;
560   }
561 
562   case Type::FunctionNoProto: {
563     const auto *Function1 = cast<FunctionType>(T1);
564     const auto *Function2 = cast<FunctionType>(T2);
565     if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
566                                   Function2->getReturnType()))
567       return false;
568     if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
569                                   Function2->getExtInfo()))
570       return false;
571     break;
572   }
573 
574   case Type::UnresolvedUsing:
575     if (!IsStructurallyEquivalent(Context,
576                                   cast<UnresolvedUsingType>(T1)->getDecl(),
577                                   cast<UnresolvedUsingType>(T2)->getDecl()))
578       return false;
579     break;
580 
581   case Type::Attributed:
582     if (!IsStructurallyEquivalent(Context,
583                                   cast<AttributedType>(T1)->getModifiedType(),
584                                   cast<AttributedType>(T2)->getModifiedType()))
585       return false;
586     if (!IsStructurallyEquivalent(
587             Context, cast<AttributedType>(T1)->getEquivalentType(),
588             cast<AttributedType>(T2)->getEquivalentType()))
589       return false;
590     break;
591 
592   case Type::Paren:
593     if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
594                                   cast<ParenType>(T2)->getInnerType()))
595       return false;
596     break;
597 
598   case Type::Typedef:
599     if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
600                                   cast<TypedefType>(T2)->getDecl()))
601       return false;
602     break;
603 
604   case Type::TypeOfExpr:
605     if (!IsStructurallyEquivalent(
606             Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
607             cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
608       return false;
609     break;
610 
611   case Type::TypeOf:
612     if (!IsStructurallyEquivalent(Context,
613                                   cast<TypeOfType>(T1)->getUnderlyingType(),
614                                   cast<TypeOfType>(T2)->getUnderlyingType()))
615       return false;
616     break;
617 
618   case Type::UnaryTransform:
619     if (!IsStructurallyEquivalent(
620             Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
621             cast<UnaryTransformType>(T2)->getUnderlyingType()))
622       return false;
623     break;
624 
625   case Type::Decltype:
626     if (!IsStructurallyEquivalent(Context,
627                                   cast<DecltypeType>(T1)->getUnderlyingExpr(),
628                                   cast<DecltypeType>(T2)->getUnderlyingExpr()))
629       return false;
630     break;
631 
632   case Type::Auto:
633     if (!IsStructurallyEquivalent(Context, cast<AutoType>(T1)->getDeducedType(),
634                                   cast<AutoType>(T2)->getDeducedType()))
635       return false;
636     break;
637 
638   case Type::DeducedTemplateSpecialization: {
639     const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
640     const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
641     if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
642                                   DT2->getTemplateName()))
643       return false;
644     if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
645                                   DT2->getDeducedType()))
646       return false;
647     break;
648   }
649 
650   case Type::Record:
651   case Type::Enum:
652     if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
653                                   cast<TagType>(T2)->getDecl()))
654       return false;
655     break;
656 
657   case Type::TemplateTypeParm: {
658     const auto *Parm1 = cast<TemplateTypeParmType>(T1);
659     const auto *Parm2 = cast<TemplateTypeParmType>(T2);
660     if (Parm1->getDepth() != Parm2->getDepth())
661       return false;
662     if (Parm1->getIndex() != Parm2->getIndex())
663       return false;
664     if (Parm1->isParameterPack() != Parm2->isParameterPack())
665       return false;
666 
667     // Names of template type parameters are never significant.
668     break;
669   }
670 
671   case Type::SubstTemplateTypeParm: {
672     const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
673     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
674     if (!IsStructurallyEquivalent(Context,
675                                   QualType(Subst1->getReplacedParameter(), 0),
676                                   QualType(Subst2->getReplacedParameter(), 0)))
677       return false;
678     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
679                                   Subst2->getReplacementType()))
680       return false;
681     break;
682   }
683 
684   case Type::SubstTemplateTypeParmPack: {
685     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
686     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
687     if (!IsStructurallyEquivalent(Context,
688                                   QualType(Subst1->getReplacedParameter(), 0),
689                                   QualType(Subst2->getReplacedParameter(), 0)))
690       return false;
691     if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
692                                   Subst2->getArgumentPack()))
693       return false;
694     break;
695   }
696 
697   case Type::TemplateSpecialization: {
698     const auto *Spec1 = cast<TemplateSpecializationType>(T1);
699     const auto *Spec2 = cast<TemplateSpecializationType>(T2);
700     if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
701                                   Spec2->getTemplateName()))
702       return false;
703     if (Spec1->getNumArgs() != Spec2->getNumArgs())
704       return false;
705     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
706       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
707                                     Spec2->getArg(I)))
708         return false;
709     }
710     break;
711   }
712 
713   case Type::Elaborated: {
714     const auto *Elab1 = cast<ElaboratedType>(T1);
715     const auto *Elab2 = cast<ElaboratedType>(T2);
716     // CHECKME: what if a keyword is ETK_None or ETK_typename ?
717     if (Elab1->getKeyword() != Elab2->getKeyword())
718       return false;
719     if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
720                                   Elab2->getQualifier()))
721       return false;
722     if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
723                                   Elab2->getNamedType()))
724       return false;
725     break;
726   }
727 
728   case Type::InjectedClassName: {
729     const auto *Inj1 = cast<InjectedClassNameType>(T1);
730     const auto *Inj2 = cast<InjectedClassNameType>(T2);
731     if (!IsStructurallyEquivalent(Context,
732                                   Inj1->getInjectedSpecializationType(),
733                                   Inj2->getInjectedSpecializationType()))
734       return false;
735     break;
736   }
737 
738   case Type::DependentName: {
739     const auto *Typename1 = cast<DependentNameType>(T1);
740     const auto *Typename2 = cast<DependentNameType>(T2);
741     if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
742                                   Typename2->getQualifier()))
743       return false;
744     if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
745                                   Typename2->getIdentifier()))
746       return false;
747 
748     break;
749   }
750 
751   case Type::DependentTemplateSpecialization: {
752     const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
753     const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
754     if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
755                                   Spec2->getQualifier()))
756       return false;
757     if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
758                                   Spec2->getIdentifier()))
759       return false;
760     if (Spec1->getNumArgs() != Spec2->getNumArgs())
761       return false;
762     for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
763       if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
764                                     Spec2->getArg(I)))
765         return false;
766     }
767     break;
768   }
769 
770   case Type::PackExpansion:
771     if (!IsStructurallyEquivalent(Context,
772                                   cast<PackExpansionType>(T1)->getPattern(),
773                                   cast<PackExpansionType>(T2)->getPattern()))
774       return false;
775     break;
776 
777   case Type::ObjCInterface: {
778     const auto *Iface1 = cast<ObjCInterfaceType>(T1);
779     const auto *Iface2 = cast<ObjCInterfaceType>(T2);
780     if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
781                                   Iface2->getDecl()))
782       return false;
783     break;
784   }
785 
786   case Type::ObjCTypeParam: {
787     const auto *Obj1 = cast<ObjCTypeParamType>(T1);
788     const auto *Obj2 = cast<ObjCTypeParamType>(T2);
789     if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
790       return false;
791 
792     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
793       return false;
794     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
795       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
796                                     Obj2->getProtocol(I)))
797         return false;
798     }
799     break;
800   }
801 
802   case Type::ObjCObject: {
803     const auto *Obj1 = cast<ObjCObjectType>(T1);
804     const auto *Obj2 = cast<ObjCObjectType>(T2);
805     if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
806                                   Obj2->getBaseType()))
807       return false;
808     if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
809       return false;
810     for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
811       if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
812                                     Obj2->getProtocol(I)))
813         return false;
814     }
815     break;
816   }
817 
818   case Type::ObjCObjectPointer: {
819     const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
820     const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
821     if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
822                                   Ptr2->getPointeeType()))
823       return false;
824     break;
825   }
826 
827   case Type::Atomic:
828     if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
829                                   cast<AtomicType>(T2)->getValueType()))
830       return false;
831     break;
832 
833   case Type::Pipe:
834     if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
835                                   cast<PipeType>(T2)->getElementType()))
836       return false;
837     break;
838   } // end switch
839 
840   return true;
841 }
842 
843 /// Determine structural equivalence of two fields.
844 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
845                                      FieldDecl *Field1, FieldDecl *Field2) {
846   const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
847 
848   // For anonymous structs/unions, match up the anonymous struct/union type
849   // declarations directly, so that we don't go off searching for anonymous
850   // types
851   if (Field1->isAnonymousStructOrUnion() &&
852       Field2->isAnonymousStructOrUnion()) {
853     RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
854     RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
855     return IsStructurallyEquivalent(Context, D1, D2);
856   }
857 
858   // Check for equivalent field names.
859   IdentifierInfo *Name1 = Field1->getIdentifier();
860   IdentifierInfo *Name2 = Field2->getIdentifier();
861   if (!::IsStructurallyEquivalent(Name1, Name2)) {
862     if (Context.Complain) {
863       Context.Diag2(Owner2->getLocation(),
864                     Context.ErrorOnTagTypeMismatch
865                         ? diag::err_odr_tag_type_inconsistent
866                         : diag::warn_odr_tag_type_inconsistent)
867           << Context.ToCtx.getTypeDeclType(Owner2);
868       Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
869           << Field2->getDeclName();
870       Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
871           << Field1->getDeclName();
872     }
873     return false;
874   }
875 
876   if (!IsStructurallyEquivalent(Context, Field1->getType(),
877                                 Field2->getType())) {
878     if (Context.Complain) {
879       Context.Diag2(Owner2->getLocation(),
880                     Context.ErrorOnTagTypeMismatch
881                         ? diag::err_odr_tag_type_inconsistent
882                         : diag::warn_odr_tag_type_inconsistent)
883           << Context.ToCtx.getTypeDeclType(Owner2);
884       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
885           << Field2->getDeclName() << Field2->getType();
886       Context.Diag1(Field1->getLocation(), diag::note_odr_field)
887           << Field1->getDeclName() << Field1->getType();
888     }
889     return false;
890   }
891 
892   if (Field1->isBitField() != Field2->isBitField()) {
893     if (Context.Complain) {
894       Context.Diag2(Owner2->getLocation(),
895                     Context.ErrorOnTagTypeMismatch
896                         ? diag::err_odr_tag_type_inconsistent
897                         : diag::warn_odr_tag_type_inconsistent)
898           << Context.ToCtx.getTypeDeclType(Owner2);
899       if (Field1->isBitField()) {
900         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
901             << Field1->getDeclName() << Field1->getType()
902             << Field1->getBitWidthValue(Context.FromCtx);
903         Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
904             << Field2->getDeclName();
905       } else {
906         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
907             << Field2->getDeclName() << Field2->getType()
908             << Field2->getBitWidthValue(Context.ToCtx);
909         Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
910             << Field1->getDeclName();
911       }
912     }
913     return false;
914   }
915 
916   if (Field1->isBitField()) {
917     // Make sure that the bit-fields are the same length.
918     unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
919     unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
920 
921     if (Bits1 != Bits2) {
922       if (Context.Complain) {
923         Context.Diag2(Owner2->getLocation(),
924                       Context.ErrorOnTagTypeMismatch
925                           ? diag::err_odr_tag_type_inconsistent
926                           : diag::warn_odr_tag_type_inconsistent)
927             << Context.ToCtx.getTypeDeclType(Owner2);
928         Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
929             << Field2->getDeclName() << Field2->getType() << Bits2;
930         Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
931             << Field1->getDeclName() << Field1->getType() << Bits1;
932       }
933       return false;
934     }
935   }
936 
937   return true;
938 }
939 
940 /// Determine structural equivalence of two methods.
941 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
942                                      CXXMethodDecl *Method1,
943                                      CXXMethodDecl *Method2) {
944   bool PropertiesEqual =
945       Method1->getDeclKind() == Method2->getDeclKind() &&
946       Method1->getRefQualifier() == Method2->getRefQualifier() &&
947       Method1->getAccess() == Method2->getAccess() &&
948       Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
949       Method1->isStatic() == Method2->isStatic() &&
950       Method1->isConst() == Method2->isConst() &&
951       Method1->isVolatile() == Method2->isVolatile() &&
952       Method1->isVirtual() == Method2->isVirtual() &&
953       Method1->isPure() == Method2->isPure() &&
954       Method1->isDefaulted() == Method2->isDefaulted() &&
955       Method1->isDeleted() == Method2->isDeleted();
956   if (!PropertiesEqual)
957     return false;
958   // FIXME: Check for 'final'.
959 
960   if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
961     auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
962     if (Constructor1->isExplicit() != Constructor2->isExplicit())
963       return false;
964   }
965 
966   if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
967     auto *Conversion2 = cast<CXXConversionDecl>(Method2);
968     if (Conversion1->isExplicit() != Conversion2->isExplicit())
969       return false;
970     if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
971                                   Conversion2->getConversionType()))
972       return false;
973   }
974 
975   const IdentifierInfo *Name1 = Method1->getIdentifier();
976   const IdentifierInfo *Name2 = Method2->getIdentifier();
977   if (!::IsStructurallyEquivalent(Name1, Name2)) {
978     return false;
979     // TODO: Names do not match, add warning like at check for FieldDecl.
980   }
981 
982   // Check the prototypes.
983   if (!::IsStructurallyEquivalent(Context,
984                                   Method1->getType(), Method2->getType()))
985     return false;
986 
987   return true;
988 }
989 
990 /// Determine structural equivalence of two records.
991 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
992                                      RecordDecl *D1, RecordDecl *D2) {
993   if (D1->isUnion() != D2->isUnion()) {
994     if (Context.Complain) {
995       Context.Diag2(D2->getLocation(),
996                     Context.ErrorOnTagTypeMismatch
997                         ? diag::err_odr_tag_type_inconsistent
998                         : diag::warn_odr_tag_type_inconsistent)
999           << Context.ToCtx.getTypeDeclType(D2);
1000       Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1001           << D1->getDeclName() << (unsigned)D1->getTagKind();
1002     }
1003     return false;
1004   }
1005 
1006   if (!D1->getDeclName() && !D2->getDeclName()) {
1007     // If both anonymous structs/unions are in a record context, make sure
1008     // they occur in the same location in the context records.
1009     if (Optional<unsigned> Index1 =
1010             StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1011       if (Optional<unsigned> Index2 =
1012               StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1013                   D2)) {
1014         if (*Index1 != *Index2)
1015           return false;
1016       }
1017     }
1018   }
1019 
1020   // If both declarations are class template specializations, we know
1021   // the ODR applies, so check the template and template arguments.
1022   const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1023   const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1024   if (Spec1 && Spec2) {
1025     // Check that the specialized templates are the same.
1026     if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1027                                   Spec2->getSpecializedTemplate()))
1028       return false;
1029 
1030     // Check that the template arguments are the same.
1031     if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1032       return false;
1033 
1034     for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1035       if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1036                                     Spec2->getTemplateArgs().get(I)))
1037         return false;
1038   }
1039   // If one is a class template specialization and the other is not, these
1040   // structures are different.
1041   else if (Spec1 || Spec2)
1042     return false;
1043 
1044   // Compare the definitions of these two records. If either or both are
1045   // incomplete (i.e. it is a forward decl), we assume that they are
1046   // equivalent.
1047   D1 = D1->getDefinition();
1048   D2 = D2->getDefinition();
1049   if (!D1 || !D2)
1050     return true;
1051 
1052   // If any of the records has external storage and we do a minimal check (or
1053   // AST import) we assume they are equivalent. (If we didn't have this
1054   // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1055   // another AST import which in turn would call the structural equivalency
1056   // check again and finally we'd have an improper result.)
1057   if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1058     if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1059       return true;
1060 
1061   // If one definition is currently being defined, we do not compare for
1062   // equality and we assume that the decls are equal.
1063   if (D1->isBeingDefined() || D2->isBeingDefined())
1064     return true;
1065 
1066   if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1067     if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1068       if (D1CXX->hasExternalLexicalStorage() &&
1069           !D1CXX->isCompleteDefinition()) {
1070         D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1071       }
1072 
1073       if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1074         if (Context.Complain) {
1075           Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
1076               << Context.ToCtx.getTypeDeclType(D2);
1077           Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1078               << D2CXX->getNumBases();
1079           Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1080               << D1CXX->getNumBases();
1081         }
1082         return false;
1083       }
1084 
1085       // Check the base classes.
1086       for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1087                                               BaseEnd1 = D1CXX->bases_end(),
1088                                               Base2 = D2CXX->bases_begin();
1089            Base1 != BaseEnd1; ++Base1, ++Base2) {
1090         if (!IsStructurallyEquivalent(Context, Base1->getType(),
1091                                       Base2->getType())) {
1092           if (Context.Complain) {
1093             Context.Diag2(D2->getLocation(),
1094                           diag::warn_odr_tag_type_inconsistent)
1095                 << Context.ToCtx.getTypeDeclType(D2);
1096             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1097                 << Base2->getType() << Base2->getSourceRange();
1098             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1099                 << Base1->getType() << Base1->getSourceRange();
1100           }
1101           return false;
1102         }
1103 
1104         // Check virtual vs. non-virtual inheritance mismatch.
1105         if (Base1->isVirtual() != Base2->isVirtual()) {
1106           if (Context.Complain) {
1107             Context.Diag2(D2->getLocation(),
1108                           diag::warn_odr_tag_type_inconsistent)
1109                 << Context.ToCtx.getTypeDeclType(D2);
1110             Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1111                 << Base2->isVirtual() << Base2->getSourceRange();
1112             Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1113                 << Base1->isVirtual() << Base1->getSourceRange();
1114           }
1115           return false;
1116         }
1117       }
1118 
1119       // Check the friends for consistency.
1120       CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1121               Friend2End = D2CXX->friend_end();
1122       for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1123                    Friend1End = D1CXX->friend_end();
1124            Friend1 != Friend1End; ++Friend1, ++Friend2) {
1125         if (Friend2 == Friend2End) {
1126           if (Context.Complain) {
1127             Context.Diag2(D2->getLocation(),
1128                           diag::warn_odr_tag_type_inconsistent)
1129                     << Context.ToCtx.getTypeDeclType(D2CXX);
1130             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1131             Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1132           }
1133           return false;
1134         }
1135 
1136         if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1137           if (Context.Complain) {
1138             Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
1139               << Context.ToCtx.getTypeDeclType(D2CXX);
1140             Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1141             Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1142           }
1143           return false;
1144         }
1145       }
1146 
1147       if (Friend2 != Friend2End) {
1148         if (Context.Complain) {
1149           Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
1150                   << Context.ToCtx.getTypeDeclType(D2);
1151           Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1152           Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1153         }
1154         return false;
1155       }
1156     } else if (D1CXX->getNumBases() > 0) {
1157       if (Context.Complain) {
1158         Context.Diag2(D2->getLocation(), diag::warn_odr_tag_type_inconsistent)
1159             << Context.ToCtx.getTypeDeclType(D2);
1160         const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1161         Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1162             << Base1->getType() << Base1->getSourceRange();
1163         Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1164       }
1165       return false;
1166     }
1167   }
1168 
1169   // Check the fields for consistency.
1170   RecordDecl::field_iterator Field2 = D2->field_begin(),
1171                              Field2End = D2->field_end();
1172   for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1173                                   Field1End = D1->field_end();
1174        Field1 != Field1End; ++Field1, ++Field2) {
1175     if (Field2 == Field2End) {
1176       if (Context.Complain) {
1177         Context.Diag2(D2->getLocation(),
1178                       Context.ErrorOnTagTypeMismatch
1179                           ? diag::err_odr_tag_type_inconsistent
1180                           : diag::warn_odr_tag_type_inconsistent)
1181             << Context.ToCtx.getTypeDeclType(D2);
1182         Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1183             << Field1->getDeclName() << Field1->getType();
1184         Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1185       }
1186       return false;
1187     }
1188 
1189     if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1190       return false;
1191   }
1192 
1193   if (Field2 != Field2End) {
1194     if (Context.Complain) {
1195       Context.Diag2(D2->getLocation(),
1196                     Context.ErrorOnTagTypeMismatch
1197                         ? diag::err_odr_tag_type_inconsistent
1198                         : diag::warn_odr_tag_type_inconsistent)
1199           << Context.ToCtx.getTypeDeclType(D2);
1200       Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1201           << Field2->getDeclName() << Field2->getType();
1202       Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1203     }
1204     return false;
1205   }
1206 
1207   return true;
1208 }
1209 
1210 /// Determine structural equivalence of two enums.
1211 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1212                                      EnumDecl *D1, EnumDecl *D2) {
1213 
1214   // Compare the definitions of these two enums. If either or both are
1215   // incomplete (i.e. forward declared), we assume that they are equivalent.
1216   D1 = D1->getDefinition();
1217   D2 = D2->getDefinition();
1218   if (!D1 || !D2)
1219     return true;
1220 
1221   EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1222                                 EC2End = D2->enumerator_end();
1223   for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1224                                      EC1End = D1->enumerator_end();
1225        EC1 != EC1End; ++EC1, ++EC2) {
1226     if (EC2 == EC2End) {
1227       if (Context.Complain) {
1228         Context.Diag2(D2->getLocation(),
1229                       Context.ErrorOnTagTypeMismatch
1230                           ? diag::err_odr_tag_type_inconsistent
1231                           : diag::warn_odr_tag_type_inconsistent)
1232             << Context.ToCtx.getTypeDeclType(D2);
1233         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1234             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1235         Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1236       }
1237       return false;
1238     }
1239 
1240     llvm::APSInt Val1 = EC1->getInitVal();
1241     llvm::APSInt Val2 = EC2->getInitVal();
1242     if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1243         !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1244       if (Context.Complain) {
1245         Context.Diag2(D2->getLocation(),
1246                       Context.ErrorOnTagTypeMismatch
1247                           ? diag::err_odr_tag_type_inconsistent
1248                           : diag::warn_odr_tag_type_inconsistent)
1249             << Context.ToCtx.getTypeDeclType(D2);
1250         Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1251             << EC2->getDeclName() << EC2->getInitVal().toString(10);
1252         Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1253             << EC1->getDeclName() << EC1->getInitVal().toString(10);
1254       }
1255       return false;
1256     }
1257   }
1258 
1259   if (EC2 != EC2End) {
1260     if (Context.Complain) {
1261       Context.Diag2(D2->getLocation(),
1262                     Context.ErrorOnTagTypeMismatch
1263                         ? diag::err_odr_tag_type_inconsistent
1264                         : diag::warn_odr_tag_type_inconsistent)
1265           << Context.ToCtx.getTypeDeclType(D2);
1266       Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1267           << EC2->getDeclName() << EC2->getInitVal().toString(10);
1268       Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1269     }
1270     return false;
1271   }
1272 
1273   return true;
1274 }
1275 
1276 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1277                                      TemplateParameterList *Params1,
1278                                      TemplateParameterList *Params2) {
1279   if (Params1->size() != Params2->size()) {
1280     if (Context.Complain) {
1281       Context.Diag2(Params2->getTemplateLoc(),
1282                     diag::err_odr_different_num_template_parameters)
1283           << Params1->size() << Params2->size();
1284       Context.Diag1(Params1->getTemplateLoc(),
1285                     diag::note_odr_template_parameter_list);
1286     }
1287     return false;
1288   }
1289 
1290   for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1291     if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1292       if (Context.Complain) {
1293         Context.Diag2(Params2->getParam(I)->getLocation(),
1294                       diag::err_odr_different_template_parameter_kind);
1295         Context.Diag1(Params1->getParam(I)->getLocation(),
1296                       diag::note_odr_template_parameter_here);
1297       }
1298       return false;
1299     }
1300 
1301     if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1302                                   Params2->getParam(I)))
1303       return false;
1304   }
1305 
1306   return true;
1307 }
1308 
1309 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1310                                      TemplateTypeParmDecl *D1,
1311                                      TemplateTypeParmDecl *D2) {
1312   if (D1->isParameterPack() != D2->isParameterPack()) {
1313     if (Context.Complain) {
1314       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1315           << D2->isParameterPack();
1316       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1317           << D1->isParameterPack();
1318     }
1319     return false;
1320   }
1321 
1322   return true;
1323 }
1324 
1325 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1326                                      NonTypeTemplateParmDecl *D1,
1327                                      NonTypeTemplateParmDecl *D2) {
1328   if (D1->isParameterPack() != D2->isParameterPack()) {
1329     if (Context.Complain) {
1330       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1331           << D2->isParameterPack();
1332       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1333           << D1->isParameterPack();
1334     }
1335     return false;
1336   }
1337 
1338   // Check types.
1339   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1340     if (Context.Complain) {
1341       Context.Diag2(D2->getLocation(),
1342                     diag::err_odr_non_type_parameter_type_inconsistent)
1343           << D2->getType() << D1->getType();
1344       Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1345           << D1->getType();
1346     }
1347     return false;
1348   }
1349 
1350   return true;
1351 }
1352 
1353 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1354                                      TemplateTemplateParmDecl *D1,
1355                                      TemplateTemplateParmDecl *D2) {
1356   if (D1->isParameterPack() != D2->isParameterPack()) {
1357     if (Context.Complain) {
1358       Context.Diag2(D2->getLocation(), diag::err_odr_parameter_pack_non_pack)
1359           << D2->isParameterPack();
1360       Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1361           << D1->isParameterPack();
1362     }
1363     return false;
1364   }
1365 
1366   // Check template parameter lists.
1367   return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1368                                   D2->getTemplateParameters());
1369 }
1370 
1371 static bool IsTemplateDeclCommonStructurallyEquivalent(
1372     StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1373   if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1374     return false;
1375   if (!D1->getIdentifier()) // Special name
1376     if (D1->getNameAsString() != D2->getNameAsString())
1377       return false;
1378   return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1379                                   D2->getTemplateParameters());
1380 }
1381 
1382 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1383                                      ClassTemplateDecl *D1,
1384                                      ClassTemplateDecl *D2) {
1385   // Check template parameters.
1386   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1387     return false;
1388 
1389   // Check the templated declaration.
1390   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1391                                   D2->getTemplatedDecl());
1392 }
1393 
1394 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1395                                      FunctionTemplateDecl *D1,
1396                                      FunctionTemplateDecl *D2) {
1397   // Check template parameters.
1398   if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1399     return false;
1400 
1401   // Check the templated declaration.
1402   return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1403                                   D2->getTemplatedDecl()->getType());
1404 }
1405 
1406 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1407                                      FriendDecl *D1, FriendDecl *D2) {
1408   if ((D1->getFriendType() && D2->getFriendDecl()) ||
1409       (D1->getFriendDecl() && D2->getFriendType())) {
1410       return false;
1411   }
1412   if (D1->getFriendType() && D2->getFriendType())
1413     return IsStructurallyEquivalent(Context,
1414                                     D1->getFriendType()->getType(),
1415                                     D2->getFriendType()->getType());
1416   if (D1->getFriendDecl() && D2->getFriendDecl())
1417     return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1418                                     D2->getFriendDecl());
1419   return false;
1420 }
1421 
1422 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1423                                      FunctionDecl *D1, FunctionDecl *D2) {
1424   // FIXME: Consider checking for function attributes as well.
1425   if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1426     return false;
1427 
1428   return true;
1429 }
1430 
1431 /// Determine structural equivalence of two declarations.
1432 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1433                                      Decl *D1, Decl *D2) {
1434   // FIXME: Check for known structural equivalences via a callback of some sort.
1435 
1436   // Check whether we already know that these two declarations are not
1437   // structurally equivalent.
1438   if (Context.NonEquivalentDecls.count(
1439           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl())))
1440     return false;
1441 
1442   // Determine whether we've already produced a tentative equivalence for D1.
1443   Decl *&EquivToD1 = Context.TentativeEquivalences[D1->getCanonicalDecl()];
1444   if (EquivToD1)
1445     return EquivToD1 == D2->getCanonicalDecl();
1446 
1447   // Produce a tentative equivalence D1 <-> D2, which will be checked later.
1448   EquivToD1 = D2->getCanonicalDecl();
1449   Context.DeclsToCheck.push_back(D1->getCanonicalDecl());
1450   return true;
1451 }
1452 
1453 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1454                                                       unsigned DiagID) {
1455   assert(Complain && "Not allowed to complain");
1456   if (LastDiagFromC2)
1457     FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1458   LastDiagFromC2 = false;
1459   return FromCtx.getDiagnostics().Report(Loc, DiagID);
1460 }
1461 
1462 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1463                                                       unsigned DiagID) {
1464   assert(Complain && "Not allowed to complain");
1465   if (!LastDiagFromC2)
1466     ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1467   LastDiagFromC2 = true;
1468   return ToCtx.getDiagnostics().Report(Loc, DiagID);
1469 }
1470 
1471 Optional<unsigned>
1472 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1473   ASTContext &Context = Anon->getASTContext();
1474   QualType AnonTy = Context.getRecordType(Anon);
1475 
1476   const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1477   if (!Owner)
1478     return None;
1479 
1480   unsigned Index = 0;
1481   for (const auto *D : Owner->noload_decls()) {
1482     const auto *F = dyn_cast<FieldDecl>(D);
1483     if (!F)
1484       continue;
1485 
1486     if (F->isAnonymousStructOrUnion()) {
1487       if (Context.hasSameType(F->getType(), AnonTy))
1488         break;
1489       ++Index;
1490       continue;
1491     }
1492 
1493     // If the field looks like this:
1494     // struct { ... } A;
1495     QualType FieldType = F->getType();
1496     // In case of nested structs.
1497     while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1498       FieldType = ElabType->getNamedType();
1499 
1500     if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1501       const RecordDecl *RecDecl = RecType->getDecl();
1502       if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1503         if (Context.hasSameType(FieldType, AnonTy))
1504           break;
1505         ++Index;
1506         continue;
1507       }
1508     }
1509   }
1510 
1511   return Index;
1512 }
1513 
1514 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1515 
1516   // Ensure that the implementation functions (all static functions in this TU)
1517   // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1518   // because that will wreak havoc the internal state (DeclsToCheck and
1519   // TentativeEquivalences members) and can cause faulty behaviour. For
1520   // instance, some leaf declarations can be stated and cached as inequivalent
1521   // as a side effect of one inequivalent element in the DeclsToCheck list.
1522   assert(DeclsToCheck.empty());
1523   assert(TentativeEquivalences.empty());
1524 
1525   if (!::IsStructurallyEquivalent(*this, D1, D2))
1526     return false;
1527 
1528   return !Finish();
1529 }
1530 
1531 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
1532   assert(DeclsToCheck.empty());
1533   assert(TentativeEquivalences.empty());
1534   if (!::IsStructurallyEquivalent(*this, T1, T2))
1535     return false;
1536 
1537   return !Finish();
1538 }
1539 
1540 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
1541   // Check for equivalent described template.
1542   TemplateDecl *Template1 = D1->getDescribedTemplate();
1543   TemplateDecl *Template2 = D2->getDescribedTemplate();
1544   if ((Template1 != nullptr) != (Template2 != nullptr))
1545     return false;
1546   if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1547     return false;
1548 
1549   // FIXME: Move check for identifier names into this function.
1550 
1551   return true;
1552 }
1553 
1554 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
1555     Decl *D1, Decl *D2) {
1556   // FIXME: Switch on all declaration kinds. For now, we're just going to
1557   // check the obvious ones.
1558   if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1559     if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1560       // Check for equivalent structure names.
1561       IdentifierInfo *Name1 = Record1->getIdentifier();
1562       if (!Name1 && Record1->getTypedefNameForAnonDecl())
1563         Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1564       IdentifierInfo *Name2 = Record2->getIdentifier();
1565       if (!Name2 && Record2->getTypedefNameForAnonDecl())
1566         Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1567       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1568           !::IsStructurallyEquivalent(*this, Record1, Record2))
1569         return false;
1570     } else {
1571       // Record/non-record mismatch.
1572       return false;
1573     }
1574   } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1575     if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1576       // Check for equivalent enum names.
1577       IdentifierInfo *Name1 = Enum1->getIdentifier();
1578       if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1579         Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1580       IdentifierInfo *Name2 = Enum2->getIdentifier();
1581       if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1582         Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1583       if (!::IsStructurallyEquivalent(Name1, Name2) ||
1584           !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1585         return false;
1586     } else {
1587       // Enum/non-enum mismatch
1588       return false;
1589     }
1590   } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1591     if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1592       if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1593                                       Typedef2->getIdentifier()) ||
1594           !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1595                                       Typedef2->getUnderlyingType()))
1596         return false;
1597     } else {
1598       // Typedef/non-typedef mismatch.
1599       return false;
1600     }
1601   } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1602     if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1603       if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1604                                       ClassTemplate2))
1605         return false;
1606     } else {
1607       // Class template/non-class-template mismatch.
1608       return false;
1609     }
1610   } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1611     if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1612       if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1613                                       FunctionTemplate2))
1614         return false;
1615     } else {
1616       // Class template/non-class-template mismatch.
1617       return false;
1618     }
1619   } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1620     if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1621       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1622         return false;
1623     } else {
1624       // Kind mismatch.
1625       return false;
1626     }
1627   } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1628     if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1629       if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1630         return false;
1631     } else {
1632       // Kind mismatch.
1633       return false;
1634     }
1635   } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1636     if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1637       if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1638         return false;
1639     } else {
1640       // Kind mismatch.
1641       return false;
1642     }
1643   } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1644     if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1645       if (!::IsStructurallyEquivalent(*this, MD1, MD2))
1646         return false;
1647     } else {
1648       // Kind mismatch.
1649       return false;
1650     }
1651   } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1652     if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1653       if (FD1->isOverloadedOperator()) {
1654         if (!FD2->isOverloadedOperator())
1655           return false;
1656         if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1657           return false;
1658       }
1659       if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1660                                       FD2->getIdentifier()))
1661         return false;
1662       if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1663         return false;
1664     } else {
1665       // Kind mismatch.
1666       return false;
1667     }
1668   } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1669     if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1670         if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1671           return false;
1672     } else {
1673       // Kind mismatch.
1674       return false;
1675     }
1676   }
1677 
1678   return true;
1679 }
1680 
1681 bool StructuralEquivalenceContext::Finish() {
1682   while (!DeclsToCheck.empty()) {
1683     // Check the next declaration.
1684     Decl *D1 = DeclsToCheck.front();
1685     DeclsToCheck.pop_front();
1686 
1687     Decl *D2 = TentativeEquivalences[D1];
1688     assert(D2 && "Unrecorded tentative equivalence?");
1689 
1690     bool Equivalent =
1691         CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1692 
1693     if (!Equivalent) {
1694       // Note that these two declarations are not equivalent (and we already
1695       // know about it).
1696       NonEquivalentDecls.insert(
1697           std::make_pair(D1->getCanonicalDecl(), D2->getCanonicalDecl()));
1698       return true;
1699     }
1700   }
1701 
1702   return false;
1703 }
1704