KHtml

dom_restyler.h
1 /*
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 2006 Allan Sandfeld Jensen ([email protected])
5  * (C) 2009 Vyacheslav Tokarev ([email protected])
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB. If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23 
24 #ifndef _DOM_restyler_h_
25 #define _DOM_restyler_h_
26 
27 #include <bitset>
28 #include <wtf/HashMap.h>
29 #include <wtf/HashSet.h>
30 #include "xml/dom_elementimpl.h"
31 #include <QVarLengthArray>
32 
33 /*namespace DOM {
34  class ElementImpl;
35 }*/
36 
37 // Restyle dependency tracker for dynamic DOM
38 
39 namespace khtml
40 {
41 
42 using DOM::ElementImpl;
43 
44 // These types are different types of dependencies, and serves to identify which element should be
45 // restyled when a change of that kind triggers on the element
46 enum StructuralDependencyType {
47  // Style relies on the children of the element (unaffected by append & close)
48  StructuralDependency = 0,
49  // Style relies on the last children of the element (affected by append & close)
50  BackwardsStructuralDependency = 1,
51  // Style relies on the element having hover
52  HoverDependency = 2,
53  // Style relies on the element being active
54  ActiveDependency = 3,
55  // Style relies on another state of element (focus, disabled, checked, etc.)
56  // (focus is special cased though since elements always depend on their own focus)
57  OtherStateDependency = 4,
58  LastStructuralDependency
59 };
60 
61 // Attribute dependencies are much coarser than structural, for memory reasons rather than performance
62 // This tracks global dependencies of various kinds.
63 // The groups are separated into where possible depending elements might be:
64 enum AttributeDependencyType {
65  // Style of the changed element depend on this attribute
66  PersonalDependency = 0,
67  // Style of the elements children depend on this attribute
68  AncestorDependency = 1,
69  // Style of the elements later siblings or their children depend on this attribute
70  PredecessorDependency = 2,
71  LastAttributeDependency
72 };
73 
74 // MultiMap implementation by mapping: ElementImpl* -> HashSet of ElementImpl*
75 // it includes an optimization which covers common mapping case: element -> element, element -> parent
76 // and set is created only if it contains more than one element otherwise direct mapping is stored as is
77 struct ElementMap {
78 private:
79  typedef WTF::HashSet<ElementImpl *> HashSet;
80  struct Value {
81  union {
82  HashSet *set;
83  ElementImpl *element;
84  } m_value;
85  bool isSet : 1;
86  bool parentDependency : 1;
87  bool selfDependency : 1;
88  };
89  typedef WTF::HashMap<ElementImpl *, Value> HashMap;
90  typedef HashMap::iterator Iterator;
91  HashMap map;
92 
93  void removeIfEmpty(const Iterator &it)
94  {
95  Value &value = it->second;
96  if (value.isSet && value.m_value.set->isEmpty()) {
97  delete value.m_value.set;
98  value.isSet = false;
99  value.m_value.element = nullptr;
100  }
101  if (!value.isSet && !value.m_value.element && !value.parentDependency && !value.selfDependency) {
102  map.remove(it);
103  }
104  }
105 
106 public:
107  typedef QVarLengthArray<ElementImpl *> ElementsList;
108 
109  ~ElementMap()
110  {
111  Iterator end = map.end();
112  for (Iterator it = map.begin(); it != end; ++it)
113  if (it->second.isSet) {
114  delete it->second.m_value.set;
115  }
116  }
117 
118  void add(ElementImpl *a, ElementImpl *b)
119  {
120  std::pair<Iterator, bool> it = map.add(a, Value());
121  Value &value = it.first->second;
122  if (it.second) {
123  value.isSet = false;
124  value.parentDependency = false;
125  value.selfDependency = false;
126  value.m_value.element = nullptr;
127  }
128  if (b == a) {
129  value.selfDependency = true;
130  } else if (b == a->parentNode()) {
131  value.parentDependency = true;
132  } else if (value.isSet) {
133  value.m_value.set->add(b);
134  } else if (!value.m_value.element || value.m_value.element == b) {
135  value.m_value.element = b;
136  } else {
137  // convert into set
138  HashSet *temp = new HashSet();
139  temp->add(value.m_value.element);
140  temp->add(b);
141  value.m_value.set = temp;
142  value.isSet = true;
143  }
144  }
145 
146  void remove(ElementImpl *a, ElementImpl *b)
147  {
148  Iterator it = map.find(a);
149  if (it == map.end()) {
150  return;
151  }
152  Value &value = it->second;
153  if (b == a) {
154  value.selfDependency = false;
155  } else if (b == a->parentNode()) {
156  value.parentDependency = false;
157  } else if (value.isSet) {
158  // don't care if set contains 1 element after this operation
159  // it could be converted back into non-set storage but it's a minor optimization only
160  value.m_value.set->remove(b);
161  } else if (value.m_value.element == b) {
162  value.m_value.element = nullptr;
163  }
164  removeIfEmpty(it);
165  }
166 
167  void remove(ElementImpl *a)
168  {
169  Iterator it = map.find(a);
170  if (it != map.end()) {
171  if (it->second.isSet) {
172  delete it->second.m_value.set;
173  }
174  map.remove(it);
175  }
176  }
177 
178 private:
179  void addFromSet(HashSet *set, ElementsList &array)
180  {
181  HashSet::iterator end = set->end();
182  for (HashSet::iterator it = set->begin(); it != end; ++it) {
183  array.append(*it);
184  }
185  }
186 
187 public:
188  void getElements(ElementImpl *element, ElementsList &array)
189  {
190  Iterator it = map.find(element);
191  if (it == map.end()) {
192  return;
193  }
194  Value &value = it->second;
195  if (value.parentDependency) {
196  array.append(static_cast<ElementImpl *>(element->parentNode()));
197  }
198  if (value.selfDependency) {
199  array.append(element);
200  }
201  if (value.isSet) {
202  addFromSet(value.m_value.set, array);
203  }
204  if (!value.isSet && value.m_value.element) {
205  array.append(value.m_value.element);
206  }
207  }
208 };
209 
214 {
215 public:
217 
218  // Structural dependencies are tracked from element to subject
219  void addDependency(ElementImpl *subject, ElementImpl *dependency, StructuralDependencyType type);
220  void resetDependencies(ElementImpl *subject);
221  void restyleDependent(ElementImpl *dependency, StructuralDependencyType type);
222 
223  // Attribute dependencies are traced on attribute alone
224  void addDependency(uint attrID, AttributeDependencyType type);
225  bool checkDependency(uint attrID, AttributeDependencyType type);
226 
227  void dumpStats() const;
228 private:
229  // Map of dependencies.
230  ElementMap dependency_map[LastStructuralDependency];
231  // Map of reverse dependencies. For fast reset
232  ElementMap reverse_map;
233 
234  // Map of the various attribute dependencies
235  std::bitset<512> attribute_map[LastAttributeDependency];
236 };
237 
238 }
239 
240 #endif
241 
This file is part of the HTML rendering engine for KDE.
KIOFILEWIDGETS_EXPORT void add(const QString &fileClass, const QString &directory)
const QList< QKeySequence > & end()
QFuture< void > map(Sequence &sequence, MapFunctor function)
This file is part of the KDE documentation.
Documentation copyright © 1996-2020 The KDE developers.
Generated on Fri Nov 27 2020 22:47:39 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.