tic/dependency.py

   1 #!/usr/bin/python
   2 # Copyright (c) 2016 Samsung Electronics Co., Ltd
   3 #
   4 # Licensed under the Flora License, Version 1.1 (the "License");
   5 # you may not use this file except in compliance with the License.
   6 # You may obtain a copy of the License at
   7 #
   8 #     http://floralicense.org/license/
   9 #
  10 # Unless required by applicable law or agreed to in writing, software
  11 # distributed under the License is distributed on an "AS IS" BASIS,
  12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 # See the License for the specific language governing permissions and
  14 # limitations under the License.
  15 #
  16 # Contributors:
  17 # - S-Core Co., Ltd
  18
  19 import logging
  20 from lxml import etree
  21 from tic.utils.error import TICError
  22 from tic.utils.rpmmisc import meetRequireVersion, compare_ver
  23 from tic.utils.rpmmisc import Dependency
  24 from tic.config import configmgr
  25
  26 DEFAULT_PROFILE = 'EMPTY'
  27
  28 def get_installed_packages(recipe, repoinfo, pkg_group):
  29     logger = logging.getLogger(__name__)
  30
  31     def _select_rpm_from_files(fileList, require):
  32         if not fileList or not require:
  33             return None
  34         # 1. sort
  35         fileList.sort()
  36         # 2-1. Choose the default rpm or the selected rpm
  37         for fname in fileList:
  38             file_info = pkg_dict.get(fname)
  39             if fname in required_inst_rpms or selected[file_info['id']] >= 1:
  40                 return file_info
  41         # 2-2. Choose the rpm (it does not conflitcs)
  42         for fname in fileList:
  43             file_info = pkg_dict.get(fname)
  44             if not _check_conflicts(file_info):
  45                 return file_info
  46         return pkg_dict.get(fileList[0])
  47
  48     def _select_rpm(capability, require, recommends=None):
  49         provide_list = []
  50         # 1. Choose the rpm included in version from provides
  51         if require.get('ver'):
  52             for provide in capability:
  53                 ver_data = provide['data']
  54                 # If there is no capability version, use version of package
  55                 if not ver_data.get('ver'):
  56                     ver_data = pkg_dict.get(provide['name']).get('version')
  57                 if meetRequireVersion(require, ver_data):
  58                     provide_list.append(provide)
  59         else:
  60             provide_list = capability
  61
  62         # error case (the rpm does not exist)
  63         if not provide_list:
  64             return None
  65
  66         if len(provide_list) == 1:
  67             return pkg_dict.get(provide_list[0].get('name'))
  68
  69         # 2 Select one of the rpms by priority
  70         # 2-1. Choose the default rpm or the selected rpm
  71         for pro in provide_list:
  72             provide_info = pkg_dict.get(pro['name'])
  73             if provide_info['name'] in required_inst_rpms or selected[provide_info['id']] >= 1:
  74                 return provide_info
  75
  76         # 2-2. Choose the defualt profile
  77         # TODO: should be supported
  78         # if provide_info['profile'] == DEFAULT_PROFILE:
  79             # return provide_info
  80
  81         # 2.3. Choose recommends pkg (pkg-name or capability)
  82         if recommends:
  83             for pro in provide_list:
  84                 provide_info = pkg_dict.get(pro.get('name'))
  85                 for reco in recommends:
  86                     # 2-3 Case. select a pkg that is named
  87                     if reco['name'] == provide_info['name']:
  88                         return provide_info
  89                     # 2-3 Case. select a pkg that provides
  90                     for cap in provide_info.get('provides'):
  91                         if reco['name'] == cap['name']:
  92                             return provide_info
  93         # 2-4. Select the latest version of rpm
  94         max_ver = None
  95         for pro in provide_list:
  96             if not _check_conflicts(pkg_dict.get(pro.get('name'))):
  97                 if max_ver:
  98                     cap_info = pro.get('data')
  99                     ret = compare_ver(max_ver.get('data'), cap_info)
 100                     if ret == 0: # equals
 101                         # string compare (compare string lexicographically using ASCII value)
 102                         if max_ver.get('name') > pro.get('name'):
 103                             max_ver = pro
 104                     elif ret == -1: # greater than max_ver
 105                         max_ver = pro
 106                 else:
 107                     max_ver = pro
 108
 109         # all of capability pkg are in conflict
 110         if max_ver is None:
 111             return pkg_dict.get(provide_list[0]['name'])
 112
 113         return pkg_dict.get(max_ver.get('name'))
 114
 115     def _create_reference(pkg1, pkg2):
 116         # duplicate check
 117         if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
 118             return False
 119         if pkg1.get('forward'):
 120             pkg1['forward'].append(pkg2['name'])
 121         else:
 122             pkg1['forward'] = [pkg2['name']]
 123
 124         if pkg2.get('backward'):
 125             pkg2['backward'].append(pkg1['name'])
 126         else:
 127             pkg2['backward'] = [pkg1['name']]
 128         return True
 129
 130     def _make_scc(pkg_id):
 131         scc_num[0] += 1
 132         scc_list = []
 133         # stack is not empty
 134         while rpm_stack:
 135             pkg = rpm_stack.pop()
 136             scc_id[pkg['id']] = scc_num[0]
 137             scc_list.append(pkg)
 138             if pkg_id == pkg['id']:
 139                 break
 140
 141         # circular dependency
 142         if len(scc_list) > 1:
 143             group_num[0] += 1
 144             group_names = []
 145             # add group id
 146             for pkg in scc_list:
 147                 pkg['group'] = group_num[0]
 148                 group_names.append(pkg['name'])
 149
 150             # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
 151             groups[group_num[0]] = group_names
 152
 153     def _check_conflicts(pkg_info):
 154         # 1. Check whether node can be installed
 155         if pkg_info.get('provides') is not None:
 156             for pro in pkg_info['provides']:
 157                 if pro['name'] in conflicts:
 158                     for con in conflicts[pro['name']]:
 159                         if not con['data'].get('ver') or meetRequireVersion(con['data'], pro):
 160                             #package conflict
 161                             #logger.info('Conflict Case-1) %s is conflict with %s' % (pkg_info['name'], con['name']))
 162                             return pkg_dict.get(con['name'])
 163
 164         #2. If the conflict package defined by node is installed
 165         if pkg_info.get('conflicts') is not None:
 166             for con in pkg_info['conflicts']:
 167                 if con['name'] in provides:
 168                     for pro in provides[con['name']]:
 169                         pkg = pkg_dict[pro['name']]
 170                         if selected[pkg['id']] != 0:
 171                             if not con.get('ver') or meetRequireVersion(con, pro['data']):
 172                                 #logger.info('Conflict Case-2) %s is conflict with %s' % (pkg['name'], pkg_info['name']))
 173                                 return pkg
 174                 elif con['name'] in pkg_dict:
 175                     pkg = pkg_dict[con['name']]
 176                     if selected[pkg['id']] != 0:
 177                         if not con.get('ver') or meetRequireVersion(con, pkg['version']):
 178                             #logger.info('Conflict Case-2) %s is conflict with %s' % (pkg['name'], pkg_info['name']))
 179                             return pkg
 180         return None
 181
 182     def _remove_conflicts(pkg_info):
 183         if pkg_info.get('conflicts'):
 184             for con in pkg_info['conflicts']:
 185                 if con['name'] in conflicts:
 186                     c_list = conflicts[con['name']]
 187                     for i in range(len(c_list)):
 188                         if c_list[i]['name'] == pkg_info['name']:
 189                             del c_list[i]
 190                             break
 191
 192     def _add_conflicts(pkg_info):
 193         if pkg_info.get('conflicts'):
 194             for con in pkg_info['conflicts']:
 195                 if not con['name'] in conflicts:
 196                     conflicts[con['name']] = []
 197                 conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
 198                 #logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
 199
 200     def _analyze_dep(pkg_info):
 201         if not pkg_info:
 202             return
 203
 204         pkg_id = pkg_info['id']
 205         number[0] += 1
 206         selected[pkg_id] = number[0]
 207         min_num[pkg_id] = number[0]
 208         rpm_stack.append(pkg_info)
 209
 210         dep_rpms = set([pkg_info['name']])
 211
 212         # check for conflicts
 213         if _check_conflicts(pkg_info):
 214             progress['status'] = False
 215             rpm_stack.pop()
 216             return
 217
 218         # add rpms into conflicts table.
 219         _add_conflicts(pkg_info)
 220
 221         # Installation dependency analysis of rpm
 222         for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
 223             if pkg_info.get(dep_tag):
 224                 for req in pkg_info.get(dep_tag):
 225                     choose = None
 226                     # self-reference (e.g. vim-base)
 227                     if req['name'] == pkg_info['name']:
 228                         continue
 229                     #  Find dependency rpm based on capability/files
 230                     if req['name'] in provides:
 231                         # Select the rpm that meets the condition (version)
 232                         if dep_tag == Dependency.REQUIRES:
 233                             choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
 234                         else:
 235                             choose = _select_rpm(provides[req['name']], req)
 236                     elif req['name'] in files:
 237                         choose = _select_rpm_from_files(files[req['name']], req)
 238                     elif req['name'] in pkg_dict:
 239                         choose = pkg_dict.get(req['name'])
 240
 241                     if dep_tag == Dependency.RECOMMENDS:
 242                         # A Recommends B: B is installed when A is installed and B has no conflicts.
 243                         if not choose or _check_conflicts(choose) is not None:
 244                             #logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
 245                             continue
 246
 247                     if choose:
 248                         # add forward/backward reference
 249                         _create_reference(pkg_info, choose)
 250
 251                         if selected[choose['id']] == 0:
 252                             dep_set = _analyze_dep(choose)
 253                             if not progress['status']:
 254                                 break
 255                             dep_rpms.update(dep_set)
 256                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 257                         elif scc_id[choose['id']] == 0:
 258                             # cross edge that can not be ignored
 259                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 260                     else:
 261                         # the rpm does not exists
 262                         logger.info(configmgr.message['dependency_not_exist'] % (req['name'], pkg_info['name']))
 263                         progress['status'] = False
 264                         break
 265             if not progress['status']:
 266                 break
 267         if min_num[pkg_id] == selected[pkg_id]:
 268             # scc(strong connected components)
 269             _make_scc(pkg_id)
 270
 271         return dep_rpms
 272
 273     def _check_circular_dep(node):
 274         g_id = node.get('group')
 275         g_pkg_list = groups[g_id]
 276         g_dict = {}
 277
 278         # Set dict for group
 279         for pkgname in g_pkg_list:
 280             g_dict[pkgname] = None
 281
 282         for pkgname in g_pkg_list:
 283             pkg = pkg_dict[pkgname]
 284             # the node is selfchecked (the root node ignores selfchecked)
 285             #if stack[0]['id'] != pkg['id'] and pkg['selfChecked']:
 286             if selected_pkg['id'] != pkg['id'] and pkg['selfChecked']:
 287                 return False
 288             # check backward ref.
 289             for bname in pkg.get('backward'):
 290                 # If node is Referenced by another node (Not a node in the group),
 291                 # unable to uncheck group nodes
 292                 if not bname in g_dict:
 293                     return False
 294
 295         # init visited dict
 296         group_visited[g_id] = {}
 297         # delete backward reference of group node
 298         for pkgname in g_pkg_list:
 299             pkg = pkg_dict[pkgname]
 300             pkg['backward'] = None;
 301             group_visited[g_id][pkg['name']] = -1
 302         return True
 303
 304     def _delete_conflictdata(node):
 305         if node.get('conflicts'):
 306             for con in node.get('conflicts'):
 307                 if con['name'] in conflicts:
 308                     con_list = conflicts[con['name']]
 309                     for i in range(len(con_list)):
 310                         if con_list[i]['name'] == node['name']:
 311                             del con_list[i]
 312                             break;
 313
 314     def _remove_reference(parent, node):
 315         if parent is not None:
 316             # remove backward reference (parent)
 317             if node.get('backward'):
 318                 for i in range(len(node['backward'])):
 319                     if node['backward'][i] == parent['name']:
 320                         del node['backward'][i]
 321                         break
 322             # selfCheck node do not remove
 323             if node.get('selfChecked'):
 324                 return
 325
 326         if node.get('backward'):
 327             if node.get('group') is None or not _check_circular_dep(node):
 328                 return
 329
 330         # the selected node is uncheckable
 331         if node.get('group') and group_visited[node['group']]:
 332             group_visited[node['group']][node['name']] = 1
 333
 334         # if selected node has forward references
 335         if node.get('forward'):
 336             for fname in node.get('forward'):
 337                 fnode = pkg_dict.get(fname)
 338
 339                 # If pkg has a circular dependency and is unchekcable,
 340                 # circular dep. pkgs can only be visited once
 341                 gvisite = group_visited.get(fnode.get('group'))
 342                 if gvisite and gvisite[fnode['name']] == 1:
 343                     continue
 344                 _remove_reference(node, fnode)
 345             node['forward'] = None
 346             node['group'] = None
 347         # delete conflict data from conflicts dict
 348         _delete_conflictdata(node)
 349
 350     def _add_refer(node, require):
 351         if node['name'] not in require_refer:
 352             require_refer[node['name']] = {}
 353         require_refer[node['name']][require['name']] = 1
 354
 355     def _get_pkg_info(pkg_name):
 356         if pkg_name in pkg_dict:
 357             return pkg_dict[pkg_name]
 358         if pkg_name in provides:
 359             pro = provides[pkg_name][0]
 360             return pkg_dict[pro['name']]
 361         return None
 362
 363     def is_compatible_pkg (origin_pkg, new_pkg):
 364         if origin_pkg['name'] in require_refer:
 365             for r_name in require_refer[origin_pkg['name']]:
 366                 matched = False
 367                 if new_pkg.get('provides'):
 368                     for pro in new_pkg['provides']:
 369                         if r_name == pro['name']:
 370                             matched = True
 371                             break;
 372                 if not matched and new_pkg.get('file'):
 373                     for fname in new_pkg['file']:
 374                         if r_name == fname:
 375                             matched = True
 376                             break;
 377                 if not matched:
 378                     return False
 379         return True
 380
 381     def _is_selfchecked(pkg_info):
 382         if pkg_info.get('selfChecked'):
 383             return True
 384         return False
 385
 386     def _add_cap_info(pkg_info):
 387         if not pkg_info.get('provides'):
 388             return
 389         for pro in pkg_info['provides']:
 390             if not capabilities.get(pro['name']):
 391                 capabilities[pro['name']] = []
 392             capabilities[pro['name']].append(pkg_info)
 393
 394     def _remove_dep_rpm(select_list):
 395         if not select_list:
 396             return
 397         for rpm_info in select_list:
 398             selected[rpm_info['id']] = 0
 399             _delete_conflictdata(rpm_info)
 400
 401     def _check_dep_validation(pkg_info, select_list):
 402         if not pkg_info:
 403             return False
 404         pkg_id = pkg_info['id']
 405         number[0] += 1
 406         selected[pkg_id] = number[0]
 407         select_list.append(pkg_info)
 408
 409         # add rpm's capabilities
 410         _add_cap_info(pkg_info)
 411
 412         # check for conflicts
 413         conflict_pkg = _check_conflicts(pkg_info)
 414         if conflict_pkg is not None:
 415             if not _is_selfchecked(conflict_pkg) and is_compatible_pkg(conflict_pkg, pkg_info):
 416                 logger.info(pkg_info['name'] + ' and ' + conflict_pkg['name'] + ' is compatible')
 417                 comp_rpms.add(pkg_info['name'])
 418                 #_remove_conflicts(conflict_pkg)
 419             else:
 420                 logger.info('###_1 ' + pkg_info['name'] + ' is conflict with ' + conflict_pkg['name'])
 421                 return False
 422         elif pkg_info.get('provides'):
 423             for pro in pkg_info['provides']:
 424                 if pro['name'] in capabilities:
 425                     for c_info in capabilities[pro['name']]:
 426                         if c_info['id'] == pkg_info['id']:
 427                             continue
 428                         if not _is_selfchecked(c_info) and is_compatible_pkg(c_info, pkg_info):
 429                             logger.info('###_2 ' + pkg_info['name'] + ' and ' + c_info['name'] + ' is compatible')
 430                             comp_rpms.add(pkg_info['name'])
 431
 432         # add rpms into conflicts table.
 433         _add_conflicts(pkg_info)
 434         # Installation dependency analysis of rpm
 435         for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
 436             if pkg_info.get(dep_tag):
 437                 for req in pkg_info.get(dep_tag):
 438                     choose = None
 439                     # self-reference (e.g. vim-base)
 440                     if req['name'] == pkg_info['name']:
 441                         continue
 442                     if req['name'] in provides:
 443                         if dep_tag == Dependency.REQUIRES:
 444                             choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
 445                         else:
 446                             choose = _select_rpm(provides[req['name']], req)
 447                     elif req['name'] in files:
 448                         choose = _select_rpm_from_files(files[req['name']], req)
 449                     elif req['name'] in pkg_dict:
 450                         choose = pkg_dict.get(req['name'])
 451
 452                     if dep_tag == Dependency.RECOMMENDS:
 453                         # A Recommends B: B is installed when A is installed and B has no conflicts.
 454                         if not choose or _check_conflicts(choose) is not None:
 455                             #logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
 456                             continue
 457
 458                     if choose:
 459                         # add refer count, only requires
 460                         if dep_tag == Dependency.REQUIRES:
 461                             _add_refer(choose, req)
 462
 463                         if selected[choose['id']] == 0:
 464                             if not _check_dep_validation(choose, select_list):
 465                                 return False
 466                     else:
 467                         # the rpm does not exists
 468                         return False
 469         return True
 470
 471     # recipe/repo
 472     if not recipe or not repoinfo:
 473         return []
 474
 475     group_set = set([])
 476     pkg_set = set([])
 477
 478     if recipe['Recipe'].get('Groups'):
 479         group_set.update(recipe['Recipe'].get('Groups'))
 480     if recipe['Recipe'].get('ExtraPackages'):
 481         pkg_set.update(recipe['Recipe'].get('ExtraPackages'))
 482
 483     # parsing group.xml
 484     if group_set:
 485         for repo in repoinfo:
 486             if repo.get('comps'):
 487                 try:
 488                     tree = etree.parse(repo.get('comps'))
 489                     root = tree.getroot()
 490                 except etree.XMLSyntaxError as e:
 491                     logger.info(e)
 492                     raise TICError(configmgr.message['xml_parse_error'] % ('group.xml', repo['baseurl']))
 493                 # Convert groups to packages
 494                 for elm in root.findall('group'):
 495                     group_name = elm.find('name').text
 496                     if group_name in group_set:
 497                         pkglist = elm.find('packagelist')
 498                         plist = []
 499                         for pkgreq in pkglist.findall('packagereq'):
 500                             plist.append(pkgreq.text)
 501                         pkg_set.update(set(plist))
 502                         group_set.discard(group_name);
 503
 504     pkg_dict = pkg_group.get('pkg_dict')
 505     provides = pkg_group.get('provides')
 506     files = pkg_group.get('files')
 507     groups = pkg_group.get('groups')
 508     conflicts = pkg_group.get('conflicts')
 509
 510     number = [0]    # for pkg count
 511     scc_num = [0]   # for scc count
 512     group_num = [0]     # for group count
 513     scc_id = [0] * len(pkg_dict)
 514     min_num = [0] * len(pkg_dict)
 515     selected = [0] * len(pkg_dict)
 516     group_visited = None
 517     install_rpm = set([])
 518     progress = dict(status=True, message=None)
 519
 520     capabilities = {}
 521     require_refer = {}
 522     candidate_rpms = set([])
 523     # add rpms to install
 524     select_rpms = set([])
 525     # add reference value for rpm selection
 526     required_inst_rpms = pkg_set.copy()
 527
 528     # 1. Check whether dependencies of rpm are available.
 529     for pkg_name in pkg_set:
 530         selected_pkg = _get_pkg_info(pkg_name)
 531         if selected_pkg:
 532             if selected[selected_pkg['id']] == 0:
 533                 select_list = []
 534                 comp_rpms = set([])
 535                 if _check_dep_validation(selected_pkg, select_list):
 536                     select_rpms.add(pkg_name)
 537                     candidate_rpms.update(comp_rpms)
 538                 else:
 539                     # case: conflict or rpm does not exist
 540                     _remove_dep_rpm(select_list)
 541                     logger.info('The %s install-dependencies are not valid, could not selected it' % pkg_name)
 542             else:
 543                 select_rpms.add(pkg_name)
 544         else:
 545             logger.info(configmgr.message['package_not_exist'] % pkg_name)
 546
 547     # init conflict table and reference
 548     number[0] = 0
 549     selected = [0] * len(pkg_dict)
 550     conflicts.clear()
 551     required_inst_rpms.clear()
 552     required_inst_rpms.update(select_rpms)
 553     required_inst_rpms.update(candidate_rpms)
 554
 555     print(candidate_rpms)
 556
 557     # 2. Analyze rpm installation dependencies.
 558     for pkg_name in select_rpms:
 559         progress['status'] = True
 560         selected_pkg = _get_pkg_info(pkg_name)
 561         if selected_pkg:
 562             rpm_stack = []
 563             selected_pkg['selfChecked'] = True
 564             if selected[selected_pkg['id']] == 0:
 565                 inst_rpms = _analyze_dep(selected_pkg)
 566                 if progress['status']:
 567                     install_rpm.update(inst_rpms)
 568                 else:
 569                     # Error Case
 570                     logger.info("[Dependency Issue] Could not install the %s" % selected_pkg)
 571                     # delete forward/backward reference
 572                     group_visited = {}
 573                     _remove_reference(None, selected_pkg)
 574         else:
 575             logger.info(configmgr.message['package_not_exist'] % pkg_name)
 576     return list(install_rpm)