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