Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Redistribution and use in source and binary forms, with or without
3 : // modification, are permitted provided that the following conditions are
4 : // met:
5 : //
6 : // * Redistributions of source code must retain the above copyright
7 : // notice, this list of conditions and the following disclaimer.
8 : // * Redistributions in binary form must reproduce the above
9 : // copyright notice, this list of conditions and the following
10 : // disclaimer in the documentation and/or other materials provided
11 : // with the distribution.
12 : // * Neither the name of Google Inc. nor the names of its
13 : // contributors may be used to endorse or promote products derived
14 : // from this software without specific prior written permission.
15 : //
16 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 :
28 : #include "src/ast/ast-value-factory.h"
29 :
30 : #include "src/char-predicates-inl.h"
31 : #include "src/objects-inl.h"
32 : #include "src/objects.h"
33 : #include "src/string-hasher.h"
34 : #include "src/utils-inl.h"
35 :
36 : namespace v8 {
37 : namespace internal {
38 :
39 : namespace {
40 :
41 : // For using StringToArrayIndex.
42 : class OneByteStringStream {
43 : public:
44 : explicit OneByteStringStream(Vector<const byte> lb) :
45 156 : literal_bytes_(lb), pos_(0) {}
46 :
47 1550 : bool HasMore() { return pos_ < literal_bytes_.length(); }
48 3100 : uint16_t GetNext() { return literal_bytes_[pos_++]; }
49 :
50 : private:
51 : Vector<const byte> literal_bytes_;
52 : int pos_;
53 : };
54 :
55 : } // namespace
56 :
57 26202170 : class AstRawStringInternalizationKey : public StringTableKey {
58 : public:
59 : explicit AstRawStringInternalizationKey(const AstRawString* string)
60 26202163 : : StringTableKey(string->hash_field()), string_(string) {}
61 :
62 72124975 : bool IsMatch(Object other) override {
63 72124975 : if (string_->is_one_byte())
64 72049216 : return String::cast(other)->IsOneByteEqualTo(string_->literal_bytes_);
65 151518 : return String::cast(other)->IsTwoByteEqualTo(
66 75759 : Vector<const uint16_t>::cast(string_->literal_bytes_));
67 : }
68 :
69 8612316 : Handle<String> AsHandle(Isolate* isolate) override {
70 8612316 : if (string_->is_one_byte())
71 : return isolate->factory()->NewOneByteInternalizedString(
72 8559319 : string_->literal_bytes_, string_->hash_field());
73 : return isolate->factory()->NewTwoByteInternalizedString(
74 : Vector<const uint16_t>::cast(string_->literal_bytes_),
75 52997 : string_->hash_field());
76 : }
77 :
78 : private:
79 : const AstRawString* string_;
80 : };
81 :
82 26202163 : void AstRawString::Internalize(Isolate* isolate) {
83 : DCHECK(!has_string_);
84 26202163 : if (literal_bytes_.length() == 0) {
85 : set_string(isolate->factory()->empty_string());
86 : } else {
87 : AstRawStringInternalizationKey key(this);
88 26202163 : set_string(StringTable::LookupKey(isolate, &key));
89 : }
90 26202170 : }
91 :
92 11534780 : bool AstRawString::AsArrayIndex(uint32_t* index) const {
93 : // The StringHasher will set up the hash in such a way that we can use it to
94 : // figure out whether the string is convertible to an array index.
95 11534780 : if ((hash_field_ & Name::kIsNotArrayIndexMask) != 0) return false;
96 4414 : if (length() <= Name::kMaxCachedArrayIndexLength) {
97 4258 : *index = Name::ArrayIndexValueBits::decode(hash_field_);
98 : } else {
99 : OneByteStringStream stream(literal_bytes_);
100 156 : CHECK(StringToArrayIndex(&stream, index));
101 : }
102 : return true;
103 : }
104 :
105 214127 : bool AstRawString::IsOneByteEqualTo(const char* data) const {
106 214127 : if (!is_one_byte()) return false;
107 :
108 214129 : size_t length = static_cast<size_t>(literal_bytes_.length());
109 214129 : if (length != strlen(data)) return false;
110 :
111 57997 : return 0 == strncmp(reinterpret_cast<const char*>(literal_bytes_.start()),
112 57997 : data, length);
113 : }
114 :
115 7975562 : uint16_t AstRawString::FirstCharacter() const {
116 7975562 : if (is_one_byte()) return literal_bytes_[0];
117 : const uint16_t* c = reinterpret_cast<const uint16_t*>(literal_bytes_.start());
118 18 : return *c;
119 : }
120 :
121 50487330 : bool AstRawString::Compare(void* a, void* b) {
122 : const AstRawString* lhs = static_cast<AstRawString*>(a);
123 : const AstRawString* rhs = static_cast<AstRawString*>(b);
124 : DCHECK_EQ(lhs->Hash(), rhs->Hash());
125 :
126 50487330 : if (lhs->length() != rhs->length()) return false;
127 50487421 : if (lhs->length() == 0) return true;
128 : const unsigned char* l = lhs->raw_data();
129 : const unsigned char* r = rhs->raw_data();
130 49869717 : size_t length = rhs->length();
131 49869717 : if (lhs->is_one_byte()) {
132 49858558 : if (rhs->is_one_byte()) {
133 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l),
134 : reinterpret_cast<const uint8_t*>(r),
135 49858552 : length) == 0;
136 : } else {
137 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l),
138 : reinterpret_cast<const uint16_t*>(r),
139 6 : length) == 0;
140 : }
141 : } else {
142 11159 : if (rhs->is_one_byte()) {
143 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l),
144 : reinterpret_cast<const uint8_t*>(r),
145 0 : length) == 0;
146 : } else {
147 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l),
148 : reinterpret_cast<const uint16_t*>(r),
149 11159 : length) == 0;
150 : }
151 : }
152 : }
153 :
154 8525360 : void AstConsString::Internalize(Isolate* isolate) {
155 8525360 : if (IsEmpty()) {
156 : set_string(isolate->factory()->empty_string());
157 : return;
158 : }
159 : // AstRawStrings are internalized before AstConsStrings, so
160 : // AstRawString::string() will just work.
161 : Handle<String> tmp(segment_.string->string());
162 3805521 : for (AstConsString::Segment* current = segment_.next; current != nullptr;
163 : current = current->next) {
164 : tmp = isolate->factory()
165 958011 : ->NewConsString(current->string->string(), tmp)
166 : .ToHandleChecked();
167 : }
168 : set_string(tmp);
169 : }
170 :
171 17 : std::forward_list<const AstRawString*> AstConsString::ToRawStrings() const {
172 : std::forward_list<const AstRawString*> result;
173 17 : if (IsEmpty()) {
174 : return result;
175 : }
176 :
177 17 : result.emplace_front(segment_.string);
178 17 : for (AstConsString::Segment* current = segment_.next; current != nullptr;
179 : current = current->next) {
180 0 : result.emplace_front(current->string);
181 : }
182 : return result;
183 : }
184 :
185 61534 : AstStringConstants::AstStringConstants(Isolate* isolate, uint64_t hash_seed)
186 : : zone_(isolate->allocator(), ZONE_NAME),
187 : string_table_(AstRawString::Compare),
188 123068 : hash_seed_(hash_seed) {
189 : DCHECK_EQ(ThreadId::Current(), isolate->thread_id());
190 : #define F(name, str) \
191 : { \
192 : const char* data = str; \
193 : Vector<const uint8_t> literal(reinterpret_cast<const uint8_t*>(data), \
194 : static_cast<int>(strlen(data))); \
195 : uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>( \
196 : literal.start(), literal.length(), hash_seed_); \
197 : name##_string_ = new (&zone_) AstRawString(true, literal, hash_field); \
198 : /* The Handle returned by the factory is located on the roots */ \
199 : /* array, not on the temporary HandleScope, so this is safe. */ \
200 : name##_string_->set_string(isolate->factory()->name##_string()); \
201 : base::HashMap::Entry* entry = \
202 : string_table_.InsertNew(name##_string_, name##_string_->Hash()); \
203 : DCHECK_NULL(entry->value); \
204 : entry->value = reinterpret_cast<void*>(1); \
205 : }
206 9476203 : AST_STRING_CONSTANTS(F)
207 : #undef F
208 61534 : }
209 :
210 91548154 : AstRawString* AstValueFactory::GetOneByteStringInternal(
211 : Vector<const uint8_t> literal) {
212 91548154 : if (literal.length() == 1 && literal[0] < kMaxOneCharStringValue) {
213 18729137 : int key = literal[0];
214 18729137 : if (V8_UNLIKELY(one_character_strings_[key] == nullptr)) {
215 3738059 : uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>(
216 3738059 : literal.start(), literal.length(), hash_seed_);
217 3738056 : one_character_strings_[key] = GetString(hash_field, true, literal);
218 : }
219 18729138 : return one_character_strings_[key];
220 : }
221 72819017 : uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>(
222 72819017 : literal.start(), literal.length(), hash_seed_);
223 72819329 : return GetString(hash_field, true, literal);
224 : }
225 :
226 77288 : AstRawString* AstValueFactory::GetTwoByteStringInternal(
227 : Vector<const uint16_t> literal) {
228 77288 : uint32_t hash_field = StringHasher::HashSequentialString<uint16_t>(
229 77288 : literal.start(), literal.length(), hash_seed_);
230 77287 : return GetString(hash_field, false, Vector<const byte>::cast(literal));
231 : }
232 :
233 722211 : const AstRawString* AstValueFactory::GetString(Handle<String> literal) {
234 : AstRawString* result = nullptr;
235 : DisallowHeapAllocation no_gc;
236 722211 : String::FlatContent content = literal->GetFlatContent(no_gc);
237 722211 : if (content.IsOneByte()) {
238 722194 : result = GetOneByteStringInternal(content.ToOneByteVector());
239 : } else {
240 : DCHECK(content.IsTwoByte());
241 17 : result = GetTwoByteStringInternal(content.ToUC16Vector());
242 : }
243 722211 : return result;
244 : }
245 :
246 80 : const AstRawString* AstValueFactory::CloneFromOtherFactory(
247 : const AstRawString* raw_string) {
248 240 : const AstRawString* result = GetString(
249 : raw_string->hash_field(), raw_string->is_one_byte(),
250 80 : Vector<const byte>(raw_string->raw_data(), raw_string->byte_length()));
251 80 : return result;
252 : }
253 :
254 3430670 : AstConsString* AstValueFactory::NewConsString() {
255 3430670 : AstConsString* new_string = new (zone_) AstConsString;
256 : DCHECK_NOT_NULL(new_string);
257 : AddConsString(new_string);
258 3430677 : return new_string;
259 : }
260 :
261 6918547 : AstConsString* AstValueFactory::NewConsString(const AstRawString* str) {
262 13837081 : return NewConsString()->AddString(zone_, str);
263 : }
264 :
265 27671 : AstConsString* AstValueFactory::NewConsString(const AstRawString* str1,
266 : const AstRawString* str2) {
267 55342 : return NewConsString()->AddString(zone_, str1)->AddString(zone_, str2);
268 : }
269 :
270 3792041 : void AstValueFactory::Internalize(Isolate* isolate) {
271 : // Strings need to be internalized before values, because values refer to
272 : // strings.
273 29994206 : for (AstRawString* current = strings_; current != nullptr;) {
274 : AstRawString* next = current->next();
275 26202171 : current->Internalize(isolate);
276 : current = next;
277 : }
278 :
279 : // AstConsStrings refer to AstRawStrings.
280 12317395 : for (AstConsString* current = cons_strings_; current != nullptr;) {
281 : AstConsString* next = current->next();
282 8525360 : current->Internalize(isolate);
283 : current = next;
284 : }
285 :
286 : ResetStrings();
287 3792035 : }
288 :
289 76638354 : AstRawString* AstValueFactory::GetString(uint32_t hash_field, bool is_one_byte,
290 : Vector<const byte> literal_bytes) {
291 : // literal_bytes here points to whatever the user passed, and this is OK
292 : // because we use vector_compare (which checks the contents) to compare
293 : // against the AstRawStrings which are in the string_table_. We should not
294 : // return this AstRawString.
295 : AstRawString key(is_one_byte, literal_bytes, hash_field);
296 153283133 : base::HashMap::Entry* entry = string_table_.LookupOrInsert(&key, key.Hash());
297 76644779 : if (entry->value == nullptr) {
298 : // Copy literal contents for later comparison.
299 : int length = literal_bytes.length();
300 29165805 : byte* new_literal_bytes = zone_->NewArray<byte>(length);
301 : memcpy(new_literal_bytes, literal_bytes.start(), length);
302 : AstRawString* new_string = new (zone_) AstRawString(
303 29165735 : is_one_byte, Vector<const byte>(new_literal_bytes, length), hash_field);
304 29165528 : CHECK_NOT_NULL(new_string);
305 : AddString(new_string);
306 29165528 : entry->key = new_string;
307 29165528 : entry->value = reinterpret_cast<void*>(1);
308 : }
309 76644502 : return reinterpret_cast<AstRawString*>(entry->key);
310 : }
311 :
312 : } // namespace internal
313 120216 : } // namespace v8
|