zypp/solver/detail/Resolver.cc

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
   2 /* Resolver.cc
   3  *
   4  * Copyright (C) 2000-2002 Ximian, Inc.
   5  * Copyright (C) 2005 SUSE Linux Products GmbH
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License,
   9  * version 2, as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  */
  21 #include <boost/static_assert.hpp>
  22
  23 #include "zypp/solver/detail/Resolver.h"
  24 #include "zypp/solver/detail/Helper.h"
  25 #include "zypp/solver/detail/Testcase.h"
  26 #include "zypp/solver/detail/SATResolver.h"
  27
  28 #include "zypp/Capabilities.h"
  29 #include "zypp/ZConfig.h"
  30 #include "zypp/base/Logger.h"
  31 #include "zypp/base/String.h"
  32 #include "zypp/base/Gettext.h"
  33 #include "zypp/base/Algorithm.h"
  34 #include "zypp/ResPool.h"
  35 #include "zypp/ResFilters.h"
  36 #include "zypp/sat/Pool.h"
  37 #include "zypp/sat/Solvable.h"
  38 #include "zypp/sat/Transaction.h"
  39 #include "zypp/ResolverProblem.h"
  40
  41 #define MAXSOLVERRUNS 5
  42
  43 /////////////////////////////////////////////////////////////////////////
  44 namespace zypp
  45 { ///////////////////////////////////////////////////////////////////////
  46   ///////////////////////////////////////////////////////////////////////
  47   namespace solver
  48   { /////////////////////////////////////////////////////////////////////
  49     /////////////////////////////////////////////////////////////////////
  50     namespace detail
  51     { ///////////////////////////////////////////////////////////////////
  52
  53 using namespace std;
  54
  55 IMPL_PTR_TYPE(Resolver);
  56
  57
  58 //---------------------------------------------------------------------------
  59
  60
  61 std::ostream & Resolver::dumpOn( std::ostream & os ) const
  62 {
  63   os << "<resolver>" << endl;
  64   #define OUTS(t) os << "  " << #t << ":\t" << t << endl;
  65   OUTS( _forceResolve );
  66   OUTS( _upgradeMode );
  67   OUTS( _updateMode );
  68   OUTS( _verifying );
  69   OUTS( _onlyRequires );
  70   OUTS( _allowVendorChange );
  71   OUTS( _solveSrcPackages );
  72   OUTS( _cleandepsOnRemove );
  73   OUTS( _ignoreAlreadyRecommended );
  74   #undef OUT
  75   return os << "<resolver/>";
  76 }
  77
  78
  79 //---------------------------------------------------------------------------
  80
  81 Resolver::Resolver (const ResPool & pool)
  82     : _pool(pool)
  83     , _satResolver(NULL)
  84     , _poolchanged(_pool.serial() )
  85     , _forceResolve             (false)
  86     , _upgradeMode              (false)
  87     , _updateMode               (false)
  88     , _verifying                (false)
  89     , _onlyRequires             ( ZConfig::instance().solver_onlyRequires() )
  90     , _allowVendorChange        ( ZConfig::instance().solver_allowVendorChange() )
  91     , _solveSrcPackages         ( false )
  92     , _cleandepsOnRemove        ( ZConfig::instance().solver_cleandepsOnRemove() )
  93     , _ignoreAlreadyRecommended ( true )
  94
  95 {
  96     sat::Pool satPool( sat::Pool::instance() );
  97     _satResolver = new SATResolver(_pool, satPool.get());
  98 }
  99
 100
 101 Resolver::~Resolver()
 102 {
 103   delete _satResolver;
 104 }
 105
 106 //---------------------------------------------------------------------------
 107
 108 void Resolver::setAllowVendorChange( TriBool state_r )
 109 {
 110   _allowVendorChange = indeterminate(state_r) ? ZConfig::instance().solver_allowVendorChange() : bool(state_r);
 111 }
 112
 113 void Resolver::setOnlyRequires( TriBool state_r )
 114 {
 115   _onlyRequires = indeterminate(state_r) ? ZConfig::instance().solver_onlyRequires() : bool(state_r);
 116 }
 117
 118 void Resolver::setCleandepsOnRemove( TriBool state_r )
 119 {
 120   _cleandepsOnRemove = indeterminate(state_r) ? ZConfig::instance().solver_cleandepsOnRemove() : bool(state_r);
 121 }
 122
 123 //---------------------------------------------------------------------------
 124
 125 ResPool Resolver::pool() const
 126 { return _pool; }
 127
 128 void Resolver::reset( bool keepExtras )
 129 {
 130     _verifying = false;
 131
 132     if (!keepExtras) {
 133       _extra_requires.clear();
 134       _extra_conflicts.clear();
 135     }
 136
 137     _isInstalledBy.clear();
 138     _installs.clear();
 139     _satifiedByInstalled.clear();
 140     _installedSatisfied.clear();
 141 }
 142
 143 bool Resolver::doUpgrade()
 144 {
 145   // Setting Resolver to upgrade mode. SAT solver will do the update
 146   _upgradeMode = true;
 147   return resolvePool();
 148 }
 149
 150 void Resolver::doUpdate()
 151 {
 152     _updateMode = true;
 153     return _satResolver->doUpdate();
 154 }
 155
 156 PoolItemList Resolver::problematicUpdateItems() const
 157 { return _satResolver->problematicUpdateItems(); }
 158
 159 void Resolver::addExtraRequire( const Capability & capability )
 160 { _extra_requires.insert (capability); }
 161
 162 void Resolver::removeExtraRequire( const Capability & capability )
 163 { _extra_requires.erase (capability); }
 164
 165 void Resolver::addExtraConflict( const Capability & capability )
 166 { _extra_conflicts.insert (capability); }
 167
 168 void Resolver::removeExtraConflict( const Capability & capability )
 169 { _extra_conflicts.erase (capability); }
 170
 171 void Resolver::removeQueueItem( SolverQueueItem_Ptr item )
 172 {
 173     bool found = false;
 174     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
 175          iter != _added_queue_items.end(); iter++) {
 176         if (*iter == item) {
 177             _added_queue_items.remove(*iter);
 178             found = true;
 179             break;
 180         }
 181     }
 182     if (!found) {
 183         _removed_queue_items.push_back (item);
 184         _removed_queue_items.unique ();
 185     }
 186 }
 187
 188 void Resolver::addQueueItem( SolverQueueItem_Ptr item )
 189 {
 190     bool found = false;
 191     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
 192          iter != _removed_queue_items.end(); iter++) {
 193         if (*iter == item) {
 194             _removed_queue_items.remove(*iter);
 195             found = true;
 196             break;
 197         }
 198     }
 199     if (!found) {
 200         _added_queue_items.push_back (item);
 201         _added_queue_items.unique ();
 202     }
 203 }
 204
 205 void Resolver::addWeak( const PoolItem & item )
 206 { _addWeak.push_back( item ); }
 207
 208 //---------------------------------------------------------------------------
 209
 210 struct UndoTransact : public resfilter::PoolItemFilterFunctor
 211 {
 212     ResStatus::TransactByValue resStatus;
 213     UndoTransact ( const ResStatus::TransactByValue &status)
 214         :resStatus(status)
 215     { }
 216
 217     bool operator()( PoolItem item )            // only transacts() items go here
 218     {
 219         item.status().resetTransact( resStatus );// clear any solver/establish transactions
 220         return true;
 221     }
 222 };
 223
 224
 225 struct DoTransact : public resfilter::PoolItemFilterFunctor
 226 {
 227     ResStatus::TransactByValue resStatus;
 228     DoTransact ( const ResStatus::TransactByValue &status)
 229         :resStatus(status)
 230     { }
 231
 232     bool operator()( PoolItem item )            // only transacts() items go here
 233     {
 234         item.status().setTransact( true, resStatus );
 235         return true;
 236     }
 237 };
 238
 239
 240 bool Resolver::verifySystem()
 241 {
 242     UndoTransact resetting (ResStatus::APPL_HIGH);
 243
 244     _DEBUG ("Resolver::verifySystem() ");
 245
 246     _verifying = true;
 247
 248     invokeOnEach ( _pool.begin(), _pool.end(),
 249                    resfilter::ByTransact( ),                    // Resetting all transcations
 250                    functor::functorRef<bool,PoolItem>(resetting) );
 251
 252     return resolvePool();
 253 }
 254
 255
 256 //----------------------------------------------------------------------------
 257 // undo
 258
 259 void Resolver::undo()
 260 {
 261     UndoTransact info(ResStatus::APPL_LOW);
 262     MIL << "*** undo ***" << endl;
 263     invokeOnEach ( _pool.begin(), _pool.end(),
 264                    resfilter::ByTransact( ),                    // collect transacts from Pool to resolver queue
 265                    functor::functorRef<bool,PoolItem>(info) );
 266     //  Regard dependencies of the item weak onl
 267     _addWeak.clear();
 268
 269     // Additional QueueItems which has to be regarded by the solver
 270     _removed_queue_items.clear();
 271     _added_queue_items.clear();
 272
 273     return;
 274 }
 275
 276 void Resolver::solverInit()
 277 {
 278     // Solving with libsolv
 279     static bool poolDumped = false;
 280     MIL << "-------------- Calling SAT Solver -------------------" << endl;
 281     if ( getenv("ZYPP_FULLLOG") ) {
 282         Testcase testcase("/var/log/YaST2/autoTestcase");
 283         if (!poolDumped) {
 284             testcase.createTestcase (*this, true, false); // dump pool
 285             poolDumped = true;
 286         } else {
 287             testcase.createTestcase (*this, false, false); // write control file only
 288         }
 289     }
 290
 291     _satResolver->setFixsystem                  ( isVerifyingMode() );
 292     _satResolver->setIgnorealreadyrecommended   ( ignoreAlreadyRecommended() );
 293     _satResolver->setOnlyRequires               ( onlyRequires() );
 294     _satResolver->setAllowdowngrade             (false);
 295     _satResolver->setAllowarchchange            (false);
 296     _satResolver->setAllowvendorchange          ( allowVendorChange() );
 297     _satResolver->setAllowuninstall             ( forceResolve() );
 298     _satResolver->setUpdatesystem               (false);
 299     _satResolver->setNoupdateprovide            (false);
 300     _satResolver->setDosplitprovides            (true);
 301     _satResolver->setSolveSrcPackages           ( solveSrcPackages() );
 302     _satResolver->setCleandepsOnRemove          ( cleandepsOnRemove() );
 303
 304     _satResolver->setDistupgrade                (_upgradeMode);
 305     if (_upgradeMode) {
 306       // may overwrite some settings
 307       _satResolver->setDistupgrade_removeunsupported    (false);
 308     }
 309
 310     // Resetting additional solver information
 311     _isInstalledBy.clear();
 312     _installs.clear();
 313     _satifiedByInstalled.clear();
 314     _installedSatisfied.clear();
 315 }
 316
 317 bool Resolver::resolvePool()
 318 {
 319     solverInit();
 320     return _satResolver->resolvePool(_extra_requires, _extra_conflicts, _addWeak, _upgradeRepos );
 321 }
 322
 323 bool Resolver::resolveQueue( solver::detail::SolverQueueItemList & queue )
 324 {
 325     solverInit();
 326
 327     // add/remove additional SolverQueueItems
 328     for (SolverQueueItemList::const_iterator iter = _removed_queue_items.begin();
 329          iter != _removed_queue_items.end(); iter++) {
 330         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
 331             if ( (*iterQueue)->cmp(*iter) == 0) {
 332                 MIL << "remove from queue" << *iter;
 333                 queue.remove(*iterQueue);
 334                 break;
 335             }
 336         }
 337     }
 338
 339     for (SolverQueueItemList::const_iterator iter = _added_queue_items.begin();
 340          iter != _added_queue_items.end(); iter++) {
 341         bool found = false;
 342         for (SolverQueueItemList::const_iterator iterQueue = queue.begin(); iterQueue != queue.end(); iterQueue++) {
 343             if ( (*iterQueue)->cmp(*iter) == 0) {
 344                 found = true;
 345                 break;
 346             }
 347         }
 348         if (!found) {
 349             MIL << "add to queue" << *iter;
 350             queue.push_back(*iter);
 351         }
 352     }
 353
 354     // The application has to take care to write these solutions back to e.g. selectables in order
 355     // give the user a chance for changing these decisions again.
 356     _removed_queue_items.clear();
 357     _added_queue_items.clear();
 358
 359     return _satResolver->resolveQueue(queue, _addWeak);
 360 }
 361
 362 sat::Transaction Resolver::getTransaction()
 363 {
 364   // FIXME: That's an ugly way of pushing autoInstalled into the transaction.
 365   sat::Transaction ret( sat::Transaction::loadFromPool );
 366   ret.autoInstalled( _satResolver->autoInstalled() );
 367   return ret;
 368 }
 369
 370
 371 //----------------------------------------------------------------------------
 372 // Getting more information about the solve results
 373
 374 ResolverProblemList Resolver::problems() const
 375 {
 376   MIL << "Resolver::problems()" << endl;
 377   return _satResolver->problems();
 378 }
 379
 380 void Resolver::applySolutions( const ProblemSolutionList & solutions )
 381 {
 382   for_( iter, solutions.begin(), solutions.end() )
 383   {
 384     ProblemSolution_Ptr solution = *iter;
 385     if ( !solution->apply( *this ) )
 386       break;
 387   }
 388 }
 389
 390 void Resolver::collectResolverInfo()
 391 {
 392     if ( _satResolver
 393          && _isInstalledBy.empty()
 394          && _installs.empty()) {
 395
 396         // generating new
 397         PoolItemList itemsToInstall = _satResolver->resultItemsToInstall();
 398
 399         for (PoolItemList::const_iterator instIter = itemsToInstall.begin();
 400              instIter != itemsToInstall.end(); instIter++) {
 401             // Requires
 402             for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::REQUIRES).begin(); capIt != (*instIter)->dep (Dep::REQUIRES).end(); ++capIt)
 403             {
 404                 sat::WhatProvides possibleProviders(*capIt);
 405                 for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 406                     PoolItem provider = ResPool::instance().find( *iter );
 407
 408                     // searching if this provider will already be installed
 409                     bool found = false;
 410                     bool alreadySetForInstallation = false;
 411                     ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
 412                     while (pos != _isInstalledBy.end()
 413                            && pos->first == provider
 414                            && !found) {
 415                         alreadySetForInstallation = true;
 416                         ItemCapKind capKind = pos->second;
 417                         if (capKind.item == *instIter)  found = true;
 418                         pos++;
 419                     }
 420
 421                     if (!found
 422                         && provider.status().isToBeInstalled()) {
 423                         if (provider.status().isBySolver()) {
 424                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
 425                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 426                         } else {
 427                             // no initial installation cause it has been set be e.g. user
 428                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::REQUIRES, false );
 429                             _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 430                         }
 431                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, !alreadySetForInstallation );
 432                         _installs.insert (make_pair( *instIter, capKindisInstalledBy));
 433                     }
 434
 435                     if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
 436                         ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::REQUIRES, false );
 437                         _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
 438
 439                         ItemCapKind installedSatisfied( *instIter, *capIt, Dep::REQUIRES, false );
 440                         _installedSatisfied.insert (make_pair( provider, installedSatisfied));
 441                     }
 442                 }
 443             }
 444
 445             if (!(_satResolver->onlyRequires())) {
 446                 //Recommends
 447                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::RECOMMENDS).begin(); capIt != (*instIter)->dep (Dep::RECOMMENDS).end(); ++capIt)
 448                 {
 449                     sat::WhatProvides possibleProviders(*capIt);
 450                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 451                         PoolItem provider = ResPool::instance().find( *iter );
 452
 453                         // searching if this provider will already be installed
 454                         bool found = false;
 455                         bool alreadySetForInstallation = false;
 456                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(provider);
 457                         while (pos != _isInstalledBy.end()
 458                                && pos->first == provider
 459                                && !found) {
 460                             alreadySetForInstallation = true;
 461                             ItemCapKind capKind = pos->second;
 462                             if (capKind.item == *instIter)  found = true;
 463                             pos++;
 464                         }
 465
 466                         if (!found
 467                             && provider.status().isToBeInstalled()) {
 468                             if (provider.status().isBySolver()) {
 469                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
 470                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 471                             } else {
 472                                 // no initial installation cause it has been set be e.g. user
 473                                 ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::RECOMMENDS, false );
 474                                 _isInstalledBy.insert (make_pair( provider, capKindisInstalledBy));
 475                             }
 476                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, !alreadySetForInstallation );
 477                             _installs.insert (make_pair( *instIter, capKindisInstalledBy));
 478                         }
 479
 480                         if (provider.status().staysInstalled()) { // Is already satisfied by an item which is installed
 481                             ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::RECOMMENDS, false );
 482                             _satifiedByInstalled.insert (make_pair( *instIter, capKindisInstalledBy));
 483
 484                             ItemCapKind installedSatisfied( *instIter, *capIt, Dep::RECOMMENDS, false );
 485                             _installedSatisfied.insert (make_pair( provider, installedSatisfied));
 486                         }
 487                     }
 488                 }
 489
 490                 //Supplements
 491                 for (Capabilities::const_iterator capIt = (*instIter)->dep (Dep::SUPPLEMENTS).begin(); capIt != (*instIter)->dep (Dep::SUPPLEMENTS).end(); ++capIt)
 492                 {
 493                     sat::WhatProvides possibleProviders(*capIt);
 494                     for_( iter, possibleProviders.begin(), possibleProviders.end() ) {
 495                         PoolItem provider = ResPool::instance().find( *iter );
 496                         // searching if this item will already be installed
 497                         bool found = false;
 498                         bool alreadySetForInstallation = false;
 499                         ItemCapKindMap::const_iterator pos = _isInstalledBy.find(*instIter);
 500                         while (pos != _isInstalledBy.end()
 501                                && pos->first == *instIter
 502                                && !found) {
 503                             alreadySetForInstallation = true;
 504                             ItemCapKind capKind = pos->second;
 505                             if (capKind.item == provider)  found = true;
 506                             pos++;
 507                         }
 508
 509                         if (!found
 510                             && instIter->status().isToBeInstalled()) {
 511                             if (instIter->status().isBySolver()) {
 512                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 513                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
 514                             } else {
 515                                 // no initial installation cause it has been set be e.g. user
 516                                 ItemCapKind capKindisInstalledBy( provider, *capIt, Dep::SUPPLEMENTS, false );
 517                                 _isInstalledBy.insert (make_pair( *instIter, capKindisInstalledBy));
 518                             }
 519                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 520                             _installs.insert (make_pair( provider, capKindisInstalledBy));
 521                         }
 522
 523                         if (instIter->status().staysInstalled()) { // Is already satisfied by an item which is installed
 524                             ItemCapKind capKindisInstalledBy( *instIter, *capIt, Dep::SUPPLEMENTS, !alreadySetForInstallation );
 525                             _satifiedByInstalled.insert (make_pair( provider, capKindisInstalledBy));
 526
 527                             ItemCapKind installedSatisfied( provider, *capIt, Dep::SUPPLEMENTS, false );
 528                             _installedSatisfied.insert (make_pair( *instIter, installedSatisfied));
 529                         }
 530                     }
 531                 }
 532             }
 533         }
 534     }
 535 }
 536
 537
 538 ItemCapKindList Resolver::isInstalledBy( const PoolItem & item )
 539 {
 540     ItemCapKindList ret;
 541     collectResolverInfo();
 542
 543     for (ItemCapKindMap::const_iterator iter = _isInstalledBy.find(item); iter != _isInstalledBy.end();) {
 544         ItemCapKind info = iter->second;
 545         PoolItem iterItem = iter->first;
 546         if (iterItem == item) {
 547             ret.push_back(info);
 548             iter++;
 549         } else {
 550             // exit
 551             iter = _isInstalledBy.end();
 552         }
 553     }
 554     return ret;
 555 }
 556
 557 ItemCapKindList Resolver::installs( const PoolItem & item )
 558 {
 559     ItemCapKindList ret;
 560     collectResolverInfo();
 561
 562     for (ItemCapKindMap::const_iterator iter = _installs.find(item); iter != _installs.end();) {
 563         ItemCapKind info = iter->second;
 564         PoolItem iterItem = iter->first;
 565         if (iterItem == item) {
 566             ret.push_back(info);
 567             iter++;
 568         } else {
 569             // exit
 570             iter = _installs.end();
 571         }
 572     }
 573     return ret;
 574 }
 575
 576 ItemCapKindList Resolver::satifiedByInstalled( const PoolItem & item )
 577 {
 578     ItemCapKindList ret;
 579     collectResolverInfo();
 580
 581     for (ItemCapKindMap::const_iterator iter = _satifiedByInstalled.find(item); iter != _satifiedByInstalled.end();) {
 582         ItemCapKind info = iter->second;
 583         PoolItem iterItem = iter->first;
 584         if (iterItem == item) {
 585             ret.push_back(info);
 586             iter++;
 587         } else {
 588             // exit
 589             iter = _satifiedByInstalled.end();
 590         }
 591     }
 592     return ret;
 593 }
 594
 595 ItemCapKindList Resolver::installedSatisfied( const PoolItem & item )
 596 {
 597     ItemCapKindList ret;
 598     collectResolverInfo();
 599
 600     for (ItemCapKindMap::const_iterator iter = _installedSatisfied.find(item); iter != _installedSatisfied.end();) {
 601         ItemCapKind info = iter->second;
 602         PoolItem iterItem = iter->first;
 603         if (iterItem == item) {
 604             ret.push_back(info);
 605             iter++;
 606         } else {
 607             // exit
 608             iter = _installedSatisfied.end();
 609         }
 610     }
 611     return ret;
 612 }
 613
 614
 615 ///////////////////////////////////////////////////////////////////
 616     };// namespace detail
 617     /////////////////////////////////////////////////////////////////////
 618     /////////////////////////////////////////////////////////////////////
 619   };// namespace solver
 620   ///////////////////////////////////////////////////////////////////////
 621   ///////////////////////////////////////////////////////////////////////
 622 };// namespace zypp
 623 /////////////////////////////////////////////////////////////////////////
 624