Implement class hierarchy analysis in the VM.

runtime/vm/class_table.cc

Index: runtime/vm/class_table.cc
===================================================================
--- runtime/vm/class_table.cc	(revision 11002)
+++ runtime/vm/class_table.cc	(working copy)
@@ -96,4 +96,78 @@
   }
 }
 
+
+// Returns true if the given array of cids contains the given cid.
+static bool ContainsCid(ZoneGrowableArray<intptr_t>* cids, intptr_t cid) {

[srdjan, 2012/08/20 22:47:16]

COde below would look simpler if you change cids to be constant reference.

[regis, 2012/08/20 23:37:21]

Done.

+  for (intptr_t i = 0; i < cids->length(); i++) {
+    if ((*cids)[i] == cid) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
+// Recursively collect direct and indirect subclass ids of cls.
+static void CollectSubclassIds(ZoneGrowableArray<intptr_t>* cids,

[srdjan, 2012/08/20 22:47:16]

For later: maybe we should create a hash_set<intptr_t> if we decide to use STLs.

[regis, 2012/08/20 23:37:21]

OK

+                               const Class& cls) {
+  const GrowableObjectArray& cls_direct_subclasses =
+      GrowableObjectArray::Handle(cls.direct_subclasses());

[srdjan, 2012/08/20 22:47:16]

How about : if (cls_direct_subclasses.IsNull()) return;

[regis, 2012/08/20 23:37:21]

Done.

+  if (!cls_direct_subclasses.IsNull()) {
+    Class& direct_subclass = Class::Handle();
+    for (intptr_t i = 0; i < cls_direct_subclasses.Length(); i++) {
+      direct_subclass ^= cls_direct_subclasses.At(i);
+      intptr_t direct_subclass_id = direct_subclass.id();
+      if (!ContainsCid(cids, direct_subclass_id)) {
+        cids->Add(direct_subclass_id);
+        CollectSubclassIds(cids, direct_subclass);
+      }
+    }
+  }
+}
+
+
+ZoneGrowableArray<intptr_t>* ClassTable::GetSubclassIdsOf(intptr_t cid) const {
+  ASSERT(cid != kObjectCid);
+  ASSERT(IsValidIndex(cid));
+  const Class& cls = Class::Handle(At(cid));
+  ASSERT(!cls.IsNull());

[srdjan, 2012/08/20 22:47:16]

ASSERT(cls.IsInstance()) ?

[regis, 2012/08/20 23:37:21]

You can use IsInstance() on handles of objects. Here, we have a class. Once we
have kDartObjectCid, we can assert cid > kDartObjectCid.

+  ZoneGrowableArray<intptr_t>* ids = new ZoneGrowableArray<intptr_t>(2);

[srdjan, 2012/08/20 22:47:16]

Why 2? If you do not specify anything, the data does not get allocated until
really needed.

[regis, 2012/08/20 23:37:21]

Done.

+  CollectSubclassIds(ids, cls);
+  return ids;
+}
+
+
+ZoneGrowableArray<Function*>* ClassTable::GetNamedInstanceFunctionsOf(
+    ZoneGrowableArray<intptr_t>* cids, const String& function_name) const {
+  ASSERT(cids != NULL);
+  ASSERT(!function_name.IsNull());
+  ZoneGrowableArray<Function*>* functions = new ZoneGrowableArray<Function*>(2);

[srdjan, 2012/08/20 22:47:16]

ditto

[regis, 2012/08/20 23:37:21]

Done.

+  Class& cls = Class::Handle();
+  Function& cls_function = Function::Handle();
+  for (intptr_t i = 0; i < cids->length(); i++) {
+    const intptr_t cid = (*cids)[i];
+    ASSERT(cid != kObjectCid);

[srdjan, 2012/08/20 22:47:16]

Assert not correct

[regis, 2012/08/20 23:37:21]

We do not yet have kDartObjectCid. I've added a TODO and changed the ASSERT.

+    ASSERT(IsValidIndex(cid));
+    cls = At(cid);

[srdjan, 2012/08/20 22:47:16]

ASSERT(cls.IsInstance()).

[regis, 2012/08/20 23:37:21]

Done.

+    cls_function = cls.LookupDynamicFunction(function_name);
+    if (!cls_function.IsNull()) {
+      functions->Add(&Function::ZoneHandle(cls_function.raw()));
+    }
+  }
+  return functions;
+}
+
+
+ZoneGrowableArray<Function*>* ClassTable::GetOverridesOf(
+    const Function& function) const {
+  ASSERT(!function.IsNull());
+  ASSERT(function.IsDynamicFunction());
+  const Class& function_owner = Class::Handle(function.Owner());
+  const String& function_name = String::Handle(function.name());
+  ZoneGrowableArray<intptr_t>* cids = new ZoneGrowableArray<intptr_t>(4);

[srdjan, 2012/08/20 22:47:16]

ditto.

[regis, 2012/08/20 23:37:21]

Done.

+  CollectSubclassIds(cids, function_owner);
+  return GetNamedInstanceFunctionsOf(cids, function_name);
+}
+
 }  // namespace dart