// Copyright 2014 The Flutter Authors. 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:flutter/foundation.dart';
import 'package:flutter/widgets.dart';

/// Provides an iterable that efficiently returns all the elements
/// rooted at the given element. See [CachingIterable] for details.
///
/// This method must be called again if the tree changes. You cannot
/// call this function once, then reuse the iterable after having
/// changed the state of the tree, because the iterable returned by
/// this function caches the results and only walks the tree once.
///
/// The same applies to any iterable obtained indirectly through this
/// one, for example the results of calling `where` on this iterable
/// are also cached.
Iterable<Element> collectAllElementsFrom(
  Element rootElement, {
  required bool skipOffstage,
}) {
  return CachingIterable<Element>(_DepthFirstChildIterator(rootElement, skipOffstage));
}

/// Provides a recursive, efficient, depth first search of an element tree.
///
/// [Element.visitChildren] does not guarnatee order, but does guarnatee stable
/// order. This iterator also guarantees stable order, and iterates in a left
/// to right order:
///
///       1
///     /   \
///    2     3
///   / \   / \
///  4   5 6   7
///
/// Will iterate in order 2, 4, 5, 3, 6, 7.
///
/// Performance is important here because this method is on the critical path
/// for flutter_driver and package:integration_test performance tests.
/// Performance is measured in the all_elements_bench microbenchmark.
/// Any changes to this implementation should check the before and after numbers
/// on that benchmark to avoid regressions in general performance test overhead.
///
/// If we could use RTL order, we could save on performance, but numerous tests
/// have been written (and developers clearly expect) that LTR order will be
/// respected.
class _DepthFirstChildIterator implements Iterator<Element> {
  _DepthFirstChildIterator(Element rootElement, this.skipOffstage) {
    _fillChildren(rootElement);
  }

  final bool skipOffstage;

  late Element _current;

  final List<Element> _stack = <Element>[];

  @override
  Element get current => _current;

  @override
  bool moveNext() {
    if (_stack.isEmpty)
      return false;

    _current = _stack.removeLast();
    _fillChildren(_current);

    return true;
  }

  void _fillChildren(Element element) {
    assert(element != null);
    // If we did not have to follow LTR order and could instead use RTL,
    // we could avoid reversing this and the operation would be measurably
    // faster. Unfortunately, a lot of tests depend on LTR order.
    final List<Element> reversed = <Element>[];
    if (skipOffstage) {
      element.debugVisitOnstageChildren(reversed.add);
    } else {
      element.visitChildren(reversed.add);
    }
    // This is faster than _stack.addAll(reversed.reversed), presumably since
    // we don't actually care about maintaining an iteration pointer.
    while (reversed.isNotEmpty) {
      _stack.add(reversed.removeLast());
    }
  }
}