Artifact ddec7fb99c7ac009ce3a1d5cd6b23888420608a3:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[87cf609021]
- Created convenience methods to create the human readable repesentation of a changeset and lists of such, and made liberal use of them.
by
aku on
2007-11-24 05:31: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 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 0a 23 20 23 20 23 23 20 23 23 23 20 ks...# # ## ###
0600: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
0610: 23 23 23 23 23 23 23 23 23 23 23 23 20 23 23 23 ############ ###
0620: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
0630: 23 23 0a 23 23 20 0a 0a 73 6e 69 74 3a 3a 74 79 ##.## ..snit::ty
0640: 70 65 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a pe ::vc::fossil:
0650: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 :import::cvs::cy
0660: 63 6c 65 62 72 65 61 6b 65 72 20 7b 0a 20 20 20 clebreaker {.
0670: 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 # # ## ### ####
0680: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
0690: 23 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 ########. ##
06a0: 50 75 62 6c 69 63 20 41 50 49 0a 0a 20 20 20 20 Public API..
06b0: 74 79 70 65 6d 65 74 68 6f 64 20 70 72 65 63 6d typemethod precm
06c0: 64 20 7b 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 d {cmd} {..::var
06d0: 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 20 24 iable myprecmd $
06e0: 63 6d 64 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 cmd..return.
06f0: 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f }.. typemetho
0700: 64 20 73 61 76 65 63 6d 64 20 7b 63 6d 64 7d 20 d savecmd {cmd}
0710: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 {..::variable my
0720: 73 61 76 65 63 6d 64 20 24 63 6d 64 0a 09 72 65 savecmd $cmd..re
0730: 74 75 72 6e 0a 20 20 20 20 7d 0a 20 0a 20 20 20 turn. }. .
0740: 20 74 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 typemethod brea
0750: 6b 63 6d 64 20 7b 63 6d 64 7d 20 7b 0a 09 3a 3a kcmd {cmd} {..::
0760: 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 6b variable mybreak
0770: 63 6d 64 20 24 63 6d 64 0a 09 72 65 74 75 72 6e cmd $cmd..return
0780: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 . }.. # #
0790: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
07a0: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
07b0: 23 23 23 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 ###.. typemet
07c0: 68 6f 64 20 64 6f 74 73 74 6f 20 7b 70 61 74 68 hod dotsto {path
07d0: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
07e0: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
07f0: 20 24 70 61 74 68 0a 09 72 65 74 75 72 6e 0a 20 $path..return.
0800: 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 }.. typeme
0810: 74 68 6f 64 20 64 6f 74 20 7b 6c 61 62 65 6c 20 thod dot {label
0820: 63 68 61 6e 67 65 73 65 74 73 7d 20 7b 0a 09 3a changesets} {..:
0830: 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 :variable mydotp
0840: 72 65 66 69 78 20 24 6c 61 62 65 6c 0a 09 3a 3a refix $label..::
0850: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 variable mydotid
0860: 20 20 20 20 20 30 0a 0a 09 73 65 74 20 64 67 20 0...set dg
0870: 5b 53 65 74 75 70 20 24 63 68 61 6e 67 65 73 65 [Setup $changese
0880: 74 73 20 30 5d 0a 09 4d 61 72 6b 20 24 64 67 0a ts 0]..Mark $dg.
0890: 09 24 64 67 20 64 65 73 74 72 6f 79 0a 09 72 65 .$dg destroy..re
08a0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
08b0: 74 79 70 65 6d 65 74 68 6f 64 20 6d 61 72 6b 20 typemethod mark
08c0: 7b 67 72 61 70 68 20 73 75 66 66 69 78 20 7b 73 {graph suffix {s
08d0: 75 62 67 72 61 70 68 20 7b 7d 7d 7d 20 7b 0a 09 ubgraph {}}} {..
08e0: 4d 61 72 6b 20 24 67 72 61 70 68 20 24 73 75 66 Mark $graph $suf
08f0: 66 69 78 20 24 73 75 62 67 72 61 70 68 0a 09 72 fix $subgraph..r
0900: 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 eturn. }..
0910: 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 # # ## ### ####
0920: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
0930: 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 ########.. ty
0940: 70 65 6d 65 74 68 6f 64 20 72 75 6e 20 7b 6c 61 pemethod run {la
0950: 62 65 6c 20 63 68 61 6e 67 65 73 65 74 63 6d 64 bel changesetcmd
0960: 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 } {..::variable
0970: 6d 79 61 74 20 20 20 20 20 20 20 20 30 0a 09 3a myat 0..:
0980: 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 :variable mydotp
0990: 72 65 66 69 78 20 24 6c 61 62 65 6c 0a 09 3a 3a refix $label..::
09a0: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 variable mydotid
09b0: 20 20 20 20 20 30 0a 0a 09 23 20 57 65 20 63 72 0...# We cr
09c0: 65 61 74 65 20 61 20 67 72 61 70 68 20 6f 66 20 eate a graph of
09d0: 74 68 65 20 72 65 76 69 73 69 6f 6e 20 63 68 61 the revision cha
09e0: 6e 67 65 73 65 74 73 2c 20 75 73 69 6e 67 20 74 ngesets, using t
09f0: 68 65 20 66 69 6c 65 0a 09 23 20 6c 65 76 65 6c he file..# level
0a00: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 74 6f dependencies to
0a10: 20 63 6f 6e 73 74 72 75 63 74 20 61 20 66 69 72 construct a fir
0a20: 73 74 20 61 70 70 72 6f 78 69 6d 61 74 69 6f 6e st approximation
0a30: 20 6f 66 20 74 68 65 0a 09 23 20 64 65 70 65 6e of the..# depen
0a40: 64 65 6e 63 69 65 73 20 61 74 20 74 68 65 20 70 dencies at the p
0a50: 72 6f 6a 65 63 74 20 6c 65 76 65 6c 2e 20 54 68 roject level. Th
0a60: 65 6e 20 77 65 20 6c 6f 6f 6b 20 66 6f 72 20 63 en we look for c
0a70: 79 63 6c 65 73 0a 09 23 20 69 6e 20 74 68 61 74 ycles..# in that
0a80: 20 67 72 61 70 68 20 61 6e 64 20 62 72 65 61 6b graph and break
0a90: 20 74 68 65 6d 2e 0a 0a 09 23 20 31 2e 20 43 72 them....# 1. Cr
0aa0: 65 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 20 61 eate nodes for a
0ab0: 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e ll relevant chan
0ac0: 67 65 73 65 74 73 20 61 6e 64 20 61 20 6d 61 70 gesets and a map
0ad0: 70 69 6e 67 0a 09 23 20 20 20 20 66 72 6f 6d 20 ping..# from
0ae0: 74 68 65 20 72 65 76 69 73 69 6f 6e 73 20 74 6f the revisions to
0af0: 20 74 68 65 69 72 20 63 68 61 6e 67 65 73 65 74 their changeset
0b00: 73 2f 6e 6f 64 65 73 2e 0a 0a 09 73 65 74 20 63 s/nodes....set c
0b10: 68 61 6e 67 65 73 65 74 73 20 5b 75 70 6c 65 76 hangesets [uplev
0b20: 65 6c 20 23 30 20 24 63 68 61 6e 67 65 73 65 74 el #0 $changeset
0b30: 63 6d 64 5d 0a 09 73 65 74 20 64 67 20 5b 53 65 cmd]..set dg [Se
0b40: 74 75 70 20 24 63 68 61 6e 67 65 73 65 74 73 5d tup $changesets]
0b50: 0a 0a 09 23 20 33 2e 20 4c 61 73 74 6c 79 20 77 ...# 3. Lastly w
0b60: 65 20 69 74 65 72 61 74 65 20 74 68 65 20 67 72 e iterate the gr
0b70: 61 70 68 20 74 6f 70 6f 6c 6f 67 69 63 61 6c 6c aph topologicall
0b80: 79 2e 20 57 65 20 6d 61 72 6b 20 6f 66 66 0a 09 y. We mark off..
0b90: 23 20 20 20 20 74 68 65 20 6e 6f 64 65 73 20 77 # the nodes w
0ba0: 68 69 63 68 20 68 61 76 65 20 6e 6f 20 70 72 65 hich have no pre
0bb0: 64 65 63 65 73 73 6f 72 73 2c 20 69 6e 20 6f 72 decessors, in or
0bc0: 64 65 72 20 66 72 6f 6d 0a 09 23 20 20 20 20 6f der from..# o
0bd0: 6c 64 65 73 74 20 74 6f 20 79 6f 75 6e 67 65 73 ldest to younges
0be0: 74 2c 20 73 61 76 69 6e 67 20 61 6e 64 20 72 65 t, saving and re
0bf0: 6d 6f 76 69 6e 67 20 64 65 70 65 6e 64 65 6e 63 moving dependenc
0c00: 69 65 73 2e 20 49 66 0a 09 23 20 20 20 20 77 65 ies. If..# we
0c10: 20 66 69 6e 64 20 6e 6f 20 6e 6f 64 65 73 20 77 find no nodes w
0c20: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
0c30: 6f 72 73 20 77 65 20 68 61 76 65 20 61 20 63 79 ors we have a cy
0c40: 63 6c 65 2c 0a 09 23 20 20 20 20 61 6e 64 20 77 cle,..# and w
0c50: 6f 72 6b 20 6f 6e 20 62 72 65 61 6b 69 6e 67 20 ork on breaking
0c60: 69 74 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 it....log write
0c70: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 3 cyclebreaker {
0c80: 4e 6f 77 20 73 6f 72 74 69 6e 67 20 74 68 65 20 Now sorting the
0c90: 63 68 61 6e 67 65 73 65 74 73 2c 20 62 72 65 61 changesets, brea
0ca0: 6b 69 6e 67 20 63 79 63 6c 65 73 7d 0a 0a 09 49 king cycles}...I
0cb0: 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 nitializeCandida
0cc0: 74 65 73 20 24 64 67 0a 09 77 68 69 6c 65 20 7b tes $dg..while {
0cd0: 31 7d 20 7b 0a 09 20 20 20 20 77 68 69 6c 65 20 1} {.. while
0ce0: 7b 5b 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 {[WithoutPredece
0cf0: 73 73 6f 72 20 24 64 67 20 6e 5d 7d 20 7b 0a 09 ssor $dg n]} {..
0d00: 09 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b 20 24 .ProcessedHook $
0d10: 64 67 20 24 6e 20 24 6d 79 61 74 0a 09 09 24 64 dg $n $myat...$d
0d20: 67 20 6e 6f 64 65 20 64 65 6c 65 74 65 20 24 6e g node delete $n
0d30: 0a 09 09 69 6e 63 72 20 6d 79 61 74 0a 09 09 53 ...incr myat...S
0d40: 68 6f 77 50 65 6e 64 69 6e 67 4e 6f 64 65 73 0a howPendingNodes.
0d50: 09 20 20 20 20 7d 0a 0a 09 20 20 20 20 69 66 20 . }... if
0d60: 7b 21 5b 6c 6c 65 6e 67 74 68 20 5b 64 67 20 6e {![llength [dg n
0d70: 6f 64 65 73 5d 5d 7d 20 62 72 65 61 6b 0a 0a 09 odes]]} break...
0d80: 20 20 20 20 42 72 65 61 6b 43 79 63 6c 65 48 6f BreakCycleHo
0d90: 6f 6b 20 20 20 20 20 20 20 24 64 67 0a 09 20 20 ok $dg..
0da0: 20 20 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 InitializeCand
0db0: 69 64 61 74 65 73 20 24 64 67 0a 09 7d 0a 0a 09 idates $dg..}...
0dc0: 24 64 67 20 64 65 73 74 72 6f 79 0a 0a 09 6c 6f $dg destroy...lo
0dd0: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
0de0: 72 65 61 6b 65 72 20 44 6f 6e 65 2e 0a 09 43 6c reaker Done...Cl
0df0: 65 61 72 48 6f 6f 6b 73 0a 0a 09 23 20 52 65 72 earHooks...# Rer
0e00: 65 61 64 20 74 68 65 20 67 72 61 70 68 20 61 6e ead the graph an
0e10: 64 20 64 75 6d 70 20 69 74 73 20 66 69 6e 61 6c d dump its final
0e20: 20 66 6f 72 6d 2c 20 69 66 20 67 72 61 70 68 20 form, if graph
0e30: 65 78 70 6f 72 74 0a 09 23 20 77 61 73 20 61 63 export..# was ac
0e40: 74 69 76 61 74 65 64 2e 0a 0a 09 3a 3a 76 61 72 tivated....::var
0e50: 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 iable mydotdesti
0e60: 6e 61 74 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 nation..if {$myd
0e70: 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 65 71 otdestination eq
0e80: 20 22 22 7d 20 72 65 74 75 72 6e 0a 0a 09 73 65 ""} return...se
0e90: 74 20 20 20 64 67 20 5b 53 65 74 75 70 20 5b 75 t dg [Setup [u
0ea0: 70 6c 65 76 65 6c 20 23 30 20 24 63 68 61 6e 67 plevel #0 $chang
0eb0: 65 73 65 74 63 6d 64 5d 20 30 5d 0a 09 4d 61 72 esetcmd] 0]..Mar
0ec0: 6b 20 24 64 67 20 2d 64 6f 6e 65 0a 09 24 64 67 k $dg -done..$dg
0ed0: 20 64 65 73 74 72 6f 79 0a 09 72 65 74 75 72 6e destroy..return
0ee0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 . }.. # #
0ef0: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
0f00: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
0f10: 23 23 23 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 ###.. typemet
0f20: 68 6f 64 20 62 72 65 61 6b 20 7b 67 72 61 70 68 hod break {graph
0f30: 7d 20 7b 0a 09 42 72 65 61 6b 43 79 63 6c 65 20 } {..BreakCycle
0f40: 24 67 72 61 70 68 20 5b 46 69 6e 64 43 79 63 6c $graph [FindCycl
0f50: 65 20 24 67 72 61 70 68 5d 0a 09 72 65 74 75 72 e $graph]..retur
0f60: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 n. }.. typ
0f70: 65 6d 65 74 68 6f 64 20 72 65 70 6c 61 63 65 20 emethod replace
0f80: 7b 67 72 61 70 68 20 6e 20 72 65 70 6c 61 63 65 {graph n replace
0f90: 6d 65 6e 74 73 7d 20 7b 0a 09 52 65 70 6c 61 63 ments} {..Replac
0fa0: 65 20 24 67 72 61 70 68 20 24 6e 20 24 72 65 70 e $graph $n $rep
0fb0: 6c 61 63 65 6d 65 6e 74 73 0a 09 72 65 74 75 72 lacements..retur
0fc0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 n. }.. # #
0fd0: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
0fe0: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
0ff0: 23 23 23 23 0a 20 20 20 20 23 23 20 49 6e 74 65 ####. ## Inte
1000: 72 6e 61 6c 20 6d 65 74 68 6f 64 73 0a 0a 20 20 rnal methods..
1010: 20 20 70 72 6f 63 20 53 65 74 75 70 20 7b 63 68 proc Setup {ch
1020: 61 6e 67 65 73 65 74 73 20 7b 6c 6f 67 20 31 7d angesets {log 1}
1030: 7d 20 7b 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b } {..if {$log} {
1040: 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 .. log write
1050: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 3 cyclebreaker "
1060: 43 72 65 61 74 69 6e 67 20 63 68 61 6e 67 65 73 Creating changes
1070: 65 74 20 67 72 61 70 68 2c 20 66 69 6c 6c 69 6e et graph, fillin
1080: 67 20 77 69 74 68 20 6e 6f 64 65 73 22 0a 09 20 g with nodes"..
1090: 20 20 20 6c 6f 67 20 77 72 69 74 65 20 33 20 63 log write 3 c
10a0: 79 63 6c 65 62 72 65 61 6b 65 72 20 22 41 64 64 yclebreaker "Add
10b0: 69 6e 67 20 5b 6e 73 70 20 5b 6c 6c 65 6e 67 74 ing [nsp [llengt
10c0: 68 20 24 63 68 61 6e 67 65 73 65 74 73 5d 20 6e h $changesets] n
10d0: 6f 64 65 5d 22 0a 09 7d 0a 0a 09 73 65 74 20 64 ode]"..}...set d
10e0: 67 20 5b 73 74 72 75 63 74 3a 3a 67 72 61 70 68 g [struct::graph
10f0: 20 64 67 5d 0a 0a 09 66 6f 72 65 61 63 68 20 63 dg]...foreach c
1100: 73 65 74 20 24 63 68 61 6e 67 65 73 65 74 73 20 set $changesets
1110: 7b 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 {.. $dg node
1120: 69 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 insert $cset..
1130: 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 $dg node set
1140: 20 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 $cset timerang
1150: 65 20 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e e [$cset timeran
1160: 67 65 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 ge].. $dg nod
1170: 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 6c e set $cset l
1180: 61 62 65 6c 20 20 20 20 20 5b 24 63 73 65 74 20 abel [$cset
1190: 73 74 72 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f str].. $dg no
11a0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
11b0: 5f 5f 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 74 __id__ [$cset
11c0: 20 69 64 5d 0a 09 7d 0a 0a 09 23 20 32 2e 20 46 id]..}...# 2. F
11d0: 69 6e 64 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 ind for all rele
11e0: 76 61 6e 74 20 63 68 61 6e 67 65 73 65 74 20 74 vant changeset t
11f0: 68 65 69 72 20 72 65 76 69 73 69 6f 6e 73 20 61 heir revisions a
1200: 6e 64 20 74 68 65 69 72 0a 09 23 20 20 20 20 64 nd their..# d
1210: 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 4d 61 70 ependencies. Map
1220: 20 74 68 65 20 6c 61 74 74 65 72 20 62 61 63 6b the latter back
1230: 20 74 6f 20 63 68 61 6e 67 65 73 65 74 73 20 61 to changesets a
1240: 6e 64 0a 09 23 20 20 20 20 63 6f 6e 73 74 72 75 nd..# constru
1250: 63 74 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e ct the correspon
1260: 64 69 6e 67 20 61 72 63 73 2e 0a 0a 09 69 66 20 ding arcs....if
1270: 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f {$log} {.. lo
1280: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
1290: 72 65 61 6b 65 72 20 7b 53 65 74 74 69 6e 67 20 reaker {Setting
12a0: 75 70 20 6e 6f 64 65 20 64 65 70 65 6e 64 65 6e up node dependen
12b0: 63 69 65 73 7d 0a 09 7d 0a 0a 09 66 6f 72 65 61 cies}..}...forea
12c0: 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 73 ch cset $changes
12d0: 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 ets {.. forea
12e0: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 ch succ [$cset s
12f0: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 uccessors] {...#
1300: 20 43 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 Changesets may
1310: 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 have dependencie
1320: 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 s outside of the
1330: 0a 09 09 23 20 63 68 6f 73 65 6e 20 73 65 74 2e ...# chosen set.
1340: 20 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 These are ignor
1350: 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e ed...if {![$dg n
1360: 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 ode exists $succ
1370: 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 ]} continue...$d
1380: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
1390: 65 74 20 24 73 75 63 63 0a 0a 09 09 23 20 43 68 et $succ....# Ch
13a0: 65 63 6b 20 66 6f 72 20 63 68 61 6e 67 65 73 65 eck for changese
13b0: 74 73 20 72 65 66 65 72 65 6e 63 69 6e 67 20 74 ts referencing t
13c0: 68 65 6d 73 65 6c 76 65 73 2e 20 53 75 63 68 20 hemselves. Such
13d0: 61 0a 09 09 23 20 6c 6f 6f 70 20 73 68 6f 77 73 a...# loop shows
13e0: 20 74 68 61 74 20 74 68 65 20 63 68 61 6e 67 65 that the change
13f0: 73 65 74 20 69 6e 20 71 75 65 73 74 69 6f 6e 20 set in question
1400: 68 61 73 0a 09 09 23 20 69 6e 74 65 72 6e 61 6c has...# internal
1410: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 53 dependencies. S
1420: 6f 6d 65 74 68 69 6e 67 20 77 68 69 63 68 20 69 omething which i
1430: 73 20 73 75 70 70 6f 73 65 64 0a 09 09 23 20 74 s supposed...# t
1440: 6f 20 62 65 20 6e 6f 74 20 70 6f 73 73 69 62 6c o be not possibl
1450: 65 2c 20 61 73 20 70 61 73 73 20 35 20 28 49 6e e, as pass 5 (In
1460: 69 74 43 73 65 74 73 29 20 74 61 6b 65 73 20 63 itCsets) takes c
1470: 61 72 65 0a 09 09 23 20 74 6f 20 74 72 61 6e 73 are...# to trans
1480: 66 6f 72 6d 20 69 6e 74 65 72 6e 61 6c 20 69 6e form internal in
1490: 74 6f 20 65 78 74 65 72 6e 61 6c 20 64 65 70 65 to external depe
14a0: 6e 64 65 6e 63 69 65 73 20 62 79 0a 09 09 23 20 ndencies by...#
14b0: 62 72 65 61 6b 69 6e 67 20 74 68 65 20 72 65 6c breaking the rel
14c0: 65 76 61 6e 74 20 63 68 61 6e 67 65 73 65 74 73 evant changesets
14d0: 20 61 70 61 72 74 2e 20 53 6f 20 68 61 76 69 6e apart. So havin
14e0: 67 0a 09 09 23 20 6f 6e 65 20 69 6e 64 69 63 61 g...# one indica
14f0: 74 65 73 20 62 69 67 20 74 72 6f 75 62 6c 65 20 tes big trouble
1500: 69 6e 20 70 61 73 73 20 35 2e 20 57 65 20 72 65 in pass 5. We re
1510: 70 6f 72 74 20 74 68 65 6d 0a 09 09 23 20 61 6e port them...# an
1520: 64 20 64 75 6d 70 20 69 6e 74 65 72 6e 61 6c 20 d dump internal
1530: 73 74 72 75 63 74 75 72 65 73 20 74 6f 20 6d 61 structures to ma
1540: 6b 65 20 69 74 20 65 61 73 69 65 72 20 74 6f 0a ke it easier to.
1550: 09 09 23 20 74 72 61 63 65 20 74 68 65 20 6c 69 ..# trace the li
1560: 6e 6b 73 20 63 61 75 73 69 6e 67 20 74 68 65 20 nks causing the
1570: 70 72 6f 62 6c 65 6d 2e 0a 09 09 69 66 20 7b 24 problem....if {$
1580: 73 75 63 63 20 65 71 20 24 63 73 65 74 7d 20 7b succ eq $cset} {
1590: 0a 09 09 20 20 20 20 74 72 6f 75 62 6c 65 20 66 ... trouble f
15a0: 61 74 61 6c 20 22 53 65 6c 66 2d 72 65 66 65 72 atal "Self-refer
15b0: 65 6e 63 69 6e 67 20 63 68 61 6e 67 65 73 65 74 encing changeset
15c0: 20 5b 24 63 73 65 74 20 73 74 72 5d 22 0a 09 09 [$cset str]"...
15d0: 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 32 20 log write 2
15e0: 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 4c 4f cyclebreaker "LO
15f0: 4f 50 20 63 68 61 6e 67 65 73 65 74 20 5b 24 63 OP changeset [$c
1600: 73 65 74 20 73 74 72 5d 20 5f 5f 5f 5f 5f 5f 5f set str] _______
1610: 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 22 0a 09 09 20 ___________"...
1620: 20 20 20 61 72 72 61 79 20 73 65 74 20 6e 6d 61 array set nma
1630: 70 20 5b 24 63 73 65 74 20 6e 65 78 74 6d 61 70 p [$cset nextmap
1640: 5d 0a 09 09 20 20 20 20 66 6f 72 65 61 63 68 20 ]... foreach
1650: 72 20 5b 6c 73 6f 72 74 20 2d 64 69 63 74 20 5b r [lsort -dict [
1660: 61 72 72 61 79 20 6e 61 6d 65 73 20 6e 6d 61 70 array names nmap
1670: 5d 5d 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 20 ]] {....foreach
1680: 73 75 63 63 72 65 76 20 24 6e 6d 61 70 28 24 72 succrev $nmap($r
1690: 29 20 7b 0a 09 09 09 20 20 20 20 6c 6f 67 20 77 ) {.... log w
16a0: 72 69 74 65 20 32 20 63 79 63 6c 65 62 72 65 61 rite 2 cyclebrea
16b0: 6b 65 72 20 5c 0a 09 09 09 09 22 4c 4f 4f 50 20 ker \....."LOOP
16c0: 2a 20 72 65 76 20 3c 24 72 3e 20 2d 2d 3e 20 72 * rev <$r> --> r
16d0: 65 76 20 3c 24 73 75 63 63 72 65 76 3e 20 2d 2d ev <$succrev> --
16e0: 3e 20 63 73 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 > cs [project::r
16f0: 65 76 20 73 74 72 6c 69 73 74 20 5b 70 72 6f 6a ev strlist [proj
1700: 65 63 74 3a 3a 72 65 76 20 6f 66 72 65 76 20 24 ect::rev ofrev $
1710: 73 75 63 63 72 65 76 5d 5d 22 0a 09 09 09 7d 0a succrev]]"....}.
1720: 09 09 20 20 20 20 7d 0a 09 09 7d 0a 09 20 20 20 .. }...}..
1730: 20 7d 0a 09 7d 0a 0a 09 23 20 52 75 6e 20 74 68 }..}...# Run th
1740: 65 20 75 73 65 72 20 68 6f 6f 6b 20 74 6f 20 6d e user hook to m
1750: 61 6e 69 70 75 6c 61 74 65 20 74 68 65 20 67 72 anipulate the gr
1760: 61 70 68 20 62 65 66 6f 72 65 0a 09 23 20 63 6f aph before..# co
1770: 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 69 66 nsummation....if
1780: 20 7b 24 6c 6f 67 7d 20 7b 20 4d 61 72 6b 20 24 {$log} { Mark $
1790: 64 67 20 2d 73 74 61 72 74 20 7d 0a 09 50 72 65 dg -start }..Pre
17a0: 48 6f 6f 6b 20 24 64 67 0a 0a 09 23 20 54 68 69 Hook $dg...# Thi
17b0: 73 20 6b 69 6c 6c 73 20 74 68 65 20 61 70 70 6c s kills the appl
17c0: 69 63 61 74 69 6f 6e 20 69 66 20 6c 6f 6f 70 73 ication if loops
17d0: 20 28 73 65 65 20 61 62 6f 76 65 29 20 77 65 72 (see above) wer
17e0: 65 20 66 6f 75 6e 64 2e 0a 09 74 72 6f 75 62 6c e found...troubl
17f0: 65 20 61 62 6f 72 74 3f 0a 09 72 65 74 75 72 6e e abort?..return
1800: 20 20 24 64 67 0a 20 20 20 20 7d 0a 0a 20 20 20 $dg. }..
1810: 20 23 20 49 6e 73 74 65 61 64 20 6f 66 20 73 65 # Instead of se
1820: 61 72 63 68 69 6e 67 20 74 68 65 20 77 68 6f 6c arching the whol
1830: 65 20 67 72 61 70 68 20 66 6f 72 20 74 68 65 20 e graph for the
1840: 64 65 67 72 65 65 2d 30 20 6e 6f 64 65 73 20 69 degree-0 nodes i
1850: 6e 0a 20 20 20 20 23 20 65 61 63 68 20 69 74 65 n. # each ite
1860: 72 61 74 69 6f 6e 20 77 65 20 63 6f 6d 70 75 74 ration we comput
1870: 65 20 74 68 65 20 6c 69 73 74 20 6f 6e 63 65 20 e the list once
1880: 74 6f 20 73 74 61 72 74 2c 20 61 6e 64 20 74 68 to start, and th
1890: 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 23 20 75 70 en only. # up
18a0: 64 61 74 65 20 69 74 20 69 6e 63 72 65 6d 65 6e date it incremen
18b0: 74 61 6c 6c 79 20 62 61 73 65 64 20 6f 6e 20 74 tally based on t
18c0: 68 65 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 he outgoing neig
18d0: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 0a 20 20 hbours of the.
18e0: 20 20 23 20 6e 6f 64 65 20 63 68 6f 73 65 6e 20 # node chosen
18f0: 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 for commit...
1900: 20 70 72 6f 63 20 49 6e 69 74 69 61 6c 69 7a 65 proc Initialize
1910: 43 61 6e 64 69 64 61 74 65 73 20 7b 64 67 7d 20 Candidates {dg}
1920: 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 {..# bottom = li
1930: 73 74 20 28 6c 69 73 74 20 28 6e 6f 64 65 2c 20 st (list (node,
1940: 72 61 6e 67 65 20 6d 69 6e 2c 20 72 61 6e 67 65 range min, range
1950: 20 6d 61 78 29 29 0a 09 3a 3a 76 61 72 69 61 62 max))..::variab
1960: 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 66 6f 72 le mybottom..for
1970: 65 61 63 68 20 6e 20 5b 24 64 67 20 6e 6f 64 65 each n [$dg node
1980: 73 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 s] {.. if {[$
1990: 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d dg node degree -
19a0: 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 in $n]} continue
19b0: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 .. lappend my
19c0: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
19d0: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6e [$dg node get $n
19e0: 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6e timerange] 0 $n
19f0: 5d 0a 09 7d 0a 09 73 65 74 20 6d 79 62 6f 74 74 ]..}..set mybott
1a00: 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 om [lsort -index
1a10: 20 31 20 2d 69 6e 74 65 67 65 72 20 5b 6c 73 6f 1 -integer [lso
1a20: 72 74 20 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 rt -index 2 -int
1a30: 65 67 65 72 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d eger $mybottom]]
1a40: 0a 09 53 68 6f 77 50 65 6e 64 69 6e 67 4e 6f 64 ..ShowPendingNod
1a50: 65 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d es..return. }
1a60: 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 74 68 6f .. proc Witho
1a70: 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 7b 64 utPredecessor {d
1a80: 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 g nv} {..::varia
1a90: 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 0a 09 75 ble mybottom...u
1aa0: 70 76 61 72 20 31 20 24 6e 76 20 6e 0a 09 69 66 pvar 1 $nv n..if
1ab0: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 {![llength $myb
1ac0: 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 72 6e ottom]} { return
1ad0: 20 30 20 7d 0a 0a 09 73 65 74 20 6e 20 5b 6c 69 0 }...set n [li
1ae0: 6e 64 65 78 20 5b 6c 69 6e 64 65 78 20 24 6d 79 ndex [lindex $my
1af0: 62 6f 74 74 6f 6d 20 30 5d 20 30 5d 0a 09 73 65 bottom 0] 0]..se
1b00: 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 72 61 6e t mybottom [lran
1b10: 67 65 20 24 6d 79 62 6f 74 74 6f 6d 20 31 20 65 ge $mybottom 1 e
1b20: 6e 64 5d 0a 09 73 65 74 20 63 68 61 6e 67 65 64 nd]..set changed
1b30: 20 30 0a 0a 09 23 20 55 70 64 61 74 65 20 6c 69 0...# Update li
1b40: 73 74 20 6f 66 20 6e 6f 64 65 73 20 77 69 74 68 st of nodes with
1b50: 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f 72 2c out predecessor,
1b60: 20 62 61 73 65 64 20 6f 6e 20 74 68 65 0a 09 23 based on the..#
1b70: 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 outgoing neighb
1b80: 6f 75 72 73 20 6f 66 20 74 68 65 20 63 68 6f 73 ours of the chos
1b90: 65 6e 20 6e 6f 64 65 2e 20 54 68 69 73 20 73 68 en node. This sh
1ba0: 6f 75 6c 64 20 62 65 0a 09 23 20 66 61 73 74 65 ould be..# faste
1bb0: 72 20 74 68 61 6e 20 69 74 65 72 61 74 69 6e 67 r than iterating
1bc0: 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 20 73 65 of the whole se
1bd0: 74 20 6f 66 20 6e 6f 64 65 73 2c 20 66 69 6e 64 t of nodes, find
1be0: 69 6e 67 20 61 6c 6c 0a 09 23 20 77 69 74 68 6f ing all..# witho
1bf0: 75 74 20 70 72 65 64 65 63 65 73 73 6f 72 73 2c ut predecessors,
1c00: 20 73 6f 72 74 69 6e 67 20 74 68 65 6d 20 62 79 sorting them by
1c10: 20 74 69 6d 65 2c 20 65 74 63 2e 20 70 70 2e 0a time, etc. pp..
1c20: 09 66 6f 72 65 61 63 68 20 6f 75 74 20 5b 24 64 .foreach out [$d
1c30: 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 6e 5d g nodes -out $n]
1c40: 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 64 67 {.. if {[$dg
1c50: 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d 69 6e node degree -in
1c60: 20 24 6f 75 74 5d 20 3e 20 31 7d 20 63 6f 6e 74 $out] > 1} cont
1c70: 69 6e 75 65 0a 09 20 20 20 20 23 20 44 65 67 72 inue.. # Degr
1c80: 65 65 2d 31 20 6e 65 69 67 68 62 6f 75 72 2c 20 ee-1 neighbour,
1c90: 77 69 6c 6c 20 68 61 76 65 20 6e 6f 20 70 72 65 will have no pre
1ca0: 64 65 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 decessors after
1cb0: 74 68 65 0a 09 20 20 20 20 23 20 72 65 6d 6f 76 the.. # remov
1cc0: 61 6c 20 6f 66 20 6e 2e 20 50 75 74 20 6f 6e 20 al of n. Put on
1cd0: 74 68 65 20 6c 69 73 74 2e 0a 09 20 20 20 20 6c the list... l
1ce0: 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 6f 6d 20 append mybottom
1cf0: 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f [linsert [$dg no
1d00: 64 65 20 67 65 74 20 24 6f 75 74 20 74 69 6d 65 de get $out time
1d10: 72 61 6e 67 65 5d 20 30 20 24 6f 75 74 5d 0a 09 range] 0 $out]..
1d20: 20 20 20 20 73 65 74 20 63 68 61 6e 67 65 64 20 set changed
1d30: 31 0a 09 7d 0a 09 69 66 20 7b 24 63 68 61 6e 67 1..}..if {$chang
1d40: 65 64 7d 20 7b 0a 09 20 20 20 20 73 65 74 20 6d ed} {.. set m
1d50: 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d ybottom [lsort -
1d60: 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72 index 1 -integer
1d70: 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32 [lsort -index 2
1d80: 20 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 74 -integer $mybot
1d90: 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 20 57 65 20 tom]]..}...# We
1da0: 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 20 74 68 do not delete th
1db0: 65 20 6e 6f 64 65 20 69 6d 6d 65 64 69 61 74 65 e node immediate
1dc0: 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 68 65 ly, to allow the
1dd0: 20 53 61 76 65 0a 09 23 20 70 72 6f 63 65 64 75 Save..# procedu
1de0: 72 65 20 74 6f 20 73 61 76 65 20 74 68 65 20 64 re to save the d
1df0: 65 70 65 6e 64 65 6e 63 69 65 73 20 61 73 20 77 ependencies as w
1e00: 65 6c 6c 20 28 65 6e 63 6f 64 65 64 20 69 6e 20 ell (encoded in
1e10: 74 68 65 0a 09 23 20 61 72 63 73 29 2e 0a 09 72 the..# arcs)...r
1e20: 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 eturn 1. }..
1e30: 20 20 20 70 72 6f 63 20 53 68 6f 77 50 65 6e 64 proc ShowPend
1e40: 69 6e 67 4e 6f 64 65 73 20 7b 7d 20 7b 0a 09 69 ingNodes {} {..i
1e50: 66 20 7b 5b 6c 6f 67 20 76 65 72 62 6f 73 69 74 f {[log verbosit
1e60: 79 3f 5d 20 3c 20 31 30 7d 20 72 65 74 75 72 6e y?] < 10} return
1e70: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 ..::variable myb
1e80: 6f 74 74 6f 6d 0a 09 6c 6f 67 20 77 72 69 74 65 ottom..log write
1e90: 20 31 30 20 63 79 63 6c 65 62 72 65 61 6b 65 72 10 cyclebreaker
1ea0: 20 5c 0a 09 20 20 20 20 22 50 65 6e 64 69 6e 67 \.. "Pending
1eb0: 3a 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 : [struct::list
1ec0: 6d 61 70 20 24 6d 79 62 6f 74 74 6f 6d 20 5b 6d map $mybottom [m
1ed0: 79 70 72 6f 63 20 46 6f 72 6d 61 74 50 65 6e 64 yproc FormatPend
1ee0: 69 6e 67 49 74 65 6d 5d 5d 22 0a 09 72 65 74 75 ingItem]]"..retu
1ef0: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
1f00: 6f 63 20 46 6f 72 6d 61 74 50 65 6e 64 69 6e 67 oc FormatPending
1f10: 49 74 65 6d 20 7b 69 74 65 6d 7d 20 7b 20 6c 72 Item {item} { lr
1f20: 65 70 6c 61 63 65 20 24 69 74 65 6d 20 30 20 30 eplace $item 0 0
1f30: 20 5b 5b 6c 69 6e 64 65 78 20 24 69 74 65 6d 20 [[lindex $item
1f40: 30 5d 20 73 74 72 5d 20 7d 0a 0a 20 20 20 20 70 0] str] }.. p
1f50: 72 6f 63 20 46 69 6e 64 43 79 63 6c 65 20 7b 64 roc FindCycle {d
1f60: 67 7d 20 7b 0a 09 23 20 54 68 69 73 20 70 72 6f g} {..# This pro
1f70: 63 65 64 75 72 65 20 69 73 20 72 75 6e 20 69 66 cedure is run if
1f80: 20 61 6e 64 20 6f 6e 6c 79 20 74 68 65 20 67 72 and only the gr
1f90: 61 70 68 20 69 73 20 6e 6f 74 20 65 6d 70 74 79 aph is not empty
1fa0: 20 61 6e 64 0a 09 23 20 61 6c 6c 20 6e 6f 64 65 and..# all node
1fb0: 73 20 68 61 76 65 20 70 72 65 64 65 63 65 73 73 s have predecess
1fc0: 6f 72 73 2e 20 54 68 69 73 20 6d 65 61 6e 73 20 ors. This means
1fd0: 74 68 61 74 20 65 61 63 68 20 6e 6f 64 65 20 69 that each node i
1fe0: 73 0a 09 23 20 65 69 74 68 65 72 20 70 61 72 74 s..# either part
1ff0: 20 6f 66 20 61 20 63 79 63 6c 65 20 6f 72 20 28 of a cycle or (
2000: 69 6e 64 69 72 65 63 74 6c 79 29 20 64 65 70 65 indirectly) depe
2010: 6e 64 69 6e 67 20 6f 6e 20 61 20 6e 6f 64 65 0a nding on a node.
2020: 09 23 20 69 6e 20 61 20 63 79 63 6c 65 2e 20 57 .# in a cycle. W
2030: 65 20 63 61 6e 20 73 74 61 72 74 20 61 74 20 61 e can start at a
2040: 6e 20 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65 n arbitrary node
2050: 2c 20 66 6f 6c 6c 6f 77 20 69 74 73 0a 09 23 20 , follow its..#
2060: 69 6e 63 6f 6d 69 6e 67 20 65 64 67 65 73 20 74 incoming edges t
2070: 6f 20 69 74 73 20 70 72 65 64 65 63 65 73 73 6f o its predecesso
2080: 72 73 20 75 6e 74 69 6c 20 77 65 20 73 65 65 20 rs until we see
2090: 61 20 6e 6f 64 65 20 61 0a 09 23 20 73 65 63 6f a node a..# seco
20a0: 6e 64 20 74 69 6d 65 2e 20 54 68 61 74 20 6e 6f nd time. That no
20b0: 64 65 20 63 6c 6f 73 65 73 20 74 68 65 20 63 79 de closes the cy
20c0: 63 6c 65 20 61 6e 64 20 74 68 65 20 62 65 67 69 cle and the begi
20d0: 6e 6e 69 6e 67 20 69 73 0a 09 23 20 69 74 73 20 nning is..# its
20e0: 66 69 72 73 74 20 6f 63 63 75 72 65 6e 63 65 2e first occurence.
20f0: 20 4e 6f 74 65 20 74 68 61 74 20 77 65 20 63 61 Note that we ca
2100: 6e 20 63 68 6f 6f 73 65 20 61 6e 20 61 72 62 69 n choose an arbi
2110: 74 72 61 72 79 0a 09 23 20 70 72 65 64 65 63 65 trary..# predece
2120: 73 73 6f 72 20 6f 66 20 65 61 63 68 20 6e 6f 64 ssor of each nod
2130: 65 20 61 73 20 77 65 6c 6c 2c 20 77 65 20 64 6f e as well, we do
2140: 20 6e 6f 74 20 68 61 76 65 20 74 6f 20 73 65 61 not have to sea
2150: 72 63 68 2e 0a 0a 09 23 20 57 65 20 72 65 63 6f rch....# We reco
2160: 72 64 20 66 6f 72 20 65 61 63 68 20 6e 6f 64 65 rd for each node
2170: 20 74 68 65 20 69 6e 64 65 78 20 6f 66 20 74 68 the index of th
2180: 65 20 66 69 72 73 74 20 61 70 70 65 61 72 61 6e e first appearan
2190: 63 65 20 69 6e 0a 09 23 20 74 68 65 20 70 61 74 ce in..# the pat
21a0: 68 2c 20 6d 61 6b 69 6e 67 20 69 74 20 65 61 73 h, making it eas
21b0: 79 20 61 74 20 74 68 65 20 65 6e 64 20 74 6f 20 y at the end to
21c0: 63 75 74 20 74 68 65 20 63 79 63 6c 65 20 66 72 cut the cycle fr
21d0: 6f 6d 0a 09 23 20 69 74 2e 0a 0a 09 23 20 43 68 om..# it....# Ch
21e0: 6f 6f 73 65 20 61 72 62 69 74 72 61 72 79 20 6e oose arbitrary n
21f0: 6f 64 65 20 74 6f 20 73 74 61 72 74 20 6f 75 72 ode to start our
2200: 20 73 65 61 72 63 68 20 61 74 2e 0a 09 73 65 74 search at...set
2210: 20 73 74 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b start [lindex [
2220: 24 64 67 20 6e 6f 64 65 73 5d 20 30 5d 0a 0a 09 $dg nodes] 0]...
2230: 23 20 49 6e 69 74 69 61 6c 69 7a 65 20 73 74 61 # Initialize sta
2240: 74 65 2c 20 70 61 74 68 20 6f 66 20 73 65 65 6e te, path of seen
2250: 20 6e 6f 64 65 73 2c 20 61 6e 64 20 77 68 65 6e nodes, and when
2260: 20 73 65 65 6e 2e 0a 09 73 65 74 20 20 20 20 20 seen...set
2270: 20 20 70 61 74 68 20 7b 7d 0a 09 61 72 72 61 79 path {}..array
2280: 20 73 65 74 20 73 65 65 6e 20 7b 7d 0a 0a 09 77 set seen {}...w
2290: 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 20 20 20 20 hile {1} {..
22a0: 23 20 53 74 6f 70 20 73 65 61 72 63 68 69 6e 67 # Stop searching
22b0: 20 77 68 65 6e 20 77 65 20 68 61 76 65 20 73 65 when we have se
22c0: 65 6e 20 74 68 65 20 63 75 72 72 65 6e 74 20 6e en the current n
22d0: 6f 64 65 0a 09 20 20 20 20 23 20 61 6c 72 65 61 ode.. # alrea
22e0: 64 79 2c 20 74 68 65 20 63 69 72 63 6c 65 20 68 dy, the circle h
22f0: 61 73 20 62 65 65 6e 20 63 6c 6f 73 65 64 2e 0a as been closed..
2300: 09 20 20 20 20 69 66 20 7b 5b 69 6e 66 6f 20 65 . if {[info e
2310: 78 69 73 74 73 20 73 65 65 6e 28 24 73 74 61 72 xists seen($star
2320: 74 29 5d 7d 20 62 72 65 61 6b 0a 09 20 20 20 20 t)]} break..
2330: 6c 61 70 70 65 6e 64 20 70 61 74 68 20 24 73 74 lappend path $st
2340: 61 72 74 0a 09 20 20 20 20 73 65 74 20 73 65 65 art.. set see
2350: 6e 28 24 73 74 61 72 74 29 20 5b 65 78 70 72 20 n($start) [expr
2360: 7b 5b 6c 6c 65 6e 67 74 68 20 24 70 61 74 68 5d {[llength $path]
2370: 2d 31 7d 5d 0a 09 20 20 20 20 23 20 43 68 6f 6f -1}].. # Choo
2380: 73 65 20 61 72 62 69 74 72 61 72 79 20 70 72 65 se arbitrary pre
2390: 64 65 63 65 73 73 6f 72 0a 09 20 20 20 20 73 65 decessor.. se
23a0: 74 20 73 74 61 72 74 20 5b 6c 69 6e 64 65 78 20 t start [lindex
23b0: 5b 24 64 67 20 6e 6f 64 65 73 20 2d 69 6e 20 24 [$dg nodes -in $
23c0: 73 74 61 72 74 5d 20 30 5d 0a 09 7d 0a 0a 09 72 start] 0]..}...r
23d0: 65 74 75 72 6e 20 5b 73 74 72 75 63 74 3a 3a 6c eturn [struct::l
23e0: 69 73 74 20 72 65 76 65 72 73 65 20 5b 6c 72 61 ist reverse [lra
23f0: 6e 67 65 20 24 70 61 74 68 20 24 73 65 65 6e 28 nge $path $seen(
2400: 24 73 74 61 72 74 29 20 65 6e 64 5d 5d 0a 20 20 $start) end]].
2410: 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 42 72 }.. proc Br
2420: 65 61 6b 43 79 63 6c 65 20 7b 64 67 20 63 79 63 eakCycle {dg cyc
2430: 6c 65 7d 20 7b 0a 09 23 20 54 68 65 20 63 79 63 le} {..# The cyc
2440: 6c 65 20 77 65 20 68 61 76 65 20 67 6f 74 74 65 le we have gotte
2450: 6e 20 69 73 20 62 72 6f 6b 65 6e 20 62 79 20 62 n is broken by b
2460: 72 65 61 6b 69 6e 67 20 61 70 61 72 74 20 6f 6e reaking apart on
2470: 65 20 6f 72 0a 09 23 20 6d 6f 72 65 20 6f 66 20 e or..# more of
2480: 74 68 65 20 63 68 61 6e 67 65 73 65 74 73 20 69 the changesets i
2490: 6e 20 74 68 65 20 63 79 63 6c 65 2e 20 54 68 69 n the cycle. Thi
24a0: 73 20 63 61 75 73 65 73 20 75 73 20 74 6f 0a 09 s causes us to..
24b0: 23 20 63 72 65 61 74 65 20 6f 6e 65 20 6f 72 20 # create one or
24c0: 6d 6f 72 65 20 63 68 61 6e 67 65 73 65 74 73 20 more changesets
24d0: 77 68 69 63 68 20 61 72 65 20 74 6f 20 62 65 20 which are to be
24e0: 63 6f 6d 6d 69 74 74 65 64 2c 0a 09 23 20 61 64 committed,..# ad
24f0: 64 65 64 20 74 6f 20 74 68 65 20 67 72 61 70 68 ded to the graph
2500: 2c 20 65 74 63 2e 20 70 70 2e 0a 0a 09 23 20 4e , etc. pp....# N
2510: 4f 54 45 2f 54 4f 44 4f 2e 20 4d 6f 76 65 20 74 OTE/TODO. Move t
2520: 68 69 73 20 6d 61 70 20 6f 70 65 72 61 74 69 6f his map operatio
2530: 6e 20 74 6f 20 70 72 6f 6a 65 63 74 3a 3a 72 65 n to project::re
2540: 76 2c 20 61 73 20 74 79 70 65 6d 65 74 68 6f 64 v, as typemethod
2550: 2e 0a 09 73 65 74 20 63 70 72 69 6e 74 20 5b 70 ...set cprint [p
2560: 72 6f 6a 65 63 74 3a 3a 72 65 76 20 73 74 72 6c roject::rev strl
2570: 69 73 74 20 24 63 79 63 6c 65 5d 0a 0a 09 6c 61 ist $cycle]...la
2580: 70 70 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 6e ppend cycle [lin
2590: 64 65 78 20 24 63 79 63 6c 65 20 30 5d 20 5b 6c dex $cycle 0] [l
25a0: 69 6e 64 65 78 20 24 63 79 63 6c 65 20 31 5d 0a index $cycle 1].
25b0: 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 7b 7d .set bestlink {}
25c0: 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 65 20 7b ..set bestnode {
25d0: 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c 0a 09 20 }...foreach \..
25e0: 20 20 20 70 72 65 76 20 5b 6c 72 61 6e 67 65 20 prev [lrange
25f0: 24 63 79 63 6c 65 20 30 20 65 6e 64 2d 32 5d 20 $cycle 0 end-2]
2600: 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 6c 72 61 \.. cset [lra
2610: 6e 67 65 20 24 63 79 63 6c 65 20 31 20 65 6e 64 nge $cycle 1 end
2620: 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 78 74 20 -1] \.. next
2630: 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 32 [lrange $cycle 2
2640: 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 45 61 63 end] {....# Eac
2650: 68 20 74 72 69 70 6c 65 20 50 52 45 56 20 2d 3e h triple PREV ->
2660: 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 20 6f 66 CSET -> NEXT of
2670: 20 63 68 61 6e 67 65 73 65 74 73 2c 20 61 0a 09 changesets, a..
2680: 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 74 68 65 .# 'link' in the
2690: 20 63 79 63 6c 65 2c 20 69 73 20 61 6e 61 6c 79 cycle, is analy
26a0: 73 65 64 20 61 6e 64 20 74 68 65 20 62 65 73 74 sed and the best
26b0: 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e 20 77 68 ...# location wh
26c0: 65 72 65 20 74 6f 20 61 74 20 6c 65 61 73 74 20 ere to at least
26d0: 77 65 61 6b 65 6e 20 74 68 65 20 63 79 63 6c 65 weaken the cycle
26e0: 20 69 73 0a 09 09 23 20 63 68 6f 73 65 6e 20 66 is...# chosen f
26f0: 6f 72 20 66 75 72 74 68 65 72 20 70 72 6f 63 65 or further proce
2700: 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 20 6c 69 ssing.....set li
2710: 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 76 nk [project::rev
2720: 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 70 72 65 link %AUTO% $pre
2730: 76 20 24 63 73 65 74 20 24 6e 65 78 74 5d 0a 09 v $cset $next]..
2740: 09 69 66 20 7b 24 62 65 73 74 6c 69 6e 6b 20 65 .if {$bestlink e
2750: 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 20 73 65 q ""} {... se
2760: 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b t bestlink $link
2770: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6e ... set bestn
2780: 6f 64 65 20 24 63 73 65 74 0a 09 09 7d 20 65 6c ode $cset...} el
2790: 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 62 65 74 seif {[$link bet
27a0: 74 65 72 74 68 61 6e 20 24 62 65 73 74 6c 69 6e terthan $bestlin
27b0: 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 62 65 73 k]} {... $bes
27c0: 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 09 tlink destroy...
27d0: 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e 6b set bestlink
27e0: 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 $link... set
27f0: 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 0a bestnode $cset.
2800: 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 20 20 20 ..} else {...
2810: 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 $link destroy..
2820: 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c 6f 67 20 .}.. }...log
2830: 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 72 65 write 5 cyclebre
2840: 61 6b 65 72 20 22 42 72 65 61 6b 69 6e 67 20 63 aker "Breaking c
2850: 79 63 6c 65 20 28 24 63 70 72 69 6e 74 29 20 62 ycle ($cprint) b
2860: 79 20 73 70 6c 69 74 74 69 6e 67 20 63 68 61 6e y splitting chan
2870: 67 65 73 65 74 20 5b 24 62 65 73 74 6e 6f 64 65 geset [$bestnode
2880: 20 73 74 72 5d 22 0a 09 73 65 74 20 49 44 20 5b str]"..set ID [
2890: 24 62 65 73 74 6e 6f 64 65 20 69 64 5d 0a 09 4d $bestnode id]..M
28a0: 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d 62 ark $dg -${ID}-b
28b0: 65 66 6f 72 65 0a 0a 09 73 65 74 20 6e 65 77 63 efore...set newc
28c0: 73 65 74 73 20 5b 24 62 65 73 74 6c 69 6e 6b 20 sets [$bestlink
28d0: 62 72 65 61 6b 5d 0a 09 24 62 65 73 74 6c 69 6e break]..$bestlin
28e0: 6b 20 64 65 73 74 72 6f 79 0a 0a 20 20 20 20 20 k destroy..
28f0: 20 20 20 23 20 41 74 20 74 68 69 73 20 70 6f 69 # At this poi
2900: 6e 74 20 74 68 65 20 6f 6c 64 20 63 68 61 6e 67 nt the old chang
2910: 65 73 65 74 20 28 42 45 53 54 4e 4f 44 45 29 20 eset (BESTNODE)
2920: 69 73 20 67 6f 6e 65 0a 20 20 20 20 20 20 20 20 is gone.
2930: 23 20 61 6c 72 65 61 64 79 2e 20 57 65 20 72 65 # already. We re
2940: 6d 6f 76 65 20 69 74 20 66 72 6f 6d 20 74 68 65 move it from the
2950: 20 67 72 61 70 68 20 61 73 20 77 65 6c 6c 20 61 graph as well a
2960: 6e 64 20 74 68 65 6e 20 65 6e 74 65 72 0a 20 20 nd then enter.
2970: 20 20 20 20 20 20 23 20 74 68 65 20 66 72 61 67 # the frag
2980: 6d 65 6e 74 73 20 67 65 6e 65 72 61 74 65 64 20 ments generated
2990: 66 6f 72 20 69 74 2e 0a 0a 09 52 65 70 6c 61 63 for it....Replac
29a0: 65 20 24 64 67 20 24 62 65 73 74 6e 6f 64 65 20 e $dg $bestnode
29b0: 24 6e 65 77 63 73 65 74 73 0a 0a 09 4d 61 72 6b $newcsets...Mark
29c0: 20 24 64 67 20 2d 24 7b 49 44 7d 2d 61 66 74 65 $dg -${ID}-afte
29d0: 72 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a r..return. }.
29e0: 0a 20 20 20 20 23 20 54 4f 44 4f 3a 20 54 68 69 . # TODO: Thi
29f0: 73 20 73 68 6f 75 6c 64 20 62 65 20 61 20 67 72 s should be a gr
2a00: 61 70 68 20 6d 65 74 68 6f 64 2e 0a 20 20 20 20 aph method..
2a10: 70 72 6f 63 20 48 61 73 41 72 63 20 7b 64 67 20 proc HasArc {dg
2a20: 61 20 62 7d 20 7b 0a 09 23 38 2e 35 3a 20 72 65 a b} {..#8.5: re
2a30: 74 75 72 6e 20 5b 65 78 70 72 20 7b 24 62 20 69 turn [expr {$b i
2a40: 6e 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 n [$dg nodes -ou
2a50: 74 20 24 61 5d 7d 5d 0a 09 69 66 20 7b 5b 6c 73 t $a]}]..if {[ls
2a60: 65 61 72 63 68 20 2d 65 78 61 63 74 20 5b 24 64 earch -exact [$d
2a70: 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 61 5d g nodes -out $a]
2a80: 20 24 62 5d 20 3c 20 30 7d 20 7b 20 72 65 74 75 $b] < 0} { retu
2a90: 72 6e 20 30 20 7d 0a 09 72 65 74 75 72 6e 20 31 rn 0 }..return 1
2aa0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
2ab0: 20 4d 61 72 6b 20 7b 64 67 20 7b 73 75 66 66 69 Mark {dg {suffi
2ac0: 78 20 7b 7d 7d 20 7b 73 75 62 67 72 61 70 68 20 x {}} {subgraph
2ad0: 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 {}}} {..::variab
2ae0: 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 le mydotdestinat
2af0: 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 6f 74 64 ion..if {$mydotd
2b00: 65 73 74 69 6e 61 74 69 6f 6e 20 65 71 20 22 22 estination eq ""
2b10: 7d 20 72 65 74 75 72 6e 0a 09 3a 3a 76 61 72 69 } return..::vari
2b20: 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 able mydotprefix
2b30: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 ..::variable myd
2b40: 6f 74 69 64 0a 09 73 65 74 20 66 6e 61 6d 65 20 otid..set fname
2b50: 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f $mydotdestinatio
2b60: 6e 2f 24 7b 6d 79 64 6f 74 70 72 65 66 69 78 7d n/${mydotprefix}
2b70: 24 7b 6d 79 64 6f 74 69 64 7d 24 7b 73 75 66 66 ${mydotid}${suff
2b80: 69 78 7d 2e 64 6f 74 0a 09 66 69 6c 65 20 6d 6b ix}.dot..file mk
2b90: 64 69 72 20 5b 66 69 6c 65 20 64 69 72 6e 61 6d dir [file dirnam
2ba0: 65 20 24 66 6e 61 6d 65 5d 0a 09 64 6f 74 20 77 e $fname]..dot w
2bb0: 72 69 74 65 20 24 64 67 20 24 6d 79 64 6f 74 70 rite $dg $mydotp
2bc0: 72 65 66 69 78 24 73 75 66 66 69 78 20 24 66 6e refix$suffix $fn
2bd0: 61 6d 65 20 24 73 75 62 67 72 61 70 68 0a 09 69 ame $subgraph..i
2be0: 6e 63 72 20 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f ncr mydotid...lo
2bf0: 67 20 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 g write 5 cycleb
2c00: 72 65 61 6b 65 72 20 22 2e 64 6f 74 20 65 78 70 reaker ".dot exp
2c10: 6f 72 74 20 24 66 6e 61 6d 65 22 0a 09 72 65 74 ort $fname"..ret
2c20: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
2c30: 72 6f 63 20 52 65 70 6c 61 63 65 20 7b 64 67 20 roc Replace {dg
2c40: 6e 20 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 n replacements}
2c50: 7b 0a 09 23 20 4e 4f 54 45 2e 20 57 65 20 68 61 {..# NOTE. We ha
2c60: 76 65 20 74 6f 20 67 65 74 20 74 68 65 20 6c 69 ve to get the li
2c70: 73 74 20 6f 66 20 69 6e 63 6f 6d 69 6e 67 20 6e st of incoming n
2c80: 65 69 67 68 62 6f 75 72 73 20 61 6e 64 0a 09 23 eighbours and..#
2c90: 20 72 65 63 6f 6d 70 75 74 65 20 74 68 65 69 72 recompute their
2ca0: 20 73 75 63 63 65 73 73 6f 72 73 20 61 66 74 65 successors afte
2cb0: 72 20 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 20 r the new nodes
2cc0: 68 61 76 65 20 62 65 65 6e 0a 09 23 20 69 6e 73 have been..# ins
2cd0: 65 72 74 65 64 2e 20 54 68 65 69 72 20 6f 75 74 erted. Their out
2ce0: 67 6f 69 6e 67 20 61 72 63 73 20 77 69 6c 6c 20 going arcs will
2cf0: 6e 6f 77 20 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 now go to one or
2d00: 20 62 6f 74 68 20 6f 66 0a 09 23 20 74 68 65 20 both of..# the
2d10: 6e 65 77 20 6e 6f 64 65 73 2c 20 61 6e 64 20 6e new nodes, and n
2d20: 6f 74 20 72 65 64 6f 69 6e 67 20 74 68 65 6d 20 ot redoing them
2d30: 6d 61 79 20 63 61 75 73 65 20 75 73 20 74 6f 20 may cause us to
2d40: 66 6f 72 67 65 74 0a 09 23 20 63 69 72 63 6c 65 forget..# circle
2d50: 73 2c 20 6c 65 61 76 69 6e 67 20 74 68 65 6d 20 s, leaving them
2d60: 69 6e 2c 20 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 in, unbroken....
2d70: 73 65 74 20 70 72 65 20 5b 24 64 67 20 6e 6f 64 set pre [$dg nod
2d80: 65 73 20 2d 69 6e 20 24 6e 5d 0a 0a 20 20 20 20 es -in $n]..
2d90: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 64 65 6c $dg node del
2da0: 65 74 65 20 24 6e 0a 0a 09 66 6f 72 65 61 63 68 ete $n...foreach
2db0: 20 63 73 65 74 20 24 72 65 70 6c 61 63 65 6d 65 cset $replaceme
2dc0: 6e 74 73 20 7b 0a 09 20 20 20 20 24 64 67 20 6e nts {.. $dg n
2dd0: 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 74 ode insert $cset
2de0: 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 .. $dg node s
2df0: 65 74 20 20 20 20 24 63 73 65 74 20 74 69 6d 65 et $cset time
2e00: 72 61 6e 67 65 20 5b 24 63 73 65 74 20 74 69 6d range [$cset tim
2e10: 65 72 61 6e 67 65 5d 0a 09 20 20 20 20 24 64 67 erange].. $dg
2e20: 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 node set $cs
2e30: 65 74 20 6c 61 62 65 6c 20 20 20 20 20 5b 24 63 et label [$c
2e40: 73 65 74 20 73 74 72 5d 0a 09 20 20 20 20 24 64 set str].. $d
2e50: 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 g node set $c
2e60: 73 65 74 20 5f 5f 69 64 5f 5f 20 20 20 20 5b 24 set __id__ [$
2e70: 63 73 65 74 20 69 64 5d 0a 09 7d 0a 0a 09 66 6f cset id]..}...fo
2e80: 72 65 61 63 68 20 63 73 65 74 20 24 72 65 70 6c reach cset $repl
2e90: 61 63 65 6d 65 6e 74 73 20 7b 0a 09 20 20 20 20 acements {..
2ea0: 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 foreach succ [$c
2eb0: 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 set successors]
2ec0: 7b 0a 09 09 23 20 54 68 65 20 6e 65 77 20 63 68 {...# The new ch
2ed0: 61 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 angesets may hav
2ee0: 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f e dependencies o
2ef0: 75 74 73 69 64 65 20 6f 66 0a 09 09 23 20 74 68 utside of...# th
2f00: 65 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 e chosen set. Th
2f10: 65 73 65 20 61 72 65 20 69 67 6e 6f 72 65 64 0a ese are ignored.
2f20: 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 ..if {![$dg node
2f30: 20 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 exists $succ]}
2f40: 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 61 continue...$dg a
2f50: 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 rc insert $cset
2f60: 24 73 75 63 63 0a 09 09 69 66 20 7b 24 73 75 63 $succ...if {$suc
2f70: 63 20 65 71 20 24 63 73 65 74 7d 20 7b 0a 09 09 c eq $cset} {...
2f80: 20 20 20 20 74 72 6f 75 62 6c 65 20 69 6e 74 65 trouble inte
2f90: 72 6e 61 6c 20 22 53 65 6c 66 2d 72 65 66 65 72 rnal "Self-refer
2fa0: 65 6e 63 69 6e 67 20 63 68 61 6e 67 65 73 65 74 encing changeset
2fb0: 20 5b 24 63 73 65 74 20 73 74 72 5d 22 0a 09 09 [$cset str]"...
2fc0: 7d 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 66 6f 72 }.. }..}..for
2fd0: 65 61 63 68 20 63 73 65 74 20 24 70 72 65 20 7b each cset $pre {
2fe0: 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 .. foreach su
2ff0: 63 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 cc [$cset succes
3000: 73 6f 72 73 5d 20 7b 0a 09 09 23 20 4e 6f 74 65 sors] {...# Note
3010: 20 74 68 61 74 20 74 68 65 20 61 72 63 20 6d 61 that the arc ma
3020: 79 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 20 y already exist
3030: 69 6e 20 74 68 65 20 67 72 61 70 68 2e 20 49 66 in the graph. If
3040: 0a 09 09 23 20 73 6f 20 69 67 6e 6f 72 65 20 69 ...# so ignore i
3050: 74 2e 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 t. The new chang
3060: 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 0a 09 esets may have..
3070: 09 23 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 .# dependencies
3080: 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 20 63 outside of the c
3090: 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 hosen set. These
30a0: 20 61 72 65 0a 09 09 23 20 69 67 6e 6f 72 65 64 are...# ignored
30b0: 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 ...if {![$dg nod
30c0: 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d e exists $succ]}
30d0: 20 63 6f 6e 74 69 6e 75 65 0a 09 09 69 66 20 7b continue...if {
30e0: 5b 48 61 73 41 72 63 20 24 64 67 20 24 63 73 65 [HasArc $dg $cse
30f0: 74 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e t $succ]} contin
3100: 75 65 3b 23 20 54 4f 44 4f 20 73 68 6f 75 6c 64 ue;# TODO should
3110: 20 62 65 20 67 72 61 70 68 20 6d 65 74 68 6f 64 be graph method
3120: 2e 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 65 ....$dg arc inse
3130: 72 74 20 24 63 73 65 74 20 24 73 75 63 63 0a 09 rt $cset $succ..
3140: 20 20 20 20 7d 0a 09 7d 0a 0a 09 72 65 74 75 72 }..}...retur
3150: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 n. }.. # #
3160: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
3170: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
3180: 23 23 23 23 0a 20 20 20 20 23 23 20 43 61 6c 6c ####. ## Call
3190: 62 61 63 6b 20 69 6e 76 6f 6b 61 74 69 6f 6e 20 back invokation
31a0: 2e 2e 2e 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 ..... proc Pr
31b0: 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 7b 0a eHook {graph} {.
31c0: 09 23 20 47 69 76 65 20 74 68 65 20 75 73 65 72 .# Give the user
31d0: 20 6f 66 20 74 68 65 20 63 79 63 6c 65 20 62 72 of the cycle br
31e0: 65 61 6b 65 72 20 74 68 65 20 6f 70 70 6f 72 74 eaker the opport
31f0: 75 6e 69 74 79 20 74 6f 20 77 6f 72 6b 0a 09 23 unity to work..#
3200: 20 77 69 74 68 20 74 68 65 20 67 72 61 70 68 20 with the graph
3210: 62 65 74 77 65 65 6e 20 73 65 74 75 70 20 61 6e between setup an
3220: 64 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a d consummation..
3230: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 70 ..::variable myp
3240: 72 65 63 6d 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 recmd..if {![lle
3250: 6e 67 74 68 20 24 6d 79 70 72 65 63 6d 64 5d 7d ngth $myprecmd]}
3260: 20 72 65 74 75 72 6e 0a 0a 09 75 70 6c 65 76 65 return...upleve
3270: 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 6d l #0 [linsert $m
3280: 79 70 72 65 63 6d 64 20 65 6e 64 20 24 67 72 61 yprecmd end $gra
3290: 70 68 5d 0a 09 4d 61 72 6b 20 24 67 72 61 70 68 ph]..Mark $graph
32a0: 20 2d 70 72 65 2d 64 6f 6e 65 0a 09 72 65 74 75 -pre-done..retu
32b0: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
32c0: 6f 63 20 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b oc ProcessedHook
32d0: 20 7b 64 67 20 63 73 65 74 20 70 6f 73 7d 20 7b {dg cset pos} {
32e0: 0a 09 23 20 47 69 76 65 20 74 68 65 20 75 73 65 ..# Give the use
32f0: 72 20 6f 66 20 74 68 65 20 63 79 63 6c 65 20 62 r of the cycle b
3300: 72 65 61 6b 65 72 20 74 68 65 20 6f 70 70 6f 72 reaker the oppor
3310: 74 75 6e 69 74 79 20 74 6f 20 77 6f 72 6b 0a 09 tunity to work..
3320: 23 20 77 69 74 68 20 74 68 65 20 63 68 61 6e 67 # with the chang
3330: 65 73 65 74 20 62 65 66 6f 72 65 20 69 74 20 69 eset before it i
3340: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 s removed from t
3350: 68 65 20 67 72 61 70 68 2e 0a 0a 09 3a 3a 76 61 he graph....::va
3360: 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 riable mysavecmd
3370: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
3380: 24 6d 79 73 61 76 65 63 6d 64 5d 7d 20 72 65 74 $mysavecmd]} ret
3390: 75 72 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 urn...uplevel #0
33a0: 20 5b 6c 69 6e 73 65 72 74 20 24 6d 79 73 61 76 [linsert $mysav
33b0: 65 63 6d 64 20 65 6e 64 20 24 64 67 20 24 70 6f ecmd end $dg $po
33c0: 73 20 24 63 73 65 74 5d 0a 09 72 65 74 75 72 6e s $cset]..return
33d0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
33e0: 20 42 72 65 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 BreakCycleHook
33f0: 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 43 61 6c {graph} {..# Cal
3400: 6c 20 6f 75 74 20 74 6f 20 74 68 65 20 63 68 6f l out to the cho
3410: 73 65 6e 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f sen algorithm fo
3420: 72 20 63 79 63 6c 65 20 62 72 65 61 6b 69 6e 67 r cycle breaking
3430: 2e 20 46 69 6e 64 69 6e 67 0a 09 23 20 61 20 63 . Finding..# a c
3440: 79 63 6c 65 20 69 66 20 6e 6f 20 62 72 65 61 6b ycle if no break
3450: 65 72 20 77 61 73 20 63 68 6f 73 65 6e 20 69 73 er was chosen is
3460: 20 61 6e 20 65 72 72 6f 72 2e 0a 0a 09 3a 3a 76 an error....::v
3470: 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 ariable mybreakc
3480: 6d 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 md..if {![llengt
3490: 68 20 24 6d 79 62 72 65 61 6b 63 6d 64 5d 7d 20 h $mybreakcmd]}
34a0: 7b 0a 09 20 20 20 20 74 72 6f 75 62 6c 65 20 66 {.. trouble f
34b0: 61 74 61 6c 20 22 46 6f 75 6e 64 20 61 20 63 79 atal "Found a cy
34c0: 63 6c 65 2c 20 65 78 70 65 63 74 69 6e 67 20 6e cle, expecting n
34d0: 6f 6e 65 2e 22 0a 09 20 20 20 20 65 78 69 74 20 one.".. exit
34e0: 31 0a 09 7d 0a 0a 09 75 70 6c 65 76 65 6c 20 23 1..}...uplevel #
34f0: 30 20 5b 6c 69 6e 73 65 72 74 20 24 6d 79 62 72 0 [linsert $mybr
3500: 65 61 6b 63 6d 64 20 65 6e 64 20 24 67 72 61 70 eakcmd end $grap
3510: 68 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d h]..return. }
3520: 0a 0a 20 20 20 20 70 72 6f 63 20 43 6c 65 61 72 .. proc Clear
3530: 48 6f 6f 6b 73 20 7b 7d 20 7b 0a 09 3a 3a 76 61 Hooks {} {..::va
3540: 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 20 riable myprecmd
3550: 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 62 6c 65 {}..::variable
3560: 20 6d 79 73 61 76 65 63 6d 64 20 20 7b 7d 0a 09 mysavecmd {}..
3570: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 ::variable mybre
3580: 61 6b 63 6d 64 20 7b 7d 0a 09 72 65 74 75 72 6e akcmd {}..return
3590: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 . }.. # #
35a0: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
35b0: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
35c0: 23 23 23 0a 0a 20 20 20 20 74 79 70 65 76 61 72 ###.. typevar
35d0: 69 61 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 iable myat
35e0: 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 66 6f 0 ; # Counter fo
35f0: 72 20 63 6f 6d 6d 69 74 20 69 64 73 20 66 6f 72 r commit ids for
3600: 20 74 68 65 0a 09 09 09 20 20 20 20 20 20 20 23 the.... #
3610: 20 63 68 61 6e 67 65 73 65 74 73 2e 0a 20 20 20 changesets..
3620: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3630: 62 6f 74 74 6f 6d 20 7b 7d 20 3b 20 23 20 4c 69 bottom {} ; # Li
3640: 73 74 20 6f 66 20 74 68 65 20 63 61 6e 64 69 64 st of the candid
3650: 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 0a 09 09 ate nodes for...
3660: 09 20 20 20 20 20 20 20 23 20 63 6f 6d 6d 69 74 . # commit
3670: 74 69 6e 67 2e 0a 0a 20 20 20 20 74 79 70 65 76 ting... typev
3680: 61 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 ariable myprecmd
3690: 20 20 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 {} ; # Callba
36a0: 63 6b 2c 20 63 68 61 6e 67 65 20 67 72 61 70 68 ck, change graph
36b0: 20 62 65 66 6f 72 65 20 77 61 6c 6b 2e 0a 20 20 before walk..
36c0: 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d typevariable m
36d0: 79 73 61 76 65 63 6d 64 20 20 7b 7d 20 3b 20 23 ysavecmd {} ; #
36e0: 20 43 61 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 Callback, for e
36f0: 61 63 68 20 70 72 6f 63 65 73 73 65 64 20 6e 6f ach processed no
3700: 64 65 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 de.. typevari
3710: 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 able mybreakcmd
3720: 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b 2c {} ; # Callback,
3730: 20 66 6f 72 20 65 61 63 68 20 66 6f 75 6e 64 20 for each found
3740: 63 79 63 6c 65 2e 0a 0a 20 20 20 20 74 79 70 65 cycle... type
3750: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 variable mydotde
3760: 73 74 69 6e 61 74 69 6f 6e 20 7b 7d 20 3b 20 23 stination {} ; #
3770: 20 44 65 73 74 69 6e 61 74 69 6f 6e 20 64 69 72 Destination dir
3780: 65 63 74 6f 72 79 20 66 6f 72 20 74 68 65 0a 09 ectory for the..
3790: 09 09 09 20 20 20 20 20 20 20 23 20 67 65 6e 65 ... # gene
37a0: 72 61 74 65 64 20 2e 64 6f 74 20 66 69 6c 65 73 rated .dot files
37b0: 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 62 .. typevariab
37c0: 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 20 20 le mydotprefix
37d0: 20 20 20 20 7b 7d 20 3b 20 23 20 50 72 65 66 69 {} ; # Prefi
37e0: 78 20 66 6f 72 20 64 6f 74 20 66 69 6c 65 73 20 x for dot files
37f0: 77 68 65 6e 0a 09 09 09 09 20 20 20 20 20 20 20 when.....
3800: 23 20 65 78 70 6f 72 74 69 6e 67 20 74 68 65 20 # exporting the
3810: 67 72 61 70 68 73 2e 0a 20 20 20 20 74 79 70 65 graphs.. type
3820: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 variable mydotid
3830: 20 20 20 20 20 20 20 20 20 20 20 30 20 3b 20 23 0 ; #
3840: 20 43 6f 75 6e 74 65 72 20 66 6f 72 20 64 6f 74 Counter for dot
3850: 20 66 69 6c 65 20 6e 61 6d 65 0a 09 09 09 09 20 file name.....
3860: 20 20 20 20 20 20 23 20 67 65 6e 65 72 61 74 69 # generati
3870: 6f 6e 2e 0a 0a 20 20 20 20 23 20 23 20 23 23 20 on... # # ##
3880: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
3890: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
38a0: 0a 20 20 20 20 23 23 20 43 6f 6e 66 69 67 75 72 . ## Configur
38b0: 61 74 69 6f 6e 0a 0a 20 20 20 20 70 72 61 67 6d ation.. pragm
38c0: 61 20 2d 68 61 73 69 6e 73 74 61 6e 63 65 73 20 a -hasinstances
38d0: 20 20 6e 6f 20 3b 20 23 20 73 69 6e 67 6c 65 74 no ; # singlet
38e0: 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 20 2d 68 on. pragma -h
38f0: 61 73 74 79 70 65 69 6e 66 6f 20 20 20 20 6e 6f astypeinfo no
3900: 20 3b 20 23 20 6e 6f 20 69 6e 74 72 6f 73 70 65 ; # no introspe
3910: 63 74 69 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 ction. pragma
3920: 20 2d 68 61 73 74 79 70 65 64 65 73 74 72 6f 79 -hastypedestroy
3930: 20 6e 6f 20 3b 20 23 20 69 6d 6d 6f 72 74 61 6c no ; # immortal
3940: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
3950: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
3960: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 7d 0a #############.}.
3970: 0a 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 .namespace eval
3980: 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d ::vc::fossil::im
3990: 70 6f 72 74 3a 3a 63 76 73 20 7b 0a 20 20 20 20 port::cvs {.
39a0: 6e 61 6d 65 73 70 61 63 65 20 65 78 70 6f 72 74 namespace export
39b0: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 cyclebreaker.
39c0: 20 20 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c namespace eval
39d0: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 0a cyclebreaker {.
39e0: 09 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 .namespace eval
39f0: 70 72 6f 6a 65 63 74 20 7b 0a 09 20 20 20 20 6e project {.. n
3a00: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
3a10: 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d ::vc::fossil::im
3a20: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 port::cvs::proje
3a30: 63 74 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d ct::rev.. nam
3a40: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3a50: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
3a60: 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 rt::cvs::project
3a70: 3a 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 ::revlink..}..na
3a80: 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a mespace import :
3a90: 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 :vc::tools::misc
3aa0: 3a 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 ::*..namespace i
3ab0: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c mport ::vc::tool
3ac0: 73 3a 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 s::log..namespac
3ad0: 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 e import ::vc::t
3ae0: 6f 6f 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a 09 6e ools::trouble..n
3af0: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
3b00: 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 ::vc::tools::dot
3b10: 0a 09 6c 6f 67 20 72 65 67 69 73 74 65 72 20 63 ..log register c
3b20: 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 yclebreaker.
3b30: 7d 0a 7d 0a 0a 23 20 23 20 23 23 20 23 23 23 20 }.}..# # ## ###
3b40: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
3b50: 23 23 23 23 23 23 23 23 23 23 23 23 20 23 23 23 ############ ###
3b60: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
3b70: 23 23 0a 23 23 20 52 65 61 64 79 0a 0a 70 61 63 ##.## Ready..pac
3b80: 6b 61 67 65 20 70 72 6f 76 69 64 65 20 76 63 3a kage provide vc:
3b90: 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a :fossil::import:
3ba0: 3a 63 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b :cvs::cyclebreak
3bb0: 65 72 20 31 2e 30 0a 72 65 74 75 72 6e 0a er 1.0.return.