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 
25 using namespace clang;
26 
27 NestedNameSpecifier *
28 NestedNameSpecifier::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 
45 NestedNameSpecifier *
46 NestedNameSpecifier::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 
58 NestedNameSpecifier *
59 NestedNameSpecifier::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 
73 NestedNameSpecifier *
74 NestedNameSpecifier::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 
88 NestedNameSpecifier *
89 NestedNameSpecifier::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 
100 NestedNameSpecifier *
101 NestedNameSpecifier::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 
110 NestedNameSpecifier *
111 NestedNameSpecifier::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 
119 NestedNameSpecifier::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.
143 NamespaceDecl *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.
152 NamespaceAliasDecl *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.
162 bool 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.
183 bool 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 
202 bool 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.
222 void
223 NestedNameSpecifier::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     std::string TypeStr;
253     const Type *T = getAsType();
254 
255     PrintingPolicy InnerPolicy(Policy);
256     InnerPolicy.SuppressScope = true;
257 
258     // Nested-name-specifiers are intended to contain minimally-qualified
259     // types. An actual ElaboratedType will not occur, since we'll store
260     // just the type that is referred to in the nested-name-specifier (e.g.,
261     // a TypedefType, TagType, etc.). However, when we are dealing with
262     // dependent template-id types (e.g., Outer<T>::template Inner<U>),
263     // the type requires its own nested-name-specifier for uniqueness, so we
264     // suppress that nested-name-specifier during printing.
265     assert(!isa<ElaboratedType>(T) &&
266            "Elaborated type in nested-name-specifier");
267     if (const TemplateSpecializationType *SpecType
268           = dyn_cast<TemplateSpecializationType>(T)) {
269       // Print the template name without its corresponding
270       // nested-name-specifier.
271       SpecType->getTemplateName().print(OS, InnerPolicy, true);
272 
273       // Print the template argument list.
274       TypeStr = TemplateSpecializationType::PrintTemplateArgumentList(
275                                                           SpecType->getArgs(),
276                                                        SpecType->getNumArgs(),
277                                                                  InnerPolicy);
278     } else {
279       // Print the type normally
280       TypeStr = QualType(T, 0).getAsString(InnerPolicy);
281     }
282     OS << TypeStr;
283     break;
284   }
285   }
286 
287   OS << "::";
288 }
289 
290 void NestedNameSpecifier::dump(const LangOptions &LO) {
291   print(llvm::errs(), PrintingPolicy(LO));
292 }
293 
294 unsigned
295 NestedNameSpecifierLoc::getLocalDataLength(NestedNameSpecifier *Qualifier) {
296   assert(Qualifier && "Expected a non-NULL qualifier");
297 
298   // Location of the trailing '::'.
299   unsigned Length = sizeof(unsigned);
300 
301   switch (Qualifier->getKind()) {
302   case NestedNameSpecifier::Global:
303     // Nothing more to add.
304     break;
305 
306   case NestedNameSpecifier::Identifier:
307   case NestedNameSpecifier::Namespace:
308   case NestedNameSpecifier::NamespaceAlias:
309     // The location of the identifier or namespace name.
310     Length += sizeof(unsigned);
311     break;
312 
313   case NestedNameSpecifier::TypeSpecWithTemplate:
314   case NestedNameSpecifier::TypeSpec:
315     // The "void*" that points at the TypeLoc data.
316     // Note: the 'template' keyword is part of the TypeLoc.
317     Length += sizeof(void *);
318     break;
319   }
320 
321   return Length;
322 }
323 
324 unsigned
325 NestedNameSpecifierLoc::getDataLength(NestedNameSpecifier *Qualifier) {
326   unsigned Length = 0;
327   for (; Qualifier; Qualifier = Qualifier->getPrefix())
328     Length += getLocalDataLength(Qualifier);
329   return Length;
330 }
331 
332 namespace {
333   /// \brief Load a (possibly unaligned) source location from a given address
334   /// and offset.
335   SourceLocation LoadSourceLocation(void *Data, unsigned Offset) {
336     unsigned Raw;
337     memcpy(&Raw, static_cast<char *>(Data) + Offset, sizeof(unsigned));
338     return SourceLocation::getFromRawEncoding(Raw);
339   }
340 
341   /// \brief Load a (possibly unaligned) pointer from a given address and
342   /// offset.
343   void *LoadPointer(void *Data, unsigned Offset) {
344     void *Result;
345     memcpy(&Result, static_cast<char *>(Data) + Offset, sizeof(void*));
346     return Result;
347   }
348 }
349 
350 SourceRange NestedNameSpecifierLoc::getSourceRange() const {
351   if (!Qualifier)
352     return SourceRange();
353 
354   NestedNameSpecifierLoc First = *this;
355   while (NestedNameSpecifierLoc Prefix = First.getPrefix())
356     First = Prefix;
357 
358   return SourceRange(First.getLocalSourceRange().getBegin(),
359                      getLocalSourceRange().getEnd());
360 }
361 
362 SourceRange NestedNameSpecifierLoc::getLocalSourceRange() const {
363   if (!Qualifier)
364     return SourceRange();
365 
366   unsigned Offset = getDataLength(Qualifier->getPrefix());
367   switch (Qualifier->getKind()) {
368   case NestedNameSpecifier::Global:
369     return LoadSourceLocation(Data, Offset);
370 
371   case NestedNameSpecifier::Identifier:
372   case NestedNameSpecifier::Namespace:
373   case NestedNameSpecifier::NamespaceAlias:
374     return SourceRange(LoadSourceLocation(Data, Offset),
375                        LoadSourceLocation(Data, Offset + sizeof(unsigned)));
376 
377   case NestedNameSpecifier::TypeSpecWithTemplate:
378   case NestedNameSpecifier::TypeSpec: {
379     // The "void*" that points at the TypeLoc data.
380     // Note: the 'template' keyword is part of the TypeLoc.
381     void *TypeData = LoadPointer(Data, Offset);
382     TypeLoc TL(Qualifier->getAsType(), TypeData);
383     return SourceRange(TL.getBeginLoc(),
384                        LoadSourceLocation(Data, Offset + sizeof(void*)));
385   }
386   }
387 
388   llvm_unreachable("Invalid NNS Kind!");
389 }
390 
391 TypeLoc NestedNameSpecifierLoc::getTypeLoc() const {
392   assert((Qualifier->getKind() == NestedNameSpecifier::TypeSpec ||
393           Qualifier->getKind() == NestedNameSpecifier::TypeSpecWithTemplate) &&
394          "Nested-name-specifier location is not a type");
395 
396   // The "void*" that points at the TypeLoc data.
397   unsigned Offset = getDataLength(Qualifier->getPrefix());
398   void *TypeData = LoadPointer(Data, Offset);
399   return TypeLoc(Qualifier->getAsType(), TypeData);
400 }
401 
402 namespace {
403   void Append(char *Start, char *End, char *&Buffer, unsigned &BufferSize,
404               unsigned &BufferCapacity) {
405     if (BufferSize + (End - Start) > BufferCapacity) {
406       // Reallocate the buffer.
407       unsigned NewCapacity
408       = std::max((unsigned)(BufferCapacity? BufferCapacity * 2
409                             : sizeof(void*) * 2),
410                  (unsigned)(BufferSize + (End - Start)));
411       char *NewBuffer = static_cast<char *>(malloc(NewCapacity));
412       memcpy(NewBuffer, Buffer, BufferSize);
413 
414       if (BufferCapacity)
415         free(Buffer);
416       Buffer = NewBuffer;
417       BufferCapacity = NewCapacity;
418     }
419 
420     memcpy(Buffer + BufferSize, Start, End - Start);
421     BufferSize += End-Start;
422   }
423 
424   /// \brief Save a source location to the given buffer.
425   void SaveSourceLocation(SourceLocation Loc, char *&Buffer,
426                           unsigned &BufferSize, unsigned &BufferCapacity) {
427     unsigned Raw = Loc.getRawEncoding();
428     Append(reinterpret_cast<char *>(&Raw),
429            reinterpret_cast<char *>(&Raw) + sizeof(unsigned),
430            Buffer, BufferSize, BufferCapacity);
431   }
432 
433   /// \brief Save a pointer to the given buffer.
434   void SavePointer(void *Ptr, char *&Buffer, unsigned &BufferSize,
435                    unsigned &BufferCapacity) {
436     Append(reinterpret_cast<char *>(&Ptr),
437            reinterpret_cast<char *>(&Ptr) + sizeof(void *),
438            Buffer, BufferSize, BufferCapacity);
439   }
440 }
441 
442 NestedNameSpecifierLocBuilder::
443 NestedNameSpecifierLocBuilder(const NestedNameSpecifierLocBuilder &Other)
444   : Representation(Other.Representation), Buffer(0),
445     BufferSize(0), BufferCapacity(0)
446 {
447   if (!Other.Buffer)
448     return;
449 
450   if (Other.BufferCapacity == 0) {
451     // Shallow copy is okay.
452     Buffer = Other.Buffer;
453     BufferSize = Other.BufferSize;
454     return;
455   }
456 
457   // Deep copy
458   BufferSize = Other.BufferSize;
459   BufferCapacity = Other.BufferSize;
460   Buffer = static_cast<char *>(malloc(BufferCapacity));
461   memcpy(Buffer, Other.Buffer, BufferSize);
462 }
463 
464 NestedNameSpecifierLocBuilder &
465 NestedNameSpecifierLocBuilder::
466 operator=(const NestedNameSpecifierLocBuilder &Other) {
467   Representation = Other.Representation;
468 
469   if (Buffer && Other.Buffer && BufferCapacity >= Other.BufferSize) {
470     // Re-use our storage.
471     BufferSize = Other.BufferSize;
472     memcpy(Buffer, Other.Buffer, BufferSize);
473     return *this;
474   }
475 
476   // Free our storage, if we have any.
477   if (BufferCapacity) {
478     free(Buffer);
479     BufferCapacity = 0;
480   }
481 
482   if (!Other.Buffer) {
483     // Empty.
484     Buffer = 0;
485     BufferSize = 0;
486     return *this;
487   }
488 
489   if (Other.BufferCapacity == 0) {
490     // Shallow copy is okay.
491     Buffer = Other.Buffer;
492     BufferSize = Other.BufferSize;
493     return *this;
494   }
495 
496   // Deep copy.
497   BufferSize = Other.BufferSize;
498   BufferCapacity = BufferSize;
499   Buffer = static_cast<char *>(malloc(BufferSize));
500   memcpy(Buffer, Other.Buffer, BufferSize);
501   return *this;
502 }
503 
504 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
505                                            SourceLocation TemplateKWLoc,
506                                            TypeLoc TL,
507                                            SourceLocation ColonColonLoc) {
508   Representation = NestedNameSpecifier::Create(Context, Representation,
509                                                TemplateKWLoc.isValid(),
510                                                TL.getTypePtr());
511 
512   // Push source-location info into the buffer.
513   SavePointer(TL.getOpaqueData(), Buffer, BufferSize, BufferCapacity);
514   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
515 }
516 
517 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
518                                            IdentifierInfo *Identifier,
519                                            SourceLocation IdentifierLoc,
520                                            SourceLocation ColonColonLoc) {
521   Representation = NestedNameSpecifier::Create(Context, Representation,
522                                                Identifier);
523 
524   // Push source-location info into the buffer.
525   SaveSourceLocation(IdentifierLoc, Buffer, BufferSize, BufferCapacity);
526   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
527 }
528 
529 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
530                                            NamespaceDecl *Namespace,
531                                            SourceLocation NamespaceLoc,
532                                            SourceLocation ColonColonLoc) {
533   Representation = NestedNameSpecifier::Create(Context, Representation,
534                                                Namespace);
535 
536   // Push source-location info into the buffer.
537   SaveSourceLocation(NamespaceLoc, Buffer, BufferSize, BufferCapacity);
538   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
539 }
540 
541 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
542                                            NamespaceAliasDecl *Alias,
543                                            SourceLocation AliasLoc,
544                                            SourceLocation ColonColonLoc) {
545   Representation = NestedNameSpecifier::Create(Context, Representation, Alias);
546 
547   // Push source-location info into the buffer.
548   SaveSourceLocation(AliasLoc, Buffer, BufferSize, BufferCapacity);
549   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
550 }
551 
552 void NestedNameSpecifierLocBuilder::MakeGlobal(ASTContext &Context,
553                                                SourceLocation ColonColonLoc) {
554   assert(!Representation && "Already have a nested-name-specifier!?");
555   Representation = NestedNameSpecifier::GlobalSpecifier(Context);
556 
557   // Push source-location info into the buffer.
558   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
559 }
560 
561 void NestedNameSpecifierLocBuilder::MakeTrivial(ASTContext &Context,
562                                                 NestedNameSpecifier *Qualifier,
563                                                 SourceRange R) {
564   Representation = Qualifier;
565 
566   // Construct bogus (but well-formed) source information for the
567   // nested-name-specifier.
568   BufferSize = 0;
569   SmallVector<NestedNameSpecifier *, 4> Stack;
570   for (NestedNameSpecifier *NNS = Qualifier; NNS; NNS = NNS->getPrefix())
571     Stack.push_back(NNS);
572   while (!Stack.empty()) {
573     NestedNameSpecifier *NNS = Stack.back();
574     Stack.pop_back();
575     switch (NNS->getKind()) {
576       case NestedNameSpecifier::Identifier:
577       case NestedNameSpecifier::Namespace:
578       case NestedNameSpecifier::NamespaceAlias:
579         SaveSourceLocation(R.getBegin(), Buffer, BufferSize, BufferCapacity);
580         break;
581 
582       case NestedNameSpecifier::TypeSpec:
583       case NestedNameSpecifier::TypeSpecWithTemplate: {
584         TypeSourceInfo *TSInfo
585         = Context.getTrivialTypeSourceInfo(QualType(NNS->getAsType(), 0),
586                                            R.getBegin());
587         SavePointer(TSInfo->getTypeLoc().getOpaqueData(), Buffer, BufferSize,
588                     BufferCapacity);
589         break;
590       }
591 
592       case NestedNameSpecifier::Global:
593         break;
594     }
595 
596     // Save the location of the '::'.
597     SaveSourceLocation(Stack.empty()? R.getEnd() : R.getBegin(),
598                        Buffer, BufferSize, BufferCapacity);
599   }
600 }
601 
602 void NestedNameSpecifierLocBuilder::Adopt(NestedNameSpecifierLoc Other) {
603   if (BufferCapacity)
604     free(Buffer);
605 
606   if (!Other) {
607     Representation = 0;
608     BufferSize = 0;
609     return;
610   }
611 
612   // Rather than copying the data (which is wasteful), "adopt" the
613   // pointer (which points into the ASTContext) but set the capacity to zero to
614   // indicate that we don't own it.
615   Representation = Other.getNestedNameSpecifier();
616   Buffer = static_cast<char *>(Other.getOpaqueData());
617   BufferSize = Other.getDataLength();
618   BufferCapacity = 0;
619 }
620 
621 NestedNameSpecifierLoc
622 NestedNameSpecifierLocBuilder::getWithLocInContext(ASTContext &Context) const {
623   if (!Representation)
624     return NestedNameSpecifierLoc();
625 
626   // If we adopted our data pointer from elsewhere in the AST context, there's
627   // no need to copy the memory.
628   if (BufferCapacity == 0)
629     return NestedNameSpecifierLoc(Representation, Buffer);
630 
631   // FIXME: After copying the source-location information, should we free
632   // our (temporary) buffer and adopt the ASTContext-allocated memory?
633   // Doing so would optimize repeated calls to getWithLocInContext().
634   void *Mem = Context.Allocate(BufferSize, llvm::alignOf<void *>());
635   memcpy(Mem, Buffer, BufferSize);
636   return NestedNameSpecifierLoc(Representation, Mem);
637 }
638