Artifact 775fd1f9e50b00e78a90fa8b6dff8b58f288294e:
File tools/cvs2fossil/lib/c2f_cyclebreaker.tcl part of check-in [00bf8c198e] - The performance was still not satisfying, even with faster recomputing of successors. Doing it multiple times (Building the graph in each breaker and sort passes) eats time. Caching in memory blows the memory. Chosen solution: Cache this information in the database.Created a new pass 'CsetDeps' which is run between 'InitCsets' and 'BreakRevCsetCycles' (i.e. changeset creation and first breaker pass). It computes the changeset dependencies from the file-level dependencies once and saves the result in the state, in the new table 'cssuccessor'. Now the breaker and sort passes can get the information quickly, with virtually no effort. The dependencies are recomputed incrementally when a changeset is split by one of the breaker passes, for its fragments and its predecessors.
The loop check is now trivial, and integrated into the successor computation, with the heavy lifting for the detailed analysis and reporting moved down into the type-dependent SQL queries. The relevant new method is 'loops'. Now that the loop check is incremental the pass based checks have been removed from the integrity module, and the option '--loopcheck' has been eliminated. For paranoia the graph setup and modification code got its loop check reinstated as an assert, redusing the changeset report code.
Renumbered the breaker and sort passes. A number of places, like graph setup and traversal, loading of changesets, etc. got feedback indicators to show their progress.
The selection of revision and symbol changesets for the associated breaker passes was a bit on the slow side. We now keep changeset lists sorted by type (during loading or general construction) and access them directly.
by aku on 2007-12-02 20:04:40.
0000: 23 23 20 2d 2a 2d 20 74 63 6c 20 2d 2a 2d 0a 23 ## -*- tcl -*-.#
0010: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
0020: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
0030: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
0040: 23 23 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 ############.##
0050: 43 6f 70 79 72 69 67 68 74 20 28 63 29 20 32 30 Copyright (c) 20
0060: 30 37 20 41 6e 64 72 65 61 73 20 4b 75 70 72 69 07 Andreas Kupri
0070: 65 73 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 es..#.# This sof
0080: 74 77 61 72 65 20 69 73 20 6c 69 63 65 6e 73 65 tware is license
0090: 64 20 61 73 20 64 65 73 63 72 69 62 65 64 20 69 d as described i
00a0: 6e 20 74 68 65 20 66 69 6c 65 20 4c 49 43 45 4e n the file LICEN
00b0: 53 45 2c 20 77 68 69 63 68 0a 23 20 79 6f 75 20 SE, which.# you
00c0: 73 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 should have rece
00d0: 69 76 65 64 20 61 73 20 70 61 72 74 20 6f 66 20 ived as part of
00e0: 74 68 69 73 20 64 69 73 74 72 69 62 75 74 69 6f this distributio
00f0: 6e 2e 0a 23 0a 23 20 54 68 69 73 20 73 6f 66 74 n..#.# This soft
0100: 77 61 72 65 20 63 6f 6e 73 69 73 74 73 20 6f 66 ware consists of
0110: 20 76 6f 6c 75 6e 74 61 72 79 20 63 6f 6e 74 72 voluntary contr
0120: 69 62 75 74 69 6f 6e 73 20 6d 61 64 65 20 62 79 ibutions made by
0130: 20 6d 61 6e 79 0a 23 20 69 6e 64 69 76 69 64 75 many.# individu
0140: 61 6c 73 2e 20 20 46 6f 72 20 65 78 61 63 74 20 als. For exact
0150: 63 6f 6e 74 72 69 62 75 74 69 6f 6e 20 68 69 73 contribution his
0160: 74 6f 72 79 2c 20 73 65 65 20 74 68 65 20 72 65 tory, see the re
0170: 76 69 73 69 6f 6e 0a 23 20 68 69 73 74 6f 72 79 vision.# history
0180: 20 61 6e 64 20 6c 6f 67 73 2c 20 61 76 61 69 6c and logs, avail
0190: 61 62 6c 65 20 61 74 20 68 74 74 70 3a 2f 2f 66 able at http://f
01a0: 6f 73 73 69 6c 2d 73 63 6d 2e 68 77 61 63 69 2e ossil-scm.hwaci.
01b0: 63 6f 6d 2f 66 6f 73 73 69 6c 0a 23 20 23 20 23 com/fossil.# # #
01c0: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
01d0: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
01e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
01f0: 23 23 23 23 23 23 23 23 0a 0a 23 23 20 54 68 69 ########..## Thi
0200: 73 20 66 69 6c 65 20 70 72 6f 76 69 64 65 73 20 s file provides
0210: 61 20 68 65 6c 70 65 72 20 70 61 63 6b 61 67 65 a helper package
0220: 20 66 6f 72 20 74 68 65 20 70 61 73 73 65 73 20 for the passes
0230: 36 20 61 6e 64 20 37 20 77 68 69 63 68 0a 23 23 6 and 7 which.##
0240: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 63 6f contains the co
0250: 6d 6d 6f 6e 20 63 6f 64 65 20 6f 66 20 74 68 65 mmon code of the
0260: 20 63 79 63 6c 65 20 62 72 65 61 6b 69 6e 67 20 cycle breaking
0270: 61 6c 67 6f 72 69 74 68 6d 2e 0a 0a 23 20 23 20 algorithm...# #
0280: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
0290: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
02a0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
02b0: 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 71 #########.## Req
02c0: 75 69 72 65 6d 65 6e 74 73 0a 0a 70 61 63 6b 61 uirements..packa
02d0: 67 65 20 72 65 71 75 69 72 65 20 54 63 6c 20 38 ge require Tcl 8
02e0: 2e 34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .4
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0300: 20 20 20 20 20 3b 20 23 20 52 65 71 75 69 72 65 ; # Require
0310: 64 20 72 75 6e 74 69 6d 65 2e 0a 70 61 63 6b 61 d runtime..packa
0320: 67 65 20 72 65 71 75 69 72 65 20 73 6e 69 74 20 ge require snit
0330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0350: 20 20 20 20 20 3b 20 23 20 4f 4f 20 73 79 73 74 ; # OO syst
0360: 65 6d 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 em..package requ
0370: 69 72 65 20 73 74 72 75 63 74 3a 3a 67 72 61 70 ire struct::grap
0380: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 h
0390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
03a0: 23 20 47 72 61 70 68 20 68 61 6e 64 6c 69 6e 67 # Graph handling
03b0: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 ..package requir
03c0: 65 20 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 20 e struct::list
03d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
03e0: 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 23 20 ; #
03f0: 48 69 67 68 65 72 20 6f 72 64 65 72 20 6c 69 73 Higher order lis
0400: 74 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 70 61 t operations..pa
0410: 63 6b 61 67 65 20 72 65 71 75 69 72 65 20 76 63 ckage require vc
0420: 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 20 20 20 20 ::tools::dot
0430: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0440: 20 20 20 20 20 20 20 20 3b 20 23 20 55 73 65 72 ; # User
0450: 20 66 65 65 64 62 61 63 6b 2e 20 44 4f 54 20 65 feedback. DOT e
0460: 78 70 6f 72 74 2e 0a 70 61 63 6b 61 67 65 20 72 xport..package r
0470: 65 71 75 69 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 equire vc::tools
0480: 3a 3a 6c 6f 67 20 20 20 20 20 20 20 20 20 20 20 ::log
0490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
04a0: 20 3b 20 23 20 55 73 65 72 20 66 65 65 64 62 61 ; # User feedba
04b0: 63 6b 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 ck..package requ
04c0: 69 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 74 ire vc::tools::t
04d0: 72 6f 75 62 6c 65 20 20 20 20 20 20 20 20 20 20 rouble
04e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 ;
04f0: 23 20 45 72 72 6f 72 20 72 65 70 6f 72 74 69 6e # Error reportin
0500: 67 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 g..package requi
0510: 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 re vc::tools::mi
0520: 73 63 20 20 20 20 20 20 20 20 20 20 20 20 20 20 sc
0530: 20 20 20 20 20 20 20 20 20 20 20 20 20 3b 20 23 ; #
0540: 20 54 65 78 74 20 66 6f 72 6d 61 74 74 69 6e 67 Text formatting
0550: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 ..package requir
0560: 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d e vc::fossil::im
0570: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 port::cvs::proje
0580: 63 74 3a 3a 72 65 76 20 20 20 20 20 3b 20 23 20 ct::rev ; #
0590: 50 72 6f 6a 65 63 74 20 6c 65 76 65 6c 20 63 68 Project level ch
05a0: 61 6e 67 65 73 65 74 73 0a 70 61 63 6b 61 67 65 angesets.package
05b0: 20 72 65 71 75 69 72 65 20 76 63 3a 3a 66 6f 73 require vc::fos
05c0: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
05d0: 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 ::project::revli
05e0: 6e 6b 20 3b 20 23 20 43 79 63 6c 65 20 6c 69 6e nk ; # Cycle lin
05f0: 6b 73 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 ks..package requ
0600: 69 72 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a ire vc::fossil::
0610: 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 69 6e 74 import::cvs::int
0620: 65 67 72 69 74 79 20 20 20 20 20 20 20 20 3b 20 egrity ;
0630: 23 20 53 74 61 74 65 20 69 6e 74 65 67 72 69 74 # State integrit
0640: 79 20 63 68 65 63 6b 73 2e 0a 0a 23 20 23 20 23 y checks...# # #
0650: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
0660: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
0670: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
0680: 23 23 23 23 23 23 23 23 0a 23 23 0a 0a 73 6e 69 ########.##..sni
0690: 74 3a 3a 74 79 70 65 20 3a 3a 76 63 3a 3a 66 6f t::type ::vc::fo
06a0: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
06b0: 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 72 20 s::cyclebreaker
06c0: 7b 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 {. # # ## ###
06d0: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
06e0: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 #############.
06f0: 20 20 23 23 20 50 75 62 6c 69 63 20 41 50 49 0a ## Public API.
0700: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
0710: 70 72 65 63 6d 64 20 7b 63 6d 64 7d 20 7b 0a 09 precmd {cmd} {..
0720: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 70 72 65 ::variable mypre
0730: 63 6d 64 20 24 63 6d 64 0a 09 72 65 74 75 72 6e cmd $cmd..return
0740: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 . }.. type
0750: 6d 65 74 68 6f 64 20 73 61 76 65 63 6d 64 20 7b method savecmd {
0760: 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 cmd} {..::variab
0770: 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 24 63 6d le mysavecmd $cm
0780: 64 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a d..return. }.
0790: 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 . typemethod
07a0: 62 72 65 61 6b 63 6d 64 20 7b 63 6d 64 7d 20 7b breakcmd {cmd} {
07b0: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 ..::variable myb
07c0: 72 65 61 6b 63 6d 64 20 24 63 6d 64 0a 09 72 65 reakcmd $cmd..re
07d0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
07e0: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
07f0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
0800: 23 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 70 #######.. typ
0810: 65 6d 65 74 68 6f 64 20 64 6f 74 73 74 6f 20 7b emethod dotsto {
0820: 70 61 74 68 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 path} {..::varia
0830: 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 ble mydotdestina
0840: 74 69 6f 6e 20 24 70 61 74 68 0a 09 72 65 74 75 tion $path..retu
0850: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 rn. }.. ty
0860: 70 65 6d 65 74 68 6f 64 20 77 61 74 63 68 20 7b pemethod watch {
0870: 69 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c id} {..::variabl
0880: 65 20 6d 79 77 61 74 63 68 69 64 73 0a 09 6c 61 e mywatchids..la
0890: 70 70 65 6e 64 20 6d 79 77 61 74 63 68 69 64 73 ppend mywatchids
08a0: 20 24 69 64 0a 20 20 20 20 7d 0a 0a 20 20 20 20 $id. }..
08b0: 74 79 70 65 6d 65 74 68 6f 64 20 64 6f 74 20 7b typemethod dot {
08c0: 6c 61 62 65 6c 20 63 68 61 6e 67 65 73 65 74 73 label changesets
08d0: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
08e0: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
08f0: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
0900: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 73 ydotid 0...s
0910: 65 74 20 64 67 20 5b 53 65 74 75 70 20 24 63 68 et dg [Setup $ch
0920: 61 6e 67 65 73 65 74 73 20 30 5d 0a 09 4d 61 72 angesets 0]..Mar
0930: 6b 20 24 64 67 0a 09 24 64 67 20 64 65 73 74 72 k $dg..$dg destr
0940: 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d oy..return. }
0950: 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 .. typemethod
0960: 20 6d 61 72 6b 20 7b 67 72 61 70 68 20 73 75 66 mark {graph suf
0970: 66 69 78 20 7b 73 75 62 67 72 61 70 68 20 7b 7d fix {subgraph {}
0980: 7d 7d 20 7b 0a 09 4d 61 72 6b 20 24 67 72 61 70 }} {..Mark $grap
0990: 68 20 24 73 75 66 66 69 78 20 24 73 75 62 67 72 h $suffix $subgr
09a0: 61 70 68 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 aph..return.
09b0: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
09c0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
09d0: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a #############..
09e0: 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 72 typemethod r
09f0: 75 6e 20 7b 6c 61 62 65 6c 20 63 68 61 6e 67 65 un {label change
0a00: 73 65 74 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 setcmd} {..::var
0a10: 69 61 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 iable myat
0a20: 20 20 30 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 0..::variable
0a30: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
0a40: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
0a50: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 23 ydotid 0...#
0a60: 20 57 65 20 63 72 65 61 74 65 20 61 20 67 72 61 We create a gra
0a70: 70 68 20 6f 66 20 74 68 65 20 72 65 76 69 73 69 ph of the revisi
0a80: 6f 6e 20 63 68 61 6e 67 65 73 65 74 73 2c 20 75 on changesets, u
0a90: 73 69 6e 67 20 74 68 65 20 66 69 6c 65 0a 09 23 sing the file..#
0aa0: 20 6c 65 76 65 6c 20 64 65 70 65 6e 64 65 6e 63 level dependenc
0ab0: 69 65 73 20 74 6f 20 63 6f 6e 73 74 72 75 63 74 ies to construct
0ac0: 20 61 20 66 69 72 73 74 20 61 70 70 72 6f 78 69 a first approxi
0ad0: 6d 61 74 69 6f 6e 20 6f 66 20 74 68 65 0a 09 23 mation of the..#
0ae0: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 74 dependencies at
0af0: 20 74 68 65 20 70 72 6f 6a 65 63 74 20 6c 65 76 the project lev
0b00: 65 6c 2e 20 54 68 65 6e 20 77 65 20 6c 6f 6f 6b el. Then we look
0b10: 20 66 6f 72 20 63 79 63 6c 65 73 0a 09 23 20 69 for cycles..# i
0b20: 6e 20 74 68 61 74 20 67 72 61 70 68 20 61 6e 64 n that graph and
0b30: 20 62 72 65 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 break them....#
0b40: 20 31 2e 20 43 72 65 61 74 65 20 6e 6f 64 65 73 1. Create nodes
0b50: 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e for all relevan
0b60: 74 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 t changesets and
0b70: 20 61 20 6d 61 70 70 69 6e 67 0a 09 23 20 20 20 a mapping..#
0b80: 20 66 72 6f 6d 20 74 68 65 20 72 65 76 69 73 69 from the revisi
0b90: 6f 6e 73 20 74 6f 20 74 68 65 69 72 20 63 68 61 ons to their cha
0ba0: 6e 67 65 73 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a ngesets/nodes...
0bb0: 09 73 65 74 20 63 68 61 6e 67 65 73 65 74 73 20 .set changesets
0bc0: 5b 75 70 6c 65 76 65 6c 20 23 30 20 24 63 68 61 [uplevel #0 $cha
0bd0: 6e 67 65 73 65 74 63 6d 64 5d 0a 09 73 65 74 20 ngesetcmd]..set
0be0: 64 67 20 5b 53 65 74 75 70 20 24 63 68 61 6e 67 dg [Setup $chang
0bf0: 65 73 65 74 73 5d 0a 0a 09 23 20 33 2e 20 4c 61 esets]...# 3. La
0c00: 73 74 6c 79 20 77 65 20 69 74 65 72 61 74 65 20 stly we iterate
0c10: 74 68 65 20 67 72 61 70 68 20 74 6f 70 6f 6c 6f the graph topolo
0c20: 67 69 63 61 6c 6c 79 2e 20 57 65 20 6d 61 72 6b gically. We mark
0c30: 20 6f 66 66 0a 09 23 20 20 20 20 74 68 65 20 6e off..# the n
0c40: 6f 64 65 73 20 77 68 69 63 68 20 68 61 76 65 20 odes which have
0c50: 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 73 2c no predecessors,
0c60: 20 69 6e 20 6f 72 64 65 72 20 66 72 6f 6d 0a 09 in order from..
0c70: 23 20 20 20 20 6f 6c 64 65 73 74 20 74 6f 20 79 # oldest to y
0c80: 6f 75 6e 67 65 73 74 2c 20 73 61 76 69 6e 67 20 oungest, saving
0c90: 61 6e 64 20 72 65 6d 6f 76 69 6e 67 20 64 65 70 and removing dep
0ca0: 65 6e 64 65 6e 63 69 65 73 2e 20 49 66 0a 09 23 endencies. If..#
0cb0: 20 20 20 20 77 65 20 66 69 6e 64 20 6e 6f 20 6e we find no n
0cc0: 6f 64 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 odes without pre
0cd0: 64 65 63 65 73 73 6f 72 73 20 77 65 20 68 61 76 decessors we hav
0ce0: 65 20 61 20 63 79 63 6c 65 2c 0a 09 23 20 20 20 e a cycle,..#
0cf0: 20 61 6e 64 20 77 6f 72 6b 20 6f 6e 20 62 72 65 and work on bre
0d00: 61 6b 69 6e 67 20 69 74 2e 0a 0a 09 6c 6f 67 20 aking it....log
0d10: 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 write 3 cyclebre
0d20: 61 6b 65 72 20 7b 54 72 61 76 65 72 73 65 20 63 aker {Traverse c
0d30: 68 61 6e 67 65 73 65 74 73 7d 0a 0a 09 49 6e 69 hangesets}...Ini
0d40: 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 tializeCandidate
0d50: 73 20 24 64 67 0a 0a 09 73 65 74 20 6b 20 20 20 s $dg...set k
0d60: 30 0a 09 73 65 74 20 6d 61 78 20 5b 6c 6c 65 6e 0..set max [llen
0d70: 67 74 68 20 5b 24 64 67 20 6e 6f 64 65 73 5d 5d gth [$dg nodes]]
0d80: 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 20 ..while {1} {..
0d90: 20 20 20 77 68 69 6c 65 20 7b 5b 57 69 74 68 6f while {[Witho
0da0: 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 24 64 utPredecessor $d
0db0: 67 20 6e 5d 7d 20 7b 0a 09 09 6c 6f 67 20 70 72 g n]} {...log pr
0dc0: 6f 67 72 65 73 73 20 32 20 63 79 63 6c 65 62 72 ogress 2 cyclebr
0dd0: 65 61 6b 65 72 20 24 6b 20 24 6d 61 78 20 3b 20 eaker $k $max ;
0de0: 69 6e 63 72 20 6b 0a 09 09 4d 61 72 6b 57 61 74 incr k...MarkWat
0df0: 63 68 20 24 64 67 0a 09 09 50 72 6f 63 65 73 73 ch $dg...Process
0e00: 65 64 48 6f 6f 6b 20 24 64 67 20 24 6e 20 24 6d edHook $dg $n $m
0e10: 79 61 74 0a 09 09 24 64 67 20 6e 6f 64 65 20 64 yat...$dg node d
0e20: 65 6c 65 74 65 20 24 6e 0a 09 09 69 6e 63 72 20 elete $n...incr
0e30: 6d 79 61 74 0a 09 09 53 68 6f 77 50 65 6e 64 69 myat...ShowPendi
0e40: 6e 67 4e 6f 64 65 73 0a 09 20 20 20 20 7d 0a 0a ngNodes.. }..
0e50: 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c 65 6e 67 . if {![lleng
0e60: 74 68 20 5b 64 67 20 6e 6f 64 65 73 5d 5d 7d 20 th [dg nodes]]}
0e70: 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 72 65 61 break... Brea
0e80: 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 20 20 20 kCycleHook
0e90: 20 24 64 67 0a 09 20 20 20 20 49 6e 69 74 69 61 $dg.. Initia
0ea0: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 24 lizeCandidates $
0eb0: 64 67 0a 09 20 20 20 20 4d 61 72 6b 57 61 74 63 dg.. MarkWatc
0ec0: 68 20 20 20 20 20 20 20 20 20 20 20 20 24 64 67 h $dg
0ed0: 0a 09 7d 0a 0a 09 24 64 67 20 64 65 73 74 72 6f ..}...$dg destro
0ee0: 79 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 33 20 y...log write 3
0ef0: 63 79 63 6c 65 62 72 65 61 6b 65 72 20 44 6f 6e cyclebreaker Don
0f00: 65 2e 0a 09 43 6c 65 61 72 48 6f 6f 6b 73 0a 0a e...ClearHooks..
0f10: 09 23 20 52 65 72 65 61 64 20 74 68 65 20 67 72 .# Reread the gr
0f20: 61 70 68 20 61 6e 64 20 64 75 6d 70 20 69 74 73 aph and dump its
0f30: 20 66 69 6e 61 6c 20 66 6f 72 6d 2c 20 69 66 20 final form, if
0f40: 67 72 61 70 68 20 65 78 70 6f 72 74 0a 09 23 20 graph export..#
0f50: 77 61 73 20 61 63 74 69 76 61 74 65 64 2e 0a 0a was activated...
0f60: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f .::variable mydo
0f70: 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 69 66 tdestination..if
0f80: 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 {$mydotdestinat
0f90: 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 75 72 ion eq ""} retur
0fa0: 6e 0a 0a 09 73 65 74 20 20 20 64 67 20 5b 53 65 n...set dg [Se
0fb0: 74 75 70 20 5b 75 70 6c 65 76 65 6c 20 23 30 20 tup [uplevel #0
0fc0: 24 63 68 61 6e 67 65 73 65 74 63 6d 64 5d 20 30 $changesetcmd] 0
0fd0: 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 64 6f 6e ]..Mark $dg -don
0fe0: 65 0a 09 24 64 67 20 64 65 73 74 72 6f 79 0a 09 e..$dg destroy..
0ff0: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
1000: 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 # # ## ### ###
1010: 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 ## ######## ####
1020: 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 74 #########.. t
1030: 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 6b 2d ypemethod break-
1040: 73 65 67 6d 65 6e 74 20 7b 67 72 61 70 68 7d 20 segment {graph}
1050: 7b 0a 09 42 72 65 61 6b 53 65 67 6d 65 6e 74 20 {..BreakSegment
1060: 24 67 72 61 70 68 20 24 70 61 74 68 20 22 73 65 $graph $path "se
1070: 67 6d 65 6e 74 20 28 5b 70 72 6f 6a 65 63 74 3a gment ([project:
1080: 3a 72 65 76 20 73 74 72 6c 69 73 74 20 24 70 61 :rev strlist $pa
1090: 74 68 5d 29 22 0a 09 72 65 74 75 72 6e 0a 20 20 th])"..return.
10a0: 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 }.. typemet
10b0: 68 6f 64 20 62 72 65 61 6b 20 7b 67 72 61 70 68 hod break {graph
10c0: 7d 20 7b 0a 09 73 65 74 20 63 79 63 6c 65 20 5b } {..set cycle [
10d0: 46 69 6e 64 43 79 63 6c 65 20 24 67 72 61 70 68 FindCycle $graph
10e0: 5d 0a 09 73 65 74 20 6c 61 62 65 6c 20 22 63 79 ]..set label "cy
10f0: 63 6c 65 20 28 5b 70 72 6f 6a 65 63 74 3a 3a 72 cle ([project::r
1100: 65 76 20 73 74 72 6c 69 73 74 20 24 63 79 63 6c ev strlist $cycl
1110: 65 5d 29 22 0a 0a 09 23 20 4e 4f 54 45 3a 20 63 e])"...# NOTE: c
1120: 76 73 32 73 76 6e 20 75 73 65 73 20 74 68 65 20 vs2svn uses the
1130: 73 65 71 75 65 6e 63 65 20 22 65 6e 64 2d 31 2c sequence "end-1,
1140: 20 63 79 63 6c 65 2c 20 30 22 20 74 6f 20 63 72 cycle, 0" to cr
1150: 65 61 74 65 0a 09 23 20 20 20 20 20 20 20 74 68 eate..# th
1160: 65 20 70 61 74 68 20 66 72 6f 6d 20 74 68 65 20 e path from the
1170: 63 79 63 6c 65 2e 20 54 68 65 20 6f 6e 6c 79 20 cycle. The only
1180: 65 66 66 65 63 74 20 49 20 63 61 6e 20 73 65 65 effect I can see
1190: 20 69 73 0a 09 23 20 20 20 20 20 20 20 74 68 61 is..# tha
11a0: 74 20 74 68 69 73 20 63 61 75 73 65 73 20 74 68 t this causes th
11b0: 65 20 6c 69 6e 6b 2d 74 72 69 70 6c 65 73 20 74 e link-triples t
11c0: 6f 20 62 65 20 67 65 6e 65 72 61 74 65 64 20 69 o be generated i
11d0: 6e 20 61 0a 09 23 20 20 20 20 20 20 20 73 69 67 n a..# sig
11e0: 68 74 6c 79 20 64 69 66 66 65 72 65 6e 74 20 6f htly different o
11f0: 72 64 65 72 2c 20 69 2e 65 2e 20 6f 6e 65 20 6c rder, i.e. one l
1200: 69 6e 6b 20 72 6f 74 61 74 65 64 20 74 6f 20 74 ink rotated to t
1210: 68 65 0a 09 23 20 20 20 20 20 20 20 72 69 67 68 he..# righ
1220: 74 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 20 68 t. This should h
1230: 61 76 65 20 6e 6f 20 65 66 66 65 63 74 20 6f 6e ave no effect on
1240: 20 74 68 65 20 73 65 61 72 63 68 20 66 6f 72 0a the search for.
1250: 09 23 20 20 20 20 20 20 20 74 68 65 20 62 65 73 .# the bes
1260: 74 20 6f 66 20 61 6c 6c 2e 0a 0a 09 6c 61 70 70 t of all....lapp
1270: 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 6e 64 65 end cycle [linde
1280: 78 20 24 63 79 63 6c 65 20 30 5d 20 5b 6c 69 6e x $cycle 0] [lin
1290: 64 65 78 20 24 63 79 63 6c 65 20 31 5d 0a 09 42 dex $cycle 1]..B
12a0: 72 65 61 6b 53 65 67 6d 65 6e 74 20 24 67 72 61 reakSegment $gra
12b0: 70 68 20 24 63 79 63 6c 65 20 24 6c 61 62 65 6c ph $cycle $label
12c0: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
12d0: 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 72 typemethod r
12e0: 65 70 6c 61 63 65 20 7b 67 72 61 70 68 20 6e 20 eplace {graph n
12f0: 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b 0a replacements} {.
1300: 09 52 65 70 6c 61 63 65 20 24 67 72 61 70 68 20 .Replace $graph
1310: 24 6e 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 73 $n $replacements
1320: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
1330: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
1340: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
1350: 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 20 ###########.
1360: 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d 65 74 68 ## Internal meth
1370: 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 20 53 65 ods.. proc Se
1380: 74 75 70 20 7b 63 68 61 6e 67 65 73 65 74 73 20 tup {changesets
1390: 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 66 20 7b {log 1}} {..if {
13a0: 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 $log} {.. log
13b0: 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 write 3 cyclebr
13c0: 65 61 6b 65 72 20 22 43 72 65 61 74 69 6e 67 20 eaker "Creating
13d0: 67 72 61 70 68 20 6f 66 20 63 68 61 6e 67 65 73 graph of changes
13e0: 65 74 73 22 0a 09 7d 0a 0a 09 73 65 74 20 64 67 ets"..}...set dg
13f0: 20 5b 73 74 72 75 63 74 3a 3a 67 72 61 70 68 20 [struct::graph
1400: 64 67 5d 0a 0a 09 73 65 74 20 6e 20 30 0a 09 73 dg]...set n 0..s
1410: 65 74 20 6d 61 78 20 5b 6c 6c 65 6e 67 74 68 20 et max [llength
1420: 24 63 68 61 6e 67 65 73 65 74 73 5d 0a 0a 09 66 $changesets]...f
1430: 6f 72 65 61 63 68 20 63 73 65 74 20 24 63 68 61 oreach cset $cha
1440: 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 20 20 6c ngesets {.. l
1450: 6f 67 20 70 72 6f 67 72 65 73 73 20 32 20 63 79 og progress 2 cy
1460: 63 6c 65 62 72 65 61 6b 65 72 20 24 6e 20 24 6d clebreaker $n $m
1470: 61 78 0a 09 20 20 20 20 73 65 74 20 74 72 20 5b ax.. set tr [
1480: 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d $cset timerange]
1490: 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 69 .. $dg node i
14a0: 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 20 nsert $cset..
14b0: 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 $dg node set
14c0: 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 $cset timerange
14d0: 20 24 74 72 0a 09 20 20 20 20 24 64 67 20 6e 6f $tr.. $dg no
14e0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
14f0: 6c 61 62 65 6c 20 20 20 20 20 22 5b 24 63 73 65 label "[$cse
1500: 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e 20 5b t str]\\n[join [
1510: 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d 61 70 struct::list map
1520: 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 66 6f $tr {::clock fo
1530: 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 0a 09 rmat}] "\\n"]"..
1540: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
1550: 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f 5f $cset __id__
1560: 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a 09 [$cset id]..
1570: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
1580: 20 20 20 20 24 63 73 65 74 20 73 68 61 70 65 20 $cset shape
1590: 20 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 73 65 [expr {[$cse
15a0: 74 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 09 09 t bysymbol].....
15b0: 09 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 65 22 .. ? "ellipse"
15c0: 0a 09 09 09 09 09 09 20 20 20 3a 20 22 62 6f 78 ....... : "box
15d0: 22 7d 5d 0a 09 20 20 20 20 69 6e 63 72 20 6e 0a "}].. incr n.
15e0: 09 7d 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b .}...if {$log} {
15f0: 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 .. log write
1600: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 3 cyclebreaker "
1610: 48 61 73 20 5b 6e 73 70 20 5b 6c 6c 65 6e 67 74 Has [nsp [llengt
1620: 68 20 24 63 68 61 6e 67 65 73 65 74 73 5d 20 63 h $changesets] c
1630: 68 61 6e 67 65 73 65 74 5d 22 0a 09 7d 0a 0a 09 hangeset]"..}...
1640: 23 20 32 2e 20 46 69 6e 64 20 66 6f 72 20 61 6c # 2. Find for al
1650: 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e 67 l relevant chang
1660: 65 73 65 74 20 74 68 65 69 72 20 72 65 76 69 73 eset their revis
1670: 69 6f 6e 73 20 61 6e 64 20 74 68 65 69 72 0a 09 ions and their..
1680: 23 20 20 20 20 64 65 70 65 6e 64 65 6e 63 69 65 # dependencie
1690: 73 2e 20 4d 61 70 20 74 68 65 20 6c 61 74 74 65 s. Map the latte
16a0: 72 20 62 61 63 6b 20 74 6f 20 63 68 61 6e 67 65 r back to change
16b0: 73 65 74 73 20 61 6e 64 0a 09 23 20 20 20 20 63 sets and..# c
16c0: 6f 6e 73 74 72 75 63 74 20 74 68 65 20 63 6f 72 onstruct the cor
16d0: 72 65 73 70 6f 6e 64 69 6e 67 20 61 72 63 73 2e responding arcs.
16e0: 0a 0a 09 73 65 74 20 6e 20 30 0a 09 66 6f 72 65 ...set n 0..fore
16f0: 61 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 ach cset $change
1700: 73 65 74 73 20 7b 0a 09 20 20 20 20 6c 6f 67 20 sets {.. log
1710: 70 72 6f 67 72 65 73 73 20 32 20 63 79 63 6c 65 progress 2 cycle
1720: 62 72 65 61 6b 65 72 20 24 6e 20 24 6d 61 78 0a breaker $n $max.
1730: 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 . foreach suc
1740: 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 c [$cset success
1750: 6f 72 73 5d 20 7b 0a 09 09 23 20 43 68 61 6e 67 ors] {...# Chang
1760: 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 esets may have d
1770: 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 ependencies outs
1780: 69 64 65 20 6f 66 20 74 68 65 0a 09 09 23 20 63 ide of the...# c
1790: 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 hosen set. These
17a0: 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 are ignored...i
17b0: 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 f {![$dg node ex
17c0: 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e ists $succ]} con
17d0: 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 tinue...$dg arc
17e0: 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 insert $cset $su
17f0: 63 63 0a 09 09 69 6e 74 65 67 72 69 74 79 20 61 cc...integrity a
1800: 73 73 65 72 74 20 7b 0a 09 09 20 20 20 20 24 73 ssert {... $s
1810: 75 63 63 20 6e 65 20 24 63 73 65 74 0a 09 09 7d ucc ne $cset...}
1820: 20 7b 5b 24 63 73 65 74 20 72 65 70 6f 72 74 6c {[$cset reportl
1830: 6f 6f 70 20 30 5d 43 68 61 6e 67 65 73 65 74 20 oop 0]Changeset
1840: 6c 6f 6f 70 20 77 61 73 20 6e 6f 74 20 64 65 74 loop was not det
1850: 65 63 74 65 64 20 64 75 72 69 6e 67 20 63 72 65 ected during cre
1860: 61 74 69 6f 6e 7d 0a 09 20 20 20 20 7d 0a 09 20 ation}.. }..
1870: 20 20 20 69 6e 63 72 20 6e 0a 09 7d 0a 0a 09 69 incr n..}...i
1880: 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 f {$log} {..
1890: 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 6c log write 3 cycl
18a0: 65 62 72 65 61 6b 65 72 20 22 48 61 73 20 5b 6e ebreaker "Has [n
18b0: 73 70 20 5b 6c 6c 65 6e 67 74 68 20 5b 24 64 67 sp [llength [$dg
18c0: 20 61 72 63 73 5d 5d 20 64 65 70 65 6e 64 65 6e arcs]] dependen
18d0: 63 79 20 64 65 70 65 6e 64 65 6e 63 69 65 73 5d cy dependencies]
18e0: 22 0a 09 7d 0a 0a 09 23 20 52 75 6e 20 74 68 65 "..}...# Run the
18f0: 20 75 73 65 72 20 68 6f 6f 6b 20 74 6f 20 6d 61 user hook to ma
1900: 6e 69 70 75 6c 61 74 65 20 74 68 65 20 67 72 61 nipulate the gra
1910: 70 68 20 62 65 66 6f 72 65 0a 09 23 20 63 6f 6e ph before..# con
1920: 73 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 69 66 20 summation....if
1930: 7b 24 6c 6f 67 7d 20 7b 20 4d 61 72 6b 20 24 64 {$log} { Mark $d
1940: 67 20 2d 73 74 61 72 74 20 7d 0a 09 4d 61 72 6b g -start }..Mark
1950: 57 61 74 63 68 20 24 64 67 0a 09 50 72 65 48 6f Watch $dg..PreHo
1960: 6f 6b 20 20 20 24 64 67 0a 09 4d 61 72 6b 57 61 ok $dg..MarkWa
1970: 74 63 68 20 24 64 67 0a 09 72 65 74 75 72 6e 20 tch $dg..return
1980: 20 24 64 67 0a 20 20 20 20 7d 0a 0a 20 20 20 20 $dg. }..
1990: 23 20 49 6e 73 74 65 61 64 20 6f 66 20 73 65 61 # Instead of sea
19a0: 72 63 68 69 6e 67 20 74 68 65 20 77 68 6f 6c 65 rching the whole
19b0: 20 67 72 61 70 68 20 66 6f 72 20 74 68 65 20 64 graph for the d
19c0: 65 67 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 6e egree-0 nodes in
19d0: 0a 20 20 20 20 23 20 65 61 63 68 20 69 74 65 72 . # each iter
19e0: 61 74 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 65 ation we compute
19f0: 20 74 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 74 the list once t
1a00: 6f 20 73 74 61 72 74 2c 20 61 6e 64 20 74 68 65 o start, and the
1a10: 6e 20 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 64 n only. # upd
1a20: 61 74 65 20 69 74 20 69 6e 63 72 65 6d 65 6e 74 ate it increment
1a30: 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 68 ally based on th
1a40: 65 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 68 e outgoing neigh
1a50: 62 6f 75 72 73 20 6f 66 20 74 68 65 0a 20 20 20 bours of the.
1a60: 20 23 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 66 # node chosen f
1a70: 6f 72 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 20 or commit...
1a80: 70 72 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 43 proc InitializeC
1a90: 61 6e 64 69 64 61 74 65 73 20 7b 64 67 7d 20 7b andidates {dg} {
1aa0: 0a 09 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 73 ..# bottom = lis
1ab0: 74 20 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 72 t (list (node, r
1ac0: 61 6e 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 20 ange min, range
1ad0: 6d 61 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 6c max))..::variabl
1ae0: 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 66 6f 72 65 e mybottom..fore
1af0: 61 63 68 20 6e 20 5b 24 64 67 20 6e 6f 64 65 73 ach n [$dg nodes
1b00: 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 64 ] {.. if {[$d
1b10: 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d 69 g node degree -i
1b20: 6e 20 24 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a n $n]} continue.
1b30: 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 . lappend myb
1b40: 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b ottom [linsert [
1b50: 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6e 20 $dg node get $n
1b60: 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6e 5d timerange] 0 $n]
1b70: 0a 09 7d 0a 09 53 63 68 65 64 75 6c 65 43 61 6e ..}..ScheduleCan
1b80: 64 69 64 61 74 65 73 0a 09 53 68 6f 77 50 65 6e didates..ShowPen
1b90: 64 69 6e 67 4e 6f 64 65 73 0a 09 72 65 74 75 72 dingNodes..retur
1ba0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
1bb0: 63 20 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 c WithoutPredece
1bc0: 73 73 6f 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 ssor {dg nv} {..
1bd0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 ::variable mybot
1be0: 74 6f 6d 0a 0a 09 75 70 76 61 72 20 31 20 24 6e tom...upvar 1 $n
1bf0: 76 20 6e 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 v n..if {![lleng
1c00: 74 68 20 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b th $mybottom]} {
1c10: 20 72 65 74 75 72 6e 20 30 20 7d 0a 0a 09 73 65 return 0 }...se
1c20: 74 20 6e 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e t n [lindex [lin
1c30: 64 65 78 20 24 6d 79 62 6f 74 74 6f 6d 20 30 5d dex $mybottom 0]
1c40: 20 30 5d 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 0]..set mybotto
1c50: 6d 20 5b 6c 72 61 6e 67 65 20 24 6d 79 62 6f 74 m [lrange $mybot
1c60: 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 65 74 20 tom 1 end]..set
1c70: 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 20 55 70 changed 0...# Up
1c80: 64 61 74 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64 date list of nod
1c90: 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 es without prede
1ca0: 63 65 73 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e cessor, based on
1cb0: 20 74 68 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67 the..# outgoing
1cc0: 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74 neighbours of t
1cd0: 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 he chosen node.
1ce0: 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 0a 09 This should be..
1cf0: 23 20 66 61 73 74 65 72 20 74 68 61 6e 20 69 74 # faster than it
1d00: 65 72 61 74 69 6e 67 20 6f 66 20 74 68 65 20 77 erating of the w
1d10: 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e 6f 64 65 hole set of node
1d20: 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 s, finding all..
1d30: 23 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 # without predec
1d40: 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20 essors, sorting
1d50: 74 68 65 6d 20 62 79 20 74 69 6d 65 2c 20 65 74 them by time, et
1d60: 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 63 68 20 c. pp...foreach
1d70: 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d out [$dg nodes -
1d80: 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69 out $n] {.. i
1d90: 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 f {[$dg node deg
1da0: 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 ree -in $out] >
1db0: 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 1} continue..
1dc0: 20 23 20 44 65 67 72 65 65 2d 31 20 6e 65 69 67 # Degree-1 neig
1dd0: 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 61 76 65 hbour, will have
1de0: 20 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 73 no predecessors
1df0: 20 61 66 74 65 72 20 74 68 65 0a 09 20 20 20 20 after the..
1e00: 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 # removal of n.
1e10: 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e Put on the list.
1e20: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 .. lappend my
1e30: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
1e40: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6f [$dg node get $o
1e50: 75 74 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 ut timerange] 0
1e60: 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 74 20 63 $out].. set c
1e70: 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 hanged 1..}..if
1e80: 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 {$changed} {..
1e90: 20 20 53 63 68 65 64 75 6c 65 43 61 6e 64 69 64 ScheduleCandid
1ea0: 61 74 65 73 0a 09 7d 0a 0a 09 23 20 57 65 20 64 ates..}...# We d
1eb0: 6f 20 6e 6f 74 20 64 65 6c 65 74 65 20 74 68 65 o not delete the
1ec0: 20 6e 6f 64 65 20 69 6d 6d 65 64 69 61 74 65 6c node immediatel
1ed0: 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 68 65 20 y, to allow the
1ee0: 53 61 76 65 0a 09 23 20 70 72 6f 63 65 64 75 72 Save..# procedur
1ef0: 65 20 74 6f 20 73 61 76 65 20 74 68 65 20 64 65 e to save the de
1f00: 70 65 6e 64 65 6e 63 69 65 73 20 61 73 20 77 65 pendencies as we
1f10: 6c 6c 20 28 65 6e 63 6f 64 65 64 20 69 6e 20 74 ll (encoded in t
1f20: 68 65 0a 09 23 20 61 72 63 73 29 2e 0a 09 72 65 he..# arcs)...re
1f30: 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 turn 1. }..
1f40: 20 20 70 72 6f 63 20 53 63 68 65 64 75 6c 65 43 proc ScheduleC
1f50: 61 6e 64 69 64 61 74 65 73 20 7b 7d 20 7b 0a 09 andidates {} {..
1f60: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 ::variable mybot
1f70: 74 6f 6d 0a 09 23 20 53 6f 72 74 20 62 79 20 63 tom..# Sort by c
1f80: 73 65 74 20 6f 62 6a 65 63 74 20 6e 61 6d 65 2c set object name,
1f90: 20 6c 6f 77 65 72 20 62 6f 72 64 65 72 20 6f 66 lower border of
1fa0: 20 74 69 6d 65 72 61 6e 67 65 2c 20 61 74 20 6c timerange, at l
1fb0: 61 73 74 0a 09 23 20 62 79 20 74 68 65 20 75 70 ast..# by the up
1fc0: 70 65 72 20 62 6f 72 64 65 72 2e 0a 09 73 65 74 per border...set
1fd0: 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 mybottom [lsort
1fe0: 20 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 67 -index 2 -integ
1ff0: 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 er [lsort -index
2000: 20 31 20 2d 69 6e 74 65 67 65 72 20 5b 6c 73 6f 1 -integer [lso
2010: 72 74 20 2d 69 6e 64 65 78 20 30 20 2d 64 69 63 rt -index 0 -dic
2020: 74 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d 5d 0a 09 t $mybottom]]]..
2030: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
2040: 20 20 70 72 6f 63 20 53 68 6f 77 50 65 6e 64 69 proc ShowPendi
2050: 6e 67 4e 6f 64 65 73 20 7b 7d 20 7b 0a 09 69 66 ngNodes {} {..if
2060: 20 7b 5b 6c 6f 67 20 76 65 72 62 6f 73 69 74 79 {[log verbosity
2070: 3f 5d 20 3c 20 31 30 7d 20 72 65 74 75 72 6e 0a ?] < 10} return.
2080: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f .::variable mybo
2090: 74 74 6f 6d 0a 09 6c 6f 67 20 77 72 69 74 65 20 ttom..log write
20a0: 31 30 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 10 cyclebreaker
20b0: 22 50 65 6e 64 69 6e 67 2e 2e 2e 2e 2e 2e 2e 2e "Pending........
20c0: 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e 2e ................
20d0: 2e 2e 2e 2e 2e 2e 2e 22 0a 09 66 6f 72 65 61 63 ......."..foreac
20e0: 68 20 69 74 65 6d 20 5b 73 74 72 75 63 74 3a 3a h item [struct::
20f0: 6c 69 73 74 20 6d 61 70 20 24 6d 79 62 6f 74 74 list map $mybott
2100: 6f 6d 20 5b 6d 79 70 72 6f 63 20 46 6f 72 6d 61 om [myproc Forma
2110: 74 50 65 6e 64 69 6e 67 49 74 65 6d 5d 5d 20 7b tPendingItem]] {
2120: 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 .. log write
2130: 31 30 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 10 cyclebreaker
2140: 22 50 65 6e 64 69 6e 67 3a 20 20 20 20 20 24 69 "Pending: $i
2150: 74 65 6d 22 0a 09 7d 0a 09 72 65 74 75 72 6e 0a tem"..}..return.
2160: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
2170: 46 6f 72 6d 61 74 50 65 6e 64 69 6e 67 49 74 65 FormatPendingIte
2180: 6d 20 7b 69 74 65 6d 7d 20 7b 0a 09 6a 6f 69 6e m {item} {..join
2190: 20 5b 6c 69 73 74 20 5b 5b 6c 69 6e 64 65 78 20 [list [[lindex
21a0: 24 69 74 65 6d 20 30 5d 20 73 74 72 5d 20 5b 63 $item 0] str] [c
21b0: 6c 6f 63 6b 20 66 6f 72 6d 61 74 20 5b 6c 69 6e lock format [lin
21c0: 64 65 78 20 24 69 74 65 6d 20 31 5d 5d 20 5b 63 dex $item 1]] [c
21d0: 6c 6f 63 6b 20 66 6f 72 6d 61 74 20 5b 6c 69 6e lock format [lin
21e0: 64 65 78 20 24 69 74 65 6d 20 32 5d 5d 5d 0a 20 dex $item 2]]].
21f0: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 46 }.. proc F
2200: 69 6e 64 43 79 63 6c 65 20 7b 64 67 7d 20 7b 0a indCycle {dg} {.
2210: 09 23 20 54 68 69 73 20 70 72 6f 63 65 64 75 72 .# This procedur
2220: 65 20 69 73 20 72 75 6e 20 69 66 20 61 6e 64 20 e is run if and
2230: 6f 6e 6c 79 20 74 68 65 20 67 72 61 70 68 20 69 only the graph i
2240: 73 20 6e 6f 74 20 65 6d 70 74 79 20 61 6e 64 0a s not empty and.
2250: 09 23 20 61 6c 6c 20 6e 6f 64 65 73 20 68 61 76 .# all nodes hav
2260: 65 20 70 72 65 64 65 63 65 73 73 6f 72 73 2e 20 e predecessors.
2270: 54 68 69 73 20 6d 65 61 6e 73 20 74 68 61 74 20 This means that
2280: 65 61 63 68 20 6e 6f 64 65 20 69 73 0a 09 23 20 each node is..#
2290: 65 69 74 68 65 72 20 70 61 72 74 20 6f 66 20 61 either part of a
22a0: 20 63 79 63 6c 65 20 6f 72 20 28 69 6e 64 69 72 cycle or (indir
22b0: 65 63 74 6c 79 29 20 64 65 70 65 6e 64 69 6e 67 ectly) depending
22c0: 20 6f 6e 20 61 20 6e 6f 64 65 0a 09 23 20 69 6e on a node..# in
22d0: 20 61 20 63 79 63 6c 65 2e 20 57 65 20 63 61 6e a cycle. We can
22e0: 20 73 74 61 72 74 20 61 74 20 61 6e 20 61 72 62 start at an arb
22f0: 69 74 72 61 72 79 20 6e 6f 64 65 2c 20 66 6f 6c itrary node, fol
2300: 6c 6f 77 20 69 74 73 0a 09 23 20 69 6e 63 6f 6d low its..# incom
2310: 69 6e 67 20 65 64 67 65 73 20 74 6f 20 69 74 73 ing edges to its
2320: 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 75 6e predecessors un
2330: 74 69 6c 20 77 65 20 73 65 65 20 61 20 6e 6f 64 til we see a nod
2340: 65 20 61 0a 09 23 20 73 65 63 6f 6e 64 20 74 69 e a..# second ti
2350: 6d 65 2e 20 54 68 61 74 20 6e 6f 64 65 20 63 6c me. That node cl
2360: 6f 73 65 73 20 74 68 65 20 63 79 63 6c 65 20 61 oses the cycle a
2370: 6e 64 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 nd the beginning
2380: 20 69 73 0a 09 23 20 69 74 73 20 66 69 72 73 74 is..# its first
2390: 20 6f 63 63 75 72 65 6e 63 65 2e 20 4e 6f 74 65 occurence. Note
23a0: 20 74 68 61 74 20 77 65 20 63 61 6e 20 63 68 6f that we can cho
23b0: 6f 73 65 20 61 6e 20 61 72 62 69 74 72 61 72 79 ose an arbitrary
23c0: 0a 09 23 20 70 72 65 64 65 63 65 73 73 6f 72 20 ..# predecessor
23d0: 6f 66 20 65 61 63 68 20 6e 6f 64 65 20 61 73 20 of each node as
23e0: 77 65 6c 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 20 well, we do not
23f0: 68 61 76 65 20 74 6f 20 73 65 61 72 63 68 2e 0a have to search..
2400: 0a 09 23 20 57 65 20 72 65 63 6f 72 64 20 66 6f ..# We record fo
2410: 72 20 65 61 63 68 20 6e 6f 64 65 20 74 68 65 20 r each node the
2420: 69 6e 64 65 78 20 6f 66 20 74 68 65 20 66 69 72 index of the fir
2430: 73 74 20 61 70 70 65 61 72 61 6e 63 65 20 69 6e st appearance in
2440: 0a 09 23 20 74 68 65 20 70 61 74 68 2c 20 6d 61 ..# the path, ma
2450: 6b 69 6e 67 20 69 74 20 65 61 73 79 20 61 74 20 king it easy at
2460: 74 68 65 20 65 6e 64 20 74 6f 20 63 75 74 20 74 the end to cut t
2470: 68 65 20 63 79 63 6c 65 20 66 72 6f 6d 0a 09 23 he cycle from..#
2480: 20 69 74 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 20 it....# Choose
2490: 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65 20 74 arbitrary node t
24a0: 6f 20 73 74 61 72 74 20 6f 75 72 20 73 65 61 72 o start our sear
24b0: 63 68 20 61 74 2e 0a 09 73 65 74 20 73 74 61 72 ch at...set star
24c0: 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e t [lindex [$dg n
24d0: 6f 64 65 73 5d 20 30 5d 0a 0a 09 23 20 49 6e 69 odes] 0]...# Ini
24e0: 74 69 61 6c 69 7a 65 20 73 74 61 74 65 2c 20 70 tialize state, p
24f0: 61 74 68 20 6f 66 20 73 65 65 6e 20 6e 6f 64 65 ath of seen node
2500: 73 2c 20 61 6e 64 20 77 68 65 6e 20 73 65 65 6e s, and when seen
2510: 2e 0a 09 73 65 74 20 20 20 20 20 20 20 70 61 74 ...set pat
2520: 68 20 7b 7d 0a 09 61 72 72 61 79 20 73 65 74 20 h {}..array set
2530: 73 65 65 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 20 seen {}...while
2540: 7b 31 7d 20 7b 0a 09 20 20 20 20 23 20 53 74 6f {1} {.. # Sto
2550: 70 20 73 65 61 72 63 68 69 6e 67 20 77 68 65 6e p searching when
2560: 20 77 65 20 68 61 76 65 20 73 65 65 6e 20 74 68 we have seen th
2570: 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 0a 09 e current node..
2580: 20 20 20 20 23 20 61 6c 72 65 61 64 79 2c 20 74 # already, t
2590: 68 65 20 63 69 72 63 6c 65 20 68 61 73 20 62 65 he circle has be
25a0: 65 6e 20 63 6c 6f 73 65 64 2e 0a 09 20 20 20 20 en closed...
25b0: 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73 if {[info exists
25c0: 20 73 65 65 6e 28 24 73 74 61 72 74 29 5d 7d 20 seen($start)]}
25d0: 62 72 65 61 6b 0a 09 20 20 20 20 6c 61 70 70 65 break.. lappe
25e0: 6e 64 20 70 61 74 68 20 24 73 74 61 72 74 0a 09 nd path $start..
25f0: 20 20 20 20 73 65 74 20 73 65 65 6e 28 24 73 74 set seen($st
2600: 61 72 74 29 20 5b 65 78 70 72 20 7b 5b 6c 6c 65 art) [expr {[lle
2610: 6e 67 74 68 20 24 70 61 74 68 5d 2d 31 7d 5d 0a ngth $path]-1}].
2620: 09 20 20 20 20 23 20 43 68 6f 6f 73 65 20 61 72 . # Choose ar
2630: 62 69 74 72 61 72 79 20 70 72 65 64 65 63 65 73 bitrary predeces
2640: 73 6f 72 0a 09 20 20 20 20 73 65 74 20 73 74 61 sor.. set sta
2650: 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 rt [lindex [$dg
2660: 6e 6f 64 65 73 20 2d 69 6e 20 24 73 74 61 72 74 nodes -in $start
2670: 5d 20 30 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e ] 0]..}...return
2680: 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 72 [struct::list r
2690: 65 76 65 72 73 65 20 5b 6c 72 61 6e 67 65 20 24 everse [lrange $
26a0: 70 61 74 68 20 24 73 65 65 6e 28 24 73 74 61 72 path $seen($star
26b0: 74 29 20 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a 0a t) end]]. }..
26c0: 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 53 65 proc BreakSe
26d0: 67 6d 65 6e 74 20 7b 64 67 20 70 61 74 68 20 6c gment {dg path l
26e0: 61 62 65 6c 7d 20 7b 0a 09 23 20 54 68 65 20 70 abel} {..# The p
26f0: 61 74 68 2c 20 75 73 75 61 6c 6c 79 20 61 20 63 ath, usually a c
2700: 79 63 6c 65 2c 20 77 65 20 68 61 76 65 20 67 6f ycle, we have go
2710: 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 6e 20 62 tten is broken b
2720: 79 0a 09 23 20 62 72 65 61 6b 69 6e 67 20 61 70 y..# breaking ap
2730: 61 72 74 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 20 art one or more
2740: 6f 66 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 of the changeset
2750: 73 20 69 6e 20 74 68 65 0a 09 23 20 63 79 63 6c s in the..# cycl
2760: 65 2e 20 54 68 69 73 20 63 61 75 73 65 73 20 75 e. This causes u
2770: 73 20 74 6f 20 63 72 65 61 74 65 20 6f 6e 65 20 s to create one
2780: 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 65 73 65 or more changese
2790: 74 73 20 77 68 69 63 68 0a 09 23 20 61 72 65 20 ts which..# are
27a0: 74 6f 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c to be committed,
27b0: 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 67 72 added to the gr
27c0: 61 70 68 2c 20 65 74 63 2e 20 70 70 2e 0a 0a 09 aph, etc. pp....
27d0: 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 7b 7d 0a set bestlink {}.
27e0: 09 73 65 74 20 62 65 73 74 6e 6f 64 65 20 7b 7d .set bestnode {}
27f0: 0a 0a 09 66 6f 72 65 61 63 68 20 5c 0a 09 20 20 ...foreach \..
2800: 20 20 70 72 65 76 20 5b 6c 72 61 6e 67 65 20 24 prev [lrange $
2810: 70 61 74 68 20 30 20 65 6e 64 2d 32 5d 20 5c 0a path 0 end-2] \.
2820: 09 20 20 20 20 63 73 65 74 20 5b 6c 72 61 6e 67 . cset [lrang
2830: 65 20 24 70 61 74 68 20 31 20 65 6e 64 2d 31 5d e $path 1 end-1]
2840: 20 5c 0a 09 20 20 20 20 6e 65 78 74 20 5b 6c 72 \.. next [lr
2850: 61 6e 67 65 20 24 70 61 74 68 20 32 20 65 6e 64 ange $path 2 end
2860: 5d 20 7b 0a 0a 09 09 23 20 45 61 63 68 20 74 72 ] {....# Each tr
2870: 69 70 6c 65 20 50 52 45 56 20 2d 3e 20 43 53 45 iple PREV -> CSE
2880: 54 20 2d 3e 20 4e 45 58 54 20 6f 66 20 63 68 61 T -> NEXT of cha
2890: 6e 67 65 73 65 74 73 2c 20 61 0a 09 09 23 20 27 ngesets, a...# '
28a0: 6c 69 6e 6b 27 20 69 6e 20 74 68 65 20 63 79 63 link' in the cyc
28b0: 6c 65 2c 20 69 73 20 61 6e 61 6c 79 73 65 64 20 le, is analysed
28c0: 61 6e 64 20 74 68 65 20 62 65 73 74 0a 09 09 23 and the best...#
28d0: 20 6c 6f 63 61 74 69 6f 6e 20 77 68 65 72 65 20 location where
28e0: 74 6f 20 61 74 20 6c 65 61 73 74 20 77 65 61 6b to at least weak
28f0: 65 6e 20 74 68 65 20 63 79 63 6c 65 20 69 73 0a en the cycle is.
2900: 09 09 23 20 63 68 6f 73 65 6e 20 66 6f 72 20 66 ..# chosen for f
2910: 75 72 74 68 65 72 20 70 72 6f 63 65 73 73 69 6e urther processin
2920: 67 2e 0a 0a 09 09 73 65 74 20 6c 69 6e 6b 20 5b g.....set link [
2930: 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e 6b project::revlink
2940: 20 25 41 55 54 4f 25 20 24 70 72 65 76 20 24 63 %AUTO% $prev $c
2950: 73 65 74 20 24 6e 65 78 74 5d 0a 09 09 69 66 20 set $next]...if
2960: 7b 24 62 65 73 74 6c 69 6e 6b 20 65 71 20 22 22 {$bestlink eq ""
2970: 7d 20 7b 0a 09 09 20 20 20 20 73 65 74 20 62 65 } {... set be
2980: 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 stlink $link...
2990: 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 20 set bestnode
29a0: 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 69 66 $cset...} elseif
29b0: 20 7b 5b 24 6c 69 6e 6b 20 62 65 74 74 65 72 74 {[$link bettert
29c0: 68 61 6e 20 24 62 65 73 74 6c 69 6e 6b 5d 7d 20 han $bestlink]}
29d0: 7b 0a 09 09 20 20 20 20 24 62 65 73 74 6c 69 6e {... $bestlin
29e0: 6b 20 64 65 73 74 72 6f 79 0a 09 09 20 20 20 20 k destroy...
29f0: 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c 69 set bestlink $li
2a00: 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 nk... set bes
2a10: 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d 20 tnode $cset...}
2a20: 65 6c 73 65 20 7b 0a 09 09 20 20 20 20 24 6c 69 else {... $li
2a30: 6e 6b 20 64 65 73 74 72 6f 79 0a 09 09 7d 0a 09 nk destroy...}..
2a40: 20 20 20 20 7d 0a 0a 09 6c 6f 67 20 77 72 69 74 }...log writ
2a50: 65 20 35 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 5 cyclebreaker
2a60: 20 22 42 72 65 61 6b 69 6e 67 20 24 6c 61 62 65 "Breaking $labe
2a70: 6c 20 62 79 20 73 70 6c 69 74 74 69 6e 67 20 63 l by splitting c
2a80: 68 61 6e 67 65 73 65 74 20 5b 24 62 65 73 74 6e hangeset [$bestn
2a90: 6f 64 65 20 73 74 72 5d 22 0a 09 73 65 74 20 49 ode str]"..set I
2aa0: 44 20 5b 24 62 65 73 74 6e 6f 64 65 20 69 64 5d D [$bestnode id]
2ab0: 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 ..Mark $dg -${ID
2ac0: 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 65 74 20 6e }-before...set n
2ad0: 65 77 63 73 65 74 73 20 5b 24 62 65 73 74 6c 69 ewcsets [$bestli
2ae0: 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 74 nk break]..$best
2af0: 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 20 link destroy..
2b00: 20 20 20 20 20 20 23 20 41 74 20 74 68 69 73 20 # At this
2b10: 70 6f 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 68 point the old ch
2b20: 61 6e 67 65 73 65 74 20 28 42 45 53 54 4e 4f 44 angeset (BESTNOD
2b30: 45 29 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 20 E) is gone.
2b40: 20 20 20 23 20 61 6c 72 65 61 64 79 2e 20 57 65 # already. We
2b50: 20 72 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d 20 remove it from
2b60: 74 68 65 20 67 72 61 70 68 20 61 73 20 77 65 6c the graph as wel
2b70: 6c 20 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 72 l and then enter
2b80: 0a 20 20 20 20 20 20 20 20 23 20 74 68 65 20 66 . # the f
2b90: 72 61 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 74 ragments generat
2ba0: 65 64 20 66 6f 72 20 69 74 2e 0a 0a 09 52 65 70 ed for it....Rep
2bb0: 6c 61 63 65 20 24 64 67 20 24 62 65 73 74 6e 6f lace $dg $bestno
2bc0: 64 65 20 24 6e 65 77 63 73 65 74 73 0a 0a 09 4d de $newcsets...M
2bd0: 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d 61 ark $dg -${ID}-a
2be0: 66 74 65 72 0a 09 72 65 74 75 72 6e 0a 20 20 20 fter..return.
2bf0: 20 7d 0a 0a 20 20 20 20 23 20 54 4f 44 4f 3a 20 }.. # TODO:
2c00: 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 20 61 This should be a
2c10: 20 67 72 61 70 68 20 6d 65 74 68 6f 64 2e 0a 20 graph method..
2c20: 20 20 20 70 72 6f 63 20 48 61 73 41 72 63 20 7b proc HasArc {
2c30: 64 67 20 61 20 62 7d 20 7b 0a 09 23 38 2e 35 3a dg a b} {..#8.5:
2c40: 20 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b 24 return [expr {$
2c50: 62 20 69 6e 20 5b 24 64 67 20 6e 6f 64 65 73 20 b in [$dg nodes
2c60: 2d 6f 75 74 20 24 61 5d 7d 5d 0a 09 69 66 20 7b -out $a]}]..if {
2c70: 5b 6c 73 65 61 72 63 68 20 2d 65 78 61 63 74 20 [lsearch -exact
2c80: 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 [$dg nodes -out
2c90: 24 61 5d 20 24 62 5d 20 3c 20 30 7d 20 7b 20 72 $a] $b] < 0} { r
2ca0: 65 74 75 72 6e 20 30 20 7d 0a 09 72 65 74 75 72 eturn 0 }..retur
2cb0: 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 n 1. }.. p
2cc0: 72 6f 63 20 4d 61 72 6b 20 7b 64 67 20 7b 73 75 roc Mark {dg {su
2cd0: 66 66 69 78 20 7b 7d 7d 20 7b 73 75 62 67 72 61 ffix {}} {subgra
2ce0: 70 68 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 72 ph {}}} {..::var
2cf0: 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 iable mydotdesti
2d00: 6e 61 74 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 nation..if {$myd
2d10: 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 65 71 otdestination eq
2d20: 20 22 22 7d 20 72 65 74 75 72 6e 0a 09 3a 3a 76 ""} return..::v
2d30: 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 ariable mydotpre
2d40: 66 69 78 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 fix..::variable
2d50: 6d 79 64 6f 74 69 64 0a 09 73 65 74 20 66 6e 61 mydotid..set fna
2d60: 6d 65 20 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 me $mydotdestina
2d70: 74 69 6f 6e 2f 24 7b 6d 79 64 6f 74 70 72 65 66 tion/${mydotpref
2d80: 69 78 7d 24 7b 6d 79 64 6f 74 69 64 7d 24 7b 73 ix}${mydotid}${s
2d90: 75 66 66 69 78 7d 2e 64 6f 74 0a 09 66 69 6c 65 uffix}.dot..file
2da0: 20 6d 6b 64 69 72 20 5b 66 69 6c 65 20 64 69 72 mkdir [file dir
2db0: 6e 61 6d 65 20 24 66 6e 61 6d 65 5d 0a 09 64 6f name $fname]..do
2dc0: 74 20 77 72 69 74 65 20 24 64 67 20 24 6d 79 64 t write $dg $myd
2dd0: 6f 74 70 72 65 66 69 78 24 73 75 66 66 69 78 20 otprefix$suffix
2de0: 24 66 6e 61 6d 65 20 24 73 75 62 67 72 61 70 68 $fname $subgraph
2df0: 0a 09 69 6e 63 72 20 6d 79 64 6f 74 69 64 0a 0a ..incr mydotid..
2e00: 09 6c 6f 67 20 77 72 69 74 65 20 35 20 63 79 63 .log write 5 cyc
2e10: 6c 65 62 72 65 61 6b 65 72 20 22 2e 64 6f 74 20 lebreaker ".dot
2e20: 65 78 70 6f 72 74 20 24 66 6e 61 6d 65 22 0a 09 export $fname"..
2e30: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
2e40: 20 20 70 72 6f 63 20 52 65 70 6c 61 63 65 20 7b proc Replace {
2e50: 64 67 20 6e 20 72 65 70 6c 61 63 65 6d 65 6e 74 dg n replacement
2e60: 73 7d 20 7b 0a 09 23 20 4e 4f 54 45 2e 20 57 65 s} {..# NOTE. We
2e70: 20 68 61 76 65 20 74 6f 20 67 65 74 20 74 68 65 have to get the
2e80: 20 6c 69 73 74 20 6f 66 20 69 6e 63 6f 6d 69 6e list of incomin
2e90: 67 20 6e 65 69 67 68 62 6f 75 72 73 20 61 6e 64 g neighbours and
2ea0: 0a 09 23 20 72 65 63 6f 6d 70 75 74 65 20 74 68 ..# recompute th
2eb0: 65 69 72 20 73 75 63 63 65 73 73 6f 72 73 20 61 eir successors a
2ec0: 66 74 65 72 20 74 68 65 20 6e 65 77 20 6e 6f 64 fter the new nod
2ed0: 65 73 20 68 61 76 65 20 62 65 65 6e 0a 09 23 20 es have been..#
2ee0: 69 6e 73 65 72 74 65 64 2e 20 54 68 65 69 72 20 inserted. Their
2ef0: 6f 75 74 67 6f 69 6e 67 20 61 72 63 73 20 77 69 outgoing arcs wi
2f00: 6c 6c 20 6e 6f 77 20 67 6f 20 74 6f 20 6f 6e 65 ll now go to one
2f10: 20 6f 72 20 62 6f 74 68 20 6f 66 0a 09 23 20 74 or both of..# t
2f20: 68 65 20 6e 65 77 20 6e 6f 64 65 73 2c 20 61 6e he new nodes, an
2f30: 64 20 6e 6f 74 20 72 65 64 6f 69 6e 67 20 74 68 d not redoing th
2f40: 65 6d 20 6d 61 79 20 63 61 75 73 65 20 75 73 20 em may cause us
2f50: 74 6f 20 66 6f 72 67 65 74 0a 09 23 20 63 69 72 to forget..# cir
2f60: 63 6c 65 73 2c 20 6c 65 61 76 69 6e 67 20 74 68 cles, leaving th
2f70: 65 6d 20 69 6e 2c 20 75 6e 62 72 6f 6b 65 6e 2e em in, unbroken.
2f80: 0a 0a 09 73 65 74 20 70 72 65 20 5b 24 64 67 20 ...set pre [$dg
2f90: 6e 6f 64 65 73 20 2d 69 6e 20 24 6e 5d 0a 0a 20 nodes -in $n]..
2fa0: 20 20 20 20 20 20 20 24 64 67 20 6e 6f 64 65 20 $dg node
2fb0: 64 65 6c 65 74 65 20 24 6e 0a 0a 09 66 6f 72 65 delete $n...fore
2fc0: 61 63 68 20 63 73 65 74 20 24 72 65 70 6c 61 63 ach cset $replac
2fd0: 65 6d 65 6e 74 73 20 7b 0a 09 20 20 20 20 73 65 ements {.. se
2fe0: 74 20 74 72 20 5b 24 63 73 65 74 20 74 69 6d 65 t tr [$cset time
2ff0: 72 61 6e 67 65 5d 0a 09 20 20 20 20 24 64 67 20 range].. $dg
3000: 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 node insert $cse
3010: 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 t.. $dg node
3020: 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 6d set $cset tim
3030: 65 72 61 6e 67 65 20 24 74 72 0a 09 20 20 20 20 erange $tr..
3040: 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 $dg node set
3050: 24 63 73 65 74 20 6c 61 62 65 6c 20 20 20 20 20 $cset label
3060: 22 5b 24 63 73 65 74 20 73 74 72 5d 5c 5c 6e 5b "[$cset str]\\n[
3070: 6a 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 join [struct::li
3080: 73 74 20 6d 61 70 20 24 74 72 20 7b 3a 3a 63 6c st map $tr {::cl
3090: 6f 63 6b 20 66 6f 72 6d 61 74 7d 5d 20 22 5c 5c ock format}] "\\
30a0: 6e 22 5d 22 0a 09 20 20 20 20 24 64 67 20 6e 6f n"]".. $dg no
30b0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
30c0: 5f 5f 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 74 __id__ [$cset
30d0: 20 69 64 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f id].. $dg no
30e0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
30f0: 73 68 61 70 65 20 20 20 20 20 5b 65 78 70 72 20 shape [expr
3100: 7b 5b 24 63 73 65 74 20 62 79 73 79 6d 62 6f 6c {[$cset bysymbol
3110: 5d 0a 09 09 09 09 09 09 20 20 20 3f 20 22 65 6c ]....... ? "el
3120: 6c 69 70 73 65 22 0a 09 09 09 09 09 09 20 20 20 lipse".......
3130: 3a 20 22 62 6f 78 22 7d 5d 0a 09 7d 0a 0a 09 66 : "box"}]..}...f
3140: 6f 72 65 61 63 68 20 63 73 65 74 20 24 72 65 70 oreach cset $rep
3150: 6c 61 63 65 6d 65 6e 74 73 20 7b 0a 09 20 20 20 lacements {..
3160: 20 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 foreach succ [$
3170: 63 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d cset successors]
3180: 20 7b 0a 09 09 23 20 54 68 65 20 6e 65 77 20 63 {...# The new c
3190: 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 hangesets may ha
31a0: 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 ve dependencies
31b0: 6f 75 74 73 69 64 65 20 6f 66 0a 09 09 23 20 74 outside of...# t
31c0: 68 65 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 he chosen set. T
31d0: 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 65 64 hese are ignored
31e0: 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 ...if {![$dg nod
31f0: 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d e exists $succ]}
3200: 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 continue...$dg
3210: 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 arc insert $cset
3220: 20 24 73 75 63 63 0a 09 09 69 6e 74 65 67 72 69 $succ...integri
3230: 74 79 20 61 73 73 65 72 74 20 7b 0a 09 09 20 20 ty assert {...
3240: 20 20 24 73 75 63 63 20 6e 65 20 24 63 73 65 74 $succ ne $cset
3250: 0a 09 09 7d 20 7b 5b 24 63 73 65 74 20 72 65 70 ...} {[$cset rep
3260: 6f 72 74 6c 6f 6f 70 20 30 5d 43 68 61 6e 67 65 ortloop 0]Change
3270: 73 65 74 20 6c 6f 6f 70 20 77 61 73 20 6e 6f 74 set loop was not
3280: 20 64 65 74 65 63 74 65 64 20 64 75 72 69 6e 67 detected during
3290: 20 63 72 65 61 74 69 6f 6e 7d 0a 09 20 20 20 20 creation}..
32a0: 7d 0a 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 }..}..foreach cs
32b0: 65 74 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 et $pre {.. f
32c0: 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 oreach succ [$cs
32d0: 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b et successors] {
32e0: 0a 09 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 ...# Note that t
32f0: 68 65 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 he arc may alrea
3300: 64 79 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 dy exist in the
3310: 67 72 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f graph. If...# so
3320: 20 69 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 ignore it. The
3330: 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d new changesets m
3340: 61 79 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 ay have...# depe
3350: 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 ndencies outside
3360: 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 of the chosen s
3370: 65 74 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 et. These are...
3380: 23 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b # ignored...if {
3390: 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 ![$dg node exist
33a0: 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e s $succ]} contin
33b0: 75 65 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 ue...if {[HasArc
33c0: 20 24 64 67 20 24 63 73 65 74 20 24 73 75 63 63 $dg $cset $succ
33d0: 5d 7d 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f ]} continue;# TO
33e0: 44 4f 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 DO should be gra
33f0: 70 68 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 ph method....$dg
3400: 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 arc insert $cse
3410: 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 t $succ.. }..
3420: 7d 0a 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d }...return. }
3430: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
3440: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
3450: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 #############.
3460: 20 20 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 6e ## Callback in
3470: 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 20 vokation .....
3480: 20 20 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 7b proc PreHook {
3490: 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 65 graph} {..# Give
34a0: 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 the user of the
34b0: 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 cycle breaker t
34c0: 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 he opportunity t
34d0: 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 o work..# with t
34e0: 68 65 20 67 72 61 70 68 20 62 65 74 77 65 65 6e he graph between
34f0: 20 73 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 75 setup and consu
3500: 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 72 mmation....::var
3510: 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a 09 iable myprecmd..
3520: 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d if {![llength $m
3530: 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e yprecmd]} return
3540: 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c ...uplevel #0 [l
3550: 69 6e 73 65 72 74 20 24 6d 79 70 72 65 63 6d 64 insert $myprecmd
3560: 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d 61 end $graph]..Ma
3570: 72 6b 20 24 67 72 61 70 68 20 2d 70 72 65 2d 64 rk $graph -pre-d
3580: 6f 6e 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 one..return.
3590: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 6f 63 }.. proc Proc
35a0: 65 73 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 73 essedHook {dg cs
35b0: 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 76 et pos} {..# Giv
35c0: 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 e the user of th
35d0: 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 e cycle breaker
35e0: 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 the opportunity
35f0: 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 to work..# with
3600: 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 62 65 the changeset be
3610: 66 6f 72 65 20 69 74 20 69 73 20 72 65 6d 6f 76 fore it is remov
3620: 65 64 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 ed from the grap
3630: 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 h....::variable
3640: 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 20 7b 21 mysavecmd..if {!
3650: 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 65 [llength $mysave
3660: 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 75 cmd]} return...u
3670: 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 plevel #0 [linse
3680: 72 74 20 24 6d 79 73 61 76 65 63 6d 64 20 65 6e rt $mysavecmd en
3690: 64 20 24 64 67 20 24 70 6f 73 20 24 63 73 65 74 d $dg $pos $cset
36a0: 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a ]..return. }.
36b0: 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 . proc BreakC
36c0: 79 63 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d ycleHook {graph}
36d0: 20 7b 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 {..# Call out t
36e0: 6f 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 o the chosen alg
36f0: 6f 72 69 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 orithm for cycle
3700: 20 62 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 breaking. Findi
3710: 6e 67 0a 09 23 20 61 20 63 79 63 6c 65 20 69 66 ng..# a cycle if
3720: 20 6e 6f 20 62 72 65 61 6b 65 72 20 77 61 73 20 no breaker was
3730: 63 68 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 72 chosen is an err
3740: 6f 72 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 or....::variable
3750: 20 6d 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 mybreakcmd..if
3760: 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 {![llength $mybr
3770: 65 61 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 eakcmd]} {..
3780: 74 72 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 46 trouble fatal "F
3790: 6f 75 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 78 ound a cycle, ex
37a0: 70 65 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 pecting none."..
37b0: 20 20 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 exit 1..}...
37c0: 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 uplevel #0 [lins
37d0: 65 72 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 ert $mybreakcmd
37e0: 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 72 65 74 end $graph]..ret
37f0: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
3800: 72 6f 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b roc ClearHooks {
3810: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
3820: 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 3a myprecmd {}..:
3830: 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 :variable mysave
3840: 63 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 cmd {}..::varia
3850: 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b ble mybreakcmd {
3860: 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a }..return. }.
3870: 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 . # # ## ###
3880: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
3890: 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 ############..
38a0: 20 20 70 72 6f 63 20 4d 61 72 6b 57 61 74 63 68 proc MarkWatch
38b0: 20 7b 67 72 61 70 68 7d 20 7b 0a 09 3a 3a 76 61 {graph} {..::va
38c0: 72 69 61 62 6c 65 20 6d 79 77 61 74 63 68 69 64 riable mywatchid
38d0: 73 0a 09 73 65 74 20 77 61 74 63 68 65 64 20 5b s..set watched [
38e0: 57 61 74 63 68 65 64 20 24 67 72 61 70 68 20 24 Watched $graph $
38f0: 6d 79 77 61 74 63 68 69 64 73 5d 0a 09 69 66 20 mywatchids]..if
3900: 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 77 61 74 63 {![llength $watc
3910: 68 65 64 5d 7d 20 72 65 74 75 72 6e 0a 09 73 65 hed]} return..se
3920: 74 20 6e 65 69 67 68 62 6f 75 72 73 20 5b 65 76 t neighbours [ev
3930: 61 6c 20 5b 6c 69 6e 73 65 72 74 20 24 77 61 74 al [linsert $wat
3940: 63 68 65 64 20 30 20 24 67 72 61 70 68 20 6e 6f ched 0 $graph no
3950: 64 65 73 20 2d 61 64 6a 5d 5d 0a 09 23 66 6f 72 des -adj]]..#for
3960: 65 61 63 68 20 6e 20 24 6e 65 69 67 68 62 6f 75 each n $neighbou
3970: 72 73 20 7b 20 6c 6f 67 20 77 72 69 74 65 20 36 rs { log write 6
3980: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 4e cyclebreaker "N
3990: 65 69 67 68 62 6f 72 20 5b 24 6e 20 69 64 5d 20 eighbor [$n id]
39a0: 3d 3e 20 24 6e 22 20 7d 0a 09 4d 61 72 6b 20 24 => $n" }..Mark $
39b0: 67 72 61 70 68 20 77 61 74 63 68 65 64 20 5b 63 graph watched [c
39c0: 6f 6e 63 61 74 20 24 77 61 74 63 68 65 64 20 24 oncat $watched $
39d0: 6e 65 69 67 68 62 6f 75 72 73 5d 0a 09 72 65 74 neighbours]..ret
39e0: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
39f0: 72 6f 63 20 57 61 74 63 68 65 64 20 7b 67 72 61 roc Watched {gra
3a00: 70 68 20 77 61 74 63 68 69 64 73 7d 20 7b 0a 09 ph watchids} {..
3a10: 73 65 74 20 72 65 73 20 7b 7d 0a 09 66 6f 72 65 set res {}..fore
3a20: 61 63 68 20 69 64 20 24 77 61 74 63 68 69 64 73 ach id $watchids
3a30: 20 7b 0a 09 20 20 20 20 73 65 74 20 6e 6c 20 5b {.. set nl [
3a40: 24 67 72 61 70 68 20 6e 6f 64 65 73 20 2d 6b 65 $graph nodes -ke
3a50: 79 20 5f 5f 69 64 5f 5f 20 2d 76 61 6c 75 65 20 y __id__ -value
3a60: 24 69 64 5d 0a 09 20 20 20 20 69 66 20 7b 21 5b $id].. if {![
3a70: 6c 6c 65 6e 67 74 68 20 24 6e 6c 5d 7d 20 63 6f llength $nl]} co
3a80: 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 ntinue.. lapp
3a90: 65 6e 64 20 72 65 73 20 24 6e 6c 0a 09 20 20 20 end res $nl..
3aa0: 20 23 6c 6f 67 20 77 72 69 74 65 20 36 20 62 72 #log write 6 br
3ab0: 65 61 6b 72 63 79 63 6c 65 20 22 57 61 74 63 68 eakrcycle "Watch
3ac0: 69 6e 67 20 24 69 64 20 3d 3e 20 24 6e 6c 22 0a ing $id => $nl".
3ad0: 09 20 20 20 20 24 67 72 61 70 68 20 6e 6f 64 65 . $graph node
3ae0: 20 73 65 74 20 24 6e 6c 20 66 6f 6e 74 63 6f 6c set $nl fontcol
3af0: 6f 72 20 72 65 64 0a 09 7d 0a 09 72 65 74 75 72 or red..}..retur
3b00: 6e 20 24 72 65 73 0a 20 20 20 20 7d 0a 0a 20 20 n $res. }..
3b10: 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 # # ## ### ###
3b20: 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 ## ######## ####
3b30: 23 23 23 23 23 23 23 23 23 0a 0a 0a 20 20 20 20 #########...
3b40: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 61 typevariable mya
3b50: 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 t 0 ; # Cou
3b60: 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 nter for commit
3b70: 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 20 ids for the....
3b80: 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 65 # changese
3b90: 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 ts.. typevari
3ba0: 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b 7d able mybottom {}
3bb0: 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 65 ; # List of the
3bc0: 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 73 candidate nodes
3bd0: 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 23 for.... #
3be0: 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 20 committing...
3bf0: 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d typevariable m
3c00: 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 23 yprecmd {} ; #
3c10: 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e 67 Callback, chang
3c20: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 77 e graph before w
3c30: 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 72 alk.. typevar
3c40: 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 iable mysavecmd
3c50: 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b {} ; # Callback
3c60: 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 , for each proce
3c70: 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 74 ssed node.. t
3c80: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 72 ypevariable mybr
3c90: 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 61 eakcmd {} ; # Ca
3ca0: 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 68 llback, for each
3cb0: 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 found cycle...
3cc0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3cd0: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
3ce0: 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 74 {} ; # Destinat
3cf0: 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 6f ion directory fo
3d00: 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 20 r the.....
3d10: 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 6f # generated .do
3d20: 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 70 t files.. typ
3d30: 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 evariable mydotp
3d40: 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b 20 refix {} ;
3d50: 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f 74 # Prefix for dot
3d60: 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 09 files when.....
3d70: 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 69 # exporti
3d80: 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a 20 ng the graphs..
3d90: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3da0: 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 20 mydotid
3db0: 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 0 ; # Counter
3dc0: 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 6d for dot file nam
3dd0: 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 67 e..... # g
3de0: 65 6e 65 72 61 74 69 6f 6e 2e 0a 20 20 20 20 74 eneration.. t
3df0: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 77 61 ypevariable mywa
3e00: 74 63 68 69 64 73 20 20 20 20 20 20 20 7b 7d 20 tchids {}
3e10: 3b 20 23 20 43 68 61 6e 67 65 73 65 74 73 20 74 ; # Changesets t
3e20: 6f 20 77 61 74 63 68 20 74 68 65 0a 09 09 09 09 o watch the.....
3e30: 20 20 20 20 20 20 20 23 20 6e 65 69 67 68 62 6f # neighbo
3e40: 75 72 68 6f 6f 64 20 6f 66 2e 0a 0a 20 20 20 20 urhood of...
3e50: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
3e60: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
3e70: 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 #######. ## C
3e80: 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 onfiguration..
3e90: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 pragma -hasins
3ea0: 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 tances no ; #
3eb0: 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 singleton. pr
3ec0: 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 agma -hastypeinf
3ed0: 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 o no ; # no i
3ee0: 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 ntrospection.
3ef0: 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 pragma -hastype
3f00: 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 destroy no ; # i
3f10: 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 mmortal.. # #
3f20: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
3f30: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
3f40: 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 ####.}..namespac
3f50: 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 e eval ::vc::fos
3f60: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
3f70: 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 {. namespace
3f80: 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 export cyclebre
3f90: 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 aker. namespa
3fa0: 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 ce eval cyclebre
3fb0: 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 aker {..namespac
3fc0: 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 e import ::vc::f
3fd0: 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 ossil::import::c
3fe0: 76 73 3a 3a 69 6e 74 65 67 72 69 74 79 0a 09 6e vs::integrity..n
3ff0: 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 70 72 amespace eval pr
4000: 6f 6a 65 63 74 20 7b 0a 09 20 20 20 20 6e 61 6d oject {.. nam
4010: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
4020: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
4030: 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 rt::cvs::project
4040: 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d 65 73 ::rev.. names
4050: 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 pace import ::vc
4060: 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 ::fossil::import
4070: 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a ::cvs::project::
4080: 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 6d 65 revlink..}..name
4090: 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 space import ::v
40a0: 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 3a 3a c::tools::misc::
40b0: 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 *..namespace imp
40c0: 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a ort ::vc::tools:
40d0: 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 65 20 :log..namespace
40e0: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
40f0: 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a 09 6e 61 6d ls::trouble..nam
4100: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
4110: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 0a 09 vc::tools::dot..
4120: 6c 6f 67 20 72 65 67 69 73 74 65 72 20 63 79 63 log register cyc
4130: 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 7d 0a lebreaker. }.
4140: 7d 0a 0a 23 20 23 20 23 23 20 23 23 23 20 23 23 }..# # ## ### ##
4150: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
4160: 23 23 23 23 23 23 23 23 23 23 20 23 23 23 23 23 ########## #####
4170: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
4180: 0a 23 23 20 52 65 61 64 79 0a 0a 70 61 63 6b 61 .## Ready..packa
4190: 67 65 20 70 72 6f 76 69 64 65 20 76 63 3a 3a 66 ge provide vc::f
41a0: 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 ossil::import::c
41b0: 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 72 vs::cyclebreaker
41c0: 20 31 2e 30 0a 72 65 74 75 72 6e 0a 1.0.return.