Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 1 | // Copyright 2015 Google Inc. All rights reserved |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
| 15 | #ifndef SYMTAB_H_ |
| 16 | #define SYMTAB_H_ |
| 17 | |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 18 | #include <bitset> |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 19 | #include <string> |
| 20 | #include <vector> |
| 21 | |
| 22 | #include "string_piece.h" |
| 23 | |
| 24 | using namespace std; |
| 25 | |
Shinichiro Hamaji | ba2ccdb | 2015-07-17 05:55:42 +0900 | [diff] [blame] | 26 | extern vector<string*>* g_symbols; |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 27 | |
| 28 | class Symtab; |
Shinichiro Hamaji | c9b9e5e | 2016-02-18 18:18:54 +0900 | [diff] [blame] | 29 | class Var; |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 30 | |
| 31 | class Symbol { |
| 32 | public: |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 33 | explicit Symbol() : v_(-1) {} |
Shinichiro Hamaji | 94d6f2a | 2015-07-05 05:32:25 +0900 | [diff] [blame] | 34 | |
Dan Willemsen | 3ce083f | 2017-10-11 22:17:48 -0700 | [diff] [blame] | 35 | const string& str() const { return *((*g_symbols)[v_]); } |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 36 | |
Dan Willemsen | 3ce083f | 2017-10-11 22:17:48 -0700 | [diff] [blame] | 37 | const char* c_str() const { return str().c_str(); } |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 38 | |
| 39 | bool empty() const { return !v_; } |
| 40 | |
| 41 | int val() const { return v_; } |
| 42 | |
| 43 | char get(size_t i) const { |
| 44 | const string& s = str(); |
| 45 | if (i >= s.size()) |
| 46 | return 0; |
| 47 | return s[i]; |
| 48 | } |
| 49 | |
Shinichiro Hamaji | a7984ad | 2015-09-11 16:33:16 +0900 | [diff] [blame] | 50 | bool IsValid() const { return v_ >= 0; } |
| 51 | |
Dan Willemsen | ff90ea3 | 2017-11-21 13:22:26 -0800 | [diff] [blame] | 52 | Var* PeekGlobalVar() const; |
Shinichiro Hamaji | c9b9e5e | 2016-02-18 18:18:54 +0900 | [diff] [blame] | 53 | Var* GetGlobalVar() const; |
Dan Willemsen | 3ce083f | 2017-10-11 22:17:48 -0700 | [diff] [blame] | 54 | void SetGlobalVar(Var* v, |
| 55 | bool is_override = false, |
| 56 | bool* readonly = nullptr) const; |
Shinichiro Hamaji | c9b9e5e | 2016-02-18 18:18:54 +0900 | [diff] [blame] | 57 | |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 58 | private: |
| 59 | explicit Symbol(int v); |
| 60 | |
| 61 | int v_; |
| 62 | |
| 63 | friend class Symtab; |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 64 | friend class SymbolSet; |
| 65 | }; |
| 66 | |
| 67 | /* A set of symbols represented as bitmap indexed by Symbol's ordinal value. */ |
| 68 | class SymbolSet { |
| 69 | public: |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 70 | SymbolSet() : low_(0), high_(0) {} |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 71 | |
| 72 | /* Returns true if Symbol belongs to this set. */ |
| 73 | bool exists(Symbol sym) const { |
| 74 | size_t bit_nr = static_cast<size_t>(sym.val()); |
| 75 | return sym.IsValid() && bit_nr >= low_ && bit_nr < high_ && |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 76 | bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64]; |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 77 | } |
| 78 | |
| 79 | /* Adds Symbol to this set. */ |
| 80 | void insert(Symbol sym) { |
| 81 | if (!sym.IsValid()) { |
| 82 | return; |
| 83 | } |
| 84 | size_t bit_nr = static_cast<size_t>(sym.val()); |
| 85 | if (bit_nr < low_ || bit_nr >= high_) { |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 86 | resize(bit_nr); |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 87 | } |
| 88 | bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64] = true; |
| 89 | } |
| 90 | |
| 91 | /* Returns the number of Symbol's in this set. */ |
| 92 | size_t size() const { |
| 93 | size_t n = 0; |
| 94 | for (auto const& bitset : bits_) { |
| 95 | n += bitset.count(); |
| 96 | } |
| 97 | return n; |
| 98 | } |
| 99 | |
| 100 | /* Allow using foreach. |
| 101 | * E.g., |
| 102 | * SymbolSet symbol_set; |
| 103 | * for (auto const& symbol: symbol_set) { ... } |
| 104 | */ |
| 105 | class iterator { |
| 106 | const SymbolSet* bitset_; |
| 107 | size_t pos_; |
| 108 | |
| 109 | iterator(const SymbolSet* bitset, size_t pos) |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 110 | : bitset_(bitset), pos_(pos) {} |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 111 | |
| 112 | /* Proceed to the next Symbol. */ |
| 113 | void next() { |
| 114 | size_t bit_nr = (pos_ > bitset_->low_) ? pos_ - bitset_->low_ : 0; |
| 115 | while (bit_nr < (bitset_->high_ - bitset_->low_)) { |
| 116 | if ((bit_nr % 64) == 0 && !bitset_->bits_[bit_nr / 64].any()) { |
| 117 | bit_nr += 64; |
| 118 | continue; |
| 119 | } |
| 120 | if (bitset_->bits_[bit_nr / 64][bit_nr % 64]) { |
| 121 | break; |
| 122 | } |
| 123 | ++bit_nr; |
| 124 | } |
| 125 | pos_ = bitset_->low_ + bit_nr; |
| 126 | } |
| 127 | |
| 128 | public: |
| 129 | iterator& operator++() { |
| 130 | if (pos_ < bitset_->high_) { |
| 131 | ++pos_; |
| 132 | next(); |
| 133 | } |
| 134 | return *this; |
| 135 | } |
| 136 | |
| 137 | bool operator==(iterator other) const { |
| 138 | return bitset_ == other.bitset_ && pos_ == other.pos_; |
| 139 | } |
| 140 | |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 141 | bool operator!=(iterator other) const { return !(*this == other); } |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 142 | |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 143 | Symbol operator*() { return Symbol(pos_); } |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 144 | |
| 145 | friend class SymbolSet; |
| 146 | }; |
| 147 | |
| 148 | iterator begin() const { |
| 149 | iterator it(this, low_); |
| 150 | it.next(); |
| 151 | return it; |
| 152 | } |
| 153 | |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 154 | iterator end() const { return iterator(this, high_); } |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 155 | |
| 156 | private: |
| 157 | friend class iterator; |
| 158 | |
| 159 | /* Ensure that given bit number is in [low_, high_) */ |
| 160 | void resize(size_t bit_nr) { |
| 161 | size_t new_low = bit_nr & ~63; |
| 162 | size_t new_high = (bit_nr + 64) & ~63; |
| 163 | if (bits_.empty()) { |
| 164 | high_ = low_ = new_low; |
| 165 | } |
| 166 | if (new_low > low_) { |
| 167 | new_low = low_; |
| 168 | } |
| 169 | if (new_high <= high_) { |
| 170 | new_high = high_; |
| 171 | } |
| 172 | if (new_low == low_) { |
| 173 | bits_.resize((new_high - new_low) / 64); |
| 174 | } else { |
Dan Willemsen | ee57a3f | 2018-11-05 16:18:44 -0800 | [diff] [blame] | 175 | std::vector<std::bitset<64> > newbits((new_high - new_low) / 64); |
| 176 | std::copy(bits_.begin(), bits_.end(), |
| 177 | newbits.begin() + (low_ - new_low) / 64); |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 178 | bits_.swap(newbits); |
| 179 | } |
| 180 | low_ = new_low; |
| 181 | high_ = new_high; |
| 182 | } |
| 183 | |
| 184 | /* Keep only the (aligned) range where at least one bit has been set. |
| 185 | * E.g., if we only ever set bits 65 and 141, |low_| will be 64, |high_| |
| 186 | * will be 192, and |bits_| will have 2 elements. |
| 187 | */ |
| 188 | size_t low_; |
| 189 | size_t high_; |
| 190 | std::vector<std::bitset<64> > bits_; |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 191 | }; |
| 192 | |
Shinichiro Hamaji | c9b9e5e | 2016-02-18 18:18:54 +0900 | [diff] [blame] | 193 | class ScopedGlobalVar { |
| 194 | public: |
| 195 | ScopedGlobalVar(Symbol name, Var* var); |
| 196 | ~ScopedGlobalVar(); |
| 197 | |
| 198 | private: |
| 199 | Symbol name_; |
| 200 | Var* orig_; |
| 201 | }; |
| 202 | |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 203 | inline bool operator==(const Symbol& x, const Symbol& y) { |
| 204 | return x.val() == y.val(); |
| 205 | } |
| 206 | |
Dan Willemsen | b248caa | 2015-10-01 16:07:48 -0700 | [diff] [blame] | 207 | inline bool operator<(const Symbol& x, const Symbol& y) { |
Shinichiro Hamaji | 675ecf3 | 2015-10-03 10:57:31 +0900 | [diff] [blame] | 208 | return x.val() < y.val(); |
Dan Willemsen | b248caa | 2015-10-01 16:07:48 -0700 | [diff] [blame] | 209 | } |
| 210 | |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 211 | namespace std { |
Dan Willemsen | 3ce083f | 2017-10-11 22:17:48 -0700 | [diff] [blame] | 212 | template <> |
| 213 | struct hash<Symbol> { |
| 214 | size_t operator()(const Symbol& s) const { return s.val(); } |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 215 | }; |
Dan Willemsen | 3ce083f | 2017-10-11 22:17:48 -0700 | [diff] [blame] | 216 | } // namespace std |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 217 | |
Shinichiro Hamaji | 43defe0 | 2015-07-11 07:06:43 +0900 | [diff] [blame] | 218 | extern Symbol kEmptySym; |
Shinichiro Hamaji | 94d6f2a | 2015-07-05 05:32:25 +0900 | [diff] [blame] | 219 | extern Symbol kShellSym; |
Sasha Smundak | 8174f9b | 2018-08-13 11:07:30 -0700 | [diff] [blame] | 220 | extern Symbol kKatiReadonlySym; |
Shinichiro Hamaji | 94d6f2a | 2015-07-05 05:32:25 +0900 | [diff] [blame] | 221 | |
Shinichiro Hamaji | e799275 | 2015-06-29 18:38:35 +0900 | [diff] [blame] | 222 | void InitSymtab(); |
| 223 | void QuitSymtab(); |
| 224 | Symbol Intern(StringPiece s); |
| 225 | |
| 226 | string JoinSymbols(const vector<Symbol>& syms, const char* sep); |
| 227 | |
| 228 | #endif // SYMTAB_H_ |