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.
23 from lxml import etree
24 from tic.utils.error import TICError
25 from tic.utils.rpmmisc import meetRequireVersion, compare_ver
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 _select_rpm(capability, require):
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)
110 provide_list = capability
112 # error case (the rpm does not exist)
116 if len(provide_list) == 1:
117 return pkg_dict.get(provide_list[0].get('name'))
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:
126 # 2-2. Select the latest version of rpm
128 for i in range(0, len(provide_list)):
129 if not _check_conflicts(pkg_dict.get(provide_list[i]['name'])):
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
135 max_ver = provide_list[i]
137 max_ver = provide_list[i]
139 # all of capability pkg are in conflict
141 return pkg_dict.get(provide_list[i]['name'])
143 return pkg_dict.get(max_ver.get('name'))
145 def _create_reference(pkg1, pkg2):
147 if pkg1.get('forward') and pkg2['name'] in pkg1.get('forward'):
150 if pkg1.get('forward'):
151 pkg1['forward'].append(pkg2['name'])
153 pkg1['forward'] = [pkg2['name']]
155 if pkg2.get('backward'):
156 pkg2['backward'].append(pkg1['name'])
158 pkg2['backward'] = [pkg1['name']]
160 def _make_scc(pkg_id):
166 scc_id[pkg['id']] = scc_num[0]
168 if pkg_id == pkg['id']:
171 # circular dependency
172 if len(scc_list) > 1:
177 pkg['group'] = group_num[0]
178 group_names.append(pkg['name'])
180 # { group_id = [ pkg_name_1, pkg_name_2 ], ... }
181 groups[group_num[0]] = group_names
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):
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']):
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']):
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']))
217 def _analyze_dep(pkg_info):
221 pkg_id = pkg_info['id']
223 selected[pkg_id] = number[0]
224 min_num[pkg_id] = number[0]
225 stack.append(pkg_info)
227 dep_rpms = set([pkg_info['name']])
229 # check for conflicts
230 if _check_conflicts(pkg_info):
231 progress['status'] = False
235 # add rpms into conflicts table.
236 _add_conflicts(pkg_info)
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):
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'])
254 if selected[choose['id']] == 0:
255 dep_set = _analyze_dep(choose)
256 if not progress['status']:
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']])
265 # add forward/backward reference
266 _create_reference(pkg_info, choose)
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
273 if not progress['status']:
275 if min_num[pkg_id] == selected[pkg_id]:
276 # scc(strong connected components)
281 def _check_circular_dep(node):
282 g_id = node.get('group')
283 g_pkg_list = groups[g_id]
287 for pkgname in g_pkg_list:
288 g_dict[pkgname] = None
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']:
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:
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
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']:
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]
329 # selfCheck node do not remove
330 if pkg_info.get('selfChecked'):
333 if node.get('backward'):
334 if node.get('group') is None or _check_circular_dep(node):
337 # the selected node is uncheckable
338 if node.get('group') and group_visited[node['group']]:
339 group_visited[node['group']][node['name']] = 1
341 # if selected node has forward references
342 if node.get('forward'):
343 for fname in node.get('forward'):
344 fnode = pkg_dict[fname]
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:
351 _remove_reference(node, fnode)
352 node['forward'] = None
354 # delete conflict data from conflicts dict
355 _delete_conflictdata(node)
358 if not recipe or not repoinfo:
361 default = recipe.get('Default')
362 config = recipe.get('Configurations')[0]
363 platform_name = config.get('Platform')
364 platform = recipe.get(platform_name)
366 # check groups/extraPackages
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)
378 for repo in repoinfo:
379 if repo.get('comps'):
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)
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')
392 for pkgreq in pkglist.findall('packagereq'):
393 plist.append(pkgreq.text)
394 pkg_set.update(set(plist))
395 group_set.discard(group_name);
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')
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)
411 install_rpm = set([])
412 progress = dict(status=True, message=None)
414 for pkg_name in pkg_set:
415 progress['status'] = True
416 pkg_info = pkg_dict.get(pkg_name)
419 if provides.get(pkg_name):
420 pro = provides.get(pkg_name)[0]
421 pkg_info = pkg_dict.get(pro['name'])
423 logger.info('the default package(%s) does not exist.' % pkg_name)
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)
432 # delete forward/backward reference
434 _remove_reference(None, pkg_info)
435 return list(install_rpm)