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