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