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

Target-size performance problem for element with many overlapping nodes #4359

Closed
straker opened this issue Mar 5, 2024 · 2 comments · Fixed by #4373 · May be fixed by wingn8t/wagtail#1, gurudeep9/mattermost-test#2 or abdulrahman305/docs#4
Labels
performance Performance related issues support

Comments

@straker
Copy link
Contributor

straker commented Mar 5, 2024

Running the target-size rule on the following html (which creates a tabpanel with a table with 20 rows, with each row containing links and buttons) causes the rule to be super slow. With even more rows and or clickable objects inside the table it can cause the rule to hang indefinitely.

<main>
  <div id="tabpanel" role="tabpanel" tabindex="0">
    <table id="tab-table"></table>
  </div>
</main>

<script>
  let html = '';
  for (let i = 0; i < 20; i++) {
    html += `
      <tr>
        <td><a href="#">Hello</a></td>
        <td>Hello</td>
        <td>Hello</td>
        <td>Hello</td>
        <td>Hello</td>
        <td>Hello</td>
        <td>Hello</td>
        <td><button>view</button></td>
        <td><button>download</button></td>
        <td><button>expand</button></td>
      </tr>
    `;
    document.querySelector('#tab-table').innerHTML = html;
  }
</script>

The main culprit is the splitRect function used by the target-offset check. The check passes it a list of ~80 rects that are obscuring the tabpanel target (each of the anchors and buttons). Split rects loops over this list and tries to split each one with the tabpanel rect, which can add up to 4 rects per split to the uniqueRects array. Do this 80 times and the uniqueRects array ends up with 37000+ rects.

We need to come up with a better way to split the larger rect with a bunch of smaller rects.

@dbjorge
Copy link
Contributor

dbjorge commented Mar 6, 2024

Neat problem. Reminds me of https://stackoverflow.com/a/6634668, though not exactly the same without reduction

@straker straker added this to the Axe-core 4.9.0 milestone Mar 6, 2024
@straker
Copy link
Contributor Author

straker commented Mar 13, 2024

As a stop-gap to fix the problem, we're going to make the splitRects function exit early and return null if it detects more than some determined amount of uniqueRects. That way axe will be able to complete the scan and not freeze up. We'll then look into finding a better way to split rects that doesn't run into this problem in a later version.

WilcoFiers added a commit that referenced this issue Mar 18, 2024
#4373)

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

---------

Co-authored-by: Wilco Fiers <WilcoFiers@users.noreply.github.com>
WilcoFiers added a commit that referenced this issue 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