Artifact 6e157515edcd96eb7d7b82adf78a73e01b103de9:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[487bb1c619]
- Modified loop check in cycle breaker to abort immediately on first looped changeset.
by
aku on
2007-12-02 06:18:42.
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 73 65 74 20 graph dg]...set
13b0: 6e 20 30 0a 09 73 65 74 20 6d 61 78 20 5b 6c 6c n 0..set max [ll
13c0: 65 6e 67 74 68 20 24 63 68 61 6e 67 65 73 65 74 ength $changeset
13d0: 73 5d 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 s]...foreach cse
13e0: 74 20 24 63 68 61 6e 67 65 73 65 74 73 20 7b 0a t $changesets {.
13f0: 09 20 20 20 20 6c 6f 67 20 70 72 6f 67 72 65 73 . log progres
1400: 73 20 32 20 63 79 63 6c 65 62 72 65 61 6b 65 72 s 2 cyclebreaker
1410: 20 24 6e 20 24 6d 61 78 0a 09 20 20 20 20 73 65 $n $max.. se
1420: 74 20 74 72 20 5b 24 63 73 65 74 20 74 69 6d 65 t tr [$cset time
1430: 72 61 6e 67 65 5d 0a 09 20 20 20 20 24 64 67 20 range].. $dg
1440: 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 node insert $cse
1450: 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 t.. $dg node
1460: 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 6d set $cset tim
1470: 65 72 61 6e 67 65 20 24 74 72 0a 09 20 20 20 20 erange $tr..
1480: 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 $dg node set
1490: 24 63 73 65 74 20 6c 61 62 65 6c 20 20 20 20 20 $cset label
14a0: 22 5b 24 63 73 65 74 20 73 74 72 5d 5c 5c 6e 5b "[$cset str]\\n[
14b0: 6a 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 join [struct::li
14c0: 73 74 20 6d 61 70 20 24 74 72 20 7b 3a 3a 63 6c st map $tr {::cl
14d0: 6f 63 6b 20 66 6f 72 6d 61 74 7d 5d 20 22 5c 5c ock format}] "\\
14e0: 6e 22 5d 22 0a 09 20 20 20 20 24 64 67 20 6e 6f n"]".. $dg no
14f0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
1500: 5f 5f 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 74 __id__ [$cset
1510: 20 69 64 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f id].. $dg no
1520: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
1530: 73 68 61 70 65 20 20 20 20 20 5b 65 78 70 72 20 shape [expr
1540: 7b 5b 24 63 73 65 74 20 62 79 73 79 6d 62 6f 6c {[$cset bysymbol
1550: 5d 0a 09 09 09 09 09 09 20 20 20 3f 20 22 65 6c ]....... ? "el
1560: 6c 69 70 73 65 22 0a 09 09 09 09 09 09 20 20 20 lipse".......
1570: 3a 20 22 62 6f 78 22 7d 5d 0a 09 20 20 20 20 69 : "box"}].. i
1580: 6e 63 72 20 6e 0a 09 7d 0a 0a 09 69 66 20 7b 24 ncr n..}...if {$
1590: 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 20 log} {.. log
15a0: 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 write 3 cyclebre
15b0: 61 6b 65 72 20 22 48 61 73 20 5b 6e 73 70 20 5b aker "Has [nsp [
15c0: 6c 6c 65 6e 67 74 68 20 24 63 68 61 6e 67 65 73 llength $changes
15d0: 65 74 73 5d 20 63 68 61 6e 67 65 73 65 74 5d 22 ets] changeset]"
15e0: 0a 09 7d 0a 0a 09 23 20 32 2e 20 46 69 6e 64 20 ..}...# 2. Find
15f0: 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 for all relevant
1600: 20 63 68 61 6e 67 65 73 65 74 20 74 68 65 69 72 changeset their
1610: 20 72 65 76 69 73 69 6f 6e 73 20 61 6e 64 20 74 revisions and t
1620: 68 65 69 72 0a 09 23 20 20 20 20 64 65 70 65 6e heir..# depen
1630: 64 65 6e 63 69 65 73 2e 20 4d 61 70 20 74 68 65 dencies. Map the
1640: 20 6c 61 74 74 65 72 20 62 61 63 6b 20 74 6f 20 latter back to
1650: 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 0a 09 changesets and..
1660: 23 20 20 20 20 63 6f 6e 73 74 72 75 63 74 20 74 # construct t
1670: 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 he corresponding
1680: 20 61 72 63 73 2e 0a 0a 09 73 65 74 20 6e 20 30 arcs....set n 0
1690: 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 ..foreach cset $
16a0: 63 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 changesets {..
16b0: 20 20 6c 6f 67 20 70 72 6f 67 72 65 73 73 20 32 log progress 2
16c0: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 24 6e cyclebreaker $n
16d0: 20 24 6d 61 78 0a 09 20 20 20 20 66 6f 72 65 61 $max.. forea
16e0: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 ch succ [$cset s
16f0: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 uccessors] {...#
1700: 20 43 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 Changesets may
1710: 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 have dependencie
1720: 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 s outside of the
1730: 0a 09 09 23 20 63 68 6f 73 65 6e 20 73 65 74 2e ...# chosen set.
1740: 20 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 These are ignor
1750: 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e ed...if {![$dg n
1760: 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 ode exists $succ
1770: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 ]} continue...$d
1780: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
1790: 65 74 20 24 73 75 63 63 0a 09 09 69 66 20 7b 24 et $succ...if {$
17a0: 73 75 63 63 20 65 71 20 24 63 73 65 74 7d 20 7b succ eq $cset} {
17b0: 0a 09 09 20 20 20 20 24 63 73 65 74 20 6c 6f 6f ... $cset loo
17c0: 70 63 68 65 63 6b 0a 09 09 20 20 20 20 74 72 6f pcheck... tro
17d0: 75 62 6c 65 20 69 6e 74 65 72 6e 61 6c 20 22 5b uble internal "[
17e0: 24 63 73 65 74 20 73 74 72 5d 20 64 65 70 65 6e $cset str] depen
17f0: 64 73 20 6f 6e 20 69 74 73 65 6c 66 22 0a 09 09 ds on itself"...
1800: 7d 0a 09 20 20 20 20 7d 0a 09 20 20 20 20 69 6e }.. }.. in
1810: 63 72 20 6e 0a 09 7d 0a 0a 09 69 66 20 7b 24 6c cr n..}...if {$l
1820: 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 20 77 og} {.. log w
1830: 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 rite 3 cyclebrea
1840: 6b 65 72 20 22 48 61 73 20 5b 6e 73 70 20 5b 6c ker "Has [nsp [l
1850: 6c 65 6e 67 74 68 20 5b 24 64 67 20 61 72 63 73 length [$dg arcs
1860: 5d 5d 20 64 65 70 65 6e 64 65 6e 63 79 20 64 65 ]] dependency de
1870: 70 65 6e 64 65 6e 63 69 65 73 5d 22 0a 09 7d 0a pendencies]"..}.
1880: 0a 09 23 20 52 75 6e 20 74 68 65 20 75 73 65 72 ..# Run the user
1890: 20 68 6f 6f 6b 20 74 6f 20 6d 61 6e 69 70 75 6c hook to manipul
18a0: 61 74 65 20 74 68 65 20 67 72 61 70 68 20 62 65 ate the graph be
18b0: 66 6f 72 65 0a 09 23 20 63 6f 6e 73 75 6d 6d 61 fore..# consumma
18c0: 74 69 6f 6e 2e 0a 0a 09 69 66 20 7b 24 6c 6f 67 tion....if {$log
18d0: 7d 20 7b 20 4d 61 72 6b 20 24 64 67 20 2d 73 74 } { Mark $dg -st
18e0: 61 72 74 20 7d 0a 09 4d 61 72 6b 57 61 74 63 68 art }..MarkWatch
18f0: 20 24 64 67 0a 09 50 72 65 48 6f 6f 6b 20 20 20 $dg..PreHook
1900: 24 64 67 0a 09 4d 61 72 6b 57 61 74 63 68 20 24 $dg..MarkWatch $
1910: 64 67 0a 09 72 65 74 75 72 6e 20 20 24 64 67 0a dg..return $dg.
1920: 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 49 6e 73 }.. # Ins
1930: 74 65 61 64 20 6f 66 20 73 65 61 72 63 68 69 6e tead of searchin
1940: 67 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61 70 g the whole grap
1950: 68 20 66 6f 72 20 74 68 65 20 64 65 67 72 65 65 h for the degree
1960: 2d 30 20 6e 6f 64 65 73 20 69 6e 0a 20 20 20 20 -0 nodes in.
1970: 23 20 65 61 63 68 20 69 74 65 72 61 74 69 6f 6e # each iteration
1980: 20 77 65 20 63 6f 6d 70 75 74 65 20 74 68 65 20 we compute the
1990: 6c 69 73 74 20 6f 6e 63 65 20 74 6f 20 73 74 61 list once to sta
19a0: 72 74 2c 20 61 6e 64 20 74 68 65 6e 20 6f 6e 6c rt, and then onl
19b0: 79 0a 20 20 20 20 23 20 75 70 64 61 74 65 20 69 y. # update i
19c0: 74 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 20 t incrementally
19d0: 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6f 75 74 based on the out
19e0: 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 going neighbours
19f0: 20 6f 66 20 74 68 65 0a 20 20 20 20 23 20 6e 6f of the. # no
1a00: 64 65 20 63 68 6f 73 65 6e 20 66 6f 72 20 63 6f de chosen for co
1a10: 6d 6d 69 74 2e 0a 0a 20 20 20 20 70 72 6f 63 20 mmit... proc
1a20: 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 InitializeCandid
1a30: 61 74 65 73 20 7b 64 67 7d 20 7b 0a 09 23 20 62 ates {dg} {..# b
1a40: 6f 74 74 6f 6d 20 3d 20 6c 69 73 74 20 28 6c 69 ottom = list (li
1a50: 73 74 20 28 6e 6f 64 65 2c 20 72 61 6e 67 65 20 st (node, range
1a60: 6d 69 6e 2c 20 72 61 6e 67 65 20 6d 61 78 29 29 min, range max))
1a70: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 ..::variable myb
1a80: 6f 74 74 6f 6d 0a 09 66 6f 72 65 61 63 68 20 6e ottom..foreach n
1a90: 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 7b 0a 09 [$dg nodes] {..
1aa0: 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 if {[$dg nod
1ab0: 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 6e 5d e degree -in $n]
1ac0: 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 } continue..
1ad0: 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 6f 6d lappend mybottom
1ae0: 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 6e [linsert [$dg n
1af0: 6f 64 65 20 67 65 74 20 24 6e 20 74 69 6d 65 72 ode get $n timer
1b00: 61 6e 67 65 5d 20 30 20 24 6e 5d 0a 09 7d 0a 09 ange] 0 $n]..}..
1b10: 53 63 68 65 64 75 6c 65 43 61 6e 64 69 64 61 74 ScheduleCandidat
1b20: 65 73 0a 09 53 68 6f 77 50 65 6e 64 69 6e 67 4e es..ShowPendingN
1b30: 6f 64 65 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 odes..return.
1b40: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 74 }.. proc Wit
1b50: 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 houtPredecessor
1b60: 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 72 {dg nv} {..::var
1b70: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 0a iable mybottom..
1b80: 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e 0a 09 .upvar 1 $nv n..
1b90: 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d if {![llength $m
1ba0: 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 ybottom]} { retu
1bb0: 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e 20 5b rn 0 }...set n [
1bc0: 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 20 24 lindex [lindex $
1bd0: 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d 0a 09 mybottom 0] 0]..
1be0: 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 72 set mybottom [lr
1bf0: 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d 20 31 ange $mybottom 1
1c00: 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 6e 67 end]..set chang
1c10: 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 65 20 ed 0...# Update
1c20: 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 77 69 list of nodes wi
1c30: 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f thout predecesso
1c40: 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 65 0a r, based on the.
1c50: 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 .# outgoing neig
1c60: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 63 68 hbours of the ch
1c70: 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 73 20 osen node. This
1c80: 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 61 73 should be..# fas
1c90: 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 74 69 ter than iterati
1ca0: 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 20 ng of the whole
1cb0: 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 66 69 set of nodes, fi
1cc0: 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 69 74 nding all..# wit
1cd0: 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f 72 hout predecessor
1ce0: 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 6d 20 s, sorting them
1cf0: 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 70 70 by time, etc. pp
1d00: 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 20 5b ...foreach out [
1d10: 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 $dg nodes -out $
1d20: 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 n] {.. if {[$
1d30: 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d dg node degree -
1d40: 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 63 6f in $out] > 1} co
1d50: 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 44 65 ntinue.. # De
1d60: 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f 75 72 gree-1 neighbour
1d70: 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f 20 70 , will have no p
1d80: 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 74 65 redecessors afte
1d90: 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 65 6d r the.. # rem
1da0: 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 20 6f oval of n. Put o
1db0: 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 20 20 n the list...
1dc0: 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 6f lappend mybotto
1dd0: 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 m [linsert [$dg
1de0: 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 74 69 node get $out ti
1df0: 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 74 5d merange] 0 $out]
1e00: 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e 67 65 .. set change
1e10: 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 68 61 d 1..}..if {$cha
1e20: 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 53 63 68 nged} {.. Sch
1e30: 65 64 75 6c 65 43 61 6e 64 69 64 61 74 65 73 0a eduleCandidates.
1e40: 09 7d 0a 0a 09 23 20 57 65 20 64 6f 20 6e 6f 74 .}...# We do not
1e50: 20 64 65 6c 65 74 65 20 74 68 65 20 6e 6f 64 65 delete the node
1e60: 20 69 6d 6d 65 64 69 61 74 65 6c 79 2c 20 74 6f immediately, to
1e70: 20 61 6c 6c 6f 77 20 74 68 65 20 53 61 76 65 0a allow the Save.
1e80: 09 23 20 70 72 6f 63 65 64 75 72 65 20 74 6f 20 .# procedure to
1e90: 73 61 76 65 20 74 68 65 20 64 65 70 65 6e 64 65 save the depende
1ea0: 6e 63 69 65 73 20 61 73 20 77 65 6c 6c 20 28 65 ncies as well (e
1eb0: 6e 63 6f 64 65 64 20 69 6e 20 74 68 65 0a 09 23 ncoded in the..#
1ec0: 20 61 72 63 73 29 2e 0a 09 72 65 74 75 72 6e 20 arcs)...return
1ed0: 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 1. }.. pro
1ee0: 63 20 53 63 68 65 64 75 6c 65 43 61 6e 64 69 64 c ScheduleCandid
1ef0: 61 74 65 73 20 7b 7d 20 7b 0a 09 3a 3a 76 61 72 ates {} {..::var
1f00: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 iable mybottom..
1f10: 23 20 53 6f 72 74 20 62 79 20 63 73 65 74 20 6f # Sort by cset o
1f20: 62 6a 65 63 74 20 6e 61 6d 65 2c 20 6c 6f 77 65 bject name, lowe
1f30: 72 20 62 6f 72 64 65 72 20 6f 66 20 74 69 6d 65 r border of time
1f40: 72 61 6e 67 65 2c 20 61 74 20 6c 61 73 74 0a 09 range, at last..
1f50: 23 20 62 79 20 74 68 65 20 75 70 70 65 72 20 62 # by the upper b
1f60: 6f 72 64 65 72 2e 0a 09 73 65 74 20 6d 79 62 6f order...set mybo
1f70: 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 ttom [lsort -ind
1f80: 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 5b 6c ex 2 -integer [l
1f90: 73 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 sort -index 1 -i
1fa0: 6e 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 nteger [lsort -i
1fb0: 6e 64 65 78 20 30 20 2d 64 69 63 74 20 24 6d 79 ndex 0 -dict $my
1fc0: 62 6f 74 74 6f 6d 5d 5d 5d 0a 09 72 65 74 75 72 bottom]]]..retur
1fd0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
1fe0: 63 20 53 68 6f 77 50 65 6e 64 69 6e 67 4e 6f 64 c ShowPendingNod
1ff0: 65 73 20 7b 7d 20 7b 0a 09 69 66 20 7b 5b 6c 6f es {} {..if {[lo
2000: 67 20 76 65 72 62 6f 73 69 74 79 3f 5d 20 3c 20 g verbosity?] <
2010: 31 30 7d 20 72 65 74 75 72 6e 0a 09 3a 3a 76 61 10} return..::va
2020: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
2030: 09 6c 6f 67 20 77 72 69 74 65 20 31 30 20 63 79 .log write 10 cy
2040: 63 6c 65 62 72 65 61 6b 65 72 20 22 50 65 6e 64 clebreaker "Pend
2050: 69 6e 67 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ing.............
2060: 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ................
2070: 2e 2e 22 0a 09 66 6f 72 65 61 63 68 20 69 74 65 .."..foreach ite
2080: 6d 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 m [struct::list
2090: 6d 61 70 20 24 6d 79 62 6f 74 74 6f 6d 20 5b 6d map $mybottom [m
20a0: 79 70 72 6f 63 20 46 6f 72 6d 61 74 50 65 6e 64 yproc FormatPend
20b0: 69 6e 67 49 74 65 6d 5d 5d 20 7b 0a 09 20 20 20 ingItem]] {..
20c0: 20 6c 6f 67 20 77 72 69 74 65 20 31 30 20 63 79 log write 10 cy
20d0: 63 6c 65 62 72 65 61 6b 65 72 20 22 50 65 6e 64 clebreaker "Pend
20e0: 69 6e 67 3a 20 20 20 20 20 24 69 74 65 6d 22 0a ing: $item".
20f0: 09 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d .}..return. }
2100: 0a 0a 20 20 20 20 70 72 6f 63 20 46 6f 72 6d 61 .. proc Forma
2110: 74 50 65 6e 64 69 6e 67 49 74 65 6d 20 7b 69 74 tPendingItem {it
2120: 65 6d 7d 20 7b 0a 09 6a 6f 69 6e 20 5b 6c 69 73 em} {..join [lis
2130: 74 20 5b 5b 6c 69 6e 64 65 78 20 24 69 74 65 6d t [[lindex $item
2140: 20 30 5d 20 73 74 72 5d 20 5b 63 6c 6f 63 6b 20 0] str] [clock
2150: 66 6f 72 6d 61 74 20 5b 6c 69 6e 64 65 78 20 24 format [lindex $
2160: 69 74 65 6d 20 31 5d 5d 20 5b 63 6c 6f 63 6b 20 item 1]] [clock
2170: 66 6f 72 6d 61 74 20 5b 6c 69 6e 64 65 78 20 24 format [lindex $
2180: 69 74 65 6d 20 32 5d 5d 5d 0a 20 20 20 20 7d 0a item 2]]]. }.
2190: 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 43 79 . proc FindCy
21a0: 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 68 cle {dg} {..# Th
21b0: 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 20 is procedure is
21c0: 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 20 run if and only
21d0: 74 68 65 20 67 72 61 70 68 20 69 73 20 6e 6f 74 the graph is not
21e0: 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 6c empty and..# al
21f0: 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 72 65 l nodes have pre
2200: 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 73 20 decessors. This
2210: 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 68 20 means that each
2220: 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 68 65 node is..# eithe
2230: 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 63 6c r part of a cycl
2240: 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 6c 79 e or (indirectly
2250: 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 61 ) depending on a
2260: 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 79 node..# in a cy
2270: 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 61 72 cle. We can star
2280: 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 61 72 t at an arbitrar
2290: 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 69 y node, follow i
22a0: 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 65 ts..# incoming e
22b0: 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 65 64 dges to its pred
22c0: 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 77 ecessors until w
22d0: 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 0a 09 e see a node a..
22e0: 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 54 # second time. T
22f0: 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 20 hat node closes
2300: 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 74 68 the cycle and th
2310: 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a 09 e beginning is..
2320: 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 63 75 # its first occu
2330: 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 74 rence. Note that
2340: 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 61 we can choose a
2350: 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 20 70 n arbitrary..# p
2360: 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 65 61 redecessor of ea
2370: 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c 2c ch node as well,
2380: 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 we do not have
2390: 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 57 to search....# W
23a0: 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 61 63 e record for eac
23b0: 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 78 h node the index
23c0: 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 61 70 of the first ap
23d0: 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 74 pearance in..# t
23e0: 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 20 he path, making
23f0: 69 74 20 65 61 73 79 20 61 74 20 74 68 65 20 65 it easy at the e
2400: 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 63 79 nd to cut the cy
2410: 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e 0a cle from..# it..
2420: 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 ..# Choose arbit
2430: 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 61 rary node to sta
2440: 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 61 74 rt our search at
2450: 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b 6c 69 ...set start [li
2460: 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 5d ndex [$dg nodes]
2470: 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c 69 0]...# Initiali
2480: 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 20 6f ze state, path o
2490: 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 6e f seen nodes, an
24a0: 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 65 d when seen...se
24b0: 74 20 20 20 20 20 20 20 70 61 74 68 20 7b 7d 0a t path {}.
24c0: 09 61 72 72 61 79 20 73 65 74 20 73 65 65 6e 20 .array set seen
24d0: 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b {}...while {1} {
24e0: 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 65 61 .. # Stop sea
24f0: 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 20 68 rching when we h
2500: 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 75 72 ave seen the cur
2510: 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 23 rent node.. #
2520: 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 63 69 already, the ci
2530: 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 63 6c rcle has been cl
2540: 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 7b 5b osed... if {[
2550: 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 65 6e info exists seen
2560: 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 61 6b ($start)]} break
2570: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 70 61 .. lappend pa
2580: 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 20 73 th $start.. s
2590: 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 29 20 et seen($start)
25a0: 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 20 [expr {[llength
25b0: 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 20 $path]-1}]..
25c0: 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 # Choose arbitra
25d0: 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 ry predecessor..
25e0: 20 20 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c set start [l
25f0: 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 index [$dg nodes
2600: 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a -in $start] 0].
2610: 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 .}...return [str
2620: 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 uct::list revers
2630: 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 e [lrange $path
2640: 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e $seen($start) en
2650: 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 d]]. }.. p
2660: 72 6f 63 20 42 72 65 61 6b 53 65 67 6d 65 6e 74 roc BreakSegment
2670: 20 7b 64 67 20 70 61 74 68 20 6c 61 62 65 6c 7d {dg path label}
2680: 20 7b 0a 09 23 20 54 68 65 20 70 61 74 68 2c 20 {..# The path,
2690: 75 73 75 61 6c 6c 79 20 61 20 63 79 63 6c 65 2c usually a cycle,
26a0: 20 77 65 20 68 61 76 65 20 67 6f 74 74 65 6e 20 we have gotten
26b0: 69 73 20 62 72 6f 6b 65 6e 20 62 79 0a 09 23 20 is broken by..#
26c0: 62 72 65 61 6b 69 6e 67 20 61 70 61 72 74 20 6f breaking apart o
26d0: 6e 65 20 6f 72 20 6d 6f 72 65 20 6f 66 20 74 68 ne or more of th
26e0: 65 20 63 68 61 6e 67 65 73 65 74 73 20 69 6e 20 e changesets in
26f0: 74 68 65 0a 09 23 20 63 79 63 6c 65 2e 20 54 68 the..# cycle. Th
2700: 69 73 20 63 61 75 73 65 73 20 75 73 20 74 6f 20 is causes us to
2710: 63 72 65 61 74 65 20 6f 6e 65 20 6f 72 20 6d 6f create one or mo
2720: 72 65 20 63 68 61 6e 67 65 73 65 74 73 20 77 68 re changesets wh
2730: 69 63 68 0a 09 23 20 61 72 65 20 74 6f 20 62 65 ich..# are to be
2740: 20 63 6f 6d 6d 69 74 74 65 64 2c 20 61 64 64 65 committed, adde
2750: 64 20 74 6f 20 74 68 65 20 67 72 61 70 68 2c 20 d to the graph,
2760: 65 74 63 2e 20 70 70 2e 0a 0a 09 73 65 74 20 62 etc. pp....set b
2770: 65 73 74 6c 69 6e 6b 20 7b 7d 0a 09 73 65 74 20 estlink {}..set
2780: 62 65 73 74 6e 6f 64 65 20 7b 7d 0a 0a 09 66 6f bestnode {}...fo
2790: 72 65 61 63 68 20 5c 0a 09 20 20 20 20 70 72 65 reach \.. pre
27a0: 76 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 v [lrange $path
27b0: 30 20 65 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 20 0 end-2] \..
27c0: 63 73 65 74 20 5b 6c 72 61 6e 67 65 20 24 70 61 cset [lrange $pa
27d0: 74 68 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 20 th 1 end-1] \..
27e0: 20 20 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 20 next [lrange
27f0: 24 70 61 74 68 20 32 20 65 6e 64 5d 20 7b 0a 0a $path 2 end] {..
2800: 09 09 23 20 45 61 63 68 20 74 72 69 70 6c 65 20 ..# Each triple
2810: 50 52 45 56 20 2d 3e 20 43 53 45 54 20 2d 3e 20 PREV -> CSET ->
2820: 4e 45 58 54 20 6f 66 20 63 68 61 6e 67 65 73 65 NEXT of changese
2830: 74 73 2c 20 61 0a 09 09 23 20 27 6c 69 6e 6b 27 ts, a...# 'link'
2840: 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2c 20 69 in the cycle, i
2850: 73 20 61 6e 61 6c 79 73 65 64 20 61 6e 64 20 74 s analysed and t
2860: 68 65 20 62 65 73 74 0a 09 09 23 20 6c 6f 63 61 he best...# loca
2870: 74 69 6f 6e 20 77 68 65 72 65 20 74 6f 20 61 74 tion where to at
2880: 20 6c 65 61 73 74 20 77 65 61 6b 65 6e 20 74 68 least weaken th
2890: 65 20 63 79 63 6c 65 20 69 73 0a 09 09 23 20 63 e cycle is...# c
28a0: 68 6f 73 65 6e 20 66 6f 72 20 66 75 72 74 68 65 hosen for furthe
28b0: 72 20 70 72 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 r processing....
28c0: 09 73 65 74 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 .set link [proje
28d0: 63 74 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 55 54 ct::revlink %AUT
28e0: 4f 25 20 24 70 72 65 76 20 24 63 73 65 74 20 24 O% $prev $cset $
28f0: 6e 65 78 74 5d 0a 09 09 69 66 20 7b 24 62 65 73 next]...if {$bes
2900: 74 6c 69 6e 6b 20 65 71 20 22 22 7d 20 7b 0a 09 tlink eq ""} {..
2910: 09 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e . set bestlin
2920: 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 k $link... se
2930: 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 t bestnode $cset
2940: 0a 09 09 7d 20 65 6c 73 65 69 66 20 7b 5b 24 6c ...} elseif {[$l
2950: 69 6e 6b 20 62 65 74 74 65 72 74 68 61 6e 20 24 ink betterthan $
2960: 62 65 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 bestlink]} {...
2970: 20 20 20 24 62 65 73 74 6c 69 6e 6b 20 64 65 73 $bestlink des
2980: 74 72 6f 79 0a 09 09 20 20 20 20 73 65 74 20 62 troy... set b
2990: 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 estlink $link...
29a0: 20 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 set bestnode
29b0: 20 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 20 $cset...} else
29c0: 7b 0a 09 09 20 20 20 20 24 6c 69 6e 6b 20 64 65 {... $link de
29d0: 73 74 72 6f 79 0a 09 09 7d 0a 09 20 20 20 20 7d stroy...}.. }
29e0: 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 20 63 ...log write 5 c
29f0: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 42 72 65 yclebreaker "Bre
2a00: 61 6b 69 6e 67 20 24 6c 61 62 65 6c 20 62 79 20 aking $label by
2a10: 73 70 6c 69 74 74 69 6e 67 20 63 68 61 6e 67 65 splitting change
2a20: 73 65 74 20 5b 24 62 65 73 74 6e 6f 64 65 20 73 set [$bestnode s
2a30: 74 72 5d 22 0a 09 73 65 74 20 49 44 20 5b 24 62 tr]"..set ID [$b
2a40: 65 73 74 6e 6f 64 65 20 69 64 5d 0a 09 4d 61 72 estnode id]..Mar
2a50: 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d 62 65 66 k $dg -${ID}-bef
2a60: 6f 72 65 0a 0a 09 73 65 74 20 6e 65 77 63 73 65 ore...set newcse
2a70: 74 73 20 5b 24 62 65 73 74 6c 69 6e 6b 20 62 72 ts [$bestlink br
2a80: 65 61 6b 5d 0a 09 24 62 65 73 74 6c 69 6e 6b 20 eak]..$bestlink
2a90: 64 65 73 74 72 6f 79 0a 0a 20 20 20 20 20 20 20 destroy..
2aa0: 20 23 20 41 74 20 74 68 69 73 20 70 6f 69 6e 74 # At this point
2ab0: 20 74 68 65 20 6f 6c 64 20 63 68 61 6e 67 65 73 the old changes
2ac0: 65 74 20 28 42 45 53 54 4e 4f 44 45 29 20 69 73 et (BESTNODE) is
2ad0: 20 67 6f 6e 65 0a 20 20 20 20 20 20 20 20 23 20 gone. #
2ae0: 61 6c 72 65 61 64 79 2e 20 57 65 20 72 65 6d 6f already. We remo
2af0: 76 65 20 69 74 20 66 72 6f 6d 20 74 68 65 20 67 ve it from the g
2b00: 72 61 70 68 20 61 73 20 77 65 6c 6c 20 61 6e 64 raph as well and
2b10: 20 74 68 65 6e 20 65 6e 74 65 72 0a 20 20 20 20 then enter.
2b20: 20 20 20 20 23 20 74 68 65 20 66 72 61 67 6d 65 # the fragme
2b30: 6e 74 73 20 67 65 6e 65 72 61 74 65 64 20 66 6f nts generated fo
2b40: 72 20 69 74 2e 0a 0a 09 52 65 70 6c 61 63 65 20 r it....Replace
2b50: 24 64 67 20 24 62 65 73 74 6e 6f 64 65 20 24 6e $dg $bestnode $n
2b60: 65 77 63 73 65 74 73 0a 0a 09 4d 61 72 6b 20 24 ewcsets...Mark $
2b70: 64 67 20 2d 24 7b 49 44 7d 2d 61 66 74 65 72 0a dg -${ID}-after.
2b80: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
2b90: 20 20 20 23 20 54 4f 44 4f 3a 20 54 68 69 73 20 # TODO: This
2ba0: 73 68 6f 75 6c 64 20 62 65 20 61 20 67 72 61 70 should be a grap
2bb0: 68 20 6d 65 74 68 6f 64 2e 0a 20 20 20 20 70 72 h method.. pr
2bc0: 6f 63 20 48 61 73 41 72 63 20 7b 64 67 20 61 20 oc HasArc {dg a
2bd0: 62 7d 20 7b 0a 09 23 38 2e 35 3a 20 72 65 74 75 b} {..#8.5: retu
2be0: 72 6e 20 5b 65 78 70 72 20 7b 24 62 20 69 6e 20 rn [expr {$b in
2bf0: 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 [$dg nodes -out
2c00: 24 61 5d 7d 5d 0a 09 69 66 20 7b 5b 6c 73 65 61 $a]}]..if {[lsea
2c10: 72 63 68 20 2d 65 78 61 63 74 20 5b 24 64 67 20 rch -exact [$dg
2c20: 6e 6f 64 65 73 20 2d 6f 75 74 20 24 61 5d 20 24 nodes -out $a] $
2c30: 62 5d 20 3c 20 30 7d 20 7b 20 72 65 74 75 72 6e b] < 0} { return
2c40: 20 30 20 7d 0a 09 72 65 74 75 72 6e 20 31 0a 20 0 }..return 1.
2c50: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 4d }.. proc M
2c60: 61 72 6b 20 7b 64 67 20 7b 73 75 66 66 69 78 20 ark {dg {suffix
2c70: 7b 7d 7d 20 7b 73 75 62 67 72 61 70 68 20 7b 7d {}} {subgraph {}
2c80: 7d 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 }} {..::variable
2c90: 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f mydotdestinatio
2ca0: 6e 0a 09 69 66 20 7b 24 6d 79 64 6f 74 64 65 73 n..if {$mydotdes
2cb0: 74 69 6e 61 74 69 6f 6e 20 65 71 20 22 22 7d 20 tination eq ""}
2cc0: 72 65 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 62 return..::variab
2cd0: 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 0a 09 le mydotprefix..
2ce0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 ::variable mydot
2cf0: 69 64 0a 09 73 65 74 20 66 6e 61 6d 65 20 24 6d id..set fname $m
2d00: 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 2f ydotdestination/
2d10: 24 7b 6d 79 64 6f 74 70 72 65 66 69 78 7d 24 7b ${mydotprefix}${
2d20: 6d 79 64 6f 74 69 64 7d 24 7b 73 75 66 66 69 78 mydotid}${suffix
2d30: 7d 2e 64 6f 74 0a 09 66 69 6c 65 20 6d 6b 64 69 }.dot..file mkdi
2d40: 72 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 r [file dirname
2d50: 24 66 6e 61 6d 65 5d 0a 09 64 6f 74 20 77 72 69 $fname]..dot wri
2d60: 74 65 20 24 64 67 20 24 6d 79 64 6f 74 70 72 65 te $dg $mydotpre
2d70: 66 69 78 24 73 75 66 66 69 78 20 24 66 6e 61 6d fix$suffix $fnam
2d80: 65 20 24 73 75 62 67 72 61 70 68 0a 09 69 6e 63 e $subgraph..inc
2d90: 72 20 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f 67 20 r mydotid...log
2da0: 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 72 65 write 5 cyclebre
2db0: 61 6b 65 72 20 22 2e 64 6f 74 20 65 78 70 6f 72 aker ".dot expor
2dc0: 74 20 24 66 6e 61 6d 65 22 0a 09 72 65 74 75 72 t $fname"..retur
2dd0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
2de0: 63 20 52 65 70 6c 61 63 65 20 7b 64 67 20 6e 20 c Replace {dg n
2df0: 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b 0a replacements} {.
2e00: 09 23 20 4e 4f 54 45 2e 20 57 65 20 68 61 76 65 .# NOTE. We have
2e10: 20 74 6f 20 67 65 74 20 74 68 65 20 6c 69 73 74 to get the list
2e20: 20 6f 66 20 69 6e 63 6f 6d 69 6e 67 20 6e 65 69 of incoming nei
2e30: 67 68 62 6f 75 72 73 20 61 6e 64 0a 09 23 20 72 ghbours and..# r
2e40: 65 63 6f 6d 70 75 74 65 20 74 68 65 69 72 20 73 ecompute their s
2e50: 75 63 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 uccessors after
2e60: 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 20 68 61 the new nodes ha
2e70: 76 65 20 62 65 65 6e 0a 09 23 20 69 6e 73 65 72 ve been..# inser
2e80: 74 65 64 2e 20 54 68 65 69 72 20 6f 75 74 67 6f ted. Their outgo
2e90: 69 6e 67 20 61 72 63 73 20 77 69 6c 6c 20 6e 6f ing arcs will no
2ea0: 77 20 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 20 62 w go to one or b
2eb0: 6f 74 68 20 6f 66 0a 09 23 20 74 68 65 20 6e 65 oth of..# the ne
2ec0: 77 20 6e 6f 64 65 73 2c 20 61 6e 64 20 6e 6f 74 w nodes, and not
2ed0: 20 72 65 64 6f 69 6e 67 20 74 68 65 6d 20 6d 61 redoing them ma
2ee0: 79 20 63 61 75 73 65 20 75 73 20 74 6f 20 66 6f y cause us to fo
2ef0: 72 67 65 74 0a 09 23 20 63 69 72 63 6c 65 73 2c rget..# circles,
2f00: 20 6c 65 61 76 69 6e 67 20 74 68 65 6d 20 69 6e leaving them in
2f10: 2c 20 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 73 65 , unbroken....se
2f20: 74 20 70 72 65 20 5b 24 64 67 20 6e 6f 64 65 73 t pre [$dg nodes
2f30: 20 2d 69 6e 20 24 6e 5d 0a 0a 20 20 20 20 20 20 -in $n]..
2f40: 20 20 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 74 $dg node delet
2f50: 65 20 24 6e 0a 0a 09 66 6f 72 65 61 63 68 20 63 e $n...foreach c
2f60: 73 65 74 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 set $replacement
2f70: 73 20 7b 0a 09 20 20 20 20 73 65 74 20 74 72 20 s {.. set tr
2f80: 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 [$cset timerange
2f90: 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 ].. $dg node
2fa0: 69 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 insert $cset..
2fb0: 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 $dg node set
2fc0: 20 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 $cset timerang
2fd0: 65 20 24 74 72 0a 09 20 20 20 20 24 64 67 20 6e e $tr.. $dg n
2fe0: 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 ode set $cset
2ff0: 20 6c 61 62 65 6c 20 20 20 20 20 22 5b 24 63 73 label "[$cs
3000: 65 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e 20 et str]\\n[join
3010: 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d 61 [struct::list ma
3020: 70 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 66 p $tr {::clock f
3030: 6f 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 0a ormat}] "\\n"]".
3040: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
3050: 74 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f t $cset __id_
3060: 5f 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a _ [$cset id].
3070: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
3080: 74 20 20 20 20 24 63 73 65 74 20 73 68 61 70 65 t $cset shape
3090: 20 20 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 73 [expr {[$cs
30a0: 65 74 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 09 et bysymbol]....
30b0: 09 09 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 65 ... ? "ellipse
30c0: 22 0a 09 09 09 09 09 09 20 20 20 3a 20 22 62 6f "....... : "bo
30d0: 78 22 7d 5d 0a 09 7d 0a 0a 09 66 6f 72 65 61 63 x"}]..}...foreac
30e0: 68 20 63 73 65 74 20 24 72 65 70 6c 61 63 65 6d h cset $replacem
30f0: 65 6e 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 ents {.. fore
3100: 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 ach succ [$cset
3110: 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 successors] {...
3120: 23 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 65 # The new change
3130: 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 sets may have de
3140: 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 pendencies outsi
3150: 64 65 20 6f 66 0a 09 09 23 20 74 68 65 20 63 68 de of...# the ch
3160: 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 osen set. These
3170: 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 are ignored...if
3180: 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 {![$dg node exi
3190: 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 sts $succ]} cont
31a0: 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 inue...$dg arc i
31b0: 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 63 nsert $cset $suc
31c0: 63 0a 09 09 69 66 20 7b 24 73 75 63 63 20 65 71 c...if {$succ eq
31d0: 20 24 63 73 65 74 7d 20 7b 0a 09 09 20 20 20 20 $cset} {...
31e0: 24 63 73 65 74 20 6c 6f 6f 70 63 68 65 63 6b 0a $cset loopcheck.
31f0: 09 09 20 20 20 20 74 72 6f 75 62 6c 65 20 69 6e .. trouble in
3200: 74 65 72 6e 61 6c 20 22 5b 24 63 73 65 74 20 73 ternal "[$cset s
3210: 74 72 5d 20 64 65 70 65 6e 64 73 20 6f 6e 20 69 tr] depends on i
3220: 74 73 65 6c 66 22 0a 09 09 7d 0a 09 20 20 20 20 tself"...}..
3230: 7d 0a 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 }..}..foreach cs
3240: 65 74 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 et $pre {.. f
3250: 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 oreach succ [$cs
3260: 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b et successors] {
3270: 0a 09 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 ...# Note that t
3280: 68 65 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 he arc may alrea
3290: 64 79 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 dy exist in the
32a0: 67 72 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f graph. If...# so
32b0: 20 69 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 ignore it. The
32c0: 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d new changesets m
32d0: 61 79 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 ay have...# depe
32e0: 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 ndencies outside
32f0: 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 of the chosen s
3300: 65 74 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 et. These are...
3310: 23 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b # ignored...if {
3320: 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 ![$dg node exist
3330: 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e s $succ]} contin
3340: 75 65 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 ue...if {[HasArc
3350: 20 24 64 67 20 24 63 73 65 74 20 24 73 75 63 63 $dg $cset $succ
3360: 5d 7d 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f ]} continue;# TO
3370: 44 4f 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 DO should be gra
3380: 70 68 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 ph method....$dg
3390: 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 arc insert $cse
33a0: 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 t $succ.. }..
33b0: 7d 0a 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d }...return. }
33c0: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
33d0: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
33e0: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 #############.
33f0: 20 20 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 6e ## Callback in
3400: 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 20 vokation .....
3410: 20 20 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 7b proc PreHook {
3420: 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 65 graph} {..# Give
3430: 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 the user of the
3440: 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 cycle breaker t
3450: 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 he opportunity t
3460: 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 o work..# with t
3470: 68 65 20 67 72 61 70 68 20 62 65 74 77 65 65 6e he graph between
3480: 20 73 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 75 setup and consu
3490: 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 72 mmation....::var
34a0: 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a 09 iable myprecmd..
34b0: 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d if {![llength $m
34c0: 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e yprecmd]} return
34d0: 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c ...uplevel #0 [l
34e0: 69 6e 73 65 72 74 20 24 6d 79 70 72 65 63 6d 64 insert $myprecmd
34f0: 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d 61 end $graph]..Ma
3500: 72 6b 20 24 67 72 61 70 68 20 2d 70 72 65 2d 64 rk $graph -pre-d
3510: 6f 6e 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 one..return.
3520: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 6f 63 }.. proc Proc
3530: 65 73 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 73 essedHook {dg cs
3540: 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 76 et pos} {..# Giv
3550: 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 e the user of th
3560: 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 e cycle breaker
3570: 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 the opportunity
3580: 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 to work..# with
3590: 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 62 65 the changeset be
35a0: 66 6f 72 65 20 69 74 20 69 73 20 72 65 6d 6f 76 fore it is remov
35b0: 65 64 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 ed from the grap
35c0: 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 h....::variable
35d0: 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 20 7b 21 mysavecmd..if {!
35e0: 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 65 [llength $mysave
35f0: 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 75 cmd]} return...u
3600: 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 plevel #0 [linse
3610: 72 74 20 24 6d 79 73 61 76 65 63 6d 64 20 65 6e rt $mysavecmd en
3620: 64 20 24 64 67 20 24 70 6f 73 20 24 63 73 65 74 d $dg $pos $cset
3630: 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a ]..return. }.
3640: 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 . proc BreakC
3650: 79 63 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d ycleHook {graph}
3660: 20 7b 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 {..# Call out t
3670: 6f 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 o the chosen alg
3680: 6f 72 69 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 orithm for cycle
3690: 20 62 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 breaking. Findi
36a0: 6e 67 0a 09 23 20 61 20 63 79 63 6c 65 20 69 66 ng..# a cycle if
36b0: 20 6e 6f 20 62 72 65 61 6b 65 72 20 77 61 73 20 no breaker was
36c0: 63 68 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 72 chosen is an err
36d0: 6f 72 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 or....::variable
36e0: 20 6d 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 mybreakcmd..if
36f0: 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 {![llength $mybr
3700: 65 61 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 eakcmd]} {..
3710: 74 72 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 46 trouble fatal "F
3720: 6f 75 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 78 ound a cycle, ex
3730: 70 65 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 pecting none."..
3740: 20 20 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 exit 1..}...
3750: 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 uplevel #0 [lins
3760: 65 72 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 ert $mybreakcmd
3770: 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 72 65 74 end $graph]..ret
3780: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
3790: 72 6f 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b roc ClearHooks {
37a0: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
37b0: 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 3a myprecmd {}..:
37c0: 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 :variable mysave
37d0: 63 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 cmd {}..::varia
37e0: 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b ble mybreakcmd {
37f0: 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a }..return. }.
3800: 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 . # # ## ###
3810: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
3820: 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 ############..
3830: 20 20 70 72 6f 63 20 4d 61 72 6b 57 61 74 63 68 proc MarkWatch
3840: 20 7b 67 72 61 70 68 7d 20 7b 0a 09 3a 3a 76 61 {graph} {..::va
3850: 72 69 61 62 6c 65 20 6d 79 77 61 74 63 68 69 64 riable mywatchid
3860: 73 0a 09 73 65 74 20 77 61 74 63 68 65 64 20 5b s..set watched [
3870: 57 61 74 63 68 65 64 20 24 67 72 61 70 68 20 24 Watched $graph $
3880: 6d 79 77 61 74 63 68 69 64 73 5d 0a 09 69 66 20 mywatchids]..if
3890: 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 77 61 74 63 {![llength $watc
38a0: 68 65 64 5d 7d 20 72 65 74 75 72 6e 0a 09 73 65 hed]} return..se
38b0: 74 20 6e 65 69 67 68 62 6f 75 72 73 20 5b 65 76 t neighbours [ev
38c0: 61 6c 20 5b 6c 69 6e 73 65 72 74 20 24 77 61 74 al [linsert $wat
38d0: 63 68 65 64 20 30 20 24 67 72 61 70 68 20 6e 6f ched 0 $graph no
38e0: 64 65 73 20 2d 61 64 6a 5d 5d 0a 09 23 66 6f 72 des -adj]]..#for
38f0: 65 61 63 68 20 6e 20 24 6e 65 69 67 68 62 6f 75 each n $neighbou
3900: 72 73 20 7b 20 6c 6f 67 20 77 72 69 74 65 20 36 rs { log write 6
3910: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 4e cyclebreaker "N
3920: 65 69 67 68 62 6f 72 20 5b 24 6e 20 69 64 5d 20 eighbor [$n id]
3930: 3d 3e 20 24 6e 22 20 7d 0a 09 4d 61 72 6b 20 24 => $n" }..Mark $
3940: 67 72 61 70 68 20 77 61 74 63 68 65 64 20 5b 63 graph watched [c
3950: 6f 6e 63 61 74 20 24 77 61 74 63 68 65 64 20 24 oncat $watched $
3960: 6e 65 69 67 68 62 6f 75 72 73 5d 0a 09 72 65 74 neighbours]..ret
3970: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
3980: 72 6f 63 20 57 61 74 63 68 65 64 20 7b 67 72 61 roc Watched {gra
3990: 70 68 20 77 61 74 63 68 69 64 73 7d 20 7b 0a 09 ph watchids} {..
39a0: 73 65 74 20 72 65 73 20 7b 7d 0a 09 66 6f 72 65 set res {}..fore
39b0: 61 63 68 20 69 64 20 24 77 61 74 63 68 69 64 73 ach id $watchids
39c0: 20 7b 0a 09 20 20 20 20 73 65 74 20 6e 6c 20 5b {.. set nl [
39d0: 24 67 72 61 70 68 20 6e 6f 64 65 73 20 2d 6b 65 $graph nodes -ke
39e0: 79 20 5f 5f 69 64 5f 5f 20 2d 76 61 6c 75 65 20 y __id__ -value
39f0: 24 69 64 5d 0a 09 20 20 20 20 69 66 20 7b 21 5b $id].. if {![
3a00: 6c 6c 65 6e 67 74 68 20 24 6e 6c 5d 7d 20 63 6f llength $nl]} co
3a10: 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 ntinue.. lapp
3a20: 65 6e 64 20 72 65 73 20 24 6e 6c 0a 09 20 20 20 end res $nl..
3a30: 20 23 6c 6f 67 20 77 72 69 74 65 20 36 20 62 72 #log write 6 br
3a40: 65 61 6b 72 63 79 63 6c 65 20 22 57 61 74 63 68 eakrcycle "Watch
3a50: 69 6e 67 20 24 69 64 20 3d 3e 20 24 6e 6c 22 0a ing $id => $nl".
3a60: 09 20 20 20 20 24 67 72 61 70 68 20 6e 6f 64 65 . $graph node
3a70: 20 73 65 74 20 24 6e 6c 20 66 6f 6e 74 63 6f 6c set $nl fontcol
3a80: 6f 72 20 72 65 64 0a 09 7d 0a 09 72 65 74 75 72 or red..}..retur
3a90: 6e 20 24 72 65 73 0a 20 20 20 20 7d 0a 0a 20 20 n $res. }..
3aa0: 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 # # ## ### ###
3ab0: 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 ## ######## ####
3ac0: 23 23 23 23 23 23 23 23 23 0a 0a 0a 20 20 20 20 #########...
3ad0: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 61 typevariable mya
3ae0: 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 t 0 ; # Cou
3af0: 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 nter for commit
3b00: 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 20 ids for the....
3b10: 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 65 # changese
3b20: 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 ts.. typevari
3b30: 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b 7d able mybottom {}
3b40: 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 65 ; # List of the
3b50: 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 73 candidate nodes
3b60: 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 23 for.... #
3b70: 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 20 committing...
3b80: 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d typevariable m
3b90: 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 23 yprecmd {} ; #
3ba0: 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e 67 Callback, chang
3bb0: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 77 e graph before w
3bc0: 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 72 alk.. typevar
3bd0: 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 iable mysavecmd
3be0: 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b {} ; # Callback
3bf0: 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 , for each proce
3c00: 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 74 ssed node.. t
3c10: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 72 ypevariable mybr
3c20: 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 61 eakcmd {} ; # Ca
3c30: 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 68 llback, for each
3c40: 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 found cycle...
3c50: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3c60: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
3c70: 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 74 {} ; # Destinat
3c80: 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 6f ion directory fo
3c90: 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 20 r the.....
3ca0: 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 6f # generated .do
3cb0: 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 70 t files.. typ
3cc0: 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 evariable mydotp
3cd0: 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b 20 refix {} ;
3ce0: 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f 74 # Prefix for dot
3cf0: 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 09 files when.....
3d00: 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 69 # exporti
3d10: 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a 20 ng the graphs..
3d20: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3d30: 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 20 mydotid
3d40: 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 0 ; # Counter
3d50: 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 6d for dot file nam
3d60: 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 67 e..... # g
3d70: 65 6e 65 72 61 74 69 6f 6e 2e 0a 20 20 20 20 74 eneration.. t
3d80: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 77 61 ypevariable mywa
3d90: 74 63 68 69 64 73 20 20 20 20 20 20 20 7b 7d 20 tchids {}
3da0: 3b 20 23 20 43 68 61 6e 67 65 73 65 74 73 20 74 ; # Changesets t
3db0: 6f 20 77 61 74 63 68 20 74 68 65 0a 09 09 09 09 o watch the.....
3dc0: 20 20 20 20 20 20 20 23 20 6e 65 69 67 68 62 6f # neighbo
3dd0: 75 72 68 6f 6f 64 20 6f 66 2e 0a 0a 20 20 20 20 urhood of...
3de0: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
3df0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
3e00: 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 #######. ## C
3e10: 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 onfiguration..
3e20: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 pragma -hasins
3e30: 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 tances no ; #
3e40: 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 singleton. pr
3e50: 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 agma -hastypeinf
3e60: 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 o no ; # no i
3e70: 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 ntrospection.
3e80: 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 pragma -hastype
3e90: 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 destroy no ; # i
3ea0: 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 mmortal.. # #
3eb0: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
3ec0: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
3ed0: 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 ####.}..namespac
3ee0: 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 e eval ::vc::fos
3ef0: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
3f00: 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 {. namespace
3f10: 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 export cyclebre
3f20: 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 aker. namespa
3f30: 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 ce eval cyclebre
3f40: 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 aker {..namespac
3f50: 65 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b e eval project {
3f60: 0a 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 .. namespace
3f70: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 import ::vc::fos
3f80: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
3f90: 3a 3a 69 6e 74 65 67 72 69 74 79 0a 09 20 20 20 ::integrity..
3fa0: 20 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 namespace impor
3fb0: 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a t ::vc::fossil::
3fc0: 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f import::cvs::pro
3fd0: 6a 65 63 74 3a 3a 72 65 76 0a 09 20 20 20 20 6e ject::rev.. n
3fe0: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
3ff0: 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d ::vc::fossil::im
4000: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 port::cvs::proje
4010: 63 74 3a 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 ct::revlink..}..
4020: 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 namespace import
4030: 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 ::vc::tools::mi
4040: 73 63 3a 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 65 sc::*..namespace
4050: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f import ::vc::to
4060: 6f 6c 73 3a 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 ols::log..namesp
4070: 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a ace import ::vc:
4080: 3a 74 6f 6f 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a :tools::trouble.
4090: 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 .namespace impor
40a0: 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 t ::vc::tools::d
40b0: 6f 74 0a 09 6c 6f 67 20 72 65 67 69 73 74 65 72 ot..log register
40c0: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 cyclebreaker.
40d0: 20 20 7d 0a 7d 0a 0a 23 20 23 20 23 23 20 23 23 }.}..# # ## ##
40e0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
40f0: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 20 23 ############# #
4100: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
4110: 23 23 23 23 0a 23 23 20 52 65 61 64 79 0a 0a 70 ####.## Ready..p
4120: 61 63 6b 61 67 65 20 70 72 6f 76 69 64 65 20 76 ackage provide v
4130: 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 c::fossil::impor
4140: 74 3a 3a 63 76 73 3a 3a 63 79 63 6c 65 62 72 65 t::cvs::cyclebre
4150: 61 6b 65 72 20 31 2e 30 0a 72 65 74 75 72 6e 0a aker 1.0.return.