build_runner/lib/src/build_script_generate/builder_ordering.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 'package:build_config/build_config.dart';
import 'package:graphs/graphs.dart';

/// Put [builders] into an order such that any builder which specifies
/// [BuilderDefinition.requiredInputs] will come after any builder which
/// produces a desired output.
///
/// Builders will be ordered such that their `required_inputs` and `runs_before`
/// constraints are met, but the rest of the ordering is arbitrary.
Iterable<BuilderDefinition> findBuilderOrder(
    Iterable<BuilderDefinition> builders) {
  final consistentOrderBuilders = builders.toList()
    ..sort((a, b) => a.key.compareTo(b.key));
  Iterable<BuilderDefinition> dependencies(BuilderDefinition parent) =>
      consistentOrderBuilders.where((child) =>
          _hasInputDependency(parent, child) || _mustRunBefore(parent, child));
  var components = stronglyConnectedComponents<BuilderDefinition>(
    consistentOrderBuilders,
    dependencies,
    equals: (a, b) => a.key == b.key,
    hashCode: (b) => b.key.hashCode,
  );
  return components.map((component) {
    if (component.length > 1) {
      throw ArgumentError('Required input cycle for ${component.toList()}');
    }
    return component.single;
  }).toList();
}

/// Whether [parent] has a `required_input` that wants to read outputs produced
/// by [child].
bool _hasInputDependency(BuilderDefinition parent, BuilderDefinition child) {
  final childOutputs = child.buildExtensions.values.expand((v) => v).toSet();
  return parent.requiredInputs
      .any((input) => childOutputs.any((output) => output.endsWith(input)));
}

/// Whether [child] specifies that it wants to run before [parent].
bool _mustRunBefore(BuilderDefinition parent, BuilderDefinition child) =>
    child.runsBefore.contains(parent.key);