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                 if (action == DOM_STACK_PUSH)
 143                         callback = context->info->push[state->node->type];
 144                 else
 145                         callback = context->info->pop[state->node->type];
 146
 147                 if (callback) {
 148                         void *data = get_dom_stack_state_data(context, state);
 149
 150                         stack->current = context;
 151                         switch (callback(stack, state->node, data)) {
 152                         case DOM_CODE_FREE_NODE:
 153                                 free_node = 1;
 154                                 break;
 155                         default:
 156                                 break;
 157                         }
 158                         stack->current = NULL;
 159                 }
 160         }
 161
 162         return free_node;
 163 }
 164
 165 enum dom_code
 166 push_dom_node(struct dom_stack *stack, struct dom_node *node)
 167 {
 168         struct dom_stack_state *state;
 169         int i;
 170
 171         assert(stack && node);
 172         assert(0 < node->type && node->type < DOM_NODES);
 173
 174         if (stack->depth > DOM_STACK_MAX_DEPTH) {
 175                 return DOM_CODE_MAX_DEPTH_ERR;
 176         }
 177
 178         state = realloc_dom_stack_states(&stack->states, stack->depth);
 179         if (!state) {
 180                 done_dom_node(node);
 181                 return DOM_CODE_ALLOC_ERR;
 182         }
 183
 184         state += stack->depth;
 185
 186         for (i = 0; i < stack->contexts_size; i++) {
 187                 struct dom_stack_context *context = stack->contexts[i];
 188
 189                 if (context->info->object_size
 190                     && !realloc_dom_stack_state_objects(context, stack->depth)) {
 191                         done_dom_node(node);
 192                         return DOM_CODE_ALLOC_ERR;
 193                 }
 194         }
 195
 196         state->depth = stack->depth;
 197         state->node = node;
 198
 199         /* Grow the state array to the new depth so the state accessors work
 200          * in the callbacks */
 201         stack->depth++;
 202         call_dom_stack_callbacks(stack, state, DOM_STACK_PUSH);
 203
 204         return DOM_CODE_OK;
 205 }
 206
 207 void
 208 pop_dom_node(struct dom_stack *stack)
 209 {
 210         struct dom_stack_state *state;
 211         int i;
 212
 213         assert(stack);
 214
 215         if (dom_stack_is_empty(stack))
 216                 return;
 217
 218         state = get_dom_stack_top(stack);
 219         if (state->immutable)
 220                 return;
 221
 222         if (call_dom_stack_callbacks(stack, state, DOM_STACK_POP)
 223             || (stack->flags & DOM_STACK_FLAG_FREE_NODES))
 224                 done_dom_node(state->node);
 225
 226         stack->depth--;
 227         assert(stack->depth >= 0);
 228
 229         for (i = 0; i < stack->contexts_size; i++) {
 230                 struct dom_stack_context *context = stack->contexts[i];
 231
 232                 if (context->info->object_size) {
 233                         void *state_data = get_dom_stack_state_data(context, state);
 234
 235                         memset(state_data, 0, context->info->object_size);
 236                 }
 237         }
 238
 239         memset(state, 0, sizeof(*state));
 240 }
 241
 242 void
 243 pop_dom_nodes(struct dom_stack *stack, enum dom_node_type type,
 244               struct dom_string *string)
 245 {
 246         struct dom_stack_state *state;
 247
 248         assert(stack);
 249
 250         if (dom_stack_is_empty(stack)) return;
 251
 252         state = search_dom_stack(stack, type, string);
 253         if (state)
 254                 pop_dom_state(stack, state);
 255 }
 256
 257 void
 258 pop_dom_state(struct dom_stack *stack, struct dom_stack_state *target)
 259 {
 260         struct dom_stack_state *state;
 261         unsigned int pos;
 262
 263         assert(stack);
 264
 265         if (!target) return;
 266
 267         if (dom_stack_is_empty(stack)) return;
 268
 269         foreachback_dom_stack_state (stack, state, pos) {
 270                 /* Don't pop past states marked immutable. */
 271                 if (state->immutable)
 272                         break;
 273
 274                 /* Pop until the target state is reached. */
 275                 pop_dom_node(stack);
 276                 if (state == target)
 277                         break;
 278         }
 279 }
 280
 281 struct dom_stack_state *
 282 search_dom_stack(struct dom_stack *stack, enum dom_node_type type,
 283                  struct dom_string *string)
 284 {
 285         struct dom_stack_state *state;
 286         int pos;
 287
 288         /* FIXME: Take node subtype and compare if non-zero or something. */
 289         foreachback_dom_stack_state (stack, state, pos) {
 290                 struct dom_node *parent = state->node;
 291
 292                 if (parent->type == type
 293                     && !dom_string_casecmp(&parent->string, string))
 294                         return state;
 295         }
 296
 297         return NULL;
 298 }
 299
 300
 301 struct dom_stack_walk_state {
 302         /* Used for recording which node list are currently being 'decended'
 303          * into. E.g. whether we are iterating all child elements or attributes
 304          * of an element. */
 305         struct dom_node_list *list;
 306         /* The index (in the list above) which are currently being handled. */
 307         size_t index;
 308 };
 309
 310 static struct dom_stack_context_info dom_stack_walk_context_info = {
 311         /* Object size: */                      sizeof(struct dom_stack_walk_state),
 312         /* Push: */
 313         {
 314                 /*                              */ NULL,
 315                 /* DOM_NODE_ELEMENT             */ NULL,
 316                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 317                 /* DOM_NODE_TEXT                */ NULL,
 318                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 319                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 320                 /* DOM_NODE_ENTITY              */ NULL,
 321                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 322                 /* DOM_NODE_COMMENT             */ NULL,
 323                 /* DOM_NODE_DOCUMENT            */ NULL,
 324                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 325                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 326                 /* DOM_NODE_NOTATION            */ NULL,
 327         },
 328         /* Pop: */
 329         {
 330                 /*                              */ NULL,
 331                 /* DOM_NODE_ELEMENT             */ NULL,
 332                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 333                 /* DOM_NODE_TEXT                */ NULL,
 334                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 335                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 336                 /* DOM_NODE_ENTITY              */ NULL,
 337                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 338                 /* DOM_NODE_COMMENT             */ NULL,
 339                 /* DOM_NODE_DOCUMENT            */ NULL,
 340                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 341                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 342                 /* DOM_NODE_NOTATION            */ NULL,
 343         }
 344 };
 345
 346 /* FIXME: Instead of walking all nodes in the tree only visit those which are
 347  * of actual interest to the contexts on the stack. */
 348 void
 349 walk_dom_nodes(struct dom_stack *stack, struct dom_node *root)
 350 {
 351         struct dom_stack_context *context;
 352
 353         assert(root && stack);
 354
 355         context = add_dom_stack_context(stack, NULL, &dom_stack_walk_context_info);
 356         if (!context)
 357                 return;
 358
 359         if (push_dom_node(stack, root) != DOM_CODE_OK)
 360                 return;
 361
 362         while (!dom_stack_is_empty(stack)) {
 363                 struct dom_stack_state *state = get_dom_stack_top(stack);
 364                 struct dom_stack_walk_state *wstate = get_dom_stack_state_data(context, state);
 365                 struct dom_node_list *list = wstate->list;
 366                 struct dom_node *node = state->node;
 367
 368                 switch (node->type) {
 369                 case DOM_NODE_DOCUMENT:
 370                         if (!list) list = node->data.document.children;
 371                         break;
 372
 373                 case DOM_NODE_ELEMENT:
 374                         if (!list) list = node->data.element.map;
 375
 376                         if (list == node->data.element.children) break;
 377                         if (is_dom_node_list_member(list, wstate->index)
 378                             && list == node->data.element.map)
 379                                 break;
 380
 381                         list = node->data.element.children;
 382                         break;
 383
 384                 case DOM_NODE_PROCESSING_INSTRUCTION:
 385                         if (!list) list = node->data.proc_instruction.map;
 386                         break;
 387
 388                 case DOM_NODE_DOCUMENT_TYPE:
 389                         if (!list) list = node->data.document_type.entities;
 390
 391                         if (list == node->data.document_type.notations) break;
 392                         if (is_dom_node_list_member(list, wstate->index)
 393                             && list == node->data.document_type.entities)
 394                                 break;
 395
 396                         list = node->data.document_type.notations;
 397                         break;
 398
 399                 case DOM_NODE_ATTRIBUTE:
 400                 case DOM_NODE_TEXT:
 401                 case DOM_NODE_CDATA_SECTION:
 402                 case DOM_NODE_COMMENT:
 403                 case DOM_NODE_NOTATION:
 404                 case DOM_NODE_DOCUMENT_FRAGMENT:
 405                 case DOM_NODE_ENTITY_REFERENCE:
 406                 case DOM_NODE_ENTITY:
 407                 default:
 408                         break;
 409                 }
 410
 411                 /* Reset list state if it is a new list */
 412                 if (list != wstate->list) {
 413                         wstate->list  = list;
 414                         wstate->index = 0;
 415                 }
 416
 417                 /* If we have next child node */
 418                 if (is_dom_node_list_member(list, wstate->index)) {
 419                         struct dom_node *child = list->entries[wstate->index++];
 420
 421                         if (push_dom_node(stack, child) == DOM_CODE_OK)
 422                                 continue;
 423                 }
 424
 425                 pop_dom_node(stack);
 426         }
 427
 428         done_dom_stack_context(stack, context);
 429 }
 430
 431
 432 /* DOM Stack Tracing: */
 433
 434 #ifdef DOM_STACK_TRACE
 435
 436 #include "util/string.h"
 437
 438 /* Compress a string to a single line with newlines etc. replaced with "\\n"
 439  * sequence. */
 440 static inline unsigned char *
 441 compress_string(unsigned char *string, unsigned int length)
 442 {
 443         struct string buffer;
 444         unsigned char escape[2] = "\\";
 445
 446         if (!init_string(&buffer)) return NULL;
 447
 448         for (; length > 0; string++, length--) {
 449                 unsigned char *bytes = string;
 450
 451                 if (*string == '\n' || *string == '\r' || *string == '\t') {
 452                         bytes     = escape;
 453                         escape[1] = *string == '\n' ? 'n'
 454                                   : (*string == '\r' ? 'r' : 't');
 455                 }
 456
 457                 add_bytes_to_string(&buffer, bytes, bytes == escape ? 2 : 1);
 458         }
 459
 460         return buffer.source;
 461 }
 462
 463 /* Set @string to the value of the given @node, however, with strings
 464  * compressed and entity references 'expanded'. */
 465 static void
 466 set_enhanced_dom_node_value(struct dom_string *string, struct dom_node *node)
 467 {
 468         struct dom_string *value;
 469
 470         assert(node);
 471
 472         memset(string, 0, sizeof(*string));
 473
 474         switch (node->type) {
 475         case DOM_NODE_ENTITY_REFERENCE:
 476                 /* FIXME: Set to the entity value. */
 477                 string->string = null_or_stracpy(string->string);
 478                 break;
 479
 480         default:
 481                 value = get_dom_node_value(node);
 482                 if (!value) {
 483                         set_dom_string(string, NULL, 0);
 484                         return;
 485                 }
 486
 487                 string->string = compress_string(value->string, value->length);
 488         }
 489
 490         string->length = string->string ? strlen(string->string) : 0;
 491 }
 492
 493 static unsigned char indent_string[] =
 494         "                                                                    ";
 495
 496 #define get_indent_offset(stack) \
 497         ((stack)->depth < sizeof(indent_string)/2 ? (stack)->depth * 2 : sizeof(indent_string))
 498
 499 enum dom_code
 500 dom_stack_trace_tree(struct dom_stack *stack, struct dom_node *node, void *data)
 501 {
 502         struct dom_string *value = &node->string;
 503         struct dom_string *name = get_dom_node_name(node);
 504
 505         LOG_INFO("%s%.*s %.*s: %.*s",
 506                 empty_string_or_(stack->current->data),
 507                 get_indent_offset(stack), indent_string,
 508                 name->length, name->string,
 509                 value->length, value->string);
 510
 511         return DOM_CODE_OK;
 512 }
 513
 514 enum dom_code
 515 dom_stack_trace_id_leaf(struct dom_stack *stack, struct dom_node *node, void *data)
 516 {
 517         struct dom_string value;
 518         struct dom_string *name;
 519         struct dom_string *id;
 520
 521         assert(node);
 522
 523         name    = get_dom_node_name(node);
 524         id      = get_dom_node_type_name(node->type);
 525         set_enhanced_dom_node_value(&value, node);
 526
 527         LOG_INFO("%s%.*s %.*s: %.*s -> %.*s",
 528                 empty_string_or_(stack->current->data),
 529                 get_indent_offset(stack), indent_string,
 530                 id->length, id->string, name->length, name->string,
 531                 value.length, value.string);
 532
 533         done_dom_string(&value);
 534
 535         return DOM_CODE_OK;
 536 }
 537
 538 enum dom_code
 539 dom_stack_trace_leaf(struct dom_stack *stack, struct dom_node *node, void *data)
 540 {
 541         struct dom_string *name;
 542         struct dom_string value;
 543
 544         assert(node);
 545
 546         name    = get_dom_node_name(node);
 547         set_enhanced_dom_node_value(&value, node);
 548
 549         LOG_INFO("%s%.*s %.*s: %.*s",
 550                 empty_string_or_(stack->current->data),
 551                 get_indent_offset(stack), indent_string,
 552                 name->length, name->string,
 553                 value.length, value.string);
 554
 555         done_dom_string(&value);
 556
 557         return DOM_CODE_OK;
 558 }
 559
 560 enum dom_code
 561 dom_stack_trace_branch(struct dom_stack *stack, struct dom_node *node, void *data)
 562 {
 563         struct dom_string *name;
 564         struct dom_string *id;
 565
 566         assert(node);
 567
 568         name    = get_dom_node_name(node);
 569         id      = get_dom_node_type_name(node->type);
 570
 571         LOG_INFO("%s%.*s %.*s: %.*s",
 572                 empty_string_or_(stack->current->data),
 573                 get_indent_offset(stack), indent_string,
 574                 id->length, id->string, name->length, name->string);
 575
 576         return DOM_CODE_OK;
 577 }
 578
 579 struct dom_stack_context_info dom_stack_trace_context_info = {
 580         /* Object size: */                      0,
 581         /* Push: */
 582         {
 583                 /*                              */ NULL,
 584                 /* DOM_NODE_ELEMENT             */ dom_stack_trace_branch,
 585                 /* DOM_NODE_ATTRIBUTE           */ dom_stack_trace_id_leaf,
 586                 /* DOM_NODE_TEXT                */ dom_stack_trace_leaf,
 587                 /* DOM_NODE_CDATA_SECTION       */ dom_stack_trace_id_leaf,
 588                 /* DOM_NODE_ENTITY_REFERENCE    */ dom_stack_trace_id_leaf,
 589                 /* DOM_NODE_ENTITY              */ dom_stack_trace_id_leaf,
 590                 /* DOM_NODE_PROC_INSTRUCTION    */ dom_stack_trace_id_leaf,
 591                 /* DOM_NODE_COMMENT             */ dom_stack_trace_leaf,
 592                 /* DOM_NODE_DOCUMENT            */ dom_stack_trace_tree,
 593                 /* DOM_NODE_DOCUMENT_TYPE       */ dom_stack_trace_id_leaf,
 594                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ dom_stack_trace_id_leaf,
 595                 /* DOM_NODE_NOTATION            */ dom_stack_trace_id_leaf,
 596         },
 597         /* Pop: */
 598         {
 599                 /*                              */ NULL,
 600                 /* DOM_NODE_ELEMENT             */ NULL,
 601                 /* DOM_NODE_ATTRIBUTE           */ NULL,
 602                 /* DOM_NODE_TEXT                */ NULL,
 603                 /* DOM_NODE_CDATA_SECTION       */ NULL,
 604                 /* DOM_NODE_ENTITY_REFERENCE    */ NULL,
 605                 /* DOM_NODE_ENTITY              */ NULL,
 606                 /* DOM_NODE_PROC_INSTRUCTION    */ NULL,
 607                 /* DOM_NODE_COMMENT             */ NULL,
 608                 /* DOM_NODE_DOCUMENT            */ NULL,
 609                 /* DOM_NODE_DOCUMENT_TYPE       */ NULL,
 610                 /* DOM_NODE_DOCUMENT_FRAGMENT   */ NULL,
 611                 /* DOM_NODE_NOTATION            */ NULL,
 612         }
 613 };
 614
 615 #endif /* DOM_STACK_TRACE */