tic/dependency.py

   1 #!/usr/bin/python
   2 # Copyright (c) 2000 - 2016 Samsung Electronics Co., Ltd. All rights reserved.
   3 #
   4 # Contact:
   5 # @author Chulwoo Shin <cw1.shin@samsung.com>
   6 #
   7 # Licensed under the Apache License, Version 2.0 (the "License");
   8 # you may not use this file except in compliance with the License.
   9 # You may obtain a copy of the License at
  10 #
  11 # http://www.apache.org/licenses/LICENSE-2.0
  12 #
  13 # Unless required by applicable law or agreed to in writing, software
  14 # distributed under the License is distributed on an "AS IS" BASIS,
  15 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 # See the License for the specific language governing permissions and
  17 # limitations under the License.
  18 #
  19 # Contributors:
  20 # - S-Core Co., Ltd
  21
  22 import logging
  23 from lxml import etree
  24 from tic.utils.error import TICError
  25 from tic.utils.rpmmisc import meetRequireVersion, compare_ver
  26 from tic.utils.rpmmisc import Dependency
  27 from tic.config import configmgr
  28
  29 DEFAULT_PROFILE = 'EMPTY'
  30
  31 def get_installed_packages(recipe, repoinfo, pkg_group):
  32     logger = logging.getLogger(__name__)
  33
  34     def _select_rpm_from_files(fileList, require):
  35         if not fileList or not require:
  36             return None
  37         # 1. sort
  38         fileList.sort()
  39         # 2-1. Choose the default rpm or the selected rpm
  40         for fname in fileList:
  41             file_info = pkg_dict.get(fname)
  42             if fname in pkg_set or selected[file_info['id']] >= 1:
  43                 return file_info
  44         # 2-2. Choose the rpm (it does not conflitcs)
  45         for fname in fileList:
  46             file_info = pkg_dict.get(fname)
  47             if not _check_conflicts(file_info):
  48                 return file_info
  49         return pkg_dict.get(fileList[0])
  50
  51     def _select_rpm(capability, require, recommends=None):
  52         provide_list = []
  53         # 1. Choose the rpm included in version from provides
  54         if require.get('ver'):
  55             for provide in capability:
  56                 ver_data = provide['data']
  57                 # If there is no capability version, use version of package
  58                 if not ver_data.get('ver'):
  59                     ver_data = pkg_dict.get(provide['name']).get('version')
  60                 if meetRequireVersion(require, ver_data):
  61                     provide_list.append(provide)
  62         else:
  63             provide_list = capability
  64
  65         # error case (the rpm does not exist)
  66         if not provide_list:
  67             return None
  68
  69         if len(provide_list) == 1:
  70             return pkg_dict.get(provide_list[0].get('name'))
  71
  72         # 2 Select one of the rpms by priority
  73         # 2-1. Choose the default rpm or the selected rpm
  74         for pro in provide_list:
  75             provide_info = pkg_dict.get(pro.get('name'))
  76             if provide_info['name'] in pkg_set or selected[provide_info['id']] >= 1:
  77                 return provide_info
  78
  79         # 2-2. Choose the defualt profile
  80         # TODO: should be supported
  81         # if provide_info['profile'] == DEFAULT_PROFILE:
  82             # return provide_info
  83
  84         # 2.3. Choose recommends pkg (pkg-name or capability)
  85         if recommends:
  86             for pro in provide_list:
  87                 provide_info = pkg_dict.get(pro.get('name'))
  88                 for reco in recommends:
  89                     # 2-3 Case. select a pkg that is named
  90                     if reco['name'] == provide_info['name']:
  91                         return provide_info
  92                     # 2-3 Case. select a pkg that provides
  93                     for cap in provide_info.get('provides'):
  94                         if reco['name'] == cap['name']:
  95                             return provide_info
  96         # 2-4. Select the latest version of rpm
  97         max_ver = None
  98         for pro in provide_list:
  99             if not _check_conflicts(pkg_dict.get(pro.get('name'))):
 100                 if max_ver:
 101                     cap_info = pro.get('data')
 102                     ret = compare_ver(max_ver.get('data'), cap_info)
 103                     if ret == 0: # equals
 104                         # string compare (compare string lexicographically using ASCII value)
 105                         if max_ver.get('name') > pro.get('name'):
 106                             max_ver = pro
 107                     elif ret == -1: # greater than max_ver
 108                         max_ver = pro
 109                 else:
 110                     max_ver = pro
 111
 112         # all of capability pkg are in conflict
 113         if max_ver is None:
 114             return pkg_dict.get(provide_list[0]['name'])
 115
 116         return pkg_dict.get(max_ver.get('name'))
 117
 118     def _create_reference(pkg1, pkg2):
 119         # duplicate check
 120         if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
 121             return
 122
 123         if pkg1.get('forward'):
 124             pkg1['forward'].append(pkg2['name'])
 125         else:
 126             pkg1['forward'] = [pkg2['name']]
 127
 128         if pkg2.get('backward'):
 129             pkg2['backward'].append(pkg1['name'])
 130         else:
 131             pkg2['backward'] = [pkg1['name']]
 132
 133     def _make_scc(pkg_id):
 134         scc_num[0] += 1
 135         scc_list = []
 136         # stack is not empty
 137         while stack:
 138             pkg = stack.pop()
 139             scc_id[pkg['id']] = scc_num[0]
 140             scc_list.append(pkg)
 141             if pkg_id == pkg['id']:
 142                 break
 143
 144         # circular dependency
 145         if len(scc_list) > 1:
 146             group_num[0] += 1
 147             group_names = []
 148             # add group id
 149             for pkg in scc_list:
 150                 pkg['group'] = group_num[0]
 151                 group_names.append(pkg['name'])
 152
 153             # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
 154             groups[group_num[0]] = group_names
 155
 156     def _check_conflicts(pkg_info):
 157         # 1. Check whether node can be installed
 158         if pkg_info.get('provides') is not None:
 159             for pro in pkg_info['provides']:
 160                 if pro['name'] in conflicts:
 161                     for con in conflicts[pro['name']]:
 162                         if not con['data'].get('ver') or meetRequireVersion(con['data'], pro):
 163                             #package conflict
 164                             logger.info('Conflict %s and %s' % (pkg_info['name'], con['name']))
 165                             return True
 166
 167         #2. If the conflict package defined by node is installed
 168         if pkg_info.get('conflicts') is not None:
 169             for con in pkg_info['conflicts']:
 170                 if con['name'] in provides:
 171                     for pro in provides[con['name']]:
 172                         pkg = pkg_dict[pro['name']]
 173                         if selected[pkg['id']] != 0:
 174                             if not con.get('ver') or meetRequireVersion(con, pkg['version']):
 175                                 logger.info('Conflict %s and %s' % (pkg_info['name'], pkg['name']))
 176                                 return True
 177                 elif con['name'] in pkg_dict:
 178                     pkg = pkg_dict[con['name']]
 179                     if selected[pkg['id']] != 0:
 180                         if not con.get('ver') or meetRequireVersion(con, pkg['version']):
 181                             logger.info('Conflict %s and %s' % (pkg_info['name'], pkg['name']))
 182                             return True
 183         return False
 184
 185     def _add_conflicts(pkg_info):
 186         if pkg_info.get('conflicts'):
 187             for con in pkg_info['conflicts']:
 188                 if not con['name'] in conflicts:
 189                     conflicts[con['name']] = []
 190                 conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
 191                 logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
 192
 193     def _analyze_dep(pkg_info):
 194         if not pkg_info:
 195             return
 196
 197         pkg_id = pkg_info['id']
 198         number[0] += 1
 199         selected[pkg_id] = number[0]
 200         min_num[pkg_id] = number[0]
 201         stack.append(pkg_info)
 202
 203         dep_rpms = set([pkg_info['name']])
 204
 205         # check for conflicts
 206         if _check_conflicts(pkg_info):
 207             progress['status'] = False
 208             stack.pop()
 209             return
 210
 211         # add rpms into conflicts table.
 212         _add_conflicts(pkg_info)
 213
 214         # Installation dependency analysis of rpm
 215         for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
 216             if pkg_info.get(dep_tag):
 217                 for req in pkg_info.get(dep_tag):
 218                     choose = None
 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)