// Copyright (c) 2015, 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 'dart:async';
import 'dart:collection';

import 'package:analyzer/exception/exception.dart';
import 'package:analyzer/src/context/cache.dart';
import 'package:analyzer/src/generated/engine.dart';
import 'package:analyzer/src/generated/resolver.dart';
import 'package:analyzer/src/generated/utilities_general.dart';
import 'package:analyzer/src/task/api/model.dart';
import 'package:analyzer/src/task/inputs.dart';
import 'package:analyzer/src/task/manager.dart';

final PerformanceTag analysisDriverProcessOutputs =
    _taskDriverTag.createChild('processOutputs');

final PerformanceTag workOrderMoveNextPerformanceTag =
    _taskDriverTag.createChild('workOrderMoveNext');

final PerformanceTag _taskDriverTag =
    PerformanceStatistics.analyzer.createChild('taskDriver');

/**
 * An object that is used to cause analysis to be performed until all of the
 * required analysis information has been computed.
 */
class AnalysisDriver {
  /**
   * The task manager used to figure out how to compute analysis results.
   */
  final TaskManager taskManager;

  /**
   * The list of [WorkManager] used to figure out which analysis results to
   * compute.
   */
  final List<WorkManager> workManagers;

  /**
   * The context in which analysis is to be performed.
   */
  final InternalAnalysisContext context;

  /**
   * The map of [ResultChangedEvent] controllers.
   */
  final Map<ResultDescriptor, StreamController<ResultChangedEvent>>
      resultComputedControllers =
      <ResultDescriptor, StreamController<ResultChangedEvent>>{};

  /**
   * The work order that was previously computed but that has not yet been
   * completed.
   */
  WorkOrder currentWorkOrder;

  /**
   * Indicates whether any tasks are currently being performed (or building
   * their inputs).  In debug builds, we use this to ensure that tasks don't
   * try to make use of the task manager in reentrant fashion.
   */
  bool isTaskRunning = false;

  /**
   * The controller that is notified when a task is started.
   */
  StreamController<AnalysisTask> _onTaskStartedController;

  /**
   * The controller that is notified when a task is complete.
   */
  StreamController<AnalysisTask> _onTaskCompletedController;

  /**
   * Initialize a newly created driver to use the tasks know to the given
   * [taskManager] to perform analysis in the given [context].
   */
  AnalysisDriver(this.taskManager, this.workManagers, this.context) {
    _onTaskStartedController = new StreamController.broadcast();
    _onTaskCompletedController = new StreamController.broadcast();
  }

  /**
   * The stream that is notified when a task is complete.
   */
  Stream<AnalysisTask> get onTaskCompleted => _onTaskCompletedController.stream;

  /**
   * The stream that is notified when a task is started.
   */
  Stream<AnalysisTask> get onTaskStarted => _onTaskStartedController.stream;

  /**
   * Perform work until the given [result] has been computed for the given
   * [target]. Return the last [AnalysisTask] that was performed.
   */
  AnalysisTask computeResult(AnalysisTarget target, ResultDescriptor result) {
    assert(!isTaskRunning);
    try {
      isTaskRunning = true;
      AnalysisTask task;
      while (true) {
        try {
          WorkOrder workOrder = createWorkOrderForResult(target, result);
          if (workOrder != null) {
            while (workOrder.moveNext()) {
              task = performWorkItem(workOrder.current);
            }
          }
          break;
        } on ModificationTimeMismatchError {
          // Cache inconsistency was detected and fixed by invalidating
          // corresponding results in cache. Computation must be restarted.
        }
      }
      return task;
    } finally {
      isTaskRunning = false;
    }
  }

  /**
   * Return the work order describing the work that should be getting worked on,
   * or `null` if there is currently no work to be done.
   */
  WorkOrder createNextWorkOrder() {
    while (true) {
      // Find the WorkManager with the highest priority.
      WorkOrderPriority highestPriority = null;
      WorkManager highestManager = null;
      for (WorkManager manager in workManagers) {
        WorkOrderPriority priority = manager.getNextResultPriority();
        if (highestPriority == null || highestPriority.index > priority.index) {
          highestPriority = priority;
          highestManager = manager;
        }
      }
      // Nothing to do.
      if (highestPriority == WorkOrderPriority.NONE) {
        return null;
      }
      // Create a new WorkOrder.
      TargetedResult request = highestManager.getNextResult();
//      print('request: $request');
      if (request != null) {
        WorkOrder workOrder =
            createWorkOrderForResult(request.target, request.result);
        if (workOrder != null) {
          return workOrder;
        }
      }
    }
  }

  /**
   * Create a work order that will produce the given [result] for the given
   * [target]. Return the work order that was created, or `null` if the result
   * has either already been computed or cannot be computed.
   */
  WorkOrder createWorkOrderForResult(
      AnalysisTarget target, ResultDescriptor result) {
    CacheEntry entry = context.getCacheEntry(target);
    CacheState state = entry.getState(result);
    if (state == CacheState.VALID ||
        state == CacheState.ERROR ||
        state == CacheState.IN_PROCESS) {
      return null;
    }
    if (context.aboutToComputeResult(entry, result)) {
      return null;
    }
    TaskDescriptor taskDescriptor = taskManager.findTask(target, result);
    if (taskDescriptor == null) {
      return null;
    }
    try {
      WorkItem workItem =
          new WorkItem(context, target, taskDescriptor, result, 0, null);
      return new WorkOrder(taskManager, workItem);
    } catch (exception, stackTrace) {
      throw new AnalysisException(
          'Could not create work order (target = $target; taskDescriptor = $taskDescriptor; result = $result)',
          new CaughtException(exception, stackTrace));
    }
  }

  /**
   * Create a work order that will produce the required analysis results for
   * the given [target]. If [isPriority] is true, then the target is a priority
   * target. Return the work order that was created, or `null` if there is no
   * further work that needs to be done for the given target.
   */
  WorkOrder createWorkOrderForTarget(AnalysisTarget target, bool isPriority) {
    for (ResultDescriptor result in taskManager.generalResults) {
      WorkOrder workOrder = createWorkOrderForResult(target, result);
      if (workOrder != null) {
        return workOrder;
      }
    }
    if (isPriority) {
      for (ResultDescriptor result in taskManager.priorityResults) {
        WorkOrder workOrder = createWorkOrderForResult(target, result);
        if (workOrder != null) {
          return workOrder;
        }
      }
    }
    return null;
  }

  /**
   * Return the stream that is notified when a new value for the given
   * [descriptor] is computed.
   */
  Stream<ResultChangedEvent> onResultComputed(ResultDescriptor descriptor) {
    return resultComputedControllers.putIfAbsent(descriptor, () {
      return new StreamController<ResultChangedEvent>.broadcast(sync: true);
    }).stream;
  }

  /**
   * Perform the next analysis task, and return `true` if there is more work to
   * be done in order to compute all of the required analysis information.
   */
  bool performAnalysisTask() {
    //
    // TODO(brianwilkerson) This implementation does not allow us to prioritize
    // work across contexts. What we need is a way for an external client to ask
    // to have all priority files analyzed for each context, then ask for normal
    // files to be analyzed. There are a couple of ways to do this.
    //
    // First, we could add a "bool priorityOnly" parameter to this method and
    // return null here when it is true.
    //
    // Second, we could add a concept of a priority order and (externally) run
    // through the priorities from highest to lowest. That would be a nice
    // generalization of the previous idea, but it isn't clear that we need the
    // generality.
    //
    // Third, we could move performAnalysisTask and createNextWorkOrder to an
    // object that knows about all sources in all contexts, so that instead of
    // the client choosing a context and telling it do to some work, the client
    // simply says "do some work", and the engine chooses the best thing to do
    // next regardless of what context it's in.
    //
    assert(!isTaskRunning);
    try {
      isTaskRunning = true;
      if (currentWorkOrder == null) {
        currentWorkOrder = createNextWorkOrder();
      } else if (currentWorkOrder.moveNext()) {
        try {
          performWorkItem(currentWorkOrder.current);
        } on ModificationTimeMismatchError {
          reset();
          return true;
        }
      } else {
        currentWorkOrder = createNextWorkOrder();
      }
      return currentWorkOrder != null;
    } finally {
      isTaskRunning = false;
    }
  }

  /**
   * Perform the given work item.
   * Return the performed [AnalysisTask].
   */
  AnalysisTask performWorkItem(WorkItem item) {
    if (item.exception != null) {
      // Mark all of the results that the task would have computed as being in
      // ERROR with the exception recorded on the work item.
      CacheEntry targetEntry = context.getCacheEntry(item.target);
      targetEntry.setErrorState(item.exception, item.descriptor.results);
      return null;
    }
    // Otherwise, perform the task.
    AnalysisTask task = item.buildTask();
    _onTaskStartedController.add(task);
    task.perform();
    analysisDriverProcessOutputs.makeCurrentWhile(() {
      AnalysisTarget target = task.target;
      CacheEntry entry = context.getCacheEntry(target);
      if (task.caughtException == null) {
        List<TargetedResult> dependedOn =
            context.analysisOptions.trackCacheDependencies
                ? item.inputTargetedResults.toList()
                : const <TargetedResult>[];
        Map<ResultDescriptor, dynamic> outputs = task.outputs;
        List<ResultDescriptor> results = task.descriptor.results;
        int resultLength = results.length;
        for (int i = 0; i < resultLength; i++) {
          ResultDescriptor result = results[i];
          // TODO(brianwilkerson) We could check here that a value was produced
          // and throw an exception if not (unless we want to allow null values).
          entry.setValue(result, outputs[result], dependedOn);
        }
        outputs.forEach((ResultDescriptor descriptor, value) {
          StreamController<ResultChangedEvent> controller =
              resultComputedControllers[descriptor];
          if (controller != null) {
            ResultChangedEvent event = new ResultChangedEvent(
                context, target, descriptor, value, true);
            controller.add(event);
          }
        });
        for (WorkManager manager in workManagers) {
          manager.resultsComputed(target, outputs);
        }
      } else {
        entry.setErrorState(task.caughtException, item.descriptor.results);
      }
    });
    _onTaskCompletedController.add(task);
    return task;
  }

  /**
   * Reset the state of the driver in response to a change in the state of one
   * or more analysis targets. This will cause any analysis that was currently
   * in process to be stopped and for analysis to resume based on the new state.
   */
  void reset() {
    currentWorkOrder = null;
  }
}

/**
 * Generic dependency walker suitable for use in the analysis task driver.
 * This class implements a variant of the path-based strong component algorithm
 * (described here: http://www.cs.colorado.edu/~hal/Papers/DFS/ipl.ps.gz), with
 * the following differences:
 *
 * - The algorithm is non-recursive so that it can be used in a coroutine
 *   fashion (each call to [getNextStronglyConnectedComponent] computes a
 *   single strongly connected component and then waits to be called again)
 *
 * - Instead of keeping a temporary array which maps nodes to their locations
 *   in the [path] array, we simply search the array when necessary.  This
 *   allows us to begin finding strongly connected components without having to
 *   know the size of the whole graph.
 *
 * - This algorithm does not compute all strongly connected components; only
 *   those reachable from the starting point which are as yet unevaluated.
 *
 * The algorithm, in essence, is to traverse the dependency graph in
 * depth-first fashion from a starting node.  If the path from the starting
 * node ever encounters the same node twice, then a cycle has been found, and
 * all the nodes comprising the cycle are (conceptually) contracted into a
 * single node.  The algorithm yields possibly-collapsed nodes in proper
 * topological sort order (all the dependencies of a node are yielded before,
 * or in the same contracted component as, the node itself).
 */
abstract class CycleAwareDependencyWalker<Node> {
  /**
   * The path through the dependency graph that is currently being considered,
   * with un-collapsed nodes.
   */
  final List<Node> _path;

  /**
   * For each node in [_path], a list of the unevaluated nodes which it is
   * already known to depend on.
   */
  final List<List<Node>> _provisionalDependencies;

  /**
   * Indices into [_path] of the nodes which begin a new strongly connected
   * component, in order.  The first index in [_contractedPath] is always 0.
   *
   * For all i < contractedPath.length - 1, at least one node in the strongly
   * connected component represented by [contractedPath[i]] depends directly
   * on at least one node in the strongly connected component represented by
   * [contractedPath[i+1]].
   */
  final List<int> _contractedPath;

  /**
   * Index into [_path] of the nodes which we are currently in the process of
   * querying for their dependencies.
   *
   * [currentIndices.last] always refers to a member of the last strongly
   * connected component indicated by [_contractedPath].
   */
  final List<int> _currentIndices;

  /**
   * Begin walking dependencies starting at [startingNode].
   */
  CycleAwareDependencyWalker(Node startingNode)
      : _path = <Node>[startingNode],
        _provisionalDependencies = <List<Node>>[<Node>[]],
        _contractedPath = <int>[0],
        _currentIndices = <int>[0];

  /**
   * Determine the next unevaluated input for [node], skipping any inputs in
   * [skipInputs], and return it.  If [node] has no further inputs, return
   * `null`.
   */
  Node getNextInput(Node node, List<Node> skipInputs);

  /**
   * Determine the next strongly connected component in the graph, and return
   * it.  The client is expected to evaluate this component before calling
   * [getNextStronglyConnectedComponent] again.
   */
  StronglyConnectedComponent<Node> getNextStronglyConnectedComponent() {
    while (_currentIndices.isNotEmpty) {
      Node nextUnevaluatedInput = getNextInput(_path[_currentIndices.last],
          _provisionalDependencies[_currentIndices.last]);
      // If the assertion below fails, it indicates that [getNextInput] did not
      // skip an input that we asked it to skip.
      assert(!_provisionalDependencies[_currentIndices.last]
          .contains(nextUnevaluatedInput));
      if (nextUnevaluatedInput != null) {
        // TODO(paulberry): the call to _path.indexOf makes the algorithm
        // O(n^2) in the depth of the dependency graph.  If this becomes a
        // problem, consider maintaining a map from node to index.
        int previousIndex = _path.indexOf(nextUnevaluatedInput);
        if (previousIndex != -1) {
          // Update contractedPath to indicate that all nodes in the path
          // between previousIndex and currentIndex are part of the same
          // strongly connected component.
          while (_contractedPath.last > previousIndex) {
            _contractedPath.removeLast();
          }
          // Store nextUnevaluatedInput as a provisional dependency so that we
          // can move on to computing other dependencies.
          _provisionalDependencies[_currentIndices.last]
              .add(nextUnevaluatedInput);
          // And loop to move on to the node's next input.
          continue;
        } else {
          // This is a brand new input and there's no reason (yet) to believe
          // that it is in the same strongly connected component as any other
          // node, so push it onto the end of the path.
          int newIndex = _path.length;
          _path.add(nextUnevaluatedInput);
          _provisionalDependencies.add(<Node>[]);
          _contractedPath.add(newIndex);
          _currentIndices.add(newIndex);
          // And loop to move on to the new node's inputs.
          continue;
        }
      } else {
        // The node has no more inputs.  Figure out if there are any more nodes
        // in the current strongly connected component that need to have their
        // indices examined.
        _currentIndices.removeLast();
        if (_currentIndices.isEmpty ||
            _currentIndices.last < _contractedPath.last) {
          // No more nodes in the current strongly connected component need to
          // have their indices examined.  We can now yield this component to
          // the caller.
          List<Node> nodes = _path.sublist(_contractedPath.last);
          bool containsCycle = nodes.length > 1;
          if (!containsCycle) {
            if (_provisionalDependencies.last.isNotEmpty) {
              containsCycle = true;
            }
          }
          _path.length = _contractedPath.last;
          _provisionalDependencies.length = _contractedPath.last;
          _contractedPath.removeLast();
          return new StronglyConnectedComponent<Node>(nodes, containsCycle);
        } else {
          // At least one node in the current strongly connected component
          // still needs to have its inputs examined.  So loop and allow the
          // inputs to be examined.
          continue;
        }
      }
    }
    // No further strongly connected components found.
    return null;
  }
}

/**
 * A place to define the behaviors that need to be added to
 * [InternalAnalysisContext].
 */
abstract class ExtendedAnalysisContext implements InternalAnalysisContext {
  List<AnalysisTarget> get explicitTargets;
  List<AnalysisTarget> get priorityTargets;
  void set typeProvider(TypeProvider typeProvider);
  CacheEntry getCacheEntry(AnalysisTarget target);
}

/**
 * An exception indicating that an attempt was made to perform a task on a
 * target while gathering the inputs to perform the same task for the same
 * target.
 */
class InfiniteTaskLoopException extends AnalysisException {
  /**
   * A concrete cyclic path of [TargetedResults] within the [dependencyCycle],
   * `null` if no such path exists.  All nodes in the path are in the
   * dependencyCycle, but the path is not guaranteed to cover the
   * entire cycle.
   */
  final List<TargetedResult> cyclicPath;

  /**
   * If a dependency cycle was found while computing the inputs for the task,
   * the set of [WorkItem]s contained in the cycle (if there are overlapping
   * cycles, this is the set of all [WorkItem]s in the entire strongly
   * connected component).  Otherwise, `null`.
   */
  final List<WorkItem> dependencyCycle;

  /**
   * Initialize a newly created exception to represent a failed attempt to
   * perform the given [task] due to the given [dependencyCycle].
   */
  InfiniteTaskLoopException(AnalysisTask task, List<WorkItem> dependencyCycle,
      [List<TargetedResult> cyclicPath])
      : this.dependencyCycle = dependencyCycle,
        this.cyclicPath = cyclicPath,
        super(_composeMessage(task, dependencyCycle, cyclicPath));

  /**
   * Compose an error message based on the data we have available.
   */
  static String _composeMessage(AnalysisTask task,
      List<WorkItem> dependencyCycle, List<TargetedResult> cyclicPath) {
    StringBuffer buffer = new StringBuffer();
    buffer.write('Infinite loop while performing task ');
    buffer.write(task.descriptor.name);
    buffer.write(' for ');
    buffer.writeln(task.target);
    buffer.writeln('  Dependency Cycle:');
    for (WorkItem item in dependencyCycle) {
      buffer.write('    ');
      buffer.writeln(item);
    }
    if (cyclicPath != null) {
      buffer.writeln('  Cyclic Path:');
      for (TargetedResult result in cyclicPath) {
        buffer.write('    ');
        buffer.writeln(result);
      }
    }
    return buffer.toString();
  }
}

/**
 * Object used by [CycleAwareDependencyWalker] to report a single strongly
 * connected component of nodes.
 */
class StronglyConnectedComponent<Node> {
  /**
   * The nodes contained in the strongly connected component.
   */
  final List<Node> nodes;

  /**
   * Indicates whether the strongly component contains any cycles.  Note that
   * if [nodes] has multiple elements, this will always be `true`.  However, if
   * [nodes] has exactly one element, this may be either `true` or `false`
   * depending on whether the node has a dependency on itself.
   */
  final bool containsCycle;

  StronglyConnectedComponent(this.nodes, this.containsCycle);
}

/**
 * A description of a single analysis task that can be performed to advance
 * analysis.
 */
class WorkItem {
  /**
   * The context in which the task will be performed.
   */
  final InternalAnalysisContext context;

  /**
   * The target for which a task is to be performed.
   */
  final AnalysisTarget target;

  /**
   * A description of the task to be performed.
   */
  final TaskDescriptor descriptor;

  /**
   * The [ResultDescriptor] which was led to this work item being spawned.
   */
  final ResultDescriptor spawningResult;

  /**
   * The level of this item in its [WorkOrder].
   */
  final int level;

  /**
   * The work order that this item is part of, may be `null`.
   */
  WorkOrder workOrder;

  /**
   * An iterator used to iterate over the descriptors of the inputs to the task,
   * or `null` if all of the inputs have been collected and the task can be
   * created.
   */
  TopLevelTaskInputBuilder builder;

  /**
   * The [TargetedResult]s outputs of this task depends on.
   */
  final HashSet<TargetedResult> inputTargetedResults =
      new HashSet<TargetedResult>();

  /**
   * The inputs to the task that have been computed.
   */
  Map<String, dynamic> inputs = const <String, dynamic>{};

  /**
   * The exception that was found while trying to populate the inputs. If this
   * field is non-`null`, then the task cannot be performed and all of the
   * results that this task would have computed need to be marked as being in
   * ERROR with this exception.
   */
  CaughtException exception = null;

  /**
   * If a dependency cycle was found while computing the inputs for the task,
   * the set of [WorkItem]s contained in the cycle (if there are overlapping
   * cycles, this is the set of all [WorkItem]s in the entire strongly
   * connected component).  Otherwise, `null`.
   */
  List<WorkItem> dependencyCycle;

  /**
   * Initialize a newly created work item to compute the inputs for the task
   * described by the given descriptor.
   */
  WorkItem(this.context, this.target, this.descriptor, this.spawningResult,
      this.level, this.workOrder) {
    AnalysisTarget actualTarget =
        identical(target, AnalysisContextTarget.request)
            ? new AnalysisContextTarget(context)
            : target;
//    print('${'\t' * level}$spawningResult of $actualTarget');
    Map<String, TaskInput> inputDescriptors =
        descriptor.createTaskInputs(actualTarget);
    builder = new TopLevelTaskInputBuilder(inputDescriptors);
    if (!builder.moveNext()) {
      builder = null;
    }
  }

  @override
  int get hashCode =>
      JenkinsSmiHash.hash2(descriptor.hashCode, target.hashCode);

  @override
  bool operator ==(other) {
    if (other is WorkItem) {
      return this.descriptor == other.descriptor && this.target == other.target;
    } else {
      return false;
    }
  }

  /**
   * Build the task represented by this work item.
   */
  AnalysisTask buildTask() {
    if (builder != null) {
      throw new StateError("some inputs have not been computed");
    }
    AnalysisTask task = descriptor.createTask(context, target, inputs);
    task.dependencyCycle = dependencyCycle;
    return task;
  }

  /**
   * Gather all of the inputs needed to perform the task.
   *
   * If at least one of the inputs have not yet been computed, return a work
   * item that can be used to generate that input to indicate that the caller
   * should perform the returned item's task before returning to gathering
   * inputs for this item's task.
   *
   * If all of the inputs have been gathered, return `null` to indicate that the
   * client should build and perform the task. A value of `null` will also be
   * returned if some of the inputs cannot be computed and the task cannot be
   * performed. Callers can differentiate between these cases by checking the
   * [exception] field. If the field is `null`, then the task can be performed;
   * if the field is non-`null` then the task cannot be performed and all of the
   * tasks' results should be marked as being in ERROR.
   */
  WorkItem gatherInputs(TaskManager taskManager, List<WorkItem> skipInputs) {
    while (builder != null) {
      AnalysisTarget inputTarget = builder.currentTarget;
      ResultDescriptor inputResult = builder.currentResult;

      // TODO(scheglov) record information to debug
      // https://github.com/dart-lang/sdk/issues/24939
      if (inputTarget == null || inputResult == null) {
        try {
          String message =
              'Invalid input descriptor ($inputTarget, $inputResult) for $this';
          if (workOrder != null) {
            message += '\nPath:\n' + workOrder.workItems.join('|\n');
          }
          throw new AnalysisException(message);
        } catch (exception, stackTrace) {
          this.exception = new CaughtException(exception, stackTrace);
          AnalysisEngine.instance.logger
              .logError('Task failed: $this', this.exception);
        }
        return null;
      }

      inputTargetedResults.add(new TargetedResult(inputTarget, inputResult));
      CacheEntry inputEntry = context.getCacheEntry(inputTarget);
      CacheState inputState = inputEntry.getState(inputResult);
      if (inputState == CacheState.ERROR) {
        exception = inputEntry.exception;
        return null;
      } else if (inputState == CacheState.IN_PROCESS) {
        //
        // TODO(brianwilkerson) Implement this case.
        //
        // One possibility would be to return a WorkItem that would perform a
        // no-op task in order to cause us to come back to this work item on the
        // next iteration. It would be more efficient, in general, to push this
        // input onto a waiting list and proceed to the next input so that work
        // could proceed, but given that the only result that can currently be
        // IN_PROCESS is CONTENT, I don't know that it's worth the extra effort
        // to implement the general solution at this point.
        //
        throw new UnimplementedError();
      } else if (inputState != CacheState.VALID) {
        if (context.aboutToComputeResult(inputEntry, inputResult)) {
          inputState = CacheState.VALID;
          builder.currentValue = inputEntry.getValue(inputResult);
        } else {
          try {
            TaskDescriptor descriptor =
                taskManager.findTask(inputTarget, inputResult);
            if (descriptor == null) {
              throw new AnalysisException(
                  'Cannot find task to build $inputResult for $inputTarget');
            }
            if (skipInputs.any((WorkItem item) =>
                item.target == inputTarget && item.descriptor == descriptor)) {
              // This input is being skipped due to a circular dependency.  Tell
              // the builder that it's not available so we can move on to other
              // inputs.
              builder.currentValueNotAvailable();
            } else {
              return new WorkItem(context, inputTarget, descriptor, inputResult,
                  level + 1, workOrder);
            }
          } on AnalysisException catch (exception, stackTrace) {
            this.exception = new CaughtException(exception, stackTrace);
            return null;
          } catch (exception, stackTrace) {
            this.exception = new CaughtException(exception, stackTrace);
            throw new AnalysisException(
                'Cannot create work order to build $inputResult for $inputTarget',
                this.exception);
          }
        }
      } else {
        builder.currentValue = inputEntry.getValue(inputResult);
        if (builder.flushOnAccess) {
          inputEntry.setState(inputResult, CacheState.FLUSHED);
        }
      }
      if (!builder.moveNext()) {
        inputs = builder.inputValue;
        builder = null;
      }
    }
    return null;
  }

  @override
  String toString() => 'Run $descriptor on $target';
}

/**
 * A description of the work to be done to compute a desired analysis result.
 * The class implements a lazy depth-first traversal of the work item's input.
 */
class WorkOrder implements Iterator<WorkItem> {
  /**
   * The dependency walker which is being used to determine what work to do
   * next.
   */
  final _WorkOrderDependencyWalker _dependencyWalker;

  /**
   * The strongly connected component most recently returned by
   * [_dependencyWalker], minus any [WorkItem]s that the iterator has already
   * moved past.
   *
   * Null if the [_dependencyWalker] hasn't been used yet.
   */
  List<WorkItem> currentItems;

  /**
   * Initialize a newly created work order to compute the result described by
   * the given work item.
   */
  WorkOrder(TaskManager taskManager, WorkItem item)
      : _dependencyWalker = new _WorkOrderDependencyWalker(taskManager, item) {
    item.workOrder = this;
  }

  @override
  WorkItem get current {
    if (currentItems == null) {
      return null;
    } else {
      return currentItems.last;
    }
  }

  List<WorkItem> get workItems => _dependencyWalker._path;

  @override
  bool moveNext() {
    return workOrderMoveNextPerformanceTag.makeCurrentWhile(() {
      if (currentItems != null && currentItems.length > 1) {
        // Yield more items.
        currentItems.removeLast();
        return true;
      } else {
        // Get a new strongly connected component.
        StronglyConnectedComponent<WorkItem> nextStronglyConnectedComponent =
            _dependencyWalker.getNextStronglyConnectedComponent();
        if (nextStronglyConnectedComponent == null) {
          currentItems = null;
          return false;
        }
        currentItems = nextStronglyConnectedComponent.nodes;
        if (nextStronglyConnectedComponent.containsCycle) {
          // A cycle has been found.
          for (WorkItem item in currentItems) {
            item.dependencyCycle = currentItems.toList();
          }
        } else {
          assert(currentItems.length == 1);
        }
        return true;
      }
    });
  }
}

/**
 * Specialization of [CycleAwareDependencyWalker] for use by [WorkOrder].
 */
class _WorkOrderDependencyWalker extends CycleAwareDependencyWalker<WorkItem> {
  /**
   * The task manager used to build work items.
   */
  final TaskManager taskManager;

  _WorkOrderDependencyWalker(this.taskManager, WorkItem startingNode)
      : super(startingNode);

  @override
  WorkItem getNextInput(WorkItem node, List<WorkItem> skipInputs) {
    return node.gatherInputs(taskManager, skipInputs);
  }
}