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
  24 def analyze_dependency(pkg_group):
  25
  26     def dep_dfs(pkg_id):
  27         logger = logging.getLogger(__name__)
  28         if pkg_list[pkg_id].get('dependency') is not None:
  29             return pkg_list[pkg_id].get('dependency')
  30
  31         number[0] += 1
  32         visited[pkg_id] = number[0]
  33         min_num[pkg_id] = number[0]
  34         stack.append(pkg_id)
  35
  36         dep_set = set([pkg_list[pkg_id]['name']])
  37
  38         if pkg_list[pkg_id].get('requires'):
  39             for req in pkg_list[pkg_id].get('requires'):
  40                 req_id = req.get('id')
  41                 if req_id is not None:
  42                     if scc_list[req_id] > 0:
  43                         dep_set.update(pkg_list[req_id].get('dependency'))
  44                         continue
  45
  46                     if visited[req_id] == 0:
  47                         dep_set.update(dep_dfs(req_id))
  48
  49                     min_num[pkg_id] = min(min_num[pkg_id], min_num[req_id])
  50                 else:
  51                     #TODO: package does not exist
  52                     #logger.warning('%s does not exist in repo', req['name'])
  53                     pass
  54
  55         if min_num[pkg_id] == visited[pkg_id]:
  56             # scc (string connected components)
  57             make_scc(pkg_id, list(dep_set))
  58
  59         return dep_set
  60
  61     def make_scc(pkg_id, dep_list):
  62         p_id = 0
  63         scc_num[0] += 1
  64         # stack is not empty
  65         while stack:
  66             p_id = stack.pop()
  67             scc_list[p_id] = scc_num[0]
  68             pkg_list[p_id]['dependency'] = dep_list
  69             if pkg_id == p_id:
  70                 break
  71
  72     def analyze():
  73         for pkg_id in range(len(pkg_list)):
  74             if visited[pkg_id] == 0:
  75                 dep_dfs(pkg_id)
  76
  77     #TODO: Exception handling
  78     if not pkg_group:
  79         return None
  80
  81     # package install-dependency analysis
  82     pkg_list = pkg_group.get('pkg_list')
  83     number = [0]
  84     scc_num = [0]
  85     visited = [0]*len(pkg_list)
  86     min_num = [0]*len(pkg_list)
  87     scc_list = [0]*len(pkg_list)
  88     stack = []
  89
  90     return analyze()
  91
  92