I have a real 7,000-line Go program (not so big)
that took over two minutes to report a trivial init cycle.
I thought the compiler was in an infinite loop but
it was actually just very slow.
CL 170062 rewrote init cycle reporting but replaced
a linear-time algorithm with an exponential one:
it explores all paths through the call graph of functions
involved in the cycle.
The net effect was that Go 1.12 took 0.25 seconds to load,
typecheck, and then diagnose the cycle in my program,
while Go 1.13 takes 600X longer.
This CL makes the new reporting code run in linear time,
restoring the speed of Go 1.12 but preserving the semantic
fixes from CL 170062.
Change-Id: I7d6dc95676d577d9b96f5953b516a64db93249bf
Reviewed-on: https://go-review.googlesource.com/c/go/+/282314
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com>