// 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.

library analyzer.src.task.driver;

import 'dart:async';
import 'dart:collection';

import 'package:analyzer/src/context/cache.dart';
import 'package:analyzer/src/generated/engine.dart'
    hide AnalysisTask, AnalysisContextImpl, WorkManager;
import 'package:analyzer/src/generated/java_engine.dart';
import 'package:analyzer/src/generated/resolver.dart';
import 'package:analyzer/src/generated/utilities_general.dart';
import 'package:analyzer/src/task/inputs.dart';
import 'package:analyzer/src/task/manager.dart';
import 'package:analyzer/task/model.dart';

final PerformanceTag workOrderMoveNextPerfTag =
    new PerformanceTag('WorkOrder.moveNext');

/**
 * 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 [ComputedResult] controllers.
   */
  final Map<ResultDescriptor,
          StreamController<ComputedResult>> resultComputedControllers =
      <ResultDescriptor, StreamController<ComputedResult>>{};

  /**
   * 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;
      WorkOrder workOrder = createWorkOrderForResult(target, result);
      if (workOrder != null) {
        while (workOrder.moveNext()) {
//          AnalysisTask previousTask = task;
//          String message = workOrder.current.toString();
          task = performWorkItem(workOrder.current);
//          if (task == null) {
//            throw new AnalysisException(message, previousTask.caughtException);
//          }
        }
      }
      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 already been 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;
    }
    TaskDescriptor taskDescriptor = taskManager.findTask(target, result);
    try {
      WorkItem workItem = new WorkItem(context, target, taskDescriptor, result);
      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<ComputedResult> onResultComputed(ResultDescriptor descriptor) {
    return resultComputedControllers
        .putIfAbsent(descriptor,
            () => new StreamController<ComputedResult>.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 implementaiton 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()) {
        performWorkItem(currentWorkOrder.current);
      } 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();
    AnalysisTarget target = task.target;
    CacheEntry entry = context.getCacheEntry(target);
    if (task.caughtException == null) {
      List<TargetedResult> dependedOn = item.inputTargetedResults.toList();
      Map<ResultDescriptor, dynamic> outputs = task.outputs;
      for (ResultDescriptor result in task.descriptor.results) {
        // 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<ComputedResult> controller =
            resultComputedControllers[descriptor];
        if (controller != null) {
          ComputedResult event =
              new ComputedResult(context, descriptor, target, value);
          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]);
      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 {
  /**
   * 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, this.dependencyCycle)
      : super(
            'Infinite loop while performing task ${task.descriptor.name} for ${task.target}');
}

/**
 * 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 anaysis 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;

  /**
   * 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.
   */
  TaskInputBuilder 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;

  /**
   * 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) {
    AnalysisTarget actualTarget =
        identical(target, AnalysisContextTarget.request)
            ? new AnalysisContextTarget(context)
            : target;
    Map<String, TaskInput> inputDescriptors =
        descriptor.createTaskInputs(actualTarget);
    builder = new TopLevelTaskInputBuilder(inputDescriptors);
    if (!builder.moveNext()) {
      builder = null;
    }
    inputs = new HashMap<String, dynamic>();
  }

  @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;
      inputTargetedResults.add(new TargetedResult(inputTarget, inputResult));
      CacheEntry inputEntry = context.getCacheEntry(inputTarget);
      CacheState inputState = inputEntry.getState(inputResult);
      if (skipInputs.any((WorkItem item) =>
          item.target == inputTarget && item.spawningResult == inputResult)) {
        // 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 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) {
        try {
          TaskDescriptor descriptor =
              taskManager.findTask(inputTarget, inputResult);
          return new WorkItem(context, inputTarget, descriptor, inputResult);
        } on AnalysisException catch (exception, stackTrace) {
          this.exception = new CaughtException(exception, stackTrace);
          return null;
        }
      } else {
        builder.currentValue = inputEntry.getValue(inputResult);
      }
      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);

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

  @override
  bool moveNext() {
    return workOrderMoveNextPerfTag.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;
      }
    });
  }
}

/**
 * Specilaization 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);
  }
}