Compute topologically sorted library cycles.

pkg/front_end/lib/src/incremental/file_state.dart

 // Copyright (c) 2017, 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 'dart:async';
 import 'dart:typed_data';
 
 import 'package:front_end/file_system.dart';
+import 'package:front_end/src/dependency_walker.dart' as graph;
 import 'package:front_end/src/fasta/parser/top_level_parser.dart';
 import 'package:front_end/src/fasta/scanner.dart';
 import 'package:front_end/src/fasta/source/directive_listener.dart';
 import 'package:front_end/src/fasta/translate_uri.dart';
 
 /// Information about a file being compiled, explicitly or implicitly.
 ///
 /// It provides a consistent view on its properties.
 ///
 /// The properties are not guaranteed to represent the most recent state
 /// of the file system. To update the file to the most recent state, [refresh]
 /// should be called.
 class FileState {
   final FileSystemState _fsState;
 
   /// The resolved URI of the file in the file system.
   final Uri fileUri;
 
   bool _exists;
   List<int> _content;
 
   List<FileState> _importedFiles;
   List<FileState> _exportedFiles;
   List<FileState> _partFiles;
 
-  Set<FileState> _directReferencedFiles = new Set<FileState>();
+  List<FileState> _directReferencedLibraries = <FileState>[];
 
   FileState._(this._fsState, this.fileUri);
 
   /// The content of the file.
   List<int> get content => _content;
 
+  /// Libraries that this library file directly imports or exports.
+  List<FileState> get directReferencedLibraries => _directReferencedLibraries;
+
   /// Whether the file exists.
   bool get exists => _exists;
 
+  /// The list of files this file exports.

[Paul Berry, 2017/05/12 14:30:43]

Sould we rename this to exportedLibraries?

[scheglov, 2017/05/12 15:40:58]

Done.

+  List<FileState> get exportedFiles => _exportedFiles;
+
   @override
   int get hashCode => fileUri.hashCode;
 
-  /// Return the set of transitive files - the file itself and all of the
-  /// directly or indirectly referenced files.
-  Set<FileState> get transitiveFiles {
-    // TODO(scheglov) add caching.
-    var transitiveFiles = new Set<FileState>();
+  /// The list of files this file imports.

[Paul Berry, 2017/05/12 14:30:43]

Similar question here

[scheglov, 2017/05/12 15:40:58]

Done.

+  List<FileState> get importedFiles => _importedFiles;
 
-    void appendReferenced(FileState file) {
-      if (transitiveFiles.add(file)) {
-        file._directReferencedFiles.forEach(appendReferenced);
-      }
-    }
+  /// The list of files this library file references as parts.
+  List<FileState> get partFiles => _partFiles;
 
-    appendReferenced(this);
-    return transitiveFiles;
+  /// Return topologically sorted cycles of dependencies for this library.
+  List<LibraryCycle> get topologicalOrder {
+    var libraryWalker = new _LibraryWalker();
+    libraryWalker.walk(libraryWalker.getNode(this));
+    return libraryWalker.topologicallySortedCycles;
   }
 
   @override
   bool operator ==(Object other) {
     return other is FileState && other.fileUri == fileUri;
   }
 
   /// Read the file content and ensure that all of the file properties are
   /// consistent with the read content, including all its dependencies.
   Future<Null> refresh() async {
@@ skipping 20 matching lines @@
     for (String uri in listener.imports) {
       await _addFileForRelativeUri(_importedFiles, uri);
     }
     for (String uri in listener.exports) {
       await _addFileForRelativeUri(_exportedFiles, uri);
     }
     for (String uri in listener.parts) {
       await _addFileForRelativeUri(_partFiles, uri);
     }
 
-    // Compute referenced files.
-    _directReferencedFiles = new Set<FileState>()
-      ..addAll(_importedFiles)
-      ..addAll(_exportedFiles)
-      ..addAll(_partFiles);
+    // Compute referenced libraries.
+    _directReferencedLibraries = (new Set<FileState>()
+          ..addAll(_importedFiles)
+          ..addAll(_exportedFiles))
+        .toList();
+  }
+
+  @override
+  String toString() {
+    if (fileUri.scheme == 'file') return fileUri.path;
+    return fileUri.toString();
   }
 
   /// Add the [FileState] for the given [relativeUri] to the [files].
   /// Do nothing if the URI cannot be parsed, cannot correspond any file, etc.
   Future<Null> _addFileForRelativeUri(
       List<FileState> files, String relativeUri) async {
     if (relativeUri.isEmpty) return;
 
     // Resolve the relative URI into absolute.
     // The result is either:
@@ skipping 55 matching lines @@
       file = new FileState._(this, fileUri);
       _fileUriToFile[fileUri] = file;
 
       // Build the sub-graph of the file.
       await file.refresh();
     }
     return file;
   }
 }
 
+/// List of libraries that reference each other, so form a cycle.
+class LibraryCycle {
+  final List<FileState> libraries = <FileState>[];
+
+  @override
+  String toString() => '[' + libraries.join(', ') + ']';
+}
+
 /// [FileSystemState] based implementation of [FileSystem].
 /// It provides a consistent view on the known file system state.
 class _FileSystemView implements FileSystem {
   final FileSystemState fsState;
 
   _FileSystemView(this.fsState);
 
   @override
   FileSystemEntity entityForUri(Uri uri) {
     FileState file = fsState._fileUriToFile[uri];
@@ skipping 28 matching lines @@
   Future<String> readAsString() async => _shouldNotBeQueried();
 
   /// _FileSystemViewEntry is used by the incremental kernel generator to
   /// provide Fasta with a consistent, race condition free view of the files
   /// constituting the project.  It should only need to be used for reading
   /// file contents.
   dynamic _shouldNotBeQueried() {
     throw new StateError('The method should not be invoked.');
   }
 }
+
+/// Node in [_LibraryWalker].
+class _LibraryNode extends graph.Node<_LibraryNode> {
+  final _LibraryWalker walker;
+  final FileState file;
+
+  @override
+  bool isEvaluated = false;
+
+  _LibraryNode(this.walker, this.file);
+
+  @override
+  List<_LibraryNode> computeDependencies() {
+    return file.directReferencedLibraries.map(walker.getNode).toList();
+  }
+}
+
+/// Helper that organizes dependencies of a library into topologically
+/// sorted [LibraryCycle]s.
+class _LibraryWalker extends graph.DependencyWalker<_LibraryNode> {
+  final nodesOfFiles = <FileState, _LibraryNode>{};
+  final topologicallySortedCycles = <LibraryCycle>[];
+
+  @override
+  void evaluate(_LibraryNode v) {
+    evaluateScc([v]);
+  }
+
+  @override
+  void evaluateScc(List<_LibraryNode> scc) {
+    var cycle = new LibraryCycle();
+    for (var node in scc) {
+      node.isEvaluated = true;
+      cycle.libraries.add(node.file);
+    }
+    topologicallySortedCycles.add(cycle);
+  }
+
+  _LibraryNode getNode(FileState file) {
+    return nodesOfFiles.putIfAbsent(file, () => new _LibraryNode(this, file));
+  }
+}