1 /* The DOM tree navigation interface */
13 #include "dom/stack.h"
14 #include "dom/string.h"
15 #include "util/memory.h"
18 /* Navigator states */
20 #define DOM_STACK_STATE_GRANULARITY 0x7
21 #define DOM_STACK_CALLBACKS_SIZE (sizeof(dom_stack_callback_T) * DOM_NODES)
23 static inline struct dom_stack_state
*
24 realloc_dom_stack_states(struct dom_stack_state
**states
, size_t size
)
26 return mem_align_alloc(states
, size
, size
+ 1,
27 DOM_STACK_STATE_GRANULARITY
);
30 static inline struct dom_stack_state
*
31 realloc_dom_stack_context(struct dom_stack_context
***contexts
, size_t size
)
33 return mem_align_alloc(contexts
, size
, size
+ 1,
34 DOM_STACK_STATE_GRANULARITY
);
37 static inline unsigned char *
38 realloc_dom_stack_state_objects(struct dom_stack_context
*context
, size_t depth
)
41 return mem_align_alloc__(__FILE__
, __LINE__
, (void **) &context
->state_objects
,
43 context
->info
->object_size
,
44 DOM_STACK_STATE_GRANULARITY
);
46 return mem_align_alloc__((void **) &context
->state_objects
,
48 context
->info
->object_size
,
49 DOM_STACK_STATE_GRANULARITY
);
54 init_dom_stack(struct dom_stack
*stack
, enum dom_stack_flag flags
)
58 memset(stack
, 0, sizeof(*stack
));
64 done_dom_stack(struct dom_stack
*stack
)
70 for (i
= 0; i
< stack
->contexts_size
; i
++) {
71 mem_free_if(stack
->contexts
[i
]->state_objects
);
72 mem_free(stack
->contexts
[i
]);
75 mem_free_if(stack
->contexts
);
76 mem_free_if(stack
->states
);
78 memset(stack
, 0, sizeof(*stack
));
81 struct dom_stack_context
*
82 add_dom_stack_context(struct dom_stack
*stack
, void *data
,
83 struct dom_stack_context_info
*context_info
)
85 struct dom_stack_context
*context
;
87 if (!realloc_dom_stack_context(&stack
->contexts
, stack
->contexts_size
))
90 context
= mem_calloc(1, sizeof(*context
));
94 stack
->contexts
[stack
->contexts_size
++] = context
;
95 context
->info
= context_info
;
102 done_dom_stack_context(struct dom_stack
*stack
, struct dom_stack_context
*context
)
106 mem_free_if(context
->state_objects
);
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
)
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
;
119 memmove(pos
, pos
+ 1, size
* sizeof(*pos
));
125 enum dom_stack_action
{
130 /* Returns whether the node should be freed with done_dom_node(). */
132 call_dom_stack_callbacks(struct dom_stack
*stack
, struct dom_stack_state
*state
,
133 enum dom_stack_action action
)
138 for (i
= 0; i
< stack
->contexts_size
; i
++) {
139 struct dom_stack_context
*context
= stack
->contexts
[i
];
140 dom_stack_callback_T callback
;
142 if (action
== DOM_STACK_PUSH
)
143 callback
= context
->info
->push
[state
->node
->type
];
145 callback
= context
->info
->pop
[state
->node
->type
];
148 void *data
= get_dom_stack_state_data(context
, state
);
150 stack
->current
= context
;
151 switch (callback(stack
, state
->node
, data
)) {
152 case DOM_CODE_FREE_NODE
:
158 stack
->current
= NULL
;
166 push_dom_node(struct dom_stack
*stack
, struct dom_node
*node
)
168 struct dom_stack_state
*state
;
171 assert(stack
&& node
);
172 assert(0 < node
->type
&& node
->type
< DOM_NODES
);
174 if (stack
->depth
> DOM_STACK_MAX_DEPTH
) {
175 return DOM_CODE_MAX_DEPTH_ERR
;
178 state
= realloc_dom_stack_states(&stack
->states
, stack
->depth
);
181 return DOM_CODE_ALLOC_ERR
;
184 state
+= stack
->depth
;
186 for (i
= 0; i
< stack
->contexts_size
; i
++) {
187 struct dom_stack_context
*context
= stack
->contexts
[i
];
189 if (context
->info
->object_size
190 && !realloc_dom_stack_state_objects(context
, stack
->depth
)) {
192 return DOM_CODE_ALLOC_ERR
;
196 state
->depth
= stack
->depth
;
199 /* Grow the state array to the new depth so the state accessors work
200 * in the callbacks */
202 call_dom_stack_callbacks(stack
, state
, DOM_STACK_PUSH
);
208 pop_dom_node(struct dom_stack
*stack
)
210 struct dom_stack_state
*state
;
215 if (dom_stack_is_empty(stack
))
218 state
= get_dom_stack_top(stack
);
219 if (state
->immutable
)
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
);
227 assert(stack
->depth
>= 0);
229 for (i
= 0; i
< stack
->contexts_size
; i
++) {
230 struct dom_stack_context
*context
= stack
->contexts
[i
];
232 if (context
->info
->object_size
) {
233 void *state_data
= get_dom_stack_state_data(context
, state
);
235 memset(state_data
, 0, context
->info
->object_size
);
239 memset(state
, 0, sizeof(*state
));
243 pop_dom_nodes(struct dom_stack
*stack
, enum dom_node_type type
,
244 struct dom_string
*string
)
246 struct dom_stack_state
*state
;
250 if (dom_stack_is_empty(stack
)) return;
252 state
= search_dom_stack(stack
, type
, string
);
254 pop_dom_state(stack
, state
);
258 pop_dom_state(struct dom_stack
*stack
, struct dom_stack_state
*target
)
260 struct dom_stack_state
*state
;
267 if (dom_stack_is_empty(stack
)) return;
269 foreachback_dom_stack_state (stack
, state
, pos
) {
270 /* Don't pop past states marked immutable. */
271 if (state
->immutable
)
274 /* Pop until the target state is reached. */
281 struct dom_stack_state
*
282 search_dom_stack(struct dom_stack
*stack
, enum dom_node_type type
,
283 struct dom_string
*string
)
285 struct dom_stack_state
*state
;
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
;
292 if (parent
->type
== type
293 && !dom_string_casecmp(&parent
->string
, string
))
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
305 struct dom_node_list
*list
;
306 /* The index (in the list above) which are currently being handled. */
310 static struct dom_stack_context_info dom_stack_walk_context_info
= {
311 /* Object size: */ sizeof(struct dom_stack_walk_state
),
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
,
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
,
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. */
349 walk_dom_nodes(struct dom_stack
*stack
, struct dom_node
*root
)
351 struct dom_stack_context
*context
;
353 assert(root
&& stack
);
355 context
= add_dom_stack_context(stack
, NULL
, &dom_stack_walk_context_info
);
359 if (push_dom_node(stack
, root
) != DOM_CODE_OK
)
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
;
368 switch (node
->type
) {
369 case DOM_NODE_DOCUMENT
:
370 if (!list
) list
= node
->data
.document
.children
;
373 case DOM_NODE_ELEMENT
:
374 if (!list
) list
= node
->data
.element
.map
;
376 if (list
== node
->data
.element
.children
) break;
377 if (is_dom_node_list_member(list
, wstate
->index
)
378 && list
== node
->data
.element
.map
)
381 list
= node
->data
.element
.children
;
384 case DOM_NODE_PROCESSING_INSTRUCTION
:
385 if (!list
) list
= node
->data
.proc_instruction
.map
;
388 case DOM_NODE_DOCUMENT_TYPE
:
389 if (!list
) list
= node
->data
.document_type
.entities
;
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
)
396 list
= node
->data
.document_type
.notations
;
399 case DOM_NODE_ATTRIBUTE
:
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
:
411 /* Reset list state if it is a new list */
412 if (list
!= wstate
->list
) {
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
++];
421 if (push_dom_node(stack
, child
) == DOM_CODE_OK
)
428 done_dom_stack_context(stack
, context
);
432 /* DOM Stack Tracing: */
434 #ifdef DOM_STACK_TRACE
436 #include "util/string.h"
438 /* Compress a string to a single line with newlines etc. replaced with "\\n"
440 static inline unsigned char *
441 compress_string(unsigned char *string
, unsigned int length
)
443 struct string buffer
;
444 unsigned char escape
[2] = "\\";
446 if (!init_string(&buffer
)) return NULL
;
448 for (; length
> 0; string
++, length
--) {
449 unsigned char *bytes
= string
;
451 if (*string
== '\n' || *string
== '\r' || *string
== '\t') {
453 escape
[1] = *string
== '\n' ? 'n'
454 : (*string
== '\r' ? 'r' : 't');
457 add_bytes_to_string(&buffer
, bytes
, bytes
== escape
? 2 : 1);
460 return buffer
.source
;
463 /* Set @string to the value of the given @node, however, with strings
464 * compressed and entity references 'expanded'. */
466 set_enhanced_dom_node_value(struct dom_string
*string
, struct dom_node
*node
)
468 struct dom_string
*value
;
472 memset(string
, 0, sizeof(*string
));
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
);
481 value
= get_dom_node_value(node
);
483 set_dom_string(string
, NULL
, 0);
487 string
->string
= compress_string(value
->string
, value
->length
);
490 string
->length
= string
->string
? strlen(string
->string
) : 0;
493 static unsigned char indent_string
[] =
496 #define get_indent_offset(stack) \
497 ((stack)->depth < sizeof(indent_string)/2 ? (stack)->depth * 2 : sizeof(indent_string))
500 dom_stack_trace_tree(struct dom_stack
*stack
, struct dom_node
*node
, void *data
)
502 struct dom_string
*value
= &node
->string
;
503 struct dom_string
*name
= get_dom_node_name(node
);
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
);
515 dom_stack_trace_id_leaf(struct dom_stack
*stack
, struct dom_node
*node
, void *data
)
517 struct dom_string value
;
518 struct dom_string
*name
;
519 struct dom_string
*id
;
523 name
= get_dom_node_name(node
);
524 id
= get_dom_node_type_name(node
->type
);
525 set_enhanced_dom_node_value(&value
, node
);
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
);
533 done_dom_string(&value
);
539 dom_stack_trace_leaf(struct dom_stack
*stack
, struct dom_node
*node
, void *data
)
541 struct dom_string
*name
;
542 struct dom_string value
;
546 name
= get_dom_node_name(node
);
547 set_enhanced_dom_node_value(&value
, node
);
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
);
555 done_dom_string(&value
);
561 dom_stack_trace_branch(struct dom_stack
*stack
, struct dom_node
*node
, void *data
)
563 struct dom_string
*name
;
564 struct dom_string
*id
;
568 name
= get_dom_node_name(node
);
569 id
= get_dom_node_type_name(node
->type
);
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
);
579 struct dom_stack_context_info dom_stack_trace_context_info
= {
580 /* Object size: */ 0,
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
,
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
,
615 #endif /* DOM_STACK_TRACE */