Package pyplusplus :: Package module_creator :: Module sort_algorithms

Source Code for Module pyplusplus.module_creator.sort_algorithms

  1  # Copyright 2004-2008 Roman Yakovenko. 
  2  # Distributed under the Boost Software License, Version 1.0. (See 
  3  # accompanying file LICENSE_1_0.txt or copy at 
  4  # http://www.boost.org/LICENSE_1_0.txt) 
  5   
  6  from pygccxml import declarations 
  7  from pyplusplus import decl_wrappers 
  8   
9 -class COLOR:
10 WHITE = 0 11 GRAY = 1 12 BLACK = 2
13
14 -class class_organizer_t(object):
15 - def __init__( self, decls ):
16 object.__init__( self ) 17 18 self.__classes = filter( lambda x: isinstance( x, declarations.class_t ) 19 , decls ) 20 self.__classes.sort( lambda cls1, cls2: cmp( cls1.decl_string, cls2.decl_string ) ) 21 self.__dependencies_graph = self._build_graph() 22 self.__time = 0 23 self.__colors = dict( zip( self.__dependencies_graph.keys() 24 , [ COLOR.WHITE ] * len( self.__dependencies_graph ) ) ) 25 self.__class_discovered = dict( zip( self.__dependencies_graph.keys() 26 , [ 0 ] * len( self.__dependencies_graph ) ) ) 27 self.__class_treated = dict( zip( self.__dependencies_graph.keys() 28 , [ 0 ] * len( self.__dependencies_graph ) ) ) 29 30 self.__desired_order = [] 31 32 self._topological_sort()
33
34 - def _build_graph(self):
35 full_name = declarations.full_name 36 graph = {} # 37 for class_ in self.__classes: 38 assert isinstance( class_, declarations.class_t ) 39 fname = full_name( class_ ) 40 graph[ fname ] = self.__find_out_class_dependencies( class_ ) 41 return graph
42
43 - def __find_out_class_dependencies( self, class_ ):
44 full_name = declarations.full_name 45 #class depends on it's base classes 46 i_depend_on_them = set( [ full_name( base.related_class ) for base in class_.bases ] ) 47 #class depends on all classes that used in function as argument 48 # types and those arguments have default value 49 calldefs = filter( lambda decl: isinstance( decl, declarations.calldef_t ) 50 , declarations.make_flatten( class_ )) 51 for calldef in calldefs: 52 for arg in calldef.arguments: 53 if declarations.is_enum( arg.type ): 54 top_class_inst = self.__get_top_class_inst( declarations.enum_declaration( arg.type ) ) 55 if top_class_inst: 56 i_depend_on_them.add( full_name( top_class_inst ) ) 57 continue 58 if not arg.default_value: 59 continue 60 if declarations.is_pointer( arg.type ) and arg.default_value == 0: 61 continue 62 base_type = declarations.base_type( arg.type ) 63 if not isinstance( base_type, declarations.declarated_t ): 64 continue 65 top_class_inst = self.__get_top_class_inst( base_type.declaration ) 66 if top_class_inst: 67 i_depend_on_them.add( full_name( top_class_inst ) ) 68 69 for internal_cls in class_.classes(allow_empty=True): 70 internal_cls_dependencies = self.__find_out_class_dependencies( internal_cls ) 71 i_depend_on_them.update( internal_cls_dependencies ) 72 73 i_depend_on_them = list( i_depend_on_them ) 74 i_depend_on_them.sort() 75 return i_depend_on_them
76
77 - def __get_top_class_inst( self, decl ):
78 curr = decl 79 while isinstance( curr.parent, declarations.class_t ): 80 curr = curr.parent 81 if isinstance( curr, declarations.class_t ): 82 return curr
83
84 - def _topological_sort(self):
85 self._dfs()
86
87 - def _dfs( self ):
88 for class_ in sorted( self.__dependencies_graph.keys() ): 89 if self.__colors[class_] == COLOR.WHITE: 90 self._dfs_visit(class_)
91
92 - def _dfs_visit(self, base):
93 self.__colors[base] = COLOR.GRAY 94 self.__time += 1 95 self.__class_discovered[base] = self.__time 96 for derived in self.__dependencies_graph[base]: 97 if self.__colors.has_key( derived ) and self.__colors[derived] == COLOR.WHITE: 98 self._dfs_visit( derived ) 99 else: 100 pass 101 #there is usecase where base class defined within some class 102 #but his derives defined out of the class. right now Py++ 103 #doesn't supports this situation. 104 105 self.__colors[base] = COLOR.BLACK 106 self.__time += 1 107 self.__class_treated = self.__time 108 self.__desired_order.append(base)
109
110 - def desired_order(self):
111 full_name = declarations.full_name 112 fname2inst = {} 113 for class_inst in self.__classes: 114 fname2inst[ full_name( class_inst ) ] = class_inst 115 answer = [] 116 for fname in self.__desired_order: 117 answer.append( fname2inst[fname] ) 118 return answer
119
120 -class calldef_organizer_t( object ):
121 #Take a look on this post: 122 # http://mail.python.org/pipermail/c++-sig/2006-October/011463.html 123 124 #calldef_organizer_t will take into account only requiered arguments. 125 #Next rules are implemented: 126 #1. calldef( bool ) will be the last registered function 127 #2. T* will come after T ( const T& )
128 - def __init__( self ):
129 object.__init__( self ) 130 #preserve order in which functions where defined 131 self.__cmp_unrelated = lambda d1, d2: cmp( d1.location.line, d2.location.line )
132
133 - def __build_groups( self, decls ):
134 groups = { None: [] } 135 for d in decls: 136 if not isinstance( d, declarations.calldef_t ) or 1 != len( d.required_args ): 137 groups[ None ].append( d ) 138 else: 139 if not groups.has_key( d.name ): 140 groups[ d.name ] = [] 141 groups[ d.name ].append( d ) 142 return groups
143
144 - def __cmp_types( self, t1, t2 ):
145 return decl_wrappers.algorithm.registration_order.is_related( t1, t2 )
146
147 - def __cmp( self, f1, f2 ):
148 result = self.__cmp_types( f1.arguments[0].type, f2.arguments[0].type ) 149 if None is result: 150 result = self.__cmp_unrelated( f1, f2 ) 151 return result
152
153 - def __sort_groups( self, groups ):
154 for group in groups.keys(): 155 if None is group: 156 continue 157 groups[ group ].sort( self.__cmp )
158
159 - def __join_groups( self, groups ):
160 decls = [] 161 sorted_keys = groups.keys() 162 sorted_keys.sort() 163 for group in sorted_keys: 164 decls.extend( groups[group] ) 165 return decls
166
167 - def sort( self, decls ):
168 groups = self.__build_groups( decls ) 169 self.__sort_groups(groups) 170 result = self.__join_groups(groups) 171 return result
172
173 -def sort_classes( classes ):
174 organizer = class_organizer_t( classes ) 175 return organizer.desired_order()
176
177 -def sort_calldefs( decls ):
178 return calldef_organizer_t().sort( decls )
179 180 USE_CALLDEF_ORGANIZER = False 181 #If you understand what problem calldef_organizer_t solves, than may be you should 182 #use this. 183
184 -def sort( decls ):
185 classes = filter( lambda x: isinstance( x, declarations.class_t ), decls ) 186 ordered = sort_classes( classes ) 187 188 ids = set( [ id( inst ) for inst in ordered ] ) 189 for decl in decls: 190 if id( decl ) not in ids: 191 ids.add( id(decl) ) 192 ordered.append( decl ) 193 #type should be exported before it can be used. 194 variables = [] 195 enums = [] 196 others = [] 197 classes = [] 198 constructors = [] 199 for inst in ordered: 200 if isinstance( inst, declarations.variable_t ): 201 variables.append( inst ) 202 elif isinstance( inst, declarations.enumeration_t ): 203 enums.append( inst ) 204 elif isinstance( inst, ( declarations.class_t, declarations.class_declaration_t ) ): 205 classes.append( inst ) 206 elif isinstance( inst, declarations.constructor_t ): 207 constructors.append( inst ) 208 else: 209 others.append( inst ) 210 #this will prevent from py++ to change the order of generated code 211 cmp_by_name = lambda d1, d2: cmp( d1.name, d2.name ) 212 cmp_by_line = lambda d1, d2: cmp( d1.location.line, d2.location.line ) 213 214 enums.sort( cmp=cmp_by_name ) 215 variables.sort( cmp=cmp_by_name ) 216 if USE_CALLDEF_ORGANIZER: 217 others = sort_calldefs(others) 218 constructors = sort_calldefs(constructors) 219 else: 220 others.sort( cmp=cmp_by_name ) 221 constructors.sort( cmp=cmp_by_line ) 222 223 new_ordered = [] 224 new_ordered.extend( enums ) 225 new_ordered.extend( classes ) 226 new_ordered.extend( constructors ) 227 new_ordered.extend( others ) 228 new_ordered.extend( variables ) 229 return new_ordered #
230