1.1 --- a/librazor/razor.c	Fri May 01 16:48:47 2009 +0100
     1.2 +++ b/librazor/razor.c	Thu May 14 05:55:19 2009 +0100
     1.3 @@ -624,11 +624,6 @@
     1.4  	razor_file_iterator_destroy(fi);
     1.5  }
     1.6  
     1.7 -/* The diff order matters.  We should sort the packages so that a
     1.8 - * REMOVE of a package comes before the INSTALL, and so that all
     1.9 - * requires for a package have been installed before the package.
    1.10 - **/
    1.11 -
    1.12  RAZOR_EXPORT void
    1.13  razor_set_diff(struct razor_set *set, struct razor_set *upstream,
    1.14  	       razor_diff_callback_t callback, void *data)
    1.15 @@ -698,7 +693,7 @@
    1.16  	struct razor_set *set;
    1.17  	struct razor_set *next;
    1.18  	struct array actions;
    1.19 -	struct install_action *a, *end;
    1.20 +	struct deque *order;
    1.21  };
    1.22  
    1.23  static void
    1.24 @@ -730,6 +725,15 @@
    1.25  				  struct razor_set *next)
    1.26  {
    1.27  	struct razor_install_iterator *ii;
    1.28 +	struct razor_property *prop;
    1.29 +	/* A graph of the actions to be perfomed where
    1.30 +	 * A->B means action A should follow action B.
    1.31 +	 */
    1.32 +	struct graph follows;
    1.33 +	struct install_action *actions, *ai, *aj;
    1.34 +	int i, j, count, vertex_added;
    1.35 +	struct list *link;
    1.36 +	struct razor_set *rs;
    1.37  
    1.38  	assert (set != NULL);
    1.39  	assert (next != NULL);
    1.40 @@ -740,11 +744,58 @@
    1.41  	
    1.42  	razor_set_diff(set, next, add_action, ii);
    1.43  
    1.44 -	ii->a = ii->actions.data;
    1.45 -	ii->end = ii->actions.data + ii->actions.size;
    1.46 +	actions = ii->actions.data;
    1.47 +	count = ii->actions.size / sizeof (struct install_action);
    1.48  
    1.49 -	/* FIXME: We need to figure out the right install order here,
    1.50 -	 * so the post and pre scripts can run. */
    1.51 +	graph_init(&follows);
    1.52 +
    1.53 +	for(i = 0; i < count; i++) {
    1.54 +		ai = actions + i;
    1.55 +		rs = ai->action == RAZOR_INSTALL_ACTION_ADD ? next : set;
    1.56 +		vertex_added = 0;
    1.57 +		link = list_first(&ai->package->properties, &rs->property_pool);
    1.58 +		for(; link; link = list_next(link)) {
    1.59 +			prop = rs->properties.data;
    1.60 +			prop += link->data;
    1.61 +			switch(prop->flags & RAZOR_PROPERTY_TYPE_MASK) {
    1.62 +			case RAZOR_PROPERTY_REQUIRES:
    1.63 +			case RAZOR_PROPERTY_CONFLICTS:
    1.64 +				for(j = 0; j < count; j++) {
    1.65 +					if (j == i)
    1.66 +						continue;
    1.67 +					aj = actions + j;
    1.68 +					if (aj->package->name == prop->name) {
    1.69 +						if (ai->action ==
    1.70 +						    RAZOR_INSTALL_ACTION_ADD)
    1.71 +							graph_add_edge(&follows,
    1.72 +								       i, j);
    1.73 +						else
    1.74 +							graph_add_edge(&follows,
    1.75 +								       j, i);
    1.76 +						vertex_added++;
    1.77 +					}
    1.78 +				}
    1.79 +				break;
    1.80 +			}
    1.81 +		}
    1.82 +		if (ai->action == RAZOR_INSTALL_ACTION_ADD) {
    1.83 +			for(j = 0; j < count; j++) {
    1.84 +				if (j == i)
    1.85 +					continue;
    1.86 +				aj = actions + j;
    1.87 +				if (aj->package == ai->package &&
    1.88 +				    aj->action == RAZOR_INSTALL_ACTION_REMOVE) {
    1.89 +					graph_add_edge(&follows, i, j);
    1.90 +					vertex_added++;
    1.91 +				}
    1.92 +			}
    1.93 +		}
    1.94 +		if (!vertex_added)
    1.95 +			graph_add_edge(&follows, i, i);
    1.96 +	}
    1.97 +
    1.98 +	ii->order = graph_sort(&follows);
    1.99 +	graph_release(&follows);
   1.100  
   1.101  	return ii;
   1.102  }
   1.103 @@ -756,10 +807,12 @@
   1.104  			    enum razor_install_action *action,
   1.105  			    int *count)
   1.106  {
   1.107 -	if (ii->a == ii->end)
   1.108 +	struct install_action *a;
   1.109 +	if (deque_empty(ii->order))
   1.110  		return 0;
   1.111  
   1.112 -	switch (ii->a->action) {
   1.113 +	a = (struct install_action *)ii->actions.data + deque_pop(ii->order);
   1.114 +	switch (a->action) {
   1.115  	case RAZOR_INSTALL_ACTION_ADD:
   1.116  		*set = ii->next;
   1.117  		break;
   1.118 @@ -768,10 +821,9 @@
   1.119  		break;
   1.120  	}
   1.121  
   1.122 -	*package = ii->a->package;
   1.123 -	*action = ii->a->action;
   1.124 +	*package = a->package;
   1.125 +	*action = a->action;
   1.126  	*count = 0;
   1.127 -	ii->a++;
   1.128  
   1.129  	return 1;
   1.130  }
   1.131 @@ -780,5 +832,6 @@
   1.132  razor_install_iterator_destroy(struct razor_install_iterator *ii)
   1.133  {
   1.134  	array_release(&ii->actions);
   1.135 +	deque_free(ii->order);
   1.136  	free(ii);
   1.137  }