apt  2.2.4
About: Apt (Advanced Package Tool) is a management system for software packages (Debian/Ubuntu). Release series 2.2.
  Fossies Dox: apt-2.2.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

algorithms.cc
Go to the documentation of this file.
1 // -*- mode: cpp; mode: fold -*-
2 // Description /*{{{*/
3 /* ######################################################################
4 
5  Algorithms - A set of misc algorithms
6 
7  The pkgProblemResolver class has become insanely complex and
8  very sophisticated, it handles every test case I have thrown at it
9  to my satisfaction. Understanding exactly why all the steps the class
10  does are required is difficult and changing though not very risky
11  may result in other cases not working.
12 
13  ##################################################################### */
14  /*}}}*/
15 // Include Files /*{{{*/
16 #include <config.h>
17 
18 #include <apt-pkg/algorithms.h>
19 #include <apt-pkg/cachefilter.h>
20 #include <apt-pkg/configuration.h>
21 #include <apt-pkg/depcache.h>
22 #include <apt-pkg/dpkgpm.h>
23 #include <apt-pkg/edsp.h>
24 #include <apt-pkg/error.h>
25 #include <apt-pkg/macros.h>
26 #include <apt-pkg/packagemanager.h>
27 #include <apt-pkg/pkgcache.h>
28 #include <apt-pkg/string_view.h>
29 #include <apt-pkg/strutl.h>
30 #include <apt-pkg/version.h>
31 
32 #include <apt-pkg/prettyprinters.h>
33 
34 #include <cstdlib>
35 #include <iostream>
36 #include <map>
37 #include <set>
38 #include <sstream>
39 #include <string>
40 #include <utility>
41 #include <vector>
42 #include <string.h>
43 #include <sys/utsname.h>
44 
45 #include <apti18n.h>
46  /*}}}*/
47 using namespace std;
48 
50 {
51 public:
52  std::vector<pkgDPkgPM::Item> List;
53 };
54 // Simulate::Simulate - Constructor /*{{{*/
55 // ---------------------------------------------------------------------
56 /* The legacy translations here of input Pkg iterators is obsolete,
57  this is not necessary since the pkgCaches are fully shared now. */
59  d(new pkgSimulatePrivate()), iPolicy(Cache),
60  Sim(&Cache->GetCache(),&iPolicy),
61  group(Sim)
62 {
63  Sim.Init(0);
64  auto PackageCount = Cache->Head().PackageCount;
65  Flags = new unsigned char[PackageCount];
66  memset(Flags,0,sizeof(*Flags)*PackageCount);
67 
68  // Fake a filename so as not to activate the media swapping
69  string Jnk = "SIMULATE";
70  for (decltype(PackageCount) I = 0; I != PackageCount; ++I)
71  FileNames[I] = Jnk;
72 
73  Cache->CheckConsistency("simulate");
74 }
75  /*}}}*/
76 // Simulate::~Simulate - Destructor /*{{{*/
78 {
79  delete[] Flags;
80  delete d;
81 }
82  /*}}}*/
83 // Simulate::Describe - Describe a package /*{{{*/
84 // ---------------------------------------------------------------------
85 /* Parameter Current == true displays the current package version,
86  Parameter Candidate == true displays the candidate package version */
87 void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
88 {
89  VerIterator Ver(Sim);
90 
91  out << Pkg.FullName(true);
92 
93  if (Current == true)
94  {
95  Ver = Pkg.CurrentVer();
96  if (Ver.end() == false)
97  out << " [" << Ver.VerStr() << ']';
98  }
99 
100  if (Candidate == true)
101  {
102  Ver = Sim[Pkg].CandidateVerIter(Sim);
103  if (Ver.end() == true)
104  return;
105 
106  out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
107  }
108 }
109  /*}}}*/
110 // Simulate::Install - Simulate unpacking of a package /*{{{*/
111 // ---------------------------------------------------------------------
112 /* */
113 bool pkgSimulate::Install(PkgIterator iPkg,string File)
114 {
115  if (iPkg.end() || File.empty())
116  return false;
117  d->List.emplace_back(pkgDPkgPM::Item::Install, iPkg, File);
118  return true;
119 }
120 bool pkgSimulate::RealInstall(PkgIterator iPkg,string /*File*/)
121 {
122  // Adapt the iterator
123  PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
124  Flags[Pkg->ID] = 1;
125 
126  cout << "Inst ";
127  Describe(Pkg,cout,true,true);
128  Sim.MarkInstall(Pkg,false);
129 
130  // Look for broken conflicts+predepends.
131  for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
132  {
133  if (Sim[I].InstallVer == 0)
134  continue;
135 
136  for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
137  {
138  DepIterator Start;
139  DepIterator End;
140  D.GlobOr(Start,End);
141  if (Start.IsNegative() == true ||
142  End->Type == pkgCache::Dep::PreDepends)
143  {
144  if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
145  {
146  cout << " [" << I.FullName(false) << " on " << Start.TargetPkg().FullName(false) << ']';
147  if (Start->Type == pkgCache::Dep::Conflicts)
148  _error->Error("Fatal, conflicts violated %s",I.FullName(false).c_str());
149  }
150  }
151  }
152  }
153 
154  if (Sim.BrokenCount() != 0)
155  ShortBreaks();
156  else
157  cout << endl;
158  return true;
159 }
160  /*}}}*/
161 // Simulate::Configure - Simulate configuration of a Package /*{{{*/
162 // ---------------------------------------------------------------------
163 /* This is not an accurate simulation of relatity, we should really not
164  install the package.. For some investigations it may be necessary
165  however. */
167 {
168  if (iPkg.end())
169  return false;
170  d->List.emplace_back(pkgDPkgPM::Item::Configure, iPkg);
171  return true;
172 }
174 {
175  // Adapt the iterator
176  PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
177 
178  Flags[Pkg->ID] = 2;
179 
180  if (Sim[Pkg].InstBroken() == true)
181  {
182  cout << "Conf " << Pkg.FullName(false) << " broken" << endl;
183 
184  Sim.Update();
185 
186  // Print out each package and the failed dependencies
187  for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; ++D)
188  {
189  if (Sim.IsImportantDep(D) == false ||
190  (Sim[D] & pkgDepCache::DepInstall) != 0)
191  continue;
192 
193  if (D->Type == pkgCache::Dep::Obsoletes)
194  cout << " Obsoletes:" << D.TargetPkg().FullName(false);
195  else if (D->Type == pkgCache::Dep::Conflicts)
196  cout << " Conflicts:" << D.TargetPkg().FullName(false);
197  else if (D->Type == pkgCache::Dep::DpkgBreaks)
198  cout << " Breaks:" << D.TargetPkg().FullName(false);
199  else
200  cout << " Depends:" << D.TargetPkg().FullName(false);
201  }
202  cout << endl;
203 
204  _error->Error("Conf Broken %s",Pkg.FullName(false).c_str());
205  }
206  else
207  {
208  cout << "Conf ";
209  Describe(Pkg,cout,false,true);
210  }
211 
212  if (Sim.BrokenCount() != 0)
213  ShortBreaks();
214  else
215  cout << endl;
216 
217  return true;
218 }
219  /*}}}*/
220 // Simulate::Remove - Simulate the removal of a package /*{{{*/
221 // ---------------------------------------------------------------------
222 /* */
223 bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
224 {
225  if (iPkg.end())
226  return false;
227  d->List.emplace_back(Purge ? pkgDPkgPM::Item::Purge : pkgDPkgPM::Item::Remove, iPkg);
228  return true;
229 }
231 {
232  // Adapt the iterator
233  PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
234  if (Pkg.end() == true)
235  {
236  std::cerr << (Purge ? "Purg" : "Remv") << " invalid package " << iPkg.FullName() << std::endl;
237  return false;
238  }
239 
240  Flags[Pkg->ID] = 3;
241  Sim.MarkDelete(Pkg);
242 
243  if (Purge == true)
244  cout << "Purg ";
245  else
246  cout << "Remv ";
247  Describe(Pkg,cout,true,false);
248 
249  if (Sim.BrokenCount() != 0)
250  ShortBreaks();
251  else
252  cout << endl;
253 
254  return true;
255 }
256  /*}}}*/
257 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
258 // ---------------------------------------------------------------------
259 /* */
261 {
262  cout << " [";
263  for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
264  {
265  if (Sim[I].InstBroken() == true)
266  {
267  if (Flags[I->ID] == 0)
268  cout << I.FullName(false) << ' ';
269 /* else
270  cout << I.Name() << "! ";*/
271  }
272  }
273  cout << ']' << endl;
274 }
275  /*}}}*/
277 {
278  if (pkgDPkgPM::ExpandPendingCalls(d->List, Cache) == false)
279  return false;
280  for (auto && I : d->List)
281  switch (I.Op)
282  {
284  if (RealInstall(I.Pkg, I.File) == false)
285  return false;
286  break;
288  if (RealConfigure(I.Pkg) == false)
289  return false;
290  break;
292  if (RealRemove(I.Pkg, false) == false)
293  return false;
294  break;
296  if (RealRemove(I.Pkg, true) == false)
297  return false;
298  break;
303  return _error->Error("Internal error, simulation encountered unexpected pending item");
304  }
305  return true;
306 }
307  /*}}}*/
308 // ApplyStatus - Adjust for non-ok packages /*{{{*/
309 // ---------------------------------------------------------------------
310 /* We attempt to change the state of the all packages that have failed
311  installation toward their real state. The ordering code will perform
312  the necessary calculations to deal with the problems. */
314 {
315  pkgDepCache::ActionGroup group(Cache);
316 
317  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
318  {
319  if (I->VersionList == 0)
320  continue;
321 
322  // Only choice for a ReInstReq package is to reinstall
323  if (I->InstState == pkgCache::State::ReInstReq ||
324  I->InstState == pkgCache::State::HoldReInstReq)
325  {
326  if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
327  Cache.MarkKeep(I, false, false);
328  else
329  {
330  // Is this right? Will dpkg choke on an upgrade?
331  if (Cache[I].CandidateVer != 0 &&
332  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
333  Cache.MarkInstall(I, false, 0, false);
334  else
335  return _error->Error(_("The package %s needs to be reinstalled, "
336  "but I can't find an archive for it."),I.FullName(true).c_str());
337  }
338 
339  continue;
340  }
341 
342  switch (I->CurrentState)
343  {
344  /* This means installation failed somehow - it does not need to be
345  re-unpacked (probably) */
350  if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
351  I.State() != pkgCache::PkgIterator::NeedsUnpack)
352  Cache.MarkKeep(I, false, false);
353  else
354  {
355  if (Cache[I].CandidateVer != 0 &&
356  Cache[I].CandidateVerIter(Cache).Downloadable() == true)
357  Cache.MarkInstall(I, true, 0, false);
358  else
359  Cache.MarkDelete(I, false, 0, false);
360  }
361  break;
362 
363  // This means removal failed
365  Cache.MarkDelete(I, false, 0, false);
366  break;
367 
368  default:
369  if (I->InstState != pkgCache::State::Ok)
370  return _error->Error("The package %s is not ok and I "
371  "don't know how to fix it!",I.FullName(false).c_str());
372  }
373  }
374  return true;
375 }
376  /*}}}*/
377 // FixBroken - Fix broken packages /*{{{*/
378 // ---------------------------------------------------------------------
379 /* This autoinstalls every broken package and then runs the problem resolver
380  on the result. */
382 {
383  pkgDepCache::ActionGroup group(Cache);
384 
385  // Auto upgrade all broken packages
386  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
387  if (Cache[I].NowBroken() == true)
388  Cache.MarkInstall(I, true, 0, false);
389 
390  /* Fix packages that are in a NeedArchive state but don't have a
391  downloadable install version */
392  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
393  {
394  if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
395  Cache[I].Delete() == true)
396  continue;
397 
398  if (Cache[I].InstVerIter(Cache).Downloadable() == false)
399  continue;
400 
401  Cache.MarkInstall(I, true, 0, false);
402  }
403 
404  pkgProblemResolver Fix(&Cache);
405  return Fix.Resolve(true);
406 }
407  /*}}}*/
408 // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
409 // ---------------------------------------------------------------------
410 /* */
411 pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : d(NULL), Cache(*pCache)
412 {
413  // Allocate memory
414  auto const Size = Cache.Head().PackageCount;
415  Scores = new int[Size];
416  Flags = new unsigned char[Size];
417  memset(Flags,0,sizeof(*Flags)*Size);
418 
419  // Set debug to true to see its decision logic
420  Debug = _config->FindB("Debug::pkgProblemResolver",false);
421 }
422  /*}}}*/
423 // ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
424 // ---------------------------------------------------------------------
425 /* */
427 {
428  delete [] Scores;
429  delete [] Flags;
430 }
431  /*}}}*/
432 // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
433 // ---------------------------------------------------------------------
434 /* */
436 {
437  if (Scores[A->ID] > Scores[B->ID])
438  return -1;
439  if (Scores[A->ID] < Scores[B->ID])
440  return 1;
441  return 0;
442 }
443  /*}}}*/
444 // ProblemResolver::MakeScores - Make the score table /*{{{*/
445 // ---------------------------------------------------------------------
446 /* */
448 {
449  auto const Size = Cache.Head().PackageCount;
450  memset(Scores,0,sizeof(*Scores)*Size);
451 
452  // maps to pkgCache::State::VerPriority:
453  // Required Important Standard Optional Extra
454  int PrioMap[] = {
455  0,
456  _config->FindI("pkgProblemResolver::Scores::Required",3),
457  _config->FindI("pkgProblemResolver::Scores::Important",2),
458  _config->FindI("pkgProblemResolver::Scores::Standard",1),
459  _config->FindI("pkgProblemResolver::Scores::Optional",-1),
460  _config->FindI("pkgProblemResolver::Scores::Extra",-2)
461  };
462  int PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
463  int PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
464  int DepMap[] = {
465  0,
466  _config->FindI("pkgProblemResolver::Scores::Depends",1),
467  _config->FindI("pkgProblemResolver::Scores::PreDepends",1),
468  _config->FindI("pkgProblemResolver::Scores::Suggests",0),
469  _config->FindI("pkgProblemResolver::Scores::Recommends",1),
470  _config->FindI("pkgProblemResolver::Scores::Conflicts",-1),
471  _config->FindI("pkgProblemResolver::Scores::Replaces",0),
472  _config->FindI("pkgProblemResolver::Scores::Obsoletes",0),
473  _config->FindI("pkgProblemResolver::Scores::Breaks",-1),
474  _config->FindI("pkgProblemResolver::Scores::Enhances",0)
475  };
476  int AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
477  int AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
478 
479  if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
480  clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
481  << " Required => " << PrioMap[pkgCache::State::Required] << endl
482  << " Important => " << PrioMap[pkgCache::State::Important] << endl
483  << " Standard => " << PrioMap[pkgCache::State::Standard] << endl
484  << " Optional => " << PrioMap[pkgCache::State::Optional] << endl
485  << " Extra => " << PrioMap[pkgCache::State::Extra] << endl
486  << " Essentials => " << PrioEssentials << endl
487  << " InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
488  << " Pre-Depends => " << DepMap[pkgCache::Dep::PreDepends] << endl
489  << " Depends => " << DepMap[pkgCache::Dep::Depends] << endl
490  << " Recommends => " << DepMap[pkgCache::Dep::Recommends] << endl
491  << " Suggests => " << DepMap[pkgCache::Dep::Suggests] << endl
492  << " Conflicts => " << DepMap[pkgCache::Dep::Conflicts] << endl
493  << " Breaks => " << DepMap[pkgCache::Dep::DpkgBreaks] << endl
494  << " Replaces => " << DepMap[pkgCache::Dep::Replaces] << endl
495  << " Obsoletes => " << DepMap[pkgCache::Dep::Obsoletes] << endl
496  << " Enhances => " << DepMap[pkgCache::Dep::Enhances] << endl
497  << " AddProtected => " << AddProtected << endl
498  << " AddEssential => " << AddEssential << endl;
499 
500  // Generate the base scores for a package based on its properties
501  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
502  {
503  if (Cache[I].InstallVer == 0)
504  continue;
505 
506  int &Score = Scores[I->ID];
507 
508  /* This is arbitrary, it should be high enough to elevate an
509  essantial package above most other packages but low enough
510  to allow an obsolete essential packages to be removed by
511  a conflicts on a powerful normal package (ie libc6) */
514  Score += PrioEssentials;
515 
516  pkgCache::VerIterator const InstVer = Cache[I].InstVerIter(Cache);
517  // We apply priorities only to downloadable packages, all others are prio:extra
518  // as an obsolete prio:standard package can't be that standard anymore…
519  if (InstVer->Priority <= pkgCache::State::Extra && InstVer.Downloadable() == true)
520  Score += PrioMap[InstVer->Priority];
521  else
523 
524  /* This helps to fix oddball problems with conflicting packages
525  on the same level. We enhance the score of installed packages
526  if those are not obsolete */
527  if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
528  Score += PrioInstalledAndNotObsolete;
529 
530  // propagate score points along dependencies
531  for (pkgCache::DepIterator D = InstVer.DependsList(); not D.end(); ++D)
532  {
533  if (DepMap[D->Type] == 0)
534  continue;
535  pkgCache::PkgIterator const T = D.TargetPkg();
536  if (not D.IsIgnorable(T))
537  {
538  if (D->Version != 0)
539  {
540  pkgCache::VerIterator const IV = Cache[T].InstVerIter(Cache);
541  if (IV.end() || not D.IsSatisfied(IV))
542  continue;
543  }
544  Scores[T->ID] += DepMap[D->Type];
545  }
546 
547  std::vector<map_id_t> providers;
548  for (auto Prv = T.ProvidesList(); not Prv.end(); ++Prv)
549  {
550  if (D.IsIgnorable(Prv))
551  continue;
552  auto const PV = Prv.OwnerVer();
553  auto const PP = PV.ParentPkg();
554  if (PV != Cache[PP].InstVerIter(Cache) || not D.IsSatisfied(Prv))
555  continue;
556  providers.push_back(PP->ID);
557  }
558  std::sort(providers.begin(), providers.end());
559  providers.erase(std::unique(providers.begin(), providers.end()), providers.end());
560  for (auto const prv : providers)
561  Scores[prv] += DepMap[D->Type];
562  }
563  }
564 
565  // Copy the scores to advoid additive looping
566  std::unique_ptr<int[]> OldScores(new int[Size]);
567  memcpy(OldScores.get(),Scores,sizeof(*Scores)*Size);
568 
569  /* Now we cause 1 level of dependency inheritance, that is we add the
570  score of the packages that depend on the target Package. This
571  fortifies high scoring packages */
572  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
573  {
574  if (Cache[I].InstallVer == 0)
575  continue;
576 
577  for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; ++D)
578  {
579  // Only do it for the install version
580  if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
581  (D->Type != pkgCache::Dep::Depends &&
582  D->Type != pkgCache::Dep::PreDepends &&
583  D->Type != pkgCache::Dep::Recommends))
584  continue;
585 
586  // Do not propagate negative scores otherwise
587  // an extra (-2) package might score better than an optional (-1)
588  if (OldScores[D.ParentPkg()->ID] > 0)
589  Scores[I->ID] += OldScores[D.ParentPkg()->ID];
590  }
591  }
592 
593  /* Now we propagate along provides. This makes the packages that
594  provide important packages extremely important */
595  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
596  {
597  auto const transfer = abs(Scores[I->ID] - OldScores[I->ID]);
598  if (transfer == 0)
599  continue;
600 
601  std::vector<map_id_t> providers;
602  for (auto Prv = I.ProvidesList(); not Prv.end(); ++Prv)
603  {
604  if (Prv.IsMultiArchImplicit())
605  continue;
606  auto const PV = Prv.OwnerVer();
607  auto const PP = PV.ParentPkg();
608  if (PV != Cache[PP].InstVerIter(Cache))
609  continue;
610  providers.push_back(PP->ID);
611  }
612  std::sort(providers.begin(), providers.end());
613  providers.erase(std::unique(providers.begin(), providers.end()), providers.end());
614  for (auto const prv : providers)
615  Scores[prv] += transfer;
616  }
617 
618  /* Protected things are pushed really high up. This number should put them
619  ahead of everything */
620  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
621  {
622  if ((Flags[I->ID] & Protected) != 0)
623  Scores[I->ID] += AddProtected;
626  Scores[I->ID] += AddEssential;
627  }
628 }
629  /*}}}*/
630 // ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
631 // ---------------------------------------------------------------------
632 /* This goes through and tries to reinstall packages to make this package
633  installable */
635 {
637 
638  if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
639  return false;
640  if ((Flags[Pkg->ID] & Protected) == Protected)
641  return false;
642 
643  Flags[Pkg->ID] &= ~~Upgradable;
644 
645  bool WasKept = Cache[Pkg].Keep();
646  if (not Cache.MarkInstall(Pkg, false, 0, false))
647  return false;
648 
649  // This must be a virtual package or something like that.
650  if (Cache[Pkg].InstVerIter(Cache).end() == true)
651  return false;
652 
653  // Isolate the problem dependency
654  bool Fail = false;
655  for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
656  {
657  // Compute a single dependency element (glob or)
658  pkgCache::DepIterator Start = D;
659  pkgCache::DepIterator End = D;
660  for (bool LastOR = true; D.end() == false && LastOR == true;)
661  {
662  LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
663  ++D;
664  if (LastOR == true)
665  End = D;
666  }
667 
668  // We only worry about critical deps.
669  if (End.IsCritical() != true)
670  continue;
671 
672  // Iterate over all the members in the or group
673  while (1)
674  {
675  // Dep is ok now
677  break;
678 
679  // Do not change protected packages
680  PkgIterator P = Start.SmartTargetPkg();
681  if (Cache[P].Protect())
682  {
683  if (Debug == true)
684  clog << " Reinst Failed because of protected " << P.FullName(false) << endl;
685  Fail = true;
686  }
687  else
688  {
689  // Upgrade the package if the candidate version will fix the problem.
691  {
692  if (DoUpgrade(P) == false)
693  {
694  if (Debug == true)
695  clog << " Reinst Failed because of " << P.FullName(false) << endl;
696  Fail = true;
697  }
698  else
699  {
700  Fail = false;
701  break;
702  }
703  }
704  else
705  {
706  /* We let the algorithm deal with conflicts on its next iteration,
707  it is much smarter than us */
708  if (Start.IsNegative() == true)
709  break;
710 
711  if (Debug == true)
712  clog << " Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
713  Fail = true;
714  }
715  }
716 
717  if (Start == End)
718  break;
719  ++Start;
720  }
721  if (Fail == true)
722  break;
723  }
724 
725  // Undo our operations - it might be smart to undo everything this did..
726  if (Fail == true)
727  {
728  if (WasKept == true)
729  Cache.MarkKeep(Pkg, false, false);
730  else
731  Cache.MarkDelete(Pkg, false, 0, false);
732  return false;
733  }
734 
735  if (Debug == true)
736  clog << " Re-Instated " << Pkg.FullName(false) << endl;
737  return true;
738 }
739  /*}}}*/
740 // ProblemResolver::Resolve - calls a resolver to fix the situation /*{{{*/
741 bool pkgProblemResolver::Resolve(bool BrokenFix, OpProgress * const Progress)
742 {
743  std::string const solver = _config->Find("APT::Solver", "internal");
744  auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, 0, Progress);
745  if (solver != "internal")
746  return ret;
747  return ResolveInternal(BrokenFix);
748 }
749  /*}}}*/
750 // ProblemResolver::ResolveInternal - Run the resolution pass /*{{{*/
751 // ---------------------------------------------------------------------
752 /* This routines works by calculating a score for each package. The score
753  is derived by considering the package's priority and all reverse
754  dependents giving an integer that reflects the amount of breakage that
755  adjusting the package will inflict.
756 
757  It goes from highest score to lowest and corrects all of the breaks by
758  keeping or removing the dependent packages. If that fails then it removes
759  the package itself and goes on. The routine should be able to intelligently
760  go from any broken state to a fixed state.
761 
762  The BrokenFix flag enables a mode where the algorithm tries to
763  upgrade packages to advoid problems. */
764 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
765 {
767 
768  if (Debug)
769  Cache.CheckConsistency("resolve start");
770 
771  // Record which packages are marked for install
772  bool Again = false;
773  do
774  {
775  Again = false;
776  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
777  {
778  if (Cache[I].Install() == true)
779  Flags[I->ID] |= PreInstalled;
780  else
781  {
782  if (Cache[I].InstBroken() == true && BrokenFix == true)
783  {
784  Cache.MarkInstall(I, false, 0, false);
785  if (Cache[I].Install() == true)
786  Again = true;
787  }
788 
789  Flags[I->ID] &= ~~PreInstalled;
790  }
791  Flags[I->ID] |= Upgradable;
792  }
793  }
794  while (Again == true);
795 
796  if (Debug == true) {
797  clog << "Starting pkgProblemResolver with broken count: "
798  << Cache.BrokenCount() << endl;
799  }
800 
801  MakeScores();
802 
803  auto const Size = Cache.Head().PackageCount;
804 
805  /* We have to order the packages so that the broken fixing pass
806  operates from highest score to lowest. This prevents problems when
807  high score packages cause the removal of lower score packages that
808  would cause the removal of even lower score packages. */
809  std::unique_ptr<pkgCache::Package *[]> PList(new pkgCache::Package *[Size]);
810  pkgCache::Package **PEnd = PList.get();
811  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
812  *PEnd++ = I;
813 
814  std::sort(PList.get(), PEnd, [this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
815 
816  if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
817  {
818  clog << "Show Scores" << endl;
819  for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
820  if (Scores[(*K)->ID] != 0)
821  {
823  clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
824  }
825  }
826 
827  if (Debug == true) {
828  clog << "Starting 2 pkgProblemResolver with broken count: "
829  << Cache.BrokenCount() << endl;
830  }
831 
832  /* Now consider all broken packages. For each broken package we either
833  remove the package or fix it's problem. We do this once, it should
834  not be possible for a loop to form (that is a < b < c and fixing b by
835  changing a breaks c) */
836  bool Change = true;
837  bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
838  int const MaxCounter = _config->FindI("pkgProblemResolver::MaxCounter", 20);
839  std::vector<PackageKill> KillList;
840  for (int Counter = 0; Counter < MaxCounter && Change; ++Counter)
841  {
842  Change = false;
843  for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
844  {
846 
847  /* We attempt to install this and see if any breaks result,
848  this takes care of some strange cases */
849  if (Cache[I].CandidateVer != Cache[I].InstallVer &&
850  I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
851  (Flags[I->ID] & PreInstalled) != 0 &&
852  not Cache[I].Protect() &&
853  (Flags[I->ID] & ReInstateTried) == 0)
854  {
855  if (Debug == true)
856  clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
857  auto const OldBreaks = Cache.BrokenCount();
858  pkgCache::Version *OldVer = Cache[I].InstallVer;
859  Flags[I->ID] &= ReInstateTried;
860 
861  Cache.MarkInstall(I, false, 0, false);
862  if (Cache[I].InstBroken() == true ||
863  OldBreaks < Cache.BrokenCount())
864  {
865  if (OldVer == 0)
866  Cache.MarkDelete(I, false, 0, false);
867  else
868  Cache.MarkKeep(I, false, false);
869  }
870  else
871  if (Debug == true)
872  clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
873  }
874 
875  if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
876  continue;
877 
878  if (Debug == true)
879  clog << "Investigating (" << Counter << ") " << APT::PrettyPkg(&Cache, I) << endl;
880 
881  // Isolate the problem dependency
882  bool InOr = false;
883  pkgCache::DepIterator Start;
885  size_t OldSize = 0;
886 
887  KillList.clear();
888 
889  enum {OrRemove,OrKeep} OrOp = OrRemove;
890  for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
891  D.end() == false || InOr == true;)
892  {
893  // Compute a single dependency element (glob or)
894  if (Start == End)
895  {
896  // Decide what to do
897  if (InOr == true && OldSize == KillList.size())
898  {
899  if (OrOp == OrRemove)
900  {
901  if (not Cache[I].Protect())
902  {
903  if (Debug == true)
904  clog << " Or group remove for " << I.FullName(false) << endl;
905  Cache.MarkDelete(I, false, 0, false);
906  Change = true;
907  }
908  }
909  else if (OrOp == OrKeep)
910  {
911  if (Debug == true)
912  clog << " Or group keep for " << I.FullName(false) << endl;
913  Cache.MarkKeep(I, false, false);
914  Change = true;
915  }
916  }
917 
918  /* We do an extra loop (as above) to finalize the or group
919  processing */
920  InOr = false;
921  OrOp = OrRemove;
922  D.GlobOr(Start,End);
923  if (Start.end() == true)
924  break;
925 
926  // We only worry about critical deps.
927  if (End.IsCritical() != true)
928  continue;
929 
930  InOr = Start != End;
931  OldSize = KillList.size();
932  }
933  else
934  {
935  ++Start;
936  // We only worry about critical deps.
937  if (Start.IsCritical() != true)
938  continue;
939  }
940 
941  // Dep is ok
943  {
944  InOr = false;
945  continue;
946  }
947 
948  if (Debug == true)
949  clog << "Broken " << APT::PrettyDep(&Cache, Start) << endl;
950 
951  /* Look across the version list. If there are no possible
952  targets then we keep the package and bail. This is necessary
953  if a package has a dep on another package that can't be found */
954  std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
955  if (VList[0] == 0 && not Cache[I].Protect() &&
956  Start.IsNegative() == false &&
957  Cache[I].NowBroken() == false)
958  {
959  if (InOr == true)
960  {
961  /* No keep choice because the keep being OK could be the
962  result of another element in the OR group! */
963  continue;
964  }
965 
966  Change = true;
967  Cache.MarkKeep(I, false, false);
968  break;
969  }
970 
971  bool Done = false;
972  for (pkgCache::Version **V = VList.get(); *V != 0; V++)
973  {
975  pkgCache::PkgIterator Pkg = Ver.ParentPkg();
976 
977  /* This is a conflicts, and the version we are looking
978  at is not the currently selected version of the
979  package, which means it is not necessary to
980  remove/keep */
981  if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
982  {
983  if (Debug)
984  clog << " Conflicts//Breaks against version "
985  << Ver.VerStr() << " for " << Pkg.Name()
986  << " but that is not InstVer, ignoring"
987  << endl;
988  continue;
989  }
990 
991  if (Debug == true)
992  clog << " Considering " << Pkg.FullName(false) << ' ' << Scores[Pkg->ID] <<
993  " as a solution to " << I.FullName(false) << ' ' << Scores[I->ID] << endl;
994 
995  /* Try to fix the package under consideration rather than
996  fiddle with the VList package */
997  if (Scores[I->ID] <= Scores[Pkg->ID] ||
998  ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
999  End.IsNegative() == false))
1000  {
1001  // Try a little harder to fix protected packages..
1002  if (Cache[I].Protect())
1003  {
1004  if (DoUpgrade(Pkg) == true)
1005  {
1006  if (Scores[Pkg->ID] > Scores[I->ID])
1007  Scores[Pkg->ID] = Scores[I->ID];
1008  break;
1009  }
1010 
1011  continue;
1012  }
1013 
1014  /* See if a keep will do, unless the package is protected,
1015  then installing it will be necessary */
1016  bool Installed = Cache[I].Install();
1017  Cache.MarkKeep(I, false, false);
1018  if (Cache[I].InstBroken() == false)
1019  {
1020  // Unwind operation will be keep now
1021  if (OrOp == OrRemove)
1022  OrOp = OrKeep;
1023 
1024  // Restore
1025  if (InOr == true && Installed == true)
1026  Cache.MarkInstall(I, false, 0, false);
1027 
1028  if (Debug == true)
1029  clog << " Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1030  }
1031  else
1032  {
1033  if (BrokenFix == false || DoUpgrade(I) == false)
1034  {
1035  // Consider other options
1036  if (InOr == false || Cache[I].Garbage == true)
1037  {
1038  if (Debug == true)
1039  clog << " Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
1040  Cache.MarkDelete(I, false, 0, false);
1041  if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
1042  Scores[I->ID] = Scores[Pkg->ID];
1043  }
1044  else if (TryFixByInstall == true &&
1045  Start.TargetPkg()->CurrentVer == 0 &&
1046  Cache[Start.TargetPkg()].Delete() == false &&
1047  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
1048  Cache.GetCandidateVersion(Start.TargetPkg()).end() == false)
1049  {
1050  /* Before removing or keeping the package with the broken dependency
1051  try instead to install the first not previously installed package
1052  solving this dependency. This helps every time a previous solver
1053  is removed by the resolver because of a conflict or alike but it is
1054  dangerous as it could trigger new breaks/conflicts… */
1055  if (Debug == true)
1056  clog << " Try Installing " << APT::PrettyPkg(&Cache, Start.TargetPkg()) << " before changing " << I.FullName(false) << std::endl;
1057  auto const OldBroken = Cache.BrokenCount();
1058  Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
1059  // FIXME: we should undo the complete MarkInstall process here
1060  if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
1061  Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
1062  }
1063  }
1064  }
1065 
1066  Change = true;
1067  Done = true;
1068  break;
1069  }
1070  else
1071  {
1072  if (Start->Type == pkgCache::Dep::DpkgBreaks)
1073  {
1074  // first, try upgradring the package, if that
1075  // does not help, the breaks goes onto the
1076  // kill list
1077  //
1078  // FIXME: use DoUpgrade(Pkg) instead?
1079  if (Cache[End] & pkgDepCache::DepGCVer)
1080  {
1081  if (Debug)
1082  clog << " Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
1083  Cache.MarkInstall(Pkg, false, 0, false);
1084  continue;
1085  }
1086  }
1087 
1088  // Skip adding to the kill list if it is protected
1089  if (Cache[Pkg].Protect() && Cache[Pkg].Mode != pkgDepCache::ModeDelete)
1090  continue;
1091 
1092  if (Debug == true)
1093  clog << " Added " << Pkg.FullName(false) << " to the remove list" << endl;
1094 
1095  KillList.push_back({Pkg, End});
1096 
1097  if (Start.IsNegative() == false)
1098  break;
1099  }
1100  }
1101 
1102  // Hm, nothing can possibly satisfy this dep. Nuke it.
1103  if (VList[0] == 0 &&
1104  Start.IsNegative() == false &&
1105  not Cache[I].Protect())
1106  {
1107  bool Installed = Cache[I].Install();
1108  Cache.MarkKeep(I);
1109  if (Cache[I].InstBroken() == false)
1110  {
1111  // Unwind operation will be keep now
1112  if (OrOp == OrRemove)
1113  OrOp = OrKeep;
1114 
1115  // Restore
1116  if (InOr == true && Installed == true)
1117  Cache.MarkInstall(I, false, 0, false);
1118 
1119  if (Debug == true)
1120  clog << " Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1121  }
1122  else
1123  {
1124  if (Debug == true)
1125  clog << " Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1126  if (InOr == false)
1127  Cache.MarkDelete(I, false, 0, false);
1128  }
1129 
1130  Change = true;
1131  Done = true;
1132  }
1133 
1134  // Try some more
1135  if (InOr == true)
1136  continue;
1137 
1138  if (Done == true)
1139  break;
1140  }
1141 
1142  // Apply the kill list now
1143  if (Cache[I].InstallVer != 0)
1144  {
1145  for (auto const &J : KillList)
1146  {
1147  bool foundSomething = false;
1148  if ((Cache[J.Dep] & pkgDepCache::DepGNow) == 0)
1149  {
1150  if (J.Dep.IsNegative() && Cache.MarkDelete(J.Pkg, false, 0, false))
1151  {
1152  if (Debug)
1153  std::clog << " Fixing " << I.FullName(false) << " via remove of " << J.Pkg.FullName(false) << '\n';
1154  foundSomething = true;
1155  }
1156  }
1157  else if (Cache.MarkKeep(J.Pkg, false, false))
1158  {
1159  if (Debug)
1160  std::clog << " Fixing " << I.FullName(false) << " via keep of " << J.Pkg.FullName(false) << '\n';
1161  foundSomething = true;
1162  }
1163 
1164  if (not foundSomething || Counter > 1)
1165  {
1166  if (Scores[I->ID] > Scores[J.Pkg->ID])
1167  {
1168  Scores[J.Pkg->ID] = Scores[I->ID];
1169  Change = true;
1170  }
1171  }
1172  if (foundSomething)
1173  Change = true;
1174  }
1175  }
1176  }
1177  }
1178 
1179  if (Debug == true)
1180  clog << "Done" << endl;
1181 
1182  if (Cache.BrokenCount() != 0)
1183  {
1184  // See if this is the result of a hold
1186  for (;I.end() != true; ++I)
1187  {
1188  if (Cache[I].InstBroken() == false)
1189  continue;
1190  if (not Cache[I].Protect())
1191  return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1192  }
1193  return _error->Error(_("Unable to correct problems, you have held broken packages."));
1194  }
1195 
1196  // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1198  for (;I.end() != true; ++I) {
1199  if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1200  if(_config->FindB("Debug::pkgAutoRemove",false)) {
1201  std::clog << "Resolve installed new pkg: " << I.FullName(false)
1202  << " (now marking it as auto)" << std::endl;
1203  }
1204  Cache[I].Flags |= pkgCache::Flag::Auto;
1205  }
1206  }
1207 
1208  if (Debug)
1209  Cache.CheckConsistency("resolve done");
1210 
1211  return true;
1212 }
1213  /*}}}*/
1214 // ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1215 // ---------------------------------------------------------------------
1216 /* This checks if the given package is broken either by a hard dependency
1217  (InstBroken()) or by introducing a new policy breakage e.g. new
1218  unsatisfied recommends for a package that was in "policy-good" state
1219 
1220  Note that this is not perfect as it will ignore further breakage
1221  for already broken policy (recommends)
1222 */
1224 {
1225  // a broken install is always a problem
1226  if (Cache[I].InstBroken() == true)
1227  {
1228  if (Debug == true)
1229  std::clog << " Dependencies are not satisfied for " << APT::PrettyPkg(&Cache, I) << std::endl;
1230  return true;
1231  }
1232 
1233  // a newly broken policy (recommends/suggests) is a problem
1234  if (Cache[I].NowPolicyBroken() == false &&
1235  Cache[I].InstPolicyBroken() == true)
1236  {
1237  if (Debug == true)
1238  std::clog << " Policy breaks with upgrade of " << APT::PrettyPkg(&Cache, I) << std::endl;
1239  return true;
1240  }
1241 
1242  return false;
1243 }
1244  /*}}}*/
1245 // ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
1246 // ---------------------------------------------------------------------
1247 /* This is the work horse of the soft upgrade routine. It is very gentle
1248  in that it does not install or remove any packages. It is assumed that the
1249  system was non-broken previously. */
1251 {
1252  std::string const solver = _config->Find("APT::Solver", "internal");
1254  auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, flags, Progress);
1255  if (solver != "internal")
1256  return ret;
1257  return ResolveByKeepInternal();
1258 }
1259  /*}}}*/
1260 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1261 // ---------------------------------------------------------------------
1262 /* This is the work horse of the soft upgrade routine. It is very gentle
1263  in that it does not install or remove any packages. It is assumed that the
1264  system was non-broken previously. */
1266 {
1268 
1269  if (Debug)
1270  Cache.CheckConsistency("keep start");
1271 
1272  MakeScores();
1273 
1274  /* We have to order the packages so that the broken fixing pass
1275  operates from highest score to lowest. This prevents problems when
1276  high score packages cause the removal of lower score packages that
1277  would cause the removal of even lower score packages. */
1278  auto Size = Cache.Head().PackageCount;
1279  pkgCache::Package **PList = new pkgCache::Package *[Size];
1280  pkgCache::Package **PEnd = PList;
1281  for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1282  *PEnd++ = I;
1283 
1284  std::sort(PList,PEnd,[this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
1285 
1286 
1287  if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1288  {
1289  clog << "Show Scores" << endl;
1290  for (pkgCache::Package **K = PList; K != PEnd; K++)
1291  if (Scores[(*K)->ID] != 0)
1292  {
1293  pkgCache::PkgIterator Pkg(Cache,*K);
1294  clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
1295  }
1296  }
1297 
1298  if (Debug == true)
1299  clog << "Entering ResolveByKeep" << endl;
1300 
1301  // Consider each broken package
1302  pkgCache::Package **LastStop = 0;
1303  for (pkgCache::Package **K = PList; K != PEnd; K++)
1304  {
1306 
1307  if (Cache[I].InstallVer == 0)
1308  continue;
1309 
1310  if (InstOrNewPolicyBroken(I) == false)
1311  continue;
1312 
1313  /* Keep the package. If this works then great, otherwise we have
1314  to be significantly more aggressive and manipulate its dependencies */
1315  if (not Cache[I].Protect())
1316  {
1317  if (Debug == true)
1318  clog << "Keeping package " << I.FullName(false) << endl;
1319  Cache.MarkKeep(I, false, false);
1320  if (InstOrNewPolicyBroken(I) == false)
1321  {
1322  K = PList - 1;
1323  continue;
1324  }
1325  }
1326 
1327  // Isolate the problem dependencies
1328  for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1329  {
1330  DepIterator Start;
1331  DepIterator End;
1332  D.GlobOr(Start,End);
1333 
1334  // We only worry about critical deps.
1335  if (End.IsCritical() != true)
1336  continue;
1337 
1338  // Dep is ok
1340  continue;
1341 
1342  /* Hm, the group is broken.. I suppose the best thing to do is to
1343  is to try every combination of keep/not-keep for the set, but that's
1344  slow, and this never happens, just be conservative and assume the
1345  list of ors is in preference and keep till it starts to work. */
1346  while (true)
1347  {
1348  if (Debug == true)
1349  clog << "Package " << I.FullName(false) << " " << APT::PrettyDep(&Cache, Start) << endl;
1350 
1351  // Look at all the possible provides on this package
1352  std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
1353  for (pkgCache::Version **V = VList.get(); *V != 0; V++)
1354  {
1355  pkgCache::VerIterator Ver(Cache,*V);
1356  pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1357 
1358  // It is not keepable
1359  if (Cache[Pkg].InstallVer == 0 ||
1360  Pkg->CurrentVer == 0)
1361  continue;
1362 
1363  if (not Cache[I].Protect())
1364  {
1365  if (Debug == true)
1366  clog << " Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1367  Cache.MarkKeep(Pkg, false, false);
1368  }
1369 
1370  if (InstOrNewPolicyBroken(I) == false)
1371  break;
1372  }
1373 
1374  if (InstOrNewPolicyBroken(I) == false)
1375  break;
1376 
1377  if (Start == End)
1378  break;
1379  ++Start;
1380  }
1381 
1382  if (InstOrNewPolicyBroken(I) == false)
1383  break;
1384  }
1385 
1386  if (InstOrNewPolicyBroken(I) == true)
1387  continue;
1388 
1389  // Restart again.
1390  if (K == LastStop) {
1391  // I is an iterator based off our temporary package list,
1392  // so copy the name we need before deleting the temporary list
1393  std::string const LoopingPackage = I.FullName(false);
1394  delete[] PList;
1395  return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1396  }
1397  LastStop = K;
1398  K = PList - 1;
1399  }
1400 
1401  delete[] PList;
1402 
1403  if (Debug)
1404  Cache.CheckConsistency("keep done");
1405 
1406  return true;
1407 }
1408  /*}}}*/
1409 // PrioSortList - Sort a list of versions by priority /*{{{*/
1410 // ---------------------------------------------------------------------
1411 /* This is meant to be used in conjunction with AllTargets to get a list
1412  of versions ordered by preference. */
1413 
1414 struct PrioComp {
1416 
1418  }
1419 
1420  bool operator() (pkgCache::Version * const &A, pkgCache::Version * const &B) {
1421  return compare(A, B) < 0;
1422  }
1423 
1424  int compare(pkgCache::Version * const &A, pkgCache::Version * const &B) {
1427 
1428  if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1429  (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1430  return 1;
1431  if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1432  (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1433  return -1;
1434 
1435  if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1436  (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1437  return 1;
1438  if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1439  (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1440  return -1;
1441 
1442  if (L->Priority != R->Priority)
1443  return R->Priority - L->Priority;
1444  return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1445  }
1446 };
1447 
1449 {
1450  unsigned long Count = 0;
1451  for (pkgCache::Version **I = List; *I != 0; I++)
1452  Count++;
1453  std::sort(List,List+Count,PrioComp(Cache));
1454 }
1455  /*}}}*/
1456 
1457 namespace APT
1458 {
1459 
1460 namespace KernelAutoRemoveHelper
1461 {
1462 
1463 // \brief Returns the uname from a kernel package name, or "" for non-kernel packages.
1464 std::string getUname(std::string const &packageName)
1465 {
1466 
1467  static const constexpr char *const prefixes[] = {
1468  "linux-image-",
1469  "kfreebsd-image-",
1470  "gnumach-image-",
1471  };
1472 
1473  for (auto prefix : prefixes)
1474  {
1475  if (likely(not APT::String::Startswith(packageName, prefix)))
1476  continue;
1477  if (unlikely(APT::String::Endswith(packageName, "-dbgsym")))
1478  continue;
1479  if (unlikely(APT::String::Endswith(packageName, "-dbg")))
1480  continue;
1481 
1482  auto aUname = packageName.substr(strlen(prefix));
1483 
1484  // aUname must start with [0-9]+\.
1485  if (aUname.length() < 2)
1486  continue;
1487  if (strchr("0123456789", aUname[0]) == nullptr)
1488  continue;
1489  auto dot = aUname.find_first_not_of("0123456789");
1490  if (dot == aUname.npos || aUname[dot] != '.')
1491  continue;
1492 
1493  return aUname;
1494  }
1495 
1496  return "";
1497 }
1498 std::string GetProtectedKernelsRegex(pkgCache *cache, bool ReturnRemove)
1499 {
1500  if (_config->FindB("APT::Protect-Kernels", true) == false)
1501  return "";
1502 
1503  struct CompareKernel
1504  {
1505  pkgCache *cache;
1506  bool operator()(const std::string &a, const std::string &b) const
1507  {
1508  return cache->VS->CmpVersion(a, b) < 0;
1509  }
1510  };
1511  bool Debug = _config->FindB("Debug::pkgAutoRemove", false);
1512  // kernel version -> list of unames
1513  std::map<std::string, std::vector<std::string>, CompareKernel> version2unames(CompareKernel{cache});
1514  // needs to be initialized to 0s, might not be set up.
1515  utsname uts{};
1516  std::string bootedVersion;
1517  std::string lastInstalledVersion;
1518 
1519  std::string lastInstalledUname = _config->Find("APT::LastInstalledKernel");
1520 
1521  // Get currently booted version, but only when not on reproducible build.
1522  if (getenv("SOURCE_DATE_EPOCH") == 0)
1523  {
1524  if (uname(&uts) != 0)
1525  abort();
1526  }
1527 
1528  auto VirtualKernelPkg = cache->FindPkg("$kernel", "any");
1529  if (VirtualKernelPkg.end())
1530  return "";
1531 
1532  for (pkgCache::PrvIterator Prv = VirtualKernelPkg.ProvidesList(); Prv.end() == false; ++Prv)
1533  {
1534  auto Pkg = Prv.OwnerPkg();
1535  if (likely(Pkg->CurrentVer == 0))
1536  continue;
1537 
1538  auto pkgUname = APT::KernelAutoRemoveHelper::getUname(Pkg.Name());
1539  auto pkgVersion = Pkg.CurrentVer().VerStr();
1540 
1541  if (pkgUname.empty())
1542  continue;
1543 
1544  if (Debug)
1545  std::clog << "Found kernel " << pkgUname << "(" << pkgVersion << ")" << std::endl;
1546 
1547  version2unames[pkgVersion].push_back(pkgUname);
1548 
1549  if (pkgUname == uts.release)
1550  bootedVersion = pkgVersion;
1551  if (pkgUname == lastInstalledUname)
1552  lastInstalledVersion = pkgVersion;
1553  }
1554 
1555  if (version2unames.size() == 0)
1556  return "";
1557 
1558  auto latest = version2unames.rbegin();
1559  auto previous = latest;
1560  ++previous;
1561 
1562  std::set<std::string> keep;
1563 
1564  if (not bootedVersion.empty())
1565  {
1566  if (Debug)
1567  std::clog << "Keeping booted kernel " << bootedVersion << std::endl;
1568  keep.insert(bootedVersion);
1569  }
1570  if (not lastInstalledVersion.empty())
1571  {
1572  if (Debug)
1573  std::clog << "Keeping installed kernel " << lastInstalledVersion << std::endl;
1574  keep.insert(lastInstalledVersion);
1575  }
1576  if (latest != version2unames.rend())
1577  {
1578  if (Debug)
1579  std::clog << "Keeping latest kernel " << latest->first << std::endl;
1580  keep.insert(latest->first);
1581  }
1582  if (keep.size() < 3 && previous != version2unames.rend())
1583  {
1584  if (Debug)
1585  std::clog << "Keeping previous kernel " << previous->first << std::endl;
1586  keep.insert(previous->first);
1587  }
1588  // Escape special characters '.' and '+' in version strings so we can build a regular expression
1589  auto escapeSpecial = [](std::string input) -> std::string {
1590  for (size_t pos = 0; (pos = input.find_first_of(".+", pos)) != input.npos; pos += 2) {
1591  input.insert(pos, 1, '\\');
1592  }
1593  return input;
1594  };
1595  std::ostringstream ss;
1596  for (auto &pattern : _config->FindVector("APT::VersionedKernelPackages"))
1597  {
1598  // Legacy compatibility: Always protected the booted uname and last installed uname
1599  if (not lastInstalledUname.empty())
1600  ss << "|^" << pattern << "-" << escapeSpecial(lastInstalledUname) << "$";
1601  if (*uts.release)
1602  ss << "|^" << pattern << "-" << escapeSpecial(uts.release) << "$";
1603  for (auto const &kernel : version2unames)
1604  {
1605  if (ReturnRemove ? keep.find(kernel.first) == keep.end() : keep.find(kernel.first) != keep.end())
1606  {
1607  for (auto const &uname : kernel.second)
1608  ss << "|^" << pattern << "-" << escapeSpecial(uname) << "$";
1609  }
1610  }
1611  }
1612 
1613  auto re_with_leading_or = ss.str();
1614 
1615  if (re_with_leading_or.empty())
1616  return "";
1617 
1618  auto re = re_with_leading_or.substr(1);
1619  if (Debug)
1620  std::clog << "Kernel protection regex: " << re << "\n";
1621 
1622  return re;
1623 }
1624 
1625 std::unique_ptr<APT::CacheFilter::Matcher> GetProtectedKernelsFilter(pkgCache *cache, bool returnRemove)
1626 {
1627  auto regex = GetProtectedKernelsRegex(cache, returnRemove);
1628 
1629  if (regex.empty())
1630  return std::make_unique<APT::CacheFilter::FalseMatcher>();
1631 
1632  return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex);
1633 }
1634 
1635 } // namespace KernelAutoRemoveHelper
1636 } // namespace APT
static bool std::string const metaIndex const *const pkgAcqMetaClearSig *const pkgAcquire::Item *const I
bool pkgFixBroken(pkgDepCache &Cache)
Definition: algorithms.cc:381
bool pkgApplyStatus(pkgDepCache &Cache)
Definition: algorithms.cc:313
void pkgPrioSortList(pkgCache &Cache, pkgCache::Version **List)
Definition: algorithms.cc:1448
pkgCache::PkgIterator PkgIterator
Definition: pkgcache.h:829
pkgCache::VerIterator VerIterator
Definition: pkgcache.h:830
pkgCache::DepIterator DepIterator
Definition: pkgcache.h:832
static APT_HIDDEN bool ExpandPendingCalls(std::vector< Item > &List, pkgDepCache &Cache)
Definition: dpkgpm.cc:1428
Represents an active action group.
Definition: depcache.h:166
PkgIterator FindPkg(APT::StringView Name)
Definition: depcache.h:358
bool MarkKeep(PkgIterator const &Pkg, bool Soft=false, bool FromUser=true, unsigned long Depth=0)
Definition: depcache.cc:931
pkgCache::VerIterator GetCandidateVersion(pkgCache::PkgIterator const &Pkg)
Definition: depcache.cc:1863
void Update(DepIterator Dep)
Definition: depcache.cc:822
bool CheckConsistency(char const *const msgtag="")
Definition: depcache.cc:144
bool MarkInstall(PkgIterator const &Pkg, bool AutoInst=true, unsigned long Depth=0, bool FromUser=true, bool ForceImportantDeps=false)
Definition: depcache.cc:1560
PkgIterator PkgBegin()
Definition: depcache.h:356
unsigned long BrokenCount()
Definition: depcache.h:497
bool Init(OpProgress *const Prog)
Definition: depcache.cc:229
bool MarkDelete(PkgIterator const &Pkg, bool MarkPurge=false, unsigned long Depth=0, bool FromUser=true)
Definition: depcache.cc:991
bool IsImportantDep(DepIterator Dep) const
Definition: depcache.h:364
Header & Head()
Definition: depcache.h:354
std::string * FileNames
pkgDepCache & Cache
bool InstOrNewPolicyBroken(pkgCache::PkgIterator Pkg)
Definition: algorithms.cc:1223
APT_HIDDEN void MakeScores()
Definition: algorithms.cc:447
bool ResolveByKeep(OpProgress *const Progress=NULL)
Definition: algorithms.cc:1250
APT_HIDDEN bool ResolveByKeepInternal()
Definition: algorithms.cc:1265
APT_HIDDEN bool ResolveInternal(bool const BrokenFix=false)
Definition: algorithms.cc:764
pkgDepCache & Cache
Definition: algorithms.h:98
APT_HIDDEN int ScoreSort(Package const *A, Package const *B) APT_PURE
Definition: algorithms.cc:435
virtual ~pkgProblemResolver()
Definition: algorithms.cc:426
pkgProblemResolver(pkgDepCache *Cache)
Definition: algorithms.cc:411
APT_HIDDEN bool DoUpgrade(pkgCache::PkgIterator Pkg)
Definition: algorithms.cc:634
bool Resolve(bool BrokenFix=false, OpProgress *const Progress=NULL)
Definition: algorithms.cc:741
pkgCache::PkgIterator PkgIterator
Definition: algorithms.h:99
void Protect(pkgCache::PkgIterator Pkg)
Definition: algorithms.h:130
pkgCache::DepIterator DepIterator
Definition: algorithms.h:101
std::vector< pkgDPkgPM::Item > List
Definition: algorithms.cc:52
APT_HIDDEN bool RealRemove(PkgIterator Pkg, bool Purge)
Definition: algorithms.cc:230
APT_HIDDEN bool RealInstall(PkgIterator Pkg, std::string File)
Definition: algorithms.cc:120
unsigned char * Flags
Definition: algorithms.h:65
virtual bool Install(PkgIterator Pkg, std::string File) APT_OVERRIDE
Definition: algorithms.cc:113
bool Go(APT::Progress::PackageManager *progress) override
Definition: algorithms.cc:276
pkgSimulate(pkgDepCache *Cache)
Definition: algorithms.cc:58
APT_HIDDEN bool RealConfigure(PkgIterator Pkg)
Definition: algorithms.cc:173
pkgDepCache Sim
Definition: algorithms.h:68
virtual bool Remove(PkgIterator Pkg, bool Purge) APT_OVERRIDE
Definition: algorithms.cc:223
virtual bool Configure(PkgIterator Pkg) APT_OVERRIDE
Definition: algorithms.cc:166
APT_HIDDEN void ShortBreaks()
Definition: algorithms.cc:260
APT_HIDDEN void Describe(PkgIterator iPkg, std::ostream &out, bool Current, bool Candidate)
Definition: algorithms.cc:87
virtual ~pkgSimulate()
Definition: algorithms.cc:77
pkgSimulatePrivate *const d
Definition: algorithms.h:49
Configuration * _config
constexpr char const *const PrioMap[]
Definition: edsp.cc:44
constexpr char const *const DepMap[]
Definition: edsp.cc:48
const char * pkgVersion
Definition: init.cc:33
#define APT_HIDDEN
Definition: macros.h:78
std::unique_ptr< APT::CacheFilter::Matcher > GetProtectedKernelsFilter(pkgCache *cache, bool returnRemove)
Definition: algorithms.cc:1625
std::string GetProtectedKernelsRegex(pkgCache *cache, bool ReturnRemove)
Definition: algorithms.cc:1498
std::string getUname(std::string const &packageName)
Definition: algorithms.cc:1464
bool Endswith(const std::string &s, const std::string &end)
Definition: strutl.cc:77
bool Startswith(const std::string &s, const std::string &start)
Definition: strutl.cc:84
@ FORBID_REMOVE
Definition: edsp.h:35
@ FORBID_NEW_INSTALL
Definition: edsp.h:34
@ UPGRADE_ALL
Definition: edsp.h:33
APT_PUBLIC bool ResolveExternal(const char *const solver, pkgDepCache &Cache, unsigned int const flags=0, OpProgress *Progress=NULL)
call an external resolver to handle the request
Definition: edsp.cc:748
pkgCache - Structure definitions for the cache file
Definition: rred.cc:136
PrioComp(pkgCache &PrioCache)
Definition: algorithms.cc:1417
pkgCache & PrioCache
Definition: algorithms.cc:1415
int compare(pkgCache::Version *const &A, pkgCache::Version *const &B)
Definition: algorithms.cc:1424
bool operator()(pkgCache::Version *const &A, pkgCache::Version *const &B)
Definition: algorithms.cc:1420
map_id_t PackageCount
Definition: pkgcache.h:335
contains information for a single unique package
Definition: pkgcache.h:450
map_id_t ID
unique sequel ID
Definition: pkgcache.h:494
information for a single version of a package
Definition: pkgcache.h:625
@ TriggersPending
Definition: dpkgpm.h:76
@ ConfigurePending
Definition: dpkgpm.h:76