Resolve ordering issues.

Resolve ordering issues.

This CL changes the way that the task model does strong mode inference to use the strongly connected components in the import/export graph.  Library cycles are computed and inference is staged by forcing each stage of inference to happen across an entire library cycle at once, and to force all external dependencies of a library cycle to have completed inference before inference for the library cycle can begin.

BUG=
R=brianwilkerson@google.com

Committed: https://github.com/dart-lang/sdk/commit/651221bb8215251959c67719778d4e8f54dd8d28

[Leaf, 2015-10-06 00:10:20]

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

[Leaf, 2015-10-06 00:14:58]

Hi Guys  - Please take a look.  This implements the approach that we've
discussed.  There is an issue that causes one of the tests to fail that I would
like some input on.  The test is for cache invalidation, ensuring that entries
are not unnecessarily invalidated.  The additional strong mode dependencies
causes this to fail.  I've added a comment at the place in dart.dart where the
issue arises (you'll have to look at the first patch set, sorry - just small
clean up changes between first and second).  I don't quite understand yet how to
express in the task model what we need to express to avoid this regression.  

Vijay, if you want to try this out and let me know if it fixes our outstanding
issues, that would be great.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/contex...
File pkg/analyzer/lib/src/context/context.dart (left):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/contex...
pkg/analyzer/lib/src/context/context.dart:1231: entry.setState(RESOLVED_UNIT5,
CacheState.FLUSHED);
I think this was a bug?

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:1870: 'resolveReachableLibraries': new
_ImportExportSourceClosureTaskInput(
For the most part, this avoids adding additional dependencies over non-strong
mode, but I don't know how to avoid these ones.  The task will return an empty
list in non-strong mode, but by virtue of its input dependencies it will have
forced additional work.  But since I don't access to the context here, I don't
know how to filter these out.  This is responsible for the failing test in
context_test.dart.  Suggestions?

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:2639: 'orderLibraryCycles':
LIBRARY_CYCLE_DEPENDENCIES.of(unit).toList(
This dependency is actually always satisfied since RESOLVED_UNIT7.of(unit)
transitively requires the same dependency.  Is it considered "good style" in the
task model to rely on these implicit transitive dependencies, or better to make
them explicit?

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
File pkg/analyzer/test/src/context/context_test.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
pkg/analyzer/test/src/context/context_test.dart:2226: void
fail_noChange_thenChange() {
This now fails because of the additional dependencies imposed by strong mode.

[Brian Wilkerson, 2015-10-06 19:04:47]

Sorry for the delay in getting this review done.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/contex...
File pkg/analyzer/lib/src/context/context.dart (left):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/contex...
pkg/analyzer/lib/src/context/context.dart:1231: entry.setState(RESOLVED_UNIT5,
CacheState.FLUSHED);
Yes, i'm sure it was a bug.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:1870: 'resolveReachableLibraries': new
_ImportExportSourceClosureTaskInput(
> For the most part, this avoids adding additional dependencies over non-strong
> mode, but I don't know how to avoid these ones.  The task will return an empty
> list in non-strong mode, but by virtue of its input dependencies it will have
> forced additional work.  But since I don't access to the context here, I don't
> know how to filter these out.

Without being able to access the context so that we can determine whether we're
running strong mode: no, I can't think of a good way. I think we'll just have to
see what the performance hit is and decide whether it's worth the effort to fix
it.

> This is responsible for the failing test in context_test.dart.

It seems like the extra tasks must be doing something differently in the
non-strong-mode case in order to cause different behavior, so that seems like a
bug we need to fix before committing.

Also, would it work to use "IMPORT_EXPORT_SOURCE_CLOSURE.of(unit.library)"
instead of creating the _ImportExportSourceClosureTaskInput directly? This input
will force the closure to be computed even if it has already been computed and
cached.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:2639: 'orderLibraryCycles':
LIBRARY_CYCLE_DEPENDENCIES.of(unit).toList(
> Is it considered "good style" in the task model to rely on these implicit
> transitive dependencies, or better to make them explicit?

I think it's better to make the dependencies explicit. That way if the
computation of a RESOLVED_UNIT7 can be optimized and that dependency removed we
don't end up breaking this task.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
File pkg/analyzer/test/src/context/context_test.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
pkg/analyzer/test/src/context/context_test.dart:2226: void
fail_noChange_thenChange() {
> This now fails because of the additional dependencies imposed by strong mode. 

I'd really like to understand what changed to cause this test to fail. Those
additional dependencies caused new tasks to be run, so those tasks must be doing
something different. I think we need to get this passing.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:159: * Only non-empty in strongMode
nit: It would be helpful (here and elsewhere) to include something like "The
result is only available for [LibrarySpecificUnit]s" to indicate what kind of
target this is produced for. My first guess, based on the description above, is
that the target is a LibraryElement, but I discovered I was wrong after looking
at the task.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1756: * compilation unit
nit: missing period

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1758: class
ComputeLibraryCycleDependenciesTask extends SourceBasedAnalysisTask {
Is there a reason for this to be a separate task? It only depends on the
LIBRARY_CYCLE of it's input, so it looks (from what I can see) that we could
just compute the LIBRARY_CYCLE_DEPENDENCIES in the same task
(ComputeLibraryCycleTask). If so, that would reduce some of the overhead for
running the task model.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1824: * library element.  Also computes the
[LIBRARY_CYCLE_UNITS]
nit: missing period

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1830: static const String UNIT_INPUT =
'UNIT_INPUT';
Perhaps "LIBRARY_ELEMENT2_INPUT"? ("UNIT_INPUT" is used everywhere else as a
name for a CompilationUnit.)

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:2702: RecordingErrorListener errorListener =
new RecordingErrorListener();
nit: In places where we are going to discard the errors we could use
"AnalysisErrorListener.NULL_LISTENER". It's slightly more efficient.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
File pkg/analyzer/test/src/task/dart_test.dart (left):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:2131: void test_perform_reresolution()
{
Out of curiosity, why was this test removed?

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
File pkg/analyzer/test/src/task/dart_test.dart (right):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:59:
runReflectiveTests(ResolveLibraryTypeNamesTaskTest);
Duplicated line. (Probably copied and pasted in preparation for adding the
missing tests noted below.)

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:65:
runReflectiveTests(VerifyUnitTaskTest);
We appear to be missing tests for ComputeLibraryCycleDependenciesTask,
ComputeLibraryCycleTask, and ResolveInstanceFieldsInUnitTask.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:2571: void
test_library_cycle_singleton() {
These tests look like they're testing the results of the
ComputeLibraryCycleDependenciesTask and/or
the ComputeLibraryCycleTask. If so, consider creating new classes for those
tasks and move these tests there.

[Leaf, 2015-10-06 20:30:55]

Thanks for the comments, working on addressing.  I think I'll need some help
understanding the cache invalidation at some point, I'll ping for a VC when I
get there.

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
File pkg/analyzer/test/src/context/context_test.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/test/src/conte...
pkg/analyzer/test/src/context/context_test.dart:2226: void
fail_noChange_thenChange() {
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> > This now fails because of the additional dependencies imposed by strong
mode. 
> 
> I'd really like to understand what changed to cause this test to fail. Those
> additional dependencies caused new tasks to be run, so those tasks must be
doing
> something different. I think we need to get this passing.

Concretely, it's the extra input dependencies on LIBRARY_CYCLE that require a
LIBRARY_ELEMENT2 for the unit and for its import/export closure.  If I eliminate
them, this test passes.  I agree that we should fix this.  I'd like to just
filter those dependencies in the non strong mode case, but we don't seem to have
a good way to do that.  Should this test pass even given those extra
dependencies?  I don't think it should in strong mode - if class A or B had an
inferred top level field or static, then resolution of b needs to be
invalidated.  If it should still pass in regular mode (even given the extra
dependencies) then I need to understand how the invalidation logic works better
to fix it - I'll need some help with that.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
File pkg/analyzer/test/src/task/dart_test.dart (left):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:2131: void test_perform_reresolution()
{
On 2015/10/06 19:04:47, Brian Wilkerson wrote:
> Out of curiosity, why was this test removed?

The thing it's testing for (re-resolution of field initializers) no longer
happens at this stage.

[Leaf, 2015-10-07 18:53:55]

PTAL, thanks!

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:1870: 'resolveReachableLibraries': new
_ImportExportSourceClosureTaskInput(
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> > For the most part, this avoids adding additional dependencies over
non-strong
> > mode, but I don't know how to avoid these ones.  The task will return an
empty
> > list in non-strong mode, but by virtue of its input dependencies it will
have
> > forced additional work.  But since I don't access to the context here, I
don't
> > know how to filter these out.
> 
> Without being able to access the context so that we can determine whether
we're
> running strong mode: no, I can't think of a good way. I think we'll just have
to
> see what the performance hit is and decide whether it's worth the effort to
fix
> it.
> 
> > This is responsible for the failing test in context_test.dart.
> 
> It seems like the extra tasks must be doing something differently in the
> non-strong-mode case in order to cause different behavior, so that seems like
a
> bug we need to fix before committing.
> 
> Also, would it work to use "IMPORT_EXPORT_SOURCE_CLOSURE.of(unit.library)"
> instead of creating the _ImportExportSourceClosureTaskInput directly? This
input
> will force the closure to be computed even if it has already been computed and
> cached.

Replaced with IMPORT_EXPORT_SOURCE_CLOSURE

https://codereview.chromium.org/1386023002/diff/1/pkg/analyzer/lib/src/task/d...
pkg/analyzer/lib/src/task/dart.dart:2639: 'orderLibraryCycles':
LIBRARY_CYCLE_DEPENDENCIES.of(unit).toList(
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> > Is it considered "good style" in the task model to rely on these implicit
> > transitive dependencies, or better to make them explicit?
> 
> I think it's better to make the dependencies explicit. That way if the
> computation of a RESOLVED_UNIT7 can be optimized and that dependency removed
we
> don't end up breaking this task.

Acknowledged.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:159: * Only non-empty in strongMode
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> nit: It would be helpful (here and elsewhere) to include something like "The
> result is only available for [LibrarySpecificUnit]s" to indicate what kind of
> target this is produced for. My first guess, based on the description above,
is
> that the target is a LibraryElement, but I discovered I was wrong after
looking
> at the task.

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1756: * compilation unit
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> nit: missing period

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1758: class
ComputeLibraryCycleDependenciesTask extends SourceBasedAnalysisTask {
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> Is there a reason for this to be a separate task? It only depends on the
> LIBRARY_CYCLE of it's input, so it looks (from what I can see) that we could
> just compute the LIBRARY_CYCLE_DEPENDENCIES in the same task
> (ComputeLibraryCycleTask). If so, that would reduce some of the overhead for
> running the task model.

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1824: * library element.  Also computes the
[LIBRARY_CYCLE_UNITS]
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> nit: missing period

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:1830: static const String UNIT_INPUT =
'UNIT_INPUT';
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> Perhaps "LIBRARY_ELEMENT2_INPUT"? ("UNIT_INPUT" is used everywhere else as a
> name for a CompilationUnit.)

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:2702: RecordingErrorListener errorListener =
new RecordingErrorListener();
On 2015/10/06 19:04:46, Brian Wilkerson wrote:
> nit: In places where we are going to discard the errors we could use
> "AnalysisErrorListener.NULL_LISTENER". It's slightly more efficient.

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
File pkg/analyzer/test/src/task/dart_test.dart (right):

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:59:
runReflectiveTests(ResolveLibraryTypeNamesTaskTest);
On 2015/10/06 19:04:47, Brian Wilkerson wrote:
> Duplicated line. (Probably copied and pasted in preparation for adding the
> missing tests noted below.)

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:65:
runReflectiveTests(VerifyUnitTaskTest);
On 2015/10/06 19:04:47, Brian Wilkerson wrote:
> We appear to be missing tests for ComputeLibraryCycleDependenciesTask,
> ComputeLibraryCycleTask, and ResolveInstanceFieldsInUnitTask.

Done.

https://codereview.chromium.org/1386023002/diff/20001/pkg/analyzer/test/src/t...
pkg/analyzer/test/src/task/dart_test.dart:2571: void
test_library_cycle_singleton() {
On 2015/10/06 19:04:47, Brian Wilkerson wrote:
> These tests look like they're testing the results of the
> ComputeLibraryCycleDependenciesTask and/or
> the ComputeLibraryCycleTask. If so, consider creating new classes for those
> tasks and move these tests there.

Done.

https://codereview.chromium.org/1386023002/diff/50001/pkg/analyzer/lib/src/ge...
File pkg/analyzer/lib/src/generated/incremental_resolver.dart (right):

https://codereview.chromium.org/1386023002/diff/50001/pkg/analyzer/lib/src/ge...
pkg/analyzer/lib/src/generated/incremental_resolver.dart:907:
isByTask(ComputeLibraryCycleTask.DESCRIPTOR) ||
This was what was causing the cache invalidation test failure.

[Brian Wilkerson, 2015-10-07 22:56:56]

LGTM

https://codereview.chromium.org/1386023002/diff/50001/pkg/analyzer/lib/src/ta...
File pkg/analyzer/lib/src/task/dart.dart (right):

https://codereview.chromium.org/1386023002/diff/50001/pkg/analyzer/lib/src/ta...
pkg/analyzer/lib/src/task/dart.dart:445: * is true of a [RESOLVED_UNIT8].
nit: "8" --> "7"

[Leaf, 2015-10-07 23:14:41]

Committed patchset #4 (id:50001) manually as
651221bb8215251959c67719778d4e8f54dd8d28 (presubmit successful).