diff -r c75a2d5caae9 -r e45f50e940b6 librazor/razor.c
--- a/librazor/razor.c	Fri May 01 16:48:47 2009 +0100
+++ b/librazor/razor.c	Thu May 14 05:55:19 2009 +0100
@@ -624,11 +624,6 @@
 	razor_file_iterator_destroy(fi);
 }
 
-/* The diff order matters.  We should sort the packages so that a
- * REMOVE of a package comes before the INSTALL, and so that all
- * requires for a package have been installed before the package.
- **/
-
 RAZOR_EXPORT void
 razor_set_diff(struct razor_set *set, struct razor_set *upstream,
 	       razor_diff_callback_t callback, void *data)
@@ -698,7 +693,7 @@
 	struct razor_set *set;
 	struct razor_set *next;
 	struct array actions;
-	struct install_action *a, *end;
+	struct deque *order;
 };
 
 static void
@@ -730,6 +725,15 @@
 				  struct razor_set *next)
 {
 	struct razor_install_iterator *ii;
+	struct razor_property *prop;
+	/* A graph of the actions to be perfomed where
+	 * A->B means action A should follow action B.
+	 */
+	struct graph follows;
+	struct install_action *actions, *ai, *aj;
+	int i, j, count, vertex_added;
+	struct list *link;
+	struct razor_set *rs;
 
 	assert (set != NULL);
 	assert (next != NULL);
@@ -740,11 +744,58 @@
 	
 	razor_set_diff(set, next, add_action, ii);
 
-	ii->a = ii->actions.data;
-	ii->end = ii->actions.data + ii->actions.size;
+	actions = ii->actions.data;
+	count = ii->actions.size / sizeof (struct install_action);
 
-	/* FIXME: We need to figure out the right install order here,
-	 * so the post and pre scripts can run. */
+	graph_init(&follows);
+
+	for(i = 0; i < count; i++) {
+		ai = actions + i;
+		rs = ai->action == RAZOR_INSTALL_ACTION_ADD ? next : set;
+		vertex_added = 0;
+		link = list_first(&ai->package->properties, &rs->property_pool);
+		for(; link; link = list_next(link)) {
+			prop = rs->properties.data;
+			prop += link->data;
+			switch(prop->flags & RAZOR_PROPERTY_TYPE_MASK) {
+			case RAZOR_PROPERTY_REQUIRES:
+			case RAZOR_PROPERTY_CONFLICTS:
+				for(j = 0; j < count; j++) {
+					if (j == i)
+						continue;
+					aj = actions + j;
+					if (aj->package->name == prop->name) {
+						if (ai->action ==
+						    RAZOR_INSTALL_ACTION_ADD)
+							graph_add_edge(&follows,
+								       i, j);
+						else
+							graph_add_edge(&follows,
+								       j, i);
+						vertex_added++;
+					}
+				}
+				break;
+			}
+		}
+		if (ai->action == RAZOR_INSTALL_ACTION_ADD) {
+			for(j = 0; j < count; j++) {
+				if (j == i)
+					continue;
+				aj = actions + j;
+				if (aj->package == ai->package &&
+				    aj->action == RAZOR_INSTALL_ACTION_REMOVE) {
+					graph_add_edge(&follows, i, j);
+					vertex_added++;
+				}
+			}
+		}
+		if (!vertex_added)
+			graph_add_edge(&follows, i, i);
+	}
+
+	ii->order = graph_sort(&follows);
+	graph_release(&follows);
 
 	return ii;
 }
@@ -756,10 +807,12 @@
 			    enum razor_install_action *action,
 			    int *count)
 {
-	if (ii->a == ii->end)
+	struct install_action *a;
+	if (deque_empty(ii->order))
 		return 0;
 
-	switch (ii->a->action) {
+	a = (struct install_action *)ii->actions.data + deque_pop(ii->order);
+	switch (a->action) {
 	case RAZOR_INSTALL_ACTION_ADD:
 		*set = ii->next;
 		break;
@@ -768,10 +821,9 @@
 		break;
 	}
 
-	*package = ii->a->package;
-	*action = ii->a->action;
+	*package = a->package;
+	*action = a->action;
 	*count = 0;
-	ii->a++;
 
 	return 1;
 }
@@ -780,5 +832,6 @@
 razor_install_iterator_destroy(struct razor_install_iterator *ii)
 {
 	array_release(&ii->actions);
+	deque_free(ii->order);
 	free(ii);
 }