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         provide_list = []
 122         # 1. Choose the rpm included in version from provides
 123         if require.get('ver') is not None:
 124             for provide in capability:
 125                 ver_data = provide['data']
 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         # TODO: default profile rpm should be selected
 143         for i in range(0, len(provide_list)):
 144             tmp_info = pkg_dict.get(provide_list[i].get('name'))
 145             if tmp_info['name'] in pkg_set or selected[tmp_info['id']] >= 1:
 146                 return tmp_info
 147         # 2-2. Select the latest version of rpm
 148         max_ver = None
 149         for i in range(0, len(provide_list)):
 150             if not _check_conflicts(pkg_dict.get(provide_list[i]['name'])):
 151                 if max_ver:
 152                     cap_info = provide_list[i].get('data')
 153                     ret = _compare_ver(max_ver.get('data'), cap_info)
 154                     # cap_info is greater than max_ver
 155                     if ret == -1:
 156                         max_ver = provide_list[i]
 157                 else:
 158                     max_ver = provide_list[i]
 159
 160         # all of capability pkg are in conflict
 161         if max_ver is None:
 162             return pkg_dict.get(provide_list[i]['name'])
 163
 164         return pkg_dict.get(max_ver.get('name'))
 165
 166     def _create_reference(pkg1, pkg2):
 167         # duplicate check
 168         if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
 169             return
 170
 171         if pkg1.get('forward'):
 172             pkg1['forward'].append(pkg2['name'])
 173         else:
 174             pkg1['forward'] = [pkg2['name']]
 175
 176         if pkg2.get('backward'):
 177             pkg2['backward'].append(pkg1['name'])
 178         else:
 179             pkg2['backward'] = [pkg1['name']]
 180
 181     def _make_scc(pkg_id):
 182         scc_num[0] += 1
 183         scc_list = []
 184         # stack is not empty
 185         while stack:
 186             pkg = stack.pop()
 187             scc_id[pkg['id']] = scc_num[0]
 188             scc_list.append(pkg)
 189             if pkg_id == pkg['id']:
 190                 break
 191
 192         # circular dependency
 193         if len(scc_list) > 1:
 194             group_num[0] += 1
 195             group_names = []
 196             # add group id
 197             for pkg in scc_list:
 198                 pkg['group'] = group_num[0]
 199                 group_names.append(pkg['name'])
 200
 201             # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
 202             groups[group_num[0]] = group_names
 203
 204     def _check_conflicts(pkg_info):
 205         # 1. Check whether node can be installed
 206         if pkg_info.get('provides') is not None:
 207             for pro in pkg_info['provides']:
 208                 if pro['name'] in conflicts:
 209                     for con in conflicts[pro['name']]:
 210                         if not con['data'].get('ver') or _meetRequireVersion(con['data'], pro):
 211                             #package conflict
 212                             return True
 213
 214         #2. If the conflict package defined by node is installed
 215         if pkg_info.get('conflicts') is not None:
 216             for con in pkg_info['conflicts']:
 217                 if con['name'] in provides:
 218                     for pro in provides[con['name']]:
 219                         pkg = pkg_dict[pro['name']]
 220                         if selected[pkg['id']] != 0:
 221                             if not con.get('ver') or _meetRequireVersion(con, pkg['version']):
 222                                 return True
 223                 elif con['name'] in pkg_dict:
 224                     pkg = pkg_dict[con['name']]
 225                     if selected[pkg['id']] != 0:
 226                         if not con.get('ver') or _meetRequireVersion(con, pkg['version']):
 227                             return True
 228         return False
 229
 230     def _add_conflicts(pkg_info):
 231         if pkg_info.get('conflicts'):
 232             for con in pkg_info['conflicts']:
 233                 if not con['name'] in conflicts:
 234                     conflicts[con['name']] = []
 235                 conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
 236                 logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
 237
 238     def _analyze_dep(pkg_info):
 239         if not pkg_info:
 240             return
 241
 242         pkg_id = pkg_info['id']
 243         number[0] += 1
 244         selected[pkg_id] = number[0]
 245         min_num[pkg_id] = number[0]
 246         stack.append(pkg_info)
 247
 248         dep_rpms = set([pkg_info['name']])
 249
 250         # check for conflicts
 251         if _check_conflicts(pkg_info):
 252             progress['status'] = False
 253             stack.pop()
 254             return
 255
 256         # add rpms into conflicts table.
 257         _add_conflicts(pkg_info)
 258
 259         # Installation dependency analysis of rpm
 260         for dep_tag in ['requires']: # 'recommends'
 261             if pkg_info.get(dep_tag):
 262                 for req in pkg_info.get(dep_tag):
 263                     choose = None
 264                     #  Find dependency rpm based on capability/files
 265                     if req['name'] in provides:
 266                         # capability : [provide_rpm_1, provide_rpm_2, ... ]
 267                         # Select the rpm that meets the condition (version)
 268                         choose = _select_rpm(provides[req['name']], req)
 269                     elif req['name'] in files:
 270                         choose = pkg_dict.get(files[req['name']][0])
 271                     elif req['name'] in pkg_dict:
 272                         choose = pkg_dict.get(req['name'])
 273
 274                     if choose:
 275                         if selected[choose['id']] == 0:
 276                             dep_set = _analyze_dep(choose)
 277                             if not progress['status']:
 278                                 break
 279
 280                             dep_rpms.update(dep_set)
 281                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 282                         elif scc_id[choose['id']] == 0:
 283                             # cross edge that can not be ignored
 284                             min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
 285
 286                         # add forward/backward reference
 287                         _create_reference(pkg_info, choose)
 288                     else:
 289                         # the rpm does not exists
 290                         logger.info('the capability(%s) needed by %s does not exist. should be checked for error' % (req['name'], pkg_info['name']))
 291                         progress['status'] = False
 292                         break
 293
 294             if not progress['status']:
 295                 break
 296         if min_num[pkg_id] == selected[pkg_id]:
 297             # scc(strong connected components)
 298             _make_scc(pkg_id)
 299
 300         return dep_rpms
 301
 302     def _check_circular_dep(node):
 303         g_id = node.get('group')
 304         g_pkg_list = groups[g_id]
 305         g_dict = {}
 306
 307         # Set dict for group
 308         for pkgname in g_pkg_list:
 309             g_dict[pkgname] = None
 310
 311         for pkgname in g_pkg_list:
 312             pkg = pkg_dict[pkgname]
 313             # the node is selfchecked (the root node ignores selfchecked)
 314             if stack[0]['id'] != pkg['id'] and pkg['selfChecked']:
 315                 return False
 316             # check backward ref.
 317             for bname in pkg.get('backward'):
 318                 # If node is Referenced by another node (Not a node in the group),
 319                 # unable to uncheck group nodes
 320                 if not bname in g_dict:
 321                     return False
 322
 323         # init visited dict
 324         group_visited[g_id] = {}
 325         # delete backward reference of group node
 326         for pkgname in g_pkg_list:
 327             pkg = pkg_dict[pkgname]
 328             pkg['backward'] = None;
 329             group_visited[g_id][pkg['name']] = -1
 330         return True
 331
 332     def _delete_conflictdata(node):
 333         if node.get('conflicts'):
 334             for con in node.get('conflicts'):
 335                 if con['name'] in conflicts:
 336                     con_list = conflicts[con['name']]
 337                     for i in range(len(con_list)):
 338                         if con_list[i]['name'] == node['name']:
 339                             del con_list[i]
 340                             break;
 341
 342     def _remove_reference(parent, node):
 343         if parent is not None:
 344             # remove backward reference (parent)
 345             if node.get('backward'):
 346                 for i in range(len(node['backward'])):
 347                     if node['backward'][i] == parent['name']:
 348                         del node['backward'][i]
 349                         break
 350             # selfCheck node do not remove
 351             if pkg_info.get('selfChecked'):
 352                 return
 353
 354         if node.get('backward'):
 355             if node.get('group') is None or _check_circular_dep(node):
 356                 return
 357
 358         # the selected node is uncheckable
 359         if node.get('group') and group_visited[node['group']]:
 360             group_visited[node['group']][node['name']] = 1
 361
 362         # if selected node has forward references
 363         if node.get('forward'):
 364             for fname in node.get('forward'):
 365                 fnode = pkg_dict[fname]
 366
 367                 # If pkg has a circular dependency and is unchekcable,
 368                 # circular dep. pkgs can only be visited once
 369                 if fnode.get('group') and group_visited[fnode['group']][fnode['name']] == 1:
 370                     continue
 371
 372                 _remove_reference(node, fnode)
 373             node['forward'] = None
 374             node['group'] = None
 375         # delete conflict data from conflicts dict
 376         _delete_conflictdata(node)
 377
 378     # recipe/repo
 379     if not recipe or not repoinfo:
 380         return []
 381
 382     default = recipe.get('Default')
 383     config = recipe.get('Configurations')[0]
 384     platform_name = config.get('Platform')
 385     platform = recipe.get(platform_name)
 386
 387     # check groups/extraPackages
 388     group_set = set([])
 389     pkg_set = set([])
 390     for g in [default, platform, config]:
 391         if g.has_key('Groups'):
 392             group_set.update(g.get('Groups'))
 393         if g.has_key('ExtraPackages'):
 394             pkg_set.update(g.get('ExtraPackages'))
 395     group_dict = dict.fromkeys(group_set)
 396
 397     # parsing group.xml
 398     try:
 399         tree = etree.parse(repoinfo[0].get('comps'))
 400         root = tree.getroot()
 401     except etree.XMLSyntaxError as e:
 402         raise TICError('primary.xml syntax error. %s', e)
 403
 404     # Convert groups to packages
 405     for elm in root.findall('group'):
 406         group_name = elm.find('name').text
 407         if group_dict.has_key(group_name):
 408             pkglist = elm.find('packagelist')
 409             plist = []
 410             for pkgreq in pkglist.findall('packagereq'):
 411                 plist.append(pkgreq.text)
 412             pkg_set.update(set(plist))
 413
 414     pkg_dict = pkg_group.get('pkg_dict')
 415     provides = pkg_group.get('provides')
 416     files = pkg_group.get('files')
 417     groups = pkg_group.get('groups')
 418     conflicts = pkg_group.get('conflicts')
 419
 420     stack = []
 421     number = [0]    # for pkg count
 422     scc_num = [0]   # for scc count
 423     group_num = [0]     # for group count
 424     scc_id = [0] * len(pkg_dict)
 425     min_num = [0] * len(pkg_dict)
 426     selected = [0] * len(pkg_dict)
 427     group_visited = None
 428     install_rpm = set([])
 429     progress = dict(status=True, message=None)
 430
 431     for pkg_name in pkg_set:
 432         progress['status'] = True
 433         pkg_info = pkg_dict.get(pkg_name)
 434
 435         # TODO: temporary code (Define capability in group)
 436         if not pkg_info:
 437             pro = provides.get(pkg_name)[0]
 438             pkg_info = pkg_dict.get(pro['name'])
 439
 440         pkg_info['selfChecked'] = True
 441         if selected[pkg_info['id']] == 0:
 442             dep_set = _analyze_dep(pkg_info)
 443             if progress['status']:
 444                 install_rpm.update(dep_set)
 445             else:
 446                 # delete forward/backward reference
 447                 group_visited = {}
 448                 _remove_reference(None, pkg_info)
 449     return list(install_rpm)