6 * Written by Keith Marshall <keithmarshall@users.sourceforge.net>
7 * Copyright (C) 2009, 2010, 2011, MinGW Project
10 * Implementation of the package dependency resolver method, of the
11 * "pkgXmlDocument" class; includes the interface to the action item
12 * task scheduler, which is called to ensure that processing for any
13 * identified prerequisite packages is appropriately scheduled.
16 * This is free software. Permission is granted to copy, modify and
17 * redistribute this software, under the provisions of the GNU General
18 * Public License, Version 3, (or, at your option, any later version),
19 * as published by the Free Software Foundation; see the file COPYING
20 * for licensing details.
22 * Note, in particular, that this software is provided "as is", in the
23 * hope that it may prove useful, but WITHOUT WARRANTY OF ANY KIND; not
24 * even an implied WARRANTY OF MERCHANTABILITY, nor of FITNESS FOR ANY
25 * PARTICULAR PURPOSE. Under no circumstances will the author, or the
26 * MinGW Project, accept liability for any damages, however caused,
27 * arising from the use of this software.
39 /* FIXME: the following declaration belongs in a future "pkgmsgs.h"
40 * header file, with the function implementation in a separate C or C++
41 * messages source file, with appropriate internationalisation...
43 EXTERN_C const char *pkgMsgUnknownPackage( void );
45 const char *pkgMsgUnknownPackage( void )
47 /* FIXME: (see note above); return English language only, for now.
49 return "%s: unknown package\n";
52 static bool is_installed( pkgXmlNode *release )
54 /* Helper to check installation status of a specified package release.
58 * First, check for any 'installed' attribute which may have been
59 * explicitly specified for the 'release' record...
61 if( (status = release->GetPropVal( installed_key, NULL )) != NULL )
63 * ...immediately returning the status deduced from it,
66 return (strcmp( status, yes_value ) == 0);
68 /* When the package definition itself doesn't bear an explicit
69 * 'installed' attribute, then we must check the system map for
70 * an associated installation record...
73 if( ((pkgname = release->GetPropVal( tarname_key, NULL )) != NULL)
74 && (release->GetInstallationRecord( pkgname ) != NULL) )
76 /* ...and, when one is found, we can mark this package with
77 * an explicit status attribute for future reference, before
78 * we return confirmation of the installed status...
80 release->SetAttribute( installed_key, yes_value );
84 /* If we get to here, we may deduce that the package is not
85 * installed; once again, we set the explicit attribute value
86 * to convey this for future reference, before returning the
87 * appropriate status flag.
89 release->SetAttribute( installed_key, no_value );
93 pkgXmlNode *pkgXmlNode::GetInstallationRecord( const char *pkgname )
95 /* Retrieve the installation record, if any, for the package
96 * specified by fully qualified canonical 'pkgname'.
98 * First, break down the specified package name, and retrieve
99 * the sysroot database entry for its associated subsystem.
102 pkgSpecs lookup( pkgname );
103 if( (sysroot = GetSysRoot( lookup.GetSubSystemName() )) != NULL )
105 /* We successfully retrieved a sysroot entry; now we must
106 * search the associated list of installed packages, for one
107 * with the appropriate canonical package name.
109 pkgXmlNode *pkg = sysroot->FindFirstAssociate( installed_key );
112 /* We found an installed package entry; check if it has
113 * the correct canonical name...
115 const char *installed = pkg->GetPropVal( tarname_key, NULL );
116 if( (installed != NULL) && (strcmp( installed, pkgname ) == 0) )
118 * ...returning this entry if so...
122 /* ...otherwise, move on to the next entry, if any.
124 pkg = pkg->FindNextAssociate( installed_key );
128 /* If we get to here, we didn't find an entry for the required
129 * package; return NULL, indicating that it is not installed.
134 const char *pkgXmlNode::GetContainerAttribute( const char *key, const char *sub )
136 /* Walk the XML path from current element, back towards the document root,
137 * until we find the innermost element which has an attribute matching "key";
138 * if such an element is found, return the value of the attribute; if we have
139 * traversed the entire path, all the way to the document root, and we have
140 * not found any element with the "key" attribute, return "sub".
142 pkgXmlNode *pkg = this;
143 pkgXmlNode *root = pkg->GetDocumentRoot();
146 /* We haven't yet tried to search beyond the document root;
147 * try matching "key" to an attribute of the current element...
149 const char *retval = pkg->GetPropVal( key, NULL );
152 * ...returning its value, if such an attribute is found...
157 * take a further step back towards the document root.
159 pkg = (pkg == root) ? NULL : pkg->GetParent();
162 /* If we get to here, then no element with the required "key"
163 * attribute could be found; substitute the specified default.
169 pkgXmlDocument::ResolveDependencies( pkgXmlNode* package, pkgActionItem* rank )
170 # define promote( request, action ) (((request) & (~ACTION_MASK)) | action )
172 /* For the specified "package", (nominally a "release"), identify its
173 * prerequisites, (as specified by "requires" tags), and schedule actions
174 * to process them; repeat recursively, to identify further dependencies
175 * of such prerequisites, and finally, extend the search to capture
176 * additional dependencies common to the containing package group.
178 pkgSpecs *refdata = NULL;
179 pkgXmlNode *refpkg = package;
181 while( package != NULL )
183 /* We have a valid XML entity, which may identify dependencies;
184 * check if it includes any "requires" specification...
186 pkgXmlNode *dep = package->FindFirstAssociate( requires_key );
189 /* We found a dependency specification...
190 * Initially, assume this package is not installed.
192 pkgXmlNode *installed = NULL;
194 /* To facilitate resolution of "%" version matching wildcards
195 * in the requirements specification, we need to parse the version
196 * specification for the current dependent package...
198 if( refdata == NULL )
200 /* ...but we deferred that until we knew for sure that it would
201 * be needed; it is, so parse it now.
204 if( (refname = refpkg->GetPropVal( tarname_key, NULL )) != NULL )
205 refdata = new pkgSpecs( refname );
208 /* Identify the prerequisite package, from its canonical name...
210 pkgActionItem wanted; pkgXmlNode *selected;
211 pkgSpecs req( wanted.SetRequirements( dep, refdata ) );
213 * (Both the package name, and subsystem if specified, must match)...
215 selected = FindPackageByName( req.GetPackageName(), req.GetSubSystemName() );
217 /* When we've identified the appropriate package...
219 if( selected != NULL )
221 /* ...and, more significantly, the appropriate component package,
222 * where applicable...
224 pkgXmlNode *component; const char *reqclass;
225 if( (reqclass = req.GetComponentClass()) == NULL )
226 reqclass = value_unknown;
228 if( (component = selected->FindFirstAssociate( component_key )) == NULL )
230 * ...but if no separate component package exists,
231 * consider the parent package itself, as sole component.
233 component = selected;
235 /* At this point, we have no more than a tentative package selection;
236 * it may not provide a component to fit the requirements specification.
237 * Thus, kill the selection, pending reaffirmation...
240 while( component != NULL )
242 /* ...by stepping through the "releases" of this component package...
244 pkgXmlNode *required = component->FindFirstAssociate( release_key );
245 while( required != NULL )
247 /* ...noting if we find one already marked as "installed"...
249 const char *tstclass;
250 pkgSpecs tst( required->GetPropVal( tarname_key, NULL ) );
251 if( (tstclass = tst.GetComponentClass()) == NULL )
252 tstclass = value_unknown;
254 if( is_installed( required ) && (strcmp( tstclass, reqclass ) == 0) )
255 installed = required;
257 /* ...and identify the most suitable candidate "release"
258 * to satisfy the current dependency...
260 if( wanted.SelectIfMostRecentFit( required ) == required )
261 selected = component = required;
263 /* ...continuing, until all available "releases"
264 * have been evaluated accordingly.
266 required = required->FindNextAssociate( release_key );
269 /* Where multiple component packages do exist,
270 * continue until all have been inspected.
272 component = component->FindNextAssociate( component_key );
275 /* We have now identified the most suitable candidate package,
276 * to resolve the current dependency...
280 /* ...this package is already installed, so we may schedule
281 * a resolved dependency match, with no pending action...
283 unsigned long fallback = request & ~ACTION_MASK;
284 if( (selected != NULL) && (selected != installed) )
286 /* ...but, if there is a better candidate than the installed
287 * version, we prefer to schedule an upgrade.
289 fallback |= ACTION_UPGRADE;
290 wanted.SelectPackage( installed, to_remove );
292 rank = Schedule( fallback, wanted, rank );
295 else if( ((request & ACTION_MASK) == ACTION_INSTALL)
297 * The required package is not installed...
298 * When performing an installation, ...
300 || ((request & (ACTION_PRIMARY | ACTION_INSTALL)) == ACTION_INSTALL) )
302 * or when this is a new requirement of a package
303 * which is being upgraded, then we must schedule it
304 * for installation now; (we may simply ignore it, if
305 * we are performing a removal).
307 rank = Schedule( promote( request, ACTION_INSTALL ), wanted, rank );
309 /* Regardless of the action scheduled, we must recursively
310 * consider further dependencies of the resolved prerequisite;
311 * FIXME: do we need to do this, when performing a removal?
312 * Right now, I (KDM) don't think so...
314 if( (request & ACTION_INSTALL) != 0 )
315 ResolveDependencies( selected, rank );
318 if( selected == NULL )
320 /* No package matching the selection criteria could be found;
321 * report a dependency resolution failure in respect of each
322 * specified criterion...
324 const char *ref, *key[] = { lt_key, le_key, eq_key, ge_key, gt_key };
325 const char *requestor = refpkg->GetPropVal( tarname_key, value_unknown );
327 dmh_control( DMH_BEGIN_DIGEST );
328 dmh_notify( DMH_ERROR, "%s: requires...\n", requestor );
329 for( int i = 0; i < sizeof( key ) / sizeof( char* ); i++ )
330 if( (ref = dep->GetPropVal( key[i], NULL )) != NULL )
332 dmh_notify( DMH_ERROR, "%s: unresolved dependency (type '%s')\n", ref, key[i] );
333 dmh_notify( DMH_ERROR, "%s: cannot identify any providing package\n" );
335 dmh_notify( DMH_ERROR, "please report this to the package maintainer\n" );
336 dmh_control( DMH_END_DIGEST );
339 /* Continue, until all prerequisites of the current package
340 * have been evaluated.
342 dep = dep->FindNextAssociate( requires_key );
344 /* Also consider any dependencies which may be common to
345 * all releases, or all components, of the current package;
346 * we do this by walking back through the XML hierarchy,
347 * searching for "requires" elements in all containing
348 * contexts, until we reach the root element.
350 package = (package == GetRoot()) ? NULL : package->GetParent();
355 static inline bool assert_unmatched
356 ( const char *ref, const char *val, const char *name, const char *alias )
358 # define if_noref( name ) ((name == NULL) || (*name == '\0'))
359 # define if_match( ref, name ) ((name != NULL) && (strcmp( ref, name ) == 0))
360 # define if_alias( ref, list ) ((list != NULL) && has_keyword( ref, list ))
362 /* Helper for the following "assert_installed" function; it determines if
363 * the reference name specified by "ref" matches either the corresponding
364 * field value "val" from a tarname look-up, or in the case of a package
365 * name reference, the containing package "name" attribute or any of its
366 * specified "alias" names. The return value is false, in the case of a
367 * match, or true when unmatched.
371 ? /* When "ref" is NULL, then a match requires all specified candidates
372 * for matching to also be NULL, or to be pointers to empty strings.
374 !( if_noref( val ) && if_noref( name ) && if_noref( alias ))
376 : /* Otherwise, when "ref" is not NULL, then a match is identified when
377 * any one candidate is found to match.
379 !( if_match( ref, val ) || if_match( ref, name ) || if_alias( ref, alias ));
383 pkgXmlNode *assert_installed( pkgXmlNode *current, pkgXmlNode *installed )
385 /* Validation hook for pkgXmlDocument::Schedule(); it checks for
386 * possible prior installation of an obsolete version of a current
387 * package, (i.e. the package itself is listed in the distribution
388 * manifest, but the listing for the installed version has been
391 * Note that, by the time this helper is called, an installation
392 * may have been identified already, by a release reference which
393 * is still present in the distribution manifest; we perform this
394 * check, only if no such identification was possible.
396 if( current && (installed == NULL) )
398 /* This is the specific case where we have selected a current
399 * package for processing, but we HAVE NOT been able to identify
400 * a prior installation through a distribution manifest reference;
401 * thus, we must perform the further check for prior installation
402 * of an obsolete version.
404 * Starting from the sysroot record for the specified release...
406 pkgXmlNode *sysroot; const char *tarname;
407 pkgSpecs lookup( current->GetPropVal( tarname_key, NULL ) );
408 if( (sysroot = current->GetSysRoot( lookup.GetSubSystemName() )) != NULL )
410 /* ...identify the first, if any, package installation record.
412 pkgXmlNode *ref = sysroot->FindFirstAssociate( installed_key );
415 /* When at least one installation record exists,
416 * establish references for the "tarname" fields which
417 * we must match, to identify a prior installation.
419 const char *refname = lookup.GetPackageName();
420 const char *cptname = lookup.GetComponentClass();
421 const char *version = lookup.GetComponentVersion();
423 /* Also identify the formal name for the containing package,
424 * and any aliases by which it may also be known, so that we
425 * may be able to identify a prior installation which may
426 * have borne a deprecated package name.
428 const char *pkgname = current->GetContainerAttribute( name_key );
429 const char *alias = current->GetContainerAttribute( alias_key );
431 /* For each candidate installation record found...
435 /* ...check if it matches the look-up criteria.
437 pkgSpecs chk( tarname = ref->GetPropVal( tarname_key, NULL ) );
438 if( assert_unmatched( chk.GetPackageName(), refname, pkgname, alias )
439 || assert_unmatched( chk.GetComponentClass(), cptname, NULL, NULL )
440 || assert_unmatched( chk.GetComponentVersion(), version, NULL, NULL ) )
442 * This candidate isn't a match; try the next, if any...
444 ref = ref->FindNextAssociate( installed_key );
447 { /* We found a prior installation of a deprecated version;
448 * back-build a corresponding reference within the associated
449 * package or component-package inventory, in the internal
450 * copy of the distribution manifest...
452 if( (installed = new pkgXmlNode( release_key )) != NULL )
454 installed->SetAttribute( tarname_key, tarname );
455 installed->SetAttribute( installed_key, value_yes );
456 if( (ref = current->GetParent()) != NULL )
457 installed = ref->AddChild( installed );
459 /* Having found a prior installation, there is no need to
460 * check any further installation records; force "ref" to
461 * NULL, to inhibit further searching.
469 /* However we get to here, we always return the pointer to the installed
470 * package entry identified by the dependency resolver, which may, or may
471 * not have been modified by this function.
476 void pkgActionItem::ConfirmInstallationStatus()
478 /* Set the "to_remove" selection in an action item to match the installed
479 * package entry, even when the release in question is no longer enumerated
480 * in the package catalogue; (used to identify any installed version when
481 * compiling a package reference listing).
484 = assert_installed( selection[to_install], selection[to_remove] );
487 void pkgXmlDocument::Schedule( unsigned long action, const char* name )
489 /* Task scheduler interface; schedules actions to process dependencies
490 * for the package specified by "name".
493 if( (release = FindPackageByName( name )) != NULL )
495 /* We found the specification for the named package...
497 pkgXmlNode *component = release->FindFirstAssociate( component_key );
498 if( component != NULL )
500 * When it is subdivided into component-packages,
501 * we need to consider each as a possible candidate
502 * for task scheduling.
506 while( release != NULL )
508 /* Within each candidate package or component-package...
510 if( (release = release->FindFirstAssociate( release_key )) != NULL )
512 /* ...initially assume it is not installed, and that
513 * no installable upgrade is available.
515 pkgActionItem latest;
516 pkgXmlNode *installed = NULL, *upgrade = NULL;
518 /* Establish the action for which dependency resolution is
519 * to be performed; note that this may be promoted to a more
520 * inclusive class, during resolution, so we need to reset
521 * it for each new dependency which may be encountered.
525 /* Any action request processed here is, by definition,
526 * a request for a primary action; mark it as such.
528 action |= ACTION_PRIMARY;
530 /* For each candidate release in turn...
532 while( release != NULL )
534 /* ...inspect it to identify any which is already installed,
535 * and also the latest available...
537 if( is_installed( release ) )
539 * ...i.e. here we have identified a release
540 * which is currently installed...
542 latest.SelectPackage( installed = release, to_remove );
544 if( latest.SelectIfMostRecentFit( release ) == release )
546 * ...while this is the most recent we have
547 * encountered so far.
551 /* Continue with the next specified release, if any.
553 release = release->FindNextAssociate( release_key );
556 if( (installed = assert_installed( upgrade, installed )) == NULL )
558 /* There is no installed version...
559 * therefore, there is nothing to do for any action
560 * other than ACTION_INSTALL...
562 if( (action & ACTION_MASK) == ACTION_INSTALL )
564 * ...in which case, we must recursively resolve
565 * any dependencies for the scheduled "upgrade".
567 ResolveDependencies( upgrade, Schedule( action, latest ));
570 /* attempting ACTION_UPGRADE or ACTION_REMOVE
571 * is an error; diagnose it.
573 dmh_notify( DMH_ERROR, "%s %s: package is not installed\n",
574 action_name( action & ACTION_MASK ), name
578 else if( upgrade && (upgrade != installed) )
580 /* There is an installed version...
581 * but an upgrade to a newer version is available;
582 * ACTION_INSTALL implies ACTION_UPGRADE.
584 unsigned long fallback = action;
585 if( (action & ACTION_MASK) == ACTION_INSTALL )
586 fallback = ACTION_UPGRADE + (action & ~ACTION_MASK);
588 /* Again, we recursively resolve any dependencies
589 * for the scheduled upgrade.
591 ResolveDependencies( upgrade, Schedule( fallback, latest ));
595 /* In this case, the package is already installed,
596 * and no more recent release is available; we still
597 * recursively resolve its dependencies, to capture
598 * any potential upgrades for them.
600 ResolveDependencies( upgrade, Schedule( action, latest ));
603 if( (component = component->FindNextAssociate( component_key )) != NULL )
605 * When evaluating a component-package, we extend our
606 * evaluation, to consider for any further components of
607 * the current package.
614 /* We found no information on the requested package;
615 * diagnose as a non-fatal error.
617 dmh_notify( DMH_ERROR, pkgMsgUnknownPackage(), name );
620 /* $RCSfile$: end of file */