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