starred/terminal
1
0
Fork 0
mirror of https://github.com/microsoft/terminal.git synced 2026-04-28 17:12:56 +00:00
Code Issues 19.0k Packages Projects Releases 20 Wiki Activity

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

New Issue
Open
opened 2026-01-31 05:44:41 +00:00 by claunia · 2 comments
claunia commented 2026-01-31 05:44:41 +00:00
Owner
Copy Link

Originally created by @jazzdelightsme on GitHub (May 18, 2022).

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).

Originally created by @jazzdelightsme on GitHub (May 18, 2022). ### 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`: ```c++ 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).
claunia added the Area-SettingsIssue-BugProduct-Terminal labels 2026-01-31 05:44:41 +00:00
claunia commented 2026-01-31 05:44:42 +00:00
Author
Owner
Copy Link

@KalleOlaviNiemitalo commented on GitHub (May 18, 2022):

Previously discussed in https://github.com/microsoft/terminal/pull/10341#issuecomment-856168045.

@KalleOlaviNiemitalo commented on GitHub (May 18, 2022): Previously discussed in <https://github.com/microsoft/terminal/pull/10341#issuecomment-856168045>.
claunia commented 2026-01-31 05:44:42 +00:00
Author
Owner
Copy Link

@lhecker commented on GitHub (May 18, 2022):

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.
@lhecker commented on GitHub (May 18, 2022): 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.
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
⛺ Reserved
A11yCO
A11yMAS
A11ySev1
A11ySev2
A11ySev3
A11yTTValidated
A11yUsable
A11yVoiceAccess
A11yWCAG
Area-Accessibility
Area-AtlasEngine
Area-AzureShell
Area-Build
Area-Build
Area-Chat
Area-CmdPal
Area-CodeHealth
Area-Commandline
Area-CookedRead
Area-DefApp
Area-Extensibility
Area-Fonts
Area-GroupPolicy
Area-i18n
Area-Input
Area-Interaction
Area-Interop
Area-Localization
Area-Output
Area-Performance
Area-Portable
Area-Quality
Area-Remoting
Area-Rendering
Area-Schema
Area-Server
Area-Settings
Area-SettingsUI
Area-ShellExtension
Area-ShellExtension
Area-ShellExtension
Area-Suggestions
Area-Suggestions
Area-TerminalConnection
Area-TerminalControl
Area-Theming
Area-UserInterface
Area-VT
Area-Windowing
Area-WPFControl
AutoMerge
Blocking-Ingestion
Culprit-Centennial
Culprit-WinUI
Disability-All
Disability-Blind
Disability-LowVision
Disability-Mobility
External-Blocked-WinUI3
Fixed
Gathering-Data
good first issue
HCL-E+D
HCL-WindowsTerminal
Help Wanted
Impact-Compatibility
Impact-Compliance
Impact-Correctness
Impact-Visual
In-PR
InclusionBacklog
InclusionBacklog-Windows TerminalWin32
InclusionCommitted-202206
Issue-Bug
Issue-Docs
Issue-Feature
Issue-Feature
Issue-Question
Issue-Samples
Issue-Scenario
Issue-Task
Needs-Attention
Needs-Author-Feedback
Needs-Bisect
Needs-Discussion
Needs-Repro
Needs-Tag-Fix
Needs-Tag-Fix
Needs-Triage
No-Recent-Activity
Priority-0
Priority-1
Priority-2
Priority-3
Product-Cmd.exe
Product-Colortool
Product-Colortool
Product-Colortool
Product-Conhost
Product-Conpty
Product-Meta
Product-Powershell
Product-Terminal
Product-WSL
pull-request
Mirrored from GitHub Pull Request
 Resolution-Answered
Resolution-By-Design
Resolution-Duplicate
Resolution-External
Resolution-Fix-Available
Resolution-Fix-Committed
Resolution-No-Repro
Resolution-Won't-Fix
Severity-Blocking
Severity-Crash
Severity-DataLoss
spam
this-will-be-a-breaking-change
Tracking-External
WindowsTerminal_Win32
Work-Item
zAskModeBug
zInbox-Bug
No Label Area-Settings Issue-Bug Product-Terminal
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
claunia
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: starred/terminal#17510
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?