1# ex:ts=8 sw=4:
2# $OpenBSD: Dependencies.pm,v 1.155 2015/01/30 11:42:55 espie Exp $
3#
4# Copyright (c) 2005-2010 Marc Espie <espie@openbsd.org>
5#
6# Permission to use, copy, modify, and distribute this software for any
7# purpose with or without fee is hereby granted, provided that the above
8# copyright notice and this permission notice appear in all copies.
9#
10# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16
17use strict;
18use warnings;
19
20use OpenBSD::SharedLibs;
21
22# generic dependencies lookup class: walk the dependency tree as far
23# as necessary to resolve dependencies
24package OpenBSD::lookup;
25
26sub lookup
27{
28	my ($self, $solver, $dependencies, $state, $obj) = @_;
29
30	my $known = $self->{known};
31	if (my $r = $self->find_in_already_done($solver, $state, $obj)) {
32		$dependencies->{$r} = 1;
33		return 1;
34	}
35	if ($self->find_in_extra_sources($solver, $state, $obj)) {
36		return 1;
37	}
38	# lookup through the rest of the tree...
39	my $done = $self->{done};
40	while (my $dep = pop @{$self->{todo}}) {
41		require OpenBSD::RequiredBy;
42
43		next if $done->{$dep};
44		$done->{$dep} = 1;
45		for my $dep2 (OpenBSD::Requiring->new($dep)->list) {
46			push(@{$self->{todo}}, $dep2) unless $done->{$dep2};
47		}
48		$known->{$dep} = 1;
49		if ($self->find_in_new_source($solver, $state, $obj, $dep)) {
50			$dependencies->{$dep} = 1;
51			return 1;
52		}
53	}
54	if (my $r = $self->find_elsewhere($solver, $state, $obj)) {
55		$dependencies->{$r} = 1;
56		return 1;
57	}
58
59	return 0;
60}
61
62sub new
63{
64	my ($class, $solver) = @_;
65
66	# prepare for closure
67	my @todo = $solver->dependencies;
68	bless { todo => \@todo, done => {}, known => {} }, $class;
69}
70
71sub dump
72{
73	my ($self, $state) = @_;
74
75	return unless %{$self->{done}};
76	$state->say("Full dependency tree is #1",
77	    join(' ', keys %{$self->{done}}));
78}
79
80package OpenBSD::lookup::library;
81our @ISA=qw(OpenBSD::lookup);
82
83sub say_found
84{
85	my ($self, $state, $obj, $where) = @_;
86
87	$state->say("found libspec #1 in #2", $obj->to_string, $where)
88	    if $state->verbose >= 3;
89}
90
91sub find_in_already_done
92{
93	my ($self, $solver, $state, $obj) = @_;
94
95
96	my $r = $solver->check_lib_spec($solver->{localbase}, $obj,
97	    $self->{known});
98	if ($r) {
99		$self->say_found($state, $obj, $state->f("package #1", $r));
100		return $r;
101	} else {
102		return undef;
103	}
104}
105
106sub find_in_extra_sources
107{
108	my ($self, $solver, $state, $obj) = @_;
109	return undef if !$obj->is_valid || defined $obj->{dir};
110
111	OpenBSD::SharedLibs::add_libs_from_system($state->{destdir}, $state);
112	for my $dir (OpenBSD::SharedLibs::system_dirs()) {
113		if ($solver->check_lib_spec($dir, $obj, {system => 1})) {
114			$self->say_found($state, $obj, $state->f("#1/lib", $dir));
115			return 'system';
116		}
117	}
118	return undef;
119}
120
121sub find_in_new_source
122{
123	my ($self, $solver, $state, $obj, $dep) = @_;
124
125	if (defined $solver->{set}->{newer}->{$dep}) {
126		OpenBSD::SharedLibs::add_libs_from_plist($solver->{set}->{newer}->{$dep}->plist, $state);
127	} else {
128		OpenBSD::SharedLibs::add_libs_from_installed_package($dep, $state);
129	}
130	if ($solver->check_lib_spec($solver->{localbase}, $obj, {$dep => 1})) {
131		$self->say_found($state, $obj, $state->f("package #1", $dep));
132		return $dep;
133	}
134	return undef;
135}
136
137sub find_elsewhere
138{
139	my ($self, $solver, $state, $obj) = @_;
140
141	for my $n ($solver->{set}->newer) {
142		for my $dep (@{$n->dependency_info->{depend}}) {
143			my $r = $solver->find_old_lib($state,
144			    $solver->{localbase}, $dep->{pattern}, $obj);
145			if ($r) {
146				$self->say_found($state, $obj,
147				    $state->f("old package #1", $r));
148				return $r;
149			}
150		}
151	}
152	return undef;
153}
154
155package OpenBSD::lookup::tag;
156our @ISA=qw(OpenBSD::lookup);
157sub find_in_extra_sources
158{
159}
160
161sub find_elsewhere
162{
163}
164
165sub find_in_already_done
166{
167	my ($self, $solver, $state, $obj) = @_;
168	my $r = $self->{known_tags}->{$obj};
169	if (defined $r) {
170		$state->say("Found tag #1 in #2", $obj, $r)
171		    if $state->verbose >= 3;
172	}
173	return $r;
174}
175
176sub find_in_plist
177{
178	my ($self, $plist, $dep) = @_;
179	if ($plist->has('define-tag')) {
180		for my $t (@{$plist->{'define-tag'}}) {
181			$self->{known_tags}->{$t->name} = $dep;
182		}
183	}
184}
185
186sub find_in_new_source
187{
188	my ($self, $solver, $state, $obj, $dep) = @_;
189	my $plist = OpenBSD::PackingList->from_installation($dep,
190	    \&OpenBSD::PackingList::DependOnly);
191	if (!defined $plist) {
192		$state->errsay("Can't read plist for #1", $dep);
193	}
194	$self->find_in_plist($plist, $dep);
195	return $self->find_in_already_done($solver, $state, $obj);
196}
197
198package _cache;
199
200sub new
201{
202	my ($class, $v) = @_;
203	bless \$v, $class;
204}
205
206sub pretty
207{
208	my $self = shift;
209	return ref($self)."(".$$self.")";
210}
211
212package _cache::self;
213our @ISA=(qw(_cache));
214sub do
215{
216	my ($v, $solver, $state, $dep, $package) = @_;
217	push(@{$package->{before}}, $$v);
218	return $$v;
219}
220
221package _cache::installed;
222our @ISA=(qw(_cache));
223sub do
224{
225	my ($v, $solver, $state, $dep, $package) = @_;
226	return $$v;
227}
228
229package _cache::bad;
230our @ISA=(qw(_cache));
231sub do
232{
233	my ($v, $solver, $state, $dep, $package) = @_;
234	return $$v;
235}
236
237package _cache::to_install;
238our @ISA=(qw(_cache));
239sub do
240{
241	my ($v, $solver, $state, $dep, $package) = @_;
242	if ($state->tracker->{uptodate}{$$v}) {
243		bless $v, "_cache::installed";
244		$solver->set_global($dep, $v);
245		return $$v;
246	}
247	if ($state->tracker->{cant_install}{$$v}) {
248		bless $v, "_cache::bad";
249		$solver->set_global($dep, $v);
250		return $$v;
251	}
252	if ($state->tracker->{to_install}{$$v}) {
253		my $set = $state->tracker->{to_install}{$$v};
254		if ($set->real_set eq $solver->{set}) {
255			bless $v, "_cache::self";
256			return $v->do($solver, $state, $dep, $package);
257		} else {
258			$solver->add_dep($set);
259			return $$v;
260		}
261	}
262	return;
263}
264
265package _cache::to_update;
266our @ISA=(qw(_cache));
267sub do
268{
269	my ($v, $solver, $state, $dep, $package) = @_;
270	my $alt = $solver->find_dep_in_self($state, $dep);
271	if ($alt) {
272		$solver->set_cache($dep, _cache::self->new($alt));
273		push(@{$package->{before}}, $alt);
274		return $alt;
275	}
276
277	if ($state->tracker->{to_update}{$$v}) {
278		$solver->add_dep($state->tracker->{to_update}{$$v});
279		return $$v;
280	}
281	if ($state->tracker->{uptodate}{$$v}) {
282		bless $v, "_cache::installed";
283		$solver->set_global($dep, $v);
284		return $$v;
285	}
286	if ($state->tracker->{cant_update}{$$v}) {
287		bless $v, "_cache::bad";
288		$solver->set_global($dep, $v);
289		return $$v;
290	}
291	my @candidates = $dep->spec->filter(keys %{$state->tracker->{installed}});
292	if (@candidates > 0) {
293		$solver->set_global($dep, _cache::installed->new($candidates[0]));
294		return $candidates[0];
295	}
296	return;
297}
298
299package OpenBSD::Cloner;
300sub clone
301{
302	my ($self, $h, @extra) = @_;
303	for my $extra (@extra) {
304		next unless defined $extra;
305		while (my ($k, $e) = each %{$extra->{$h}}) {
306			$self->{$h}{$k} //= $e;
307		}
308	}
309}
310
311package OpenBSD::Dependencies::SolverBase;
312our @ISA = qw(OpenBSD::Cloner);
313
314my $global_cache = {};
315
316sub cached
317{
318	my ($self, $dep) = @_;
319	return $global_cache->{$dep->{pattern}} ||
320	    $self->{cache}{$dep->{pattern}};
321}
322
323sub set_cache
324{
325	my ($self, $dep, $value) = @_;
326	$self->{cache}{$dep->{pattern}} = $value;
327}
328
329sub set_global
330{
331	my ($self, $dep, $value) = @_;
332	$global_cache->{$dep->{pattern}} = $value;
333}
334
335sub global_cache
336{
337	my ($self, $pattern) = @_;
338	return $global_cache->{$pattern};
339}
340
341sub find_candidate
342{
343	my ($self, $dep, @list) = @_;
344	my @candidates = $dep->spec->filter(@list);
345	if (@candidates >= 1) {
346		return $candidates[0];
347	} else {
348		return undef;
349	}
350}
351
352sub solve_dependency
353{
354	my ($self, $state, $dep, $package) = @_;
355
356	my $v;
357
358	if (defined $self->cached($dep)) {
359		if ($state->defines('stat_cache')) {
360			if (defined $self->global_cache($dep->{pattern})) {
361				$state->print("Global ");
362			}
363			$state->say("Cache hit on #1: #2", $dep->{pattern},
364			    $self->cached($dep)->pretty);
365		}
366		$v = $self->cached($dep)->do($self, $state, $dep, $package);
367		return $v if $v;
368	}
369	if ($state->defines('stat_cache')) {
370		$state->say("No cache hit on #1", $dep->{pattern});
371	}
372
373	$self->really_solve_dependency($state, $dep, $package);
374}
375
376sub solve_depends
377{
378	my ($self, $state) = @_;
379
380	$self->{all_dependencies} = {};
381	$self->{to_register} = {};
382	$self->{deplist} = {};
383	delete $self->{installed};
384
385	for my $package ($self->{set}->newer, $self->{set}->kept) {
386		$package->{before} = [];
387		for my $dep (@{$package->dependency_info->{depend}}) {
388			my $v = $self->solve_dependency($state, $dep, $package);
389			# XXX
390			next if !defined $v;
391			$self->{all_dependencies}->{$v} = $dep;
392			$self->{to_register}->{$package}->{$v} = $dep;
393		}
394	}
395
396	return values %{$self->{deplist}};
397}
398
399sub solve_wantlibs
400{
401	my ($solver, $state) = @_;
402	my $okay = 1;
403
404	my $lib_finder = OpenBSD::lookup::library->new($solver);
405	for my $h ($solver->{set}->newer) {
406		for my $lib (@{$h->{plist}->{wantlib}}) {
407			$solver->{localbase} = $h->{plist}->localbase;
408			next if $lib_finder->lookup($solver,
409			    $solver->{to_register}->{$h}, $state,
410			    $lib->spec);
411			if ($okay) {
412				$solver->errsay_library($state, $h);
413			}
414			$okay = 0;
415			OpenBSD::SharedLibs::report_problem($state,
416			    $lib->spec);
417		}
418	}
419	if (!$okay) {
420		$solver->dump($state);
421		$lib_finder->dump($state);
422	}
423	return $okay;
424}
425
426sub dump
427{
428	my ($self, $state) = @_;
429	if ($self->dependencies) {
430	    $state->print("Direct dependencies for #1 resolve to #2",
431	    	$self->{set}->print, join(' ',  $self->dependencies));
432	    $state->print(" (todo: #1)",
433	    	join(' ', (map {$_->print} values %{$self->{deplist}})))
434	    	if %{$self->{deplist}};
435	    $state->print("\n");
436	}
437}
438
439sub dependencies
440{
441	my $self = shift;
442	if (wantarray) {
443		return keys %{$self->{all_dependencies}};
444	} else {
445		return scalar(%{$self->{all_dependencies}});
446	}
447}
448
449sub check_lib_spec
450{
451	my ($self, $base, $spec, $dependencies) = @_;
452	my $r = OpenBSD::SharedLibs::lookup_libspec($base, $spec);
453	for my $candidate (@$r) {
454		if ($dependencies->{$candidate->origin}) {
455			return $candidate->origin;
456		}
457	}
458	return;
459}
460
461sub find_dep_in_installed
462{
463	my ($self, $state, $dep) = @_;
464
465	return $self->find_candidate($dep, @{$self->installed_list});
466}
467
468sub find_dep_in_self
469{
470	my ($self, $state, $dep) = @_;
471
472	return $self->find_candidate($dep, $self->{set}->newer_names);
473}
474
475use OpenBSD::PackageInfo;
476OpenBSD::Auto::cache(installed_list,
477	sub {
478		my $self = shift;
479		my @l = installed_packages();
480
481		for my $o ($self->{set}->older_names) {
482			@l = grep {$_ ne $o} @l;
483		}
484		return \@l;
485	}
486);
487
488sub add_dep
489{
490	my ($self, $d) = @_;
491	$self->{deplist}{$d} = $d;
492}
493
494package OpenBSD::Dependencies::Solver;
495our @ISA = qw(OpenBSD::Dependencies::SolverBase);
496
497use OpenBSD::PackageInfo;
498
499sub merge
500{
501	my ($solver, @extra) = @_;
502
503	$solver->clone('cache', @extra);
504}
505
506sub new
507{
508	my ($class, $set) = @_;
509	bless { set => $set, bad => [] }, $class;
510}
511
512sub check_for_loops
513{
514	my ($self, $state) = @_;
515
516	my $initial = $self->{set};
517
518	my @todo = ();
519	my @to_merge = ();
520	push(@todo, $initial);
521	my $done = {};
522
523	while (my $set = shift @todo) {
524		next unless defined $set->{solver};
525		for my $l (values %{$set->solver->{deplist}}) {
526			if ($l eq $initial) {
527				push(@to_merge, $set);
528			}
529			next if $done->{$l};
530			next if $done->{$l->real_set};
531			push(@todo, $l);
532			$done->{$l} = $set;
533		}
534	}
535	if (@to_merge > 0) {
536		my $merged = {};
537		my @real = ();
538		$state->say("Detected loop, merging sets #1", $state->ntogo);
539		$state->say("| #1", $initial->print);
540		for my $set (@to_merge) {
541			my $k = $set;
542			while ($k ne $initial && !$merged->{$k}) {
543				unless ($k->{finished}) {
544					$state->say("| #1", $k->print);
545					delete $k->solver->{deplist};
546					push(@real, $k);
547				}
548				$merged->{$k} = 1;
549				$k = $done->{$k};
550			}
551		}
552		delete $initial->solver->{deplist};
553		$initial->merge($state->tracker, @real);
554	}
555}
556
557sub find_dep_in_repositories
558{
559	my ($self, $state, $dep) = @_;
560
561	return unless $dep->spec->is_valid;
562
563	my $candidates = $self->{set}->match_locations($dep->spec);
564	if (!$state->defines('allversions')) {
565		require OpenBSD::Search;
566		$candidates = OpenBSD::Search::FilterLocation->
567		    keep_most_recent->filter_locations($candidates);
568	}
569	# XXX not really efficient, but hey
570	my %c = map {($_->name, $_)} @$candidates;
571	my @pkgs = keys %c;
572	if (@pkgs == 1) {
573		return $candidates->[0];
574	} elsif (@pkgs > 1) {
575		# unless -ii, we return the def if available
576		if ($state->is_interactive < 2) {
577			if (defined(my $d = $c{$dep->{def}})) {
578				return $d;
579			}
580		}
581		# put default first if available
582		@pkgs = ((grep {$_ eq $dep->{def}} @pkgs),
583		    (sort (grep {$_ ne $dep->{def}} @pkgs)));
584		my $good = $state->ask_list(
585		    'Ambiguous: choose dependency for '.$self->{set}->print.': ',
586		    @pkgs);
587		return $c{$good};
588	} else {
589		return;
590	}
591}
592
593sub find_dep_in_stuff_to_install
594{
595	my ($self, $state, $dep) = @_;
596
597	my $v = $self->find_candidate($dep,
598	    keys %{$state->tracker->{uptodate}});
599	if ($v) {
600		$self->set_global($dep, _cache::installed->new($v));
601		return $v;
602	}
603	# this is tricky, we don't always know what we're going to actually
604	# install yet.
605	my @candidates = $dep->spec->filter(keys %{$state->tracker->{to_update}});
606	if (@candidates > 0) {
607		for my $k (@candidates) {
608			my $set = $state->tracker->{to_update}{$k};
609			$self->add_dep($set);
610		}
611		if (@candidates == 1) {
612			$self->set_cache($dep,
613			    _cache::to_update->new($candidates[0]));
614		}
615		return $candidates[0];
616	}
617
618	$v = $self->find_candidate($dep, keys %{$state->tracker->{to_install}});
619	if ($v) {
620		$self->set_cache($dep, _cache::to_install->new($v));
621		$self->add_dep($state->tracker->{to_install}->{$v});
622	}
623	return $v;
624}
625
626sub really_solve_dependency
627{
628	my ($self, $state, $dep, $package) = @_;
629
630	my $v;
631
632	if ($state->{allow_replacing}) {
633
634		$v = $self->find_dep_in_self($state, $dep);
635		if ($v) {
636			$self->set_cache($dep, _cache::self->new($v));
637			push(@{$package->{before}}, $v);
638			return $v;
639		}
640		$v = $self->find_candidate($dep, $self->{set}->older_names);
641		if ($v) {
642			push(@{$self->{bad}}, $dep->{pattern});
643			return $v;
644		}
645		$v = $self->find_dep_in_stuff_to_install($state, $dep);
646		return $v if $v;
647	}
648
649	$v = $self->find_dep_in_installed($state, $dep);
650	if ($v) {
651		if ($state->{newupdates}) {
652			if ($state->tracker->is_known($v)) {
653				return $v;
654			}
655			my $set = $state->updateset->add_older(OpenBSD::Handle->create_old($v, $state));
656			$set->merge_paths($self->{set});
657			$self->add_dep($set);
658			$self->set_cache($dep, _cache::to_update->new($v));
659			$state->tracker->todo($set);
660		}
661		return $v;
662	}
663	if (!$state->{allow_replacing}) {
664		$v = $self->find_dep_in_stuff_to_install($state, $dep);
665		return $v if $v;
666	}
667
668	$v = $self->find_dep_in_repositories($state, $dep);
669
670	my $s;
671	if ($v) {
672		$s = $state->updateset_from_location($v);
673		$v = $v->name;
674	} else {
675		# resort to default if nothing else
676		$v = $dep->{def};
677		$s = $state->updateset_with_new($v);
678	}
679
680	$s->merge_paths($self->{set});
681	$state->tracker->todo($s);
682	$self->add_dep($s);
683	$self->set_cache($dep, _cache::to_install->new($v));
684	return $v;
685}
686
687sub check_depends
688{
689	my $self = shift;
690
691	for my $dep ($self->dependencies) {
692		push(@{$self->{bad}}, $dep)
693		    unless is_installed($dep) or
694		    	defined $self->{set}->{newer}->{$dep};
695	}
696	return $self->{bad};
697}
698
699sub register_dependencies
700{
701	my ($self, $state) = @_;
702
703	require OpenBSD::RequiredBy;
704	for my $pkg ($self->{set}->newer) {
705		my $pkgname = $pkg->pkgname;
706		my @l = keys %{$self->{to_register}->{$pkg}};
707
708		OpenBSD::Requiring->new($pkgname)->add(@l);
709		for my $dep (@l) {
710			OpenBSD::RequiredBy->new($dep)->add($pkgname);
711		}
712	}
713}
714
715sub repair_dependencies
716{
717	my ($self, $state) = @_;
718	for my $p ($self->{set}->newer) {
719		my $pkgname = $p->pkgname;
720		for my $pkg (installed_packages(1)) {
721			my $plist = OpenBSD::PackingList->from_installation(
722			    $pkg, \&OpenBSD::PackingList::DependOnly);
723			$plist->repair_dependency($pkg, $pkgname);
724		}
725	}
726}
727
728sub find_old_lib
729{
730	my ($self, $state, $base, $pattern, $lib) = @_;
731
732	require OpenBSD::Search;
733
734	my $r = $state->repo->installed->match_locations(OpenBSD::Search::PkgSpec->new(".libs-".$pattern));
735	for my $try (map {$_->name} @$r) {
736		OpenBSD::SharedLibs::add_libs_from_installed_package($try, $state);
737		if ($self->check_lib_spec($base, $lib, {$try => 1})) {
738			return $try;
739		}
740	}
741	return undef;
742}
743
744sub errsay_library
745{
746	my ($solver, $state, $h) = @_;
747
748	$state->errsay("Can't install #1 because of libraries", $h->pkgname);
749}
750
751sub solve_tags
752{
753	my ($solver, $state) = @_;
754	my $okay = 1;
755
756	my $tag_finder = OpenBSD::lookup::tag->new($solver);
757	for my $h ($solver->{set}->newer) {
758		for my $tag (keys %{$h->{plist}->{tags}}) {
759			next if $tag_finder->lookup($solver,
760			    $solver->{to_register}->{$h}, $state, $tag);
761			$state->errsay("Can't install #1: tag definition not found #2",
762			    $h->pkgname, $tag);
763			if ($okay) {
764				$solver->dump($state);
765				$tag_finder->dump($state);
766				$okay = 0;
767			}
768	    	}
769	}
770	return $okay;
771}
772
773package OpenBSD::PackingElement;
774sub repair_dependency
775{
776}
777
778package OpenBSD::PackingElement::Dependency;
779sub repair_dependency
780{
781	my ($self, $requiring, $required) = @_;
782	if ($self->spec->filter($required) == 1) {
783		require OpenBSD::RequiredBy;
784		OpenBSD::RequiredBy->new($required)->add($requiring);
785		OpenBSD::Requiring->new($requiring)->add($required);
786	}
787}
788
7891;
790