x/tools/gopls: unimported package search using up completion budget

[muirdm]

On master (5d1fdd8fa3469142b9369713b23d8413d6d83189) I'm seeing mysteriously disappearing deep completions:

In the above example, I expect the candidate "foo.blah.baz.l" to continue to show up, but it disappears as I type.

I think completing fo<> works because "fo" matches enough "easy" unimported candidates so we don't hit the slow unimported package case. Once I get to foo<>, we hit the slow case in unimportedPackages and that gobbles up the completion budget so there is none left for deep completions.

The above example doesn't reproduce in a vacuum. I assume you need a "big enough" go.mod to hit some threshold. Below is the go.mod and foo.go file I used for my example:

Big go.mod

``` module foo go 1.13 require ( cloud.google.com/go v0.53.0 cloud.google.com/go/storage v1.5.0 github.com/GoogleCloudPlatform/opentelemetry-operations-go/exporter/trace v0.2.0 github.com/NYTimes/gziphandler v1.1.1 github.com/aws/aws-lambda-go v1.6.0 github.com/aws/aws-sdk-go v1.29.11 github.com/aws/aws-sdk-go-v2 v0.20.0 github.com/aws/aws-xray-sdk-go v1.0.0-rc.14.0.20200127194803-2226f427d358 github.com/cbroglie/mustache v1.0.2-0.20180526013208-73b1f3905474 github.com/certifi/gocertifi v0.0.0-20180905225744-ee1a9a0726d2 // indirect github.com/codingsince1985/geo-golang v0.0.0-20170710130525-51713292c3b1 github.com/dgrijalva/jwt-go v3.2.1-0.20190620180102-5e25c22bd5d6+incompatible // indirect github.com/disintegration/imaging v1.6.2 github.com/duosecurity/duo_api_golang v0.0.0-20190308151101-6c680f768e74 github.com/felixge/httpsnoop v1.0.1 github.com/fiorix/wsdl2go v1.4.7 github.com/fogleman/gg v1.2.1-0.20190220221249-0403632d5b90 github.com/gedex/inflector v0.0.0-20170307190818-16278e9db813 // indirect github.com/getsentry/raven-go v0.2.0 github.com/go-playground/locales v0.11.2-0.20170327191450-1e5f1161c641 github.com/go-playground/universal-translator v0.16.1-0.20170327191703-71201497bace github.com/gocql/gocql v0.0.0-20200624222514-34081eda590e github.com/gogo/protobuf v1.3.1 github.com/golang/protobuf v1.3.4 github.com/golang/snappy v0.0.1 github.com/gomodule/redigo v1.8.2 github.com/googleapis/gax-go/v2 v2.0.5 github.com/gorilla/context v1.1.1 // indirect github.com/gorilla/csrf v1.0.3-0.20160926154116-0ff6a2ce414a github.com/gorilla/handlers v0.0.0-20160816184729-a5775781a543 github.com/gorilla/mux v0.0.0-20160920230813-757bef944d0f github.com/gorilla/schema v0.0.0-20160817190122-0164a00ab4cd github.com/gorilla/securecookie v0.0.0-20160816222338-c13558c2b1c4 // indirect github.com/gorilla/websocket v1.4.1 github.com/hashicorp/go-uuid v1.0.2-0.20191001231223-f32f5fe8d6a8 // indirect github.com/jcmturner/gofork v1.0.0 // indirect github.com/klauspost/compress v1.9.3-0.20191112205758-ce4ce462ed0a // indirect github.com/kr/fs v0.0.0-20131111012553-2788f0dbd169 // indirect github.com/leonelquinteros/gotext v1.3.2-0.20180705143725-8e9d9df2e208 github.com/lib/pq v1.2.1-0.20190813065522-78223426e7c6 github.com/mailgun/mailgun-go/v3 v3.6.4 github.com/mailru/easyjson v0.7.1 github.com/manyminds/api2go v0.0.0-20181019084807-186a8a2128df github.com/mattn/go-sqlite3 v2.0.3+incompatible github.com/matttproud/golang_protobuf_extensions v1.0.1 // indirect github.com/microcosm-cc/bluemonday v1.0.3 github.com/paulmach/go.geo v0.0.0-20161214220750-7ab6b01a30d0 github.com/paulmach/go.geojson v0.0.0-20161109192638-16c6a8e9da10 // indirect github.com/pkg/browser v0.0.0-20180916011732-0a3d74bf9ce4 github.com/prometheus/client_golang v0.9.0-pre1.0.20180410130117-e11c6ff8170b github.com/prometheus/client_model v0.0.0-20190812154241-14fe0d1b01d4 github.com/psanford/getlogin v0.0.0-20180808181731-1377b4b71adb github.com/samuel/go-zookeeper v0.0.0-20170815201139-e6b59f6144be github.com/sideshow/apns2 v0.20.0 github.com/slack-go/slack v0.6.4 github.com/snowflakedb/gosnowflake v1.3.4 github.com/streadway/amqp v0.0.0-20190827072141-edfb9018d271 github.com/tealeg/xlsx v0.0.0-20181024002044-dbf71b6a931e github.com/zhangpeihao/goamf v0.0.0-20140409082417-3ff2c19514a8 go.mozilla.org/pkcs7 v0.0.0-20180823194901-e990b50b8fb7 go.uber.org/ratelimit v0.1.0 go.uber.org/zap v1.15.0 gocloud.dev v0.19.0 golang.org/x/crypto v0.0.0-20200622213623-75b288015ac9 golang.org/x/exp v0.0.0-20200207192155-f17229e696bd golang.org/x/image v0.0.0-20191009234506-e7c1f5e7dbb8 golang.org/x/net v0.0.0-20200625001655-4c5254603344 golang.org/x/oauth2 v0.0.0-20200107190931-bf48bf16ab8d golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd golang.org/x/text v0.3.2 golang.org/x/time v0.0.0-20190308202827-9d24e82272b4 golang.org/x/tools v0.0.0-20200731060945-b5fad4ed8dd6 gonum.org/v1/gonum v0.6.2 google.golang.org/api v0.20.0 google.golang.org/genproto v0.0.0-20200303153909-beee998c1893 google.golang.org/grpc v1.30.0 gopkg.in/alexcesaro/quotedprintable.v3 v3.0.0-20150716171945-2caba252f4dc // indirect gopkg.in/asn1-ber.v1 v1.0.0-20170511165959-379148ca0225 // indirect gopkg.in/gomail.v2 v2.0.0-20160411212932-81ebce5c23df gopkg.in/guregu/null.v2 v2.1.2 // indirect gopkg.in/jarcoal/httpmock.v1 v1.0.0-20180719183105-8007e27cdb32 gopkg.in/jcmturner/gokrb5.v7 v7.3.0 // indirect gopkg.in/ldap.v2 v2.5.1 gopkg.in/olivere/elastic.v5 v5.0.86 gopkg.in/urfave/cli.v1 v1.20.0 gopkg.in/yaml.v2 v2.2.7 honnef.co/go/tools v0.0.1-2019.2.3 layeh.com/radius v0.0.0-20180718204440-ae3c365c0348 mvdan.cc/gofumpt v0.0.0-20200802201014-ab5a8192947d ) ```

foo.go

``` package main import ( "time" ) func main() { var foo struct { blah struct { baz struct { l *time.Location } } } var _ *time.Location = fo } ```

Below is a CPU pprof from me spamming completion after foo<>: pprof.samples.cpu.045.pb.gz

[stamblerre]

Thanks for figuring out this repro!

/cc @heschik @dandua98

[gopherbot]

Change https://golang.org/cl/257967 mentions this issue: internal/lsp/source: use completion budget for only deep completions

[gopherbot]

Change https://golang.org/cl/257974 mentions this issue: internal/lsp/source: run unimported completions after other deep completions.

[gopherbot]

Change https://golang.org/cl/258286 mentions this issue: internal/lsp/source: run deep completions before unimported completions