Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix(target-size): do not crash for nodes with many overlapping widgets #4373

Merged
merged 9 commits into from
Mar 18, 2024

Conversation

straker
Copy link
Contributor

@straker straker commented Mar 14, 2024

Decided that instead of returning null, splitRects should return an empty array to signify the bail out state. splitRects returns the original node if there is no overlap, so an empty array allows us to still signify the desired state as well as still allow all the code that used it to treat it as an array. Otherwise I would need to propagate a null check through 4 different functions in target-offset-evaluate (getOffset, getTargetSize, getTargetRects, etc.).

In trying to catch the new state in target-size-evaluate it became difficult to figure out the logic of all the different things that needed to be checked to know what to return. I decided to refactor the entire function to make the flow easier by eliminating possibilities higher up so the if statements only needed to check a single condition rather than multiple conditions. The two key parts of the refactor was to move the overflow content check to the top.

For overflowing content the return would always be undefined unless the target had sufficient size, in which case it would return true. This meant we can check those states first and not have to check for it again, which greatly simplifies all the logic of the if statements.

In terms of the magic number for when to exit early, it was based on running performance tests against the code in #4359 and logging how long the inner loop took as uniqueRects size grew. Once the time got to ~2 seconds to complete I took that number then reduced it by a factor of 10x for slower machines.

uniqueRects: 4
time: 0.10000014305114746

uniqueRects: 7
time: 0

uniqueRects: 10
time: 0

uniqueRects: 13
time: 0

uniqueRects: 16
time: 0

uniqueRects: 19
time: 0.09999990463256836

uniqueRects: 22
time: 0

uniqueRects: 25
time: 0

uniqueRects: 34
time: 0.10000014305114746

uniqueRects: 43
time: 0.09999990463256836

uniqueRects: 55
time: 0.09999990463256836

uniqueRects: 75
time: 0

uniqueRects: 90
time: 0.09999990463256836

uniqueRects: 122
time: 0.09999990463256836

uniqueRects: 140
time: 0.10000014305114746

uniqueRects: 187
time: 0.20000004768371582

uniqueRects: 208
time: 0.09999990463256836

uniqueRects: 273
time: 0.10000014305114746

uniqueRects: 297
time: 0.8999998569488525

uniqueRects: 383
time: 0.2999999523162842

uniqueRects: 410
time: 0.20000004768371582

uniqueRects: 520
time: 0.2999999523162842

uniqueRects: 548
time: 0.2999999523162842

uniqueRects: 683
time: 0.2999999523162842

uniqueRects: 692
time: 0.5

uniqueRects: 720
time: 0.5999999046325684

uniqueRects: 775
time: 0.7000000476837158

uniqueRects: 872
time: 1.1999998092651367

uniqueRects: 1029
time: 0.5999999046325684

uniqueRects: 1267
time: 1

uniqueRects: 1610
time: 1.2000000476837158

uniqueRects: 2083
time: 1.3999998569488525

uniqueRects: 2089
time: 1.8999998569488525

uniqueRects: 2095
time: 1.9000000953674316

uniqueRects: 2101
time: 1.7000000476837158

uniqueRects: 2107
time: 1.6000001430511475

uniqueRects: 2113
time: 1.7999999523162842

uniqueRects: 2119
time: 1.6000001430511475

uniqueRects: 2125
time: 1.7000000476837158

uniqueRects: 2131
time: 1.6000001430511475

uniqueRects: 2164
time: 1.6999998092651367

uniqueRects: 2329
time: 1.7000000476837158

uniqueRects: 2365
time: 1.7000000476837158

uniqueRects: 2565
time: 2

uniqueRects: 2604
time: 2.0999999046325684

uniqueRects: 2840
time: 2.5

uniqueRects: 2882
time: 2.6000001430511475

uniqueRects: 3157
time: 2.5

uniqueRects: 3202
time: 2.5999999046325684

uniqueRects: 3519
time: 2.700000047683716

uniqueRects: 3567
time: 3.0999999046325684

uniqueRects: 3929
time: 3.4000000953674316

uniqueRects: 3980
time: 15.5

uniqueRects: 4390
time: 6.599999904632568

uniqueRects: 4442
time: 4.200000047683716

uniqueRects: 4901
time: 4.299999952316284

uniqueRects: 5534
time: 5.299999952316284

uniqueRects: 6366
time: 6.3999998569488525

uniqueRects: 7429
time: 7.8999998569488525

uniqueRects: 8762
time: 10.600000143051147

uniqueRects: 10407
time: 12.5

uniqueRects: 12409
time: 16.100000143051147

uniqueRects: 14816
time: 21.5

uniqueRects: 17677
time: 30.199999809265137

uniqueRects: 17686
time: 33.200000047683716

uniqueRects: 17695
time: 33.200000047683716

uniqueRects: 17704
time: 34.5

uniqueRects: 17713
time: 34.09999990463257

uniqueRects: 17722
time: 34.299999952316284

uniqueRects: 17731
time: 34.59999990463257

uniqueRects: 17740
time: 34.09999990463257

uniqueRects: 17749
time: 35.5

uniqueRects: 17806
time: 34.89999985694885

uniqueRects: 18319
time: 35.09999990463257

uniqueRects: 18379
time: 36.10000014305115

uniqueRects: 18951
time: 37.200000047683716

uniqueRects: 19014
time: 38.59999990463257

uniqueRects: 19646
time: 39.700000047683716

uniqueRects: 19712
time: 41.40000009536743

uniqueRects: 20407
time: 43.09999990463257

uniqueRects: 20476
time: 43.69999980926514

uniqueRects: 21237
time: 44.5

uniqueRects: 21309
time: 47.200000047683716

uniqueRects: 22139
time: 48.5

uniqueRects: 22214
time: 50.799999952316284

uniqueRects: 23116
time: 51.799999952316284

uniqueRects: 23192
time: 55.299999952316284

uniqueRects: 24167
time: 57

uniqueRects: 27536
time: 66.39999985694885

uniqueRects: 31476
time: 85.89999985694885

uniqueRects: 36043
time: 131.5

uniqueRects: 41300
time: 230.20000004768372

Closes: #4359
Closes: #4360

@straker straker requested a review from a team as a code owner March 14, 2024 22:45
Copy link
Contributor

@WilcoFiers WilcoFiers left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Couple editorials, and I think this needs an integration test.

lib/checks/mobile/target-size.json Outdated Show resolved Hide resolved
locales/_template.json Outdated Show resolved Hide resolved
lib/checks/mobile/target-size-evaluate.js Outdated Show resolved Hide resolved
lib/checks/mobile/target-size-evaluate.js Outdated Show resolved Hide resolved
lib/commons/math/split-rects.js Show resolved Hide resolved
@@ -10,7 +10,7 @@ import {
* Determine if an element has a minimum size, taking into account
* any elements that may obscure it.
*/
export default function targetSize(node, options, vNode) {
export default function targetSizeEvaluate(node, options, vNode) {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We talked about adding an early pass for elements that have 10x the required size. I don't mind that in a different PR, but I don't think we should close the issues until we have that in.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think I'd prefer to move that to it's own pr so we can get this in quicker. Which ticket do you think it shouldn't close?

@WilcoFiers WilcoFiers merged commit 1dbea83 into develop Mar 18, 2024
21 checks passed
@WilcoFiers WilcoFiers deleted the target-size-perf branch March 18, 2024 18:27
WilcoFiers added a commit that referenced this pull request Mar 25, 2024
##
[4.9.0](v4.8.4...v4.9.0)
(2024-03-25)

### Features

- adding the wcag131 tag to the aria-hidden-body rule
([#4349](#4349))
([dd4c3c3](dd4c3c3)),
closes [#4315](#4315)
- **checks:** deprecate aria-busy check
([#4356](#4356))
([be0b555](be0b555)),
closes [#4347](#4347)
[#4340](#4340)
- **color:** add color channel values and luminosity, saturation, clip
functions ([#4366](#4366))
([9e70199](9e70199)),
closes
[/github.com//pull/4365/files#r1517706612](https://github.com/dequelabs//github.com/dequelabs/axe-core/pull/4365/files/issues/r1517706612)
- **i18n:** add Greek Translations
([#3836](#3836))
([3ea9a48](3ea9a48))
- **i18n:** Add Italian translation
([#4344](#4344))
([de1baa9](de1baa9))
- **i18n:** Add Simplified Chinese translation
([#4379](#4379))
([bda7c8d](bda7c8d))
- **i18n:** Add Taiwanese Mandarin translation
([#4299](#4299))
([c5e11de](c5e11de))

### Bug Fixes

- Add LICENSE-3RD-PARTY.txt file
([#4304](#4304))
([daa0fe6](daa0fe6))
- add Object.values polyfill for node <=6
([#4274](#4274))
([5eb867b](5eb867b))
- **aria-required-children:** avoid confusing aria-busy message in
failures ([#4347](#4347))
([591607d](591607d)),
closes [#fail13](https://github.com/dequelabs/axe-core/issues/fail13)
[#4340](#4340)
- avoid reading element-specific node properties of non-element node
types ([#4317](#4317))
([b853b18](b853b18)),
closes [#4316](#4316)
[#4316](#4316)
- **color-contrast:** handle text that is outside `overflow: hidden`
ancestor ([#4357](#4357))
([bdb7300](bdb7300)),
closes [#4253](#4253)
- **color-contrast:** support color blend modes hue, saturation, color,
luminosity ([#4365](#4365))
([7ae4761](7ae4761))
- **d.ts:** RawNodesResult issues
([#4229](#4229))
([d660518](d660518))
- **d.ts:** RunOptions.reporter can be any string
([#4218](#4218))
([e53f5c5](e53f5c5))
- **i18n:** update Italian translations
([#4377](#4377))
([4d65d4b](4d65d4b))
- **listitem:** clarify roleNotValid message
([#4374](#4374))
([0f8a9af](0f8a9af))
- **scrollable-region-focusable:** missing wcag213 tag
([#4201](#4201))
([0080a72](0080a72))
- **target-size:** always pass 10x targets (avoid perf bottleneck)
([#4376](#4376))
([be327c4](be327c4))
- **target-size:** do not crash for nodes with many overlapping widgets
([#4373](#4373))
([1dbea83](1dbea83)),
closes [#4359](#4359)
[#4359](#4359)
[#4360](#4360)
- **utils/get-selector:** ignore 'xmlns' attribute when generating a
selector ([#4303](#4303))
([938b411](938b411))

This PR was opened by a robot 🤖 🎉
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
2 participants