path: root/content/handlers/html/box/manager.c

#include <stdlib.h>

#include "desktop/gui_internal.h"
#include "html/box/manager.h"
#include "netsurf/misc.h"
#include "utils/corestrings.h"
#include "utils/log.h"

/* Flags for DOM Element nodes */

#define BM_DOM_FLAG_NODE_INSERTED		0x00000001
/* This node has been inserted into the DOM tree */
#define BM_DOM_FLAG_PREVIOUS_NODE_REMOVED	0x00000002
/* The node preceding this one was removed from the DOM tree */
#define BM_DOM_FLAG_ID_ATTRIBUTE_CHANGED	0x00000004
/* This node's @id has changed */
#define BM_DOM_FLAG_CLASS_ATTRIBUTE_CHANGED	0x00000008
/* This node's @class has changed */
#define BM_DOM_FLAG_ATTRIBUTE_CHANGED		0x00000010
/* A (non-@class/@id) attribute on this node has changed */

/* If any of the above flags are set on a node: recompute style information
 * for it, its descendants, its subsequent siblings, and their descendants.
 * If styles have changed, rebuild box subtree */

#define BM_DOM_FLAG_TEXT_CONTENTS_CHANGED	0x00000100
/* Text contents of this node have changed: rebuild box subtree */


struct box_manager
{
	dom_document *doc;
	dom_event_listener *listener;

	/* Whether we have been told that stylesheets are available */
	// XXX: need an API for stylesheet change notifications
	// On receipt, mark entire tree invalid (synthesise a subtree modified event? -- not fired at DOM, for obvious reasons, but could be thrown at our event handler)
	bool have_styles;
	/* Whether there is an outstanding callback pending */
	bool callback_pending;

	dom_node **pending_queue;
	size_t pending_queue_idx;
	size_t pending_queue_slots;
};

typedef struct
{
	box_manager *mgr;

	/* Flag state for our ancestors (and their preceding siblings) */
	uintptr_t flags_ancestor;
	/* Flag state for our preceding siblings */
	uintptr_t flags_sibling;

} rebuild_ctx;

static dom_exception
_foreach_child(dom_node *parent,
		dom_exception (*cb)(dom_node *, void *), void *pw)
{
	dom_node *cur = NULL, *sibling = NULL;
	dom_exception exc;

	exc = dom_node_get_first_child(parent, &cur);
	if (exc != DOM_NO_ERR || cur == NULL) {
		return exc;
	}

	do {
		dom_node_type node_type;

		exc = dom_node_get_node_type(cur, &node_type);
		if (exc == DOM_NO_ERR && node_type == DOM_ELEMENT_NODE) {
			exc = cb(cur, pw);
		}
		if (exc == DOM_NO_ERR) {
			exc = dom_node_get_next_sibling(cur, &sibling);
			dom_node_unref(cur);
			cur = NULL;

			if (exc == DOM_NO_ERR && sibling != NULL) {
				cur = sibling;
				sibling = NULL;
			}
		}
	} while (exc == DOM_NO_ERR && cur != NULL);

	dom_node_unref(cur);

	return exc;
}

static dom_exception
_rebuild_boxes_for_element(dom_node *node, void *pw)
{
	rebuild_ctx *ctx = pw;
	const uintptr_t flags_ancestor = ctx->flags_ancestor;
	const uintptr_t flags_sibling = ctx->flags_sibling;
	uintptr_t flags_self = 0;
	dom_exception exc;

	/* Invalidate node data, extracting current value */
	exc = dom_node_set_user_data(node,
			corestring_dom___ns_key_bm_node_data,
			NULL, NULL, (void **) &flags_self);
	if (exc != DOM_NO_ERR) {
		return exc;
	}

	/* Prepare to process children */
	ctx->flags_ancestor |= (ctx->flags_sibling | flags_self);
	ctx->flags_sibling = 0;

	/* Process children */
	exc = _foreach_child(node, _rebuild_boxes_for_element, ctx);

	/* Restore values */
	ctx->flags_ancestor = flags_ancestor;
	ctx->flags_sibling = flags_sibling;

	{
		dom_string *name = NULL;

		exc = dom_node_get_node_name(node, &name);
		if (exc == DOM_NO_ERR && name != NULL) {
			NSLOG(layout, DBG, "bm: <%.*s>:"
					" ancestor: %08"PRIxPTR
					" sibling: %08"PRIxPTR
					" self: %08"PRIxPTR,
					(int) dom_string_byte_length(name),
					dom_string_data(name),
					flags_ancestor,
					flags_sibling,
					flags_self);
			dom_string_unref(name);
		}
	}

	/* Consider whether anything has changed that might affect this node's
	 * box tree segment (noting that we have already done so for the box
	 * tree segments attached to our descendants) */
	if (flags_ancestor != 0 || flags_sibling != 0 || flags_self != 0) { // XXX: or if there's no style information for this node yet
		/* DOM structure has changed: (re)select styles for node */

		// XXX: if styles have changed, ensure our box tree segment reflects reality
	}

	// XXX: regardless, ensure that box tree is in normal form (only need to consider relationship between our box(es) and those of our child elements)

	// XXX: then, if the box tree changed (either because our styles changed, or we needed to normalize things):
	//    a. find the immediate containing block(s) for our segment
	//       (there may be more than one if posititioned/out-of-flow elements are in play)
	//    b. emit (a) "box tree modified" event(s) referencing the containing block(s)
	//
	// Note that our children will also have done this, so there will be
	// multiple events if done here and emitted directly; if we want to
	// coalesce things, then we'll probably want to fire the events to an
	// internal queue that we then flush out after we've finished
	// processing the top-level external (e.g. DOM) event. Also, as we're
	// (re)building the box tree on the way back up the DOM, it will be
	// the case that we do not actually have any containing blocks yet
	// (because they'll be constructed when we unwind back up to our
	// parent). Given this, some further thought needs to happen here.
	//
	// Layout calculators will receive the "box tree modified" events and deal with them

	/* Update flags for next sibling (if any) */
	ctx->flags_sibling |= flags_self;

	return exc;
}

static void
box_manager_rebuild_boxes_for_children(box_manager *mgr, dom_node *parent)
{
	rebuild_ctx ctx;

	/* Prepare context */
	ctx.mgr = mgr;
	ctx.flags_ancestor = 0;
	ctx.flags_sibling = 0;

	// XXX: this recurses. iteration better?
	(void) _foreach_child(parent, _rebuild_boxes_for_element, &ctx);
}

static void
box_manager_process_events(void *pw)
{
	box_manager *mgr = pw;
	dom_exception exc;
	size_t i, j;
	size_t orphaned_nodes = 0, duplicate_nodes = 0;
	size_t descendant_nodes = 0, processed_events = 0;

	mgr->callback_pending = false;

	/* 1. Eliminate nodes which are no longer in our document, or in a
	 * detached tree (we expect to have received a corresponding event for
	 * their parent) */
	for (i = mgr->pending_queue_idx; i > 0; i--) {
		bool contains = false;

		if (mgr->pending_queue[i-1] == NULL) {
			continue;
		}

		exc = dom_node_contains(mgr->doc, mgr->pending_queue[i-1],
				&contains);
		if (exc == DOM_NO_ERR && contains == false) {
			dom_node_unref(mgr->pending_queue[i-1]);
			mgr->pending_queue[i-1] = NULL;
			orphaned_nodes++;
			continue;
		}

		/* 2. Eliminate duplicate nodes from the list */
		for (j = mgr->pending_queue_idx; j > i + 1; j--) {
			if (mgr->pending_queue[j-1] == NULL) {
				continue;
			}

			if (mgr->pending_queue[i-1] ==
					mgr->pending_queue[j-1]) {
				dom_node_unref(mgr->pending_queue[i-1]);
				mgr->pending_queue[i-1] = NULL;
				duplicate_nodes++;
				break;
			}
		}
	}

	/* 3. Eliminate nodes which are descendants of other nodes in the
	 * list */
	for (i = mgr->pending_queue_idx; i > 0; i--) {
		if (mgr->pending_queue[i-1] == NULL) {
			continue;
		}

		for (j = mgr->pending_queue_idx; j > 0; j--) {
			bool contains = false;

			if (j == i || mgr->pending_queue[j-1] == NULL) {
				continue;
			}

			exc = dom_node_contains(mgr->pending_queue[j-1],
					mgr->pending_queue[i-1], &contains);
			if (exc == DOM_NO_ERR && contains == true) {
				dom_node_unref(mgr->pending_queue[i-1]);
				mgr->pending_queue[i-1] = NULL;
				descendant_nodes++;
				break;
			}
		}
	}

	/* 4. For every remaining node: (re)build the structural box tree
	 * segment rooted at each of node's children. We do this in receive
	 * order, though it should make no difference. */
	for (i = 0; i < mgr->pending_queue_idx; i++) {
		if (mgr->pending_queue[i] == NULL) {
			continue;
		}
		box_manager_rebuild_boxes_for_children(mgr,
				mgr->pending_queue[i]);

		/* We're done with this node */
		dom_node_unref(mgr->pending_queue[i]);
		mgr->pending_queue[i] = NULL;

		processed_events++;
	}

	NSLOG(layout, DBG, "bm: received %zu raw events (%zu orphaned, "
			"%zu duplicate, %zu descendant) => "
			"processed %zu events",
			mgr->pending_queue_idx, orphaned_nodes,
			duplicate_nodes, descendant_nodes,
			processed_events);

	/* 5. All events processed. Clean up. */
	mgr->pending_queue_idx = 0;
}

static void
box_manager_capture_event_target(box_manager *mgr, dom_event_target *target)
{
	if (mgr->pending_queue_idx == mgr->pending_queue_slots) {
		size_t slots;
		dom_node **tmp;
		if (mgr->pending_queue == NULL) {
			slots = 1024;
			tmp = malloc(sizeof(*tmp) * slots);
		} else {
			slots = mgr->pending_queue_slots * 2;
			tmp = realloc(mgr->pending_queue,
					sizeof(*tmp) * slots);
		}
		if (tmp == NULL) {
			/* ENOMEM, but no way to deal with it? */
			return;
		}

		mgr->pending_queue = tmp;
		mgr->pending_queue_slots = slots;
	}

	mgr->pending_queue[mgr->pending_queue_idx++] = (dom_node *) target;
}

static dom_node *
_find_parent_element_or_document(dom_node *target)
{
	dom_node *parent = NULL;
	dom_exception exc = DOM_NO_ERR;

	/* Take ref on target (we'll release it in the loop) */
	dom_node_ref(target);

	do {
		exc = dom_node_get_parent_node(target, &parent);
		dom_node_unref(target);
		target = NULL;

		if (exc == DOM_NO_ERR && parent != NULL) {
			dom_node_type node_type;

			target = parent;
			parent = NULL;

			exc = dom_node_get_node_type(target, &node_type);
			if (exc == DOM_NO_ERR &&
					(node_type == DOM_ELEMENT_NODE ||
					 node_type == DOM_DOCUMENT_NODE)) {
				break;
			}
		}
	} while (exc == DOM_NO_ERR && target != NULL);

	if (exc != DOM_NO_ERR) {
		dom_node_unref(target);
		target = NULL;
	}

	return target;
}

static dom_exception
_next_element_sibling(dom_node *cur,
		dom_exception (*cb)(dom_node *, void *), void *pw)
{
	dom_node *sibling = NULL;
	dom_exception exc;

	/* Take ref on cur (we'll release it in the loop) */
	dom_node_ref(cur);

	do {
		exc = dom_node_get_next_sibling(cur, &sibling);
		dom_node_unref(cur);
		cur = NULL;

		if (exc == DOM_NO_ERR && sibling != NULL) {
			dom_node_type sibling_type;

			cur = sibling;
			sibling = NULL;

			exc = dom_node_get_node_type(cur, &sibling_type);
			if (exc == DOM_NO_ERR &&
					sibling_type == DOM_ELEMENT_NODE) {
				exc = cb(cur, pw);
				break;
			}
		}
	} while (exc == DOM_NO_ERR && cur != NULL);

	dom_node_unref(cur);

	return exc;
}

static dom_exception
_set_node_flags(dom_node *node, void *pw)
{
	uintptr_t flags_to_set = (uintptr_t) pw;
	uintptr_t node_flags = 0;
	dom_exception exc;

	exc = dom_node_get_user_data(node,
			corestring_dom___ns_key_bm_node_data,
			(void **) &node_flags);
	if (exc == DOM_NO_ERR) {
		node_flags |= flags_to_set;
		exc = dom_node_set_user_data(node,
				corestring_dom___ns_key_bm_node_data,
				(void *) node_flags,
				NULL,
				(void **) &node_flags);
	}
	return exc;
}

static uintptr_t
_attr_name_to_flag(dom_string *attr_name)
{
	uintptr_t flag = 0;

	if (dom_string_isequal(attr_name, corestring_dom_class)) {
		flag = BM_DOM_FLAG_CLASS_ATTRIBUTE_CHANGED;
	} else if (dom_string_isequal(attr_name, corestring_dom_id)) {
		flag = BM_DOM_FLAG_ID_ATTRIBUTE_CHANGED;
	} else {
		flag = BM_DOM_FLAG_ATTRIBUTE_CHANGED;
	}

	return flag;
}

static void
box_manager_handle_dom_event(dom_event *evt, void *pw)
{
	box_manager *mgr = pw;
	dom_node *parent = NULL;
	dom_event_target *target = NULL;
	dom_node_type target_type;
	dom_string *evt_type = NULL, *computed_type = NULL;
	dom_exception exc;

	/* 0. During DOM construction, ignore events until we have all
	 * known stylesheets */
	if (mgr->have_styles == false) {
		return;
	}

	/* 1. Ignore unknown events */
	exc = dom_event_get_type(evt, &evt_type);
	if (exc == DOM_NO_ERR) {
		/* Select corestring from event type */
		if (dom_string_isequal(evt_type,
				corestring_dom_DOMNodeInserted)) {
			computed_type = corestring_dom_DOMNodeInserted;
		} else if (dom_string_isequal(evt_type,
				corestring_dom_DOMNodeRemoved)) {
			computed_type = corestring_dom_DOMNodeRemoved;
		} else if (dom_string_isequal(evt_type,
				corestring_dom_DOMAttrModified)) {
			computed_type = corestring_dom_DOMAttrModified;
		} else if (dom_string_isequal(evt_type,
				corestring_dom_DOMCharacterDataModified)) {
			computed_type = corestring_dom_DOMCharacterDataModified;
		}
	}
	dom_string_unref(evt_type);
	if (exc != DOM_NO_ERR || computed_type == NULL) {
		return;
	}

	/* 2. Ignore events without targets */
	exc = dom_event_get_target(evt, &target);
	if (exc != DOM_NO_ERR || target == NULL) {
	       return;
	}

	/* 3. The event target must be an Element or Text node */
	exc = dom_node_get_node_type(target, &target_type);
	if (exc != DOM_NO_ERR || (target_type != DOM_ELEMENT_NODE &&
			target_type != DOM_TEXT_NODE)) {
		dom_node_unref(target);
		return;
	}

	/* 4. Find the parent node whose subtree is now invalid */
	parent = _find_parent_element_or_document((dom_node *) target);
	if (parent == NULL) {
		dom_node_unref(target);
		return;
	}

	/* 5. update node flags */
	if (target_type == DOM_ELEMENT_NODE) {
		/* Mark nodes as structurally changed */
		if (computed_type == corestring_dom_DOMNodeRemoved) {
			/* Node removed: subsequent sibling element */
			exc = _next_element_sibling((dom_node *) target,
				_set_node_flags,
				(void *) BM_DOM_FLAG_PREVIOUS_NODE_REMOVED);
		} else if (computed_type == corestring_dom_DOMNodeInserted) {
			/* Node inserted: target itself */
			exc = _set_node_flags((dom_node *) target,
				(void *) BM_DOM_FLAG_NODE_INSERTED);
		} else {
			/* Attribute modified: target itself */
			dom_string *attr_name = NULL;

			exc = dom_mutation_event_get_attr_name(evt,
					&attr_name);
			if (exc == DOM_NO_ERR && attr_name != NULL) {
				exc = _set_node_flags((dom_node *) target,
						(void *) _attr_name_to_flag(
							attr_name));

				dom_string_unref(attr_name);
			}
		}
	} else if (target_type == DOM_TEXT_NODE) {
		/* Mark parent as text content changed */
		exc = _set_node_flags((dom_node *) parent,
				(void *) BM_DOM_FLAG_TEXT_CONTENTS_CHANGED);
	}
	dom_node_unref(target);
	if (exc != DOM_NO_ERR) {
		dom_node_unref(parent);
		return;
	}

	/* 6. Capture parent node (ensuring we keep a ref) into list of
	 * pending events. */
	box_manager_capture_event_target(mgr, (dom_event_target *) parent);

	/* 7. Schedule a callback to process the list (if no callback already
	 * scheduled) */
	if (mgr->callback_pending == false) {
		// XXX: 20ms ~= 50Hz -- enough?
		guit->misc->schedule(20, box_manager_process_events, mgr);
		mgr->callback_pending = true;
	}
}

nserror
box_manager_create(dom_document *doc, box_manager **manager)
{
	box_manager *mgr;
	dom_exception exc;

	mgr = malloc(sizeof(*mgr));
	if (mgr == NULL) {
		return NSERROR_NOMEM;
	}

	/* Register event listener.
	 *
	 * We listen for AttrModified, CharacterDataModified, NodeInserted,
	 * and NodeRemoved events.
	 *
	 * In all cases (where the event target is an Element), the affected
	 * subtree is rooted at the Element's *parent* Element.
	 *
	 * Where the event target is a Text node, the affected Element is the
	 * closest Element ancestor of the Text node.
	 */
	exc = dom_event_listener_create(box_manager_handle_dom_event, mgr,
			&mgr->listener);
	if (exc != DOM_NO_ERR) {
		free(mgr);
		return NSERROR_DOM;
	}

	exc = dom_event_target_add_event_listener(doc,
			corestring_dom_DOMNodeInserted,
			mgr->listener,
			true);
	if (exc != DOM_NO_ERR) {
		dom_event_listener_unref(mgr->listener);
		free(mgr);
		return NSERROR_DOM;
	}

	exc = dom_event_target_add_event_listener(doc,
			corestring_dom_DOMNodeRemoved,
			mgr->listener,
			true);
	if (exc != DOM_NO_ERR) {
		/* Remove all instances of this listener */
		dom_event_target_remove_event_listener(doc, NULL,
				mgr->listener, true);
		dom_event_listener_unref(mgr->listener);
		free(mgr);
		return NSERROR_DOM;
	}

	exc = dom_event_target_add_event_listener(doc,
			corestring_dom_DOMAttrModified,
			mgr->listener,
			true);
	if (exc != DOM_NO_ERR) {
		/* Remove all instances of this listener */
		dom_event_target_remove_event_listener(doc, NULL,
				mgr->listener, true);
		dom_event_listener_unref(mgr->listener);
		free(mgr);
		return NSERROR_DOM;
	}

	exc = dom_event_target_add_event_listener(doc,
			corestring_dom_DOMCharacterDataModified,
			mgr->listener,
			true);
	if (exc != DOM_NO_ERR) {
		/* Remove all instances of this listener */
		dom_event_target_remove_event_listener(doc, NULL,
				mgr->listener, true);
		dom_event_listener_unref(mgr->listener);
		free(mgr);
		return NSERROR_DOM;
	}

	mgr->doc = (dom_document *) dom_node_ref(doc);
	mgr->have_styles = false;
	mgr->callback_pending = false;
	mgr->pending_queue = NULL;
	mgr->pending_queue_idx = mgr->pending_queue_slots = 0;

	*manager = mgr;

	return NSERROR_OK;
}

nserror
box_manager_destroy(box_manager *manager)
{
	if (manager->callback_pending) {
		guit->misc->schedule(-1, box_manager_process_events, manager);
	}
	while (manager->pending_queue_idx > 0) {
		manager->pending_queue_idx--;
		dom_node_unref(
			manager->pending_queue[manager->pending_queue_idx]);
	}
	free(manager->pending_queue);
	(void) dom_event_target_remove_event_listener(manager->doc,
			NULL,
			manager->listener,
			true);
	dom_event_listener_unref(manager->listener);
	dom_node_unref(manager->doc);
	free(manager);

	return NSERROR_OK;
}