Skip to content

Commit

Permalink
internal/lsp: adopt bcmills' suggestion for an improved debouncer API
Browse files Browse the repository at this point in the history 
The debounce API becomes both more testable and more elegant when using
channels rather than callbacks to signal events, as suggested by bcmills
in CL 333349. Adopt these suggestions.

Fixes golang/go#45085

Change-Id: Ic1843f582d514af8aa109c24f5e3311536e54a60
Reviewed-on: https://go-review.googlesource.com/c/tools/+/334252
Trust: Robert Findley <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Bryan C. Mills <bcmills@google.com>
  • Loading branch information
@findleyr
findleyr committed Jul 13, 2021
1 parent ae0deb7 commit 8e85a28
Show file tree
Hide file tree
Showing 4 changed files with 61 additions and 121 deletions.
82 changes: 36 additions & 46 deletions internal/lsp/debounce.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -9,73 +9,63 @@ import (
"time"
)

type debounceFunc struct {
type debounceEvent struct {
order uint64
done chan struct{}
}

type debouncer struct {
mu sync.Mutex
funcs map[string]*debounceFunc
mu sync.Mutex
events map[string]*debounceEvent
}

func newDebouncer() *debouncer {
return &debouncer{
funcs: make(map[string]*debounceFunc),
events: make(map[string]*debounceEvent),
}
}

// debounce waits timeout before running f, if no subsequent call is made with
// the same key in the intervening time. If a later call to debounce with the
// same key occurs while the original call is blocking, the original call will
// return immediately without running its f.
//
// If order is specified, it will be used to order calls logically, so calls
// with lesser order will not cancel calls with greater order.
func (d *debouncer) debounce(key string, order uint64, timeout time.Duration, f func()) {
if timeout == 0 {
// Degenerate case: no debouncing.
f()
return
}
// debounce returns a channel that receives a boolean reporting whether,
// by the time the delay channel receives a value, this call is (or will be)
// the most recent call with the highest order number for its key.
func (d *debouncer) debounce(key string, order uint64, delay <-chan time.Time) <-chan bool {
okc := make(chan bool, 1)

// First, atomically acquire the current func, cancel it, and insert this
// call into d.funcs.
d.mu.Lock()
current, ok := d.funcs[key]
if ok && current.order > order {
// If we have a logical ordering of events (as is the case for snapshots),
// don't overwrite a later event with an earlier event.
d.mu.Unlock()
return
}
if ok {
close(current.done)
if prev, ok := d.events[key]; ok {
if prev.order > order {
// If we have a logical ordering of events (as is the case for snapshots),
// don't overwrite a later event with an earlier event.
d.mu.Unlock()
okc <- false
return okc
}
close(prev.done)
}
done := make(chan struct{})
next := &debounceFunc{
next := &debounceEvent{
order: order,
done: done,
}
d.funcs[key] = next
d.events[key] = next
d.mu.Unlock()

// Next, wait to be cancelled or for our wait to expire. There is a race here
// that we must handle: our timer could expire while another goroutine holds
// d.mu.
select {
case <-done:
case <-time.After(timeout):
d.mu.Lock()
if d.funcs[key] != next {
// We lost the race: another event has arrived for the key and started
// waiting. We could reasonably choose to run f at this point, but doing
// nothing is simpler.
go func() {
ok := false
select {
case <-delay:
d.mu.Lock()
if d.events[key] == next {
ok = true
delete(d.events, key)
} else {
// The event was superseded before we acquired d.mu.
}
d.mu.Unlock()
return
case <-done:
}
delete(d.funcs, key)
d.mu.Unlock()
f()
}
okc <- ok
}()

return okc
}
85 changes: 15 additions & 70 deletions internal/lsp/debounce_test.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -5,25 +5,16 @@
package lsp

import (
"fmt"
"strings"
"sync"
"testing"
"time"

errors "golang.org/x/xerrors"
)

func TestDebouncer(t *testing.T) {
t.Parallel()

const evtWait = 30 * time.Millisecond
const initialDelay = 400 * time.Millisecond

type event struct {
key string
order uint64
fired bool
wantFired bool
}
tests := []struct {
Expand Down Expand Up @@ -65,72 +56,26 @@ func TestDebouncer(t *testing.T) {
for _, test := range tests {
test := test
t.Run(test.label, func(t *testing.T) {
try := func(delay time.Duration) (bool, error) {
d := newDebouncer()
var wg sync.WaitGroup
var validMu sync.Mutex
valid := true
prev := -1
for i, e := range test.events {
wg.Add(1)
go func(i int, e *event) {
// Check if goroutines were not scheduled in the intended order.
validMu.Lock()
if prev != i-1 {
valid = false
}
prev = i
validMu.Unlock()
d := newDebouncer()

d.debounce(e.key, e.order, delay, func() {
e.fired = true
})
wg.Done()
}(i, e)
// For a bit more fidelity, sleep to try to make things actually
// execute in order. This shouldn't have to be perfect: as long as we
// don't have extreme pauses the test should still pass.
if i < len(test.events)-1 {
time.Sleep(evtWait)
}
}
wg.Wait()
delays := make([]chan time.Time, len(test.events))
okcs := make([]<-chan bool, len(test.events))

var errs []string
for _, event := range test.events {
if event.fired != event.wantFired {
msg := fmt.Sprintf("(key: %q, order: %d): fired = %t, want %t",
event.key, event.order, event.fired, event.wantFired)
errs = append(errs, msg)
}
}
var err error
if len(errs) > 0 {
err = errors.New(strings.Join(errs, "\n"))
}
return valid, err
// Register the events in deterministic order, synchronously.
for i, e := range test.events {
delays[i] = make(chan time.Time, 1)
okcs[i] = d.debounce(e.key, e.order, delays[i])
}

if err := retryInvalid(initialDelay, try); err != nil {
t.Error(err)
// Now see which event fired.
for i, okc := range okcs {
event := test.events[i]
delays[i] <- time.Now()
fired := <-okc
if fired != event.wantFired {
t.Errorf("[key: %q, order: %d]: fired = %t, want %t", event.key, event.order, fired, event.wantFired)
}
}
})
}
}

// retryInvalid runs the try func up to three times with exponential back-off
// in its duration argument, starting with the provided initial duration. Calls
// to try are retried if their first result indicates that they may be invalid,
// and their second result is a non-nil error.
func retryInvalid(initial time.Duration, try func(time.Duration) (valid bool, err error)) (err error) {
delay := initial
for attempts := 3; attempts > 0; attempts-- {
var valid bool
valid, err = try(delay)
if err == nil || valid {
return err
}
delay += delay
}
return err
}
5 changes: 3 additions & 2 deletions internal/lsp/diagnostics.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,7 @@ import (
"path/filepath"
"strings"
"sync"
"time"

"golang.org/x/tools/internal/event"
"golang.org/x/tools/internal/lsp/debug/log"
Expand Down Expand Up @@ -119,10 +120,10 @@ func (s *Server) diagnoseSnapshot(snapshot source.Snapshot, changedURIs []span.U
// delay.
s.diagnoseChangedFiles(ctx, snapshot, changedURIs, onDisk)
s.publishDiagnostics(ctx, false, snapshot)
s.diagDebouncer.debounce(snapshot.View().Name(), snapshot.ID(), delay, func() {
if ok := <-s.diagDebouncer.debounce(snapshot.View().Name(), snapshot.ID(), time.After(delay)); ok {
s.diagnose(ctx, snapshot, false)
s.publishDiagnostics(ctx, true, snapshot)
})
}
return
}

Expand Down
10 changes: 7 additions & 3 deletions internal/lsp/text_synchronization.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -9,6 +9,7 @@ import (
"context"
"fmt"
"path/filepath"
"time"

"golang.org/x/tools/internal/event"
"golang.org/x/tools/internal/jsonrpc2"
Expand Down Expand Up @@ -241,7 +242,11 @@ func (s *Server) didModifyFiles(ctx context.Context, modifications []source.File
// process changes in order.
s.pendingOnDiskChanges = append(s.pendingOnDiskChanges, pending)
ctx = xcontext.Detach(ctx)
delayed := func() {
okc := s.watchedFileDebouncer.debounce("", 0, time.After(delay))
go func() {
if ok := <-okc; !ok {
return
}
s.fileChangeMu.Lock()
var allChanges []source.FileModification
// For accurate progress notifications, we must notify all goroutines
Expand All @@ -263,8 +268,7 @@ func (s *Server) didModifyFiles(ctx context.Context, modifications []source.File
for _, done := range dones {
close(done)
}
}
go s.watchedFileDebouncer.debounce("", 0, delay, delayed)
}()
return nil
}

Expand Down

0 comments on commit 8e85a28

Please sign in to comment.