What version of Go are you using (go version)?

$ go version
go version devel +da4d58587e Sat Dec 7 15:57:30 2019 +0000 linux/amd64
$ go list -m golang.org/x/tools
golang.org/x/tools v0.0.0-20191213221258-04c2e8eff935
$ go list -m golang.org/x/tools/gopls
golang.org/x/tools/gopls v0.1.8-0.20191213221258-04c2e8eff935

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

$ go env
GO111MODULE="on"
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/myitcv/.cache/go-build"
GOENV="/home/myitcv/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/myitcv/gostuff"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/myitcv/gos"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/myitcv/gos/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/myitcv/gostuff/src/github.com/myitcv/govim/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build191688178=/tmp/go-build -gno-record-gcc-switches"

What did you do?

See below for background. We very quickly established this is related to the deep completion Budget being exceeded. Hence #36142 (comment) and the updated title.

Background

In govim test complete_deep_fuzzy we verify that deep fuzzy completions work.

The test is as simple as ensuring that the input file:

package main

func main() {
	var a struct {
		b struct {
			crikey int
		}
		d int
	}
	var x int
	x = a.ck
}

when completed after a.ck results in:

package main

func main() {
	var a struct {
		b struct {
			crikey int
		}
		d int
	}
	var x int
	x = a.b.crikey
}

However, over 50% of the time we're seeing this test fail because no completion items are returned.

Here are the gopls logs from a failing and passing run:

• fail.log
• pass.log

Much like #35638 this is a timing/race related issue and hard to reproduce standalone. Generally I find this fails when my machine is under high stress.

The test can be run on a machine that uses Docker via:

go test -exec="dockexec govim/govim:go1.13.4_vim_v8.1.2253_v1 -t -e VIM_FLAVOR=vim" -count=1 -v -run "TestScripts/scenario_default/complete_deep_fuzzy" ./cmd/govim

(download of Docker image may initially take some time)

What did you expect to see?

A consistently passing test.

What did you see instead?

Intermittent failures.

cc @stamblerre @muirdm