Implement canonical name scheme in kernel.

runtime/vm/kernel_binary.cc

Index: runtime/vm/kernel_binary.cc
diff --git a/runtime/vm/kernel_binary.cc b/runtime/vm/kernel_binary.cc
index a90ad37055c455b3722b85d9aa78da14a193cf0e..39cf7ba819e9fc70af1f81856b47b32139478ad1 100644
--- a/runtime/vm/kernel_binary.cc
+++ b/runtime/vm/kernel_binary.cc
@@ -33,8 +33,7 @@ enum Tag {
   kNothing = 0,
   kSomething = 1,
 
-  kNormalClass = 2,
-  kMixinClass = 3,
+  kClass = 2,
 
   kField = 4,
   kConstructor = 5,
@@ -123,16 +122,6 @@ enum Tag {
   kSimpleInterfaceType = 96,
   kSimpleFunctionType = 97,
 
-  kNullReference = 99,
-  kNormalClassReference = 100,
-  kMixinClassReference = 101,
-
-  kLibraryFieldReference = 102,
-  kClassFieldReference = 103,
-  kClassConstructorReference = 104,
-  kLibraryProcedureReference = 105,
-  kClassProcedureReference = 106,
-
   kSpecializedTagHighBit = 0x80,  // 10000000
   kSpecializedTagMask = 0xF8,     // 11111000
   kSpecializedPayloadMask = 0x7,  // 00000111
@@ -321,8 +310,15 @@ class ReaderHelper {
   BlockStack<LabeledStatement>* labels() { return labels_; }
   void set_labels(BlockStack<LabeledStatement>* labels) { labels_ = labels; }
 
+  CanonicalName* GetCanonicalName(int index) { return canonical_names_[index]; }
+  void SetCanonicalName(int index, CanonicalName* name) {
+    canonical_names_[index] = name;
+  }
+  void SetCanonicalNameCount(int count) { canonical_names_.SetLength(count); }
+
  private:
   Program* program_;
+  MallocGrowableArray<Ref<CanonicalName> > canonical_names_;

[kustermann, 2017/02/01 13:00:55]

This will leak the memory forever! Similar to the strings, you have to make a
table in the [Program] object.

You should be able to use a List<CanonicalName> and then implement
CanonicalName::ReadFrom(Reader* reader) method.

The [Reader] can give you access to the [Program] object (and with that, to the
root canonical name, which is a Child<CanonicalName> of Program and is therefore
correctly freed)

[asgerf, 2017/02/02 12:30:28]

It is here to support linking in the VM by reading concatenated binaries. I did
not implement that yet, as it is not yet useful as long as we rely on
whole-program transformations, but Kevin is looking into it.

When reading from different binaries, the mapping from index to CanonicalName is
different in each binary, so I thought it best to consider it a mapping that
only exists in a certain scope.

The same problem will come up for strings, since each binary has a different
string table.

As for the memory leak: my intention was that CanonicalName destroys its
children, i.e. the Program destroys the root name, and the root name recursively
destroys everything else. I forgot to actually put the list of children on the
CanonicalName, though, but I think it should be fixed now (thanks for pointing
it out!).

[kustermann, 2017/02/03 11:48:20]

Normally I'd argue that we should do one thing at a time and be consistent (in
this case, treat strings/canonical-names the same). But leave it as it is now.

[asgerf, 2017/02/03 12:47:38]

Acknowledged.

   BlockStack<VariableDeclaration> scope_;
   BlockStack<TypeParameter> type_parameters_;
   BlockStack<SwitchCase> switch_cases_;
@@ -461,6 +457,14 @@ class Reader {
 
   ReaderHelper* helper() { return &builder_; }
 
+  CanonicalName* ReadCanonicalNameReference() {
+    int index = ReadUInt();
+    if (index == 0) return NULL;
+    CanonicalName* name = builder_.GetCanonicalName(index - 1);
+    ASSERT(name != NULL);
+    return name;
+  }
+
  private:
   const uint8_t* buffer_;
   int64_t size_;
@@ -644,8 +648,13 @@ Library* Library::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   int flags = reader->ReadFlags();
   ASSERT(flags == 0);  // external libraries not supported
+
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  ASSERT(canonical_name != NULL);
+  canonical_name->LinkTo(this);
+
   name_ = Reference::ReadStringFrom(reader);
-  import_uri_ = Reference::ReadStringFrom(reader);
+  import_uri_ = canonical_name->name();
   source_uri_index_ = reader->ReadUInt();
   reader->set_current_script_id(source_uri_index_);
 
@@ -653,13 +662,14 @@ Library* Library::ReadFrom(Reader* reader) {
   classes().EnsureInitialized(num_classes);
   for (int i = 0; i < num_classes; i++) {
     Tag tag = reader->ReadTag();
-    if (tag == kNormalClass) {
+    if (tag == kClass) {

[kustermann, 2017/02/01 13:00:55]

Theoretically we can get rid of this byte  in the binary format now that there
is only one kind of class.

[asgerf, 2017/02/02 12:30:28]

But the redundancy does make debugging a bit nicer, so I don't mind having it.

       NormalClass* klass = classes().GetOrCreate<NormalClass>(i, this);
       klass->ReadFrom(reader);
     } else {
-      ASSERT(tag == kMixinClass);
-      MixinClass* klass = classes().GetOrCreate<MixinClass>(i, this);
-      klass->ReadFrom(reader);
+      FATAL("Mixin application.");
+      // ASSERT(tag == kMixinClass);
+      // MixinClass* klass = classes().GetOrCreate<MixinClass>(i, this);
+      // klass->ReadFrom(reader);
     }

[kustermann, 2017/02/01 13:00:55]

Remove the else branch and ASSERT(tag == kClass);

[asgerf, 2017/02/02 12:30:28]

Done.

   }
 
@@ -672,6 +682,9 @@ Library* Library::ReadFrom(Reader* reader) {
 Class* Class::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
 
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  ASSERT(canonical_name != NULL);
+  canonical_name->LinkTo(this);
   position_ = reader->ReadPosition();
   is_abstract_ = reader->ReadBool();
   name_ = Reference::ReadStringFrom(reader);
@@ -692,6 +705,7 @@ NormalClass* NormalClass::ReadFrom(Reader* reader) {
   DartType* type = reader->ReadOptional<DartType>();
 
   super_class_ = InterfaceType::Cast(type);
+  reader->ReadOptional<DartType>();  // Mixed-in type is unused.
   implemented_classes_.ReadFromStatic<DowncastReader<DartType, InterfaceType> >(
       reader);
   fields_.ReadFrom<Field>(reader, this);
@@ -717,82 +731,35 @@ MixinClass* MixinClass::ReadFrom(Reader* reader) {
 }
 
 
-Member* Reference::ReadMemberFrom(Reader* reader, bool allow_null) {
+CanonicalName* Reference::ReadMemberFrom(Reader* reader, bool allow_null) {
   TRACE_READ_OFFSET();
 
-  Program* program = reader->helper()->program();
-  Tag tag = reader->ReadTag();
-  switch (tag) {
-    case kLibraryFieldReference: {
-      int library_idx = reader->ReadUInt();
-      int field_idx = reader->ReadUInt();
-      Library* library = program->libraries().GetOrCreate<Library>(library_idx);
-      return library->fields().GetOrCreate<Field>(field_idx, library);
-    }
-    case kLibraryProcedureReference: {
-      int library_idx = reader->ReadUInt();
-      int procedure_idx = reader->ReadUInt();
-      Library* library = program->libraries().GetOrCreate<Library>(library_idx);
-      return library->procedures().GetOrCreate<Procedure>(procedure_idx,
-                                                          library);
-    }
-    case kClassFieldReference:
-    case kClassConstructorReference:
-    case kClassProcedureReference: {
-      Class* klass = Reference::ReadClassFrom(reader);
-      if (tag == kClassFieldReference) {
-        int field_idx = reader->ReadUInt();
-        return klass->fields().GetOrCreate<Field>(field_idx, klass);
-      } else if (tag == kClassConstructorReference) {
-        int constructor_idx = reader->ReadUInt();
-        return klass->constructors().GetOrCreate<Constructor>(constructor_idx,
-                                                              klass);
-      } else {
-        ASSERT(tag == kClassProcedureReference);
-        int procedure_idx = reader->ReadUInt();
-        return klass->procedures().GetOrCreate<Procedure>(procedure_idx, klass);
-      }
-    }
-    case kNullReference:
-      if (allow_null) {
-        return NULL;
-      } else {
-        FATAL("Expected a valid member reference, but got `null`");
-      }
-    default:
-      UNREACHABLE();
-      break;
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  if (canonical_name == NULL && !allow_null) {
+    FATAL("Expected a valid member reference, but got `null`");
   }
 
-  UNREACHABLE();
-  return NULL;
+  if (canonical_name != NULL) {
+    canonical_name->set_referenced(true);
+  }
+
+  return canonical_name;
 }
 
 
-Class* Reference::ReadClassFrom(Reader* reader, bool allow_null) {
+CanonicalName* Reference::ReadClassFrom(Reader* reader, bool allow_null) {
   TRACE_READ_OFFSET();
-  Program* program = reader->helper()->program();
 
-  Tag klass_member_tag = reader->ReadTag();
-  if (klass_member_tag == kNullReference) {
-    if (allow_null) {
-      return NULL;
-    } else {
-      FATAL("Expected a valid class reference but got `null`.");
-    }
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  if (canonical_name == NULL && !allow_null) {
+    FATAL("Expected a valid class reference, but got `null`");
   }
-  int library_idx = reader->ReadUInt();
-  int class_idx = reader->ReadUInt();
 
-  Library* library = program->libraries().GetOrCreate<Library>(library_idx);
-  Class* klass;
-  if (klass_member_tag == kNormalClassReference) {
-    klass = library->classes().GetOrCreate<NormalClass>(class_idx, library);
-  } else {
-    ASSERT(klass_member_tag == kMixinClassReference);
-    klass = library->classes().GetOrCreate<MixinClass>(class_idx, library);
+  if (canonical_name != NULL) {
+    canonical_name->set_referenced(true);
   }
-  return klass;
+
+  return canonical_name;
 }
 
 
@@ -807,6 +774,10 @@ Field* Field::ReadFrom(Reader* reader) {
   Tag tag = reader->ReadTag();
   ASSERT(tag == kField);
 
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  ASSERT(canonical_name != NULL);
+  canonical_name->LinkTo(this);

[kustermann, 2017/02/01 13:00:55]

You could add another method to Reader:

CanonicalName* ReadCanonicalNameReference();
CanonicalName* ReadDefiningCanonicalNameReference(LinkedNode* node_to_link) {
  CanonicalName* name = ReadCanonicalReference();
  ASSERT(name != NULL);
  name->LinkTo(node_to_link);
  return name;
}

and get rid of the ASSERT/LinkTo on all call sites.

[asgerf, 2017/02/02 12:30:28]

Done.

+
   position_ = reader->ReadPosition();
   end_position_ = reader->ReadPosition();
   flags_ = reader->ReadFlags();
@@ -826,6 +797,10 @@ Constructor* Constructor::ReadFrom(Reader* reader) {
   Tag tag = reader->ReadTag();
   ASSERT(tag == kConstructor);
 
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  ASSERT(canonical_name != NULL);
+  canonical_name->LinkTo(this);
+
   VariableScope<ReaderHelper> parameters(reader->helper());
   position_ = reader->ReadPosition();
   end_position_ = reader->ReadPosition();
@@ -843,6 +818,10 @@ Procedure* Procedure::ReadFrom(Reader* reader) {
   Tag tag = reader->ReadTag();
   ASSERT(tag == kProcedure);
 
+  CanonicalName* canonical_name = reader->ReadCanonicalNameReference();
+  ASSERT(canonical_name != NULL);
+  canonical_name->LinkTo(this);
+
   VariableScope<ReaderHelper> parameters(reader->helper());
   position_ = reader->ReadPosition();
   end_position_ = reader->ReadPosition();
@@ -887,7 +866,7 @@ InvalidInitializer* InvalidInitializer::ReadFromImpl(Reader* reader) {
 FieldInitializer* FieldInitializer::ReadFromImpl(Reader* reader) {
   TRACE_READ_OFFSET();
   FieldInitializer* initializer = new FieldInitializer();
-  initializer->field_ = Field::Cast(Reference::ReadMemberFrom(reader));
+  initializer->field_reference_ = Reference::ReadMemberFrom(reader, false);
   initializer->value_ = Expression::ReadFrom(reader);
   return initializer;
 }
@@ -896,7 +875,7 @@ FieldInitializer* FieldInitializer::ReadFromImpl(Reader* reader) {
 SuperInitializer* SuperInitializer::ReadFromImpl(Reader* reader) {
   TRACE_READ_OFFSET();
   SuperInitializer* init = new SuperInitializer();
-  init->target_ = Constructor::Cast(Reference::ReadMemberFrom(reader));
+  init->target_reference_ = Reference::ReadMemberFrom(reader, false);
   init->arguments_ = Arguments::ReadFrom(reader);
   return init;
 }
@@ -905,7 +884,7 @@ SuperInitializer* SuperInitializer::ReadFromImpl(Reader* reader) {
 RedirectingInitializer* RedirectingInitializer::ReadFromImpl(Reader* reader) {
   TRACE_READ_OFFSET();
   RedirectingInitializer* init = new RedirectingInitializer();
-  init->target_ = Constructor::Cast(Reference::ReadMemberFrom(reader));
+  init->target_reference_ = Reference::ReadMemberFrom(reader, false);

[kustermann, 2017/02/01 13:00:55]

If you explicitly pass 'false' everywhere, then get rid of the default value in
the header file.

[asgerf, 2017/02/02 12:30:28]

No, it was just here. I've removed the redundant argument.

   init->arguments_ = Arguments::ReadFrom(reader);
   return init;
 }
@@ -1070,7 +1049,7 @@ PropertyGet* PropertyGet::ReadFrom(Reader* reader) {
   get->position_ = reader->ReadPosition();
   get->receiver_ = Expression::ReadFrom(reader);
   get->name_ = Name::ReadFrom(reader);
-  get->interfaceTarget_ = Reference::ReadMemberFrom(reader, true);
+  get->interface_target_reference_ = Reference::ReadMemberFrom(reader, true);
   return get;
 }
 
@@ -1082,7 +1061,7 @@ PropertySet* PropertySet::ReadFrom(Reader* reader) {
   set->receiver_ = Expression::ReadFrom(reader);
   set->name_ = Name::ReadFrom(reader);
   set->value_ = Expression::ReadFrom(reader);
-  set->interfaceTarget_ = Reference::ReadMemberFrom(reader, true);
+  set->interface_target_reference_ = Reference::ReadMemberFrom(reader, true);
   return set;
 }
 
@@ -1091,7 +1070,7 @@ DirectPropertyGet* DirectPropertyGet::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   DirectPropertyGet* get = new DirectPropertyGet();
   get->receiver_ = Expression::ReadFrom(reader);
-  get->target_ = Reference::ReadMemberFrom(reader);
+  get->target_reference_ = Reference::ReadMemberFrom(reader);
   return get;
 }
 
@@ -1100,7 +1079,7 @@ DirectPropertySet* DirectPropertySet::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   DirectPropertySet* set = new DirectPropertySet();
   set->receiver_ = Expression::ReadFrom(reader);
-  set->target_ = Reference::ReadMemberFrom(reader);
+  set->target_reference_ = Reference::ReadMemberFrom(reader);
   set->value_ = Expression::ReadFrom(reader);
   return set;
 }
@@ -1110,7 +1089,7 @@ StaticGet* StaticGet::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   StaticGet* get = new StaticGet();
   get->position_ = reader->ReadPosition();
-  get->target_ = Reference::ReadMemberFrom(reader);
+  get->target_reference_ = Reference::ReadMemberFrom(reader);
   return get;
 }
 
@@ -1118,7 +1097,7 @@ StaticGet* StaticGet::ReadFrom(Reader* reader) {
 StaticSet* StaticSet::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   StaticSet* set = new StaticSet();
-  set->target_ = Reference::ReadMemberFrom(reader);
+  set->target_reference_ = Reference::ReadMemberFrom(reader);
   set->expression_ = Expression::ReadFrom(reader);
   return set;
 }
@@ -1149,7 +1128,8 @@ MethodInvocation* MethodInvocation::ReadFrom(Reader* reader) {
   invocation->receiver_ = Expression::ReadFrom(reader);
   invocation->name_ = Name::ReadFrom(reader);
   invocation->arguments_ = Arguments::ReadFrom(reader);
-  invocation->interfaceTarget_ = Reference::ReadMemberFrom(reader, true);
+  invocation->interface_target_reference_ =
+      Reference::ReadMemberFrom(reader, true);
   return invocation;
 }
 
@@ -1158,7 +1138,7 @@ DirectMethodInvocation* DirectMethodInvocation::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
   DirectMethodInvocation* invocation = new DirectMethodInvocation();
   invocation->receiver_ = Expression::ReadFrom(reader);
-  invocation->target_ = Procedure::Cast(Reference::ReadMemberFrom(reader));
+  invocation->target_reference_ = Reference::ReadMemberFrom(reader);
   invocation->arguments_ = Arguments::ReadFrom(reader);
   return invocation;
 }
@@ -1169,7 +1149,7 @@ StaticInvocation* StaticInvocation::ReadFrom(Reader* reader, bool is_const) {
   StaticInvocation* invocation = new StaticInvocation();
   invocation->is_const_ = is_const;
   invocation->position_ = reader->ReadPosition();
-  invocation->procedure_ = Procedure::Cast(Reference::ReadMemberFrom(reader));
+  invocation->procedure_reference_ = Reference::ReadMemberFrom(reader);
   invocation->arguments_ = Arguments::ReadFrom(reader);
   return invocation;
 }
@@ -1181,7 +1161,7 @@ ConstructorInvocation* ConstructorInvocation::ReadFrom(Reader* reader,
   ConstructorInvocation* invocation = new ConstructorInvocation();
   invocation->is_const_ = is_const;
   invocation->position_ = reader->ReadPosition();
-  invocation->target_ = Constructor::Cast(Reference::ReadMemberFrom(reader));
+  invocation->target_reference_ = Reference::ReadMemberFrom(reader);
   invocation->arguments_ = Arguments::ReadFrom(reader);
   return invocation;
 }
@@ -1711,11 +1691,8 @@ FunctionDeclaration* FunctionDeclaration::ReadFrom(Reader* reader) {
 Name* Name::ReadFrom(Reader* reader) {
   String* string = Reference::ReadStringFrom(reader);
   if (string->size() >= 1 && string->buffer()[0] == '_') {
-    int lib_index = reader->ReadUInt();
-    Library* library =
-        reader->helper()->program()->libraries().GetOrCreate<Library>(
-            lib_index);
-    return new Name(string, library);
+    CanonicalName* library_reference = reader->ReadCanonicalNameReference();
+    return new Name(string, library_reference);
   } else {
     return new Name(string, NULL);
   }
@@ -1724,7 +1701,7 @@ Name* Name::ReadFrom(Reader* reader) {
 
 InferredValue* InferredValue::ReadFrom(Reader* reader) {
   InferredValue* type = new InferredValue();
-  type->klass_ = Reference::ReadClassFrom(reader, true);
+  type->klass_reference_ = Reference::ReadClassFrom(reader, true);
   type->kind_ = static_cast<BaseClassKind>(reader->ReadByte());
   type->value_bits_ = reader->ReadByte();
   return type;
@@ -1779,8 +1756,8 @@ VoidType* VoidType::ReadFrom(Reader* reader) {
 
 InterfaceType* InterfaceType::ReadFrom(Reader* reader) {
   TRACE_READ_OFFSET();
-  Class* klass = Reference::ReadClassFrom(reader);
-  InterfaceType* type = new InterfaceType(klass);
+  CanonicalName* klass_name = Reference::ReadClassFrom(reader);
+  InterfaceType* type = new InterfaceType(klass_name);
   type->type_arguments().ReadFromStatic<DartType>(reader);
   return type;
 }
@@ -1789,8 +1766,8 @@ InterfaceType* InterfaceType::ReadFrom(Reader* reader) {
 InterfaceType* InterfaceType::ReadFrom(Reader* reader,
                                        bool _without_type_arguments_) {
   TRACE_READ_OFFSET();
-  Class* klass = Reference::ReadClassFrom(reader);
-  InterfaceType* type = new InterfaceType(klass);
+  CanonicalName* klass_name = Reference::ReadClassFrom(reader);
+  InterfaceType* type = new InterfaceType(klass_name);
   ASSERT(_without_type_arguments_);
   return type;
 }
@@ -1835,19 +1812,44 @@ Program* Program::ReadFrom(Reader* reader) {
   if (magic != kMagicProgramFile) FATAL("Invalid magic identifier");
 
   Program* program = new Program();
+  program->canonical_name_root_ = CanonicalName::NewRoot();
   reader->helper()->set_program(program);
 
   program->string_table_.ReadFrom(reader);
   program->source_uri_table_.ReadFrom(reader);
   program->source_table_.ReadFrom(reader);
 
+  int canonical_names = reader->ReadUInt();
+  reader->helper()->SetCanonicalNameCount(canonical_names);
+  for (int i = 0; i < canonical_names; ++i) {
+    int biased_parent_index = reader->ReadUInt();
+    CanonicalName* parent;
+    if (biased_parent_index != 0) {
+      parent = reader->helper()->GetCanonicalName(biased_parent_index - 1);
+    } else {
+      parent = program->canonical_name_root();
+    }
+    ASSERT(parent != NULL);
+    int name_index = reader->ReadUInt();
+    String* name = program->string_table().strings()[name_index];
+    CanonicalName* canonical_name = parent->AddChild(name);
+    reader->helper()->SetCanonicalName(i, canonical_name);
+  }
+

[kustermann, 2017/02/01 13:00:55]

As mentioned above, this should should be implemented differently, more like:

program->canonical_names_.ReadFrom(reader);

with  

class Program {
List<CanonicalName> canonical_names_;
}

and 

CanonicalName::ReadFrom

[asgerf, 2017/02/02 12:30:28]

From previous answer: it won't work for linking in the VM.

   int libraries = reader->ReadUInt();
   program->libraries().EnsureInitialized(libraries);
   for (int i = 0; i < libraries; i++) {
     program->libraries().GetOrCreate<Library>(i)->ReadFrom(reader);
   }
 
-  program->main_method_ = Procedure::Cast(Reference::ReadMemberFrom(reader));
+  program->main_method_reference_ = Reference::ReadMemberFrom(reader);
+
+  for (int i = 0; i < canonical_names; ++i) {

[kustermann, 2017/02/01 13:00:55]

Can we guarantee this invariant in the kernel verifier and move this  into a 

#ifdef DEBUG

#endif

block?

[asgerf, 2017/02/02 12:30:28]

Done.

+    CanonicalName* name = reader->helper()->GetCanonicalName(i);
+    if (name->is_referenced() && name->definition() == NULL) {
+      FATAL("Missing definition for canonical name");
+    }
+  }
 
   return program;
 }