Ensure equality when hashing default args and no args in actions by carlos-zamora · Pull Request #10341 · microsoft/terminal

carlos-zamora · 2021-06-04T22:57:28Z

Summary of the Pull Request

#10297 found a bug in ActionMap where the ToggleCommandPalette key chord could not be found using GetKeyBindingForAction.

This was caused by the following:

AddAction: when adding the action, the ActionAndArgs is basically added as {ToggleCommandPalette, ToggleCommandLineArgs{}} (Note the default ctor used for the action args)
GetKeyBindingForAction: we're searching for an ActionAndArgs structured as {ToggleCommandPalette, nullptr}
Since these are technically two different actions, we are unable to find it.

This issue was fixed by making the Hash(ActionAndArgs) function smarter! If the ActionAndArgs has no args, but the ShortcutAction supports args, generate the args using the default ctor.

By making Hash() smarter, everybody benefits from this logic! We can basically now enforce that ActionAndArgs{ <X>, nullptr } == ActionAndArgs{ <X>, <default_ctor> }.

Validation Steps Performed

Added a test.
Tested this on Replace feedback button with command palette button in dropdown #10297's branch and this does fix the bug

DHowett · 2021-06-04T23:43:48Z

This can't be serviced to Stable as that code doesn't exist in Stable. Be careful with those servicing tags...

src/cascadia/TerminalSettingsModel/ActionMap.cpp

lhecker

Woops I meant to comment and not approve.
I'll request changes, since I can't undo an approval.

src/cascadia/TerminalSettingsModel/ActionMap.cpp

KalleOlaviNiemitalo · 2021-06-05T08:07:19Z

It seems static InternalActionID Hash(const Model::ActionAndArgs& actionAndArgs) might have some hash collisions for non-equal inputs but each of its callers assumes that InternalActionID being equal means the ActionAndArgs is equal. That's not caused by this PR, though.

carlos-zamora · 2021-06-07T18:03:10Z

This can't be serviced to Stable as that code doesn't exist in Stable. Be careful with those servicing tags...

My bad. Wasn't sure if ActionMap was in stable or not. Removing the tag.

carlos-zamora · 2021-06-07T18:34:45Z

It seems static InternalActionID Hash(const Model::ActionAndArgs& actionAndArgs) might have some hash collisions for non-equal inputs but each of its callers assumes that InternalActionID being equal means the ActionAndArgs is equal. That's not caused by this PR, though.

Yeah. This is where I wish I took a course on cryptography and hashing in college haha. I don't think that theoretically there could be no collisions. That said, in practice, we haven't seen any so we're probably fine for now.

lhecker

Long term a more robust equality-solution would be nice, but that's for another day.
Until then: LGTM.

src/cascadia/TerminalSettingsModel/ActionMap.cpp

DHowett · 2021-06-10T17:25:14Z

src/cascadia/TerminalSettingsModel/ActionMap.cpp

+#define ON_ALL_ACTIONS_WITH_ARGS(action)                                    \
+    case ShortcutAction::action:                                            \
+        /* If it does, hash the default values for the args.*/              \
+        hashedArgs = gsl::narrow_cast<size_t>(make<action##Args>().Hash()); \


I low-key hate that this requires constructing an entire object filled with default values to calculate a hash; it could be wildly expensive. Can you profile to make sure we're not making a bunch of objects just to destroy them moments later? Both CPU and memory-wise.

I feel like we could get around this by maintaining a static .Empty singleton of each of these if this is what we need to Hash... or cache the hash of the empty one as a singleton...

To be fair though none of the ActionArgs constructors are complex at the moment.

As such I "propose" the following solution:

add constexpr to the default constructors of all ActionArgs classes

add constexpr to all their Hash() member functions

add constexpr to the getters of the ACTION_ARG and WINRT_PROPERTY macros

write:
case ShortcutAction::action: hashedArgs = implementation::action##Args{}.Hash(); break;

This will probably compile to constants in release mode and in debug mode it won't allocate anything on the heap.

That will be illegal because we're not using winrt::make for something that's known to be a runtimeclass.

carlos-zamora · 2021-06-10T21:16:23Z

Added EmptyHash() which lazy loads and caches the hash value of a default constructed action args.

Took the average of 5 perf traces in VS:

	Allocations (delta)	Heap Size (delta)
`main`	70511.2	13431.52
`d83a764`	71268	13472.34

With this change, we see an average increase of 756.8 Allocations and 70.82 Heap Size.

Scenario:

First snapshot taken on first ActionMap::AddAction
Second snapshot taken after Windows Terminal loads and the Command Palette is opened

These hashes are always first used in AddAction, but then they are used a few times in ActionMap (i.e. adding more actions, action comparison, action queries, etc...).

src/cascadia/TerminalSettingsModel/ActionArgs.h

Co-authored-by: Dustin L. Howett <[email protected]>

ghost · 2021-06-16T22:43:14Z

Hello @DHowett!

Because this pull request has the AutoMerge label, I will be glad to assist with helping to merge this pull request once all check-in policies pass.

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (`@msftbot`) and give me an instruction to get started! Learn more here.

) ## Summary of the Pull Request #10297 found a bug in `ActionMap` where the `ToggleCommandPalette` key chord could not be found using `GetKeyBindingForAction`. This was caused by the following: - `AddAction`: when adding the action, the `ActionAndArgs` is basically added as `{ToggleCommandPalette, ToggleCommandLineArgs{}}` (Note the default ctor used for the action args) - `GetKeyBindingForAction`: we're searching for an `ActionAndArgs` structured as `{ToggleCommandPalette, nullptr}` - Since these are _technically_ two different actions, we are unable to find it. This issue was fixed by making the `Hash(ActionAndArgs)` function smarter! If the `ActionAndArgs` has no args, but the `ShortcutAction` _supports_ args, generate the args using the default ctor. By making `Hash()` smarter, everybody benefits from this logic! We can basically now enforce that `ActionAndArgs{ <X>, nullptr } == ActionAndArgs{ <X>, <default_ctor> }`. ## Validation Steps Performed - Added a test. - Tested this on #10297's branch and this does fix the bug (cherry picked from commit b3b6484)

carlos-zamora added zPreview-Service-Consider labels Jun 4, 2021

carlos-zamora requested a review from DHowett June 4, 2021 23:00

carlos-zamora mentioned this pull request Jun 4, 2021

Replace feedback button with command palette button in dropdown #10297

Merged

1 task

lhecker approved these changes Jun 5, 2021

View reviewed changes

src/cascadia/TerminalSettingsModel/ActionMap.cpp Outdated Show resolved Hide resolved

lhecker requested changes Jun 5, 2021

View reviewed changes

ghost added the Needs-Author-Feedback The original author of the issue/PR needs to come back and respond to something label Jun 5, 2021

lhecker reviewed Jun 5, 2021

View reviewed changes

src/cascadia/TerminalSettingsModel/ActionMap.cpp Outdated Show resolved Hide resolved

ghost removed the Needs-Author-Feedback The original author of the issue/PR needs to come back and respond to something label Jun 7, 2021

carlos-zamora removed the zStable-Service-Consider label Jun 7, 2021

carlos-zamora assigned lhecker Jun 7, 2021

carlos-zamora added this to the Terminal v1.10 milestone Jun 7, 2021

lhecker approved these changes Jun 7, 2021

View reviewed changes

src/cascadia/TerminalSettingsModel/ActionMap.cpp Outdated Show resolved Hide resolved

carlos-zamora unassigned lhecker Jun 7, 2021

carlos-zamora added the Needs-Second It's a PR that needs another sign-off label Jun 9, 2021

ghost requested review from PankajBhojwani, leonMSFT, miniksa and zadjii-msft June 9, 2021 17:32

DHowett requested changes Jun 10, 2021

View reviewed changes

ghost added the Needs-Author-Feedback The original author of the issue/PR needs to come back and respond to something label Jun 10, 2021

carlos-zamora force-pushed the dev/cazamor/bugfix/hash-hidden-args branch from 03dd81d to a5e6d46 Compare June 10, 2021 18:30

ghost removed the Needs-Author-Feedback The original author of the issue/PR needs to come back and respond to something label Jun 10, 2021

carlos-zamora and others added 3 commits June 10, 2021 13:38

Ensure equality when hashing default args and no args in actions

56d48a2

use switch-case instead

1b6846e

Remove unnecessary braces from cases

96a08ba

cache the special hash value

d83a764

carlos-zamora force-pushed the dev/cazamor/bugfix/hash-hidden-args branch from a5e6d46 to d83a764 Compare June 10, 2021 21:10

carlos-zamora assigned DHowett Jun 10, 2021

DHowett reviewed Jun 10, 2021

View reviewed changes

src/cascadia/TerminalSettingsModel/ActionArgs.h Outdated Show resolved Hide resolved

Use magic static for EmptyHash

160b17a

Co-authored-by: Dustin L. Howett <[email protected]>

carlos-zamora mentioned this pull request Jun 11, 2021

Epic: Introduce Actions page to the Settings UI #6900

Open

12 tasks

DHowett approved these changes Jun 16, 2021

View reviewed changes

DHowett added the AutoMerge Marked for automatic merge by the bot when requirements are met label Jun 16, 2021

ghost merged commit b3b6484 into main Jun 16, 2021

ghost deleted the dev/cazamor/bugfix/hash-hidden-args branch June 16, 2021 22:43

DHowett removed the zPreview-Service-Consider label Jul 7, 2021

WSLUser mentioned this pull request Aug 23, 2021

Boost hashing performance with Robin Hood #11016

Closed

KalleOlaviNiemitalo mentioned this pull request May 18, 2022

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

Open

This pull request was closed.

Conversation

carlos-zamora commented Jun 4, 2021

Summary of the Pull Request

Validation Steps Performed

Uh oh!

DHowett commented Jun 4, 2021

Uh oh!

Uh oh!

lhecker left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

KalleOlaviNiemitalo commented Jun 5, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

carlos-zamora commented Jun 7, 2021

Uh oh!

carlos-zamora commented Jun 7, 2021

Uh oh!

lhecker left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

DHowett Jun 10, 2021

Choose a reason for hiding this comment

Uh oh!

miniksa Jun 10, 2021

Choose a reason for hiding this comment

Uh oh!

lhecker Jun 10, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

DHowett Jun 10, 2021

Choose a reason for hiding this comment

Uh oh!

carlos-zamora commented Jun 10, 2021

Uh oh!

Uh oh!

ghost commented Jun 16, 2021

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (@msftbot) and give me an instruction to get started! Learn more here.

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

KalleOlaviNiemitalo commented Jun 5, 2021 •

edited

Loading

lhecker Jun 10, 2021 •

edited

Loading

p.s. you can customize the way I help with merging this pull request, such as holding this pull request until a specific person approves. Simply @mention me (`@msftbot`) and give me an instruction to get started! Learn more here.