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