?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
rewrite: update default dumb and smart prefixes
[elinks/elinks-j605.git] / src / dom / select.c
blob3b17dcbd0653dd0ee21944cc7c427092a2b11eb2
1 /* DOM node selection */
2
3 #ifdef HAVE_CONFIG_H
4 #include "config.h"
5 #endif
6
7 #include "elinks.h"
8
9 #include "dom/css/scanner.h"
10 #include "dom/code.h"
11 #include "dom/node.h"
12 #include "dom/scanner.h"
13 #include "dom/select.h"
14 #include "dom/stack.h"
15 #include "dom/string.h"
16 #include "util/memory.h"
17
18
19 /* Selector parsing: */
20
21 /* Maps the content of a scanner token to a pseudo-class or -element ID. */
22 static enum dom_select_pseudo
23 get_dom_select_pseudo(struct dom_scanner_token *token)
24 {
25 static struct {
26 struct dom_string string;
27 enum dom_select_pseudo pseudo;
28 } pseudo_info[] = {
29
30 #define INIT_DOM_SELECT_PSEUDO_STRING(str, type) \
31 { STATIC_DOM_STRING(str), DOM_SELECT_PSEUDO_##type }
32
33 INIT_DOM_SELECT_PSEUDO_STRING("first-line", FIRST_LINE),
34 INIT_DOM_SELECT_PSEUDO_STRING("first-letter", FIRST_LETTER),
35 INIT_DOM_SELECT_PSEUDO_STRING("selection", SELECTION),
36 INIT_DOM_SELECT_PSEUDO_STRING("after", AFTER),
37 INIT_DOM_SELECT_PSEUDO_STRING("before", BEFORE),
38 INIT_DOM_SELECT_PSEUDO_STRING("link", LINK),
39 INIT_DOM_SELECT_PSEUDO_STRING("visited", VISITED),
40 INIT_DOM_SELECT_PSEUDO_STRING("active", ACTIVE),
41 INIT_DOM_SELECT_PSEUDO_STRING("hover", HOVER),
42 INIT_DOM_SELECT_PSEUDO_STRING("focus", FOCUS),
43 INIT_DOM_SELECT_PSEUDO_STRING("target", TARGET),
44 INIT_DOM_SELECT_PSEUDO_STRING("enabled", ENABLED),
45 INIT_DOM_SELECT_PSEUDO_STRING("disabled", DISABLED),
46 INIT_DOM_SELECT_PSEUDO_STRING("checked", CHECKED),
47 INIT_DOM_SELECT_PSEUDO_STRING("indeterminate", INDETERMINATE),
48
49 /* Content pseudo-classes: */
50
51 INIT_DOM_SELECT_PSEUDO_STRING("contains", CONTAINS),
52
53 /* Structural pseudo-classes: */
54
55 INIT_DOM_SELECT_PSEUDO_STRING("nth-child", NTH_CHILD),
56 INIT_DOM_SELECT_PSEUDO_STRING("nth-last-child", NTH_LAST_CHILD),
57 INIT_DOM_SELECT_PSEUDO_STRING("first-child", FIRST_CHILD),
58 INIT_DOM_SELECT_PSEUDO_STRING("last-child", LAST_CHILD),
59 INIT_DOM_SELECT_PSEUDO_STRING("only-child", ONLY_CHILD),
60
61 INIT_DOM_SELECT_PSEUDO_STRING("nth-of-type", NTH_TYPE),
62 INIT_DOM_SELECT_PSEUDO_STRING("nth-last-of-type",NTH_LAST_TYPE),
63 INIT_DOM_SELECT_PSEUDO_STRING("first-of-type", FIRST_TYPE),
64 INIT_DOM_SELECT_PSEUDO_STRING("last-of-type", LAST_TYPE),
65 INIT_DOM_SELECT_PSEUDO_STRING("only-of-type", ONLY_TYPE),
66
67 INIT_DOM_SELECT_PSEUDO_STRING("root", ROOT),
68 INIT_DOM_SELECT_PSEUDO_STRING("empty", EMPTY),
69
70 #undef INIT_DOM_SELECT_PSEUDO_STRING
71
72 };
73 int i;
74
75 for (i = 0; i < sizeof_array(pseudo_info); i++)
76 if (!dom_string_casecmp(&pseudo_info[i].string, &token->string))
77 return pseudo_info[i].pseudo;
78
79 return DOM_SELECT_PSEUDO_UNKNOWN;
80 }
81
82 /* Parses attribute selector. For example '[foo="bar"]' or '[foo|="boo"]'. */
83 static enum dom_code
84 parse_dom_select_attribute(struct dom_select_node *sel, struct dom_scanner *scanner)
85 {
86 struct dom_scanner_token *token = get_dom_scanner_token(scanner);
87
88 /* Get '['. */
89
90 if (token->type != '[')
91 return DOM_CODE_SYNTAX_ERR;
92
93 /* Get the attribute name. */
94
95 token = get_next_dom_scanner_token(scanner);
96 if (!token || token->type != CSS_TOKEN_IDENT)
97 return DOM_CODE_SYNTAX_ERR;
98
99 copy_dom_string(&sel->node.string, &token->string);
100
101 /* Get the optional '=' combo or ending ']'. */
102
103 token = get_next_dom_scanner_token(scanner);
104 if (!token) return DOM_CODE_SYNTAX_ERR;
105
106 switch (token->type) {
107 case ']':
108 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_ANY;
109 return DOM_CODE_OK;
110
111 case CSS_TOKEN_SELECT_SPACE_LIST:
112 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_SPACE_LIST;
113 break;
114
115 case CSS_TOKEN_SELECT_HYPHEN_LIST:
116 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_HYPHEN_LIST;
117 break;
118
119 case CSS_TOKEN_SELECT_BEGIN:
120 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_BEGIN;
121 break;
122
123 case CSS_TOKEN_SELECT_END:
124 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_END;
125 break;
126
127 case CSS_TOKEN_SELECT_CONTAINS:
128 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_CONTAINS;
129 break;
130
131 default:
132 return DOM_CODE_SYNTAX_ERR;
133 }
134
135 /* Get the required value. */
136
137 token = get_next_dom_scanner_token(scanner);
138 if (!token) return DOM_CODE_SYNTAX_ERR;
139
140 switch (token->type) {
141 case CSS_TOKEN_IDENT:
142 case CSS_TOKEN_STRING:
143 copy_dom_string(&sel->node.data.attribute.value, &token->string);
144 break;
145
146 default:
147 return DOM_CODE_SYNTAX_ERR;
148 }
149
150 /* Get the ending ']'. */
151
152 token = get_next_dom_scanner_token(scanner);
153 if (token && token->type == ']')
154 return DOM_CODE_OK;
155
156 return DOM_CODE_SYNTAX_ERR;
157 }
158
159 /* Parse:
160 *
161 * 0n+1 / 1
162 * 2n+0 / 2n
163 * 2n+1
164 * -0n+2
165 * -0n+1 / -1
166 * 1n+0 / n+0 / n
167 * 0n+0
168 */
169
170 /* FIXME: Move somewhere else? dom/scanner.h? */
171 static size_t
172 get_scanner_token_number(struct dom_scanner_token *token)
173 {
174 size_t number = 0;
175
176 while (token->string.length > 0 && isdigit(token->string.string[0])) {
177 size_t old_number = number;
178
179 number *= 10;
180
181 /* -E2BIG */
182 if (old_number > number)
183 return -1;
184
185 number += token->string.string[0] - '0';
186 skip_dom_scanner_token_char(token);
187 }
188
189 return number;
190 }
191
192 /* Parses the '(...)' part of ':nth-of-type(...)' and ':nth-child(...)'. */
193 static enum dom_code
194 parse_dom_select_nth_arg(struct dom_select_nth_match *nth, struct dom_scanner *scanner)
195 {
196 struct dom_scanner_token *token = get_next_dom_scanner_token(scanner);
197 int sign = 1;
198 int number = -1;
199
200 if (!token || token->type != '(')
201 return DOM_CODE_SYNTAX_ERR;
202
203 token = get_next_dom_scanner_token(scanner);
204 if (!token)
205 return DOM_CODE_SYNTAX_ERR;
206
207 switch (token->type) {
208 case CSS_TOKEN_IDENT:
209 if (dom_scanner_token_contains(token, "even")) {
210 nth->step = 2;
211 nth->index = 0;
212
213 } else if (dom_scanner_token_contains(token, "odd")) {
214 nth->step = 2;
215 nth->index = 1;
216
217 } else {
218 /* Check for 'n' ident below. */
219 break;
220 }
221
222 if (skip_css_tokens(scanner, ')'))
223 return DOM_CODE_OK;
224
225 return DOM_CODE_SYNTAX_ERR;
226
227 case '-':
228 sign = -1;
229
230 token = get_next_dom_scanner_token(scanner);
231 if (!token) return DOM_CODE_SYNTAX_ERR;
232
233 if (token->type != CSS_TOKEN_IDENT)
234 break;
235
236 if (token->type != CSS_TOKEN_NUMBER)
237 return DOM_CODE_SYNTAX_ERR;
238 /* Fall-through */
239
240 case CSS_TOKEN_NUMBER:
241 number = get_scanner_token_number(token);
242 if (number < 0)
243 return DOM_CODE_VALUE_ERR;
244
245 token = get_next_dom_scanner_token(scanner);
246 if (!token) return DOM_CODE_SYNTAX_ERR;
247 break;
248
249 default:
250 return DOM_CODE_SYNTAX_ERR;
251 }
252
253 /* The rest can contain n+ part */
254 switch (token->type) {
255 case CSS_TOKEN_IDENT:
256 if (!dom_scanner_token_contains(token, "n"))
257 return DOM_CODE_SYNTAX_ERR;
258
259 nth->step = sign * number;
260
261 token = get_next_dom_scanner_token(scanner);
262 if (!token) return DOM_CODE_SYNTAX_ERR;
263
264 if (token->type != '+')
265 break;
266
267 token = get_next_dom_scanner_token(scanner);
268 if (!token) return DOM_CODE_SYNTAX_ERR;
269
270 if (token->type != CSS_TOKEN_NUMBER)
271 break;
272
273 number = get_scanner_token_number(token);
274 if (number < 0)
275 return DOM_CODE_VALUE_ERR;
276
277 nth->index = sign * number;
278 break;
279
280 default:
281 nth->step = 0;
282 nth->index = sign * number;
283 }
284
285 if (skip_css_tokens(scanner, ')'))
286 return DOM_CODE_OK;
287
288 return DOM_CODE_SYNTAX_ERR;
289 }
290
291 /* Parse a pseudo-class or -element with the syntax: ':<ident>'. */
292 static enum dom_code
293 parse_dom_select_pseudo(struct dom_select *select, struct dom_select_node *sel,
294 struct dom_scanner *scanner)
295 {
296 struct dom_scanner_token *token = get_dom_scanner_token(scanner);
297 enum dom_select_pseudo pseudo;
298 enum dom_code code;
299
300 /* Skip double :'s in front of some pseudo's (::first-line, etc.) */
301 do {
302 token = get_next_dom_scanner_token(scanner);
303 } while (token && token->type == ':');
304
305 if (!token || token->type != CSS_TOKEN_IDENT)
306 return DOM_CODE_SYNTAX_ERR;
307
308 pseudo = get_dom_select_pseudo(token);
309 switch (pseudo) {
310 case DOM_SELECT_PSEUDO_UNKNOWN:
311 return DOM_CODE_ERR;
312
313 case DOM_SELECT_PSEUDO_CONTAINS:
314 /* FIXME: E:contains("text") */
315 break;
316
317 case DOM_SELECT_PSEUDO_NTH_CHILD:
318 case DOM_SELECT_PSEUDO_NTH_LAST_CHILD:
319 code = parse_dom_select_nth_arg(&sel->nth_child, scanner);
320 if (code != DOM_CODE_OK)
321 return code;
322
323 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
324 break;
325
326 case DOM_SELECT_PSEUDO_FIRST_CHILD:
327 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
328 set_dom_select_nth_match(&sel->nth_child, 0, 1);
329 break;
330
331 case DOM_SELECT_PSEUDO_LAST_CHILD:
332 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
333 set_dom_select_nth_match(&sel->nth_child, 0, -1);
334 break;
335
336 case DOM_SELECT_PSEUDO_ONLY_CHILD:
337 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
338 set_dom_select_nth_match(&sel->nth_child, 0, 0);
339 break;
340
341 case DOM_SELECT_PSEUDO_NTH_TYPE:
342 case DOM_SELECT_PSEUDO_NTH_LAST_TYPE:
343 code = parse_dom_select_nth_arg(&sel->nth_type, scanner);
344 if (code != DOM_CODE_OK)
345 return code;
346
347 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
348 break;
349
350 case DOM_SELECT_PSEUDO_FIRST_TYPE:
351 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
352 set_dom_select_nth_match(&sel->nth_type, 0, 1);
353 break;
354
355 case DOM_SELECT_PSEUDO_LAST_TYPE:
356 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
357 set_dom_select_nth_match(&sel->nth_type, 0, -1);
358 break;
359
360 case DOM_SELECT_PSEUDO_ONLY_TYPE:
361 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
362 set_dom_select_nth_match(&sel->nth_type, 0, 0);
363 break;
364
365 case DOM_SELECT_PSEUDO_ROOT:
366 sel->match.element |= DOM_SELECT_ELEMENT_ROOT;
367 break;
368
369 case DOM_SELECT_PSEUDO_EMPTY:
370 sel->match.element |= DOM_SELECT_ELEMENT_EMPTY;
371 break;
372
373 default:
374 /* It's a bitflag! */
375 select->pseudo |= pseudo;
376 }
377
378 return DOM_CODE_OK;
379 }
380
381 /* The element relation flags are mutual exclusive. This macro can be used
382 * for checking if anyflag is set. */
383 #define get_element_relation(sel) \
384 ((sel)->match.element & DOM_SELECT_RELATION_FLAGS)
385
386 /* Parse a CSS3 selector and add selector nodes to the @select struct. */
387 static enum dom_code
388 parse_dom_select(struct dom_select *select, struct dom_stack *stack,
389 struct dom_string *string)
390 {
391 struct dom_scanner scanner;
392 struct dom_select_node sel;
393
394 init_dom_scanner(&scanner, &dom_css_scanner_info, string, 0, 0, 1, 0, 0);
395
396 memset(&sel, 0, sizeof(sel));
397
398 while (dom_scanner_has_tokens(&scanner)) {
399 struct dom_scanner_token *token = get_dom_scanner_token(&scanner);
400 enum dom_code code;
401 struct dom_select_node *select_node;
402
403 assert(token);
404
405 if (token->type == '{'
406 || token->type == '}'
407 || token->type == ';'
408 || token->type == ',')
409 break;
410
411 /* Examine the selector fragment */
412
413 switch (token->type) {
414 case CSS_TOKEN_IDENT:
415 sel.node.type = DOM_NODE_ELEMENT;
416 copy_dom_string(&sel.node.string, &token->string);
417 if (dom_scanner_token_contains(token, "*"))
418 sel.match.element |= DOM_SELECT_ELEMENT_UNIVERSAL;
419 break;
420
421 case CSS_TOKEN_HASH:
422 case CSS_TOKEN_HEX_COLOR:
423 /* ID fragment */
424 sel.node.type = DOM_NODE_ATTRIBUTE;
425 sel.match.attribute |= DOM_SELECT_ATTRIBUTE_ID;
426 /* Skip the leading '#'. */
427 skip_dom_scanner_token_char(token);
428 break;
429
430 case '[':
431 sel.node.type = DOM_NODE_ATTRIBUTE;
432 code = parse_dom_select_attribute(&sel, &scanner);
433 if (code != DOM_CODE_OK)
434 return code;
435 break;
436
437 case '.':
438 token = get_next_dom_scanner_token(&scanner);
439 if (!token || token->type != CSS_TOKEN_IDENT)
440 return DOM_CODE_SYNTAX_ERR;
441
442 sel.node.type = DOM_NODE_ATTRIBUTE;
443 sel.match.attribute |= DOM_SELECT_ATTRIBUTE_SPACE_LIST;
444 set_dom_string(&sel.node.string, "class", -1);
445 copy_dom_string(&sel.node.data.attribute.value, &token->string);
446 break;
447
448 case ':':
449 code = parse_dom_select_pseudo(select, &sel, &scanner);
450 if (code != DOM_CODE_OK)
451 return code;
452 break;
453
454 case '>':
455 if (get_element_relation(&sel) != DOM_SELECT_RELATION_DESCENDANT)
456 return DOM_CODE_SYNTAX_ERR;
457 sel.match.element |= DOM_SELECT_RELATION_DIRECT_CHILD;
458 break;
459
460 case '+':
461 if (get_element_relation(&sel) != DOM_SELECT_RELATION_DESCENDANT)
462 return DOM_CODE_SYNTAX_ERR;
463 sel.match.element |= DOM_SELECT_RELATION_DIRECT_ADJACENT;
464 break;
465
466 case '~':
467 if (get_element_relation(&sel) != DOM_SELECT_RELATION_DESCENDANT)
468 return DOM_CODE_SYNTAX_ERR;
469 sel.match.element |= DOM_SELECT_RELATION_INDIRECT_ADJACENT;
470 break;
471
472 default:
473 return DOM_CODE_SYNTAX_ERR;
474 }
475
476 skip_dom_scanner_token(&scanner);
477
478 if (sel.node.type == DOM_NODE_UNKNOWN)
479 continue;
480
481 select_node = mem_calloc(1, sizeof(*select_node));
482 copy_struct(select_node, &sel);
483
484 if (!dom_stack_is_empty(stack)) {
485 struct dom_node *node = &select_node->node;
486 struct dom_node *parent = get_dom_stack_top(stack)->node;
487 struct dom_node_list **list = get_dom_node_list(parent, node);
488 int sort = (node->type == DOM_NODE_ATTRIBUTE);
489 int index;
490
491 assertm(list != NULL, "Adding node to bad parent [%d -> %d]",
492 node->type, parent->type);
493
494 index = *list && (*list)->size > 0 && sort
495 ? get_dom_node_map_index(*list, node) : -1;
496
497 if (!add_to_dom_node_list(list, node, index)) {
498 done_dom_node(node);
499 return DOM_CODE_ALLOC_ERR;
500 }
501
502 node->parent = parent;
503
504 } else {
505 assert(!select->selector);
506 select->selector = select_node;
507 }
508
509 code = push_dom_node(stack, &select_node->node);
510 if (code != DOM_CODE_OK)
511 return code;
512
513 if (select_node->node.type != DOM_NODE_ELEMENT)
514 pop_dom_node(stack);
515
516 memset(&sel, 0, sizeof(sel));
517 }
518
519 if (select->selector)
520 return DOM_CODE_OK;
521
522 return DOM_CODE_ERR;
523 }
524
525 /* Basically this is just a wrapper for parse_dom_select() to ease error
526 * handling. */
527 struct dom_select *
528 init_dom_select(enum dom_select_syntax syntax, struct dom_string *string)
529 {
530 struct dom_select *select = mem_calloc(1, sizeof(select));
531 struct dom_stack stack;
532 enum dom_code code;
533
534 init_dom_stack(&stack, DOM_STACK_FLAG_NONE);
535 add_dom_stack_tracer(&stack, "init-select: ");
536
537 code = parse_dom_select(select, &stack, string);
538 done_dom_stack(&stack);
539
540 if (code == DOM_CODE_OK)
541 return select;
542
543 done_dom_select(select);
544
545 return NULL;
546 }
547
548 void
549 done_dom_select(struct dom_select *select)
550 {
551 if (select->selector) {
552 struct dom_node *node = (struct dom_node *) select->selector;
553
554 /* This will recursively free all children select nodes. */
555 done_dom_node(node);
556 }
557
558 mem_free(select);
559 }
560
561
562 /* DOM node selection: */
563
564 /* This struct stores data related to the 'application' of a DOM selector
565 * on a DOM tree or stream. */
566 struct dom_select_data {
567 /* The selector matching stack. The various selector nodes are pushed
568 * onto this stack as they are matched (and later popped when they are
569 * no longer 'reachable', that is, has been popped from the DOM tree or
570 * stream. This way the selector can match each selector node multiple
571 * times and the selection is a simple matter of matching the current
572 * node against each state on this stack. */
573 struct dom_stack stack;
574
575 /* Reference to the selector. */
576 struct dom_select *select;
577
578 /* The list of nodes who have been matched / selected. */
579 struct dom_node_list *list;
580 };
581
582 /* This state struct is used for the select data stack and holds info about the
583 * node that was matched. */
584 struct dom_select_state {
585 /* The matched node. This is always an element node. */
586 struct dom_node *node;
587 };
588
589 /* Get a child node of a given type. By design, a selector node can
590 * only have one child per type of node. */
591 static struct dom_select_node *
592 get_child_dom_select_node(struct dom_select_node *selector,
593 enum dom_node_type type)
594 {
595 struct dom_node_list *children = selector->node.data.element.children;
596 struct dom_node *node;
597 int index;
598
599 if (!children)
600 return NULL;
601
602 foreach_dom_node (children, node, index) {
603 if (node->type == type)
604 return (struct dom_select_node *) node;
605 }
606
607 return NULL;
608 }
609
610
611 #define has_attribute_match(selector, name) \
612 ((selector)->match.attribute & (name))
613
614 static int
615 match_attribute_value(struct dom_select_node *selector, struct dom_node *node)
616 {
617 struct dom_string str;
618 struct dom_string *selvalue = &selector->node.data.attribute.value;
619 struct dom_string *value = &node->data.attribute.value;
620 unsigned char separator;
621 int do_compare;
622
623 assert(selvalue->length);
624
625 /* The attribute selector value should atleast be contained in the
626 * attribute value. */
627 if (value->length < selvalue->length)
628 return 0;
629
630 /* The following three matching methods requires the selector value to
631 * match a substring at a well-defined offset. */
632
633 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_EXACT)) {
634 return !dom_string_casecmp(value, selvalue);
635 }
636
637 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_BEGIN)) {
638 set_dom_string(&str, value->string, selvalue->length);
639
640 return !dom_string_casecmp(&str, selvalue);
641 }
642
643 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_END)) {
644 size_t offset = value->length - selvalue->length;
645
646 set_dom_string(&str, value->string + offset, selvalue->length);
647
648 return !dom_string_casecmp(&str, selvalue);
649 }
650
651 /* The 3 following matching methods requires the selector value to be a
652 * substring of the value enclosed in a specific separator (with the
653 * begining and ending of the attribute value both being valid
654 * separators). */
655
656 set_dom_string(&str, value->string, value->length);
657
658 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_HYPHEN_LIST)) {
659 separator = '-';
660
661 } else if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_CONTAINS)) {
662 separator = '\0';
663
664 } if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_SPACE_LIST)) {
665 separator = ' ';
666
667 } else {
668 INTERNAL("No attribute selector matching method defined");
669 return 0;
670 }
671
672 do_compare = 1;
673
674 do {
675 if (do_compare
676 && !dom_string_ncasecmp(&str, selvalue, selvalue->length)) {
677 /* "Contains" matches no matter what comes after. */
678 if (str.length == selvalue->length)
679 return 1;
680
681 switch (separator) {
682 case '\0':
683 /* "Contains" matches no matter what comes after. */
684 return 1;
685
686 case '-':
687 if (str.string[str.length] == separator)
688 return 1;
689 break;
690
691 default:
692 if (isspace(str.string[str.length]))
693 return 1;
694 }
695 }
696
697 switch (separator) {
698 case '\0':
699 do_compare = 1;
700 break;
701
702 case '-':
703 do_compare = (str.string[0] == '-');
704 break;
705
706 default:
707 do_compare = isspace(str.string[0]);
708 }
709
710 str.length--, str.string++;
711
712 } while (str.length >= selvalue->length);
713
714 return 0;
715 }
716
717 /* Match the attribute of an element @node against attribute selector nodes
718 * of a given @base. */
719 static int
720 match_attribute_selectors(struct dom_select_node *base, struct dom_node *node)
721 {
722 struct dom_node_list *attrs = node->data.element.map;
723 struct dom_node_list *selnodes = base->node.data.element.map;
724 struct dom_node *selnode;
725 size_t index;
726
727 assert(base->node.type == DOM_NODE_ELEMENT
728 && node->type == DOM_NODE_ELEMENT);
729
730 /* If there are no attribute selectors that is a clean match ... */
731 if (!selnodes)
732 return 1;
733
734 /* ... the opposite goes if there are no attributes to match. */
735 if (!attrs)
736 return 0;
737
738 foreach_dom_node (selnodes, selnode, index) {
739 struct dom_select_node *selector = (void *) selnode;
740 struct dom_node *attr;
741
742 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_ID)) {
743 size_t idindex;
744
745 attr = NULL;
746 foreach_dom_node (attrs, attr, idindex) {
747 if (attr->data.attribute.id)
748 break;
749 }
750
751 if (!is_dom_node_list_member(attrs, idindex))
752 attr = NULL;
753
754 } else {
755 attr = get_dom_node_map_entry(attrs, DOM_NODE_ATTRIBUTE,
756 selnode->data.attribute.type,
757 &selnode->string);
758 }
759
760 if (!attr)
761 return 0;
762
763 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_ANY))
764 continue;
765
766 if (!match_attribute_value(selector, attr))
767 return 0;
768 }
769
770 return 1;
771 }
772
773 /* XXX: Assume the first context is the one! */
774 #define get_dom_select_state(stack, state) \
775 ((struct dom_select_state *) get_dom_stack_state_data((stack)->contexts[0], state))
776
777 static int
778 match_element_relation(struct dom_select_node *selector, struct dom_node *node,
779 struct dom_stack *stack)
780 {
781 struct dom_stack_state *state;
782 enum dom_select_element_match relation = get_element_relation(selector);
783 int i, index;
784
785 assert(relation);
786
787 /* When matching any relation there must be a parent, either so that
788 * the node is a descendant or it is possible to check for siblings. */
789 if (!node->parent)
790 return 0;
791
792 if (relation != DOM_SELECT_RELATION_DIRECT_CHILD) {
793 /* When looking for preceeding siblings of the current node,
794 * the current node cannot be first or not in the list (-1). */
795 index = get_dom_node_list_index(node->parent, node);
796 if (index < 1)
797 return 0;
798 } else {
799 index = -1;
800 }
801
802 /* Find states which hold the parent of the current selector
803 * and check if the parent selector's node is the parent of the
804 * current node. */
805 foreachback_dom_stack_state(stack, state, i) {
806 struct dom_node *selnode;
807
808 /* We are only interested in states which hold the parent of
809 * the current selector. */
810 if (state->node != selector->node.parent)
811 continue;
812
813 selnode = get_dom_select_state(stack, state)->node;
814
815 if (relation == DOM_SELECT_RELATION_DIRECT_CHILD) {
816 /* Check if the parent selector's node is the parent of
817 * the current node. */
818 if (selnode == node->parent)
819 return 1;
820
821 } else {
822 int sibindex;
823
824 /* Check if they are siblings. */
825 if (selnode->parent != node->parent)
826 continue;
827
828 sibindex = get_dom_node_list_index(node->parent, selnode);
829
830 if (relation == DOM_SELECT_RELATION_DIRECT_ADJACENT) {
831 /* Check if the sibling node immediately
832 * preceeds the current node. */
833 if (sibindex + 1 == index)
834 return 1;
835
836 } else { /* DOM_SELECT_RELATION_INDIRECT_ADJACENT */
837 /* Check if the sibling node preceeds the
838 * current node. */
839 if (sibindex < index)
840 return 1;
841 }
842 }
843 }
844
845 return 0;
846 }
847
848 #define has_element_match(selector, name) \
849 ((selector)->match.element & (name))
850
851 static int
852 match_element_selector(struct dom_select_node *selector, struct dom_node *node,
853 struct dom_stack *stack)
854 {
855 assert(node && node->type == DOM_NODE_ELEMENT);
856
857 if (!has_element_match(selector, DOM_SELECT_ELEMENT_UNIVERSAL)
858 && dom_node_casecmp(&selector->node, node))
859 return 0;
860
861 if (get_element_relation(selector) != DOM_SELECT_RELATION_DESCENDANT
862 && !match_element_relation(selector, node, stack))
863 return 0;
864
865 /* Root nodes either have no parents or are the single child of the
866 * document node. */
867 if (has_element_match(selector, DOM_SELECT_ELEMENT_ROOT)
868 && node->parent) {
869 if (node->parent->type != DOM_NODE_DOCUMENT
870 || node->parent->data.document.children->size > 1)
871 return 0;
872 }
873
874 if (has_element_match(selector, DOM_SELECT_ELEMENT_EMPTY)
875 && node->data.element.children
876 && node->data.element.children->size > 0)
877 return 0;
878
879 if (has_element_match(selector, DOM_SELECT_ELEMENT_NTH_CHILD)) {
880 /* FIXME */
881 return 0;
882 }
883
884 if (has_element_match(selector, DOM_SELECT_ELEMENT_NTH_TYPE)) {
885 /* FIXME */
886 return 0;
887 }
888
889 /* Check attribute selectors. */
890 if (selector->node.data.element.map
891 && !match_attribute_selectors(selector, node))
892 return 0;
893
894 return 1;
895 }
896
897
898 #define get_dom_select_data(stack) ((stack)->current->data)
899
900 /* Matches an element node being visited against the current selector stack. */
901 enum dom_code
902 dom_select_push_element(struct dom_stack *stack, struct dom_node *node, void *data)
903 {
904 struct dom_select_data *select_data = get_dom_select_data(stack);
905 struct dom_stack_state *state;
906 int pos;
907
908 foreach_dom_stack_state(&select_data->stack, state, pos) {
909 struct dom_select_node *selector = (void *) state->node;
910
911 /* FIXME: Since the same dom_select_node can be multiple times
912 * on the select_data->stack, cache what select nodes was
913 * matches so that it is only checked once. */
914
915 if (!match_element_selector(selector, node, &select_data->stack))
916 continue;
917
918 WDBG("Matched element: %.*s.", node->string.length, node->string.string);
919 /* This node is matched, so push the next selector node to
920 * match on the stack. */
921 selector = get_child_dom_select_node(selector, DOM_NODE_ELEMENT);
922 if (selector)
923 push_dom_node(&select_data->stack, &selector->node);
924 }
925
926 return DOM_CODE_OK;
927 }
928
929 /* Ensures that nodes, no longer 'reachable' on the stack do not have any
930 * states associated with them on the select data stack. */
931 enum dom_code
932 dom_select_pop_element(struct dom_stack *stack, struct dom_node *node, void *data)
933 {
934 struct dom_select_data *select_data = get_dom_select_data(stack);
935 struct dom_stack_state *state;
936 int index;
937
938 stack = &select_data->stack;
939
940 foreachback_dom_stack_state (stack, state, index) {
941 struct dom_select_state *select_state;
942
943 select_state = get_dom_select_state(stack, state);
944 if (select_state->node == node) {
945 pop_dom_state(stack, state);
946 WDBG("Remove element.");
947 continue;
948 }
949 }
950
951 return DOM_CODE_OK;
952 }
953
954 /* For now this is only for matching the ':contains(<string>)' pseudo-class.
955 * Any node which can contain text and thus characters from the given <string>
956 * are handled in this common callback. */
957 enum dom_code
958 dom_select_push_text(struct dom_stack *stack, struct dom_node *node, void *data)
959 {
960 struct dom_select_data *select_data = get_dom_select_data(stack);
961 struct dom_stack_state *state = get_dom_stack_top(&select_data->stack);
962 struct dom_select_node *selector = (void *) state->node;
963 struct dom_select_node *text_sel = get_child_dom_select_node(selector, DOM_NODE_TEXT);
964
965 WDBG("Text node: %d chars", node->string.length);
966
967 if (!text_sel)
968 return DOM_CODE_OK;
969
970 switch (node->type) {
971 case DOM_NODE_TEXT:
972 case DOM_NODE_CDATA_SECTION:
973 case DOM_NODE_ENTITY_REFERENCE:
974 break;
975 default:
976 ERROR("Unhandled type");
977 }
978
979 return DOM_CODE_OK;
980 }
981
982 /* Context info for interacting with the DOM tree or stream stack. */
983 static struct dom_stack_context_info dom_select_context_info = {
984 /* Object size: */ 0,
985 /* Push: */
986 {
987 /* */ NULL,
988 /* DOM_NODE_ELEMENT */ dom_select_push_element,
989 /* DOM_NODE_ATTRIBUTE */ NULL,
990 /* DOM_NODE_TEXT */ dom_select_push_text,
991 /* DOM_NODE_CDATA_SECTION */ dom_select_push_text,
992 /* DOM_NODE_ENTITY_REFERENCE */ dom_select_push_text,
993 /* DOM_NODE_ENTITY */ NULL,
994 /* DOM_NODE_PROC_INSTRUCTION */ NULL,
995 /* DOM_NODE_COMMENT */ NULL,
996 /* DOM_NODE_DOCUMENT */ NULL,
997 /* DOM_NODE_DOCUMENT_TYPE */ NULL,
998 /* DOM_NODE_DOCUMENT_FRAGMENT */ NULL,
999 /* DOM_NODE_NOTATION */ NULL,
1000 },
1001 /* Pop: */
1002 {
1003 /* */ NULL,
1004 /* DOM_NODE_ELEMENT */ dom_select_pop_element,
1005 /* DOM_NODE_ATTRIBUTE */ NULL,
1006 /* DOM_NODE_TEXT */ NULL,
1007 /* DOM_NODE_CDATA_SECTION */ NULL,
1008 /* DOM_NODE_ENTITY_REFERENCE */ NULL,
1009 /* DOM_NODE_ENTITY */ NULL,
1010 /* DOM_NODE_PROC_INSTRUCTION */ NULL,
1011 /* DOM_NODE_COMMENT */ NULL,
1012 /* DOM_NODE_DOCUMENT */ NULL,
1013 /* DOM_NODE_DOCUMENT_TYPE */ NULL,
1014 /* DOM_NODE_DOCUMENT_FRAGMENT */ NULL,
1015 /* DOM_NODE_NOTATION */ NULL,
1016 }
1017 };
1018
1019 /* Context info related to the private select data stack of matched nodes. */
1020 static struct dom_stack_context_info dom_select_data_context_info = {
1021 /* Object size: */ sizeof(struct dom_select_state),
1022 /* Push: */
1023 {
1024 /* */ NULL,
1025 /* DOM_NODE_ELEMENT */ NULL,
1026 /* DOM_NODE_ATTRIBUTE */ NULL,
1027 /* DOM_NODE_TEXT */ NULL,
1028 /* DOM_NODE_CDATA_SECTION */ NULL,
1029 /* DOM_NODE_ENTITY_REFERENCE */ NULL,
1030 /* DOM_NODE_ENTITY */ NULL,
1031 /* DOM_NODE_PROC_INSTRUCTION */ NULL,
1032 /* DOM_NODE_COMMENT */ NULL,
1033 /* DOM_NODE_DOCUMENT */ NULL,
1034 /* DOM_NODE_DOCUMENT_TYPE */ NULL,
1035 /* DOM_NODE_DOCUMENT_FRAGMENT */ NULL,
1036 /* DOM_NODE_NOTATION */ NULL,
1037 },
1038 /* Pop: */
1039 {
1040 /* */ NULL,
1041 /* DOM_NODE_ELEMENT */ NULL,
1042 /* DOM_NODE_ATTRIBUTE */ NULL,
1043 /* DOM_NODE_TEXT */ NULL,
1044 /* DOM_NODE_CDATA_SECTION */ NULL,
1045 /* DOM_NODE_ENTITY_REFERENCE */ NULL,
1046 /* DOM_NODE_ENTITY */ NULL,
1047 /* DOM_NODE_PROC_INSTRUCTION */ NULL,
1048 /* DOM_NODE_COMMENT */ NULL,
1049 /* DOM_NODE_DOCUMENT */ NULL,
1050 /* DOM_NODE_DOCUMENT_TYPE */ NULL,
1051 /* DOM_NODE_DOCUMENT_FRAGMENT */ NULL,
1052 /* DOM_NODE_NOTATION */ NULL,
1053 }
1054 };
1055
1056
1057 struct dom_node_list *
1058 select_dom_nodes(struct dom_select *select, struct dom_node *root)
1059 {
1060 struct dom_select_data select_data;
1061 struct dom_stack stack;
1062
1063 memset(&select_data, 0, sizeof(select_data));
1064
1065 select_data.select = select;;
1066
1067 init_dom_stack(&stack, DOM_STACK_FLAG_NONE);
1068 add_dom_stack_context(&stack, &select_data,
1069 &dom_select_context_info);
1070 add_dom_stack_tracer(&stack, "select-tree: ");
1071
1072 init_dom_stack(&select_data.stack, DOM_STACK_FLAG_NONE);
1073 add_dom_stack_context(&select_data.stack, &select_data,
1074 &dom_select_data_context_info);
1075 add_dom_stack_tracer(&select_data.stack, "select-match: ");
1076
1077 if (push_dom_node(&select_data.stack, &select->selector->node) == DOM_CODE_OK) {
1078 get_dom_stack_top(&select_data.stack)->immutable = 1;
1079 walk_dom_nodes(&stack, root);
1080 }
1081
1082 done_dom_stack(&select_data.stack);
1083 done_dom_stack(&stack);
1084
1085 return select_data.list;
1086 }