- update transaction ordering code

- add queue insert/delete functions

5 files changed, 667 insertions, 128 deletions

diff --git a/src/queue.c b/src/queue.c
index 345050f..38fd765 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -75,3 +75,54 @@ queue_alloc_one(Queue *q)
     }
 }
 
+void
+queue_insert(Queue *q, int pos, Id id)
+{
+  queue_push(q, id);	/* make room */
+  if (pos < q->count - 1)
+    {
+      memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id));
+      q->elements[pos] = id;
+    }
+}
+
+void
+queue_delete(Queue *q, int pos)
+{
+  if (pos >= q->count)
+    return;
+  if (pos < q->count - 1)
+    memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id));
+  q->left++;
+  q->count--;
+}
+
+void
+queue_insert2(Queue *q, int pos, Id id1, Id id2)
+{
+  queue_push(q, id1);	/* make room */
+  queue_push(q, id2);	/* make room */
+  if (pos < q->count - 2)
+    {
+      memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id));
+      q->elements[pos] = id1;
+      q->elements[pos] = id2;
+    }
+}
+
+void
+queue_delete2(Queue *q, int pos)
+{
+  if (pos >= q->count)
+    return;
+  if (pos == q->count - 1)
+    {
+      q->left++;
+      q->count--;
+      return;
+    }
+  if (pos < q->count - 2)
+    memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id));
+  q->left += 2;
+  q->count -= 2;
+}
diff --git a/src/queue.h b/src/queue.h
index 4b3f9eb..090799e 100644
--- a/src/queue.h
+++ b/src/queue.h
@@ -106,4 +106,9 @@ extern void queue_init_buffer(Queue *q, Id *buf, int size);
 extern void queue_init_clone(Queue *t, Queue *s);
 extern void queue_free(Queue *q);
 
+extern void queue_insert(Queue *q, int pos, Id id);
+extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
+extern void queue_delete(Queue *q, int pos);
+extern void queue_delete2(Queue *q, int pos);
+
 #endif /* SATSOLVER_QUEUE_H */
diff --git a/src/solvable.c b/src/solvable.c
index 68a3855..6f6f590 100644
--- a/src/solvable.c
+++ b/src/solvable.c
@@ -42,6 +42,29 @@ solvable_lookup_id(Solvable *s, Id keyname)
   return repo_lookup_id(s->repo, s - s->repo->pool->solvables, keyname);
 }
 
+int
+solvable_lookup_idarray(Solvable *s, Id keyname, Queue *q)
+{
+  Dataiterator di;
+  int found = 0;
+
+  queue_empty(q);
+  if (!s->repo)
+    return 0;
+  dataiterator_init(&di, s->repo->pool, s->repo, s - s->repo->pool->solvables, keyname, 0, SEARCH_ARRAYSENTINEL);
+  while (dataiterator_step(&di))
+    {
+      if (di.key->type != REPOKEY_TYPE_IDARRAY && di.key->type != REPOKEY_TYPE_REL_IDARRAY)
+	continue;
+      found = 1;
+      if (di.kv.eof)
+	break;
+      queue_push(q, di.kv.id);
+    }
+  dataiterator_free(&di);
+  return found;
+}
+
 const char *
 solvable_lookup_str(Solvable *s, Id keyname)
 {
diff --git a/src/transaction.c b/src/transaction.c
index cfedc79..b0cde03 100644
--- a/src/transaction.c
+++ b/src/transaction.c
@@ -324,6 +324,9 @@ transaction_free(Transaction *trans)
   queue_free(&trans->transaction_info);
   trans->transaction_installed = sat_free(trans->transaction_installed);
   map_free(&trans->transactsmap);
+  trans->tes = sat_free(trans->tes);
+  trans->ntes = 0;
+  trans->invedgedata = sat_free(trans->invedgedata);
 }
 
 void
@@ -433,42 +436,84 @@ transaction_calculate(Transaction *trans, Queue *decisionq, Map *noobsmap)
 #define TYPE_REQ    	(1<<4)
 #define TYPE_PREREQ 	(1<<5)
 
-#define EDGEDATA_BLOCK	127
+#define TYPE_CYCLETAIL  (1<<16)
+#define TYPE_CYCLEHEAD  (1<<17)
 
-struct transel {
-  Id p;
-  Id type;
-  Id edges;
-  Id invedges;
-  Id mark;
-  Id medianr;
-  Id ddeg;	/* unused */
-};
+#define EDGEDATA_BLOCK	127
 
 struct orderdata {
   Transaction *trans;
-  struct transel *tes;
+  struct _TransactionElement *tes;
   int ntes;
   Id *edgedata;
   int nedgedata;
   Id *invedgedata;
-  Map cycletes;
+
+  Queue cycles;
+  Queue cyclesdata;
+  int ncycles;
 };
 
 static int
+addteedge(struct orderdata *od, int from, int to, int type)
+{
+  int i;
+  struct _TransactionElement *te;
+
+  if (from == to)
+    return 0;
+
+  /* printf("edge %d(%s) -> %d(%s) type %x\n", from, solvid2str(pool, od->tes[from].p), to, solvid2str(pool, od->tes[to].p), type); */
+
+  te = od->tes + from;
+  for (i = te->edges; od->edgedata[i]; i += 2)
+    if (od->edgedata[i] == to)
+      break;
+  /* test of brokenness */
+  if (type == TYPE_BROKEN)
+    return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
+  if (od->edgedata[i])
+    {
+      od->edgedata[i + 1] |= type;
+      return 0;
+    }
+  if (i + 1 == od->nedgedata)
+    {
+      /* printf("tail add %d\n", i - te->edges); */
+      if (!i)
+	te->edges = ++i;
+      od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
+    }
+  else
+    {
+      /* printf("extend %d\n", i - te->edges); */
+      od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
+      if (i > te->edges)
+	memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
+      i = od->nedgedata + (i - te->edges);
+      te->edges = od->nedgedata;
+    }
+  od->edgedata[i] = to;
+  od->edgedata[i + 1] = type;
+  od->edgedata[i + 2] = 0;	/* end marker */
+  od->nedgedata = i + 3;
+  return 0;
+}
+
+static int
 addedge(struct orderdata *od, Id from, Id to, int type)
 {
   Transaction *trans = od->trans;
   Pool *pool = trans->pool;
   Solvable *s;
-  struct transel *te;
+  struct _TransactionElement *te;
   int i;
 
   // printf("addedge %d %d type %d\n", from, to, type);
   s = pool->solvables + from;
   if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start])
     {
-      /* passive, map to active */
+      /* obsolete, map to install */
       if (trans->transaction_installed[from - pool->installed->start] > 0)
 	from = trans->transaction_installed[from - pool->installed->start];
       else
@@ -488,7 +533,7 @@ addedge(struct orderdata *od, Id from, Id to, int type)
   s = pool->solvables + to;
   if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start])
     {
-      /* passive, map to active */
+      /* obsolete, map to install */
       if (trans->transaction_installed[to - pool->installed->start] > 0)
 	to = trans->transaction_installed[to - pool->installed->start];
       else
@@ -506,7 +551,7 @@ addedge(struct orderdata *od, Id from, Id to, int type)
 	}
     }
 
-  /* map target to te num */
+  /* map from/to to te numbers */
   for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
     if (te->p == to)
       break;
@@ -520,47 +565,10 @@ addedge(struct orderdata *od, Id from, Id to, int type)
   if (i == od->ntes)
     return 0;
 
-  if (i == to)
-    return 0;	/* no edges to ourselfes */
-
-  /* printf("edge %d(%s) -> %d(%s) type %x\n", i, solvid2str(pool, od->tes[i].p), to, solvid2str(pool, od->tes[to].p), type); */
-
-  for (i = te->edges; od->edgedata[i]; i += 2)
-    if (od->edgedata[i] == to)
-      break;
-  /* test of brokenness */
-  if (type == TYPE_BROKEN)
-    return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0;
-  if (od->edgedata[i])
-    {
-      od->edgedata[i + 1] |= type;
-      return 0;
-    }
-  if (i + 1 == od->nedgedata)
-    {
-      /* printf("tail add %d\n", i - te->edges); */
-      if (!i)
-	te->edges = ++i;
-      od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK);
-    }
-  else
-    {
-      /* printf("extend %d\n", i - te->edges); */
-      od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK);
-      if (i > te->edges)
-	memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges));
-      i = od->nedgedata + (i - te->edges);
-      te->edges = od->nedgedata;
-    }
-  od->edgedata[i] = to;
-  od->edgedata[i + 1] = type;
-  od->edgedata[i + 2] = 0;
-  od->nedgedata = i + 3;
-  te->ddeg++;
-  od->tes[to].ddeg--;
-  return 0;
+  return addteedge(od, i, to, type);
 }
 
+#if 1
 static int
 havechoice(struct orderdata *od, Id p, Id q1, Id q2)
 {
@@ -572,7 +580,9 @@ havechoice(struct orderdata *od, Id p, Id q1, Id q2)
 
   /* both q1 and q2 are uninstalls. check if their TEs intersect */
   /* common case: just one TE for both packages */
+#if 0
   printf("havechoice %d %d %d\n", p, q1, q2);
+#endif
   if (trans->transaction_installed[q1 - pool->installed->start] == 0)
     return 1;
   if (trans->transaction_installed[q2 - pool->installed->start] == 0)
@@ -598,6 +608,34 @@ havechoice(struct orderdata *od, Id p, Id q1, Id q2)
   queue_free(&ti2);
   return 1;
 }
+#endif
+
+static inline int
+havescripts(Pool *pool, Id solvid)
+{
+  Solvable *s = pool->solvables + solvid;
+  const char *dep;
+  if (s->requires)
+    {
+      Id req, *reqp;
+      int inpre = 0;
+      reqp = s->repo->idarraydata + s->requires;
+      while ((req = *reqp++) != 0)
+	{
+          if (req == SOLVABLE_PREREQMARKER)
+	    {
+	      inpre = 1;
+	      continue;
+	    }
+	  if (!inpre)
+	    continue;
+	  dep = id2str(pool, req);
+	  if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0)
+	    return 1;
+	}
+    }
+  return 0;
+}
 
 static void
 addsolvableedges(struct orderdata *od, Solvable *s)
@@ -610,7 +648,11 @@ addsolvableedges(struct orderdata *od, Solvable *s)
   Repo *installed = pool->installed;
   Solvable *s2;
   Queue reqq;
+  int provbyinst;
 
+#if 0
+  printf("addsolvableedges %s\n", solvable2str(pool, s));
+#endif
   p = s - pool->solvables;
   queue_init(&reqq);
   if (s->requires)
@@ -624,8 +666,17 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 	      pre = TYPE_PREREQ;
 	      continue;
 	    }
+#if 0
+	  if (pre != TYPE_PREREQ && installed && s->repo == installed)
+	    {
+	      /* ignore normal requires if we're getting obsoleted */
+	      if (trans->transaction_installed[p - pool->installed->start])
+	        continue;
+	    }
+#endif
 	  queue_empty(&reqq);
 	  numins = 0;	/* number of packages to be installed providing it */
+	  provbyinst = 0;	/* provided by kept package */
 	  FOR_PROVIDES(p2, pp2, req)
 	    {
 	      s2 = pool->solvables + p2;
@@ -636,8 +687,14 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		}
 	      if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2))
 		{
+		  provbyinst = 1;
+#if 0
+		  printf("IGNORE inst provides %s by %s\n", dep2str(pool, req), solvable2str(pool, s2));
 		  reqq.count = 0;	/* provided by package that stays installed */
 		  break;
+#else
+		  continue;
+#endif
 		}
 	      if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2))
 		continue;		/* package stays uninstalled */
@@ -654,11 +711,40 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		  if (s2->repo == installed)
 		    continue;	/* s2 gets uninstalled */
 		  queue_pushunique(&reqq, p2);
-		  /* EDGE s(A) -> s2(A) */
 		}
 	    }
+	  if (provbyinst)
+	    {
+	      /* prune to harmless ->inst edges */
+	      for (i = j = 0; i < reqq.count; i++)
+		if (pool->solvables[reqq.elements[i]].repo != installed)
+		  reqq.elements[j++] = reqq.elements[i];
+	      reqq.count = j;
+	    }
+
 	  if (numins && reqq.count)
 	    {
+	      if (s->repo == installed)
+		{
+		  for (i = 0; i < reqq.count; i++)
+		    {
+		      if (pool->solvables[reqq.elements[i]].repo == installed)
+			{
+			  for (j = 0; j < reqq.count; j++)
+			    {
+			      if (pool->solvables[reqq.elements[j]].repo != installed)
+				{
+				  if (trans->transaction_installed[reqq.elements[i] - pool->installed->start] == reqq.elements[j])
+				    continue;	/* no self edge */
+#if 0
+				  printf("add interrreq uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, reqq.elements[i]), dep2str(pool, req), solvid2str(pool, reqq.elements[j]));
+#endif
+				  addedge(od, reqq.elements[i], reqq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P);
+				}
+			    }
+			}
+		    }
+		}
 	      /* no mixed types, remove all deps on uninstalls */
 	      for (i = j = 0; i < reqq.count; i++)
 		if (pool->solvables[reqq.elements[i]].repo != installed)
@@ -678,7 +764,7 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		  if (pool->solvables[p].repo != installed)
 		    {
 #if 0
-		      printf("add inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
+		      printf("add inst->inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2));
 #endif
 		      addedge(od, p, p2, pre);
 		    }
@@ -692,6 +778,16 @@ addsolvableedges(struct orderdata *od, Solvable *s)
 		}
 	      else
 		{
+		  if (s->repo != installed)
+		    continue;	/* no inst->uninst edges, please! */
+
+		  /* uninst -> uninst edge. Those make trouble. Only add if we must */
+		  if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p))
+		    {
+		      /* p is obsoleted by another package and has no scripts */
+		      /* we assume that the obsoletor is good enough to replace p */
+		      continue;
+		    }
 #if 1
 		  choice = 0;
 		  for (j = 0; j < reqq.count; j++)
@@ -745,42 +841,20 @@ addsolvableedges(struct orderdata *od, Solvable *s)
   queue_free(&reqq);
 }
 
-static inline int
-haveprereq(Pool *pool, Id solvid)
-{
-  Solvable *s = pool->solvables + solvid;
-  if (s->requires)
-    {
-      Id req, *reqp;
-      int inpre = 0;
-      reqp = s->repo->idarraydata + s->requires;
-      while ((req = *reqp++) != 0)
-	{
-          if (req == SOLVABLE_PREREQMARKER)
-	    {
-	      inpre = 1;
-	      continue;
-	    }
-	  if (inpre && strncmp(id2str(pool, req), "rpmlib(", 7) != 0)
-	    return 1;
-	}
-    }
-  return 0;
-}
 
-void
+/* break an edge in a cycle */
+static void
 breakcycle(struct orderdata *od, Id *cycle)
 {
   Pool *pool = od->trans->pool;
   Id ddegmin, ddegmax, ddeg;
   int k, l;
-  struct transel *te;
+  struct _TransactionElement *te;
 
   l = 0;
   ddegmin = ddegmax = 0;
   for (k = 0; cycle[k + 1]; k += 2)
     {
-      MAPSET(&od->cycletes, cycle[k]);	/* this te is involved in a cycle */
       ddeg = od->edgedata[cycle[k + 1] + 1];
       if (ddeg > ddegmax)
 	ddegmax = ddeg;
@@ -792,7 +866,7 @@ breakcycle(struct orderdata *od, Id *cycle)
 	}
       if (ddeg == ddegmin)
 	{
-	  if (haveprereq(pool, od->tes[cycle[l]].p) && !haveprereq(pool, od->tes[cycle[k]].p))
+	  if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p))
 	    {
 	      /* prefer k, as l comes from a package with contains scriptlets */
 	      l = k;
@@ -803,6 +877,23 @@ breakcycle(struct orderdata *od, Id *cycle)
 	}
     }
 
+  /* record brkoen cycle starting with the tail */
+  queue_push(&od->cycles, od->cyclesdata.count);		/* offset into data */
+  queue_push(&od->cycles, k / 2);				/* cycle elements */
+  queue_push(&od->cycles, od->edgedata[cycle[l + 1] + 1]);	/* broken edge */
+  od->ncycles++;
+  for (k = l;;)
+    {
+      k += 2;
+      if (!cycle[k + 1])
+	k = 0;
+      queue_push(&od->cyclesdata, cycle[k]);
+      if (k == l)
+	break;
+    }
+  queue_push(&od->cyclesdata, 0);	/* mark end */
+
+  /* break that edge */
   od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN;
 
 #if 1
@@ -810,9 +901,8 @@ breakcycle(struct orderdata *od, Id *cycle)
     return;
 #endif
 
-
   /* cycle recorded, print it */
-  if ((ddegmax & TYPE_PREREQ) != 0)
+  if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0)
     printf("CRITICAL ");
   printf("cycle: --> ");
   for (k = 0; cycle[k + 1]; k += 2)
@@ -826,6 +916,181 @@ breakcycle(struct orderdata *od, Id *cycle)
   printf("\n");
 }
 
+static inline void
+dump_tes(struct orderdata *od)
+{
+  Pool *pool = od->trans->pool;
+  int i, j;
+  Queue obsq;
+  struct _TransactionElement *te, *te2;
+
+  queue_init(&obsq);
+  for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
+    {
+      Solvable *s = pool->solvables + te->p;
+      printf("TE %4d: %c%s\n", i, s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
+      if (s->repo != pool->installed)
+        {
+	  queue_empty(&obsq);
+	  solver_transaction_all_pkgs(od->trans, te->p, &obsq);
+	  for (j = 0; j < obsq.count; j++)
+	    printf("         -%s\n", solvid2str(pool, obsq.elements[j]));
+	}
+      for (j = te->edges; od->edgedata[j]; j += 2)
+	{
+	  te2 = od->tes + od->edgedata[j];
+	  printf("       --%x--> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], solvid2str(pool, te2->p));
+	}
+    }
+}
+
+#if 1
+static void
+reachable(struct orderdata *od, Id i)
+{
+  struct _TransactionElement *te = od->tes + i;
+  int j, k;
+
+  if (te->mark != 0)
+    return;
+  te->mark = 1;
+  for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
+    {
+      if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
+	continue;
+      if (!od->tes[k].mark)
+        reachable(od, k);
+      if (od->tes[k].mark == 2)
+	{
+	  te->mark = 2;
+	  return;
+	}
+    }
+  te->mark = -1;
+}
+#endif
+
+static void
+addcycleedges(struct orderdata *od, Id *cycle, Queue *todo)
+{
+#if 0
+  Transaction *trans = od->trans;
+  Pool *pool = trans->pool;
+#endif
+  struct _TransactionElement *te;
+  int i, j, k, tail;
+#if 1
+  int head;
+#endif
+
+#if 0
+  printf("addcycleedges\n");
+  for (i = 0; (j = cycle[i]) != 0; i++)
+    printf("cycle %s\n", solvid2str(pool, od->tes[j].p));
+#endif
+
+  /* first add all the tail cycle edges */
+
+  /* see what we can reach from the cycle */
+  queue_empty(todo);
+  for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
+    te->mark = 0;
+  for (i = 0; (j = cycle[i]) != 0; i++)
+    {
+      od->tes[j].mark = -1;
+      queue_push(todo, j);
+    }
+  while (todo->count)
+    {
+      i = queue_pop(todo);
+      te = od->tes + i;
+      if (te->mark > 0)
+	continue;
+      te->mark = te->mark < 0 ? 2 : 1;
+      for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
+	{
+	  if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
+	    continue;
+	  if (od->tes[k].mark > 0)
+	    continue;	/* no need to visit again */
+	  queue_push(todo, k);
+	}
+    }
+  /* now all cycle TEs are marked with 2, all TEs reachable
+   * from the cycle are marked with 1 */
+  tail = cycle[0];
+  od->tes[tail].mark = 1;	/* no need to add edges */
+
+  for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
+    {
+      if (te->mark)
+	continue;	/* reachable from cycle */
+      for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
+	{
+	  if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
+	    continue;
+	  if (od->tes[k].mark != 2)
+	    continue;
+	  /* We found an edge to the cycle. Add an extra edge to the tail */
+	  /* the TE was not reachable, so we're not creating a new cycle! */
+#if 0
+	  printf("adding TO TAIL cycle edge %d->%d %s->%s!\n", i, tail, solvid2str(pool, od->tes[i].p), solvid2str(pool, od->tes[tail].p));
+#endif
+	  j -= te->edges;	/* in case we move */
+	  addteedge(od, i, tail, TYPE_CYCLETAIL);
+	  j += te->edges;
+	  break;	/* one edge is enough */
+	}
+    }
+
+#if 1
+  /* now add all head cycle edges */
+
+  /* reset marks */
+  for (i = 1, te = od->tes + i; i < od->ntes; i++, te++)
+    te->mark = 0;
+  head = 0;
+  for (i = 0; (j = cycle[i]) != 0; i++)
+    {
+      head = j;
+      od->tes[j].mark = 2;
+    }
+  /* first the head to save some time */
+  te = od->tes + head;
+  for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
+    {
+      if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
+	continue;
+      if (!od->tes[k].mark)
+	reachable(od, k);
+      if (od->tes[k].mark == -1)
+	od->tes[k].mark = -2;	/* no need for another edge */
+    }
+  for (i = 0; cycle[i] != 0; i++)
+    {
+      if (cycle[i] == head)
+	break;
+      te = od->tes + cycle[i];
+      for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2)
+	{
+	  if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0)
+	    continue;
+	  /* see if we can reach a cycle TE from k */
+	  if (!od->tes[k].mark)
+	    reachable(od, k);
+	  if (od->tes[k].mark == -1)
+	    {
+#if 0
+	      printf("adding FROM HEAD cycle edge %d->%d %s->%s [%s]!\n", head, k, solvid2str(pool, od->tes[head].p), solvid2str(pool, od->tes[k].p), solvid2str(pool, od->tes[cycle[i]].p));
+#endif
+	      addteedge(od, head, k, TYPE_CYCLEHEAD);
+	      od->tes[k].mark = -2;	/* no need to add that one again */
+	    }
+	}
+    }
+#endif
+}
+
 void
 transaction_order(Transaction *trans)
 {
@@ -836,15 +1101,15 @@ transaction_order(Transaction *trans)
   Solvable *s;
   int i, j, k, numte, numedge;
   struct orderdata od;
-  struct transel *te;
+  struct _TransactionElement *te;
   Queue todo, obsq;
-  int cycstart, cycel, broken;
+  int cycstart, cycel;
   Id *cycle, *obstypes;
   int oldcount;
-  int now;
+  int start, now;
 
   POOL_DEBUG(SAT_DEBUG_STATS, "ordering transaction\n");
-  now = sat_timems(0);
+  start = now = sat_timems(0);
   /* create a transaction element for every active component */
   numte = 0;
   for (i = 0; i < tr->count; i += 2)
@@ -867,7 +1132,7 @@ transaction_order(Transaction *trans)
   od.edgedata = sat_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK);
   od.edgedata[0] = 0;
   od.nedgedata = 1;
-  map_init(&od.cycletes, numte);
+  queue_init(&od.cycles);
 
   for (i = 0, te = od.tes + 1; i < tr->count; i += 2)
     {
@@ -877,7 +1142,6 @@ transaction_order(Transaction *trans)
 	continue;
       te->p = p;
       te->type = tr->elements[i];
-      te->medianr = solvable_lookup_num(s, SOLVABLE_MEDIANR, 0);
       te++;
     }
 
@@ -896,10 +1160,13 @@ transaction_order(Transaction *trans)
       numedge++;
   POOL_DEBUG(SAT_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2);
   POOL_DEBUG(SAT_DEBUG_STATS, "edge creation took %d ms\n", sat_timems(now));
+
+#if 0
+  dump_tes(&od);
+#endif
   
+  now = sat_timems(0);
   /* kill all cycles */
-  broken = 0;
-
   queue_init(&todo);
   for (i = numte - 1; i > 0; i--)
     queue_push(&todo, i);
@@ -961,8 +1228,8 @@ transaction_order(Transaction *trans)
 	{
 	  cycle[k * 2] = cycle[k];
 	  te = od.tes + cycle[k - 1];
-	  if (te->mark == 1)
-	    te->mark = 0;	/* reset investigation marker */
+	  assert(te->mark == 1);
+	  te->mark = 0;	/* reset investigation marker */
 	  /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */
 	  for (j = te->edges; od.edgedata[j]; j += 2)
 	    if (od.edgedata[j] == cycle[k])
@@ -973,34 +1240,47 @@ transaction_order(Transaction *trans)
       /* now cycle looks like this: */
       /* te1 edge te2 edge te3 ... teN edge te1 0 */
       breakcycle(&od, cycle);
-      broken++;
       /* restart with start of cycle */
       todo.count = cycstart + 1;
     }
-  POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", broken);
+  POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", od.ncycles);
+  POOL_DEBUG(SAT_DEBUG_STATS, "cycle breaking took %d ms\n", sat_timems(now));
 
-  /* invert all edges */
-  for (i = 1, te = od.tes + i; i < numte; i++, te++)
-    {
-      te->invedges = 1;	/* term 0 */
-      te->mark = 0;	/* backref count */
-    }
+  now = sat_timems(0);
+  /* now go through all broken cycles and create cycle edges to help
+     the ordering */
+   for (i = od.cycles.count - 3; i >= 0; i -= 3)
+     {
+       if (od.cycles.elements[i + 2] >= TYPE_REQ)
+         addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
+     }
+   for (i = od.cycles.count - 3; i >= 0; i -= 3)
+     {
+       if (od.cycles.elements[i + 2] < TYPE_REQ)
+         addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo);
+     }
+  POOL_DEBUG(SAT_DEBUG_STATS, "cycle edge creation took %d ms\n", sat_timems(now));
 
+  /* all edges are finally set up and there are no cycles, now the easy part.
+   * Create an ordered transaction */
+  now = sat_timems(0);
+  /* first invert all edges */
+  for (i = 1, te = od.tes + i; i < numte; i++, te++)
+    te->mark = 1;	/* term 0 */
   for (i = 1, te = od.tes + i; i < numte; i++, te++)
     {
       for (j = te->edges; od.edgedata[j]; j += 2)
         {
 	  if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 	    continue;
-	  struct transel *te2 = od.tes + od.edgedata[j];
-	  te2->invedges++;
+	  od.tes[od.edgedata[j]].mark++;
 	}
     }
   j = 1;
   for (i = 1, te = od.tes + i; i < numte; i++, te++)
     {
-      te->invedges += j;
-      j = te->invedges;
+      te->mark += j;
+      j = te->mark;
     }
   POOL_DEBUG(SAT_DEBUG_STATS, "invedge space: %d\n", j + 1);
   od.invedgedata = sat_calloc(j + 1, sizeof(Id));
@@ -1010,13 +1290,20 @@ transaction_order(Transaction *trans)
         {
 	  if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0)
 	    continue;
-	  struct transel *te2 = od.tes + od.edgedata[j];
-	  od.invedgedata[--te2->invedges] = i;
-	  te->mark++;
+	  od.invedgedata[--od.tes[od.edgedata[j]].mark] = i;
 	}
     }
+  for (i = 1, te = od.tes + i; i < numte; i++, te++)
+    te->edges = te->mark;	/* edges now points into invedgedata */
+  od.edgedata = sat_free(od.edgedata);
+
   /* now the final ordering */
   for (i = 1, te = od.tes + i; i < numte; i++, te++)
+    te->mark = 0;
+  for (i = 1, te = od.tes + i; i < numte; i++, te++)
+    for (j = te->edges; od.invedgedata[j]; j++)
+      od.tes[od.invedgedata[j]].mark++;
+  for (i = 1, te = od.tes + i; i < numte; i++, te++)
     if (te->mark == 0)
       queue_push(&todo, i);
   assert(todo.count > 0);
@@ -1051,19 +1338,13 @@ transaction_order(Transaction *trans)
 	    }
 	}
       if (i == todo.count)
-	{
-	  for (i = 0; i < todo.count; i++)
-	    {
-	      j = todo.elements[i];
-	      if (MAPTST(&od.cycletes, j))
-		break;
-	    }
-	}
-      if (i == todo.count)
-        i = 0;
+	i = 0;
       te = od.tes + todo.elements[i];
       queue_push(tr, te->type);
       queue_push(tr, te->p);
+#if 0
+printf("do %s\n", solvid2str(pool, te->p));
+#endif
       s = pool->solvables + te->p;
       if (installed && s->repo != installed)
 	{
@@ -1081,24 +1362,187 @@ transaction_order(Transaction *trans)
 		}
 	    }
 	}
-      if (i < todo.count - 1)
-        memmove(todo.elements + i, todo.elements + i + 1, (todo.count - 1 - i) * sizeof(Id));
-      queue_pop(&todo);
-      for (j = te->invedges; od.invedgedata[j]; j++)
+      queue_delete(&todo, i);
+      for (j = te->edges; od.invedgedata[j]; j++)
 	{
-	  struct transel *te2 = od.tes + od.invedgedata[j];
+	  struct _TransactionElement *te2 = od.tes + od.invedgedata[j];
 	  assert(te2->mark > 0);
 	  if (--te2->mark == 0)
 	    {
 	      queue_push(&todo, od.invedgedata[j]);
+#if 0
+printf("free %s\n", solvid2str(pool, od.tes[od.invedgedata[j]].p));
+#endif
 	    }
 	}
     }
+  sat_free(obstypes);
   queue_free(&todo);
   queue_free(&obsq);
   for (i = 1, te = od.tes + i; i < numte; i++, te++)
     assert(te->mark == 0);
   assert(tr->count == oldcount);
-  POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(now));
+  POOL_DEBUG(SAT_DEBUG_STATS, "creating new transaction took %d ms\n", sat_timems(now));
+  POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(start));
+
+  trans->tes = od.tes;
+  trans->ntes = numte;
+  trans->invedgedata = od.invedgedata;
+}
+
+static void
+transaction_check_pkg(Transaction *trans, Id tepkg, Id pkg, Map *ins, Map *seen, int onlyprereq, Id noconfpkg, int depth)
+{
+  Pool *pool = trans->pool;
+  Id p, pp;
+  Solvable *s;
+  int good;
+
+  if (MAPTST(seen, pkg))
+    return;
+  MAPSET(seen, pkg);
+  s = pool->solvables + pkg;
+#if 0
+  printf("- %*s%c%s\n", depth * 2, "", s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
+#endif
+  if (s->requires)
+    {
+      Id req, *reqp;
+      int inpre = 0;
+      reqp = s->repo->idarraydata + s->requires;
+      while ((req = *reqp++) != 0)
+	{
+          if (req == SOLVABLE_PREREQMARKER)
+	    {
+	      inpre = 1;
+	      continue;
+	    }
+	  if (onlyprereq && !inpre)
+	    continue;
+	  if (!strncmp(id2str(pool, req), "rpmlib(", 7))
+	    continue;
+	  good = 0;
+	  /* first check kept packages, then freshly installed, then not yet uninstalled */
+	  FOR_PROVIDES(p, pp, req)
+	    {
+	      if (!MAPTST(ins, p))
+		continue;
+	      if (MAPTST(&trans->transactsmap, p))
+		continue;
+	      good++;
+	      transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
+	    }
+	  if (!good)
+	    {
+	      FOR_PROVIDES(p, pp, req)
+		{
+		  if (!MAPTST(ins, p))
+		    continue;
+		  if (pool->solvables[p].repo == pool->installed)
+		    continue;
+		  good++;
+		  transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
+		}
+	    }
+	  if (!good)
+	    {
+	      FOR_PROVIDES(p, pp, req)
+		{
+		  if (!MAPTST(ins, p))
+		    continue;
+		  good++;
+		  transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1);
+		}
+	    }
+	  if (!good)
+	    {
+	      printf("  %c%s: nothing provides %s needed by %c%s\n", pool->solvables[tepkg].repo == pool->installed ? '-' : '+', solvid2str(pool, tepkg), dep2str(pool, req), s->repo == pool->installed ? '-' : '+', solvable2str(pool, s));
+	    }
+	}
+    }
+}
+
+void
+transaction_check(Transaction *trans)
+{
+  Pool *pool = trans->pool;
+  Solvable *s;
+  Id p, type, lastins;
+  Map ins, seen;
+  int i;
+
+  printf("\nchecking transaction order...\n");
+  map_init(&ins, pool->nsolvables);
+  map_init(&seen, pool->nsolvables);
+  if (pool->installed)
+    FOR_REPO_SOLVABLES(pool->installed, p, s)
+      MAPSET(&ins, p);
+  lastins = 0;
+  for (i = 0; i < trans->steps.count; i += 2)
+    {
+      type = trans->steps.elements[i];
+      p = trans->steps.elements[i + 1];
+      s = pool->solvables + p;
+      if (s->repo != pool->installed)
+	lastins = p;
+      if (s->repo != pool->installed)
+	MAPSET(&ins, p);
+      if (havescripts(pool, p))
+	{
+	  MAPZERO(&seen);
+	  transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0);
+	}
+      if (s->repo == pool->installed)
+	MAPCLR(&ins, p);
+    }
+  map_free(&seen);
+  map_free(&ins);
+  printf("transaction order check done.\n");
 }
 
+int
+transaction_add_choices(Transaction *trans, Queue *choices, Id chosen)
+{
+  int i, j;
+  struct _TransactionElement *te;
+
+  if (!chosen)
+    {
+      /* initialization step */
+      for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++)
+	te->mark = 0;
+      for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++)
+	{
+	  for (j = te->edges; trans->invedgedata[j]; j++)
+	    trans->tes[trans->invedgedata[j]].mark++;
+	}
+      for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++)
+	if (!te->mark)
+	  {
+	    queue_push(choices, te->type);
+	    queue_push(choices, te->p);
+	  }
+      return choices->count;
+    }
+  for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++)
+    if (te->p == chosen)
+      break;
+  if (i == trans->ntes)
+    return choices->count;
+  if (te->mark > 0)
+    {
+      /* hey! out-of-order installation! */
+      te->mark = -1;
+    }
+  for (j = te->edges; trans->invedgedata[j]; j++)
+    {
+      te = trans->tes + trans->invedgedata[j];
+      assert(te->mark > 0 || te->mark == -1);
+      if (te->mark > 0 && --te->mark == 0)
+	{
+	  queue_push(choices, te->type);
+	  queue_push(choices, te->p);
+	}
+    }
+  return choices->count;
+}
diff --git a/src/transaction.h b/src/transaction.h
index c1f87b8..ea01d02 100644
--- a/src/transaction.h
+++ b/src/transaction.h
@@ -23,12 +23,27 @@ extern "C" {
 
 struct _Pool;
 
+/* internal */
+struct _TransactionElement {
+  Id p;			/* solvable id */
+  Id type;		/* installation type */
+  Id edges;
+  Id mark;
+};
+
 typedef struct _Transaction {
-  struct _Pool *pool;
-  Queue steps;
+  struct _Pool *pool;		/* back pointer to pool */
+
+  Queue steps;			/* the transaction steps */
+
   Queue transaction_info;
   Id *transaction_installed;
   Map transactsmap;
+
+  struct _TransactionElement *tes;
+  int ntes;
+  Id *invedgedata;
+
 } Transaction;
 
 
@@ -62,6 +77,7 @@ extern void solver_transaction_all_pkgs(Transaction *trans, Id p, Queue *pkgs);
 extern Id   solver_transaction_pkg(Transaction *trans, Id p);
 extern Id   solver_transaction_show(Transaction *trans, Id type, Id p, int mode);
 extern void transaction_order(Transaction *trans);
+extern void transaction_check(Transaction *trans);
 
 #ifdef __cplusplus
 }