topologicalSort static method

List<MapperModel> topologicalSort(List<MapperModel> mappers)

Performs a topological sort on mappers to ensure dependencies are processed first.

Returns a list where each mapper either has no dependencies or depends only on mappers that appear earlier in the list. External dependencies (not in the mapper list) are ignored for sorting purposes.

Throws StateError if circular dependencies are detected within the mapper set.

Implementation

static List<MapperModel> topologicalSort(List<MapperModel> mappers) {
  final mapperById = <MapperRef, MapperModel>{
    for (final mapper in mappers) mapper.id: mapper
  };
  final visited = <MapperRef>{};
  final visiting = <MapperRef>{};
  final result = <MapperModel>[];

  void visit(MapperModel mapper) {
    final mapperId = mapper.id;

    if (visited.contains(mapperId)) {
      return; // Already processed
    }

    if (visiting.contains(mapperId)) {
      throw StateError(
          'Circular dependency detected involving mapper ${mapperId.id}. '
          'Dependency chain: ${visiting.map((id) => id.id).join(' -> ')} -> ${mapperId.id}');
    }

    visiting.add(mapperId);

    // Process dependencies that are also in our mapper set
    for (final dependency in mapper.dependencies) {
      if (dependency is MapperDependency) {
        final dependentMapperId = dependency.mapperRef;
        final dependentMapper = mapperById[dependentMapperId];

        // Only process if the dependency is in our mapper set
        if (dependentMapper != null) {
          visit(dependentMapper);
        }
        // If dependency is not in our set, it's external - ignore for sorting
      }
      // External dependencies (non-MapperDependency) are ignored for sorting
    }

    visiting.remove(mapperId);
    visited.add(mapperId);
    result.add(mapper);
  }

  // Visit all mappers to ensure we process all connected components
  for (final mapper in mappers) {
    if (!visited.contains(mapper.id)) {
      visit(mapper);
    }
  }

  return result;
}