feat: nextest profile inheritance

[asder8215]

This PR implements a way for nextest profiles to inherit from other profiles as mentioned in #387.

[codecov[bot]]

Codecov Report

:x: Patch coverage is 98.24561% with 6 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 80.43%. Comparing base (3abb8ca) to head (47a843a). :warning: Report is 63 commits behind head on main.

Files with missing lines	Patch %	Lines
nextest-runner/src/config/elements/inherits.rs	95.89%	6 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #2786      +/-   ##
==========================================
+ Coverage   80.12%   80.43%   +0.31%     
==========================================
  Files         113      114       +1     
  Lines       26167    26587     +420     
==========================================
+ Hits        20966    21385     +419     
- Misses       5201     5202       +1     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[asder8215]

Hi @sunshowers, whenever you are able to, could you take a look at this PR in introducing profile inheritance?

The inheritance cycle detection is a little bit verbose due to how isolated nodes without edges are considered as SCCs by korasaju_scc(). I'm up for any feedback on how to reduce or improve that code.

I'll also add tests for profile inheritance (testing for cycles, nonexistent profile to inherit from, and whether config fields are appropriately filled in from an inherited profile) later today as well.

[sunshowers]

Can you just check for any SCCs with 2 or more nodes? That's how I've done this in the past.

[asder8215]

Isn't it possible for there to be a self referential SCC if the user sets the inherits to the current profile?

[sunshowers]

Ah I think we should just reject that case separately, no good reason to even try to model it or support it.

[asder8215]

I think I'm having a hard time finding out on how to do this in a neat and efficient manner.

Earlier, I wanted to use remove_node() to get rid of all isolated nodes in the first graph, but I realized that removing a node shifts the index of all the other nodes in the graph (which repeatedly checking for isolated nodes would have been an O(N^2) issue).

Instead of doing that, in the current implementation, I'm grabbing all nodes that are not isolated and inserting them into a new graph (which I'm not too sure if the way I'm doing this right now is the neatest way to do this). From reading through the docs in petgraph crate and searching up for examples, I wasn't sure if there was a better way to just keep the current graph and filter out isolated nodes since Graph<N, E, Directed, u32> doesn't have an .iter() method; it does have a .into_nodes_edges() method (which returns a (Vec<Node<N, Ix>>, Vec<Edge<E, Ix>>), but that itself means I'd be reconstructing the new graph again and in a clunky manner since Node<N, Ix> contains an [EdgeIndex<Ix>; 2] which I believe stores indices to the incoming and outgoing edges within Vec<Edge<E, Ix>>.

The one thing that comes up to my head is that I could do an earlier check here:

        // For each custom profile, we add a directed edge from the inherited node
        // to the current custom profile node
        for (profile_name, profile) in &self.other_profiles {
            if let Some(inherit_name) = &profile.inherits
                && let (Some(&from), Some(&to)) =
                    (profile_map.get(inherit_name), profile_map.get(profile_name))
            {
                profile_graph.add_edge(from, to, ());
            }
        }

to detect self referential SCCs and append it in a vec of cyclic inherited profile nodes and not insert it into the graph. This way, all non-isolated nodes are guaranteed to be in a chain of 2 or more nodes and I could create a new graph around this.

Just so I'm understanding correctly, when you say reject the self referential SCC case separately, do you want it's own error message to be thrown or should it be bundled up with all other detected SCCs? My understanding from zohkcat's PR is that you would find it nice for all SCCs to be printed out. The current implementation here does that through using kosaraju_scc(), but do you still want this behavior? Not sure because you asked earlier if I could check for any SCCs with 2<= nodes.

I also had a couple of questions regarding error handling for inherits:

• One difference that I made from zokhcat's PR is to raise the inheritance cycle error within deserialize_individual_config() instead of unwrapping it within make_profile(). I was wondering if this is the appropriate place to check for inheritance cycle?
• Currently, inherits does not have a ConfigParseErrorKind for a nonexistent profile that it wants to inherit from. This is because there's already a ProfileNotFound error within nextest-runner/src/errors.rs, which is used and raised in resolve_profile_chain(...) (called in make_profile()). I was wondering whether inheriting from a nonexistent profile should be detected as its own ConfigParseErrorKind and raised within deserialize_individual_config()?

How did you approach checking for SCCs with 2 or more nodes personally?

Edit: My apologies if I'm bombarding you with a lot of questions on this!

[sunshowers]

I think this can be way simpler than what you're imagining. There are 4 properties which need to be verified:

1. The default profile cannot inherit from any other profile. (And in fact, any profiles under default- cannot inherit from any other profile.)
2. A profile cannot inherit from itself.
3. A profile cannot inherit from a profile that isn't defined.

1, 2, and 3 don't need the construction of a graph at all, so check for them at the beginning. Then, construct a reduced graph with each node being a profile and each edge being an inherits relationship not rejected by any of the 1/2/3 checks above. (Include the implicit inherits relationship from each non-default profile to the default profile if inherits is not defined.) You can probably combine all 3 properties + graph construction into the same loop.

Then, the only remaining check is:

4. In this reduced graph, there are no SCCs with 2 or more nodes.

These 4 properties together should establish the overall invariant that the inheritance graph is well-formed (acyclic, and nothing points to unknown nodes.) You don't need to remove nodes or anything at any point, just break it up into graph and non-graph checks.

To report errors here I'd use an "error collector" or "diagnostic sink" pattern. Pass in a &mut Vec<InheritError> or something where InheritError is an enum with variants for all the properties, then push to that vector on seeing an error.

Hope this helps.

[asder8215]

I appreciate the advice and I agree with your properties and error handling here (didn't think about the error collector pattern!). I have a couple of follow up questions to ask on this.

• What if we had an SCC where the end node in the inheritance chain is self referential (i.e. A -> B -> C -> C)?
  • ~Formally, the SCC cycle is {A, B, C}, but the primary node that causes this cycle is C.~
  • Should we prioritize property 2 and report this as a self referential inheritance error? Or should we use property 4, look at it as an entire SCC, and report this as an inheritance chain cycle error?
  • My opinion is doing the former, as constructing the reduced graph with self referential profiles removed will prevent cycles from being detected from this inheritance chain case.
• When reporting errors for property 4, should we report the whole SCC or the first profile that contributes to this cycle?
  • With using the first profile, the benefit is that the error message will be much shorter, where if you have a cycle like A -> B -> C -> A, all you're reporting is an inheritance chain cycle at prof A
  • With using the entire SCC, the error message will be bigger, but it gives the user a better idea on where the cycle could be occurring. For example, A -> B -> C -> D -> E -> C, the SCC that will be detected is ~{A, B, C, D, E}~ {C, D, E}, but if I were to return prof ~A~ C, it may not be super clear to the user where the cycle is occurring
    • Edit: Okay, another idea that came to my head is to report the beginning element and last element in the SCC to let user know about the cycle range.

Edit: Correction on SCC, I think I got it wrong. It should be {C} instead of {A, B, C} for the first and {C, D, E} instead of {A, B, C, D, E} for the second one, but still curious about how reporting errors for inheritance chain cycles should work.

[sunshowers]

Can you just report the entire SCC? And definitely prioritize property 2.

[asder8215]

@sunshowers, I modified the code to follow the properties we talked about earlier and added a couple of test cases. Let me know if there's anything I should change or if there are any other test cases I should add here!

[asder8215]

Took your suggestions and modularized the check_inheritance_cycles() (now called custom_profile_inheritances(); there's a separate check_inheritance_cycles() function that fits the purpose of the name) into a few smaller functions for neatness.

I haven't sorted the SCC cycle vec in the new check_inheritance_cycles()-- not too sure how useful that would be since the SCCs are reported in cyclical order just can't deterministically show one cyclical order and I think it would be confusing to the user to not be able to visibly follow the cycle in the error. Let me know your thoughts on this!

[sunshowers]

With apologies, I need to tackle something urgently at work this week. Hoping to look at this by the end of the week.

[asder8215]

It's all good and no pressure or rush in checking this out.

[sunshowers]

Looks good overall -- I've fixed a few issues (particularly inheritance order being incorrect) and pushed them. Going to land once this passes CI and once I've had a final look.

[asder8215]

Okay sweet, it's nice to see that this got merged in. Thank you for the opportunity on letting me work on this issue!