1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/renderer/platform/graphics/paint/paint_property_node.h"
#include "third_party/blink/renderer/platform/graphics/paint/clip_paint_property_node.h"
#include "third_party/blink/renderer/platform/graphics/paint/effect_paint_property_node.h"
#include "third_party/blink/renderer/platform/graphics/paint/scroll_paint_property_node.h"
#include "third_party/blink/renderer/platform/graphics/paint/transform_paint_property_node.h"
namespace blink {
namespace {
// Returns -1 if |maybe_ancestor| is found in the ancestor chain, or returns
// the depth of the node from the root.
template <typename NodeType>
int NodeDepthOrFoundAncestor(const NodeType& node,
const NodeType& maybe_ancestor) {
int depth = 0;
for (const NodeType* n = &node; n; n = n->Parent()) {
if (n == &maybe_ancestor)
return -1;
depth++;
}
return depth;
}
template <typename NodeType>
const NodeType& LowestCommonAncestorTemplate(const NodeType& a,
const NodeType& b) {
// Measure both depths.
auto depth_a = NodeDepthOrFoundAncestor(a, b);
if (depth_a == -1)
return b;
auto depth_b = NodeDepthOrFoundAncestor(b, a);
if (depth_b == -1)
return a;
const auto* a_ptr = &a;
const auto* b_ptr = &b;
// Make it so depthA >= depthB.
if (depth_a < depth_b) {
std::swap(a_ptr, b_ptr);
std::swap(depth_a, depth_b);
}
// Make it so depthA == depthB.
while (depth_a > depth_b) {
a_ptr = a_ptr->Parent();
depth_a--;
}
// Walk up until we find the ancestor.
while (a_ptr != b_ptr) {
a_ptr = a_ptr->Parent();
b_ptr = b_ptr->Parent();
}
DCHECK(a_ptr) << "Malformed property tree. All nodes must be descendant of "
"the same root.";
return *a_ptr;
}
} // namespace
const TransformPaintPropertyNode& LowestCommonAncestorInternal(
const TransformPaintPropertyNode& a,
const TransformPaintPropertyNode& b) {
return LowestCommonAncestorTemplate(a, b);
}
const ClipPaintPropertyNode& LowestCommonAncestorInternal(
const ClipPaintPropertyNode& a,
const ClipPaintPropertyNode& b) {
return LowestCommonAncestorTemplate(a, b);
}
const EffectPaintPropertyNode& LowestCommonAncestorInternal(
const EffectPaintPropertyNode& a,
const EffectPaintPropertyNode& b) {
return LowestCommonAncestorTemplate(a, b);
}
const ScrollPaintPropertyNode& LowestCommonAncestorInternal(
const ScrollPaintPropertyNode& a,
const ScrollPaintPropertyNode& b) {
return LowestCommonAncestorTemplate(a, b);
}
} // namespace blink
|