[vm] Introduce immutable maps and sets in backend
This CL introduces immutable maps and sets in the VM backend but does
not yet target them from the frontend. The changes are tested by unit
tests constructing these immutable maps and sets.
This CL introduces immutable variants of the hash map and set in
compact_hash.dart and recognizes them in the VM. The immutable ones
use a different mixin with a different recognized method for accessing
members.
* Data list is an immutable list with a different cid. (Otherwise the
optimizer notices that immutable and mutable lists cannot be equal.)
* Index is a nullable mutable typed data. (Otherwise optimizer removes
necessary null checks.)
* Index should use a store-release barrier when written to.
Multiple isolates might lazily compute the index for const sets and
maps. This is fine because all identityHashCodes and hashCodes are
guaranteed to be race-free. The later isolates will override the index
pointer with an identical index.
This CL does not introduce support for using these immutable maps and
sets in AOT (clustered_snapshot) and in messages to other isolates
(message_snapshot) because that is harder to test with unit tests. That
will be added in the follow-up CL.
Design doc: go/dart-vm-const-maps
TEST=runtime/vm/object_test.cc
Bug: https://github.com/dart-lang/sdk/issues/45908
Change-Id: I4042179c15e8b37692d3255655351c01c7124991
Cq-Include-Trybots: luci.dart.try:analyzer-nnbd-linux-release-try,app-kernel-linux-debug-x64-try,dart-sdk-linux-try,front-end-nnbd-linux-release-x64-try,pkg-linux-debug-try,vm-canary-linux-debug-try,vm-kernel-asan-linux-release-x64-try,vm-kernel-checked-linux-release-x64-try,vm-kernel-linux-debug-x64c-try,vm-kernel-linux-debug-x64-try,vm-kernel-linux-debug-simarm64c-try,vm-kernel-nnbd-linux-release-simarm-try,vm-kernel-optcounter-threshold-linux-release-x64-try,vm-kernel-precomp-android-release-arm_x64-try,vm-kernel-precomp-linux-debug-x64-try,vm-kernel-precomp-linux-debug-x64c-try,vm-kernel-reload-linux-debug-x64-try,vm-kernel-reload-rollback-linux-debug-x64-try,vm-precomp-ffi-qemu-linux-release-arm-try,vm-kernel-precomp-linux-debug-simarm_x64-try,vm-kernel-precomp-linux-debug-x64-try
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/210860
Reviewed-by: Martin Kustermann <kustermann@google.com>
diff --git a/pkg/vm/testcases/transformations/type_flow/transformer/enum_from_lib_used_as_type.dart.expect b/pkg/vm/testcases/transformations/type_flow/transformer/enum_from_lib_used_as_type.dart.expect
index 0e15b41..b774bd3 100644
--- a/pkg/vm/testcases/transformations/type_flow/transformer/enum_from_lib_used_as_type.dart.expect
+++ b/pkg/vm/testcases/transformations/type_flow/transformer/enum_from_lib_used_as_type.dart.expect
@@ -17,12 +17,12 @@
import "dart:core" as core;
abstract class Enum extends core::Object implements core::Enum {
-[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasNonThisUses:false,hasTearOffUses:false,getterSelectorId:3267] abstract get /*isLegacy*/ index() → core::int;
+[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasNonThisUses:false,hasTearOffUses:false,getterSelectorId:3275] abstract get /*isLegacy*/ index() → core::int;
}
class Class extends core::Object {
synthetic constructor •() → self::Class
: super core::Object::•()
;
-[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasTearOffUses:false,methodOrSetterSelectorId:3268,getterSelectorId:3269] method method([@vm.inferred-type.metadata=dart.core::Null? (value: null)] self::Enum e) → core::int
+[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasTearOffUses:false,methodOrSetterSelectorId:3276,getterSelectorId:3277] method method([@vm.inferred-type.metadata=dart.core::Null? (value: null)] self::Enum e) → core::int
return [@vm.inferred-type.metadata=!] e.{self::Enum::index}{core::int};
}
diff --git a/pkg/vm/testcases/transformations/type_flow/transformer/tree_shake_enum_from_lib.dart.expect b/pkg/vm/testcases/transformations/type_flow/transformer/tree_shake_enum_from_lib.dart.expect
index 1f84d00..60c22a0 100644
--- a/pkg/vm/testcases/transformations/type_flow/transformer/tree_shake_enum_from_lib.dart.expect
+++ b/pkg/vm/testcases/transformations/type_flow/transformer/tree_shake_enum_from_lib.dart.expect
@@ -48,12 +48,12 @@
import "dart:core" as core;
abstract class ConstEnum extends core::Object implements core::Enum {
-[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasNonThisUses:false,hasTearOffUses:false,getterSelectorId:3273] abstract get /*isLegacy*/ index() → core::int;
+[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasNonThisUses:false,hasTearOffUses:false,getterSelectorId:3281] abstract get /*isLegacy*/ index() → core::int;
}
class ConstClass extends core::Object {
synthetic constructor •() → self::ConstClass
: super core::Object::•()
;
-[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasTearOffUses:false,methodOrSetterSelectorId:3274,getterSelectorId:3275] method method([@vm.inferred-type.metadata=dart.core::Null? (value: null)] self::ConstEnum e) → core::int
+[@vm.procedure-attributes.metadata=methodOrSetterCalledDynamically:false,getterCalledDynamically:false,hasThisUses:false,hasTearOffUses:false,methodOrSetterSelectorId:3282,getterSelectorId:3283] method method([@vm.inferred-type.metadata=dart.core::Null? (value: null)] self::ConstEnum e) → core::int
return [@vm.inferred-type.metadata=!] e.{self::ConstEnum::index}{core::int};
}
diff --git a/runtime/vm/class_finalizer.cc b/runtime/vm/class_finalizer.cc
index c858051..d4a768d 100644
--- a/runtime/vm/class_finalizer.cc
+++ b/runtime/vm/class_finalizer.cc
@@ -266,8 +266,12 @@
ASSERT_EQUAL(WeakProperty::InstanceSize(), cls.host_instance_size());
cls = object_store->linked_hash_map_class();
ASSERT_EQUAL(LinkedHashMap::InstanceSize(), cls.host_instance_size());
- cls = object_store->linked_hash_set_class();
+ cls = object_store->immutable_linked_hash_map_class();
ASSERT_EQUAL(LinkedHashMap::InstanceSize(), cls.host_instance_size());
+ cls = object_store->linked_hash_set_class();
+ ASSERT_EQUAL(LinkedHashSet::InstanceSize(), cls.host_instance_size());
+ cls = object_store->immutable_linked_hash_set_class();
+ ASSERT_EQUAL(LinkedHashSet::InstanceSize(), cls.host_instance_size());
#endif // defined(DEBUG)
// Remember the currently pending classes.
diff --git a/runtime/vm/class_id.h b/runtime/vm/class_id.h
index e7f7cbc..ad9f6b0 100644
--- a/runtime/vm/class_id.h
+++ b/runtime/vm/class_id.h
@@ -101,11 +101,13 @@
#define CLASS_LIST_NO_OBJECT_NOR_STRING_NOR_ARRAY_NOR_MAP(V) \
CLASS_LIST_INTERNAL_ONLY(V) CLASS_LIST_INSTANCE_SINGLETONS(V)
-// TODO(http://dartbug.com/45908): Add ImmutableLinkedHashMap.
-#define CLASS_LIST_MAPS(V) V(LinkedHashMap)
+#define CLASS_LIST_MAPS(V) \
+ V(LinkedHashMap) \
+ V(ImmutableLinkedHashMap)
-// TODO(http://dartbug.com/45908): Add ImmutableLinkedHashSet.
-#define CLASS_LIST_SETS(V) V(LinkedHashSet)
+#define CLASS_LIST_SETS(V) \
+ V(LinkedHashSet) \
+ V(ImmutableLinkedHashSet)
#define CLASS_LIST_FIXED_LENGTH_ARRAYS(V) \
V(Array) \
diff --git a/runtime/vm/compiler/backend/il.cc b/runtime/vm/compiler/backend/il.cc
index d15f357..215b0cc 100644
--- a/runtime/vm/compiler/backend/il.cc
+++ b/runtime/vm/compiler/backend/il.cc
@@ -2825,6 +2825,7 @@
switch (call->function().recognized_kind()) {
case MethodRecognizer::kByteDataFactory:
case MethodRecognizer::kLinkedHashBase_getData:
+ case MethodRecognizer::kImmutableLinkedHashBase_getData:
return flow_graph->constant_null();
default:
break;
diff --git a/runtime/vm/compiler/backend/range_analysis.cc b/runtime/vm/compiler/backend/range_analysis.cc
index 17a1c15..7d35302 100644
--- a/runtime/vm/compiler/backend/range_analysis.cc
+++ b/runtime/vm/compiler/backend/range_analysis.cc
@@ -2789,7 +2789,9 @@
break;
case Slot::Kind::kLinkedHashBase_index:
+ case Slot::Kind::kImmutableLinkedHashBase_index:
case Slot::Kind::kLinkedHashBase_data:
+ case Slot::Kind::kImmutableLinkedHashBase_data:
case Slot::Kind::kGrowableObjectArray_data:
case Slot::Kind::kContext_parent:
case Slot::Kind::kTypeArguments:
diff --git a/runtime/vm/compiler/backend/slot.cc b/runtime/vm/compiler/backend/slot.cc
index 9f84201..15f0080 100644
--- a/runtime/vm/compiler/backend/slot.cc
+++ b/runtime/vm/compiler/backend/slot.cc
@@ -201,7 +201,9 @@
UNBOXED_NATIVE_SLOTS_LIST(UNBOXED_NATIVE_SLOT_CASE)
#undef UNBOXED_NATIVE_SLOT_CASE
case Slot::Kind::kLinkedHashBase_index:
+ case Slot::Kind::kImmutableLinkedHashBase_index:
case Slot::Kind::kLinkedHashBase_data:
+ case Slot::Kind::kImmutableLinkedHashBase_data:
case Slot::Kind::kLinkedHashBase_hash_mask:
case Slot::Kind::kLinkedHashBase_used_data:
case Slot::Kind::kLinkedHashBase_deleted_keys:
diff --git a/runtime/vm/compiler/backend/slot.h b/runtime/vm/compiler/backend/slot.h
index 27adf00..a31e9a9 100644
--- a/runtime/vm/compiler/backend/slot.h
+++ b/runtime/vm/compiler/backend/slot.h
@@ -61,6 +61,8 @@
V(Closure, UntaggedClosure, function_type_arguments, TypeArguments, FINAL) \
V(FunctionType, UntaggedFunctionType, type_parameters, TypeParameters, \
FINAL) \
+ V(ImmutableLinkedHashBase, UntaggedLinkedHashBase, index, \
+ TypedDataUint32Array, VAR) \
V(Instance, UntaggedInstance, native_fields_array, Dynamic, VAR) \
V(Type, UntaggedType, arguments, TypeArguments, FINAL) \
V(TypeParameters, UntaggedTypeParameters, flags, Array, FINAL) \
@@ -98,6 +100,8 @@
V(String, UntaggedString, length, Smi, FINAL) \
V(LinkedHashBase, UntaggedLinkedHashBase, index, TypedDataUint32Array, VAR) \
V(LinkedHashBase, UntaggedLinkedHashBase, data, Array, VAR) \
+ V(ImmutableLinkedHashBase, UntaggedLinkedHashBase, data, ImmutableArray, \
+ FINAL) \
V(LinkedHashBase, UntaggedLinkedHashBase, hash_mask, Smi, VAR) \
V(LinkedHashBase, UntaggedLinkedHashBase, used_data, Smi, VAR) \
V(LinkedHashBase, UntaggedLinkedHashBase, deleted_keys, Smi, VAR) \
diff --git a/runtime/vm/compiler/frontend/kernel_to_il.cc b/runtime/vm/compiler/frontend/kernel_to_il.cc
index ad2f103..52d7171 100644
--- a/runtime/vm/compiler/frontend/kernel_to_il.cc
+++ b/runtime/vm/compiler/frontend/kernel_to_il.cc
@@ -883,6 +883,9 @@
case MethodRecognizer::kLinkedHashBase_setUsedData:
case MethodRecognizer::kLinkedHashBase_getDeletedKeys:
case MethodRecognizer::kLinkedHashBase_setDeletedKeys:
+ case MethodRecognizer::kImmutableLinkedHashBase_getData:
+ case MethodRecognizer::kImmutableLinkedHashBase_getIndex:
+ case MethodRecognizer::kImmutableLinkedHashBase_setIndexStoreRelease:
case MethodRecognizer::kWeakProperty_getKey:
case MethodRecognizer::kWeakProperty_setKey:
case MethodRecognizer::kWeakProperty_getValue:
@@ -1190,6 +1193,11 @@
body += LoadLocal(parsed_function_->RawParameterVariable(0));
body += LoadNativeField(Slot::LinkedHashBase_index());
break;
+ case MethodRecognizer::kImmutableLinkedHashBase_getIndex:
+ ASSERT_EQUAL(function.NumParameters(), 1);
+ body += LoadLocal(parsed_function_->RawParameterVariable(0));
+ body += LoadNativeField(Slot::ImmutableLinkedHashBase_index());
+ break;
case MethodRecognizer::kLinkedHashBase_setIndex:
ASSERT_EQUAL(function.NumParameters(), 2);
body += LoadLocal(parsed_function_->RawParameterVariable(0));
@@ -1197,11 +1205,28 @@
body += StoreNativeField(Slot::LinkedHashBase_index());
body += NullConstant();
break;
+ case MethodRecognizer::kImmutableLinkedHashBase_setIndexStoreRelease:
+ ASSERT_EQUAL(function.NumParameters(), 2);
+ body += LoadLocal(parsed_function_->RawParameterVariable(0));
+ body += LoadLocal(parsed_function_->RawParameterVariable(1));
+ // Uses a store-release barrier so that other isolates will see the
+ // contents of the index after seeing the index itself.
+ body +=
+ StoreNativeField(Slot::ImmutableLinkedHashBase_index(),
+ StoreInstanceFieldInstr::Kind::kOther,
+ kEmitStoreBarrier, compiler::Assembler::kRelease);
+ body += NullConstant();
+ break;
case MethodRecognizer::kLinkedHashBase_getData:
ASSERT_EQUAL(function.NumParameters(), 1);
body += LoadLocal(parsed_function_->RawParameterVariable(0));
body += LoadNativeField(Slot::LinkedHashBase_data());
break;
+ case MethodRecognizer::kImmutableLinkedHashBase_getData:
+ ASSERT(function.NumParameters() == 1);
+ body += LoadLocal(parsed_function_->RawParameterVariable(0));
+ body += LoadNativeField(Slot::ImmutableLinkedHashBase_data());
+ break;
case MethodRecognizer::kLinkedHashBase_setData:
ASSERT_EQUAL(function.NumParameters(), 2);
body += LoadLocal(parsed_function_->RawParameterVariable(0));
diff --git a/runtime/vm/compiler/recognized_methods_list.h b/runtime/vm/compiler/recognized_methods_list.h
index 3142cb9..554d11b 100644
--- a/runtime/vm/compiler/recognized_methods_list.h
+++ b/runtime/vm/compiler/recognized_methods_list.h
@@ -13,7 +13,7 @@
// debug mode to get the correct fingerprint from the mismatch error.
#define OTHER_RECOGNIZED_LIST(V) \
V(::, identical, ObjectIdentical, 0x04168315) \
- V(ClassID, getID, ClassIDgetID, 0xbe1d6669) \
+ V(ClassID, getID, ClassIDgetID, 0xdc8b888a) \
V(Object, Object., ObjectConstructor, 0xab6d6cfa) \
V(List, ., ListFactory, 0xbc820cf9) \
V(_List, ., ObjectArrayAllocate, 0xd693eee6) \
@@ -174,6 +174,12 @@
V(_HashVMBase, set:_hashMask, LinkedHashBase_setHashMask, 0xbbcebb58) \
V(_HashVMBase, get:_deletedKeys, LinkedHashBase_getDeletedKeys, 0x510dc4a0) \
V(_HashVMBase, set:_deletedKeys, LinkedHashBase_setDeletedKeys, 0xbdcdb85c) \
+ V(_HashVMImmutableBase, get:_data, ImmutableLinkedHashBase_getData, \
+ 0x780e14ad) \
+ V(_HashVMImmutableBase, get:_indexNullable, \
+ ImmutableLinkedHashBase_getIndex, 0xfd877bfb) \
+ V(_HashVMImmutableBase, set:_index, \
+ ImmutableLinkedHashBase_setIndexStoreRelease, 0xa2be9418) \
V(_WeakProperty, get:key, WeakProperty_getKey, 0xde00e462) \
V(_WeakProperty, set:key, WeakProperty_setKey, 0x963a095f) \
V(_WeakProperty, get:value, WeakProperty_getValue, 0xd2f28aae) \
diff --git a/runtime/vm/compiler/runtime_api.h b/runtime/vm/compiler/runtime_api.h
index ba5d79b..d2e9510 100644
--- a/runtime/vm/compiler/runtime_api.h
+++ b/runtime/vm/compiler/runtime_api.h
@@ -648,6 +648,12 @@
static word InstanceSize();
};
+class ImmutableLinkedHashBase : public LinkedHashBase {
+ public:
+ // The data slot is an immutable list and final in immutable maps and sets.
+ static word data_offset();
+};
+
class LinkedHashMap : public LinkedHashBase {
public:
FINAL_CLASS();
diff --git a/runtime/vm/compiler/runtime_offsets_extracted.h b/runtime/vm/compiler/runtime_offsets_extracted.h
index 8598191..72ec4ff 100644
--- a/runtime/vm/compiler/runtime_offsets_extracted.h
+++ b/runtime/vm/compiler/runtime_offsets_extracted.h
@@ -197,6 +197,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 12;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
8;
@@ -742,6 +744,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 24;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
16;
@@ -1292,6 +1296,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 12;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
8;
@@ -1834,6 +1840,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 24;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
16;
@@ -2385,6 +2393,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 16;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
12;
@@ -2935,6 +2945,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 16;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
12;
@@ -3482,6 +3494,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 16;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 12;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
8;
@@ -4021,6 +4035,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 32;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 24;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
16;
@@ -4565,6 +4581,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 16;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 12;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
8;
@@ -5101,6 +5119,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 32;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 24;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
16;
@@ -5646,6 +5666,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 32;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 16;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
12;
@@ -6190,6 +6212,8 @@
static constexpr dart::compiler::target::word Isolate_user_tag_offset = 32;
static constexpr dart::compiler::target::word LinkedHashBase_data_offset = 16;
static constexpr dart::compiler::target::word
+ ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word LinkedHashBase_hash_mask_offset =
12;
@@ -6761,6 +6785,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
12;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 8;
@@ -7370,6 +7396,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
24;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 16;
@@ -7985,6 +8013,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
24;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 16;
@@ -8597,6 +8627,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
16;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 12;
@@ -9208,6 +9240,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
16;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 12;
@@ -9815,6 +9849,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
12;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 12;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 20;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 8;
@@ -10417,6 +10453,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
24;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 16;
@@ -11025,6 +11063,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
24;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 24;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 40;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 16;
@@ -11630,6 +11670,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
16;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 12;
@@ -12234,6 +12276,8 @@
static constexpr dart::compiler::target::word AOT_LinkedHashBase_data_offset =
16;
static constexpr dart::compiler::target::word
+ AOT_ImmutableLinkedHashBase_data_offset = 16;
+static constexpr dart::compiler::target::word
AOT_LinkedHashBase_deleted_keys_offset = 24;
static constexpr dart::compiler::target::word
AOT_LinkedHashBase_hash_mask_offset = 12;
diff --git a/runtime/vm/compiler/runtime_offsets_list.h b/runtime/vm/compiler/runtime_offsets_list.h
index 2954ccb7..65505e1 100644
--- a/runtime/vm/compiler/runtime_offsets_list.h
+++ b/runtime/vm/compiler/runtime_offsets_list.h
@@ -157,6 +157,7 @@
NOT_IN_PRODUCT(FIELD(Isolate, single_step_offset)) \
FIELD(Isolate, user_tag_offset) \
FIELD(LinkedHashBase, data_offset) \
+ FIELD(ImmutableLinkedHashBase, data_offset) \
FIELD(LinkedHashBase, deleted_keys_offset) \
FIELD(LinkedHashBase, hash_mask_offset) \
FIELD(LinkedHashBase, index_offset) \
diff --git a/runtime/vm/message_snapshot.cc b/runtime/vm/message_snapshot.cc
index b2ff598..d41151e 100644
--- a/runtime/vm/message_snapshot.cc
+++ b/runtime/vm/message_snapshot.cc
@@ -2498,7 +2498,7 @@
void ReadNodes(MessageDeserializer* d) {
intptr_t count = d->ReadUnsigned();
for (intptr_t i = 0; i < count; i++) {
- d->AssignRef(LinkedHashMap::NewUninitialized());
+ d->AssignRef(LinkedHashMap::NewUninitialized(kLinkedHashMapCid));
}
}
@@ -2568,7 +2568,7 @@
void ReadNodes(MessageDeserializer* d) {
intptr_t count = d->ReadUnsigned();
for (intptr_t i = 0; i < count; i++) {
- d->AssignRef(LinkedHashSet::NewUninitialized());
+ d->AssignRef(LinkedHashSet::NewUninitialized(kLinkedHashSetCid));
}
}
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index 8344d4b..3c01297 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -1658,10 +1658,11 @@
object_store->set_array_class(cls);
// VM classes that are parameterized (Array, ImmutableArray,
- // GrowableObjectArray, and LinkedHashMap) are also pre-finalized, so
- // CalculateFieldOffsets() is not called, so we need to set the offset of
- // their type_arguments_ field, which is explicitly declared in their
- // respective Raw* classes.
+ // GrowableObjectArray, LinkedHashMap, ImmutableLinkedHashMap,
+ // LinkedHashSet, ImmutableLinkedHashSet) are also pre-finalized, so
+ // CalculateFieldOffsets() is not called, so we need to set the offset
+ // of their type_arguments_ field, which is explicitly
+ // declared in their respective Raw* classes.
cls.set_type_arguments_field_offset(Array::type_arguments_offset(),
RTN::Array::type_arguments_offset());
cls.set_num_type_arguments_unsafe(1);
@@ -1965,6 +1966,17 @@
RegisterPrivateClass(cls, Symbols::_LinkedHashMap(), lib);
pending_classes.Add(cls);
+ cls = Class::New<LinkedHashMap, RTN::LinkedHashMap>(
+ kImmutableLinkedHashMapCid, isolate_group);
+ object_store->set_immutable_linked_hash_map_class(cls);
+ cls.set_type_arguments_field_offset(
+ LinkedHashMap::type_arguments_offset(),
+ RTN::LinkedHashMap::type_arguments_offset());
+ cls.set_num_type_arguments_unsafe(2);
+ cls.set_is_prefinalized();
+ RegisterPrivateClass(cls, Symbols::_ImmutableLinkedHashMap(), lib);
+ pending_classes.Add(cls);
+
cls = Class::New<LinkedHashSet, RTN::LinkedHashSet>(isolate_group);
object_store->set_linked_hash_set_class(cls);
cls.set_type_arguments_field_offset(
@@ -1974,6 +1986,17 @@
RegisterPrivateClass(cls, Symbols::_LinkedHashSet(), lib);
pending_classes.Add(cls);
+ cls = Class::New<LinkedHashSet, RTN::LinkedHashSet>(
+ kImmutableLinkedHashSetCid, isolate_group);
+ object_store->set_immutable_linked_hash_set_class(cls);
+ cls.set_type_arguments_field_offset(
+ LinkedHashSet::type_arguments_offset(),
+ RTN::LinkedHashSet::type_arguments_offset());
+ cls.set_num_type_arguments_unsafe(1);
+ cls.set_is_prefinalized();
+ RegisterPrivateClass(cls, Symbols::_ImmutableLinkedHashSet(), lib);
+ pending_classes.Add(cls);
+
// Pre-register the async library so we can place the vm class
// FutureOr there rather than the core library.
lib = Library::LookupLibrary(thread, Symbols::DartAsync());
@@ -2438,9 +2461,17 @@
cls = Class::New<LinkedHashMap, RTN::LinkedHashMap>(isolate_group);
object_store->set_linked_hash_map_class(cls);
+ cls = Class::New<LinkedHashMap, RTN::LinkedHashMap>(
+ kImmutableLinkedHashMapCid, isolate_group);
+ object_store->set_immutable_linked_hash_map_class(cls);
+
cls = Class::New<LinkedHashSet, RTN::LinkedHashSet>(isolate_group);
object_store->set_linked_hash_set_class(cls);
+ cls = Class::New<LinkedHashSet, RTN::LinkedHashSet>(
+ kImmutableLinkedHashSetCid, isolate_group);
+ object_store->set_immutable_linked_hash_set_class(cls);
+
cls = Class::New<Float32x4, RTN::Float32x4>(isolate_group);
object_store->set_float32x4_class(cls);
@@ -2806,6 +2837,11 @@
size - kHeaderSizeInBytes);
}
+ if (IsTypedDataClassId(raw_clone->GetClassId())) {
+ auto raw_typed_data = TypedData::RawCast(raw_clone);
+ raw_typed_data.untag()->RecomputeDataField();
+ }
+
// Add clone to store buffer, if needed.
if (!raw_clone->IsOldObject()) {
// No need to remember an object in new space.
@@ -4631,6 +4667,9 @@
CLASS_LIST_TYPED_DATA(ADD_SET_FIELD)
#undef ADD_SET_FIELD
#undef CLASS_LIST_WITH_NULL
+ // Used in const hashing to determine whether we're dealing with a
+ // user-defined const. See lib/_internal/vm/lib/compact_hash.dart.
+ {"numPredefinedCids", kNumPredefinedCids},
};
const AbstractType& field_type = Type::Handle(zone, Type::IntType());
@@ -6056,6 +6095,7 @@
InstancePtr Class::InsertCanonicalConstant(Zone* zone,
const Instance& constant) const {
+ ASSERT(constant.IsCanonical());
ASSERT(this->ptr() == constant.clazz());
Instance& canonical_value = Instance::Handle(zone);
if (this->constants() == Array::null()) {
@@ -24566,7 +24606,8 @@
}
};
-LinkedHashMapPtr LinkedHashMap::NewDefault(Heap::Space space) {
+LinkedHashMapPtr LinkedHashMap::NewDefault(intptr_t class_id,
+ Heap::Space space) {
const Array& data = Array::Handle(Array::New(kInitialIndexSize, space));
const TypedData& index = TypedData::Handle(
TypedData::New(kTypedDataUint32ArrayCid, kInitialIndexSize, space));
@@ -24574,35 +24615,40 @@
static const intptr_t kAvailableBits = (kSmiBits >= 32) ? 32 : kSmiBits;
static const intptr_t kInitialHashMask =
(1 << (kAvailableBits - kInitialIndexBits)) - 1;
- return LinkedHashMap::New(data, index, kInitialHashMask, 0, 0, space);
+ return LinkedHashMap::New(class_id, data, index, kInitialHashMask, 0, 0,
+ space);
}
-LinkedHashMapPtr LinkedHashMap::New(const Array& data,
+LinkedHashMapPtr LinkedHashMap::New(intptr_t class_id,
+ const Array& data,
const TypedData& index,
intptr_t hash_mask,
intptr_t used_data,
intptr_t deleted_keys,
Heap::Space space) {
+ ASSERT(class_id == kLinkedHashMapCid ||
+ class_id == kImmutableLinkedHashMapCid);
ASSERT(IsolateGroup::Current()->object_store()->linked_hash_map_class() !=
Class::null());
LinkedHashMap& result =
- LinkedHashMap::Handle(LinkedHashMap::NewUninitialized(space));
- result.SetData(data);
- result.SetIndex(index);
- result.SetHashMask(hash_mask);
- result.SetUsedData(used_data);
- result.SetDeletedKeys(deleted_keys);
+ LinkedHashMap::Handle(LinkedHashMap::NewUninitialized(class_id, space));
+ result.set_data(data);
+ result.set_index(index);
+ result.set_hash_mask(hash_mask);
+ result.set_used_data(used_data);
+ result.set_deleted_keys(deleted_keys);
return result.ptr();
}
-LinkedHashMapPtr LinkedHashMap::NewUninitialized(Heap::Space space) {
+LinkedHashMapPtr LinkedHashMap::NewUninitialized(intptr_t class_id,
+ Heap::Space space) {
ASSERT(IsolateGroup::Current()->object_store()->linked_hash_map_class() !=
Class::null());
LinkedHashMap& result = LinkedHashMap::Handle();
{
ObjectPtr raw =
- Object::Allocate(LinkedHashMap::kClassId, LinkedHashMap::InstanceSize(),
- space, LinkedHashMap::ContainsCompressedPointers());
+ Object::Allocate(class_id, LinkedHashMap::InstanceSize(), space,
+ LinkedHashMap::ContainsCompressedPointers());
NoSafepointScope no_safepoint;
result ^= raw;
}
@@ -24611,28 +24657,155 @@
const char* LinkedHashMap::ToCString() const {
Zone* zone = Thread::Current()->zone();
- return zone->PrintToString("_LinkedHashMap len:%" Pd, Length());
+ return zone->PrintToString(
+ "_%sLinkedHashMap len:%" Pd,
+ GetClassId() == kImmutableLinkedHashMapCid ? "Immutable" : "", Length());
}
-LinkedHashSetPtr LinkedHashSet::New(const Array& data,
+void LinkedHashBase::ComputeAndSetHashMask() const {
+ ASSERT(IsImmutable());
+ ASSERT_EQUAL(Smi::Value(deleted_keys()), 0);
+ Thread* const thread = Thread::Current();
+ Zone* const zone = thread->zone();
+
+ const auto& data_array = Array::Handle(zone, data());
+ const intptr_t data_length = data_array.Length();
+ ASSERT(Utils::IsPowerOfTwo(data_length));
+ const intptr_t index_size_mult = IsLinkedHashMap() ? 1 : 2;
+ const intptr_t index_size = Utils::Maximum(LinkedHashBase::kInitialIndexSize,
+ data_length * index_size_mult);
+
+ const intptr_t hash_mask = IndexSizeToHashMask(index_size);
+ set_hash_mask(hash_mask);
+}
+
+bool LinkedHashBase::CanonicalizeEquals(const Instance& other) const {
+ ASSERT(IsImmutable());
+
+ if (this->ptr() == other.ptr()) {
+ // Both handles point to the same raw instance.
+ return true;
+ }
+ if (other.IsNull()) {
+ return false;
+ }
+ if (GetClassId() != other.GetClassId()) {
+ return false;
+ }
+
+ Zone* zone = Thread::Current()->zone();
+
+ const LinkedHashBase& other_map = LinkedHashBase::Cast(other);
+
+ if (!Smi::Handle(zone, used_data())
+ .Equals(Smi::Handle(zone, other_map.used_data()))) {
+ return false;
+ }
+
+ // Immutable maps and sets do not have deleted keys.
+ ASSERT_EQUAL(RawSmiValue(deleted_keys()), 0);
+
+ if (!Array::Handle(zone, data())
+ .CanonicalizeEquals(Array::Handle(zone, other_map.data()))) {
+ return false;
+ }
+
+ if (GetTypeArguments() == other.GetTypeArguments()) {
+ return true;
+ }
+ const TypeArguments& type_args =
+ TypeArguments::Handle(zone, GetTypeArguments());
+ const TypeArguments& other_type_args =
+ TypeArguments::Handle(zone, other.GetTypeArguments());
+ return type_args.Equals(other_type_args);
+}
+
+uint32_t LinkedHashBase::CanonicalizeHash() const {
+ ASSERT(IsImmutable());
+
+ Thread* thread = Thread::Current();
+ uint32_t hash = thread->heap()->GetCanonicalHash(ptr());
+ if (hash != 0) {
+ return hash;
+ }
+
+ // Immutable maps and sets do not have deleted keys.
+ ASSERT_EQUAL(RawSmiValue(deleted_keys()), 0);
+
+ Zone* zone = thread->zone();
+ auto& member = Instance::Handle(zone, GetTypeArguments());
+ hash = member.CanonicalizeHash();
+ member = data();
+ hash = CombineHashes(hash, member.CanonicalizeHash());
+ member = used_data();
+ hash = CombineHashes(hash, member.CanonicalizeHash());
+ hash = FinalizeHash(hash, kHashBits);
+ thread->heap()->SetCanonicalHash(ptr(), hash);
+ return hash;
+}
+
+void LinkedHashBase::CanonicalizeFieldsLocked(Thread* thread) const {
+ ASSERT(IsImmutable());
+
+ Zone* zone = thread->zone();
+
+ TypeArguments& type_args = TypeArguments::Handle(zone, GetTypeArguments());
+ if (!type_args.IsNull()) {
+ type_args = type_args.Canonicalize(thread, nullptr);
+ SetTypeArguments(type_args);
+ }
+
+ auto& data_array = Array::Handle(zone, data());
+ data_array.MakeImmutable();
+ data_array ^= data_array.CanonicalizeLocked(thread);
+ set_data(data_array);
+
+ // The index should not be set yet. It is populated lazily on first read.
+ const auto& index_td = TypedData::Handle(zone, index());
+ ASSERT(index_td.IsNull());
+}
+
+ImmutableLinkedHashMapPtr ImmutableLinkedHashMap::NewDefault(
+ Heap::Space space) {
+ ASSERT(IsolateGroup::Current()
+ ->object_store()
+ ->immutable_linked_hash_map_class() != Class::null());
+ return static_cast<ImmutableLinkedHashMapPtr>(
+ LinkedHashMap::NewDefault(kClassId, space));
+}
+
+ImmutableLinkedHashMapPtr ImmutableLinkedHashMap::NewUninitialized(
+ Heap::Space space) {
+ ASSERT(IsolateGroup::Current()
+ ->object_store()
+ ->immutable_linked_hash_map_class() != Class::null());
+ return static_cast<ImmutableLinkedHashMapPtr>(
+ LinkedHashMap::NewUninitialized(kClassId, space));
+}
+
+LinkedHashSetPtr LinkedHashSet::New(intptr_t class_id,
+ const Array& data,
const TypedData& index,
intptr_t hash_mask,
intptr_t used_data,
intptr_t deleted_keys,
Heap::Space space) {
+ ASSERT(class_id == kLinkedHashSetCid ||
+ class_id == kImmutableLinkedHashSetCid);
ASSERT(IsolateGroup::Current()->object_store()->linked_hash_map_class() !=
Class::null());
LinkedHashSet& result =
- LinkedHashSet::Handle(LinkedHashSet::NewUninitialized(space));
- result.SetData(data);
- result.SetIndex(index);
- result.SetHashMask(hash_mask);
- result.SetUsedData(used_data);
- result.SetDeletedKeys(deleted_keys);
+ LinkedHashSet::Handle(LinkedHashSet::NewUninitialized(class_id, space));
+ result.set_data(data);
+ result.set_index(index);
+ result.set_hash_mask(hash_mask);
+ result.set_used_data(used_data);
+ result.set_deleted_keys(deleted_keys);
return result.ptr();
}
-LinkedHashSetPtr LinkedHashSet::NewDefault(Heap::Space space) {
+LinkedHashSetPtr LinkedHashSet::NewDefault(intptr_t class_id,
+ Heap::Space space) {
const Array& data = Array::Handle(Array::New(kInitialIndexSize, space));
const TypedData& index = TypedData::Handle(
TypedData::New(kTypedDataUint32ArrayCid, kInitialIndexSize, space));
@@ -24640,26 +24813,48 @@
static const intptr_t kAvailableBits = (kSmiBits >= 32) ? 32 : kSmiBits;
static const intptr_t kInitialHashMask =
(1 << (kAvailableBits - kInitialIndexBits)) - 1;
- return LinkedHashSet::New(data, index, kInitialHashMask, 0, 0, space);
+ return LinkedHashSet::New(class_id, data, index, kInitialHashMask, 0, 0,
+ space);
}
-LinkedHashSetPtr LinkedHashSet::NewUninitialized(Heap::Space space) {
+LinkedHashSetPtr LinkedHashSet::NewUninitialized(intptr_t class_id,
+ Heap::Space space) {
ASSERT(IsolateGroup::Current()->object_store()->linked_hash_map_class() !=
Class::null());
LinkedHashSet& result = LinkedHashSet::Handle();
{
ObjectPtr raw =
- Object::Allocate(kLinkedHashSetCid, LinkedHashSet::InstanceSize(),
- space, LinkedHashSet::ContainsCompressedPointers());
+ Object::Allocate(class_id, LinkedHashSet::InstanceSize(), space,
+ LinkedHashSet::ContainsCompressedPointers());
NoSafepointScope no_safepoint;
result ^= raw;
}
return result.ptr();
}
+ImmutableLinkedHashSetPtr ImmutableLinkedHashSet::NewDefault(
+ Heap::Space space) {
+ ASSERT(IsolateGroup::Current()
+ ->object_store()
+ ->immutable_linked_hash_set_class() != Class::null());
+ return static_cast<ImmutableLinkedHashSetPtr>(
+ LinkedHashSet::NewDefault(kClassId, space));
+}
+
+ImmutableLinkedHashSetPtr ImmutableLinkedHashSet::NewUninitialized(
+ Heap::Space space) {
+ ASSERT(IsolateGroup::Current()
+ ->object_store()
+ ->immutable_linked_hash_map_class() != Class::null());
+ return static_cast<ImmutableLinkedHashSetPtr>(
+ LinkedHashSet::NewUninitialized(kClassId, space));
+}
+
const char* LinkedHashSet::ToCString() const {
Zone* zone = Thread::Current()->zone();
- return zone->PrintToString("LinkedHashSet len:%" Pd, Length());
+ return zone->PrintToString(
+ "_%sLinkedHashSet len:%" Pd,
+ GetClassId() == kImmutableLinkedHashSetCid ? "Immutable" : "", Length());
}
const char* FutureOr::ToCString() const {
diff --git a/runtime/vm/object.h b/runtime/vm/object.h
index 3b9d8ec..a787575 100644
--- a/runtime/vm/object.h
+++ b/runtime/vm/object.h
@@ -10970,6 +10970,16 @@
class LinkedHashBase : public Instance {
public:
+ // Keep consistent with _indexSizeToHashMask in compact_hash.dart.
+ static intptr_t IndexSizeToHashMask(intptr_t index_size) {
+ ASSERT(index_size >= kInitialIndexSize);
+ intptr_t index_bits = Utils::BitLength(index_size) - 2;
+#if defined(HAS_SMI_63_BITS)
+ return (1 << (32 - index_bits)) - 1;
+#else
+ return (1 << (Object::kHashBits - index_bits)) - 1;
+#endif
+ }
static intptr_t InstanceSize() {
return RoundedAllocationSize(sizeof(UntaggedLinkedHashBase));
}
@@ -10998,15 +11008,101 @@
return OFFSET_OF(UntaggedLinkedHashBase, deleted_keys_);
}
+ static const LinkedHashBase& Cast(const Object& obj) {
+ ASSERT(obj.IsLinkedHashMap() || obj.IsLinkedHashSet());
+ return static_cast<const LinkedHashBase&>(obj);
+ }
+
+ bool IsImmutable() const {
+ return GetClassId() == kImmutableLinkedHashMapCid ||
+ GetClassId() == kImmutableLinkedHashSetCid;
+ }
+
+ virtual TypeArgumentsPtr GetTypeArguments() const {
+ return untag()->type_arguments();
+ }
+ virtual void SetTypeArguments(const TypeArguments& value) const {
+ const intptr_t num_type_args = IsLinkedHashMap() ? 2 : 1;
+ ASSERT(value.IsNull() ||
+ ((value.Length() >= num_type_args) &&
+ value.IsInstantiated() /*&& value.IsCanonical()*/));
+ // TODO(asiva): Values read from a message snapshot are not properly marked
+ // as canonical. See for example tests/isolate/message3_test.dart.
+ untag()->set_type_arguments(value.ptr());
+ }
+
+ TypedDataPtr index() const { return untag()->index(); }
+ void set_index(const TypedData& value) const {
+ ASSERT(!value.IsNull());
+ untag()->set_index(value.ptr());
+ }
+
+ ArrayPtr data() const { return untag()->data(); }
+ void set_data(const Array& value) const { untag()->set_data(value.ptr()); }
+
+ SmiPtr hash_mask() const { return untag()->hash_mask(); }
+ void set_hash_mask(intptr_t value) const {
+ untag()->set_hash_mask(Smi::New(value));
+ }
+
+ SmiPtr used_data() const { return untag()->used_data(); }
+ void set_used_data(intptr_t value) const {
+ untag()->set_used_data(Smi::New(value));
+ }
+
+ SmiPtr deleted_keys() const { return untag()->deleted_keys(); }
+ void set_deleted_keys(intptr_t value) const {
+ untag()->set_deleted_keys(Smi::New(value));
+ }
+
+ intptr_t Length() const {
+ // The map or set may be uninitialized.
+ if (untag()->used_data() == Object::null()) return 0;
+ if (untag()->deleted_keys() == Object::null()) return 0;
+
+ intptr_t used = Smi::Value(untag()->used_data());
+ if (IsLinkedHashMap()) {
+ used >>= 1;
+ }
+ const intptr_t deleted = Smi::Value(untag()->deleted_keys());
+ return used - deleted;
+ }
+
+ // We do not compute the indices in the VM, but we do precompute the hash
+ // mask to avoid a load acquire barrier on reading the combination of index
+ // and hash mask.
+ void ComputeAndSetHashMask() const;
+
+ virtual bool CanonicalizeEquals(const Instance& other) const;
+ virtual uint32_t CanonicalizeHash() const;
+ virtual void CanonicalizeFieldsLocked(Thread* thread) const;
+
protected:
// Keep this in sync with Dart implementation (lib/compact_hash.dart).
static const intptr_t kInitialIndexBits = 2;
static const intptr_t kInitialIndexSize = 1 << (kInitialIndexBits + 1);
+ private:
+ LinkedHashBasePtr ptr() const { return static_cast<LinkedHashBasePtr>(ptr_); }
+ UntaggedLinkedHashBase* untag() const {
+ ASSERT(ptr() != null());
+ return const_cast<UntaggedLinkedHashBase*>(ptr()->untag());
+ }
+
friend class Class;
+ friend class ImmutableLinkedHashBase;
friend class LinkedHashBaseDeserializationCluster;
};
+class ImmutableLinkedHashBase : public AllStatic {
+ public:
+ static constexpr bool ContainsCompressedPointers() {
+ return LinkedHashBase::ContainsCompressedPointers();
+ }
+
+ static intptr_t data_offset() { return LinkedHashBase::data_offset(); }
+};
+
// Corresponds to
// - "new Map()",
// - non-const map literals, and
@@ -11018,60 +11114,16 @@
}
// Allocates a map with some default capacity, just like "new Map()".
- static LinkedHashMapPtr NewDefault(Heap::Space space = Heap::kNew);
- static LinkedHashMapPtr New(const Array& data,
+ static LinkedHashMapPtr NewDefault(intptr_t class_id = kLinkedHashMapCid,
+ Heap::Space space = Heap::kNew);
+ static LinkedHashMapPtr New(intptr_t class_id,
+ const Array& data,
const TypedData& index,
intptr_t hash_mask,
intptr_t used_data,
intptr_t deleted_keys,
Heap::Space space = Heap::kNew);
- virtual TypeArgumentsPtr GetTypeArguments() const {
- return untag()->type_arguments();
- }
- virtual void SetTypeArguments(const TypeArguments& value) const {
- ASSERT(value.IsNull() ||
- ((value.Length() >= 2) &&
- value.IsInstantiated() /*&& value.IsCanonical()*/));
- // TODO(asiva): Values read from a message snapshot are not properly marked
- // as canonical. See for example tests/isolate/message3_test.dart.
- untag()->set_type_arguments(value.ptr());
- }
-
- TypedDataPtr index() const { return untag()->index(); }
- void SetIndex(const TypedData& value) const {
- ASSERT(!value.IsNull());
- untag()->set_index(value.ptr());
- }
-
- ArrayPtr data() const { return untag()->data(); }
- void SetData(const Array& value) const { untag()->set_data(value.ptr()); }
-
- SmiPtr hash_mask() const { return untag()->hash_mask(); }
- void SetHashMask(intptr_t value) const {
- untag()->set_hash_mask(Smi::New(value));
- }
-
- SmiPtr used_data() const { return untag()->used_data(); }
- void SetUsedData(intptr_t value) const {
- untag()->set_used_data(Smi::New(value));
- }
-
- SmiPtr deleted_keys() const { return untag()->deleted_keys(); }
- void SetDeletedKeys(intptr_t value) const {
- untag()->set_deleted_keys(Smi::New(value));
- }
-
- intptr_t Length() const {
- // The map may be uninitialized.
- if (untag()->used_data() == Object::null()) return 0;
- if (untag()->deleted_keys() == Object::null()) return 0;
-
- intptr_t used = Smi::Value(untag()->used_data());
- intptr_t deleted = Smi::Value(untag()->deleted_keys());
- return (used >> 1) - deleted;
- }
-
// This iterator differs somewhat from its Dart counterpart (_CompactIterator
// in runtime/lib/compact_hash.dart):
// - There are no checks for concurrent modifications.
@@ -11115,12 +11167,42 @@
// Allocate a map, but leave all fields set to null.
// Used during deserialization (since map might contain itself as key/value).
- static LinkedHashMapPtr NewUninitialized(Heap::Space space = Heap::kNew);
+ static LinkedHashMapPtr NewUninitialized(intptr_t class_id,
+ Heap::Space space = Heap::kNew);
friend class Class;
+ friend class ImmutableLinkedHashMap;
friend class LinkedHashMapDeserializationCluster;
};
+class ImmutableLinkedHashMap : public AllStatic {
+ public:
+ static constexpr bool ContainsCompressedPointers() {
+ return LinkedHashMap::ContainsCompressedPointers();
+ }
+
+ static ImmutableLinkedHashMapPtr NewDefault(Heap::Space space = Heap::kNew);
+
+ static ImmutableLinkedHashMapPtr NewUninitialized(
+ Heap::Space space = Heap::kNew);
+
+ static const ClassId kClassId = kImmutableLinkedHashMapCid;
+
+ static intptr_t InstanceSize() { return LinkedHashMap::InstanceSize(); }
+
+ private:
+ static intptr_t NextFieldOffset() {
+ // Indicates this class cannot be extended by dart code.
+ return -kWordSize;
+ }
+
+ static ImmutableLinkedHashMapPtr raw(const LinkedHashMap& map) {
+ return static_cast<ImmutableLinkedHashMapPtr>(map.ptr());
+ }
+
+ friend class Class;
+};
+
class LinkedHashSet : public LinkedHashBase {
public:
static intptr_t InstanceSize() {
@@ -11128,60 +11210,16 @@
}
// Allocates a set with some default capacity, just like "new Set()".
- static LinkedHashSetPtr NewDefault(Heap::Space space = Heap::kNew);
- static LinkedHashSetPtr New(const Array& data,
+ static LinkedHashSetPtr NewDefault(intptr_t class_id = kLinkedHashSetCid,
+ Heap::Space space = Heap::kNew);
+ static LinkedHashSetPtr New(intptr_t class_id,
+ const Array& data,
const TypedData& index,
intptr_t hash_mask,
intptr_t used_data,
intptr_t deleted_keys,
Heap::Space space = Heap::kNew);
- virtual TypeArgumentsPtr GetTypeArguments() const {
- return untag()->type_arguments();
- }
- virtual void SetTypeArguments(const TypeArguments& value) const {
- ASSERT(value.IsNull() ||
- ((value.Length() >= 1) &&
- value.IsInstantiated() /*&& value.IsCanonical()*/));
- // TODO(asiva): Values read from a message snapshot are not properly marked
- // as canonical. See for example tests/isolate/message3_test.dart.
- untag()->set_type_arguments(value.ptr());
- }
-
- TypedDataPtr index() const { return untag()->index(); }
- void SetIndex(const TypedData& value) const {
- ASSERT(!value.IsNull());
- untag()->set_index(value.ptr());
- }
-
- ArrayPtr data() const { return untag()->data(); }
- void SetData(const Array& value) const { untag()->set_data(value.ptr()); }
-
- SmiPtr hash_mask() const { return untag()->hash_mask(); }
- void SetHashMask(intptr_t value) const {
- untag()->set_hash_mask(Smi::New(value));
- }
-
- SmiPtr used_data() const { return untag()->used_data(); }
- void SetUsedData(intptr_t value) const {
- untag()->set_used_data(Smi::New(value));
- }
-
- SmiPtr deleted_keys() const { return untag()->deleted_keys(); }
- void SetDeletedKeys(intptr_t value) const {
- untag()->set_deleted_keys(Smi::New(value));
- }
-
- intptr_t Length() const {
- // The map may be uninitialized.
- if (untag()->used_data() == Object::null()) return 0;
- if (untag()->deleted_keys() == Object::null()) return 0;
-
- intptr_t used = Smi::Value(untag()->used_data());
- intptr_t deleted = Smi::Value(untag()->deleted_keys());
- return used - deleted;
- }
-
// This iterator differs somewhat from its Dart counterpart (_CompactIterator
// in runtime/lib/compact_hash.dart):
// - There are no checks for concurrent modifications.
@@ -11223,7 +11261,38 @@
// Allocate a set, but leave all fields set to null.
// Used during deserialization (since set might contain itself as key/value).
- static LinkedHashSetPtr NewUninitialized(Heap::Space space = Heap::kNew);
+ static LinkedHashSetPtr NewUninitialized(intptr_t class_id,
+ Heap::Space space = Heap::kNew);
+
+ friend class Class;
+ friend class ImmutableLinkedHashSet;
+ friend class LinkedHashSetDeserializationCluster;
+};
+
+class ImmutableLinkedHashSet : public AllStatic {
+ public:
+ static constexpr bool ContainsCompressedPointers() {
+ return LinkedHashSet::ContainsCompressedPointers();
+ }
+
+ static ImmutableLinkedHashSetPtr NewDefault(Heap::Space space = Heap::kNew);
+
+ static ImmutableLinkedHashSetPtr NewUninitialized(
+ Heap::Space space = Heap::kNew);
+
+ static const ClassId kClassId = kImmutableLinkedHashSetCid;
+
+ static intptr_t InstanceSize() { return LinkedHashSet::InstanceSize(); }
+
+ private:
+ static intptr_t NextFieldOffset() {
+ // Indicates this class cannot be extended by dart code.
+ return -kWordSize;
+ }
+
+ static ImmutableLinkedHashSetPtr raw(const LinkedHashSet& map) {
+ return static_cast<ImmutableLinkedHashSetPtr>(map.ptr());
+ }
friend class Class;
};
diff --git a/runtime/vm/object_graph.cc b/runtime/vm/object_graph.cc
index 749c0f3..dfa116b 100644
--- a/runtime/vm/object_graph.cc
+++ b/runtime/vm/object_graph.cc
@@ -953,11 +953,11 @@
writer_->WriteUnsigned(kLengthData);
writer_->WriteUnsigned(Smi::Value(
static_cast<GrowableObjectArrayPtr>(obj)->untag()->length()));
- } else if (cid == kLinkedHashMapCid) {
+ } else if (cid == kLinkedHashMapCid || cid == kImmutableLinkedHashMapCid) {
writer_->WriteUnsigned(kLengthData);
writer_->WriteUnsigned(
Smi::Value(static_cast<LinkedHashMapPtr>(obj)->untag()->used_data()));
- } else if (cid == kLinkedHashSetCid) {
+ } else if (cid == kLinkedHashSetCid || cid == kImmutableLinkedHashSetCid) {
writer_->WriteUnsigned(kLengthData);
writer_->WriteUnsigned(
Smi::Value(static_cast<LinkedHashSetPtr>(obj)->untag()->used_data()));
@@ -1428,6 +1428,8 @@
case kExternalTwoByteStringCid:
case kGrowableObjectArrayCid:
case kImmutableArrayCid:
+ case kImmutableLinkedHashMapCid:
+ case kImmutableLinkedHashSetCid:
case kInstructionsCid:
case kInstructionsSectionCid:
case kInstructionsTableCid:
@@ -1454,7 +1456,7 @@
}
// Generates a random value which can serve as an identity hash.
-// It must be a non-zero smi value (see also [Object._getObjectHash]).
+// It must be a non-zero smi value (see also [Object._objectHashCode]).
static uint32_t GenerateHash(Random* random) {
uint32_t hash;
do {
diff --git a/runtime/vm/object_store.h b/runtime/vm/object_store.h
index a944d89..85a4265 100644
--- a/runtime/vm/object_store.h
+++ b/runtime/vm/object_store.h
@@ -136,7 +136,9 @@
RW(Class, immutable_array_class) \
RW(Class, growable_object_array_class) \
RW(Class, linked_hash_map_class) \
+ RW(Class, immutable_linked_hash_map_class) \
RW(Class, linked_hash_set_class) \
+ RW(Class, immutable_linked_hash_set_class) \
RW(Class, float32x4_class) \
RW(Class, int32x4_class) \
RW(Class, float64x2_class) \
diff --git a/runtime/vm/object_test.cc b/runtime/vm/object_test.cc
index fbb1527..910bd0c 100644
--- a/runtime/vm/object_test.cc
+++ b/runtime/vm/object_test.cc
@@ -5029,64 +5029,6 @@
/*check_identity=*/false));
}
-// Because we want to reuse CanonicalizeHash for hashCode, we should not have
-// collisions.
-TEST_CASE(CanonicalizeHash_Const_Instances) {
- const char* kScript =
- "class A {\n"
- " final int n;\n"
- " \n"
- " const A(this.n);\n"
- "}\n"
- "\n"
- "class B {\n"
- " final int n;\n"
- " \n"
- " const B(this.n);\n"
- "}\n"
- "\n"
- "valueA() {\n"
- " return const A(5);\n"
- "}\n"
- "\n"
- "valueB() {\n"
- " return const B(5);\n"
- "}\n";
-
- Dart_Handle lib = TestCase::LoadTestScript(kScript, nullptr);
- EXPECT_VALID(lib);
-
- Dart_Handle value_a_result =
- Dart_Invoke(lib, NewString("valueA"), 0, nullptr);
- EXPECT_VALID(value_a_result);
- Dart_Handle value_b_result =
- Dart_Invoke(lib, NewString("valueB"), 0, nullptr);
- EXPECT_VALID(value_b_result);
-
- TransitionNativeToVM transition(Thread::Current());
-
- const auto& value_a_dart = Instance::CheckedHandle(
- Thread::Current()->zone(), Api::UnwrapHandle(value_a_result));
- const auto& value_b_dart = Instance::CheckedHandle(
- Thread::Current()->zone(), Api::UnwrapHandle(value_b_result));
-
- const uint32_t canonicalize_hash_a = value_a_dart.CanonicalizeHash();
- const uint32_t canonicalize_hash_b = value_b_dart.CanonicalizeHash();
-
- bool success = canonicalize_hash_a != canonicalize_hash_b;
-
- if (!success) {
- LogBlock lb;
- THR_Print("Hash collision between %s and %s\n", value_a_dart.ToCString(),
- value_b_dart.ToCString());
- THR_Print("VM CanonicalizeHash a %" Px32 " %" Pd32 "\n",
- canonicalize_hash_a, canonicalize_hash_a);
- THR_Print("VM CanonicalizeHash b %" Px32 " %" Pd32 "\n",
- canonicalize_hash_b, canonicalize_hash_b);
- }
- EXPECT(success);
-}
-
TEST_CASE(LinkedHashMap_iteration) {
const char* kScript =
"makeMap() {\n"
@@ -5126,14 +5068,251 @@
EXPECT(!iterator.MoveNext());
}
+template <class LinkedHashBase>
+static bool LinkedHashBaseEqual(const LinkedHashBase& map1,
+ const LinkedHashBase& map2,
+ bool print_diff,
+ bool check_data = true) {
+ if (check_data) {
+ // Check data, only for non-nested.
+ const auto& data1 = Array::Handle(map1.data());
+ const auto& data2 = Array::Handle(map2.data());
+ const bool data_length_equal = data1.Length() == data2.Length();
+ bool data_equal = data_length_equal;
+ if (data_length_equal) {
+ auto& object1 = Instance::Handle();
+ auto& object2 = Instance::Handle();
+ for (intptr_t i = 0; i < data1.Length(); i++) {
+ object1 ^= data1.At(i);
+ object2 ^= data2.At(i);
+ data_equal &= object1.CanonicalizeEquals(object2);
+ }
+ }
+ if (!data_equal) {
+ if (print_diff) {
+ THR_Print("LinkedHashBaseEqual Data not equal.\n");
+ THR_Print("LinkedHashBaseEqual data1.length %" Pd " data1.length %" Pd
+ " \n",
+ data1.Length(), data2.Length());
+ auto& object1 = Instance::Handle();
+ for (intptr_t i = 0; i < data1.Length(); i++) {
+ object1 ^= data1.At(i);
+ THR_Print("LinkedHashBaseEqual data1[%" Pd "] %s\n", i,
+ object1.ToCString());
+ }
+ for (intptr_t i = 0; i < data2.Length(); i++) {
+ object1 ^= data2.At(i);
+ THR_Print("LinkedHashBaseEqual data2[%" Pd "] %s\n", i,
+ object1.ToCString());
+ }
+ }
+ return false;
+ }
+ }
+
+ // Check hashing.
+ intptr_t hash_mask1 = Smi::Value(map1.hash_mask());
+ EXPECT(!Integer::Handle(map2.hash_mask()).IsNull());
+ intptr_t hash_mask2 = Smi::Value(map2.hash_mask());
+ const bool hash_masks_equal = hash_mask1 == hash_mask2;
+ if (!hash_masks_equal) {
+ if (print_diff) {
+ THR_Print("LinkedHashBaseEqual Hash masks not equal.\n");
+ THR_Print("LinkedHashBaseEqual hash_mask1 %" Px " hash_mask2 %" Px " \n",
+ hash_mask1, hash_mask2);
+ }
+ }
+
+ // Check indices.
+ const auto& index1 = TypedData::Handle(map1.index());
+ const auto& index2 = TypedData::Handle(map2.index());
+ EXPECT(!index2.IsNull());
+ ASSERT(index1.ElementType() == kUint32ArrayElement);
+ ASSERT(index2.ElementType() == kUint32ArrayElement);
+ const intptr_t kElementSize = 4;
+ ASSERT(kElementSize == index1.ElementSizeInBytes());
+ const bool index_length_equal = index1.Length() == index2.Length();
+ bool index_equal = index_length_equal;
+ if (index_length_equal) {
+ for (intptr_t i = 0; i < index1.Length(); i++) {
+ const uint32_t index1_val = index1.GetUint32(i * kElementSize);
+ const uint32_t index2_val = index2.GetUint32(i * kElementSize);
+ index_equal &= index1_val == index2_val;
+ }
+ }
+ if (!index_equal && print_diff) {
+ THR_Print("LinkedHashBaseEqual Indices not equal.\n");
+ THR_Print("LinkedHashBaseEqual index1.length %" Pd " index2.length %" Pd
+ " \n",
+ index1.Length(), index2.Length());
+ for (intptr_t i = 0; i < index1.Length(); i++) {
+ const uint32_t index_val = index1.GetUint32(i * kElementSize);
+ THR_Print("LinkedHashBaseEqual index1[%" Pd "] %" Px32 "\n", i,
+ index_val);
+ }
+ for (intptr_t i = 0; i < index2.Length(); i++) {
+ const uint32_t index_val = index2.GetUint32(i * kElementSize);
+ THR_Print("LinkedHashBaseEqual index2[%" Pd "] %" Px32 "\n", i,
+ index_val);
+ }
+ }
+ return index_equal;
+}
+
+// Copies elements from data.
+static LinkedHashMapPtr ConstructImmutableMap(
+ const Array& input_data,
+ intptr_t used_data,
+ const TypeArguments& type_arguments) {
+ auto& map = LinkedHashMap::Handle(ImmutableLinkedHashMap::NewUninitialized());
+
+ const auto& data = Array::Handle(Array::New(input_data.Length()));
+ for (intptr_t i = 0; i < used_data; i++) {
+ data.SetAt(i, Object::Handle(input_data.At(i)));
+ }
+ map.set_data(data);
+ map.set_used_data(used_data);
+ map.SetTypeArguments(type_arguments);
+ map.set_deleted_keys(0);
+ map.ComputeAndSetHashMask();
+ map ^= map.Canonicalize(Thread::Current());
+
+ return map.ptr();
+}
+
+// Constructs an immutable hashmap from a mutable one in this test.
+TEST_CASE(ImmutableLinkedHashMap_vm) {
+ const char* kScript = R"(
+enum ExperimentalFlag {
+ alternativeInvalidationStrategy,
+ constFunctions,
+ constantUpdate2018,
+ constructorTearoffs,
+ controlFlowCollections,
+ extensionMethods,
+ extensionTypes,
+ genericMetadata,
+ nonNullable,
+ nonfunctionTypeAliases,
+ setLiterals,
+ spreadCollections,
+ testExperiment,
+ tripleShift,
+ valueClass,
+ variance,
+}
+
+final Map<ExperimentalFlag?, bool> expiredExperimentalFlagsNonConst = {
+ ExperimentalFlag.alternativeInvalidationStrategy: false,
+ ExperimentalFlag.constFunctions: false,
+ ExperimentalFlag.constantUpdate2018: true,
+ ExperimentalFlag.constructorTearoffs: false,
+ ExperimentalFlag.controlFlowCollections: true,
+ ExperimentalFlag.extensionMethods: false,
+ ExperimentalFlag.extensionTypes: false,
+ ExperimentalFlag.genericMetadata: false,
+ ExperimentalFlag.nonNullable: false,
+ ExperimentalFlag.nonfunctionTypeAliases: false,
+ ExperimentalFlag.setLiterals: true,
+ ExperimentalFlag.spreadCollections: true,
+ ExperimentalFlag.testExperiment: false,
+ ExperimentalFlag.tripleShift: false,
+ ExperimentalFlag.valueClass: false,
+ ExperimentalFlag.variance: false,
+};
+
+makeNonConstMap() {
+ return expiredExperimentalFlagsNonConst;
+}
+
+firstKey() {
+ return ExperimentalFlag.alternativeInvalidationStrategy;
+}
+
+firstKeyHashCode() {
+ return firstKey().hashCode;
+}
+
+firstKeyIdentityHashCode() {
+ return identityHashCode(firstKey());
+}
+
+bool lookupSpreadCollections(Map map) =>
+ map[ExperimentalFlag.spreadCollections];
+
+bool? lookupNull(Map map) => map[null];
+)";
+ Dart_Handle lib = TestCase::LoadTestScript(kScript, NULL);
+ EXPECT_VALID(lib);
+ Dart_Handle non_const_result =
+ Dart_Invoke(lib, NewString("makeNonConstMap"), 0, NULL);
+ EXPECT_VALID(non_const_result);
+ Dart_Handle first_key_result =
+ Dart_Invoke(lib, NewString("firstKey"), 0, NULL);
+ EXPECT_VALID(first_key_result);
+ Dart_Handle first_key_hashcode_result =
+ Dart_Invoke(lib, NewString("firstKeyHashCode"), 0, NULL);
+ EXPECT_VALID(first_key_hashcode_result);
+ Dart_Handle first_key_identity_hashcode_result =
+ Dart_Invoke(lib, NewString("firstKeyIdentityHashCode"), 0, NULL);
+ EXPECT_VALID(first_key_identity_hashcode_result);
+
+ Dart_Handle const_argument;
+
+ {
+ TransitionNativeToVM transition(thread);
+ const auto& non_const_map = LinkedHashMap::Cast(
+ Object::Handle(Api::UnwrapHandle(non_const_result)));
+ const auto& non_const_type_args =
+ TypeArguments::Handle(non_const_map.GetTypeArguments());
+ const auto& non_const_data = Array::Handle(non_const_map.data());
+ const auto& const_map = LinkedHashMap::Handle(ConstructImmutableMap(
+ non_const_data, Smi::Value(non_const_map.used_data()),
+ non_const_type_args));
+ ASSERT(non_const_map.GetClassId() == kLinkedHashMapCid);
+ ASSERT(const_map.GetClassId() == kImmutableLinkedHashMapCid);
+ ASSERT(!non_const_map.IsCanonical());
+ ASSERT(const_map.IsCanonical());
+
+ const_argument = Api::NewHandle(thread, const_map.ptr());
+ }
+
+ Dart_Handle lookup_result = Dart_Invoke(
+ lib, NewString("lookupSpreadCollections"), 1, &const_argument);
+ EXPECT_VALID(lookup_result);
+ EXPECT_TRUE(lookup_result);
+
+ Dart_Handle lookup_null_result =
+ Dart_Invoke(lib, NewString("lookupNull"), 1, &const_argument);
+ EXPECT_VALID(lookup_null_result);
+ EXPECT_NULL(lookup_null_result);
+
+ {
+ TransitionNativeToVM transition(thread);
+ const auto& non_const_object =
+ Object::Handle(Api::UnwrapHandle(non_const_result));
+ const auto& non_const_map = LinkedHashMap::Cast(non_const_object);
+ const auto& const_object =
+ Object::Handle(Api::UnwrapHandle(const_argument));
+ const auto& const_map = LinkedHashMap::Cast(const_object);
+
+ EXPECT(non_const_map.GetClassId() != const_map.GetClassId());
+
+ // Check that the index is identical.
+ EXPECT(LinkedHashBaseEqual(non_const_map, const_map,
+ /*print_diff=*/true));
+ }
+}
+
TEST_CASE(LinkedHashSet_iteration) {
- const char* kScript =
- "makeSet() {\n"
- " var set = {'x', 'y', 'z', 'w'};\n"
- " set.remove('y');\n"
- " set.remove('w');\n"
- " return set;\n"
- "}";
+ const char* kScript = R"(
+makeSet() {
+ var set = {'x', 'y', 'z', 'w'};
+ set.remove('y');
+ set.remove('w');
+ return set;
+}
+)";
Dart_Handle h_lib = TestCase::LoadTestScript(kScript, NULL);
EXPECT_VALID(h_lib);
Dart_Handle h_result = Dart_Invoke(h_lib, NewString("makeSet"), 0, NULL);
@@ -5161,6 +5340,85 @@
EXPECT(!iterator.MoveNext());
}
+// Copies elements from data.
+static LinkedHashSetPtr ConstructImmutableSet(
+ const Array& input_data,
+ intptr_t used_data,
+ const TypeArguments& type_arguments) {
+ auto& set = LinkedHashSet::Handle(ImmutableLinkedHashSet::NewUninitialized());
+
+ const auto& data = Array::Handle(Array::New(input_data.Length()));
+ for (intptr_t i = 0; i < used_data; i++) {
+ data.SetAt(i, Object::Handle(input_data.At(i)));
+ }
+ set.set_data(data);
+ set.set_used_data(used_data);
+ set.SetTypeArguments(type_arguments);
+ set.set_deleted_keys(0);
+ set.ComputeAndSetHashMask();
+ set ^= set.Canonicalize(Thread::Current());
+
+ return set.ptr();
+}
+
+TEST_CASE(ImmutableLinkedHashSet_vm) {
+ const char* kScript = R"(
+makeNonConstSet() {
+ return {1, 2, 3, 5, 8, 13};
+}
+
+bool containsFive(Set set) => set.contains(5);
+)";
+ Dart_Handle lib = TestCase::LoadTestScript(kScript, NULL);
+ EXPECT_VALID(lib);
+ Dart_Handle non_const_result =
+ Dart_Invoke(lib, NewString("makeNonConstSet"), 0, NULL);
+ EXPECT_VALID(non_const_result);
+
+ Dart_Handle const_argument;
+
+ {
+ TransitionNativeToVM transition(thread);
+ const auto& non_const_object =
+ Object::Handle(Api::UnwrapHandle(non_const_result));
+ const auto& non_const_set = LinkedHashSet::Cast(non_const_object);
+ ASSERT(non_const_set.GetClassId() == kLinkedHashSetCid);
+ ASSERT(!non_const_set.IsCanonical());
+
+ const auto& non_const_data = Array::Handle(non_const_set.data());
+ const auto& non_const_type_args =
+ TypeArguments::Handle(non_const_set.GetTypeArguments());
+ const auto& const_set = LinkedHashSet::Handle(ConstructImmutableSet(
+ non_const_data, Smi::Value(non_const_set.used_data()),
+ non_const_type_args));
+ ASSERT(const_set.GetClassId() == kImmutableLinkedHashSetCid);
+ ASSERT(const_set.IsCanonical());
+
+ const_argument = Api::NewHandle(thread, const_set.ptr());
+ }
+
+ Dart_Handle contains_5_result =
+ Dart_Invoke(lib, NewString("containsFive"), 1, &const_argument);
+ EXPECT_VALID(contains_5_result);
+ EXPECT_TRUE(contains_5_result);
+
+ {
+ TransitionNativeToVM transition(thread);
+ const auto& non_const_object =
+ Object::Handle(Api::UnwrapHandle(non_const_result));
+ const auto& non_const_set = LinkedHashSet::Cast(non_const_object);
+ const auto& const_object =
+ Object::Handle(Api::UnwrapHandle(const_argument));
+ const auto& const_set = LinkedHashSet::Cast(const_object);
+
+ EXPECT(non_const_set.GetClassId() != const_set.GetClassId());
+
+ // Check that the index is identical.
+ EXPECT(LinkedHashBaseEqual(non_const_set, const_set,
+ /*print_diff=*/true));
+ }
+}
+
static void CheckConcatAll(const String* data[], intptr_t n) {
Thread* thread = Thread::Current();
Zone* zone = thread->zone();
diff --git a/runtime/vm/raw_object.cc b/runtime/vm/raw_object.cc
index b79c6b9..ae6c199 100644
--- a/runtime/vm/raw_object.cc
+++ b/runtime/vm/raw_object.cc
@@ -727,6 +727,18 @@
return UntaggedArray::VisitArrayPointers(raw_obj, visitor);
}
+intptr_t UntaggedImmutableLinkedHashMap::VisitImmutableLinkedHashMapPointers(
+ ImmutableLinkedHashMapPtr raw_obj,
+ ObjectPointerVisitor* visitor) {
+ return UntaggedLinkedHashMap::VisitLinkedHashMapPointers(raw_obj, visitor);
+}
+
+intptr_t UntaggedImmutableLinkedHashSet::VisitImmutableLinkedHashSetPointers(
+ ImmutableLinkedHashSetPtr raw_obj,
+ ObjectPointerVisitor* visitor) {
+ return UntaggedLinkedHashSet::VisitLinkedHashSetPointers(raw_obj, visitor);
+}
+
void UntaggedObject::RememberCard(ObjectPtr const* slot) {
OldPage::Of(static_cast<ObjectPtr>(this))->RememberCard(slot);
}
diff --git a/runtime/vm/raw_object.h b/runtime/vm/raw_object.h
index 5fd0641..58b66be 100644
--- a/runtime/vm/raw_object.h
+++ b/runtime/vm/raw_object.h
@@ -2943,6 +2943,8 @@
friend class LinkedHashMapSerializationCluster;
friend class LinkedHashMapDeserializationCluster;
+ friend class LinkedHashSetSerializationCluster;
+ friend class LinkedHashSetDeserializationCluster;
friend class CodeSerializationCluster;
friend class CodeDeserializationCluster;
friend class Deserializer;
@@ -2951,6 +2953,7 @@
friend class GrowableObjectArray;
friend class LinkedHashMap;
friend class UntaggedLinkedHashMap;
+ friend class UntaggedImmutableLinkedHashMap;
friend class Object;
friend class ICData; // For high performance access.
friend class SubtypeTestCache; // For high performance access.
@@ -2999,10 +3002,22 @@
class UntaggedLinkedHashMap : public UntaggedLinkedHashBase {
RAW_HEAP_OBJECT_IMPLEMENTATION(LinkedHashMap);
+
+ friend class UntaggedImmutableLinkedHashMap;
+};
+
+class UntaggedImmutableLinkedHashMap : public UntaggedLinkedHashMap {
+ RAW_HEAP_OBJECT_IMPLEMENTATION(ImmutableLinkedHashMap);
};
class UntaggedLinkedHashSet : public UntaggedLinkedHashBase {
RAW_HEAP_OBJECT_IMPLEMENTATION(LinkedHashSet);
+
+ friend class UntaggedImmutableLinkedHashSet;
+};
+
+class UntaggedImmutableLinkedHashSet : public UntaggedLinkedHashSet {
+ RAW_HEAP_OBJECT_IMPLEMENTATION(ImmutableLinkedHashSet);
};
class UntaggedFloat32x4 : public UntaggedInstance {
diff --git a/runtime/vm/symbols.h b/runtime/vm/symbols.h
index f5cc31c..eee7c62 100644
--- a/runtime/vm/symbols.h
+++ b/runtime/vm/symbols.h
@@ -325,6 +325,8 @@
V(_GrowableListGenerateFactory, "_GrowableList.generate") \
V(_GrowableListLiteralFactory, "_GrowableList._literal") \
V(_GrowableListWithData, "_GrowableList._withData") \
+ V(_ImmutableLinkedHashMap, "_InternalImmutableLinkedHashMap") \
+ V(_ImmutableLinkedHashSet, "_CompactImmutableLinkedHashSet") \
V(_ImmutableList, "_ImmutableList") \
V(_Int16ArrayFactory, "Int16List.") \
V(_Int16ArrayView, "_Int16ArrayView") \
diff --git a/runtime/vm/tagged_pointer.h b/runtime/vm/tagged_pointer.h
index 19444ff..c7c8b94 100644
--- a/runtime/vm/tagged_pointer.h
+++ b/runtime/vm/tagged_pointer.h
@@ -397,6 +397,8 @@
DEFINE_TAGGED_POINTER(LinkedHashBase, Instance)
DEFINE_TAGGED_POINTER(LinkedHashMap, LinkedHashBase)
DEFINE_TAGGED_POINTER(LinkedHashSet, LinkedHashBase)
+DEFINE_TAGGED_POINTER(ImmutableLinkedHashMap, LinkedHashMap)
+DEFINE_TAGGED_POINTER(ImmutableLinkedHashSet, LinkedHashSet)
DEFINE_TAGGED_POINTER(Float32x4, Instance)
DEFINE_TAGGED_POINTER(Int32x4, Instance)
DEFINE_TAGGED_POINTER(Float64x2, Instance)
diff --git a/sdk/lib/_internal/vm/lib/class_id_fasta.dart b/sdk/lib/_internal/vm/lib/class_id_fasta.dart
index 006314b..52c81ad 100644
--- a/sdk/lib/_internal/vm/lib/class_id_fasta.dart
+++ b/sdk/lib/_internal/vm/lib/class_id_fasta.dart
@@ -8,7 +8,7 @@
class ClassID {
@pragma("vm:recognized", "other")
@pragma("vm:exact-result-type", "dart:core#_Smi")
- static int getID(Object value) native "ClassID_getID";
+ static int getID(Object? value) native "ClassID_getID";
@pragma("vm:entry-point")
static final int cidArray = 0;
@@ -38,4 +38,8 @@
static final int cidUint8ClampedArray = 0;
@pragma("vm:entry-point")
static final int cidExternalUint8ClampedArray = 0;
+ // Used in const hashing to determine whether we're dealing with a
+ // user-defined const. See lib/_internal/vm/lib/compact_hash.dart.
+ @pragma("vm:entry-point")
+ static final int numPredefinedCids = 0;
}
diff --git a/sdk/lib/_internal/vm/lib/collection_patch.dart b/sdk/lib/_internal/vm/lib/collection_patch.dart
index a1acbcb..4755514 100644
--- a/sdk/lib/_internal/vm/lib/collection_patch.dart
+++ b/sdk/lib/_internal/vm/lib/collection_patch.dart
@@ -9,7 +9,9 @@
import "dart:_internal" as internal;
-import "dart:_internal" show patch, IterableElementError;
+import "dart:_internal" show patch, IterableElementError, ClassID;
+
+import "dart:math" show max;
import "dart:typed_data" show Uint32List;
diff --git a/sdk/lib/_internal/vm/lib/compact_hash.dart b/sdk/lib/_internal/vm/lib/compact_hash.dart
index dc552c7..29c57e7 100644
--- a/sdk/lib/_internal/vm/lib/compact_hash.dart
+++ b/sdk/lib/_internal/vm/lib/compact_hash.dart
@@ -30,6 +30,8 @@
int _hashMask = 0;
// Fixed-length list of keys (set) or key/value at even/odd indices (map).
+ //
+ // Can be either a mutable or immutable list.
List _data = _initialData;
// Length of _data that is used (i.e., keys + values for a map).
@@ -87,6 +89,27 @@
void set _deletedKeys(int value) native "LinkedHashBase_setDeletedKeys";
}
+// Base class for VM-internal classes; keep in sync with _HashFieldBase.
+abstract class _HashVMImmutableBase extends _HashVMBase {
+ // The data is an immutable list rather than a mutable list.
+ @pragma("vm:recognized", "other")
+ @pragma("vm:exact-result-type", "dart:core#_ImmutableList")
+ @pragma("vm:prefer-inline")
+ List get _data native "ImmutableLinkedHashBase_getData";
+
+ // The index is nullable rather than not nullable.
+ @pragma("vm:recognized", "other")
+ @pragma("vm:prefer-inline")
+ Uint32List? get _indexNullable native "ImmutableLinkedHashBase_getIndex";
+ Uint32List get _index => _indexNullable!;
+
+ // Uses store-release atomic.
+ @pragma("vm:recognized", "other")
+ @pragma("vm:prefer-inline")
+ void set _index(Uint32List value)
+ native "ImmutableLinkedHashBase_setIndexStoreRelease";
+}
+
// This mixin can be applied to _HashFieldBase or _HashVMBase (for
// normal and VM-internalized classes, respectiveley), which provide the
// actual fields/accessors that this mixin assumes.
@@ -107,6 +130,7 @@
// On 32-bit, the top bits are wasted to avoid Mint allocation.
// TODO(koda): Reclaim the bits by making the compiler treat hash patterns
// as unsigned words.
+ // Keep consistent with IndexSizeToHashMask in runtime/vm/object.h.
static int _indexSizeToHashMask(int indexSize) {
int indexBits = indexSize.bitLength - 2;
return internal.has63BitSmis
@@ -155,6 +179,20 @@
bool _equals(e1, e2) => identical(e1, e2);
}
+class _OperatorEqualsAndCanonicalHashCode {
+ static final int cidSymbol = ClassID.getID(#a);
+
+ int _hashCode(e) {
+ final int cid = ClassID.getID(e);
+ if (cid < ClassID.numPredefinedCids || cid == cidSymbol) {
+ return e.hashCode;
+ }
+ return identityHashCode(e);
+ }
+
+ bool _equals(e1, e2) => e1 == e2;
+}
+
final _initialIndex = new Uint32List(1);
// Note: not const. Const arrays are made immutable by having a different class
// than regular arrays that throws on element assignment. We want the data field
@@ -179,6 +217,82 @@
}
}
+// This is essentially the same class as _InternalLinkedHashMap, but it does
+// not permit any modification of map entries from Dart code. We use
+// this class for maps constructed from Dart constant maps.
+@pragma("vm:entry-point")
+class _InternalImmutableLinkedHashMap<K, V> extends _HashVMImmutableBase
+ with
+ MapMixin<K, V>,
+ _LinkedHashMapMixin<K, V>,
+ _HashBase,
+ _OperatorEqualsAndCanonicalHashCode,
+ _UnmodifiableMapMixin<K, V>
+ implements LinkedHashMap<K, V> {
+ factory _InternalImmutableLinkedHashMap._uninstantiable() {
+ throw new UnsupportedError("ImmutableMap can only be allocated by the VM");
+ }
+
+ bool containsKey(Object? key) {
+ if (_indexNullable == null) {
+ _createIndex();
+ }
+ return super.containsKey(key);
+ }
+
+ V? operator [](Object? key) {
+ if (_indexNullable == null) {
+ _createIndex();
+ }
+ return super[key];
+ }
+
+ void _createIndex() {
+ assert(_indexNullable == null);
+
+ final size = max(_data.length, _HashBase._INITIAL_INDEX_SIZE);
+ assert(size == _roundUpToPowerOfTwo(size));
+ final newIndex = new Uint32List(size);
+ final hashMask = _HashBase._indexSizeToHashMask(size);
+ assert(_hashMask == hashMask);
+
+ for (int j = 0; j < _usedData; j += 2) {
+ final key = _data[j];
+ final value = _data[j + 1];
+
+ final fullHash = _hashCode(key);
+ final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
+ final d =
+ _findValueOrInsertPoint(key, fullHash, hashPattern, size, newIndex);
+ // We just allocated the index, so we should not find this key in it yet.
+ assert(d <= 0);
+
+ final i = -d;
+
+ assert(1 <= hashPattern && hashPattern < (1 << 32));
+ final index = j >> 1;
+ assert((index & hashPattern) == 0);
+ newIndex[i] = hashPattern | index;
+ }
+
+ // Publish new index, uses store release semantics.
+ _index = newIndex;
+ }
+}
+
+// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
+// figure 3-3, page 48, where the function is called clp2.
+int _roundUpToPowerOfTwo(int x) {
+ x = x - 1;
+ x = x | (x >> 1);
+ x = x | (x >> 2);
+ x = x | (x >> 4);
+ x = x | (x >> 8);
+ x = x | (x >> 16);
+ x = x | (x >> 32);
+ return x + 1;
+}
+
abstract class _LinkedHashMapMixin<K, V> implements _HashBase {
int _hashCode(e);
bool _equals(e1, e2);
@@ -260,13 +374,14 @@
}
// If key is present, returns the index of the value in _data, else returns
- // the negated insertion point in _index.
- int _findValueOrInsertPoint(K key, int fullHash, int hashPattern, int size) {
+ // the negated insertion point in index.
+ int _findValueOrInsertPoint(
+ K key, int fullHash, int hashPattern, int size, Uint32List index) {
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
int i = _HashBase._firstProbe(fullHash, sizeMask);
int firstDeleted = -1;
- int pair = _index[i];
+ int pair = index[i];
while (pair != _HashBase._UNUSED_PAIR) {
if (pair == _HashBase._DELETED_PAIR) {
if (firstDeleted < 0) {
@@ -282,7 +397,7 @@
}
}
i = _HashBase._nextProbe(i, sizeMask);
- pair = _index[i];
+ pair = index[i];
}
return firstDeleted >= 0 ? -firstDeleted : -i;
}
@@ -291,7 +406,8 @@
final int size = _index.length;
final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
- final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
+ final int d =
+ _findValueOrInsertPoint(key, fullHash, hashPattern, size, _index);
if (d > 0) {
_data[d] = value;
} else {
@@ -304,7 +420,8 @@
final int size = _index.length;
final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
- final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
+ final int d =
+ _findValueOrInsertPoint(key, fullHash, hashPattern, size, _index);
if (d > 0) {
return _data[d];
}
@@ -682,6 +799,84 @@
Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this);
}
+@pragma("vm:entry-point")
+class _CompactImmutableLinkedHashSet<E> extends _HashVMImmutableBase
+ with
+ SetMixin<E>,
+ _LinkedHashSetMixin<E>,
+ _HashBase,
+ _OperatorEqualsAndCanonicalHashCode,
+ _UnmodifiableSetMixin<E>
+ implements LinkedHashSet<E> {
+ factory _CompactImmutableLinkedHashSet._uninstantiable() {
+ throw new UnsupportedError("ImmutableSet can only be allocated by the VM");
+ }
+
+ E? lookup(Object? key) {
+ if (_indexNullable == null) {
+ _createIndex();
+ }
+ return super.lookup(key);
+ }
+
+ bool contains(Object? key) {
+ if (_indexNullable == null) {
+ _createIndex();
+ }
+ return super.contains(key);
+ }
+
+ void _createIndex() {
+ assert(_indexNullable == null);
+
+ final size = _roundUpToPowerOfTwo(
+ max(_data.length * 2, _HashBase._INITIAL_INDEX_SIZE));
+ final index = new Uint32List(size);
+ final hashMask = _HashBase._indexSizeToHashMask(size);
+ assert(_hashMask == hashMask);
+
+ final sizeMask = size - 1;
+ final maxEntries = size >> 1;
+
+ for (int j = 0; j < _usedData; j++) {
+ final key = _data[j];
+
+ final fullHash = _hashCode(key);
+ final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
+
+ int i = _HashBase._firstProbe(fullHash, sizeMask);
+ int pair = index[i];
+ while (pair != _HashBase._UNUSED_PAIR) {
+ assert(pair != _HashBase._DELETED_PAIR);
+
+ final int d = hashPattern ^ pair;
+ if (d < maxEntries) {
+ // We should not already find an entry in the index.
+ assert(!_equals(key, _data[d]));
+ }
+
+ i = _HashBase._nextProbe(i, sizeMask);
+ pair = index[i];
+ }
+
+ final int insertionPoint = i;
+ assert(1 <= hashPattern && hashPattern < (1 << 32));
+ assert((hashPattern & j) == 0);
+ index[insertionPoint] = hashPattern | j;
+ }
+
+ // Publish new index, uses store release semantics.
+ _index = index;
+ }
+
+ Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);
+
+ static Set<R> _newEmpty<R>() => new _CompactLinkedHashSet<R>();
+
+ // Returns a mutable set.
+ Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this);
+}
+
class _CompactLinkedIdentityHashSet<E> extends _HashFieldBase
with
SetMixin<E>,
