Artifact 9dfc0b4e4fd3ed1f151ba71720b7163cf60f20c6:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[0af7a3c8ac]
- Easier name for self-referential changesets, loopcheck. Made conditional on option --loopcheck, default off, and avoided if the general checks on changesets report trouble. Reinstated the loop check in the cycle breaker core in simpler form, reusing the new command in the changeset class.
by
aku on
2007-11-30 06:57:19.
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 09 77 68 69 6c 65 20 7b 31 7d s $dg..while {1}
0d60: 20 7b 0a 09 20 20 20 20 77 68 69 6c 65 20 7b 5b {.. while {[
0d70: 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 WithoutPredecess
0d80: 6f 72 20 24 64 67 20 6e 5d 7d 20 7b 0a 09 09 4d or $dg n]} {...M
0d90: 61 72 6b 57 61 74 63 68 20 24 64 67 0a 09 09 50 arkWatch $dg...P
0da0: 72 6f 63 65 73 73 65 64 48 6f 6f 6b 20 24 64 67 rocessedHook $dg
0db0: 20 24 6e 20 24 6d 79 61 74 0a 09 09 24 64 67 20 $n $myat...$dg
0dc0: 6e 6f 64 65 20 64 65 6c 65 74 65 20 24 6e 0a 09 node delete $n..
0dd0: 09 69 6e 63 72 20 6d 79 61 74 0a 09 09 53 68 6f .incr myat...Sho
0de0: 77 50 65 6e 64 69 6e 67 4e 6f 64 65 73 0a 09 20 wPendingNodes..
0df0: 20 20 20 7d 0a 0a 09 20 20 20 20 69 66 20 7b 21 }... if {!
0e00: 5b 6c 6c 65 6e 67 74 68 20 5b 64 67 20 6e 6f 64 [llength [dg nod
0e10: 65 73 5d 5d 7d 20 62 72 65 61 6b 0a 0a 09 20 20 es]]} break...
0e20: 20 20 42 72 65 61 6b 43 79 63 6c 65 48 6f 6f 6b BreakCycleHook
0e30: 20 20 20 20 20 20 20 24 64 67 0a 09 20 20 20 20 $dg..
0e40: 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 InitializeCandid
0e50: 61 74 65 73 20 24 64 67 0a 09 20 20 20 20 4d 61 ates $dg.. Ma
0e60: 72 6b 57 61 74 63 68 20 20 20 20 20 20 20 20 20 rkWatch
0e70: 20 20 20 24 64 67 0a 09 7d 0a 0a 09 24 64 67 20 $dg..}...$dg
0e80: 64 65 73 74 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 destroy...log wr
0e90: 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b ite 3 cyclebreak
0ea0: 65 72 20 44 6f 6e 65 2e 0a 09 43 6c 65 61 72 48 er Done...ClearH
0eb0: 6f 6f 6b 73 0a 0a 09 23 20 52 65 72 65 61 64 20 ooks...# Reread
0ec0: 74 68 65 20 67 72 61 70 68 20 61 6e 64 20 64 75 the graph and du
0ed0: 6d 70 20 69 74 73 20 66 69 6e 61 6c 20 66 6f 72 mp its final for
0ee0: 6d 2c 20 69 66 20 67 72 61 70 68 20 65 78 70 6f m, if graph expo
0ef0: 72 74 0a 09 23 20 77 61 73 20 61 63 74 69 76 61 rt..# was activa
0f00: 74 65 64 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c ted....::variabl
0f10: 65 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 e mydotdestinati
0f20: 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 6f 74 64 65 on..if {$mydotde
0f30: 73 74 69 6e 61 74 69 6f 6e 20 65 71 20 22 22 7d stination eq ""}
0f40: 20 72 65 74 75 72 6e 0a 0a 09 73 65 74 20 20 20 return...set
0f50: 64 67 20 5b 53 65 74 75 70 20 5b 75 70 6c 65 76 dg [Setup [uplev
0f60: 65 6c 20 23 30 20 24 63 68 61 6e 67 65 73 65 74 el #0 $changeset
0f70: 63 6d 64 5d 20 30 5d 0a 09 4d 61 72 6b 20 24 64 cmd] 0]..Mark $d
0f80: 67 20 2d 64 6f 6e 65 0a 09 24 64 67 20 64 65 73 g -done..$dg des
0f90: 74 72 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 20 troy..return.
0fa0: 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 }.. # # ## #
0fb0: 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 ## ##### #######
0fc0: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a # #############.
0fd0: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
0fe0: 62 72 65 61 6b 2d 73 65 67 6d 65 6e 74 20 7b 67 break-segment {g
0ff0: 72 61 70 68 7d 20 7b 0a 09 42 72 65 61 6b 53 65 raph} {..BreakSe
1000: 67 6d 65 6e 74 20 24 67 72 61 70 68 20 24 70 61 gment $graph $pa
1010: 74 68 20 22 73 65 67 6d 65 6e 74 20 28 5b 70 72 th "segment ([pr
1020: 6f 6a 65 63 74 3a 3a 72 65 76 20 73 74 72 6c 69 oject::rev strli
1030: 73 74 20 24 70 61 74 68 5d 29 22 0a 09 72 65 74 st $path])"..ret
1040: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 urn. }.. t
1050: 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 6b 20 ypemethod break
1060: 7b 67 72 61 70 68 7d 20 7b 0a 09 73 65 74 20 63 {graph} {..set c
1070: 79 63 6c 65 20 5b 46 69 6e 64 43 79 63 6c 65 20 ycle [FindCycle
1080: 24 67 72 61 70 68 5d 0a 09 73 65 74 20 6c 61 62 $graph]..set lab
1090: 65 6c 20 22 63 79 63 6c 65 20 28 5b 70 72 6f 6a el "cycle ([proj
10a0: 65 63 74 3a 3a 72 65 76 20 73 74 72 6c 69 73 74 ect::rev strlist
10b0: 20 24 63 79 63 6c 65 5d 29 22 0a 0a 09 23 20 4e $cycle])"...# N
10c0: 4f 54 45 3a 20 63 76 73 32 73 76 6e 20 75 73 65 OTE: cvs2svn use
10d0: 73 20 74 68 65 20 73 65 71 75 65 6e 63 65 20 22 s the sequence "
10e0: 65 6e 64 2d 31 2c 20 63 79 63 6c 65 2c 20 30 22 end-1, cycle, 0"
10f0: 20 74 6f 20 63 72 65 61 74 65 0a 09 23 20 20 20 to create..#
1100: 20 20 20 20 74 68 65 20 70 61 74 68 20 66 72 6f the path fro
1110: 6d 20 74 68 65 20 63 79 63 6c 65 2e 20 54 68 65 m the cycle. The
1120: 20 6f 6e 6c 79 20 65 66 66 65 63 74 20 49 20 63 only effect I c
1130: 61 6e 20 73 65 65 20 69 73 0a 09 23 20 20 20 20 an see is..#
1140: 20 20 20 74 68 61 74 20 74 68 69 73 20 63 61 75 that this cau
1150: 73 65 73 20 74 68 65 20 6c 69 6e 6b 2d 74 72 69 ses the link-tri
1160: 70 6c 65 73 20 74 6f 20 62 65 20 67 65 6e 65 72 ples to be gener
1170: 61 74 65 64 20 69 6e 20 61 0a 09 23 20 20 20 20 ated in a..#
1180: 20 20 20 73 69 67 68 74 6c 79 20 64 69 66 66 65 sightly diffe
1190: 72 65 6e 74 20 6f 72 64 65 72 2c 20 69 2e 65 2e rent order, i.e.
11a0: 20 6f 6e 65 20 6c 69 6e 6b 20 72 6f 74 61 74 65 one link rotate
11b0: 64 20 74 6f 20 74 68 65 0a 09 23 20 20 20 20 20 d to the..#
11c0: 20 20 72 69 67 68 74 2e 20 54 68 69 73 20 73 68 right. This sh
11d0: 6f 75 6c 64 20 68 61 76 65 20 6e 6f 20 65 66 66 ould have no eff
11e0: 65 63 74 20 6f 6e 20 74 68 65 20 73 65 61 72 63 ect on the searc
11f0: 68 20 66 6f 72 0a 09 23 20 20 20 20 20 20 20 74 h for..# t
1200: 68 65 20 62 65 73 74 20 6f 66 20 61 6c 6c 2e 0a he best of all..
1210: 0a 09 6c 61 70 70 65 6e 64 20 63 79 63 6c 65 20 ..lappend cycle
1220: 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 30 [lindex $cycle 0
1230: 5d 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 ] [lindex $cycle
1240: 20 31 5d 0a 09 42 72 65 61 6b 53 65 67 6d 65 6e 1]..BreakSegmen
1250: 74 20 24 67 72 61 70 68 20 24 63 79 63 6c 65 20 t $graph $cycle
1260: 24 6c 61 62 65 6c 0a 09 72 65 74 75 72 6e 0a 20 $label..return.
1270: 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 }.. typeme
1280: 74 68 6f 64 20 72 65 70 6c 61 63 65 20 7b 67 72 thod replace {gr
1290: 61 70 68 20 6e 20 72 65 70 6c 61 63 65 6d 65 6e aph n replacemen
12a0: 74 73 7d 20 7b 0a 09 52 65 70 6c 61 63 65 20 24 ts} {..Replace $
12b0: 67 72 61 70 68 20 24 6e 20 24 72 65 70 6c 61 63 graph $n $replac
12c0: 65 6d 65 6e 74 73 0a 09 72 65 74 75 72 6e 0a 20 ements..return.
12d0: 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 }.. # # ##
12e0: 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 ### ##### #####
12f0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
1300: 23 0a 20 20 20 20 23 23 20 49 6e 74 65 72 6e 61 #. ## Interna
1310: 6c 20 6d 65 74 68 6f 64 73 0a 0a 20 20 20 20 70 l methods.. p
1320: 72 6f 63 20 53 65 74 75 70 20 7b 63 68 61 6e 67 roc Setup {chang
1330: 65 73 65 74 73 20 7b 6c 6f 67 20 31 7d 7d 20 7b esets {log 1}} {
1340: 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 ..if {$log} {..
1350: 20 20 20 6c 6f 67 20 77 72 69 74 65 20 33 20 63 log write 3 c
1360: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 43 72 65 yclebreaker "Cre
1370: 61 74 69 6e 67 20 67 72 61 70 68 20 6f 66 20 63 ating graph of c
1380: 68 61 6e 67 65 73 65 74 73 22 0a 09 7d 0a 0a 09 hangesets"..}...
1390: 73 65 74 20 64 67 20 5b 73 74 72 75 63 74 3a 3a set dg [struct::
13a0: 67 72 61 70 68 20 64 67 5d 0a 0a 09 66 6f 72 65 graph dg]...fore
13b0: 61 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 ach cset $change
13c0: 73 65 74 73 20 7b 0a 09 20 20 20 20 73 65 74 20 sets {.. set
13d0: 74 72 20 5b 24 63 73 65 74 20 74 69 6d 65 72 61 tr [$cset timera
13e0: 6e 67 65 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f nge].. $dg no
13f0: 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 74 0a de insert $cset.
1400: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
1410: 74 20 20 20 20 24 63 73 65 74 20 74 69 6d 65 72 t $cset timer
1420: 61 6e 67 65 20 24 74 72 0a 09 20 20 20 20 24 64 ange $tr.. $d
1430: 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 g node set $c
1440: 73 65 74 20 6c 61 62 65 6c 20 20 20 20 20 22 5b set label "[
1450: 24 63 73 65 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f $cset str]\\n[jo
1460: 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 in [struct::list
1470: 20 6d 61 70 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 map $tr {::cloc
1480: 6b 20 66 6f 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 k format}] "\\n"
1490: 5d 22 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 ]".. $dg node
14a0: 20 73 65 74 20 20 20 20 24 63 73 65 74 20 5f 5f set $cset __
14b0: 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 74 20 69 id__ [$cset i
14c0: 64 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 d].. $dg node
14d0: 20 73 65 74 20 20 20 20 24 63 73 65 74 20 73 68 set $cset sh
14e0: 61 70 65 20 20 20 20 20 5b 65 78 70 72 20 7b 5b ape [expr {[
14f0: 24 63 73 65 74 20 62 79 73 79 6d 62 6f 6c 5d 0a $cset bysymbol].
1500: 09 09 09 09 09 09 20 20 20 3f 20 22 65 6c 6c 69 ...... ? "elli
1510: 70 73 65 22 0a 09 09 09 09 09 09 20 20 20 3a 20 pse"....... :
1520: 22 62 6f 78 22 7d 5d 0a 09 7d 0a 0a 09 69 66 20 "box"}]..}...if
1530: 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f {$log} {.. lo
1540: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
1550: 72 65 61 6b 65 72 20 22 48 61 73 20 5b 6e 73 70 reaker "Has [nsp
1560: 20 5b 6c 6c 65 6e 67 74 68 20 24 63 68 61 6e 67 [llength $chang
1570: 65 73 65 74 73 5d 20 63 68 61 6e 67 65 73 65 74 esets] changeset
1580: 5d 22 0a 09 7d 0a 0a 09 23 20 32 2e 20 46 69 6e ]"..}...# 2. Fin
1590: 64 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 d for all releva
15a0: 6e 74 20 63 68 61 6e 67 65 73 65 74 20 74 68 65 nt changeset the
15b0: 69 72 20 72 65 76 69 73 69 6f 6e 73 20 61 6e 64 ir revisions and
15c0: 20 74 68 65 69 72 0a 09 23 20 20 20 20 64 65 70 their..# dep
15d0: 65 6e 64 65 6e 63 69 65 73 2e 20 4d 61 70 20 74 endencies. Map t
15e0: 68 65 20 6c 61 74 74 65 72 20 62 61 63 6b 20 74 he latter back t
15f0: 6f 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 o changesets and
1600: 0a 09 23 20 20 20 20 63 6f 6e 73 74 72 75 63 74 ..# construct
1610: 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 the correspondi
1620: 6e 67 20 61 72 63 73 2e 0a 0a 09 66 6f 72 65 61 ng arcs....forea
1630: 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 73 ch cset $changes
1640: 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 ets {.. forea
1650: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 ch succ [$cset s
1660: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 uccessors] {...#
1670: 20 43 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 Changesets may
1680: 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 have dependencie
1690: 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 s outside of the
16a0: 0a 09 09 23 20 63 68 6f 73 65 6e 20 73 65 74 2e ...# chosen set.
16b0: 20 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 These are ignor
16c0: 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e ed...if {![$dg n
16d0: 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 ode exists $succ
16e0: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 ]} continue...$d
16f0: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
1700: 65 74 20 24 73 75 63 63 0a 09 09 69 66 20 7b 24 et $succ...if {$
1710: 73 75 63 63 20 65 71 20 24 63 73 65 74 7d 20 7b succ eq $cset} {
1720: 0a 09 09 20 20 20 20 24 63 73 65 74 20 6c 6f 6f ... $cset loo
1730: 70 63 68 65 63 6b 0a 09 09 20 20 20 20 74 72 6f pcheck... tro
1740: 75 62 6c 65 20 66 61 74 61 6c 20 22 5b 24 63 73 uble fatal "[$cs
1750: 65 74 20 73 74 72 5d 20 64 65 70 65 6e 64 73 20 et str] depends
1760: 6f 6e 20 69 74 73 65 6c 66 22 0a 09 09 7d 0a 09 on itself"...}..
1770: 20 20 20 20 7d 0a 09 7d 0a 0a 09 69 66 20 7b 24 }..}...if {$
1780: 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 20 log} {.. log
1790: 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 write 3 cyclebre
17a0: 61 6b 65 72 20 22 48 61 73 20 5b 6e 73 70 20 5b aker "Has [nsp [
17b0: 6c 6c 65 6e 67 74 68 20 5b 24 64 67 20 61 72 63 llength [$dg arc
17c0: 73 5d 5d 20 64 65 70 65 6e 64 65 6e 63 79 20 64 s]] dependency d
17d0: 65 70 65 6e 64 65 6e 63 69 65 73 5d 22 0a 09 7d ependencies]"..}
17e0: 0a 0a 09 23 20 52 75 6e 20 74 68 65 20 75 73 65 ...# Run the use
17f0: 72 20 68 6f 6f 6b 20 74 6f 20 6d 61 6e 69 70 75 r hook to manipu
1800: 6c 61 74 65 20 74 68 65 20 67 72 61 70 68 20 62 late the graph b
1810: 65 66 6f 72 65 0a 09 23 20 63 6f 6e 73 75 6d 6d efore..# consumm
1820: 61 74 69 6f 6e 2e 0a 0a 09 69 66 20 7b 24 6c 6f ation....if {$lo
1830: 67 7d 20 7b 20 4d 61 72 6b 20 24 64 67 20 2d 73 g} { Mark $dg -s
1840: 74 61 72 74 20 7d 0a 09 4d 61 72 6b 57 61 74 63 tart }..MarkWatc
1850: 68 20 24 64 67 0a 09 50 72 65 48 6f 6f 6b 20 20 h $dg..PreHook
1860: 20 24 64 67 0a 09 4d 61 72 6b 57 61 74 63 68 20 $dg..MarkWatch
1870: 24 64 67 0a 09 72 65 74 75 72 6e 20 20 24 64 67 $dg..return $dg
1880: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 49 6e . }.. # In
1890: 73 74 65 61 64 20 6f 66 20 73 65 61 72 63 68 69 stead of searchi
18a0: 6e 67 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61 ng the whole gra
18b0: 70 68 20 66 6f 72 20 74 68 65 20 64 65 67 72 65 ph for the degre
18c0: 65 2d 30 20 6e 6f 64 65 73 20 69 6e 0a 20 20 20 e-0 nodes in.
18d0: 20 23 20 65 61 63 68 20 69 74 65 72 61 74 69 6f # each iteratio
18e0: 6e 20 77 65 20 63 6f 6d 70 75 74 65 20 74 68 65 n we compute the
18f0: 20 6c 69 73 74 20 6f 6e 63 65 20 74 6f 20 73 74 list once to st
1900: 61 72 74 2c 20 61 6e 64 20 74 68 65 6e 20 6f 6e art, and then on
1910: 6c 79 0a 20 20 20 20 23 20 75 70 64 61 74 65 20 ly. # update
1920: 69 74 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 it incrementally
1930: 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6f 75 based on the ou
1940: 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 tgoing neighbour
1950: 73 20 6f 66 20 74 68 65 0a 20 20 20 20 23 20 6e s of the. # n
1960: 6f 64 65 20 63 68 6f 73 65 6e 20 66 6f 72 20 63 ode chosen for c
1970: 6f 6d 6d 69 74 2e 0a 0a 20 20 20 20 70 72 6f 63 ommit... proc
1980: 20 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 InitializeCandi
1990: 64 61 74 65 73 20 7b 64 67 7d 20 7b 0a 09 23 20 dates {dg} {..#
19a0: 62 6f 74 74 6f 6d 20 3d 20 6c 69 73 74 20 28 6c bottom = list (l
19b0: 69 73 74 20 28 6e 6f 64 65 2c 20 72 61 6e 67 65 ist (node, range
19c0: 20 6d 69 6e 2c 20 72 61 6e 67 65 20 6d 61 78 29 min, range max)
19d0: 29 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 )..::variable my
19e0: 62 6f 74 74 6f 6d 0a 09 66 6f 72 65 61 63 68 20 bottom..foreach
19f0: 6e 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 7b 0a n [$dg nodes] {.
1a00: 09 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f . if {[$dg no
1a10: 64 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 6e de degree -in $n
1a20: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 ]} continue..
1a30: 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 6f lappend mybotto
1a40: 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 m [linsert [$dg
1a50: 6e 6f 64 65 20 67 65 74 20 24 6e 20 74 69 6d 65 node get $n time
1a60: 72 61 6e 67 65 5d 20 30 20 24 6e 5d 0a 09 7d 0a range] 0 $n]..}.
1a70: 09 53 63 68 65 64 75 6c 65 43 61 6e 64 69 64 61 .ScheduleCandida
1a80: 74 65 73 0a 09 53 68 6f 77 50 65 6e 64 69 6e 67 tes..ShowPending
1a90: 4e 6f 64 65 73 0a 09 72 65 74 75 72 6e 0a 20 20 Nodes..return.
1aa0: 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 }.. proc Wi
1ab0: 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 thoutPredecessor
1ac0: 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 {dg nv} {..::va
1ad0: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
1ae0: 0a 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e 0a ..upvar 1 $nv n.
1af0: 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 .if {![llength $
1b00: 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 mybottom]} { ret
1b10: 75 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e 20 urn 0 }...set n
1b20: 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 20 [lindex [lindex
1b30: 24 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d 0a $mybottom 0] 0].
1b40: 09 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c .set mybottom [l
1b50: 72 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d 20 range $mybottom
1b60: 31 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 6e 1 end]..set chan
1b70: 67 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 65 ged 0...# Update
1b80: 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 77 list of nodes w
1b90: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
1ba0: 6f 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 65 or, based on the
1bb0: 0a 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 ..# outgoing nei
1bc0: 67 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 63 ghbours of the c
1bd0: 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 73 hosen node. This
1be0: 20 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 61 should be..# fa
1bf0: 73 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 74 ster than iterat
1c00: 69 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 ing of the whole
1c10: 20 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 66 set of nodes, f
1c20: 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 69 inding all..# wi
1c30: 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f thout predecesso
1c40: 72 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 6d rs, sorting them
1c50: 20 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 70 by time, etc. p
1c60: 70 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 20 p...foreach out
1c70: 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 [$dg nodes -out
1c80: 24 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b $n] {.. if {[
1c90: 24 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 $dg node degree
1ca0: 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 63 -in $out] > 1} c
1cb0: 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 44 ontinue.. # D
1cc0: 65 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f 75 egree-1 neighbou
1cd0: 72 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f 20 r, will have no
1ce0: 70 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 74 predecessors aft
1cf0: 65 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 65 er the.. # re
1d00: 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 20 moval of n. Put
1d10: 6f 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 20 on the list...
1d20: 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 lappend mybott
1d30: 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 om [linsert [$dg
1d40: 20 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 74 node get $out t
1d50: 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 74 imerange] 0 $out
1d60: 5d 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e 67 ].. set chang
1d70: 65 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 68 ed 1..}..if {$ch
1d80: 61 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 53 63 anged} {.. Sc
1d90: 68 65 64 75 6c 65 43 61 6e 64 69 64 61 74 65 73 heduleCandidates
1da0: 0a 09 7d 0a 0a 09 23 20 57 65 20 64 6f 20 6e 6f ..}...# We do no
1db0: 74 20 64 65 6c 65 74 65 20 74 68 65 20 6e 6f 64 t delete the nod
1dc0: 65 20 69 6d 6d 65 64 69 61 74 65 6c 79 2c 20 74 e immediately, t
1dd0: 6f 20 61 6c 6c 6f 77 20 74 68 65 20 53 61 76 65 o allow the Save
1de0: 0a 09 23 20 70 72 6f 63 65 64 75 72 65 20 74 6f ..# procedure to
1df0: 20 73 61 76 65 20 74 68 65 20 64 65 70 65 6e 64 save the depend
1e00: 65 6e 63 69 65 73 20 61 73 20 77 65 6c 6c 20 28 encies as well (
1e10: 65 6e 63 6f 64 65 64 20 69 6e 20 74 68 65 0a 09 encoded in the..
1e20: 23 20 61 72 63 73 29 2e 0a 09 72 65 74 75 72 6e # arcs)...return
1e30: 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 1. }.. pr
1e40: 6f 63 20 53 63 68 65 64 75 6c 65 43 61 6e 64 69 oc ScheduleCandi
1e50: 64 61 74 65 73 20 7b 7d 20 7b 0a 09 3a 3a 76 61 dates {} {..::va
1e60: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
1e70: 09 23 20 53 6f 72 74 20 62 79 20 63 73 65 74 20 .# Sort by cset
1e80: 6f 62 6a 65 63 74 20 6e 61 6d 65 2c 20 6c 6f 77 object name, low
1e90: 65 72 20 62 6f 72 64 65 72 20 6f 66 20 74 69 6d er border of tim
1ea0: 65 72 61 6e 67 65 2c 20 61 74 20 6c 61 73 74 0a erange, at last.
1eb0: 09 23 20 62 79 20 74 68 65 20 75 70 70 65 72 20 .# by the upper
1ec0: 62 6f 72 64 65 72 2e 0a 09 73 65 74 20 6d 79 62 border...set myb
1ed0: 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e ottom [lsort -in
1ee0: 64 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 5b dex 2 -integer [
1ef0: 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d lsort -index 1 -
1f00: 69 6e 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d integer [lsort -
1f10: 69 6e 64 65 78 20 30 20 2d 64 69 63 74 20 24 6d index 0 -dict $m
1f20: 79 62 6f 74 74 6f 6d 5d 5d 5d 0a 09 72 65 74 75 ybottom]]]..retu
1f30: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
1f40: 6f 63 20 53 68 6f 77 50 65 6e 64 69 6e 67 4e 6f oc ShowPendingNo
1f50: 64 65 73 20 7b 7d 20 7b 0a 09 69 66 20 7b 5b 6c des {} {..if {[l
1f60: 6f 67 20 76 65 72 62 6f 73 69 74 79 3f 5d 20 3c og verbosity?] <
1f70: 20 31 30 7d 20 72 65 74 75 72 6e 0a 09 3a 3a 76 10} return..::v
1f80: 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d ariable mybottom
1f90: 0a 09 6c 6f 67 20 77 72 69 74 65 20 31 30 20 63 ..log write 10 c
1fa0: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 50 65 6e yclebreaker "Pen
1fb0: 64 69 6e 67 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ding............
1fc0: 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ................
1fd0: 2e 2e 2e 22 0a 09 66 6f 72 65 61 63 68 20 69 74 ..."..foreach it
1fe0: 65 6d 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 em [struct::list
1ff0: 20 6d 61 70 20 24 6d 79 62 6f 74 74 6f 6d 20 5b map $mybottom [
2000: 6d 79 70 72 6f 63 20 46 6f 72 6d 61 74 50 65 6e myproc FormatPen
2010: 64 69 6e 67 49 74 65 6d 5d 5d 20 7b 0a 09 20 20 dingItem]] {..
2020: 20 20 6c 6f 67 20 77 72 69 74 65 20 31 30 20 63 log write 10 c
2030: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 50 65 6e yclebreaker "Pen
2040: 64 69 6e 67 3a 20 20 20 20 20 24 69 74 65 6d 22 ding: $item"
2050: 0a 09 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 ..}..return.
2060: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 46 6f 72 6d }.. proc Form
2070: 61 74 50 65 6e 64 69 6e 67 49 74 65 6d 20 7b 69 atPendingItem {i
2080: 74 65 6d 7d 20 7b 0a 09 6a 6f 69 6e 20 5b 6c 69 tem} {..join [li
2090: 73 74 20 5b 5b 6c 69 6e 64 65 78 20 24 69 74 65 st [[lindex $ite
20a0: 6d 20 30 5d 20 73 74 72 5d 20 5b 63 6c 6f 63 6b m 0] str] [clock
20b0: 20 66 6f 72 6d 61 74 20 5b 6c 69 6e 64 65 78 20 format [lindex
20c0: 24 69 74 65 6d 20 31 5d 5d 20 5b 63 6c 6f 63 6b $item 1]] [clock
20d0: 20 66 6f 72 6d 61 74 20 5b 6c 69 6e 64 65 78 20 format [lindex
20e0: 24 69 74 65 6d 20 32 5d 5d 5d 0a 20 20 20 20 7d $item 2]]]. }
20f0: 0a 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 43 .. proc FindC
2100: 79 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 ycle {dg} {..# T
2110: 68 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 his procedure is
2120: 20 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 run if and only
2130: 20 74 68 65 20 67 72 61 70 68 20 69 73 20 6e 6f the graph is no
2140: 74 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 t empty and..# a
2150: 6c 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 72 ll nodes have pr
2160: 65 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 73 edecessors. This
2170: 20 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 68 means that each
2180: 20 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 68 node is..# eith
2190: 65 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 63 er part of a cyc
21a0: 6c 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 6c le or (indirectl
21b0: 79 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 y) depending on
21c0: 61 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 a node..# in a c
21d0: 79 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 61 ycle. We can sta
21e0: 72 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 61 rt at an arbitra
21f0: 72 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 ry node, follow
2200: 69 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 its..# incoming
2210: 65 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 65 edges to its pre
2220: 64 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 decessors until
2230: 77 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 0a we see a node a.
2240: 09 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 .# second time.
2250: 54 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 That node closes
2260: 20 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 74 the cycle and t
2270: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a he beginning is.
2280: 09 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 63 .# its first occ
2290: 75 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 urence. Note tha
22a0: 74 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 t we can choose
22b0: 61 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 20 an arbitrary..#
22c0: 70 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 65 predecessor of e
22d0: 61 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c ach node as well
22e0: 2c 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 , we do not have
22f0: 20 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 to search....#
2300: 57 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 61 We record for ea
2310: 63 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 ch node the inde
2320: 78 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 61 x of the first a
2330: 70 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 ppearance in..#
2340: 74 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 the path, making
2350: 20 69 74 20 65 61 73 79 20 61 74 20 74 68 65 20 it easy at the
2360: 65 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 63 end to cut the c
2370: 79 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e ycle from..# it.
2380: 0a 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 69 ...# Choose arbi
2390: 74 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 trary node to st
23a0: 61 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 61 art our search a
23b0: 74 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b 6c t...set start [l
23c0: 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 index [$dg nodes
23d0: 5d 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c ] 0]...# Initial
23e0: 69 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 20 ize state, path
23f0: 6f 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 of seen nodes, a
2400: 6e 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 nd when seen...s
2410: 65 74 20 20 20 20 20 20 20 70 61 74 68 20 7b 7d et path {}
2420: 0a 09 61 72 72 61 79 20 73 65 74 20 73 65 65 6e ..array set seen
2430: 20 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 {}...while {1}
2440: 7b 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 65 {.. # Stop se
2450: 61 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 20 arching when we
2460: 68 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 75 have seen the cu
2470: 72 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 rrent node..
2480: 23 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 63 # already, the c
2490: 69 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 63 ircle has been c
24a0: 6c 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 7b losed... if {
24b0: 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 65 [info exists see
24c0: 6e 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 61 n($start)]} brea
24d0: 6b 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 70 k.. lappend p
24e0: 61 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 20 ath $start..
24f0: 73 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 29 set seen($start)
2500: 20 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 [expr {[llength
2510: 20 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 $path]-1}]..
2520: 20 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 # Choose arbitr
2530: 61 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a ary predecessor.
2540: 09 20 20 20 20 73 65 74 20 73 74 61 72 74 20 5b . set start [
2550: 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 lindex [$dg node
2560: 73 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d s -in $start] 0]
2570: 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 ..}...return [st
2580: 72 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 ruct::list rever
2590: 73 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 se [lrange $path
25a0: 20 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 $seen($start) e
25b0: 6e 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 nd]]. }..
25c0: 70 72 6f 63 20 42 72 65 61 6b 53 65 67 6d 65 6e proc BreakSegmen
25d0: 74 20 7b 64 67 20 70 61 74 68 20 6c 61 62 65 6c t {dg path label
25e0: 7d 20 7b 0a 09 23 20 54 68 65 20 70 61 74 68 2c } {..# The path,
25f0: 20 75 73 75 61 6c 6c 79 20 61 20 63 79 63 6c 65 usually a cycle
2600: 2c 20 77 65 20 68 61 76 65 20 67 6f 74 74 65 6e , we have gotten
2610: 20 69 73 20 62 72 6f 6b 65 6e 20 62 79 0a 09 23 is broken by..#
2620: 20 62 72 65 61 6b 69 6e 67 20 61 70 61 72 74 20 breaking apart
2630: 6f 6e 65 20 6f 72 20 6d 6f 72 65 20 6f 66 20 74 one or more of t
2640: 68 65 20 63 68 61 6e 67 65 73 65 74 73 20 69 6e he changesets in
2650: 20 74 68 65 0a 09 23 20 63 79 63 6c 65 2e 20 54 the..# cycle. T
2660: 68 69 73 20 63 61 75 73 65 73 20 75 73 20 74 6f his causes us to
2670: 20 63 72 65 61 74 65 20 6f 6e 65 20 6f 72 20 6d create one or m
2680: 6f 72 65 20 63 68 61 6e 67 65 73 65 74 73 20 77 ore changesets w
2690: 68 69 63 68 0a 09 23 20 61 72 65 20 74 6f 20 62 hich..# are to b
26a0: 65 20 63 6f 6d 6d 69 74 74 65 64 2c 20 61 64 64 e committed, add
26b0: 65 64 20 74 6f 20 74 68 65 20 67 72 61 70 68 2c ed to the graph,
26c0: 20 65 74 63 2e 20 70 70 2e 0a 0a 09 73 65 74 20 etc. pp....set
26d0: 62 65 73 74 6c 69 6e 6b 20 7b 7d 0a 09 73 65 74 bestlink {}..set
26e0: 20 62 65 73 74 6e 6f 64 65 20 7b 7d 0a 0a 09 66 bestnode {}...f
26f0: 6f 72 65 61 63 68 20 5c 0a 09 20 20 20 20 70 72 oreach \.. pr
2700: 65 76 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 ev [lrange $path
2710: 20 30 20 65 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 0 end-2] \..
2720: 20 63 73 65 74 20 5b 6c 72 61 6e 67 65 20 24 70 cset [lrange $p
2730: 61 74 68 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 ath 1 end-1] \..
2740: 20 20 20 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 next [lrange
2750: 20 24 70 61 74 68 20 32 20 65 6e 64 5d 20 7b 0a $path 2 end] {.
2760: 0a 09 09 23 20 45 61 63 68 20 74 72 69 70 6c 65 ...# Each triple
2770: 20 50 52 45 56 20 2d 3e 20 43 53 45 54 20 2d 3e PREV -> CSET ->
2780: 20 4e 45 58 54 20 6f 66 20 63 68 61 6e 67 65 73 NEXT of changes
2790: 65 74 73 2c 20 61 0a 09 09 23 20 27 6c 69 6e 6b ets, a...# 'link
27a0: 27 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2c 20 ' in the cycle,
27b0: 69 73 20 61 6e 61 6c 79 73 65 64 20 61 6e 64 20 is analysed and
27c0: 74 68 65 20 62 65 73 74 0a 09 09 23 20 6c 6f 63 the best...# loc
27d0: 61 74 69 6f 6e 20 77 68 65 72 65 20 74 6f 20 61 ation where to a
27e0: 74 20 6c 65 61 73 74 20 77 65 61 6b 65 6e 20 74 t least weaken t
27f0: 68 65 20 63 79 63 6c 65 20 69 73 0a 09 09 23 20 he cycle is...#
2800: 63 68 6f 73 65 6e 20 66 6f 72 20 66 75 72 74 68 chosen for furth
2810: 65 72 20 70 72 6f 63 65 73 73 69 6e 67 2e 0a 0a er processing...
2820: 09 09 73 65 74 20 6c 69 6e 6b 20 5b 70 72 6f 6a ..set link [proj
2830: 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 55 ect::revlink %AU
2840: 54 4f 25 20 24 70 72 65 76 20 24 63 73 65 74 20 TO% $prev $cset
2850: 24 6e 65 78 74 5d 0a 09 09 69 66 20 7b 24 62 65 $next]...if {$be
2860: 73 74 6c 69 6e 6b 20 65 71 20 22 22 7d 20 7b 0a stlink eq ""} {.
2870: 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 .. set bestli
2880: 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 nk $link... s
2890: 65 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 et bestnode $cse
28a0: 74 0a 09 09 7d 20 65 6c 73 65 69 66 20 7b 5b 24 t...} elseif {[$
28b0: 6c 69 6e 6b 20 62 65 74 74 65 72 74 68 61 6e 20 link betterthan
28c0: 24 62 65 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 $bestlink]} {...
28d0: 20 20 20 20 24 62 65 73 74 6c 69 6e 6b 20 64 65 $bestlink de
28e0: 73 74 72 6f 79 0a 09 09 20 20 20 20 73 65 74 20 stroy... set
28f0: 62 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 bestlink $link..
2900: 09 20 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 . set bestnod
2910: 65 20 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 e $cset...} else
2920: 20 7b 0a 09 09 20 20 20 20 24 6c 69 6e 6b 20 64 {... $link d
2930: 65 73 74 72 6f 79 0a 09 09 7d 0a 09 20 20 20 20 estroy...}..
2940: 7d 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 20 }...log write 5
2950: 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 42 72 cyclebreaker "Br
2960: 65 61 6b 69 6e 67 20 24 6c 61 62 65 6c 20 62 79 eaking $label by
2970: 20 73 70 6c 69 74 74 69 6e 67 20 63 68 61 6e 67 splitting chang
2980: 65 73 65 74 20 5b 24 62 65 73 74 6e 6f 64 65 20 eset [$bestnode
2990: 73 74 72 5d 22 0a 09 73 65 74 20 49 44 20 5b 24 str]"..set ID [$
29a0: 62 65 73 74 6e 6f 64 65 20 69 64 5d 0a 09 4d 61 bestnode id]..Ma
29b0: 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d 62 65 rk $dg -${ID}-be
29c0: 66 6f 72 65 0a 0a 09 73 65 74 20 6e 65 77 63 73 fore...set newcs
29d0: 65 74 73 20 5b 24 62 65 73 74 6c 69 6e 6b 20 62 ets [$bestlink b
29e0: 72 65 61 6b 5d 0a 09 24 62 65 73 74 6c 69 6e 6b reak]..$bestlink
29f0: 20 64 65 73 74 72 6f 79 0a 0a 20 20 20 20 20 20 destroy..
2a00: 20 20 23 20 41 74 20 74 68 69 73 20 70 6f 69 6e # At this poin
2a10: 74 20 74 68 65 20 6f 6c 64 20 63 68 61 6e 67 65 t the old change
2a20: 73 65 74 20 28 42 45 53 54 4e 4f 44 45 29 20 69 set (BESTNODE) i
2a30: 73 20 67 6f 6e 65 0a 20 20 20 20 20 20 20 20 23 s gone. #
2a40: 20 61 6c 72 65 61 64 79 2e 20 57 65 20 72 65 6d already. We rem
2a50: 6f 76 65 20 69 74 20 66 72 6f 6d 20 74 68 65 20 ove it from the
2a60: 67 72 61 70 68 20 61 73 20 77 65 6c 6c 20 61 6e graph as well an
2a70: 64 20 74 68 65 6e 20 65 6e 74 65 72 0a 20 20 20 d then enter.
2a80: 20 20 20 20 20 23 20 74 68 65 20 66 72 61 67 6d # the fragm
2a90: 65 6e 74 73 20 67 65 6e 65 72 61 74 65 64 20 66 ents generated f
2aa0: 6f 72 20 69 74 2e 0a 0a 09 52 65 70 6c 61 63 65 or it....Replace
2ab0: 20 24 64 67 20 24 62 65 73 74 6e 6f 64 65 20 24 $dg $bestnode $
2ac0: 6e 65 77 63 73 65 74 73 0a 0a 09 4d 61 72 6b 20 newcsets...Mark
2ad0: 24 64 67 20 2d 24 7b 49 44 7d 2d 61 66 74 65 72 $dg -${ID}-after
2ae0: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
2af0: 20 20 20 20 23 20 54 4f 44 4f 3a 20 54 68 69 73 # TODO: This
2b00: 20 73 68 6f 75 6c 64 20 62 65 20 61 20 67 72 61 should be a gra
2b10: 70 68 20 6d 65 74 68 6f 64 2e 0a 20 20 20 20 70 ph method.. p
2b20: 72 6f 63 20 48 61 73 41 72 63 20 7b 64 67 20 61 roc HasArc {dg a
2b30: 20 62 7d 20 7b 0a 09 23 38 2e 35 3a 20 72 65 74 b} {..#8.5: ret
2b40: 75 72 6e 20 5b 65 78 70 72 20 7b 24 62 20 69 6e urn [expr {$b in
2b50: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
2b60: 20 24 61 5d 7d 5d 0a 09 69 66 20 7b 5b 6c 73 65 $a]}]..if {[lse
2b70: 61 72 63 68 20 2d 65 78 61 63 74 20 5b 24 64 67 arch -exact [$dg
2b80: 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 61 5d 20 nodes -out $a]
2b90: 24 62 5d 20 3c 20 30 7d 20 7b 20 72 65 74 75 72 $b] < 0} { retur
2ba0: 6e 20 30 20 7d 0a 09 72 65 74 75 72 6e 20 31 0a n 0 }..return 1.
2bb0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
2bc0: 4d 61 72 6b 20 7b 64 67 20 7b 73 75 66 66 69 78 Mark {dg {suffix
2bd0: 20 7b 7d 7d 20 7b 73 75 62 67 72 61 70 68 20 7b {}} {subgraph {
2be0: 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c }}} {..::variabl
2bf0: 65 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 e mydotdestinati
2c00: 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 6f 74 64 65 on..if {$mydotde
2c10: 73 74 69 6e 61 74 69 6f 6e 20 65 71 20 22 22 7d stination eq ""}
2c20: 20 72 65 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 return..::varia
2c30: 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 0a ble mydotprefix.
2c40: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f .::variable mydo
2c50: 74 69 64 0a 09 73 65 74 20 66 6e 61 6d 65 20 24 tid..set fname $
2c60: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
2c70: 2f 24 7b 6d 79 64 6f 74 70 72 65 66 69 78 7d 24 /${mydotprefix}$
2c80: 7b 6d 79 64 6f 74 69 64 7d 24 7b 73 75 66 66 69 {mydotid}${suffi
2c90: 78 7d 2e 64 6f 74 0a 09 66 69 6c 65 20 6d 6b 64 x}.dot..file mkd
2ca0: 69 72 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 ir [file dirname
2cb0: 20 24 66 6e 61 6d 65 5d 0a 09 64 6f 74 20 77 72 $fname]..dot wr
2cc0: 69 74 65 20 24 64 67 20 24 6d 79 64 6f 74 70 72 ite $dg $mydotpr
2cd0: 65 66 69 78 24 73 75 66 66 69 78 20 24 66 6e 61 efix$suffix $fna
2ce0: 6d 65 20 24 73 75 62 67 72 61 70 68 0a 09 69 6e me $subgraph..in
2cf0: 63 72 20 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f 67 cr mydotid...log
2d00: 20 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 72 write 5 cyclebr
2d10: 65 61 6b 65 72 20 22 2e 64 6f 74 20 65 78 70 6f eaker ".dot expo
2d20: 72 74 20 24 66 6e 61 6d 65 22 0a 09 72 65 74 75 rt $fname"..retu
2d30: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
2d40: 6f 63 20 52 65 70 6c 61 63 65 20 7b 64 67 20 6e oc Replace {dg n
2d50: 20 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b replacements} {
2d60: 0a 09 23 20 4e 4f 54 45 2e 20 57 65 20 68 61 76 ..# NOTE. We hav
2d70: 65 20 74 6f 20 67 65 74 20 74 68 65 20 6c 69 73 e to get the lis
2d80: 74 20 6f 66 20 69 6e 63 6f 6d 69 6e 67 20 6e 65 t of incoming ne
2d90: 69 67 68 62 6f 75 72 73 20 61 6e 64 0a 09 23 20 ighbours and..#
2da0: 72 65 63 6f 6d 70 75 74 65 20 74 68 65 69 72 20 recompute their
2db0: 73 75 63 63 65 73 73 6f 72 73 20 61 66 74 65 72 successors after
2dc0: 20 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 20 68 the new nodes h
2dd0: 61 76 65 20 62 65 65 6e 0a 09 23 20 69 6e 73 65 ave been..# inse
2de0: 72 74 65 64 2e 20 54 68 65 69 72 20 6f 75 74 67 rted. Their outg
2df0: 6f 69 6e 67 20 61 72 63 73 20 77 69 6c 6c 20 6e oing arcs will n
2e00: 6f 77 20 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 20 ow go to one or
2e10: 62 6f 74 68 20 6f 66 0a 09 23 20 74 68 65 20 6e both of..# the n
2e20: 65 77 20 6e 6f 64 65 73 2c 20 61 6e 64 20 6e 6f ew nodes, and no
2e30: 74 20 72 65 64 6f 69 6e 67 20 74 68 65 6d 20 6d t redoing them m
2e40: 61 79 20 63 61 75 73 65 20 75 73 20 74 6f 20 66 ay cause us to f
2e50: 6f 72 67 65 74 0a 09 23 20 63 69 72 63 6c 65 73 orget..# circles
2e60: 2c 20 6c 65 61 76 69 6e 67 20 74 68 65 6d 20 69 , leaving them i
2e70: 6e 2c 20 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 73 n, unbroken....s
2e80: 65 74 20 70 72 65 20 5b 24 64 67 20 6e 6f 64 65 et pre [$dg node
2e90: 73 20 2d 69 6e 20 24 6e 5d 0a 0a 20 20 20 20 20 s -in $n]..
2ea0: 20 20 20 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 $dg node dele
2eb0: 74 65 20 24 6e 0a 0a 09 66 6f 72 65 61 63 68 20 te $n...foreach
2ec0: 63 73 65 74 20 24 72 65 70 6c 61 63 65 6d 65 6e cset $replacemen
2ed0: 74 73 20 7b 0a 09 20 20 20 20 73 65 74 20 74 72 ts {.. set tr
2ee0: 20 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 [$cset timerang
2ef0: 65 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 e].. $dg node
2f00: 20 69 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 insert $cset..
2f10: 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 $dg node set
2f20: 20 20 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e $cset timeran
2f30: 67 65 20 24 74 72 0a 09 20 20 20 20 24 64 67 20 ge $tr.. $dg
2f40: 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 node set $cse
2f50: 74 20 6c 61 62 65 6c 20 20 20 20 20 22 5b 24 63 t label "[$c
2f60: 73 65 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e set str]\\n[join
2f70: 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d [struct::list m
2f80: 61 70 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 ap $tr {::clock
2f90: 66 6f 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 format}] "\\n"]"
2fa0: 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 .. $dg node s
2fb0: 65 74 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 et $cset __id
2fc0: 5f 5f 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d __ [$cset id]
2fd0: 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 .. $dg node s
2fe0: 65 74 20 20 20 20 24 63 73 65 74 20 73 68 61 70 et $cset shap
2ff0: 65 20 20 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 e [expr {[$c
3000: 73 65 74 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 set bysymbol]...
3010: 09 09 09 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 .... ? "ellips
3020: 65 22 0a 09 09 09 09 09 09 20 20 20 3a 20 22 62 e"....... : "b
3030: 6f 78 22 7d 5d 0a 09 7d 0a 0a 09 66 6f 72 65 61 ox"}]..}...forea
3040: 63 68 20 63 73 65 74 20 24 72 65 70 6c 61 63 65 ch cset $replace
3050: 6d 65 6e 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 ments {.. for
3060: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
3070: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
3080: 09 23 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 .# The new chang
3090: 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 esets may have d
30a0: 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 ependencies outs
30b0: 69 64 65 20 6f 66 0a 09 09 23 20 74 68 65 20 63 ide of...# the c
30c0: 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 hosen set. These
30d0: 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 are ignored...i
30e0: 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 f {![$dg node ex
30f0: 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e ists $succ]} con
3100: 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 tinue...$dg arc
3110: 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 insert $cset $su
3120: 63 63 0a 09 09 69 66 20 7b 24 73 75 63 63 20 65 cc...if {$succ e
3130: 71 20 24 63 73 65 74 7d 20 7b 0a 09 09 20 20 20 q $cset} {...
3140: 20 24 63 73 65 74 20 6c 6f 6f 70 63 68 65 63 6b $cset loopcheck
3150: 0a 09 09 20 20 20 20 74 72 6f 75 62 6c 65 20 66 ... trouble f
3160: 61 74 61 6c 20 22 5b 24 63 73 65 74 20 73 74 72 atal "[$cset str
3170: 5d 20 64 65 70 65 6e 64 73 20 6f 6e 20 69 74 73 ] depends on its
3180: 65 6c 66 22 0a 09 09 7d 0a 09 20 20 20 20 7d 0a elf"...}.. }.
3190: 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 .}..foreach cset
31a0: 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 6f 72 $pre {.. for
31b0: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
31c0: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
31d0: 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 68 65 .# Note that the
31e0: 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 64 79 arc may already
31f0: 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 67 72 exist in the gr
3200: 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f 20 69 aph. If...# so i
3210: 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 6e 65 gnore it. The ne
3220: 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d 61 79 w changesets may
3230: 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 6e 64 have...# depend
3240: 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 20 6f encies outside o
3250: 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 65 74 f the chosen set
3260: 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 23 20 . These are...#
3270: 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b ignored...if {![
3280: 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 73 20 $dg node exists
3290: 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 $succ]} continue
32a0: 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 20 24 ...if {[HasArc $
32b0: 64 67 20 24 63 73 65 74 20 24 73 75 63 63 5d 7d dg $cset $succ]}
32c0: 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f 44 4f continue;# TODO
32d0: 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 70 68 should be graph
32e0: 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 20 61 method....$dg a
32f0: 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 rc insert $cset
3300: 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a $succ.. }..}.
3310: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
3320: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
3330: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
3340: 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 20 ###########.
3350: 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 6e 76 6f ## Callback invo
3360: 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 20 20 20 kation .....
3370: 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 7b 67 72 proc PreHook {gr
3380: 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 65 20 74 aph} {..# Give t
3390: 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 63 he user of the c
33a0: 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 65 ycle breaker the
33b0: 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f 20 opportunity to
33c0: 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 65 work..# with the
33d0: 20 67 72 61 70 68 20 62 65 74 77 65 65 6e 20 73 graph between s
33e0: 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 75 6d 6d etup and consumm
33f0: 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 72 69 61 ation....::varia
3400: 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a 09 69 66 ble myprecmd..if
3410: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 70 {![llength $myp
3420: 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a recmd]} return..
3430: 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e .uplevel #0 [lin
3440: 73 65 72 74 20 24 6d 79 70 72 65 63 6d 64 20 65 sert $myprecmd e
3450: 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d 61 72 6b nd $graph]..Mark
3460: 20 24 67 72 61 70 68 20 2d 70 72 65 2d 64 6f 6e $graph -pre-don
3470: 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a e..return. }.
3480: 0a 20 20 20 20 70 72 6f 63 20 50 72 6f 63 65 73 . proc Proces
3490: 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 73 65 74 sedHook {dg cset
34a0: 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 76 65 20 pos} {..# Give
34b0: 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 the user of the
34c0: 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 cycle breaker th
34d0: 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f e opportunity to
34e0: 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 work..# with th
34f0: 65 20 63 68 61 6e 67 65 73 65 74 20 62 65 66 6f e changeset befo
3500: 72 65 20 69 74 20 69 73 20 72 65 6d 6f 76 65 64 re it is removed
3510: 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 68 2e from the graph.
3520: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
3530: 73 61 76 65 63 6d 64 0a 09 69 66 20 7b 21 5b 6c savecmd..if {![l
3540: 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 65 63 6d length $mysavecm
3550: 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 75 70 6c d]} return...upl
3560: 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 evel #0 [linsert
3570: 20 24 6d 79 73 61 76 65 63 6d 64 20 65 6e 64 20 $mysavecmd end
3580: 24 64 67 20 24 70 6f 73 20 24 63 73 65 74 5d 0a $dg $pos $cset].
3590: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
35a0: 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 79 63 proc BreakCyc
35b0: 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 7b leHook {graph} {
35c0: 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 6f 20 ..# Call out to
35d0: 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 6f 72 the chosen algor
35e0: 69 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 20 62 ithm for cycle b
35f0: 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 6e 67 reaking. Finding
3600: 0a 09 23 20 61 20 63 79 63 6c 65 20 69 66 20 6e ..# a cycle if n
3610: 6f 20 62 72 65 61 6b 65 72 20 77 61 73 20 63 68 o breaker was ch
3620: 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 72 6f 72 osen is an error
3630: 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d ....::variable m
3640: 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 7b 21 ybreakcmd..if {!
3650: 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 65 61 [llength $mybrea
3660: 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 74 72 kcmd]} {.. tr
3670: 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 46 6f 75 ouble fatal "Fou
3680: 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 78 70 65 nd a cycle, expe
3690: 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 20 20 cting none."..
36a0: 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 75 70 exit 1..}...up
36b0: 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 level #0 [linser
36c0: 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 65 6e t $mybreakcmd en
36d0: 64 20 24 67 72 61 70 68 5d 0a 09 72 65 74 75 72 d $graph]..retur
36e0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
36f0: 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b 7d 20 c ClearHooks {}
3700: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 {..::variable my
3710: 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 3a 3a 76 precmd {}..::v
3720: 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d ariable mysavecm
3730: 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 62 6c d {}..::variabl
3740: 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b 7d 0a e mybreakcmd {}.
3750: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
3760: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
3770: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
3780: 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 ##########..
3790: 70 72 6f 63 20 4d 61 72 6b 57 61 74 63 68 20 7b proc MarkWatch {
37a0: 67 72 61 70 68 7d 20 7b 0a 09 3a 3a 76 61 72 69 graph} {..::vari
37b0: 61 62 6c 65 20 6d 79 77 61 74 63 68 69 64 73 0a able mywatchids.
37c0: 09 73 65 74 20 77 61 74 63 68 65 64 20 5b 57 61 .set watched [Wa
37d0: 74 63 68 65 64 20 24 67 72 61 70 68 20 24 6d 79 tched $graph $my
37e0: 77 61 74 63 68 69 64 73 5d 0a 09 69 66 20 7b 21 watchids]..if {!
37f0: 5b 6c 6c 65 6e 67 74 68 20 24 77 61 74 63 68 65 [llength $watche
3800: 64 5d 7d 20 72 65 74 75 72 6e 0a 09 73 65 74 20 d]} return..set
3810: 6e 65 69 67 68 62 6f 75 72 73 20 5b 65 76 61 6c neighbours [eval
3820: 20 5b 6c 69 6e 73 65 72 74 20 24 77 61 74 63 68 [linsert $watch
3830: 65 64 20 30 20 24 67 72 61 70 68 20 6e 6f 64 65 ed 0 $graph node
3840: 73 20 2d 61 64 6a 5d 5d 0a 09 23 66 6f 72 65 61 s -adj]]..#forea
3850: 63 68 20 6e 20 24 6e 65 69 67 68 62 6f 75 72 73 ch n $neighbours
3860: 20 7b 20 6c 6f 67 20 77 72 69 74 65 20 36 20 63 { log write 6 c
3870: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 4e 65 69 yclebreaker "Nei
3880: 67 68 62 6f 72 20 5b 24 6e 20 69 64 5d 20 3d 3e ghbor [$n id] =>
3890: 20 24 6e 22 20 7d 0a 09 4d 61 72 6b 20 24 67 72 $n" }..Mark $gr
38a0: 61 70 68 20 77 61 74 63 68 65 64 20 5b 63 6f 6e aph watched [con
38b0: 63 61 74 20 24 77 61 74 63 68 65 64 20 24 6e 65 cat $watched $ne
38c0: 69 67 68 62 6f 75 72 73 5d 0a 09 72 65 74 75 72 ighbours]..retur
38d0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
38e0: 63 20 57 61 74 63 68 65 64 20 7b 67 72 61 70 68 c Watched {graph
38f0: 20 77 61 74 63 68 69 64 73 7d 20 7b 0a 09 73 65 watchids} {..se
3900: 74 20 72 65 73 20 7b 7d 0a 09 66 6f 72 65 61 63 t res {}..foreac
3910: 68 20 69 64 20 24 77 61 74 63 68 69 64 73 20 7b h id $watchids {
3920: 0a 09 20 20 20 20 73 65 74 20 6e 6c 20 5b 24 67 .. set nl [$g
3930: 72 61 70 68 20 6e 6f 64 65 73 20 2d 6b 65 79 20 raph nodes -key
3940: 5f 5f 69 64 5f 5f 20 2d 76 61 6c 75 65 20 24 69 __id__ -value $i
3950: 64 5d 0a 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c d].. if {![ll
3960: 65 6e 67 74 68 20 24 6e 6c 5d 7d 20 63 6f 6e 74 ength $nl]} cont
3970: 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 65 6e inue.. lappen
3980: 64 20 72 65 73 20 24 6e 6c 0a 09 20 20 20 20 23 d res $nl.. #
3990: 6c 6f 67 20 77 72 69 74 65 20 36 20 62 72 65 61 log write 6 brea
39a0: 6b 72 63 79 63 6c 65 20 22 57 61 74 63 68 69 6e krcycle "Watchin
39b0: 67 20 24 69 64 20 3d 3e 20 24 6e 6c 22 0a 09 20 g $id => $nl"..
39c0: 20 20 20 24 67 72 61 70 68 20 6e 6f 64 65 20 73 $graph node s
39d0: 65 74 20 24 6e 6c 20 66 6f 6e 74 63 6f 6c 6f 72 et $nl fontcolor
39e0: 20 72 65 64 0a 09 7d 0a 09 72 65 74 75 72 6e 20 red..}..return
39f0: 24 72 65 73 0a 20 20 20 20 7d 0a 0a 20 20 20 20 $res. }..
3a00: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
3a10: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
3a20: 23 23 23 23 23 23 23 0a 0a 0a 20 20 20 20 74 79 #######... ty
3a30: 70 65 76 61 72 69 61 62 6c 65 20 6d 79 61 74 20 pevariable myat
3a40: 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 0 ; # Count
3a50: 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 69 64 er for commit id
3a60: 73 20 66 6f 72 20 74 68 65 0a 09 09 09 20 20 20 s for the....
3a70: 20 20 20 20 23 20 63 68 61 6e 67 65 73 65 74 73 # changesets
3a80: 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 62 .. typevariab
3a90: 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b 7d 20 3b le mybottom {} ;
3aa0: 20 23 20 4c 69 73 74 20 6f 66 20 74 68 65 20 63 # List of the c
3ab0: 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 73 20 66 andidate nodes f
3ac0: 6f 72 0a 09 09 09 20 20 20 20 20 20 20 23 20 63 or.... # c
3ad0: 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 20 20 20 ommitting...
3ae0: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 70 typevariable myp
3af0: 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 23 20 43 recmd {} ; # C
3b00: 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e 67 65 20 allback, change
3b10: 67 72 61 70 68 20 62 65 66 6f 72 65 20 77 61 6c graph before wal
3b20: 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 k.. typevaria
3b30: 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 20 7b ble mysavecmd {
3b40: 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b 2c 20 } ; # Callback,
3b50: 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 73 73 for each process
3b60: 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 74 79 70 ed node.. typ
3b70: 65 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 evariable mybrea
3b80: 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 61 6c 6c kcmd {} ; # Call
3b90: 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 68 20 66 back, for each f
3ba0: 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 20 20 ound cycle...
3bb0: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3bc0: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 7b dotdestination {
3bd0: 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 74 69 6f } ; # Destinatio
3be0: 6e 20 64 69 72 65 63 74 6f 72 79 20 66 6f 72 20 n directory for
3bf0: 74 68 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 the..... #
3c00: 20 67 65 6e 65 72 61 74 65 64 20 2e 64 6f 74 20 generated .dot
3c10: 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 70 65 76 files.. typev
3c20: 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 ariable mydotpre
3c30: 66 69 78 20 20 20 20 20 20 7b 7d 20 3b 20 23 20 fix {} ; #
3c40: 50 72 65 66 69 78 20 66 6f 72 20 64 6f 74 20 66 Prefix for dot f
3c50: 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 09 20 20 iles when.....
3c60: 20 20 20 20 20 23 20 65 78 70 6f 72 74 69 6e 67 # exporting
3c70: 20 74 68 65 20 67 72 61 70 68 73 2e 0a 20 20 20 the graphs..
3c80: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3c90: 64 6f 74 69 64 20 20 20 20 20 20 20 20 20 20 20 dotid
3ca0: 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 66 6f 0 ; # Counter fo
3cb0: 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 6d 65 0a r dot file name.
3cc0: 09 09 09 09 20 20 20 20 20 20 20 23 20 67 65 6e .... # gen
3cd0: 65 72 61 74 69 6f 6e 2e 0a 20 20 20 20 74 79 70 eration.. typ
3ce0: 65 76 61 72 69 61 62 6c 65 20 6d 79 77 61 74 63 evariable mywatc
3cf0: 68 69 64 73 20 20 20 20 20 20 20 7b 7d 20 3b 20 hids {} ;
3d00: 23 20 43 68 61 6e 67 65 73 65 74 73 20 74 6f 20 # Changesets to
3d10: 77 61 74 63 68 20 74 68 65 0a 09 09 09 09 20 20 watch the.....
3d20: 20 20 20 20 20 23 20 6e 65 69 67 68 62 6f 75 72 # neighbour
3d30: 68 6f 6f 64 20 6f 66 2e 0a 0a 20 20 20 20 23 20 hood of... #
3d40: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
3d50: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
3d60: 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 6f 6e #####. ## Con
3d70: 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 20 20 figuration..
3d80: 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 74 61 pragma -hasinsta
3d90: 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 73 69 nces no ; # si
3da0: 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 61 67 ngleton. prag
3db0: 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 6f 20 ma -hastypeinfo
3dc0: 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 6e 74 no ; # no int
3dd0: 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 20 70 rospection. p
3de0: 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 64 65 ragma -hastypede
3df0: 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 6d 6d stroy no ; # imm
3e00: 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 20 23 ortal.. # # #
3e10: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
3e20: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
3e30: 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 65 20 ##.}..namespace
3e40: 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 eval ::vc::fossi
3e50: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 20 7b l::import::cvs {
3e60: 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 . namespace e
3e70: 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 61 6b xport cyclebreak
3e80: 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 er. namespace
3e90: 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 61 6b eval cyclebreak
3ea0: 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 20 er {..namespace
3eb0: 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b 0a 09 eval project {..
3ec0: 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d namespace im
3ed0: 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 port ::vc::fossi
3ee0: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a l::import::cvs::
3ef0: 69 6e 74 65 67 72 69 74 79 0a 09 20 20 20 20 6e integrity.. n
3f00: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
3f10: 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d ::vc::fossil::im
3f20: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 port::cvs::proje
3f30: 63 74 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d ct::rev.. nam
3f40: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3f50: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
3f60: 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 rt::cvs::project
3f70: 3a 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 ::revlink..}..na
3f80: 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a mespace import :
3f90: 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 :vc::tools::misc
3fa0: 3a 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 ::*..namespace i
3fb0: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c mport ::vc::tool
3fc0: 73 3a 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 s::log..namespac
3fd0: 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 e import ::vc::t
3fe0: 6f 6f 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a 09 6e ools::trouble..n
3ff0: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
4000: 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 ::vc::tools::dot
4010: 0a 09 6c 6f 67 20 72 65 67 69 73 74 65 72 20 63 ..log register c
4020: 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 yclebreaker.
4030: 7d 0a 7d 0a 0a 23 20 23 20 23 23 20 23 23 23 20 }.}..# # ## ###
4040: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
4050: 23 23 23 23 23 23 23 23 23 23 23 23 20 23 23 23 ############ ###
4060: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
4070: 23 23 0a 23 23 20 52 65 61 64 79 0a 0a 70 61 63 ##.## Ready..pac
4080: 6b 61 67 65 20 70 72 6f 76 69 64 65 20 76 63 3a kage provide vc:
4090: 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a :fossil::import:
40a0: 3a 63 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b :cvs::cyclebreak
40b0: 65 72 20 31 2e 30 0a 72 65 74 75 72 6e 0a er 1.0.return.