First cut at analysis driver

First cut at analysis driver

R=paulberry@google.com, scheglov@google.com

Committed: https://code.google.com/p/dart/source/detail?r=44199

[Brian Wilkerson, 2015-02-09 16:00:05]

brianwilkerson@google.com changed reviewers:
+ paulberry@google.com, scheglov@google.com

[Brian Wilkerson, 2015-02-09 16:00:06]

Obviously, there's no rush to review this. Other tasks take priority.

There's still a lot of work that needs to be done. I'm reasonably happy with the
general structure of the driver, but there are several pieces that aren't fully
implemented yet. I tried to comment them to make it easier to review.

I'm not very happy yet with the cache implementation. I essentially copied over
the old cache implementation and cleaned it up a little bit, but I think we need
some deeper changes. First, I want to incorporate some of Paul's ideas about
tracking dependencies between results so that we can simplify the whole story of
propagating invalidation. Second, we need a much more generic and automated
story for flushing data from the cache. But, I needed to reference the cache in
the driver, so I had to have some kind of implementation.

[scheglov, 2015-02-09 16:44:45]

LGTM

[Paul Berry, 2015-03-03 17:21:32]

lgtm.  Sorry for the slow response.

I've made a lot of comments but I doubt that many of them need to be addressed
immediately, since the code isn't going live yet.  So feel free to land as is,
and we can iterate.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
File pkg/analyzer/lib/src/context/cache.dart (right):

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:44: int get astSize =>
_partitions[_partitions.length - 1].astSize;
Why not sum .astSize over all partitions?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:46: //  /**
Add a TODO comment here?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:69: if (_partitions[i].contains(target))
{
It seems like we do this loop over partitions in a lot of places.  Would it be
better to de-duplicate the code by making a function like this?

CachePartition _getPartitionFor(AnalysisTarget target) {
  int count = _partitions.length;
  for (int i = 0; i < count; i++) {
    if (_partitions[i].contains(target)) {
      return partitions[i];
    }
  }
  throw ...; // No partition found to handle the target
}

An advantage of this approach is that it makes us consistent about how we handle
the "should never happen" case where no partition handles the target, as opposed
to the current implementation where some functions do nothing, others return
null, and others report a log message.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:95: * Return context that owns the given
[target].
I'm not sure I understand what you mean by "owns".  Is this intended to handle
cases like sharing the analysis results for the SDK, so that SDK files get
analyzed in a special "SDK context" and the rest of the files get analyzed in
the context created by the client?

If so, consider saying something like "Return the context that should be used to
analyze the given [target]."

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:109:
AnalysisEngine.instance.logger.logInformation(
I'm concerned that if we just log the error, it won't be noticed during
development unless someone is watching their log file very carefully.  Given
that it should be *really* easy to avoid this every happening by making the last
partition a universal partition, I think it would be better to throw an
exception, since that gives us a fighting chance of noticing the bug before
deployment (e.g. in a unit test).

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:147: } catch (exception) {
Why would an exception ever occur here?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:155: }
If we get to the end of the function without finding a partition that contains
target, we just drop the new cache entry on the floor.  It seems like it would
be better to throw an exception, or at the very least log the error condition,
since this should never happen in the absence of bugs elsewhere.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:168: } catch (exception) {
Why would an exception ever occur here?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:239: */
I'm assuming that an intended invariant is that when exception != null, at least
one piece of data in the cache entry is in the ERROR state, and vice versa.  Is
that correct?

If so, who is responsible for maintaining that invariant?  This class, or code
elsewhere?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:290: //
Since this should never happen, should we also add an entry to the log?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:309: });
To restore the invariant, we might need to set this.exception to null.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:351: _resultMap.clear();
To restore the invariant, we should set this.exception to null.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:377: }
I'm surprised this function doesn't set this.exception.  What happens if the
state change moves us in or out of an error state?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:390: }
Similar question about this.exception for this function.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:489: List<AnalysisTarget> _recentlyUsed
= <AnalysisTarget>[];
How big is this list expected to get in typical use?  It seems like we're at
risk of taking on some O(n^2) operations here.

Consider replacing with a LinkedHashSet.

Also, it would be nice to more clearly state the invariant that we're going to
try to maintain on this data structure.  I think the invariant we want is:
(_recentlyUsed.length <= _maxCacheSize OR all entries in _recentlyUsed have a
retention policy of HIGH)

However, I'm concerned that it may be difficult to maintain that invariant,
since the retention policy may change its notion of the priority of a file at
any time based on what the client sets as priority files.  It seems conceivable
that _recentlyUsed.length could grow much larger than _maxCacheSize due to lots
of files being in the HIGH priority state, and then later when the priority gets
lowered, we wouldn't shrink _recentlyUsed down.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:520: * <b>Note:</b> This method is only
visible for use by [AnalysisCache] and
Since AnalysisCache is in the same library, how about having it just access
_targetMap directly, so there's no need for this function?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:553: break;
Here's a case where I'm concerned about the invariant on _recentlyUsed.  If we
can rely on that invariant being satisfied before entry to this function, then a
"break" here is appropriate, because we only need to remove one AST from the
cache to make it safe to add another one.  However, if _recentlyUsed is
currently much larger than _maxCacheSize (due to a lot of files being HIGH
priority at some point in the past), then by breaking out of the loop we prevent
_recentlyUsed from shrinking back down to its proper size.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:562: bool contains(AnalysisTarget
target);
For a long time I was confused by code calling contains(), because I assumed
that it answered the question "is there currently data in the cache partition
corresponding to the given target?"  I now see that it answers the question "is
this cache partition responsible for storing data for the given target?"  So,
for example, I was really confused about how removedAst() could work, because I
couldn't understand why contains() would return true *after* the cache entry had
been removed.

Could we rename this function to something like "responsibleFor"?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:640: */
The doc comments should also explain when this method might return null.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:711: //    if (sourceEntry is DartEntry)
{
Add a TODO comment here?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:725: class ResultData {
Would it be beneficial to make this a generic class so that we can get a little
extra type checking, similar to what we do for ResultDescriptor?

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
File pkg/analyzer/lib/src/task/driver.dart (right):

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:90: // work that needs to be done.
An easy (but slightly hacky) way to achieve most of the performance improvement
would be to have some saved state that remembers our list index (and whether
we're iterating through priorityTargets or explicitTargets) between calls, so
that we can pick up where we left off rather than starting over from the
beginning each time.

We'd have to be careful to reset the saved state appropriately on a call to
reset(), so that if a change occurs to a priority target after we've moved on to
visiting explicit targets, we'll go back to visiting priority targets again.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:92: for (AnalysisTarget target in
context.priorityTargets) {
I'm surprised to see only two levels of priority here.  In AnalysisContextImpl,
we had to add a third level of priority (_pendingFutureSources) to support
completions in analysis server.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:168: //
A third approach, which I personally favor, would be to 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.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:362: * A description of the work to be
done to compute a desired analysis result.
It would me nice to have a comment explaining that the iterator implements a
lazy depth-first traversal of the work item's inputs (visiting inputs at each
layer in reverse order).  It took me a while to figure that out by reading the
implementation of moveNext() :)

Also: is it necessary to visit inputs at each layer in reverse order?  It seems
like visiting them in order would lead to less surprise and confusion when
debugging.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:391: currentItem = null;
This seems dangerous because it violates the usual convention that an iterator's
"current" getter is idempotent.

Also I'm not sure what we gain by setting currentItem to null here, and checking
whether it's null in moveNext(), since we always call moveNext() and current in
strict alternation.

It seems like we would get more conventional iterator behavior, without losing
any functionality, by dropping this line and replacing lines 397-402 with:

if (pendingItems.isEmpty) {
  currentItem = null;
  return false;
}
currentItem = pendingItems.removeLast();

[Brian Wilkerson, 2015-03-03 21:21:18]

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
File pkg/analyzer/lib/src/context/cache.dart (right):

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:44: int get astSize =>
_partitions[_partitions.length - 1].astSize;
This is kind of a hold-over from an earlier implementation before there were
partitions. It isn't clear what the right solution is when entries are in
multiple partitions (which exist so that results can be shared between
contexts). I think we really need a more global cache manager that can balance
the amount of cache being used across all of the partitions accessible from any
context.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:46: //  /**
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:69: if (_partitions[i].contains(target))
{
Sounds reasonable. Left for a later CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:95: * Return context that owns the given
[target].
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:109:
AnalysisEngine.instance.logger.logInformation(
Saved for a follow-on CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:147: } catch (exception) {
My guess is that it was debugging code added to the original implementation and
accidentally preserved in this implementation. I've removed it.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:155: }
Added TODO.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:168: } catch (exception) {
Removed

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:239: */
On 2015/03/03 17:21:32, Paul Berry wrote:
> I'm assuming that an intended invariant is that when exception != null, at
least
> one piece of data in the cache entry is in the ERROR state, and vice versa. 
Is
> that correct?

Yes.

> If so, who is responsible for maintaining that invariant?  This class, or code
> elsewhere?

That currently happens in AnalysisDriver.performWorkItem

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:290: //
> Since this should never happen, should we also add an entry to the log?

That would potentially let us know that it happened, but I don't think it would
help us track down the problem, so I'm not sure how useful it would be.
Postponing for a later CL (assuming you still think we should).

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:309: });
> To restore the invariant, we might need to set this.exception to null.

If the state were ERROR, then the value would be null, so we wouldn't change the
state.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:351: _resultMap.clear();
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:377: }
> What happens if the state change moves us in or out of an error state?

Then the client is expected to set the exception as a separate step.

We could make this class preserve the invariant (which I would generally
prefer), but at the cost of making the API more complex. For example, this
method could also throw an exception if the new state is ERROR and we could
introduce a new method that would set a list of descriptors to ERROR and take
the exception to be set. Sounds like a reasonable trade-off, but I'll save it
for a future CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:390: }
On 2015/03/03 17:21:31, Paul Berry wrote:
> Similar question about this.exception for this function.

The current assumption is that values won't be created for results marked as
being in ERROR. There's a description of the expected state transitions in each
CacheState constant's comment. The only valid transition from ERROR is to
INVALID.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:489: List<AnalysisTarget> _recentlyUsed
= <AnalysisTarget>[];
It's a valid concern, but we should discuss off-line. The retention policy
serves two purposes, one of which I think we no longer need, so we might be able
to solve the problems.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:520: * <b>Note:</b> This method is only
visible for use by [AnalysisCache] and
A hold-over from Java. It's currently also being used by tests, so I'm
postponing changes to a later CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:553: break;
Part of a larger discussion.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:562: bool contains(AnalysisTarget
target);
> Could we rename this function to something like "responsibleFor"?

Yes, in a future CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:640: */
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:711: //    if (sourceEntry is DartEntry)
{
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/context...
pkg/analyzer/lib/src/context/cache.dart:725: class ResultData {
Possibly. I'll look into it for a follow-on CL.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
File pkg/analyzer/lib/src/task/driver.dart (right):

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:90: // work that needs to be done.
True. I think WorkManager is less "hacky" and shouldn't be hard to port over; I
just had to stop coding somewhere so that others could also contribute :-)

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:92: for (AnalysisTarget target in
context.priorityTargets) {
That was probably done after I copied this code. I've added a TODO.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:168: //
Added to the TODO.

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:362: * A description of the work to be
done to compute a desired analysis result.
Done

https://codereview.chromium.org/913483002/diff/1/pkg/analyzer/lib/src/task/dr...
pkg/analyzer/lib/src/task/driver.dart:391: currentItem = null;
Done

[Brian Wilkerson, 2015-03-03 21:26:02]

Committed patchset #1 (id:1) manually as 44199 (presubmit successful).