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 analyze_dependency(pkg_group):
  32
  33     def dep_dfs(pkg_id):
  34         #logger = logging.getLogger(__name__)
  35         if pkg_list[pkg_id].get('dependency') is not None:
  36             return pkg_list[pkg_id].get('dependency')
  37
  38         number[0] += 1
  39         visited[pkg_id] = number[0]
  40         min_num[pkg_id] = number[0]
  41         stack.append(pkg_id)
  42
  43         dep_set = set([pkg_list[pkg_id]['name']])
  44
  45         if pkg_list[pkg_id].get('requires'):
  46             for req in pkg_list[pkg_id].get('requires'):
  47                 req_id = req.get('id')
  48                 if req_id is not None:
  49                     if scc_list[req_id] > 0:
  50                         dep_set.update(pkg_list[req_id].get('dependency'))
  51                         continue
  52
  53                     if visited[req_id] == 0:
  54                         dep_set.update(dep_dfs(req_id))
  55
  56                     min_num[pkg_id] = min(min_num[pkg_id], min_num[req_id])
  57                 else:
  58                     #TODO: package does not exist
  59                     #logger.warning('%s does not exist in repo', req['name'])
  60                     pass
  61
  62         if min_num[pkg_id] == visited[pkg_id]:
  63             # scc (string connected components)
  64             make_scc(pkg_id, list(dep_set))
  65
  66         return dep_set
  67
  68     def make_scc(pkg_id, dep_list):
  69         p_id = 0
  70         scc_num[0] += 1
  71         # stack is not empty
  72         while stack:
  73             p_id = stack.pop()
  74             scc_list[p_id] = scc_num[0]
  75             pkg_list[p_id]['dependency'] = dep_list
  76             if pkg_id == p_id:
  77                 break
  78
  79     def analyze():
  80         for pkg_id in range(len(pkg_list)):
  81             if visited[pkg_id] == 0:
  82                 dep_dfs(pkg_id)
  83
  84     #TODO: Exception handling
  85     if not pkg_group:
  86         return None
  87
  88     # package install-dependency analysis
  89     pkg_list = pkg_group.get('pkg_list')
  90     number = [0]
  91     scc_num = [0]
  92     visited = [0]*len(pkg_list)
  93     min_num = [0]*len(pkg_list)
  94     scc_list = [0]*len(pkg_list)
  95     stack = []
  96
  97     return analyze()
  98
  99 def get_installed_packages(recipe, repoinfo, pkg_group):
 100     logger = logging.getLogger(__name__)
 101
 102     def _select_rpm_from_files(fileList, require):
 103         if not fileList or not require:
 104             return None
 105         # 1. sort
 106         fileList.sort()
 107         # 2-1. Choose the default rpm or the selected rpm
 108         for fname in fileList:
 109             file_info = pkg_dict.get(fname)
 110             if fname in pkg_set or selected[file_info['id']] >= 1:
 111                 return file_info
 112         # 2-2. Choose the rpm (it does not conflitcs)
 113         for fname in fileList:
 114             file_info = pkg_dict.get(fname)
 115             if not _check_conflicts(file_info):
 116                 return file_info
 117         return pkg_dict.get(fileList[0])
 118
 119     def _select_rpm(capability, require, recommends=None):
 120         provide_list = []
 121         # 1. Choose the rpm included in version from provides
 122         if require.get('ver'):
 123             for provide in capability:
 124                 ver_data = provide['data']
 125                 # If there is no capability version, use version of package
 126                 if not ver_data.get('ver'):
 127                     ver_data = pkg_dict.get(provide['name']).get('version')
 128                 if meetRequireVersion(require, ver_data):
 129                     provide_list.append(provide)
 130         else:
 131             provide_list = capability
 132
 133         # error case (the rpm does not exist)
 134         if not provide_list:
 135             return None
 136
 137         if len(provide_list) == 1:
 138             return pkg_dict.get(provide_list[0].get('name'))
 139
 140         # 2 Select one of the rpms by priority
 141         # 2-1. Choose the default rpm or the selected rpm
 142         for pro in provide_list:
 143             provide_info = pkg_dict.get(pro.get('name'))
 144             if provide_info['name'] in pkg_set or selected[provide_info['id']] >= 1:
 145                 return provide_info
 146
 147         # 2-2. Choose the defualt profile
 148         # TODO: should be supported
 149         # if provide_info['profile'] == DEFAULT_PROFILE:
 150             # return provide_info
 151
 152         # 2.3. Choose recommends pkg (pkg-name or capability)
 153         if recommends:
 154             for pro in provide_list:
 155                 provide_info = pkg_dict.get(pro.get('name'))
 156                 for reco in recommends:
 157                     # 2-3 Case. select a pkg that is named
 158                     if reco['name'] == provide_info['name']:
 159                         return provide_info
 160                     # 2-3 Case. select a pkg that provides
 161                     for cap in provide_info.get('provides'):
 162                         if reco['name'] == cap['name']:
 163                             return provide_info
 164         # 2-4. Select the latest version of rpm
 165         max_ver = None
 166         for pro in provide_list:
 167             if not _check_conflicts(pkg_dict.get(pro.get('name'))):
 168                 if max_ver:
 169                     cap_info = pro.get('data')
 170                     ret = compare_ver(max_ver.get('data'), cap_info)
 171                     if ret == 0: # equals
 172                         # string compare (compare string lexicographically using ASCII value)
 173                         if max_ver.get('name') > pro.get('name'):
 174                             max_ver = pro
 175                     elif ret == -1: # greater than max_ver
 176                         max_ver = pro
 177                 else:
 178                     max_ver = pro
 179
 180         # all of capability pkg are in conflict
 181         if max_ver is None:
 182             return pkg_dict.get(provide_list[0]['name'])
 183
 184         return pkg_dict.get(max_ver.get('name'))
 185
 186     def _create_reference(pkg1, pkg2):
 187         # duplicate check
 188         if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
 189             return
 190
 191         if pkg1.get('forward'):
 192             pkg1['forward'].append(pkg2['name'])
 193         else:
 194             pkg1['forward'] = [pkg2['name']]
 195
 196         if pkg2.get('backward'):
 197             pkg2['backward'].append(pkg1['name'])
 198         else:
 199             pkg2['backward'] = [pkg1['name']]
 200
 201     def _make_scc(pkg_id):
 202         scc_num[0] += 1
 203         scc_list = []
 204         # stack is not empty
 205         while stack:
 206             pkg = stack.pop()
 207             scc_id[pkg['id']] = scc_num[0]
 208             scc_list.append(pkg)
 209             if pkg_id == pkg['id']:
 210                 break
 211
 212         # circular dependency
 213         if len(scc_list) > 1:
 214             group_num[0] += 1
 215             group_names = []
 216             # add group id
 217             for pkg in scc_list:
 218                 pkg['group'] = group_num[0]
 219                 group_names.append(pkg['name'])
 220
 221             # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
 222             groups[group_num[0]] = group_names
 223
 224     def _check_conflicts(pkg_info):
 225         # 1. Check whether node can be installed
 226         if pkg_info.get('provides') is not None:
 227             for pro in pkg_info['provides']:
 228                 if pro['name'] in conflicts:
 229                     for con in conflicts[pro['name']]:
 230                         if not con['data'].get('ver') or meetRequireVersion(con['data'], pro):
 231                             #package conflict
 232                             logger.info('Conflict %s and %s' % (pkg_info['name'], con['name']))
 233                             return True
 234
 235         #2. If the conflict package defined by node is installed
 236         if pkg_info.get('conflicts') is not None:
 237             for con in pkg_info['conflicts']:
 238                 if con['name'] in provides:
 239                     for pro in provides[con['name']]:
 240                         pkg = pkg_dict[pro['name']]
 241                         if selected[pkg['id']] != 0:
 242                             if not con.get('ver') or meetRequireVersion(con, pkg['version']):
 243                                 logger.info('Conflict %s and %s' % (pkg_info['name'], pkg['name']))
 244                                 return True
 245                 elif con['name'] in pkg_dict:
 246                     pkg = pkg_dict[con['name']]
 247                     if selected[pkg['id']] != 0:
 248                         if not con.get('ver') or meetRequireVersion(con, pkg['version']):
 249                             logger.info('Conflict %s and %s' % (pkg_info['name'], pkg['name']))
 250                             return True
 251         return False
 252
 253     def _add_conflicts(pkg_info):
 254         if pkg_info.get('conflicts'):
 255             for con in pkg_info['conflicts']:
 256                 if not con['name'] in conflicts:
 257                     conflicts[con['name']] = []
 258                 conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
 259                 logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
 260
 261     def _analyze_dep(pkg_info):
 262         if not pkg_info:
 263             return
 264
 265         pkg_id = pkg_info['id']
 266         number[0] += 1
 267         selected[pkg_id] = number[0]
 268         min_num[pkg_id] = number[0]
 269         stack.append(pkg_info)
 270
 271         dep_rpms = set([pkg_info['name']])
 272
 273         # check for conflicts
 274         if _check_conflicts(pkg_info):
 275             progress['status'] = False
 276             stack.pop()
 277             return
 278
 279         # add rpms into conflicts table.
 280         _add_conflicts(pkg_info)
 281
 282         # Installation dependency analysis of rpm
 283         for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
 284             if pkg_info.get(dep_tag):
 285                 for req in pkg_info.get(dep_tag):
 286                     choose = None
 287                     #  Find dependency rpm based on capability/files
 288                     if req['name'] in provides:
 289                         # capability : [provide_rpm_1, provide_rpm_2, ... ]
 290                         # Select the rpm that meets the condition (version)
 291                         if dep_tag == Dependency.REQUIRES:
 292                             choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
 293                         else:
 294                             choose = _select_rpm(provides[req['name']], req)
 295                     elif req['name'] in files:
 296                         choose = _select_rpm_from_files(files[req['name']], req)
 297                         #choose = pkg_dict.get(files[req['name']][0])
 298                     elif req['name'] in pkg_dict:
 299                         choose = pkg_dict.get(req['name'])
 300
 301                     if dep_tag == Dependency.RECOMMENDS:
 302                         # A Recommends B: B is installed when A is installed and B has no conflicts.
 303                         if not choose or _check_conflicts(choose):
 304                             logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
 305                             continue
 306
 307                     if choose:
 308                         if selected[choose['id']] == 0:
 309                             dep_set = _analyze_dep(choose)
 310                             if not progress['status']:
 311                                 break
 312
 313                             dep_rpms.update(dep_set)
 314                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 315                         elif scc_id[choose['id']] == 0:
 316                             # cross edge that can not be ignored
 317                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 318
 319                         # add forward/backward reference
 320                         _create_reference(pkg_info, choose)
 321                     else:
 322                         # the rpm does not exists
 323                         logger.info(configmgr.message['dependency_not_exist'] % (req['name'], pkg_info['name']))
 324                         progress['status'] = False
 325                         break
 326
 327             if not progress['status']:
 328                 break
 329         if min_num[pkg_id] == selected[pkg_id]:
 330             # scc(strong connected components)
 331             _make_scc(pkg_id)
 332
 333         return dep_rpms
 334
 335     def _check_circular_dep(node):
 336         g_id = node.get('group')
 337         g_pkg_list = groups[g_id]
 338         g_dict = {}
 339
 340         # Set dict for group
 341         for pkgname in g_pkg_list:
 342             g_dict[pkgname] = None
 343
 344         for pkgname in g_pkg_list:
 345             pkg = pkg_dict[pkgname]
 346             # the node is selfchecked (the root node ignores selfchecked)
 347             if stack[0]['id'] != pkg['id'] and pkg['selfChecked']:
 348                 return False
 349             # check backward ref.
 350             for bname in pkg.get('backward'):
 351                 # If node is Referenced by another node (Not a node in the group),
 352                 # unable to uncheck group nodes
 353                 if not bname in g_dict:
 354                     return False
 355
 356         # init visited dict
 357         group_visited[g_id] = {}
 358         # delete backward reference of group node
 359         for pkgname in g_pkg_list:
 360             pkg = pkg_dict[pkgname]
 361             pkg['backward'] = None;
 362             group_visited[g_id][pkg['name']] = -1
 363         return True
 364
 365     def _delete_conflictdata(node):
 366         if node.get('conflicts'):
 367             for con in node.get('conflicts'):
 368                 if con['name'] in conflicts:
 369                     con_list = conflicts[con['name']]
 370                     for i in range(len(con_list)):
 371                         if con_list[i]['name'] == node['name']:
 372                             del con_list[i]
 373                             break;
 374
 375     def _remove_reference(parent, node):
 376         if parent is not None:
 377             # remove backward reference (parent)
 378             if node.get('backward'):
 379                 for i in range(len(node['backward'])):
 380                     if node['backward'][i] == parent['name']:
 381                         del node['backward'][i]
 382                         break
 383             # selfCheck node do not remove
 384             if pkg_info.get('selfChecked'):
 385                 return
 386
 387         if node.get('backward'):
 388             if node.get('group') is None or _check_circular_dep(node):
 389                 return
 390
 391         # the selected node is uncheckable
 392         if node.get('group') and group_visited[node['group']]:
 393             group_visited[node['group']][node['name']] = 1
 394
 395         # if selected node has forward references
 396         if node.get('forward'):
 397             for fname in node.get('forward'):
 398                 fnode = pkg_dict[fname]
 399
 400                 # If pkg has a circular dependency and is unchekcable,
 401                 # circular dep. pkgs can only be visited once
 402                 gvisite = group_visited.get(fnode.get('group'))
 403                 if gvisite and gvisite[fnode['name']] == 1:
 404                     continue
 405                 _remove_reference(node, fnode)
 406             node['forward'] = None
 407             node['group'] = None
 408         # delete conflict data from conflicts dict
 409         _delete_conflictdata(node)
 410
 411     # recipe/repo
 412     if not recipe or not repoinfo:
 413         return []
 414
 415     default = recipe.get('Default')
 416     config = recipe.get('Configurations')[0]
 417     platform_name = config.get('Platform')
 418     platform = recipe.get(platform_name)
 419
 420     # check groups/extraPackages
 421     group_set = set([])
 422     pkg_set = set([])
 423     for g in [default, platform, config]:
 424         if g.has_key('Groups'):
 425             group_set.update(g.get('Groups'))
 426         if g.has_key('ExtraPackages'):
 427             pkg_set.update(g.get('ExtraPackages'))
 428     #group_dict = dict.fromkeys(group_set)
 429
 430     # parsing group.xml
 431     if group_set:
 432         for repo in repoinfo:
 433             if repo.get('comps'):
 434                 try:
 435                     tree = etree.parse(repo.get('comps'))
 436                     root = tree.getroot()
 437                 except etree.XMLSyntaxError as e:
 438                     logger.info(e)
 439                     raise TICError(configmgr.message['xml_parse_error'] % ('group.xml', repo['baseurl']))
 440
 441                 # Convert groups to packages
 442                 for elm in root.findall('group'):
 443                     group_name = elm.find('name').text
 444                     if group_name in group_set:
 445                         pkglist = elm.find('packagelist')
 446                         plist = []
 447                         for pkgreq in pkglist.findall('packagereq'):
 448                             plist.append(pkgreq.text)
 449                         pkg_set.update(set(plist))
 450                         group_set.discard(group_name);
 451
 452     pkg_dict = pkg_group.get('pkg_dict')
 453     provides = pkg_group.get('provides')
 454     files = pkg_group.get('files')
 455     groups = pkg_group.get('groups')
 456     conflicts = pkg_group.get('conflicts')
 457
 458     stack = []
 459     number = [0]    # for pkg count
 460     scc_num = [0]   # for scc count
 461     group_num = [0]     # for group count
 462     scc_id = [0] * len(pkg_dict)
 463     min_num = [0] * len(pkg_dict)
 464     selected = [0] * len(pkg_dict)
 465     group_visited = None
 466     install_rpm = set([])
 467     progress = dict(status=True, message=None)
 468
 469     for pkg_name in pkg_set:
 470         progress['status'] = True
 471         pkg_info = pkg_dict.get(pkg_name)
 472
 473         if not pkg_info:
 474             if provides.get(pkg_name):
 475                 pro = provides.get(pkg_name)[0]
 476                 pkg_info = pkg_dict.get(pro['name'])
 477             else:
 478                 logger.info(configmgr.message['package_not_exist'] % pkg_name)
 479                 continue
 480
 481         pkg_info['selfChecked'] = True
 482         if selected[pkg_info['id']] == 0:
 483             dep_set = _analyze_dep(pkg_info)
 484             if progress['status']:
 485                 install_rpm.update(dep_set)
 486             else:
 487                 # delete forward/backward reference
 488                 group_visited = {}
 489                 _remove_reference(None, pkg_info)
 490     return list(install_rpm)