| // Copyright (c) 2013, 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 dart2js.ir_pickler; |
| |
| import 'ir_nodes.dart' as ir; |
| import '../dart2jslib.dart' show |
| Constant, FalseConstant, TrueConstant, IntConstant, DoubleConstant, |
| StringConstant, NullConstant, ListConstant, MapConstant, |
| InterceptorConstant, DummyConstant, FunctionConstant, TypeConstant, |
| ConstructedConstant, |
| ConstantVisitor, ConstantSystem, |
| Compiler, NO_LOCATION_SPANNABLE; |
| import 'dart:typed_data' show ByteData, Endianness, Uint8List; |
| import 'dart:convert' show UTF8; |
| import '../tree/tree.dart' as ast show |
| DartString, LiteralDartString, RawSourceDartString, EscapedSourceDartString, |
| ConsDartString; |
| import '../elements/elements.dart' show |
| Element, LibraryElement, FunctionElement; |
| import '../universe/universe.dart' show Selector, TypedSelector, SelectorKind; |
| |
| part 'ir_unpickler.dart'; |
| |
| /* The int(entries) counts expression nodes, which might potentially be |
| * referred to in a back reference. |
| * |
| * pickle ::= int(entries) function |
| * |
| * function ::= int(endSourceOffset) int(namePosition) node(body) |
| * |
| * int ::= see [writeInt] for number encoding |
| * |
| * string ::= byte(STRING_ASCII) int(length) {byte(ascii)} |
| * | byte(STRING_UTF8) int(length) {byte(utf8)} |
| * |
| * node ::= byte(NODE_CONSTANT) constant node(next) |
| * | byte(NODE_LET_CONT) node(next) node(body) |
| * | byte(NODE_INVOKE_STATIC) element selector |
| * reference(continuation) {reference(argument)} |
| * | byte(NODE_INVOKE_CONTINUATION) reference(continuation) |
| * reference(argument) |
| * |
| * reference ::= int(indexDelta) |
| * |
| * constant ::= byte(CONST_BOOL) byte(0 or 1) |
| * | byte(CONST_DOUBLE) byte{8} |
| * | byte(CONST_INT) int(value) |
| * | byte(CONST_STRING_LITERAL) string |
| * | byte(CONST_STRING_RAW) string int(length) |
| * | byte(CONST_STRING_ESCAPED) string int(length) |
| * | byte(CONST_STRING_CONS) constant(left) constant(right) |
| * | byte(CONST_NULL) |
| * |
| * selector ::= byte(BACKREFERENCE) reference |
| * | byte(SELECTOR_UNTYPED) int(kind) string(name) element(library) |
| * int(argumentsCount) int(namedArgumentsCount) |
| * {string(parameterName)} |
| * |
| * element ::= int(constantPoolIndex) |
| */ |
| class Pickles { |
| static const int BACKREFERENCE = 1; |
| |
| static const int STRING_ASCII = BACKREFERENCE + 1; |
| static const int STRING_UTF8 = STRING_ASCII + 1; |
| |
| static const int FIRST_NODE_TAG = STRING_UTF8 + 1; |
| static const int NODE_CONSTANT = FIRST_NODE_TAG; |
| static const int NODE_LET_CONT = NODE_CONSTANT + 1; |
| static const int NODE_INVOKE_STATIC = NODE_LET_CONT + 1; |
| static const int NODE_INVOKE_CONTINUATION = NODE_INVOKE_STATIC + 1; |
| static const int LAST_NODE_TAG = NODE_INVOKE_CONTINUATION; |
| |
| static const int FIRST_CONST_TAG = LAST_NODE_TAG + 1; |
| static const int CONST_BOOL = FIRST_CONST_TAG; |
| static const int CONST_INT = CONST_BOOL + 1; |
| static const int CONST_DOUBLE = CONST_INT + 1; |
| static const int CONST_STRING_LITERAL = CONST_DOUBLE + 1; |
| static const int CONST_STRING_RAW = CONST_STRING_LITERAL + 1; |
| static const int CONST_STRING_ESCAPED = CONST_STRING_RAW + 1; |
| static const int CONST_STRING_CONS = CONST_STRING_ESCAPED + 1; |
| static const int CONST_NULL = CONST_STRING_CONS + 1; |
| static const int LAST_CONST_TAG = CONST_NULL; |
| |
| static const int FIRST_SELECTOR_TAG = LAST_CONST_TAG + 1; |
| static const int SELECTOR_UNTYPED = FIRST_SELECTOR_TAG; |
| static const int LAST_SELECTOR_TAG = SELECTOR_UNTYPED; |
| |
| static const int LAST_TAG = LAST_SELECTOR_TAG; |
| |
| static final List<SelectorKind> selectorKindFromId = _selectorKindFromId(); |
| |
| static List<SelectorKind> _selectorKindFromId() { |
| List<SelectorKind> result = <SelectorKind>[ |
| SelectorKind.GETTER, |
| SelectorKind.SETTER, |
| SelectorKind.CALL, |
| SelectorKind.OPERATOR, |
| SelectorKind.INDEX]; |
| for (int i = 0; i < result.length; i++) { |
| assert(result[i].hashCode == i); |
| } |
| return result; |
| } |
| } |
| |
| class IrConstantPool { |
| static Map<LibraryElement, IrConstantPool> _constantPools = |
| <LibraryElement, IrConstantPool>{}; |
| |
| static IrConstantPool forLibrary(LibraryElement library) { |
| return _constantPools.putIfAbsent(library, () => new IrConstantPool()); |
| } |
| |
| /** |
| * The entries of the constant pool. Method [add] ensures that an object |
| * is only added once to this list. |
| */ |
| List<Object> entries = <Object>[]; |
| |
| /** |
| * This map is the inverse of [entries], it stores the index of each object. |
| */ |
| Map<Object, int> entryIndex = <Object, int>{}; |
| |
| int add(Object o) { |
| return entryIndex.putIfAbsent(o, () { |
| entries.add(o); |
| return entries.length - 1; |
| }); |
| } |
| |
| Object get(int index) => entries[index]; |
| } |
| |
| /** |
| * The [Pickler] serializes [ir.Node]s to a byte array. |
| */ |
| class Pickler extends ir.Visitor { |
| ConstantPickler constantPickler; |
| |
| IrConstantPool constantPool; |
| |
| Pickler(this.constantPool) { |
| assert(Pickles.LAST_TAG <= 0xff); |
| constantPickler = new ConstantPickler(this); |
| } |
| |
| static final int INITIAL_SIZE = 8; |
| static final int MAX_GROW_RATE = 4096; |
| |
| List<int> data; |
| |
| /** Offset of the next byte that will be written. */ |
| int offset; |
| |
| /** Stores the index for emitted entries that might be back-referenced. */ |
| Map<Object, int> emitted; |
| |
| /** A counter for entries in the [emitted] map. */ |
| int index; |
| |
| /** |
| * This buffer is used in [writeConstDouble] to obtain a byte representation |
| * for doubles. |
| */ |
| ByteData doubleData = new ByteData(8); |
| |
| List<int> pickle(ir.Function function) { |
| data = new Uint8List(INITIAL_SIZE); |
| offset = 0; |
| emitted = <Object, int>{}; |
| index = 0; |
| function.accept(this); |
| |
| int sizeOffset = offset; |
| writeInt(emitted.length); |
| int sizeBytes = offset - sizeOffset; |
| |
| // The array is longer than necessary, create a copy with the actual size. |
| Uint8List result = new Uint8List(offset); |
| // Emit the number or entries in the beginning. |
| for (int i = 0, j = sizeOffset; i < sizeBytes; i++, j++) { |
| result[i] = data[j]; |
| } |
| for (int i = sizeBytes, j = 0; i < offset; i++, j++) { |
| result[i] = data[j]; |
| } |
| return result; |
| } |
| |
| void resize(int newSize) { |
| Uint8List newData = new Uint8List(newSize); |
| for (int i = 0; i < data.length; i++) { |
| newData[i] = data[i]; |
| } |
| data = newData; |
| } |
| |
| void ensureCapacity() { |
| // (offset == data.length-1) is still OK, the byte at [offset] has not yet |
| // been written. |
| int size = data.length; |
| if (offset < size) return; |
| if (size > MAX_GROW_RATE) { |
| size += MAX_GROW_RATE; |
| } else { |
| size *= 2; |
| } |
| resize(size); |
| } |
| |
| static isByte(int byte) => 0 <= byte && byte <= 0xff; |
| |
| void writeByte(int byte) { |
| assert(isByte(byte)); |
| ensureCapacity(); |
| data[offset++] = byte; |
| } |
| |
| /** |
| * Writes integers to the buffer. |
| * |
| * The least significant bit of the serialized data encodes the sign. Each |
| * byte contains 7 bits of data and one bit indicating if it is the last byte |
| * of the number. |
| */ |
| void writeInt(int n) { |
| bool isNegative = n < 0; |
| n = isNegative ? -n : n; |
| // Least significant bit is the sign. |
| int bits = (n << 1) | (isNegative ? 1 : 0); |
| do { |
| int next = bits & 0x7f; |
| bits >>= 7; |
| bool hasMore = bits != 0; |
| next = (next << 1) | (hasMore ? 1 : 0); |
| writeByte(next); |
| } while (bits != 0); |
| } |
| |
| void writeString(String s) { |
| int startOffset = offset; |
| writeByte(Pickles.STRING_ASCII); |
| writeInt(s.length); |
| for (int i = 0; i < s.length; i++) { |
| int c = s.codeUnitAt(i); |
| if (c < 0x80) { |
| writeByte(c); |
| } else { |
| // Strings with non-ascii characters are encoded using UTF-8. |
| writeUtf8String(s, startOffset); |
| return; |
| } |
| } |
| } |
| |
| void writeUtf8String(String s, int startOffset) { |
| offset = startOffset; |
| writeByte(Pickles.STRING_UTF8); |
| List<int> bytes = UTF8.encode(s); |
| writeInt(bytes.length); |
| for (int i = 0; i < bytes.length; i++) { |
| writeByte(bytes[i]); |
| } |
| } |
| |
| /** |
| * This function records [entry] in the [emitted] table. It needs to be |
| * invoked when pickling an object which might later on be used in a back |
| * reference, for example expression nodes or selectors. |
| */ |
| void recordForBackReference(Object entry) { |
| assert(emitted[entry] == null); |
| emitted[entry] = index++; |
| } |
| |
| void writeBackReference(Object entry) { |
| int entryIndex = emitted[entry]; |
| writeInt(index - entryIndex); |
| } |
| |
| void writeBackReferenceList(List entries) { |
| writeInt(entries.length); |
| for (int i = 0; i < entries.length; i++) { |
| writeBackReference(entries[i]); |
| } |
| } |
| |
| void writeConstBool(bool b) { |
| writeByte(Pickles.CONST_BOOL); |
| writeByte(b ? 1 : 0); |
| } |
| |
| void writeConstInt(int n) { |
| writeByte(Pickles.CONST_INT); |
| writeInt(n); |
| } |
| |
| void writeConstDouble(double d) { |
| writeByte(Pickles.CONST_DOUBLE); |
| doubleData.setFloat64(0, d, Endianness.BIG_ENDIAN); |
| for (int i = 0; i < 8; i++) { |
| writeByte(doubleData.getUint8(i)); |
| } |
| } |
| |
| void writeDartString(ast.DartString s) { |
| if (s is ast.LiteralDartString) { |
| writeByte(Pickles.CONST_STRING_LITERAL); |
| writeString(s.string); |
| } else if (s is ast.RawSourceDartString) { |
| writeByte(Pickles.CONST_STRING_RAW); |
| writeString(s.source); |
| writeInt(s.length); |
| } else if (s is ast.EscapedSourceDartString) { |
| writeByte(Pickles.CONST_STRING_ESCAPED); |
| writeString(s.source); |
| writeInt(s.length); |
| } else if (s is ast.ConsDartString) { |
| writeByte(Pickles.CONST_STRING_CONS); |
| writeDartString(s.left); |
| writeDartString(s.right); |
| } else { |
| throw "Unexpected DartString: $s"; |
| } |
| } |
| |
| void writeConstNull() { |
| writeByte(Pickles.CONST_NULL); |
| } |
| |
| void writeElement(Element element) { |
| writeInt(constantPool.add(element)); |
| } |
| |
| void writeSelector(Selector selector) { |
| if (emitted.containsKey(selector)) { |
| writeByte(Pickles.BACKREFERENCE); |
| writeBackReference(selector); |
| } else { |
| recordForBackReference(selector); |
| assert(selector is !TypedSelector); |
| writeByte(Pickles.SELECTOR_UNTYPED); |
| writeInt(selector.kind.hashCode); |
| writeString(selector.name); |
| writeElement(selector.library); |
| writeInt(selector.argumentCount); |
| int namedArgumentsCount = selector.namedArguments.length; |
| writeInt(namedArgumentsCount); |
| for (int i = 0; i < namedArgumentsCount; i++) { |
| writeString(selector.namedArguments[i]); |
| } |
| } |
| } |
| |
| void visitFunction(ir.Function node) { |
| writeInt(node.endOffset); |
| writeInt(node.namePosition); |
| // The continuation parameter is bound in the body. |
| recordForBackReference(node.returnContinuation); |
| node.body.accept(this); |
| } |
| |
| void visitLetPrim(ir.LetPrim node) { |
| node.primitive.accept(this); |
| // The right-hand side is bound in the body. |
| recordForBackReference(node.primitive); |
| node.body.accept(this); |
| } |
| |
| void visitLetCont(ir.LetCont node) { |
| // There are two choices of which expression tree to write first---the |
| // continuation body or the LetCont body. The unpickler will unpickle the |
| // the first recursively and the second iteratively. Since the hole in |
| // LetCont contexts is in the continuation body, the continuation should be |
| // written second. |
| writeByte(Pickles.NODE_LET_CONT); |
| // The continuation is bound in the body. |
| recordForBackReference(node.continuation); |
| node.body.accept(this); |
| // The continuation parameter is bound in the continuation's body. |
| recordForBackReference(node.continuation.parameter); |
| node.continuation.body.accept(this); |
| } |
| |
| void visitInvokeStatic(ir.InvokeStatic node) { |
| writeByte(Pickles.NODE_INVOKE_STATIC); |
| writeElement(node.target); |
| writeSelector(node.selector); |
| // TODO(lry): compact encoding when the arity of the selector and the |
| // arguments list are the same |
| writeBackReference(node.continuation.definition); |
| writeBackReferenceList(node.arguments.map( |
| (a) => a.definition).toList(growable: false)); |
| } |
| |
| void visitInvokeContinuation(ir.InvokeContinuation node) { |
| writeByte(Pickles.NODE_INVOKE_CONTINUATION); |
| writeBackReference(node.continuation.definition); |
| writeBackReference(node.argument.definition); |
| } |
| |
| void visitConstant(ir.Constant node) { |
| writeByte(Pickles.NODE_CONSTANT); |
| node.value.accept(constantPickler); |
| } |
| |
| void visitNode(ir.Node node) { |
| throw "Unexpected $node in pickler."; |
| } |
| } |
| |
| /** |
| * A visitor for constants which writes the constant values to its [Pickler]. |
| */ |
| class ConstantPickler extends ConstantVisitor { |
| |
| final Pickler pickler; |
| ConstantPickler(this.pickler); |
| |
| void visitFalse(FalseConstant constant) { |
| pickler.writeConstBool(false); |
| } |
| |
| void visitTrue(TrueConstant constant) { |
| pickler.writeConstBool(true); |
| } |
| |
| void visitInt(IntConstant constant) { |
| pickler.writeConstInt(constant.value); |
| } |
| |
| void visitDouble(DoubleConstant constant) { |
| pickler.writeConstDouble(constant.value); |
| } |
| |
| void visitString(StringConstant constant) { |
| pickler.writeDartString(constant.value); |
| } |
| |
| void visitNull(NullConstant constant) { |
| pickler.writeConstNull(); |
| } |
| |
| void visitList(ListConstant constant) => abort(constant); |
| void visitMap(MapConstant constant) => abort(constant); |
| void visitInterceptor(InterceptorConstant constant) => abort(constant); |
| void visitDummy(DummyConstant constant) => abort(constant); |
| void visitFunction(FunctionConstant constant) => abort(constant); |
| void visitType(TypeConstant constant) => abort(constant); |
| void visitConstructed(ConstructedConstant constant) => abort(constant); |
| |
| void abort(Constant value) => throw "Can not pickle constant $value"; |
| } |