src/document/dom/select.c

   1 /* DOM node selection */
   2
   3 #ifdef HAVE_CONFIG_H
   4 #include "config.h"
   5 #endif
   6
   7 #include "elinks.h"
   8
   9 #include "document/css/scanner.h"
  10 #include "document/dom/dom.h"
  11 #include "document/dom/node.h"
  12 #include "document/dom/select.h"
  13 #include "document/dom/stack.h"
  14 #include "util/memory.h"
  15 #include "util/scanner.h"
  16 #include "util/string.h"
  17
  18
  19 static enum dom_select_pseudo
  20 get_dom_select_pseudo(struct scanner_token *token)
  21 {
  22         static struct {
  23                 struct dom_string string;
  24                 enum dom_select_pseudo pseudo;
  25         } pseudo_info[] = {
  26
  27 #define INIT_DOM_SELECT_PSEUDO_STRING(str, type) \
  28         { INIT_DOM_STRING(str, -1), DOM_SELECT_PSEUDO_##type }
  29
  30         INIT_DOM_SELECT_PSEUDO_STRING("first-line",     FIRST_LINE),
  31         INIT_DOM_SELECT_PSEUDO_STRING("first-letter",   FIRST_LETTER),
  32         INIT_DOM_SELECT_PSEUDO_STRING("selection",      SELECTION),
  33         INIT_DOM_SELECT_PSEUDO_STRING("after",          AFTER),
  34         INIT_DOM_SELECT_PSEUDO_STRING("before",         BEFORE),
  35         INIT_DOM_SELECT_PSEUDO_STRING("link",           LINK),
  36         INIT_DOM_SELECT_PSEUDO_STRING("visited",        VISITED),
  37         INIT_DOM_SELECT_PSEUDO_STRING("active",         ACTIVE),
  38         INIT_DOM_SELECT_PSEUDO_STRING("hover",          HOVER),
  39         INIT_DOM_SELECT_PSEUDO_STRING("focus",          FOCUS),
  40         INIT_DOM_SELECT_PSEUDO_STRING("target",         TARGET),
  41         INIT_DOM_SELECT_PSEUDO_STRING("enabled",        ENABLED),
  42         INIT_DOM_SELECT_PSEUDO_STRING("disabled",       DISABLED),
  43         INIT_DOM_SELECT_PSEUDO_STRING("checked",        CHECKED),
  44         INIT_DOM_SELECT_PSEUDO_STRING("indeterminate",  INDETERMINATE),
  45
  46         /* Content pseudo-classes: */
  47
  48         INIT_DOM_SELECT_PSEUDO_STRING("contains",       CONTAINS),
  49
  50         /* Structural pseudo-classes: */
  51
  52         INIT_DOM_SELECT_PSEUDO_STRING("nth-child",      NTH_CHILD),
  53         INIT_DOM_SELECT_PSEUDO_STRING("nth-last-child", NTH_LAST_CHILD),
  54         INIT_DOM_SELECT_PSEUDO_STRING("first-child",    FIRST_CHILD),
  55         INIT_DOM_SELECT_PSEUDO_STRING("last-child",     LAST_CHILD),
  56         INIT_DOM_SELECT_PSEUDO_STRING("only-child",     ONLY_CHILD),
  57
  58         INIT_DOM_SELECT_PSEUDO_STRING("nth-of-type",    NTH_TYPE),
  59         INIT_DOM_SELECT_PSEUDO_STRING("nth-last-of-type",NTH_LAST_TYPE),
  60         INIT_DOM_SELECT_PSEUDO_STRING("first-of-type",  FIRST_TYPE),
  61         INIT_DOM_SELECT_PSEUDO_STRING("last-of-type",   LAST_TYPE),
  62         INIT_DOM_SELECT_PSEUDO_STRING("only-of-type",   ONLY_TYPE),
  63
  64         INIT_DOM_SELECT_PSEUDO_STRING("root",           ROOT),
  65         INIT_DOM_SELECT_PSEUDO_STRING("empty",          EMPTY),
  66
  67 #undef INIT_DOM_SELECT_PSEUDO_STRING
  68
  69         };
  70         struct dom_string string;
  71         int i;
  72
  73         set_dom_string(&string, token->string, token->length);
  74
  75         for (i = 0; i < sizeof_array(pseudo_info); i++)
  76                 if (!dom_string_casecmp(&pseudo_info[i].string, &string))
  77                         return pseudo_info[i].pseudo;
  78
  79         return DOM_SELECT_PSEUDO_UNKNOWN;
  80 }
  81
  82
  83 static enum dom_exception_code
  84 parse_dom_select_attribute(struct dom_select_node *sel, struct scanner *scanner)
  85 {
  86         struct scanner_token *token = get_scanner_token(scanner);
  87
  88         if (token->type != '[')
  89                 return DOM_ERR_INVALID_STATE;
  90
  91         token = get_next_scanner_token(scanner);
  92         if (!token || token->type != CSS_TOKEN_IDENT)
  93                 return DOM_ERR_SYNTAX;
  94
  95         set_dom_string(&sel->node.string, token->string, token->length);
  96
  97         token = get_next_scanner_token(scanner);
  98         if (!token) return DOM_ERR_SYNTAX;
  99
 100         switch (token->type) {
 101         case ']':
 102                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_ANY;
 103                 return DOM_ERR_NONE;
 104
 105         case CSS_TOKEN_SELECT_SPACE_LIST:
 106                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_SPACE_LIST;
 107                 break;
 108
 109         case CSS_TOKEN_SELECT_HYPHEN_LIST:
 110                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_HYPHEN_LIST;
 111                 break;
 112
 113         case CSS_TOKEN_SELECT_BEGIN:
 114                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_BEGIN;
 115                 break;
 116
 117         case CSS_TOKEN_SELECT_END:
 118                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_END;
 119                 break;
 120
 121         case CSS_TOKEN_SELECT_CONTAINS:
 122                 sel->match.attribute |= DOM_SELECT_ATTRIBUTE_CONTAINS;
 123                 break;
 124
 125         default:
 126                 return DOM_ERR_SYNTAX;
 127         }
 128
 129         token = get_next_scanner_token(scanner);
 130         if (!token) return DOM_ERR_SYNTAX;
 131
 132         switch (token->type) {
 133         case CSS_TOKEN_IDENT:
 134         case CSS_TOKEN_STRING:
 135                 set_dom_string(&sel->node.data.attribute.value, token->string, token->length);
 136                 break;
 137
 138         default:
 139                 return DOM_ERR_SYNTAX;
 140         }
 141
 142         token = get_next_scanner_token(scanner);
 143         if (token && token->type == ']')
 144                 return DOM_ERR_NONE;
 145
 146         return DOM_ERR_SYNTAX;
 147 }
 148
 149 /* Parse:
 150  *
 151  *   0n+1 / 1
 152  *   2n+0 / 2n
 153  *   2n+1
 154  *  -0n+2
 155  *  -0n+1 / -1
 156  *   1n+0 / n+0 / n
 157  *   0n+0
 158  */
 159
 160 static size_t
 161 get_scanner_token_number(struct scanner_token *token)
 162 {
 163         size_t number = 0;
 164
 165         while (token->length > 0 && isdigit(token->string[0])) {
 166                 size_t old_number = number;
 167
 168                 number *= 10;
 169
 170                 /* -E2BIG */
 171                 if (old_number > number)
 172                         return -1;
 173
 174                 number += token->string[0] - '0';
 175                 token->string++, token->length--;
 176         }
 177
 178         return number;
 179 }
 180
 181 static enum dom_exception_code
 182 parse_dom_select_nth_arg(struct dom_select_nth_match *nth, struct scanner *scanner)
 183 {
 184         struct scanner_token *token = get_next_scanner_token(scanner);
 185         int sign = 1;
 186         int number = -1;
 187
 188         if (!token || token->type != '(')
 189                 return DOM_ERR_SYNTAX;
 190
 191         token = get_next_scanner_token(scanner);
 192         if (!token)
 193                 return DOM_ERR_SYNTAX;
 194
 195         switch (token->type) {
 196         case CSS_TOKEN_IDENT:
 197                 if (scanner_token_contains(token, "even")) {
 198                         nth->step = 2;
 199                         nth->index = 0;
 200
 201                 } else if (scanner_token_contains(token, "odd")) {
 202                         nth->step = 2;
 203                         nth->index = 1;
 204
 205                 } else {
 206                         /* Check for 'n' ident below. */
 207                         break;
 208                 }
 209
 210                 if (skip_css_tokens(scanner, ')'))
 211                         return DOM_ERR_NONE;
 212
 213                 return DOM_ERR_SYNTAX;
 214
 215         case '-':
 216                 sign = -1;
 217
 218                 token = get_next_scanner_token(scanner);
 219                 if (!token) return DOM_ERR_SYNTAX;
 220
 221                 if (token->type != CSS_TOKEN_IDENT)
 222                         break;
 223
 224                 if (token->type != CSS_TOKEN_NUMBER)
 225                         return DOM_ERR_SYNTAX;
 226                 /* Fall-through */
 227
 228         case CSS_TOKEN_NUMBER:
 229                 number = get_scanner_token_number(token);
 230                 if (number < 0)
 231                         return DOM_ERR_INVALID_STATE;
 232
 233                 token = get_next_scanner_token(scanner);
 234                 if (!token) return DOM_ERR_SYNTAX;
 235                 break;
 236
 237         default:
 238                 return DOM_ERR_SYNTAX;
 239         }
 240
 241         /* The rest can contain n+ part */
 242         switch (token->type) {
 243         case CSS_TOKEN_IDENT:
 244                 if (!scanner_token_contains(token, "n"))
 245                         return DOM_ERR_SYNTAX;
 246
 247                 nth->step = sign * number;
 248
 249                 token = get_next_scanner_token(scanner);
 250                 if (!token) return DOM_ERR_SYNTAX;
 251
 252                 if (token->type != '+')
 253                         break;
 254
 255                 token = get_next_scanner_token(scanner);
 256                 if (!token) return DOM_ERR_SYNTAX;
 257
 258                 if (token->type != CSS_TOKEN_NUMBER)
 259                         break;
 260
 261                 number = get_scanner_token_number(token);
 262                 if (number < 0)
 263                         return DOM_ERR_INVALID_STATE;
 264
 265                 nth->index = sign * number;
 266                 break;
 267
 268         default:
 269                 nth->step  = 0;
 270                 nth->index = sign * number;
 271         }
 272
 273         if (skip_css_tokens(scanner, ')'))
 274                 return DOM_ERR_NONE;
 275
 276         return DOM_ERR_SYNTAX;
 277 }
 278
 279 static enum dom_exception_code
 280 parse_dom_select_pseudo(struct dom_select *select, struct dom_select_node *sel,
 281                         struct scanner *scanner)
 282 {
 283         struct scanner_token *token = get_scanner_token(scanner);
 284         enum dom_select_pseudo pseudo;
 285         enum dom_exception_code code;
 286
 287         /* Skip double :'s in front of some pseudo's */
 288         do {
 289                 token = get_next_scanner_token(scanner);
 290         } while (token && token->type == ':');
 291
 292         if (!token || token->type != CSS_TOKEN_IDENT)
 293                 return DOM_ERR_SYNTAX;
 294
 295         pseudo = get_dom_select_pseudo(token);
 296         switch (pseudo) {
 297         case DOM_SELECT_PSEUDO_UNKNOWN:
 298                 return DOM_ERR_NOT_FOUND;
 299
 300         case DOM_SELECT_PSEUDO_CONTAINS:
 301                 /* FIXME: E:contains("text") */
 302                 break;
 303
 304         case DOM_SELECT_PSEUDO_NTH_CHILD:
 305         case DOM_SELECT_PSEUDO_NTH_LAST_CHILD:
 306                 code = parse_dom_select_nth_arg(&sel->nth_child, scanner);
 307                 if (code != DOM_ERR_NONE)
 308                         return code;
 309
 310                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
 311                 break;
 312
 313         case DOM_SELECT_PSEUDO_FIRST_CHILD:
 314                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
 315                 set_dom_select_nth_match(&sel->nth_child, 0, 1);
 316                 break;
 317
 318         case DOM_SELECT_PSEUDO_LAST_CHILD:
 319                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
 320                 set_dom_select_nth_match(&sel->nth_child, 0, -1);
 321                 break;
 322
 323         case DOM_SELECT_PSEUDO_ONLY_CHILD:
 324                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_CHILD;
 325                 set_dom_select_nth_match(&sel->nth_child, 0, 0);
 326                 break;
 327
 328         case DOM_SELECT_PSEUDO_NTH_TYPE:
 329         case DOM_SELECT_PSEUDO_NTH_LAST_TYPE:
 330                 code = parse_dom_select_nth_arg(&sel->nth_type, scanner);
 331                 if (code != DOM_ERR_NONE)
 332                         return code;
 333
 334                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
 335                 break;
 336
 337         case DOM_SELECT_PSEUDO_FIRST_TYPE:
 338                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
 339                 set_dom_select_nth_match(&sel->nth_type, 0, 1);
 340                 break;
 341
 342         case DOM_SELECT_PSEUDO_LAST_TYPE:
 343                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
 344                 set_dom_select_nth_match(&sel->nth_type, 0, -1);
 345                 break;
 346
 347         case DOM_SELECT_PSEUDO_ONLY_TYPE:
 348                 sel->match.element |= DOM_SELECT_ELEMENT_NTH_TYPE;
 349                 set_dom_select_nth_match(&sel->nth_type, 0, 0);
 350                 break;
 351
 352         case DOM_SELECT_PSEUDO_ROOT:
 353                 sel->match.element |= DOM_SELECT_ELEMENT_ROOT;
 354                 break;
 355
 356         case DOM_SELECT_PSEUDO_EMPTY:
 357                 sel->match.element |= DOM_SELECT_ELEMENT_EMPTY;
 358                 break;
 359
 360         default:
 361                 /* It's a bitflag! */
 362                 select->pseudo |= pseudo;
 363         }
 364
 365         return DOM_ERR_NONE;
 366 }
 367
 368 #define get_element_relation(sel) \
 369         ((sel)->match.element & DOM_SELECT_RELATION_FLAGS)
 370
 371 static enum dom_exception_code
 372 parse_dom_select(struct dom_select *select, unsigned char *string, int length)
 373 {
 374         struct dom_stack stack;
 375         struct scanner scanner;
 376         struct dom_select_node sel;
 377
 378         init_scanner(&scanner, &css_scanner_info, string, string + length);
 379         init_dom_stack(&stack, select, 0, 1);
 380
 381         memset(&sel, 0, sizeof(sel));
 382
 383         while (scanner_has_tokens(&scanner)) {
 384                 struct scanner_token *token = get_scanner_token(&scanner);
 385                 enum dom_exception_code code;
 386                 struct dom_select_node *select_node;
 387
 388                 assert(token);
 389
 390                 if (token->type == '{'
 391                     || token->type == '}'
 392                     || token->type == ';'
 393                     || token->type == ',')
 394                         break;
 395
 396                 /* Examine the selector fragment */
 397
 398                 switch (token->type) {
 399                 case CSS_TOKEN_IDENT:
 400                         sel.node.type = DOM_NODE_ELEMENT;
 401                         set_dom_string(&sel.node.string, token->string, token->length);
 402                         if (token->length == 1 && token->string[0] == '*')
 403                                 sel.match.element |= DOM_SELECT_ELEMENT_UNIVERSAL;
 404                         break;
 405
 406                 case CSS_TOKEN_HASH:
 407                 case CSS_TOKEN_HEX_COLOR:
 408                         /* ID fragment */
 409                         sel.node.type = DOM_NODE_ATTRIBUTE;
 410                         sel.match.attribute |= DOM_SELECT_ATTRIBUTE_ID;
 411                         /* Skip the leading '#'. */
 412                         token->string++, token->length--;
 413                         break;
 414
 415                 case '[':
 416                         sel.node.type = DOM_NODE_ATTRIBUTE;
 417                         code = parse_dom_select_attribute(&sel, &scanner);
 418                         if (code != DOM_ERR_NONE)
 419                                 return code;
 420                         break;
 421
 422                 case '.':
 423                         token = get_next_scanner_token(&scanner);
 424                         if (!token || token->type != CSS_TOKEN_IDENT)
 425                                 return DOM_ERR_SYNTAX;
 426
 427                         sel.node.type = DOM_NODE_ATTRIBUTE;
 428                         sel.match.attribute |= DOM_SELECT_ATTRIBUTE_SPACE_LIST;
 429                         set_dom_string(&sel.node.string, "class", -1);
 430                         set_dom_string(&sel.node.data.attribute.value, token->string, token->length);
 431                         break;
 432
 433                 case ':':
 434                         code = parse_dom_select_pseudo(select, &sel, &scanner);
 435                         if (code != DOM_ERR_NONE)
 436                                 return code;
 437                         break;
 438
 439                 case '>':
 440                         if (get_element_relation(&sel))
 441                                 return DOM_ERR_SYNTAX;
 442                         sel.match.element |= DOM_SELECT_RELATION_DIRECT_CHILD;
 443                         break;
 444
 445                 case '+':
 446                         if (get_element_relation(&sel))
 447                                 return DOM_ERR_SYNTAX;
 448                         sel.match.element |= DOM_SELECT_RELATION_DIRECT_ADJACENT;
 449                         break;
 450
 451                 case '~':
 452                         if (get_element_relation(&sel))
 453                                 return DOM_ERR_SYNTAX;
 454                         sel.match.element |= DOM_SELECT_RELATION_INDIRECT_ADJACENT;
 455                         break;
 456
 457                 default:
 458                         return DOM_ERR_SYNTAX;
 459                 }
 460
 461                 skip_scanner_token(&scanner);
 462
 463                 if (sel.node.type == DOM_NODE_UNKNOWN)
 464                         continue;
 465
 466                 WDBG("Adding %s: %.*s", (sel.node.type == DOM_NODE_ELEMENT) ? "element" : "attr", sel.node.string.length, sel.node.string.string);
 467                 /* FIXME */
 468                 select_node = mem_calloc(1, sizeof(*select_node));
 469                 copy_struct(select_node, &sel);
 470
 471                 if (select_node->node.parent) {
 472                         struct dom_node *node = &select_node->node;
 473                         struct dom_node *parent = node->parent;
 474                         struct dom_node_list **list = get_dom_node_list(parent, node);
 475                         int sort = (node->type == DOM_NODE_ATTRIBUTE);
 476                         int index;
 477
 478                         assertm(list, "Adding node to bad parent",
 479                                 get_dom_node_type_name(node->type),
 480                                 get_dom_node_type_name(parent->type));
 481
 482                         index = *list && (*list)->size > 0 && sort
 483                                 ? get_dom_node_map_index(*list, node) : -1;
 484
 485                         if (!add_to_dom_node_list(list, node, index)) {
 486                                 done_dom_node(node);
 487                                 return DOM_ERR_INVALID_STATE;
 488                         }
 489                 } else {
 490                         assert(!select->selector);
 491                         select->selector = select_node;
 492                 }
 493
 494                 memset(&sel, 0, sizeof(sel));
 495                 sel.node.parent = &select_node->node;
 496         }
 497
 498         if (select->selector)
 499                 return DOM_ERR_NONE;
 500
 501         return DOM_ERR_INVALID_STATE;
 502 }
 503
 504 struct dom_select *
 505 init_dom_select(enum dom_select_syntax syntax,
 506                 unsigned char *string, int length)
 507 {
 508         struct dom_select *select = mem_calloc(1, sizeof(select));
 509         enum dom_exception_code code;
 510
 511         code = parse_dom_select(select, string, length);
 512         if (code == DOM_ERR_NONE)
 513                 return select;
 514
 515         done_dom_select(select);
 516
 517         return NULL;
 518 }
 519
 520 void
 521 done_dom_select(struct dom_select *select)
 522 {
 523         if (select->selector) {
 524                 struct dom_node *node = (struct dom_node *) select->selector;
 525
 526                 done_dom_node(node);
 527         }
 528
 529         mem_free(select);
 530 }
 531
 532
 533 struct dom_select_data {
 534         struct dom_stack stack;
 535         struct dom_select *select;
 536         struct dom_node_list *list;
 537 };
 538
 539 struct dom_select_state {
 540         struct dom_node *node;
 541 };
 542
 543
 544 static int
 545 compare_element_type(struct dom_node *node1, struct dom_node *node2)
 546 {
 547         /* Assuming the same document type */
 548         if (node1->data.element.type
 549             && node2->data.element.type
 550             && node1->data.element.type == node2->data.element.type)
 551                 return 0;
 552
 553         return dom_string_casecmp(&node1->string, &node2->string);
 554 }
 555
 556 static struct dom_select_node *
 557 get_child_dom_select_node(struct dom_select_node *selector,
 558                           enum dom_node_type type)
 559 {
 560         struct dom_node_list *children = selector->node.data.element.children;
 561         struct dom_node *node;
 562         int index;
 563
 564         if (!children)
 565                 return NULL;
 566
 567         foreach_dom_node (children, node, index) {
 568                 if (node->type == type)
 569                         return (struct dom_select_node *) node;
 570         }
 571
 572         return NULL;
 573 }
 574
 575
 576 #define has_attribute_match(selector, name) \
 577         ((selector)->match.attribute & (name))
 578
 579 static int
 580 match_attribute_selectors(struct dom_select_node *base, struct dom_node *node)
 581 {
 582         struct dom_node_list *attrs = node->data.element.map;
 583         struct dom_node_list *selnodes = base->node.data.element.map;
 584         struct dom_node *selnode;
 585         size_t index;
 586
 587         assert(base->node.type == DOM_NODE_ELEMENT
 588                && node->type == DOM_NODE_ELEMENT);
 589
 590         if (!selnodes)
 591                 return 1;
 592
 593         if (!attrs)
 594                 return 0;
 595
 596         foreach_dom_node (selnodes, selnode, index) {
 597                 struct dom_select_node *selector = (void *) selnode;
 598                 struct dom_node *attr;
 599                 struct dom_string *value;
 600                 struct dom_string *selvalue;
 601
 602                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_ID)) {
 603                         size_t idindex;
 604
 605                         attr = NULL;
 606                         foreach_dom_node (attrs, attr, idindex) {
 607                                 if (attr->data.attribute.id)
 608                                         break;
 609                         }
 610
 611                         if (!is_dom_node_list_member(attrs, idindex))
 612                                 attr = NULL;
 613
 614                 } else {
 615                         attr = get_dom_node_map_entry(attrs, DOM_NODE_ATTRIBUTE,
 616                                                       selnode->data.attribute.type,
 617                                                       &selnode->string);
 618                 }
 619
 620                 if (!attr)
 621                         return 0;
 622
 623                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_ANY))
 624                         continue;
 625
 626                 value    = &attr->data.attribute.value;
 627                 selvalue = &selnode->data.attribute.value;
 628
 629                 if (value->length < selvalue->length)
 630                         return 0;
 631
 632                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_EXACT)
 633                     && dom_string_casecmp(value, selvalue))
 634                         return 0;
 635
 636                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_BEGIN))
 637                         return 0;
 638
 639                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_END))
 640                         return 0;
 641
 642                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_SPACE_LIST))
 643                         return 0;
 644
 645                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_HYPHEN_LIST))
 646                         return 0;
 647
 648                 if (has_attribute_match(selector, DOM_SELECT_ATTRIBUTE_CONTAINS))
 649                         return 0;
 650         }
 651
 652         return 1;
 653 }
 654
 655 #define has_element_match(selector, name) \
 656         ((selector)->match.element & (name))
 657
 658 static void
 659 dom_select_push_element(struct dom_stack *stack, struct dom_node *node, void *data)
 660 {
 661         struct dom_select_data *select_data = stack->data;
 662         struct dom_stack_state *state;
 663         int pos;
 664
 665         WDBG("Push element %.*s.", node->string.length, node->string.string);
 666
 667         foreach_dom_stack_state(&select_data->stack, state, pos) {
 668                 struct dom_select_node *selector = (void *) state->node;
 669
 670                 /* Match the node. */
 671                 if (!has_element_match(selector, DOM_SELECT_ELEMENT_UNIVERSAL)
 672                     && compare_element_type(&selector->node, node))
 673                         continue;
 674
 675                 switch (get_element_relation(selector)) {
 676                 case DOM_SELECT_RELATION_DIRECT_CHILD:          /* E > F */
 677                         /* node->parent */
 678                         /* Check all states to see if node->parent is there
 679                          * and for the right reasons. */
 680                         break;
 681
 682                 case DOM_SELECT_RELATION_DIRECT_ADJACENT:       /* E + F */
 683                         /* Get preceding node to see if it is on the stack. */
 684                         break;
 685
 686                 case DOM_SELECT_RELATION_INDIRECT_ADJACENT:     /* E ~ F */
 687                         /* Check all states with same depth? */
 688                         break;
 689
 690                 case DOM_SELECT_RELATION_DESCENDANT:            /* E   F */
 691                 default:
 692                         break;
 693                 }
 694
 695                 /* Roots don't have parent nodes. */
 696                 if (has_element_match(selector, DOM_SELECT_ELEMENT_ROOT)
 697                     && node->parent)
 698                         continue;
 699
 700                 if (has_element_match(selector, DOM_SELECT_ELEMENT_EMPTY)
 701                     && node->data.element.map->size > 0)
 702                         continue;
 703
 704                 if (has_element_match(selector, DOM_SELECT_ELEMENT_NTH_CHILD)) {
 705                         /* FIXME */
 706                         continue;
 707                 }
 708
 709                 if (has_element_match(selector, DOM_SELECT_ELEMENT_NTH_TYPE)) {
 710                         /* FIXME */
 711                         continue;
 712                 }
 713
 714                 /* Check attribute selectors. */
 715                 if (selector->node.data.element.map
 716                     && !match_attribute_selectors(selector, node))
 717                         continue;
 718
 719                 WDBG("Matched element: %.*s.", node->string.length, node->string.string);
 720                 /* This node is matched, so push the next selector node to
 721                  * match on the stack. */
 722                 selector = get_child_dom_select_node(selector, DOM_NODE_ELEMENT);
 723                 if (selector)
 724                         push_dom_node(&select_data->stack, &selector->node);
 725         }
 726 }
 727
 728 static void
 729 dom_select_pop_element(struct dom_stack *stack, struct dom_node *node, void *data)
 730 {
 731         struct dom_select_data *select_data = stack->data;
 732         struct dom_stack_state *state;
 733         int index;
 734
 735         WDBG("Pop element: %.*s", node->string.length, node->string.string);
 736         stack = &select_data->stack;
 737
 738         foreachback_dom_stack_state (stack, state, index) {
 739                 struct dom_select_node *selector = (void *) state->node;
 740                 struct dom_select_state *select_state;
 741
 742                 select_state = get_dom_stack_state_data(stack, state);
 743                 if (select_state->node == node) {
 744                         pop_dom_state(stack, state);
 745                         WDBG("Remove element.");
 746                         continue;
 747                 }
 748
 749                 /* Pop states that no longer lives up to a relation. */
 750                 switch (get_element_relation(selector)) {
 751                 case DOM_SELECT_RELATION_DIRECT_CHILD:          /* E > F */
 752                 case DOM_SELECT_RELATION_DIRECT_ADJACENT:       /* E + F */
 753                 case DOM_SELECT_RELATION_INDIRECT_ADJACENT:     /* E ~ F */
 754                 case DOM_SELECT_RELATION_DESCENDANT:            /* E   F */
 755                 default:
 756                         break;
 757                 }
 758         }
 759 }
 760
 761 static void
 762 dom_select_push_text(struct dom_stack *stack, struct dom_node *node, void *data)
 763 {
 764         struct dom_select_data *select_data = stack->data;
 765         struct dom_stack_state *state = get_dom_stack_top(&select_data->stack);
 766         struct dom_select_node *selector = (void *) state->node;
 767         struct dom_select_node *text_sel = get_child_dom_select_node(selector, DOM_NODE_TEXT);
 768         struct dom_string *text;
 769
 770         WDBG("Text node: %d chars", node->string.length);
 771
 772         if (!text_sel)
 773                 return;
 774
 775         text = &text_sel->node.string;
 776
 777         switch (node->type) {
 778         case DOM_NODE_TEXT:
 779         case DOM_NODE_CDATA_SECTION:
 780         case DOM_NODE_ENTITY_REFERENCE:
 781                 break;
 782         default:
 783                 ERROR("Unhandled type");
 784         }
 785 }
 786
 787 static struct dom_stack_context_info dom_select_context_info = {
 788         /* Push: */
 789         {
 790                 /*                              */ NULL,
 791                 /* DOM_NODE_ELEMENT             */ dom_select_push_element,
 792                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 793                 /* DOM_NODE_TEXT                */ dom_select_push_text,
 794                 /* DOM_NODE_CDATA_SECTION       */ dom_select_push_text,
 795                 /* DOM_NODE_ENTITY_REFERENCE    */ dom_select_push_text,
 796                 /* DOM_NODE_ENTITY              */ NULL,
 797                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 798                 /* DOM_NODE_COMMENT             */ NULL,
 799                 /* DOM_NODE_DOCUMENT            */ NULL,
 800                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 801                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 802                 /* DOM_NODE_NOTATION            */ NULL,
 803         },
 804         /* Pop: */
 805         {
 806                 /*                              */ NULL,
 807                 /* DOM_NODE_ELEMENT             */ dom_select_pop_element,
 808                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 809                 /* DOM_NODE_TEXT                */ NULL,
 810                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 811                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 812                 /* DOM_NODE_ENTITY              */ NULL,
 813                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 814                 /* DOM_NODE_COMMENT             */ NULL,
 815                 /* DOM_NODE_DOCUMENT            */ NULL,
 816                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 817                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 818                 /* DOM_NODE_NOTATION            */ NULL,
 819         }
 820 };
 821
 822 struct dom_node_list *
 823 select_dom_nodes(struct dom_select *select, struct dom_node *root)
 824 {
 825         struct dom_select_data select_data;
 826         struct dom_stack stack;
 827         size_t obj_size = sizeof(struct dom_select_state);
 828
 829         memset(&select_data, 0, sizeof(select_data));
 830
 831         select_data.select = select;;
 832
 833         init_dom_stack(&stack, &select_data, 0, 1);
 834         add_dom_stack_callbacks(&stack, &dom_select_context_info);
 835
 836         init_dom_stack(&select_data.stack, &select_data, obj_size, 1);
 837
 838         if (push_dom_node(&select_data.stack, &select->selector->node)) {
 839                 get_dom_stack_top(&select_data.stack)->immutable = 1;
 840                 walk_dom_nodes(&stack, root);
 841         }
 842
 843         done_dom_stack(&select_data.stack);
 844         done_dom_stack(&stack);
 845
 846         return select_data.list;
 847 }