pkg/compiler/lib/src/serialization/indexed_sink_source.dart - sdk.git - Git at Google

 // Copyright (c) 2018, 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.

 import 'serialization.dart';

 abstract class IndexedSource<E extends Object> {
   Map<int, E> get cache;

   E? read(DataSourceReader source, E Function() readValue);
   E? readWithoutCache(DataSourceReader source, E Function() readValue);
 }

 abstract class IndexedSink<E extends Object> {
   Map<E, int> get cache;

   void write(DataSinkWriter sink, E? value, void Function(E value) writeValue);
 }

 const int _dataInPlaceIndicator = 0;
 const int _nullIndicator = 1;
 const int _nonCompactOffsetIndicator = 2;
 const int _indicatorOffset = 3;

 /// Facilitates indexed reads and writes for [IndexedSource] and [IndexedSink].
 ///
 /// Created and stores shared [IndexedSource] and [IndexedSink] instances for
 /// cached types. Copies indices from sources to sinks when a sink is requested
 /// so that the indices are shared across data files.
 ///
 /// [DataSourceReader] instances must be registered so that contiguous start
 /// offsets can be set on each reader. This allows global offsets to be
 /// correctly calculated by the indices. See [UnorderedIndexedSource] for more
 /// info.
 class SerializationIndices {
   final Map<Type, IndexedSource> _indexedSources = {};
   final Map<Type, IndexedSink> _indexedSinks = {};
   final List<DataSourceReader> _sources = [];
   final bool testMode;

   SerializationIndices({this.testMode = false});

   int registerSource(DataSourceReader source) {
     int startOffset;
     if (_sources.isEmpty) {
       startOffset = 0;
     } else {
       final lastSource = _sources.last;
       startOffset = lastSource.startOffset + lastSource.length;
     }
     _sources.add(source);
     return startOffset;
   }

   IndexedSource<E> getIndexedSource<E extends Object>() {
     final source =
         (_indexedSources[E] ??= UnorderedIndexedSource<E>(this))
             as IndexedSource<E>;
     if (testMode) {
       /// In test mode we ensure that the values we read out are identical to
       /// the values we write in. When copying the elements we turn the local
       /// offsets to global offsets so that the source cache will hit.
       /// Note: Mapped sinks will not get copied over since the mapped write
       /// type will be different from the read type.
       final sink = _indexedSinks[E] as IndexedSink<E>?;
       sink?.cache.forEach((value, offset) {
         // We convert local offsets to relative offsets because source caching
         // uses the relative address space. We want to ensure objects that are
         // serialized and immediately deserialized during testing share the same
         // cached references.
         source.cache[_localToGlobalForTesting(offset)] = value;
       });
     }
     return source;
   }

   IndexedSink<E> getIndexedSink<E extends Object>({bool identity = false}) {
     return _getIndexedSink<E, E>(null, identity: identity);
   }

   IndexedSink<T> getMappedIndexedSink<E extends Object, T extends Object>(
     T Function(E value) f,
   ) {
     return _getIndexedSink<E, T>(f, identity: false);
   }

   IndexedSink<T> _getIndexedSink<E extends Object, T extends Object>(
     T Function(E value)? f, {
     required bool identity,
   }) {
     final sink =
         (_indexedSinks[T] ??= UnorderedIndexedSink<T>(identity: identity))
             as IndexedSink<T>;
     final source = _indexedSources[E] as UnorderedIndexedSource<E>?;
     source?.cache.forEach((offset, value) {
       final key = (f != null ? f(value) : value) as T;
       sink.cache[key] = offset;
     });
     return sink;
   }
 }

 /// We use one bit to represent that an offset is local to the same data file.
 const int _numLocalityBits = 1;

 /// We can only compactly represent offsets up to the max supported by the
 /// [BinaryDataSink] minus the number of bits used to represent offset locality.
 const int _maxCompactOffset = BinaryDataSink.maxIntValue >> _numLocalityBits;

 // Real offsets are the offsets into the file the data is written in.
 // Local offsets are real offsets with an extra indicator bit set to 1.
 // Global offsets are offsets into the address space of all files with an
 // extra indicator bit set to 0.
 int _realToLocalOffset(int offset) => (offset << 1) | 1;
 int _realToGlobalOffset(int offset, DataSourceReader source) =>
     (offset + source.startOffset) << 1;
 bool _isLocalOffset(int offset) => (offset & 1) == 1;
 int _offsetWithoutIndicator(int offset) => offset >> 1;
 int _globalToRealOffset(int offset, DataSourceReader source) =>
     (offset >> 1) - source.startOffset;
 int _localToGlobalOffset(int offset, DataSourceReader source) =>
     _realToGlobalOffset(offset >> 1, source);
 int _localToGlobalForTesting(int offset) => offset & ~1;

 /// Data sink helper that canonicalizes [E?] values using IDs.
 ///
 /// Writes a unique ID in place of previously visited indexable values. This
 /// ID is the offset in the data stream at which the serialized value can be
 /// read. The read and write order do not need to be the same because no matter
 /// what occurrence of the ID we encounter, we can always recover the value.
 ///
 /// We increment all written offsets by an adjustment value in order to
 /// distinguish which source file the offset is from on deserialization.
 /// See [UnorderedIndexedSource] for more info.
 class UnorderedIndexedSink<E extends Object> implements IndexedSink<E> {
   final Map<E, int> _cache;

   UnorderedIndexedSink({bool identity = false})
     : _cache = identity ? Map.identity() : {};

   @override
   Map<E, int> get cache => _cache;

   /// Write a reference to [value] to the data sink.
   ///
   /// If [value] has not been canonicalized yet, [writeValue] is called to
   /// serialize the [value] itself.
   @override
   void write(DataSinkWriter sink, E? value, void Function(E value) writeValue) {
     if (value == null) {
       // We reserve 1 as an indicator for `null`.
       sink.writeInt(_nullIndicator);
       return;
     }
     final offset = _cache[value];
     if (offset == null) {
       // We reserve 0 as an indicator that the data is written 'here'.
       sink.writeInt(_dataInPlaceIndicator);
       _cache[value] = _realToLocalOffset(sink.length);
       writeValue(value);
     } else {
       final writtenOffset = offset + _indicatorOffset;
       if (writtenOffset >= _maxCompactOffset) {
         sink.writeInt(_nonCompactOffsetIndicator);
         sink.writeUint32(offset);
       } else {
         sink.writeInt(writtenOffset);
       }
     }
   }
 }

 /// Data source helper reads canonicalized [E?] values through IDs.
 ///
 /// Reads indexable elements via their unique ID. Each ID is the offset in
 /// the data stream at which the serialized value can be read. The first time an
 /// ID is discovered we jump to the value's offset, deserialize it, and
 /// then jump back to the 'current' offset.
 ///
 /// In order to read cached offsets across files, we map offset ranges to a
 /// specific source:
 ///
 ///   offset 0  .. K1    --- source S1
 ///   offset K1 .. K2    --- source S2
 ///   offset K2 .. K3    --- source S3
 ///
 /// This effectively treats all the files as a contiguous address space with
 /// offsets being global to the start of the first source.
 ///
 /// Offsets are written in one of two forms. Either as a local offset, an offset
 /// relative to the start of the same file, or as a global offset, an offset
 /// relative to the start of the concatenated address space of all sources. The
 /// two forms are indicated via the lowest bit, the former has that bit set,
 /// the latter does not. Local offsets are turned into global offsets when they
 /// are written into a later file.
 ///
 /// If an offset is encountered outside the block accessible to current source,
 /// [SerializationIndices] provides pointers to the previous sources to check
 /// (i.e. previous blocks in the address space).
 class UnorderedIndexedSource<E extends Object> implements IndexedSource<E> {
   final Map<int, E> _cache = {};
   final SerializationIndices _indices;

   UnorderedIndexedSource(this._indices);

   @override
   Map<int, E> get cache => _cache;

   /// Reads a reference to an [E?] value from the data source or the backing
   /// cache if the index has already been read.
   ///
   /// If the value hasn't yet been read, [readValue] is called to deserialize
   /// the value itself.
   @override
   E? read(DataSourceReader source, E Function() readValue) {
     final markerOrOffset = source.readInt();

     if (markerOrOffset == _dataInPlaceIndicator) {
       final globalOffset = _realToGlobalOffset(source.currentOffset, source);
       // We have to read the value regardless of whether or not it's cached to
       // move the reader past it.
       final value = readValue();
       final cachedValue = _cache[globalOffset];
       if (cachedValue != null) return cachedValue;
       _cache[globalOffset] = value;
       return value;
     } else if (markerOrOffset == _nullIndicator) {
       return null;
     } else {
       int offset;
       if (markerOrOffset == _nonCompactOffsetIndicator) {
         offset = source.readUint32();
       } else {
         offset = markerOrOffset - _indicatorOffset;
       }
       bool isLocal = _isLocalOffset(offset);
       final globalOffset = isLocal
           ? _localToGlobalOffset(offset, source)
           : offset;
       final cachedValue = _cache[globalOffset];
       if (cachedValue != null) return cachedValue;
       return _readAtOffset(
         source,
         readValue,
         globalOffset,
         isLocal,
         isCached: true,
       );
     }
   }

   /// Reads a reference to an [E?] value from the data source.
   ///
   /// Does not cache the read value so each call to [readWithoutCache] of the
   /// associated index will create a new object.
   @override
   E? readWithoutCache(DataSourceReader source, E Function() readValue) {
     final markerOrOffset = source.readInt();

     if (markerOrOffset == _dataInPlaceIndicator) {
       return readValue();
     } else if (markerOrOffset == _nullIndicator) {
       return null;
     } else {
       int offset;
       if (markerOrOffset == _nonCompactOffsetIndicator) {
         offset = source.readUint32();
       } else {
         offset = markerOrOffset - _indicatorOffset;
       }
       bool isLocal = _isLocalOffset(offset);
       final globalOffset = isLocal
           ? _localToGlobalOffset(offset, source)
           : offset;
       return _readAtOffset(
         source,
         readValue,
         globalOffset,
         isLocal,
         isCached: false,
       );
     }
   }

   DataSourceReader findSource(int globalOffset) {
     final offset = _offsetWithoutIndicator(globalOffset);
     final sources = _indices._sources;
     for (int i = sources.length - 1; i >= 0; i--) {
       final source = sources[i];
       if (source.startOffset <= offset) return source;
     }
     throw StateError('Could not find source for $offset.');
   }

   E _readAtOffset(
     DataSourceReader source,
     E Function() readValue,
     int globalOffset,
     bool isLocal, {
     required bool isCached,
   }) {
     final realSource = isLocal ? source : findSource(globalOffset);
     final realOffset = _globalToRealOffset(globalOffset, realSource);
     final value = isLocal
         ? source.readWithOffset(realOffset, readValue)
         : source.readWithSource(
             realSource,
             () => source.readWithOffset(realOffset, readValue),
           );
     if (isCached) _cache[globalOffset] = value;
     return value;
   }
 }
	// Copyright (c) 2018, 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.

	import 'serialization.dart';

	abstract class IndexedSource<E extends Object> {
	Map<int, E> get cache;

	E? read(DataSourceReader source, E Function() readValue);
	E? readWithoutCache(DataSourceReader source, E Function() readValue);
	}

	abstract class IndexedSink<E extends Object> {
	Map<E, int> get cache;

	void write(DataSinkWriter sink, E? value, void Function(E value) writeValue);
	}

	const int _dataInPlaceIndicator = 0;
	const int _nullIndicator = 1;
	const int _nonCompactOffsetIndicator = 2;
	const int _indicatorOffset = 3;

	/// Facilitates indexed reads and writes for [IndexedSource] and [IndexedSink].
	///
	/// Created and stores shared [IndexedSource] and [IndexedSink] instances for
	/// cached types. Copies indices from sources to sinks when a sink is requested
	/// so that the indices are shared across data files.
	///
	/// [DataSourceReader] instances must be registered so that contiguous start
	/// offsets can be set on each reader. This allows global offsets to be
	/// correctly calculated by the indices. See [UnorderedIndexedSource] for more
	/// info.
	class SerializationIndices {
	final Map<Type, IndexedSource> _indexedSources = {};
	final Map<Type, IndexedSink> _indexedSinks = {};
	final List<DataSourceReader> _sources = [];
	final bool testMode;

	SerializationIndices({this.testMode = false});

	int registerSource(DataSourceReader source) {
	int startOffset;
	if (_sources.isEmpty) {
	startOffset = 0;
	} else {
	final lastSource = _sources.last;
	startOffset = lastSource.startOffset + lastSource.length;
	}
	_sources.add(source);
	return startOffset;
	}

	IndexedSource<E> getIndexedSource<E extends Object>() {
	final source =
	(_indexedSources[E] ??= UnorderedIndexedSource<E>(this))
	as IndexedSource<E>;
	if (testMode) {
	/// In test mode we ensure that the values we read out are identical to
	/// the values we write in. When copying the elements we turn the local
	/// offsets to global offsets so that the source cache will hit.
	/// Note: Mapped sinks will not get copied over since the mapped write
	/// type will be different from the read type.
	final sink = _indexedSinks[E] as IndexedSink<E>?;
	sink?.cache.forEach((value, offset) {
	// We convert local offsets to relative offsets because source caching
	// uses the relative address space. We want to ensure objects that are
	// serialized and immediately deserialized during testing share the same
	// cached references.
	source.cache[_localToGlobalForTesting(offset)] = value;
	});
	}
	return source;
	}

	IndexedSink<E> getIndexedSink<E extends Object>({bool identity = false}) {
	return _getIndexedSink<E, E>(null, identity: identity);
	}

	IndexedSink<T> getMappedIndexedSink<E extends Object, T extends Object>(
	T Function(E value) f,
	) {
	return _getIndexedSink<E, T>(f, identity: false);
	}

	IndexedSink<T> _getIndexedSink<E extends Object, T extends Object>(
	T Function(E value)? f, {
	required bool identity,
	}) {
	final sink =
	(_indexedSinks[T] ??= UnorderedIndexedSink<T>(identity: identity))
	as IndexedSink<T>;
	final source = _indexedSources[E] as UnorderedIndexedSource<E>?;
	source?.cache.forEach((offset, value) {
	final key = (f != null ? f(value) : value) as T;
	sink.cache[key] = offset;
	});
	return sink;
	}
	}

	/// We use one bit to represent that an offset is local to the same data file.
	const int _numLocalityBits = 1;

	/// We can only compactly represent offsets up to the max supported by the
	/// [BinaryDataSink] minus the number of bits used to represent offset locality.
	const int _maxCompactOffset = BinaryDataSink.maxIntValue >> _numLocalityBits;

	// Real offsets are the offsets into the file the data is written in.
	// Local offsets are real offsets with an extra indicator bit set to 1.
	// Global offsets are offsets into the address space of all files with an
	// extra indicator bit set to 0.
	int _realToLocalOffset(int offset) => (offset << 1) \| 1;
	int _realToGlobalOffset(int offset, DataSourceReader source) =>
	(offset + source.startOffset) << 1;
	bool _isLocalOffset(int offset) => (offset & 1) == 1;
	int _offsetWithoutIndicator(int offset) => offset >> 1;
	int _globalToRealOffset(int offset, DataSourceReader source) =>
	(offset >> 1) - source.startOffset;
	int _localToGlobalOffset(int offset, DataSourceReader source) =>
	_realToGlobalOffset(offset >> 1, source);
	int _localToGlobalForTesting(int offset) => offset & ~1;

	/// Data sink helper that canonicalizes [E?] values using IDs.
	///
	/// Writes a unique ID in place of previously visited indexable values. This
	/// ID is the offset in the data stream at which the serialized value can be
	/// read. The read and write order do not need to be the same because no matter
	/// what occurrence of the ID we encounter, we can always recover the value.
	///
	/// We increment all written offsets by an adjustment value in order to
	/// distinguish which source file the offset is from on deserialization.
	/// See [UnorderedIndexedSource] for more info.
	class UnorderedIndexedSink<E extends Object> implements IndexedSink<E> {
	final Map<E, int> _cache;

	UnorderedIndexedSink({bool identity = false})
	: _cache = identity ? Map.identity() : {};

	@override
	Map<E, int> get cache => _cache;

	/// Write a reference to [value] to the data sink.
	///
	/// If [value] has not been canonicalized yet, [writeValue] is called to
	/// serialize the [value] itself.
	@override
	void write(DataSinkWriter sink, E? value, void Function(E value) writeValue) {
	if (value == null) {
	// We reserve 1 as an indicator for `null`.
	sink.writeInt(_nullIndicator);
	return;
	}
	final offset = _cache[value];
	if (offset == null) {
	// We reserve 0 as an indicator that the data is written 'here'.
	sink.writeInt(_dataInPlaceIndicator);
	_cache[value] = _realToLocalOffset(sink.length);
	writeValue(value);
	} else {
	final writtenOffset = offset + _indicatorOffset;
	if (writtenOffset >= _maxCompactOffset) {
	sink.writeInt(_nonCompactOffsetIndicator);
	sink.writeUint32(offset);
	} else {
	sink.writeInt(writtenOffset);
	}
	}
	}
	}

	/// Data source helper reads canonicalized [E?] values through IDs.
	///
	/// Reads indexable elements via their unique ID. Each ID is the offset in
	/// the data stream at which the serialized value can be read. The first time an
	/// ID is discovered we jump to the value's offset, deserialize it, and
	/// then jump back to the 'current' offset.
	///
	/// In order to read cached offsets across files, we map offset ranges to a
	/// specific source:
	///
	/// offset 0 .. K1 --- source S1
	/// offset K1 .. K2 --- source S2
	/// offset K2 .. K3 --- source S3
	///
	/// This effectively treats all the files as a contiguous address space with
	/// offsets being global to the start of the first source.
	///
	/// Offsets are written in one of two forms. Either as a local offset, an offset
	/// relative to the start of the same file, or as a global offset, an offset
	/// relative to the start of the concatenated address space of all sources. The
	/// two forms are indicated via the lowest bit, the former has that bit set,
	/// the latter does not. Local offsets are turned into global offsets when they
	/// are written into a later file.
	///
	/// If an offset is encountered outside the block accessible to current source,
	/// [SerializationIndices] provides pointers to the previous sources to check
	/// (i.e. previous blocks in the address space).
	class UnorderedIndexedSource<E extends Object> implements IndexedSource<E> {
	final Map<int, E> _cache = {};
	final SerializationIndices _indices;

	UnorderedIndexedSource(this._indices);

	@override
	Map<int, E> get cache => _cache;

	/// Reads a reference to an [E?] value from the data source or the backing
	/// cache if the index has already been read.
	///
	/// If the value hasn't yet been read, [readValue] is called to deserialize
	/// the value itself.
	@override
	E? read(DataSourceReader source, E Function() readValue) {
	final markerOrOffset = source.readInt();

	if (markerOrOffset == _dataInPlaceIndicator) {
	final globalOffset = _realToGlobalOffset(source.currentOffset, source);
	// We have to read the value regardless of whether or not it's cached to
	// move the reader past it.
	final value = readValue();
	final cachedValue = _cache[globalOffset];
	if (cachedValue != null) return cachedValue;
	_cache[globalOffset] = value;
	return value;
	} else if (markerOrOffset == _nullIndicator) {
	return null;
	} else {
	int offset;
	if (markerOrOffset == _nonCompactOffsetIndicator) {
	offset = source.readUint32();
	} else {
	offset = markerOrOffset - _indicatorOffset;
	}
	bool isLocal = _isLocalOffset(offset);
	final globalOffset = isLocal
	? _localToGlobalOffset(offset, source)
	: offset;
	final cachedValue = _cache[globalOffset];
	if (cachedValue != null) return cachedValue;
	return _readAtOffset(
	source,
	readValue,
	globalOffset,
	isLocal,
	isCached: true,
	);
	}
	}

	/// Reads a reference to an [E?] value from the data source.
	///
	/// Does not cache the read value so each call to [readWithoutCache] of the
	/// associated index will create a new object.
	@override
	E? readWithoutCache(DataSourceReader source, E Function() readValue) {
	final markerOrOffset = source.readInt();

	if (markerOrOffset == _dataInPlaceIndicator) {
	return readValue();
	} else if (markerOrOffset == _nullIndicator) {
	return null;
	} else {
	int offset;
	if (markerOrOffset == _nonCompactOffsetIndicator) {
	offset = source.readUint32();
	} else {
	offset = markerOrOffset - _indicatorOffset;
	}
	bool isLocal = _isLocalOffset(offset);
	final globalOffset = isLocal
	? _localToGlobalOffset(offset, source)
	: offset;
	return _readAtOffset(
	source,
	readValue,
	globalOffset,
	isLocal,
	isCached: false,
	);
	}
	}

	DataSourceReader findSource(int globalOffset) {
	final offset = _offsetWithoutIndicator(globalOffset);
	final sources = _indices._sources;
	for (int i = sources.length - 1; i >= 0; i--) {
	final source = sources[i];
	if (source.startOffset <= offset) return source;
	}
	throw StateError('Could not find source for $offset.');
	}

	E _readAtOffset(
	DataSourceReader source,
	E Function() readValue,
	int globalOffset,
	bool isLocal, {
	required bool isCached,
	}) {
	final realSource = isLocal ? source : findSource(globalOffset);
	final realOffset = _globalToRealOffset(globalOffset, realSource);
	final value = isLocal
	? source.readWithOffset(realOffset, readValue)
	: source.readWithSource(
	realSource,
	() => source.readWithOffset(realOffset, readValue),
	);
	if (isCached) _cache[globalOffset] = value;
	return value;
	}
	}