Properly handle circular references among constants in the task model.

pkg/analyzer/lib/src/task/driver.dart

 // 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';
@@ skipping 131 matching lines @@
       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;
     }
     try {
       TaskDescriptor taskDescriptor = taskManager.findTask(target, result);
-      WorkItem workItem = new WorkItem(context, target, taskDescriptor);
+      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; result = $result)',
           new CaughtException(exception, stackTrace));
     }
   }
 
   /**
    * Create a work order that will produce the required analysis results for
@@ skipping 182 matching lines @@
 
   /**
    * Determine the next strongly connected component in the graph, and return
    * it.  The client is expected to evaluate this component before calling
    * [getNextStronglyConnectedComponent] again.
    */
   List<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) {
@@ skipping 56 matching lines @@
   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 {
   /**
-   * Initialize a newly created exception to represent an attempt to perform
-   * the task for the target represented by the given [item].
+   * 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`.
    */
-  InfiniteTaskLoopException(WorkItem item) : super(
-          'Infinite loop while performing task ${item.descriptor.name} for ${item.target}');
+  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}');
 }
 
 /**
  * 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) {
+  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;
     }
@@ skipping 13 matching lines @@
     }
   }
 
   /**
    * Build the task represented by this work item.
    */
   AnalysisTask buildTask() {
     if (builder != null) {
       throw new StateError("some inputs have not been computed");
     }
-    return descriptor.createTask(context, target, inputs);
+    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) {
+  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 (inputState == CacheState.ERROR) {
+      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);
+          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);
       }
-      builder.currentValue = inputEntry.getValue(inputResult);
       if (!builder.moveNext()) {
         inputs = builder.inputValue;
         builder = null;
       }
     }
     return null;
   }
 
   @override
   String toString() => 'Run $descriptor on $target';
 }
 
 /**
- * The priorities of work orders returned by [WorkManager]s.
- */
-enum WorkOrderPriority {
-  /**
-   * Responding to an user's action.
-   */
-  INTERACTIVE,
-
-  /**
-   * Computing information for priority sources.
-   */
-  PRIORITY,
-
-  /**
-   * A work should be done, but without any special urgency.
-   */
-  NORMAL,
-
-  /**
-   * Nothing to do.
-   */
-  NONE
-}
-
-/**
  * [AnalysisDriver] uses [WorkManager]s to select results to compute.
  *
  * They know specific of the targets and results they care about,
  * so they can request analysis results in optimal order.
  */
 abstract class WorkManager {
   /**
    * Notifies the managers that the given set of priority [targets] was set.
    */
   void applyPriorityTargets(List<AnalysisTarget> targets);
@@ skipping 66 matching lines @@
       return true;
     } else {
       // Get a new strongly connected component.
       currentItems = _dependencyWalker.getNextStronglyConnectedComponent();
       if (currentItems == null) {
         return false;
       }
       if (currentItems.length > 1) {
         // A cycle has been found.
         for (WorkItem item in currentItems) {
-          try {
-            throw new InfiniteTaskLoopException(item);
-          } on InfiniteTaskLoopException catch (exception, stackTrace) {
-            item.exception = new CaughtException(exception, stackTrace);
-          }
+          item.dependencyCycle = currentItems.toList();
         }
       } else {
         assert(currentItems.length == 1);
       }
       return true;
     }
   }
 }
 
 /**
+ * The priorities of work orders returned by [WorkManager]s.
+ */
+enum WorkOrderPriority {
+  /**
+   * Responding to an user's action.
+   */
+  INTERACTIVE,
+
+  /**
+   * Computing information for priority sources.
+   */
+  PRIORITY,
+
+  /**
+   * A work should be done, but without any special urgency.
+   */
+  NORMAL,
+
+  /**
+   * Nothing to do.
+   */
+  NONE
+}
+
+/**
  * 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) {
-    if (skipInputs.isNotEmpty) {
-      // TODO(paulberry): this is a hack.  We assume that an analysis loop has
-      // been found, so we don't try to compute anything else.
-      return null;
-    }
-    return node.gatherInputs(taskManager);
+    return node.gatherInputs(taskManager, skipInputs);
   }
 }