1 //===- IdentifierResolver.h - Lexical Scope Name lookup ---------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the IdentifierResolver class, which is used for lexical
10 // scoped lookup, based on declaration names.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H
15 #define LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H
16 
17 #include "clang/Basic/LLVM.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include <cassert>
20 #include <cstddef>
21 #include <cstdint>
22 #include <iterator>
23 
24 namespace clang {
25 
26 class Decl;
27 class DeclarationName;
28 class DeclContext;
29 class IdentifierInfo;
30 class LangOptions;
31 class NamedDecl;
32 class Preprocessor;
33 class Scope;
34 
35 /// IdentifierResolver - Keeps track of shadowed decls on enclosing
36 /// scopes.  It manages the shadowing chains of declaration names and
37 /// implements efficient decl lookup based on a declaration name.
38 class IdentifierResolver {
39   /// IdDeclInfo - Keeps track of information about decls associated
40   /// to a particular declaration name. IdDeclInfos are lazily
41   /// constructed and assigned to a declaration name the first time a
42   /// decl with that declaration name is shadowed in some scope.
43   class IdDeclInfo {
44   public:
45     using DeclsTy = SmallVector<NamedDecl *, 2>;
46 
47     DeclsTy::iterator decls_begin() { return Decls.begin(); }
48     DeclsTy::iterator decls_end() { return Decls.end(); }
49 
50     void AddDecl(NamedDecl *D) { Decls.push_back(D); }
51 
52     /// RemoveDecl - Remove the decl from the scope chain.
53     /// The decl must already be part of the decl chain.
54     void RemoveDecl(NamedDecl *D);
55 
56     /// Insert the given declaration at the given position in the list.
57     void InsertDecl(DeclsTy::iterator Pos, NamedDecl *D) {
58       Decls.insert(Pos, D);
59     }
60 
61   private:
62     DeclsTy Decls;
63   };
64 
65 public:
66   /// iterator - Iterate over the decls of a specified declaration name.
67   /// It will walk or not the parent declaration contexts depending on how
68   /// it was instantiated.
69   class iterator {
70   public:
71     friend class IdentifierResolver;
72 
73     using value_type = NamedDecl *;
74     using reference = NamedDecl *;
75     using pointer = NamedDecl *;
76     using iterator_category = std::input_iterator_tag;
77     using difference_type = std::ptrdiff_t;
78 
79     /// Ptr - There are 2 forms that 'Ptr' represents:
80     /// 1) A single NamedDecl. (Ptr & 0x1 == 0)
81     /// 2) A IdDeclInfo::DeclsTy::iterator that traverses only the decls of the
82     ///    same declaration context. (Ptr & 0x1 == 0x1)
83     uintptr_t Ptr = 0;
84     using BaseIter = IdDeclInfo::DeclsTy::iterator;
85 
86     /// A single NamedDecl. (Ptr & 0x1 == 0)
87     iterator(NamedDecl *D) {
88       Ptr = reinterpret_cast<uintptr_t>(D);
89       assert((Ptr & 0x1) == 0 && "Invalid Ptr!");
90     }
91 
92     /// A IdDeclInfo::DeclsTy::iterator that walks or not the parent declaration
93     /// contexts depending on 'LookInParentCtx'.
94     iterator(BaseIter I) {
95       Ptr = reinterpret_cast<uintptr_t>(I) | 0x1;
96     }
97 
98     bool isIterator() const { return (Ptr & 0x1); }
99 
100     BaseIter getIterator() const {
101       assert(isIterator() && "Ptr not an iterator!");
102       return reinterpret_cast<BaseIter>(Ptr & ~0x1);
103     }
104 
105     void incrementSlowCase();
106 
107   public:
108     iterator() = default;
109 
110     NamedDecl *operator*() const {
111       if (isIterator())
112         return *getIterator();
113       else
114         return reinterpret_cast<NamedDecl*>(Ptr);
115     }
116 
117     bool operator==(const iterator &RHS) const {
118       return Ptr == RHS.Ptr;
119     }
120     bool operator!=(const iterator &RHS) const {
121       return Ptr != RHS.Ptr;
122     }
123 
124     // Preincrement.
125     iterator& operator++() {
126       if (!isIterator()) // common case.
127         Ptr = 0;
128       else
129         incrementSlowCase();
130       return *this;
131     }
132   };
133 
134   explicit IdentifierResolver(Preprocessor &PP);
135   ~IdentifierResolver();
136 
137   IdentifierResolver(const IdentifierResolver &) = delete;
138   IdentifierResolver &operator=(const IdentifierResolver &) = delete;
139 
140   /// Returns a range of decls with the name 'Name'.
141   llvm::iterator_range<iterator> decls(DeclarationName Name);
142 
143   /// Returns an iterator over decls with the name 'Name'.
144   iterator begin(DeclarationName Name);
145 
146   /// Returns the end iterator.
147   iterator end() { return iterator(); }
148 
149   /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
150   /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
151   /// true if 'D' belongs to the given declaration context.
152   ///
153   /// \param AllowInlineNamespace If \c true, we are checking whether a prior
154   ///        declaration is in scope in a declaration that requires a prior
155   ///        declaration (because it is either explicitly qualified or is a
156   ///        template instantiation or specialization). In this case, a
157   ///        declaration is in scope if it's in the inline namespace set of the
158   ///        context.
159   bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S = nullptr,
160                      bool AllowInlineNamespace = false) const;
161 
162   /// AddDecl - Link the decl to its shadowed decl chain.
163   void AddDecl(NamedDecl *D);
164 
165   /// RemoveDecl - Unlink the decl from its shadowed decl chain.
166   /// The decl must already be part of the decl chain.
167   void RemoveDecl(NamedDecl *D);
168 
169   /// Insert the given declaration after the given iterator
170   /// position.
171   void InsertDeclAfter(iterator Pos, NamedDecl *D);
172 
173   /// Try to add the given declaration to the top level scope, if it
174   /// (or a redeclaration of it) hasn't already been added.
175   ///
176   /// \param D The externally-produced declaration to add.
177   ///
178   /// \param Name The name of the externally-produced declaration.
179   ///
180   /// \returns true if the declaration was added, false otherwise.
181   bool tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name);
182 
183 private:
184   const LangOptions &LangOpt;
185   Preprocessor &PP;
186 
187   class IdDeclInfoMap;
188   IdDeclInfoMap *IdDeclInfos;
189 
190   void updatingIdentifier(IdentifierInfo &II);
191   void readingIdentifier(IdentifierInfo &II);
192 
193   /// FETokenInfo contains a Decl pointer if lower bit == 0.
194   static inline bool isDeclPtr(void *Ptr) {
195     return (reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 0;
196   }
197 
198   /// FETokenInfo contains a IdDeclInfo pointer if lower bit == 1.
199   static inline IdDeclInfo *toIdDeclInfo(void *Ptr) {
200     assert((reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 1
201           && "Ptr not a IdDeclInfo* !");
202     return reinterpret_cast<IdDeclInfo*>(
203                     reinterpret_cast<uintptr_t>(Ptr) & ~0x1);
204   }
205 };
206 
207 } // namespace clang
208 
209 #endif // LLVM_CLANG_SEMA_IDENTIFIERRESOLVER_H
210