src/pkgdeps.cpp

   1 /*
   2  * pkgdeps.cpp
   3  *
   4  * $Id$
   5  *
   6  * Written by Keith Marshall <keithmarshall@users.sourceforge.net>
   7  * Copyright (C) 2009, 2010, 2011, MinGW Project
   8  *
   9  *
  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.
  14  *
  15  *
  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.
  21  *
  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.
  28  *
  29  */
  30 #include <string.h>
  31
  32 #include "dmh.h"
  33
  34 #include "pkginfo.h"
  35 #include "pkgbase.h"
  36 #include "pkgkeys.h"
  37 #include "pkgtask.h"
  38
  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...
  42  */
  43 EXTERN_C const char *pkgMsgUnknownPackage( void );
  44
  45 const char *pkgMsgUnknownPackage( void )
  46 {
  47   /* FIXME: (see note above); return English language only, for now.
  48    */
  49   return "%s: unknown package\n";
  50 }
  51
  52 static bool is_installed( pkgXmlNode *release )
  53 {
  54   /* Helper to check installation status of a specified package release.
  55    */
  56   const char *status;
  57   /*
  58    * First, check for any 'installed' attribute which may have been
  59    * explicitly specified for the 'release' record...
  60    */
  61   if( (status = release->GetPropVal( installed_key, NULL )) != NULL )
  62     /*
  63      * ...immediately returning the status deduced from it,
  64      * when present.
  65      */
  66     return (strcmp( status, yes_value ) == 0);
  67
  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...
  71    */
  72   const char *pkgname;
  73   if( ((pkgname = release->GetPropVal( tarname_key, NULL )) != NULL)
  74   &&   (release->GetInstallationRecord( pkgname ) != NULL)  )
  75   {
  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...
  79      */
  80     release->SetAttribute( installed_key, yes_value );
  81     return true;
  82   }
  83
  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.
  88    */
  89   release->SetAttribute( installed_key, no_value );
  90   return false;
  91 }
  92
  93 pkgXmlNode *pkgXmlNode::GetInstallationRecord( const char *pkgname )
  94 {
  95   /* Retrieve the installation record, if any, for the package
  96    * specified by fully qualified canonical 'pkgname'.
  97    *
  98    * First, break down the specified package name, and retrieve
  99    * the sysroot database entry for its associated subsystem.
 100    */
 101   pkgXmlNode *sysroot;
 102   pkgSpecs lookup( pkgname );
 103   if( (sysroot = GetSysRoot( lookup.GetSubSystemName() )) != NULL )
 104   {
 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.
 108      */
 109     pkgXmlNode *pkg = sysroot->FindFirstAssociate( installed_key );
 110     while( pkg != NULL )
 111     {
 112       /* We found an installed package entry; check if it has
 113        * the correct canonical name...
 114        */
 115       const char *installed = pkg->GetPropVal( tarname_key, NULL );
 116       if( (installed != NULL) && (strcmp( installed, pkgname ) == 0) )
 117         /*
 118          * ...returning this entry if so...
 119          */
 120         return pkg;
 121
 122       /* ...otherwise, move on to the next entry, if any.
 123        */
 124       pkg = pkg->FindNextAssociate( installed_key );
 125     }
 126   }
 127
 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.
 130    */
 131   return NULL;
 132 }
 133
 134 const char *pkgXmlNode::GetContainerAttribute( const char *key, const char *sub )
 135 {
 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".
 141    */
 142   pkgXmlNode *pkg = this;
 143   pkgXmlNode *root = pkg->GetDocumentRoot();
 144   while( pkg != NULL )
 145   {
 146     /* We haven't yet tried to search beyond the document root;
 147      * try matching "key" to an attribute of the current element...
 148      */
 149     const char *retval = pkg->GetPropVal( key, NULL );
 150     if( retval != NULL )
 151       /*
 152        * ...returning its value, if such an attribute is found...
 153        */
 154       return retval;
 155
 156     /* ...otherwise,
 157      * take a further step back towards the document root.
 158      */
 159     pkg = (pkg == root) ? NULL : pkg->GetParent();
 160   }
 161
 162   /* If we get to here, then no element with the required "key"
 163    * attribute could be found; substitute the specified default.
 164    */
 165   return sub;
 166 }
 167
 168 void
 169 pkgXmlDocument::ResolveDependencies( pkgXmlNode* package, pkgActionItem* rank )
 170 # define promote( request, action )  (((request) & (~ACTION_MASK)) | action )
 171 {
 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.
 177    */
 178   pkgSpecs *refdata = NULL;
 179   pkgXmlNode *refpkg = package;
 180
 181   while( package != NULL )
 182   {
 183     /* We have a valid XML entity, which may identify dependencies;
 184      * check if it includes any "requires" specification...
 185      */
 186     pkgXmlNode *dep = package->FindFirstAssociate( requires_key );
 187     while( dep != NULL )
 188     {
 189       /* We found a dependency specification...
 190        * Initially, assume this package is not installed.
 191        */
 192       pkgXmlNode *installed = NULL;
 193
 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...
 197        */
 198       if( refdata == NULL )
 199       {
 200         /* ...but we deferred that until we knew for sure that it would
 201          * be needed; it is, so parse it now.
 202          */
 203         const char *refname;
 204         if( (refname = refpkg->GetPropVal( tarname_key, NULL )) != NULL )
 205           refdata = new pkgSpecs( refname );
 206       }
 207
 208       /* Identify the prerequisite package, from its canonical name...
 209        */
 210       pkgActionItem wanted; pkgXmlNode *selected;
 211       pkgSpecs req( wanted.SetRequirements( dep, refdata ) );
 212       /*
 213        * (Both the package name, and subsystem if specified, must match)...
 214        */
 215       selected = FindPackageByName( req.GetPackageName(), req.GetSubSystemName() );
 216
 217       /* When we've identified the appropriate package...
 218        */
 219       if( selected != NULL )
 220       {
 221         /* ...and, more significantly, the appropriate component package,
 222          * where applicable...
 223          */
 224         pkgXmlNode *component; const char *reqclass;
 225         if( (reqclass = req.GetComponentClass()) == NULL )
 226           reqclass = value_unknown;
 227
 228         if( (component = selected->FindFirstAssociate( component_key )) == NULL )
 229           /*
 230            * ...but if no separate component package exists,
 231            * consider the parent package itself, as sole component.
 232            */
 233           component = selected;
 234
 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...
 238          */
 239         selected = NULL;
 240         while( component != NULL )
 241         {
 242           /* ...by stepping through the "releases" of this component package...
 243           */
 244           pkgXmlNode *required = component->FindFirstAssociate( release_key );
 245           while( required != NULL )
 246           {
 247             /* ...noting if we find one already marked as "installed"...
 248             */
 249             const char *tstclass;
 250             pkgSpecs tst( required->GetPropVal( tarname_key, NULL ) );
 251             if( (tstclass = tst.GetComponentClass()) == NULL )
 252               tstclass = value_unknown;
 253
 254             if( is_installed( required ) && (strcmp( tstclass, reqclass ) == 0) )
 255               installed = required;
 256
 257             /* ...and identify the most suitable candidate "release"
 258              * to satisfy the current dependency...
 259              */
 260             if( wanted.SelectIfMostRecentFit( required ) == required )
 261               selected = component = required;
 262
 263             /* ...continuing, until all available "releases"
 264              * have been evaluated accordingly.
 265              */
 266             required = required->FindNextAssociate( release_key );
 267           }
 268
 269           /* Where multiple component packages do exist,
 270            * continue until all have been inspected.
 271            */
 272           component = component->FindNextAssociate( component_key );
 273         }
 274
 275         /* We have now identified the most suitable candidate package,
 276          * to resolve the current dependency...
 277          */
 278         if( installed )
 279         {
 280           /* ...this package is already installed, so we may schedule
 281            * a resolved dependency match, with no pending action...
 282            */
 283           unsigned long fallback = request & ~ACTION_MASK;
 284           if( (selected != NULL) && (selected != installed) )
 285           {
 286             /* ...but, if there is a better candidate than the installed
 287              * version, we prefer to schedule an upgrade.
 288              */
 289             fallback |= ACTION_UPGRADE;
 290             wanted.SelectPackage( installed, to_remove );
 291           }
 292           rank = Schedule( fallback, wanted, rank );
 293         }
 294
 295         else if( ((request & ACTION_MASK) == ACTION_INSTALL)
 296           /*
 297            * The required package is not installed...
 298            * When performing an installation, ...
 299            */
 300         || ((request & (ACTION_PRIMARY | ACTION_INSTALL)) == ACTION_INSTALL) )
 301           /*
 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).
 306            */
 307           rank = Schedule( promote( request, ACTION_INSTALL ), wanted, rank );
 308
 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...
 313          */
 314         if( (request & ACTION_INSTALL) != 0 )
 315           ResolveDependencies( selected, rank );
 316       }
 317
 318       if( selected == NULL )
 319       {
 320         /* No package matching the selection criteria could be found;
 321          * report a dependency resolution failure in respect of each
 322          * specified criterion...
 323          */
 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 );
 326
 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 )
 331           {
 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" );
 334           }
 335         dmh_notify( DMH_ERROR, "please report this to the package maintainer\n" );
 336         dmh_control( DMH_END_DIGEST );
 337       }
 338
 339       /* Continue, until all prerequisites of the current package
 340        * have been evaluated.
 341        */
 342       dep = dep->FindNextAssociate( requires_key );
 343     }
 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.
 349      */
 350     package = (package == GetRoot()) ? NULL : package->GetParent();
 351   }
 352   delete refdata;
 353 }
 354
 355 static inline bool assert_unmatched
 356 ( const char *ref, const char *val, const char *name, const char *alias )
 357 {
 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 ))
 361
 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.
 368    */
 369   return (ref == NULL)
 370
 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.
 373        */
 374       !( if_noref( val ) && if_noref( name ) && if_noref( alias ))
 375
 376     : /* Otherwise, when "ref" is not NULL, then a match is identified when
 377        * any one candidate is found to match.
 378        */
 379       !( if_match( ref, val ) || if_match( ref, name ) || if_alias( ref, alias ));
 380 }
 381
 382 static
 383 pkgXmlNode *assert_installed( pkgXmlNode *current, pkgXmlNode *installed )
 384 {
 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
 389    * removed).
 390    *
 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.
 395    */
 396   if( current && (installed == NULL) )
 397   {
 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.
 403      *
 404      * Starting from the sysroot record for the specified release...
 405      */
 406     pkgXmlNode *sysroot; const char *tarname;
 407     pkgSpecs lookup( current->GetPropVal( tarname_key, NULL ) );
 408     if( (sysroot = current->GetSysRoot( lookup.GetSubSystemName() )) != NULL )
 409     {
 410       /* ...identify the first, if any, package installation record.
 411        */
 412       pkgXmlNode *ref = sysroot->FindFirstAssociate( installed_key );
 413       if( ref != NULL )
 414       {
 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.
 418          */
 419         const char *refname = lookup.GetPackageName();
 420         const char *cptname = lookup.GetComponentClass();
 421         const char *version = lookup.GetComponentVersion();
 422
 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.
 427          */
 428         const char *pkgname = current->GetContainerAttribute( name_key );
 429         const char *alias = current->GetContainerAttribute( alias_key );
 430
 431         /* For each candidate installation record found...
 432          */
 433         while( ref != NULL )
 434         {
 435           /* ...check if it matches the look-up criteria.
 436            */
 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 )  )
 441             /*
 442              * This candidate isn't a match; try the next, if any...
 443              */
 444             ref = ref->FindNextAssociate( installed_key );
 445
 446           else
 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...
 451              */
 452             if( (installed = new pkgXmlNode( release_key )) != NULL )
 453             {
 454               installed->SetAttribute( tarname_key, tarname );
 455               installed->SetAttribute( installed_key, value_yes );
 456               if( (ref = current->GetParent()) != NULL )
 457                 installed = ref->AddChild( installed );
 458             }
 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.
 462              */
 463             ref = NULL;
 464           }
 465         }
 466       }
 467     }
 468   }
 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.
 472    */
 473   return installed;
 474 }
 475
 476 void pkgActionItem::ConfirmInstallationStatus()
 477 {
 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).
 482    */
 483   selection[to_remove]
 484     = assert_installed( selection[to_install], selection[to_remove] );
 485 }
 486
 487 void pkgXmlDocument::Schedule( unsigned long action, const char* name )
 488 {
 489   /* Task scheduler interface; schedules actions to process dependencies
 490    * for the package specified by "name".
 491    */
 492   pkgXmlNode *release;
 493   if( (release = FindPackageByName( name )) != NULL )
 494   {
 495     /* We found the specification for the named package...
 496      */
 497     pkgXmlNode *component = release->FindFirstAssociate( component_key );
 498     if( component != NULL )
 499       /*
 500        * When it is subdivided into component-packages,
 501        * we need to consider each as a possible candidate
 502        * for task scheduling.
 503        */
 504       release = component;
 505
 506     while( release != NULL )
 507     {
 508       /* Within each candidate package or component-package...
 509        */
 510       if( (release = release->FindFirstAssociate( release_key )) != NULL )
 511       {
 512         /* ...initially assume it is not installed, and that
 513          * no installable upgrade is available.
 514          */
 515         pkgActionItem latest;
 516         pkgXmlNode *installed = NULL, *upgrade = NULL;
 517
 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.
 522          */
 523         request = action;
 524
 525         /* Any action request processed here is, by definition,
 526          * a request for a primary action; mark it as such.
 527          */
 528         action |= ACTION_PRIMARY;
 529
 530         /* For each candidate release in turn...
 531          */
 532         while( release != NULL )
 533         {
 534           /* ...inspect it to identify any which is already installed,
 535            * and also the latest available...
 536            */
 537           if( is_installed( release ) )
 538             /*
 539              * ...i.e. here we have identified a release
 540              * which is currently installed...
 541              */
 542             latest.SelectPackage( installed = release, to_remove );
 543
 544           if( latest.SelectIfMostRecentFit( release ) == release )
 545             /*
 546              * ...while this is the most recent we have
 547              * encountered so far.
 548              */
 549             upgrade = release;
 550
 551           /* Continue with the next specified release, if any.
 552            */
 553           release = release->FindNextAssociate( release_key );
 554         }
 555
 556         if( (installed = assert_installed( upgrade, installed )) == NULL )
 557         {
 558           /* There is no installed version...
 559            * therefore, there is nothing to do for any action
 560            * other than ACTION_INSTALL...
 561            */
 562           if( (action & ACTION_MASK) == ACTION_INSTALL )
 563             /*
 564              * ...in which case, we must recursively resolve
 565              * any dependencies for the scheduled "upgrade".
 566              */
 567             ResolveDependencies( upgrade, Schedule( action, latest ));
 568
 569           else
 570             /* attempting ACTION_UPGRADE or ACTION_REMOVE
 571              * is an error; diagnose it.
 572              */
 573             dmh_notify( DMH_ERROR, "%s %s: package is not installed\n",
 574                 action_name( action & ACTION_MASK ), name
 575               );
 576         }
 577
 578         else if( upgrade && (upgrade != installed) )
 579         {
 580           /* There is an installed version...
 581            * but an upgrade to a newer version is available;
 582            * ACTION_INSTALL implies ACTION_UPGRADE.
 583            */
 584           unsigned long fallback = action;
 585           if( (action & ACTION_MASK) == ACTION_INSTALL )
 586             fallback = ACTION_UPGRADE + (action & ~ACTION_MASK);
 587
 588           /* Again, we recursively resolve any dependencies
 589            * for the scheduled upgrade.
 590            */
 591           ResolveDependencies( upgrade, Schedule( fallback, latest ));
 592         }
 593
 594         else
 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.
 599            */
 600           ResolveDependencies( upgrade, Schedule( action, latest ));
 601       }
 602
 603       if( (component = component->FindNextAssociate( component_key )) != NULL )
 604         /*
 605          * When evaluating a component-package, we extend our
 606          * evaluation, to consider for any further components of
 607          * the current package.
 608          */
 609         release = component;
 610     }
 611   }
 612
 613   else
 614     /* We found no information on the requested package;
 615      * diagnose as a non-fatal error.
 616      */
 617     dmh_notify( DMH_ERROR, pkgMsgUnknownPackage(), name );
 618 }
 619
 620 /* $RCSfile$: end of file */