Add VM class for Map/LinkedHashMap.

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 38122)
+++ runtime/vm/object.cc	(working copy)
@@ -1153,6 +1153,27 @@
   cls = Class::New<MirrorReference>();
   RegisterPrivateClass(cls, Symbols::_MirrorReference(), lib);
 
+  // Pre-register the collection library so we can place the vm class
+  // LinkedHashMap there rather than the core library.
+  lib = Library::LookupLibrary(Symbols::DartCollection());
+  if (lib.IsNull()) {
+    lib = Library::NewLibraryHelper(Symbols::DartCollection(), true);
+    lib.SetLoadRequested();
+    lib.Register();
+    isolate->object_store()->set_bootstrap_library(ObjectStore::kCollection,
+                                                   lib);
+  }
+  ASSERT(!lib.IsNull());
+  ASSERT(lib.raw() == Library::CollectionLibrary());
+
+  cls = Class::New<LinkedHashMap>();
+  object_store->set_linked_hash_map_class(cls);
+  cls.set_type_arguments_field_offset(LinkedHashMap::type_arguments_offset());
+  cls.set_num_type_arguments(2);
+  cls.set_num_own_type_arguments(2);
+  RegisterPrivateClass(cls, Symbols::_LinkedHashMap(), lib);
+  pending_classes.Add(cls);
+
   // Pre-register the profiler library so we can place the vm class
   // UserTag there rather than the core library.
   lib = Library::LookupLibrary(Symbols::DartProfiler());
@@ -1423,6 +1444,9 @@
   cls = Class::New<GrowableObjectArray>();
   object_store->set_growable_object_array_class(cls);
 
+  cls = Class::New<LinkedHashMap>();
+  object_store->set_linked_hash_map_class(cls);
+
   cls = Class::New<Float32x4>();
   object_store->set_float32x4_class(cls);
 
@@ -17989,6 +18013,172 @@
 }
 
 
+// Equivalent to Dart's operator "==" and hashCode.
+class DefaultHashTraits {
+ public:
+  static bool IsMatch(const Object& a, const Object& b) {
+    if (a.IsNull() || b.IsNull()) {

[siva, 2014/07/23 22:43:07]

why not

if (a.raw() == b.raw()) {
  return true;
} else {
  return Instance::Cast(a).......
}  

[koda, 2014/07/24 19:31:44]

Because that could give the wrong result for NaN.

I focused on correctness in this CL. We could definitely inline the common
cases, but performance tuning will come later (and probably focus more on the
Dart/intrinsics).

On 2014/07/23 22:43:07, siva wrote:

+      return (a.IsNull() && b.IsNull());
+    } else {
+      return Instance::Cast(a).OperatorEquals(Instance::Cast(b));
+    }
+  }
+  static uword Hash(const Object& obj) {
+    if (obj.IsNull()) {
+      return 0;
+    }

[siva, 2014/07/23 22:43:07]

Need a NoGCScope here right as we have a raw object being used below.

[koda, 2014/07/24 19:31:44]

Although I don't think there was any actual bug, I agree that the code looks
unsafe.

So, for now I'll instead always create the handle (cannot use NoGCScope since
HashCode currently might allocate). Once the TODO has been addressed and we only
have Smis, this will be simple and fast.

+    RawObject* raw_hash_code = Instance::Cast(obj).HashCode();
+    // TODO(koda): Ensure VM classes only produce Smi hash codes, and remove
+    // non-Smi cases once Dart-side implementation is complete.
+    if (raw_hash_code->IsHeapObject()) {
+      Isolate* isolate = Isolate::Current();
+      REUSABLE_OBJECT_HANDLESCOPE(isolate);
+      Object& hash_code = isolate->ObjectHandle();
+      hash_code = raw_hash_code;
+      if (hash_code.IsInteger()) {
+        return static_cast<uword>(
+            Integer::Cast(hash_code).AsTruncatedUint32Value());
+      } else {
+        return 0;
+      }
+    } else {
+      // May waste some bits on 64-bit, to ensure consistency with non-Smi case.
+      return static_cast<uword>(
+          Smi::Value(Smi::RawCast(raw_hash_code)) & 0xFFFFFFFF);
+    }
+  }
+};
+typedef EnumIndexHashMap<DefaultHashTraits> EnumIndexDefaultMap;
+
+
+intptr_t LinkedHashMap::Length() const {
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  intptr_t result = map.NumOccupied();
+  {
+    RawArray* array = map.Release();
+    ASSERT(array == data());
+  }
+  return result;
+}
+
+
+void LinkedHashMap::InsertOrUpdate(const Object& key,
+                                     const Object& value) const {
+  ASSERT(!IsNull());
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  if (!map.UpdateOrInsert(key, value)) {
+    SetModified();
+  }
+  StorePointer(&raw_ptr()->data_, map.Release());
+}
+
+
+RawObject* LinkedHashMap::LookUp(const Object& key) const {
+  ASSERT(!IsNull());
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  Object& result = Object::Handle(map.GetOrNull(key));

[siva, 2014/07/23 22:43:07]

const Object& result ....

[koda, 2014/07/24 19:31:44]

Done.

+  {
+    RawArray* array = map.Release();
+    ASSERT(array == data());
+  }
+  return result.raw();
+}
+
+
+bool LinkedHashMap::Contains(const Object& key) const {
+  ASSERT(!IsNull());
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  bool result = map.ContainsKey(key);
+  {
+    RawArray* array = map.Release();
+    ASSERT(array == data());
+  }
+  return result;
+}
+
+
+RawObject* LinkedHashMap::Remove(const Object& key) const {
+  ASSERT(!IsNull());
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  // TODO(koda): Make 'Remove' also return the old value.
+  Object& result = Object::Handle(map.GetOrNull(key));

[siva, 2014/07/23 22:43:06]

const Object& result ....

[koda, 2014/07/24 19:31:44]

Done.

+  if (map.Remove(key)) {
+    SetModified();
+  }
+  StorePointer(&raw_ptr()->data_, map.Release());
+  return result.raw();
+}
+
+
+void LinkedHashMap::Clear() const {
+  ASSERT(!IsNull());
+  if (Length() != 0) {
+    SetModified();
+  }
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  map.Initialize();
+  StorePointer(&raw_ptr()->data_, map.Release());

[siva, 2014/07/23 22:43:07]

Do we still require to do a map.Initialize() if Length() is 0.

i.e if Clear() is called twice in succession do we need to go over this code
twice?

[koda, 2014/07/24 19:31:44]

No, you are right. Moved everything into the 'if'.

+}
+
+
+RawArray* LinkedHashMap::ToArray() const {
+  EnumIndexDefaultMap map(Array::Handle(data()));
+  const Array& result = Array::Handle(HashTables::ToArray(map, true));
+  RawArray* array = map.Release();
+  ASSERT(array == data());
+  return result.raw();
+}
+
+
+void LinkedHashMap::SetModified() const {
+  StorePointer(&raw_ptr()->cme_mark_, Instance::null());
+}
+
+
+RawInstance* LinkedHashMap::GetModificationMark(bool create) const {
+  if (create && raw_ptr()->cme_mark_ == Instance::null()) {
+    Class& object_class =
+        Class::Handle(Isolate::Current()->object_store()->object_class());
+    Instance& current = Instance::Handle(Instance::New(object_class));

[siva, 2014/07/23 22:43:07]

Would be worth allocating a local variable isolate and using it for the handle
creation and access to object_class();

Isolate* Isolate = Isolate::Current();
const Class& object_class = Class::Handle(isolate, isolate->...);
const Instance& current = Instance::Handle(isolate, ...);

Also instead of creating a new mark object every time should we just
create one per isolate upfront and use it here. Similar to how we have
Object::sentinel_
Object::transition_sentinel_
etc.

Maybe Object::sentinel_ itself could be your mark object ?

[koda, 2014/07/24 19:31:44]

First part done.

As for the marks, we do need more than one. I've added the following comment in
linked_hash_map.dart. Let me know if you still think it needs clarification (a
counter-based solution would be easier to explain, but needs overflow handling).

  // "Modificaton marks" are tokens used to detect concurrent modification.
  // Considering only modifications (M) and iterator creation (I) events, e.g.:
  //   M, M, M, I, I, M, I, M, M, I, I, I, M ...
  // a new mark is allocated at the start of each run of I's and cleared from
the map at
  // the start of each run of M's. Iterators' moveNext check whether the map's
  // mark was changed or cleared since the iterator was created.
  // TODO(koda): Consider a counter instead.

On 2014/07/23 22:43:07, siva wrote:

+    StorePointer(&raw_ptr()->cme_mark_, current.raw());
+  }
+  return raw_ptr()->cme_mark_;
+}
+
+
+RawLinkedHashMap* LinkedHashMap::New(Heap::Space space) {
+  ASSERT(Isolate::Current()->object_store()->linked_hash_map_class()
+         != Class::null());
+  static const intptr_t kInitialCapacity = 4;
+  const Array& data =
+      Array::Handle(HashTables::New<EnumIndexDefaultMap>(kInitialCapacity,
+                                                         space));
+  LinkedHashMap& result = LinkedHashMap::Handle();
+  {
+    RawObject* raw = Object::Allocate(LinkedHashMap::kClassId,
+                                      LinkedHashMap::InstanceSize(),
+                                      space);
+    NoGCScope no_gc;
+    result ^= raw;
+    result.SetData(data);
+    result.SetModified();
+  }
+  return result.raw();
+}
+
+
+const char* LinkedHashMap::ToCString() const {
+  // TODO(koda): Print key/value pairs.
+  return "_LinkedHashMap";
+}
+
+
+void LinkedHashMap::PrintJSONImpl(JSONStream* stream, bool ref) const {
+  // TODO(koda): Print key/value pairs.
+  Instance::PrintJSONImpl(stream, ref);
+}
+
+
 RawFloat32x4* Float32x4::New(float v0, float v1, float v2, float v3,
                              Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->float32x4_class() !=