getAllProviderElementsInOrder method Null safety

Iterable<ProviderElementBase> getAllProviderElementsInOrder()

Visit all nodes of the graph at most once, from roots to leaves.

This is fairly expensive and should be avoided as much as possible. If you do not need for providers to be sorted, consider using getAllProviderElements instead, which returns an unsorted list and is significantly faster.

Implementation

Iterable<ProviderElementBase> getAllProviderElementsInOrder() sync* {
  final visitedNodes = HashSet<ProviderElementBase>();
  final queue = DoubleLinkedQueue<ProviderElementBase>();

  // get providers that don't depend on other providers from this container
  for (final reader in _stateReaders.values) {
    if (reader.container != this) continue;
    final element = reader._element;
    if (element == null) continue;

    var hasAncestorsInContainer = false;
    element.visitAncestors((element) {
      // We ignore dependencies that are defined in another container, as
      // they are in a separate graph
      if (element._container == this) {
        hasAncestorsInContainer = true;
      }
    });

    if (!hasAncestorsInContainer) {
      queue.add(element);
    }
  }

  while (queue.isNotEmpty) {
    final element = queue.removeFirst();

    if (!visitedNodes.add(element)) {
      // Already visited
      continue;
    }

    yield element;

    // Queue the children of this element, but only if all of its ancestors
    // were already visited before.
    // If a child does not have all of its ancestors visited, when those
    // ancestors will be visited, they will retry visiting this child.
    element.visitChildren((dependent) {
      if (dependent.container == this) {
        // All the parents of a node must have been visited before a node is visited
        var areAllAncestorsAlreadyVisited = true;
        dependent.visitAncestors((e) {
          if (e._container == this && !visitedNodes.contains(e)) {
            areAllAncestorsAlreadyVisited = false;
          }
        });

        if (areAllAncestorsAlreadyVisited) queue.add(dependent);
      }
    });
  }
}