Artifact 7d4b849665b953e0c3928b79ade67c18d257c0fd:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[7f15be9078]
- Added the ability to export the changeset graphs processed by the passes 6 to 8 using GraphViz's dot-format. This is activated by using the switch '--dots'. Bugfixes in the cycle breaker. First corrected variable names, I forgot to use the standard 'myXXX' format for the typevariables. Second, fixed a bug uncovered by looking at the exported graphs, which caused the system to loose arcs, possibly breaking cycles without actually breaking them, leaving them in the dependencies.
by
aku on
2007-11-20 06:59:03.
0000: 23 23 20 2d 2a 2d 20 74 63 6c 20 2d 2a 2d 0a 23 ## -*- tcl -*-.#
0010: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
0020: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
0030: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
0040: 23 23 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 ############.##
0050: 43 6f 70 79 72 69 67 68 74 20 28 63 29 20 32 30 Copyright (c) 20
0060: 30 37 20 41 6e 64 72 65 61 73 20 4b 75 70 72 69 07 Andreas Kupri
0070: 65 73 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 es..#.# This sof
0080: 74 77 61 72 65 20 69 73 20 6c 69 63 65 6e 73 65 tware is license
0090: 64 20 61 73 20 64 65 73 63 72 69 62 65 64 20 69 d as described i
00a0: 6e 20 74 68 65 20 66 69 6c 65 20 4c 49 43 45 4e n the file LICEN
00b0: 53 45 2c 20 77 68 69 63 68 0a 23 20 79 6f 75 20 SE, which.# you
00c0: 73 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 should have rece
00d0: 69 76 65 64 20 61 73 20 70 61 72 74 20 6f 66 20 ived as part of
00e0: 74 68 69 73 20 64 69 73 74 72 69 62 75 74 69 6f this distributio
00f0: 6e 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 74 n..#.# This soft
0100: 77 61 72 65 20 63 6f 6e 73 69 73 74 73 20 6f 66 ware consists of
0110: 20 76 6f 6c 75 6e 74 61 72 79 20 63 6f 6e 74 72 voluntary contr
0120: 69 62 75 74 69 6f 6e 73 20 6d 61 64 65 20 62 79 ibutions made by
0130: 20 6d 61 6e 79 0a 23 20 69 6e 64 69 76 69 64 75 many.# individu
0140: 61 6c 73 2e 20 20 46 6f 72 20 65 78 61 63 74 20 als. For exact
0150: 63 6f 6e 74 72 69 62 75 74 69 6f 6e 20 68 69 73 contribution his
0160: 74 6f 72 79 2c 20 73 65 65 20 74 68 65 20 72 65 tory, see the re
0170: 76 69 73 69 6f 6e 0a 23 20 68 69 73 74 6f 72 79 vision.# history
0180: 20 61 6e 64 20 6c 6f 67 73 2c 20 61 76 61 69 6c and logs, avail
0190: 61 62 6c 65 20 61 74 20 68 74 74 70 3a 2f 2f 66 able at http://f
01a0: 6f 73 73 69 6c 2d 73 63 6d 2e 68 77 61 63 69 2e ossil-scm.hwaci.
01b0: 63 6f 6d 2f 66 6f 73 73 69 6c 0a 23 20 23 20 23 com/fossil.# # #
01c0: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
01d0: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
01e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
01f0: 23 23 23 23 23 23 23 23 0a 0a 23 23 20 54 68 69 ########..## Thi
0200: 73 20 66 69 6c 65 20 70 72 6f 76 69 64 65 73 20 s file provides
0210: 61 20 68 65 6c 70 65 72 20 70 61 63 6b 61 67 65 a helper package
0220: 20 66 6f 72 20 74 68 65 20 70 61 73 73 65 73 20 for the passes
0230: 36 20 61 6e 64 20 37 20 77 68 69 63 68 0a 23 23 6 and 7 which.##
0240: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 6f contains the co
0250: 6d 6d 6f 6e 20 63 6f 64 65 20 6f 66 20 74 68 65 mmon code of the
0260: 20 63 79 63 6c 65 20 62 72 65 61 6b 69 6e 67 20 cycle breaking
0270: 61 6c 67 6f 72 69 74 68 6d 2e 0a 0a 23 20 23 20 algorithm...# #
0280: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
0290: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
02a0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
02b0: 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 71 #########.## Req
02c0: 75 69 72 65 6d 65 6e 74 73 0a 0a 70 61 63 6b 61 uirements..packa
02d0: 67 65 20 72 65 71 75 69 72 65 20 54 63 6c 20 38 ge require Tcl 8
02e0: 2e 34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .4
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0300: 20 20 20 20 20 3b 20 23 20 52 65 71 75 69 72 65 ; # Require
0310: 64 20 72 75 6e 74 69 6d 65 2e 0a 70 61 63 6b 61 d runtime..packa
0320: 67 65 20 72 65 71 75 69 72 65 20 73 6e 69 74 20 ge require snit
0330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0350: 20 20 20 20 20 3b 20 23 20 4f 4f 20 73 79 73 74 ; # OO syst
0360: 65 6d 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 em..package requ
0370: 69 72 65 20 73 74 72 75 63 74 3a 3a 67 72 61 70 ire struct::grap
0380: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 h
0390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
03a0: 23 20 47 72 61 70 68 20 68 61 6e 64 6c 69 6e 67 # Graph handling
03b0: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 ..package requir
03c0: 65 20 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 20 e struct::list
03d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
03e0: 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 23 20 ; #
03f0: 48 69 67 68 65 72 20 6f 72 64 65 72 20 6c 69 73 Higher order lis
0400: 74 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 70 61 t operations..pa
0410: 63 6b 61 67 65 20 72 65 71 75 69 72 65 20 76 63 ckage require vc
0420: 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 20 20 20 20 ::tools::dot
0430: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0440: 20 20 20 20 20 20 20 20 3b 20 23 20 55 73 65 72 ; # User
0450: 20 66 65 65 64 62 61 63 6b 2e 20 44 4f 54 20 65 feedback. DOT e
0460: 78 70 6f 72 74 2e 0a 70 61 63 6b 61 67 65 20 72 xport..package r
0470: 65 71 75 69 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 equire vc::tools
0480: 3a 3a 6c 6f 67 20 20 20 20 20 20 20 20 20 20 20 ::log
0490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
04a0: 20 3b 20 23 20 55 73 65 72 20 66 65 65 64 62 61 ; # User feedba
04b0: 63 6b 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 ck..package requ
04c0: 69 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d ire vc::tools::m
04d0: 69 73 63 20 20 20 20 20 20 20 20 20 20 20 20 20 isc
04e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
04f0: 23 20 54 65 78 74 20 66 6f 72 6d 61 74 74 69 6e # Text formattin
0500: 67 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 g..package requi
0510: 72 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 re vc::fossil::i
0520: 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a mport::cvs::proj
0530: 65 63 74 3a 3a 72 65 76 20 20 20 20 20 3b 20 23 ect::rev ; #
0540: 20 50 72 6f 6a 65 63 74 20 6c 65 76 65 6c 20 63 Project level c
0550: 68 61 6e 67 65 73 65 74 73 0a 70 61 63 6b 61 67 hangesets.packag
0560: 65 20 72 65 71 75 69 72 65 20 76 63 3a 3a 66 6f e require vc::fo
0570: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
0580: 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c s::project::revl
0590: 69 6e 6b 20 3b 20 23 20 43 79 63 6c 65 20 6c 69 ink ; # Cycle li
05a0: 6e 6b 73 2e 0a 0a 23 20 23 20 23 23 20 23 23 23 nks...# # ## ###
05b0: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
05c0: 23 23 23 23 23 23 23 23 23 23 23 23 23 20 23 23 ############# ##
05d0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
05e0: 23 23 23 0a 23 23 20 0a 0a 73 6e 69 74 3a 3a 74 ###.## ..snit::t
05f0: 79 70 65 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c ype ::vc::fossil
0600: 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 ::import::cvs::c
0610: 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 0a 20 20 yclebreaker {.
0620: 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 # # ## ### ###
0630: 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 ## ######## ####
0640: 23 23 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 #########. ##
0650: 20 50 75 62 6c 69 63 20 41 50 49 0a 0a 20 20 20 Public API..
0660: 20 74 79 70 65 6d 65 74 68 6f 64 20 64 6f 74 73 typemethod dots
0670: 74 6f 20 7b 70 61 74 68 7d 20 7b 0a 09 3a 3a 76 to {path} {..::v
0680: 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 ariable mydotdes
0690: 74 69 6e 61 74 69 6f 6e 20 24 70 61 74 68 0a 09 tination $path..
06a0: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
06b0: 20 20 74 79 70 65 6d 65 74 68 6f 64 20 64 6f 74 typemethod dot
06c0: 20 7b 6c 61 62 65 6c 20 63 68 61 6e 67 65 73 65 {label changese
06d0: 74 73 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c ts} {..::variabl
06e0: 65 20 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c e mydotprefix $l
06f0: 61 62 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 abel..::variable
0700: 20 6d 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a mydotid 0..
0710: 09 73 65 74 20 64 67 20 5b 53 65 74 75 70 20 24 .set dg [Setup $
0720: 63 68 61 6e 67 65 73 65 74 73 20 30 5d 0a 09 4d changesets 0]..M
0730: 61 72 6b 20 24 64 67 0a 09 24 64 67 20 64 65 73 ark $dg..$dg des
0740: 74 72 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 20 troy..return.
0750: 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 }.. typemeth
0760: 6f 64 20 72 75 6e 20 7b 6c 61 62 65 6c 20 63 68 od run {label ch
0770: 61 6e 67 65 73 65 74 73 20 7b 73 61 76 65 63 6d angesets {savecm
0780: 64 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 72 69 d {}}} {..::vari
0790: 61 62 6c 65 20 6d 79 73 61 76 65 20 20 20 20 20 able mysave
07a0: 20 24 73 61 76 65 63 6d 64 0a 09 3a 3a 76 61 72 $savecmd..::var
07b0: 69 61 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 iable myat
07c0: 20 20 30 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 0..::variable
07d0: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
07e0: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
07f0: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 23 ydotid 0...#
0800: 20 57 65 20 63 72 65 61 74 65 20 61 20 67 72 61 We create a gra
0810: 70 68 20 6f 66 20 74 68 65 20 72 65 76 69 73 69 ph of the revisi
0820: 6f 6e 20 63 68 61 6e 67 65 73 65 74 73 2c 20 75 on changesets, u
0830: 73 69 6e 67 20 74 68 65 20 66 69 6c 65 0a 09 23 sing the file..#
0840: 20 6c 65 76 65 6c 20 64 65 70 65 6e 64 65 6e 63 level dependenc
0850: 69 65 73 20 74 6f 20 63 6f 6e 73 74 72 75 63 74 ies to construct
0860: 20 61 20 66 69 72 73 74 20 61 70 70 72 6f 78 69 a first approxi
0870: 6d 61 74 69 6f 6e 20 6f 66 20 74 68 65 0a 09 23 mation of the..#
0880: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 74 dependencies at
0890: 20 74 68 65 20 70 72 6f 6a 65 63 74 20 6c 65 76 the project lev
08a0: 65 6c 2e 20 54 68 65 6e 20 77 65 20 6c 6f 6f 6b el. Then we look
08b0: 20 66 6f 72 20 63 79 63 6c 65 73 0a 09 23 20 69 for cycles..# i
08c0: 6e 20 74 68 61 74 20 67 72 61 70 68 20 61 6e 64 n that graph and
08d0: 20 62 72 65 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 break them....#
08e0: 20 31 2e 20 43 72 65 61 74 65 20 6e 6f 64 65 73 1. Create nodes
08f0: 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e for all relevan
0900: 74 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 t changesets and
0910: 20 61 20 6d 61 70 70 69 6e 67 0a 09 23 20 20 20 a mapping..#
0920: 20 66 72 6f 6d 20 74 68 65 20 72 65 76 69 73 69 from the revisi
0930: 6f 6e 73 20 74 6f 20 74 68 65 69 72 20 63 68 61 ons to their cha
0940: 6e 67 65 73 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a ngesets/nodes...
0950: 09 73 65 74 20 64 67 20 5b 53 65 74 75 70 20 24 .set dg [Setup $
0960: 63 68 61 6e 67 65 73 65 74 73 5d 0a 0a 09 23 20 changesets]...#
0970: 33 2e 20 4c 61 73 74 6c 79 20 77 65 20 69 74 65 3. Lastly we ite
0980: 72 61 74 65 20 74 68 65 20 67 72 61 70 68 20 74 rate the graph t
0990: 6f 70 6f 6c 6f 67 69 63 61 6c 6c 79 2e 20 57 65 opologically. We
09a0: 20 6d 61 72 6b 20 6f 66 66 0a 09 23 20 20 20 20 mark off..#
09b0: 74 68 65 20 6e 6f 64 65 73 20 77 68 69 63 68 20 the nodes which
09c0: 68 61 76 65 20 6e 6f 20 70 72 65 64 65 63 65 73 have no predeces
09d0: 73 6f 72 73 2c 20 69 6e 20 6f 72 64 65 72 20 66 sors, in order f
09e0: 72 6f 6d 0a 09 23 20 20 20 20 6f 6c 64 65 73 74 rom..# oldest
09f0: 20 74 6f 20 79 6f 75 6e 67 65 73 74 2c 20 73 61 to youngest, sa
0a00: 76 69 6e 67 20 61 6e 64 20 72 65 6d 6f 76 69 6e ving and removin
0a10: 67 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 g dependencies.
0a20: 49 66 0a 09 23 20 20 20 20 77 65 20 66 69 6e 64 If..# we find
0a30: 20 6e 6f 20 6e 6f 64 65 73 20 77 69 74 68 6f 75 no nodes withou
0a40: 74 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 77 t predecessors w
0a50: 65 20 68 61 76 65 20 61 20 63 79 63 6c 65 2c 0a e have a cycle,.
0a60: 09 23 20 20 20 20 61 6e 64 20 77 6f 72 6b 20 6f .# and work o
0a70: 6e 20 62 72 65 61 6b 69 6e 67 20 69 74 2e 0a 0a n breaking it...
0a80: 09 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 .log write 3 cyc
0a90: 6c 65 62 72 65 61 6b 65 72 20 7b 4e 6f 77 20 73 lebreaker {Now s
0aa0: 6f 72 74 69 6e 67 20 74 68 65 20 63 68 61 6e 67 orting the chang
0ab0: 65 73 65 74 73 2c 20 62 72 65 61 6b 69 6e 67 20 esets, breaking
0ac0: 63 79 63 6c 65 73 7d 0a 0a 09 49 6e 69 74 69 61 cycles}...Initia
0ad0: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 24 lizeCandidates $
0ae0: 64 67 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a dg..while {1} {.
0af0: 09 20 20 20 20 77 68 69 6c 65 20 7b 5b 57 69 74 . while {[Wit
0b00: 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 houtPredecessor
0b10: 24 64 67 20 6e 5d 7d 20 7b 0a 09 09 53 61 76 65 $dg n]} {...Save
0b20: 41 6e 64 52 65 6d 6f 76 65 20 24 64 67 20 24 6e AndRemove $dg $n
0b30: 0a 09 20 20 20 20 7d 0a 09 20 20 20 20 69 66 20 .. }.. if
0b40: 7b 21 5b 6c 6c 65 6e 67 74 68 20 5b 64 67 20 6e {![llength [dg n
0b50: 6f 64 65 73 5d 5d 7d 20 62 72 65 61 6b 0a 09 20 odes]]} break..
0b60: 20 20 20 42 72 65 61 6b 43 79 63 6c 65 20 24 64 BreakCycle $d
0b70: 67 20 5b 46 69 6e 64 43 79 63 6c 65 20 24 64 67 g [FindCycle $dg
0b80: 5d 0a 09 20 20 20 20 49 6e 69 74 69 61 6c 69 7a ].. Initializ
0b90: 65 43 61 6e 64 69 64 61 74 65 73 20 24 64 67 0a eCandidates $dg.
0ba0: 09 7d 0a 0a 09 64 67 20 64 65 73 74 72 6f 79 0a .}...dg destroy.
0bb0: 0a 09 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 ..log write 3 cy
0bc0: 63 6c 65 62 72 65 61 6b 65 72 20 44 6f 6e 65 2e clebreaker Done.
0bd0: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
0be0: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
0bf0: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
0c00: 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 20 ###########.
0c10: 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d 65 74 68 ## Internal meth
0c20: 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 20 53 65 ods.. proc Se
0c30: 74 75 70 20 7b 63 68 61 6e 67 65 73 65 74 73 20 tup {changesets
0c40: 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 66 20 7b {log 1}} {..if {
0c50: 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 $log} {.. log
0c60: 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 write 3 cyclebr
0c70: 65 61 6b 65 72 20 22 43 72 65 61 74 69 6e 67 20 eaker "Creating
0c80: 63 68 61 6e 67 65 73 65 74 20 67 72 61 70 68 2c changeset graph,
0c90: 20 66 69 6c 6c 69 6e 67 20 77 69 74 68 20 6e 6f filling with no
0ca0: 64 65 73 22 0a 09 20 20 20 20 6c 6f 67 20 77 72 des".. log wr
0cb0: 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b ite 3 cyclebreak
0cc0: 65 72 20 22 41 64 64 69 6e 67 20 5b 6e 73 70 20 er "Adding [nsp
0cd0: 5b 6c 6c 65 6e 67 74 68 20 24 63 68 61 6e 67 65 [llength $change
0ce0: 73 65 74 73 5d 20 6e 6f 64 65 5d 22 0a 09 7d 0a sets] node]"..}.
0cf0: 0a 09 73 65 74 20 64 67 20 5b 73 74 72 75 63 74 ..set dg [struct
0d00: 3a 3a 67 72 61 70 68 20 64 67 5d 0a 0a 09 66 6f ::graph dg]...fo
0d10: 72 65 61 63 68 20 63 73 65 74 20 24 63 68 61 6e reach cset $chan
0d20: 67 65 73 65 74 73 20 7b 0a 09 20 20 20 20 24 64 gesets {.. $d
0d30: 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 g node insert $c
0d40: 73 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 set.. $dg nod
0d50: 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 74 e set $cset t
0d60: 69 6d 65 72 61 6e 67 65 20 5b 24 63 73 65 74 20 imerange [$cset
0d70: 74 69 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a 09 timerange]..}...
0d80: 23 20 32 2e 20 46 69 6e 64 20 66 6f 72 20 61 6c # 2. Find for al
0d90: 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e 67 l relevant chang
0da0: 65 73 65 74 20 74 68 65 69 72 20 72 65 76 69 73 eset their revis
0db0: 69 6f 6e 73 20 61 6e 64 20 74 68 65 69 72 0a 09 ions and their..
0dc0: 23 20 20 20 20 64 65 70 65 6e 64 65 6e 63 69 65 # dependencie
0dd0: 73 2e 20 4d 61 70 20 74 68 65 20 6c 61 74 74 65 s. Map the latte
0de0: 72 20 62 61 63 6b 20 74 6f 20 63 68 61 6e 67 65 r back to change
0df0: 73 65 74 73 20 61 6e 64 0a 09 23 20 20 20 20 63 sets and..# c
0e00: 6f 6e 73 74 72 75 63 74 20 74 68 65 20 63 6f 72 onstruct the cor
0e10: 72 65 73 70 6f 6e 64 69 6e 67 20 61 72 63 73 2e responding arcs.
0e20: 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 ...if {$log} {..
0e30: 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 33 20 log write 3
0e40: 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 53 65 cyclebreaker {Se
0e50: 74 74 69 6e 67 20 75 70 20 6e 6f 64 65 20 64 65 tting up node de
0e60: 70 65 6e 64 65 6e 63 69 65 73 7d 0a 09 7d 0a 0a pendencies}..}..
0e70: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 63 .foreach cset $c
0e80: 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 20 hangesets {..
0e90: 20 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 foreach succ [$
0ea0: 63 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d cset successors]
0eb0: 20 7b 0a 09 09 23 20 43 68 61 6e 67 65 73 65 74 {...# Changeset
0ec0: 73 20 6d 61 79 20 68 61 76 65 20 64 65 70 65 6e s may have depen
0ed0: 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 20 dencies outside
0ee0: 6f 66 20 74 68 65 0a 09 09 23 20 63 68 6f 73 65 of the...# chose
0ef0: 6e 20 73 65 74 2e 20 54 68 65 73 65 20 61 72 65 n set. These are
0f00: 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b 21 ignored...if {!
0f10: 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 73 [$dg node exists
0f20: 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 $succ]} continu
0f30: 65 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 65 e...$dg arc inse
0f40: 72 74 20 24 63 73 65 74 20 24 73 75 63 63 0a 09 rt $cset $succ..
0f50: 20 20 20 20 7d 0a 09 7d 0a 0a 09 72 65 74 75 72 }..}...retur
0f60: 6e 20 24 64 67 0a 20 20 20 20 7d 0a 0a 20 20 20 n $dg. }..
0f70: 20 23 20 49 6e 73 74 65 61 64 20 6f 66 20 73 65 # Instead of se
0f80: 61 72 63 68 69 6e 67 20 74 68 65 20 77 68 6f 6c arching the whol
0f90: 65 20 67 72 61 70 68 20 66 6f 72 20 74 68 65 20 e graph for the
0fa0: 64 65 67 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 degree-0 nodes i
0fb0: 6e 0a 20 20 20 20 23 20 65 61 63 68 20 69 74 65 n. # each ite
0fc0: 72 61 74 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 ration we comput
0fd0: 65 20 74 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 e the list once
0fe0: 74 6f 20 73 74 61 72 74 2c 20 61 6e 64 20 74 68 to start, and th
0ff0: 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 en only. # up
1000: 64 61 74 65 20 69 74 20 69 6e 63 72 65 6d 65 6e date it incremen
1010: 74 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 tally based on t
1020: 68 65 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 he outgoing neig
1030: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 0a 20 20 hbours of the.
1040: 20 20 23 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 # node chosen
1050: 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 for commit...
1060: 20 70 72 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 proc Initialize
1070: 43 61 6e 64 69 64 61 74 65 73 20 7b 64 67 7d 20 Candidates {dg}
1080: 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 {..# bottom = li
1090: 73 74 20 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 st (list (node,
10a0: 72 61 6e 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 range min, range
10b0: 20 6d 61 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 max))..::variab
10c0: 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 66 6f 72 le mybottom..for
10d0: 65 61 63 68 20 6e 20 5b 24 64 67 20 6e 6f 64 65 each n [$dg node
10e0: 73 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 s] {.. if {[$
10f0: 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d dg node degree -
1100: 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 in $n]} continue
1110: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 .. lappend my
1120: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
1130: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6e [$dg node get $n
1140: 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6e timerange] 0 $n
1150: 5d 0a 09 7d 0a 09 73 65 74 20 6d 79 62 6f 74 74 ]..}..set mybott
1160: 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 om [lsort -index
1170: 20 31 20 2d 69 6e 74 65 67 65 72 20 5b 6c 73 6f 1 -integer [lso
1180: 72 74 20 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 rt -index 2 -int
1190: 65 67 65 72 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d eger $mybottom]]
11a0: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
11b0: 20 20 20 20 70 72 6f 63 20 57 69 74 68 6f 75 74 proc Without
11c0: 50 72 65 64 65 63 65 73 73 6f 72 20 7b 64 67 20 Predecessor {dg
11d0: 6e 76 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c nv} {..::variabl
11e0: 65 20 6d 79 62 6f 74 74 6f 6d 0a 0a 09 75 70 76 e mybottom...upv
11f0: 61 72 20 31 20 24 6e 76 20 6e 0a 09 69 66 20 7b ar 1 $nv n..if {
1200: 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 6f 74 ![llength $mybot
1210: 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 72 6e 20 30 tom]} { return 0
1220: 20 7d 0a 0a 09 73 65 74 20 6e 20 5b 6c 69 6e 64 }...set n [lind
1230: 65 78 20 5b 6c 69 6e 64 65 78 20 24 6d 79 62 6f ex [lindex $mybo
1240: 74 74 6f 6d 20 30 5d 20 30 5d 0a 09 73 65 74 20 ttom 0] 0]..set
1250: 6d 79 62 6f 74 74 6f 6d 20 5b 6c 72 61 6e 67 65 mybottom [lrange
1260: 20 24 6d 79 62 6f 74 74 6f 6d 20 31 20 65 6e 64 $mybottom 1 end
1270: 5d 0a 09 73 65 74 20 63 68 61 6e 67 65 64 20 30 ]..set changed 0
1280: 0a 0a 09 23 20 55 70 64 61 74 65 20 6c 69 73 74 ...# Update list
1290: 20 6f 66 20 6e 6f 64 65 73 20 77 69 74 68 6f 75 of nodes withou
12a0: 74 20 70 72 65 64 65 63 65 73 73 6f 72 2c 20 62 t predecessor, b
12b0: 61 73 65 64 20 6f 6e 20 74 68 65 0a 09 23 20 6f ased on the..# o
12c0: 75 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 utgoing neighbou
12d0: 72 73 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e rs of the chosen
12e0: 20 6e 6f 64 65 2e 20 54 68 69 73 20 73 68 6f 75 node. This shou
12f0: 6c 64 20 62 65 0a 09 23 20 66 61 73 74 65 72 20 ld be..# faster
1300: 74 68 61 6e 20 69 74 65 72 61 74 69 6e 67 20 6f than iterating o
1310: 66 20 74 68 65 20 77 68 6f 6c 65 20 73 65 74 20 f the whole set
1320: 6f 66 20 6e 6f 64 65 73 2c 20 66 69 6e 64 69 6e of nodes, findin
1330: 67 20 61 6c 6c 0a 09 23 20 77 69 74 68 6f 75 74 g all..# without
1340: 20 70 72 65 64 65 63 65 73 73 6f 72 73 2c 20 73 predecessors, s
1350: 6f 72 74 69 6e 67 20 74 68 65 6d 20 62 79 20 74 orting them by t
1360: 69 6d 65 2c 20 65 74 63 2e 20 70 70 2e 0a 09 66 ime, etc. pp...f
1370: 6f 72 65 61 63 68 20 6f 75 74 20 5b 24 64 67 20 oreach out [$dg
1380: 6e 6f 64 65 73 20 2d 6f 75 74 20 24 6e 5d 20 7b nodes -out $n] {
1390: 0a 09 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e .. if {[$dg n
13a0: 6f 64 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 ode degree -in $
13b0: 6f 75 74 5d 20 3e 20 31 7d 20 63 6f 6e 74 69 6e out] > 1} contin
13c0: 75 65 0a 09 20 20 20 20 23 20 44 65 67 72 65 65 ue.. # Degree
13d0: 2d 31 20 6e 65 69 67 68 62 6f 75 72 2c 20 77 69 -1 neighbour, wi
13e0: 6c 6c 20 68 61 76 65 20 6e 6f 20 70 72 65 64 65 ll have no prede
13f0: 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 74 68 cessors after th
1400: 65 0a 09 20 20 20 20 23 20 72 65 6d 6f 76 61 6c e.. # removal
1410: 20 6f 66 20 6e 2e 20 50 75 74 20 6f 6e 20 74 68 of n. Put on th
1420: 65 20 6c 69 73 74 2e 0a 09 20 20 20 20 6c 61 70 e list... lap
1430: 70 65 6e 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c pend mybottom [l
1440: 69 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 insert [$dg node
1450: 20 67 65 74 20 24 6f 75 74 20 74 69 6d 65 72 61 get $out timera
1460: 6e 67 65 5d 20 30 20 24 6f 75 74 5d 0a 09 20 20 nge] 0 $out]..
1470: 20 20 73 65 74 20 63 68 61 6e 67 65 64 20 31 0a set changed 1.
1480: 09 7d 0a 09 69 66 20 7b 24 63 68 61 6e 67 65 64 .}..if {$changed
1490: 7d 20 7b 0a 09 20 20 20 20 73 65 74 20 6d 79 62 } {.. set myb
14a0: 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e ottom [lsort -in
14b0: 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72 20 5b dex 1 -integer [
14c0: 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32 20 2d lsort -index 2 -
14d0: 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 74 74 6f integer $mybotto
14e0: 6d 5d 5d 0a 09 7d 0a 0a 09 23 20 57 65 20 64 6f m]]..}...# We do
14f0: 20 6e 6f 74 20 64 65 6c 65 74 65 20 74 68 65 20 not delete the
1500: 6e 6f 64 65 20 69 6d 6d 65 64 69 61 74 65 6c 79 node immediately
1510: 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 68 65 20 53 , to allow the S
1520: 61 76 65 0a 09 23 20 70 72 6f 63 65 64 75 72 65 ave..# procedure
1530: 20 74 6f 20 73 61 76 65 20 74 68 65 20 64 65 70 to save the dep
1540: 65 6e 64 65 6e 63 69 65 73 20 61 73 20 77 65 6c endencies as wel
1550: 6c 20 28 65 6e 63 6f 64 65 64 20 69 6e 20 74 68 l (encoded in th
1560: 65 0a 09 23 20 61 72 63 73 29 2e 0a 09 72 65 74 e..# arcs)...ret
1570: 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 urn 1. }..
1580: 20 70 72 6f 63 20 53 61 76 65 41 6e 64 52 65 6d proc SaveAndRem
1590: 6f 76 65 20 7b 64 67 20 6e 7d 20 7b 0a 09 3a 3a ove {dg n} {..::
15a0: 76 61 72 69 61 62 6c 65 20 6d 79 61 74 0a 09 3a variable myat..:
15b0: 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 :variable mysave
15c0: 0a 0a 09 23 20 47 69 76 65 20 74 68 65 20 75 73 ...# Give the us
15d0: 65 72 20 6f 66 20 74 68 65 20 63 79 63 6c 65 20 er of the cycle
15e0: 62 72 65 61 6b 65 72 20 74 68 65 20 6f 70 70 6f breaker the oppo
15f0: 72 74 75 6e 69 74 79 20 74 6f 20 77 6f 72 6b 0a rtunity to work.
1600: 09 23 20 77 69 74 68 20 74 68 65 20 63 68 61 6e .# with the chan
1610: 67 65 73 65 74 20 62 65 66 6f 72 65 20 69 74 20 geset before it
1620: 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 is removed from
1630: 74 68 65 20 67 72 61 70 68 2e 0a 0a 09 69 66 20 the graph....if
1640: 7b 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 {[llength $mysav
1650: 65 5d 7d 20 7b 0a 09 20 20 20 20 75 70 6c 65 76 e]} {.. uplev
1660: 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 el #0 [linsert $
1670: 6d 79 73 61 76 65 20 65 6e 64 20 24 6d 79 61 74 mysave end $myat
1680: 20 24 6e 5d 0a 09 7d 0a 0a 09 69 6e 63 72 20 6d $n]..}...incr m
1690: 79 61 74 0a 09 24 64 67 20 6e 6f 64 65 20 64 65 yat..$dg node de
16a0: 6c 65 74 65 20 24 6e 0a 09 72 65 74 75 72 6e 0a lete $n..return.
16b0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
16c0: 46 69 6e 64 43 79 63 6c 65 20 7b 64 67 7d 20 7b FindCycle {dg} {
16d0: 0a 09 23 20 54 68 69 73 20 70 72 6f 63 65 64 75 ..# This procedu
16e0: 72 65 20 69 73 20 72 75 6e 20 69 66 20 61 6e 64 re is run if and
16f0: 20 6f 6e 6c 79 20 74 68 65 20 67 72 61 70 68 20 only the graph
1700: 69 73 20 6e 6f 74 20 65 6d 70 74 79 20 61 6e 64 is not empty and
1710: 0a 09 23 20 61 6c 6c 20 6e 6f 64 65 73 20 68 61 ..# all nodes ha
1720: 76 65 20 70 72 65 64 65 63 65 73 73 6f 72 73 2e ve predecessors.
1730: 20 54 68 69 73 20 6d 65 61 6e 73 20 74 68 61 74 This means that
1740: 20 65 61 63 68 20 6e 6f 64 65 20 69 73 0a 09 23 each node is..#
1750: 20 65 69 74 68 65 72 20 70 61 72 74 20 6f 66 20 either part of
1760: 61 20 63 79 63 6c 65 20 6f 72 20 28 69 6e 64 69 a cycle or (indi
1770: 72 65 63 74 6c 79 29 20 64 65 70 65 6e 64 69 6e rectly) dependin
1780: 67 20 6f 6e 20 61 20 6e 6f 64 65 0a 09 23 20 69 g on a node..# i
1790: 6e 20 61 20 63 79 63 6c 65 2e 20 57 65 20 63 61 n a cycle. We ca
17a0: 6e 20 73 74 61 72 74 20 61 74 20 61 6e 20 61 72 n start at an ar
17b0: 62 69 74 72 61 72 79 20 6e 6f 64 65 2c 20 66 6f bitrary node, fo
17c0: 6c 6c 6f 77 20 69 74 73 0a 09 23 20 69 6e 63 6f llow its..# inco
17d0: 6d 69 6e 67 20 65 64 67 65 73 20 74 6f 20 69 74 ming edges to it
17e0: 73 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 75 s predecessors u
17f0: 6e 74 69 6c 20 77 65 20 73 65 65 20 61 20 6e 6f ntil we see a no
1800: 64 65 20 61 0a 09 23 20 73 65 63 6f 6e 64 20 74 de a..# second t
1810: 69 6d 65 2e 20 54 68 61 74 20 6e 6f 64 65 20 63 ime. That node c
1820: 6c 6f 73 65 73 20 74 68 65 20 63 79 63 6c 65 20 loses the cycle
1830: 61 6e 64 20 74 68 65 20 62 65 67 69 6e 6e 69 6e and the beginnin
1840: 67 20 69 73 0a 09 23 20 69 74 73 20 66 69 72 73 g is..# its firs
1850: 74 20 6f 63 63 75 72 65 6e 63 65 2e 20 4e 6f 74 t occurence. Not
1860: 65 20 74 68 61 74 20 77 65 20 63 61 6e 20 63 68 e that we can ch
1870: 6f 6f 73 65 20 61 6e 20 61 72 62 69 74 72 61 72 oose an arbitrar
1880: 79 0a 09 23 20 70 72 65 64 65 63 65 73 73 6f 72 y..# predecessor
1890: 20 6f 66 20 65 61 63 68 20 6e 6f 64 65 20 61 73 of each node as
18a0: 20 77 65 6c 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 well, we do not
18b0: 20 68 61 76 65 20 74 6f 20 73 65 61 72 63 68 2e have to search.
18c0: 0a 0a 09 23 20 57 65 20 72 65 63 6f 72 64 20 66 ...# We record f
18d0: 6f 72 20 65 61 63 68 20 6e 6f 64 65 20 74 68 65 or each node the
18e0: 20 69 6e 64 65 78 20 6f 66 20 74 68 65 20 66 69 index of the fi
18f0: 72 73 74 20 61 70 70 65 61 72 61 6e 63 65 20 69 rst appearance i
1900: 6e 0a 09 23 20 74 68 65 20 70 61 74 68 2c 20 6d n..# the path, m
1910: 61 6b 69 6e 67 20 69 74 20 65 61 73 79 20 61 74 aking it easy at
1920: 20 74 68 65 20 65 6e 64 20 74 6f 20 63 75 74 20 the end to cut
1930: 74 68 65 20 63 79 63 6c 65 20 66 72 6f 6d 0a 09 the cycle from..
1940: 23 20 69 74 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 # it....# Choose
1950: 20 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65 20 arbitrary node
1960: 74 6f 20 73 74 61 72 74 20 6f 75 72 20 73 65 61 to start our sea
1970: 72 63 68 20 61 74 2e 0a 09 73 65 74 20 73 74 61 rch at...set sta
1980: 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 rt [lindex [$dg
1990: 6e 6f 64 65 73 5d 20 30 5d 0a 0a 09 23 20 49 6e nodes] 0]...# In
19a0: 69 74 69 61 6c 69 7a 65 20 73 74 61 74 65 2c 20 itialize state,
19b0: 70 61 74 68 20 6f 66 20 73 65 65 6e 20 6e 6f 64 path of seen nod
19c0: 65 73 2c 20 61 6e 64 20 77 68 65 6e 20 73 65 65 es, and when see
19d0: 6e 2e 0a 09 73 65 74 20 20 20 20 20 20 20 70 61 n...set pa
19e0: 74 68 20 7b 7d 0a 09 61 72 72 61 79 20 73 65 74 th {}..array set
19f0: 20 73 65 65 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 seen {}...while
1a00: 20 7b 31 7d 20 7b 0a 09 20 20 20 20 23 20 53 74 {1} {.. # St
1a10: 6f 70 20 73 65 61 72 63 68 69 6e 67 20 77 68 65 op searching whe
1a20: 6e 20 77 65 20 68 61 76 65 20 73 65 65 6e 20 74 n we have seen t
1a30: 68 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 0a he current node.
1a40: 09 20 20 20 20 23 20 61 6c 72 65 61 64 79 2c 20 . # already,
1a50: 74 68 65 20 63 69 72 63 6c 65 20 68 61 73 20 62 the circle has b
1a60: 65 65 6e 20 63 6c 6f 73 65 64 2e 0a 09 20 20 20 een closed...
1a70: 20 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 73 74 if {[info exist
1a80: 73 20 73 65 65 6e 28 24 73 74 61 72 74 29 5d 7d s seen($start)]}
1a90: 20 62 72 65 61 6b 0a 09 20 20 20 20 6c 61 70 70 break.. lapp
1aa0: 65 6e 64 20 70 61 74 68 20 24 73 74 61 72 74 0a end path $start.
1ab0: 09 20 20 20 20 73 65 74 20 73 65 65 6e 28 24 73 . set seen($s
1ac0: 74 61 72 74 29 20 5b 65 78 70 72 20 7b 5b 6c 6c tart) [expr {[ll
1ad0: 65 6e 67 74 68 20 24 70 61 74 68 5d 2d 31 7d 5d ength $path]-1}]
1ae0: 0a 09 20 20 20 20 23 20 43 68 6f 6f 73 65 20 61 .. # Choose a
1af0: 72 62 69 74 72 61 72 79 20 70 72 65 64 65 63 65 rbitrary predece
1b00: 73 73 6f 72 0a 09 20 20 20 20 73 65 74 20 73 74 ssor.. set st
1b10: 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 art [lindex [$dg
1b20: 20 6e 6f 64 65 73 20 2d 69 6e 20 24 73 74 61 72 nodes -in $star
1b30: 74 5d 20 30 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 t] 0]..}...retur
1b40: 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 n [struct::list
1b50: 72 65 76 65 72 73 65 20 5b 6c 72 61 6e 67 65 20 reverse [lrange
1b60: 24 70 61 74 68 20 24 73 65 65 6e 28 24 73 74 61 $path $seen($sta
1b70: 72 74 29 20 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a rt) end]]. }.
1b80: 0a 20 20 20 20 70 72 6f 63 20 49 44 20 7b 63 73 . proc ID {cs
1b90: 65 74 7d 20 7b 20 72 65 74 75 72 6e 20 22 3c 5b et} { return "<[
1ba0: 24 63 73 65 74 20 69 64 5d 3e 22 20 7d 0a 0a 20 $cset id]>" }..
1bb0: 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 79 63 proc BreakCyc
1bc0: 6c 65 20 7b 64 67 20 63 79 63 6c 65 7d 20 7b 0a le {dg cycle} {.
1bd0: 09 23 20 54 68 65 20 63 79 63 6c 65 20 77 65 20 .# The cycle we
1be0: 68 61 76 65 20 67 6f 74 74 65 6e 20 69 73 20 62 have gotten is b
1bf0: 72 6f 6b 65 6e 20 62 79 20 62 72 65 61 6b 69 6e roken by breakin
1c00: 67 20 61 70 61 72 74 20 6f 6e 65 20 6f 72 0a 09 g apart one or..
1c10: 23 20 6d 6f 72 65 20 6f 66 20 74 68 65 20 63 68 # more of the ch
1c20: 61 6e 67 65 73 65 74 73 20 69 6e 20 74 68 65 20 angesets in the
1c30: 63 79 63 6c 65 2e 20 54 68 69 73 20 63 61 75 73 cycle. This caus
1c40: 65 73 20 75 73 20 74 6f 0a 09 23 20 63 72 65 61 es us to..# crea
1c50: 74 65 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 20 63 te one or more c
1c60: 68 61 6e 67 65 73 65 74 73 20 77 68 69 63 68 20 hangesets which
1c70: 61 72 65 20 74 6f 20 62 65 20 63 6f 6d 6d 69 74 are to be commit
1c80: 74 65 64 2c 0a 09 23 20 61 64 64 65 64 20 74 6f ted,..# added to
1c90: 20 74 68 65 20 67 72 61 70 68 2c 20 65 74 63 2e the graph, etc.
1ca0: 20 70 70 2e 0a 0a 09 73 65 74 20 63 70 72 69 6e pp....set cprin
1cb0: 74 20 5b 6a 6f 69 6e 20 5b 73 74 72 75 63 74 3a t [join [struct:
1cc0: 3a 6c 69 73 74 20 6d 61 70 20 24 63 79 63 6c 65 :list map $cycle
1cd0: 20 5b 6d 79 70 72 6f 63 20 49 44 5d 5d 20 7b 20 [myproc ID]] {
1ce0: 7d 5d 0a 0a 09 6c 61 70 70 65 6e 64 20 63 79 63 }]...lappend cyc
1cf0: 6c 65 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c le [lindex $cycl
1d00: 65 20 30 5d 20 5b 6c 69 6e 64 65 78 20 24 63 79 e 0] [lindex $cy
1d10: 63 6c 65 20 31 5d 0a 09 73 65 74 20 62 65 73 74 cle 1]..set best
1d20: 6c 69 6e 6b 20 7b 7d 0a 09 73 65 74 20 62 65 73 link {}..set bes
1d30: 74 6e 6f 64 65 20 7b 7d 0a 0a 09 66 6f 72 65 61 tnode {}...forea
1d40: 63 68 20 5c 0a 09 20 20 20 20 70 72 65 76 20 5b ch \.. prev [
1d50: 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 30 20 lrange $cycle 0
1d60: 65 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 20 63 73 end-2] \.. cs
1d70: 65 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c et [lrange $cycl
1d80: 65 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 e 1 end-1] \..
1d90: 20 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 20 24 next [lrange $
1da0: 63 79 63 6c 65 20 32 20 65 6e 64 5d 20 7b 0a 0a cycle 2 end] {..
1db0: 09 09 23 20 45 61 63 68 20 74 72 69 70 6c 65 20 ..# Each triple
1dc0: 50 52 45 56 20 2d 3e 20 43 53 45 54 20 2d 3e 20 PREV -> CSET ->
1dd0: 4e 45 58 54 20 6f 66 20 63 68 61 6e 67 65 73 65 NEXT of changese
1de0: 74 73 2c 20 61 0a 09 09 23 20 27 6c 69 6e 6b 27 ts, a...# 'link'
1df0: 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2c 20 69 in the cycle, i
1e00: 73 20 61 6e 61 6c 79 73 65 64 20 61 6e 64 20 74 s analysed and t
1e10: 68 65 20 62 65 73 74 0a 09 09 23 20 6c 6f 63 61 he best...# loca
1e20: 74 69 6f 6e 20 77 68 65 72 65 20 74 6f 20 61 74 tion where to at
1e30: 20 6c 65 61 73 74 20 77 65 61 6b 65 6e 20 74 68 least weaken th
1e40: 65 20 63 79 63 6c 65 20 69 73 0a 09 09 23 20 63 e cycle is...# c
1e50: 68 6f 73 65 6e 20 66 6f 72 20 66 75 72 74 68 65 hosen for furthe
1e60: 72 20 70 72 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 r processing....
1e70: 09 73 65 74 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 .set link [proje
1e80: 63 74 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 55 54 ct::revlink %AUT
1e90: 4f 25 20 24 70 72 65 76 20 24 63 73 65 74 20 24 O% $prev $cset $
1ea0: 6e 65 78 74 5d 0a 09 09 69 66 20 7b 24 62 65 73 next]...if {$bes
1eb0: 74 6c 69 6e 6b 20 65 71 20 22 22 7d 20 7b 0a 09 tlink eq ""} {..
1ec0: 09 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e . set bestlin
1ed0: 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 k $link... se
1ee0: 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 t bestnode $cset
1ef0: 0a 09 09 7d 20 65 6c 73 65 69 66 20 7b 5b 24 6c ...} elseif {[$l
1f00: 69 6e 6b 20 62 65 74 74 65 72 74 68 61 6e 20 24 ink betterthan $
1f10: 62 65 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 bestlink]} {...
1f20: 20 20 20 24 62 65 73 74 6c 69 6e 6b 20 64 65 73 $bestlink des
1f30: 74 72 6f 79 0a 09 09 20 20 20 20 73 65 74 20 62 troy... set b
1f40: 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 estlink $link...
1f50: 20 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 set bestnode
1f60: 20 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 20 $cset...} else
1f70: 7b 0a 09 09 20 20 20 20 24 6c 69 6e 6b 20 64 65 {... $link de
1f80: 73 74 72 6f 79 0a 09 09 7d 0a 09 20 20 20 20 7d stroy...}.. }
1f90: 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 20 62 ...log write 5 b
1fa0: 72 65 61 6b 72 63 79 63 6c 65 20 22 42 72 65 61 reakrcycle "Brea
1fb0: 6b 69 6e 67 20 63 79 63 6c 65 20 28 24 63 70 72 king cycle ($cpr
1fc0: 69 6e 74 29 20 62 79 20 73 70 6c 69 74 74 69 6e int) by splittin
1fd0: 67 20 63 68 61 6e 67 65 73 65 74 20 3c 5b 24 62 g changeset <[$b
1fe0: 65 73 74 6e 6f 64 65 20 69 64 5d 3e 22 0a 09 73 estnode id]>"..s
1ff0: 65 74 20 49 44 20 5b 24 62 65 73 74 6e 6f 64 65 et ID [$bestnode
2000: 20 69 64 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d id]..Mark $dg -
2010: 24 7b 49 44 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 ${ID}-before...s
2020: 65 74 20 6e 65 77 63 73 65 74 73 20 5b 24 62 65 et newcsets [$be
2030: 73 74 6c 69 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 stlink break]..$
2040: 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 bestlink destroy
2050: 0a 0a 20 20 20 20 20 20 20 20 23 20 41 74 20 74 .. # At t
2060: 68 69 73 20 70 6f 69 6e 74 20 74 68 65 20 6f 6c his point the ol
2070: 64 20 63 68 61 6e 67 65 73 65 74 20 28 42 45 53 d changeset (BES
2080: 54 4e 4f 44 45 29 20 69 73 20 67 6f 6e 65 0a 20 TNODE) is gone.
2090: 20 20 20 20 20 20 20 23 20 61 6c 72 65 61 64 79 # already
20a0: 2e 20 57 65 20 72 65 6d 6f 76 65 20 69 74 20 66 . We remove it f
20b0: 72 6f 6d 20 74 68 65 20 67 72 61 70 68 20 61 73 rom the graph as
20c0: 20 77 65 6c 6c 20 61 6e 64 20 74 68 65 6e 20 65 well and then e
20d0: 6e 74 65 72 0a 20 20 20 20 20 20 20 20 23 20 74 nter. # t
20e0: 68 65 20 66 72 61 67 6d 65 6e 74 73 20 67 65 6e he fragments gen
20f0: 65 72 61 74 65 64 20 66 6f 72 20 69 74 2e 0a 0a erated for it...
2100: 09 23 20 4e 4f 54 45 2e 20 57 65 20 68 61 76 65 .# NOTE. We have
2110: 20 74 6f 20 67 65 74 20 74 68 65 20 6c 69 73 74 to get the list
2120: 20 6f 66 20 69 6e 63 6f 6d 69 6e 67 20 6e 65 69 of incoming nei
2130: 67 68 62 6f 75 72 73 20 61 6e 64 0a 09 23 20 72 ghbours and..# r
2140: 65 63 6f 6d 70 75 74 65 20 74 68 65 69 72 20 73 ecompute their s
2150: 75 63 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 uccessors after
2160: 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 20 68 61 the new nodes ha
2170: 76 65 20 62 65 65 6e 0a 09 23 20 69 6e 73 65 72 ve been..# inser
2180: 74 65 64 2e 20 54 68 65 69 72 20 6f 75 74 67 6f ted. Their outgo
2190: 69 6e 67 20 61 72 63 73 20 77 69 6c 6c 20 6e 6f ing arcs will no
21a0: 77 20 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 20 62 w go to one or b
21b0: 6f 74 68 20 6f 66 0a 09 23 20 74 68 65 20 6e 65 oth of..# the ne
21c0: 77 20 6e 6f 64 65 73 2c 20 61 6e 64 20 6e 6f 74 w nodes, and not
21d0: 20 72 65 64 6f 69 6e 67 20 74 68 65 6d 20 6d 61 redoing them ma
21e0: 79 20 63 61 75 73 65 20 75 73 20 74 6f 20 66 6f y cause us to fo
21f0: 72 67 65 74 0a 09 23 20 63 69 72 63 6c 65 73 2c rget..# circles,
2200: 20 6c 65 61 76 69 6e 67 20 74 68 65 6d 20 69 6e leaving them in
2210: 2c 20 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 73 65 , unbroken....se
2220: 74 20 70 72 65 20 5b 24 64 67 20 6e 6f 64 65 73 t pre [$dg nodes
2230: 20 2d 69 6e 20 24 62 65 73 74 6e 6f 64 65 5d 0a -in $bestnode].
2240: 0a 20 20 20 20 20 20 20 20 24 64 67 20 6e 6f 64 . $dg nod
2250: 65 20 64 65 6c 65 74 65 20 24 62 65 73 74 6e 6f e delete $bestno
2260: 64 65 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 de...foreach cse
2270: 74 20 24 6e 65 77 63 73 65 74 73 20 7b 0a 09 20 t $newcsets {..
2280: 20 20 20 24 64 67 20 6e 6f 64 65 20 69 6e 73 65 $dg node inse
2290: 72 74 20 24 63 73 65 74 0a 09 20 20 20 20 24 64 rt $cset.. $d
22a0: 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 g node set $c
22b0: 73 65 74 20 74 69 6d 65 72 61 6e 67 65 20 5b 24 set timerange [$
22c0: 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d 0a cset timerange].
22d0: 09 7d 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 .}...foreach cse
22e0: 74 20 24 6e 65 77 63 73 65 74 73 20 7b 0a 09 20 t $newcsets {..
22f0: 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 63 20 foreach succ
2300: 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 6f 72 [$cset successor
2310: 73 5d 20 7b 0a 09 09 23 20 54 68 65 20 6e 65 77 s] {...# The new
2320: 20 63 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 changesets may
2330: 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 have dependencie
2340: 73 20 6f 75 74 73 69 64 65 20 6f 66 0a 09 09 23 s outside of...#
2350: 20 74 68 65 20 63 68 6f 73 65 6e 20 73 65 74 2e the chosen set.
2360: 20 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 These are ignor
2370: 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e ed...if {![$dg n
2380: 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 ode exists $succ
2390: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 ]} continue...$d
23a0: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
23b0: 65 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a et $succ.. }.
23c0: 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 .}..foreach cset
23d0: 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 6f 72 $pre {.. for
23e0: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
23f0: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
2400: 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 68 65 .# Note that the
2410: 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 64 79 arc may already
2420: 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 67 72 exist in the gr
2430: 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f 20 69 aph. If...# so i
2440: 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 6e 65 gnore it. The ne
2450: 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d 61 79 w changesets may
2460: 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 6e 64 have...# depend
2470: 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 20 6f encies outside o
2480: 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 65 74 f the chosen set
2490: 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 23 20 . These are...#
24a0: 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b ignored...if {![
24b0: 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 73 20 $dg node exists
24c0: 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 $succ]} continue
24d0: 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 20 24 ...if {[HasArc $
24e0: 64 67 20 24 63 73 65 74 20 24 73 75 63 63 5d 7d dg $cset $succ]}
24f0: 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f 44 4f continue;# TODO
2500: 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 70 68 should be graph
2510: 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 20 61 method....$dg a
2520: 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 rc insert $cset
2530: 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a $succ.. }..}.
2540: 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 ..Mark $dg -${ID
2550: 7d 2d 61 66 74 65 72 0a 09 72 65 74 75 72 6e 0a }-after..return.
2560: 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 54 4f 44 }.. # TOD
2570: 4f 3a 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 O: This should b
2580: 65 20 61 20 67 72 61 70 68 20 6d 65 74 68 6f 64 e a graph method
2590: 2e 0a 20 20 20 20 70 72 6f 63 20 48 61 73 41 72 .. proc HasAr
25a0: 63 20 7b 64 67 20 61 20 62 7d 20 7b 0a 09 23 38 c {dg a b} {..#8
25b0: 2e 35 3a 20 72 65 74 75 72 6e 20 5b 65 78 70 72 .5: return [expr
25c0: 20 7b 24 62 20 69 6e 20 5b 24 64 67 20 6e 6f 64 {$b in [$dg nod
25d0: 65 73 20 2d 6f 75 74 20 24 61 5d 7d 5d 0a 09 69 es -out $a]}]..i
25e0: 66 20 7b 5b 6c 73 65 61 72 63 68 20 2d 65 78 61 f {[lsearch -exa
25f0: 63 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f ct [$dg nodes -o
2600: 75 74 20 24 61 5d 20 24 62 5d 20 3c 20 30 7d 20 ut $a] $b] < 0}
2610: 7b 20 72 65 74 75 72 6e 20 30 20 7d 0a 09 72 65 { return 0 }..re
2620: 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 turn 1. }..
2630: 20 20 70 72 6f 63 20 4d 61 72 6b 20 7b 64 67 20 proc Mark {dg
2640: 7b 73 75 66 66 69 78 20 7b 7d 7d 7d 20 7b 0a 09 {suffix {}}} {..
2650: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 ::variable mydot
2660: 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 69 66 20 destination..if
2670: 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 {$mydotdestinati
2680: 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 75 72 6e on eq ""} return
2690: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 ..::variable myd
26a0: 6f 74 70 72 65 66 69 78 0a 09 3a 3a 76 61 72 69 otprefix..::vari
26b0: 61 62 6c 65 20 6d 79 64 6f 74 69 64 0a 09 73 65 able mydotid..se
26c0: 74 20 66 6e 61 6d 65 20 24 6d 79 64 6f 74 64 65 t fname $mydotde
26d0: 73 74 69 6e 61 74 69 6f 6e 2f 24 7b 6d 79 64 6f stination/${mydo
26e0: 74 70 72 65 66 69 78 7d 24 7b 6d 79 64 6f 74 69 tprefix}${mydoti
26f0: 64 7d 24 7b 73 75 66 66 69 78 7d 2e 64 6f 74 0a d}${suffix}.dot.
2700: 09 66 69 6c 65 20 6d 6b 64 69 72 20 5b 66 69 6c .file mkdir [fil
2710: 65 20 64 69 72 6e 61 6d 65 20 24 66 6e 61 6d 65 e dirname $fname
2720: 5d 0a 09 64 6f 74 20 77 72 69 74 65 20 24 64 67 ]..dot write $dg
2730: 20 24 6d 79 64 6f 74 70 72 65 66 69 78 24 73 75 $mydotprefix$su
2740: 66 66 69 78 20 24 66 6e 61 6d 65 0a 09 69 6e 63 ffix $fname..inc
2750: 72 20 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f 67 20 r mydotid...log
2760: 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 72 65 write 5 cyclebre
2770: 61 6b 65 72 20 22 2e 64 6f 74 20 65 78 70 6f 72 aker ".dot expor
2780: 74 20 24 66 6e 61 6d 65 22 0a 09 72 65 74 75 72 t $fname"..retur
2790: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 n. }.. typ
27a0: 65 76 61 72 69 61 62 6c 65 20 6d 79 61 74 20 20 evariable myat
27b0: 20 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 0 ; # Cou
27c0: 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 nter for commit
27d0: 69 64 73 20 66 6f 72 20 74 68 65 20 63 68 61 6e ids for the chan
27e0: 67 65 73 65 74 73 2e 0a 20 20 20 20 74 79 70 65 gesets.. type
27f0: 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f variable mybotto
2800: 6d 20 20 20 20 7b 7d 20 3b 20 23 20 4c 69 73 74 m {} ; # List
2810: 20 6f 66 20 63 61 6e 64 69 64 61 74 65 20 6e 6f of candidate no
2820: 64 65 73 20 66 6f 72 20 63 6f 6d 6d 69 74 74 69 des for committi
2830: 6e 67 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 ng.. typevari
2840: 61 62 6c 65 20 6d 79 73 61 76 65 20 20 20 20 20 able mysave
2850: 20 7b 7d 20 3b 20 23 20 54 68 65 20 63 6f 6d 6d {} ; # The comm
2860: 61 6e 64 20 74 6f 20 63 61 6c 6c 20 66 6f 72 20 and to call for
2870: 65 61 63 68 20 70 72 6f 63 65 73 73 65 64 20 6e each processed n
2880: 6f 64 65 0a 0a 20 20 20 20 74 79 70 65 76 61 72 ode.. typevar
2890: 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 iable mydotdesti
28a0: 6e 61 74 69 6f 6e 20 7b 7d 20 3b 20 23 20 44 65 nation {} ; # De
28b0: 73 74 69 6e 61 74 69 6f 6e 20 64 69 72 65 63 74 stination direct
28c0: 6f 72 79 20 66 6f 72 20 2e 64 6f 74 20 66 69 6c ory for .dot fil
28d0: 65 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 es.. typevari
28e0: 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 able mydotprefix
28f0: 20 7b 7d 20 3b 20 23 20 50 72 65 66 69 78 20 66 {} ; # Prefix f
2900: 6f 72 20 64 6f 74 20 66 69 6c 65 73 20 77 68 65 or dot files whe
2910: 6e 20 65 78 70 6f 72 74 69 6e 67 20 74 68 65 20 n exporting the
2920: 67 72 61 70 68 73 2e 0a 20 20 20 20 74 79 70 65 graphs.. type
2930: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 variable mydotid
2940: 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 0 ; # Coun
2950: 74 65 72 20 66 6f 72 20 64 6f 74 20 66 69 6c 65 ter for dot file
2960: 20 6e 61 6d 65 20 67 65 6e 65 72 61 74 69 6f 6e name generation
2970: 2e 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 ... # # ## ##
2980: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
2990: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
29a0: 20 20 20 23 23 20 43 6f 6e 66 69 67 75 72 61 74 ## Configurat
29b0: 69 6f 6e 0a 0a 20 20 20 20 70 72 61 67 6d 61 20 ion.. pragma
29c0: 2d 68 61 73 69 6e 73 74 61 6e 63 65 73 20 20 20 -hasinstances
29d0: 6e 6f 20 3b 20 23 20 73 69 6e 67 6c 65 74 6f 6e no ; # singleton
29e0: 0a 20 20 20 20 70 72 61 67 6d 61 20 2d 68 61 73 . pragma -has
29f0: 74 79 70 65 69 6e 66 6f 20 20 20 20 6e 6f 20 3b typeinfo no ;
2a00: 20 23 20 6e 6f 20 69 6e 74 72 6f 73 70 65 63 74 # no introspect
2a10: 69 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 20 2d ion. pragma -
2a20: 68 61 73 74 79 70 65 64 65 73 74 72 6f 79 20 6e hastypedestroy n
2a30: 6f 20 3b 20 23 20 69 6d 6d 6f 72 74 61 6c 0a 0a o ; # immortal..
2a40: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
2a50: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
2a60: 23 23 23 23 23 23 23 23 23 23 23 0a 7d 0a 0a 6e ###########.}..n
2a70: 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 3a 3a amespace eval ::
2a80: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
2a90: 72 74 3a 3a 63 76 73 20 7b 0a 20 20 20 20 6e 61 rt::cvs {. na
2aa0: 6d 65 73 70 61 63 65 20 65 78 70 6f 72 74 20 63 mespace export c
2ab0: 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 yclebreaker.
2ac0: 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 63 namespace eval c
2ad0: 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 0a 09 6e yclebreaker {..n
2ae0: 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 70 72 amespace eval pr
2af0: 6f 6a 65 63 74 20 7b 0a 09 20 20 20 20 6e 61 6d oject {.. nam
2b00: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
2b10: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
2b20: 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 rt::cvs::project
2b30: 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d 65 73 ::rev.. names
2b40: 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 pace import ::vc
2b50: 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 ::fossil::import
2b60: 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a ::cvs::project::
2b70: 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 6d 65 revlink..}..name
2b80: 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 space import ::v
2b90: 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 3a 3a c::tools::misc::
2ba0: 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 *..namespace imp
2bb0: 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a ort ::vc::tools:
2bc0: 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 65 20 :log..namespace
2bd0: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
2be0: 6c 73 3a 3a 64 6f 74 0a 09 6c 6f 67 20 72 65 67 ls::dot..log reg
2bf0: 69 73 74 65 72 20 63 79 63 6c 65 62 72 65 61 6b ister cyclebreak
2c00: 65 72 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 23 20 er. }.}..# #
2c10: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
2c20: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
2c30: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
2c40: 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 61 #########.## Rea
2c50: 64 79 0a 0a 70 61 63 6b 61 67 65 20 70 72 6f 76 dy..package prov
2c60: 69 64 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a ide vc::fossil::
2c70: 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 63 import::cvs::cyc
2c80: 6c 65 62 72 65 61 6b 65 72 20 31 2e 30 0a 72 65 lebreaker 1.0.re
2c90: 74 75 72 6e 0a turn.