InternalActionID is a hash, which cannot be depended on for equality comparison

[jazzdelightsme]

Windows Terminal version

latest

Windows build number

10.0.22621.0

Other Software

No response

Steps to reproduce

From doc\specs\#885 - Terminal Settings Model\Actions Addendum.md:

std::map<KeyChord, InternalActionID> _KeyMap;
std::map<InternalActionID, Command> _ActionMap;

InternalActionID will be a hash of ActionAndArgs such that two ActionAndArgs with the same ShortcutAction and IActionArgs output the same hash value.

A hash function can be used to quickly determine if two items are NOT equal: if they have different hashes, they are not the same.

However, if the hashes are the same, that does not mean the items are equal. It just means that you've had a "hash collision", and need to perform a thorough equality check. But Terminal uses InternalActionID as a dictionary key (and the values are not lists), so if you have a collision, an action gets dropped.

I ran into this trying to add a new action--the hash function was not great, so there were collisions, which resulted in very confusing behavior, since some of my actions appeared to be straight-up do the wrong thing, but not just any wrong thing; but the same thing as some other instance of the command with different arguments!

I was fortunately able to improve the hash function, but this still depends on getting lucky.

Expected Behavior

I expected to be able to add a new ActionAndArgs, even though it had a not-very-good hash function, without some of my actions being mysteriously subsumed by others.

Actual Behavior

Some new actions appeared to do the wrong thing (the same thing as some other action that had different args, but ended up with the same hash value).

[KalleOlaviNiemitalo]

Previously discussed in #10341 (comment).

[lhecker]

There's two ways forward IMO:

• Quick fix: Replace til::hasher's FNV1a algorithm with a modern one. My personal preference is xxhash 3 which has a very low collision rate in line with the birthday paradox. It would effectively reduce the likelihood of this being an issue for a long time with a low development cost. Something more compact, like Murmurhash would largely work the same though...
• Long term fix: ActionMap.cpp's Hash() functions are already build in terms of til::hasher's generic Write() function, which only accepts binary data. We can make our own, equivalent Write() function which builds a std::vector<std::byte> out of the binary data instead, then we hash the vector and finally keep both, the vector and the memoized hash, around in a struct InternalActionID. The hash would keep most comparisons and hashmap operations cheap, and the vector would serve for quick memcmp-comparisons. InternalActionID can also be aliased as a std::shared_ptr so that the behavior of it as a "cheap" ID would be the same as before.