| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library analyzer.src.task.driver; | |
| 6 | |
| 7 import 'dart:async'; | |
| 8 import 'dart:collection'; | |
| 9 | |
| 10 import 'package:analyzer/src/context/cache.dart'; | |
| 11 import 'package:analyzer/src/generated/engine.dart' | |
| 12 hide AnalysisTask, AnalysisContextImpl; | |
| 13 import 'package:analyzer/src/generated/java_engine.dart'; | |
| 14 import 'package:analyzer/src/generated/resolver.dart'; | |
| 15 import 'package:analyzer/src/generated/utilities_general.dart'; | |
| 16 import 'package:analyzer/src/task/inputs.dart'; | |
| 17 import 'package:analyzer/src/task/manager.dart'; | |
| 18 import 'package:analyzer/task/model.dart'; | |
| 19 | |
| 20 final PerformanceTag workOrderMoveNextPerfTag = | |
| 21 new PerformanceTag('WorkOrder.moveNext'); | |
| 22 | |
| 23 /** | |
| 24 * An object that is used to cause analysis to be performed until all of the | |
| 25 * required analysis information has been computed. | |
| 26 */ | |
| 27 class AnalysisDriver { | |
| 28 /** | |
| 29 * The task manager used to figure out how to compute analysis results. | |
| 30 */ | |
| 31 final TaskManager taskManager; | |
| 32 | |
| 33 /** | |
| 34 * The list of [WorkManager] used to figure out which analysis results to | |
| 35 * compute. | |
| 36 */ | |
| 37 final List<WorkManager> workManagers; | |
| 38 | |
| 39 /** | |
| 40 * The context in which analysis is to be performed. | |
| 41 */ | |
| 42 final InternalAnalysisContext context; | |
| 43 | |
| 44 /** | |
| 45 * The map of [ComputedResult] controllers. | |
| 46 */ | |
| 47 final Map<ResultDescriptor, StreamController<ComputedResult>> resultComputedCo
ntrollers = | |
| 48 <ResultDescriptor, StreamController<ComputedResult>>{}; | |
| 49 | |
| 50 /** | |
| 51 * The work order that was previously computed but that has not yet been | |
| 52 * completed. | |
| 53 */ | |
| 54 WorkOrder currentWorkOrder; | |
| 55 | |
| 56 /** | |
| 57 * Indicates whether any tasks are currently being performed (or building | |
| 58 * their inputs). In debug builds, we use this to ensure that tasks don't | |
| 59 * try to make use of the task manager in reentrant fashion. | |
| 60 */ | |
| 61 bool isTaskRunning = false; | |
| 62 | |
| 63 /** | |
| 64 * The controller that is notified when a task is started. | |
| 65 */ | |
| 66 StreamController<AnalysisTask> _onTaskStartedController; | |
| 67 | |
| 68 /** | |
| 69 * The controller that is notified when a task is complete. | |
| 70 */ | |
| 71 StreamController<AnalysisTask> _onTaskCompletedController; | |
| 72 | |
| 73 /** | |
| 74 * Initialize a newly created driver to use the tasks know to the given | |
| 75 * [taskManager] to perform analysis in the given [context]. | |
| 76 */ | |
| 77 AnalysisDriver(this.taskManager, this.workManagers, this.context) { | |
| 78 _onTaskStartedController = new StreamController.broadcast(); | |
| 79 _onTaskCompletedController = new StreamController.broadcast(); | |
| 80 } | |
| 81 | |
| 82 /** | |
| 83 * The stream that is notified when a task is complete. | |
| 84 */ | |
| 85 Stream<AnalysisTask> get onTaskCompleted => _onTaskCompletedController.stream; | |
| 86 | |
| 87 /** | |
| 88 * The stream that is notified when a task is started. | |
| 89 */ | |
| 90 Stream<AnalysisTask> get onTaskStarted => _onTaskStartedController.stream; | |
| 91 | |
| 92 /** | |
| 93 * Perform work until the given [result] has been computed for the given | |
| 94 * [target]. Return the last [AnalysisTask] that was performed. | |
| 95 */ | |
| 96 AnalysisTask computeResult(AnalysisTarget target, ResultDescriptor result) { | |
| 97 assert(!isTaskRunning); | |
| 98 try { | |
| 99 isTaskRunning = true; | |
| 100 AnalysisTask task; | |
| 101 WorkOrder workOrder = createWorkOrderForResult(target, result); | |
| 102 if (workOrder != null) { | |
| 103 while (workOrder.moveNext()) { | |
| 104 task = performWorkItem(workOrder.current); | |
| 105 } | |
| 106 } | |
| 107 return task; | |
| 108 } finally { | |
| 109 isTaskRunning = false; | |
| 110 } | |
| 111 } | |
| 112 | |
| 113 /** | |
| 114 * Return the work order describing the work that should be getting worked on, | |
| 115 * or `null` if there is currently no work to be done. | |
| 116 */ | |
| 117 WorkOrder createNextWorkOrder() { | |
| 118 while (true) { | |
| 119 // Find the WorkManager with the highest priority. | |
| 120 WorkOrderPriority highestPriority = null; | |
| 121 WorkManager highestManager = null; | |
| 122 for (WorkManager manager in workManagers) { | |
| 123 WorkOrderPriority priority = manager.getNextResultPriority(); | |
| 124 if (highestPriority == null || highestPriority.index > priority.index) { | |
| 125 highestPriority = priority; | |
| 126 highestManager = manager; | |
| 127 } | |
| 128 } | |
| 129 // Nothing to do. | |
| 130 if (highestPriority == WorkOrderPriority.NONE) { | |
| 131 return null; | |
| 132 } | |
| 133 // Create a new WorkOrder. | |
| 134 TargetedResult request = highestManager.getNextResult(); | |
| 135 // print('request: $request'); | |
| 136 if (request != null) { | |
| 137 WorkOrder workOrder = | |
| 138 createWorkOrderForResult(request.target, request.result); | |
| 139 if (workOrder != null) { | |
| 140 return workOrder; | |
| 141 } | |
| 142 } | |
| 143 } | |
| 144 } | |
| 145 | |
| 146 /** | |
| 147 * Create a work order that will produce the given [result] for the given | |
| 148 * [target]. Return the work order that was created, or `null` if the result | |
| 149 * has already been computed. | |
| 150 */ | |
| 151 WorkOrder createWorkOrderForResult( | |
| 152 AnalysisTarget target, ResultDescriptor result) { | |
| 153 CacheEntry entry = context.getCacheEntry(target); | |
| 154 CacheState state = entry.getState(result); | |
| 155 if (state == CacheState.VALID || | |
| 156 state == CacheState.ERROR || | |
| 157 state == CacheState.IN_PROCESS) { | |
| 158 return null; | |
| 159 } | |
| 160 TaskDescriptor taskDescriptor = taskManager.findTask(target, result); | |
| 161 try { | |
| 162 WorkItem workItem = new WorkItem(context, target, taskDescriptor, result); | |
| 163 return new WorkOrder(taskManager, workItem); | |
| 164 } catch (exception, stackTrace) { | |
| 165 throw new AnalysisException( | |
| 166 'Could not create work order (target = $target; taskDescriptor = $task
Descriptor; result = $result)', | |
| 167 new CaughtException(exception, stackTrace)); | |
| 168 } | |
| 169 } | |
| 170 | |
| 171 /** | |
| 172 * Create a work order that will produce the required analysis results for | |
| 173 * the given [target]. If [isPriority] is true, then the target is a priority | |
| 174 * target. Return the work order that was created, or `null` if there is no | |
| 175 * further work that needs to be done for the given target. | |
| 176 */ | |
| 177 WorkOrder createWorkOrderForTarget(AnalysisTarget target, bool isPriority) { | |
| 178 for (ResultDescriptor result in taskManager.generalResults) { | |
| 179 WorkOrder workOrder = createWorkOrderForResult(target, result); | |
| 180 if (workOrder != null) { | |
| 181 return workOrder; | |
| 182 } | |
| 183 } | |
| 184 if (isPriority) { | |
| 185 for (ResultDescriptor result in taskManager.priorityResults) { | |
| 186 WorkOrder workOrder = createWorkOrderForResult(target, result); | |
| 187 if (workOrder != null) { | |
| 188 return workOrder; | |
| 189 } | |
| 190 } | |
| 191 } | |
| 192 return null; | |
| 193 } | |
| 194 | |
| 195 /** | |
| 196 * Return the stream that is notified when a new value for the given | |
| 197 * [descriptor] is computed. | |
| 198 */ | |
| 199 Stream<ComputedResult> onResultComputed(ResultDescriptor descriptor) { | |
| 200 return resultComputedControllers.putIfAbsent(descriptor, () => | |
| 201 new StreamController<ComputedResult>.broadcast(sync: true)).stream; | |
| 202 } | |
| 203 | |
| 204 /** | |
| 205 * Perform the next analysis task, and return `true` if there is more work to | |
| 206 * be done in order to compute all of the required analysis information. | |
| 207 */ | |
| 208 bool performAnalysisTask() { | |
| 209 // | |
| 210 // TODO(brianwilkerson) This implementaiton does not allow us to prioritize | |
| 211 // work across contexts. What we need is a way for an external client to ask | |
| 212 // to have all priority files analyzed for each context, then ask for normal | |
| 213 // files to be analyzed. There are a couple of ways to do this. | |
| 214 // | |
| 215 // First, we could add a "bool priorityOnly" parameter to this method and | |
| 216 // return null here when it is true. | |
| 217 // | |
| 218 // Second, we could add a concept of a priority order and (externally) run | |
| 219 // through the priorities from highest to lowest. That would be a nice | |
| 220 // generalization of the previous idea, but it isn't clear that we need the | |
| 221 // generality. | |
| 222 // | |
| 223 // Third, we could move performAnalysisTask and createNextWorkOrder to an | |
| 224 // object that knows about all sources in all contexts, so that instead of | |
| 225 // the client choosing a context and telling it do to some work, the client | |
| 226 // simply says "do some work", and the engine chooses the best thing to do | |
| 227 // next regardless of what context it's in. | |
| 228 // | |
| 229 assert(!isTaskRunning); | |
| 230 try { | |
| 231 isTaskRunning = true; | |
| 232 if (currentWorkOrder == null) { | |
| 233 currentWorkOrder = createNextWorkOrder(); | |
| 234 } else if (currentWorkOrder.moveNext()) { | |
| 235 performWorkItem(currentWorkOrder.current); | |
| 236 } else { | |
| 237 currentWorkOrder = createNextWorkOrder(); | |
| 238 } | |
| 239 return currentWorkOrder != null; | |
| 240 } finally { | |
| 241 isTaskRunning = false; | |
| 242 } | |
| 243 } | |
| 244 | |
| 245 /** | |
| 246 * Perform the given work item. | |
| 247 * Return the performed [AnalysisTask]. | |
| 248 */ | |
| 249 AnalysisTask performWorkItem(WorkItem item) { | |
| 250 if (item.exception != null) { | |
| 251 // Mark all of the results that the task would have computed as being in | |
| 252 // ERROR with the exception recorded on the work item. | |
| 253 CacheEntry targetEntry = context.getCacheEntry(item.target); | |
| 254 targetEntry.setErrorState(item.exception, item.descriptor.results); | |
| 255 return null; | |
| 256 } | |
| 257 // Otherwise, perform the task. | |
| 258 AnalysisTask task = item.buildTask(); | |
| 259 _onTaskStartedController.add(task); | |
| 260 task.perform(); | |
| 261 AnalysisTarget target = task.target; | |
| 262 CacheEntry entry = context.getCacheEntry(target); | |
| 263 if (task.caughtException == null) { | |
| 264 List<TargetedResult> dependedOn = item.inputTargetedResults.toList(); | |
| 265 Map<ResultDescriptor, dynamic> outputs = task.outputs; | |
| 266 for (ResultDescriptor result in task.descriptor.results) { | |
| 267 // TODO(brianwilkerson) We could check here that a value was produced | |
| 268 // and throw an exception if not (unless we want to allow null values). | |
| 269 entry.setValue(result, outputs[result], dependedOn); | |
| 270 } | |
| 271 outputs.forEach((ResultDescriptor descriptor, value) { | |
| 272 StreamController<ComputedResult> controller = | |
| 273 resultComputedControllers[descriptor]; | |
| 274 if (controller != null) { | |
| 275 ComputedResult event = | |
| 276 new ComputedResult(context, descriptor, target, value); | |
| 277 controller.add(event); | |
| 278 } | |
| 279 }); | |
| 280 for (WorkManager manager in workManagers) { | |
| 281 manager.resultsComputed(target, outputs); | |
| 282 } | |
| 283 } else { | |
| 284 entry.setErrorState(task.caughtException, item.descriptor.results); | |
| 285 } | |
| 286 _onTaskCompletedController.add(task); | |
| 287 return task; | |
| 288 } | |
| 289 | |
| 290 /** | |
| 291 * Reset the state of the driver in response to a change in the state of one | |
| 292 * or more analysis targets. This will cause any analysis that was currently | |
| 293 * in process to be stopped and for analysis to resume based on the new state. | |
| 294 */ | |
| 295 void reset() { | |
| 296 currentWorkOrder = null; | |
| 297 } | |
| 298 } | |
| 299 | |
| 300 /** | |
| 301 * Generic dependency walker suitable for use in the analysis task driver. | |
| 302 * This class implements a variant of the path-based strong component algorithm | |
| 303 * (described here: http://www.cs.colorado.edu/~hal/Papers/DFS/ipl.ps.gz), with | |
| 304 * the following differences: | |
| 305 * | |
| 306 * - The algorithm is non-recursive so that it can be used in a coroutine | |
| 307 * fashion (each call to [getNextStronglyConnectedComponent] computes a | |
| 308 * single strongly connected component and then waits to be called again) | |
| 309 * | |
| 310 * - Instead of keeping a temporary array which maps nodes to their locations | |
| 311 * in the [path] array, we simply search the array when necessary. This | |
| 312 * allows us to begin finding strongly connected components without having to | |
| 313 * know the size of the whole graph. | |
| 314 * | |
| 315 * - This algorithm does not compute all strongly connected components; only | |
| 316 * those reachable from the starting point which are as yet unevaluated. | |
| 317 * | |
| 318 * The algorithm, in essence, is to traverse the dependency graph in | |
| 319 * depth-first fashion from a starting node. If the path from the starting | |
| 320 * node ever encounters the same node twice, then a cycle has been found, and | |
| 321 * all the nodes comprising the cycle are (conceptually) contracted into a | |
| 322 * single node. The algorithm yields possibly-collapsed nodes in proper | |
| 323 * topological sort order (all the dependencies of a node are yielded before, | |
| 324 * or in the same contracted component as, the node itself). | |
| 325 */ | |
| 326 abstract class CycleAwareDependencyWalker<Node> { | |
| 327 /** | |
| 328 * The path through the dependency graph that is currently being considered, | |
| 329 * with un-collapsed nodes. | |
| 330 */ | |
| 331 final List<Node> _path; | |
| 332 | |
| 333 /** | |
| 334 * For each node in [_path], a list of the unevaluated nodes which it is | |
| 335 * already known to depend on. | |
| 336 */ | |
| 337 final List<List<Node>> _provisionalDependencies; | |
| 338 | |
| 339 /** | |
| 340 * Indices into [_path] of the nodes which begin a new strongly connected | |
| 341 * component, in order. The first index in [_contractedPath] is always 0. | |
| 342 * | |
| 343 * For all i < contractedPath.length - 1, at least one node in the strongly | |
| 344 * connected component represented by [contractedPath[i]] depends directly | |
| 345 * on at least one node in the strongly connected component represented by | |
| 346 * [contractedPath[i+1]]. | |
| 347 */ | |
| 348 final List<int> _contractedPath; | |
| 349 | |
| 350 /** | |
| 351 * Index into [_path] of the nodes which we are currently in the process of | |
| 352 * querying for their dependencies. | |
| 353 * | |
| 354 * [currentIndices.last] always refers to a member of the last strongly | |
| 355 * connected component indicated by [_contractedPath]. | |
| 356 */ | |
| 357 final List<int> _currentIndices; | |
| 358 | |
| 359 /** | |
| 360 * Begin walking dependencies starting at [startingNode]. | |
| 361 */ | |
| 362 CycleAwareDependencyWalker(Node startingNode) | |
| 363 : _path = <Node>[startingNode], | |
| 364 _provisionalDependencies = <List<Node>>[<Node>[]], | |
| 365 _contractedPath = <int>[0], | |
| 366 _currentIndices = <int>[0]; | |
| 367 | |
| 368 /** | |
| 369 * Determine the next unevaluated input for [node], skipping any inputs in | |
| 370 * [skipInputs], and return it. If [node] has no further inputs, return | |
| 371 * `null`. | |
| 372 */ | |
| 373 Node getNextInput(Node node, List<Node> skipInputs); | |
| 374 | |
| 375 /** | |
| 376 * Determine the next strongly connected component in the graph, and return | |
| 377 * it. The client is expected to evaluate this component before calling | |
| 378 * [getNextStronglyConnectedComponent] again. | |
| 379 */ | |
| 380 StronglyConnectedComponent<Node> getNextStronglyConnectedComponent() { | |
| 381 while (_currentIndices.isNotEmpty) { | |
| 382 Node nextUnevaluatedInput = getNextInput(_path[_currentIndices.last], | |
| 383 _provisionalDependencies[_currentIndices.last]); | |
| 384 assert(!_provisionalDependencies[_currentIndices.last] | |
| 385 .contains(nextUnevaluatedInput)); | |
| 386 if (nextUnevaluatedInput != null) { | |
| 387 // TODO(paulberry): the call to _path.indexOf makes the algorithm | |
| 388 // O(n^2) in the depth of the dependency graph. If this becomes a | |
| 389 // problem, consider maintaining a map from node to index. | |
| 390 int previousIndex = _path.indexOf(nextUnevaluatedInput); | |
| 391 if (previousIndex != -1) { | |
| 392 // Update contractedPath to indicate that all nodes in the path | |
| 393 // between previousIndex and currentIndex are part of the same | |
| 394 // strongly connected component. | |
| 395 while (_contractedPath.last > previousIndex) { | |
| 396 _contractedPath.removeLast(); | |
| 397 } | |
| 398 // Store nextUnevaluatedInput as a provisional dependency so that we | |
| 399 // can move on to computing other dependencies. | |
| 400 _provisionalDependencies[_currentIndices.last] | |
| 401 .add(nextUnevaluatedInput); | |
| 402 // And loop to move on to the node's next input. | |
| 403 continue; | |
| 404 } else { | |
| 405 // This is a brand new input and there's no reason (yet) to believe | |
| 406 // that it is in the same strongly connected component as any other | |
| 407 // node, so push it onto the end of the path. | |
| 408 int newIndex = _path.length; | |
| 409 _path.add(nextUnevaluatedInput); | |
| 410 _provisionalDependencies.add(<Node>[]); | |
| 411 _contractedPath.add(newIndex); | |
| 412 _currentIndices.add(newIndex); | |
| 413 // And loop to move on to the new node's inputs. | |
| 414 continue; | |
| 415 } | |
| 416 } else { | |
| 417 // The node has no more inputs. Figure out if there are any more nodes | |
| 418 // in the current strongly connected component that need to have their | |
| 419 // indices examined. | |
| 420 _currentIndices.removeLast(); | |
| 421 if (_currentIndices.isEmpty || | |
| 422 _currentIndices.last < _contractedPath.last) { | |
| 423 // No more nodes in the current strongly connected component need to | |
| 424 // have their indices examined. We can now yield this component to | |
| 425 // the caller. | |
| 426 List<Node> nodes = _path.sublist(_contractedPath.last); | |
| 427 bool containsCycle = nodes.length > 1; | |
| 428 if (!containsCycle) { | |
| 429 if (_provisionalDependencies.last.isNotEmpty) { | |
| 430 containsCycle = true; | |
| 431 } | |
| 432 } | |
| 433 _path.length = _contractedPath.last; | |
| 434 _provisionalDependencies.length = _contractedPath.last; | |
| 435 _contractedPath.removeLast(); | |
| 436 return new StronglyConnectedComponent<Node>(nodes, containsCycle); | |
| 437 } else { | |
| 438 // At least one node in the current strongly connected component | |
| 439 // still needs to have its inputs examined. So loop and allow the | |
| 440 // inputs to be examined. | |
| 441 continue; | |
| 442 } | |
| 443 } | |
| 444 } | |
| 445 // No further strongly connected components found. | |
| 446 return null; | |
| 447 } | |
| 448 } | |
| 449 | |
| 450 /** | |
| 451 * A place to define the behaviors that need to be added to | |
| 452 * [InternalAnalysisContext]. | |
| 453 */ | |
| 454 abstract class ExtendedAnalysisContext implements InternalAnalysisContext { | |
| 455 List<AnalysisTarget> get explicitTargets; | |
| 456 List<AnalysisTarget> get priorityTargets; | |
| 457 void set typeProvider(TypeProvider typeProvider); | |
| 458 CacheEntry getCacheEntry(AnalysisTarget target); | |
| 459 } | |
| 460 | |
| 461 /** | |
| 462 * An exception indicating that an attempt was made to perform a task on a | |
| 463 * target while gathering the inputs to perform the same task for the same | |
| 464 * target. | |
| 465 */ | |
| 466 class InfiniteTaskLoopException extends AnalysisException { | |
| 467 /** | |
| 468 * If a dependency cycle was found while computing the inputs for the task, | |
| 469 * the set of [WorkItem]s contained in the cycle (if there are overlapping | |
| 470 * cycles, this is the set of all [WorkItem]s in the entire strongly | |
| 471 * connected component). Otherwise, `null`. | |
| 472 */ | |
| 473 final List<WorkItem> dependencyCycle; | |
| 474 | |
| 475 /** | |
| 476 * Initialize a newly created exception to represent a failed attempt to | |
| 477 * perform the given [task] due to the given [dependencyCycle]. | |
| 478 */ | |
| 479 InfiniteTaskLoopException(AnalysisTask task, this.dependencyCycle) : super( | |
| 480 'Infinite loop while performing task ${task.descriptor.name} for ${tas
k.target}'); | |
| 481 } | |
| 482 | |
| 483 /** | |
| 484 * Object used by CycleAwareDependencyWalker to report a single strongly | |
| 485 * connected component of nodes. | |
| 486 */ | |
| 487 class StronglyConnectedComponent<Node> { | |
| 488 /** | |
| 489 * The nodes contained in the strongly connected component. | |
| 490 */ | |
| 491 final List<Node> nodes; | |
| 492 | |
| 493 /** | |
| 494 * Indicates whether the strongly component contains any cycles. Note that | |
| 495 * if [nodes] has multiple elements, this will always be `true`. However, if | |
| 496 * [nodes] has exactly one element, this may be either `true` or `false` | |
| 497 * depending on whether the node has a dependency on itself. | |
| 498 */ | |
| 499 final bool containsCycle; | |
| 500 | |
| 501 StronglyConnectedComponent(this.nodes, this.containsCycle); | |
| 502 } | |
| 503 | |
| 504 /** | |
| 505 * A description of a single anaysis task that can be performed to advance | |
| 506 * analysis. | |
| 507 */ | |
| 508 class WorkItem { | |
| 509 /** | |
| 510 * The context in which the task will be performed. | |
| 511 */ | |
| 512 final InternalAnalysisContext context; | |
| 513 | |
| 514 /** | |
| 515 * The target for which a task is to be performed. | |
| 516 */ | |
| 517 final AnalysisTarget target; | |
| 518 | |
| 519 /** | |
| 520 * A description of the task to be performed. | |
| 521 */ | |
| 522 final TaskDescriptor descriptor; | |
| 523 | |
| 524 /** | |
| 525 * The [ResultDescriptor] which was led to this work item being spawned. | |
| 526 */ | |
| 527 final ResultDescriptor spawningResult; | |
| 528 | |
| 529 /** | |
| 530 * An iterator used to iterate over the descriptors of the inputs to the task, | |
| 531 * or `null` if all of the inputs have been collected and the task can be | |
| 532 * created. | |
| 533 */ | |
| 534 TaskInputBuilder builder; | |
| 535 | |
| 536 /** | |
| 537 * The [TargetedResult]s outputs of this task depends on. | |
| 538 */ | |
| 539 final HashSet<TargetedResult> inputTargetedResults = | |
| 540 new HashSet<TargetedResult>(); | |
| 541 | |
| 542 /** | |
| 543 * The inputs to the task that have been computed. | |
| 544 */ | |
| 545 Map<String, dynamic> inputs; | |
| 546 | |
| 547 /** | |
| 548 * The exception that was found while trying to populate the inputs. If this | |
| 549 * field is non-`null`, then the task cannot be performed and all of the | |
| 550 * results that this task would have computed need to be marked as being in | |
| 551 * ERROR with this exception. | |
| 552 */ | |
| 553 CaughtException exception = null; | |
| 554 | |
| 555 /** | |
| 556 * If a dependency cycle was found while computing the inputs for the task, | |
| 557 * the set of [WorkItem]s contained in the cycle (if there are overlapping | |
| 558 * cycles, this is the set of all [WorkItem]s in the entire strongly | |
| 559 * connected component). Otherwise, `null`. | |
| 560 */ | |
| 561 List<WorkItem> dependencyCycle; | |
| 562 | |
| 563 /** | |
| 564 * Initialize a newly created work item to compute the inputs for the task | |
| 565 * described by the given descriptor. | |
| 566 */ | |
| 567 WorkItem(this.context, this.target, this.descriptor, this.spawningResult) { | |
| 568 AnalysisTarget actualTarget = identical( | |
| 569 target, AnalysisContextTarget.request) | |
| 570 ? new AnalysisContextTarget(context) | |
| 571 : target; | |
| 572 Map<String, TaskInput> inputDescriptors = | |
| 573 descriptor.createTaskInputs(actualTarget); | |
| 574 builder = new TopLevelTaskInputBuilder(inputDescriptors); | |
| 575 if (!builder.moveNext()) { | |
| 576 builder = null; | |
| 577 } | |
| 578 inputs = new HashMap<String, dynamic>(); | |
| 579 } | |
| 580 | |
| 581 @override | |
| 582 int get hashCode => | |
| 583 JenkinsSmiHash.hash2(descriptor.hashCode, target.hashCode); | |
| 584 | |
| 585 @override | |
| 586 bool operator ==(other) { | |
| 587 if (other is WorkItem) { | |
| 588 return this.descriptor == other.descriptor && this.target == other.target; | |
| 589 } else { | |
| 590 return false; | |
| 591 } | |
| 592 } | |
| 593 | |
| 594 /** | |
| 595 * Build the task represented by this work item. | |
| 596 */ | |
| 597 AnalysisTask buildTask() { | |
| 598 if (builder != null) { | |
| 599 throw new StateError("some inputs have not been computed"); | |
| 600 } | |
| 601 AnalysisTask task = descriptor.createTask(context, target, inputs); | |
| 602 task.dependencyCycle = dependencyCycle; | |
| 603 return task; | |
| 604 } | |
| 605 | |
| 606 /** | |
| 607 * Gather all of the inputs needed to perform the task. | |
| 608 * | |
| 609 * If at least one of the inputs have not yet been computed, return a work | |
| 610 * item that can be used to generate that input to indicate that the caller | |
| 611 * should perform the returned item's task before returning to gathering | |
| 612 * inputs for this item's task. | |
| 613 * | |
| 614 * If all of the inputs have been gathered, return `null` to indicate that the | |
| 615 * client should build and perform the task. A value of `null` will also be | |
| 616 * returned if some of the inputs cannot be computed and the task cannot be | |
| 617 * performed. Callers can differentiate between these cases by checking the | |
| 618 * [exception] field. If the field is `null`, then the task can be performed; | |
| 619 * if the field is non-`null` then the task cannot be performed and all of the | |
| 620 * tasks' results should be marked as being in ERROR. | |
| 621 */ | |
| 622 WorkItem gatherInputs(TaskManager taskManager, List<WorkItem> skipInputs) { | |
| 623 while (builder != null) { | |
| 624 AnalysisTarget inputTarget = builder.currentTarget; | |
| 625 ResultDescriptor inputResult = builder.currentResult; | |
| 626 inputTargetedResults.add(new TargetedResult(inputTarget, inputResult)); | |
| 627 CacheEntry inputEntry = context.getCacheEntry(inputTarget); | |
| 628 CacheState inputState = inputEntry.getState(inputResult); | |
| 629 if (skipInputs.any((WorkItem item) => | |
| 630 item.target == inputTarget && item.spawningResult == inputResult)) { | |
| 631 // This input is being skipped due to a circular dependency. Tell the | |
| 632 // builder that it's not available so we can move on to other inputs. | |
| 633 builder.currentValueNotAvailable(); | |
| 634 } else if (inputState == CacheState.ERROR) { | |
| 635 exception = inputEntry.exception; | |
| 636 return null; | |
| 637 } else if (inputState == CacheState.IN_PROCESS) { | |
| 638 // | |
| 639 // TODO(brianwilkerson) Implement this case. | |
| 640 // | |
| 641 // One possibility would be to return a WorkItem that would perform a | |
| 642 // no-op task in order to cause us to come back to this work item on the | |
| 643 // next iteration. It would be more efficient, in general, to push this | |
| 644 // input onto a waiting list and proceed to the next input so that work | |
| 645 // could proceed, but given that the only result that can currently be | |
| 646 // IN_PROCESS is CONTENT, I don't know that it's worth the extra effort | |
| 647 // to implement the general solution at this point. | |
| 648 // | |
| 649 throw new UnimplementedError(); | |
| 650 } else if (inputState != CacheState.VALID) { | |
| 651 try { | |
| 652 TaskDescriptor descriptor = | |
| 653 taskManager.findTask(inputTarget, inputResult); | |
| 654 return new WorkItem(context, inputTarget, descriptor, inputResult); | |
| 655 } on AnalysisException catch (exception, stackTrace) { | |
| 656 this.exception = new CaughtException(exception, stackTrace); | |
| 657 return null; | |
| 658 } | |
| 659 } else { | |
| 660 builder.currentValue = inputEntry.getValue(inputResult); | |
| 661 } | |
| 662 if (!builder.moveNext()) { | |
| 663 inputs = builder.inputValue; | |
| 664 builder = null; | |
| 665 } | |
| 666 } | |
| 667 return null; | |
| 668 } | |
| 669 | |
| 670 @override | |
| 671 String toString() => 'Run $descriptor on $target'; | |
| 672 } | |
| 673 | |
| 674 /** | |
| 675 * [AnalysisDriver] uses [WorkManager]s to select results to compute. | |
| 676 * | |
| 677 * They know specific of the targets and results they care about, | |
| 678 * so they can request analysis results in optimal order. | |
| 679 */ | |
| 680 abstract class WorkManager { | |
| 681 /** | |
| 682 * Notifies the managers that the given set of priority [targets] was set. | |
| 683 */ | |
| 684 void applyPriorityTargets(List<AnalysisTarget> targets); | |
| 685 | |
| 686 /** | |
| 687 * Return the next [TargetedResult] that this work manager wants to be | |
| 688 * computed, or `null` if this manager doesn't need any new results. | |
| 689 */ | |
| 690 TargetedResult getNextResult(); | |
| 691 | |
| 692 /** | |
| 693 * Return the priority if the next work order this work manager want to be | |
| 694 * computed. The [AnalysisDriver] will perform the work order with | |
| 695 * the highest priority. | |
| 696 * | |
| 697 * Even if the returned value is [WorkOrderPriority.NONE], it still does not | |
| 698 * guarantee that [getNextResult] will return not `null`. | |
| 699 */ | |
| 700 WorkOrderPriority getNextResultPriority(); | |
| 701 | |
| 702 /** | |
| 703 * Notifies the manager that the given [outputs] were produced for | |
| 704 * the given [target]. | |
| 705 */ | |
| 706 void resultsComputed( | |
| 707 AnalysisTarget target, Map<ResultDescriptor, dynamic> outputs); | |
| 708 } | |
| 709 | |
| 710 /** | |
| 711 * A description of the work to be done to compute a desired analysis result. | |
| 712 * The class implements a lazy depth-first traversal of the work item's input. | |
| 713 */ | |
| 714 class WorkOrder implements Iterator<WorkItem> { | |
| 715 /** | |
| 716 * The dependency walker which is being used to determine what work to do | |
| 717 * next. | |
| 718 */ | |
| 719 final _WorkOrderDependencyWalker _dependencyWalker; | |
| 720 | |
| 721 /** | |
| 722 * The strongly connected component most recently returned by | |
| 723 * [_dependencyWalker], minus any [WorkItem]s that the iterator has already | |
| 724 * moved past. | |
| 725 * | |
| 726 * Null if the [_dependencyWalker] hasn't been used yet. | |
| 727 */ | |
| 728 List<WorkItem> currentItems; | |
| 729 | |
| 730 /** | |
| 731 * Initialize a newly created work order to compute the result described by | |
| 732 * the given work item. | |
| 733 */ | |
| 734 WorkOrder(TaskManager taskManager, WorkItem item) | |
| 735 : _dependencyWalker = new _WorkOrderDependencyWalker(taskManager, item); | |
| 736 | |
| 737 @override | |
| 738 WorkItem get current { | |
| 739 if (currentItems == null) { | |
| 740 return null; | |
| 741 } else { | |
| 742 return currentItems.last; | |
| 743 } | |
| 744 } | |
| 745 | |
| 746 @override | |
| 747 bool moveNext() { | |
| 748 return workOrderMoveNextPerfTag.makeCurrentWhile(() { | |
| 749 if (currentItems != null && currentItems.length > 1) { | |
| 750 // Yield more items. | |
| 751 currentItems.removeLast(); | |
| 752 return true; | |
| 753 } else { | |
| 754 // Get a new strongly connected component. | |
| 755 StronglyConnectedComponent<WorkItem> nextStronglyConnectedComponent = | |
| 756 _dependencyWalker.getNextStronglyConnectedComponent(); | |
| 757 if (nextStronglyConnectedComponent == null) { | |
| 758 currentItems = null; | |
| 759 return false; | |
| 760 } | |
| 761 currentItems = nextStronglyConnectedComponent.nodes; | |
| 762 if (nextStronglyConnectedComponent.containsCycle) { | |
| 763 // A cycle has been found. | |
| 764 for (WorkItem item in currentItems) { | |
| 765 item.dependencyCycle = currentItems.toList(); | |
| 766 } | |
| 767 } else { | |
| 768 assert(currentItems.length == 1); | |
| 769 } | |
| 770 return true; | |
| 771 } | |
| 772 }); | |
| 773 } | |
| 774 } | |
| 775 | |
| 776 /** | |
| 777 * The priorities of work orders returned by [WorkManager]s. | |
| 778 */ | |
| 779 enum WorkOrderPriority { | |
| 780 /** | |
| 781 * Responding to an user's action. | |
| 782 */ | |
| 783 INTERACTIVE, | |
| 784 | |
| 785 /** | |
| 786 * Computing information for priority sources. | |
| 787 */ | |
| 788 PRIORITY, | |
| 789 | |
| 790 /** | |
| 791 * A work should be done, but without any special urgency. | |
| 792 */ | |
| 793 NORMAL, | |
| 794 | |
| 795 /** | |
| 796 * Nothing to do. | |
| 797 */ | |
| 798 NONE | |
| 799 } | |
| 800 | |
| 801 /** | |
| 802 * Specilaization of [CycleAwareDependencyWalker] for use by [WorkOrder]. | |
| 803 */ | |
| 804 class _WorkOrderDependencyWalker extends CycleAwareDependencyWalker<WorkItem> { | |
| 805 /** | |
| 806 * The task manager used to build work items. | |
| 807 */ | |
| 808 final TaskManager taskManager; | |
| 809 | |
| 810 _WorkOrderDependencyWalker(this.taskManager, WorkItem startingNode) | |
| 811 : super(startingNode); | |
| 812 | |
| 813 @override | |
| 814 WorkItem getNextInput(WorkItem node, List<WorkItem> skipInputs) { | |
| 815 return node.gatherInputs(taskManager, skipInputs); | |
| 816 } | |
| 817 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1400473008:
Roll Observatory packages and add a roll script (Closed)
Base URL: git@github.com:dart-lang/observatory_pub_packages.git@master