Artifact b193a65e99720250826579001800b51905924623:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[770a9b576a]
- Completed pass 7, breaking dependency cycles over symbol changesets. Moved the bulk of the cycle breaker code into its own class as it was common to the passes 6 and 7, and updated the two passes accordingly. Added code to load the changeset counter from the state to start properly.
by
aku on
2007-11-16 04:17:30.
0000: 23 23 20 2d 2a 2d 20 74 63 6c 20 2d 2a 2d 0a 23 ## -*- tcl -*-.#
0010: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
0020: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
0030: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
0040: 23 23 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 ############.##
0050: 43 6f 70 79 72 69 67 68 74 20 28 63 29 20 32 30 Copyright (c) 20
0060: 30 37 20 41 6e 64 72 65 61 73 20 4b 75 70 72 69 07 Andreas Kupri
0070: 65 73 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 es..#.# This sof
0080: 74 77 61 72 65 20 69 73 20 6c 69 63 65 6e 73 65 tware is license
0090: 64 20 61 73 20 64 65 73 63 72 69 62 65 64 20 69 d as described i
00a0: 6e 20 74 68 65 20 66 69 6c 65 20 4c 49 43 45 4e n the file LICEN
00b0: 53 45 2c 20 77 68 69 63 68 0a 23 20 79 6f 75 20 SE, which.# you
00c0: 73 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 should have rece
00d0: 69 76 65 64 20 61 73 20 70 61 72 74 20 6f 66 20 ived as part of
00e0: 74 68 69 73 20 64 69 73 74 72 69 62 75 74 69 6f this distributio
00f0: 6e 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 74 n..#.# This soft
0100: 77 61 72 65 20 63 6f 6e 73 69 73 74 73 20 6f 66 ware consists of
0110: 20 76 6f 6c 75 6e 74 61 72 79 20 63 6f 6e 74 72 voluntary contr
0120: 69 62 75 74 69 6f 6e 73 20 6d 61 64 65 20 62 79 ibutions made by
0130: 20 6d 61 6e 79 0a 23 20 69 6e 64 69 76 69 64 75 many.# individu
0140: 61 6c 73 2e 20 20 46 6f 72 20 65 78 61 63 74 20 als. For exact
0150: 63 6f 6e 74 72 69 62 75 74 69 6f 6e 20 68 69 73 contribution his
0160: 74 6f 72 79 2c 20 73 65 65 20 74 68 65 20 72 65 tory, see the re
0170: 76 69 73 69 6f 6e 0a 23 20 68 69 73 74 6f 72 79 vision.# history
0180: 20 61 6e 64 20 6c 6f 67 73 2c 20 61 76 61 69 6c and logs, avail
0190: 61 62 6c 65 20 61 74 20 68 74 74 70 3a 2f 2f 66 able at http://f
01a0: 6f 73 73 69 6c 2d 73 63 6d 2e 68 77 61 63 69 2e ossil-scm.hwaci.
01b0: 63 6f 6d 2f 66 6f 73 73 69 6c 0a 23 20 23 20 23 com/fossil.# # #
01c0: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
01d0: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
01e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
01f0: 23 23 23 23 23 23 23 23 0a 0a 23 23 20 54 68 69 ########..## Thi
0200: 73 20 66 69 6c 65 20 70 72 6f 76 69 64 65 73 20 s file provides
0210: 61 20 68 65 6c 70 65 72 20 70 61 63 6b 61 67 65 a helper package
0220: 20 66 6f 72 20 74 68 65 20 70 61 73 73 65 73 20 for the passes
0230: 36 20 61 6e 64 20 37 20 77 68 69 63 68 0a 23 23 6 and 7 which.##
0240: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 6f contains the co
0250: 6d 6d 6f 6e 20 63 6f 64 65 20 6f 66 20 74 68 65 mmon code of the
0260: 20 63 79 63 6c 65 20 62 72 65 61 6b 69 6e 67 20 cycle breaking
0270: 61 6c 67 6f 72 69 74 68 6d 2e 0a 0a 23 20 23 20 algorithm...# #
0280: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
0290: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
02a0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
02b0: 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 71 #########.## Req
02c0: 75 69 72 65 6d 65 6e 74 73 0a 0a 70 61 63 6b 61 uirements..packa
02d0: 67 65 20 72 65 71 75 69 72 65 20 54 63 6c 20 38 ge require Tcl 8
02e0: 2e 34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .4
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0300: 20 20 20 20 20 3b 20 23 20 52 65 71 75 69 72 65 ; # Require
0310: 64 20 72 75 6e 74 69 6d 65 2e 0a 70 61 63 6b 61 d runtime..packa
0320: 67 65 20 72 65 71 75 69 72 65 20 73 6e 69 74 20 ge require snit
0330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0350: 20 20 20 20 20 3b 20 23 20 4f 4f 20 73 79 73 74 ; # OO syst
0360: 65 6d 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 em..package requ
0370: 69 72 65 20 73 74 72 75 63 74 3a 3a 67 72 61 70 ire struct::grap
0380: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 h
0390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
03a0: 23 20 47 72 61 70 68 20 68 61 6e 64 6c 69 6e 67 # Graph handling
03b0: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 ..package requir
03c0: 65 20 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 20 e struct::list
03d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
03e0: 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 23 20 ; #
03f0: 48 69 67 68 65 72 20 6f 72 64 65 72 20 6c 69 73 Higher order lis
0400: 74 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 70 61 t operations..pa
0410: 63 6b 61 67 65 20 72 65 71 75 69 72 65 20 76 63 ckage require vc
0420: 3a 3a 74 6f 6f 6c 73 3a 3a 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 6c 6f 67 20 77 72 $dg..}...log wr
0cd0: 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b ite 3 cyclebreak
0ce0: 65 72 20 44 6f 6e 65 2e 0a 09 72 65 74 75 72 6e er Done...return
0cf0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 . }.. # #
0d00: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
0d10: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
0d20: 23 23 23 0a 20 20 20 20 23 23 20 49 6e 74 65 72 ###. ## Inter
0d30: 6e 61 6c 20 6d 65 74 68 6f 64 73 0a 0a 20 20 20 nal methods..
0d40: 20 23 20 49 6e 73 74 65 61 64 20 6f 66 20 73 65 # Instead of se
0d50: 61 72 63 68 69 6e 67 20 74 68 65 20 77 68 6f 6c arching the whol
0d60: 65 20 67 72 61 70 68 20 66 6f 72 20 74 68 65 20 e graph for the
0d70: 64 65 67 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 degree-0 nodes i
0d80: 6e 0a 20 20 20 20 23 20 65 61 63 68 20 69 74 65 n. # each ite
0d90: 72 61 74 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 ration we comput
0da0: 65 20 74 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 e the list once
0db0: 74 6f 20 73 74 61 72 74 2c 20 61 6e 64 20 74 68 to start, and th
0dc0: 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 en only. # up
0dd0: 64 61 74 65 20 69 74 20 69 6e 63 72 65 6d 65 6e date it incremen
0de0: 74 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 tally based on t
0df0: 68 65 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 he outgoing neig
0e00: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 0a 20 20 hbours of the.
0e10: 20 20 23 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 # node chosen
0e20: 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 for commit...
0e30: 20 70 72 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 proc Initialize
0e40: 43 61 6e 64 69 64 61 74 65 73 20 7b 64 67 7d 20 Candidates {dg}
0e50: 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 {..# bottom = li
0e60: 73 74 20 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 st (list (node,
0e70: 72 61 6e 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 range min, range
0e80: 20 6d 61 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 max))..::variab
0e90: 6c 65 20 62 6f 74 74 6f 6d 0a 09 66 6f 72 65 61 le bottom..forea
0ea0: 63 68 20 6e 20 5b 24 64 67 20 6e 6f 64 65 73 5d ch n [$dg nodes]
0eb0: 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 64 67 {.. if {[$dg
0ec0: 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d 69 6e node degree -in
0ed0: 20 24 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 $n]} continue..
0ee0: 20 20 20 20 6c 61 70 70 65 6e 64 20 62 6f 74 74 lappend bott
0ef0: 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 om [linsert [$dg
0f00: 20 6e 6f 64 65 20 67 65 74 20 24 6e 20 74 69 6d node get $n tim
0f10: 65 72 61 6e 67 65 5d 20 30 20 24 6e 5d 0a 09 7d erange] 0 $n]..}
0f20: 0a 09 73 65 74 20 62 6f 74 74 6f 6d 20 5b 6c 73 ..set bottom [ls
0f30: 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e ort -index 1 -in
0f40: 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e teger [lsort -in
0f50: 64 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 dex 2 -integer $
0f60: 62 6f 74 74 6f 6d 5d 5d 0a 09 72 65 74 75 72 6e bottom]]..return
0f70: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
0f80: 20 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 WithoutPredeces
0f90: 73 6f 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a sor {dg nv} {..:
0fa0: 3a 76 61 72 69 61 62 6c 65 20 62 6f 74 74 6f 6d :variable bottom
0fb0: 0a 0a 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e ...upvar 1 $nv n
0fc0: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
0fd0: 24 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 $bottom]} { retu
0fe0: 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e 20 5b rn 0 }...set n [
0ff0: 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 20 24 lindex [lindex $
1000: 62 6f 74 74 6f 6d 20 30 5d 20 30 5d 0a 09 73 65 bottom 0] 0]..se
1010: 74 20 62 6f 74 74 6f 6d 20 5b 6c 72 61 6e 67 65 t bottom [lrange
1020: 20 24 62 6f 74 74 6f 6d 20 31 20 65 6e 64 5d 0a $bottom 1 end].
1030: 09 73 65 74 20 63 68 61 6e 67 65 64 20 30 0a 0a .set changed 0..
1040: 09 23 20 55 70 64 61 74 65 20 6c 69 73 74 20 6f .# Update list o
1050: 66 20 6e 6f 64 65 73 20 77 69 74 68 6f 75 74 20 f nodes without
1060: 70 72 65 64 65 63 65 73 73 6f 72 2c 20 62 61 73 predecessor, bas
1070: 65 64 20 6f 6e 20 74 68 65 0a 09 23 20 6f 75 74 ed on the..# out
1080: 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 going neighbours
1090: 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 6e of the chosen n
10a0: 6f 64 65 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 ode. This should
10b0: 20 62 65 0a 09 23 20 66 61 73 74 65 72 20 74 68 be..# faster th
10c0: 61 6e 20 69 74 65 72 61 74 69 6e 67 20 6f 66 20 an iterating of
10d0: 74 68 65 20 77 68 6f 6c 65 20 73 65 74 20 6f 66 the whole set of
10e0: 20 6e 6f 64 65 73 2c 20 66 69 6e 64 69 6e 67 20 nodes, finding
10f0: 61 6c 6c 0a 09 23 20 77 69 74 68 6f 75 74 20 70 all..# without p
1100: 72 65 64 65 63 65 73 73 6f 72 73 2c 20 73 6f 72 redecessors, sor
1110: 74 69 6e 67 20 74 68 65 6d 20 62 79 20 74 69 6d ting them by tim
1120: 65 2c 20 65 74 63 2e 20 70 70 2e 0a 09 66 6f 72 e, etc. pp...for
1130: 65 61 63 68 20 6f 75 74 20 5b 24 64 67 20 6e 6f each out [$dg no
1140: 64 65 73 20 2d 6f 75 74 20 24 6e 5d 20 7b 0a 09 des -out $n] {..
1150: 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 if {[$dg nod
1160: 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 6f 75 e degree -in $ou
1170: 74 5d 20 3e 20 31 7d 20 63 6f 6e 74 69 6e 75 65 t] > 1} continue
1180: 0a 09 20 20 20 20 23 20 44 65 67 72 65 65 2d 31 .. # Degree-1
1190: 20 6e 65 69 67 68 62 6f 75 72 2c 20 77 69 6c 6c neighbour, will
11a0: 20 68 61 76 65 20 6e 6f 20 70 72 65 64 65 63 65 have no predece
11b0: 73 73 6f 72 73 20 61 66 74 65 72 20 74 68 65 0a ssors after the.
11c0: 09 20 20 20 20 23 20 72 65 6d 6f 76 61 6c 20 6f . # removal o
11d0: 66 20 6e 2e 20 50 75 74 20 6f 6e 20 74 68 65 20 f n. Put on the
11e0: 6c 69 73 74 2e 0a 09 20 20 20 20 6c 61 70 70 65 list... lappe
11f0: 6e 64 20 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 nd bottom [linse
1200: 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 rt [$dg node get
1210: 20 24 6f 75 74 20 74 69 6d 65 72 61 6e 67 65 5d $out timerange]
1220: 20 30 20 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 0 $out].. se
1230: 74 20 63 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 t changed 1..}..
1240: 69 66 20 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a if {$changed} {.
1250: 09 20 20 20 20 73 65 74 20 62 6f 74 74 6f 6d 20 . set bottom
1260: 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 [lsort -index 1
1270: 2d 69 6e 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 -integer [lsort
1280: 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 67 65 -index 2 -intege
1290: 72 20 24 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a r $bottom]]..}..
12a0: 09 23 20 57 65 20 64 6f 20 6e 6f 74 20 64 65 6c .# We do not del
12b0: 65 74 65 20 74 68 65 20 6e 6f 64 65 20 69 6d 6d ete the node imm
12c0: 65 64 69 61 74 65 6c 79 2c 20 74 6f 20 61 6c 6c ediately, to all
12d0: 6f 77 20 74 68 65 20 53 61 76 65 0a 09 23 20 70 ow the Save..# p
12e0: 72 6f 63 65 64 75 72 65 20 74 6f 20 73 61 76 65 rocedure to save
12f0: 20 74 68 65 20 64 65 70 65 6e 64 65 6e 63 69 65 the dependencie
1300: 73 20 61 73 20 77 65 6c 6c 20 28 65 6e 63 6f 64 s as well (encod
1310: 65 64 20 69 6e 20 74 68 65 0a 09 23 20 61 72 63 ed in the..# arc
1320: 73 29 2e 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 s)...return 1.
1330: 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 53 61 }.. proc Sa
1340: 76 65 41 6e 64 52 65 6d 6f 76 65 20 7b 64 67 20 veAndRemove {dg
1350: 6e 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 n} {..::variable
1360: 20 61 74 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 at..::variable
1370: 73 61 76 65 0a 0a 09 23 20 47 69 76 65 20 74 68 save...# Give th
1380: 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 63 79 e user of the cy
1390: 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 65 20 cle breaker the
13a0: 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f 20 77 opportunity to w
13b0: 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 65 20 ork..# with the
13c0: 63 68 61 6e 67 65 73 65 74 20 62 65 66 6f 72 65 changeset before
13d0: 20 69 74 20 69 73 20 72 65 6d 6f 76 65 64 20 66 it is removed f
13e0: 72 6f 6d 20 74 68 65 20 67 72 61 70 68 2e 0a 0a rom the graph...
13f0: 09 69 66 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 73 .if {[llength $s
1400: 61 76 65 5d 7d 20 7b 0a 09 20 20 20 20 75 70 6c ave]} {.. upl
1410: 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 evel #0 [linsert
1420: 20 24 73 61 76 65 20 65 6e 64 20 24 61 74 20 24 $save end $at $
1430: 6e 5d 0a 09 7d 0a 0a 09 69 6e 63 72 20 61 74 0a n]..}...incr at.
1440: 09 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 74 65 .$dg node delete
1450: 20 24 6e 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 $n..return.
1460: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 }.. proc Find
1470: 43 79 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 Cycle {dg} {..#
1480: 54 68 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 This procedure i
1490: 73 20 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c s run if and onl
14a0: 79 20 74 68 65 20 67 72 61 70 68 20 69 73 20 6e y the graph is n
14b0: 6f 74 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 ot empty and..#
14c0: 61 6c 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 all nodes have p
14d0: 72 65 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 redecessors. Thi
14e0: 73 20 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 s means that eac
14f0: 68 20 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 h node is..# eit
1500: 68 65 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 her part of a cy
1510: 63 6c 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 cle or (indirect
1520: 6c 79 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e ly) depending on
1530: 20 61 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 a node..# in a
1540: 63 79 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 cycle. We can st
1550: 61 72 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 art at an arbitr
1560: 61 72 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 ary node, follow
1570: 20 69 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 its..# incoming
1580: 20 65 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 edges to its pr
1590: 65 64 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c edecessors until
15a0: 20 77 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 we see a node a
15b0: 0a 09 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e ..# second time.
15c0: 20 54 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 That node close
15d0: 73 20 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 s the cycle and
15e0: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 the beginning is
15f0: 0a 09 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 ..# its first oc
1600: 63 75 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 curence. Note th
1610: 61 74 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 at we can choose
1620: 20 61 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 an arbitrary..#
1630: 20 70 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 predecessor of
1640: 65 61 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c each node as wel
1650: 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 l, we do not hav
1660: 65 20 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 e to search....#
1670: 20 57 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 We record for e
1680: 61 63 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 ach node the ind
1690: 65 78 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 ex of the first
16a0: 61 70 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 appearance in..#
16b0: 20 74 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e the path, makin
16c0: 67 20 69 74 20 65 61 73 79 20 61 74 20 74 68 65 g it easy at the
16d0: 20 65 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 end to cut the
16e0: 63 79 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 cycle from..# it
16f0: 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 ....# Choose arb
1700: 69 74 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 itrary node to s
1710: 74 61 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 tart our search
1720: 61 74 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b at...set start [
1730: 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 lindex [$dg node
1740: 73 5d 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 s] 0]...# Initia
1750: 6c 69 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 lize state, path
1760: 20 6f 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 of seen nodes,
1770: 61 6e 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 and when seen...
1780: 73 65 74 20 20 20 20 20 20 20 70 61 74 68 20 7b set path {
1790: 7d 0a 09 61 72 72 61 79 20 73 65 74 20 73 65 65 }..array set see
17a0: 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d n {}...while {1}
17b0: 20 7b 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 {.. # Stop s
17c0: 65 61 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 earching when we
17d0: 20 68 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 have seen the c
17e0: 75 72 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 urrent node..
17f0: 20 23 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 # already, the
1800: 63 69 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 circle has been
1810: 63 6c 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 closed... if
1820: 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 {[info exists se
1830: 65 6e 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 en($start)]} bre
1840: 61 6b 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 ak.. lappend
1850: 70 61 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 path $start..
1860: 20 73 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 set seen($start
1870: 29 20 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 ) [expr {[llengt
1880: 68 20 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 h $path]-1}]..
1890: 20 20 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 # Choose arbit
18a0: 72 61 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 rary predecessor
18b0: 0a 09 20 20 20 20 73 65 74 20 73 74 61 72 74 20 .. set start
18c0: 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 [lindex [$dg nod
18d0: 65 73 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 es -in $start] 0
18e0: 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 ]..}...return [s
18f0: 74 72 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 truct::list reve
1900: 72 73 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 rse [lrange $pat
1910: 68 20 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 h $seen($start)
1920: 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 end]]. }..
1930: 20 70 72 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 proc ID {cset}
1940: 7b 20 72 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 { return "<[$cse
1950: 74 20 69 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 t id]>" }.. p
1960: 72 6f 63 20 42 72 65 61 6b 43 79 63 6c 65 20 7b roc BreakCycle {
1970: 64 67 20 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 dg cycle} {..# T
1980: 68 65 20 63 79 63 6c 65 20 77 65 20 68 61 76 65 he cycle we have
1990: 20 67 6f 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 gotten is broke
19a0: 6e 20 62 79 20 62 72 65 61 6b 69 6e 67 20 61 70 n by breaking ap
19b0: 61 72 74 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f art one or..# mo
19c0: 72 65 20 6f 66 20 74 68 65 20 63 68 61 6e 67 65 re of the change
19d0: 73 65 74 73 20 69 6e 20 74 68 65 20 63 79 63 6c sets in the cycl
19e0: 65 2e 20 54 68 69 73 20 63 61 75 73 65 73 20 75 e. This causes u
19f0: 73 20 74 6f 0a 09 23 20 63 72 65 61 74 65 20 6f s to..# create o
1a00: 6e 65 20 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 ne or more chang
1a10: 65 73 65 74 73 20 77 68 69 63 68 20 61 72 65 20 esets which are
1a20: 74 6f 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c to be committed,
1a30: 0a 09 23 20 61 64 64 65 64 20 74 6f 20 74 68 65 ..# added to the
1a40: 20 67 72 61 70 68 2c 20 65 74 63 2e 20 70 70 2e graph, etc. pp.
1a50: 0a 0a 09 73 65 74 20 63 70 72 69 6e 74 20 5b 6a ...set cprint [j
1a60: 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 oin [struct::lis
1a70: 74 20 6d 61 70 20 24 63 79 63 6c 65 20 5b 6d 79 t map $cycle [my
1a80: 70 72 6f 63 20 49 44 5d 5d 20 7b 20 7d 5d 0a 0a proc ID]] { }]..
1a90: 09 6c 61 70 70 65 6e 64 20 63 79 63 6c 65 20 5b .lappend cycle [
1aa0: 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 30 5d lindex $cycle 0]
1ab0: 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 [lindex $cycle
1ac0: 31 5d 0a 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 1]..set bestlink
1ad0: 20 7b 7d 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 {}..set bestnod
1ae0: 65 20 7b 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c e {}...foreach \
1af0: 0a 09 20 20 20 20 70 72 65 76 20 5b 6c 72 61 6e .. prev [lran
1b00: 67 65 20 24 63 79 63 6c 65 20 30 20 65 6e 64 2d ge $cycle 0 end-
1b10: 32 5d 20 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 2] \.. cset [
1b20: 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 31 20 lrange $cycle 1
1b30: 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 end-1] \.. ne
1b40: 78 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c xt [lrange $cycl
1b50: 65 20 32 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 e 2 end] {....#
1b60: 45 61 63 68 20 74 72 69 70 6c 65 20 50 52 45 56 Each triple PREV
1b70: 20 2d 3e 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 -> CSET -> NEXT
1b80: 20 6f 66 20 63 68 61 6e 67 65 73 65 74 73 2c 20 of changesets,
1b90: 61 0a 09 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 a...# 'link' in
1ba0: 74 68 65 20 63 79 63 6c 65 2c 20 69 73 20 61 6e the cycle, is an
1bb0: 61 6c 79 73 65 64 20 61 6e 64 20 74 68 65 20 62 alysed and the b
1bc0: 65 73 74 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e est...# location
1bd0: 20 77 68 65 72 65 20 74 6f 20 61 74 20 6c 65 61 where to at lea
1be0: 73 74 20 77 65 61 6b 65 6e 20 74 68 65 20 63 79 st weaken the cy
1bf0: 63 6c 65 20 69 73 0a 09 09 23 20 63 68 6f 73 65 cle is...# chose
1c00: 6e 20 66 6f 72 20 66 75 72 74 68 65 72 20 70 72 n for further pr
1c10: 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 ocessing.....set
1c20: 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a link [project::
1c30: 72 65 76 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 revlink %AUTO% $
1c40: 70 72 65 76 20 24 63 73 65 74 20 24 6e 65 78 74 prev $cset $next
1c50: 5d 0a 09 09 69 66 20 7b 24 62 65 73 74 6c 69 6e ]...if {$bestlin
1c60: 6b 20 65 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 k eq ""} {...
1c70: 20 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c set bestlink $l
1c80: 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 ink... set be
1c90: 73 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d stnode $cset...}
1ca0: 20 65 6c 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 elseif {[$link
1cb0: 62 65 74 74 65 72 74 68 61 6e 20 24 62 65 73 74 betterthan $best
1cc0: 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 link]} {... $
1cd0: 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 bestlink destroy
1ce0: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6c ... set bestl
1cf0: 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 ink $link...
1d00: 73 65 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 set bestnode $cs
1d10: 65 74 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 et...} else {...
1d20: 20 20 20 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f $link destro
1d30: 79 0a 09 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c y...}.. }...l
1d40: 6f 67 20 77 72 69 74 65 20 35 20 62 72 65 61 6b og write 5 break
1d50: 72 63 79 63 6c 65 20 22 42 72 65 61 6b 69 6e 67 rcycle "Breaking
1d60: 20 63 79 63 6c 65 20 28 24 63 70 72 69 6e 74 29 cycle ($cprint)
1d70: 20 62 79 20 73 70 6c 69 74 74 69 6e 67 20 63 68 by splitting ch
1d80: 61 6e 67 65 73 65 74 20 3c 5b 24 62 65 73 74 6e angeset <[$bestn
1d90: 6f 64 65 20 69 64 5d 3e 22 0a 0a 09 73 65 74 20 ode id]>"...set
1da0: 6e 65 77 63 73 65 74 73 20 5b 24 62 65 73 74 6c newcsets [$bestl
1db0: 69 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 ink break]..$bes
1dc0: 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 tlink destroy..
1dd0: 20 20 20 20 20 20 20 23 20 41 74 20 74 68 69 73 # At this
1de0: 20 70 6f 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 point the old c
1df0: 68 61 6e 67 65 73 65 74 20 28 42 45 53 54 4e 4f hangeset (BESTNO
1e00: 44 45 29 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 DE) is gone.
1e10: 20 20 20 20 23 20 61 6c 72 65 61 64 79 2e 20 57 # already. W
1e20: 65 20 72 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d e remove it from
1e30: 20 74 68 65 20 67 72 61 70 68 20 61 73 20 77 65 the graph as we
1e40: 6c 6c 20 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 ll and then ente
1e50: 72 0a 20 20 20 20 20 20 20 20 23 20 74 68 65 20 r. # the
1e60: 66 72 61 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 fragments genera
1e70: 74 65 64 20 66 6f 72 20 69 74 2e 0a 0a 20 20 20 ted for it...
1e80: 20 20 20 20 20 24 64 67 20 6e 6f 64 65 20 64 65 $dg node de
1e90: 6c 65 74 65 20 24 62 65 73 74 6e 6f 64 65 0a 0a lete $bestnode..
1ea0: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e .foreach cset $n
1eb0: 65 77 63 73 65 74 73 20 7b 0a 09 20 20 20 20 24 ewcsets {.. $
1ec0: 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 dg node insert $
1ed0: 63 73 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f cset.. $dg no
1ee0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
1ef0: 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 73 65 74 timerange [$cset
1f00: 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a timerange]..}..
1f10: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e .foreach cset $n
1f20: 65 77 63 73 65 74 73 20 7b 0a 09 20 20 20 20 66 ewcsets {.. f
1f30: 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 oreach succ [$cs
1f40: 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b et successors] {
1f50: 0a 09 09 23 20 54 68 65 20 6e 65 77 20 63 68 61 ...# The new cha
1f60: 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 ngesets may have
1f70: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 dependencies ou
1f80: 74 73 69 64 65 20 6f 66 0a 09 09 23 20 74 68 65 tside of...# the
1f90: 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 chosen set. The
1fa0: 73 65 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 se are ignored..
1fb0: 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 .if {![$dg node
1fc0: 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 exists $succ]} c
1fd0: 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 ontinue...$dg ar
1fe0: 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 c insert $cset $
1ff0: 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 succ.. }..}..
2000: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
2010: 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 61 typevariable a
2020: 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 t 0 ; # Cou
2030: 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 nter for commit
2040: 69 64 73 20 66 6f 72 20 74 68 65 20 63 68 61 6e ids for the chan
2050: 67 65 73 65 74 73 2e 0a 20 20 20 20 74 79 70 65 gesets.. type
2060: 76 61 72 69 61 62 6c 65 20 62 6f 74 74 6f 6d 20 variable bottom
2070: 7b 7d 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 63 {} ; # List of c
2080: 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 73 20 66 andidate nodes f
2090: 6f 72 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 20 or committing..
20a0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
20b0: 73 61 76 65 20 20 20 7b 7d 20 3b 20 23 20 54 68 save {} ; # Th
20c0: 65 20 63 6f 6d 6d 61 6e 64 20 74 6f 20 63 61 6c e command to cal
20d0: 6c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 l for each proce
20e0: 73 73 65 64 20 6e 6f 64 65 0a 0a 20 20 20 20 23 ssed node.. #
20f0: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
2100: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
2110: 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 6f ######. ## Co
2120: 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 20 nfiguration..
2130: 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 74 pragma -hasinst
2140: 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 73 ances no ; # s
2150: 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 61 ingleton. pra
2160: 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 6f gma -hastypeinfo
2170: 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 6e no ; # no in
2180: 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 20 trospection.
2190: 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 64 pragma -hastyped
21a0: 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 6d estroy no ; # im
21b0: 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 20 mortal.. # #
21c0: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
21d0: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
21e0: 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 65 ###.}..namespace
21f0: 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 73 eval ::vc::foss
2200: 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 20 il::import::cvs
2210: 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 {. namespace
2220: 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 61 export cyclebrea
2230: 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 ker. namespac
2240: 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 61 e eval cyclebrea
2250: 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 ker {..namespace
2260: 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b 0a eval project {.
2270: 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 . namespace i
2280: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 mport ::vc::foss
2290: 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a il::import::cvs:
22a0: 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a 09 20 :project::rev..
22b0: 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 namespace imp
22c0: 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c ort ::vc::fossil
22d0: 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 ::import::cvs::p
22e0: 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 0a roject::revlink.
22f0: 09 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d .}..namespace im
2300: 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 port ::vc::tools
2310: 3a 3a 6d 69 73 63 3a 3a 2a 0a 09 6e 61 6d 65 73 ::misc::*..names
2320: 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 pace import ::vc
2330: 3a 3a 74 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 6c 6f ::tools::log..lo
2340: 67 20 72 65 67 69 73 74 65 72 20 63 79 63 6c 65 g register cycle
2350: 62 72 65 61 6b 65 72 0a 20 20 20 20 7d 0a 7d 0a breaker. }.}.
2360: 0a 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 .# # ## ### ####
2370: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
2380: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
2390: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 23 ##############.#
23a0: 23 20 52 65 61 64 79 0a 0a 70 61 63 6b 61 67 65 # Ready..package
23b0: 20 70 72 6f 76 69 64 65 20 76 63 3a 3a 66 6f 73 provide vc::fos
23c0: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
23d0: 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 72 20 31 ::cyclebreaker 1
23e0: 2e 30 0a 72 65 74 75 72 6e 0a .0.return.