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