a11y traversal: sort locally; use new sorting algorithm #16253

yjbanov · 2018-04-04T23:27:01Z

Remove global sorting that's not supported by iOS. Instead it sorts locally using a new algorithm illustrated here.
RTL
Remove nextNodeId/previousNodeId

Fixes #12187
Fixes #14375
Fixes #14570 (together with flutter/engine#4937)

TODO:

remove traces of geometric sort order (e.g. the enum option)
pass hit test order so it can be applied on Android (iOS doesn't support it; this requires an engine-side change)

/cc @goderbauer @gspencergoog

goderbauer

Some high level comments:

We should remove the useless DebugSemanticsDumpOrder.geometricOrder option and instead replace it with a DebugSemanticsDumpOrder.traversalOrder option that allows you to print the semantics tree in, well, traversal order.
I am still a little afraid of the complexity of this algorithm. I know, this should be mostly mitigated by the fact that n will be small, but still...

goderbauer · 2018-04-10T06:34:17Z

packages/flutter/lib/src/material/date_picker.dart

Why the indirection via _MonthPickerSortKey? I think I'd find this easier to read/understand if it would just say sortKey: const OrdinalSortKey(1.0) right here.

In general keys are grouped by type, so using plain OrdinalSortKey would cause these nodes to be sorted together with potentially unrelated nodes that roll up under the same parent. That's probably not going to happen in the current implementation of the picker.

goderbauer · 2018-04-10T06:35:55Z

packages/flutter/test/material/bottom_navigation_bar_test.dart

I assume the previousNodeId/nextNodeId here get removed in a follow-up PR? Maybe remove the "// Should be x" comments for now as these just seem more confusing now?

goderbauer · 2018-04-10T06:44:01Z

packages/flutter/test/material/date_picker_test.dart

nit: these lists were easier to read when there was one entry per line as before.

I used generateTestSemanticsExpressionForCurrentSemanticsTree to update this test. I'll fix that method in a separate change when the dust settles.

goderbauer · 2018-04-10T06:46:02Z

packages/flutter/lib/src/semantics/semantics.dart

Does the sort key still have to be its own data type? Why do we not simplify this to be just a double now?

A double value is undocumentable, so it's unclear what it means to have your nodes sorted together with nodes authored by someone else. The numbers would look magical in the source code. But if the sort keys are provided by one author then they can define and use a custom type.

goderbauer · 2018-04-10T06:50:30Z

packages/flutter/lib/src/semantics/semantics.dart

Position as determined by default sort order?

True. Added.

goderbauer · 2018-04-10T07:24:02Z

packages/flutter/lib/src/semantics/semantics.dart

bonus points: would be great to link to the graphic from you slides here.

goderbauer · 2018-04-10T07:36:12Z

packages/flutter/lib/src/semantics/semantics.dart

to avoid all this mapping, can search not operate on semanticsnodes and sortedIds be a List<SemanticNode>?

It uses the position in the list as a tie breaker to guarantee that the sorting is stable. So for now I think this is the most idiomatic method. I also measured the efficiency of the entire algorithm across many of the Flutter Gallery screens. It never exceeded 100µs on Moto G4. This is not surprising as the SemanticsNode tree is very sparse compared to the RenderNode tree.

goderbauer · 2018-04-10T07:38:04Z

packages/flutter/lib/src/semantics/semantics.dart

do we have to do all this work to bring nodes, that specify a sort key, into default sort order only to re-sort them then according to their sort key?

goderbauer · 2018-04-10T07:43:06Z

packages/flutter/test/material/bottom_navigation_bar_test.dart

Unfortunately, this test still doesn't verify that the traversal order is defined correctly -- and I believe we currently have no way of asserting traversal order in a widget test like this because at this point the SemanticNodes have not been sorted yet?

It does now. After fad0555 hasSemantics tests traversal order by default.

Perfect. 👍

goderbauer · 2018-04-10T07:45:12Z

packages/flutter/test/widgets/sliver_semantics_test.dart

Again, we need to find a way to assert that things are in the correct traversal order in a test.

goderbauer

This looks good!

Can you update what's left to do in the PR description? I believe it's remove geometric sort order and add hit testing?

goderbauer · 2018-04-19T17:08:01Z

examples/flutter_gallery/lib/gallery/app.dart

Directionality is not enough to set the semantic textDirection? Might be worth filing an issue about this.

Done. #16835

goderbauer · 2018-04-19T17:08:26Z

examples/flutter_gallery/lib/gallery/app.dart

Is this change intentional?

Oops. Reverted.

goderbauer · 2018-04-19T17:12:03Z

packages/flutter/test/widgets/semantics_traversal_test.dart

goderbauer · 2018-04-19T17:14:22Z

packages/flutter/test/widgets/semantics_traversal_test.dart

Love all these test cases. Should we add some test cases that use artificial sort keys?

We have them. They just live in one of the semantics_#_test.dart files. We should revise this at some point. It's hard to tell what each of those files is testing.

goderbauer · 2018-04-19T17:18:29Z

examples/flutter_gallery/lib/main.dart

revert this file?

Oops, pulled in my experiments. Fixed.

goderbauer · 2018-04-19T17:19:42Z

packages/flutter/test/widgets/semantics_tester.dart

Should this be traversalOrder by default?

It is now. Thanks for the suggestiong.

goderbauer · 2018-04-19T17:22:39Z

packages/flutter/test/material/bottom_navigation_bar_test.dart

Perfect. 👍

goderbauer · 2018-04-19T17:25:12Z

examples/flutter_gallery/lib/gallery/app.dart

Is this required for every App? Should it be part of MaterialApp? What changes if I don't specify a top level textDirection for semantics?

I guess it reverts to paint order?

Reverting for now. Let's address this in #16835.

goderbauer · 2018-04-19T17:26:06Z

packages/flutter/lib/src/semantics/semantics.dart

Why call _childrenInDefaultOrder twice in this case?

My bad, the first one is unnecessary.

goderbauer · 2018-04-19T17:27:43Z

packages/flutter/lib/src/semantics/semantics.dart

I don't know where the appropriate place is, but it feels like we should document this somewhere.

goderbauer · 2018-04-19T17:36:57Z

packages/flutter/lib/src/material/app_bar.dart

Can you add a test that verifies correct traversal order for app bar with a leading icon (e.g. hamburger menu), a title, and a trailing icon (e.g. three dots menu)? That's the traversal order we got most called out for in a11y reviews. Will be good to ensure with tests to keep it correct.

direct link

yjbanov · 2018-04-21T00:36:26Z

For some reason GitHub is not letting me respond to some of the comments, so responding here:

isCompatibleWithPreviousSortKey && sortNodes.isNotEmpty
I don't know where the appropriate place is, but it feels like we should document this somewhere.

This is documented in SemanticsSortKey:

/// If subclasses of this class compare themselves to another subclass of
/// [SemanticsSortKey], they will compare as "equal" so that keys of the same
/// type are ordered only with respect to one another.

I'm not sure this wording is accurate enough though, as it assumes a specific sorting algorithm. I'll try to think of a better wording.

Can you update what's left to do in the PR description? I believe it's remove geometric sort order and add hit testing?

Done.

goderbauer

LGTM

New a11y traversal: - sort direct sibling SemanticsNodes only - use new sorting algorithm - implement RTL - test semantics in traversal order by default - add AppBar traversal test - breaking: remove nextNodeId/previousNodeId from the framework - breaking: remove DebugSemanticsDumpOrder.geometricOrder

googlebot added the cla: yes label Apr 4, 2018

yjbanov mentioned this pull request Apr 4, 2018

ios: remove geometric order; it will be supplied by framework flutter/engine#4937

Merged

yjbanov changed the title ~~a11y traversal: sort locally; use new sorting algorithm~~ [WIP] a11y traversal: sort locally; use new sorting algorithm Apr 5, 2018

goderbauer reviewed Apr 10, 2018

View reviewed changes

yjbanov force-pushed the submit-traversal-order branch from 959c026 to ac6651c Compare April 18, 2018 21:04

goderbauer reviewed Apr 19, 2018

View reviewed changes

yjbanov added 9 commits April 20, 2018 15:03

a11y traversal: sort locally; use new sorting algorithm

11b0232

implement RTL

0c1c774

traversal tests

663ac44

remove nextNodeId/previousNodeId from the framework

879a6bf

test semantics in traversal order by default

4c94af2

remove timing; "start" -> "leading"; dartdoc fixes

24791e2

use explicit new keyword

d0bc947

merge with HEAD

7667a84

add AppBar traversal test

c19f8ed

yjbanov force-pushed the submit-traversal-order branch from 6068931 to c19f8ed Compare April 20, 2018 22:59

revert experiments; document sorting algorithm in detail

6fd77f4

yjbanov force-pushed the submit-traversal-order branch from afc9903 to 6fd77f4 Compare April 21, 2018 00:41

remove DebugSemanticsDumpOrder.geometricOrder

48b1935

goderbauer approved these changes Apr 23, 2018

View reviewed changes

yjbanov changed the title ~~[WIP] a11y traversal: sort locally; use new sorting algorithm~~ a11y traversal: sort locally; use new sorting algorithm Apr 23, 2018

yjbanov mentioned this pull request Apr 23, 2018

replace nextNodeId/previousNodeId with hitTestPosition flutter/engine#5066

Merged

yjbanov merged commit d354096 into flutter:master Apr 23, 2018

zoechi mentioned this pull request Jul 12, 2018

Feature request: Allow null values in child or children[] collections to signal that an element should not be drawn #17862

Closed

This was referenced Jun 12, 2019

SemanticsTester doesn't match correctly on last child #34363

Closed

Fix semantics_tester #34368

Merged

github-actions bot locked as resolved and limited conversation to collaborators Aug 11, 2021

a11y traversal: sort locally; use new sorting algorithm #16253

a11y traversal: sort locally; use new sorting algorithm #16253

Uh oh!

Conversation

yjbanov commented Apr 4, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

goderbauer left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

goderbauer Apr 10, 2018 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

goderbauer left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

yjbanov commented Apr 4, 2018 •

edited

Loading

goderbauer Apr 10, 2018 •

edited

Loading