Imported Upstream version 0.6.35
[platform/upstream/libsolv.git] / src / transaction.c
1 /*
2  * Copyright (c) 2007-2015, SUSE LLC
3  *
4  * This program is licensed under the BSD license, read LICENSE.BSD
5  * for further information
6  */
7
8 /*
9  * transaction.c
10  *
11  * Transaction handling
12  */
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <unistd.h>
17 #include <string.h>
18 #include <assert.h>
19
20 #include "transaction.h"
21 #include "solver.h"
22 #include "bitmap.h"
23 #include "pool.h"
24 #include "poolarch.h"
25 #include "evr.h"
26 #include "util.h"
27
28 static int
29 obsq_sortcmp(const void *ap, const void *bp, void *dp)
30 {
31   Id a, b, oa, ob;
32   Pool *pool = dp;
33   Solvable *s, *oas, *obs;
34   int r;
35
36   a = ((Id *)ap)[0];
37   oa = ((Id *)ap)[1];
38   b = ((Id *)bp)[0];
39   ob = ((Id *)bp)[1];
40   if (a != b)
41     return a - b;
42   if (oa == ob)
43     return 0;
44   s = pool->solvables + a;
45   oas = pool->solvables + oa;
46   obs = pool->solvables + ob;
47   if (oas->name != obs->name)
48     {
49       /* bring "same name" obsoleters (i.e. upgraders) to front */
50       if (oas->name == s->name)
51         return -1;
52       if (obs->name == s->name)
53         return 1;
54       return strcmp(pool_id2str(pool, oas->name), pool_id2str(pool, obs->name));
55     }
56   r = pool_evrcmp(pool, oas->evr, obs->evr, EVRCMP_COMPARE);
57   if (r)
58     return -r;  /* highest version first */
59   if (oas->arch != obs->arch)
60     {
61       /* bring same arch to front */
62       if (oas->arch == s->arch)
63         return -1;
64       if (obs->arch == s->arch)
65         return 1;
66     }
67   return oa - ob;
68 }
69
70 void
71 transaction_all_obs_pkgs(Transaction *trans, Id p, Queue *pkgs)
72 {
73   Pool *pool = trans->pool;
74   Solvable *s = pool->solvables + p;
75   Queue *ti = &trans->transaction_info;
76   Id q;
77   int i;
78
79   queue_empty(pkgs);
80   if (p <= 0 || !s->repo)
81     return;
82   if (s->repo == pool->installed)
83     {
84       q = trans->transaction_installed[p - pool->installed->start];
85       if (!q)
86         return;
87       if (q > 0)
88         {
89           /* only a single obsoleting package */
90           queue_push(pkgs, q);
91           return;
92         }
93       /* find which packages obsolete us */
94       for (i = 0; i < ti->count; i += 2)
95         if (ti->elements[i + 1] == p)
96           queue_push2(pkgs, p, ti->elements[i]);
97       /* sort obsoleters */
98       if (pkgs->count > 2)
99         solv_sort(pkgs->elements, pkgs->count / 2, 2 * sizeof(Id), obsq_sortcmp, pool);
100       for (i = 0; i < pkgs->count; i += 2)
101         pkgs->elements[i / 2] = pkgs->elements[i + 1];
102       queue_truncate(pkgs, pkgs->count / 2);
103     }
104   else
105     {
106       /* find the packages we obsolete */
107       for (i = 0; i < ti->count; i += 2)
108         {
109           if (ti->elements[i] == p)
110             queue_push(pkgs, ti->elements[i + 1]);
111           else if (pkgs->count)
112             break;
113         }
114     }
115 }
116
117 Id
118 transaction_obs_pkg(Transaction *trans, Id p)
119 {
120   Pool *pool = trans->pool;
121   Solvable *s = pool->solvables + p;
122   Queue *ti;
123   int i;
124
125   if (p <= 0 || !s->repo)
126     return 0;
127   if (s->repo == pool->installed)
128     {
129       p = trans->transaction_installed[p - pool->installed->start];
130       return p < 0 ? -p : p;
131     }
132   ti = &trans->transaction_info;
133   for (i = 0; i < ti->count; i += 2)
134     if (ti->elements[i] == p)
135       return ti->elements[i + 1];
136   return 0;
137 }
138
139
140 /*
141  * calculate base type of transaction element
142  */
143
144 static Id
145 transaction_base_type(Transaction *trans, Id p)
146 {
147   Pool *pool = trans->pool;
148   Solvable *s, *s2;
149   int r;
150   Id p2;
151
152   if (!MAPTST(&trans->transactsmap, p))
153     return SOLVER_TRANSACTION_IGNORE;
154   p2 = transaction_obs_pkg(trans, p);
155   if (pool->installed && pool->solvables[p].repo == pool->installed)
156     {
157       /* erase */
158       if (!p2)
159         return SOLVER_TRANSACTION_ERASE;
160       s = pool->solvables + p;
161       s2 = pool->solvables + p2;
162       if (s->name == s2->name)
163         {
164           if (s->evr == s2->evr && solvable_identical(s, s2))
165             return SOLVER_TRANSACTION_REINSTALLED;
166           r = pool_evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
167           if (r < 0)
168             return SOLVER_TRANSACTION_UPGRADED;
169           else if (r > 0)
170             return SOLVER_TRANSACTION_DOWNGRADED;
171           return SOLVER_TRANSACTION_CHANGED;
172         }
173       return SOLVER_TRANSACTION_OBSOLETED;
174     }
175   else
176     {
177       /* install or multiinstall */
178       int multi = trans->multiversionmap.size && MAPTST(&trans->multiversionmap, p);
179       if (multi)
180         {
181           if (p2)
182             {
183               s = pool->solvables + p;
184               s2 = pool->solvables + p2;
185               if (s->name == s2->name && s->arch == s2->arch && s->evr == s2->evr)
186                 return SOLVER_TRANSACTION_MULTIREINSTALL;
187             }
188           return SOLVER_TRANSACTION_MULTIINSTALL;
189         }
190       if (!p2)
191         return SOLVER_TRANSACTION_INSTALL;
192       s = pool->solvables + p;
193       s2 = pool->solvables + p2;
194       if (s->name == s2->name)
195         {
196           if (s->evr == s2->evr && solvable_identical(s, s2))
197             return SOLVER_TRANSACTION_REINSTALL;
198           r = pool_evrcmp(pool, s->evr, s2->evr, EVRCMP_COMPARE);
199           if (r > 0)
200             return SOLVER_TRANSACTION_UPGRADE;
201           else if (r < 0)
202             return SOLVER_TRANSACTION_DOWNGRADE;
203           else
204             return SOLVER_TRANSACTION_CHANGE;
205         }
206       return SOLVER_TRANSACTION_OBSOLETES;
207     }
208 }
209
210 /* these packages do not get installed by the package manager */
211 static inline int
212 is_pseudo_package(Pool *pool, Solvable *s)
213 {
214   const char *n = pool_id2str(pool, s->name);
215   if (*n == 'p' && !strncmp(n, "patch:", 6))
216     return 1;
217   if (*n == 'p' && !strncmp(n, "pattern:", 8))
218     return 1;
219   if (*n == 'p' && !strncmp(n, "product:", 8))
220     return 1;
221   if (*n == 'a' && !strncmp(n, "application:", 12))
222     return 1;
223   return 0;
224 }
225
226 /* these packages will never show up installed */
227 static inline int
228 is_noinst_pseudo_package(Pool *pool, Solvable *s)
229 {
230   const char *n = pool_id2str(pool, s->name);
231   if (!strncmp(n, "patch:", 6))
232     return 1;
233   if (!strncmp(n, "pattern:", 8))
234     {
235 #if defined(SUSE) && defined(ENABLE_LINKED_PKGS)
236       /* unlike normal patterns, autopatterns *can* be installed (via the package link),
237          so do not filter them */
238       if (s->provides)
239         {
240           Id prv, *prvp = s->repo->idarraydata + s->provides;
241           while ((prv = *prvp++) != 0)
242             if (ISRELDEP(prv) && !strcmp(pool_id2str(pool, prv), "autopattern()"))
243               return 0;
244         }
245 #endif
246       return 1;
247     }
248   return 0;
249 }
250
251 static int
252 obsoleted_by_pseudos_only(Transaction *trans, Id p)
253 {
254   Pool *pool = trans->pool;
255   Queue q;
256   Id op;
257   int i;
258
259   op = transaction_obs_pkg(trans, p);
260   if (op && !is_pseudo_package(pool, pool->solvables + op))
261     return 0;
262   queue_init(&q);
263   transaction_all_obs_pkgs(trans, p, &q);
264   for (i = 0; i < q.count; i++)
265     if (!is_pseudo_package(pool, pool->solvables + q.elements[i]))
266       break;
267   i = !q.count || i < q.count ? 0 : 1;
268   queue_free(&q);
269   return i;
270 }
271
272 /*
273  * return type of transaction element
274  *
275  * filtering is needed if either not all packages are shown
276  * or replaces are not shown, as otherwise parts of the
277  * transaction might not be shown to the user */
278
279 Id
280 transaction_type(Transaction *trans, Id p, int mode)
281 {
282   Pool *pool = trans->pool;
283   Solvable *s = pool->solvables + p;
284   Queue oq, rq;
285   Id type, q;
286   int i, j, ref = 0;
287
288   if (!s->repo)
289     return SOLVER_TRANSACTION_IGNORE;
290
291   /* XXX: SUSE only? */
292   if (!(mode & SOLVER_TRANSACTION_KEEP_PSEUDO) && is_noinst_pseudo_package(pool, s))
293     return SOLVER_TRANSACTION_IGNORE;
294
295   type = transaction_base_type(trans, p);
296
297   if (type == SOLVER_TRANSACTION_IGNORE)
298     return SOLVER_TRANSACTION_IGNORE;   /* not part of the transaction */
299
300   if ((mode & SOLVER_TRANSACTION_RPM_ONLY) != 0)
301     {
302       /* application wants to know what to feed to the package manager */
303       if (!(mode & SOLVER_TRANSACTION_KEEP_PSEUDO) && is_pseudo_package(pool, s))
304         return SOLVER_TRANSACTION_IGNORE;
305       if (type == SOLVER_TRANSACTION_ERASE || type == SOLVER_TRANSACTION_INSTALL || type == SOLVER_TRANSACTION_MULTIINSTALL)
306         return type;
307       if (s->repo == pool->installed)
308         {
309           /* check if we're a real package that is obsoleted by pseudos */
310           if (!is_pseudo_package(pool, s) && obsoleted_by_pseudos_only(trans, s - pool->solvables))
311             return SOLVER_TRANSACTION_ERASE;
312           return SOLVER_TRANSACTION_IGNORE;     /* ignore as we're being obsoleted */
313         }
314       if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
315         return SOLVER_TRANSACTION_MULTIINSTALL;
316       return SOLVER_TRANSACTION_INSTALL;
317     }
318
319   if ((mode & SOLVER_TRANSACTION_SHOW_MULTIINSTALL) == 0)
320     {
321       /* application wants to make no difference between install
322        * and multiinstall */
323       if (type == SOLVER_TRANSACTION_MULTIINSTALL)
324         type = SOLVER_TRANSACTION_INSTALL;
325       if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
326         type = SOLVER_TRANSACTION_REINSTALL;
327     }
328
329   if ((mode & SOLVER_TRANSACTION_CHANGE_IS_REINSTALL) != 0)
330     {
331       /* application wants to make no difference between change
332        * and reinstall */
333       if (type == SOLVER_TRANSACTION_CHANGED)
334         type = SOLVER_TRANSACTION_REINSTALLED;
335       else if (type == SOLVER_TRANSACTION_CHANGE)
336         type = SOLVER_TRANSACTION_REINSTALL;
337     }
338
339   if (type == SOLVER_TRANSACTION_ERASE || type == SOLVER_TRANSACTION_INSTALL || type == SOLVER_TRANSACTION_MULTIINSTALL)
340     return type;
341
342   if (s->repo == pool->installed && (mode & SOLVER_TRANSACTION_SHOW_ACTIVE) == 0)
343     {
344       /* erase element and we're showing the passive side */
345       if (type == SOLVER_TRANSACTION_OBSOLETED && (mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
346         type = SOLVER_TRANSACTION_ERASE;
347       if (type == SOLVER_TRANSACTION_OBSOLETED && (mode & SOLVER_TRANSACTION_OBSOLETE_IS_UPGRADE) != 0)
348         type = SOLVER_TRANSACTION_UPGRADED;
349       return type;
350     }
351   if (s->repo != pool->installed && (mode & SOLVER_TRANSACTION_SHOW_ACTIVE) != 0)
352     {
353       /* install element and we're showing the active side */
354       if (type == SOLVER_TRANSACTION_OBSOLETES && (mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
355         type = SOLVER_TRANSACTION_INSTALL;
356       if (type == SOLVER_TRANSACTION_OBSOLETES && (mode & SOLVER_TRANSACTION_OBSOLETE_IS_UPGRADE) != 0)
357         type = SOLVER_TRANSACTION_UPGRADE;
358       return type;
359     }
360
361   /* the element doesn't match the show mode */
362
363   /* if we're showing all references, we can ignore this package */
364   if ((mode & (SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES)) == (SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES))
365     return SOLVER_TRANSACTION_IGNORE;
366
367   /* we're not showing all refs. check if some other package
368    * references us. If yes, it's safe to ignore this package,
369    * otherwise we need to map the type */
370
371   /* most of the time there's only one reference, so check it first */
372   q = transaction_obs_pkg(trans, p);
373
374   if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
375     {
376       Solvable *sq = pool->solvables + q;
377       if (sq->name != s->name)
378         {
379           /* it's a replace but we're not showing replaces. map type. */
380           if (s->repo == pool->installed)
381             return SOLVER_TRANSACTION_ERASE;
382           else if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
383             return SOLVER_TRANSACTION_MULTIINSTALL;
384           else
385             return SOLVER_TRANSACTION_INSTALL;
386         }
387     }
388
389   /* if there's a match, p will be shown when q
390    * is processed */
391   if (transaction_obs_pkg(trans, q) == p)
392     return SOLVER_TRANSACTION_IGNORE;
393
394   /* too bad, a miss. check em all */
395   queue_init(&oq);
396   queue_init(&rq);
397   transaction_all_obs_pkgs(trans, p, &oq);
398   for (i = 0; i < oq.count; i++)
399     {
400       q = oq.elements[i];
401       if ((mode & SOLVER_TRANSACTION_SHOW_OBSOLETES) == 0)
402         {
403           Solvable *sq = pool->solvables + q;
404           if (sq->name != s->name)
405             continue;
406         }
407       /* check if we are referenced? */
408       if ((mode & SOLVER_TRANSACTION_SHOW_ALL) != 0)
409         {
410           transaction_all_obs_pkgs(trans, q, &rq);
411           for (j = 0; j < rq.count; j++)
412             if (rq.elements[j] == p)
413               {
414                 ref = 1;
415                 break;
416               }
417           if (ref)
418             break;
419         }
420       else if (transaction_obs_pkg(trans, q) == p)
421         {
422           ref = 1;
423           break;
424         }
425     }
426   queue_free(&oq);
427   queue_free(&rq);
428
429   if (!ref)
430     {
431       /* we're not referenced. map type */
432       if (s->repo == pool->installed)
433         return SOLVER_TRANSACTION_ERASE;
434       else if (type == SOLVER_TRANSACTION_MULTIREINSTALL)
435         return SOLVER_TRANSACTION_MULTIINSTALL;
436       else
437         return SOLVER_TRANSACTION_INSTALL;
438     }
439   /* there was a ref, so p is shown with some other package */
440   return SOLVER_TRANSACTION_IGNORE;
441 }
442
443
444
445 static int
446 classify_cmp(const void *ap, const void *bp, void *dp)
447 {
448   Transaction *trans = dp;
449   Pool *pool = trans->pool;
450   const Id *a = ap;
451   const Id *b = bp;
452   int r;
453
454   r = a[0] - b[0];
455   if (r)
456     return r;
457   r = a[2] - b[2];
458   if (r)
459     return a[2] && b[2] ? strcmp(pool_id2str(pool, a[2]), pool_id2str(pool, b[2])) : r;
460   r = a[3] - b[3];
461   if (r)
462     return a[3] && b[3] ? strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3])) : r;
463   return 0;
464 }
465
466 static int
467 classify_cmp_pkgs(const void *ap, const void *bp, void *dp)
468 {
469   Transaction *trans = dp;
470   Pool *pool = trans->pool;
471   Id a = *(Id *)ap;
472   Id b = *(Id *)bp;
473   Solvable *sa, *sb;
474
475   sa = pool->solvables + a;
476   sb = pool->solvables + b;
477   if (sa->name != sb->name)
478     return strcmp(pool_id2str(pool, sa->name), pool_id2str(pool, sb->name));
479   if (sa->evr != sb->evr)
480     {
481       int r = pool_evrcmp(pool, sa->evr, sb->evr, EVRCMP_COMPARE);
482       if (r)
483         return r;
484     }
485   return a - b;
486 }
487
488 static inline void
489 queue_push4(Queue *q, Id id1, Id id2, Id id3, Id id4)
490 {
491   queue_push(q, id1);
492   queue_push(q, id2);
493   queue_push(q, id3);
494   queue_push(q, id4);
495 }
496
497 static inline void
498 queue_unshift4(Queue *q, Id id1, Id id2, Id id3, Id id4)
499 {
500   queue_unshift(q, id4);
501   queue_unshift(q, id3);
502   queue_unshift(q, id2);
503   queue_unshift(q, id1);
504 }
505
506 void
507 transaction_classify(Transaction *trans, int mode, Queue *classes)
508 {
509   Pool *pool = trans->pool;
510   int ntypes[SOLVER_TRANSACTION_MAXTYPE + 1];
511   Solvable *s, *sq;
512   Id v, vq, type, p, q;
513   int i, j;
514
515   queue_empty(classes);
516   memset(ntypes, 0, sizeof(ntypes));
517   /* go through transaction and classify each step */
518   for (i = 0; i < trans->steps.count; i++)
519     {
520       p = trans->steps.elements[i];
521       s = pool->solvables + p;
522       type = transaction_type(trans, p, mode);
523       ntypes[type]++;
524       if (!pool->installed || s->repo != pool->installed)
525         continue;
526       /* don't report vendor/arch changes if we were mapped to erase. */
527       if (type == SOLVER_TRANSACTION_ERASE)
528         continue;
529       /* look at arch/vendor changes */
530       q = transaction_obs_pkg(trans, p);
531       if (!q)
532         continue;
533       sq = pool->solvables + q;
534
535       v = s->arch;
536       vq = sq->arch;
537       if (v != vq)
538         {
539           if ((mode & SOLVER_TRANSACTION_MERGE_ARCHCHANGES) != 0)
540             v = vq = 0;
541           for (j = 0; j < classes->count; j += 4)
542             if (classes->elements[j] == SOLVER_TRANSACTION_ARCHCHANGE && classes->elements[j + 2] == v && classes->elements[j + 3] == vq)
543               break;
544           if (j == classes->count)
545             queue_push4(classes, SOLVER_TRANSACTION_ARCHCHANGE, 1, v, vq);
546           else
547             classes->elements[j + 1]++;
548         }
549
550       v = s->vendor ? s->vendor : 1;
551       vq = sq->vendor ? sq->vendor : 1;
552       if (v != vq)
553         {
554           if ((mode & SOLVER_TRANSACTION_MERGE_VENDORCHANGES) != 0)
555             v = vq = 0;
556           for (j = 0; j < classes->count; j += 4)
557             if (classes->elements[j] == SOLVER_TRANSACTION_VENDORCHANGE && classes->elements[j + 2] == v && classes->elements[j + 3] == vq)
558               break;
559           if (j == classes->count)
560             queue_push4(classes, SOLVER_TRANSACTION_VENDORCHANGE, 1, v, vq);
561           else
562             classes->elements[j + 1]++;
563         }
564     }
565   /* now sort all vendor/arch changes */
566   if (classes->count > 4)
567     solv_sort(classes->elements, classes->count / 4, 4 * sizeof(Id), classify_cmp, trans);
568   /* finally add all classes. put erases last */
569   i = SOLVER_TRANSACTION_ERASE;
570   if (ntypes[i])
571     queue_unshift4(classes, i, ntypes[i], 0, 0);
572   for (i = SOLVER_TRANSACTION_MAXTYPE; i > 0; i--)
573     {
574       if (!ntypes[i])
575         continue;
576       if (i == SOLVER_TRANSACTION_ERASE)
577         continue;
578       queue_unshift4(classes, i, ntypes[i], 0, 0);
579     }
580 }
581
582 void
583 transaction_classify_pkgs(Transaction *trans, int mode, Id class, Id from, Id to, Queue *pkgs)
584 {
585   Pool *pool = trans->pool;
586   int i;
587   Id type, p, q;
588   Solvable *s, *sq;
589
590   queue_empty(pkgs);
591   for (i = 0; i < trans->steps.count; i++)
592     {
593       p = trans->steps.elements[i];
594       s = pool->solvables + p;
595       if (class <= SOLVER_TRANSACTION_MAXTYPE)
596         {
597           type = transaction_type(trans, p, mode);
598           if (type == class)
599             queue_push(pkgs, p);
600           continue;
601         }
602       if (!pool->installed || s->repo != pool->installed)
603         continue;
604       q = transaction_obs_pkg(trans, p);
605       if (!q)
606         continue;
607       sq = pool->solvables + q;
608       if (class == SOLVER_TRANSACTION_ARCHCHANGE)
609         {
610           if ((!from && !to) || (s->arch == from && sq->arch == to))
611             queue_push(pkgs, p);
612           continue;
613         }
614       if (class == SOLVER_TRANSACTION_VENDORCHANGE)
615         {
616           Id v = s->vendor ? s->vendor : 1;
617           Id vq = sq->vendor ? sq->vendor : 1;
618           if ((!from && !to) || (v == from && vq == to))
619             queue_push(pkgs, p);
620           continue;
621         }
622     }
623   if (pkgs->count > 1)
624     solv_sort(pkgs->elements, pkgs->count, sizeof(Id), classify_cmp_pkgs, trans);
625 }
626
627 static void
628 create_transaction_info(Transaction *trans, Queue *decisionq)
629 {
630   Pool *pool = trans->pool;
631   Queue *ti = &trans->transaction_info;
632   Repo *installed = pool->installed;
633   int i, j, multi;
634   Id p, p2, pp2;
635   Solvable *s, *s2;
636
637   queue_empty(ti);
638   trans->transaction_installed = solv_free(trans->transaction_installed);
639   if (!installed)
640     return;     /* no info needed */
641   for (i = 0; i < decisionq->count; i++)
642     {
643       p = decisionq->elements[i];
644       if (p <= 0 || p == SYSTEMSOLVABLE)
645         continue;
646       s = pool->solvables + p;
647       if (!s->repo || s->repo == installed)
648         continue;
649       multi = trans->multiversionmap.size && MAPTST(&trans->multiversionmap, p);
650       FOR_PROVIDES(p2, pp2, s->name)
651         {
652           if (!MAPTST(&trans->transactsmap, p2))
653             continue;
654           s2 = pool->solvables + p2;
655           if (s2->repo != installed)
656             continue;
657           if (multi && (s->name != s2->name || s->evr != s2->evr || s->arch != s2->arch))
658             continue;
659           if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
660             continue;
661           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, s2))
662             continue;
663           queue_push2(ti, p, p2);
664         }
665       if (s->obsoletes && !multi)
666         {
667           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
668           while ((obs = *obsp++) != 0)
669             {
670               FOR_PROVIDES(p2, pp2, obs)
671                 {
672                   if (!MAPTST(&trans->transactsmap, p2))
673                     continue;
674                   s2 = pool->solvables + p2;
675                   if (s2->repo != installed)
676                     continue;
677                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, s2, obs))
678                     continue;
679                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
680                     continue;
681                   queue_push2(ti, p, p2);
682                 }
683             }
684         }
685     }
686   if (ti->count > 2)
687     {
688       /* sort and unify */
689       solv_sort(ti->elements, ti->count / 2, 2 * sizeof(Id), obsq_sortcmp, pool);
690       for (i = j = 2; i < ti->count; i += 2)
691         {
692           if (ti->elements[i] == ti->elements[j - 2] && ti->elements[i + 1] == ti->elements[j - 1])
693             continue;
694           ti->elements[j++] = ti->elements[i];
695           ti->elements[j++] = ti->elements[i + 1];
696         }
697       queue_truncate(ti, j);
698     }
699
700   /* create transaction_installed helper */
701   /*   entry > 0: exactly one obsoleter, entry < 0: multiple obsoleters, -entry is "best" */
702   trans->transaction_installed = solv_calloc(installed->end - installed->start, sizeof(Id));
703   for (i = 0; i < ti->count; i += 2)
704     {
705       j = ti->elements[i + 1] - installed->start;
706       if (!trans->transaction_installed[j])
707         trans->transaction_installed[j] = ti->elements[i];
708       else
709         {
710           /* more than one package obsoletes us. compare to find "best" */
711           Id q[4];
712           if (trans->transaction_installed[j] > 0)
713             trans->transaction_installed[j] = -trans->transaction_installed[j];
714           q[0] = q[2] = ti->elements[i + 1];
715           q[1] = ti->elements[i];
716           q[3] = -trans->transaction_installed[j];
717           if (obsq_sortcmp(q, q + 2, pool) < 0)
718             trans->transaction_installed[j] = -ti->elements[i];
719         }
720     }
721 }
722
723 /* create a transaction from the decisionq */
724 Transaction *
725 transaction_create_decisionq(Pool *pool, Queue *decisionq, Map *multiversionmap)
726 {
727   Repo *installed = pool->installed;
728   int i, needmulti;
729   Id p;
730   Solvable *s;
731   Transaction *trans;
732
733   trans = transaction_create(pool);
734   if (multiversionmap && !multiversionmap->size)
735     multiversionmap = 0;        /* ignore empty map */
736   queue_empty(&trans->steps);
737   map_init(&trans->transactsmap, pool->nsolvables);
738   needmulti = 0;
739   for (i = 0; i < decisionq->count; i++)
740     {
741       p = decisionq->elements[i];
742       s = pool->solvables + (p > 0 ? p : -p);
743       if (!s->repo)
744         continue;
745       if (installed && s->repo == installed && p < 0)
746         MAPSET(&trans->transactsmap, -p);
747       if (!(installed && s->repo == installed) && p > 0)
748         {
749           MAPSET(&trans->transactsmap, p);
750           if (multiversionmap && MAPTST(multiversionmap, p))
751             needmulti = 1;
752         }
753     }
754   MAPCLR(&trans->transactsmap, SYSTEMSOLVABLE);
755   if (needmulti)
756     map_init_clone(&trans->multiversionmap, multiversionmap);
757
758   create_transaction_info(trans, decisionq);
759
760   if (installed)
761     {
762       FOR_REPO_SOLVABLES(installed, p, s)
763         {
764           if (MAPTST(&trans->transactsmap, p))
765             queue_push(&trans->steps, p);
766         }
767     }
768   for (i = 0; i < decisionq->count; i++)
769     {
770       p = decisionq->elements[i];
771       if (p > 0 && MAPTST(&trans->transactsmap, p))
772         queue_push(&trans->steps, p);
773     }
774   return trans;
775 }
776
777 int
778 transaction_installedresult(Transaction *trans, Queue *installedq)
779 {
780   Pool *pool = trans->pool;
781   Repo *installed = pool->installed;
782   Solvable *s;
783   int i, cutoff;
784   Id p;
785
786   queue_empty(installedq);
787   /* first the new installs, than the kept packages */
788   for (i = 0; i < trans->steps.count; i++)
789     {
790       p = trans->steps.elements[i];
791       s = pool->solvables + p;
792       if (installed && s->repo == installed)
793         continue;
794       queue_push(installedq, p);
795     }
796   cutoff = installedq->count;
797   if (installed)
798     {
799       FOR_REPO_SOLVABLES(installed, p, s)
800         if (!MAPTST(&trans->transactsmap, p))
801           queue_push(installedq, p);
802     }
803   return cutoff;
804 }
805
806 static void
807 transaction_make_installedmap(Transaction *trans, Map *installedmap)
808 {
809   Pool *pool = trans->pool;
810   Repo *installed = pool->installed;
811   Solvable *s;
812   Id p;
813   int i;
814
815   map_init(installedmap, pool->nsolvables);
816   for (i = 0; i < trans->steps.count; i++)
817     {
818       p = trans->steps.elements[i];
819       s = pool->solvables + p;
820       if (!installed || s->repo != installed)
821         MAPSET(installedmap, p);
822     }
823   if (installed)
824     {
825       FOR_REPO_SOLVABLES(installed, p, s)
826         if (!MAPTST(&trans->transactsmap, p))
827           MAPSET(installedmap, p);
828     }
829 }
830
831 int
832 transaction_calc_installsizechange(Transaction *trans)
833 {
834   Map installedmap;
835   int change;
836
837   transaction_make_installedmap(trans, &installedmap);
838   change = pool_calc_installsizechange(trans->pool, &installedmap);
839   map_free(&installedmap);
840   return change;
841 }
842
843 void
844 transaction_calc_duchanges(Transaction *trans, DUChanges *mps, int nmps)
845 {
846   Map installedmap;
847
848   transaction_make_installedmap(trans, &installedmap);
849   pool_calc_duchanges(trans->pool, &installedmap, mps, nmps);
850   map_free(&installedmap);
851 }
852
853 Transaction *
854 transaction_create(Pool *pool)
855 {
856   Transaction *trans = solv_calloc(1, sizeof(*trans));
857   trans->pool = pool;
858   return trans;
859 }
860
861 Transaction *
862 transaction_create_clone(Transaction *srctrans)
863 {
864   Transaction *trans = transaction_create(srctrans->pool);
865   queue_init_clone(&trans->steps, &srctrans->steps);
866   queue_init_clone(&trans->transaction_info, &srctrans->transaction_info);
867   if (srctrans->transaction_installed)
868     {
869       Repo *installed = srctrans->pool->installed;
870       trans->transaction_installed = solv_memdup2(srctrans->transaction_installed, installed->end - installed->start, sizeof(Id));
871     }
872   map_init_clone(&trans->transactsmap, &srctrans->transactsmap);
873   map_init_clone(&trans->multiversionmap, &srctrans->multiversionmap);
874   if (srctrans->orderdata)
875     transaction_clone_orderdata(trans, srctrans);
876   return trans;
877 }
878
879 void
880 transaction_free(Transaction *trans)
881 {
882   queue_free(&trans->steps);
883   queue_free(&trans->transaction_info);
884   trans->transaction_installed = solv_free(trans->transaction_installed);
885   map_free(&trans->transactsmap);
886   map_free(&trans->multiversionmap);
887   if (trans->orderdata)
888     transaction_free_orderdata(trans);
889   free(trans);
890 }
891