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