2 # Copyright (c) 2000 - 2016 Samsung Electronics Co., Ltd. All rights reserved.
5 # @author Chulwoo Shin <cw1.shin@samsung.com>
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
11 # http://www.apache.org/licenses/LICENSE-2.0
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.
24 from lxml import etree
25 from tic.utils.error import TICError
27 def analyze_dependency(pkg_group):
30 logger = logging.getLogger(__name__)
31 if pkg_list[pkg_id].get('dependency') is not None:
32 return pkg_list[pkg_id].get('dependency')
35 visited[pkg_id] = number[0]
36 min_num[pkg_id] = number[0]
39 dep_set = set([pkg_list[pkg_id]['name']])
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'))
49 if visited[req_id] == 0:
50 dep_set.update(dep_dfs(req_id))
52 min_num[pkg_id] = min(min_num[pkg_id], min_num[req_id])
54 #TODO: package does not exist
55 #logger.warning('%s does not exist in repo', req['name'])
58 if min_num[pkg_id] == visited[pkg_id]:
59 # scc (string connected components)
60 make_scc(pkg_id, list(dep_set))
64 def make_scc(pkg_id, dep_list):
70 scc_list[p_id] = scc_num[0]
71 pkg_list[p_id]['dependency'] = dep_list
76 for pkg_id in range(len(pkg_list)):
77 if visited[pkg_id] == 0:
80 #TODO: Exception handling
84 # package install-dependency analysis
85 pkg_list = pkg_group.get('pkg_list')
88 visited = [0]*len(pkg_list)
89 min_num = [0]*len(pkg_list)
90 scc_list = [0]*len(pkg_list)
95 def get_installed_packages(recipe, repoinfo, pkg_group):
96 logger = logging.getLogger(__name__)
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')))
102 def _compare_req_cap_ver(req, cap):
103 epoch = cap.get('epoch')
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))
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'):
114 elif cmp_ret == 1 and (req_ver['flags'] == 'LT' or req_ver['flags'] == 'LE'):
116 elif cmp_ret == -1 and (req_ver['flags'] == 'GT' or req_ver['flags'] == 'GE'):
120 def _select_rpm(capability, require):
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)
131 provide_list = capability
133 # error case (the rpm does not exist)
137 if len(provide_list) == 1:
138 return pkg_dict.get(provide_list[0].get('name'))
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:
147 # 2-2. Select the latest version of rpm
149 for i in range(0, len(provide_list)):
150 if not _check_conflicts(pkg_dict.get(provide_list[i]['name'])):
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
156 max_ver = provide_list[i]
158 max_ver = provide_list[i]
160 # all of capability pkg are in conflict
162 return pkg_dict.get(provide_list[i]['name'])
164 return pkg_dict.get(max_ver.get('name'))
166 def _create_reference(pkg1, pkg2):
168 if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
171 if pkg1.get('forward'):
172 pkg1['forward'].append(pkg2['name'])
174 pkg1['forward'] = [pkg2['name']]
176 if pkg2.get('backward'):
177 pkg2['backward'].append(pkg1['name'])
179 pkg2['backward'] = [pkg1['name']]
181 def _make_scc(pkg_id):
187 scc_id[pkg['id']] = scc_num[0]
189 if pkg_id == pkg['id']:
192 # circular dependency
193 if len(scc_list) > 1:
198 pkg['group'] = group_num[0]
199 group_names.append(pkg['name'])
201 # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
202 groups[group_num[0]] = group_names
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):
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']):
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']):
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']))
238 def _analyze_dep(pkg_info):
242 pkg_id = pkg_info['id']
244 selected[pkg_id] = number[0]
245 min_num[pkg_id] = number[0]
246 stack.append(pkg_info)
248 dep_rpms = set([pkg_info['name']])
250 # check for conflicts
251 if _check_conflicts(pkg_info):
252 progress['status'] = False
256 # add rpms into conflicts table.
257 _add_conflicts(pkg_info)
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):
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'])
275 if selected[choose['id']] == 0:
276 dep_set = _analyze_dep(choose)
277 if not progress['status']:
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']])
286 # add forward/backward reference
287 _create_reference(pkg_info, choose)
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
294 if not progress['status']:
296 if min_num[pkg_id] == selected[pkg_id]:
297 # scc(strong connected components)
302 def _check_circular_dep(node):
303 g_id = node.get('group')
304 g_pkg_list = groups[g_id]
308 for pkgname in g_pkg_list:
309 g_dict[pkgname] = None
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']:
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:
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
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']:
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]
350 # selfCheck node do not remove
351 if pkg_info.get('selfChecked'):
354 if node.get('backward'):
355 if node.get('group') is None or _check_circular_dep(node):
358 # the selected node is uncheckable
359 if node.get('group') and group_visited[node['group']]:
360 group_visited[node['group']][node['name']] = 1
362 # if selected node has forward references
363 if node.get('forward'):
364 for fname in node.get('forward'):
365 fnode = pkg_dict[fname]
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:
372 _remove_reference(node, fnode)
373 node['forward'] = None
375 # delete conflict data from conflicts dict
376 _delete_conflictdata(node)
379 if not recipe or not repoinfo:
382 default = recipe.get('Default')
383 config = recipe.get('Configurations')[0]
384 platform_name = config.get('Platform')
385 platform = recipe.get(platform_name)
387 # check groups/extraPackages
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)
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)
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')
410 for pkgreq in pkglist.findall('packagereq'):
411 plist.append(pkgreq.text)
412 pkg_set.update(set(plist))
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')
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)
428 install_rpm = set([])
429 progress = dict(status=True, message=None)
431 for pkg_name in pkg_set:
432 progress['status'] = True
433 pkg_info = pkg_dict.get(pkg_name)
435 # TODO: temporary code (Define capability in group)
437 pro = provides.get(pkg_name)[0]
438 pkg_info = pkg_dict.get(pro['name'])
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)
446 # delete forward/backward reference
448 _remove_reference(None, pkg_info)
449 return list(install_rpm)