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 pkg_set 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.get('name'))
  73             if provide_info['name'] in pkg_set 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
 119
 120         if pkg1.get('forward'):
 121             pkg1['forward'].append(pkg2['name'])
 122         else:
 123             pkg1['forward'] = [pkg2['name']]
 124
 125         if pkg2.get('backward'):
 126             pkg2['backward'].append(pkg1['name'])
 127         else:
 128             pkg2['backward'] = [pkg1['name']]
 129
 130     def _make_scc(pkg_id):
 131         scc_num[0] += 1
 132         scc_list = []
 133         # stack is not empty
 134         while stack:
 135             pkg = 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 %s and %s' % (pkg_info['name'], con['name']))
 162                             return True
 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, pkg['version']):
 172                                 logger.info('Conflict %s and %s' % (pkg_info['name'], pkg['name']))
 173                                 return True
 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 %s and %s' % (pkg_info['name'], pkg['name']))
 179                             return True
 180         return False
 181
 182     def _add_conflicts(pkg_info):
 183         if pkg_info.get('conflicts'):
 184             for con in pkg_info['conflicts']:
 185                 if not con['name'] in conflicts:
 186                     conflicts[con['name']] = []
 187                 conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
 188                 logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
 189
 190     def _analyze_dep(pkg_info):
 191         if not pkg_info:
 192             return
 193
 194         pkg_id = pkg_info['id']
 195         number[0] += 1
 196         selected[pkg_id] = number[0]
 197         min_num[pkg_id] = number[0]
 198         stack.append(pkg_info)
 199
 200         dep_rpms = set([pkg_info['name']])
 201
 202         # check for conflicts
 203         if _check_conflicts(pkg_info):
 204             progress['status'] = False
 205             stack.pop()
 206             return
 207
 208         # add rpms into conflicts table.
 209         _add_conflicts(pkg_info)
 210
 211         # Installation dependency analysis of rpm
 212         for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
 213             if pkg_info.get(dep_tag):
 214                 for req in pkg_info.get(dep_tag):
 215                     choose = None
 216                     #  Find dependency rpm based on capability/files
 217                     if req['name'] in provides:
 218                         # capability : [provide_rpm_1, provide_rpm_2, ... ]
 219                         # Select the rpm that meets the condition (version)
 220                         if dep_tag == Dependency.REQUIRES:
 221                             choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
 222                         else:
 223                             choose = _select_rpm(provides[req['name']], req)
 224                     elif req['name'] in files:
 225                         choose = _select_rpm_from_files(files[req['name']], req)
 226                     elif req['name'] in pkg_dict:
 227                         choose = pkg_dict.get(req['name'])
 228
 229                     if dep_tag == Dependency.RECOMMENDS:
 230                         # A Recommends B: B is installed when A is installed and B has no conflicts.
 231                         if not choose or _check_conflicts(choose):
 232                             logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
 233                             continue
 234
 235                     if choose:
 236                         # add forward/backward reference
 237                         _create_reference(pkg_info, choose)
 238
 239                         # ref count
 240                         # choose['ref_cnt'] = {req['name']: 1}
 241
 242                         if selected[choose['id']] == 0:
 243                             dep_set = _analyze_dep(choose)
 244                             if not progress['status']:
 245                                 break
 246
 247                             dep_rpms.update(dep_set)
 248                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 249                         elif scc_id[choose['id']] == 0:
 250                             # cross edge that can not be ignored
 251                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 252                     else:
 253                         # the rpm does not exists
 254                         logger.info(configmgr.message['dependency_not_exist'] % (req['name'], pkg_info['name']))
 255                         progress['status'] = False
 256                         break
 257
 258             if not progress['status']:
 259                 break
 260         if min_num[pkg_id] == selected[pkg_id]:
 261             # scc(strong connected components)
 262             _make_scc(pkg_id)
 263
 264         return dep_rpms
 265
 266     def _check_circular_dep(node):
 267         g_id = node.get('group')
 268         g_pkg_list = groups[g_id]
 269         g_dict = {}
 270
 271         # Set dict for group
 272         for pkgname in g_pkg_list:
 273             g_dict[pkgname] = None
 274
 275         for pkgname in g_pkg_list:
 276             pkg = pkg_dict[pkgname]
 277             # the node is selfchecked (the root node ignores selfchecked)
 278             #if stack[0]['id'] != pkg['id'] and pkg['selfChecked']:
 279             if selected_pkg['id'] != pkg['id'] and pkg['selfChecked']:
 280                 return False
 281             # check backward ref.
 282             for bname in pkg.get('backward'):
 283                 # If node is Referenced by another node (Not a node in the group),
 284                 # unable to uncheck group nodes
 285                 if not bname in g_dict:
 286                     return False
 287
 288         # init visited dict
 289         group_visited[g_id] = {}
 290         # delete backward reference of group node
 291         for pkgname in g_pkg_list:
 292             pkg = pkg_dict[pkgname]
 293             pkg['backward'] = None;
 294             group_visited[g_id][pkg['name']] = -1
 295         return True
 296
 297     def _delete_conflictdata(node):
 298         if node.get('conflicts'):
 299             for con in node.get('conflicts'):
 300                 if con['name'] in conflicts:
 301                     con_list = conflicts[con['name']]
 302                     for i in range(len(con_list)):
 303                         if con_list[i]['name'] == node['name']:
 304                             del con_list[i]
 305                             break;
 306
 307     def _remove_reference(parent, node):
 308         if parent is not None:
 309             # remove backward reference (parent)
 310             if node.get('backward'):
 311                 for i in range(len(node['backward'])):
 312                     if node['backward'][i] == parent['name']:
 313                         del node['backward'][i]
 314                         break
 315             # selfCheck node do not remove
 316             if node.get('selfChecked'):
 317                 return
 318
 319         if node.get('backward'):
 320             if node.get('group') is None or not _check_circular_dep(node):
 321                 return
 322
 323         # the selected node is uncheckable
 324         if node.get('group') and group_visited[node['group']]:
 325             group_visited[node['group']][node['name']] = 1
 326
 327         # if selected node has forward references
 328         if node.get('forward'):
 329             for fname in node.get('forward'):
 330                 fnode = pkg_dict.get(fname)
 331
 332                 # If pkg has a circular dependency and is unchekcable,
 333                 # circular dep. pkgs can only be visited once
 334                 gvisite = group_visited.get(fnode.get('group'))
 335                 if gvisite and gvisite[fnode['name']] == 1:
 336                     continue
 337                 _remove_reference(node, fnode)
 338             node['forward'] = None
 339             node['group'] = None
 340         # delete conflict data from conflicts dict
 341         _delete_conflictdata(node)
 342
 343     # recipe/repo
 344     if not recipe or not repoinfo:
 345         return []
 346
 347     group_set = set([])
 348     pkg_set = set([])
 349
 350     if recipe['Recipe'].get('Groups'):
 351         group_set.update(recipe['Recipe'].get('Groups'))
 352     if recipe['Recipe'].get('ExtraPackages'):
 353         pkg_set.update(recipe['Recipe'].get('ExtraPackages'))
 354
 355     # parsing group.xml
 356     if group_set:
 357         for repo in repoinfo:
 358             if repo.get('comps'):
 359                 try:
 360                     tree = etree.parse(repo.get('comps'))
 361                     root = tree.getroot()
 362                 except etree.XMLSyntaxError as e:
 363                     logger.info(e)
 364                     raise TICError(configmgr.message['xml_parse_error'] % ('group.xml', repo['baseurl']))
 365
 366                 # Convert groups to packages
 367                 for elm in root.findall('group'):
 368                     group_name = elm.find('name').text
 369                     if group_name in group_set:
 370                         pkglist = elm.find('packagelist')
 371                         plist = []
 372                         for pkgreq in pkglist.findall('packagereq'):
 373                             plist.append(pkgreq.text)
 374                         pkg_set.update(set(plist))
 375                         group_set.discard(group_name);
 376
 377     pkg_dict = pkg_group.get('pkg_dict')
 378     provides = pkg_group.get('provides')
 379     files = pkg_group.get('files')
 380     groups = pkg_group.get('groups')
 381     conflicts = pkg_group.get('conflicts')
 382
 383     stack = []
 384     number = [0]    # for pkg count
 385     scc_num = [0]   # for scc count
 386     group_num = [0]     # for group count
 387     scc_id = [0] * len(pkg_dict)
 388     min_num = [0] * len(pkg_dict)
 389     selected = [0] * len(pkg_dict)
 390     group_visited = None
 391     install_rpm = set([])
 392     progress = dict(status=True, message=None)
 393
 394     for pkg_name in pkg_set:
 395         progress['status'] = True
 396         selected_pkg = pkg_dict.get(pkg_name)
 397
 398         if not selected_pkg:
 399             if provides.get(pkg_name):
 400                 pro = provides.get(pkg_name)[0]
 401                 selected_pkg = pkg_dict.get(pro['name'])
 402             else:
 403                 logger.info(configmgr.message['package_not_exist'] % pkg_name)
 404                 continue
 405
 406         selected_pkg['selfChecked'] = True
 407         if selected[selected_pkg['id']] == 0:
 408             dep_set = _analyze_dep(selected_pkg)
 409             if progress['status']:
 410                 install_rpm.update(dep_set)
 411             else:
 412                 # delete forward/backward reference
 413                 group_visited = {}
 414                 _remove_reference(None, selected_pkg)
 415     return list(install_rpm)