src/dom/stack.c

   1 /* The DOM tree navigation interface */
   2
   3 #ifdef HAVE_CONFIG_H
   4 #include "config.h"
   5 #endif
   6
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 #include "elinks.h"
  11
  12 #include "dom/node.h"
  13 #include "dom/stack.h"
  14 #include "dom/string.h"
  15 #include "util/memory.h"
  16
  17
  18 /* Navigator states */
  19
  20 #define DOM_STACK_STATE_GRANULARITY     0x7
  21 #define DOM_STACK_CALLBACKS_SIZE        (sizeof(dom_stack_callback_T) * DOM_NODES)
  22
  23 static inline struct dom_stack_state *
  24 realloc_dom_stack_states(struct dom_stack_state **states, size_t size)
  25 {
  26         return mem_align_alloc(states, size, size + 1,
  27                                DOM_STACK_STATE_GRANULARITY);
  28 }
  29
  30 static inline struct dom_stack_state *
  31 realloc_dom_stack_context(struct dom_stack_context ***contexts, size_t size)
  32 {
  33         return mem_align_alloc(contexts, size, size + 1,
  34                                DOM_STACK_STATE_GRANULARITY);
  35 }
  36
  37 static inline unsigned char *
  38 realloc_dom_stack_state_objects(struct dom_stack_context *context, size_t depth)
  39 {
  40 #ifdef DEBUG_MEMLEAK
  41         return mem_align_alloc__(__FILE__, __LINE__, (void **) &context->state_objects,
  42                                depth, depth + 1,
  43                                context->info->object_size,
  44                                DOM_STACK_STATE_GRANULARITY);
  45 #else
  46         return mem_align_alloc__((void **) &context->state_objects,
  47                                depth, depth + 1,
  48                                context->info->object_size,
  49                                DOM_STACK_STATE_GRANULARITY);
  50 #endif
  51 }
  52
  53 void
  54 init_dom_stack(struct dom_stack *stack, enum dom_stack_flag flags)
  55 {
  56         assert(stack);
  57
  58         memset(stack, 0, sizeof(*stack));
  59
  60         stack->flags = flags;
  61 }
  62
  63 void
  64 done_dom_stack(struct dom_stack *stack)
  65 {
  66         int i;
  67
  68         assert(stack);
  69
  70         for (i = 0; i < stack->contexts_size; i++) {
  71                 mem_free_if(stack->contexts[i]->state_objects);
  72                 mem_free(stack->contexts[i]);
  73         }
  74
  75         mem_free_if(stack->contexts);
  76         mem_free_if(stack->states);
  77
  78         memset(stack, 0, sizeof(*stack));
  79 }
  80
  81 struct dom_stack_context *
  82 add_dom_stack_context(struct dom_stack *stack, void *data,
  83                       struct dom_stack_context_info *context_info)
  84 {
  85         struct dom_stack_context *context;
  86
  87         if (!realloc_dom_stack_context(&stack->contexts, stack->contexts_size))
  88                 return NULL;
  89
  90         context = mem_calloc(1, sizeof(*context));
  91         if (!context)
  92                 return NULL;
  93
  94         stack->contexts[stack->contexts_size++] = context;
  95         context->info = context_info;
  96         context->data = data;
  97
  98         return context;
  99 }
 100
 101 void
 102 done_dom_stack_context(struct dom_stack *stack, struct dom_stack_context *context)
 103 {
 104         size_t i;
 105
 106         mem_free_if(context->state_objects);
 107         mem_free(context);
 108
 109         /* Handle the trivial case of temporary contexts optimally by iteration last added first. */
 110         for (i = stack->contexts_size - 1; i >= 0; i--) {
 111                 if (stack->contexts[i] != context)
 112                         continue;
 113
 114                 stack->contexts_size--;
 115                 if (i < stack->contexts_size) {
 116                         struct dom_stack_context **pos = &stack->contexts[i];
 117                         size_t size = stack->contexts_size - i;
 118
 119                         memmove(pos, pos + 1, size * sizeof(*pos));
 120                 }
 121                 break;
 122         }
 123 }
 124
 125 enum dom_stack_action {
 126         DOM_STACK_PUSH,
 127         DOM_STACK_POP,
 128 };
 129
 130 /* Returns whether the node should be freed with done_dom_node(). */
 131 static int
 132 call_dom_stack_callbacks(struct dom_stack *stack, struct dom_stack_state *state,
 133                          enum dom_stack_action action)
 134 {
 135         int free_node = 0;
 136         int i;
 137
 138         for (i = 0; i < stack->contexts_size; i++) {
 139                 struct dom_stack_context *context = stack->contexts[i];
 140                 dom_stack_callback_T callback;
 141
 142                 assert(state->node->type < DOM_NODES); /* unsigned comparison */
 143                 if_assert_failed {
 144                         /* The node type is out of range for the
 145                          * callback arrays.  The node may have been
 146                          * corrupted or already freed.  Ignore
 147                          * free_node here because attempting to free
 148                          * the node would probably just corrupt things
 149                          * further.  */
 150                         return 0;
 151                 }
 152
 153                 if (action == DOM_STACK_PUSH)
 154                         callback = context->info->push[state->node->type];
 155                 else
 156                         callback = context->info->pop[state->node->type];
 157
 158                 if (callback) {
 159                         void *data = get_dom_stack_state_data(context, state);
 160
 161                         stack->current = context;
 162                         switch (callback(stack, state->node, data)) {
 163                         case DOM_CODE_FREE_NODE:
 164                                 free_node = 1;
 165                                 break;
 166                         default:
 167                                 break;
 168                         }
 169                         stack->current = NULL;
 170                 }
 171         }
 172
 173         return free_node;
 174 }
 175
 176 enum dom_code
 177 push_dom_node(struct dom_stack *stack, struct dom_node *node)
 178 {
 179         struct dom_stack_state *state;
 180         int i;
 181
 182         assert(stack && node);
 183         assert(0 < node->type && node->type < DOM_NODES);
 184
 185         if (stack->depth > DOM_STACK_MAX_DEPTH) {
 186                 return DOM_CODE_MAX_DEPTH_ERR;
 187         }
 188
 189         state = realloc_dom_stack_states(&stack->states, stack->depth);
 190         if (!state) {
 191                 done_dom_node(node);
 192                 return DOM_CODE_ALLOC_ERR;
 193         }
 194
 195         state += stack->depth;
 196
 197         for (i = 0; i < stack->contexts_size; i++) {
 198                 struct dom_stack_context *context = stack->contexts[i];
 199
 200                 if (context->info->object_size
 201                     && !realloc_dom_stack_state_objects(context, stack->depth)) {
 202                         done_dom_node(node);
 203                         return DOM_CODE_ALLOC_ERR;
 204                 }
 205         }
 206
 207         state->depth = stack->depth;
 208         state->node = node;
 209
 210         /* Grow the state array to the new depth so the state accessors work
 211          * in the callbacks */
 212         stack->depth++;
 213         call_dom_stack_callbacks(stack, state, DOM_STACK_PUSH);
 214
 215         return DOM_CODE_OK;
 216 }
 217
 218 void
 219 pop_dom_node(struct dom_stack *stack)
 220 {
 221         struct dom_stack_state *state;
 222         int i;
 223
 224         assert(stack);
 225
 226         if (dom_stack_is_empty(stack))
 227                 return;
 228
 229         state = get_dom_stack_top(stack);
 230         if (state->immutable)
 231                 return;
 232
 233         if (call_dom_stack_callbacks(stack, state, DOM_STACK_POP)
 234             || (stack->flags & DOM_STACK_FLAG_FREE_NODES))
 235                 done_dom_node(state->node);
 236
 237         stack->depth--;
 238         assert(stack->depth >= 0);
 239
 240         for (i = 0; i < stack->contexts_size; i++) {
 241                 struct dom_stack_context *context = stack->contexts[i];
 242
 243                 if (context->info->object_size) {
 244                         void *state_data = get_dom_stack_state_data(context, state);
 245
 246                         memset(state_data, 0, context->info->object_size);
 247                 }
 248         }
 249
 250         memset(state, 0, sizeof(*state));
 251 }
 252
 253 void
 254 pop_dom_nodes(struct dom_stack *stack, enum dom_node_type type,
 255               struct dom_string *string)
 256 {
 257         struct dom_stack_state *state;
 258
 259         assert(stack);
 260
 261         if (dom_stack_is_empty(stack)) return;
 262
 263         state = search_dom_stack(stack, type, string);
 264         if (state)
 265                 pop_dom_state(stack, state);
 266 }
 267
 268 void
 269 pop_dom_state(struct dom_stack *stack, struct dom_stack_state *target)
 270 {
 271         struct dom_stack_state *state;
 272         unsigned int pos;
 273
 274         assert(stack);
 275
 276         if (!target) return;
 277
 278         if (dom_stack_is_empty(stack)) return;
 279
 280         foreachback_dom_stack_state (stack, state, pos) {
 281                 /* Don't pop past states marked immutable. */
 282                 if (state->immutable)
 283                         break;
 284
 285                 /* Pop until the target state is reached. */
 286                 pop_dom_node(stack);
 287                 if (state == target)
 288                         break;
 289         }
 290 }
 291
 292 struct dom_stack_state *
 293 search_dom_stack(struct dom_stack *stack, enum dom_node_type type,
 294                  struct dom_string *string)
 295 {
 296         struct dom_stack_state *state;
 297         int pos;
 298
 299         /* FIXME: Take node subtype and compare if non-zero or something. */
 300         foreachback_dom_stack_state (stack, state, pos) {
 301                 struct dom_node *parent = state->node;
 302
 303                 if (parent->type == type
 304                     && !dom_string_casecmp(&parent->string, string))
 305                         return state;
 306         }
 307
 308         return NULL;
 309 }
 310
 311
 312 struct dom_stack_walk_state {
 313         /* Used for recording which node list are currently being 'decended'
 314          * into. E.g. whether we are iterating all child elements or attributes
 315          * of an element. */
 316         struct dom_node_list *list;
 317         /* The index (in the list above) which are currently being handled. */
 318         size_t index;
 319 };
 320
 321 static struct dom_stack_context_info dom_stack_walk_context_info = {
 322         /* Object size: */                      sizeof(struct dom_stack_walk_state),
 323         /* Push: */
 324         {
 325                 /*                              */ NULL,
 326                 /* DOM_NODE_ELEMENT             */ NULL,
 327                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 328                 /* DOM_NODE_TEXT                */ NULL,
 329                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 330                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 331                 /* DOM_NODE_ENTITY              */ NULL,
 332                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 333                 /* DOM_NODE_COMMENT             */ NULL,
 334                 /* DOM_NODE_DOCUMENT            */ NULL,
 335                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 336                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 337                 /* DOM_NODE_NOTATION            */ NULL,
 338         },
 339         /* Pop: */
 340         {
 341                 /*                              */ NULL,
 342                 /* DOM_NODE_ELEMENT             */ NULL,
 343                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 344                 /* DOM_NODE_TEXT                */ NULL,
 345                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 346                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 347                 /* DOM_NODE_ENTITY              */ NULL,
 348                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 349                 /* DOM_NODE_COMMENT             */ NULL,
 350                 /* DOM_NODE_DOCUMENT            */ NULL,
 351                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 352                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 353                 /* DOM_NODE_NOTATION            */ NULL,
 354         }
 355 };
 356
 357 /* FIXME: Instead of walking all nodes in the tree only visit those which are
 358  * of actual interest to the contexts on the stack. */
 359 void
 360 walk_dom_nodes(struct dom_stack *stack, struct dom_node *root)
 361 {
 362         struct dom_stack_context *context;
 363
 364         assert(root && stack);
 365
 366         context = add_dom_stack_context(stack, NULL, &dom_stack_walk_context_info);
 367         if (!context)
 368                 return;
 369
 370         if (push_dom_node(stack, root) != DOM_CODE_OK)
 371                 return;
 372
 373         while (!dom_stack_is_empty(stack)) {
 374                 struct dom_stack_state *state = get_dom_stack_top(stack);
 375                 struct dom_stack_walk_state *wstate = get_dom_stack_state_data(context, state);
 376                 struct dom_node_list *list = wstate->list;
 377                 struct dom_node *node = state->node;
 378
 379                 switch (node->type) {
 380                 case DOM_NODE_DOCUMENT:
 381                         if (!list) list = node->data.document.children;
 382                         break;
 383
 384                 case DOM_NODE_ELEMENT:
 385                         if (!list) list = node->data.element.map;
 386
 387                         if (list == node->data.element.children) break;
 388                         if (is_dom_node_list_member(list, wstate->index)
 389                             && list == node->data.element.map)
 390                                 break;
 391
 392                         list = node->data.element.children;
 393                         break;
 394
 395                 case DOM_NODE_PROCESSING_INSTRUCTION:
 396                         if (!list) list = node->data.proc_instruction.map;
 397                         break;
 398
 399                 case DOM_NODE_DOCUMENT_TYPE:
 400                         if (!list) list = node->data.document_type.entities;
 401
 402                         if (list == node->data.document_type.notations) break;
 403                         if (is_dom_node_list_member(list, wstate->index)
 404                             && list == node->data.document_type.entities)
 405                                 break;
 406
 407                         list = node->data.document_type.notations;
 408                         break;
 409
 410                 case DOM_NODE_ATTRIBUTE:
 411                 case DOM_NODE_TEXT:
 412                 case DOM_NODE_CDATA_SECTION:
 413                 case DOM_NODE_COMMENT:
 414                 case DOM_NODE_NOTATION:
 415                 case DOM_NODE_DOCUMENT_FRAGMENT:
 416                 case DOM_NODE_ENTITY_REFERENCE:
 417                 case DOM_NODE_ENTITY:
 418                 default:
 419                         break;
 420                 }
 421
 422                 /* Reset list state if it is a new list */
 423                 if (list != wstate->list) {
 424                         wstate->list  = list;
 425                         wstate->index = 0;
 426                 }
 427
 428                 /* If we have next child node */
 429                 if (is_dom_node_list_member(list, wstate->index)) {
 430                         struct dom_node *child = list->entries[wstate->index++];
 431
 432                         if (push_dom_node(stack, child) == DOM_CODE_OK)
 433                                 continue;
 434                 }
 435
 436                 pop_dom_node(stack);
 437         }
 438
 439         done_dom_stack_context(stack, context);
 440 }
 441
 442
 443 /* DOM Stack Tracing: */
 444
 445 #ifdef DOM_STACK_TRACE
 446
 447 #include "util/string.h"
 448
 449 /* Compress a string to a single line with newlines etc. replaced with "\\n"
 450  * sequence. */
 451 static inline unsigned char *
 452 compress_string(unsigned char *string, unsigned int length)
 453 {
 454         struct string buffer;
 455         unsigned char escape[2] = "\\";
 456
 457         if (!init_string(&buffer)) return NULL;
 458
 459         for (; length > 0; string++, length--) {
 460                 unsigned char *bytes = string;
 461
 462                 if (*string == '\n' || *string == '\r' || *string == '\t') {
 463                         bytes     = escape;
 464                         escape[1] = *string == '\n' ? 'n'
 465                                   : (*string == '\r' ? 'r' : 't');
 466                 }
 467
 468                 add_bytes_to_string(&buffer, bytes, bytes == escape ? 2 : 1);
 469         }
 470
 471         return buffer.source;
 472 }
 473
 474 /* Set @string to the value of the given @node, however, with strings
 475  * compressed and entity references 'expanded'. */
 476 static void
 477 set_enhanced_dom_node_value(struct dom_string *string, struct dom_node *node)
 478 {
 479         struct dom_string *value;
 480
 481         assert(node);
 482
 483         memset(string, 0, sizeof(*string));
 484
 485         switch (node->type) {
 486         case DOM_NODE_ENTITY_REFERENCE:
 487                 /* FIXME: Set to the entity value. */
 488                 string->string = null_or_stracpy(string->string);
 489                 break;
 490
 491         default:
 492                 value = get_dom_node_value(node);
 493                 if (!value) {
 494                         set_dom_string(string, NULL, 0);
 495                         return;
 496                 }
 497
 498                 string->string = compress_string(value->string, value->length);
 499         }
 500
 501         string->length = string->string ? strlen(string->string) : 0;
 502 }
 503
 504 static unsigned char indent_string[] =
 505         "                                                                    ";
 506
 507 #define get_indent_offset(stack) \
 508         ((stack)->depth < sizeof(indent_string)/2 ? (stack)->depth * 2 : sizeof(indent_string))
 509
 510 enum dom_code
 511 dom_stack_trace_tree(struct dom_stack *stack, struct dom_node *node, void *data)
 512 {
 513         struct dom_string *value = &node->string;
 514         struct dom_string *name = get_dom_node_name(node);
 515
 516         LOG_INFO("%s%.*s %.*s: %.*s",
 517                 empty_string_or_(stack->current->data),
 518                 get_indent_offset(stack), indent_string,
 519                 name->length, name->string,
 520                 value->length, value->string);
 521
 522         return DOM_CODE_OK;
 523 }
 524
 525 enum dom_code
 526 dom_stack_trace_id_leaf(struct dom_stack *stack, struct dom_node *node, void *data)
 527 {
 528         struct dom_string value;
 529         struct dom_string *name;
 530         struct dom_string *id;
 531
 532         assert(node);
 533
 534         name    = get_dom_node_name(node);
 535         id      = get_dom_node_type_name(node->type);
 536         set_enhanced_dom_node_value(&value, node);
 537
 538         LOG_INFO("%s%.*s %.*s: %.*s -> %.*s",
 539                 empty_string_or_(stack->current->data),
 540                 get_indent_offset(stack), indent_string,
 541                 id->length, id->string, name->length, name->string,
 542                 value.length, value.string);
 543
 544         done_dom_string(&value);
 545
 546         return DOM_CODE_OK;
 547 }
 548
 549 enum dom_code
 550 dom_stack_trace_leaf(struct dom_stack *stack, struct dom_node *node, void *data)
 551 {
 552         struct dom_string *name;
 553         struct dom_string value;
 554
 555         assert(node);
 556
 557         name    = get_dom_node_name(node);
 558         set_enhanced_dom_node_value(&value, node);
 559
 560         LOG_INFO("%s%.*s %.*s: %.*s",
 561                 empty_string_or_(stack->current->data),
 562                 get_indent_offset(stack), indent_string,
 563                 name->length, name->string,
 564                 value.length, value.string);
 565
 566         done_dom_string(&value);
 567
 568         return DOM_CODE_OK;
 569 }
 570
 571 enum dom_code
 572 dom_stack_trace_branch(struct dom_stack *stack, struct dom_node *node, void *data)
 573 {
 574         struct dom_string *name;
 575         struct dom_string *id;
 576
 577         assert(node);
 578
 579         name    = get_dom_node_name(node);
 580         id      = get_dom_node_type_name(node->type);
 581
 582         LOG_INFO("%s%.*s %.*s: %.*s",
 583                 empty_string_or_(stack->current->data),
 584                 get_indent_offset(stack), indent_string,
 585                 id->length, id->string, name->length, name->string);
 586
 587         return DOM_CODE_OK;
 588 }
 589
 590 struct dom_stack_context_info dom_stack_trace_context_info = {
 591         /* Object size: */                      0,
 592         /* Push: */
 593         {
 594                 /*                              */ NULL,
 595                 /* DOM_NODE_ELEMENT             */ dom_stack_trace_branch,
 596                 /* DOM_NODE_ATTRIBUTE           */ dom_stack_trace_id_leaf,
 597                 /* DOM_NODE_TEXT                */ dom_stack_trace_leaf,
 598                 /* DOM_NODE_CDATA_SECTION       */ dom_stack_trace_id_leaf,
 599                 /* DOM_NODE_ENTITY_REFERENCE    */ dom_stack_trace_id_leaf,
 600                 /* DOM_NODE_ENTITY              */ dom_stack_trace_id_leaf,
 601                 /* DOM_NODE_PROC_INSTRUCTION    */ dom_stack_trace_id_leaf,
 602                 /* DOM_NODE_COMMENT             */ dom_stack_trace_leaf,
 603                 /* DOM_NODE_DOCUMENT            */ dom_stack_trace_tree,
 604                 /* DOM_NODE_DOCUMENT_TYPE       */ dom_stack_trace_id_leaf,
 605                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ dom_stack_trace_id_leaf,
 606                 /* DOM_NODE_NOTATION            */ dom_stack_trace_id_leaf,
 607         },
 608         /* Pop: */
 609         {
 610                 /*                              */ NULL,
 611                 /* DOM_NODE_ELEMENT             */ NULL,
 612                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 613                 /* DOM_NODE_TEXT                */ NULL,
 614                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 615                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 616                 /* DOM_NODE_ENTITY              */ NULL,
 617                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 618                 /* DOM_NODE_COMMENT             */ NULL,
 619                 /* DOM_NODE_DOCUMENT            */ NULL,
 620                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 621                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 622                 /* DOM_NODE_NOTATION            */ NULL,
 623         }
 624 };
 625
 626 #endif /* DOM_STACK_TRACE */