Add ServerOperation and queue.

Add ServerOperation and queue.

Schedule operations to perform analysis.
Moving notifications into operations to be done in the next CL.

R=brianwilkerson@google.com, paulberry@google.com
BUG=

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

[Brian Wilkerson, 2014-06-02 14:32:18]

I have some concerns about this CL (including the fact that it totally breaks
the timing tests I wrote) and would prefer to have them addressed before you
commit. Let me know if that would be harder.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:135: _scheduleTask();
I believe that this will cause the event queue to become flooded with calls to
performTask (because performTask also schedules itself).

I think the better design is to have a single method that adds an operation to
the queue and conditionally schedules performTask to be run if the queue was
previously empty. Perhaps we should pass a closure (_scheduleTask) into "add"
that gets run iff the queue was previously empty.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:192: _scheduleTask();
This method should only get scheduled if the queue is not empty.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:198: void
internalPerformAnalysis(AnalysisContext context) {
I would prefer a style in which the code to perform an operation were in the
operation's perform() method rather than having to implement an internal method
for every operation.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:214:
schedulePerformAnalysisOperation(context, true);
We need to take the "continuation" flag into account when scheduling analysis
operations. Otherwise we're going to be using more memory than necessary at any
given time and for longer periods of time.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation_queue.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation_queue.dart:16: class
ServerOperationQueue {
The implementation of this class makes the assumption that the priority of an
operation cannot change over time, but I believe that the ability to set
priority files makes that assumption wrong.

This might be an indication that an explicit queue is not the best approach.
(Something to think about.)

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
File pkg/analysis_server/test/operation/operation_queue_test.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/operation/operation_queue_test.dart:32:
expect(queue.take(), null);
Should this (and line 42) be "isNull"?

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/operation/operation_queue_test.dart:46: test('false',
() {
This test is duplicated on line 58.

[Paul Berry, 2014-06-02 16:04:41]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (left):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:111: * Invariant: when this
list is non-empty, there is exactly one pending call
Why is this comment being deleted?  Is your intent to establish a different
invariant?  If so, what?  I think this invariant was a good one.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:204: contextWorkQueue.clear();
Why are we getting rid of this code?  Was it incorrect?

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:222: } finally {
Why are we dropping this logic?  I believe that scheduling the next task in a
finally block is the right thing to do.  If we don't, then it means that a
single exception will effectively grind the whole server to a halt, because it
breaks the invariant.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:135: _scheduleTask();
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> I believe that this will cause the event queue to become flooded with calls to
> performTask (because performTask also schedules itself).
> 
> I think the better design is to have a single method that adds an operation to
> the queue and conditionally schedules performTask to be run if the queue was
> previously empty. Perhaps we should pass a closure (_scheduleTask) into "add"
> that gets run iff the queue was previously empty.

I'm not sure we even need a closure.  I think it is sufficient to do:

bool wasEmpty = operationQueue.isEmpty;
operationQueue.add(...);
if (wasEmpty) {
  _scheduleTask();
}

(which is essentially the logic we had before this CL, except that previously we
had a .length method so we could simply check whether length was 1 after adding
the task).

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
I don't understand why analysis notifications need to be a separate task.  It
seems like what the code was previously doing (firing notifications as soon as
they were available) has exactly the same effect since it effectively makes
notifications top priority.

I suspect that if we remove ANALYSIS_NOTIFICATION by firing notifications as
soon as they are available, then we will be able to collapse
ANALYSIS_PRIORITY_CONTINUE with ANALYSIS_PRIORITY, and collapse
ANALYSIS_PRIORITY with ANALYSIS, because it will be possible for a single server
operation to perform analysis in several phases and fire notifications as they
become available.  The only thing we'd lose by making this change is that if a
priority request came in while we were doing a normal analysis of a given file,
we would have to wait until that normal analysis fully completed before we could
start the new priority analysis.  Personally, I think that's an ok tradeoff to
make for now--we can always implement something more sophisticated later if we
find that this makes analysis too unresponsive.

[Brian Wilkerson, 2014-06-02 16:21:00]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
> I don't understand why analysis notifications need to be a separate task.  It
> seems like what the code was previously doing (firing notifications as soon as
> they were available) has exactly the same effect ...

There are two advantage I can think of. First, if it takes a significant amount
of time to compute the information to be passed back in a notification (which it
might not), then by separating that out into a separate task we have reduced the
latency for handling requests that have come in (especially if there are
multiple notifications for a single file). Second, we have the potential to be
able to cancel notifications that have become outdated, which would reduce the
communication overhead. I'm not sure how much that really buys us in either
case, and it might not be worth the added complexity.

[Paul Berry, 2014-06-02 16:29:25]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
On 2014/06/02 16:21:01, Brian Wilkerson wrote:
> > I don't understand why analysis notifications need to be a separate task. 
It
> > seems like what the code was previously doing (firing notifications as soon
as
> > they were available) has exactly the same effect ...
> 
> There are two advantage I can think of. First, if it takes a significant
amount
> of time to compute the information to be passed back in a notification (which
it
> might not), then by separating that out into a separate task we have reduced
the
> latency for handling requests that have come in (especially if there are
> multiple notifications for a single file). Second, we have the potential to be
> able to cancel notifications that have become outdated, which would reduce the
> communication overhead. I'm not sure how much that really buys us in either
> case, and it might not be worth the added complexity.

I would understand that if notifications weren't the highest priority type of
task.  But since they are the highest priority type of task, that means that (a)
the only requests whose latency we reduce are those that do not require doing
any analysis, and (b) in practice we will never cancel any outdated
notifications, since as soon as a set of notifications is generated, the highest
priority task will be to send them.

[Brian Wilkerson, 2014-06-02 16:42:33]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
> I would understand that if notifications weren't the highest priority type of
> task.  But since they are the highest priority type of task, that means that
(a)
> the only requests whose latency we reduce are those that do not require doing
> any analysis,

True, which means that this might not be worthwhile.

> and (b) in practice we will never cancel any outdated
> notifications, since as soon as a set of notifications is generated, the
highest
> priority task will be to send them.

Here's the scenario I was thinking of:

1. Server processes a request telling it that a file has changed.
2. Server analyzes the file (after several iterations), and schedules a
notification.
3. Server processes a request telling it that the same file has changed again.
4. The notification can be cancelled because the data it was depending on is
out-of-date.

It seems like a very small window of opportunity, and perhaps it would never buy
us any real advantage. Again, it might not be worth the complexity this
mechanism adds.

I'm happy to have it removed, and we can investigate solutions like this if we
see a problem.

[scheglov, 2014-06-02 17:56:59]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (left):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:111: * Invariant: when this
list is non-empty, there is exactly one pending call
On 2014/06/02 16:04:41, Paul Berry wrote:
> Why is this comment being deleted?  Is your intent to establish a different
> invariant?  If so, what?  I think this invariant was a good one.

Restored for the operation queue field.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:204: contextWorkQueue.clear();
On 2014/06/02 16:04:41, Paul Berry wrote:
> Why are we getting rid of this code?  Was it incorrect?

Restored.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:222: } finally {
On 2014/06/02 16:04:41, Paul Berry wrote:
> Why are we dropping this logic?  I believe that scheduling the next task in a
> finally block is the right thing to do.  If we don't, then it means that a
> single exception will effectively grind the whole server to a halt, because it
> breaks the invariant.

Restored in performTask/performOperation.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:192: _scheduleTask();
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> This method should only get scheduled if the queue is not empty.

Done.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:198: void
internalPerformAnalysis(AnalysisContext context) {
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> I would prefer a style in which the code to perform an operation were in the
> operation's perform() method rather than having to implement an internal
method
> for every operation.

Me too, but I'm afraid we have to expose too much internals of AnalysisServer to
do so.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:214:
schedulePerformAnalysisOperation(context, true);
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> We need to take the "continuation" flag into account when scheduling analysis
> operations. Otherwise we're going to be using more memory than necessary at
any
> given time and for longer periods of time.

We do use it - PerformAnalysisOperation returns different priority depending on
if it is a continuation or not.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
On 2014/06/02 16:42:33, Brian Wilkerson wrote:
> > I would understand that if notifications weren't the highest priority type
of
> > task.  But since they are the highest priority type of task, that means that
> (a)
> > the only requests whose latency we reduce are those that do not require
doing
> > any analysis,
> 
> True, which means that this might not be worthwhile.
> 
> > and (b) in practice we will never cancel any outdated
> > notifications, since as soon as a set of notifications is generated, the
> highest
> > priority task will be to send them.
> 
> Here's the scenario I was thinking of:
> 
> 1. Server processes a request telling it that a file has changed.
> 2. Server analyzes the file (after several iterations), and schedules a
> notification.
> 3. Server processes a request telling it that the same file has changed again.
> 4. The notification can be cancelled because the data it was depending on is
> out-of-date.
> 
> It seems like a very small window of opportunity, and perhaps it would never
buy
> us any real advantage. Again, it might not be worth the complexity this
> mechanism adds.
> 
> I'm happy to have it removed, and we can investigate solutions like this if we
> see a problem.

I will remove separate priorities for notifications for now.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation_queue.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation_queue.dart:16: class
ServerOperationQueue {
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> The implementation of this class makes the assumption that the priority of an
> operation cannot change over time, but I believe that the ability to set
> priority files makes that assumption wrong.
> 
> This might be an indication that an explicit queue is not the best approach.
> (Something to think about.)

Done.
Now we do two passes - during the first we look for a priority analysis
operations, and during the second we use operation priorities.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
File pkg/analysis_server/test/operation/operation_queue_test.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/operation/operation_queue_test.dart:32:
expect(queue.take(), null);
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> Should this (and line 42) be "isNull"?

As I see it now, we actually don't need mergeable operations.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/operation/operation_queue_test.dart:46: test('false',
() {
On 2014/06/02 14:32:18, Brian Wilkerson wrote:
> This test is duplicated on line 58.

Removed.

[scheglov, 2014-06-02 17:57:08]

PTAL

[Brian Wilkerson, 2014-06-02 18:21:02]

LGTM

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:198: void
internalPerformAnalysis(AnalysisContext context) {
I'd like to start with doing it the better way until we know that it won't work.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:214:
schedulePerformAnalysisOperation(context, true);
> > We need to take the "continuation" flag into account when scheduling
analysis
> > operations.
> 
> We do use it - PerformAnalysisOperation returns different priority depending
on
> if it is a continuation or not.

I meant, if we are continuing analysis of a context then that operation should
be added at the head of the queue rather than the tail.

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:210:
sendStatusNotification(null);
This isn't optimal, but perhaps we should address it in a later CL. While this
guarantees that we will send a status notification after analysis is complete,
it doesn't guarantee that it will happen as soon as analysis is complete. Once
we have other operations, they will also need to complete before we can send
notification.

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:236: if (notices != null) {
notices can only be non-null at this point because of the previous return.

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/test...
File pkg/analysis_server/test/analysis_server_test.dart (right):

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/test...
pkg/analysis_server/test/analysis_server_test.dart:53:
expect(notifications.length, equals(5));
Given that the length will change every time we adjust the number of status
notifications that are sent, perhaps we should just confirm that it's greater
than zero.

[scheglov, 2014-06-02 18:32:02]

Committed patchset #4 manually as r36890 (presubmit successful).

[scheglov, 2014-06-02 18:32:25]

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:214:
schedulePerformAnalysisOperation(context, true);
On 2014/06/02 18:21:03, Brian Wilkerson wrote:
> > > We need to take the "continuation" flag into account when scheduling
> analysis
> > > operations.
> > 
> > We do use it - PerformAnalysisOperation returns different priority depending
> on
> > if it is a continuation or not.
> 
> I meant, if we are continuing analysis of a context then that operation should
> be added at the head of the queue rather than the tail.

Well, it is added to the tail of the ANALYSIS_CONTINUE queue, which is
practically always has 0 or 1 item.

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/analysis_server.dart (right):

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/analysis_server.dart:236: if (notices != null) {
On 2014/06/02 18:21:03, Brian Wilkerson wrote:
> notices can only be non-null at this point because of the previous return.

Done.

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/test...
File pkg/analysis_server/test/analysis_server_test.dart (right):

https://codereview.chromium.org/308003009/diff/40001/pkg/analysis_server/test...
pkg/analysis_server/test/analysis_server_test.dart:53:
expect(notifications.length, equals(5));
On 2014/06/02 18:21:03, Brian Wilkerson wrote:
> Given that the length will change every time we adjust the number of status
> notifications that are sent, perhaps we should just confirm that it's greater
> than zero.

Done.

[Paul Berry, 2014-06-02 18:49:31]

It looks like the CL got committed while I was drafting my follow-up comments,
so my comments may be moot.  Sending them anyway in case they are useful.

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/operation/operation.dart (right):

https://codereview.chromium.org/308003009/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/operation/operation.dart:22: static const
ServerOperationPriority ANALYSIS_NOTIFICATION = const
ServerOperationPriority._(0, "ANALYSIS_NOTIFICATION");
On 2014/06/02 17:56:59, scheglov wrote:
> On 2014/06/02 16:42:33, Brian Wilkerson wrote:
> > > I would understand that if notifications weren't the highest priority type
> of
> > > task.  But since they are the highest priority type of task, that means
that
> > (a)
> > > the only requests whose latency we reduce are those that do not require
> doing
> > > any analysis,
> > 
> > True, which means that this might not be worthwhile.
> > 
> > > and (b) in practice we will never cancel any outdated
> > > notifications, since as soon as a set of notifications is generated, the
> > highest
> > > priority task will be to send them.
> > 
> > Here's the scenario I was thinking of:
> > 
> > 1. Server processes a request telling it that a file has changed.
> > 2. Server analyzes the file (after several iterations), and schedules a
> > notification.
> > 3. Server processes a request telling it that the same file has changed
again.
> > 4. The notification can be cancelled because the data it was depending on is
> > out-of-date.
> > 
> > It seems like a very small window of opportunity, and perhaps it would never
> buy
> > us any real advantage. Again, it might not be worth the complexity this
> > mechanism adds.
> > 
> > I'm happy to have it removed, and we can investigate solutions like this if
we
> > see a problem.
> 
> I will remove separate priorities for notifications for now.

Shoot, I think we've had some miscommunications.  I never meant to suggest
getting rid of "ANALYSIS_PRIORITY".  I meant to suggest getting rid of
"ANALYSIS_CONTINUE".

However, reading back through the code and my comments, I realize that I'd
misunderstood this code to be prioritizing analysis on a file-by-file basis, but
now I see that it's prioritizing analysis on a context-by-context basis.  That
changes things.

Now that I'm properly thinking about this code as operating on a
context-by-context basis, I'm not convinced that we want to do priorities this
way.  Effectively what we are saying is that we are going to first analyze all
contexts in round robin fashion.  Then when that's done we will do indexing
("search") for all contexts in round robin fashion.  Then when that's done we
will do refactoring for all contexts in round robin fashion.  That seems bad
because:

- By postponing indexing of context A until all other contexts have been
analyzed, we decrease the chances that the data we need for indexing is still in
the analysis cache, which means that indexing might do a lot of redundant work.

- By postponing refactoring of context A until all other contexts have been
analyzed and indexed, we penalize users who have a lot of contexts open.  If a
user requests a refactoring on context A, we really ought to focus on analyzing
and indexing context A so that we can get the refactoring done as soon as
possible--it should take priority over analyzing all other contexts.

This is making me think that maybe the only prioritization we want to do at this
point in the code is to make sure that (a) we fully operate on the priority
context (including search and refactoring) before doing operations on any other
contexts, and (b) as much as possible, we try to finish operating on one context
before moving on to the next (except when that conflicts with (a)).  Maybe
prioritization between analysis, search, and refactoring really belongs
exclusively within the context.