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