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