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/raw_ostream.h"
22 #include <cassert>
23 
24 using namespace clang;
25 
26 NestedNameSpecifier *
27 NestedNameSpecifier::FindOrInsert(const ASTContext &Context,
28                                   const NestedNameSpecifier &Mockup) {
29   llvm::FoldingSetNodeID ID;
30   Mockup.Profile(ID);
31 
32   void *InsertPos = 0;
33   NestedNameSpecifier *NNS
34     = Context.NestedNameSpecifiers.FindNodeOrInsertPos(ID, InsertPos);
35   if (!NNS) {
36     NNS = new (Context, 4) NestedNameSpecifier(Mockup);
37     Context.NestedNameSpecifiers.InsertNode(NNS, InsertPos);
38   }
39 
40   return NNS;
41 }
42 
43 NestedNameSpecifier *
44 NestedNameSpecifier::Create(const ASTContext &Context,
45                             NestedNameSpecifier *Prefix, IdentifierInfo *II) {
46   assert(II && "Identifier cannot be NULL");
47   assert((!Prefix || Prefix->isDependent()) && "Prefix must be dependent");
48 
49   NestedNameSpecifier Mockup;
50   Mockup.Prefix.setPointer(Prefix);
51   Mockup.Prefix.setInt(StoredIdentifier);
52   Mockup.Specifier = II;
53   return FindOrInsert(Context, Mockup);
54 }
55 
56 NestedNameSpecifier *
57 NestedNameSpecifier::Create(const ASTContext &Context,
58                             NestedNameSpecifier *Prefix, NamespaceDecl *NS) {
59   assert(NS && "Namespace cannot be NULL");
60   assert((!Prefix ||
61           (Prefix->getAsType() == 0 && Prefix->getAsIdentifier() == 0)) &&
62          "Broken nested name specifier");
63   NestedNameSpecifier Mockup;
64   Mockup.Prefix.setPointer(Prefix);
65   Mockup.Prefix.setInt(StoredNamespaceOrAlias);
66   Mockup.Specifier = NS;
67   return FindOrInsert(Context, Mockup);
68 }
69 
70 NestedNameSpecifier *
71 NestedNameSpecifier::Create(const ASTContext &Context,
72                             NestedNameSpecifier *Prefix,
73                             NamespaceAliasDecl *Alias) {
74   assert(Alias && "Namespace alias cannot be NULL");
75   assert((!Prefix ||
76           (Prefix->getAsType() == 0 && Prefix->getAsIdentifier() == 0)) &&
77          "Broken nested name specifier");
78   NestedNameSpecifier Mockup;
79   Mockup.Prefix.setPointer(Prefix);
80   Mockup.Prefix.setInt(StoredNamespaceOrAlias);
81   Mockup.Specifier = Alias;
82   return FindOrInsert(Context, Mockup);
83 }
84 
85 NestedNameSpecifier *
86 NestedNameSpecifier::Create(const ASTContext &Context,
87                             NestedNameSpecifier *Prefix,
88                             bool Template, const Type *T) {
89   assert(T && "Type cannot be NULL");
90   NestedNameSpecifier Mockup;
91   Mockup.Prefix.setPointer(Prefix);
92   Mockup.Prefix.setInt(Template? StoredTypeSpecWithTemplate : StoredTypeSpec);
93   Mockup.Specifier = const_cast<Type*>(T);
94   return FindOrInsert(Context, Mockup);
95 }
96 
97 NestedNameSpecifier *
98 NestedNameSpecifier::Create(const ASTContext &Context, IdentifierInfo *II) {
99   assert(II && "Identifier cannot be NULL");
100   NestedNameSpecifier Mockup;
101   Mockup.Prefix.setPointer(0);
102   Mockup.Prefix.setInt(StoredIdentifier);
103   Mockup.Specifier = II;
104   return FindOrInsert(Context, Mockup);
105 }
106 
107 NestedNameSpecifier *
108 NestedNameSpecifier::GlobalSpecifier(const ASTContext &Context) {
109   if (!Context.GlobalNestedNameSpecifier)
110     Context.GlobalNestedNameSpecifier = new (Context, 4) NestedNameSpecifier();
111   return Context.GlobalNestedNameSpecifier;
112 }
113 
114 NestedNameSpecifier::SpecifierKind NestedNameSpecifier::getKind() const {
115   if (Specifier == 0)
116     return Global;
117 
118   switch (Prefix.getInt()) {
119   case StoredIdentifier:
120     return Identifier;
121 
122   case StoredNamespaceOrAlias:
123     return isa<NamespaceDecl>(static_cast<NamedDecl *>(Specifier))? Namespace
124                                                             : NamespaceAlias;
125 
126   case StoredTypeSpec:
127     return TypeSpec;
128 
129   case StoredTypeSpecWithTemplate:
130     return TypeSpecWithTemplate;
131   }
132 
133   return Global;
134 }
135 
136 /// \brief Retrieve the namespace stored in this nested name
137 /// specifier.
138 NamespaceDecl *NestedNameSpecifier::getAsNamespace() const {
139   if (Prefix.getInt() == StoredNamespaceOrAlias)
140     return dyn_cast<NamespaceDecl>(static_cast<NamedDecl *>(Specifier));
141 
142   return 0;
143 }
144 
145 /// \brief Retrieve the namespace alias stored in this nested name
146 /// specifier.
147 NamespaceAliasDecl *NestedNameSpecifier::getAsNamespaceAlias() const {
148   if (Prefix.getInt() == StoredNamespaceOrAlias)
149     return dyn_cast<NamespaceAliasDecl>(static_cast<NamedDecl *>(Specifier));
150 
151   return 0;
152 }
153 
154 
155 /// \brief Whether this nested name specifier refers to a dependent
156 /// type or not.
157 bool NestedNameSpecifier::isDependent() const {
158   switch (getKind()) {
159   case Identifier:
160     // Identifier specifiers always represent dependent types
161     return true;
162 
163   case Namespace:
164   case NamespaceAlias:
165   case Global:
166     return false;
167 
168   case TypeSpec:
169   case TypeSpecWithTemplate:
170     return getAsType()->isDependentType();
171   }
172 
173   // Necessary to suppress a GCC warning.
174   return false;
175 }
176 
177 /// \brief Whether this nested name specifier refers to a dependent
178 /// type or not.
179 bool NestedNameSpecifier::isInstantiationDependent() const {
180   switch (getKind()) {
181   case Identifier:
182     // Identifier specifiers always represent dependent types
183     return true;
184 
185   case Namespace:
186   case NamespaceAlias:
187   case Global:
188     return false;
189 
190   case TypeSpec:
191   case TypeSpecWithTemplate:
192     return getAsType()->isInstantiationDependentType();
193   }
194 
195   // Necessary to suppress a GCC warning.
196   return false;
197 }
198 
199 bool NestedNameSpecifier::containsUnexpandedParameterPack() const {
200   switch (getKind()) {
201   case Identifier:
202     return getPrefix() && getPrefix()->containsUnexpandedParameterPack();
203 
204   case Namespace:
205   case NamespaceAlias:
206   case Global:
207     return false;
208 
209   case TypeSpec:
210   case TypeSpecWithTemplate:
211     return getAsType()->containsUnexpandedParameterPack();
212   }
213 
214   // Necessary to suppress a GCC warning.
215   return false;
216 }
217 
218 /// \brief Print this nested name specifier to the given output
219 /// stream.
220 void
221 NestedNameSpecifier::print(raw_ostream &OS,
222                            const PrintingPolicy &Policy) const {
223   if (getPrefix())
224     getPrefix()->print(OS, Policy);
225 
226   switch (getKind()) {
227   case Identifier:
228     OS << getAsIdentifier()->getName();
229     break;
230 
231   case Namespace:
232     if (getAsNamespace()->isAnonymousNamespace())
233       return;
234 
235     OS << getAsNamespace()->getName();
236     break;
237 
238   case NamespaceAlias:
239     OS << getAsNamespaceAlias()->getName();
240     break;
241 
242   case Global:
243     break;
244 
245   case TypeSpecWithTemplate:
246     OS << "template ";
247     // Fall through to print the type.
248 
249   case TypeSpec: {
250     std::string TypeStr;
251     const Type *T = getAsType();
252 
253     PrintingPolicy InnerPolicy(Policy);
254     InnerPolicy.SuppressScope = true;
255 
256     // Nested-name-specifiers are intended to contain minimally-qualified
257     // types. An actual ElaboratedType will not occur, since we'll store
258     // just the type that is referred to in the nested-name-specifier (e.g.,
259     // a TypedefType, TagType, etc.). However, when we are dealing with
260     // dependent template-id types (e.g., Outer<T>::template Inner<U>),
261     // the type requires its own nested-name-specifier for uniqueness, so we
262     // suppress that nested-name-specifier during printing.
263     assert(!isa<ElaboratedType>(T) &&
264            "Elaborated type in nested-name-specifier");
265     if (const TemplateSpecializationType *SpecType
266           = dyn_cast<TemplateSpecializationType>(T)) {
267       // Print the template name without its corresponding
268       // nested-name-specifier.
269       SpecType->getTemplateName().print(OS, InnerPolicy, true);
270 
271       // Print the template argument list.
272       TypeStr = TemplateSpecializationType::PrintTemplateArgumentList(
273                                                           SpecType->getArgs(),
274                                                        SpecType->getNumArgs(),
275                                                                  InnerPolicy);
276     } else {
277       // Print the type normally
278       TypeStr = QualType(T, 0).getAsString(InnerPolicy);
279     }
280     OS << TypeStr;
281     break;
282   }
283   }
284 
285   OS << "::";
286 }
287 
288 void NestedNameSpecifier::dump(const LangOptions &LO) {
289   print(llvm::errs(), PrintingPolicy(LO));
290 }
291 
292 unsigned
293 NestedNameSpecifierLoc::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 
322 unsigned
323 NestedNameSpecifierLoc::getDataLength(NestedNameSpecifier *Qualifier) {
324   unsigned Length = 0;
325   for (; Qualifier; Qualifier = Qualifier->getPrefix())
326     Length += getLocalDataLength(Qualifier);
327   return Length;
328 }
329 
330 namespace {
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 
348 SourceRange 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 
360 SourceRange 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   return SourceRange();
387 }
388 
389 TypeLoc 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 
400 namespace {
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 
440 NestedNameSpecifierLocBuilder::NestedNameSpecifierLocBuilder()
441   : Representation(0), Buffer(0), BufferSize(0), BufferCapacity(0) { }
442 
443 NestedNameSpecifierLocBuilder::
444 NestedNameSpecifierLocBuilder(const NestedNameSpecifierLocBuilder &Other)
445   : Representation(Other.Representation), Buffer(0),
446     BufferSize(0), BufferCapacity(0)
447 {
448   if (!Other.Buffer)
449     return;
450 
451   if (Other.BufferCapacity == 0) {
452     // Shallow copy is okay.
453     Buffer = Other.Buffer;
454     BufferSize = Other.BufferSize;
455     return;
456   }
457 
458   // Deep copy
459   BufferSize = Other.BufferSize;
460   BufferCapacity = Other.BufferSize;
461   Buffer = static_cast<char *>(malloc(BufferCapacity));
462   memcpy(Buffer, Other.Buffer, BufferSize);
463 }
464 
465 NestedNameSpecifierLocBuilder &
466 NestedNameSpecifierLocBuilder::
467 operator=(const NestedNameSpecifierLocBuilder &Other) {
468   Representation = Other.Representation;
469 
470   if (Buffer && Other.Buffer && BufferCapacity >= Other.BufferSize) {
471     // Re-use our storage.
472     BufferSize = Other.BufferSize;
473     memcpy(Buffer, Other.Buffer, BufferSize);
474     return *this;
475   }
476 
477   // Free our storage, if we have any.
478   if (BufferCapacity) {
479     free(Buffer);
480     BufferCapacity = 0;
481   }
482 
483   if (!Other.Buffer) {
484     // Empty.
485     Buffer = 0;
486     BufferSize = 0;
487     return *this;
488   }
489 
490   if (Other.BufferCapacity == 0) {
491     // Shallow copy is okay.
492     Buffer = Other.Buffer;
493     BufferSize = Other.BufferSize;
494     return *this;
495   }
496 
497   // Deep copy.
498   BufferSize = Other.BufferSize;
499   BufferCapacity = BufferSize;
500   Buffer = static_cast<char *>(malloc(BufferSize));
501   memcpy(Buffer, Other.Buffer, BufferSize);
502   return *this;
503 }
504 
505 NestedNameSpecifierLocBuilder::~NestedNameSpecifierLocBuilder() {
506   if (BufferCapacity)
507     free(Buffer);
508 }
509 
510 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
511                                            SourceLocation TemplateKWLoc,
512                                            TypeLoc TL,
513                                            SourceLocation ColonColonLoc) {
514   Representation = NestedNameSpecifier::Create(Context, Representation,
515                                                TemplateKWLoc.isValid(),
516                                                TL.getTypePtr());
517 
518   // Push source-location info into the buffer.
519   SavePointer(TL.getOpaqueData(), Buffer, BufferSize, BufferCapacity);
520   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
521 }
522 
523 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
524                                            IdentifierInfo *Identifier,
525                                            SourceLocation IdentifierLoc,
526                                            SourceLocation ColonColonLoc) {
527   Representation = NestedNameSpecifier::Create(Context, Representation,
528                                                Identifier);
529 
530   // Push source-location info into the buffer.
531   SaveSourceLocation(IdentifierLoc, Buffer, BufferSize, BufferCapacity);
532   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
533 }
534 
535 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
536                                            NamespaceDecl *Namespace,
537                                            SourceLocation NamespaceLoc,
538                                            SourceLocation ColonColonLoc) {
539   Representation = NestedNameSpecifier::Create(Context, Representation,
540                                                Namespace);
541 
542   // Push source-location info into the buffer.
543   SaveSourceLocation(NamespaceLoc, Buffer, BufferSize, BufferCapacity);
544   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
545 }
546 
547 void NestedNameSpecifierLocBuilder::Extend(ASTContext &Context,
548                                            NamespaceAliasDecl *Alias,
549                                            SourceLocation AliasLoc,
550                                            SourceLocation ColonColonLoc) {
551   Representation = NestedNameSpecifier::Create(Context, Representation, Alias);
552 
553   // Push source-location info into the buffer.
554   SaveSourceLocation(AliasLoc, Buffer, BufferSize, BufferCapacity);
555   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
556 }
557 
558 void NestedNameSpecifierLocBuilder::MakeGlobal(ASTContext &Context,
559                                                SourceLocation ColonColonLoc) {
560   assert(!Representation && "Already have a nested-name-specifier!?");
561   Representation = NestedNameSpecifier::GlobalSpecifier(Context);
562 
563   // Push source-location info into the buffer.
564   SaveSourceLocation(ColonColonLoc, Buffer, BufferSize, BufferCapacity);
565 }
566 
567 void NestedNameSpecifierLocBuilder::MakeTrivial(ASTContext &Context,
568                                                 NestedNameSpecifier *Qualifier,
569                                                 SourceRange R) {
570   Representation = Qualifier;
571 
572   // Construct bogus (but well-formed) source information for the
573   // nested-name-specifier.
574   BufferSize = 0;
575   SmallVector<NestedNameSpecifier *, 4> Stack;
576   for (NestedNameSpecifier *NNS = Qualifier; NNS; NNS = NNS->getPrefix())
577     Stack.push_back(NNS);
578   while (!Stack.empty()) {
579     NestedNameSpecifier *NNS = Stack.back();
580     Stack.pop_back();
581     switch (NNS->getKind()) {
582       case NestedNameSpecifier::Identifier:
583       case NestedNameSpecifier::Namespace:
584       case NestedNameSpecifier::NamespaceAlias:
585         SaveSourceLocation(R.getBegin(), Buffer, BufferSize, BufferCapacity);
586         break;
587 
588       case NestedNameSpecifier::TypeSpec:
589       case NestedNameSpecifier::TypeSpecWithTemplate: {
590         TypeSourceInfo *TSInfo
591         = Context.getTrivialTypeSourceInfo(QualType(NNS->getAsType(), 0),
592                                            R.getBegin());
593         SavePointer(TSInfo->getTypeLoc().getOpaqueData(), Buffer, BufferSize,
594                     BufferCapacity);
595         break;
596       }
597 
598       case NestedNameSpecifier::Global:
599         break;
600     }
601 
602     // Save the location of the '::'.
603     SaveSourceLocation(Stack.empty()? R.getEnd() : R.getBegin(),
604                        Buffer, BufferSize, BufferCapacity);
605   }
606 }
607 
608 void NestedNameSpecifierLocBuilder::Adopt(NestedNameSpecifierLoc Other) {
609   if (BufferCapacity)
610     free(Buffer);
611 
612   if (!Other) {
613     Representation = 0;
614     BufferSize = 0;
615     return;
616   }
617 
618   // Rather than copying the data (which is wasteful), "adopt" the
619   // pointer (which points into the ASTContext) but set the capacity to zero to
620   // indicate that we don't own it.
621   Representation = Other.getNestedNameSpecifier();
622   Buffer = static_cast<char *>(Other.getOpaqueData());
623   BufferSize = Other.getDataLength();
624   BufferCapacity = 0;
625 }
626 
627 NestedNameSpecifierLoc
628 NestedNameSpecifierLocBuilder::getWithLocInContext(ASTContext &Context) const {
629   if (!Representation)
630     return NestedNameSpecifierLoc();
631 
632   // If we adopted our data pointer from elsewhere in the AST context, there's
633   // no need to copy the memory.
634   if (BufferCapacity == 0)
635     return NestedNameSpecifierLoc(Representation, Buffer);
636 
637   // FIXME: After copying the source-location information, should we free
638   // our (temporary) buffer and adopt the ASTContext-allocated memory?
639   // Doing so would optimize repeated calls to getWithLocInContext().
640   void *Mem = Context.Allocate(BufferSize, llvm::alignOf<void *>());
641   memcpy(Mem, Buffer, BufferSize);
642   return NestedNameSpecifierLoc(Representation, Mem);
643 }
644 
645