Reverts: [flutter_tools] Fix Use dependency graph to determine plugin initialization order

Initiated by: @cbracken

Reason for reverting: broke Linux analyzer_benchmark and Linux analyze

Original PR Author: @bkonyi

Reviewed By: @vashworth

The original PR description is provided below:

Fixes #99153

Summary

Flutter Issue Investigation: #99153

Issue: #99153 - Use dependency graph to determine plugin initialization order
Status: Resolved
Scope: packages/flutter_tools

1. Overview and Problem Statement

When Flutter generates native plugin registrants (such as GeneratedPluginRegistrant.java, GeneratedPluginRegistrant.m, generated_plugin_registrant.cc, web_plugin_registrant.dart) and plugin dependency files (.flutter-plugins-dependencies), plugins were previously sorted purely alphabetically by plugin name (left.name.compareTo(right.name)).

While alphabetical sorting ensured deterministic registrant generation, it did not take into account dependencies between plugins. If plugin_a depended on plugin_z, plugin_a would be registered and initialized before plugin_z, leading to potential initialization order bugs when a plugin depends on services or state initialized by another plugin.

2. Root Cause Analysis

1. findPlugins & refreshPluginsList:
   • findPlugins collected plugins in arbitrary traversal order from computeTransitiveDependencies.
   • refreshPluginsList sorted plugins alphabetically (plugins.sort((Plugin left, Plugin right) => left.name.compareTo(right.name));).
2. _resolvePluginImplementationsByPlatform:
   • Platform implementation candidate resolution re-sorted the platform-specific plugins alphabetically (pluginImplementations.sort((Plugin left, Plugin right) => left.name.compareTo(right.name));), overriding any topological order.
3. _writeFlutterPluginsList and Registrant Generators:
   • Iterated over the sorted lists and wrote registrations directly to disk.

3. Solution & Architecture

Topological Sort (sortByDependencies)

Implemented sortByDependencies(Iterable<Plugin> plugins) in packages/flutter_tools/lib/src/flutter_plugins.dart:

• Uses Kahn's algorithm for topological sorting:
  1. Computes in-degree for all plugins within the set of active plugins based on plugin.dependencies. Non-plugin dependencies (e.g., flutter, meta, external packages) are filtered out.
  2. Seeds available queue with plugins having 0 in-degree, sorted alphabetically.
  3. Dequeues plugins and decrements dependent plugins' in-degrees. When in-degree reaches 0, dependent plugins are added to the available queue (alphabetically sorted).
  4. If a dependency cycle occurs, the algorithm breaks cycles deterministically by selecting the unplaced plugin with the smallest in-degree, breaking ties alphabetically.
  5. For independent plugins with no dependency relationships, preserves alphabetical sorting.

Call Site Updates

• Updated findPlugins to return sortByDependencies(plugins).
• Updated _resolvePluginImplementationsByPlatform to sort platform implementations using sortByDependencies(pluginResolution.values).
• Removed redundant plugins.sort in refreshPluginsList and packages/flutter_tools/lib/src/commands/build_swift_package.dart.

4. Automated Testing and Verification

Regression & Unit Tests Added

• Refreshing the plugin list sorts plugins by dependency order in packages/flutter_tools/test/general.shard/plugins_test.dart.
• group('sortByDependencies') in plugins_test.dart:
  • returns empty list when input is empty
  • returns single element list as-is
  • sorts independent plugins alphabetically
  • sorts direct dependency before dependent plugin
  • sorts multi-level linear dependency chain
  • sorts diamond dependency graph
  • ignores non-plugin dependencies
  • handles dependency cycle deterministically without throwing or hanging
• Registrant Injection Tests:
  • Generated Linux plugin files sorts by dependency order
  • Generated Windows plugin files sorts by dependency order

Verification Results

• dart format cleanly applied across all modified files.
• dart analyze --fatal-infos packages/flutter_tools: Passed with 0 errors, 0 warnings, 0 infos.
• dart test packages/flutter_tools/test/general.shard/plugins_test.dart: All 97 tests passing.

Verification

• Regression test included and verified.