Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/vgo: list -m includes spurious dependencies #24150

Closed
rogpeppe opened this issue Feb 27, 2018 · 5 comments

Comments

@rogpeppe
Copy link
Contributor

commented Feb 27, 2018

go version devel +104445e Wed Feb 7 19:22:09 2018 +0000 linux/amd64 vgo:2018-02-20.1

What did you do?

% cd /tmp
% export GOPATH=/tmp/testmodgopath
% mkdir testmod
% cd testmod
% cat > main.go
package main
func main() {}
% cat > go.mod
module "github.com/test/testmod"

require (
	"gopkg.in/macaroon-bakery.v2" v0.0.0-20180209090814-22c04a94d902
)
% vgo list -m
vgo: finding gopkg.in/macaroon-bakery.v2 v0.0.0-20180209090814-22c04a94d902
vgo: finding gopkg.in/yaml.v2 v0.0.0-20180108131554-1244d3ce02e3
vgo: finding gopkg.in/mgo.v2 v0.0.0-20160818020120-3f83fa500528
vgo: finding gopkg.in/macaroon.v2 v0.0.0-20171017153037-bed2a428da6e
vgo: finding gopkg.in/juju/environschema.v1 v0.0.0-20151104115810-7359fc7857ab
vgo: finding gopkg.in/yaml.v1 v0.0.0-20140924161607-9f9df34309c0
vgo: finding gopkg.in/check.v1 v0.0.0-20141024133853-64131543e789
vgo: finding github.com/juju/testing v0.0.0-20150421103242-c7042d828963
vgo: finding github.com/juju/schema v0.0.0-20150602101902-e32c2dd75b90
vgo: finding github.com/juju/loggo v0.0.0-20141117040526-dc8e19f7c70a
vgo: finding gopkg.in/httprequest.v1 v0.0.0-20171212180935-fdaf1bffa255
vgo: finding gopkg.in/yaml.v2 v0.0.0-20160301204022-a83829b6f129
vgo: finding gopkg.in/mgo.v2 v0.0.0-20160818015218-f2b6f6c918c4
vgo: finding gopkg.in/errgo.v1 v0.0.0-20151007153157-66cb46252b94
vgo: finding golang.org/x/tools v0.0.0-20160427052601-1f1b3322f67a
vgo: finding golang.org/x/net v0.0.0-20150829230318-ea47fc708ee3
vgo: finding golang.org/x/crypto v0.0.0-20160922170629-8e06e8ddd962
vgo: finding github.com/mattn/go-isatty v0.0.0-20160806122752-66b8e73f3f5c
vgo: finding github.com/mattn/go-colorable v0.0.0-20160731235417-ed8eb9e318d7
vgo: finding github.com/lunixbochs/vtclean v0.0.0-20160125035106-4fbf7632a2c6
vgo: finding github.com/juju/version v0.0.0-20160603194958-4ae6172c0062
vgo: finding github.com/juju/utils v0.0.0-20161003233226-28c01ec2ad93
vgo: finding gopkg.in/tomb.v1 v0.0.0-20141024135613-dd632973f1e7
vgo: finding gopkg.in/mgo.v2 v0.0.0-20151026163453-4d04138ffef2
vgo: finding gopkg.in/juju/names.v2 v0.0.0-20160525230723-e38bc90539f2
vgo: finding golang.org/x/crypto v0.0.0-20150830180642-aedad9a179ec
vgo: finding github.com/juju/testing v0.0.0-20160926125916-7177264a582e
vgo: finding github.com/juju/utils v0.0.0-20160926124957-d3ba4256601a
vgo: finding github.com/juju/testing v0.0.0-20160926104802-40381bc6e42e
vgo: finding github.com/juju/loggo v0.0.0-20160804221526-15901ae4de78
vgo: finding github.com/juju/httprequest v0.0.0-20160302100958-89d547093c45
vgo: finding gopkg.in/yaml.v2 v0.0.0-20150924142314-53feefa2559f
vgo: finding gopkg.in/errgo.v1 v0.0.0-20150707183445-150989630885
vgo: finding gopkg.in/check.v1 v0.0.0-20150626105028-b3d3430320d4
vgo: finding golang.org/x/tools v0.0.0-20150714180118-c5ca59aab8c2
vgo: finding golang.org/x/net v0.0.0-20150721022738-446d52dd4018
vgo: finding github.com/julienschmidt/httprouter v0.0.0-20150408170429-b59a38004596
vgo: finding github.com/juju/testing v0.0.0-20151010234657-5955efc6d5f6
vgo: finding github.com/juju/loggo v0.0.0-20150527035839-8477fc936adf
vgo: finding github.com/juju/httpprof v0.0.0-20141217160036-14bf14c30767
vgo: finding github.com/juju/gnuflag v0.0.0-20160809165214-4e76c5658185
vgo: finding github.com/juju/cmd v0.0.0-20160810125308-7c57a7d5a206
vgo: finding github.com/juju/testing v0.0.0-20161031103713-b8689951f6db
vgo: finding github.com/juju/loggo v0.0.0-20160818025724-3b7ece48644d
vgo: finding github.com/juju/ansiterm v0.0.0-20160817025220-c368f42cb4b3
vgo: finding github.com/juju/ansiterm v0.0.0-20160907234532-b99631de12cf
vgo: finding gopkg.in/errgo.v1 v0.0.0-20161222125816-442357a80af5
vgo: finding gopkg.in/check.v1 v0.0.0-20160105164936-4f90aeace3a2
vgo: finding golang.org/x/sys v0.0.0-20170201051245-7a6e5648d140
vgo: finding golang.org/x/net v0.0.0-20171004034648-a04bdaca5b32
vgo: finding golang.org/x/crypto v0.0.0-20170421043120-96846453c37f
vgo: finding github.com/rogpeppe/fastuuid v0.0.0-20150106093220-6724a57986af
vgo: finding github.com/lib/pq v0.0.0-20170603225454-8837942c3e09
vgo: finding github.com/julienschmidt/httprouter v0.0.0-20151013225520-77a895ad01eb
vgo: finding github.com/juju/webbrowser v0.0.0-20160309143629-54b8c57083b4
vgo: finding github.com/juju/version v0.0.0-20161031051906-1f41e27e54f2
vgo: finding github.com/juju/utils v0.0.0-20171122093653-4d9b38694f1e
vgo: finding gopkg.in/yaml.v2 v0.0.0-20170208141851-a3f3340b5840
vgo: finding gopkg.in/juju/names.v2 v0.0.0-20170515224847-0f8ae7499c60
vgo: finding gopkg.in/httprequest.v1 v0.0.0-20171103091905-35158f716c22
vgo: finding golang.org/x/text v0.0.0-20171102192421-88f656faf3f3
vgo: finding github.com/nu7hatch/gouuid v0.0.0-20131221200532-179d4d0c4d8d
vgo: finding github.com/masterzen/xmlpath v0.0.0-20140218185901-13f4951698ad
vgo: finding github.com/masterzen/winrm v0.0.0-20161014151040-7a535cd943fc
vgo: finding github.com/masterzen/simplexml v0.0.0-20160608183007-4572e39b1ab9
vgo: finding github.com/masterzen/azure-sdk-for-go v0.0.0-20161014135628-ee4f0065d00c
vgo: finding golang.org/x/crypto v0.0.0-20160811152348-595bbbd7f5f3
vgo: finding github.com/dgrijalva/jwt-go v0.0.0-20160729164851-63734eae1ef5
vgo: finding github.com/Azure/go-autorest v0.0.0-20160811212434-f0b1c4ee3551
vgo: finding golang.org/x/crypto v0.0.0-20160612191547-f3241ce85058
vgo: finding github.com/dgrijalva/jwt-go v0.0.0-20160617170158-f0777076321a
vgo: finding github.com/juju/mutex v0.0.0-20160617010907-59c26ee16344
vgo: finding github.com/juju/cmd v0.0.0-20170622125307-ad2437ef0ef2
vgo: finding github.com/juju/testing v0.0.0-20170608054451-2fe0e88cf232
vgo: finding github.com/juju/schema v0.0.0-20160420044203-075de04f9b7d
vgo: finding github.com/juju/retry v0.0.0-20151029024821-62c620325291
vgo: finding github.com/juju/postgrestest v0.0.0-20171221150903-15b53a8afa18
vgo: finding github.com/juju/loggo v0.0.0-20170605014607-8232ab8918d9
vgo: finding golang.org/x/sys v0.0.0-20161012001920-9bb9f0998d48
vgo: finding github.com/juju/errors v0.0.0-20150916125642-1b5e39b83d18
vgo: finding github.com/golang/protobuf v0.0.0-20161109072736-4bd1920723d7
MODULE                                 VERSION
github.com/test/testmod                -
github.com/Azure/go-autorest           v0.0.0-20160811212434-f0b1c4ee3551
github.com/dgrijalva/jwt-go            v0.0.0-20160729164851-63734eae1ef5
github.com/golang/protobuf             v0.0.0-20161109072736-4bd1920723d7
github.com/juju/ansiterm               v0.0.0-20160907234532-b99631de12cf
github.com/juju/cmd                    v0.0.0-20170622125307-ad2437ef0ef2
github.com/juju/errors                 v0.0.0-20150916125642-1b5e39b83d18
github.com/juju/gnuflag                v0.0.0-20160809165214-4e76c5658185
github.com/juju/httpprof               v0.0.0-20141217160036-14bf14c30767
github.com/juju/loggo                  v0.0.0-20170605014607-8232ab8918d9
github.com/juju/mutex                  v0.0.0-20160617010907-59c26ee16344
github.com/juju/postgrestest           v0.0.0-20171221150903-15b53a8afa18
github.com/juju/retry                  v0.0.0-20151029024821-62c620325291
github.com/juju/schema                 v0.0.0-20160420044203-075de04f9b7d
github.com/juju/testing                v0.0.0-20170608054451-2fe0e88cf232
github.com/juju/utils                  v0.0.0-20171122093653-4d9b38694f1e
github.com/juju/version                v0.0.0-20161031051906-1f41e27e54f2
github.com/juju/webbrowser             v0.0.0-20160309143629-54b8c57083b4
github.com/julienschmidt/httprouter    v0.0.0-20151013225520-77a895ad01eb
github.com/lib/pq                      v0.0.0-20170603225454-8837942c3e09
github.com/lunixbochs/vtclean          v0.0.0-20160125035106-4fbf7632a2c6
github.com/masterzen/azure-sdk-for-go  v0.0.0-20161014135628-ee4f0065d00c
github.com/masterzen/simplexml         v0.0.0-20160608183007-4572e39b1ab9
github.com/masterzen/winrm             v0.0.0-20161014151040-7a535cd943fc
github.com/masterzen/xmlpath           v0.0.0-20140218185901-13f4951698ad
github.com/mattn/go-colorable          v0.0.0-20160731235417-ed8eb9e318d7
github.com/mattn/go-isatty             v0.0.0-20160806122752-66b8e73f3f5c
github.com/nu7hatch/gouuid             v0.0.0-20131221200532-179d4d0c4d8d
github.com/rogpeppe/fastuuid           v0.0.0-20150106093220-6724a57986af
golang.org/x/crypto                    v0.0.0-20170421043120-96846453c37f
golang.org/x/net                       v0.0.0-20171004034648-a04bdaca5b32
golang.org/x/sys                       v0.0.0-20170201051245-7a6e5648d140
golang.org/x/text                      v0.0.0-20171102192421-88f656faf3f3
golang.org/x/tools                     v0.0.0-20160427052601-1f1b3322f67a
gopkg.in/check.v1                      v0.0.0-20160105164936-4f90aeace3a2
gopkg.in/errgo.v1                      v0.0.0-20161222125816-442357a80af5
gopkg.in/httprequest.v1                v0.0.0-20171212180935-fdaf1bffa255
gopkg.in/juju/environschema.v1         v0.0.0-20151104115810-7359fc7857ab
gopkg.in/juju/names.v2                 v0.0.0-20170515224847-0f8ae7499c60
gopkg.in/macaroon-bakery.v2            v0.0.0-20180209090814-22c04a94d902
gopkg.in/macaroon.v2                   v0.0.0-20171017153037-bed2a428da6e
gopkg.in/mgo.v2                        v0.0.0-20160818020120-3f83fa500528
gopkg.in/tomb.v1                       v0.0.0-20141024135613-dd632973f1e7
gopkg.in/yaml.v1                       v0.0.0-20140924161607-9f9df34309c0
gopkg.in/yaml.v2                       v0.0.0-20180108131554-1244d3ce02e3

This module list includes quite a few dependencies that are not actually dependencies of the chosen gopkg.in/macaroon-bakery.v2 module. For example gopkg.in.yaml.v1 should not be there.

The reason appears to be that dependencies are included if they're in the dependency list as it's first calculated.

For example, gopkg.in/yaml.v1 appears to be present because the dependencies.tsv file for gopkg.in/macaroon-bakery.v2 contains this line:

gopkg.in/juju/environschema.v1	git	7359fc7857abe2b11b5b3e23811a9c64cb6b01e0	2015-11-04T11:58:10Z

That commit of the gopkg.in/juju/environschema.v1 module has these lines in its dependencies.tsv file:

github.com/juju/testing	git	c7042d828963caa252862b759ef56ada297e8323	2015-04-21T10:32:42Z
gopkg.in/yaml.v1	git	9f9df34309c04878acc86042b16630b0f696e1de	2014-09-24T16:16:07Z

and that particular commit of the github.com/juju/testing module uses gopkg.yaml.v1.

However when all the dependencies are finally resolved, we end up using v0.0.0-20170608054451-2fe0e88cf232 of github.com/juju/testing which does not depend on yaml.v1 (neither does any other dependency).

I would suggest that the modules listed by vgo list -m should include only modules that are actual dependencies of the currently calculated versions, not modules that are depended on by versions not in use. It's perhaps telling that github.com/juju/testing is retrieved 6 times. Perhaps the find algorithm needs to be breadth-first, with all immediate dependencies solved before recursing?

@gopherbot gopherbot added this to the vgo milestone Feb 27, 2018

@magical

This comment has been minimized.

Copy link
Contributor

commented Feb 27, 2018

Also reported in the comments to Russ's Minimal Version Selection article, where ezyang points out that the algorithm as described doesn't seem to prune unused dependencies.

For algorithm 1, it seems that you can end up with unused modules in your build list with the current algorithm, when an older version has deps that a newer version does not. Concretely, suppose you have the dependency list:

A 1 -> B 1.1
A 1 -> C 1.1
B 1.1 -> D 1
C 1.1 -> B 1.2
B 1.2 (no deps)

IIUC, the algorithm will add D 1 to the build list, but eventually will select a version of B (1.2) which has no dependency on it.

@kardianos

This comment has been minimized.

Copy link
Contributor

commented Feb 28, 2018

The hard thing about unused dependencies is they are build tag dependant. While there is a maximum dependency graph for all tags, it is reasonably common to not care about a subset of them.

In other words, there are three definitions of unused:

  1. GOOS GOARCH current unused.
  2. Some module specific defined list of tags or list of ignore tags unused.
  3. Max graph unused.

It would be nice if go list could take a tag Boolean expression and report the use status of the module. We could then use that primative to compute and of the thee views above. Then to prune something like:

go list -unused -tag "!appengine AND !solaris" | go get -remove

@rsc

This comment has been minimized.

Copy link
Contributor

commented Mar 27, 2018

Re @magical's comment, this is working as designed & intended. Including D 1 in the build list is part of making sure there is a single, minimal, unique answer. Consider:

A -> X
A -> Y
X -> B 1.1
Y -> B 1.2
B 1.1 - > D 1.2
B 1.2 -> D 1.1

Even though A->X, A->Y, X->B 1.1, Y->B 1.2 implies that we're going to use B 1.2, it's still important to chase down what B 1.1 wants and incorporate that information, because that's what X wants too. X is being built against D 1.2. If we didn't follow into B 1.1, we might build X with too old a D and not be able to build at all.

In the case where B 1.2 does not depend on D at all, then there's an argument for dropping D from the go list -m output, but we still have to look and see what D 1.2 in turn requires and apply any of its constraints to move any versions forward.

@rsc

This comment has been minimized.

Copy link
Contributor

commented Mar 27, 2018

Pruning is #24101; closing this one as working.

@rsc rsc closed this Mar 27, 2018

@rogpeppe

This comment has been minimized.

Copy link
Contributor Author

commented Apr 3, 2018

@rsc With respect, I see this as a different issue, although they are related.

Issue #24101 is about pruning dependencies that are explicitly listed in a go.mod file which might have nothing at all to do with the current program (for example when a given package import line has been removed).

This issue is concerned with the fact that vgo list -m prints modules that aren't used at all by the current module (although, as you say, they will need to have been considered when calculating the current module set).

In the case where B 1.2 does not depend on D at all, then there's an argument for dropping D from the go list -m output, but we still have to look and see what D 1.2 in turn requires and apply any of its constraints to move any versions forward.

Yes, I think it's important to drop D from the go list -m output even if it has been used in the intermediate dependency calculation, because whether more than one major version of a given package is used by a module can be a significant correctness issue. For example, a package may assume ownership of some global resource, or it might contain a registry that must be uniformly used across the program. Historically, using gopkg.in, I have found it extremely useful to have a canonical list of all the modules used by the program. The go list -m command seems like it's the way to do that now. †

I won't reopen the issue, because my reasoning may well be wrong here, but ISTM that it might be worth tracking this issue separately from #24101.

† One thing that I think I'll miss is that with all dependencies explicitly listed (using dependencies.tsv in our case), it was very obvious at code review time when a new major version (often a potential bug, not uncommonly introduced when using goimports) was introduced. I wonder what a good approach to dealing with that in the vgo world might be.

@golang golang locked and limited conversation to collaborators Apr 3, 2019

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
5 participants
You can’t perform that action at this time.