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