#!/usr/bin/python
-# Copyright (c) 2000 - 2016 Samsung Electronics Co., Ltd. All rights reserved.
+# Copyright (c) 2016 Samsung Electronics Co., Ltd
#
-# Contact:
-# @author Chulwoo Shin <cw1.shin@samsung.com>
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
+# Licensed under the Flora License, Version 1.1 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
-# http://www.apache.org/licenses/LICENSE-2.0
+# http://floralicense.org/license/
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# - S-Core Co., Ltd
import logging
+from lxml import etree
+from tic.utils.error import TICError
+from tic.utils.rpmmisc import meetRequireVersion, compare_ver
+from tic.utils.rpmmisc import Dependency
+from tic.config import configmgr
-def analyze_dependency(pkg_group):
+DEFAULT_PROFILE = 'EMPTY'
+
+def get_installed_packages(recipe, repoinfo, pkg_group):
+ logger = logging.getLogger(__name__)
+
+ def _select_rpm_from_files(fileList, require):
+ if not fileList or not require:
+ return None
+ # 1. sort
+ fileList.sort()
+ # 2-1. Choose the default rpm or the selected rpm
+ for fname in fileList:
+ file_info = pkg_dict.get(fname)
+ if fname in required_inst_rpms or selected[file_info['id']] >= 1:
+ return file_info
+ # 2-2. Choose the rpm (it does not conflitcs)
+ for fname in fileList:
+ file_info = pkg_dict.get(fname)
+ if not _check_conflicts(file_info):
+ return file_info
+ return pkg_dict.get(fileList[0])
+
+ def _select_rpm(capability, require, recommends=None):
+ provide_list = []
+ # 1. Choose the rpm included in version from provides
+ if require.get('ver'):
+ for provide in capability:
+ ver_data = provide['data']
+ # If there is no capability version, use version of package
+ if not ver_data.get('ver'):
+ ver_data = pkg_dict.get(provide['name']).get('version')
+ if meetRequireVersion(require, ver_data):
+ provide_list.append(provide)
+ else:
+ provide_list = capability
+
+ # error case (the rpm does not exist)
+ if not provide_list:
+ return None
+
+ if len(provide_list) == 1:
+ return pkg_dict.get(provide_list[0].get('name'))
+
+ # 2 Select one of the rpms by priority
+ # 2-1. Choose the default rpm or the selected rpm
+ for pro in provide_list:
+ provide_info = pkg_dict.get(pro['name'])
+ if provide_info['name'] in required_inst_rpms or selected[provide_info['id']] >= 1:
+ return provide_info
+
+ # 2-2. Choose the defualt profile
+ # TODO: should be supported
+ # if provide_info['profile'] == DEFAULT_PROFILE:
+ # return provide_info
+
+ # 2.3. Choose recommends pkg (pkg-name or capability)
+ if recommends:
+ for pro in provide_list:
+ provide_info = pkg_dict.get(pro.get('name'))
+ for reco in recommends:
+ # 2-3 Case. select a pkg that is named
+ if reco['name'] == provide_info['name']:
+ return provide_info
+ # 2-3 Case. select a pkg that provides
+ for cap in provide_info.get('provides'):
+ if reco['name'] == cap['name']:
+ return provide_info
+ # 2-4. Select the latest version of rpm
+ max_ver = None
+ for pro in provide_list:
+ if not _check_conflicts(pkg_dict.get(pro.get('name'))):
+ if max_ver:
+ cap_info = pro.get('data')
+ ret = compare_ver(max_ver.get('data'), cap_info)
+ if ret == 0: # equals
+ # string compare (compare string lexicographically using ASCII value)
+ if max_ver.get('name') > pro.get('name'):
+ max_ver = pro
+ elif ret == -1: # greater than max_ver
+ max_ver = pro
+ else:
+ max_ver = pro
+
+ # all of capability pkg are in conflict
+ if max_ver is None:
+ return pkg_dict.get(provide_list[0]['name'])
+
+ return pkg_dict.get(max_ver.get('name'))
- def dep_dfs(pkg_id):
- logger = logging.getLogger(__name__)
- if pkg_list[pkg_id].get('dependency') is not None:
- return pkg_list[pkg_id].get('dependency')
+ def _create_reference(pkg1, pkg2):
+ # duplicate check
+ if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
+ return False
+ if pkg1.get('forward'):
+ pkg1['forward'].append(pkg2['name'])
+ else:
+ pkg1['forward'] = [pkg2['name']]
+
+ if pkg2.get('backward'):
+ pkg2['backward'].append(pkg1['name'])
+ else:
+ pkg2['backward'] = [pkg1['name']]
+ return True
+
+ def _make_scc(pkg_id):
+ scc_num[0] += 1
+ scc_list = []
+ # stack is not empty
+ while rpm_stack:
+ pkg = rpm_stack.pop()
+ scc_id[pkg['id']] = scc_num[0]
+ scc_list.append(pkg)
+ if pkg_id == pkg['id']:
+ break
+
+ # circular dependency
+ if len(scc_list) > 1:
+ group_num[0] += 1
+ group_names = []
+ # add group id
+ for pkg in scc_list:
+ pkg['group'] = group_num[0]
+ group_names.append(pkg['name'])
+
+ # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
+ groups[group_num[0]] = group_names
+
+ def _check_conflicts(pkg_info):
+ # 1. Check whether node can be installed
+ if pkg_info.get('provides') is not None:
+ for pro in pkg_info['provides']:
+ if pro['name'] in conflicts:
+ for con in conflicts[pro['name']]:
+ if not con['data'].get('ver') or meetRequireVersion(con['data'], pro):
+ #package conflict
+ #logger.info('Conflict Case-1) %s is conflict with %s' % (pkg_info['name'], con['name']))
+ return pkg_dict.get(con['name'])
+ #2. If the conflict package defined by node is installed
+ if pkg_info.get('conflicts') is not None:
+ for con in pkg_info['conflicts']:
+ if con['name'] in provides:
+ for pro in provides[con['name']]:
+ pkg = pkg_dict[pro['name']]
+ if selected[pkg['id']] != 0:
+ if not con.get('ver') or meetRequireVersion(con, pro['data']):
+ #logger.info('Conflict Case-2) %s is conflict with %s' % (pkg['name'], pkg_info['name']))
+ return pkg
+ elif con['name'] in pkg_dict:
+ pkg = pkg_dict[con['name']]
+ if selected[pkg['id']] != 0:
+ if not con.get('ver') or meetRequireVersion(con, pkg['version']):
+ #logger.info('Conflict Case-2) %s is conflict with %s' % (pkg['name'], pkg_info['name']))
+ return pkg
+ return None
+
+ def _remove_conflicts(pkg_info):
+ if pkg_info.get('conflicts'):
+ for con in pkg_info['conflicts']:
+ if con['name'] in conflicts:
+ c_list = conflicts[con['name']]
+ for i in range(len(c_list)):
+ if c_list[i]['name'] == pkg_info['name']:
+ del c_list[i]
+ break
+
+ def _add_conflicts(pkg_info):
+ if pkg_info.get('conflicts'):
+ for con in pkg_info['conflicts']:
+ if not con['name'] in conflicts:
+ conflicts[con['name']] = []
+ conflicts[con['name']].append(dict(name=pkg_info['name'], data=con))
+ #logger.info('%s add conflict package : %s' % (pkg_info['name'], con['name']))
+
+ def _analyze_dep(pkg_info):
+ if not pkg_info:
+ return
+
+ pkg_id = pkg_info['id']
number[0] += 1
- visited[pkg_id] = number[0]
+ selected[pkg_id] = number[0]
min_num[pkg_id] = number[0]
- stack.append(pkg_id)
-
- dep_set = set([pkg_list[pkg_id]['name']])
+ rpm_stack.append(pkg_info)
+
+ dep_rpms = set([pkg_info['name']])
+
+ # check for conflicts
+ if _check_conflicts(pkg_info):
+ progress['status'] = False
+ rpm_stack.pop()
+ return
- if pkg_list[pkg_id].get('requires'):
- for req in pkg_list[pkg_id].get('requires'):
- req_id = req.get('id')
- if req_id is not None:
- if scc_list[req_id] > 0:
- dep_set.update(pkg_list[req_id].get('dependency'))
+ # add rpms into conflicts table.
+ _add_conflicts(pkg_info)
+
+ # Installation dependency analysis of rpm
+ for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
+ if pkg_info.get(dep_tag):
+ for req in pkg_info.get(dep_tag):
+ choose = None
+ # self-reference (e.g. vim-base)
+ if req['name'] == pkg_info['name']:
continue
+ # Find dependency rpm based on capability/files
+ if req['name'] in provides:
+ # Select the rpm that meets the condition (version)
+ if dep_tag == Dependency.REQUIRES:
+ choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
+ else:
+ choose = _select_rpm(provides[req['name']], req)
+ elif req['name'] in files:
+ choose = _select_rpm_from_files(files[req['name']], req)
+ elif req['name'] in pkg_dict:
+ choose = pkg_dict.get(req['name'])
- if visited[req_id] == 0:
- dep_set.update(dep_dfs(req_id))
+ if dep_tag == Dependency.RECOMMENDS:
+ # A Recommends B: B is installed when A is installed and B has no conflicts.
+ if not choose or _check_conflicts(choose) is not None:
+ #logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
+ continue
+
+ if choose:
+ # add forward/backward reference
+ _create_reference(pkg_info, choose)
+
+ if selected[choose['id']] == 0:
+ dep_set = _analyze_dep(choose)
+ if not progress['status']:
+ break
+ dep_rpms.update(dep_set)
+ min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
+ elif scc_id[choose['id']] == 0:
+ # cross edge that can not be ignored
+ min_num[pkg_id] = min(min_num[pkg_id], min_num[choose['id']])
+ else:
+ # the rpm does not exists
+ logger.info(configmgr.message['dependency_not_exist'] % (req['name'], pkg_info['name']))
+ progress['status'] = False
+ break
+ if not progress['status']:
+ break
+ if min_num[pkg_id] == selected[pkg_id]:
+ # scc(strong connected components)
+ _make_scc(pkg_id)
+
+ return dep_rpms
+
+ def _check_circular_dep(node):
+ g_id = node.get('group')
+ g_pkg_list = groups[g_id]
+ g_dict = {}
+
+ # Set dict for group
+ for pkgname in g_pkg_list:
+ g_dict[pkgname] = None
+
+ for pkgname in g_pkg_list:
+ pkg = pkg_dict[pkgname]
+ # the node is selfchecked (the root node ignores selfchecked)
+ #if stack[0]['id'] != pkg['id'] and pkg['selfChecked']:
+ if selected_pkg['id'] != pkg['id'] and pkg['selfChecked']:
+ return False
+ # check backward ref.
+ for bname in pkg.get('backward'):
+ # If node is Referenced by another node (Not a node in the group),
+ # unable to uncheck group nodes
+ if not bname in g_dict:
+ return False
+
+ # init visited dict
+ group_visited[g_id] = {}
+ # delete backward reference of group node
+ for pkgname in g_pkg_list:
+ pkg = pkg_dict[pkgname]
+ pkg['backward'] = None;
+ group_visited[g_id][pkg['name']] = -1
+ return True
+
+ def _delete_conflictdata(node):
+ if node.get('conflicts'):
+ for con in node.get('conflicts'):
+ if con['name'] in conflicts:
+ con_list = conflicts[con['name']]
+ for i in range(len(con_list)):
+ if con_list[i]['name'] == node['name']:
+ del con_list[i]
+ break;
- min_num[pkg_id] = min(min_num[pkg_id], min_num[req_id])
- else:
- #TODO: package does not exist
- #logger.warning('%s does not exist in repo', req['name'])
- pass
+ def _remove_reference(parent, node):
+ if parent is not None:
+ # remove backward reference (parent)
+ if node.get('backward'):
+ for i in range(len(node['backward'])):
+ if node['backward'][i] == parent['name']:
+ del node['backward'][i]
+ break
+ # selfCheck node do not remove
+ if node.get('selfChecked'):
+ return
+
+ if node.get('backward'):
+ if node.get('group') is None or not _check_circular_dep(node):
+ return
- if min_num[pkg_id] == visited[pkg_id]:
- # scc (string connected components)
- make_scc(pkg_id, list(dep_set))
+ # the selected node is uncheckable
+ if node.get('group') and group_visited[node['group']]:
+ group_visited[node['group']][node['name']] = 1
- return dep_set
+ # if selected node has forward references
+ if node.get('forward'):
+ for fname in node.get('forward'):
+ fnode = pkg_dict.get(fname)
+
+ # If pkg has a circular dependency and is unchekcable,
+ # circular dep. pkgs can only be visited once
+ gvisite = group_visited.get(fnode.get('group'))
+ if gvisite and gvisite[fnode['name']] == 1:
+ continue
+ _remove_reference(node, fnode)
+ node['forward'] = None
+ node['group'] = None
+ # delete conflict data from conflicts dict
+ _delete_conflictdata(node)
- def make_scc(pkg_id, dep_list):
- p_id = 0
- scc_num[0] += 1
- # stack is not empty
- while stack:
- p_id = stack.pop()
- scc_list[p_id] = scc_num[0]
- pkg_list[p_id]['dependency'] = dep_list
- if pkg_id == p_id:
- break
+ def _add_refer(node, require):
+ if node['name'] not in require_refer:
+ require_refer[node['name']] = {}
+ require_refer[node['name']][require['name']] = 1
+
+ def _get_pkg_info(pkg_name):
+ if pkg_name in pkg_dict:
+ return pkg_dict[pkg_name]
+ if pkg_name in provides:
+ pro = provides[pkg_name][0]
+ return pkg_dict[pro['name']]
+ return None
- def analyze():
- for pkg_id in range(len(pkg_list)):
- if visited[pkg_id] == 0:
- dep_dfs(pkg_id)
+ def is_compatible_pkg (origin_pkg, new_pkg):
+ if origin_pkg['name'] in require_refer:
+ for r_name in require_refer[origin_pkg['name']]:
+ matched = False
+ if new_pkg.get('provides'):
+ for pro in new_pkg['provides']:
+ if r_name == pro['name']:
+ matched = True
+ break;
+ if not matched and new_pkg.get('file'):
+ for fname in new_pkg['file']:
+ if r_name == fname:
+ matched = True
+ break;
+ if not matched:
+ return False
+ return True
- #TODO: Exception handling
- if not pkg_group:
- return None
+ def _is_selfchecked(pkg_info):
+ if pkg_info.get('selfChecked'):
+ return True
+ return False
+
+ def _add_cap_info(pkg_info):
+ if not pkg_info.get('provides'):
+ return
+ for pro in pkg_info['provides']:
+ if not capabilities.get(pro['name']):
+ capabilities[pro['name']] = []
+ capabilities[pro['name']].append(pkg_info)
+
+ def _remove_dep_rpm(select_list):
+ if not select_list:
+ return
+ for rpm_info in select_list:
+ selected[rpm_info['id']] = 0
+ _delete_conflictdata(rpm_info)
+
+ def _check_dep_validation(pkg_info, select_list):
+ if not pkg_info:
+ return False
+ pkg_id = pkg_info['id']
+ number[0] += 1
+ selected[pkg_id] = number[0]
+ select_list.append(pkg_info)
+
+ # add rpm's capabilities
+ _add_cap_info(pkg_info)
+
+ # check for conflicts
+ conflict_pkg = _check_conflicts(pkg_info)
+ if conflict_pkg is not None:
+ if not _is_selfchecked(conflict_pkg) and is_compatible_pkg(conflict_pkg, pkg_info):
+ logger.info(pkg_info['name'] + ' and ' + conflict_pkg['name'] + ' is compatible')
+ comp_rpms.add(pkg_info['name'])
+ #_remove_conflicts(conflict_pkg)
+ else:
+ logger.info('###_1 ' + pkg_info['name'] + ' is conflict with ' + conflict_pkg['name'])
+ return False
+ elif pkg_info.get('provides'):
+ for pro in pkg_info['provides']:
+ if pro['name'] in capabilities:
+ for c_info in capabilities[pro['name']]:
+ if c_info['id'] == pkg_info['id']:
+ continue
+ if not _is_selfchecked(c_info) and is_compatible_pkg(c_info, pkg_info):
+ logger.info('###_2 ' + pkg_info['name'] + ' and ' + c_info['name'] + ' is compatible')
+ comp_rpms.add(pkg_info['name'])
+
+ # add rpms into conflicts table.
+ _add_conflicts(pkg_info)
+ # Installation dependency analysis of rpm
+ for dep_tag in [Dependency.REQUIRES, Dependency.RECOMMENDS]:
+ if pkg_info.get(dep_tag):
+ for req in pkg_info.get(dep_tag):
+ choose = None
+ # self-reference (e.g. vim-base)
+ if req['name'] == pkg_info['name']:
+ continue
+ if req['name'] in provides:
+ if dep_tag == Dependency.REQUIRES:
+ choose = _select_rpm(provides[req['name']], req, pkg_info.get('recommends'))
+ else:
+ choose = _select_rpm(provides[req['name']], req)
+ elif req['name'] in files:
+ choose = _select_rpm_from_files(files[req['name']], req)
+ elif req['name'] in pkg_dict:
+ choose = pkg_dict.get(req['name'])
+
+ if dep_tag == Dependency.RECOMMENDS:
+ # A Recommends B: B is installed when A is installed and B has no conflicts.
+ if not choose or _check_conflicts(choose) is not None:
+ #logger.info('%s recommended by %s is ignored for selection (Conflict)' % (req['name'], pkg_info['name']))
+ continue
+
+ if choose:
+ # add refer count, only requires
+ if dep_tag == Dependency.REQUIRES:
+ _add_refer(choose, req)
+
+ if selected[choose['id']] == 0:
+ if not _check_dep_validation(choose, select_list):
+ return False
+ else:
+ # the rpm does not exists
+ return False
+ return True
+
+ # recipe/repo
+ if not recipe or not repoinfo:
+ return []
- # package install-dependency analysis
- pkg_list = pkg_group.get('pkg_list')
- number = [0]
- scc_num = [0]
- visited = [0]*len(pkg_list)
- min_num = [0]*len(pkg_list)
- scc_list = [0]*len(pkg_list)
- stack = []
+ group_set = set([])
+ pkg_set = set([])
- return analyze()
+ if recipe['Recipe'].get('Groups'):
+ group_set.update(recipe['Recipe'].get('Groups'))
+ if recipe['Recipe'].get('ExtraPackages'):
+ pkg_set.update(recipe['Recipe'].get('ExtraPackages'))
+
+ # parsing group.xml
+ if group_set:
+ for repo in repoinfo:
+ if repo.get('comps'):
+ try:
+ tree = etree.parse(repo.get('comps'))
+ root = tree.getroot()
+ except etree.XMLSyntaxError as e:
+ logger.info(e)
+ raise TICError(configmgr.message['xml_parse_error'] % ('group.xml', repo['baseurl']))
+ # Convert groups to packages
+ for elm in root.findall('group'):
+ group_name = elm.find('name').text
+ if group_name in group_set:
+ pkglist = elm.find('packagelist')
+ plist = []
+ for pkgreq in pkglist.findall('packagereq'):
+ plist.append(pkgreq.text)
+ pkg_set.update(set(plist))
+ group_set.discard(group_name);
+
+ pkg_dict = pkg_group.get('pkg_dict')
+ provides = pkg_group.get('provides')
+ files = pkg_group.get('files')
+ groups = pkg_group.get('groups')
+ conflicts = pkg_group.get('conflicts')
+
+ number = [0] # for pkg count
+ scc_num = [0] # for scc count
+ group_num = [0] # for group count
+ scc_id = [0] * len(pkg_dict)
+ min_num = [0] * len(pkg_dict)
+ selected = [0] * len(pkg_dict)
+ group_visited = None
+ install_rpm = set([])
+ progress = dict(status=True, message=None)
+
+ capabilities = {}
+ require_refer = {}
+ candidate_rpms = set([])
+ # add rpms to install
+ select_rpms = set([])
+ # add reference value for rpm selection
+ required_inst_rpms = pkg_set.copy()
+
+ # 1. Check whether dependencies of rpm are available.
+ for pkg_name in pkg_set:
+ selected_pkg = _get_pkg_info(pkg_name)
+ if selected_pkg:
+ if selected[selected_pkg['id']] == 0:
+ select_list = []
+ comp_rpms = set([])
+ if _check_dep_validation(selected_pkg, select_list):
+ select_rpms.add(pkg_name)
+ candidate_rpms.update(comp_rpms)
+ else:
+ # case: conflict or rpm does not exist
+ _remove_dep_rpm(select_list)
+ logger.info('The %s install-dependencies are not valid, could not selected it' % pkg_name)
+ else:
+ select_rpms.add(pkg_name)
+ else:
+ logger.info(configmgr.message['package_not_exist'] % pkg_name)
+ # init conflict table and reference
+ number[0] = 0
+ selected = [0] * len(pkg_dict)
+ conflicts.clear()
+ required_inst_rpms.clear()
+ required_inst_rpms.update(select_rpms)
+ required_inst_rpms.update(candidate_rpms)
+ print(candidate_rpms)
+
+ # 2. Analyze rpm installation dependencies.
+ for pkg_name in select_rpms:
+ progress['status'] = True
+ selected_pkg = _get_pkg_info(pkg_name)
+ if selected_pkg:
+ rpm_stack = []
+ selected_pkg['selfChecked'] = True
+ if selected[selected_pkg['id']] == 0:
+ inst_rpms = _analyze_dep(selected_pkg)
+ if progress['status']:
+ install_rpm.update(inst_rpms)
+ else:
+ # Error Case
+ logger.info("[Dependency Issue] Could not install the %s" % selected_pkg)
+ # delete forward/backward reference
+ group_visited = {}
+ _remove_reference(None, selected_pkg)
+ else:
+ logger.info(configmgr.message['package_not_exist'] % pkg_name)
+ return list(install_rpm)