1# ex:ts=8 sw=4:
2# $OpenBSD: SolverBase.pm,v 1.13 2021/06/21 14:36:48 espie Exp $
3#
4# Copyright (c) 2005-2018 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
20# generic dependencies lookup class: walk the dependency tree as far
21# as necessary to resolve dependencies
22package OpenBSD::lookup;
23
24sub lookup
25{
26	my ($self, $solver, $dependencies, $state, $obj) = @_;
27
28	my $known = $self->{known};
29	if (my $r = $self->find_in_already_done($solver, $state, $obj)) {
30		$dependencies->{$r} = 1;
31		return 1;
32	}
33	if ($self->find_in_extra_sources($solver, $state, $obj)) {
34		return 1;
35	}
36	# lookup through the rest of the tree...
37	my $done = $self->{done};
38
39	while (my $dep = pop @{$self->{todo}}) {
40		require OpenBSD::RequiredBy;
41
42		next if $done->{$dep};
43		# may need to replace older dep with newer ?
44		my $newer = $self->may_adjust($solver, $state, $dep);
45		if (defined $newer) {
46			push(@{$self->{todo}}, $newer);
47			next;
48		}
49		$done->{$dep} = 1;
50		for my $dep2 (OpenBSD::Requiring->new($dep)->list) {
51			push(@{$self->{todo}}, $dep2) unless $done->{$dep2};
52		}
53		$known->{$dep} = 1;
54		if ($dep ne 'BaseSystem' && # XXX fake dependency
55		    # updated package -> base system, don't bother looking
56		    # (at this point there should be a fake handle but it's
57		    # simpler to just test rather than retrofit everything)
58		    $self->find_in_new_source($solver, $state, $obj, $dep)) {
59			$dependencies->{$dep} = 2;
60			return 1;
61		}
62	}
63	if (my $r = $self->find_elsewhere($solver, $state, $obj)) {
64		$dependencies->{$r} = 3;
65		return 1;
66	}
67
68	return 0;
69}
70
71# While walking the dependency tree, we may loop back to an older package,
72# because we're relying on dep lists on disk, that we haven't adjusted yet
73# since we're just checking. We need to prepare for the update here as well!
74sub may_adjust
75{
76	my ($self, $solver, $state, $dep) = @_;
77	my $h = $solver->{set}{older}{$dep};
78	if (defined $h) {
79		$state->print("Detecting older #1...", $dep)
80		    if $state->verbose >=3;
81		my $u = $h->{update_found};
82		if (!defined $u) {
83			$state->errsay("NO UPDATE FOUND for #1!", $dep);
84		} elsif ($u->pkgname ne $dep) {
85			$state->say("converting into #1", $u->pkgname)
86			    if $state->verbose >=3;
87			return $u->pkgname;
88		} else {
89			$state->say("didn't change")
90			    if $state->verbose >=3;
91		}
92	}
93	return undef;
94}
95
96sub new
97{
98	my ($class, $solver) = @_;
99
100	# prepare for closure
101	my @todo = $solver->dependencies;
102	bless { todo => \@todo, done => {}, known => {} }, $class;
103}
104
105sub dump
106{
107	my ($self, $state) = @_;
108
109	return unless %{$self->{done}};
110	$state->say("Full dependency tree is #1",
111	    join(' ', keys %{$self->{done}}));
112}
113
114package OpenBSD::lookup::library;
115our @ISA=qw(OpenBSD::lookup);
116
117sub say_found
118{
119	my ($self, $state, $obj, $where) = @_;
120
121	$state->say("found libspec #1 in #2", $obj->to_string, $where)
122	    if $state->verbose >= 3;
123}
124
125sub find_in_already_done
126{
127	my ($self, $solver, $state, $obj) = @_;
128
129
130	my $r = $solver->check_lib_spec($solver->{localbase}, $obj,
131	    $self->{known});
132	if ($r) {
133		$self->say_found($state, $obj, $state->f("package #1", $r));
134		return $r;
135	} else {
136		return undef;
137	}
138}
139
140sub find_in_extra_sources
141{
142	my ($self, $solver, $state, $obj) = @_;
143	return undef if !$obj->is_valid || defined $obj->{dir};
144
145	OpenBSD::SharedLibs::add_libs_from_system($state->{destdir}, $state);
146	for my $dir (OpenBSD::SharedLibs::system_dirs()) {
147		if ($solver->check_lib_spec($dir, $obj, {system => 1})) {
148			$self->say_found($state, $obj, $state->f("#1/lib", $dir));
149			return 'system';
150		}
151	}
152	return undef;
153}
154
155sub find_in_new_source
156{
157	my ($self, $solver, $state, $obj, $dep) = @_;
158
159	if (defined $solver->{set}{newer}{$dep}) {
160		OpenBSD::SharedLibs::add_libs_from_plist($solver->{set}{newer}{$dep}->plist, $state);
161	} else {
162		OpenBSD::SharedLibs::add_libs_from_installed_package($dep, $state);
163	}
164	if ($solver->check_lib_spec($solver->{localbase}, $obj, {$dep => 1})) {
165		$self->say_found($state, $obj, $state->f("package #1", $dep));
166		return $dep;
167	}
168	return undef;
169}
170
171sub find_elsewhere
172{
173	my ($self, $solver, $state, $obj) = @_;
174
175	for my $n ($solver->{set}->newer) {
176		for my $dep (@{$n->dependency_info->{depend}}) {
177			my $r = $solver->find_old_lib($state,
178			    $solver->{localbase}, $dep->{pattern}, $obj);
179			if ($r) {
180				$self->say_found($state, $obj,
181				    $state->f("old package #1", $r));
182				return $r;
183			}
184		}
185	}
186	return undef;
187}
188
189package OpenBSD::lookup::tag;
190our @ISA=qw(OpenBSD::lookup);
191sub new
192{
193	my ($class, $solver, $state) = @_;
194
195	# prepare for closure
196	if (!defined $solver->{old_dependencies}) {
197		$solver->solve_old_depends($state);
198	}
199	my @todo = ($solver->dependencies, keys %{$solver->{old_dependencies}});
200	bless { todo => \@todo, done => {}, known => {} }, $class;
201}
202
203sub find_in_extra_sources
204{
205}
206
207sub find_elsewhere
208{
209}
210
211sub find_in_already_done
212{
213	my ($self, $solver, $state, $obj) = @_;
214	my $r = $self->{known_tags}{$obj->name};
215	if (defined $r) {
216		my ($dep, $d) = @$r;
217		$obj->{definition_list} = $d;
218		$state->say("Found tag #1 in #2", $obj->stringize, $dep)
219		    if $state->verbose >= 3;
220		return $dep;
221	}
222	return undef;
223}
224
225sub find_in_plist
226{
227	my ($self, $plist, $dep) = @_;
228	if (defined $plist->{tags_definitions}) {
229		while (my ($name, $d) = each %{$plist->{tags_definitions}}) {
230			$self->{known_tags}{$name} = [$dep, $d];
231		}
232	}
233}
234
235sub find_in_new_source
236{
237	my ($self, $solver, $state, $obj, $dep) = @_;
238	my $plist;
239
240	if (defined $solver->{set}{newer}{$dep}) {
241		$plist = $solver->{set}{newer}{$dep}->plist;
242	} else {
243		$plist = OpenBSD::PackingList->from_installation($dep,
244		    \&OpenBSD::PackingList::DependOnly);
245	}
246	if (!defined $plist) {
247		$state->errsay("Can't read plist for #1", $dep);
248	}
249	$self->find_in_plist($plist, $dep);
250	return $self->find_in_already_done($solver, $state, $obj);
251}
252
253
254# both the solver and the conflict cache inherit from cloner
255# they both want to merge several hashes from extra data.
256package OpenBSD::Cloner;
257sub clone
258{
259	my ($self, $h, @extra) = @_;
260	for my $extra (@extra) {
261		next unless defined $extra;
262		while (my ($k, $e) = each %{$extra->{$h}}) {
263			$self->{$h}{$k} //= $e;
264		}
265	}
266}
267
268# The actual solver derives from SolverBase:
269# there is a specific subclass for pkg_create which does resolve
270# dependencies in a much lighter way than the normal pkg_add code.
271package OpenBSD::Dependencies::SolverBase;
272our @ISA = qw(OpenBSD::Cloner);
273
274my $global_cache = {};
275
276sub cached
277{
278	my ($self, $dep) = @_;
279	return $global_cache->{$dep->{pattern}} ||
280	    $self->{cache}{$dep->{pattern}};
281}
282
283sub set_cache
284{
285	my ($self, $dep, $value) = @_;
286	$self->{cache}{$dep->{pattern}} = $value;
287}
288
289sub set_global
290{
291	my ($self, $dep, $value) = @_;
292	$global_cache->{$dep->{pattern}} = $value;
293}
294
295sub global_cache
296{
297	my ($self, $pattern) = @_;
298	return $global_cache->{$pattern};
299}
300
301sub find_candidate
302{
303	my ($self, $dep, @list) = @_;
304	my @candidates = $dep->spec->filter(@list);
305	if (@candidates >= 1) {
306		return $candidates[0];
307	} else {
308		return undef;
309	}
310}
311
312sub solve_dependency
313{
314	my ($self, $state, $dep, $package) = @_;
315
316	my $v;
317
318	if (defined $self->cached($dep)) {
319		if ($state->defines('stat_cache')) {
320			if (defined $self->global_cache($dep->{pattern})) {
321				$state->print("Global ");
322			}
323			$state->say("Cache hit on #1: #2", $dep->{pattern},
324			    $self->cached($dep)->pretty);
325		}
326		$v = $self->cached($dep)->do($self, $state, $dep, $package);
327		return $v if $v;
328	}
329	if ($state->defines('stat_cache')) {
330		$state->say("No cache hit on #1", $dep->{pattern});
331	}
332
333	# we need an indirection because deleting is simpler
334	$state->solve_dependency($self, $dep, $package);
335}
336
337sub solve_depends
338{
339	my ($self, $state) = @_;
340
341	$self->{all_dependencies} = {};
342	$self->{to_register} = {};
343	$self->{deplist} = {};
344	delete $self->{installed_list};
345
346	for my $package ($self->{set}->newer, $self->{set}->kept) {
347		$package->{before} = [];
348		for my $dep (@{$package->dependency_info->{depend}}) {
349			my $v = $self->solve_dependency($state, $dep, $package);
350			# XXX
351			next if !defined $v;
352			$self->{all_dependencies}{$v} = $dep;
353			$self->{to_register}{$package}{$v} = $dep;
354		}
355	}
356
357	return sort values %{$self->{deplist}};
358}
359
360sub solve_wantlibs
361{
362	my ($solver, $state) = @_;
363	my $okay = 1;
364
365	my $lib_finder = OpenBSD::lookup::library->new($solver);
366	for my $h ($solver->{set}->newer) {
367		for my $lib (@{$h->{plist}->{wantlib}}) {
368			$solver->{localbase} = $h->{plist}->localbase;
369			next if $lib_finder->lookup($solver,
370			    $solver->{to_register}{$h}, $state,
371			    $lib->spec);
372			if ($okay) {
373				$solver->errsay_library($state, $h);
374			}
375			$okay = 0;
376			OpenBSD::SharedLibs::report_problem($state,
377			    $lib->spec);
378		}
379	}
380	if (!$okay) {
381		$solver->dump($state);
382		$lib_finder->dump($state);
383	}
384	return $okay;
385}
386
387sub dump
388{
389	my ($self, $state) = @_;
390	if ($self->dependencies) {
391	    $state->print("Direct dependencies for #1 resolve to #2",
392	    	$self->{set}->print, join(' ',  $self->dependencies));
393	    $state->print(" (todo: #1)",
394	    	join(' ', (map {$_->print} values %{$self->{deplist}})))
395	    	if %{$self->{deplist}};
396	    $state->print("\n");
397	}
398}
399
400sub dependencies
401{
402	my $self = shift;
403	if (wantarray) {
404		return keys %{$self->{all_dependencies}};
405	} else {
406		return scalar(%{$self->{all_dependencies}});
407	}
408}
409
410sub check_lib_spec
411{
412	my ($self, $base, $spec, $dependencies) = @_;
413	my $r = OpenBSD::SharedLibs::lookup_libspec($base, $spec);
414	for my $candidate (@$r) {
415		if ($dependencies->{$candidate->origin}) {
416			return $candidate->origin;
417		}
418	}
419	return;
420}
421
422sub find_dep_in_installed
423{
424	my ($self, $state, $dep) = @_;
425
426	return $self->find_candidate($dep, @{$self->installed_list});
427}
428
429sub find_dep_in_self
430{
431	my ($self, $state, $dep) = @_;
432
433	return $self->find_candidate($dep, $self->{set}->newer_names,
434	    $self->{set}->kept_names);
435}
436
437sub find_in_self
438{
439	my ($solver, $plist, $state, $tag) = @_;
440	return 0 unless defined $plist->{tags_definitions}{$tag->name};
441	$tag->{definition_list} = $plist->{tags_definitions}{$tag->name};
442	$tag->{found_in_self} = 1;
443	$state->say("Found tag #1 in self", $tag->stringize)
444	    if $state->verbose >= 3;
445	return 1;
446}
447
448use OpenBSD::PackageInfo;
449OpenBSD::Auto::cache(installed_list,
450	sub {
451		my $self = shift;
452		my @l = installed_packages();
453
454		for my $o ($self->{set}->older_names) {
455			@l = grep {$_ ne $o} @l;
456		}
457		return \@l;
458	}
459);
460
461sub add_dep
462{
463	my ($self, $d) = @_;
464	$self->{deplist}{$d} = $d;
465}
466
467
468sub verify_tag
469{
470	my ($self, $tag, $state, $plist, $is_old) = @_;
471	my $bad_return = $is_old ? 1 : 0;
472	my $type = $is_old ? "Warning" : "Error";
473	my $msg = "#1 in #2: \@tag #3";
474	if (!defined $tag->{definition_list}) {
475		$state->errsay("$msg definition not found",
476		    $type, $plist->pkgname, $tag->name);
477		return $bad_return;
478	}
479	my $use_params = 0;
480	for my $d (@{$tag->{definition_list}}) {
481		if ($d->need_params) {
482			$use_params = 1;
483			last;
484		}
485	}
486	if ($tag->{params} eq '' && $use_params && !$tag->{found_in_self}) {
487		$state->errsay(
488		    "$msg has no parameters but some define wants them",
489		    $type, $plist->pkgname, $tag->name);
490		return $bad_return;
491	} elsif ($tag->{params} ne '' && !$use_params) {
492		$state->errsay(
493		    "$msg has parameters but no define uses them",
494		    $type, $plist->pkgname, $tag->name);
495		return $bad_return;
496	}
497	return 1;
498}
499
5001;
501