Artifact 59ef48a9b8851e680f238e1243e86c05a81428c8:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[5b2d15f183]
- Fixed typo, although it did not break anything.
by
aku on
2007-12-05 02:25:30.
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 74 ire vc::tools::t
04d0: 72 6f 75 62 6c 65 20 20 20 20 20 20 20 20 20 20 rouble
04e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
04f0: 23 20 45 72 72 6f 72 20 72 65 70 6f 72 74 69 6e # Error reportin
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 74 6f 6f 6c 73 3a 3a 6d 69 re vc::tools::mi
0520: 73 63 20 20 20 20 20 20 20 20 20 20 20 20 20 20 sc
0530: 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 23 ; #
0540: 20 54 65 78 74 20 66 6f 72 6d 61 74 74 69 6e 67 Text formatting
0550: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 ..package requir
0560: 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d e vc::fossil::im
0570: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 port::cvs::proje
0580: 63 74 3a 3a 72 65 76 20 20 20 20 20 3b 20 23 20 ct::rev ; #
0590: 50 72 6f 6a 65 63 74 20 6c 65 76 65 6c 20 63 68 Project level ch
05a0: 61 6e 67 65 73 65 74 73 0a 70 61 63 6b 61 67 65 angesets.package
05b0: 20 72 65 71 75 69 72 65 20 76 63 3a 3a 66 6f 73 require vc::fos
05c0: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
05d0: 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 ::project::revli
05e0: 6e 6b 20 3b 20 23 20 43 79 63 6c 65 20 6c 69 6e nk ; # Cycle lin
05f0: 6b 73 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 ks..package requ
0600: 69 72 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a ire vc::fossil::
0610: 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 69 6e 74 import::cvs::int
0620: 65 67 72 69 74 79 20 20 20 20 20 20 20 20 3b 20 egrity ;
0630: 23 20 53 74 61 74 65 20 69 6e 74 65 67 72 69 74 # State integrit
0640: 79 20 63 68 65 63 6b 73 2e 0a 0a 23 20 23 20 23 y checks...# # #
0650: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
0660: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
0670: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
0680: 23 23 23 23 23 23 23 23 0a 23 23 0a 0a 73 6e 69 ########.##..sni
0690: 74 3a 3a 74 79 70 65 20 3a 3a 76 63 3a 3a 66 6f t::type ::vc::fo
06a0: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
06b0: 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 72 20 s::cyclebreaker
06c0: 7b 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 {. # # ## ###
06d0: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
06e0: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 #############.
06f0: 20 20 23 23 20 50 75 62 6c 69 63 20 41 50 49 0a ## Public API.
0700: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
0710: 70 72 65 63 6d 64 20 7b 63 6d 64 7d 20 7b 0a 09 precmd {cmd} {..
0720: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 70 72 65 ::variable mypre
0730: 63 6d 64 20 24 63 6d 64 0a 09 72 65 74 75 72 6e cmd $cmd..return
0740: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 . }.. type
0750: 6d 65 74 68 6f 64 20 73 61 76 65 63 6d 64 20 7b method savecmd {
0760: 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 cmd} {..::variab
0770: 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 24 63 6d le mysavecmd $cm
0780: 64 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a d..return. }.
0790: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
07a0: 62 72 65 61 6b 63 6d 64 20 7b 63 6d 64 7d 20 7b breakcmd {cmd} {
07b0: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 ..::variable myb
07c0: 72 65 61 6b 63 6d 64 20 24 63 6d 64 0a 09 72 65 reakcmd $cmd..re
07d0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
07e0: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
07f0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
0800: 23 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 70 #######.. typ
0810: 65 6d 65 74 68 6f 64 20 64 6f 74 73 74 6f 20 7b emethod dotsto {
0820: 70 61 74 68 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 path} {..::varia
0830: 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 ble mydotdestina
0840: 74 69 6f 6e 20 24 70 61 74 68 0a 09 72 65 74 75 tion $path..retu
0850: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 rn. }.. ty
0860: 70 65 6d 65 74 68 6f 64 20 77 61 74 63 68 20 7b pemethod watch {
0870: 69 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c id} {..::variabl
0880: 65 20 6d 79 77 61 74 63 68 69 64 73 0a 09 6c 61 e mywatchids..la
0890: 70 70 65 6e 64 20 6d 79 77 61 74 63 68 69 64 73 ppend mywatchids
08a0: 20 24 69 64 0a 20 20 20 20 7d 0a 0a 20 20 20 20 $id. }..
08b0: 74 79 70 65 6d 65 74 68 6f 64 20 64 6f 74 20 7b typemethod dot {
08c0: 6c 61 62 65 6c 20 63 68 61 6e 67 65 73 65 74 73 label changesets
08d0: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
08e0: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
08f0: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
0900: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 73 ydotid 0...s
0910: 65 74 20 64 67 20 5b 53 65 74 75 70 20 24 63 68 et dg [Setup $ch
0920: 61 6e 67 65 73 65 74 73 20 30 5d 0a 09 4d 61 72 angesets 0]..Mar
0930: 6b 20 24 64 67 0a 09 24 64 67 20 64 65 73 74 72 k $dg..$dg destr
0940: 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d oy..return. }
0950: 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 .. typemethod
0960: 20 6d 61 72 6b 20 7b 67 72 61 70 68 20 73 75 66 mark {graph suf
0970: 66 69 78 20 7b 73 75 62 67 72 61 70 68 20 7b 7d fix {subgraph {}
0980: 7d 7d 20 7b 0a 09 4d 61 72 6b 20 24 67 72 61 70 }} {..Mark $grap
0990: 68 20 24 73 75 66 66 69 78 20 24 73 75 62 67 72 h $suffix $subgr
09a0: 61 70 68 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 aph..return.
09b0: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
09c0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
09d0: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a #############..
09e0: 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 72 typemethod r
09f0: 75 6e 20 7b 6c 61 62 65 6c 20 63 68 61 6e 67 65 un {label change
0a00: 73 65 74 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 setcmd} {..::var
0a10: 69 61 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 iable myat
0a20: 20 20 30 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 0..::variable
0a30: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
0a40: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
0a50: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 23 ydotid 0...#
0a60: 20 57 65 20 63 72 65 61 74 65 20 61 20 67 72 61 We create a gra
0a70: 70 68 20 6f 66 20 74 68 65 20 72 65 76 69 73 69 ph of the revisi
0a80: 6f 6e 20 63 68 61 6e 67 65 73 65 74 73 2c 20 75 on changesets, u
0a90: 73 69 6e 67 20 74 68 65 20 66 69 6c 65 0a 09 23 sing the file..#
0aa0: 20 6c 65 76 65 6c 20 64 65 70 65 6e 64 65 6e 63 level dependenc
0ab0: 69 65 73 20 74 6f 20 63 6f 6e 73 74 72 75 63 74 ies to construct
0ac0: 20 61 20 66 69 72 73 74 20 61 70 70 72 6f 78 69 a first approxi
0ad0: 6d 61 74 69 6f 6e 20 6f 66 20 74 68 65 0a 09 23 mation of the..#
0ae0: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 74 dependencies at
0af0: 20 74 68 65 20 70 72 6f 6a 65 63 74 20 6c 65 76 the project lev
0b00: 65 6c 2e 20 54 68 65 6e 20 77 65 20 6c 6f 6f 6b el. Then we look
0b10: 20 66 6f 72 20 63 79 63 6c 65 73 0a 09 23 20 69 for cycles..# i
0b20: 6e 20 74 68 61 74 20 67 72 61 70 68 20 61 6e 64 n that graph and
0b30: 20 62 72 65 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 break them....#
0b40: 20 31 2e 20 43 72 65 61 74 65 20 6e 6f 64 65 73 1. Create nodes
0b50: 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e for all relevan
0b60: 74 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 t changesets and
0b70: 20 61 20 6d 61 70 70 69 6e 67 0a 09 23 20 20 20 a mapping..#
0b80: 20 66 72 6f 6d 20 74 68 65 20 72 65 76 69 73 69 from the revisi
0b90: 6f 6e 73 20 74 6f 20 74 68 65 69 72 20 63 68 61 ons to their cha
0ba0: 6e 67 65 73 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a ngesets/nodes...
0bb0: 09 73 65 74 20 63 68 61 6e 67 65 73 65 74 73 20 .set changesets
0bc0: 5b 75 70 6c 65 76 65 6c 20 23 30 20 24 63 68 61 [uplevel #0 $cha
0bd0: 6e 67 65 73 65 74 63 6d 64 5d 0a 09 73 65 74 20 ngesetcmd]..set
0be0: 64 67 20 5b 53 65 74 75 70 20 24 63 68 61 6e 67 dg [Setup $chang
0bf0: 65 73 65 74 73 5d 0a 0a 09 23 20 33 2e 20 4c 61 esets]...# 3. La
0c00: 73 74 6c 79 20 77 65 20 69 74 65 72 61 74 65 20 stly we iterate
0c10: 74 68 65 20 67 72 61 70 68 20 74 6f 70 6f 6c 6f the graph topolo
0c20: 67 69 63 61 6c 6c 79 2e 20 57 65 20 6d 61 72 6b gically. We mark
0c30: 20 6f 66 66 0a 09 23 20 20 20 20 74 68 65 20 6e off..# the n
0c40: 6f 64 65 73 20 77 68 69 63 68 20 68 61 76 65 20 odes which have
0c50: 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 73 2c no predecessors,
0c60: 20 69 6e 20 6f 72 64 65 72 20 66 72 6f 6d 0a 09 in order from..
0c70: 23 20 20 20 20 6f 6c 64 65 73 74 20 74 6f 20 79 # oldest to y
0c80: 6f 75 6e 67 65 73 74 2c 20 73 61 76 69 6e 67 20 oungest, saving
0c90: 61 6e 64 20 72 65 6d 6f 76 69 6e 67 20 64 65 70 and removing dep
0ca0: 65 6e 64 65 6e 63 69 65 73 2e 20 49 66 0a 09 23 endencies. If..#
0cb0: 20 20 20 20 77 65 20 66 69 6e 64 20 6e 6f 20 6e we find no n
0cc0: 6f 64 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 odes without pre
0cd0: 64 65 63 65 73 73 6f 72 73 20 77 65 20 68 61 76 decessors we hav
0ce0: 65 20 61 20 63 79 63 6c 65 2c 0a 09 23 20 20 20 e a cycle,..#
0cf0: 20 61 6e 64 20 77 6f 72 6b 20 6f 6e 20 62 72 65 and work on bre
0d00: 61 6b 69 6e 67 20 69 74 2e 0a 0a 09 6c 6f 67 20 aking it....log
0d10: 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 write 3 cyclebre
0d20: 61 6b 65 72 20 7b 54 72 61 76 65 72 73 65 20 63 aker {Traverse c
0d30: 68 61 6e 67 65 73 65 74 73 7d 0a 0a 09 49 6e 69 hangesets}...Ini
0d40: 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 tializeCandidate
0d50: 73 20 24 64 67 0a 0a 09 73 65 74 20 6b 20 20 20 s $dg...set k
0d60: 30 0a 09 73 65 74 20 6d 61 78 20 5b 6c 6c 65 6e 0..set max [llen
0d70: 67 74 68 20 5b 24 64 67 20 6e 6f 64 65 73 5d 5d gth [$dg nodes]]
0d80: 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 20 ..while {1} {..
0d90: 20 20 20 77 68 69 6c 65 20 7b 5b 57 69 74 68 6f while {[Witho
0da0: 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 24 64 utPredecessor $d
0db0: 67 20 6e 5d 7d 20 7b 0a 09 09 6c 6f 67 20 70 72 g n]} {...log pr
0dc0: 6f 67 72 65 73 73 20 32 20 63 79 63 6c 65 62 72 ogress 2 cyclebr
0dd0: 65 61 6b 65 72 20 24 6b 20 24 6d 61 78 20 3b 20 eaker $k $max ;
0de0: 69 6e 63 72 20 6b 0a 09 09 4d 61 72 6b 57 61 74 incr k...MarkWat
0df0: 63 68 20 24 64 67 0a 09 09 50 72 6f 63 65 73 73 ch $dg...Process
0e00: 65 64 48 6f 6f 6b 20 24 64 67 20 24 6e 20 24 6d edHook $dg $n $m
0e10: 79 61 74 0a 09 09 24 64 67 20 6e 6f 64 65 20 64 yat...$dg node d
0e20: 65 6c 65 74 65 20 24 6e 0a 09 09 69 6e 63 72 20 elete $n...incr
0e30: 6d 79 61 74 0a 09 09 53 68 6f 77 50 65 6e 64 69 myat...ShowPendi
0e40: 6e 67 4e 6f 64 65 73 0a 09 20 20 20 20 7d 0a 0a ngNodes.. }..
0e50: 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c 65 6e 67 . if {![lleng
0e60: 74 68 20 5b 24 64 67 20 6e 6f 64 65 73 5d 5d 7d th [$dg nodes]]}
0e70: 20 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 72 65 break... Bre
0e80: 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 20 20 akCycleHook
0e90: 20 20 24 64 67 0a 09 20 20 20 20 49 6e 69 74 69 $dg.. Initi
0ea0: 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 alizeCandidates
0eb0: 24 64 67 0a 09 20 20 20 20 4d 61 72 6b 57 61 74 $dg.. MarkWat
0ec0: 63 68 20 20 20 20 20 20 20 20 20 20 20 20 24 64 ch $d
0ed0: 67 0a 09 7d 0a 0a 09 24 64 67 20 64 65 73 74 72 g..}...$dg destr
0ee0: 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 33 oy...log write 3
0ef0: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 44 6f cyclebreaker Do
0f00: 6e 65 2e 0a 09 43 6c 65 61 72 48 6f 6f 6b 73 0a ne...ClearHooks.
0f10: 0a 09 23 20 52 65 72 65 61 64 20 74 68 65 20 67 ..# Reread the g
0f20: 72 61 70 68 20 61 6e 64 20 64 75 6d 70 20 69 74 raph and dump it
0f30: 73 20 66 69 6e 61 6c 20 66 6f 72 6d 2c 20 69 66 s final form, if
0f40: 20 67 72 61 70 68 20 65 78 70 6f 72 74 0a 09 23 graph export..#
0f50: 20 77 61 73 20 61 63 74 69 76 61 74 65 64 2e 0a was activated..
0f60: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 ..::variable myd
0f70: 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 69 otdestination..i
0f80: 66 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 f {$mydotdestina
0f90: 74 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 75 tion eq ""} retu
0fa0: 72 6e 0a 0a 09 73 65 74 20 20 20 64 67 20 5b 53 rn...set dg [S
0fb0: 65 74 75 70 20 5b 75 70 6c 65 76 65 6c 20 23 30 etup [uplevel #0
0fc0: 20 24 63 68 61 6e 67 65 73 65 74 63 6d 64 5d 20 $changesetcmd]
0fd0: 30 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 64 6f 0]..Mark $dg -do
0fe0: 6e 65 0a 09 24 64 67 20 64 65 73 74 72 6f 79 0a ne..$dg destroy.
0ff0: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
1000: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
1010: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
1020: 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 ##########..
1030: 74 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 6b typemethod break
1040: 2d 73 65 67 6d 65 6e 74 20 7b 67 72 61 70 68 7d -segment {graph}
1050: 20 7b 0a 09 42 72 65 61 6b 53 65 67 6d 65 6e 74 {..BreakSegment
1060: 20 24 67 72 61 70 68 20 24 70 61 74 68 20 22 73 $graph $path "s
1070: 65 67 6d 65 6e 74 20 28 5b 70 72 6f 6a 65 63 74 egment ([project
1080: 3a 3a 72 65 76 20 73 74 72 6c 69 73 74 20 24 70 ::rev strlist $p
1090: 61 74 68 5d 29 22 0a 09 72 65 74 75 72 6e 0a 20 ath])"..return.
10a0: 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 }.. typeme
10b0: 74 68 6f 64 20 62 72 65 61 6b 20 7b 67 72 61 70 thod break {grap
10c0: 68 7d 20 7b 0a 09 73 65 74 20 63 79 63 6c 65 20 h} {..set cycle
10d0: 5b 46 69 6e 64 43 79 63 6c 65 20 24 67 72 61 70 [FindCycle $grap
10e0: 68 5d 0a 09 73 65 74 20 6c 61 62 65 6c 20 22 63 h]..set label "c
10f0: 79 63 6c 65 20 28 5b 70 72 6f 6a 65 63 74 3a 3a ycle ([project::
1100: 72 65 76 20 73 74 72 6c 69 73 74 20 24 63 79 63 rev strlist $cyc
1110: 6c 65 5d 29 22 0a 0a 09 23 20 4e 4f 54 45 3a 20 le])"...# NOTE:
1120: 63 76 73 32 73 76 6e 20 75 73 65 73 20 74 68 65 cvs2svn uses the
1130: 20 73 65 71 75 65 6e 63 65 20 22 65 6e 64 2d 31 sequence "end-1
1140: 2c 20 63 79 63 6c 65 2c 20 30 22 20 74 6f 20 63 , cycle, 0" to c
1150: 72 65 61 74 65 0a 09 23 20 20 20 20 20 20 20 74 reate..# t
1160: 68 65 20 70 61 74 68 20 66 72 6f 6d 20 74 68 65 he path from the
1170: 20 63 79 63 6c 65 2e 20 54 68 65 20 6f 6e 6c 79 cycle. The only
1180: 20 65 66 66 65 63 74 20 49 20 63 61 6e 20 73 65 effect I can se
1190: 65 20 69 73 0a 09 23 20 20 20 20 20 20 20 74 68 e is..# th
11a0: 61 74 20 74 68 69 73 20 63 61 75 73 65 73 20 74 at this causes t
11b0: 68 65 20 6c 69 6e 6b 2d 74 72 69 70 6c 65 73 20 he link-triples
11c0: 74 6f 20 62 65 20 67 65 6e 65 72 61 74 65 64 20 to be generated
11d0: 69 6e 20 61 0a 09 23 20 20 20 20 20 20 20 73 69 in a..# si
11e0: 67 68 74 6c 79 20 64 69 66 66 65 72 65 6e 74 20 ghtly different
11f0: 6f 72 64 65 72 2c 20 69 2e 65 2e 20 6f 6e 65 20 order, i.e. one
1200: 6c 69 6e 6b 20 72 6f 74 61 74 65 64 20 74 6f 20 link rotated to
1210: 74 68 65 0a 09 23 20 20 20 20 20 20 20 72 69 67 the..# rig
1220: 68 74 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 20 ht. This should
1230: 68 61 76 65 20 6e 6f 20 65 66 66 65 63 74 20 6f have no effect o
1240: 6e 20 74 68 65 20 73 65 61 72 63 68 20 66 6f 72 n the search for
1250: 0a 09 23 20 20 20 20 20 20 20 74 68 65 20 62 65 ..# the be
1260: 73 74 20 6f 66 20 61 6c 6c 2e 0a 0a 09 6c 61 70 st of all....lap
1270: 70 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 6e 64 pend cycle [lind
1280: 65 78 20 24 63 79 63 6c 65 20 30 5d 20 5b 6c 69 ex $cycle 0] [li
1290: 6e 64 65 78 20 24 63 79 63 6c 65 20 31 5d 0a 09 ndex $cycle 1]..
12a0: 42 72 65 61 6b 53 65 67 6d 65 6e 74 20 24 67 72 BreakSegment $gr
12b0: 61 70 68 20 24 63 79 63 6c 65 20 24 6c 61 62 65 aph $cycle $labe
12c0: 6c 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a l..return. }.
12d0: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
12e0: 72 65 70 6c 61 63 65 20 7b 67 72 61 70 68 20 6e replace {graph n
12f0: 20 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b replacements} {
1300: 0a 09 52 65 70 6c 61 63 65 20 24 67 72 61 70 68 ..Replace $graph
1310: 20 24 6e 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 $n $replacement
1320: 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a s..return. }.
1330: 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 . # # ## ###
1340: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
1350: 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 ############.
1360: 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d 65 74 ## Internal met
1370: 68 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 20 53 hods.. proc S
1380: 65 74 75 70 20 7b 63 68 61 6e 67 65 73 65 74 73 etup {changesets
1390: 20 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 66 20 {log 1}} {..if
13a0: 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f {$log} {.. lo
13b0: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
13c0: 72 65 61 6b 65 72 20 22 43 72 65 61 74 69 6e 67 reaker "Creating
13d0: 20 67 72 61 70 68 20 6f 66 20 63 68 61 6e 67 65 graph of change
13e0: 73 65 74 73 22 0a 09 7d 0a 0a 09 73 65 74 20 64 sets"..}...set d
13f0: 67 20 5b 73 74 72 75 63 74 3a 3a 67 72 61 70 68 g [struct::graph
1400: 20 64 67 5d 0a 0a 09 73 65 74 20 6e 20 30 0a 09 dg]...set n 0..
1410: 73 65 74 20 6d 61 78 20 5b 6c 6c 65 6e 67 74 68 set max [llength
1420: 20 24 63 68 61 6e 67 65 73 65 74 73 5d 0a 0a 09 $changesets]...
1430: 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 63 68 foreach cset $ch
1440: 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 20 20 angesets {..
1450: 6c 6f 67 20 70 72 6f 67 72 65 73 73 20 32 20 63 log progress 2 c
1460: 79 63 6c 65 62 72 65 61 6b 65 72 20 24 6e 20 24 yclebreaker $n $
1470: 6d 61 78 0a 09 20 20 20 20 73 65 74 20 74 72 20 max.. set tr
1480: 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 [$cset timerange
1490: 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 ].. $dg node
14a0: 69 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 insert $cset..
14b0: 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 $dg node set
14c0: 20 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 $cset timerang
14d0: 65 20 24 74 72 0a 09 20 20 20 20 24 64 67 20 6e e $tr.. $dg n
14e0: 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 ode set $cset
14f0: 20 6c 61 62 65 6c 20 20 20 20 20 22 5b 24 63 73 label "[$cs
1500: 65 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e 20 et str]\\n[join
1510: 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d 61 [struct::list ma
1520: 70 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 66 p $tr {::clock f
1530: 6f 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 0a ormat}] "\\n"]".
1540: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
1550: 74 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f t $cset __id_
1560: 5f 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a _ [$cset id].
1570: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
1580: 74 20 20 20 20 24 63 73 65 74 20 73 68 61 70 65 t $cset shape
1590: 20 20 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 73 [expr {[$cs
15a0: 65 74 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 09 et bysymbol]....
15b0: 09 09 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 65 ... ? "ellipse
15c0: 22 0a 09 09 09 09 09 09 20 20 20 3a 20 22 62 6f "....... : "bo
15d0: 78 22 7d 5d 0a 09 20 20 20 20 69 6e 63 72 20 6e x"}].. incr n
15e0: 0a 09 7d 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 ..}...if {$log}
15f0: 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 {.. log write
1600: 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 3 cyclebreaker
1610: 22 48 61 73 20 5b 6e 73 70 20 5b 6c 6c 65 6e 67 "Has [nsp [lleng
1620: 74 68 20 24 63 68 61 6e 67 65 73 65 74 73 5d 20 th $changesets]
1630: 63 68 61 6e 67 65 73 65 74 5d 22 0a 09 7d 0a 0a changeset]"..}..
1640: 09 23 20 32 2e 20 46 69 6e 64 20 66 6f 72 20 61 .# 2. Find for a
1650: 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e ll relevant chan
1660: 67 65 73 65 74 20 74 68 65 69 72 20 72 65 76 69 geset their revi
1670: 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 69 72 0a sions and their.
1680: 09 23 20 20 20 20 64 65 70 65 6e 64 65 6e 63 69 .# dependenci
1690: 65 73 2e 20 4d 61 70 20 74 68 65 20 6c 61 74 74 es. Map the latt
16a0: 65 72 20 62 61 63 6b 20 74 6f 20 63 68 61 6e 67 er back to chang
16b0: 65 73 65 74 73 20 61 6e 64 0a 09 23 20 20 20 20 esets and..#
16c0: 63 6f 6e 73 74 72 75 63 74 20 74 68 65 20 63 6f construct the co
16d0: 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 72 63 73 rresponding arcs
16e0: 2e 0a 0a 09 73 65 74 20 6e 20 30 0a 09 66 6f 72 ....set n 0..for
16f0: 65 61 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 each cset $chang
1700: 65 73 65 74 73 20 7b 0a 09 20 20 20 20 6c 6f 67 esets {.. log
1710: 20 70 72 6f 67 72 65 73 73 20 32 20 63 79 63 6c progress 2 cycl
1720: 65 62 72 65 61 6b 65 72 20 24 6e 20 24 6d 61 78 ebreaker $n $max
1730: 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 .. foreach su
1740: 63 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 cc [$cset succes
1750: 73 6f 72 73 5d 20 7b 0a 09 09 23 20 43 68 61 6e sors] {...# Chan
1760: 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 gesets may have
1770: 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 dependencies out
1780: 73 69 64 65 20 6f 66 20 74 68 65 0a 09 09 23 20 side of the...#
1790: 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 chosen set. Thes
17a0: 65 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 e are ignored...
17b0: 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 if {![$dg node e
17c0: 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f xists $succ]} co
17d0: 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 ntinue...$dg arc
17e0: 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 insert $cset $s
17f0: 75 63 63 0a 09 09 69 6e 74 65 67 72 69 74 79 20 ucc...integrity
1800: 61 73 73 65 72 74 20 7b 0a 09 09 20 20 20 20 24 assert {... $
1810: 73 75 63 63 20 6e 65 20 24 63 73 65 74 0a 09 09 succ ne $cset...
1820: 7d 20 7b 5b 24 63 73 65 74 20 72 65 70 6f 72 74 } {[$cset report
1830: 6c 6f 6f 70 20 30 5d 43 68 61 6e 67 65 73 65 74 loop 0]Changeset
1840: 20 6c 6f 6f 70 20 77 61 73 20 6e 6f 74 20 64 65 loop was not de
1850: 74 65 63 74 65 64 20 64 75 72 69 6e 67 20 63 72 tected during cr
1860: 65 61 74 69 6f 6e 7d 0a 09 20 20 20 20 7d 0a 09 eation}.. }..
1870: 20 20 20 20 69 6e 63 72 20 6e 0a 09 7d 0a 0a 09 incr n..}...
1880: 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 if {$log} {..
1890: 20 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 log write 3 cyc
18a0: 6c 65 62 72 65 61 6b 65 72 20 22 48 61 73 20 5b lebreaker "Has [
18b0: 6e 73 70 20 5b 6c 6c 65 6e 67 74 68 20 5b 24 64 nsp [llength [$d
18c0: 67 20 61 72 63 73 5d 5d 20 64 65 70 65 6e 64 65 g arcs]] depende
18d0: 6e 63 79 20 64 65 70 65 6e 64 65 6e 63 69 65 73 ncy dependencies
18e0: 5d 22 0a 09 7d 0a 0a 09 23 20 52 75 6e 20 74 68 ]"..}...# Run th
18f0: 65 20 75 73 65 72 20 68 6f 6f 6b 20 74 6f 20 6d e user hook to m
1900: 61 6e 69 70 75 6c 61 74 65 20 74 68 65 20 67 72 anipulate the gr
1910: 61 70 68 20 62 65 66 6f 72 65 0a 09 23 20 63 6f aph before..# co
1920: 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 69 66 nsummation....if
1930: 20 7b 24 6c 6f 67 7d 20 7b 20 4d 61 72 6b 20 24 {$log} { Mark $
1940: 64 67 20 2d 73 74 61 72 74 20 7d 0a 09 4d 61 72 dg -start }..Mar
1950: 6b 57 61 74 63 68 20 24 64 67 0a 09 50 72 65 48 kWatch $dg..PreH
1960: 6f 6f 6b 20 20 20 24 64 67 0a 09 4d 61 72 6b 57 ook $dg..MarkW
1970: 61 74 63 68 20 24 64 67 0a 09 72 65 74 75 72 6e atch $dg..return
1980: 20 20 24 64 67 0a 20 20 20 20 7d 0a 0a 20 20 20 $dg. }..
1990: 20 23 20 49 6e 73 74 65 61 64 20 6f 66 20 73 65 # Instead of se
19a0: 61 72 63 68 69 6e 67 20 74 68 65 20 77 68 6f 6c arching the whol
19b0: 65 20 67 72 61 70 68 20 66 6f 72 20 74 68 65 20 e graph for the
19c0: 64 65 67 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 degree-0 nodes i
19d0: 6e 0a 20 20 20 20 23 20 65 61 63 68 20 69 74 65 n. # each ite
19e0: 72 61 74 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 ration we comput
19f0: 65 20 74 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 e the list once
1a00: 74 6f 20 73 74 61 72 74 2c 20 61 6e 64 20 74 68 to start, and th
1a10: 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 en only. # up
1a20: 64 61 74 65 20 69 74 20 69 6e 63 72 65 6d 65 6e date it incremen
1a30: 74 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 tally based on t
1a40: 68 65 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 he outgoing neig
1a50: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 0a 20 20 hbours of the.
1a60: 20 20 23 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 # node chosen
1a70: 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 for commit...
1a80: 20 70 72 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 proc Initialize
1a90: 43 61 6e 64 69 64 61 74 65 73 20 7b 64 67 7d 20 Candidates {dg}
1aa0: 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 {..# bottom = li
1ab0: 73 74 20 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 st (list (node,
1ac0: 72 61 6e 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 range min, range
1ad0: 20 6d 61 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 max))..::variab
1ae0: 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 66 6f 72 le mybottom..for
1af0: 65 61 63 68 20 6e 20 5b 24 64 67 20 6e 6f 64 65 each n [$dg node
1b00: 73 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 s] {.. if {[$
1b10: 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d dg node degree -
1b20: 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 in $n]} continue
1b30: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 .. lappend my
1b40: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
1b50: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6e [$dg node get $n
1b60: 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6e timerange] 0 $n
1b70: 5d 0a 09 7d 0a 09 53 63 68 65 64 75 6c 65 43 61 ]..}..ScheduleCa
1b80: 6e 64 69 64 61 74 65 73 0a 09 53 68 6f 77 50 65 ndidates..ShowPe
1b90: 6e 64 69 6e 67 4e 6f 64 65 73 0a 09 72 65 74 75 ndingNodes..retu
1ba0: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
1bb0: 6f 63 20 57 69 74 68 6f 75 74 50 72 65 64 65 63 oc WithoutPredec
1bc0: 65 73 73 6f 72 20 7b 64 67 20 6e 76 7d 20 7b 0a essor {dg nv} {.
1bd0: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f .::variable mybo
1be0: 74 74 6f 6d 0a 0a 09 75 70 76 61 72 20 31 20 24 ttom...upvar 1 $
1bf0: 6e 76 20 6e 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e nv n..if {![llen
1c00: 67 74 68 20 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 gth $mybottom]}
1c10: 7b 20 72 65 74 75 72 6e 20 30 20 7d 0a 0a 09 73 { return 0 }...s
1c20: 65 74 20 6e 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 et n [lindex [li
1c30: 6e 64 65 78 20 24 6d 79 62 6f 74 74 6f 6d 20 30 ndex $mybottom 0
1c40: 5d 20 30 5d 0a 09 73 65 74 20 6d 79 62 6f 74 74 ] 0]..set mybott
1c50: 6f 6d 20 5b 6c 72 61 6e 67 65 20 24 6d 79 62 6f om [lrange $mybo
1c60: 74 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 65 74 ttom 1 end]..set
1c70: 20 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 20 55 changed 0...# U
1c80: 70 64 61 74 65 20 6c 69 73 74 20 6f 66 20 6e 6f pdate list of no
1c90: 64 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 64 des without pred
1ca0: 65 63 65 73 73 6f 72 2c 20 62 61 73 65 64 20 6f ecessor, based o
1cb0: 6e 20 74 68 65 0a 09 23 20 6f 75 74 67 6f 69 6e n the..# outgoin
1cc0: 67 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 g neighbours of
1cd0: 74 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 65 2e the chosen node.
1ce0: 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 0a This should be.
1cf0: 09 23 20 66 61 73 74 65 72 20 74 68 61 6e 20 69 .# faster than i
1d00: 74 65 72 61 74 69 6e 67 20 6f 66 20 74 68 65 20 terating of the
1d10: 77 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e 6f 64 whole set of nod
1d20: 65 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c 6c 0a es, finding all.
1d30: 09 23 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 .# without prede
1d40: 63 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 6e 67 cessors, sorting
1d50: 20 74 68 65 6d 20 62 79 20 74 69 6d 65 2c 20 65 them by time, e
1d60: 74 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 63 68 tc. pp...foreach
1d70: 20 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 out [$dg nodes
1d80: 2d 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 20 20 -out $n] {..
1d90: 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 if {[$dg node de
1da0: 67 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d 20 3e gree -in $out] >
1db0: 20 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 1} continue..
1dc0: 20 20 23 20 44 65 67 72 65 65 2d 31 20 6e 65 69 # Degree-1 nei
1dd0: 67 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 61 76 ghbour, will hav
1de0: 65 20 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 e no predecessor
1df0: 73 20 61 66 74 65 72 20 74 68 65 0a 09 20 20 20 s after the..
1e00: 20 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e # removal of n.
1e10: 20 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 73 74 Put on the list
1e20: 2e 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d ... lappend m
1e30: 79 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 ybottom [linsert
1e40: 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 [$dg node get $
1e50: 6f 75 74 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 out timerange] 0
1e60: 20 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 74 20 $out].. set
1e70: 63 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 69 66 changed 1..}..if
1e80: 20 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a 09 20 {$changed} {..
1e90: 20 20 20 53 63 68 65 64 75 6c 65 43 61 6e 64 69 ScheduleCandi
1ea0: 64 61 74 65 73 0a 09 7d 0a 0a 09 23 20 57 65 20 dates..}...# We
1eb0: 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 20 74 68 do not delete th
1ec0: 65 20 6e 6f 64 65 20 69 6d 6d 65 64 69 61 74 65 e node immediate
1ed0: 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 68 65 ly, to allow the
1ee0: 20 53 61 76 65 0a 09 23 20 70 72 6f 63 65 64 75 Save..# procedu
1ef0: 72 65 20 74 6f 20 73 61 76 65 20 74 68 65 20 64 re to save the d
1f00: 65 70 65 6e 64 65 6e 63 69 65 73 20 61 73 20 77 ependencies as w
1f10: 65 6c 6c 20 28 65 6e 63 6f 64 65 64 20 69 6e 20 ell (encoded in
1f20: 74 68 65 0a 09 23 20 61 72 63 73 29 2e 0a 09 72 the..# arcs)...r
1f30: 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 eturn 1. }..
1f40: 20 20 20 70 72 6f 63 20 53 63 68 65 64 75 6c 65 proc Schedule
1f50: 43 61 6e 64 69 64 61 74 65 73 20 7b 7d 20 7b 0a Candidates {} {.
1f60: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f .::variable mybo
1f70: 74 74 6f 6d 0a 09 23 20 53 6f 72 74 20 62 79 20 ttom..# Sort by
1f80: 63 73 65 74 20 6f 62 6a 65 63 74 20 6e 61 6d 65 cset object name
1f90: 2c 20 6c 6f 77 65 72 20 62 6f 72 64 65 72 20 6f , lower border o
1fa0: 66 20 74 69 6d 65 72 61 6e 67 65 2c 20 61 74 20 f timerange, at
1fb0: 6c 61 73 74 0a 09 23 20 62 79 20 74 68 65 20 75 last..# by the u
1fc0: 70 70 65 72 20 62 6f 72 64 65 72 2e 0a 09 73 65 pper border...se
1fd0: 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 t mybottom [lsor
1fe0: 74 20 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 t -index 2 -inte
1ff0: 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 ger [lsort -inde
2000: 78 20 31 20 2d 69 6e 74 65 67 65 72 20 5b 6c 73 x 1 -integer [ls
2010: 6f 72 74 20 2d 69 6e 64 65 78 20 30 20 2d 64 69 ort -index 0 -di
2020: 63 74 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d 5d 0a ct $mybottom]]].
2030: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
2040: 20 20 20 70 72 6f 63 20 53 68 6f 77 50 65 6e 64 proc ShowPend
2050: 69 6e 67 4e 6f 64 65 73 20 7b 7d 20 7b 0a 09 69 ingNodes {} {..i
2060: 66 20 7b 5b 6c 6f 67 20 76 65 72 62 6f 73 69 74 f {[log verbosit
2070: 79 3f 5d 20 3c 20 31 30 7d 20 72 65 74 75 72 6e y?] < 10} return
2080: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 ..::variable myb
2090: 6f 74 74 6f 6d 0a 09 6c 6f 67 20 77 72 69 74 65 ottom..log write
20a0: 20 31 30 20 63 79 63 6c 65 62 72 65 61 6b 65 72 10 cyclebreaker
20b0: 20 22 50 65 6e 64 69 6e 67 2e 2e 2e 2e 2e 2e 2e "Pending.......
20c0: 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ................
20d0: 2e 2e 2e 2e 2e 2e 2e 2e 22 0a 09 66 6f 72 65 61 ........"..forea
20e0: 63 68 20 69 74 65 6d 20 5b 73 74 72 75 63 74 3a ch item [struct:
20f0: 3a 6c 69 73 74 20 6d 61 70 20 24 6d 79 62 6f 74 :list map $mybot
2100: 74 6f 6d 20 5b 6d 79 70 72 6f 63 20 46 6f 72 6d tom [myproc Form
2110: 61 74 50 65 6e 64 69 6e 67 49 74 65 6d 5d 5d 20 atPendingItem]]
2120: 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 {.. log write
2130: 20 31 30 20 63 79 63 6c 65 62 72 65 61 6b 65 72 10 cyclebreaker
2140: 20 22 50 65 6e 64 69 6e 67 3a 20 20 20 20 20 24 "Pending: $
2150: 69 74 65 6d 22 0a 09 7d 0a 09 72 65 74 75 72 6e item"..}..return
2160: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
2170: 20 46 6f 72 6d 61 74 50 65 6e 64 69 6e 67 49 74 FormatPendingIt
2180: 65 6d 20 7b 69 74 65 6d 7d 20 7b 0a 09 6a 6f 69 em {item} {..joi
2190: 6e 20 5b 6c 69 73 74 20 5b 5b 6c 69 6e 64 65 78 n [list [[lindex
21a0: 20 24 69 74 65 6d 20 30 5d 20 73 74 72 5d 20 5b $item 0] str] [
21b0: 63 6c 6f 63 6b 20 66 6f 72 6d 61 74 20 5b 6c 69 clock format [li
21c0: 6e 64 65 78 20 24 69 74 65 6d 20 31 5d 5d 20 5b ndex $item 1]] [
21d0: 63 6c 6f 63 6b 20 66 6f 72 6d 61 74 20 5b 6c 69 clock format [li
21e0: 6e 64 65 78 20 24 69 74 65 6d 20 32 5d 5d 5d 0a ndex $item 2]]].
21f0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
2200: 46 69 6e 64 43 79 63 6c 65 20 7b 64 67 7d 20 7b FindCycle {dg} {
2210: 0a 09 23 20 54 68 69 73 20 70 72 6f 63 65 64 75 ..# This procedu
2220: 72 65 20 69 73 20 72 75 6e 20 69 66 20 61 6e 64 re is run if and
2230: 20 6f 6e 6c 79 20 74 68 65 20 67 72 61 70 68 20 only the graph
2240: 69 73 20 6e 6f 74 20 65 6d 70 74 79 20 61 6e 64 is not empty and
2250: 0a 09 23 20 61 6c 6c 20 6e 6f 64 65 73 20 68 61 ..# all nodes ha
2260: 76 65 20 70 72 65 64 65 63 65 73 73 6f 72 73 2e ve predecessors.
2270: 20 54 68 69 73 20 6d 65 61 6e 73 20 74 68 61 74 This means that
2280: 20 65 61 63 68 20 6e 6f 64 65 20 69 73 0a 09 23 each node is..#
2290: 20 65 69 74 68 65 72 20 70 61 72 74 20 6f 66 20 either part of
22a0: 61 20 63 79 63 6c 65 20 6f 72 20 28 69 6e 64 69 a cycle or (indi
22b0: 72 65 63 74 6c 79 29 20 64 65 70 65 6e 64 69 6e rectly) dependin
22c0: 67 20 6f 6e 20 61 20 6e 6f 64 65 0a 09 23 20 69 g on a node..# i
22d0: 6e 20 61 20 63 79 63 6c 65 2e 20 57 65 20 63 61 n a cycle. We ca
22e0: 6e 20 73 74 61 72 74 20 61 74 20 61 6e 20 61 72 n start at an ar
22f0: 62 69 74 72 61 72 79 20 6e 6f 64 65 2c 20 66 6f bitrary node, fo
2300: 6c 6c 6f 77 20 69 74 73 0a 09 23 20 69 6e 63 6f llow its..# inco
2310: 6d 69 6e 67 20 65 64 67 65 73 20 74 6f 20 69 74 ming edges to it
2320: 73 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 75 s predecessors u
2330: 6e 74 69 6c 20 77 65 20 73 65 65 20 61 20 6e 6f ntil we see a no
2340: 64 65 20 61 0a 09 23 20 73 65 63 6f 6e 64 20 74 de a..# second t
2350: 69 6d 65 2e 20 54 68 61 74 20 6e 6f 64 65 20 63 ime. That node c
2360: 6c 6f 73 65 73 20 74 68 65 20 63 79 63 6c 65 20 loses the cycle
2370: 61 6e 64 20 74 68 65 20 62 65 67 69 6e 6e 69 6e and the beginnin
2380: 67 20 69 73 0a 09 23 20 69 74 73 20 66 69 72 73 g is..# its firs
2390: 74 20 6f 63 63 75 72 65 6e 63 65 2e 20 4e 6f 74 t occurence. Not
23a0: 65 20 74 68 61 74 20 77 65 20 63 61 6e 20 63 68 e that we can ch
23b0: 6f 6f 73 65 20 61 6e 20 61 72 62 69 74 72 61 72 oose an arbitrar
23c0: 79 0a 09 23 20 70 72 65 64 65 63 65 73 73 6f 72 y..# predecessor
23d0: 20 6f 66 20 65 61 63 68 20 6e 6f 64 65 20 61 73 of each node as
23e0: 20 77 65 6c 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 well, we do not
23f0: 20 68 61 76 65 20 74 6f 20 73 65 61 72 63 68 2e have to search.
2400: 0a 0a 09 23 20 57 65 20 72 65 63 6f 72 64 20 66 ...# We record f
2410: 6f 72 20 65 61 63 68 20 6e 6f 64 65 20 74 68 65 or each node the
2420: 20 69 6e 64 65 78 20 6f 66 20 74 68 65 20 66 69 index of the fi
2430: 72 73 74 20 61 70 70 65 61 72 61 6e 63 65 20 69 rst appearance i
2440: 6e 0a 09 23 20 74 68 65 20 70 61 74 68 2c 20 6d n..# the path, m
2450: 61 6b 69 6e 67 20 69 74 20 65 61 73 79 20 61 74 aking it easy at
2460: 20 74 68 65 20 65 6e 64 20 74 6f 20 63 75 74 20 the end to cut
2470: 74 68 65 20 63 79 63 6c 65 20 66 72 6f 6d 0a 09 the cycle from..
2480: 23 20 69 74 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 # it....# Choose
2490: 20 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65 20 arbitrary node
24a0: 74 6f 20 73 74 61 72 74 20 6f 75 72 20 73 65 61 to start our sea
24b0: 72 63 68 20 61 74 2e 0a 09 73 65 74 20 73 74 61 rch at...set sta
24c0: 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 rt [lindex [$dg
24d0: 6e 6f 64 65 73 5d 20 30 5d 0a 0a 09 23 20 49 6e nodes] 0]...# In
24e0: 69 74 69 61 6c 69 7a 65 20 73 74 61 74 65 2c 20 itialize state,
24f0: 70 61 74 68 20 6f 66 20 73 65 65 6e 20 6e 6f 64 path of seen nod
2500: 65 73 2c 20 61 6e 64 20 77 68 65 6e 20 73 65 65 es, and when see
2510: 6e 2e 0a 09 73 65 74 20 20 20 20 20 20 20 70 61 n...set pa
2520: 74 68 20 7b 7d 0a 09 61 72 72 61 79 20 73 65 74 th {}..array set
2530: 20 73 65 65 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 seen {}...while
2540: 20 7b 31 7d 20 7b 0a 09 20 20 20 20 23 20 53 74 {1} {.. # St
2550: 6f 70 20 73 65 61 72 63 68 69 6e 67 20 77 68 65 op searching whe
2560: 6e 20 77 65 20 68 61 76 65 20 73 65 65 6e 20 74 n we have seen t
2570: 68 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 0a he current node.
2580: 09 20 20 20 20 23 20 61 6c 72 65 61 64 79 2c 20 . # already,
2590: 74 68 65 20 63 69 72 63 6c 65 20 68 61 73 20 62 the circle has b
25a0: 65 65 6e 20 63 6c 6f 73 65 64 2e 0a 09 20 20 20 een closed...
25b0: 20 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 73 74 if {[info exist
25c0: 73 20 73 65 65 6e 28 24 73 74 61 72 74 29 5d 7d s seen($start)]}
25d0: 20 62 72 65 61 6b 0a 09 20 20 20 20 6c 61 70 70 break.. lapp
25e0: 65 6e 64 20 70 61 74 68 20 24 73 74 61 72 74 0a end path $start.
25f0: 09 20 20 20 20 73 65 74 20 73 65 65 6e 28 24 73 . set seen($s
2600: 74 61 72 74 29 20 5b 65 78 70 72 20 7b 5b 6c 6c tart) [expr {[ll
2610: 65 6e 67 74 68 20 24 70 61 74 68 5d 2d 31 7d 5d ength $path]-1}]
2620: 0a 09 20 20 20 20 23 20 43 68 6f 6f 73 65 20 61 .. # Choose a
2630: 72 62 69 74 72 61 72 79 20 70 72 65 64 65 63 65 rbitrary predece
2640: 73 73 6f 72 0a 09 20 20 20 20 73 65 74 20 73 74 ssor.. set st
2650: 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 art [lindex [$dg
2660: 20 6e 6f 64 65 73 20 2d 69 6e 20 24 73 74 61 72 nodes -in $star
2670: 74 5d 20 30 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 t] 0]..}...retur
2680: 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 n [struct::list
2690: 72 65 76 65 72 73 65 20 5b 6c 72 61 6e 67 65 20 reverse [lrange
26a0: 24 70 61 74 68 20 24 73 65 65 6e 28 24 73 74 61 $path $seen($sta
26b0: 72 74 29 20 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a rt) end]]. }.
26c0: 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 53 . proc BreakS
26d0: 65 67 6d 65 6e 74 20 7b 64 67 20 70 61 74 68 20 egment {dg path
26e0: 6c 61 62 65 6c 7d 20 7b 0a 09 23 20 54 68 65 20 label} {..# The
26f0: 70 61 74 68 2c 20 75 73 75 61 6c 6c 79 20 61 20 path, usually a
2700: 63 79 63 6c 65 2c 20 77 65 20 68 61 76 65 20 67 cycle, we have g
2710: 6f 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 6e 20 otten is broken
2720: 62 79 0a 09 23 20 62 72 65 61 6b 69 6e 67 20 61 by..# breaking a
2730: 70 61 72 74 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 part one or more
2740: 20 6f 66 20 74 68 65 20 63 68 61 6e 67 65 73 65 of the changese
2750: 74 73 20 69 6e 20 74 68 65 0a 09 23 20 63 79 63 ts in the..# cyc
2760: 6c 65 2e 20 54 68 69 73 20 63 61 75 73 65 73 20 le. This causes
2770: 75 73 20 74 6f 20 63 72 65 61 74 65 20 6f 6e 65 us to create one
2780: 20 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 65 73 or more changes
2790: 65 74 73 20 77 68 69 63 68 0a 09 23 20 61 72 65 ets which..# are
27a0: 20 74 6f 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 to be committed
27b0: 2c 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 67 , added to the g
27c0: 72 61 70 68 2c 20 65 74 63 2e 20 70 70 2e 0a 0a raph, etc. pp...
27d0: 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 7b 7d .set bestlink {}
27e0: 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 65 20 7b ..set bestnode {
27f0: 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c 0a 09 20 }...foreach \..
2800: 20 20 20 70 72 65 76 20 5b 6c 72 61 6e 67 65 20 prev [lrange
2810: 24 70 61 74 68 20 30 20 65 6e 64 2d 32 5d 20 5c $path 0 end-2] \
2820: 0a 09 20 20 20 20 63 73 65 74 20 5b 6c 72 61 6e .. cset [lran
2830: 67 65 20 24 70 61 74 68 20 31 20 65 6e 64 2d 31 ge $path 1 end-1
2840: 5d 20 5c 0a 09 20 20 20 20 6e 65 78 74 20 5b 6c ] \.. next [l
2850: 72 61 6e 67 65 20 24 70 61 74 68 20 32 20 65 6e range $path 2 en
2860: 64 5d 20 7b 0a 0a 09 09 23 20 45 61 63 68 20 74 d] {....# Each t
2870: 72 69 70 6c 65 20 50 52 45 56 20 2d 3e 20 43 53 riple PREV -> CS
2880: 45 54 20 2d 3e 20 4e 45 58 54 20 6f 66 20 63 68 ET -> NEXT of ch
2890: 61 6e 67 65 73 65 74 73 2c 20 61 0a 09 09 23 20 angesets, a...#
28a0: 27 6c 69 6e 6b 27 20 69 6e 20 74 68 65 20 63 79 'link' in the cy
28b0: 63 6c 65 2c 20 69 73 20 61 6e 61 6c 79 73 65 64 cle, is analysed
28c0: 20 61 6e 64 20 74 68 65 20 62 65 73 74 0a 09 09 and the best...
28d0: 23 20 6c 6f 63 61 74 69 6f 6e 20 77 68 65 72 65 # location where
28e0: 20 74 6f 20 61 74 20 6c 65 61 73 74 20 77 65 61 to at least wea
28f0: 6b 65 6e 20 74 68 65 20 63 79 63 6c 65 20 69 73 ken the cycle is
2900: 0a 09 09 23 20 63 68 6f 73 65 6e 20 66 6f 72 20 ...# chosen for
2910: 66 75 72 74 68 65 72 20 70 72 6f 63 65 73 73 69 further processi
2920: 6e 67 2e 0a 0a 09 09 73 65 74 20 6c 69 6e 6b 20 ng.....set link
2930: 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e [project::revlin
2940: 6b 20 25 41 55 54 4f 25 20 24 70 72 65 76 20 24 k %AUTO% $prev $
2950: 63 73 65 74 20 24 6e 65 78 74 5d 0a 09 09 69 66 cset $next]...if
2960: 20 7b 24 62 65 73 74 6c 69 6e 6b 20 65 71 20 22 {$bestlink eq "
2970: 22 7d 20 7b 0a 09 09 20 20 20 20 73 65 74 20 62 "} {... set b
2980: 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 estlink $link...
2990: 20 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 set bestnode
29a0: 20 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 69 $cset...} elsei
29b0: 66 20 7b 5b 24 6c 69 6e 6b 20 62 65 74 74 65 72 f {[$link better
29c0: 74 68 61 6e 20 24 62 65 73 74 6c 69 6e 6b 5d 7d than $bestlink]}
29d0: 20 7b 0a 09 09 20 20 20 20 24 62 65 73 74 6c 69 {... $bestli
29e0: 6e 6b 20 64 65 73 74 72 6f 79 0a 09 09 20 20 20 nk destroy...
29f0: 20 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c set bestlink $l
2a00: 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 ink... set be
2a10: 73 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d stnode $cset...}
2a20: 20 65 6c 73 65 20 7b 0a 09 09 20 20 20 20 24 6c else {... $l
2a30: 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 09 7d 0a ink destroy...}.
2a40: 09 20 20 20 20 7d 0a 0a 09 6c 6f 67 20 77 72 69 . }...log wri
2a50: 74 65 20 35 20 63 79 63 6c 65 62 72 65 61 6b 65 te 5 cyclebreake
2a60: 72 20 22 42 72 65 61 6b 69 6e 67 20 24 6c 61 62 r "Breaking $lab
2a70: 65 6c 20 62 79 20 73 70 6c 69 74 74 69 6e 67 20 el by splitting
2a80: 63 68 61 6e 67 65 73 65 74 20 5b 24 62 65 73 74 changeset [$best
2a90: 6e 6f 64 65 20 73 74 72 5d 22 0a 09 73 65 74 20 node str]"..set
2aa0: 49 44 20 5b 24 62 65 73 74 6e 6f 64 65 20 69 64 ID [$bestnode id
2ab0: 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 ]..Mark $dg -${I
2ac0: 44 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 65 74 20 D}-before...set
2ad0: 6e 65 77 63 73 65 74 73 20 5b 24 62 65 73 74 6c newcsets [$bestl
2ae0: 69 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 ink break]..$bes
2af0: 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 tlink destroy..
2b00: 20 20 20 20 20 20 20 23 20 41 74 20 74 68 69 73 # At this
2b10: 20 70 6f 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 point the old c
2b20: 68 61 6e 67 65 73 65 74 20 28 42 45 53 54 4e 4f hangeset (BESTNO
2b30: 44 45 29 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 DE) is gone.
2b40: 20 20 20 20 23 20 61 6c 72 65 61 64 79 2e 20 57 # already. W
2b50: 65 20 72 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d e remove it from
2b60: 20 74 68 65 20 67 72 61 70 68 20 61 73 20 77 65 the graph as we
2b70: 6c 6c 20 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 ll and then ente
2b80: 72 0a 20 20 20 20 20 20 20 20 23 20 74 68 65 20 r. # the
2b90: 66 72 61 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 fragments genera
2ba0: 74 65 64 20 66 6f 72 20 69 74 2e 0a 0a 09 52 65 ted for it....Re
2bb0: 70 6c 61 63 65 20 24 64 67 20 24 62 65 73 74 6e place $dg $bestn
2bc0: 6f 64 65 20 24 6e 65 77 63 73 65 74 73 0a 0a 09 ode $newcsets...
2bd0: 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d Mark $dg -${ID}-
2be0: 61 66 74 65 72 0a 09 72 65 74 75 72 6e 0a 20 20 after..return.
2bf0: 20 20 7d 0a 0a 20 20 20 20 23 20 54 4f 44 4f 3a }.. # TODO:
2c00: 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 20 This should be
2c10: 61 20 67 72 61 70 68 20 6d 65 74 68 6f 64 2e 0a a graph method..
2c20: 20 20 20 20 70 72 6f 63 20 48 61 73 41 72 63 20 proc HasArc
2c30: 7b 64 67 20 61 20 62 7d 20 7b 0a 09 23 38 2e 35 {dg a b} {..#8.5
2c40: 3a 20 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b : return [expr {
2c50: 24 62 20 69 6e 20 5b 24 64 67 20 6e 6f 64 65 73 $b in [$dg nodes
2c60: 20 2d 6f 75 74 20 24 61 5d 7d 5d 0a 09 69 66 20 -out $a]}]..if
2c70: 7b 5b 6c 73 65 61 72 63 68 20 2d 65 78 61 63 74 {[lsearch -exact
2c80: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
2c90: 20 24 61 5d 20 24 62 5d 20 3c 20 30 7d 20 7b 20 $a] $b] < 0} {
2ca0: 72 65 74 75 72 6e 20 30 20 7d 0a 09 72 65 74 75 return 0 }..retu
2cb0: 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 rn 1. }..
2cc0: 70 72 6f 63 20 4d 61 72 6b 20 7b 64 67 20 7b 73 proc Mark {dg {s
2cd0: 75 66 66 69 78 20 7b 7d 7d 20 7b 73 75 62 67 72 uffix {}} {subgr
2ce0: 61 70 68 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 aph {}}} {..::va
2cf0: 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 riable mydotdest
2d00: 69 6e 61 74 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 ination..if {$my
2d10: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 65 dotdestination e
2d20: 71 20 22 22 7d 20 72 65 74 75 72 6e 0a 09 3a 3a q ""} return..::
2d30: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 variable mydotpr
2d40: 65 66 69 78 0a 09 3a 3a 76 61 72 69 61 62 6c 65 efix..::variable
2d50: 20 6d 79 64 6f 74 69 64 0a 09 73 65 74 20 66 6e mydotid..set fn
2d60: 61 6d 65 20 24 6d 79 64 6f 74 64 65 73 74 69 6e ame $mydotdestin
2d70: 61 74 69 6f 6e 2f 24 7b 6d 79 64 6f 74 70 72 65 ation/${mydotpre
2d80: 66 69 78 7d 24 7b 6d 79 64 6f 74 69 64 7d 24 7b fix}${mydotid}${
2d90: 73 75 66 66 69 78 7d 2e 64 6f 74 0a 09 66 69 6c suffix}.dot..fil
2da0: 65 20 6d 6b 64 69 72 20 5b 66 69 6c 65 20 64 69 e mkdir [file di
2db0: 72 6e 61 6d 65 20 24 66 6e 61 6d 65 5d 0a 09 64 rname $fname]..d
2dc0: 6f 74 20 77 72 69 74 65 20 24 64 67 20 24 6d 79 ot write $dg $my
2dd0: 64 6f 74 70 72 65 66 69 78 24 73 75 66 66 69 78 dotprefix$suffix
2de0: 20 24 66 6e 61 6d 65 20 24 73 75 62 67 72 61 70 $fname $subgrap
2df0: 68 0a 09 69 6e 63 72 20 6d 79 64 6f 74 69 64 0a h..incr mydotid.
2e00: 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 20 63 79 ..log write 5 cy
2e10: 63 6c 65 62 72 65 61 6b 65 72 20 22 2e 64 6f 74 clebreaker ".dot
2e20: 20 65 78 70 6f 72 74 20 24 66 6e 61 6d 65 22 0a export $fname".
2e30: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
2e40: 20 20 20 70 72 6f 63 20 52 65 70 6c 61 63 65 20 proc Replace
2e50: 7b 64 67 20 6e 20 72 65 70 6c 61 63 65 6d 65 6e {dg n replacemen
2e60: 74 73 7d 20 7b 0a 09 23 20 4e 4f 54 45 2e 20 57 ts} {..# NOTE. W
2e70: 65 20 68 61 76 65 20 74 6f 20 67 65 74 20 74 68 e have to get th
2e80: 65 20 6c 69 73 74 20 6f 66 20 69 6e 63 6f 6d 69 e list of incomi
2e90: 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 20 61 6e ng neighbours an
2ea0: 64 0a 09 23 20 72 65 63 6f 6d 70 75 74 65 20 74 d..# recompute t
2eb0: 68 65 69 72 20 73 75 63 63 65 73 73 6f 72 73 20 heir successors
2ec0: 61 66 74 65 72 20 74 68 65 20 6e 65 77 20 6e 6f after the new no
2ed0: 64 65 73 20 68 61 76 65 20 62 65 65 6e 0a 09 23 des have been..#
2ee0: 20 69 6e 73 65 72 74 65 64 2e 20 54 68 65 69 72 inserted. Their
2ef0: 20 6f 75 74 67 6f 69 6e 67 20 61 72 63 73 20 77 outgoing arcs w
2f00: 69 6c 6c 20 6e 6f 77 20 67 6f 20 74 6f 20 6f 6e ill now go to on
2f10: 65 20 6f 72 20 62 6f 74 68 20 6f 66 0a 09 23 20 e or both of..#
2f20: 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 2c 20 61 the new nodes, a
2f30: 6e 64 20 6e 6f 74 20 72 65 64 6f 69 6e 67 20 74 nd not redoing t
2f40: 68 65 6d 20 6d 61 79 20 63 61 75 73 65 20 75 73 hem may cause us
2f50: 20 74 6f 20 66 6f 72 67 65 74 0a 09 23 20 63 69 to forget..# ci
2f60: 72 63 6c 65 73 2c 20 6c 65 61 76 69 6e 67 20 74 rcles, leaving t
2f70: 68 65 6d 20 69 6e 2c 20 75 6e 62 72 6f 6b 65 6e hem in, unbroken
2f80: 2e 0a 0a 09 73 65 74 20 70 72 65 20 5b 24 64 67 ....set pre [$dg
2f90: 20 6e 6f 64 65 73 20 2d 69 6e 20 24 6e 5d 0a 0a nodes -in $n]..
2fa0: 20 20 20 20 20 20 20 20 24 64 67 20 6e 6f 64 65 $dg node
2fb0: 20 64 65 6c 65 74 65 20 24 6e 0a 0a 09 66 6f 72 delete $n...for
2fc0: 65 61 63 68 20 63 73 65 74 20 24 72 65 70 6c 61 each cset $repla
2fd0: 63 65 6d 65 6e 74 73 20 7b 0a 09 20 20 20 20 73 cements {.. s
2fe0: 65 74 20 74 72 20 5b 24 63 73 65 74 20 74 69 6d et tr [$cset tim
2ff0: 65 72 61 6e 67 65 5d 0a 09 20 20 20 20 24 64 67 erange].. $dg
3000: 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 node insert $cs
3010: 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 et.. $dg node
3020: 20 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 set $cset ti
3030: 6d 65 72 61 6e 67 65 20 24 74 72 0a 09 20 20 20 merange $tr..
3040: 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 $dg node set
3050: 20 24 63 73 65 74 20 6c 61 62 65 6c 20 20 20 20 $cset label
3060: 20 22 5b 24 63 73 65 74 20 73 74 72 5d 5c 5c 6e "[$cset str]\\n
3070: 5b 6a 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c [join [struct::l
3080: 69 73 74 20 6d 61 70 20 24 74 72 20 7b 3a 3a 63 ist map $tr {::c
3090: 6c 6f 63 6b 20 66 6f 72 6d 61 74 7d 5d 20 22 5c lock format}] "\
30a0: 5c 6e 22 5d 22 0a 09 20 20 20 20 24 64 67 20 6e \n"]".. $dg n
30b0: 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 ode set $cset
30c0: 20 5f 5f 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 __id__ [$cse
30d0: 74 20 69 64 5d 0a 09 20 20 20 20 24 64 67 20 6e t id].. $dg n
30e0: 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 ode set $cset
30f0: 20 73 68 61 70 65 20 20 20 20 20 5b 65 78 70 72 shape [expr
3100: 20 7b 5b 24 63 73 65 74 20 62 79 73 79 6d 62 6f {[$cset bysymbo
3110: 6c 5d 0a 09 09 09 09 09 09 20 20 20 3f 20 22 65 l]....... ? "e
3120: 6c 6c 69 70 73 65 22 0a 09 09 09 09 09 09 20 20 llipse".......
3130: 20 3a 20 22 62 6f 78 22 7d 5d 0a 09 7d 0a 0a 09 : "box"}]..}...
3140: 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 72 65 foreach cset $re
3150: 70 6c 61 63 65 6d 65 6e 74 73 20 7b 0a 09 20 20 placements {..
3160: 20 20 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b foreach succ [
3170: 24 63 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 $cset successors
3180: 5d 20 7b 0a 09 09 23 20 54 68 65 20 6e 65 77 20 ] {...# The new
3190: 63 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 68 changesets may h
31a0: 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 ave dependencies
31b0: 20 6f 75 74 73 69 64 65 20 6f 66 0a 09 09 23 20 outside of...#
31c0: 74 68 65 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 the chosen set.
31d0: 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 65 These are ignore
31e0: 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f d...if {![$dg no
31f0: 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d de exists $succ]
3200: 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 } continue...$dg
3210: 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 arc insert $cse
3220: 74 20 24 73 75 63 63 0a 09 09 69 6e 74 65 67 72 t $succ...integr
3230: 69 74 79 20 61 73 73 65 72 74 20 7b 0a 09 09 20 ity assert {...
3240: 20 20 20 24 73 75 63 63 20 6e 65 20 24 63 73 65 $succ ne $cse
3250: 74 0a 09 09 7d 20 7b 5b 24 63 73 65 74 20 72 65 t...} {[$cset re
3260: 70 6f 72 74 6c 6f 6f 70 20 30 5d 43 68 61 6e 67 portloop 0]Chang
3270: 65 73 65 74 20 6c 6f 6f 70 20 77 61 73 20 6e 6f eset loop was no
3280: 74 20 64 65 74 65 63 74 65 64 20 64 75 72 69 6e t detected durin
3290: 67 20 63 72 65 61 74 69 6f 6e 7d 0a 09 20 20 20 g creation}..
32a0: 20 7d 0a 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 }..}..foreach c
32b0: 73 65 74 20 24 70 72 65 20 7b 0a 09 20 20 20 20 set $pre {..
32c0: 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 foreach succ [$c
32d0: 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 set successors]
32e0: 7b 0a 09 09 23 20 4e 6f 74 65 20 74 68 61 74 20 {...# Note that
32f0: 74 68 65 20 61 72 63 20 6d 61 79 20 61 6c 72 65 the arc may alre
3300: 61 64 79 20 65 78 69 73 74 20 69 6e 20 74 68 65 ady exist in the
3310: 20 67 72 61 70 68 2e 20 49 66 0a 09 09 23 20 73 graph. If...# s
3320: 6f 20 69 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 o ignore it. The
3330: 20 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 new changesets
3340: 6d 61 79 20 68 61 76 65 0a 09 09 23 20 64 65 70 may have...# dep
3350: 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 endencies outsid
3360: 65 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 e of the chosen
3370: 73 65 74 2e 20 54 68 65 73 65 20 61 72 65 0a 09 set. These are..
3380: 09 23 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 .# ignored...if
3390: 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 {![$dg node exis
33a0: 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 ts $succ]} conti
33b0: 6e 75 65 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 nue...if {[HasAr
33c0: 63 20 24 64 67 20 24 63 73 65 74 20 24 73 75 63 c $dg $cset $suc
33d0: 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 c]} continue;# T
33e0: 4f 44 4f 20 73 68 6f 75 6c 64 20 62 65 20 67 72 ODO should be gr
33f0: 61 70 68 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 aph method....$d
3400: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
3410: 65 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a et $succ.. }.
3420: 09 7d 0a 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 .}...return.
3430: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
3440: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
3450: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
3460: 20 20 20 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 ## Callback i
3470: 6e 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 nvokation .....
3480: 20 20 20 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 proc PreHook
3490: 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 {graph} {..# Giv
34a0: 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 e the user of th
34b0: 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 e cycle breaker
34c0: 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 the opportunity
34d0: 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 to work..# with
34e0: 74 68 65 20 67 72 61 70 68 20 62 65 74 77 65 65 the graph betwee
34f0: 6e 20 73 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 n setup and cons
3500: 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 ummation....::va
3510: 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a riable myprecmd.
3520: 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 .if {![llength $
3530: 6d 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 myprecmd]} retur
3540: 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b n...uplevel #0 [
3550: 6c 69 6e 73 65 72 74 20 24 6d 79 70 72 65 63 6d linsert $myprecm
3560: 64 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d d end $graph]..M
3570: 61 72 6b 20 24 67 72 61 70 68 20 2d 70 72 65 2d ark $graph -pre-
3580: 64 6f 6e 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 done..return.
3590: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 6f }.. proc Pro
35a0: 63 65 73 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 cessedHook {dg c
35b0: 73 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 set pos} {..# Gi
35c0: 76 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 ve the user of t
35d0: 68 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 he cycle breaker
35e0: 20 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 the opportunity
35f0: 20 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 to work..# with
3600: 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 62 the changeset b
3610: 65 66 6f 72 65 20 69 74 20 69 73 20 72 65 6d 6f efore it is remo
3620: 76 65 64 20 66 72 6f 6d 20 74 68 65 20 67 72 61 ved from the gra
3630: 70 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 ph....::variable
3640: 20 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 20 7b mysavecmd..if {
3650: 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 ![llength $mysav
3660: 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 ecmd]} return...
3670: 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 uplevel #0 [lins
3680: 65 72 74 20 24 6d 79 73 61 76 65 63 6d 64 20 65 ert $mysavecmd e
3690: 6e 64 20 24 64 67 20 24 70 6f 73 20 24 63 73 65 nd $dg $pos $cse
36a0: 74 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d t]..return. }
36b0: 0a 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b .. proc Break
36c0: 43 79 63 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 CycleHook {graph
36d0: 7d 20 7b 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 } {..# Call out
36e0: 74 6f 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c to the chosen al
36f0: 67 6f 72 69 74 68 6d 20 66 6f 72 20 63 79 63 6c gorithm for cycl
3700: 65 20 62 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 e breaking. Find
3710: 69 6e 67 0a 09 23 20 61 20 63 79 63 6c 65 20 69 ing..# a cycle i
3720: 66 20 6e 6f 20 62 72 65 61 6b 65 72 20 77 61 73 f no breaker was
3730: 20 63 68 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 chosen is an er
3740: 72 6f 72 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c ror....::variabl
3750: 65 20 6d 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 e mybreakcmd..if
3760: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 {![llength $myb
3770: 72 65 61 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 reakcmd]} {..
3780: 20 74 72 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 trouble fatal "
3790: 46 6f 75 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 Found a cycle, e
37a0: 78 70 65 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a xpecting none.".
37b0: 09 20 20 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a . exit 1..}..
37c0: 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e .uplevel #0 [lin
37d0: 73 65 72 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 sert $mybreakcmd
37e0: 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 72 65 end $graph]..re
37f0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
3800: 70 72 6f 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 proc ClearHooks
3810: 7b 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 {} {..::variable
3820: 20 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 myprecmd {}..
3830: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 ::variable mysav
3840: 65 63 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 ecmd {}..::vari
3850: 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 able mybreakcmd
3860: 7b 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d {}..return. }
3870: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
3880: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
3890: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 #############..
38a0: 20 20 20 70 72 6f 63 20 4d 61 72 6b 57 61 74 63 proc MarkWatc
38b0: 68 20 7b 67 72 61 70 68 7d 20 7b 0a 09 3a 3a 76 h {graph} {..::v
38c0: 61 72 69 61 62 6c 65 20 6d 79 77 61 74 63 68 69 ariable mywatchi
38d0: 64 73 0a 09 73 65 74 20 77 61 74 63 68 65 64 20 ds..set watched
38e0: 5b 57 61 74 63 68 65 64 20 24 67 72 61 70 68 20 [Watched $graph
38f0: 24 6d 79 77 61 74 63 68 69 64 73 5d 0a 09 69 66 $mywatchids]..if
3900: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 77 61 74 {![llength $wat
3910: 63 68 65 64 5d 7d 20 72 65 74 75 72 6e 0a 09 73 ched]} return..s
3920: 65 74 20 6e 65 69 67 68 62 6f 75 72 73 20 5b 65 et neighbours [e
3930: 76 61 6c 20 5b 6c 69 6e 73 65 72 74 20 24 77 61 val [linsert $wa
3940: 74 63 68 65 64 20 30 20 24 67 72 61 70 68 20 6e tched 0 $graph n
3950: 6f 64 65 73 20 2d 61 64 6a 5d 5d 0a 09 23 66 6f odes -adj]]..#fo
3960: 72 65 61 63 68 20 6e 20 24 6e 65 69 67 68 62 6f reach n $neighbo
3970: 75 72 73 20 7b 20 6c 6f 67 20 77 72 69 74 65 20 urs { log write
3980: 36 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 6 cyclebreaker "
3990: 4e 65 69 67 68 62 6f 72 20 5b 24 6e 20 69 64 5d Neighbor [$n id]
39a0: 20 3d 3e 20 24 6e 22 20 7d 0a 09 4d 61 72 6b 20 => $n" }..Mark
39b0: 24 67 72 61 70 68 20 77 61 74 63 68 65 64 20 5b $graph watched [
39c0: 63 6f 6e 63 61 74 20 24 77 61 74 63 68 65 64 20 concat $watched
39d0: 24 6e 65 69 67 68 62 6f 75 72 73 5d 0a 09 72 65 $neighbours]..re
39e0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
39f0: 70 72 6f 63 20 57 61 74 63 68 65 64 20 7b 67 72 proc Watched {gr
3a00: 61 70 68 20 77 61 74 63 68 69 64 73 7d 20 7b 0a aph watchids} {.
3a10: 09 73 65 74 20 72 65 73 20 7b 7d 0a 09 66 6f 72 .set res {}..for
3a20: 65 61 63 68 20 69 64 20 24 77 61 74 63 68 69 64 each id $watchid
3a30: 73 20 7b 0a 09 20 20 20 20 73 65 74 20 6e 6c 20 s {.. set nl
3a40: 5b 24 67 72 61 70 68 20 6e 6f 64 65 73 20 2d 6b [$graph nodes -k
3a50: 65 79 20 5f 5f 69 64 5f 5f 20 2d 76 61 6c 75 65 ey __id__ -value
3a60: 20 24 69 64 5d 0a 09 20 20 20 20 69 66 20 7b 21 $id].. if {!
3a70: 5b 6c 6c 65 6e 67 74 68 20 24 6e 6c 5d 7d 20 63 [llength $nl]} c
3a80: 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 ontinue.. lap
3a90: 70 65 6e 64 20 72 65 73 20 24 6e 6c 0a 09 20 20 pend res $nl..
3aa0: 20 20 23 6c 6f 67 20 77 72 69 74 65 20 36 20 62 #log write 6 b
3ab0: 72 65 61 6b 72 63 79 63 6c 65 20 22 57 61 74 63 reakrcycle "Watc
3ac0: 68 69 6e 67 20 24 69 64 20 3d 3e 20 24 6e 6c 22 hing $id => $nl"
3ad0: 0a 09 20 20 20 20 24 67 72 61 70 68 20 6e 6f 64 .. $graph nod
3ae0: 65 20 73 65 74 20 24 6e 6c 20 66 6f 6e 74 63 6f e set $nl fontco
3af0: 6c 6f 72 20 72 65 64 0a 09 7d 0a 09 72 65 74 75 lor red..}..retu
3b00: 72 6e 20 24 72 65 73 0a 20 20 20 20 7d 0a 0a 20 rn $res. }..
3b10: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
3b20: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
3b30: 23 23 23 23 23 23 23 23 23 23 0a 0a 0a 20 20 20 ##########...
3b40: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3b50: 61 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f at 0 ; # Co
3b60: 75 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 unter for commit
3b70: 20 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 ids for the....
3b80: 20 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 # changes
3b90: 65 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 ets.. typevar
3ba0: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b iable mybottom {
3bb0: 7d 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 } ; # List of th
3bc0: 65 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 e candidate node
3bd0: 73 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 s for....
3be0: 23 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 # committing...
3bf0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3c00: 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 myprecmd {} ;
3c10: 23 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e # Callback, chan
3c20: 67 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 ge graph before
3c30: 77 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 walk.. typeva
3c40: 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 riable mysavecmd
3c50: 20 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 {} ; # Callbac
3c60: 6b 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 k, for each proc
3c70: 65 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 essed node..
3c80: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 typevariable myb
3c90: 72 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 reakcmd {} ; # C
3ca0: 61 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 allback, for eac
3cb0: 68 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a h found cycle...
3cc0: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
3cd0: 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f mydotdestinatio
3ce0: 6e 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 n {} ; # Destina
3cf0: 74 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 tion directory f
3d00: 6f 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 or the.....
3d10: 20 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 # generated .d
3d20: 6f 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 ot files.. ty
3d30: 70 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 pevariable mydot
3d40: 70 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b prefix {} ;
3d50: 20 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f # Prefix for do
3d60: 74 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 t files when....
3d70: 09 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 . # export
3d80: 69 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a ing the graphs..
3d90: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
3da0: 20 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 mydotid
3db0: 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 0 ; # Counter
3dc0: 20 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 for dot file na
3dd0: 6d 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 me..... #
3de0: 67 65 6e 65 72 61 74 69 6f 6e 2e 0a 20 20 20 20 generation..
3df0: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 77 typevariable myw
3e00: 61 74 63 68 69 64 73 20 20 20 20 20 20 20 7b 7d atchids {}
3e10: 20 3b 20 23 20 43 68 61 6e 67 65 73 65 74 73 20 ; # Changesets
3e20: 74 6f 20 77 61 74 63 68 20 74 68 65 0a 09 09 09 to watch the....
3e30: 09 20 20 20 20 20 20 20 23 20 6e 65 69 67 68 62 . # neighb
3e40: 6f 75 72 68 6f 6f 64 20 6f 66 2e 0a 0a 20 20 20 ourhood of...
3e50: 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 # # ## ### ####
3e60: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
3e70: 23 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 ########. ##
3e80: 43 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 Configuration..
3e90: 20 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e pragma -hasin
3ea0: 73 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 stances no ; #
3eb0: 20 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 singleton. p
3ec0: 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e ragma -hastypein
3ed0: 66 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 fo no ; # no
3ee0: 69 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 introspection.
3ef0: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 pragma -hastyp
3f00: 65 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 edestroy no ; #
3f10: 69 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 immortal.. #
3f20: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
3f30: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
3f40: 23 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 #####.}..namespa
3f50: 63 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f ce eval ::vc::fo
3f60: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
3f70: 73 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 s {. namespac
3f80: 65 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 e export cyclebr
3f90: 65 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 eaker. namesp
3fa0: 61 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 ace eval cyclebr
3fb0: 65 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 eaker {..namespa
3fc0: 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a ce import ::vc::
3fd0: 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a fossil::import::
3fe0: 63 76 73 3a 3a 69 6e 74 65 67 72 69 74 79 0a 09 cvs::integrity..
3ff0: 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 70 namespace eval p
4000: 72 6f 6a 65 63 74 20 7b 0a 09 20 20 20 20 6e 61 roject {.. na
4010: 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a mespace import :
4020: 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 :vc::fossil::imp
4030: 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 ort::cvs::projec
4040: 74 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d 65 t::rev.. name
4050: 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 space import ::v
4060: 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 c::fossil::impor
4070: 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 3a t::cvs::project:
4080: 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 6d :revlink..}..nam
4090: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
40a0: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 3a vc::tools::misc:
40b0: 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d :*..namespace im
40c0: 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 port ::vc::tools
40d0: 3a 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 65 ::log..namespace
40e0: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f import ::vc::to
40f0: 6f 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a 09 6e 61 ols::trouble..na
4100: 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a mespace import :
4110: 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 0a :vc::tools::dot.
4120: 09 6c 6f 67 20 72 65 67 69 73 74 65 72 20 63 79 .log register cy
4130: 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 7d clebreaker. }
4140: 0a 7d 0a 0a 23 20 23 20 23 23 20 23 23 23 20 23 .}..# # ## ### #
4150: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
4160: 23 23 23 23 23 23 23 23 23 23 23 20 23 23 23 23 ########### ####
4170: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
4180: 23 0a 23 23 20 52 65 61 64 79 0a 0a 70 61 63 6b #.## Ready..pack
4190: 61 67 65 20 70 72 6f 76 69 64 65 20 76 63 3a 3a age provide vc::
41a0: 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a fossil::import::
41b0: 63 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 cvs::cyclebreake
41c0: 72 20 31 2e 30 0a 72 65 74 75 72 6e 0a r 1.0.return.