1//===--- NestedNameSpecifier.cpp - C++ nested name specifiers -----*- C++ -*-=//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines the NestedNameSpecifier class, which represents
11//  a C++ nested-name-specifier.
12//
13//===----------------------------------------------------------------------===//
14#include "clang/AST/NestedNameSpecifier.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/Decl.h"
17#include "clang/AST/DeclCXX.h"
18#include "clang/AST/PrettyPrinter.h"
19#include "clang/AST/Type.h"
20#include "clang/AST/TypeLoc.h"
21#include "llvm/Support/AlignOf.h"
22#include "llvm/Support/raw_ostream.h"
23#include <cassert>
24
25using namespace clang;
26
27NestedNameSpecifier *
28NestedNameSpecifier::FindOrInsert(const ASTContext &Context,
29                                  const NestedNameSpecifier &Mockup) {
30  llvm::FoldingSetNodeID ID;
31  Mockup.Profile(ID);
32
33  void *InsertPos = nullptr;
34  NestedNameSpecifier *NNS
35    = Context.NestedNameSpecifiers.FindNodeOrInsertPos(ID, InsertPos);
36  if (!NNS) {
37    NNS = new (Context, llvm::alignOf<NestedNameSpecifier>())
38        NestedNameSpecifier(Mockup);
39    Context.NestedNameSpecifiers.InsertNode(NNS, InsertPos);
40  }
41
42  return NNS;
43}
44
45NestedNameSpecifier *
46NestedNameSpecifier::Create(const ASTContext &Context,
47                            NestedNameSpecifier *Prefix, IdentifierInfo *II) {
48  assert(II && "Identifier cannot be NULL");
49  assert((!Prefix || Prefix->isDependent()) && "Prefix must be dependent");
50
51  NestedNameSpecifier Mockup;
52  Mockup.Prefix.setPointer(Prefix);
53  Mockup.Prefix.setInt(StoredIdentifier);
54  Mockup.Specifier = II;
55  return FindOrInsert(Context, Mockup);
56}
57
58NestedNameSpecifier *
59NestedNameSpecifier::Create(const ASTContext &Context,
60                            NestedNameSpecifier *Prefix,
61                            const NamespaceDecl *NS) {
62  assert(NS && "Namespace cannot be NULL");
63  assert((!Prefix ||
64          (Prefix->getAsType() == nullptr &&
65           Prefix->getAsIdentifier() == nullptr)) &&
66         "Broken nested name specifier");
67  NestedNameSpecifier Mockup;
68  Mockup.Prefix.setPointer(Prefix);
69  Mockup.Prefix.setInt(StoredNamespaceOrAlias);
70  Mockup.Specifier = const_cast<NamespaceDecl *>(NS);
71  return FindOrInsert(Context, Mockup);
72}
73
74NestedNameSpecifier *
75NestedNameSpecifier::Create(const ASTContext &Context,
76                            NestedNameSpecifier *Prefix,
77                            NamespaceAliasDecl *Alias) {
78  assert(Alias && "Namespace alias cannot be NULL");
79  assert((!Prefix ||
80          (Prefix->getAsType() == nullptr &&
81           Prefix->getAsIdentifier() == nullptr)) &&
82         "Broken nested name specifier");
83  NestedNameSpecifier Mockup;
84  Mockup.Prefix.setPointer(Prefix);
85  Mockup.Prefix.setInt(StoredNamespaceOrAlias);
86  Mockup.Specifier = Alias;
87  return FindOrInsert(Context, Mockup);
88}
89
90NestedNameSpecifier *
91NestedNameSpecifier::Create(const ASTContext &Context,
92                            NestedNameSpecifier *Prefix,
93                            bool Template, const Type *T) {
94  assert(T && "Type cannot be NULL");
95  NestedNameSpecifier Mockup;
96  Mockup.Prefix.setPointer(Prefix);
97  Mockup.Prefix.setInt(Template? StoredTypeSpecWithTemplate : StoredTypeSpec);
98  Mockup.Specifier = const_cast<Type*>(T);
99  return FindOrInsert(Context, Mockup);
100}
101
102NestedNameSpecifier *
103NestedNameSpecifier::Create(const ASTContext &Context, IdentifierInfo *II) {
104  assert(II && "Identifier cannot be NULL");
105  NestedNameSpecifier Mockup;
106  Mockup.Prefix.setPointer(nullptr);
107  Mockup.Prefix.setInt(StoredIdentifier);
108  Mockup.Specifier = II;
109  return FindOrInsert(Context, Mockup);
110}
111
112NestedNameSpecifier *
113NestedNameSpecifier::GlobalSpecifier(const ASTContext &Context) {
114  if (!Context.GlobalNestedNameSpecifier)
115    Context.GlobalNestedNameSpecifier =
116        new (Context, llvm::alignOf<NestedNameSpecifier>())
117            NestedNameSpecifier();
118  return Context.GlobalNestedNameSpecifier;
119}
120
121NestedNameSpecifier::SpecifierKind NestedNameSpecifier::getKind() const {
122  if (!Specifier)
123    return Global;
124
125  switch (Prefix.getInt()) {
126  case StoredIdentifier:
127    return Identifier;
128
129  case StoredNamespaceOrAlias:
130    return isa<NamespaceDecl>(static_cast<NamedDecl *>(Specifier))? Namespace
131                                                            : NamespaceAlias;
132
133  case StoredTypeSpec:
134    return TypeSpec;
135
136  case StoredTypeSpecWithTemplate:
137    return TypeSpecWithTemplate;
138  }
139
140  llvm_unreachable("Invalid NNS Kind!");
141}
142
143/// \brief Retrieve the namespace stored in this nested name
144/// specifier.
145NamespaceDecl *NestedNameSpecifier::getAsNamespace() const {
146  if (Prefix.getInt() == StoredNamespaceOrAlias)
147    return dyn_cast<NamespaceDecl>(static_cast<NamedDecl *>(Specifier));
148
149  return nullptr;
150}
151
152/// \brief Retrieve the namespace alias stored in this nested name
153/// specifier.
154NamespaceAliasDecl *NestedNameSpecifier::getAsNamespaceAlias() const {
155  if (Prefix.getInt() == StoredNamespaceOrAlias)
156    return dyn_cast<NamespaceAliasDecl>(static_cast<NamedDecl *>(Specifier));
157
158  return nullptr;
159}
160
161
162/// \brief Whether this nested name specifier refers to a dependent
163/// type or not.
164bool NestedNameSpecifier::isDependent() const {
165  switch (getKind()) {
166  case Identifier:
167    // Identifier specifiers always represent dependent types
168    return true;
169
170  case Namespace:
171  case NamespaceAlias:
172  case Global:
173    return false;
174
175  case TypeSpec:
176  case TypeSpecWithTemplate:
177    return getAsType()->isDependentType();
178  }
179
180  llvm_unreachable("Invalid NNS Kind!");
181}
182
183/// \brief Whether this nested name specifier refers to a dependent
184/// type or not.
185bool NestedNameSpecifier::isInstantiationDependent() const {
186  switch (getKind()) {
187  case Identifier:
188    // Identifier specifiers always represent dependent types
189    return true;
190
191  case Namespace:
192  case NamespaceAlias:
193  case Global:
194    return false;
195
196  case TypeSpec:
197  case TypeSpecWithTemplate:
198    return getAsType()->isInstantiationDependentType();
199  }
200
201  llvm_unreachable("Invalid NNS Kind!");
202}
203
204bool NestedNameSpecifier::containsUnexpandedParameterPack() const {
205  switch (getKind()) {
206  case Identifier:
207    return getPrefix() && getPrefix()->containsUnexpandedParameterPack();
208
209  case Namespace:
210  case NamespaceAlias:
211  case Global:
212    return false;
213
214  case TypeSpec:
215  case TypeSpecWithTemplate:
216    return getAsType()->containsUnexpandedParameterPack();
217  }
218
219  llvm_unreachable("Invalid NNS Kind!");
220}
221
222/// \brief Print this nested name specifier to the given output
223/// stream.
224void
225NestedNameSpecifier::print(raw_ostream &OS,
226                           const PrintingPolicy &Policy) const {
227  if (getPrefix())
228    getPrefix()->print(OS, Policy);
229
230  switch (getKind()) {
231  case Identifier:
232    OS << getAsIdentifier()->getName();
233    break;
234
235  case Namespace:
236    if (getAsNamespace()->isAnonymousNamespace())
237      return;
238
239    OS << getAsNamespace()->getName();
240    break;
241
242  case NamespaceAlias:
243    OS << getAsNamespaceAlias()->getName();
244    break;
245
246  case Global:
247    break;
248
249  case TypeSpecWithTemplate:
250    OS << "template ";
251    // Fall through to print the type.
252
253  case TypeSpec: {
254    const Type *T = getAsType();
255
256    PrintingPolicy InnerPolicy(Policy);
257    InnerPolicy.SuppressScope = true;
258
259    // Nested-name-specifiers are intended to contain minimally-qualified
260    // types. An actual ElaboratedType will not occur, since we'll store
261    // just the type that is referred to in the nested-name-specifier (e.g.,
262    // a TypedefType, TagType, etc.). However, when we are dealing with
263    // dependent template-id types (e.g., Outer<T>::template Inner<U>),
264    // the type requires its own nested-name-specifier for uniqueness, so we
265    // suppress that nested-name-specifier during printing.
266    assert(!isa<ElaboratedType>(T) &&
267           "Elaborated type in nested-name-specifier");
268    if (const TemplateSpecializationType *SpecType
269          = dyn_cast<TemplateSpecializationType>(T)) {
270      // Print the template name without its corresponding
271      // nested-name-specifier.
272      SpecType->getTemplateName().print(OS, InnerPolicy, true);
273
274      // Print the template argument list.
275      TemplateSpecializationType::PrintTemplateArgumentList(
276          OS, SpecType->getArgs(), SpecType->getNumArgs(), InnerPolicy);
277    } else {
278      // Print the type normally
279      QualType(T, 0).print(OS, InnerPolicy);
280    }
281    break;
282  }
283  }
284
285  OS << "::";
286}
287
288void NestedNameSpecifier::dump(const LangOptions &LO) {
289  print(llvm::errs(), PrintingPolicy(LO));
290}
291
292unsigned
293NestedNameSpecifierLoc::getLocalDataLength(NestedNameSpecifier *Qualifier) {
294  assert(Qualifier && "Expected a non-NULL qualifier");
295
296  // Location of the trailing '::'.
297  unsigned Length = sizeof(unsigned);
298
299  switch (Qualifier->getKind()) {
300  case NestedNameSpecifier::Global:
301    // Nothing more to add.
302    break;
303
304  case NestedNameSpecifier::Identifier:
305  case NestedNameSpecifier::Namespace:
306  case NestedNameSpecifier::NamespaceAlias:
307    // The location of the identifier or namespace name.
308    Length += sizeof(unsigned);
309    break;
310
311  case NestedNameSpecifier::TypeSpecWithTemplate:
312  case NestedNameSpecifier::TypeSpec:
313    // The "void*" that points at the TypeLoc data.
314    // Note: the 'template' keyword is part of the TypeLoc.
315    Length += sizeof(void *);
316    break;
317  }
318
319  return Length;
320}
321
322unsigned
323NestedNameSpecifierLoc::getDataLength(NestedNameSpecifier *Qualifier) {
324  unsigned Length = 0;
325  for (; Qualifier; Qualifier = Qualifier->getPrefix())
326    Length += getLocalDataLength(Qualifier);
327  return Length;
328}
329
330namespace {
331  /// \brief Load a (possibly unaligned) source location from a given address
332  /// and offset.
333  SourceLocation LoadSourceLocation(void *Data, unsigned Offset) {
334    unsigned Raw;
335    memcpy(&Raw, static_cast<char *>(Data) + Offset, sizeof(unsigned));
336    return SourceLocation::getFromRawEncoding(Raw);
337  }
338
339  /// \brief Load a (possibly unaligned) pointer from a given address and
340  /// offset.
341  void *LoadPointer(void *Data, unsigned Offset) {
342    void *Result;
343    memcpy(&Result, static_cast<char *>(Data) + Offset, sizeof(void*));
344    return Result;
345  }
346}
347
348SourceRange NestedNameSpecifierLoc::getSourceRange() const {
349  if (!Qualifier)
350    return SourceRange();
351
352  NestedNameSpecifierLoc First = *this;
353  while (NestedNameSpecifierLoc Prefix = First.getPrefix())
354    First = Prefix;
355
356  return SourceRange(First.getLocalSourceRange().getBegin(),
357                     getLocalSourceRange().getEnd());
358}
359
360SourceRange NestedNameSpecifierLoc::getLocalSourceRange() const {
361  if (!Qualifier)
362    return SourceRange();
363
364  unsigned Offset = getDataLength(Qualifier->getPrefix());
365  switch (Qualifier->getKind()) {
366  case NestedNameSpecifier::Global:
367    return LoadSourceLocation(Data, Offset);
368
369  case NestedNameSpecifier::Identifier:
370  case NestedNameSpecifier::Namespace:
371  case NestedNameSpecifier::NamespaceAlias:
372    return SourceRange(LoadSourceLocation(Data, Offset),
373                       LoadSourceLocation(Data, Offset + sizeof(unsigned)));
374
375  case NestedNameSpecifier::TypeSpecWithTemplate:
376  case NestedNameSpecifier::TypeSpec: {
377    // The "void*" that points at the TypeLoc data.
378    // Note: the 'template' keyword is part of the TypeLoc.
379    void *TypeData = LoadPointer(Data, Offset);
380    TypeLoc TL(Qualifier->getAsType(), TypeData);
381    return SourceRange(TL.getBeginLoc(),
382                       LoadSourceLocation(Data, Offset + sizeof(void*)));
383  }
384  }
385
386  llvm_unreachable("Invalid NNS Kind!");
387}
388
389TypeLoc NestedNameSpecifierLoc::getTypeLoc() const {
390  assert((Qualifier->getKind() == NestedNameSpecifier::TypeSpec ||
391          Qualifier->getKind() == NestedNameSpecifier::TypeSpecWithTemplate) &&
392         "Nested-name-specifier location is not a type");
393
394  // The "void*" that points at the TypeLoc data.
395  unsigned Offset = getDataLength(Qualifier->getPrefix());
396  void *TypeData = LoadPointer(Data, Offset);
397  return TypeLoc(Qualifier->getAsType(), TypeData);
398}
399
400namespace {
401  void Append(char *Start, char *End, char *&Buffer, unsigned &BufferSize,
402              unsigned &BufferCapacity) {
403    if (BufferSize + (End - Start) > BufferCapacity) {
404      // Reallocate the buffer.
405      unsigned NewCapacity
406      = std::max((unsigned)(BufferCapacity? BufferCapacity * 2
407                            : sizeof(void*) * 2),
408                 (unsigned)(BufferSize + (End - Start)));
409      char *NewBuffer = static_cast<char *>(malloc(NewCapacity));
410      memcpy(NewBuffer, Buffer, BufferSize);
411
412      if (BufferCapacity)
413        free(Buffer);
414      Buffer = NewBuffer;
415      BufferCapacity = NewCapacity;
416    }
417
418    memcpy(Buffer + BufferSize, Start, End - Start);
419    BufferSize += End-Start;
420  }
421
422  /// \brief Save a source location to the given buffer.
423  void SaveSourceLocation(SourceLocation Loc, char *&Buffer,
424                          unsigned &BufferSize, unsigned &BufferCapacity) {
425    unsigned Raw = Loc.getRawEncoding();
426    Append(reinterpret_cast<char *>(&Raw),
427           reinterpret_cast<char *>(&Raw) + sizeof(unsigned),
428           Buffer, BufferSize, BufferCapacity);
429  }
430
431  /// \brief Save a pointer to the given buffer.
432  void SavePointer(void *Ptr, char *&Buffer, unsigned &BufferSize,
433                   unsigned &BufferCapacity) {
434    Append(reinterpret_cast<char *>(&Ptr),
435           reinterpret_cast<char *>(&Ptr) + sizeof(void *),
436           Buffer, BufferSize, BufferCapacity);
437  }
438}
439
440NestedNameSpecifierLocBuilder::
441NestedNameSpecifierLocBuilder(const NestedNameSpecifierLocBuilder &Other)
442  : Representation(Other.Representation), Buffer(nullptr),
443    BufferSize(0), BufferCapacity(0)
444{
445  if (!Other.Buffer)
446    return;
447
448  if (Other.BufferCapacity == 0) {
449    // Shallow copy is okay.
450    Buffer = Other.Buffer;
451    BufferSize = Other.BufferSize;
452    return;
453  }
454
455  // Deep copy
456  BufferSize = Other.BufferSize;
457  BufferCapacity = Other.BufferSize;
458  Buffer = static_cast<char *>(malloc(BufferCapacity));
459  memcpy(Buffer, Other.Buffer, BufferSize);
460}
461
462NestedNameSpecifierLocBuilder &
463NestedNameSpecifierLocBuilder::
464operator=(const NestedNameSpecifierLocBuilder &Other) {
465  Representation = Other.Representation;
466
467  if (Buffer && Other.Buffer && BufferCapacity >= Other.BufferSize) {
468    // Re-use our storage.
469    BufferSize = Other.BufferSize;
470    memcpy(Buffer, Other.Buffer, BufferSize);
471    return *this;
472  }
473
474  // Free our storage, if we have any.
475  if (BufferCapacity) {
476    free(Buffer);
477    BufferCapacity = 0;
478  }
479
480  if (!Other.Buffer) {
481    // Empty.
482    Buffer = nullptr;
483    BufferSize = 0;
484    return *this;
485  }
486
487  if (Other.BufferCapacity == 0) {
488    // Shallow copy is okay.
489    Buffer = Other.Buffer;
490    BufferSize = Other.BufferSize;
491    return *this;
492  }
493
494  // Deep copy.
495  BufferSize = Other.BufferSize;
496  BufferCapacity = BufferSize;
497  Buffer = static_cast<char *>(malloc(BufferSize));
498  memcpy(Buffer, Other.Buffer, BufferSize);
499  return *this;
500}
501
502void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
503                                           SourceLocation TemplateKWLoc,
504                                           TypeLoc TL,
505                                           SourceLocation ColonColonLoc) {
506  Representation = NestedNameSpecifier::Create(Context, Representation,
507                                               TemplateKWLoc.isValid(),
508                                               TL.getTypePtr());
509
510  // Push source-location info into the buffer.
511  SavePointer(TL.getOpaqueData(), Buffer, BufferSize, BufferCapacity);
512  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
513}
514
515void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
516                                           IdentifierInfo *Identifier,
517                                           SourceLocation IdentifierLoc,
518                                           SourceLocation ColonColonLoc) {
519  Representation = NestedNameSpecifier::Create(Context, Representation,
520                                               Identifier);
521
522  // Push source-location info into the buffer.
523  SaveSourceLocation(IdentifierLoc, Buffer, BufferSize, BufferCapacity);
524  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
525}
526
527void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
528                                           NamespaceDecl *Namespace,
529                                           SourceLocation NamespaceLoc,
530                                           SourceLocation ColonColonLoc) {
531  Representation = NestedNameSpecifier::Create(Context, Representation,
532                                               Namespace);
533
534  // Push source-location info into the buffer.
535  SaveSourceLocation(NamespaceLoc, Buffer, BufferSize, BufferCapacity);
536  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
537}
538
539void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
540                                           NamespaceAliasDecl *Alias,
541                                           SourceLocation AliasLoc,
542                                           SourceLocation ColonColonLoc) {
543  Representation = NestedNameSpecifier::Create(Context, Representation, Alias);
544
545  // Push source-location info into the buffer.
546  SaveSourceLocation(AliasLoc, Buffer, BufferSize, BufferCapacity);
547  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
548}
549
550void NestedNameSpecifierLocBuilder::MakeGlobal(ASTContext &Context,
551                                               SourceLocation ColonColonLoc) {
552  assert(!Representation && "Already have a nested-name-specifier!?");
553  Representation = NestedNameSpecifier::GlobalSpecifier(Context);
554
555  // Push source-location info into the buffer.
556  SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
557}
558
559void NestedNameSpecifierLocBuilder::MakeTrivial(ASTContext &Context,
560                                                NestedNameSpecifier *Qualifier,
561                                                SourceRange R) {
562  Representation = Qualifier;
563
564  // Construct bogus (but well-formed) source information for the
565  // nested-name-specifier.
566  BufferSize = 0;
567  SmallVector<NestedNameSpecifier *, 4> Stack;
568  for (NestedNameSpecifier *NNS = Qualifier; NNS; NNS = NNS->getPrefix())
569    Stack.push_back(NNS);
570  while (!Stack.empty()) {
571    NestedNameSpecifier *NNS = Stack.pop_back_val();
572    switch (NNS->getKind()) {
573      case NestedNameSpecifier::Identifier:
574      case NestedNameSpecifier::Namespace:
575      case NestedNameSpecifier::NamespaceAlias:
576        SaveSourceLocation(R.getBegin(), Buffer, BufferSize, BufferCapacity);
577        break;
578
579      case NestedNameSpecifier::TypeSpec:
580      case NestedNameSpecifier::TypeSpecWithTemplate: {
581        TypeSourceInfo *TSInfo
582        = Context.getTrivialTypeSourceInfo(QualType(NNS->getAsType(), 0),
583                                           R.getBegin());
584        SavePointer(TSInfo->getTypeLoc().getOpaqueData(), Buffer, BufferSize,
585                    BufferCapacity);
586        break;
587      }
588
589      case NestedNameSpecifier::Global:
590        break;
591    }
592
593    // Save the location of the '::'.
594    SaveSourceLocation(Stack.empty()? R.getEnd() : R.getBegin(),
595                       Buffer, BufferSize, BufferCapacity);
596  }
597}
598
599void NestedNameSpecifierLocBuilder::Adopt(NestedNameSpecifierLoc Other) {
600  if (BufferCapacity)
601    free(Buffer);
602
603  if (!Other) {
604    Representation = nullptr;
605    BufferSize = 0;
606    return;
607  }
608
609  // Rather than copying the data (which is wasteful), "adopt" the
610  // pointer (which points into the ASTContext) but set the capacity to zero to
611  // indicate that we don't own it.
612  Representation = Other.getNestedNameSpecifier();
613  Buffer = static_cast<char *>(Other.getOpaqueData());
614  BufferSize = Other.getDataLength();
615  BufferCapacity = 0;
616}
617
618NestedNameSpecifierLoc
619NestedNameSpecifierLocBuilder::getWithLocInContext(ASTContext &Context) const {
620  if (!Representation)
621    return NestedNameSpecifierLoc();
622
623  // If we adopted our data pointer from elsewhere in the AST context, there's
624  // no need to copy the memory.
625  if (BufferCapacity == 0)
626    return NestedNameSpecifierLoc(Representation, Buffer);
627
628  // FIXME: After copying the source-location information, should we free
629  // our (temporary) buffer and adopt the ASTContext-allocated memory?
630  // Doing so would optimize repeated calls to getWithLocInContext().
631  void *Mem = Context.Allocate(BufferSize, llvm::alignOf<void *>());
632  memcpy(Mem, Buffer, BufferSize);
633  return NestedNameSpecifierLoc(Representation, Mem);
634}
635