Skip to content

Commit 086a6c8

Browse files
authored
[flutter_tools] Fix Use dependency graph to determine plugin initialization order (#191591)
Fixes #99153 ## Summary # Flutter Issue Investigation: #99153 **Issue**: [#99153 - Use dependency graph to determine plugin initialization order](#99153) **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.
1 parent f2a4d12 commit 086a6c8

5 files changed

Lines changed: 273 additions & 13 deletions

File tree

‎dev/devicelab/bin/tasks/plugin_dependencies_test.dart‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -217,10 +217,6 @@ public class DummyPluginAClass {
217217
'"dependencies":[]'
218218
'},'
219219
'{'
220-
'"name":"plugin_a",'
221-
'"dependencies":["plugin_b","plugin_c","plugin_d"]'
222-
'},'
223-
'{'
224220
'"name":"plugin_b",'
225221
'"dependencies":[]'
226222
'},'
@@ -231,6 +227,10 @@ public class DummyPluginAClass {
231227
'{'
232228
'"name":"plugin_d",'
233229
'"dependencies":[]'
230+
'},'
231+
'{'
232+
'"name":"plugin_a",'
233+
'"dependencies":["plugin_b","plugin_c","plugin_d"]'
234234
'}'
235235
']';
236236
final String graphString = json.encode(dependencyGraph);

‎packages/flutter_tools/lib/src/commands/build_swift_package.dart‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -299,7 +299,6 @@ class BuildSwiftPackage extends BuildSubCommand {
299299
}
300300

301301
final List<Plugin> plugins = await findPlugins(project, logger: logger);
302-
plugins.sort((Plugin left, Plugin right) => left.name.compareTo(right.name));
303302
await pluginSwiftDependencies.processPlugins(
304303
cacheDirectory: cacheDirectory,
305304
plugins: plugins,

‎packages/flutter_tools/lib/src/flutter_plugins.dart‎

Lines changed: 73 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -219,7 +219,77 @@ Future<List<Plugin>> findPlugins(
219219
plugins.add(plugin);
220220
}
221221
}
222-
return plugins;
222+
return sortByDependencies(plugins);
223+
}
224+
225+
/// Sorts [plugins] according to their dependency graph so that dependencies
226+
/// are listed before dependent plugins.
227+
///
228+
/// If multiple plugins have no dependency relationship with each other, they are
229+
/// sorted alphabetically by name to keep ordering stable and deterministic.
230+
/// If dependency cycles exist, cycles are broken predictably.
231+
List<Plugin> sortByDependencies(Iterable<Plugin> plugins) {
232+
final pluginMap = <String, Plugin>{for (final Plugin p in plugins) p.name: p};
233+
if (pluginMap.length <= 1) {
234+
return plugins.toList();
235+
}
236+
237+
final inDegree = <String, int>{};
238+
final dependents = <String, List<String>>{
239+
for (final String name in pluginMap.keys) name: <String>[],
240+
};
241+
242+
for (final Plugin p in pluginMap.values) {
243+
final Set<String> directDeps = p.dependencies
244+
.where((String dep) => dep != p.name && pluginMap.containsKey(dep))
245+
.toSet();
246+
inDegree[p.name] = directDeps.length;
247+
for (final dep in directDeps) {
248+
dependents[dep]!.add(p.name);
249+
}
250+
}
251+
252+
final List<String> available =
253+
inDegree.entries
254+
.where((MapEntry<String, int> entry) => entry.value == 0)
255+
.map((MapEntry<String, int> entry) => entry.key)
256+
.toList()
257+
..sort();
258+
259+
final sortedPlugins = <Plugin>[];
260+
final placed = <String>{};
261+
262+
while (placed.length < pluginMap.length) {
263+
if (available.isEmpty) {
264+
// Cycle detected among remaining unplaced plugins.
265+
// Select the unplaced plugin with smallest in-degree, breaking ties alphabetically.
266+
final List<String> unplaced = pluginMap.keys
267+
.where((String k) => !placed.contains(k))
268+
.toList();
269+
unplaced.sort((String a, String b) {
270+
final int degComp = inDegree[a]!.compareTo(inDegree[b]!);
271+
return degComp != 0 ? degComp : a.compareTo(b);
272+
});
273+
available.add(unplaced.first);
274+
}
275+
final String current = available.removeAt(0);
276+
if (placed.add(current)) {
277+
sortedPlugins.add(pluginMap[current]!);
278+
final newlyAvailable = <String>[];
279+
for (final String dependent in dependents[current]!) {
280+
inDegree[dependent] = inDegree[dependent]! - 1;
281+
if (inDegree[dependent] == 0 && !placed.contains(dependent)) {
282+
newlyAvailable.add(dependent);
283+
}
284+
}
285+
if (newlyAvailable.isNotEmpty) {
286+
available.addAll(newlyAvailable);
287+
available.sort();
288+
}
289+
}
290+
}
291+
292+
return sortedPlugins;
223293
}
224294

225295
/// Plugin resolution type to determine the injection mechanism.
@@ -1312,8 +1382,6 @@ Future<void> refreshPluginsList(
13121382
packageGraph: packageGraph,
13131383
packageConfig: packageConfig,
13141384
);
1315-
// Sort the plugins by name to keep ordering stable in generated files.
1316-
plugins.sort((Plugin left, Plugin right) => left.name.compareTo(right.name));
13171385

13181386
var swiftPackageManagerEnabledIos = false;
13191387
var swiftPackageManagerEnabledMacos = false;
@@ -1712,9 +1780,8 @@ _resolvePluginImplementationsByPlatform(
17121780
}
17131781
}
17141782

1715-
// Sort the plugins by name to keep ordering stable in generated files.
1716-
final List<Plugin> pluginImplementations = pluginResolution.values.toList()
1717-
..sort((Plugin left, Plugin right) => left.name.compareTo(right.name));
1783+
// Sort the plugins by dependency order to ensure dependencies are initialized first.
1784+
final List<Plugin> pluginImplementations = sortByDependencies(pluginResolution.values);
17181785
return (pluginImplementations, hasPluginPubspecError, hasResolutionError);
17191786
}
17201787

‎packages/flutter_tools/test/general.shard/macos/darwin_dependency_management_test.dart‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1864,6 +1864,9 @@ class FakePlugin extends Fake implements Plugin {
18641864
@override
18651865
final Map<String, PluginPlatform> platforms;
18661866

1867+
@override
1868+
final List<String> dependencies = const <String>[];
1869+
18671870
@override
18681871
String? get implementsPackage => null;
18691872

‎packages/flutter_tools/test/general.shard/plugins_test.dart‎

Lines changed: 193 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -483,6 +483,43 @@ dependencies:
483483
},
484484
);
485485

486+
testUsingContext(
487+
'Refreshing the plugin list sorts plugins by dependency order',
488+
() async {
489+
createPlugin(
490+
name: 'plugin_b',
491+
platforms: const <String, _PluginPlatformInfo>{
492+
'ios': _PluginPlatformInfo(pluginClass: 'PluginB'),
493+
},
494+
dependencies: <String>['plugin_z'],
495+
);
496+
createPlugin(
497+
name: 'plugin_z',
498+
platforms: const <String, _PluginPlatformInfo>{
499+
'ios': _PluginPlatformInfo(pluginClass: 'PluginZ'),
500+
},
501+
);
502+
503+
iosProject.testExists = true;
504+
505+
await refreshPluginsList(flutterProject);
506+
507+
expect(flutterProject.flutterPluginsDependenciesFile, exists);
508+
509+
final String pluginsFileContents = flutterProject.flutterPluginsDependenciesFile
510+
.readAsStringSync();
511+
expect(
512+
pluginsFileContents.indexOf('plugin_z'),
513+
lessThan(pluginsFileContents.indexOf('plugin_b')),
514+
);
515+
},
516+
overrides: <Type, Generator>{
517+
FileSystem: () => fs,
518+
ProcessManager: () => FakeProcessManager.any(),
519+
Pub: ThrowingPub.new,
520+
},
521+
);
522+
486523
testUsingContext(
487524
'does not crash when a plugin pubspec.yaml is not valid UTF-8',
488525
() async {
@@ -1676,7 +1713,7 @@ flutter:
16761713
);
16771714

16781715
testUsingContext(
1679-
'Generated Linux plugin files sorts by plugin name',
1716+
'Generated Linux plugin files sorts by plugin name when independent',
16801717
() async {
16811718
createFakePlugins(fs, <String>[
16821719
'plugin_d',
@@ -1705,6 +1742,41 @@ flutter:
17051742
},
17061743
);
17071744

1745+
testUsingContext(
1746+
'Generated Linux plugin files sorts by dependency order',
1747+
() async {
1748+
createPlugin(
1749+
name: 'plugin_b',
1750+
platforms: const <String, _PluginPlatformInfo>{
1751+
'linux': _PluginPlatformInfo(pluginClass: 'PluginB'),
1752+
},
1753+
dependencies: <String>['plugin_z'],
1754+
);
1755+
createPlugin(
1756+
name: 'plugin_z',
1757+
platforms: const <String, _PluginPlatformInfo>{
1758+
'linux': _PluginPlatformInfo(pluginClass: 'PluginZ'),
1759+
},
1760+
);
1761+
1762+
await injectPlugins(flutterProject, releaseMode: false, linuxPlatform: true);
1763+
1764+
final File pluginCmakeFile = linuxProject.generatedPluginCmakeFile;
1765+
final File pluginRegistrant = linuxProject.managedDirectory.childFile(
1766+
'generated_plugin_registrant.cc',
1767+
);
1768+
for (final file in <File>[pluginCmakeFile, pluginRegistrant]) {
1769+
final String contents = file.readAsStringSync();
1770+
expect(contents.indexOf('plugin_z'), lessThan(contents.indexOf('plugin_b')));
1771+
}
1772+
},
1773+
overrides: <Type, Generator>{
1774+
FileSystem: () => fs,
1775+
ProcessManager: () => FakeProcessManager.any(),
1776+
Pub: ThrowingPub.new,
1777+
},
1778+
);
1779+
17081780
testUsingContext(
17091781
'Injecting creates generated Windows registrant',
17101782
() async {
@@ -1760,7 +1832,7 @@ flutter:
17601832
);
17611833

17621834
testUsingContext(
1763-
'Generated Windows plugin files sorts by plugin name',
1835+
'Generated Windows plugin files sorts by plugin name when independent',
17641836
() async {
17651837
createFakePlugins(fs, <String>[
17661838
'plugin_d',
@@ -1789,6 +1861,41 @@ flutter:
17891861
},
17901862
);
17911863

1864+
testUsingContext(
1865+
'Generated Windows plugin files sorts by dependency order',
1866+
() async {
1867+
createPlugin(
1868+
name: 'plugin_b',
1869+
platforms: const <String, _PluginPlatformInfo>{
1870+
'windows': _PluginPlatformInfo(pluginClass: 'PluginB'),
1871+
},
1872+
dependencies: <String>['plugin_z'],
1873+
);
1874+
createPlugin(
1875+
name: 'plugin_z',
1876+
platforms: const <String, _PluginPlatformInfo>{
1877+
'windows': _PluginPlatformInfo(pluginClass: 'PluginZ'),
1878+
},
1879+
);
1880+
1881+
await injectPlugins(flutterProject, releaseMode: false, windowsPlatform: true);
1882+
1883+
final File pluginCmakeFile = windowsProject.generatedPluginCmakeFile;
1884+
final File pluginRegistrant = windowsProject.managedDirectory.childFile(
1885+
'generated_plugin_registrant.cc',
1886+
);
1887+
for (final file in <File>[pluginCmakeFile, pluginRegistrant]) {
1888+
final String contents = file.readAsStringSync();
1889+
expect(contents.indexOf('plugin_z'), lessThan(contents.indexOf('plugin_b')));
1890+
}
1891+
},
1892+
overrides: <Type, Generator>{
1893+
FileSystem: () => fs,
1894+
ProcessManager: () => FakeProcessManager.any(),
1895+
Pub: ThrowingPub.new,
1896+
},
1897+
);
1898+
17921899
testUsingContext(
17931900
'Generated plugin CMake files always use posix-style paths',
17941901
() async {
@@ -3358,6 +3465,90 @@ flutter:
33583465
expect(cache.containsKey('file:///pkgs/example_only_plugin/'), isFalse);
33593466
});
33603467
});
3468+
3469+
group('sortByDependencies', () {
3470+
Plugin makePlugin(String name, {List<String> dependencies = const <String>[]}) {
3471+
return Plugin(
3472+
name: name,
3473+
path: '/pkgs/$name',
3474+
platforms: const <String, PluginPlatform>{},
3475+
defaultPackagePlatforms: const <String, String>{},
3476+
pluginDartClassPlatforms: const <String, DartPluginClassAndFilePair>{},
3477+
dependencies: dependencies,
3478+
isDirectDependency: true,
3479+
isDevDependency: false,
3480+
);
3481+
}
3482+
3483+
test('returns empty list when input is empty', () {
3484+
expect(sortByDependencies(<Plugin>[]), isEmpty);
3485+
});
3486+
3487+
test('returns single element list as-is', () {
3488+
final Plugin plugin = makePlugin('plugin_a');
3489+
expect(sortByDependencies(<Plugin>[plugin]), <Plugin>[plugin]);
3490+
});
3491+
3492+
test('sorts independent plugins alphabetically', () {
3493+
final Plugin pluginA = makePlugin('plugin_a');
3494+
final Plugin pluginB = makePlugin('plugin_b');
3495+
final Plugin pluginC = makePlugin('plugin_c');
3496+
3497+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginC, pluginA, pluginB]);
3498+
expect(sorted, <Plugin>[pluginA, pluginB, pluginC]);
3499+
});
3500+
3501+
test('sorts direct dependency before dependent plugin', () {
3502+
// plugin_a depends on plugin_z.
3503+
final Plugin pluginA = makePlugin('plugin_a', dependencies: <String>['plugin_z']);
3504+
final Plugin pluginZ = makePlugin('plugin_z');
3505+
3506+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginA, pluginZ]);
3507+
expect(sorted, <Plugin>[pluginZ, pluginA]);
3508+
});
3509+
3510+
test('sorts multi-level linear dependency chain', () {
3511+
// plugin_a -> plugin_b -> plugin_c
3512+
final Plugin pluginA = makePlugin('plugin_a', dependencies: <String>['plugin_b']);
3513+
final Plugin pluginB = makePlugin('plugin_b', dependencies: <String>['plugin_c']);
3514+
final Plugin pluginC = makePlugin('plugin_c');
3515+
3516+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginA, pluginB, pluginC]);
3517+
expect(sorted, <Plugin>[pluginC, pluginB, pluginA]);
3518+
});
3519+
3520+
test('sorts diamond dependency graph', () {
3521+
// plugin_d depends on plugin_b and plugin_c; plugin_b and plugin_c depend on plugin_a.
3522+
final Plugin pluginA = makePlugin('plugin_a');
3523+
final Plugin pluginB = makePlugin('plugin_b', dependencies: <String>['plugin_a']);
3524+
final Plugin pluginC = makePlugin('plugin_c', dependencies: <String>['plugin_a']);
3525+
final Plugin pluginD = makePlugin('plugin_d', dependencies: <String>['plugin_b', 'plugin_c']);
3526+
3527+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginD, pluginC, pluginB, pluginA]);
3528+
expect(sorted, <Plugin>[pluginA, pluginB, pluginC, pluginD]);
3529+
});
3530+
3531+
test('ignores non-plugin dependencies', () {
3532+
final Plugin pluginA = makePlugin(
3533+
'plugin_a',
3534+
dependencies: <String>['flutter', 'collection', 'plugin_b'],
3535+
);
3536+
final Plugin pluginB = makePlugin('plugin_b', dependencies: <String>['meta']);
3537+
3538+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginA, pluginB]);
3539+
expect(sorted, <Plugin>[pluginB, pluginA]);
3540+
});
3541+
3542+
test('handles dependency cycle deterministically without throwing or hanging', () {
3543+
// plugin_a depends on plugin_b; plugin_b depends on plugin_a.
3544+
final Plugin pluginA = makePlugin('plugin_a', dependencies: <String>['plugin_b']);
3545+
final Plugin pluginB = makePlugin('plugin_b', dependencies: <String>['plugin_a']);
3546+
3547+
final List<Plugin> sorted = sortByDependencies(<Plugin>[pluginB, pluginA]);
3548+
expect(sorted.length, 2);
3549+
expect(sorted.map((Plugin p) => p.name).toSet(), <String>{'plugin_a', 'plugin_b'});
3550+
});
3551+
});
33613552
}
33623553

33633554
class FakeFlutterManifest extends Fake implements FlutterManifest {

0 commit comments

Comments
 (0)