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