pkg/front_end/lib/src/fasta/incremental_serializer.dart - sdk.git - Git at Google

 // Copyright (c) 2019, 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 fasta.incremental_serializer;

 import 'dart:typed_data' show Uint8List;

 import 'package:kernel/binary/ast_from_binary.dart' show SubComponentView;

 import 'package:kernel/binary/ast_to_binary.dart' show BinaryPrinter;

 import 'package:kernel/kernel.dart' show Component, Library, LibraryDependency;

 import 'kernel/utils.dart' show ByteSink;

 class IncrementalSerializer {
   final Map<Uri, SerializationGroup> uriToGroup =
       new Map<Uri, SerializationGroup>();
   final Set<Uri> invalidatedUris = new Set<Uri>();

   /// Invalidate the uri: Will remove cache associated with it, depending on it
   /// etc. Called by the incremental compiler.
   void invalidate(Uri uri) {
     invalidatedUris.add(uri);
   }

   /// Initializes the cache via a already serialized list of bytes based on the
   /// view of those bytes. Called by the incremental compiler.
   bool initialize(List<int> bytes, List<SubComponentView> views) {
     if (uriToGroup.isNotEmpty) {
       throw "Cannot initialize when already in use.";
     }

     // Find the sub-components that are packaged correctly.
     List<SubComponentView> goodViews = [];
     Set<Uri> uris = new Set<Uri>();
     for (int i = 0; i < views.length; i++) {
       SubComponentView view = views[i];
       bool good = true;
       String packageName;
       for (Library lib in view.libraries) {
         Uri uri = lib.importUri;
         // Uris need to be unique.
         if (!uris.add(lib.fileUri)) return false;
         if (uri.scheme == "package") {
           String thisPackageName = uri.pathSegments.first;
           if (packageName == null) {
             packageName = thisPackageName;
           } else if (packageName != thisPackageName) {
             good = false;
           }
         } else {
           good = false;
         }
       }
       if (good) {
         goodViews.add(view);
       }
     }

     // Add groups. Wrap in try because an exception will be thrown if a group
     // has a dependency that isn't being met.
     try {
       List<SerializationGroup> newGroups = new List<SerializationGroup>();
       for (int i = 0; i < goodViews.length; i++) {
         SubComponentView view = goodViews[i];
         List<int> data = new Uint8List(view.componentFileSize);
         data.setRange(0, data.length, bytes, view.componentStartOffset);
         SerializationGroup newGroup = createGroupFor(view.libraries, data);
         newGroups.add(newGroup);
       }

       // Setup dependency tracking for the new groups.
       for (int i = 0; i < goodViews.length; i++) {
         SubComponentView view = goodViews[i];
         List<Library> libraries = view.libraries;
         SerializationGroup packageGroup = newGroups[i];
         setupDependencyTracking(libraries, packageGroup);
       }
     } catch (e) {
       uriToGroup.clear();
       return false;
     }
     return true;
   }

   /// Write packages to sink, cache new package data, trim input component.
   void writePackagesToSinkAndTrimComponent(
       Component component, Sink<List<int>> sink) {
     if (component == null) return;
     if (component.libraries.isEmpty) return;

     // If we're given a partial component (i.e. an actual delta component)
     // incremental serialization (at least currently) doesn't work.
     // The reason is that it might contain a new partial thing of what we
     // already have cached while still depending on something from the same
     // group that is currently cached. We would throw away the cache, but
     // actually depend on something we just threw away --- we would try to
     // include it and crash because we no longer have it.
     // Alternative ways to fix this could be:
     // * to group into smaller groups so this wouldn't happen.
     // * cache the actual Libraries too, so we could re-serialize when needed
     //   (though maybe not eagerly).
     if (!isSelfContained(component)) return;

     // Remove cache pertaining to invalidated uris.
     if (invalidatedUris.isNotEmpty) {
       removeInvalidated();
     }

     // Make sure we can serialize individual libraries.
     component.computeCanonicalNames();

     // Split into package and non-package libraries.
     List<Library> packageLibraries = new List<Library>();
     List<Library> nonPackageLibraries = new List<Library>();
     for (Library lib in component.libraries) {
       Uri uri = lib.importUri;
       if (uri.scheme == "package") {
         packageLibraries.add(lib);
       } else {
         nonPackageLibraries.add(lib);
       }
     }

     // Output already serialized packages and group needed non-serialized
     // packages.
     Map<String, List<Library>> newPackages = new Map<String, List<Library>>();
     Set<SerializationGroup> cachedPackagesInOutput =
         new Set<SerializationGroup>.identity();
     for (Library lib in packageLibraries) {
       SerializationGroup group = uriToGroup[lib.fileUri];
       if (group != null) {
         addDataButNotDependentData(group, cachedPackagesInOutput, sink);
       } else {
         String package = lib.importUri.pathSegments.first;
         newPackages[package] ??= <Library>[];
         newPackages[package].add(lib);
       }
     }

     // Add any dependencies that wasn't added already.
     List<SerializationGroup> upFrontGroups = cachedPackagesInOutput.toList();
     for (SerializationGroup group in upFrontGroups) {
       if (group.dependencies != null) {
         // Now also add all dependencies.
         for (SerializationGroup dep in group.dependencies) {
           addDataAndDependentData(dep, cachedPackagesInOutput, sink);
         }
       }
     }

     // Serialize all new packages, create groups and add to sink.
     Map<String, SerializationGroup> newPackageGroups =
         new Map<String, SerializationGroup>();
     for (String package in newPackages.keys) {
       List<Library> libraries = newPackages[package];
       List<int> data = serialize(component, libraries);
       sink.add(data);
       SerializationGroup newGroup = createGroupFor(libraries, data);
       newPackageGroups[package] = newGroup;
     }

     // Setup dependency tracking for the new groups.
     for (String package in newPackages.keys) {
       List<Library> libraries = newPackages[package];
       SerializationGroup packageGroup = newPackageGroups[package];
       setupDependencyTracking(libraries, packageGroup);
     }

     // All packages have been added to the sink already.
     component.libraries
       ..clear()
       ..addAll(nonPackageLibraries);
   }

   bool isSelfContained(Component component) {
     Set<Library> got = new Set<Library>.from(component.libraries);
     for (Library lib in component.libraries) {
       for (LibraryDependency dependency in lib.dependencies) {
         if (!got.contains(dependency.targetLibrary)) {
           if (dependency.targetLibrary.importUri.scheme == "dart") {
             continue;
           }
           return false;
         }
       }
     }
     return true;
   }

   /// Remove cached data based on what has been invalidated.
   /// Note that invalidating a single file can remove many cached things because
   /// of dependencies.
   void removeInvalidated() {
     // Remove all directly invalidated entries.
     Set<SerializationGroup> removed = new Set<SerializationGroup>();
     List<SerializationGroup> workList = new List<SerializationGroup>();
     for (Uri uri in invalidatedUris) {
       removeUriFromMap(uri, removed, workList);
     }

     // Continuously remove all that depend on the removed groups.
     //
     // Note that with the current invalidating strategy in the incremental
     // compiler this is not strictly necessary (assuming the incremental
     // compiler is used via the incremental compiler) - but it is included for
     // completeness.
     //
     // The reason we have to do this (assuming a different incremental
     // compiler invalidation strategy), is that we group things into packages,
     // meaning that a group as a whole might depend on another group containing
     // libraries that is not in the input component. Not removing these groups
     // could lead to including a group in an output where we cannot re-create
     // the dependencies. Example:
     // Group #1: [lib1]
     // Group #2: [lib2, lib3]. Note that lib3 depends on lib1, but lib2 is
     //                         standalone.
     // Lib1 is invalidated and we thus remove group #1.
     // We then serialize something that needs lib2. We thus output group #2.
     // We should now also output group #1, but we don't have it so we can't.
     // We can't re-create it either, because the input component only contains
     // lib2 as it is standalone. Had we removed group #2 too everything would
     // have been fine as we would then just serialize and cached lib2 by itself.
     while (workList.isNotEmpty) {
       SerializationGroup group = workList.removeLast();
       if (group.othersDependingOnMe == null) continue;
       for (SerializationGroup dependsOnGroup in group.othersDependingOnMe) {
         removeUriFromMap(dependsOnGroup.uris.first, removed, workList);
       }
     }

     invalidatedUris.clear();
   }

   /// Setup dependency tracking for a single group having the specified
   /// libraries. Note that all groups this depend on has to be created prior
   /// to calling this.
   void setupDependencyTracking(
       List<Library> libraries, SerializationGroup packageGroup) {
     for (Library lib in libraries) {
       for (LibraryDependency dep in lib.dependencies) {
         Library dependencyLibrary = dep.importedLibraryReference.asLibrary;
         if (dependencyLibrary.importUri.scheme != "package") continue;
         Uri dependencyLibraryUri =
             dep.importedLibraryReference.asLibrary.fileUri;
         SerializationGroup depGroup = uriToGroup[dependencyLibraryUri];
         if (depGroup == null) {
           throw "Didn't contain group for $dependencyLibraryUri";
         }
         if (depGroup == packageGroup) continue;
         packageGroup.registerDependency(depGroup);
       }
     }
   }

   /// Add the group but not its dependencies to the output if they weren't added
   /// already.
   addDataButNotDependentData(SerializationGroup group,
       Set<SerializationGroup> cachedPackagesInOutput, Sink<List<int>> sink) {
     if (cachedPackagesInOutput.add(group)) {
       sink.add(group.serializedData);
     }
   }

   /// Add the group and its dependencies to the output if they weren't added
   /// already.
   addDataAndDependentData(SerializationGroup group,
       Set<SerializationGroup> cachedPackagesInOutput, Sink<List<int>> sink) {
     if (cachedPackagesInOutput.add(group)) {
       sink.add(group.serializedData);
       if (group.dependencies != null) {
         // Now also add all dependencies.
         for (SerializationGroup dep in group.dependencies) {
           addDataAndDependentData(dep, cachedPackagesInOutput, sink);
         }
       }
     }
   }

   /// Create a [SerializationGroup] for the input, setting up [uriToGroup].
   SerializationGroup createGroupFor(List<Library> libraries, List<int> data) {
     Set<Uri> libraryUris = new Set<Uri>();
     for (Library lib in libraries) {
       libraryUris.add(lib.fileUri);
     }

     SerializationGroup newGroup = new SerializationGroup(data, libraryUris);

     for (Uri uri in libraryUris) {
       assert(!uriToGroup.containsKey(uri));
       uriToGroup[uri] = newGroup;
     }
     return newGroup;
   }

   /// Serialize the specified libraries using other needed data from the
   /// component.
   List<int> serialize(Component component, List<Library> libraries) {
     Component singlePackageLibraries = new Component(
         libraries: libraries,
         uriToSource: component.uriToSource,
         nameRoot: component.root);

     ByteSink byteSink = new ByteSink();
     final BinaryPrinter printer = new BinaryPrinter(byteSink);
     printer.writeComponentFile(singlePackageLibraries);
     return byteSink.builder.takeBytes();
   }

   /// Remove the specified uri from the [uriToGroup] map.
   ///
   /// Also remove all uris in the group the uri belongs to, and add the group to
   /// the worklist.
   void removeUriFromMap(Uri uri, Set<SerializationGroup> removed,
       List<SerializationGroup> workList) {
     SerializationGroup group = uriToGroup.remove(uri);
     if (group == null) return;
     bool added = removed.add(group);
     assert(added);
     workList.add(group);
     for (Uri groupUri in group.uris) {
       SerializationGroup sameGroup = uriToGroup.remove(groupUri);
       assert((groupUri == uri && sameGroup == null) ||
           (groupUri != uri && sameGroup != null));
     }
   }
 }

 class SerializationGroup {
   final List<int> serializedData;
   final Set<Uri> uris;
   Set<SerializationGroup> dependencies;
   Set<SerializationGroup> othersDependingOnMe;

   SerializationGroup(this.serializedData, this.uris);

   /// Register the dependency that this group depends on the [other] one.
   /// The registration is bilateral so that [other] is added as a dependency for
   /// this, and this is added as a "others depend on me" for [other].
   void registerDependency(SerializationGroup other) {
     dependencies ??= new Set<SerializationGroup>.identity();
     if (dependencies.add(other)) {
       other.othersDependingOnMe ??= new Set<SerializationGroup>.identity();
       other.othersDependingOnMe.add(this);
     }
   }
 }
	// Copyright (c) 2019, 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 fasta.incremental_serializer;

	import 'dart:typed_data' show Uint8List;

	import 'package:kernel/binary/ast_from_binary.dart' show SubComponentView;

	import 'package:kernel/binary/ast_to_binary.dart' show BinaryPrinter;

	import 'package:kernel/kernel.dart' show Component, Library, LibraryDependency;

	import 'kernel/utils.dart' show ByteSink;

	class IncrementalSerializer {
	final Map<Uri, SerializationGroup> uriToGroup =
	new Map<Uri, SerializationGroup>();
	final Set<Uri> invalidatedUris = new Set<Uri>();

	/// Invalidate the uri: Will remove cache associated with it, depending on it
	/// etc. Called by the incremental compiler.
	void invalidate(Uri uri) {
	invalidatedUris.add(uri);
	}

	/// Initializes the cache via a already serialized list of bytes based on the
	/// view of those bytes. Called by the incremental compiler.
	bool initialize(List<int> bytes, List<SubComponentView> views) {
	if (uriToGroup.isNotEmpty) {
	throw "Cannot initialize when already in use.";
	}

	// Find the sub-components that are packaged correctly.
	List<SubComponentView> goodViews = [];
	Set<Uri> uris = new Set<Uri>();
	for (int i = 0; i < views.length; i++) {
	SubComponentView view = views[i];
	bool good = true;
	String packageName;
	for (Library lib in view.libraries) {
	Uri uri = lib.importUri;
	// Uris need to be unique.
	if (!uris.add(lib.fileUri)) return false;
	if (uri.scheme == "package") {
	String thisPackageName = uri.pathSegments.first;
	if (packageName == null) {
	packageName = thisPackageName;
	} else if (packageName != thisPackageName) {
	good = false;
	}
	} else {
	good = false;
	}
	}
	if (good) {
	goodViews.add(view);
	}
	}

	// Add groups. Wrap in try because an exception will be thrown if a group
	// has a dependency that isn't being met.
	try {
	List<SerializationGroup> newGroups = new List<SerializationGroup>();
	for (int i = 0; i < goodViews.length; i++) {
	SubComponentView view = goodViews[i];
	List<int> data = new Uint8List(view.componentFileSize);
	data.setRange(0, data.length, bytes, view.componentStartOffset);
	SerializationGroup newGroup = createGroupFor(view.libraries, data);
	newGroups.add(newGroup);
	}

	// Setup dependency tracking for the new groups.
	for (int i = 0; i < goodViews.length; i++) {
	SubComponentView view = goodViews[i];
	List<Library> libraries = view.libraries;
	SerializationGroup packageGroup = newGroups[i];
	setupDependencyTracking(libraries, packageGroup);
	}
	} catch (e) {
	uriToGroup.clear();
	return false;
	}
	return true;
	}

	/// Write packages to sink, cache new package data, trim input component.
	void writePackagesToSinkAndTrimComponent(
	Component component, Sink<List<int>> sink) {
	if (component == null) return;
	if (component.libraries.isEmpty) return;

	// If we're given a partial component (i.e. an actual delta component)
	// incremental serialization (at least currently) doesn't work.
	// The reason is that it might contain a new partial thing of what we
	// already have cached while still depending on something from the same
	// group that is currently cached. We would throw away the cache, but
	// actually depend on something we just threw away --- we would try to
	// include it and crash because we no longer have it.
	// Alternative ways to fix this could be:
	// * to group into smaller groups so this wouldn't happen.
	// * cache the actual Libraries too, so we could re-serialize when needed
	// (though maybe not eagerly).
	if (!isSelfContained(component)) return;

	// Remove cache pertaining to invalidated uris.
	if (invalidatedUris.isNotEmpty) {
	removeInvalidated();
	}

	// Make sure we can serialize individual libraries.
	component.computeCanonicalNames();

	// Split into package and non-package libraries.
	List<Library> packageLibraries = new List<Library>();
	List<Library> nonPackageLibraries = new List<Library>();
	for (Library lib in component.libraries) {
	Uri uri = lib.importUri;
	if (uri.scheme == "package") {
	packageLibraries.add(lib);
	} else {
	nonPackageLibraries.add(lib);
	}
	}

	// Output already serialized packages and group needed non-serialized
	// packages.
	Map<String, List<Library>> newPackages = new Map<String, List<Library>>();
	Set<SerializationGroup> cachedPackagesInOutput =
	new Set<SerializationGroup>.identity();
	for (Library lib in packageLibraries) {
	SerializationGroup group = uriToGroup[lib.fileUri];
	if (group != null) {
	addDataButNotDependentData(group, cachedPackagesInOutput, sink);
	} else {
	String package = lib.importUri.pathSegments.first;
	newPackages[package] ??= <Library>[];
	newPackages[package].add(lib);
	}
	}

	// Add any dependencies that wasn't added already.
	List<SerializationGroup> upFrontGroups = cachedPackagesInOutput.toList();
	for (SerializationGroup group in upFrontGroups) {
	if (group.dependencies != null) {
	// Now also add all dependencies.
	for (SerializationGroup dep in group.dependencies) {
	addDataAndDependentData(dep, cachedPackagesInOutput, sink);
	}
	}
	}

	// Serialize all new packages, create groups and add to sink.
	Map<String, SerializationGroup> newPackageGroups =
	new Map<String, SerializationGroup>();
	for (String package in newPackages.keys) {
	List<Library> libraries = newPackages[package];
	List<int> data = serialize(component, libraries);
	sink.add(data);
	SerializationGroup newGroup = createGroupFor(libraries, data);
	newPackageGroups[package] = newGroup;
	}

	// Setup dependency tracking for the new groups.
	for (String package in newPackages.keys) {
	List<Library> libraries = newPackages[package];
	SerializationGroup packageGroup = newPackageGroups[package];
	setupDependencyTracking(libraries, packageGroup);
	}

	// All packages have been added to the sink already.
	component.libraries
	..clear()
	..addAll(nonPackageLibraries);
	}

	bool isSelfContained(Component component) {
	Set<Library> got = new Set<Library>.from(component.libraries);
	for (Library lib in component.libraries) {
	for (LibraryDependency dependency in lib.dependencies) {
	if (!got.contains(dependency.targetLibrary)) {
	if (dependency.targetLibrary.importUri.scheme == "dart") {
	continue;
	}
	return false;
	}
	}
	}
	return true;
	}

	/// Remove cached data based on what has been invalidated.
	/// Note that invalidating a single file can remove many cached things because
	/// of dependencies.
	void removeInvalidated() {
	// Remove all directly invalidated entries.
	Set<SerializationGroup> removed = new Set<SerializationGroup>();
	List<SerializationGroup> workList = new List<SerializationGroup>();
	for (Uri uri in invalidatedUris) {
	removeUriFromMap(uri, removed, workList);
	}

	// Continuously remove all that depend on the removed groups.
	//
	// Note that with the current invalidating strategy in the incremental
	// compiler this is not strictly necessary (assuming the incremental
	// compiler is used via the incremental compiler) - but it is included for
	// completeness.
	//
	// The reason we have to do this (assuming a different incremental
	// compiler invalidation strategy), is that we group things into packages,
	// meaning that a group as a whole might depend on another group containing
	// libraries that is not in the input component. Not removing these groups
	// could lead to including a group in an output where we cannot re-create
	// the dependencies. Example:
	// Group #1: [lib1]
	// Group #2: [lib2, lib3]. Note that lib3 depends on lib1, but lib2 is
	// standalone.
	// Lib1 is invalidated and we thus remove group #1.
	// We then serialize something that needs lib2. We thus output group #2.
	// We should now also output group #1, but we don't have it so we can't.
	// We can't re-create it either, because the input component only contains
	// lib2 as it is standalone. Had we removed group #2 too everything would
	// have been fine as we would then just serialize and cached lib2 by itself.
	while (workList.isNotEmpty) {
	SerializationGroup group = workList.removeLast();
	if (group.othersDependingOnMe == null) continue;
	for (SerializationGroup dependsOnGroup in group.othersDependingOnMe) {
	removeUriFromMap(dependsOnGroup.uris.first, removed, workList);
	}
	}

	invalidatedUris.clear();
	}

	/// Setup dependency tracking for a single group having the specified
	/// libraries. Note that all groups this depend on has to be created prior
	/// to calling this.
	void setupDependencyTracking(
	List<Library> libraries, SerializationGroup packageGroup) {
	for (Library lib in libraries) {
	for (LibraryDependency dep in lib.dependencies) {
	Library dependencyLibrary = dep.importedLibraryReference.asLibrary;
	if (dependencyLibrary.importUri.scheme != "package") continue;
	Uri dependencyLibraryUri =
	dep.importedLibraryReference.asLibrary.fileUri;
	SerializationGroup depGroup = uriToGroup[dependencyLibraryUri];
	if (depGroup == null) {
	throw "Didn't contain group for $dependencyLibraryUri";
	}
	if (depGroup == packageGroup) continue;
	packageGroup.registerDependency(depGroup);
	}
	}
	}

	/// Add the group but not its dependencies to the output if they weren't added
	/// already.
	addDataButNotDependentData(SerializationGroup group,
	Set<SerializationGroup> cachedPackagesInOutput, Sink<List<int>> sink) {
	if (cachedPackagesInOutput.add(group)) {
	sink.add(group.serializedData);
	}
	}

	/// Add the group and its dependencies to the output if they weren't added
	/// already.
	addDataAndDependentData(SerializationGroup group,
	Set<SerializationGroup> cachedPackagesInOutput, Sink<List<int>> sink) {
	if (cachedPackagesInOutput.add(group)) {
	sink.add(group.serializedData);
	if (group.dependencies != null) {
	// Now also add all dependencies.
	for (SerializationGroup dep in group.dependencies) {
	addDataAndDependentData(dep, cachedPackagesInOutput, sink);
	}
	}
	}
	}

	/// Create a [SerializationGroup] for the input, setting up [uriToGroup].
	SerializationGroup createGroupFor(List<Library> libraries, List<int> data) {
	Set<Uri> libraryUris = new Set<Uri>();
	for (Library lib in libraries) {
	libraryUris.add(lib.fileUri);
	}

	SerializationGroup newGroup = new SerializationGroup(data, libraryUris);

	for (Uri uri in libraryUris) {
	assert(!uriToGroup.containsKey(uri));
	uriToGroup[uri] = newGroup;
	}
	return newGroup;
	}

	/// Serialize the specified libraries using other needed data from the
	/// component.
	List<int> serialize(Component component, List<Library> libraries) {
	Component singlePackageLibraries = new Component(
	libraries: libraries,
	uriToSource: component.uriToSource,
	nameRoot: component.root);

	ByteSink byteSink = new ByteSink();
	final BinaryPrinter printer = new BinaryPrinter(byteSink);
	printer.writeComponentFile(singlePackageLibraries);
	return byteSink.builder.takeBytes();
	}

	/// Remove the specified uri from the [uriToGroup] map.
	///
	/// Also remove all uris in the group the uri belongs to, and add the group to
	/// the worklist.
	void removeUriFromMap(Uri uri, Set<SerializationGroup> removed,
	List<SerializationGroup> workList) {
	SerializationGroup group = uriToGroup.remove(uri);
	if (group == null) return;
	bool added = removed.add(group);
	assert(added);
	workList.add(group);
	for (Uri groupUri in group.uris) {
	SerializationGroup sameGroup = uriToGroup.remove(groupUri);
	assert((groupUri == uri && sameGroup == null) \|\|
	(groupUri != uri && sameGroup != null));
	}
	}
	}

	class SerializationGroup {
	final List<int> serializedData;
	final Set<Uri> uris;
	Set<SerializationGroup> dependencies;
	Set<SerializationGroup> othersDependingOnMe;

	SerializationGroup(this.serializedData, this.uris);

	/// Register the dependency that this group depends on the [other] one.
	/// The registration is bilateral so that [other] is added as a dependency for
	/// this, and this is added as a "others depend on me" for [other].
	void registerDependency(SerializationGroup other) {
	dependencies ??= new Set<SerializationGroup>.identity();
	if (dependencies.add(other)) {
	other.othersDependingOnMe ??= new Set<SerializationGroup>.identity();
	other.othersDependingOnMe.add(this);
	}
	}
	}