1// Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_CANONICAL_TABLES_H_
6#define RUNTIME_VM_CANONICAL_TABLES_H_
7
8#include "platform/assert.h"
9#include "vm/hash_table.h"
10#include "vm/object.h"
11
12namespace dart {
13
14template <typename CharType>
15class CharArray {
16 public:
17 CharArray(const CharType* data, intptr_t len) : data_(data), len_(len) {
18 hash_ = String::Hash(data, len);
19 }
20 StringPtr ToSymbol() const {
21 String& result = String::Handle(StringFrom(data_, len_, Heap::kOld));
22 result.SetCanonical();
23 result.SetHash(hash_);
24 return result.ptr();
25 }
26 bool Equals(const String& other) const {
27 ASSERT(other.HasHash());
28 if (other.Hash() != hash_) {
29 return false;
30 }
31 return other.Equals(data_, len_);
32 }
33 uword Hash() const { return hash_; }
34
35 private:
36 const CharType* data_;
37 intptr_t len_;
38 uword hash_;
39};
40typedef CharArray<uint8_t> Latin1Array;
41typedef CharArray<uint16_t> UTF16Array;
42typedef CharArray<int32_t> UTF32Array;
43
44class StringSlice {
45 public:
46 StringSlice(const String& str, intptr_t begin_index, intptr_t length)
47 : str_(str), begin_index_(begin_index), len_(length) {
48 hash_ = is_all() ? str.Hash() : String::Hash(str, begin_index, len: length);
49 }
50 StringPtr ToSymbol() const;
51 bool Equals(const String& other) const {
52 ASSERT(other.HasHash());
53 if (other.Hash() != hash_) {
54 return false;
55 }
56 return other.Equals(str: str_, begin_index: begin_index_, len: len_);
57 }
58 uword Hash() const { return hash_; }
59
60 private:
61 bool is_all() const { return begin_index_ == 0 && len_ == str_.Length(); }
62 const String& str_;
63 intptr_t begin_index_;
64 intptr_t len_;
65 uword hash_;
66};
67
68class ConcatString {
69 public:
70 ConcatString(const String& str1, const String& str2)
71 : str1_(str1), str2_(str2), hash_(String::HashConcat(str1, str2)) {}
72 StringPtr ToSymbol() const;
73 bool Equals(const String& other) const {
74 ASSERT(other.HasHash());
75 if (other.Hash() != hash_) {
76 return false;
77 }
78 return other.EqualsConcat(str1: str1_, str2: str2_);
79 }
80 uword Hash() const { return hash_; }
81
82 private:
83 const String& str1_;
84 const String& str2_;
85 uword hash_;
86};
87
88class SymbolTraits {
89 public:
90 static const char* Name() { return "SymbolTraits"; }
91 static bool ReportStats() { return false; }
92
93 static bool IsMatch(const Object& a, const Object& b) {
94 const String& a_str = String::Cast(obj: a);
95 const String& b_str = String::Cast(obj: b);
96 ASSERT(a_str.HasHash());
97 ASSERT(b_str.HasHash());
98 if (a_str.Hash() != b_str.Hash()) {
99 return false;
100 }
101 intptr_t a_len = a_str.Length();
102 if (a_len != b_str.Length()) {
103 return false;
104 }
105 // Use a comparison which does not consider the state of the canonical bit.
106 return a_str.Equals(str: b_str, begin_index: 0, len: a_len);
107 }
108 template <typename CharType>
109 static bool IsMatch(const CharArray<CharType>& array, const Object& obj) {
110 return array.Equals(String::Cast(obj));
111 }
112 static bool IsMatch(const StringSlice& slice, const Object& obj) {
113 return slice.Equals(other: String::Cast(obj));
114 }
115 static bool IsMatch(const ConcatString& concat, const Object& obj) {
116 return concat.Equals(other: String::Cast(obj));
117 }
118 static uword Hash(const Object& key) { return String::Cast(obj: key).Hash(); }
119 template <typename CharType>
120 static uword Hash(const CharArray<CharType>& array) {
121 return array.Hash();
122 }
123 static uword Hash(const StringSlice& slice) { return slice.Hash(); }
124 static uword Hash(const ConcatString& concat) { return concat.Hash(); }
125 template <typename CharType>
126 static ObjectPtr NewKey(const CharArray<CharType>& array) {
127 return array.ToSymbol();
128 }
129 static ObjectPtr NewKey(const StringSlice& slice) { return slice.ToSymbol(); }
130 static ObjectPtr NewKey(const ConcatString& concat) {
131 return concat.ToSymbol();
132 }
133};
134
135typedef UnorderedHashSet<SymbolTraits, WeakAcqRelStorageTraits>
136 CanonicalStringSet;
137
138class CanonicalTypeKey {
139 public:
140 explicit CanonicalTypeKey(const Type& key) : key_(key) {}
141 bool Matches(const Type& arg) const { return key_.Equals(other: arg); }
142 uword Hash() const { return key_.Hash(); }
143 const Type& key_;
144
145 private:
146 DISALLOW_ALLOCATION();
147};
148
149// Traits for looking up Canonical Type based on its hash.
150class CanonicalTypeTraits {
151 public:
152 static const char* Name() { return "CanonicalTypeTraits"; }
153 static bool ReportStats() { return false; }
154
155 // Called when growing the table.
156 static bool IsMatch(const Object& a, const Object& b) {
157 ASSERT(a.IsType() && b.IsType());
158 const Type& arg1 = Type::Cast(obj: a);
159 const Type& arg2 = Type::Cast(obj: b);
160 return arg1.Equals(other: arg2) && (arg1.Hash() == arg2.Hash());
161 }
162 static bool IsMatch(const CanonicalTypeKey& a, const Object& b) {
163 ASSERT(b.IsType());
164 return a.Matches(arg: Type::Cast(obj: b));
165 }
166 static uword Hash(const Object& key) {
167 ASSERT(key.IsType());
168 return Type::Cast(obj: key).Hash();
169 }
170 static uword Hash(const CanonicalTypeKey& key) { return key.Hash(); }
171 static ObjectPtr NewKey(const CanonicalTypeKey& obj) {
172 return obj.key_.ptr();
173 }
174};
175typedef UnorderedHashSet<CanonicalTypeTraits> CanonicalTypeSet;
176
177class CanonicalFunctionTypeKey {
178 public:
179 explicit CanonicalFunctionTypeKey(const FunctionType& key) : key_(key) {}
180 bool Matches(const FunctionType& arg) const { return key_.Equals(other: arg); }
181 uword Hash() const { return key_.Hash(); }
182 const FunctionType& key_;
183
184 private:
185 DISALLOW_ALLOCATION();
186};
187
188// Traits for looking up Canonical FunctionType based on its hash.
189class CanonicalFunctionTypeTraits {
190 public:
191 static const char* Name() { return "CanonicalFunctionTypeTraits"; }
192 static bool ReportStats() { return false; }
193
194 // Called when growing the table.
195 static bool IsMatch(const Object& a, const Object& b) {
196 ASSERT(a.IsFunctionType() && b.IsFunctionType());
197 const FunctionType& arg1 = FunctionType::Cast(obj: a);
198 const FunctionType& arg2 = FunctionType::Cast(obj: b);
199 return arg1.Equals(other: arg2) && (arg1.Hash() == arg2.Hash());
200 }
201 static bool IsMatch(const CanonicalFunctionTypeKey& a, const Object& b) {
202 ASSERT(b.IsFunctionType());
203 return a.Matches(arg: FunctionType::Cast(obj: b));
204 }
205 static uword Hash(const Object& key) {
206 ASSERT(key.IsFunctionType());
207 return FunctionType::Cast(obj: key).Hash();
208 }
209 static uword Hash(const CanonicalFunctionTypeKey& key) { return key.Hash(); }
210 static ObjectPtr NewKey(const CanonicalFunctionTypeKey& obj) {
211 return obj.key_.ptr();
212 }
213};
214typedef UnorderedHashSet<CanonicalFunctionTypeTraits> CanonicalFunctionTypeSet;
215
216class CanonicalRecordTypeKey {
217 public:
218 explicit CanonicalRecordTypeKey(const RecordType& key) : key_(key) {}
219 bool Matches(const RecordType& arg) const { return key_.Equals(other: arg); }
220 uword Hash() const { return key_.Hash(); }
221 const RecordType& key_;
222
223 private:
224 DISALLOW_ALLOCATION();
225};
226
227// Traits for looking up Canonical RecordType based on its hash.
228class CanonicalRecordTypeTraits {
229 public:
230 static const char* Name() { return "CanonicalRecordTypeTraits"; }
231 static bool ReportStats() { return false; }
232
233 // Called when growing the table.
234 static bool IsMatch(const Object& a, const Object& b) {
235 ASSERT(a.IsRecordType() && b.IsRecordType());
236 const RecordType& arg1 = RecordType::Cast(obj: a);
237 const RecordType& arg2 = RecordType::Cast(obj: b);
238 return arg1.Equals(other: arg2) && (arg1.Hash() == arg2.Hash());
239 }
240 static bool IsMatch(const CanonicalRecordTypeKey& a, const Object& b) {
241 ASSERT(b.IsRecordType());
242 return a.Matches(arg: RecordType::Cast(obj: b));
243 }
244 static uword Hash(const Object& key) {
245 ASSERT(key.IsRecordType());
246 return RecordType::Cast(obj: key).Hash();
247 }
248 static uword Hash(const CanonicalRecordTypeKey& key) { return key.Hash(); }
249 static ObjectPtr NewKey(const CanonicalRecordTypeKey& obj) {
250 return obj.key_.ptr();
251 }
252};
253typedef UnorderedHashSet<CanonicalRecordTypeTraits> CanonicalRecordTypeSet;
254
255class CanonicalTypeParameterKey {
256 public:
257 explicit CanonicalTypeParameterKey(const TypeParameter& key) : key_(key) {}
258 bool Matches(const TypeParameter& arg) const { return key_.Equals(other: arg); }
259 uword Hash() const { return key_.Hash(); }
260 const TypeParameter& key_;
261
262 private:
263 DISALLOW_ALLOCATION();
264};
265
266// Traits for looking up Canonical TypeParameter based on its hash.
267class CanonicalTypeParameterTraits {
268 public:
269 static const char* Name() { return "CanonicalTypeParameterTraits"; }
270 static bool ReportStats() { return false; }
271
272 // Called when growing the table.
273 static bool IsMatch(const Object& a, const Object& b) {
274 ASSERT(a.IsTypeParameter() && b.IsTypeParameter());
275 const TypeParameter& arg1 = TypeParameter::Cast(obj: a);
276 const TypeParameter& arg2 = TypeParameter::Cast(obj: b);
277 return arg1.Equals(other: arg2) && (arg1.Hash() == arg2.Hash());
278 }
279 static bool IsMatch(const CanonicalTypeParameterKey& a, const Object& b) {
280 ASSERT(b.IsTypeParameter());
281 return a.Matches(arg: TypeParameter::Cast(obj: b));
282 }
283 static uword Hash(const Object& key) {
284 ASSERT(key.IsTypeParameter());
285 return TypeParameter::Cast(obj: key).Hash();
286 }
287 static uword Hash(const CanonicalTypeParameterKey& key) { return key.Hash(); }
288 static ObjectPtr NewKey(const CanonicalTypeParameterKey& obj) {
289 return obj.key_.ptr();
290 }
291};
292typedef UnorderedHashSet<CanonicalTypeParameterTraits>
293 CanonicalTypeParameterSet;
294
295class CanonicalTypeArgumentsKey {
296 public:
297 explicit CanonicalTypeArgumentsKey(const TypeArguments& key) : key_(key) {}
298 bool Matches(const TypeArguments& arg) const {
299 return key_.Equals(other: arg) && (key_.Hash() == arg.Hash());
300 }
301 uword Hash() const { return key_.Hash(); }
302 const TypeArguments& key_;
303
304 private:
305 DISALLOW_ALLOCATION();
306};
307
308// Traits for looking up Canonical TypeArguments based on its hash.
309class CanonicalTypeArgumentsTraits {
310 public:
311 static const char* Name() { return "CanonicalTypeArgumentsTraits"; }
312 static bool ReportStats() { return false; }
313
314 // Called when growing the table.
315 static bool IsMatch(const Object& a, const Object& b) {
316 ASSERT(a.IsTypeArguments() && b.IsTypeArguments());
317 const TypeArguments& arg1 = TypeArguments::Cast(obj: a);
318 const TypeArguments& arg2 = TypeArguments::Cast(obj: b);
319 return arg1.Equals(other: arg2) && (arg1.Hash() == arg2.Hash());
320 }
321 static bool IsMatch(const CanonicalTypeArgumentsKey& a, const Object& b) {
322 ASSERT(b.IsTypeArguments());
323 return a.Matches(arg: TypeArguments::Cast(obj: b));
324 }
325 static uword Hash(const Object& key) {
326 ASSERT(key.IsTypeArguments());
327 return TypeArguments::Cast(obj: key).Hash();
328 }
329 static uword Hash(const CanonicalTypeArgumentsKey& key) { return key.Hash(); }
330 static ObjectPtr NewKey(const CanonicalTypeArgumentsKey& obj) {
331 return obj.key_.ptr();
332 }
333};
334typedef UnorderedHashSet<CanonicalTypeArgumentsTraits>
335 CanonicalTypeArgumentsSet;
336
337class MetadataMapTraits {
338 public:
339 static const char* Name() { return "MetadataMapTraits"; }
340 static bool ReportStats() { return false; }
341 static bool IsMatch(const Object& a, const Object& b);
342 static uword Hash(const Object& key);
343};
344typedef UnorderedHashMap<MetadataMapTraits> MetadataMap;
345
346class DispatcherKey {
347 public:
348 DispatcherKey(const String& name,
349 const Array& args_desc,
350 UntaggedFunction::Kind kind)
351 : name_(name), args_desc_(args_desc), kind_(kind) {}
352 bool Equals(const Function& other) const {
353 return (name_.ptr() == other.name()) &&
354 (args_desc_.ptr() == other.saved_args_desc()) &&
355 (kind_ == other.kind());
356 }
357 uword Hash() const { return CombineHashes(hash: name_.Hash(), other_hash: kind_); }
358
359 private:
360 const String& name_;
361 const Array& args_desc_;
362 UntaggedFunction::Kind kind_;
363};
364
365class DispatcherTraits {
366 public:
367 static const char* Name() { return "DispatcherTraits"; }
368 static bool ReportStats() { return false; }
369
370 // Called when growing the table.
371 static bool IsMatch(const Object& a, const Object& b) {
372 const Function& a_func = Function::Cast(obj: a);
373 const Function& b_func = Function::Cast(obj: b);
374 return (a_func.name() == b_func.name()) &&
375 (a_func.kind() == b_func.kind()) &&
376 (a_func.saved_args_desc() == b_func.saved_args_desc());
377 }
378 static bool IsMatch(const DispatcherKey& key, const Object& obj) {
379 return key.Equals(other: Function::Cast(obj));
380 }
381 static uword Hash(const Object& key) {
382 const Function& func = Function::Cast(obj: key);
383 return CombineHashes(hash: String::Hash(raw: func.name()), other_hash: func.kind());
384 }
385 static uword Hash(const DispatcherKey& key) { return key.Hash(); }
386 static ObjectPtr NewKey(const DispatcherKey& key) { UNREACHABLE(); }
387};
388
389typedef UnorderedHashSet<DispatcherTraits, AcqRelStorageTraits> DispatcherSet;
390
391class CanonicalInstanceKey {
392 public:
393 explicit CanonicalInstanceKey(const Instance& key);
394 bool Matches(const Instance& obj) const;
395 uword Hash() const;
396 const Instance& key_;
397
398 private:
399 DISALLOW_ALLOCATION();
400};
401
402// Traits for looking up Canonical Instances based on a hash of the fields.
403class CanonicalInstanceTraits {
404 public:
405 static const char* Name() { return "CanonicalInstanceTraits"; }
406 static bool ReportStats() { return false; }
407
408 // Called when growing the table.
409 static bool IsMatch(const Object& a, const Object& b);
410 static bool IsMatch(const CanonicalInstanceKey& a, const Object& b);
411 static uword Hash(const Object& key);
412 static uword Hash(const CanonicalInstanceKey& key);
413 static ObjectPtr NewKey(const CanonicalInstanceKey& obj);
414};
415
416typedef UnorderedHashSet<CanonicalInstanceTraits> CanonicalInstancesSet;
417
418struct CanonicalFfiCallbackFunctionTraits {
419 static uint32_t Hash(const Object& key) { return Function::Cast(obj: key).Hash(); }
420 static const char* Name() { return "CanonicalFfiCallbackFunctionTraits"; }
421 static bool IsMatch(const Object& x, const Object& y) {
422 const auto& f1 = Function::Cast(obj: x);
423 const auto& f2 = Function::Cast(obj: y);
424 return (f1.FfiCallbackTarget() == f2.FfiCallbackTarget() &&
425 f1.FfiCSignature() == f2.FfiCSignature() &&
426 f1.FfiCallbackExceptionalReturn() ==
427 f2.FfiCallbackExceptionalReturn() &&
428 f1.GetFfiTrampolineKind() == f2.GetFfiTrampolineKind());
429 }
430 static bool ReportStats() { return false; }
431};
432
433using FfiCallbackFunctionSet =
434 UnorderedHashSet<CanonicalFfiCallbackFunctionTraits>;
435
436class RegExpKey {
437 public:
438 RegExpKey(const String& pattern, RegExpFlags flags)
439 : pattern_(pattern), flags_(flags) {}
440
441 bool Equals(const RegExp& other) const {
442 return pattern_.Equals(str: String::Handle(ptr: other.pattern())) &&
443 (flags_ == other.flags());
444 }
445 uword Hash() const {
446 // Must agree with RegExp::CanonicalizeHash.
447 return CombineHashes(hash: pattern_.Hash(), other_hash: flags_.value());
448 }
449
450 const String& pattern_;
451 RegExpFlags flags_;
452
453 private:
454 DISALLOW_ALLOCATION();
455};
456
457class CanonicalRegExpTraits {
458 public:
459 static const char* Name() { return "CanonicalRegExpTraits"; }
460 static bool ReportStats() { return false; }
461 static bool IsMatch(const Object& a, const Object& b) {
462 return RegExp::Cast(obj: a).CanonicalizeEquals(other: RegExp::Cast(obj: b));
463 }
464 static bool IsMatch(const RegExpKey& a, const Object& b) {
465 return a.Equals(other: RegExp::Cast(obj: b));
466 }
467 static uword Hash(const Object& key) {
468 return RegExp::Cast(obj: key).CanonicalizeHash();
469 }
470 static uword Hash(const RegExpKey& key) { return key.Hash(); }
471 static ObjectPtr NewKey(const RegExpKey& key);
472};
473
474typedef UnorderedHashSet<CanonicalRegExpTraits, WeakAcqRelStorageTraits>
475 CanonicalRegExpSet;
476
477} // namespace dart
478
479#endif // RUNTIME_VM_CANONICAL_TABLES_H_
480

source code of dart_sdk/runtime/vm/canonical_tables.h