Artifact 41093323e5c42f3af7c63b40a3b364d74d5288ae:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[38b967dcf5]
- Merge aku's CVS import changes into the main line. Fix a small bug in diff.c.
by
drh on
2007-11-17 00:29:42.
Also file
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[7b3928681e]
- Bugfix. Destroy graph object after use.
by
aku on
2007-11-16 06:51:25.
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 6c 6f 67 20 20 20 20 ::tools::log
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 0a 70 61 63 6b 61 feedback..packa
0460: 67 65 20 72 65 71 75 69 72 65 20 76 63 3a 3a 74 ge require vc::t
0470: 6f 6f 6c 73 3a 3a 6d 69 73 63 20 20 20 20 20 20 ools::misc
0480: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0490: 20 20 20 20 20 3b 20 23 20 54 65 78 74 20 66 6f ; # Text fo
04a0: 72 6d 61 74 74 69 6e 67 2e 0a 70 61 63 6b 61 67 rmatting..packag
04b0: 65 20 72 65 71 75 69 72 65 20 76 63 3a 3a 66 6f e require vc::fo
04c0: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
04d0: 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 20 s::project::rev
04e0: 20 20 20 20 3b 20 23 20 50 72 6f 6a 65 63 74 20 ; # Project
04f0: 6c 65 76 65 6c 20 63 68 61 6e 67 65 73 65 74 73 level changesets
0500: 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 65 .package require
0510: 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 vc::fossil::imp
0520: 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 ort::cvs::projec
0530: 74 3a 3a 72 65 76 6c 69 6e 6b 20 3b 20 23 20 43 t::revlink ; # C
0540: 79 63 6c 65 20 6c 69 6e 6b 73 2e 0a 0a 23 20 23 ycle links...# #
0550: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
0560: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
0570: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
0580: 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 0a 0a ##########.## ..
0590: 73 6e 69 74 3a 3a 74 79 70 65 20 3a 3a 76 63 3a snit::type ::vc:
05a0: 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a :fossil::import:
05b0: 3a 63 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b :cvs::cyclebreak
05c0: 65 72 20 7b 0a 20 20 20 20 23 20 23 20 23 23 20 er {. # # ##
05d0: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
05e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
05f0: 0a 20 20 20 20 23 23 20 50 75 62 6c 69 63 20 41 . ## Public A
0600: 50 49 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 PI.. typemeth
0610: 6f 64 20 72 75 6e 20 7b 63 68 61 6e 67 65 73 65 od run {changese
0620: 74 73 20 7b 73 61 76 65 63 6d 64 20 7b 7d 7d 7d ts {savecmd {}}}
0630: 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 73 {..::variable s
0640: 61 76 65 20 24 73 61 76 65 63 6d 64 0a 09 3a 3a ave $savecmd..::
0650: 76 61 72 69 61 62 6c 65 20 61 74 20 20 20 30 0a variable at 0.
0660: 0a 09 23 20 57 65 20 63 72 65 61 74 65 20 61 20 ..# We create a
0670: 67 72 61 70 68 20 6f 66 20 74 68 65 20 72 65 76 graph of the rev
0680: 69 73 69 6f 6e 20 63 68 61 6e 67 65 73 65 74 73 ision changesets
0690: 2c 20 75 73 69 6e 67 20 74 68 65 20 66 69 6c 65 , using the file
06a0: 0a 09 23 20 6c 65 76 65 6c 20 64 65 70 65 6e 64 ..# level depend
06b0: 65 6e 63 69 65 73 20 74 6f 20 63 6f 6e 73 74 72 encies to constr
06c0: 75 63 74 20 61 20 66 69 72 73 74 20 61 70 70 72 uct a first appr
06d0: 6f 78 69 6d 61 74 69 6f 6e 20 6f 66 20 74 68 65 oximation of the
06e0: 0a 09 23 20 64 65 70 65 6e 64 65 6e 63 69 65 73 ..# dependencies
06f0: 20 61 74 20 74 68 65 20 70 72 6f 6a 65 63 74 20 at the project
0700: 6c 65 76 65 6c 2e 20 54 68 65 6e 20 77 65 20 6c level. Then we l
0710: 6f 6f 6b 20 66 6f 72 20 63 79 63 6c 65 73 0a 09 ook for cycles..
0720: 23 20 69 6e 20 74 68 61 74 20 67 72 61 70 68 20 # in that graph
0730: 61 6e 64 20 62 72 65 61 6b 20 74 68 65 6d 2e 0a and break them..
0740: 0a 09 23 20 31 2e 20 43 72 65 61 74 65 20 6e 6f ..# 1. Create no
0750: 64 65 73 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 des for all rele
0760: 76 61 6e 74 20 63 68 61 6e 67 65 73 65 74 73 20 vant changesets
0770: 61 6e 64 20 61 20 6d 61 70 70 69 6e 67 0a 09 23 and a mapping..#
0780: 20 20 20 20 66 72 6f 6d 20 74 68 65 20 72 65 76 from the rev
0790: 69 73 69 6f 6e 73 20 74 6f 20 74 68 65 69 72 20 isions to their
07a0: 63 68 61 6e 67 65 73 65 74 73 2f 6e 6f 64 65 73 changesets/nodes
07b0: 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 33 20 ....log write 3
07c0: 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 43 72 cyclebreaker "Cr
07d0: 65 61 74 69 6e 67 20 63 68 61 6e 67 65 73 65 74 eating changeset
07e0: 20 67 72 61 70 68 2c 20 66 69 6c 6c 69 6e 67 20 graph, filling
07f0: 77 69 74 68 20 6e 6f 64 65 73 22 0a 09 6c 6f 67 with nodes"..log
0800: 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 write 3 cyclebr
0810: 65 61 6b 65 72 20 22 41 64 64 69 6e 67 20 5b 6e eaker "Adding [n
0820: 73 70 20 5b 6c 6c 65 6e 67 74 68 20 24 63 68 61 sp [llength $cha
0830: 6e 67 65 73 65 74 73 5d 20 6e 6f 64 65 5d 22 0a ngesets] node]".
0840: 0a 09 73 65 74 20 64 67 20 5b 73 74 72 75 63 74 ..set dg [struct
0850: 3a 3a 67 72 61 70 68 20 64 67 5d 0a 0a 09 66 6f ::graph dg]...fo
0860: 72 65 61 63 68 20 63 73 65 74 20 24 63 68 61 6e reach cset $chan
0870: 67 65 73 65 74 73 20 7b 0a 09 20 20 20 20 64 67 gesets {.. dg
0880: 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 node insert $cs
0890: 65 74 0a 09 20 20 20 20 64 67 20 6e 6f 64 65 20 et.. dg node
08a0: 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 6d set $cset tim
08b0: 65 72 61 6e 67 65 20 5b 24 63 73 65 74 20 74 69 erange [$cset ti
08c0: 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a 09 23 20 merange]..}...#
08d0: 32 2e 20 46 69 6e 64 20 66 6f 72 20 61 6c 6c 20 2. Find for all
08e0: 72 65 6c 65 76 61 6e 74 20 63 68 61 6e 67 65 73 relevant changes
08f0: 65 74 20 74 68 65 69 72 20 72 65 76 69 73 69 6f et their revisio
0900: 6e 73 20 61 6e 64 20 74 68 65 69 72 0a 09 23 20 ns and their..#
0910: 20 20 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e dependencies.
0920: 20 4d 61 70 20 74 68 65 20 6c 61 74 74 65 72 20 Map the latter
0930: 62 61 63 6b 20 74 6f 20 63 68 61 6e 67 65 73 65 back to changese
0940: 74 73 20 61 6e 64 0a 09 23 20 20 20 20 63 6f 6e ts and..# con
0950: 73 74 72 75 63 74 20 74 68 65 20 63 6f 72 72 65 struct the corre
0960: 73 70 6f 6e 64 69 6e 67 20 61 72 63 73 2e 0a 0a sponding arcs...
0970: 09 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 .log write 3 cyc
0980: 6c 65 62 72 65 61 6b 65 72 20 7b 53 65 74 74 69 lebreaker {Setti
0990: 6e 67 20 75 70 20 6e 6f 64 65 20 64 65 70 65 6e ng up node depen
09a0: 64 65 6e 63 69 65 73 7d 0a 0a 09 66 6f 72 65 61 dencies}...forea
09b0: 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 73 ch cset $changes
09c0: 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 ets {.. forea
09d0: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 ch succ [$cset s
09e0: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 uccessors] {...#
09f0: 20 43 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 Changesets may
0a00: 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 have dependencie
0a10: 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 s outside of the
0a20: 0a 09 09 23 20 63 68 6f 73 65 6e 20 73 65 74 2e ...# chosen set.
0a30: 20 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 These are ignor
0a40: 65 64 0a 09 09 69 66 20 7b 21 5b 64 67 20 6e 6f ed...if {![dg no
0a50: 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d de exists $succ]
0a60: 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 64 67 20 } continue...dg
0a70: 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 arc insert $cset
0a80: 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d $succ.. }..}
0a90: 0a 0a 09 23 20 33 2e 20 4c 61 73 74 6c 79 20 77 ...# 3. Lastly w
0aa0: 65 20 69 74 65 72 61 74 65 20 74 68 65 20 67 72 e iterate the gr
0ab0: 61 70 68 20 74 6f 70 6f 6c 6f 67 69 63 61 6c 6c aph topologicall
0ac0: 79 2e 20 57 65 20 6d 61 72 6b 20 6f 66 66 0a 09 y. We mark off..
0ad0: 23 20 20 20 20 74 68 65 20 6e 6f 64 65 73 20 77 # the nodes w
0ae0: 68 69 63 68 20 68 61 76 65 20 6e 6f 20 70 72 65 hich have no pre
0af0: 64 65 63 65 73 73 6f 72 73 2c 20 69 6e 20 6f 72 decessors, in or
0b00: 64 65 72 20 66 72 6f 6d 0a 09 23 20 20 20 20 6f der from..# o
0b10: 6c 64 65 73 74 20 74 6f 20 79 6f 75 6e 67 65 73 ldest to younges
0b20: 74 2c 20 73 61 76 69 6e 67 20 61 6e 64 20 72 65 t, saving and re
0b30: 6d 6f 76 69 6e 67 20 64 65 70 65 6e 64 65 6e 63 moving dependenc
0b40: 69 65 73 2e 20 49 66 0a 09 23 20 20 20 20 77 65 ies. If..# we
0b50: 20 66 69 6e 64 20 6e 6f 20 6e 6f 64 65 73 20 77 find no nodes w
0b60: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
0b70: 6f 72 73 20 77 65 20 68 61 76 65 20 61 20 63 79 ors we have a cy
0b80: 63 6c 65 2c 0a 09 23 20 20 20 20 61 6e 64 20 77 cle,..# and w
0b90: 6f 72 6b 20 6f 6e 20 62 72 65 61 6b 69 6e 67 20 ork on breaking
0ba0: 69 74 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 it....log write
0bb0: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 3 cyclebreaker {
0bc0: 4e 6f 77 20 73 6f 72 74 69 6e 67 20 74 68 65 20 Now sorting the
0bd0: 63 68 61 6e 67 65 73 65 74 73 2c 20 62 72 65 61 changesets, brea
0be0: 6b 69 6e 67 20 63 79 63 6c 65 73 7d 0a 0a 09 49 king cycles}...I
0bf0: 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 nitializeCandida
0c00: 74 65 73 20 24 64 67 0a 09 77 68 69 6c 65 20 7b tes $dg..while {
0c10: 31 7d 20 7b 0a 09 20 20 20 20 77 68 69 6c 65 20 1} {.. while
0c20: 7b 5b 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 {[WithoutPredece
0c30: 73 73 6f 72 20 24 64 67 20 6e 5d 7d 20 7b 0a 09 ssor $dg n]} {..
0c40: 09 53 61 76 65 41 6e 64 52 65 6d 6f 76 65 20 24 .SaveAndRemove $
0c50: 64 67 20 24 6e 0a 09 20 20 20 20 7d 0a 09 20 20 dg $n.. }..
0c60: 20 20 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 if {![llength
0c70: 5b 64 67 20 6e 6f 64 65 73 5d 5d 7d 20 62 72 65 [dg nodes]]} bre
0c80: 61 6b 0a 09 20 20 20 20 42 72 65 61 6b 43 79 63 ak.. BreakCyc
0c90: 6c 65 20 24 64 67 20 5b 46 69 6e 64 43 79 63 6c le $dg [FindCycl
0ca0: 65 20 24 64 67 5d 0a 09 20 20 20 20 49 6e 69 74 e $dg].. Init
0cb0: 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 ializeCandidates
0cc0: 20 24 64 67 0a 09 7d 0a 0a 09 64 67 20 64 65 73 $dg..}...dg des
0cd0: 74 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 74 65 troy...log write
0ce0: 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 3 cyclebreaker
0cf0: 44 6f 6e 65 2e 0a 09 72 65 74 75 72 6e 0a 20 20 Done...return.
0d00: 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 }.. # # ##
0d10: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
0d20: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
0d30: 0a 20 20 20 20 23 23 20 49 6e 74 65 72 6e 61 6c . ## Internal
0d40: 20 6d 65 74 68 6f 64 73 0a 0a 20 20 20 20 23 20 methods.. #
0d50: 49 6e 73 74 65 61 64 20 6f 66 20 73 65 61 72 63 Instead of searc
0d60: 68 69 6e 67 20 74 68 65 20 77 68 6f 6c 65 20 67 hing the whole g
0d70: 72 61 70 68 20 66 6f 72 20 74 68 65 20 64 65 67 raph for the deg
0d80: 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 6e 0a 20 ree-0 nodes in.
0d90: 20 20 20 23 20 65 61 63 68 20 69 74 65 72 61 74 # each iterat
0da0: 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 65 20 74 ion we compute t
0db0: 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 74 6f 20 he list once to
0dc0: 73 74 61 72 74 2c 20 61 6e 64 20 74 68 65 6e 20 start, and then
0dd0: 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 64 61 74 only. # updat
0de0: 65 20 69 74 20 69 6e 63 72 65 6d 65 6e 74 61 6c e it incremental
0df0: 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 ly based on the
0e00: 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f outgoing neighbo
0e10: 75 72 73 20 6f 66 20 74 68 65 0a 20 20 20 20 23 urs of the. #
0e20: 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 66 6f 72 node chosen for
0e30: 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 20 70 72 commit... pr
0e40: 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e oc InitializeCan
0e50: 64 69 64 61 74 65 73 20 7b 64 67 7d 20 7b 0a 09 didates {dg} {..
0e60: 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 73 74 20 # bottom = list
0e70: 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 72 61 6e (list (node, ran
0e80: 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 20 6d 61 ge min, range ma
0e90: 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 x))..::variable
0ea0: 62 6f 74 74 6f 6d 0a 09 66 6f 72 65 61 63 68 20 bottom..foreach
0eb0: 6e 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 7b 0a n [$dg nodes] {.
0ec0: 09 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f . if {[$dg no
0ed0: 64 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 6e de degree -in $n
0ee0: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 ]} continue..
0ef0: 20 6c 61 70 70 65 6e 64 20 62 6f 74 74 6f 6d 20 lappend bottom
0f00: 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f [linsert [$dg no
0f10: 64 65 20 67 65 74 20 24 6e 20 74 69 6d 65 72 61 de get $n timera
0f20: 6e 67 65 5d 20 30 20 24 6e 5d 0a 09 7d 0a 09 73 nge] 0 $n]..}..s
0f30: 65 74 20 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 et bottom [lsort
0f40: 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 -index 1 -integ
0f50: 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 er [lsort -index
0f60: 20 32 20 2d 69 6e 74 65 67 65 72 20 24 62 6f 74 2 -integer $bot
0f70: 74 6f 6d 5d 5d 0a 09 72 65 74 75 72 6e 0a 20 20 tom]]..return.
0f80: 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 }.. proc Wi
0f90: 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 thoutPredecessor
0fa0: 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 {dg nv} {..::va
0fb0: 72 69 61 62 6c 65 20 62 6f 74 74 6f 6d 0a 0a 09 riable bottom...
0fc0: 75 70 76 61 72 20 31 20 24 6e 76 20 6e 0a 09 69 upvar 1 $nv n..i
0fd0: 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 62 6f f {![llength $bo
0fe0: 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 72 6e 20 ttom]} { return
0ff0: 30 20 7d 0a 0a 09 73 65 74 20 6e 20 5b 6c 69 6e 0 }...set n [lin
1000: 64 65 78 20 5b 6c 69 6e 64 65 78 20 24 62 6f 74 dex [lindex $bot
1010: 74 6f 6d 20 30 5d 20 30 5d 0a 09 73 65 74 20 62 tom 0] 0]..set b
1020: 6f 74 74 6f 6d 20 5b 6c 72 61 6e 67 65 20 24 62 ottom [lrange $b
1030: 6f 74 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 65 ottom 1 end]..se
1040: 74 20 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 20 t changed 0...#
1050: 55 70 64 61 74 65 20 6c 69 73 74 20 6f 66 20 6e Update list of n
1060: 6f 64 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 odes without pre
1070: 64 65 63 65 73 73 6f 72 2c 20 62 61 73 65 64 20 decessor, based
1080: 6f 6e 20 74 68 65 0a 09 23 20 6f 75 74 67 6f 69 on the..# outgoi
1090: 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 ng neighbours of
10a0: 20 74 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 65 the chosen node
10b0: 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 . This should be
10c0: 0a 09 23 20 66 61 73 74 65 72 20 74 68 61 6e 20 ..# faster than
10d0: 69 74 65 72 61 74 69 6e 67 20 6f 66 20 74 68 65 iterating of the
10e0: 20 77 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e 6f whole set of no
10f0: 64 65 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c 6c des, finding all
1100: 0a 09 23 20 77 69 74 68 6f 75 74 20 70 72 65 64 ..# without pred
1110: 65 63 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 6e ecessors, sortin
1120: 67 20 74 68 65 6d 20 62 79 20 74 69 6d 65 2c 20 g them by time,
1130: 65 74 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 63 etc. pp...foreac
1140: 68 20 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 73 h out [$dg nodes
1150: 20 2d 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 20 -out $n] {..
1160: 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 if {[$dg node d
1170: 65 67 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d 20 egree -in $out]
1180: 3e 20 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 > 1} continue..
1190: 20 20 20 23 20 44 65 67 72 65 65 2d 31 20 6e 65 # Degree-1 ne
11a0: 69 67 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 61 ighbour, will ha
11b0: 76 65 20 6e 6f 20 70 72 65 64 65 63 65 73 73 6f ve no predecesso
11c0: 72 73 20 61 66 74 65 72 20 74 68 65 0a 09 20 20 rs after the..
11d0: 20 20 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 6e # removal of n
11e0: 2e 20 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 73 . Put on the lis
11f0: 74 2e 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 t... lappend
1200: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
1210: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6f [$dg node get $o
1220: 75 74 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 ut timerange] 0
1230: 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 74 20 63 $out].. set c
1240: 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 hanged 1..}..if
1250: 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 {$changed} {..
1260: 20 20 73 65 74 20 62 6f 74 74 6f 6d 20 5b 6c 73 set bottom [ls
1270: 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e ort -index 1 -in
1280: 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e teger [lsort -in
1290: 64 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 dex 2 -integer $
12a0: 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 20 bottom]]..}...#
12b0: 57 65 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 We do not delete
12c0: 20 74 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 69 the node immedi
12d0: 61 74 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 ately, to allow
12e0: 74 68 65 20 53 61 76 65 0a 09 23 20 70 72 6f 63 the Save..# proc
12f0: 65 64 75 72 65 20 74 6f 20 73 61 76 65 20 74 68 edure to save th
1300: 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 e dependencies a
1310: 73 20 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 20 s well (encoded
1320: 69 6e 20 74 68 65 0a 09 23 20 61 72 63 73 29 2e in the..# arcs).
1330: 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 20 20 7d ..return 1. }
1340: 0a 0a 20 20 20 20 70 72 6f 63 20 53 61 76 65 41 .. proc SaveA
1350: 6e 64 52 65 6d 6f 76 65 20 7b 64 67 20 6e 7d 20 ndRemove {dg n}
1360: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 61 74 {..::variable at
1370: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 73 61 76 ..::variable sav
1380: 65 0a 0a 09 23 20 47 69 76 65 20 74 68 65 20 75 e...# Give the u
1390: 73 65 72 20 6f 66 20 74 68 65 20 63 79 63 6c 65 ser of the cycle
13a0: 20 62 72 65 61 6b 65 72 20 74 68 65 20 6f 70 70 breaker the opp
13b0: 6f 72 74 75 6e 69 74 79 20 74 6f 20 77 6f 72 6b ortunity to work
13c0: 0a 09 23 20 77 69 74 68 20 74 68 65 20 63 68 61 ..# with the cha
13d0: 6e 67 65 73 65 74 20 62 65 66 6f 72 65 20 69 74 ngeset before it
13e0: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d is removed from
13f0: 20 74 68 65 20 67 72 61 70 68 2e 0a 0a 09 69 66 the graph....if
1400: 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 73 61 76 65 {[llength $save
1410: 5d 7d 20 7b 0a 09 20 20 20 20 75 70 6c 65 76 65 ]} {.. upleve
1420: 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 73 l #0 [linsert $s
1430: 61 76 65 20 65 6e 64 20 24 61 74 20 24 6e 5d 0a ave end $at $n].
1440: 09 7d 0a 0a 09 69 6e 63 72 20 61 74 0a 09 24 64 .}...incr at..$d
1450: 67 20 6e 6f 64 65 20 64 65 6c 65 74 65 20 24 6e g node delete $n
1460: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
1470: 20 20 20 20 70 72 6f 63 20 46 69 6e 64 43 79 63 proc FindCyc
1480: 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 68 69 le {dg} {..# Thi
1490: 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 20 72 s procedure is r
14a0: 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 20 74 un if and only t
14b0: 68 65 20 67 72 61 70 68 20 69 73 20 6e 6f 74 20 he graph is not
14c0: 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 6c 6c empty and..# all
14d0: 20 6e 6f 64 65 73 20 68 61 76 65 20 70 72 65 64 nodes have pred
14e0: 65 63 65 73 73 6f 72 73 2e 20 54 68 69 73 20 6d ecessors. This m
14f0: 65 61 6e 73 20 74 68 61 74 20 65 61 63 68 20 6e eans that each n
1500: 6f 64 65 20 69 73 0a 09 23 20 65 69 74 68 65 72 ode is..# either
1510: 20 70 61 72 74 20 6f 66 20 61 20 63 79 63 6c 65 part of a cycle
1520: 20 6f 72 20 28 69 6e 64 69 72 65 63 74 6c 79 29 or (indirectly)
1530: 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 61 20 depending on a
1540: 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 79 63 node..# in a cyc
1550: 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 61 72 74 le. We can start
1560: 20 61 74 20 61 6e 20 61 72 62 69 74 72 61 72 79 at an arbitrary
1570: 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 69 74 node, follow it
1580: 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 65 64 s..# incoming ed
1590: 67 65 73 20 74 6f 20 69 74 73 20 70 72 65 64 65 ges to its prede
15a0: 63 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 77 65 cessors until we
15b0: 20 73 65 65 20 61 20 6e 6f 64 65 20 61 0a 09 23 see a node a..#
15c0: 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 54 68 second time. Th
15d0: 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 20 74 at node closes t
15e0: 68 65 20 63 79 63 6c 65 20 61 6e 64 20 74 68 65 he cycle and the
15f0: 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a 09 23 beginning is..#
1600: 20 69 74 73 20 66 69 72 73 74 20 6f 63 63 75 72 its first occur
1610: 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 74 20 ence. Note that
1620: 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 61 6e we can choose an
1630: 20 61 72 62 69 74 72 61 72 79 0a 09 23 20 70 72 arbitrary..# pr
1640: 65 64 65 63 65 73 73 6f 72 20 6f 66 20 65 61 63 edecessor of eac
1650: 68 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c 2c 20 h node as well,
1660: 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 74 we do not have t
1670: 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 57 65 o search....# We
1680: 20 72 65 63 6f 72 64 20 66 6f 72 20 65 61 63 68 record for each
1690: 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 78 20 node the index
16a0: 6f 66 20 74 68 65 20 66 69 72 73 74 20 61 70 70 of the first app
16b0: 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 74 68 earance in..# th
16c0: 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 20 69 e path, making i
16d0: 74 20 65 61 73 79 20 61 74 20 74 68 65 20 65 6e t easy at the en
16e0: 64 20 74 6f 20 63 75 74 20 74 68 65 20 63 79 63 d to cut the cyc
16f0: 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e 0a 0a le from..# it...
1700: 09 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 .# Choose arbitr
1710: 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 61 72 ary node to star
1720: 74 20 6f 75 72 20 73 65 61 72 63 68 20 61 74 2e t our search at.
1730: 0a 09 73 65 74 20 73 74 61 72 74 20 5b 6c 69 6e ..set start [lin
1740: 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 dex [$dg nodes]
1750: 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c 69 7a 0]...# Initializ
1760: 65 20 73 74 61 74 65 2c 20 70 61 74 68 20 6f 66 e state, path of
1770: 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 6e 64 seen nodes, and
1780: 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 65 74 when seen...set
1790: 20 20 20 20 20 20 20 70 61 74 68 20 7b 7d 0a 09 path {}..
17a0: 61 72 72 61 79 20 73 65 74 20 73 65 65 6e 20 7b array set seen {
17b0: 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a }...while {1} {.
17c0: 09 20 20 20 20 23 20 53 74 6f 70 20 73 65 61 72 . # Stop sear
17d0: 63 68 69 6e 67 20 77 68 65 6e 20 77 65 20 68 61 ching when we ha
17e0: 76 65 20 73 65 65 6e 20 74 68 65 20 63 75 72 72 ve seen the curr
17f0: 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 23 20 ent node.. #
1800: 61 6c 72 65 61 64 79 2c 20 74 68 65 20 63 69 72 already, the cir
1810: 63 6c 65 20 68 61 73 20 62 65 65 6e 20 63 6c 6f cle has been clo
1820: 73 65 64 2e 0a 09 20 20 20 20 69 66 20 7b 5b 69 sed... if {[i
1830: 6e 66 6f 20 65 78 69 73 74 73 20 73 65 65 6e 28 nfo exists seen(
1840: 24 73 74 61 72 74 29 5d 7d 20 62 72 65 61 6b 0a $start)]} break.
1850: 09 20 20 20 20 6c 61 70 70 65 6e 64 20 70 61 74 . lappend pat
1860: 68 20 24 73 74 61 72 74 0a 09 20 20 20 20 73 65 h $start.. se
1870: 74 20 73 65 65 6e 28 24 73 74 61 72 74 29 20 5b t seen($start) [
1880: 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 expr {[llength $
1890: 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 20 23 path]-1}].. #
18a0: 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 72 Choose arbitrar
18b0: 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 20 y predecessor..
18c0: 20 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c 69 set start [li
18d0: 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 20 ndex [$dg nodes
18e0: 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a 09 -in $start] 0]..
18f0: 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 75 }...return [stru
1900: 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 65 ct::list reverse
1910: 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 24 [lrange $path $
1920: 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e 64 seen($start) end
1930: 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 ]]. }.. pr
1940: 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 7b 20 72 oc ID {cset} { r
1950: 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 74 20 69 eturn "<[$cset i
1960: 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 72 6f 63 d]>" }.. proc
1970: 20 42 72 65 61 6b 43 79 63 6c 65 20 7b 64 67 20 BreakCycle {dg
1980: 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 68 65 20 cycle} {..# The
1990: 63 79 63 6c 65 20 77 65 20 68 61 76 65 20 67 6f cycle we have go
19a0: 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 6e 20 62 tten is broken b
19b0: 79 20 62 72 65 61 6b 69 6e 67 20 61 70 61 72 74 y breaking apart
19c0: 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f 72 65 20 one or..# more
19d0: 6f 66 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 of the changeset
19e0: 73 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2e 20 s in the cycle.
19f0: 54 68 69 73 20 63 61 75 73 65 73 20 75 73 20 74 This causes us t
1a00: 6f 0a 09 23 20 63 72 65 61 74 65 20 6f 6e 65 20 o..# create one
1a10: 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 65 73 65 or more changese
1a20: 74 73 20 77 68 69 63 68 20 61 72 65 20 74 6f 20 ts which are to
1a30: 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c 0a 09 23 be committed,..#
1a40: 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 67 72 added to the gr
1a50: 61 70 68 2c 20 65 74 63 2e 20 70 70 2e 0a 0a 09 aph, etc. pp....
1a60: 73 65 74 20 63 70 72 69 6e 74 20 5b 6a 6f 69 6e set cprint [join
1a70: 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d [struct::list m
1a80: 61 70 20 24 63 79 63 6c 65 20 5b 6d 79 70 72 6f ap $cycle [mypro
1a90: 63 20 49 44 5d 5d 20 7b 20 7d 5d 0a 0a 09 6c 61 c ID]] { }]...la
1aa0: 70 70 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 6e ppend cycle [lin
1ab0: 64 65 78 20 24 63 79 63 6c 65 20 30 5d 20 5b 6c dex $cycle 0] [l
1ac0: 69 6e 64 65 78 20 24 63 79 63 6c 65 20 31 5d 0a index $cycle 1].
1ad0: 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 7b 7d .set bestlink {}
1ae0: 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 65 20 7b ..set bestnode {
1af0: 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c 0a 09 20 }...foreach \..
1b00: 20 20 20 70 72 65 76 20 5b 6c 72 61 6e 67 65 20 prev [lrange
1b10: 24 63 79 63 6c 65 20 30 20 65 6e 64 2d 32 5d 20 $cycle 0 end-2]
1b20: 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 6c 72 61 \.. cset [lra
1b30: 6e 67 65 20 24 63 79 63 6c 65 20 31 20 65 6e 64 nge $cycle 1 end
1b40: 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 78 74 20 -1] \.. next
1b50: 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 32 [lrange $cycle 2
1b60: 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 45 61 63 end] {....# Eac
1b70: 68 20 74 72 69 70 6c 65 20 50 52 45 56 20 2d 3e h triple PREV ->
1b80: 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 20 6f 66 CSET -> NEXT of
1b90: 20 63 68 61 6e 67 65 73 65 74 73 2c 20 61 0a 09 changesets, a..
1ba0: 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 74 68 65 .# 'link' in the
1bb0: 20 63 79 63 6c 65 2c 20 69 73 20 61 6e 61 6c 79 cycle, is analy
1bc0: 73 65 64 20 61 6e 64 20 74 68 65 20 62 65 73 74 sed and the best
1bd0: 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e 20 77 68 ...# location wh
1be0: 65 72 65 20 74 6f 20 61 74 20 6c 65 61 73 74 20 ere to at least
1bf0: 77 65 61 6b 65 6e 20 74 68 65 20 63 79 63 6c 65 weaken the cycle
1c00: 20 69 73 0a 09 09 23 20 63 68 6f 73 65 6e 20 66 is...# chosen f
1c10: 6f 72 20 66 75 72 74 68 65 72 20 70 72 6f 63 65 or further proce
1c20: 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 20 6c 69 ssing.....set li
1c30: 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 76 nk [project::rev
1c40: 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 70 72 65 link %AUTO% $pre
1c50: 76 20 24 63 73 65 74 20 24 6e 65 78 74 5d 0a 09 v $cset $next]..
1c60: 09 69 66 20 7b 24 62 65 73 74 6c 69 6e 6b 20 65 .if {$bestlink e
1c70: 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 20 73 65 q ""} {... se
1c80: 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b t bestlink $link
1c90: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6e ... set bestn
1ca0: 6f 64 65 20 24 63 73 65 74 0a 09 09 7d 20 65 6c ode $cset...} el
1cb0: 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 62 65 74 seif {[$link bet
1cc0: 74 65 72 74 68 61 6e 20 24 62 65 73 74 6c 69 6e terthan $bestlin
1cd0: 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 62 65 73 k]} {... $bes
1ce0: 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 09 tlink destroy...
1cf0: 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e 6b set bestlink
1d00: 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 $link... set
1d10: 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 0a bestnode $cset.
1d20: 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 20 20 20 ..} else {...
1d30: 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 $link destroy..
1d40: 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c 6f 67 20 .}.. }...log
1d50: 77 72 69 74 65 20 35 20 62 72 65 61 6b 72 63 79 write 5 breakrcy
1d60: 63 6c 65 20 22 42 72 65 61 6b 69 6e 67 20 63 79 cle "Breaking cy
1d70: 63 6c 65 20 28 24 63 70 72 69 6e 74 29 20 62 79 cle ($cprint) by
1d80: 20 73 70 6c 69 74 74 69 6e 67 20 63 68 61 6e 67 splitting chang
1d90: 65 73 65 74 20 3c 5b 24 62 65 73 74 6e 6f 64 65 eset <[$bestnode
1da0: 20 69 64 5d 3e 22 0a 0a 09 73 65 74 20 6e 65 77 id]>"...set new
1db0: 63 73 65 74 73 20 5b 24 62 65 73 74 6c 69 6e 6b csets [$bestlink
1dc0: 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 74 6c 69 break]..$bestli
1dd0: 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 20 20 20 nk destroy..
1de0: 20 20 20 20 23 20 41 74 20 74 68 69 73 20 70 6f # At this po
1df0: 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 68 61 6e int the old chan
1e00: 67 65 73 65 74 20 28 42 45 53 54 4e 4f 44 45 29 geset (BESTNODE)
1e10: 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 20 20 20 is gone.
1e20: 20 23 20 61 6c 72 65 61 64 79 2e 20 57 65 20 72 # already. We r
1e30: 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d 20 74 68 emove it from th
1e40: 65 20 67 72 61 70 68 20 61 73 20 77 65 6c 6c 20 e graph as well
1e50: 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 72 0a 20 and then enter.
1e60: 20 20 20 20 20 20 20 23 20 74 68 65 20 66 72 61 # the fra
1e70: 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 74 65 64 gments generated
1e80: 20 66 6f 72 20 69 74 2e 0a 0a 20 20 20 20 20 20 for it...
1e90: 20 20 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 74 $dg node delet
1ea0: 65 20 24 62 65 73 74 6e 6f 64 65 0a 0a 09 66 6f e $bestnode...fo
1eb0: 72 65 61 63 68 20 63 73 65 74 20 24 6e 65 77 63 reach cset $newc
1ec0: 73 65 74 73 20 7b 0a 09 20 20 20 20 24 64 67 20 sets {.. $dg
1ed0: 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 node insert $cse
1ee0: 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 t.. $dg node
1ef0: 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 6d set $cset tim
1f00: 65 72 61 6e 67 65 20 5b 24 63 73 65 74 20 74 69 erange [$cset ti
1f10: 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a 09 66 6f merange]..}...fo
1f20: 72 65 61 63 68 20 63 73 65 74 20 24 6e 65 77 63 reach cset $newc
1f30: 73 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 sets {.. fore
1f40: 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 ach succ [$cset
1f50: 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 successors] {...
1f60: 23 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 65 # The new change
1f70: 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 sets may have de
1f80: 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 pendencies outsi
1f90: 64 65 20 6f 66 0a 09 09 23 20 74 68 65 20 63 68 de of...# the ch
1fa0: 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 osen set. These
1fb0: 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 are ignored...if
1fc0: 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 {![$dg node exi
1fd0: 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 sts $succ]} cont
1fe0: 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 inue...$dg arc i
1ff0: 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 63 nsert $cset $suc
2000: 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 72 65 74 c.. }..}..ret
2010: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 urn. }.. t
2020: 79 70 65 76 61 72 69 61 62 6c 65 20 61 74 20 20 ypevariable at
2030: 20 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 0 ; # Counte
2040: 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 69 64 73 r for commit ids
2050: 20 66 6f 72 20 74 68 65 20 63 68 61 6e 67 65 73 for the changes
2060: 65 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 ets.. typevar
2070: 69 61 62 6c 65 20 62 6f 74 74 6f 6d 20 7b 7d 20 iable bottom {}
2080: 3b 20 23 20 4c 69 73 74 20 6f 66 20 63 61 6e 64 ; # List of cand
2090: 69 64 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 20 idate nodes for
20a0: 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 20 20 20 20 committing..
20b0: 74 79 70 65 76 61 72 69 61 62 6c 65 20 73 61 76 typevariable sav
20c0: 65 20 20 20 7b 7d 20 3b 20 23 20 54 68 65 20 63 e {} ; # The c
20d0: 6f 6d 6d 61 6e 64 20 74 6f 20 63 61 6c 6c 20 66 ommand to call f
20e0: 6f 72 20 65 61 63 68 20 70 72 6f 63 65 73 73 65 or each processe
20f0: 64 20 6e 6f 64 65 0a 0a 20 20 20 20 23 20 23 20 d node.. # #
2100: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
2110: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
2120: 23 23 23 0a 20 20 20 20 23 23 20 43 6f 6e 66 69 ###. ## Confi
2130: 67 75 72 61 74 69 6f 6e 0a 0a 20 20 20 20 70 72 guration.. pr
2140: 61 67 6d 61 20 2d 68 61 73 69 6e 73 74 61 6e 63 agma -hasinstanc
2150: 65 73 20 20 20 6e 6f 20 3b 20 23 20 73 69 6e 67 es no ; # sing
2160: 6c 65 74 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 leton. pragma
2170: 20 2d 68 61 73 74 79 70 65 69 6e 66 6f 20 20 20 -hastypeinfo
2180: 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 6e 74 72 6f no ; # no intro
2190: 73 70 65 63 74 69 6f 6e 0a 20 20 20 20 70 72 61 spection. pra
21a0: 67 6d 61 20 2d 68 61 73 74 79 70 65 64 65 73 74 gma -hastypedest
21b0: 72 6f 79 20 6e 6f 20 3b 20 23 20 69 6d 6d 6f 72 roy no ; # immor
21c0: 74 61 6c 0a 0a 20 20 20 20 23 20 23 20 23 23 20 tal.. # # ##
21d0: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
21e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
21f0: 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 65 20 65 76 .}..namespace ev
2200: 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a al ::vc::fossil:
2210: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 20 7b 0a 20 :import::cvs {.
2220: 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 78 70 namespace exp
2230: 6f 72 74 20 63 79 63 6c 65 62 72 65 61 6b 65 72 ort cyclebreaker
2240: 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 . namespace e
2250: 76 61 6c 20 63 79 63 6c 65 62 72 65 61 6b 65 72 val cyclebreaker
2260: 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 20 65 76 {..namespace ev
2270: 61 6c 20 70 72 6f 6a 65 63 74 20 7b 0a 09 20 20 al project {..
2280: 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f namespace impo
2290: 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a rt ::vc::fossil:
22a0: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 :import::cvs::pr
22b0: 6f 6a 65 63 74 3a 3a 72 65 76 0a 09 20 20 20 20 oject::rev..
22c0: 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 namespace import
22d0: 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 ::vc::fossil::i
22e0: 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a mport::cvs::proj
22f0: 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a ect::revlink..}.
2300: 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 .namespace impor
2310: 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d t ::vc::tools::m
2320: 69 73 63 3a 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 isc::*..namespac
2330: 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 e import ::vc::t
2340: 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 6c 6f 67 20 72 ools::log..log r
2350: 65 67 69 73 74 65 72 20 63 79 63 6c 65 62 72 65 egister cyclebre
2360: 61 6b 65 72 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 aker. }.}..#
2370: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
2380: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
2390: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
23a0: 23 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 ###########.## R
23b0: 65 61 64 79 0a 0a 70 61 63 6b 61 67 65 20 70 72 eady..package pr
23c0: 6f 76 69 64 65 20 76 63 3a 3a 66 6f 73 73 69 6c ovide vc::fossil
23d0: 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 ::import::cvs::c
23e0: 79 63 6c 65 62 72 65 61 6b 65 72 20 31 2e 30 0a yclebreaker 1.0.
23f0: 72 65 74 75 72 6e 0a return.