planner r894 - in trunk: . libplanner tests

[mvdpot svn gnome org]

Author: mvdpot
Date: Sat Mar 15 12:35:55 2008
New Revision: 894
URL: http://svn.gnome.org/viewvc/planner?rev=894&view=rev

Log:
2008-03-15  Maurice van der Pot  <griffon26 kfk4ever com>

	* libplanner/mrp-task-manager.c:
	(remove_parent_predecessors_from_dependency_graph),
	(remove_parent_from_dependency_graph),
	(add_parent_predecessors_to_dependency_graph),
	(add_parent_to_dependency_graph),
	(task_manager_build_dependency_graph),
	(task_manager_do_forward_pass), (task_manager_do_backward_pass),
	(check_move_traverse_recursive), (check_move_traverse),
	(mrp_task_manager_check_move):
	Fixed bug #382548. Planner now correctly detects loops that would be created
	by indenting a task that is a predecessor of the task that would become its
	parent, so it will no longer crash trying to undo an invalid action.
	* tests/task-test.c: (main):
	Added regression tests for bug #382548 and related issues.



Modified:
   trunk/ChangeLog
   trunk/libplanner/mrp-task-manager.c
   trunk/tests/task-test.c

Modified: trunk/libplanner/mrp-task-manager.c
==============================================================================
--- trunk/libplanner/mrp-task-manager.c	(original)
+++ trunk/libplanner/mrp-task-manager.c	Sat Mar 15 12:35:55 2008
@@ -47,7 +47,7 @@
 	gboolean    needs_recalc;
 	gboolean    in_recalc;
 
-	GList      *depencency_list;
+	GList      *dependency_list;
 };
 
 typedef struct {
@@ -903,6 +903,35 @@
 }
 
 static void
+remove_parent_predecessors_from_dependency_graph (MrpTask *task,
+						  MrpTask *parent)
+{
+	MrpTask            *predecessor;
+	MrpTaskGraphNode   *predecessor_node;
+	MrpTaskGraphNode   *task_node;
+	GList              *list, *l;
+	MrpRelation        *relation;
+	
+	/* Remove parent's predecessors from task and all of its children. */
+	list = imrp_task_peek_predecessors (parent);
+	for (l = list; l; l = l->next) {
+		relation = l->data;
+		predecessor = mrp_relation_get_predecessor (relation);
+
+		/* Remove predecessor from task */
+		predecessor_node = imrp_task_get_graph_node (predecessor);
+		predecessor_node->next = g_list_remove (predecessor_node->next, task);
+		task_node = imrp_task_get_graph_node (task);
+		task_node->prev = g_list_remove (task_node->prev, predecessor);
+			
+		/* Remove predecessor from all its children */
+		if (mrp_task_get_n_children (task) > 0) {
+			remove_predecessor_from_dependency_graph_recursive (task, predecessor);
+		}
+	}
+}
+
+static void
 remove_parent_from_dependency_graph (MrpTaskManager *manager,
 				     MrpTask        *task,
 				     MrpTask        *parent)
@@ -918,6 +947,40 @@
 
 	task_node->next = g_list_remove (task_node->next, parent);
 	parent_node->prev = g_list_remove (parent_node->prev, task);
+
+	/* Remove dependencies from the parent's predecessors from the task and all
+	 * its children.
+	 */
+	remove_parent_predecessors_from_dependency_graph (task, parent);
+}
+
+static void
+add_parent_predecessors_to_dependency_graph (MrpTask *task,
+					     MrpTask *parent)
+{
+	MrpTask            *predecessor;
+	MrpTaskGraphNode   *predecessor_node;
+	MrpTaskGraphNode   *task_node;
+	GList              *list, *l;
+	MrpRelation        *relation;
+
+	/* Add parent's predecessors to task and all of its children. */
+	list = imrp_task_peek_predecessors (parent);
+	for (l = list; l; l = l->next) {
+		relation = l->data;
+		predecessor = mrp_relation_get_predecessor (relation);
+
+		/* Add predecessor to task */
+		predecessor_node = imrp_task_get_graph_node (predecessor);
+		predecessor_node->next = g_list_append (predecessor_node->next, task);
+		task_node = imrp_task_get_graph_node (task);
+		task_node->prev = g_list_append (task_node->prev, predecessor);
+
+		/* Add predecessor to all its children */
+		if (mrp_task_get_n_children (task) > 0) {
+			add_predecessor_to_dependency_graph_recursive (task, predecessor);
+		}
+	}
 }
 
 static void
@@ -936,6 +999,11 @@
 
 	task_node->next = g_list_append (task_node->next, parent);
 	parent_node->prev = g_list_append (parent_node->prev, task);
+
+	/* Add dependencies from the parent's predecessors to the task and all
+	 * its children.
+	 */
+	add_parent_predecessors_to_dependency_graph (task, parent);
 }
 
 static void
@@ -1102,8 +1170,8 @@
 		}
 	}
 
-	g_list_free (priv->depencency_list);
-	priv->depencency_list = g_list_reverse (deps);
+	g_list_free (priv->dependency_list);
+	priv->dependency_list = g_list_reverse (deps);
 
 	g_list_free (queue);
 	g_list_free (tasks);
@@ -2129,9 +2197,9 @@
 	*/
 
 	if (start_task) {
-		l = g_list_find (priv->depencency_list, start_task);
+		l = g_list_find (priv->dependency_list, start_task);
 	} else {
-		l = priv->depencency_list;
+		l = priv->dependency_list;
 	}
 	
 	while (l) {
@@ -2161,7 +2229,7 @@
 
 	project_finish = mrp_task_get_finish (priv->root);
 
-	tasks = g_list_reverse (g_list_copy (priv->depencency_list));
+	tasks = g_list_reverse (g_list_copy (priv->dependency_list));
 
 	for (l = tasks; l; l = l->next) {
 		MrpTask *task, *parent;
@@ -2488,6 +2556,35 @@
 	return TRUE;
 }
 
+static gboolean
+check_move_traverse_recursive (MrpTaskManager *manager,
+			       MrpTask *task)
+{
+	MrpTask          *child;
+	gboolean          retval = TRUE;
+	
+	child = mrp_task_get_first_child (task);
+	while (retval && child) {
+		retval = check_predecessor_traverse (manager, child, child, 1);
+
+		if (retval && mrp_task_get_n_children (child) > 0) {
+			retval = check_move_traverse_recursive (manager, child);
+		}
+		
+		child = mrp_task_get_next_sibling (child);
+	}
+
+	return retval;
+}
+
+static gboolean
+check_move_traverse (MrpTaskManager *manager,
+		     MrpTask        *task)
+{
+	return check_predecessor_traverse (manager, task, task, 1) &&
+		check_move_traverse_recursive (manager, task);
+}
+
 gboolean
 mrp_task_manager_check_predecessor (MrpTaskManager  *manager,
 				    MrpTask         *task,
@@ -2546,8 +2643,6 @@
 	g_return_val_if_fail (MRP_IS_TASK (task), FALSE);
 	g_return_val_if_fail (MRP_IS_TASK (parent), FALSE);
 
-	/* FIXME: Check this. */
-
 	/* Remove the task from the old parent and add it to its new parent. */
 	remove_task_from_dependency_graph (manager, task, mrp_task_get_parent (task));
 	add_task_to_dependency_graph (manager, task, parent);
@@ -2563,7 +2658,7 @@
 				   task_manager_unset_visited_func,
 				   NULL);
 	
-	retval = check_predecessor_traverse (manager, task, task, 1);
+	retval = check_move_traverse (manager, task);
 
 	/* Put the task back again. */
 	remove_task_from_dependency_graph (manager, task, parent);

Modified: trunk/tests/task-test.c
==============================================================================
--- trunk/tests/task-test.c	(original)
+++ trunk/tests/task-test.c	Sat Mar 15 12:35:55 2008
@@ -1,3 +1,4 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
 #include <config.h>
 #include <locale.h>
 #include <string.h>
@@ -12,10 +13,11 @@
 {
 	MrpApplication *app;
 	MrpProject     *project;
-	MrpTask        *task1, *task2;
+	MrpTask        *task1, *task2, *task3, *task4;
 	mrptime         project_start, t1;
 	gint            work, duration;
 	gboolean        critical;
+	gboolean	success;
 	MrpTask        *root;
 	MrpRelation    *relation;
 	
@@ -48,7 +50,7 @@
 	/* Check that we don't mess with work, it should be as set above. */
 	CHECK_INTEGER_RESULT (work, DAY);
 
-	/* Check that duration is calculated correctly. Duration == work if on
+	/* Check that duration is calculated correctly. Duration == work if no
 	 * resources are assigned.
 	 */
         CHECK_INTEGER_RESULT (duration, DAY);
@@ -110,6 +112,89 @@
 
 	CHECK_POINTER_RESULT (relation, NULL);
 
+	/* Check that we can't make task2 the parent of task1 with the
+	 * predecessor relation in place
+	 */
+	success = mrp_project_move_task (project, 
+					 task1, 
+					 NULL, 
+					 task2, 
+					 FALSE, 
+					 NULL);
+
+	CHECK_BOOLEAN_RESULT (success, FALSE);
+
+	/* Check that we can't make task1 the parent of task2 with the
+	 * predecessor relation in place (bug #382548).
+	 * This test verifies that a loop is created in the dependency graph by
+	 * this action and that it is detected.
+	 */
+	success = mrp_project_move_task (project, 
+					 task2, 
+					 NULL, 
+					 task1, 
+					 FALSE, 
+					 NULL);
+
+	CHECK_BOOLEAN_RESULT (success, FALSE);
+
+	/* Add task3 as parent of task2 and see if we can't make task1 the
+	 * parent of task3. This test verifies that loops that include direct 
+	 * children but not the parent, are detected.
+	 */
+	task3 = g_object_new (MRP_TYPE_TASK,
+			      "name", "T3",
+			      "work", 10*DAY,
+			      NULL);
+
+	mrp_project_insert_task (project, NULL, -1, task3);
+
+	success = mrp_project_move_task (project,
+					 task2,
+					 NULL,
+					 task3,
+					 FALSE,
+					 NULL);
+	CHECK_BOOLEAN_RESULT (success, TRUE);
+
+	success = mrp_project_move_task (project, 
+					 task3, 
+					 NULL, 
+					 task1, 
+					 FALSE, 
+					 NULL);
+
+	CHECK_BOOLEAN_RESULT (success, FALSE);
+
+	/* Add task4 as parent of task3 and see if we can't make task1 the
+	 * parent of task3. This test verifies that loops that include indirect
+	 * children but not the parent or a direct child, are detected. If this
+	 * works, we'll assume detection is recursive as it should be.
+	 */
+	task4 = g_object_new (MRP_TYPE_TASK,
+			      "name", "T4",
+			      "work", 10*DAY,
+			      NULL);
+
+	mrp_project_insert_task (project, NULL, -1, task4);
+
+	success = mrp_project_move_task (project,
+					 task3,
+					 NULL,
+					 task4,
+					 FALSE,
+					 NULL);
+	CHECK_BOOLEAN_RESULT (success, TRUE);
+
+	success = mrp_project_move_task (project, 
+					 task4, 
+					 NULL, 
+					 task1, 
+					 FALSE, 
+					 NULL);
+
+	CHECK_BOOLEAN_RESULT (success, FALSE);
+
 	/* Retrieve a relation and see that it's correct. */
 	relation = mrp_task_get_relation (task1, task2);