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_STRUCTURE_CHANGED		0x00000001
/* Document structure has changed at this 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	0x00000002
/* 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;
};

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

	//XXX: implement
	//
	// 1. (re)build the structural box tree segment rooted at each of parent's children.
	// 2. For each modified box tree segment:
	//    a. find the immediate containing block(s) for the 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)
	//
	// The box tree must always be in normal form so it may be necessary to insert (or remove?) elements between the segment root and its parent box
	// Layout calculators will receive the "box tree modified" events and deal with them
}

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
_foreach_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;

			exc = dom_node_get_node_type(sibling, &sibling_type);
			if (exc == DOM_NO_ERR &&
					sibling_type == DOM_ELEMENT_NODE) {
				exc = cb(sibling, pw);
			}

			cur = sibling;
			sibling = NULL;
		}
	} 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 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) {
			/* All subsequent sibling elements */
			exc = _foreach_element_sibling((dom_node *) target,
				_set_node_flags,
				(void *) BM_DOM_FLAG_STRUCTURE_CHANGED);
		} else {
			/* Just target itself */
			exc = _set_node_flags((dom_node *) target,
				(void *) BM_DOM_FLAG_STRUCTURE_CHANGED);
		}
	} 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;
}