Coverage Report

Created: 2019-07-24 05:18

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