jpedroh / generic-merge / 8914939962

80%

push

github

feat(matching): use the Hungarian Algorithm for unordered matching (#50)

Our current approach to unordered node matching relies on a naive
assumption: that all nodes possess an identifier. While this holds true
for most nodes we've encountered thus far, such as method and property
declarations within a Java class, it proves insufficient when attempting
to match nodes lacking a label, like static blocks in Java. In such
cases, calculations for matchings may yield incorrect results,
consequently leading to erroneous merges.

This pull request introduces a solution for matching unordered nodes via
the Assignment Problem, utilizing the Hungarian Algorithm to resolve it.
This approach mirrors the one used in jDime.

Given the widespread recognition of the Hungarian Algorithm, we rely on
the implementation provided by the
[pathfinding](https://github.com/evenfurther/pathfinding) crate. This
simplifies our implementation efforts, as we only need to provide the
weights matrix and extract the matching information from the solution.

A workaround had to be implemented since pathfinding expects the input
matrix weight to have the same number of rows and columns, which might
not always be true in our case since nodes can have a different number
of children. The solution involves initializing the remaining
columns/rows with 0.

For now, our naive label implementation has been bypassed and is not
being utilized. In a further pull request, the idea is to resort to the
Hungarian algorithm only if the nodes are unlabeled, as it's
significantly more complex than merely matching identifiers.

513 of 876 branches covered (58.56%)

Branch coverage included in aggregate %.

45 of 47 new or added lines in 2 files covered. (95.74%)

2386 of 2490 relevant lines covered (95.82%)

12457.95 hits per line