<s> """<STR_LIT>""" <EOL> import heapq <EOL> from cvs2svn_lib . log import logger <EOL> from cvs2svn_lib . changeset import RevisionChangeset <EOL> from cvs2svn_lib . changeset import OrderedChangeset <EOL> from cvs2svn_lib . changeset import BranchChangeset <EOL> from cvs2svn_lib . changeset import TagChangeset <EOL> class CycleInGraphException ( Exception ) : <EOL> def __init__ ( self , cycle ) : <EOL> Exception . __init__ ( <EOL> self , <EOL> '<STR_LIT>' <EOL> % '<STR_LIT>' . join ( map ( str , cycle + [ cycle [ <NUM_LIT:0> ] ] ) ) ) <EOL> class NoPredNodeInGraphException ( Exception ) : <EOL> def __init__ ( self , node ) : <EOL> Exception . __init__ ( self , '<STR_LIT>' % ( node , ) ) <EOL> class _NoPredNodes ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , changeset_db , initial_nodes ) : <EOL> """<STR_LIT>""" <EOL> self . changeset_db = changeset_db <EOL> self . _nodes = [ <EOL> ( node . time_range , self . changeset_db [ node . id ] , node ) <EOL> for node in initial_nodes <EOL> ] <EOL> heapq . heapify ( self . _nodes ) <EOL> def __len__ ( self ) : <EOL> return len ( self . _nodes ) <EOL> def add ( self , node ) : <EOL> node = ( node . time_range , self . changeset_db [ node . id ] , node ) <EOL> heapq . heappush ( self . _nodes , node ) <EOL> def get ( self ) : <EOL> """<STR_LIT>""" <EOL> ( time_range , changeset , node ) = heapq . heappop ( self . _nodes ) <EOL> return ( node , changeset ) <EOL> class ChangesetGraph ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , changeset_db , cvs_item_to_changeset_id ) : <EOL> self . _changeset_db = changeset_db <EOL> self . _cvs_item_to_changeset_id = cvs_item_to_changeset_id <EOL> self . nodes = { } <EOL> def close ( self ) : <EOL> self . _cvs_item_to_changeset_id . close ( ) <EOL> self . _cvs_item_to_changeset_id = None <EOL> self . _changeset_db . close ( ) <EOL> self . _changeset_db = None <EOL> def add_changeset ( self , changeset ) : <EOL> """<STR_LIT>""" <EOL> node = changeset . create_graph_node ( self . _cvs_item_to_changeset_id ) <EOL> for pred_id in list ( node . pred_ids ) : <EOL> pred_node = self . nodes . get ( pred_id ) <EOL> if pred_node is not None : <EOL> pred_node . succ_ids . add ( node . id ) <EOL> else : <EOL> node . pred_ids . remove ( pred_id ) <EOL> for succ_id in list ( node . succ_ids ) : <EOL> succ_node = self . nodes . get ( succ_id ) <EOL> if succ_node is not None : <EOL> succ_node . pred_ids . add ( node . id ) <EOL> else : <EOL> node . succ_ids . remove ( succ_id ) <EOL> self . nodes [ node . id ] = node <EOL> def store_changeset ( self , changeset ) : <EOL> for cvs_item_id in changeset . cvs_item_ids : <EOL> self . _cvs_item_to_changeset_id [ cvs_item_id ] = changeset . id <EOL> self . _changeset_db . store ( changeset ) <EOL> def add_new_changeset ( self , changeset ) : <EOL> """<STR_LIT>""" <EOL> if logger . is_on ( logger . DEBUG ) : <EOL> logger . debug ( '<STR_LIT>' % ( changeset , ) ) <EOL> self . add_changeset ( changeset ) <EOL> self . store_changeset ( changeset ) <EOL> def delete_changeset ( self , changeset ) : <EOL> """<STR_LIT>""" <EOL> if logger . is_on ( logger . DEBUG ) : <EOL> logger . debug ( '<STR_LIT>' % ( changeset , ) ) <EOL> del self [ changeset . id ] <EOL> del self . _changeset_db [ changeset . id ] <EOL> def __nonzero__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return bool ( self . nodes ) <EOL> def __contains__ ( self , id ) : <EOL> """<STR_LIT>""" <EOL> return id in self . nodes <EOL> def __getitem__ ( self , id ) : <EOL> return self . nodes [ id ] <EOL> def get ( self , id ) : <EOL> return self . nodes . get ( id ) <EOL> def __delitem__ ( self , id ) : <EOL> """<STR_LIT>""" <EOL> node = self [ id ] <EOL> for succ_id in node . succ_ids : <EOL> succ = self [ succ_id ] <EOL> succ . pred_ids . remove ( node . id ) <EOL> for pred_id in node . pred_ids : <EOL> pred = self [ pred_id ] <EOL> pred . succ_ids . remove ( node . id ) <EOL> del self . nodes [ node . id ] <EOL> def keys ( self ) : <EOL> return self . nodes . keys ( ) <EOL> def __iter__ ( self ) : <EOL> return self . nodes . itervalues ( ) <EOL> def _get_path ( self , reachable_changesets , starting_node_id , ending_node_id ) : <EOL> """<STR_LIT>""" <EOL> if ending_node_id not in reachable_changesets : <EOL> return None <EOL> path = [ self . _changeset_db [ ending_node_id ] ] <EOL> id = reachable_changesets [ ending_node_id ] [ <NUM_LIT:1> ] <EOL> while id != starting_node_id : <EOL> path . append ( self . _changeset_db [ id ] ) <EOL> id = reachable_changesets [ id ] [ <NUM_LIT:1> ] <EOL> path . append ( self . _changeset_db [ starting_node_id ] ) <EOL> return path <EOL> def search_for_path ( self , starting_node_id , stop_set ) : <EOL> """<STR_LIT>""" <EOL> reachable_changesets = { } <EOL> open_nodes = [ ( starting_node_id , <NUM_LIT:0> ) ] <EOL> while open_nodes : <EOL> ( id , steps ) = open_nodes . pop ( <NUM_LIT:0> ) <EOL> steps += <NUM_LIT:1> <EOL> node = self [ id ] <EOL> for pred_id in node . pred_ids : <EOL> if pred_id not in reachable_changesets : <EOL> reachable_changesets [ pred_id ] = ( steps , id ) <EOL> open_nodes . append ( ( pred_id , steps ) ) <EOL> if pred_id in stop_set : <EOL> return self . _get_path ( <EOL> reachable_changesets , starting_node_id , pred_id <EOL> ) <EOL> return None <EOL> def consume_nopred_nodes ( self ) : <EOL> """<STR_LIT>""" <EOL> nopred_nodes = _NoPredNodes ( <EOL> self . _changeset_db , <EOL> ( <EOL> node <EOL> for node in self . nodes . itervalues ( ) <EOL> if not node . pred_ids <EOL> ) , <EOL> ) <EOL> while nopred_nodes : <EOL> ( node , changeset , ) = nopred_nodes . get ( ) <EOL> del self [ node . id ] <EOL> for succ_id in node . succ_ids : <EOL> succ = self [ succ_id ] <EOL> if not succ . pred_ids : <EOL> nopred_nodes . add ( succ ) <EOL> yield ( changeset , node . time_range ) <EOL> def find_cycle ( self , starting_node_id ) : <EOL> """<STR_LIT>""" <EOL> node = self [ starting_node_id ] <EOL> seen_nodes = [ node ] <EOL> while True : <EOL> try : <EOL> node_id = node . pred_ids . __iter__ ( ) . next ( ) <EOL> except StopIteration : <EOL> raise NoPredNodeInGraphException ( node ) <EOL> node = self [ node_id ] <EOL> try : <EOL> i = seen_nodes . index ( node ) <EOL> except ValueError : <EOL> seen_nodes . append ( node ) <EOL> else : <EOL> seen_nodes = seen_nodes [ i : ] <EOL> seen_nodes . reverse ( ) <EOL> return [ self . _changeset_db [ node . id ] for node in seen_nodes ] <EOL> def consume_graph ( self , cycle_breaker = None ) : <EOL> """<STR_LIT>""" <EOL> while True : <EOL> for ( changeset , time_range ) in self . consume_nopred_nodes ( ) : <EOL> yield ( changeset , time_range ) <EOL> start_node_id = self . nodes . iterkeys ( ) . next ( ) <EOL> cycle = self . find_cycle ( start_node_id ) <EOL> if cycle_breaker is not None : <EOL> cycle_breaker ( cycle ) <EOL> else : <EOL> raise CycleInGraphException ( cycle ) <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . nodes : <EOL> return '<STR_LIT>' % '<STR_LIT>' . join ( [ '<STR_LIT>' % node for node in self ] ) <EOL> else : <EOL> return '<STR_LIT>' <EOL> node_colors = { <EOL> RevisionChangeset : '<STR_LIT>' , <EOL> OrderedChangeset : '<STR_LIT>' , <EOL> BranchChangeset : '<STR_LIT>' , <EOL> TagChangeset : '<STR_LIT>' , <EOL> } <EOL> def output_coarse_dot ( self , f ) : <EOL> """<STR_LIT>""" <EOL> f . write ( '<STR_LIT>' ) <EOL> for node in self : <EOL> f . write ( <EOL> '<STR_LIT>' % ( <EOL> node . id , <EOL> self . node_colors [ self . _changeset_db [ node . id ] . __class__ ] , <EOL> ) <EOL> ) <EOL> f . write ( '<STR_LIT:\n>' ) <EOL> for node in self : <EOL> for succ_id in node . succ_ids : <EOL> f . write ( '<STR_LIT>' % ( node . id , succ_id , ) ) <EOL> f . write ( '<STR_LIT:\n>' ) <EOL> f . write ( '<STR_LIT>' ) <EOL> def output_fine_dot ( self , f ) : <EOL> """<STR_LIT>""" <EOL> f . write ( '<STR_LIT>' ) <EOL> for node in self : <EOL> f . write ( '<STR_LIT>' % ( node . id , ) ) <EOL> f . write ( '<STR_LIT>' % ( node . id , ) ) <EOL> changeset = self . _changeset_db [ node . id ] <EOL> for item_id in changeset . cvs_item_ids : <EOL> f . write ( '<STR_LIT>' % ( item_id , ) ) <EOL> f . write ( '<STR_LIT>' ) <EOL> f . write ( <EOL> '<STR_LIT>' <EOL> % ( self . node_colors [ self . _changeset_db [ node . id ] . __class__ ] , ) ) <EOL> f . write ( '<STR_LIT>' ) <EOL> for node in self : <EOL> changeset = self . _changeset_db [ node . id ] <EOL> for cvs_item in changeset . iter_cvs_items ( ) : <EOL> for succ_id in cvs_item . get_succ_ids ( ) : <EOL> f . write ( '<STR_LIT>' % ( cvs_item . id , succ_id , ) ) <EOL> f . write ( '<STR_LIT:\n>' ) <EOL> f . write ( '<STR_LIT>' ) </s>
