GitLab

Previously, CDP would fail if the scroll child wasn't the immediate
descendant of the lowest common ancestor of the scroll parent and child.

With this patch I've fixed up two things so that CDP can handle these
cases.

1. Dumber sorting.
  I've made sorting simpler by removing assumptions about the tree
  topology. Instead, I assigned "sort weights" to the layers in
  PreCalculateMetaInformation. The approach is pretty naive. As I
  walk the tree I assign a monotonically increasing weight. If I ever
  hit a scroll child before its parent, I jump up to the lowest common
  ancestor and make sure that the child of the LCA is assigned the
  smallest weight in the tree so far (the negative of the next
  monotonically increasing weight). This ensures that the scroll parent
  will be visited first. Here's a picture of a layer tree and the
  weights that would be assigned.

  lca(0)
  + filler(1)
  | + scroll child(2)
  + more-filler(-3)
    + scroll parent(4)

  It would be a huge bummer if we had to sort all the time, though, so
  I've taken care to flag the LCA if I ever have to assign a negative
  weight so that we only sort in that case.

  Here's my argument for the correctness of the algorithm. Clearly,
  we force correct ordering of a particular scroll child/parent pair,
  but the worry is that by setting a negative weight, we'll force an
  illegal ordering (i.e., we'll "undo" an ordering we've forced
  earlier in the algorithm). Here's a diagram.

  lca
  + subtree with scroll parent #1
  + subtree with scroll child #1 and scroll_parent #2
  + subtree with scroll child #2.

  Now, say we're processing scroll child #2. We want to be sure that
  we don't go reordering subtrees and mess up the relative ordering of
  scroll child #1 and scroll parent #1's subtrees.

  But we know that this is impossible. Since we've already visited the
  subtree with scroll child #1, scroll child #2 will necessarily get a
  higher sort weight, so we'll never need to force any reordering in
  this case; we won't assign any negative weights here.

  Say the ordering were changed such that when processing scroll child
  #2, we haven't seen scroll child #1's subtree. We're also fine in
  this case because we will do any ordering fixups required when we do
  eventually visit scroll child #1.

  The only case where we get into trouble is when we have a cycle. For
  example,

  lca
   + scroll parent 1
   | + scroll child 2
   + scroll parent 2
     + scroll child 1

  No ordering could satisfy a situation with a cycle, but this is
  an impossible situation as CSS stacking defines a well defined, non
  circular order.

2. Proper clip transformations.
  We sometimes need to put the scroll parent's clip into the space of
  the scroll child's immediate parent. This needs to go through the
  LCA. Previously, we'd assumed that the LCA was going to be the scroll
  child's immediate parent, but we no longer make that assumption.

BUG=403866

Review URL: https://codereview.chromium.org/548963002

Cr-Commit-Position: refs/heads/master@{#294521}