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