Source generator hangs with long target members

[TimothyMakkison]

Mapperly currently uses a slow way of finding matching properties. Most of the time this isnt a problem as $n$ will usually be less than 5. However performance can take a hit when a member contains a lot of capital letters ie:
USERS_UNIQUE_PRINTER_ID or doesn't have a matching source property.

To get the full set of ordered partitions is $O(2^{(n-1)})$ and in a (very unlikely) worse case scenario (lots of types with almost matching members) will generate a lot of concatenated strings see here.

Benchmarks

Benchmarks for generating the Sample project. CarDto has a variable length all capital letters member.
13 chars

Method	Mean	Error	StdDev	Gen0	Allocated
Compile	42.09 ms	0.757 ms	0.708 ms	6363.6364	9.6 MB

15 chars

Method	Mean	Error	StdDev	Gen0	Allocated
Compile	259.8 ms	4.64 ms	7.09 ms	27000.0000	40.68 MB

16 chars

Method	Mean	Error	StdDev	Median	Gen0	Allocated
Compile	302.6 ms	8.99 ms	26.07 ms	293.3 ms	56000.0000	84.03 MB

17 chars

Method	Mean	Error	StdDev	Gen0	Allocated
Compile	1.100 s	0.0217 s	0.0232 s	116000.0000	173.53 MB

Fixes
This is an uncommon problem, so a warning or diagnostic could be made. Perhaps a check for members with over 10 capital letters.

I did have a couple of ideas for optimizing matching, for both normal complex mappings and worse case scenarios. Unfortunately most would change the order that members are mapped.

[latonz]

This does improve with #480, doesn't it?
We could probably add a maximum value to permutationsCount in Riok.Mapperly.Descriptors.MemberPathCandidateBuilder.BuildMemberPathCandidates or stop building indices after a max iteration limit in Riok.Mapperly.Descriptors.MemberPathCandidateBuilder.GetPascalCaseSplitIndices.

[TimothyMakkison]

#480 improves it but doesn't resolve the underlying issue.

I have a couple of solutions/ideas.

• Add a max number of iterations or a diagnostic warning for long member names.
• Cache or build an index of all possible source member paths.
• If ReadOnlySpan is supported, remove all allocations from member path builder (won't prevent $O(2^{(n-1)})$ time tho).
• If you are okay with changing the order members match, I have a depth first member matching algorithm. it only matches paths that exist so the member ABCDEFGHIJKLMN would take $O(n)$ time to determine that there are no matching paths.

[latonz]

I think changing the order is not an option as I think the current order makes sense and changing it would probably be a breaking change. For now I think limiting the number of permutations and probably emit an info should be sufficient.
The algorithm could probably be optimised taking the known member into account and using a trie data structure or similar.