src/dom/stack.h

   1 /** The DOM stack interface.
   2  *
   3  * @file dom/stack.h
   4  *
   5  * The DOM stack interface is used by the parser when building a DOM
   6  * tree and by the various DOM tree traversers. It allows for several
   7  * stack contexts to be registered, each defining their own type
   8  * specific node handlers or callbacks (#dom_stack_callback_T) which
   9  * will be called upon a node being pushed onto or popped from the
  10  * stack. As an example a example, by defining DOM_STACK_TRACE it is be
  11  * possible to add a DOM stack tracer (using #add_dom_stack_tracer) to
  12  * debug all push and pop operations.
  13  *
  14  * The stack interface provides a method for automatically having
  15  * objects allocated when a new node is pushed onto the stack. This
  16  * object can then be used for storing private state information
  17  * belonging to the individual contexts. This is done by setting the
  18  * #dom_stack_context_info.object_size member to a non-zero value,
  19  * usually using sizeof().
  20  *
  21  * States on the stack can be marked immutable meaning that they will
  22  * be "locked" down so that any operations to pop them will fail. This
  23  * can be used when parsing a "subdocument", e.g. output from
  24  * ECMAScripts "document.write" function, where badly formatted SGML
  25  * should not be allowed to change the root document.
  26  *
  27  * In some situations, it may be desired to avoid building a complete
  28  * DOM tree in memory when only one document traversal is required, for
  29  * example when highlighting SGML code. This can be done by passing the
  30  * #DOM_STACK_FLAG_FREE_NODES flag to #init_dom_stack. Nodes that are
  31  * popped from the stack will immediately be deallocated. A pop node
  32  * callback can also request that a node is deallocated and removed from
  33  * the DOM tree by returning the #DOM_CODE_FREE_NODE return code. An
  34  * example of this can be seen in the DOM configuration module where
  35  * comment nodes may be pruned from the tree.
  36  */
  37 /* TODO: Write about:
  38  * - How to access stack states and context state objects.
  39  * - Using search_dom_stack() and walk_dom_nodes().
  40  */
  41
  42 #ifndef EL_DOM_STACK_H
  43 #define EL_DOM_STACK_H
  44
  45 #include "dom/code.h"
  46 #include "dom/node.h"
  47 #include "util/error.h"
  48 #include "util/hash.h"
  49
  50 struct dom_stack;
  51
  52 /** DOM stack callback
  53  *
  54  * Used by contexts, for 'hooking' into the node traversing. */
  55 typedef enum dom_code
  56         (*dom_stack_callback_T)(struct dom_stack *, struct dom_node *, void *);
  57
  58 #define DOM_STACK_MAX_DEPTH     4096
  59
  60 /** DOM stack state
  61  *
  62  * This state records what node and where it is placed. */
  63 struct dom_stack_state {
  64         /** The node assiciated with the state */
  65         struct dom_node *node;
  66         /**
  67          * The depth of the state in the stack. This is amongst other things
  68          * used to get the state object data. */
  69         unsigned int depth;
  70         /** Whether this stack state can be popped with #pop_dom_node,
  71          * #pop_dom_nodes, or #pop_dom_state. */
  72         unsigned int immutable:1;
  73 };
  74
  75 /** DOM stack context info
  76  *
  77  * To add a DOM stack context define this struct either statically or on the
  78  * stack. */
  79 struct dom_stack_context_info {
  80         /**
  81          * The number of bytes to allocate on the stack for each state's
  82          * data member.  Zero means no state data should be allocated.
  83          * */
  84         size_t object_size;
  85
  86         /** Callbacks to be called when pushing nodes. */
  87         dom_stack_callback_T push[DOM_NODES];
  88         /** Callbacks to be called when popping nodes. */
  89         dom_stack_callback_T pop[DOM_NODES];
  90 };
  91
  92 /** DOM stack context
  93  *
  94  * This holds 'runtime' data for the stack context. */
  95 struct dom_stack_context {
  96         /** Data specific to the context. */
  97         void *data;
  98
  99         /**
 100          * This is one big array of context specific objects. For the SGML
 101          * parser this holds DTD-oriented info about the node (recorded in
 102          * struct #sgml_node_info). E.g.  whether an element node is optional.
 103          */
 104         unsigned char *state_objects;
 105
 106         /** Info about node callbacks and such. */
 107         struct dom_stack_context_info *info;
 108 };
 109
 110 /** Flags for controlling the DOM stack */
 111 enum dom_stack_flag {
 112         /** No flag needed. */
 113         DOM_STACK_FLAG_NONE = 0,
 114
 115         /** Free nodes when popping by calling #done_dom_node. */
 116         DOM_STACK_FLAG_FREE_NODES = 1,
 117 };
 118
 119 /** The DOM stack
 120  *
 121  * The DOM stack is a convenient way to traverse DOM trees. Also it
 122  * maintains needed state info and is therefore also a holder of the current
 123  * context since the stack is used to when the DOM tree is manipulated. */
 124 struct dom_stack {
 125         /** The states currently on the stack. */
 126         struct dom_stack_state *states;
 127         /** The depth of the stack. */
 128         size_t depth;
 129
 130         /** Flags given to ref:[init_dom_stack]. */
 131         enum dom_stack_flag flags;
 132
 133         /** Contexts for the pushed and popped nodes. */
 134         struct dom_stack_context **contexts;
 135         /** The number of active contexts. */
 136         size_t contexts_size;
 137
 138         /**
 139          * The current context. Only meaningful within
 140          * #dom_stack_callback_T functions. */
 141         struct dom_stack_context *current;
 142 };
 143
 144 /** Check whether stack is empty or not
 145  *
 146  * @param stack         The stack to check.
 147  *
 148  * @returns             Non-zero if stack is empty. */
 149 #define dom_stack_is_empty(stack) \
 150         (!(stack)->states || (stack)->depth == 0)
 151
 152 /** Access state by offset from top
 153  *
 154  * @param stack         The stack to fetch the state from.
 155  * @param top_offset    The offset from the stack top, zero is the top.
 156  *
 157  * @returns             The requested state. */
 158 static inline struct dom_stack_state *
 159 get_dom_stack_state(struct dom_stack *stack, int top_offset)
 160 {
 161         assertm(stack->depth - 1 - top_offset >= 0,
 162                 "Attempting to access invalid state");
 163         return &stack->states[stack->depth - 1 - top_offset];
 164 }
 165
 166 /** Access the stack top
 167  *
 168  * @param stack         The stack to get the top state from.
 169  *
 170  * @returns             The top state. */
 171 #define get_dom_stack_top(stack) \
 172         get_dom_stack_state(stack, 0)
 173
 174 /** Access context specific state data
 175  *
 176  * Similar to ref:[get_dom_stack_state], this will fetch the data
 177  * associated with the state for the given context.
 178  *
 179  * @param context       The context to get data from.
 180  * @param state         The stack state to get data from.
 181  *
 182  * @returns             The state data or NULL if
 183  *                      #dom_stack_context_info.object_size was zero. */
 184 static inline void *
 185 get_dom_stack_state_data(struct dom_stack_context *context,
 186                          struct dom_stack_state *state)
 187 {
 188         size_t object_size = context->info->object_size;
 189
 190         if (!object_size) return NULL;
 191
 192         assertm(context->state_objects);
 193
 194         return (void *) &context->state_objects[state->depth * object_size];
 195 }
 196
 197 /*#define DOM_STACK_TRACE*/
 198
 199 /** Get debug info from the DOM stack
 200  *
 201  * Define `DOM_STACK_TRACE` to have debug info about the nodes added printed to
 202  * the log. It will define add_dom_stack_tracer() to not be a no-op.
 203  *
 204  * Run as:
 205  *
 206  *      ELINKS_LOG=/tmp/dom-dump.txt ./elinks -no-connect URL
 207  *
 208  * to have the debug dumped into a file. */
 209 #ifdef DOM_STACK_TRACE
 210 #define add_dom_stack_tracer(stack, name) \
 211         add_dom_stack_context(stack, name, &dom_stack_trace_context_info)
 212 extern struct dom_stack_context_info dom_stack_trace_context_info;
 213 #else
 214 #define add_dom_stack_tracer(stack, name) /* Nada */
 215 #endif
 216
 217 /** The state iterators
 218  *
 219  * To safely iterate through the stack state iterators. */
 220
 221 /** Iterate the stack from bottom to top. */
 222 #define foreach_dom_stack_state(stack, state, pos)                      \
 223         for ((pos) = 0; (pos) < (stack)->depth; (pos)++)                \
 224                 if (((state) = &(stack)->states[(pos)]))
 225
 226 /** Iterate the stack from top to bottom. */
 227 #define foreachback_dom_stack_state(stack, state, pos)                  \
 228         for ((pos) = (stack)->depth - 1; (pos) >= 0; (pos)--)           \
 229                 if (((state) = &(stack)->states[(pos)]))
 230
 231
 232 /* Life cycle functions. */
 233
 234 /** Initialise a DOM stack
 235  *
 236  * @param stack         Pointer to a (preallocated) stack.
 237  * @param flags         Any flags needed for controlling the behaviour of the stack.
 238  */
 239 void init_dom_stack(struct dom_stack *stack, enum dom_stack_flag flags);
 240
 241 /** Release a DOM stack
 242  *
 243  * Free all resources collected by the stack.
 244  *
 245  * @param stack         The stack to release. */
 246 void done_dom_stack(struct dom_stack *stack);
 247
 248 /** Add a context to the stack
 249  *
 250  * This is needed if either you want to have the stack allocated objects for
 251  * created states and/or if you want to install callbacks for pushing or
 252  * popping.
 253  *
 254  * @param stack         The stack where the context should be created.
 255  * @param data          Private data to be stored in ref:[dom_stack_context.data].
 256  * @param context_info  Information about state objects and node callbacks.
 257  *
 258  * @returns             A pointer to the newly created context or NULL. */
 259 struct dom_stack_context *
 260 add_dom_stack_context(struct dom_stack *stack, void *data,
 261                       struct dom_stack_context_info *context_info);
 262
 263 /** Unregister a stack context
 264  *
 265  * This should be done especially for temporary stack contexts (without any
 266  * callbacks) so that they do not increasing the memory usage. */
 267 void done_dom_stack_context(struct dom_stack *stack, struct dom_stack_context *context);
 268
 269 /** Push a node onto the stack
 270  *
 271  * Makes the pushed node the new top of the stack.
 272  *
 273  * @param stack         The stack to push onto.
 274  * @param node          The node to push onto the stack.
 275  *
 276  * @returns             If an error occurs the node is released with
 277  *                      #done_dom_node and NULL is returned. Else the pushed
 278  *                      node is returned. */
 279 enum dom_code push_dom_node(struct dom_stack *stack, struct dom_node *node);
 280
 281 /** Pop the top stack state
 282  *
 283  * @param stack         The stack to pop from. */
 284 void pop_dom_node(struct dom_stack *stack);
 285
 286 /** Conditionally pop the stack states
 287  *
 288  * Searches the stack (using ref:[search_dom_stack]) for a specific node and
 289  * pops all states until that particular state is met.
 290  *
 291  * @note                The popping is stopped if an immutable state is
 292  *                      encountered. */
 293 void pop_dom_nodes(struct dom_stack *stack, enum dom_node_type type,
 294                    struct dom_string *string);
 295
 296 /** Pop all states until target state
 297  *
 298  * Pop all stack states until a specific state is reached. The target state
 299  * is also popped.
 300  *
 301  * @param stack         The stack to pop from.
 302  * @param target        The state to pop until and including. */
 303 void pop_dom_state(struct dom_stack *stack, struct dom_stack_state *target);
 304
 305 /** Search the stack states
 306  *
 307  * The string comparison is done against the ref:[dom_node.string] member of
 308  * the of the state nodes.
 309  *
 310  * @param stack         The stack to search in.
 311  * @param type          The type of node to match against.
 312  * @param string        The string to match against.
 313  *
 314  * @returns             A state that matched the type and string or NULL. */
 315 struct dom_stack_state *
 316 search_dom_stack(struct dom_stack *stack, enum dom_node_type type,
 317                  struct dom_string *string);
 318
 319 /** Walk all nodes reachable from a given node
 320  *
 321  * Visits each node in the DOM tree rooted at a given node, pre-order style.
 322  *
 323  * @param stack         The stack to use for walking the nodes.
 324  * @param root          The root node to start from.
 325  *
 326  * It is assummed that the given stack has been initialised with
 327  * #init_dom_stack and that the caller already added one or more context
 328  * to the stack. */
 329 void walk_dom_nodes(struct dom_stack *stack, struct dom_node *root);
 330
 331 #endif