Algorithms in 6.3. Sequential Focus Navigation are too complex

[rniwa]

There are four algorithms involved in determining the sequential focus navigation order, and they're all intertwined.

Instead, we should spec it so that shadow root and slot creates a control group.

[rniwa]

@TakayoshiKochi @LJWatson

[TakayoshiKochi]

At first I wrote the draft using the term "control group", but the term is used for somewhat more upper layer notion, as @hayatoito pointed out.

The algorithm may seem unnecessarily complex to read, but we tried to record the algorithm as precise as possible, rather than easy to understand but sloppy.

[rniwa]

I can't really do a meaningful review of the spec as things stand because it's too complicated. I think we need to figure out a way to document the ordering in more concise way.

[hayatoito]

@TakayoshiKochi , could you help @rniwa to understand the spec somehow?

[chaals]

I agree with @rniwa that it is really hard to follow.

As far as I can tell, what happens roughly is that a shadow root or a slot provide a special scope for making tab order. Within those, the tab order is determined for the stuff in the scope, and then each set of steps is blended into the overall tab order wherever their "owner node" - the shadow root or slot - appears in the overall tab order.

It would be helpful to say something like this (optionally changed to be true), and have a simple example that shows what happens and the resulting tab order.

[domenic]

I agree with @chaals's way of framing the issue. The spec as it stands is really great, and gives enough normative detail to be implementable and to integrate with HTML's existing focus navigation framework well. It is of course complicated, because focus navigation is already very complicated in browsers. But the problem is not with the normative text. An example or three would be really great, and a non-normative note saying what the general intent and outcome would be makes sense as an addition.

[rniwa]

Well, the problem with the current spec is that it creates a list of elements and transforms it multiple times into the final sequence of elements that define the tab sequencing order. Having to construct such a list each time tab focusing order is changed, or even to retain such a huge list of elements after creating it lazily is way too inefficient for our implementation purposes.

What we need instead is an algorithm that defines how to find the next sequentially focusable element. With the right set of abstractions, that algorithm can be defined a lot more concisely. I'll get around to doing that once I took care of more urgent matters.

[chaals]

Hmm. I agree that you might not want to implement the algorithm as written - but you don't have to, you just have to behave as though you did. In the case of something static, the algorithm itself might be fine, but working out how to describe it in a way that lets you calculate the next/previous tabstop from where you are is also a reasonable thing - and unless I read something wrong, would match the algorithm.

It would also be a lot simpler algo IMHO - without thinking it might be almost as short as Check your scope - slot or shadow root or boundary of those or doc, and then check for things with positive tabindex, and if there are none, find the next thing in your scope - if you're on a boundary, that might be inside…

[hayatoito]

FYI. Blink does not construct such a list, as an optimization.
As long as we can achieve the processing equivalence, it should be okay.

Yeah, the spec is complicated, however, the basic idea does not change from my comment: #375 (comment).

Hopefully, the example in the comment would be helpful.

If we are to define the behavior in a normative way, we had to use such a list in the spec for the purpose of the normative explanation.

Ideally, we should have a spec which UA can implement literally, but that can not be always easy.... :(

What we need instead is an algorithm that defines how to find the next sequentially focusable element.

Yeah, that's a preferred way. Can someone try this?
As long as the processing equivalence does not change, it should be okay.

[chaals]

Ideally, we should have a spec which the UA can implement literally, but that can not be always easy.... :(

It's ideal if the UA can implement the spec literally, but it's also idea if we have processing equivalence but people don't implement the spec algorithm literally, because that would mean we stop trying out different approaches and enforce a monoculture. I think the critical bit is that people get the same result at the point where someone cares about interoperability, not that the code paths in browsers are the same. So I think we're OK here…

[rniwa]

If we are to define the behavior in a normative way, we had to use such a list in the spec for the purpose of the normative explanation.

Why? If we can define an algorithm that finds the next element to focus given the current focused element, we can define a total order for all focusable areas.

I think the critical bit is that people get the same result at the point where someone cares about interoperability, not that the code paths in browsers are the same. So I think we're OK here…

The whole point of writing a spec is to define a behavior that can be implemented interoperably by different engines. Unfortunately, the current spec text is so complex that I can't follow and I can't even reason about what the expected output is compared to what we do.

[hayatoito]

Nothing prevents us from improving the spec. :)

I had assigned this task to @TakayoshiKochi , so I hope @TakayoshiKochi would address your concerns and improve the current situation somehow.

I am happy to review a PR.

[TakayoshiKochi]

@rniwa I generally agree that you can define the algorithm in iterative steps to find the next or previous element. Once I tried, but during the PR review @hayatoito preferred the way as it is, for the reasons stated above, and we did that way.

It is still pretty tough to upstream the current focus navigation to the html spec, I'd like to work on express the algorithm in better way.

With that said, dumping the current Blink implementation into spec text should not what you want, and it is already quite complex to handle various cases, probably has bugs on corner cases. The testability is also a problem, as we don't have a good way to test how tab navigation works in e.g. web platform tests infrastructure (of course, Blink and WebKit has both eventSender, though).

As a first step toward it, I'd like to make some non-normative notes like what chaals commented #496 (comment) and write down some examples (or manual tests).

Does it make sense?

[chaals]

It is still pretty tough to upstream the current focus navigation to the html spec, I'd like to work on express the algorithm in better way.

HTML's focus navigation stuff is pretty horrible. I'm planning to rewrite it, so I'd be happy to work with you on making it easier to e.g. work this stuff in.

[TakayoshiKochi]

HTML's focus navigation stuff is pretty horrible. I'm planning to rewrite it, so I'd be happy to work with you on making it easier to e.g. work this stuff in.

Sounds awesome!

[hayatoito]

I am now checking the status of all Shadow DOM v1 spec issues.

What's the status of this issue? Could someone update this issue?

I would like to send an "Intent to ship: Shadow DOM v1" in Blink next week or later.
Regarding sequential focus navigations, if someone still thinks that there is a great risk for interoperability, please let me know that.

[TakayoshiKochi]

I think the spec itself is sound.
I have a plan to add more samples in the spec, but it should not change any definition.

[hayatoito]

Okay. Could you add more samples asap so that it can address the original concern?

I think the original concern is "hard to understand the current spec", rather than the behavior which defines.

[TakayoshiKochi]

I've put an example in JSbin (and will include in the spec, if it makes sense).
http://jsbin.com/cubiye/2/edit?html,output

The document has 3 shadow roots, and each shadow root has 2 slots.
If we run the algorithm described in 6.3,

• Step 1: Scope owners are identified: document, shadow roots, slots
  • document, 3 shadow roots (under #host1, #host2, #host3), 6 slots (2 slots in each shadow tree)
• Step 2: All elements in document and shadow trees are identified to which scope it belongs
  • e.g. <input> in slotted <div> belongs to the <div>'s assigned slot. So <input>s under #host1's shadow labeled RA1 and RA2 will belong to its <slot name="A">, etc.
• Step 3: For each scope, navigation order is determined
  • e.g. in #host1's <slot name="A"> scope, the order is RA1 to RA2, determined by their tabindices. #host2 is excluded because it has tabindex="-1".
  • expected order for each scope is:
    • document: D1, D2, D3, D4, #host1, #host3
    • #host1's shadow: R1, R2, R3, R4 (Slot A), R5 (Slot B)
    • #host2's shadow: R1, R2, R3, R4 (Slot A), R5 (Slot B)
    • #host3's shadow: R1, R2, R3, R4 (Slot A), R5 (Slot B)
    • Slot A of #host1: R1A1, R1A2
    • Slot B of #host1: R1B1, R1B2
    • Slot A of #host2: R2A
    • Slot B of #host2: R2B
    • Slot A of #host3: R3A1, R3A2
    • Slot B of #host3: none
• Step 4: Document-wide navigation order is determined
  • e.g. all the focusable areas in #host1 will be visited after <input> labeled D4. All <input>s under #host2 will be skipped because it was excluded in the previous step.
  • expected total order is
    • D1, D2, D3, D4, #host1, R1, R2, R3, R1A1, R1A2, R1B1, R1B2, #host3, R1, R2, R3, R3A1, R3A2.
    • (Note: R1-R3 right after #host1 are under #host1, R1-R3 after #host3 are under #host3, labels are duplicate as they are from the same template)

I hope this kind of examples would help understanding the spec.
Any feedback is welcome.

[hayatoito]

Could you add an expected navigation order in each scope, and an expected total order, as I did it in #375 (comment) ?

An example should have an expected result.

[TakayoshiKochi]

Updated the comment above to include expected orders.
Thanks for the feedback.

[bicknellr]

Am I correct in thinking that the spec says that only assigned nodes of a slot (not descendants, i.e. fallback content) are within a new scope? (See 6.3 Sequential Focus Navigation, Step 2, 2.1.4. "4. If CURRENT is a slot element and ..." for the section that I think defines this.)

I don't know if this is really a concern or not, but it seems odd that slot fallback content doesn't also get put into a separate scope. Particularly, this means that elements can be 'inserted' into the surrounding sequential focus order when a slot doesn't have fallback content.

For example, if all x-custom elements host a ShadowRoot containing:

<input id="shadow-input-A" tabindex="1">
<input id="shadow-input-B" tabindex="3">
<slot tabindex="4">
  <input id="shadow-slot-input-A" tabindex="2">
  <input id="shadow-slot-input-B" tabindex="6">
</slot>
<input id="shadow-input-C" tabindex="5">
<input id="shadow-input-D" tabindex="7">

And two x-custom elements exist with this structure:

<x-custom id="x-custom-A">
  <input id="light-input">
</x-custom>
<x-custom id="x-custom-B"></x-custom>

Then the sequential focus order of #x-custom-A and all descendants will be:

#shadow-input-A, #shadow-input-B, #light-input, #shadow-input-C, #shadow-input-D

And the sequential focus order of #x-custom-B and all descendants will be:

#shadow-input-A, #shadow-slot-input-A, #shadow-input-B, #shadow-input-C, #shadow-input-slot-B, #shadow-input-D

I don't have a real use case in favor of or against either behavior but this feels inconsistent at first glance. (Although, it does reduce the number of things that create focus scopes.) If anyone has any corrections to what I've written here / opinions on this behavior / if this is a known and intended side effect, I'd be interested to hear.

[hayatoito]

I don't know if this is really a concern or not, but it seems odd that slot fallback content doesn't also get put into a separate scope. Particularly, this means that elements can be 'inserted' into the surrounding sequential focus order when a slot doesn't have fallback content.

I am aware these cases, and I thought these cases should be handled correctly in the spec.
If we can not read that from the spec, it should be considered as a bug of the spec.

At least, Blink should handle such a case correctly, Let me check it again later.

It would be better that the example should cover these cases to clarify that. These cases are important non-edge cases.

[TakayoshiKochi]

@bicknellr when <slot> has fallback contents and it does not have assigned nodes, the slot is a scope owner and tabindex within the slot makes sense.

In your case, #shadow-slot-input-A and #shadow-slot-input-B will be visited sequentially within the slot. As the slot has tabindex 4, the sequence in the shadow root is #shadow-input-A, #shadow-input-B, <slot>, #shadow-input-C, #shadow-input-D.

Therefore the combined sequence when the slot has no assigned nodes is #shadow-input-A, #shadow-input-B, #shadow-slot-input-A, #shadow-slot-input-B, #shadow-input-C, #shadow-input-D, for #x-custom-B.

The order for #x-custom-A is correct.

In the spec, In section 6.3 Step 2, all elements in the tree will be divided into scopes, and descendants of <slot> element which will become fallback content will belong to the slot scope (Specifically, Step 2, 2.1.4.2. "Otherwise append ELEMENT to SCOPE-MAP[CURRENT]").

[bicknellr]

Ok, thank you for the clarification. I think I have a better understanding of Step 2 now: the outer loop (2.1) iterates through all elements in a tree (in document order) and the inner loop (2.1.2) walks up the tree from each element to find its scope owner; if the element is a descendant of a slot, it only gets added to the slot's focus scope if that slot has no assigned nodes. So, a slot's focus scope becomes the owner of either its assigned nodes or, if there are no assigned nodes, its descendants.

[hayatoito]

I am triaging issues. Let me close this issue. If there is an unclear point further, please feel free to re-open this issue (or notify us).

Eventually, we should upstream this to HTML Standard. That could be tracked as another issue, I think.