SelectorEngine.cpp 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426
  1. /*
  2. * Copyright (c) 2018-2022, Andreas Kling <kling@serenityos.org>
  3. * Copyright (c) 2021, Sam Atkins <atkinssj@serenityos.org>
  4. *
  5. * SPDX-License-Identifier: BSD-2-Clause
  6. */
  7. #include <LibWeb/CSS/Parser/Parser.h>
  8. #include <LibWeb/CSS/SelectorEngine.h>
  9. #include <LibWeb/DOM/Document.h>
  10. #include <LibWeb/DOM/Element.h>
  11. #include <LibWeb/DOM/Text.h>
  12. #include <LibWeb/HTML/AttributeNames.h>
  13. #include <LibWeb/HTML/HTMLAnchorElement.h>
  14. #include <LibWeb/HTML/HTMLAreaElement.h>
  15. #include <LibWeb/HTML/HTMLButtonElement.h>
  16. #include <LibWeb/HTML/HTMLFieldSetElement.h>
  17. #include <LibWeb/HTML/HTMLHtmlElement.h>
  18. #include <LibWeb/HTML/HTMLInputElement.h>
  19. #include <LibWeb/HTML/HTMLOptGroupElement.h>
  20. #include <LibWeb/HTML/HTMLOptionElement.h>
  21. #include <LibWeb/HTML/HTMLSelectElement.h>
  22. #include <LibWeb/HTML/HTMLTextAreaElement.h>
  23. namespace Web::SelectorEngine {
  24. // https://drafts.csswg.org/selectors-4/#the-lang-pseudo
  25. static inline bool matches_lang_pseudo_class(DOM::Element const& element, Vector<FlyString> const& languages)
  26. {
  27. FlyString element_language;
  28. for (auto const* e = &element; e; e = e->parent_element()) {
  29. auto lang = e->attribute(HTML::AttributeNames::lang);
  30. if (!lang.is_null()) {
  31. element_language = lang;
  32. break;
  33. }
  34. }
  35. if (element_language.is_null())
  36. return false;
  37. // FIXME: This is ad-hoc. Implement a proper language range matching algorithm as recommended by BCP47.
  38. for (auto const& language : languages) {
  39. if (language.is_empty())
  40. return false;
  41. if (language == "*"sv)
  42. return true;
  43. if (!element_language.view().contains('-'))
  44. return element_language.equals_ignoring_case(language);
  45. auto parts = element_language.view().split_view('-');
  46. return parts[0].equals_ignoring_case(language);
  47. }
  48. return false;
  49. }
  50. // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-link
  51. static inline bool matches_link_pseudo_class(DOM::Element const& element)
  52. {
  53. // All a elements that have an href attribute, and all area elements that have an href attribute, must match one of :link and :visited.
  54. if (!is<HTML::HTMLAnchorElement>(element) && !is<HTML::HTMLAreaElement>(element))
  55. return false;
  56. return element.has_attribute(HTML::AttributeNames::href);
  57. }
  58. static inline bool matches_hover_pseudo_class(DOM::Element const& element)
  59. {
  60. auto* hovered_node = element.document().hovered_node();
  61. if (!hovered_node)
  62. return false;
  63. if (&element == hovered_node)
  64. return true;
  65. return element.is_ancestor_of(*hovered_node);
  66. }
  67. // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-checked
  68. static inline bool matches_checked_pseudo_class(DOM::Element const& element)
  69. {
  70. // The :checked pseudo-class must match any element falling into one of the following categories:
  71. // - input elements whose type attribute is in the Checkbox state and whose checkedness state is true
  72. // - input elements whose type attribute is in the Radio Button state and whose checkedness state is true
  73. if (is<HTML::HTMLInputElement>(element)) {
  74. auto const& input_element = static_cast<HTML::HTMLInputElement const&>(element);
  75. switch (input_element.type_state()) {
  76. case HTML::HTMLInputElement::TypeAttributeState::Checkbox:
  77. case HTML::HTMLInputElement::TypeAttributeState::RadioButton:
  78. return static_cast<HTML::HTMLInputElement const&>(element).checked();
  79. default:
  80. return false;
  81. }
  82. }
  83. // FIXME: - option elements whose selectedness is true
  84. return false;
  85. }
  86. static inline bool matches_attribute(CSS::Selector::SimpleSelector::Attribute const& attribute, DOM::Element const& element)
  87. {
  88. if (attribute.match_type == CSS::Selector::SimpleSelector::Attribute::MatchType::HasAttribute) {
  89. // Early way out in case of an attribute existence selector.
  90. return element.has_attribute(attribute.name);
  91. }
  92. auto const case_insensitive_match = (attribute.case_type == CSS::Selector::SimpleSelector::Attribute::CaseType::CaseInsensitiveMatch);
  93. auto const case_sensitivity = case_insensitive_match
  94. ? CaseSensitivity::CaseInsensitive
  95. : CaseSensitivity::CaseSensitive;
  96. switch (attribute.match_type) {
  97. case CSS::Selector::SimpleSelector::Attribute::MatchType::ExactValueMatch:
  98. return case_insensitive_match
  99. ? element.attribute(attribute.name).equals_ignoring_case(attribute.value)
  100. : element.attribute(attribute.name) == attribute.value;
  101. case CSS::Selector::SimpleSelector::Attribute::MatchType::ContainsWord: {
  102. if (attribute.value.is_empty()) {
  103. // This selector is always false is match value is empty.
  104. return false;
  105. }
  106. auto const view = element.attribute(attribute.name).split_view(' ');
  107. auto const size = view.size();
  108. for (size_t i = 0; i < size; ++i) {
  109. auto const value = view.at(i);
  110. if (case_insensitive_match
  111. ? value.equals_ignoring_case(attribute.value)
  112. : value == attribute.value) {
  113. return true;
  114. }
  115. }
  116. return false;
  117. }
  118. case CSS::Selector::SimpleSelector::Attribute::MatchType::ContainsString:
  119. return !attribute.value.is_empty()
  120. && element.attribute(attribute.name).contains(attribute.value, case_sensitivity);
  121. case CSS::Selector::SimpleSelector::Attribute::MatchType::StartsWithSegment: {
  122. auto const element_attr_value = element.attribute(attribute.name);
  123. if (element_attr_value.is_empty()) {
  124. // If the attribute value on element is empty, the selector is true
  125. // if the match value is also empty and false otherwise.
  126. return attribute.value.is_empty();
  127. }
  128. if (attribute.value.is_empty()) {
  129. return false;
  130. }
  131. auto segments = element_attr_value.split_view('-');
  132. return case_insensitive_match
  133. ? segments.first().equals_ignoring_case(attribute.value)
  134. : segments.first() == attribute.value;
  135. }
  136. case CSS::Selector::SimpleSelector::Attribute::MatchType::StartsWithString:
  137. return !attribute.value.is_empty()
  138. && element.attribute(attribute.name).starts_with(attribute.value, case_sensitivity);
  139. case CSS::Selector::SimpleSelector::Attribute::MatchType::EndsWithString:
  140. return !attribute.value.is_empty()
  141. && element.attribute(attribute.name).ends_with(attribute.value, case_sensitivity);
  142. default:
  143. break;
  144. }
  145. return false;
  146. }
  147. static inline DOM::Element const* previous_sibling_with_same_tag_name(DOM::Element const& element)
  148. {
  149. for (auto const* sibling = element.previous_element_sibling(); sibling; sibling = sibling->previous_element_sibling()) {
  150. if (sibling->tag_name() == element.tag_name())
  151. return sibling;
  152. }
  153. return nullptr;
  154. }
  155. static inline DOM::Element const* next_sibling_with_same_tag_name(DOM::Element const& element)
  156. {
  157. for (auto const* sibling = element.next_element_sibling(); sibling; sibling = sibling->next_element_sibling()) {
  158. if (sibling->tag_name() == element.tag_name())
  159. return sibling;
  160. }
  161. return nullptr;
  162. }
  163. static inline bool matches_pseudo_class(CSS::Selector::SimpleSelector::PseudoClass const& pseudo_class, DOM::Element const& element)
  164. {
  165. switch (pseudo_class.type) {
  166. case CSS::Selector::SimpleSelector::PseudoClass::Type::Link:
  167. return matches_link_pseudo_class(element);
  168. case CSS::Selector::SimpleSelector::PseudoClass::Type::Visited:
  169. // FIXME: Maybe match this selector sometimes?
  170. return false;
  171. case CSS::Selector::SimpleSelector::PseudoClass::Type::Active:
  172. return element.is_active();
  173. case CSS::Selector::SimpleSelector::PseudoClass::Type::Hover:
  174. return matches_hover_pseudo_class(element);
  175. case CSS::Selector::SimpleSelector::PseudoClass::Type::Focus:
  176. return element.is_focused();
  177. case CSS::Selector::SimpleSelector::PseudoClass::Type::FocusWithin: {
  178. auto* focused_element = element.document().focused_element();
  179. return focused_element && element.is_inclusive_ancestor_of(*focused_element);
  180. }
  181. case CSS::Selector::SimpleSelector::PseudoClass::Type::FirstChild:
  182. return !element.previous_element_sibling();
  183. case CSS::Selector::SimpleSelector::PseudoClass::Type::LastChild:
  184. return !element.next_element_sibling();
  185. case CSS::Selector::SimpleSelector::PseudoClass::Type::OnlyChild:
  186. return !(element.previous_element_sibling() || element.next_element_sibling());
  187. case CSS::Selector::SimpleSelector::PseudoClass::Type::Empty: {
  188. if (!element.has_children())
  189. return true;
  190. if (element.first_child_of_type<DOM::Element>())
  191. return false;
  192. // NOTE: CSS Selectors level 4 changed ":empty" to also match whitespace-only text nodes.
  193. // However, none of the major browser supports this yet, so let's just hang back until they do.
  194. bool has_nonempty_text_child = false;
  195. element.for_each_child_of_type<DOM::Text>([&](auto const& text_child) {
  196. if (!text_child.data().is_empty()) {
  197. has_nonempty_text_child = true;
  198. return IterationDecision::Break;
  199. }
  200. return IterationDecision::Continue;
  201. });
  202. return !has_nonempty_text_child;
  203. }
  204. case CSS::Selector::SimpleSelector::PseudoClass::Type::Root:
  205. return is<HTML::HTMLHtmlElement>(element);
  206. case CSS::Selector::SimpleSelector::PseudoClass::Type::FirstOfType:
  207. return !previous_sibling_with_same_tag_name(element);
  208. case CSS::Selector::SimpleSelector::PseudoClass::Type::LastOfType:
  209. return !next_sibling_with_same_tag_name(element);
  210. case CSS::Selector::SimpleSelector::PseudoClass::Type::OnlyOfType:
  211. return !previous_sibling_with_same_tag_name(element) && !next_sibling_with_same_tag_name(element);
  212. case CSS::Selector::SimpleSelector::PseudoClass::Type::Lang:
  213. return matches_lang_pseudo_class(element, pseudo_class.languages);
  214. case CSS::Selector::SimpleSelector::PseudoClass::Type::Disabled:
  215. // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-disabled
  216. // The :disabled pseudo-class must match any element that is actually disabled.
  217. return element.is_actually_disabled();
  218. case CSS::Selector::SimpleSelector::PseudoClass::Type::Enabled:
  219. // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-enabled
  220. // The :enabled pseudo-class must match any button, input, select, textarea, optgroup, option, fieldset element, or form-associated custom element that is not actually disabled.
  221. return (is<HTML::HTMLButtonElement>(element) || is<HTML::HTMLInputElement>(element) || is<HTML::HTMLSelectElement>(element) || is<HTML::HTMLTextAreaElement>(element) || is<HTML::HTMLOptGroupElement>(element) || is<HTML::HTMLOptionElement>(element) || is<HTML::HTMLFieldSetElement>(element))
  222. && !element.is_actually_disabled();
  223. case CSS::Selector::SimpleSelector::PseudoClass::Type::Checked:
  224. return matches_checked_pseudo_class(element);
  225. case CSS::Selector::SimpleSelector::PseudoClass::Type::Is:
  226. case CSS::Selector::SimpleSelector::PseudoClass::Type::Where:
  227. for (auto& selector : pseudo_class.argument_selector_list) {
  228. if (matches(selector, element))
  229. return true;
  230. }
  231. return false;
  232. case CSS::Selector::SimpleSelector::PseudoClass::Type::Not:
  233. for (auto& selector : pseudo_class.argument_selector_list) {
  234. if (matches(selector, element))
  235. return false;
  236. }
  237. return true;
  238. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthChild:
  239. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthLastChild:
  240. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthOfType:
  241. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthLastOfType:
  242. auto const step_size = pseudo_class.nth_child_pattern.step_size;
  243. auto const offset = pseudo_class.nth_child_pattern.offset;
  244. if (step_size == 0 && offset == 0)
  245. return false; // "If both a and b are equal to zero, the pseudo-class represents no element in the document tree."
  246. auto const* parent = element.parent_element();
  247. if (!parent)
  248. return false;
  249. auto matches_selector_list = [](CSS::SelectorList const& list, DOM::Element const& element) {
  250. if (list.is_empty())
  251. return true;
  252. for (auto const& child_selector : list) {
  253. if (matches(child_selector, element)) {
  254. return true;
  255. }
  256. }
  257. return false;
  258. };
  259. int index = 1;
  260. switch (pseudo_class.type) {
  261. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthChild: {
  262. if (!matches_selector_list(pseudo_class.argument_selector_list, element))
  263. return false;
  264. for (auto* child = parent->first_child_of_type<DOM::Element>(); child && child != &element; child = child->next_element_sibling()) {
  265. if (matches_selector_list(pseudo_class.argument_selector_list, *child))
  266. ++index;
  267. }
  268. break;
  269. }
  270. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthLastChild: {
  271. if (!matches_selector_list(pseudo_class.argument_selector_list, element))
  272. return false;
  273. for (auto* child = parent->last_child_of_type<DOM::Element>(); child && child != &element; child = child->previous_element_sibling()) {
  274. if (matches_selector_list(pseudo_class.argument_selector_list, *child))
  275. ++index;
  276. }
  277. break;
  278. }
  279. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthOfType: {
  280. for (auto* child = previous_sibling_with_same_tag_name(element); child; child = previous_sibling_with_same_tag_name(*child))
  281. ++index;
  282. break;
  283. }
  284. case CSS::Selector::SimpleSelector::PseudoClass::Type::NthLastOfType: {
  285. for (auto* child = next_sibling_with_same_tag_name(element); child; child = next_sibling_with_same_tag_name(*child))
  286. ++index;
  287. break;
  288. }
  289. default:
  290. VERIFY_NOT_REACHED();
  291. }
  292. // When "step_size == -1", selector represents first "offset" elements in document tree.
  293. if (step_size == -1)
  294. return !(offset <= 0 || index > offset);
  295. // When "step_size == 1", selector represents last "offset" elements in document tree.
  296. if (step_size == 1)
  297. return !(offset < 0 || index < offset);
  298. // When "step_size == 0", selector picks only the "offset" element.
  299. if (step_size == 0)
  300. return index == offset;
  301. // If both are negative, nothing can match.
  302. if (step_size < 0 && offset < 0)
  303. return false;
  304. // Like "a % b", but handles negative integers correctly.
  305. auto const canonical_modulo = [](int a, int b) -> int {
  306. int c = a % b;
  307. if ((c < 0 && b > 0) || (c > 0 && b < 0)) {
  308. c += b;
  309. }
  310. return c;
  311. };
  312. // When "step_size < 0", we start at "offset" and count backwards.
  313. if (step_size < 0)
  314. return index <= offset && canonical_modulo(index - offset, -step_size) == 0;
  315. // Otherwise, we start at "offset" and count forwards.
  316. return index >= offset && canonical_modulo(index - offset, step_size) == 0;
  317. }
  318. return false;
  319. }
  320. static inline bool matches(CSS::Selector::SimpleSelector const& component, DOM::Element const& element)
  321. {
  322. switch (component.type) {
  323. case CSS::Selector::SimpleSelector::Type::Universal:
  324. return true;
  325. case CSS::Selector::SimpleSelector::Type::Id:
  326. return component.name() == element.attribute(HTML::AttributeNames::id);
  327. case CSS::Selector::SimpleSelector::Type::Class:
  328. return element.has_class(component.name());
  329. case CSS::Selector::SimpleSelector::Type::TagName:
  330. // See https://html.spec.whatwg.org/multipage/semantics-other.html#case-sensitivity-of-selectors
  331. if (element.document().document_type() == DOM::Document::Type::HTML)
  332. return component.lowercase_name() == element.local_name();
  333. return component.name().equals_ignoring_case(element.local_name());
  334. case CSS::Selector::SimpleSelector::Type::Attribute:
  335. return matches_attribute(component.attribute(), element);
  336. case CSS::Selector::SimpleSelector::Type::PseudoClass:
  337. return matches_pseudo_class(component.pseudo_class(), element);
  338. case CSS::Selector::SimpleSelector::Type::PseudoElement:
  339. // Pseudo-element matching/not-matching is handled in the top level matches().
  340. return true;
  341. default:
  342. VERIFY_NOT_REACHED();
  343. }
  344. }
  345. static inline bool matches(CSS::Selector const& selector, int component_list_index, DOM::Element const& element)
  346. {
  347. auto& relative_selector = selector.compound_selectors()[component_list_index];
  348. for (auto& simple_selector : relative_selector.simple_selectors) {
  349. if (!matches(simple_selector, element))
  350. return false;
  351. }
  352. switch (relative_selector.combinator) {
  353. case CSS::Selector::Combinator::None:
  354. return true;
  355. case CSS::Selector::Combinator::Descendant:
  356. VERIFY(component_list_index != 0);
  357. for (auto* ancestor = element.parent(); ancestor; ancestor = ancestor->parent()) {
  358. if (!is<DOM::Element>(*ancestor))
  359. continue;
  360. if (matches(selector, component_list_index - 1, static_cast<DOM::Element const&>(*ancestor)))
  361. return true;
  362. }
  363. return false;
  364. case CSS::Selector::Combinator::ImmediateChild:
  365. VERIFY(component_list_index != 0);
  366. if (!element.parent() || !is<DOM::Element>(*element.parent()))
  367. return false;
  368. return matches(selector, component_list_index - 1, static_cast<DOM::Element const&>(*element.parent()));
  369. case CSS::Selector::Combinator::NextSibling:
  370. VERIFY(component_list_index != 0);
  371. if (auto* sibling = element.previous_element_sibling())
  372. return matches(selector, component_list_index - 1, *sibling);
  373. return false;
  374. case CSS::Selector::Combinator::SubsequentSibling:
  375. VERIFY(component_list_index != 0);
  376. for (auto* sibling = element.previous_element_sibling(); sibling; sibling = sibling->previous_element_sibling()) {
  377. if (matches(selector, component_list_index - 1, *sibling))
  378. return true;
  379. }
  380. return false;
  381. case CSS::Selector::Combinator::Column:
  382. TODO();
  383. }
  384. VERIFY_NOT_REACHED();
  385. }
  386. bool matches(CSS::Selector const& selector, DOM::Element const& element, Optional<CSS::Selector::PseudoElement> pseudo_element)
  387. {
  388. VERIFY(!selector.compound_selectors().is_empty());
  389. if (pseudo_element.has_value() && selector.pseudo_element() != pseudo_element)
  390. return false;
  391. if (!pseudo_element.has_value() && selector.pseudo_element().has_value())
  392. return false;
  393. return matches(selector, selector.compound_selectors().size() - 1, element);
  394. }
  395. }