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