Refactor graph representation

[sywhang]

This is the first PR to prepare Dig for in-graph modifications.

This PR contains several changes to allow further extensibility in the graph representation used in Dig, and decouple reflection Type info from the graph algorithms as much as possible.

Specifically, this PR makes the following changes:

• Add internal/graph package which contains Dig-agnostic graph algorithm used for cycle detection
• Remove the somewhat duplicated embedded cycle detection logic in Container and cycle.go
• Add graphHolder type in Container which holds all the graph nodes and implements the graph iterator interface used for graph algorithm in internal/graph.
• Add paramGroupedSlice as part of node in graph.
• Remove the param visitor funcs and related helpers.
• Rename node to constructorNode.

There is also a change in the way cycle error messages are displayed. Previously, the errors looked like:

typeA provided by funcName (file_location.go:line_number)
  depends on typeB provided by funcName (file_location.go:line_number)
  depends on typeC provided by funcName (file_location.go:line_number)
 ... and so on

This error message generation depended on knowing the "edge" info between nodes, which is the reflect.Type that connects the two constructor nodes.

Now that the graph representation holds not only constructor nodes but also value groups, and because graph representation does not know what type holds the nodes together, this needs to be changed.

Now, the error messages look like:

func(*typeB) *typeA provided by funcName(file_location.go:line_number)
  depends on func(*typeC) *typeB provided by funcName(file_location.go:line_number)
  depends on func(*typeA) *typeC provided by funcName(file_location.go:line_number)
... and so on

(Note that the function signature is now printed instead of the type that holds the nodes as dependencies).

For param value groups, the error message skips over it so that the error message doesn't look cluttered but that can be subject to change in the future.

[codecov[bot]]

Codecov Report

Merging #301 (65c512b) into master (173b7b1) will increase coverage by 0.03%. The diff coverage is 96.17%.

@@            Coverage Diff             @@
##           master     #301      +/-   ##
==========================================
+ Coverage   98.26%   98.29%   +0.03%     
==========================================
  Files          14       16       +2     
  Lines        1153     1174      +21     
==========================================
+ Hits         1133     1154      +21     
+ Misses         13       12       -1     
- Partials        7        8       +1     

Impacted Files	Coverage Δ
stringer.go	100.00% <ø> (ø)
visualize.go	89.74% <89.74%> (ø)
graph.go	90.90% <90.90%> (+1.16%)	:arrow_up:
cycle_error.go	100.00% <100.00%> (ø)
dig.go	100.00% <100.00%> (ø)
internal/graph/graph.go	100.00% <100.00%> (ø)
param.go	98.22% <100.00%> (+1.13%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 173b7b1...65c512b. Read the comment docs.

[CLAassistant]

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you all sign our Contributor License Agreement before we can accept your contribution.
2 out of 3 committers have signed the CLA.

:white_check_mark: abhinav
:white_check_mark: sywhang
:x: schomatis
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

[shirchen]

High-level comment: can you refactor existing dig_test file to add DeferAcyclicVerification option to some tests. I think we are currently missing some code coverage around it. Ref GO-76

[sywhang]

It's also a bit unclear how keying on the constructor type is safe? Is it not possible that we provide two constructors with the same signature? Like, say two constructors pushing to the same value group?

@abhinav So I thought about this for a while and used multiple ways to test it, and current implementation does work. I also thought this wouldn't work, (or shouldn't) so I did some digging and it turns out that the current implementation is still fine. Here's why:

Currently the way this works is that graphHolder.orders is a map that maps a type of either a constructor or a value group to an order.

Conceptually, if we provide two constructors of the same type, then it is okay for the graph representation to contain a single node to represent that, because currently, dependency resolution is still performed by the providers map defined in Container, and that is a map of key to a list of constructorNodes. The graph representation still holds because cycle detection algorithm (which is the only graph algorithm that we currently run on this representation) does not care if there is one node or multiple constructorNodes with the same types.

For example, given 4 constructors ctor1, ctor2, ctor3, and ctor4 where ctor3 and ctor4 are of the same type, this graph:

is the "same" graph as this one:

.