Implement canonical name scheme in kernel.

pkg/kernel/lib/binary/ast_to_binary.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 library kernel.ast_to_binary;
 
 import '../ast.dart';
 import '../import_table.dart';
 import 'tag.dart';
 import 'dart:convert';
 import 'dart:typed_data';
 import 'dart:collection';
 
 /// Writes to a binary file.
 ///
 /// A [BinaryPrinter] can be used to write one file and must then be
 /// discarded.
 class BinaryPrinter extends Visitor {
-  ImportTable _importTable;
-
   VariableIndexer _variableIndexer;
   LabelIndexer _labelIndexer;
   SwitchCaseIndexer _switchCaseIndexer;
   final TypeParameterIndexer _typeParameterIndexer = new TypeParameterIndexer();
-  final GlobalIndexer _globalIndexer;
   final StringIndexer _stringIndexer = new StringIndexer();
   final StringIndexer _sourceUriIndexer = new StringIndexer();
   Map<DeferredImport, int> _deferredImportIndexer = <DeferredImport, int>{};
 
   final BufferedSink _sink;
 
   /// Create a printer that writes to the given [sink].
   ///
   /// The BinaryPrinter will use its own buffer, so the [sink] does not need
   /// one.
   ///
   /// If multiple binaries are to be written based on the same IR, a shared
   /// [globalIndexer] may be passed in to avoid rebuilding the same indices
   /// in every printer.
-  BinaryPrinter(Sink<List<int>> sink, {GlobalIndexer globalIndexer})
-      : _sink = new BufferedSink(sink),
-        _globalIndexer = globalIndexer ?? new GlobalIndexer();
+  BinaryPrinter(Sink<List<int>> sink) : _sink = new BufferedSink(sink);
 
   void _flush() {
     _sink.flushAndDestroy();
   }
 
   void writeByte(int byte) {
     _sink.addByte(byte);
   }
 
   void writeBytes(List<int> bytes) {
@@ skipping 74 matching lines @@
     if (node == null) {
       writeByte(Tag.Nothing);
     } else {
       writeByte(Tag.Something);
       writeClassReference(node.baseClass, allowNull: true);
       writeByte(node.baseClassKind.index);
       writeByte(node.valueBits);
     }
   }
 
+  void writeLinkTable(Program program) {
+    List<CanonicalName> list = <CanonicalName>[];
+    void visitCanonicalName(CanonicalName node) {
+      node.index = list.length;
+      list.add(node);
+      node.children.forEach(visitCanonicalName);
+    }
+
+    for (var library in program.libraries) {
+      visitCanonicalName(library.canonicalName);
+    }
+    writeList(list, writeCanonicalNameEntry);
+  }
+
+  void writeCanonicalNameEntry(CanonicalName node) {
+    var parent = node.parent;
+    if (parent.isRoot) {
+      writeByte(0);
+    } else {
+      writeUInt30(parent.index + 1);
+    }
+    writeStringReference(node.name);
+  }
+
   void writeProgramFile(Program program) {
+    program.computeCanonicalNames();
     writeMagicWord(Tag.ProgramFile);
-    _importTable = new ProgramImportTable(program);
-    _stringIndexer.build(program);
+    _stringIndexer.scanProgram(program);
     writeStringTable(_stringIndexer);
     writeUriToSource(program);
+    writeLinkTable(program);
     writeList(program.libraries, writeNode);
     writeMemberReference(program.mainMethod, allowNull: true);
     _flush();
   }
 
   void writeUriToSource(Program program) {
     program.uriToSource.keys.forEach((uri) {
       _sourceUriIndexer.put(uri);
     });
     writeStringTable(_sourceUriIndexer);
     for (int i = 0; i < _sourceUriIndexer.entries.length; i++) {
       String uri = _sourceUriIndexer.entries[i].value;
       Source source = program.uriToSource[uri] ?? new Source([], '');
       String sourceCode = source.source;
       writeStringTableEntry(sourceCode);
       List<int> lineStarts = source.lineStarts;
       writeUInt30(lineStarts.length);
       int previousLineStart = 0;
       lineStarts.forEach((lineStart) {
         writeUInt30(lineStart - previousLineStart);
         previousLineStart = lineStart;
       });
     }
   }
 
-  void writeLibraryImportTable(LibraryImportTable imports) {
-    writeList(imports.importPaths, writeStringReference);
-  }
-
-  void writeLibraryReference(Library node) {
-    int index = _importTable.getImportIndex(node);
-    if (index == -1) {
-      throw 'Missing import for library: ${node.importUri}';
-    }
-    writeUInt30(index);
-  }
-
   void writeDeferredImportReference(DeferredImport node) {
     int index = _deferredImportIndexer[node];
     if (index == null) {
       throw 'Reference to deferred import $node out of scope';
     }
     writeUInt30(index);
   }
 
-  void writeClassIndex(Class node) {
-    writeUInt30(_globalIndexer[node]);
-  }
-
-  void writeClassReference(Class node, {bool allowNull: false}) {
-    if (node == null) {
-      if (allowNull) {
-        writeByte(Tag.NullReference);
-      } else {
-        throw 'Expected a class reference to be valid but was `null`.';
+  void writeReference(Reference reference) {
+    if (reference == null) {
+      writeByte(0);
+    } else {
+      CanonicalName name = reference.canonicalName;
+      if (name == null) {
+        throw 'Missing canonical name for $reference';
       }
-    } else {
-      node.acceptReference(this);
+      writeUInt30(name.index + 1);
     }
   }
 
-  void writeMemberReference(Member node, {bool allowNull: false}) {
-    if (node == null) {
-      if (allowNull) {
-        writeByte(Tag.NullReference);
-      } else {
-        throw 'Expected a member reference to be valid but was `null`.';
-      }
+  void writeCanonicalNameReference(CanonicalName name) {
+    if (name == null) {
+      writeByte(0);
     } else {
-      node.acceptReference(this);
+      writeUInt30(name.index + 1);
     }
   }
 
+  void writeLibraryReference(Library node) {
+    writeCanonicalNameReference(node.canonicalName);
+  }
+
   writeOffset(TreeNode node, int offset) {
     // TODO(jensj): Delta-encoding.
     // File offset ranges from -1 and up,
     // but is here saved as unsigned (thus the +1)
     writeUInt30(offset + 1);
   }
 
-  void visitClassReference(Class node) {
-    var library = node.enclosingLibrary;
-    writeByte(node.isMixinApplication
-        ? Tag.MixinClassReference
-        : Tag.NormalClassReference);
-    writeLibraryReference(library);
-    writeClassIndex(node);
+  void writeClassReference(Class class_, {bool allowNull: false}) {
+    if (class_ == null && !allowNull) {
+      throw 'Expected a class reference to be valid but was `null`.';
+    }
+    writeCanonicalNameReference(getCanonicalNameOfClass(class_));
   }
 
-  void visitFieldReference(Field node) {
-    if (node.enclosingClass != null) {
-      writeByte(Tag.ClassFieldReference);
-      Class classNode = node.enclosingClass;
-      writeClassReference(classNode);
-      writeUInt30(_globalIndexer[node]);
-    } else {
-      writeByte(Tag.LibraryFieldReference);
-      writeLibraryReference(node.enclosingLibrary);
-      writeUInt30(_globalIndexer[node]);
+  void writeMemberReference(Member member, {bool allowNull: false}) {
+    if (member == null && !allowNull) {
+      throw 'Expected a member reference to be valid but was `null`.';
     }
-  }
-
-  void visitConstructorReference(Constructor node) {
-    writeByte(Tag.ClassConstructorReference);
-    writeClassReference(node.enclosingClass);
-    writeUInt30(_globalIndexer[node]);
-  }
-
-  void visitProcedureReference(Procedure node) {
-    if (node.enclosingClass != null) {
-      writeByte(Tag.ClassProcedureReference);
-      Class classNode = node.enclosingClass;
-      writeClassReference(classNode);
-      writeUInt30(_globalIndexer[node]);
-    } else {
-      writeByte(Tag.LibraryProcedureReference);
-      writeLibraryReference(node.enclosingLibrary);
-      writeUInt30(_globalIndexer[node]);
-    }
+    writeCanonicalNameReference(getCanonicalNameOfMember(member));
   }
 
   void writeName(Name node) {
     writeStringReference(node.name);
     // TODO: Consider a more compressed format for private names within the
     // enclosing library.
     if (node.isPrivate) {
       writeLibraryReference(node.library);
     }
   }
 
   bool insideExternalLibrary = false;
 
   visitLibrary(Library node) {
     insideExternalLibrary = node.isExternal;
     writeByte(insideExternalLibrary ? 1 : 0);
+    writeCanonicalNameReference(getCanonicalNameOfLibrary(node));
     writeStringReference(node.name ?? '');
-    writeStringReference('${node.importUri}');
     // TODO(jensj): We save (almost) the same URI twice.
     writeUriReference(node.fileUri ?? '');
     writeDeferredImports(node);
     writeNodeList(node.classes);
     writeNodeList(node.fields);
     writeNodeList(node.procedures);
   }
 
   void writeDeferredImports(Library library) {
     _deferredImportIndexer = library.deferredImports.isEmpty
@@ skipping 22 matching lines @@
   }
 
   int _encodeClassFlags(bool isAbstract, ClassLevel level) {
     int abstactFlag = isAbstract ? 1 : 0;
     int levelFlags = (level.index - 1) << 1;
     return abstactFlag | levelFlags;
   }
 
   visitClass(Class node) {
     int flags = _encodeClassFlags(node.isAbstract, node.level);
-    if (node.isMixinApplication) {
-      writeByte(Tag.MixinClass);
-      writeOffset(node, node.fileOffset);
-      writeByte(flags);
-      writeStringReference(node.name ?? '');
-      writeUriReference(node.fileUri ?? '');
-      writeAnnotationList(node.annotations);
-      _typeParameterIndexer.enter(node.typeParameters);
-      writeNodeList(node.typeParameters);
-      writeNode(node.supertype);
-      writeNode(node.mixedInType);
-      writeNodeList(node.implementedTypes);
-      writeNodeList(node.constructors);
-      _typeParameterIndexer.exit(node.typeParameters);
-    } else {
-      writeByte(Tag.NormalClass);
-      writeOffset(node, node.fileOffset);
-      writeByte(flags);
-      writeStringReference(node.name ?? '');
-      writeUriReference(node.fileUri ?? '');
-      writeAnnotationList(node.annotations);
-      _typeParameterIndexer.enter(node.typeParameters);
-      writeNodeList(node.typeParameters);
-      writeOptionalNode(node.supertype);
-      writeNodeList(node.implementedTypes);
-      writeNodeList(node.fields);
-      writeNodeList(node.constructors);
-      writeNodeList(node.procedures);
-      _typeParameterIndexer.exit(node.typeParameters);
+    if (node.canonicalName == null) {
+      throw 'Missing canonical name for $node';
     }
+    writeByte(Tag.Class);
+    writeCanonicalNameReference(getCanonicalNameOfClass(node));
+    writeOffset(node, node.fileOffset);
+    writeByte(flags);
+    writeStringReference(node.name ?? '');
+    writeUriReference(node.fileUri ?? '');
+    writeAnnotationList(node.annotations);
+    _typeParameterIndexer.enter(node.typeParameters);
+    writeNodeList(node.typeParameters);
+    writeOptionalNode(node.supertype);
+    writeOptionalNode(node.mixedInType);
+    writeNodeList(node.implementedTypes);
+    writeNodeList(node.fields);
+    writeNodeList(node.constructors);
+    writeNodeList(node.procedures);
+    _typeParameterIndexer.exit(node.typeParameters);
   }
 
   static final Name _emptyName = new Name('');
 
   visitConstructor(Constructor node) {
+    if (node.canonicalName == null) {
+      throw 'Missing canonical name for $node';
+    }
     _variableIndexer = new VariableIndexer();
     writeByte(Tag.Constructor);
+    writeCanonicalNameReference(getCanonicalNameOfMember(node));
     writeOffset(node, node.fileOffset);
     writeOffset(node, node.fileEndOffset);
     writeByte(node.flags);
     writeName(node.name ?? _emptyName);
     writeAnnotationList(node.annotations);
     assert(node.function.typeParameters.isEmpty);
     writeNode(node.function);
     // Parameters are in scope in the initializers.
     _variableIndexer.restoreScope(node.function.positionalParameters.length +
         node.function.namedParameters.length);
     writeNodeList(node.initializers);
     _variableIndexer = null;
   }
 
   visitProcedure(Procedure node) {
+    if (node.canonicalName == null) {
+      throw 'Missing canonical name for $node';
+    }
     _variableIndexer = new VariableIndexer();
     writeByte(Tag.Procedure);
+    writeCanonicalNameReference(getCanonicalNameOfMember(node));
     writeOffset(node, node.fileOffset);
     writeOffset(node, node.fileEndOffset);
     writeByte(node.kind.index);
     writeByte(node.flags);
     writeName(node.name ?? '');
     writeUriReference(node.fileUri ?? '');
     writeAnnotationList(node.annotations);
     writeOptionalNode(node.function);
     _variableIndexer = null;
   }
 
   visitField(Field node) {
+    if (node.canonicalName == null) {
+      throw 'Missing canonical name for $node';
+    }
     _variableIndexer = new VariableIndexer();
     writeByte(Tag.Field);
+    writeCanonicalNameReference(getCanonicalNameOfMember(node));
     writeOffset(node, node.fileOffset);
     writeOffset(node, node.fileEndOffset);
     writeByte(node.flags);
-    writeName(node.name ?? '');
+    writeName(node.name);
     writeUriReference(node.fileUri ?? '');
     writeAnnotationList(node.annotations);
     writeNode(node.type);
     writeOptionalInferredValue(node.inferredValue);
     writeOptionalNode(node.initializer);
     _variableIndexer = null;
   }
 
   visitInvalidInitializer(InvalidInitializer node) {
     writeByte(Tag.InvalidInitializer);
   }
 
   visitFieldInitializer(FieldInitializer node) {
     writeByte(Tag.FieldInitializer);
-    writeMemberReference(node.field);
+    writeReference(node.fieldReference);
     writeNode(node.value);
   }
 
   visitSuperInitializer(SuperInitializer node) {
     writeByte(Tag.SuperInitializer);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.arguments);
   }
 
   visitRedirectingInitializer(RedirectingInitializer node) {
     writeByte(Tag.RedirectingInitializer);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.arguments);
   }
 
   visitLocalInitializer(LocalInitializer node) {
     writeByte(Tag.LocalInitializer);
     writeVariableDeclaration(node.variable);
   }
 
   visitFunctionNode(FunctionNode node) {
     assert(_variableIndexer != null);
@@ skipping 54 matching lines @@
       writeUInt30(_variableIndexer[node.variable]);
       writeNode(node.value);
     }
   }
 
   visitPropertyGet(PropertyGet node) {
     writeByte(Tag.PropertyGet);
     writeOffset(node, node.fileOffset);
     writeNode(node.receiver);
     writeName(node.name);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitPropertySet(PropertySet node) {
     writeByte(Tag.PropertySet);
     writeOffset(node, node.fileOffset);
     writeNode(node.receiver);
     writeName(node.name);
     writeNode(node.value);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitSuperPropertyGet(SuperPropertyGet node) {
     writeByte(Tag.SuperPropertyGet);
     writeName(node.name);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitSuperPropertySet(SuperPropertySet node) {
     writeByte(Tag.SuperPropertySet);
     writeName(node.name);
     writeNode(node.value);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitDirectPropertyGet(DirectPropertyGet node) {
     writeByte(Tag.DirectPropertyGet);
     writeNode(node.receiver);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
   }
 
   visitDirectPropertySet(DirectPropertySet node) {
     writeByte(Tag.DirectPropertySet);
     writeNode(node.receiver);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.value);
   }
 
   visitStaticGet(StaticGet node) {
     writeByte(Tag.StaticGet);
     writeOffset(node, node.fileOffset);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
   }
 
   visitStaticSet(StaticSet node) {
     writeByte(Tag.StaticSet);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.value);
   }
 
   visitMethodInvocation(MethodInvocation node) {
     writeByte(Tag.MethodInvocation);
     writeOffset(node, node.fileOffset);
     writeNode(node.receiver);
     writeName(node.name);
     writeNode(node.arguments);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitSuperMethodInvocation(SuperMethodInvocation node) {
     writeByte(Tag.SuperMethodInvocation);
     writeOffset(node, node.fileOffset);
     writeName(node.name);
     writeNode(node.arguments);
-    writeMemberReference(node.interfaceTarget, allowNull: true);
+    writeReference(node.interfaceTargetReference);
   }
 
   visitDirectMethodInvocation(DirectMethodInvocation node) {
     writeByte(Tag.DirectMethodInvocation);
     writeNode(node.receiver);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.arguments);
   }
 
   visitStaticInvocation(StaticInvocation node) {
     writeByte(node.isConst ? Tag.ConstStaticInvocation : Tag.StaticInvocation);
     writeOffset(node, node.fileOffset);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.arguments);
   }
 
   visitConstructorInvocation(ConstructorInvocation node) {
     writeByte(node.isConst
         ? Tag.ConstConstructorInvocation
         : Tag.ConstructorInvocation);
     writeOffset(node, node.fileOffset);
-    writeMemberReference(node.target);
+    writeReference(node.targetReference);
     writeNode(node.arguments);
   }
 
   visitArguments(Arguments node) {
     writeNodeList(node.types);
     writeNodeList(node.positional);
     writeNodeList(node.named);
   }
 
   visitNamedExpression(NamedExpression node) {
@@ skipping 349 matching lines @@
     writeByte(Tag.DynamicType);
   }
 
   visitVoidType(VoidType node) {
     writeByte(Tag.VoidType);
   }
 
   visitInterfaceType(InterfaceType node) {
     if (node.typeArguments.isEmpty) {
       writeByte(Tag.SimpleInterfaceType);
-      writeClassReference(node.classNode);
+      writeReference(node.className);
     } else {
       writeByte(Tag.InterfaceType);
-      writeClassReference(node.classNode);
+      writeReference(node.className);
       writeNodeList(node.typeArguments);
     }
   }
 
   visitSupertype(Supertype node) {
     if (node.typeArguments.isEmpty) {
       writeByte(Tag.SimpleInterfaceType);
-      writeClassReference(node.classNode);
+      writeReference(node.className);
     } else {
       writeByte(Tag.InterfaceType);
-      writeClassReference(node.classNode);
+      writeReference(node.className);
       writeNodeList(node.typeArguments);
     }
   }
 
   visitFunctionType(FunctionType node) {
     if (node.requiredParameterCount == node.positionalParameters.length &&
         node.typeParameters.isEmpty &&
         node.namedParameters.isEmpty) {
       writeByte(Tag.SimpleFunctionType);
       writeNodeList(node.positionalParameters);
@@ skipping 118 matching lines @@
 class StringIndexer extends RecursiveVisitor<Null> {
   final List<StringTableEntry> entries = <StringTableEntry>[];
   final LinkedHashMap<String, int> index = new LinkedHashMap<String, int>();
 
   StringIndexer() {
     put('');
   }
 
   int get numberOfStrings => index.length;
 
-  void build(Node node) {
+  void scanProgram(Node node) {
     node.accept(this);
     entries.sort();
     for (int i = 0; i < entries.length; ++i) {
       index[entries[i].value] = i;
     }
   }
 
+  void visitCanonicalName(CanonicalName name) {
+    put(name.name);
+    name.children.forEach(visitCanonicalName);
+  }
+
   void put(String string) {
     int i = index.putIfAbsent(string, () {
       entries.add(new StringTableEntry(string));
       return index.length;
     });
     ++entries[i].frequency;
   }
 
   void putOptional(String string) {
     if (string != null) {
       put(string);
     }
   }
 
   int operator [](String string) => index[string];
 
   void addLibraryImports(LibraryImportTable imports) {
     imports.importPaths.forEach(put);
   }
 
   visitName(Name node) {
     put(node.name);
   }
 
   visitLibrary(Library node) {
+    visitCanonicalName(node.canonicalName);
     putOptional(node.name);
     put('${node.importUri}');
     node.visitChildren(this);
   }
 
   visitDeferredImport(DeferredImport node) {
     put(node.name);
   }
 
   visitClass(Class node) {
@@ skipping 139 matching lines @@
   void flush() {
     _sink.add(_buffer.sublist(0, length));
     _buffer = new Uint8List(SIZE);
     length = 0;
   }
 
   void flushAndDestroy() {
     _sink.add(_buffer.sublist(0, length));
   }
 }