Rules that have multiple dependencies may get run multiple times, and will still get run if one of those dependencies fails (as long as another one also passes)

[mcmire]

Say you have a rule that has two dependencies:

export default buildRule({
  name: RuleName.ValidateChangelog,
  description: 'Is `CHANGELOG.md` well-formatted?',
  dependencies: [
    RuleName.RequireValidPackageManifest,
    RuleName.RequireChangelog
  ],
  execute: async (ruleExecutionArguments) => {
    // ...
  }
});

There are two problems with this:

1. The rule may get run more than once. This happens because the rule exists underneath two separate nodes in the rule tree: 1) require-valid-package-manifest and 2) require-changelog. The rule tree does not look like this:

   graph BT
   validate-changelog --> require-valid-package-manifest;
   validate-changelog --> require-changelog;

   but rather this:

   graph BT
   validate-changelog1["validate-changelog"] --> require-valid-package-manifest;
   validate-changelog2["validate-changelog"] --> require-changelog;

2. Because there are two instances of the same rule, the rule may still run even if, for instance, require-valid-package-manifest fails, but require-changelog passes.

(Possible solutions moved to a comment.)

[mcmire]

To solve this, we will want to add logic which prevents a rule from getting executed more than once.

Past this, we have two possible routes:

1. Remove the concept of a rule tree and execute the rules in alphabetical order. If a rule has dependencies, attempt to execute them first if we haven't already done so. Then, output the results in a flat list, like #42 is doing, except again, in alphabetical order. (We will add categories later.)
2. Continue to use a rule tree, but rework how it's built so that a rule does not appear more than once. Then, modify how rules are executed so that as the rule tree is iterated over, ensure that a rule only gets run if ALL of its dependencies pass (as opposed to what happens now, which is that a rule gets run is ANY of its dependencies pass).

[MajorLift]

Could we level-order traverse the rule tree with topological sort or depth-first-search?

This would prevent rules from being processed redundantly, it would satisfy the ALL dependencies must pass for each rule requirement, and wouldn't keep us from producing a flattened list as output. It's also probably the most theoretically efficient way to handle this if I'm understanding the problem correctly.

Edit: If we are able to iterate over the rule tree in alphabetic order, wouldn't we be able to create a dependency graph first that has a 1-1 relationship between each rule and each graph node?

[mcmire]

@MajorLift Hmm, good thoughts. I think rather than using breadth- or depth-first iteration or even sorting the list alphabetically as I suggested, sorting the whole list of rules in the tree topologically first and then iterating over all of them as you suggested makes sense to me. Perhaps there is a way to prevent from flattening the list, but note that we don't need to keep the existing hierarchy as we plan on reorganizing the list into categories anyway: https://github.com/MetaMask/module-lint/issues/64