Artifact bc82f06795a318e37db3dbc81bec52ada8807c23:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[97b4405ecf]
- Extended cycle breaker with debug facility allowing the user to watch the neighbourhood of specific changesets during the traversal. Extended label information, highlighting of the nodes of interest. Tweaked log output a bit.
by
aku on
2007-11-25 07:35: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 77 61 74 63 68 20 7b 69 64 7d 20 thod watch {id}
0820: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 {..::variable my
0830: 77 61 74 63 68 69 64 73 0a 09 6c 61 70 70 65 6e watchids..lappen
0840: 64 20 6d 79 77 61 74 63 68 69 64 73 20 24 69 64 d mywatchids $id
0850: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 . }.. type
0860: 6d 65 74 68 6f 64 20 64 6f 74 20 7b 6c 61 62 65 method dot {labe
0870: 6c 20 63 68 61 6e 67 65 73 65 74 73 7d 20 7b 0a l changesets} {.
0880: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f .::variable mydo
0890: 74 70 72 65 66 69 78 20 24 6c 61 62 65 6c 0a 09 tprefix $label..
08a0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 ::variable mydot
08b0: 69 64 20 20 20 20 20 30 0a 0a 09 73 65 74 20 64 id 0...set d
08c0: 67 20 5b 53 65 74 75 70 20 24 63 68 61 6e 67 65 g [Setup $change
08d0: 73 65 74 73 20 30 5d 0a 09 4d 61 72 6b 20 24 64 sets 0]..Mark $d
08e0: 67 0a 09 24 64 67 20 64 65 73 74 72 6f 79 0a 09 g..$dg destroy..
08f0: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
0900: 20 20 74 79 70 65 6d 65 74 68 6f 64 20 6d 61 72 typemethod mar
0910: 6b 20 7b 67 72 61 70 68 20 73 75 66 66 69 78 20 k {graph suffix
0920: 7b 73 75 62 67 72 61 70 68 20 7b 7d 7d 7d 20 7b {subgraph {}}} {
0930: 0a 09 4d 61 72 6b 20 24 67 72 61 70 68 20 24 73 ..Mark $graph $s
0940: 75 66 66 69 78 20 24 73 75 62 67 72 61 70 68 0a uffix $subgraph.
0950: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
0960: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
0970: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
0980: 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 ##########..
0990: 74 79 70 65 6d 65 74 68 6f 64 20 72 75 6e 20 7b typemethod run {
09a0: 6c 61 62 65 6c 20 63 68 61 6e 67 65 73 65 74 63 label changesetc
09b0: 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c md} {..::variabl
09c0: 65 20 6d 79 61 74 20 20 20 20 20 20 20 20 30 0a e myat 0.
09d0: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f .::variable mydo
09e0: 74 70 72 65 66 69 78 20 24 6c 61 62 65 6c 0a 09 tprefix $label..
09f0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 ::variable mydot
0a00: 69 64 20 20 20 20 20 30 0a 0a 09 23 20 57 65 20 id 0...# We
0a10: 63 72 65 61 74 65 20 61 20 67 72 61 70 68 20 6f create a graph o
0a20: 66 20 74 68 65 20 72 65 76 69 73 69 6f 6e 20 63 f the revision c
0a30: 68 61 6e 67 65 73 65 74 73 2c 20 75 73 69 6e 67 hangesets, using
0a40: 20 74 68 65 20 66 69 6c 65 0a 09 23 20 6c 65 76 the file..# lev
0a50: 65 6c 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 el dependencies
0a60: 74 6f 20 63 6f 6e 73 74 72 75 63 74 20 61 20 66 to construct a f
0a70: 69 72 73 74 20 61 70 70 72 6f 78 69 6d 61 74 69 irst approximati
0a80: 6f 6e 20 6f 66 20 74 68 65 0a 09 23 20 64 65 70 on of the..# dep
0a90: 65 6e 64 65 6e 63 69 65 73 20 61 74 20 74 68 65 endencies at the
0aa0: 20 70 72 6f 6a 65 63 74 20 6c 65 76 65 6c 2e 20 project level.
0ab0: 54 68 65 6e 20 77 65 20 6c 6f 6f 6b 20 66 6f 72 Then we look for
0ac0: 20 63 79 63 6c 65 73 0a 09 23 20 69 6e 20 74 68 cycles..# in th
0ad0: 61 74 20 67 72 61 70 68 20 61 6e 64 20 62 72 65 at graph and bre
0ae0: 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 20 31 2e 20 ak them....# 1.
0af0: 43 72 65 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 Create nodes for
0b00: 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 all relevant ch
0b10: 61 6e 67 65 73 65 74 73 20 61 6e 64 20 61 20 6d angesets and a m
0b20: 61 70 70 69 6e 67 0a 09 23 20 20 20 20 66 72 6f apping..# fro
0b30: 6d 20 74 68 65 20 72 65 76 69 73 69 6f 6e 73 20 m the revisions
0b40: 74 6f 20 74 68 65 69 72 20 63 68 61 6e 67 65 73 to their changes
0b50: 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a 09 73 65 74 ets/nodes....set
0b60: 20 63 68 61 6e 67 65 73 65 74 73 20 5b 75 70 6c changesets [upl
0b70: 65 76 65 6c 20 23 30 20 24 63 68 61 6e 67 65 73 evel #0 $changes
0b80: 65 74 63 6d 64 5d 0a 09 73 65 74 20 64 67 20 5b etcmd]..set dg [
0b90: 53 65 74 75 70 20 24 63 68 61 6e 67 65 73 65 74 Setup $changeset
0ba0: 73 5d 0a 0a 09 23 20 33 2e 20 4c 61 73 74 6c 79 s]...# 3. Lastly
0bb0: 20 77 65 20 69 74 65 72 61 74 65 20 74 68 65 20 we iterate the
0bc0: 67 72 61 70 68 20 74 6f 70 6f 6c 6f 67 69 63 61 graph topologica
0bd0: 6c 6c 79 2e 20 57 65 20 6d 61 72 6b 20 6f 66 66 lly. We mark off
0be0: 0a 09 23 20 20 20 20 74 68 65 20 6e 6f 64 65 73 ..# the nodes
0bf0: 20 77 68 69 63 68 20 68 61 76 65 20 6e 6f 20 70 which have no p
0c00: 72 65 64 65 63 65 73 73 6f 72 73 2c 20 69 6e 20 redecessors, in
0c10: 6f 72 64 65 72 20 66 72 6f 6d 0a 09 23 20 20 20 order from..#
0c20: 20 6f 6c 64 65 73 74 20 74 6f 20 79 6f 75 6e 67 oldest to young
0c30: 65 73 74 2c 20 73 61 76 69 6e 67 20 61 6e 64 20 est, saving and
0c40: 72 65 6d 6f 76 69 6e 67 20 64 65 70 65 6e 64 65 removing depende
0c50: 6e 63 69 65 73 2e 20 49 66 0a 09 23 20 20 20 20 ncies. If..#
0c60: 77 65 20 66 69 6e 64 20 6e 6f 20 6e 6f 64 65 73 we find no nodes
0c70: 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 without predece
0c80: 73 73 6f 72 73 20 77 65 20 68 61 76 65 20 61 20 ssors we have a
0c90: 63 79 63 6c 65 2c 0a 09 23 20 20 20 20 61 6e 64 cycle,..# and
0ca0: 20 77 6f 72 6b 20 6f 6e 20 62 72 65 61 6b 69 6e work on breakin
0cb0: 67 20 69 74 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 g it....log writ
0cc0: 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 3 cyclebreaker
0cd0: 20 7b 54 72 61 76 65 72 73 65 20 63 68 61 6e 67 {Traverse chang
0ce0: 65 73 65 74 73 7d 0a 0a 09 49 6e 69 74 69 61 6c esets}...Initial
0cf0: 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 24 64 izeCandidates $d
0d00: 67 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 g..while {1} {..
0d10: 20 20 20 20 77 68 69 6c 65 20 7b 5b 57 69 74 68 while {[With
0d20: 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 24 outPredecessor $
0d30: 64 67 20 6e 5d 7d 20 7b 0a 09 09 4d 61 72 6b 57 dg n]} {...MarkW
0d40: 61 74 63 68 20 24 64 67 0a 09 09 50 72 6f 63 65 atch $dg...Proce
0d50: 73 73 65 64 48 6f 6f 6b 20 24 64 67 20 24 6e 20 ssedHook $dg $n
0d60: 24 6d 79 61 74 0a 09 09 24 64 67 20 6e 6f 64 65 $myat...$dg node
0d70: 20 64 65 6c 65 74 65 20 24 6e 0a 09 09 69 6e 63 delete $n...inc
0d80: 72 20 6d 79 61 74 0a 09 09 53 68 6f 77 50 65 6e r myat...ShowPen
0d90: 64 69 6e 67 4e 6f 64 65 73 0a 09 20 20 20 20 7d dingNodes.. }
0da0: 0a 0a 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c 65 ... if {![lle
0db0: 6e 67 74 68 20 5b 64 67 20 6e 6f 64 65 73 5d 5d ngth [dg nodes]]
0dc0: 7d 20 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 72 } break... Br
0dd0: 65 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 20 eakCycleHook
0de0: 20 20 20 24 64 67 0a 09 20 20 20 20 49 6e 69 74 $dg.. Init
0df0: 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 ializeCandidates
0e00: 20 24 64 67 0a 09 20 20 20 20 4d 61 72 6b 57 61 $dg.. MarkWa
0e10: 74 63 68 20 20 20 20 20 20 20 20 20 20 20 20 24 tch $
0e20: 64 67 0a 09 7d 0a 0a 09 24 64 67 20 64 65 73 74 dg..}...$dg dest
0e30: 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 roy...log write
0e40: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 44 3 cyclebreaker D
0e50: 6f 6e 65 2e 0a 09 43 6c 65 61 72 48 6f 6f 6b 73 one...ClearHooks
0e60: 0a 0a 09 23 20 52 65 72 65 61 64 20 74 68 65 20 ...# Reread the
0e70: 67 72 61 70 68 20 61 6e 64 20 64 75 6d 70 20 69 graph and dump i
0e80: 74 73 20 66 69 6e 61 6c 20 66 6f 72 6d 2c 20 69 ts final form, i
0e90: 66 20 67 72 61 70 68 20 65 78 70 6f 72 74 0a 09 f graph export..
0ea0: 23 20 77 61 73 20 61 63 74 69 76 61 74 65 64 2e # was activated.
0eb0: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
0ec0: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 dotdestination..
0ed0: 69 66 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e if {$mydotdestin
0ee0: 61 74 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 ation eq ""} ret
0ef0: 75 72 6e 0a 0a 09 73 65 74 20 20 20 64 67 20 5b urn...set dg [
0f00: 53 65 74 75 70 20 5b 75 70 6c 65 76 65 6c 20 23 Setup [uplevel #
0f10: 30 20 24 63 68 61 6e 67 65 73 65 74 63 6d 64 5d 0 $changesetcmd]
0f20: 20 30 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 64 0]..Mark $dg -d
0f30: 6f 6e 65 0a 09 24 64 67 20 64 65 73 74 72 6f 79 one..$dg destroy
0f40: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
0f50: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
0f60: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
0f70: 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 ###########..
0f80: 20 74 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 typemethod brea
0f90: 6b 2d 73 65 67 6d 65 6e 74 20 7b 67 72 61 70 68 k-segment {graph
0fa0: 7d 20 7b 0a 09 42 72 65 61 6b 53 65 67 6d 65 6e } {..BreakSegmen
0fb0: 74 20 24 67 72 61 70 68 20 24 70 61 74 68 20 22 t $graph $path "
0fc0: 73 65 67 6d 65 6e 74 20 28 5b 70 72 6f 6a 65 63 segment ([projec
0fd0: 74 3a 3a 72 65 76 20 73 74 72 6c 69 73 74 20 24 t::rev strlist $
0fe0: 70 61 74 68 5d 29 22 0a 09 72 65 74 75 72 6e 0a path])"..return.
0ff0: 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d }.. typem
1000: 65 74 68 6f 64 20 62 72 65 61 6b 20 7b 67 72 61 ethod break {gra
1010: 70 68 7d 20 7b 0a 09 73 65 74 20 63 79 63 6c 65 ph} {..set cycle
1020: 20 5b 46 69 6e 64 43 79 63 6c 65 20 24 67 72 61 [FindCycle $gra
1030: 70 68 5d 0a 09 73 65 74 20 6c 61 62 65 6c 20 22 ph]..set label "
1040: 63 79 63 6c 65 20 28 5b 70 72 6f 6a 65 63 74 3a cycle ([project:
1050: 3a 72 65 76 20 73 74 72 6c 69 73 74 20 24 63 79 :rev strlist $cy
1060: 63 6c 65 5d 29 22 0a 0a 09 23 20 4e 4f 54 45 3a cle])"...# NOTE:
1070: 20 63 76 73 32 73 76 6e 20 75 73 65 73 20 74 68 cvs2svn uses th
1080: 65 20 73 65 71 75 65 6e 63 65 20 22 65 6e 64 2d e sequence "end-
1090: 31 2c 20 63 79 63 6c 65 2c 20 30 22 20 74 6f 20 1, cycle, 0" to
10a0: 63 72 65 61 74 65 0a 09 23 20 20 20 20 20 20 20 create..#
10b0: 74 68 65 20 70 61 74 68 20 66 72 6f 6d 20 74 68 the path from th
10c0: 65 20 63 79 63 6c 65 2e 20 54 68 65 20 6f 6e 6c e cycle. The onl
10d0: 79 20 65 66 66 65 63 74 20 49 20 63 61 6e 20 73 y effect I can s
10e0: 65 65 20 69 73 0a 09 23 20 20 20 20 20 20 20 74 ee is..# t
10f0: 68 61 74 20 74 68 69 73 20 63 61 75 73 65 73 20 hat this causes
1100: 74 68 65 20 6c 69 6e 6b 2d 74 72 69 70 6c 65 73 the link-triples
1110: 20 74 6f 20 62 65 20 67 65 6e 65 72 61 74 65 64 to be generated
1120: 20 69 6e 20 61 0a 09 23 20 20 20 20 20 20 20 73 in a..# s
1130: 69 67 68 74 6c 79 20 64 69 66 66 65 72 65 6e 74 ightly different
1140: 20 6f 72 64 65 72 2c 20 69 2e 65 2e 20 6f 6e 65 order, i.e. one
1150: 20 6c 69 6e 6b 20 72 6f 74 61 74 65 64 20 74 6f link rotated to
1160: 20 74 68 65 0a 09 23 20 20 20 20 20 20 20 72 69 the..# ri
1170: 67 68 74 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 ght. This should
1180: 20 68 61 76 65 20 6e 6f 20 65 66 66 65 63 74 20 have no effect
1190: 6f 6e 20 74 68 65 20 73 65 61 72 63 68 20 66 6f on the search fo
11a0: 72 0a 09 23 20 20 20 20 20 20 20 74 68 65 20 62 r..# the b
11b0: 65 73 74 20 6f 66 20 61 6c 6c 2e 0a 0a 09 6c 61 est of all....la
11c0: 70 70 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 6e ppend cycle [lin
11d0: 64 65 78 20 24 63 79 63 6c 65 20 30 5d 20 5b 6c dex $cycle 0] [l
11e0: 69 6e 64 65 78 20 24 63 79 63 6c 65 20 31 5d 0a index $cycle 1].
11f0: 09 42 72 65 61 6b 53 65 67 6d 65 6e 74 20 24 67 .BreakSegment $g
1200: 72 61 70 68 20 24 63 79 63 6c 65 20 24 6c 61 62 raph $cycle $lab
1210: 65 6c 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d el..return. }
1220: 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 .. typemethod
1230: 20 72 65 70 6c 61 63 65 20 7b 67 72 61 70 68 20 replace {graph
1240: 6e 20 72 65 70 6c 61 63 65 6d 65 6e 74 73 7d 20 n replacements}
1250: 7b 0a 09 52 65 70 6c 61 63 65 20 24 67 72 61 70 {..Replace $grap
1260: 68 20 24 6e 20 24 72 65 70 6c 61 63 65 6d 65 6e h $n $replacemen
1270: 74 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d ts..return. }
1280: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
1290: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
12a0: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 #############.
12b0: 20 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d 65 ## Internal me
12c0: 74 68 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 20 thods.. proc
12d0: 53 65 74 75 70 20 7b 63 68 61 6e 67 65 73 65 74 Setup {changeset
12e0: 73 20 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 66 s {log 1}} {..if
12f0: 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c {$log} {.. l
1300: 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 og write 3 cycle
1310: 62 72 65 61 6b 65 72 20 22 43 72 65 61 74 69 6e breaker "Creatin
1320: 67 20 67 72 61 70 68 20 6f 66 20 63 68 61 6e 67 g graph of chang
1330: 65 73 65 74 73 22 0a 09 7d 0a 0a 09 73 65 74 20 esets"..}...set
1340: 64 67 20 5b 73 74 72 75 63 74 3a 3a 67 72 61 70 dg [struct::grap
1350: 68 20 64 67 5d 0a 0a 09 66 6f 72 65 61 63 68 20 h dg]...foreach
1360: 63 73 65 74 20 24 63 68 61 6e 67 65 73 65 74 73 cset $changesets
1370: 20 7b 0a 09 20 20 20 20 73 65 74 20 74 72 20 5b {.. set tr [
1380: 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d $cset timerange]
1390: 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 69 .. $dg node i
13a0: 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 20 nsert $cset..
13b0: 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 $dg node set
13c0: 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 $cset timerange
13d0: 20 24 74 72 0a 09 20 20 20 20 24 64 67 20 6e 6f $tr.. $dg no
13e0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
13f0: 6c 61 62 65 6c 20 20 20 20 20 22 5b 24 63 73 65 label "[$cse
1400: 74 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e 20 5b t str]\\n[join [
1410: 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d 61 70 struct::list map
1420: 20 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 66 6f $tr {::clock fo
1430: 72 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 0a 09 rmat}] "\\n"]"..
1440: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
1450: 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f 5f $cset __id__
1460: 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a 09 [$cset id]..
1470: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
1480: 20 20 20 20 24 63 73 65 74 20 73 68 61 70 65 20 $cset shape
1490: 20 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 73 65 [expr {[$cse
14a0: 74 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 09 09 t bysymbol].....
14b0: 09 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 65 22 .. ? "ellipse"
14c0: 0a 09 09 09 09 09 09 20 20 20 3a 20 22 62 6f 78 ....... : "box
14d0: 22 7d 5d 0a 09 7d 0a 0a 09 69 66 20 7b 24 6c 6f "}]..}...if {$lo
14e0: 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 g} {.. log wr
14f0: 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b ite 3 cyclebreak
1500: 65 72 20 22 48 61 73 20 5b 6e 73 70 20 5b 6c 6c er "Has [nsp [ll
1510: 65 6e 67 74 68 20 24 63 68 61 6e 67 65 73 65 74 ength $changeset
1520: 73 5d 20 63 68 61 6e 67 65 73 65 74 5d 22 0a 09 s] changeset]"..
1530: 7d 0a 0a 09 23 20 32 2e 20 46 69 6e 64 20 66 6f }...# 2. Find fo
1540: 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 r all relevant c
1550: 68 61 6e 67 65 73 65 74 20 74 68 65 69 72 20 72 hangeset their r
1560: 65 76 69 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 evisions and the
1570: 69 72 0a 09 23 20 20 20 20 64 65 70 65 6e 64 65 ir..# depende
1580: 6e 63 69 65 73 2e 20 4d 61 70 20 74 68 65 20 6c ncies. Map the l
1590: 61 74 74 65 72 20 62 61 63 6b 20 74 6f 20 63 68 atter back to ch
15a0: 61 6e 67 65 73 65 74 73 20 61 6e 64 0a 09 23 20 angesets and..#
15b0: 20 20 20 63 6f 6e 73 74 72 75 63 74 20 74 68 65 construct the
15c0: 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 corresponding a
15d0: 72 63 73 2e 0a 0a 09 66 6f 72 65 61 63 68 20 63 rcs....foreach c
15e0: 73 65 74 20 24 63 68 61 6e 67 65 73 65 74 73 20 set $changesets
15f0: 7b 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 {.. foreach s
1600: 75 63 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 ucc [$cset succe
1610: 73 73 6f 72 73 5d 20 7b 0a 09 09 23 20 43 68 61 ssors] {...# Cha
1620: 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 ngesets may have
1630: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 dependencies ou
1640: 74 73 69 64 65 20 6f 66 20 74 68 65 0a 09 09 23 tside of the...#
1650: 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 chosen set. The
1660: 73 65 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 se are ignored..
1670: 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 .if {![$dg node
1680: 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 exists $succ]} c
1690: 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 ontinue...$dg ar
16a0: 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 c insert $cset $
16b0: 73 75 63 63 0a 0a 09 09 23 20 43 68 65 63 6b 20 succ....# Check
16c0: 66 6f 72 20 63 68 61 6e 67 65 73 65 74 73 20 72 for changesets r
16d0: 65 66 65 72 65 6e 63 69 6e 67 20 74 68 65 6d 73 eferencing thems
16e0: 65 6c 76 65 73 2e 20 53 75 63 68 20 61 0a 09 09 elves. Such a...
16f0: 23 20 6c 6f 6f 70 20 73 68 6f 77 73 20 74 68 61 # loop shows tha
1700: 74 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 t the changeset
1710: 69 6e 20 71 75 65 73 74 69 6f 6e 20 68 61 73 0a in question has.
1720: 09 09 23 20 69 6e 74 65 72 6e 61 6c 20 64 65 70 ..# internal dep
1730: 65 6e 64 65 6e 63 69 65 73 2e 20 53 6f 6d 65 74 endencies. Somet
1740: 68 69 6e 67 20 77 68 69 63 68 20 69 73 20 73 75 hing which is su
1750: 70 70 6f 73 65 64 0a 09 09 23 20 74 6f 20 62 65 pposed...# to be
1760: 20 6e 6f 74 20 70 6f 73 73 69 62 6c 65 2c 20 61 not possible, a
1770: 73 20 70 61 73 73 20 35 20 28 49 6e 69 74 43 73 s pass 5 (InitCs
1780: 65 74 73 29 20 74 61 6b 65 73 20 63 61 72 65 0a ets) takes care.
1790: 09 09 23 20 74 6f 20 74 72 61 6e 73 66 6f 72 6d ..# to transform
17a0: 20 69 6e 74 65 72 6e 61 6c 20 69 6e 74 6f 20 65 internal into e
17b0: 78 74 65 72 6e 61 6c 20 64 65 70 65 6e 64 65 6e xternal dependen
17c0: 63 69 65 73 20 62 79 0a 09 09 23 20 62 72 65 61 cies by...# brea
17d0: 6b 69 6e 67 20 74 68 65 20 72 65 6c 65 76 61 6e king the relevan
17e0: 74 20 63 68 61 6e 67 65 73 65 74 73 20 61 70 61 t changesets apa
17f0: 72 74 2e 20 53 6f 20 68 61 76 69 6e 67 0a 09 09 rt. So having...
1800: 23 20 6f 6e 65 20 69 6e 64 69 63 61 74 65 73 20 # one indicates
1810: 62 69 67 20 74 72 6f 75 62 6c 65 20 69 6e 20 70 big trouble in p
1820: 61 73 73 20 35 2e 20 57 65 20 72 65 70 6f 72 74 ass 5. We report
1830: 20 74 68 65 6d 0a 09 09 23 20 61 6e 64 20 64 75 them...# and du
1840: 6d 70 20 69 6e 74 65 72 6e 61 6c 20 73 74 72 75 mp internal stru
1850: 63 74 75 72 65 73 20 74 6f 20 6d 61 6b 65 20 69 ctures to make i
1860: 74 20 65 61 73 69 65 72 20 74 6f 0a 09 09 23 20 t easier to...#
1870: 74 72 61 63 65 20 74 68 65 20 6c 69 6e 6b 73 20 trace the links
1880: 63 61 75 73 69 6e 67 20 74 68 65 20 70 72 6f 62 causing the prob
1890: 6c 65 6d 2e 0a 09 09 69 66 20 7b 24 73 75 63 63 lem....if {$succ
18a0: 20 65 71 20 24 63 73 65 74 7d 20 7b 0a 09 09 20 eq $cset} {...
18b0: 20 20 20 74 72 6f 75 62 6c 65 20 66 61 74 61 6c trouble fatal
18c0: 20 22 53 65 6c 66 2d 72 65 66 65 72 65 6e 63 69 "Self-referenci
18d0: 6e 67 20 63 68 61 6e 67 65 73 65 74 20 5b 24 63 ng changeset [$c
18e0: 73 65 74 20 73 74 72 5d 22 0a 09 09 20 20 20 20 set str]"...
18f0: 6c 6f 67 20 77 72 69 74 65 20 32 20 63 79 63 6c log write 2 cycl
1900: 65 62 72 65 61 6b 65 72 20 22 4c 4f 4f 50 20 63 ebreaker "LOOP c
1910: 68 61 6e 67 65 73 65 74 20 5b 24 63 73 65 74 20 hangeset [$cset
1920: 73 74 72 5d 20 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f str] ___________
1930: 5f 5f 5f 5f 5f 5f 5f 22 0a 09 09 20 20 20 20 61 _______"... a
1940: 72 72 61 79 20 73 65 74 20 6e 6d 61 70 20 5b 24 rray set nmap [$
1950: 63 73 65 74 20 6e 65 78 74 6d 61 70 5d 0a 09 09 cset nextmap]...
1960: 20 20 20 20 66 6f 72 65 61 63 68 20 72 20 5b 6c foreach r [l
1970: 73 6f 72 74 20 2d 64 69 63 74 20 5b 61 72 72 61 sort -dict [arra
1980: 79 20 6e 61 6d 65 73 20 6e 6d 61 70 5d 5d 20 7b y names nmap]] {
1990: 0a 09 09 09 66 6f 72 65 61 63 68 20 73 75 63 63 ....foreach succ
19a0: 72 65 76 20 24 6e 6d 61 70 28 24 72 29 20 7b 0a rev $nmap($r) {.
19b0: 09 09 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 ... log write
19c0: 20 32 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 2 cyclebreaker
19d0: 5c 0a 09 09 09 09 22 4c 4f 4f 50 20 2a 20 72 65 \....."LOOP * re
19e0: 76 20 3c 24 72 3e 20 2d 2d 3e 20 72 65 76 20 3c v <$r> --> rev <
19f0: 24 73 75 63 63 72 65 76 3e 20 2d 2d 3e 20 63 73 $succrev> --> cs
1a00: 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 76 20 73 [project::rev s
1a10: 74 72 6c 69 73 74 20 5b 70 72 6f 6a 65 63 74 3a trlist [project:
1a20: 3a 72 65 76 20 6f 66 72 65 76 20 24 73 75 63 63 :rev ofrev $succ
1a30: 72 65 76 5d 5d 22 0a 09 09 09 7d 0a 09 09 20 20 rev]]"....}...
1a40: 20 20 7d 0a 09 09 7d 0a 09 20 20 20 20 7d 0a 09 }...}.. }..
1a50: 7d 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a }...if {$log} {.
1a60: 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 33 . log write 3
1a70: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 48 cyclebreaker "H
1a80: 61 73 20 5b 6e 73 70 20 5b 6c 6c 65 6e 67 74 68 as [nsp [llength
1a90: 20 5b 24 64 67 20 61 72 63 73 5d 5d 20 64 65 70 [$dg arcs]] dep
1aa0: 65 6e 64 65 6e 63 79 20 64 65 70 65 6e 64 65 6e endency dependen
1ab0: 63 69 65 73 5d 22 0a 09 7d 0a 0a 09 23 20 52 75 cies]"..}...# Ru
1ac0: 6e 20 74 68 65 20 75 73 65 72 20 68 6f 6f 6b 20 n the user hook
1ad0: 74 6f 20 6d 61 6e 69 70 75 6c 61 74 65 20 74 68 to manipulate th
1ae0: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 0a 09 e graph before..
1af0: 23 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a # consummation..
1b00: 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 20 4d 61 ..if {$log} { Ma
1b10: 72 6b 20 24 64 67 20 2d 73 74 61 72 74 20 7d 0a rk $dg -start }.
1b20: 09 4d 61 72 6b 57 61 74 63 68 20 24 64 67 0a 09 .MarkWatch $dg..
1b30: 50 72 65 48 6f 6f 6b 20 20 20 24 64 67 0a 09 4d PreHook $dg..M
1b40: 61 72 6b 57 61 74 63 68 20 24 64 67 0a 0a 09 23 arkWatch $dg...#
1b50: 20 54 68 69 73 20 6b 69 6c 6c 73 20 74 68 65 20 This kills the
1b60: 61 70 70 6c 69 63 61 74 69 6f 6e 20 69 66 20 6c application if l
1b70: 6f 6f 70 73 20 28 73 65 65 20 61 62 6f 76 65 29 oops (see above)
1b80: 20 77 65 72 65 20 66 6f 75 6e 64 2e 0a 09 74 72 were found...tr
1b90: 6f 75 62 6c 65 20 61 62 6f 72 74 3f 0a 09 72 65 ouble abort?..re
1ba0: 74 75 72 6e 20 20 24 64 67 0a 20 20 20 20 7d 0a turn $dg. }.
1bb0: 0a 20 20 20 20 23 20 49 6e 73 74 65 61 64 20 6f . # Instead o
1bc0: 66 20 73 65 61 72 63 68 69 6e 67 20 74 68 65 20 f searching the
1bd0: 77 68 6f 6c 65 20 67 72 61 70 68 20 66 6f 72 20 whole graph for
1be0: 74 68 65 20 64 65 67 72 65 65 2d 30 20 6e 6f 64 the degree-0 nod
1bf0: 65 73 20 69 6e 0a 20 20 20 20 23 20 65 61 63 68 es in. # each
1c00: 20 69 74 65 72 61 74 69 6f 6e 20 77 65 20 63 6f iteration we co
1c10: 6d 70 75 74 65 20 74 68 65 20 6c 69 73 74 20 6f mpute the list o
1c20: 6e 63 65 20 74 6f 20 73 74 61 72 74 2c 20 61 6e nce to start, an
1c30: 64 20 74 68 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 d then only.
1c40: 23 20 75 70 64 61 74 65 20 69 74 20 69 6e 63 72 # update it incr
1c50: 65 6d 65 6e 74 61 6c 6c 79 20 62 61 73 65 64 20 ementally based
1c60: 6f 6e 20 74 68 65 20 6f 75 74 67 6f 69 6e 67 20 on the outgoing
1c70: 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 neighbours of th
1c80: 65 0a 20 20 20 20 23 20 6e 6f 64 65 20 63 68 6f e. # node cho
1c90: 73 65 6e 20 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a sen for commit..
1ca0: 0a 20 20 20 20 70 72 6f 63 20 49 6e 69 74 69 61 . proc Initia
1cb0: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 7b lizeCandidates {
1cc0: 64 67 7d 20 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 dg} {..# bottom
1cd0: 3d 20 6c 69 73 74 20 28 6c 69 73 74 20 28 6e 6f = list (list (no
1ce0: 64 65 2c 20 72 61 6e 67 65 20 6d 69 6e 2c 20 72 de, range min, r
1cf0: 61 6e 67 65 20 6d 61 78 29 29 0a 09 3a 3a 76 61 ange max))..::va
1d00: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
1d10: 09 66 6f 72 65 61 63 68 20 6e 20 5b 24 64 67 20 .foreach n [$dg
1d20: 6e 6f 64 65 73 5d 20 7b 0a 09 20 20 20 20 69 66 nodes] {.. if
1d30: 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 {[$dg node degr
1d40: 65 65 20 2d 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 ee -in $n]} cont
1d50: 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 65 6e inue.. lappen
1d60: 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 d mybottom [lins
1d70: 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 ert [$dg node ge
1d80: 74 20 24 6e 20 74 69 6d 65 72 61 6e 67 65 5d 20 t $n timerange]
1d90: 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74 20 6d 79 0 $n]..}..set my
1da0: 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 bottom [lsort -i
1db0: 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72 20 ndex 1 -integer
1dc0: 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32 20 [lsort -index 2
1dd0: 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 74 74 -integer $mybott
1de0: 6f 6d 5d 5d 0a 09 53 68 6f 77 50 65 6e 64 69 6e om]]..ShowPendin
1df0: 67 4e 6f 64 65 73 0a 09 72 65 74 75 72 6e 0a 20 gNodes..return.
1e00: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 }.. proc W
1e10: 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f ithoutPredecesso
1e20: 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 r {dg nv} {..::v
1e30: 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d ariable mybottom
1e40: 0a 0a 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e ...upvar 1 $nv n
1e50: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
1e60: 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 $mybottom]} { re
1e70: 74 75 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e turn 0 }...set n
1e80: 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 [lindex [lindex
1e90: 20 24 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d $mybottom 0] 0]
1ea0: 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b ..set mybottom [
1eb0: 6c 72 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d lrange $mybottom
1ec0: 20 31 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 1 end]..set cha
1ed0: 6e 67 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 nged 0...# Updat
1ee0: 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 e list of nodes
1ef0: 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 without predeces
1f00: 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 sor, based on th
1f10: 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 e..# outgoing ne
1f20: 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 ighbours of the
1f30: 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 chosen node. Thi
1f40: 73 20 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 s should be..# f
1f50: 61 73 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 aster than itera
1f60: 74 69 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c ting of the whol
1f70: 65 20 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 e set of nodes,
1f80: 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 finding all..# w
1f90: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
1fa0: 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 ors, sorting the
1fb0: 6d 20 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 m by time, etc.
1fc0: 70 70 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 pp...foreach out
1fd0: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
1fe0: 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b $n] {.. if {
1ff0: 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 [$dg node degree
2000: 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 -in $out] > 1}
2010: 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 continue.. #
2020: 44 65 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f Degree-1 neighbo
2030: 75 72 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f ur, will have no
2040: 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 predecessors af
2050: 74 65 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 ter the.. # r
2060: 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 emoval of n. Put
2070: 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 on the list...
2080: 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 lappend mybot
2090: 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 tom [linsert [$d
20a0: 67 20 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 g node get $out
20b0: 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 timerange] 0 $ou
20c0: 74 5d 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e t].. set chan
20d0: 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 ged 1..}..if {$c
20e0: 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 73 hanged} {.. s
20f0: 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f et mybottom [lso
2100: 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 rt -index 1 -int
2110: 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 eger [lsort -ind
2120: 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 6d ex 2 -integer $m
2130: 79 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 ybottom]]..}...#
2140: 20 57 65 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 We do not delet
2150: 65 20 74 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 e the node immed
2160: 69 61 74 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 iately, to allow
2170: 20 74 68 65 20 53 61 76 65 0a 09 23 20 70 72 6f the Save..# pro
2180: 63 65 64 75 72 65 20 74 6f 20 73 61 76 65 20 74 cedure to save t
2190: 68 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 he dependencies
21a0: 61 73 20 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 as well (encoded
21b0: 20 69 6e 20 74 68 65 0a 09 23 20 61 72 63 73 29 in the..# arcs)
21c0: 2e 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 20 20 ...return 1.
21d0: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 53 68 6f 77 }.. proc Show
21e0: 50 65 6e 64 69 6e 67 4e 6f 64 65 73 20 7b 7d 20 PendingNodes {}
21f0: 7b 0a 09 69 66 20 7b 5b 6c 6f 67 20 76 65 72 62 {..if {[log verb
2200: 6f 73 69 74 79 3f 5d 20 3c 20 31 30 7d 20 72 65 osity?] < 10} re
2210: 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 62 6c 65 turn..::variable
2220: 20 6d 79 62 6f 74 74 6f 6d 0a 09 6c 6f 67 20 77 mybottom..log w
2230: 72 69 74 65 20 31 30 20 63 79 63 6c 65 62 72 65 rite 10 cyclebre
2240: 61 6b 65 72 20 5c 0a 09 20 20 20 20 22 50 65 6e aker \.. "Pen
2250: 64 69 6e 67 3a 20 5b 73 74 72 75 63 74 3a 3a 6c ding: [struct::l
2260: 69 73 74 20 6d 61 70 20 24 6d 79 62 6f 74 74 6f ist map $mybotto
2270: 6d 20 5b 6d 79 70 72 6f 63 20 46 6f 72 6d 61 74 m [myproc Format
2280: 50 65 6e 64 69 6e 67 49 74 65 6d 5d 5d 22 0a 09 PendingItem]]"..
2290: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
22a0: 20 20 70 72 6f 63 20 46 6f 72 6d 61 74 50 65 6e proc FormatPen
22b0: 64 69 6e 67 49 74 65 6d 20 7b 69 74 65 6d 7d 20 dingItem {item}
22c0: 7b 20 6c 72 65 70 6c 61 63 65 20 24 69 74 65 6d { lreplace $item
22d0: 20 30 20 30 20 5b 5b 6c 69 6e 64 65 78 20 24 69 0 0 [[lindex $i
22e0: 74 65 6d 20 30 5d 20 73 74 72 5d 20 7d 0a 0a 20 tem 0] str] }..
22f0: 20 20 20 70 72 6f 63 20 46 69 6e 64 43 79 63 6c proc FindCycl
2300: 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 68 69 73 e {dg} {..# This
2310: 20 70 72 6f 63 65 64 75 72 65 20 69 73 20 72 75 procedure is ru
2320: 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 20 74 68 n if and only th
2330: 65 20 67 72 61 70 68 20 69 73 20 6e 6f 74 20 65 e graph is not e
2340: 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 6c 6c 20 mpty and..# all
2350: 6e 6f 64 65 73 20 68 61 76 65 20 70 72 65 64 65 nodes have prede
2360: 63 65 73 73 6f 72 73 2e 20 54 68 69 73 20 6d 65 cessors. This me
2370: 61 6e 73 20 74 68 61 74 20 65 61 63 68 20 6e 6f ans that each no
2380: 64 65 20 69 73 0a 09 23 20 65 69 74 68 65 72 20 de is..# either
2390: 70 61 72 74 20 6f 66 20 61 20 63 79 63 6c 65 20 part of a cycle
23a0: 6f 72 20 28 69 6e 64 69 72 65 63 74 6c 79 29 20 or (indirectly)
23b0: 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 61 20 6e depending on a n
23c0: 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 79 63 6c ode..# in a cycl
23d0: 65 2e 20 57 65 20 63 61 6e 20 73 74 61 72 74 20 e. We can start
23e0: 61 74 20 61 6e 20 61 72 62 69 74 72 61 72 79 20 at an arbitrary
23f0: 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 69 74 73 node, follow its
2400: 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 65 64 67 ..# incoming edg
2410: 65 73 20 74 6f 20 69 74 73 20 70 72 65 64 65 63 es to its predec
2420: 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 77 65 20 essors until we
2430: 73 65 65 20 61 20 6e 6f 64 65 20 61 0a 09 23 20 see a node a..#
2440: 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 54 68 61 second time. Tha
2450: 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 20 74 68 t node closes th
2460: 65 20 63 79 63 6c 65 20 61 6e 64 20 74 68 65 20 e cycle and the
2470: 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a 09 23 20 beginning is..#
2480: 69 74 73 20 66 69 72 73 74 20 6f 63 63 75 72 65 its first occure
2490: 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 74 20 77 nce. Note that w
24a0: 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 61 6e 20 e can choose an
24b0: 61 72 62 69 74 72 61 72 79 0a 09 23 20 70 72 65 arbitrary..# pre
24c0: 64 65 63 65 73 73 6f 72 20 6f 66 20 65 61 63 68 decessor of each
24d0: 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c 2c 20 77 node as well, w
24e0: 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 74 6f e do not have to
24f0: 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 57 65 20 search....# We
2500: 72 65 63 6f 72 64 20 66 6f 72 20 65 61 63 68 20 record for each
2510: 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 78 20 6f node the index o
2520: 66 20 74 68 65 20 66 69 72 73 74 20 61 70 70 65 f the first appe
2530: 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 74 68 65 arance in..# the
2540: 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 20 69 74 path, making it
2550: 20 65 61 73 79 20 61 74 20 74 68 65 20 65 6e 64 easy at the end
2560: 20 74 6f 20 63 75 74 20 74 68 65 20 63 79 63 6c to cut the cycl
2570: 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e 0a 0a 09 e from..# it....
2580: 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 # Choose arbitra
2590: 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 61 72 74 ry node to start
25a0: 20 6f 75 72 20 73 65 61 72 63 68 20 61 74 2e 0a our search at..
25b0: 09 73 65 74 20 73 74 61 72 74 20 5b 6c 69 6e 64 .set start [lind
25c0: 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 30 ex [$dg nodes] 0
25d0: 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c 69 7a 65 ]...# Initialize
25e0: 20 73 74 61 74 65 2c 20 70 61 74 68 20 6f 66 20 state, path of
25f0: 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 6e 64 20 seen nodes, and
2600: 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 65 74 20 when seen...set
2610: 20 20 20 20 20 20 70 61 74 68 20 7b 7d 0a 09 61 path {}..a
2620: 72 72 61 79 20 73 65 74 20 73 65 65 6e 20 7b 7d rray set seen {}
2630: 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 ...while {1} {..
2640: 20 20 20 20 23 20 53 74 6f 70 20 73 65 61 72 63 # Stop searc
2650: 68 69 6e 67 20 77 68 65 6e 20 77 65 20 68 61 76 hing when we hav
2660: 65 20 73 65 65 6e 20 74 68 65 20 63 75 72 72 65 e seen the curre
2670: 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 23 20 61 nt node.. # a
2680: 6c 72 65 61 64 79 2c 20 74 68 65 20 63 69 72 63 lready, the circ
2690: 6c 65 20 68 61 73 20 62 65 65 6e 20 63 6c 6f 73 le has been clos
26a0: 65 64 2e 0a 09 20 20 20 20 69 66 20 7b 5b 69 6e ed... if {[in
26b0: 66 6f 20 65 78 69 73 74 73 20 73 65 65 6e 28 24 fo exists seen($
26c0: 73 74 61 72 74 29 5d 7d 20 62 72 65 61 6b 0a 09 start)]} break..
26d0: 20 20 20 20 6c 61 70 70 65 6e 64 20 70 61 74 68 lappend path
26e0: 20 24 73 74 61 72 74 0a 09 20 20 20 20 73 65 74 $start.. set
26f0: 20 73 65 65 6e 28 24 73 74 61 72 74 29 20 5b 65 seen($start) [e
2700: 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 70 xpr {[llength $p
2710: 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 20 23 20 ath]-1}].. #
2720: 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 72 79 Choose arbitrary
2730: 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 20 20 predecessor..
2740: 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c 69 6e set start [lin
2750: 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d dex [$dg nodes -
2760: 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a 09 7d in $start] 0]..}
2770: 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 75 63 ...return [struc
2780: 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 65 20 t::list reverse
2790: 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 24 73 [lrange $path $s
27a0: 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e 64 5d een($start) end]
27b0: 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f ]. }.. pro
27c0: 63 20 42 72 65 61 6b 53 65 67 6d 65 6e 74 20 7b c BreakSegment {
27d0: 64 67 20 70 61 74 68 20 6c 61 62 65 6c 7d 20 7b dg path label} {
27e0: 0a 09 23 20 54 68 65 20 70 61 74 68 2c 20 75 73 ..# The path, us
27f0: 75 61 6c 6c 79 20 61 20 63 79 63 6c 65 2c 20 77 ually a cycle, w
2800: 65 20 68 61 76 65 20 67 6f 74 74 65 6e 20 69 73 e have gotten is
2810: 20 62 72 6f 6b 65 6e 20 62 79 0a 09 23 20 62 72 broken by..# br
2820: 65 61 6b 69 6e 67 20 61 70 61 72 74 20 6f 6e 65 eaking apart one
2830: 20 6f 72 20 6d 6f 72 65 20 6f 66 20 74 68 65 20 or more of the
2840: 63 68 61 6e 67 65 73 65 74 73 20 69 6e 20 74 68 changesets in th
2850: 65 0a 09 23 20 63 79 63 6c 65 2e 20 54 68 69 73 e..# cycle. This
2860: 20 63 61 75 73 65 73 20 75 73 20 74 6f 20 63 72 causes us to cr
2870: 65 61 74 65 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 eate one or more
2880: 20 63 68 61 6e 67 65 73 65 74 73 20 77 68 69 63 changesets whic
2890: 68 0a 09 23 20 61 72 65 20 74 6f 20 62 65 20 63 h..# are to be c
28a0: 6f 6d 6d 69 74 74 65 64 2c 20 61 64 64 65 64 20 ommitted, added
28b0: 74 6f 20 74 68 65 20 67 72 61 70 68 2c 20 65 74 to the graph, et
28c0: 63 2e 20 70 70 2e 0a 0a 09 73 65 74 20 62 65 73 c. pp....set bes
28d0: 74 6c 69 6e 6b 20 7b 7d 0a 09 73 65 74 20 62 65 tlink {}..set be
28e0: 73 74 6e 6f 64 65 20 7b 7d 0a 0a 09 66 6f 72 65 stnode {}...fore
28f0: 61 63 68 20 5c 0a 09 20 20 20 20 70 72 65 76 20 ach \.. prev
2900: 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 30 20 [lrange $path 0
2910: 65 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 20 63 73 end-2] \.. cs
2920: 65 74 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 et [lrange $path
2930: 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 20 1 end-1] \..
2940: 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 20 24 70 next [lrange $p
2950: 61 74 68 20 32 20 65 6e 64 5d 20 7b 0a 0a 09 09 ath 2 end] {....
2960: 23 20 45 61 63 68 20 74 72 69 70 6c 65 20 50 52 # Each triple PR
2970: 45 56 20 2d 3e 20 43 53 45 54 20 2d 3e 20 4e 45 EV -> CSET -> NE
2980: 58 54 20 6f 66 20 63 68 61 6e 67 65 73 65 74 73 XT of changesets
2990: 2c 20 61 0a 09 09 23 20 27 6c 69 6e 6b 27 20 69 , a...# 'link' i
29a0: 6e 20 74 68 65 20 63 79 63 6c 65 2c 20 69 73 20 n the cycle, is
29b0: 61 6e 61 6c 79 73 65 64 20 61 6e 64 20 74 68 65 analysed and the
29c0: 20 62 65 73 74 0a 09 09 23 20 6c 6f 63 61 74 69 best...# locati
29d0: 6f 6e 20 77 68 65 72 65 20 74 6f 20 61 74 20 6c on where to at l
29e0: 65 61 73 74 20 77 65 61 6b 65 6e 20 74 68 65 20 east weaken the
29f0: 63 79 63 6c 65 20 69 73 0a 09 09 23 20 63 68 6f cycle is...# cho
2a00: 73 65 6e 20 66 6f 72 20 66 75 72 74 68 65 72 20 sen for further
2a10: 70 72 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 09 73 processing.....s
2a20: 65 74 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 63 74 et link [project
2a30: 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 55 54 4f 25 ::revlink %AUTO%
2a40: 20 24 70 72 65 76 20 24 63 73 65 74 20 24 6e 65 $prev $cset $ne
2a50: 78 74 5d 0a 09 09 69 66 20 7b 24 62 65 73 74 6c xt]...if {$bestl
2a60: 69 6e 6b 20 65 71 20 22 22 7d 20 7b 0a 09 09 20 ink eq ""} {...
2a70: 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 set bestlink
2a80: 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 $link... set
2a90: 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 bestnode $cset..
2aa0: 09 7d 20 65 6c 73 65 69 66 20 7b 5b 24 6c 69 6e .} elseif {[$lin
2ab0: 6b 20 62 65 74 74 65 72 74 68 61 6e 20 24 62 65 k betterthan $be
2ac0: 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 20 20 stlink]} {...
2ad0: 20 24 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 $bestlink destr
2ae0: 6f 79 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 oy... set bes
2af0: 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 tlink $link...
2b00: 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 20 24 set bestnode $
2b10: 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 20 7b 0a cset...} else {.
2b20: 09 09 20 20 20 20 24 6c 69 6e 6b 20 64 65 73 74 .. $link dest
2b30: 72 6f 79 0a 09 09 7d 0a 09 20 20 20 20 7d 0a 0a roy...}.. }..
2b40: 09 6c 6f 67 20 77 72 69 74 65 20 35 20 63 79 63 .log write 5 cyc
2b50: 6c 65 62 72 65 61 6b 65 72 20 22 42 72 65 61 6b lebreaker "Break
2b60: 69 6e 67 20 24 6c 61 62 65 6c 20 62 79 20 73 70 ing $label by sp
2b70: 6c 69 74 74 69 6e 67 20 63 68 61 6e 67 65 73 65 litting changese
2b80: 74 20 5b 24 62 65 73 74 6e 6f 64 65 20 73 74 72 t [$bestnode str
2b90: 5d 22 0a 09 73 65 74 20 49 44 20 5b 24 62 65 73 ]"..set ID [$bes
2ba0: 74 6e 6f 64 65 20 69 64 5d 0a 09 4d 61 72 6b 20 tnode id]..Mark
2bb0: 24 64 67 20 2d 24 7b 49 44 7d 2d 62 65 66 6f 72 $dg -${ID}-befor
2bc0: 65 0a 0a 09 73 65 74 20 6e 65 77 63 73 65 74 73 e...set newcsets
2bd0: 20 5b 24 62 65 73 74 6c 69 6e 6b 20 62 72 65 61 [$bestlink brea
2be0: 6b 5d 0a 09 24 62 65 73 74 6c 69 6e 6b 20 64 65 k]..$bestlink de
2bf0: 73 74 72 6f 79 0a 0a 20 20 20 20 20 20 20 20 23 stroy.. #
2c00: 20 41 74 20 74 68 69 73 20 70 6f 69 6e 74 20 74 At this point t
2c10: 68 65 20 6f 6c 64 20 63 68 61 6e 67 65 73 65 74 he old changeset
2c20: 20 28 42 45 53 54 4e 4f 44 45 29 20 69 73 20 67 (BESTNODE) is g
2c30: 6f 6e 65 0a 20 20 20 20 20 20 20 20 23 20 61 6c one. # al
2c40: 72 65 61 64 79 2e 20 57 65 20 72 65 6d 6f 76 65 ready. We remove
2c50: 20 69 74 20 66 72 6f 6d 20 74 68 65 20 67 72 61 it from the gra
2c60: 70 68 20 61 73 20 77 65 6c 6c 20 61 6e 64 20 74 ph as well and t
2c70: 68 65 6e 20 65 6e 74 65 72 0a 20 20 20 20 20 20 hen enter.
2c80: 20 20 23 20 74 68 65 20 66 72 61 67 6d 65 6e 74 # the fragment
2c90: 73 20 67 65 6e 65 72 61 74 65 64 20 66 6f 72 20 s generated for
2ca0: 69 74 2e 0a 0a 09 52 65 70 6c 61 63 65 20 24 64 it....Replace $d
2cb0: 67 20 24 62 65 73 74 6e 6f 64 65 20 24 6e 65 77 g $bestnode $new
2cc0: 63 73 65 74 73 0a 0a 09 4d 61 72 6b 20 24 64 67 csets...Mark $dg
2cd0: 20 2d 24 7b 49 44 7d 2d 61 66 74 65 72 0a 09 72 -${ID}-after..r
2ce0: 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 eturn. }..
2cf0: 20 23 20 54 4f 44 4f 3a 20 54 68 69 73 20 73 68 # TODO: This sh
2d00: 6f 75 6c 64 20 62 65 20 61 20 67 72 61 70 68 20 ould be a graph
2d10: 6d 65 74 68 6f 64 2e 0a 20 20 20 20 70 72 6f 63 method.. proc
2d20: 20 48 61 73 41 72 63 20 7b 64 67 20 61 20 62 7d HasArc {dg a b}
2d30: 20 7b 0a 09 23 38 2e 35 3a 20 72 65 74 75 72 6e {..#8.5: return
2d40: 20 5b 65 78 70 72 20 7b 24 62 20 69 6e 20 5b 24 [expr {$b in [$
2d50: 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 61 dg nodes -out $a
2d60: 5d 7d 5d 0a 09 69 66 20 7b 5b 6c 73 65 61 72 63 ]}]..if {[lsearc
2d70: 68 20 2d 65 78 61 63 74 20 5b 24 64 67 20 6e 6f h -exact [$dg no
2d80: 64 65 73 20 2d 6f 75 74 20 24 61 5d 20 24 62 5d des -out $a] $b]
2d90: 20 3c 20 30 7d 20 7b 20 72 65 74 75 72 6e 20 30 < 0} { return 0
2da0: 20 7d 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 20 }..return 1.
2db0: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 4d 61 72 }.. proc Mar
2dc0: 6b 20 7b 64 67 20 7b 73 75 66 66 69 78 20 7b 7d k {dg {suffix {}
2dd0: 7d 20 7b 73 75 62 67 72 61 70 68 20 7b 7d 7d 7d } {subgraph {}}}
2de0: 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d {..::variable m
2df0: 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a ydotdestination.
2e00: 09 69 66 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 .if {$mydotdesti
2e10: 6e 61 74 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 nation eq ""} re
2e20: 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 62 6c 65 turn..::variable
2e30: 20 6d 79 64 6f 74 70 72 65 66 69 78 0a 09 3a 3a mydotprefix..::
2e40: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 variable mydotid
2e50: 0a 09 73 65 74 20 66 6e 61 6d 65 20 24 6d 79 64 ..set fname $myd
2e60: 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 2f 24 7b otdestination/${
2e70: 6d 79 64 6f 74 70 72 65 66 69 78 7d 24 7b 6d 79 mydotprefix}${my
2e80: 64 6f 74 69 64 7d 24 7b 73 75 66 66 69 78 7d 2e dotid}${suffix}.
2e90: 64 6f 74 0a 09 66 69 6c 65 20 6d 6b 64 69 72 20 dot..file mkdir
2ea0: 5b 66 69 6c 65 20 64 69 72 6e 61 6d 65 20 24 66 [file dirname $f
2eb0: 6e 61 6d 65 5d 0a 09 64 6f 74 20 77 72 69 74 65 name]..dot write
2ec0: 20 24 64 67 20 24 6d 79 64 6f 74 70 72 65 66 69 $dg $mydotprefi
2ed0: 78 24 73 75 66 66 69 78 20 24 66 6e 61 6d 65 20 x$suffix $fname
2ee0: 24 73 75 62 67 72 61 70 68 0a 09 69 6e 63 72 20 $subgraph..incr
2ef0: 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f 67 20 77 72 mydotid...log wr
2f00: 69 74 65 20 35 20 63 79 63 6c 65 62 72 65 61 6b ite 5 cyclebreak
2f10: 65 72 20 22 2e 64 6f 74 20 65 78 70 6f 72 74 20 er ".dot export
2f20: 24 66 6e 61 6d 65 22 0a 09 72 65 74 75 72 6e 0a $fname"..return.
2f30: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
2f40: 52 65 70 6c 61 63 65 20 7b 64 67 20 6e 20 72 65 Replace {dg n re
2f50: 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b 0a 09 23 placements} {..#
2f60: 20 4e 4f 54 45 2e 20 57 65 20 68 61 76 65 20 74 NOTE. We have t
2f70: 6f 20 67 65 74 20 74 68 65 20 6c 69 73 74 20 6f o get the list o
2f80: 66 20 69 6e 63 6f 6d 69 6e 67 20 6e 65 69 67 68 f incoming neigh
2f90: 62 6f 75 72 73 20 61 6e 64 0a 09 23 20 72 65 63 bours and..# rec
2fa0: 6f 6d 70 75 74 65 20 74 68 65 69 72 20 73 75 63 ompute their suc
2fb0: 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 74 68 cessors after th
2fc0: 65 20 6e 65 77 20 6e 6f 64 65 73 20 68 61 76 65 e new nodes have
2fd0: 20 62 65 65 6e 0a 09 23 20 69 6e 73 65 72 74 65 been..# inserte
2fe0: 64 2e 20 54 68 65 69 72 20 6f 75 74 67 6f 69 6e d. Their outgoin
2ff0: 67 20 61 72 63 73 20 77 69 6c 6c 20 6e 6f 77 20 g arcs will now
3000: 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 20 62 6f 74 go to one or bot
3010: 68 20 6f 66 0a 09 23 20 74 68 65 20 6e 65 77 20 h of..# the new
3020: 6e 6f 64 65 73 2c 20 61 6e 64 20 6e 6f 74 20 72 nodes, and not r
3030: 65 64 6f 69 6e 67 20 74 68 65 6d 20 6d 61 79 20 edoing them may
3040: 63 61 75 73 65 20 75 73 20 74 6f 20 66 6f 72 67 cause us to forg
3050: 65 74 0a 09 23 20 63 69 72 63 6c 65 73 2c 20 6c et..# circles, l
3060: 65 61 76 69 6e 67 20 74 68 65 6d 20 69 6e 2c 20 eaving them in,
3070: 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 73 65 74 20 unbroken....set
3080: 70 72 65 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d pre [$dg nodes -
3090: 69 6e 20 24 6e 5d 0a 0a 20 20 20 20 20 20 20 20 in $n]..
30a0: 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 74 65 20 $dg node delete
30b0: 24 6e 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 $n...foreach cse
30c0: 74 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 73 20 t $replacements
30d0: 7b 0a 09 20 20 20 20 73 65 74 20 74 72 20 5b 24 {.. set tr [$
30e0: 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d 0a cset timerange].
30f0: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 69 6e . $dg node in
3100: 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 20 20 sert $cset..
3110: 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 $dg node set
3120: 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 20 $cset timerange
3130: 24 74 72 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 $tr.. $dg nod
3140: 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 6c e set $cset l
3150: 61 62 65 6c 20 20 20 20 20 22 5b 24 63 73 65 74 abel "[$cset
3160: 20 73 74 72 5d 5c 5c 6e 5b 6a 6f 69 6e 20 5b 73 str]\\n[join [s
3170: 74 72 75 63 74 3a 3a 6c 69 73 74 20 6d 61 70 20 truct::list map
3180: 24 74 72 20 7b 3a 3a 63 6c 6f 63 6b 20 66 6f 72 $tr {::clock for
3190: 6d 61 74 7d 5d 20 22 5c 5c 6e 22 5d 22 0a 09 20 mat}] "\\n"]"..
31a0: 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 $dg node set
31b0: 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f 5f 20 $cset __id__
31c0: 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a 09 20 [$cset id]..
31d0: 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 $dg node set
31e0: 20 20 20 24 63 73 65 74 20 73 68 61 70 65 20 20 $cset shape
31f0: 20 20 20 5b 65 78 70 72 20 7b 5b 24 63 73 65 74 [expr {[$cset
3200: 20 62 79 73 79 6d 62 6f 6c 5d 0a 09 09 09 09 09 bysymbol]......
3210: 09 20 20 20 3f 20 22 65 6c 6c 69 70 73 65 22 0a . ? "ellipse".
3220: 09 09 09 09 09 09 20 20 20 3a 20 22 62 6f 78 22 ...... : "box"
3230: 7d 5d 0a 09 7d 0a 0a 09 66 6f 72 65 61 63 68 20 }]..}...foreach
3240: 63 73 65 74 20 24 72 65 70 6c 61 63 65 6d 65 6e cset $replacemen
3250: 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 63 ts {.. foreac
3260: 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 75 h succ [$cset su
3270: 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 20 ccessors] {...#
3280: 54 68 65 20 6e 65 77 20 63 68 61 6e 67 65 73 65 The new changese
3290: 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 70 65 ts may have depe
32a0: 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 ndencies outside
32b0: 20 6f 66 0a 09 09 23 20 74 68 65 20 63 68 6f 73 of...# the chos
32c0: 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 61 72 en set. These ar
32d0: 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b e ignored...if {
32e0: 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 ![$dg node exist
32f0: 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e s $succ]} contin
3300: 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 ue...$dg arc ins
3310: 65 72 74 20 24 63 73 65 74 20 24 73 75 63 63 0a ert $cset $succ.
3320: 09 09 69 66 20 7b 24 73 75 63 63 20 65 71 20 24 ..if {$succ eq $
3330: 63 73 65 74 7d 20 7b 0a 09 09 20 20 20 20 74 72 cset} {... tr
3340: 6f 75 62 6c 65 20 69 6e 74 65 72 6e 61 6c 20 22 ouble internal "
3350: 53 65 6c 66 2d 72 65 66 65 72 65 6e 63 69 6e 67 Self-referencing
3360: 20 63 68 61 6e 67 65 73 65 74 20 5b 24 63 73 65 changeset [$cse
3370: 74 20 73 74 72 5d 22 0a 09 09 7d 0a 09 20 20 20 t str]"...}..
3380: 20 7d 0a 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 }..}..foreach c
3390: 73 65 74 20 24 70 72 65 20 7b 0a 09 20 20 20 20 set $pre {..
33a0: 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 foreach succ [$c
33b0: 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 set successors]
33c0: 7b 0a 09 09 23 20 4e 6f 74 65 20 74 68 61 74 20 {...# Note that
33d0: 74 68 65 20 61 72 63 20 6d 61 79 20 61 6c 72 65 the arc may alre
33e0: 61 64 79 20 65 78 69 73 74 20 69 6e 20 74 68 65 ady exist in the
33f0: 20 67 72 61 70 68 2e 20 49 66 0a 09 09 23 20 73 graph. If...# s
3400: 6f 20 69 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 o ignore it. The
3410: 20 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 new changesets
3420: 6d 61 79 20 68 61 76 65 0a 09 09 23 20 64 65 70 may have...# dep
3430: 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 endencies outsid
3440: 65 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 e of the chosen
3450: 73 65 74 2e 20 54 68 65 73 65 20 61 72 65 0a 09 set. These are..
3460: 09 23 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 .# ignored...if
3470: 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 {![$dg node exis
3480: 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 ts $succ]} conti
3490: 6e 75 65 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 nue...if {[HasAr
34a0: 63 20 24 64 67 20 24 63 73 65 74 20 24 73 75 63 c $dg $cset $suc
34b0: 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 c]} continue;# T
34c0: 4f 44 4f 20 73 68 6f 75 6c 64 20 62 65 20 67 72 ODO should be gr
34d0: 61 70 68 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 aph method....$d
34e0: 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 g arc insert $cs
34f0: 65 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a et $succ.. }.
3500: 09 7d 0a 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 .}...return.
3510: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
3520: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
3530: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
3540: 20 20 20 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 ## Callback i
3550: 6e 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 nvokation .....
3560: 20 20 20 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 proc PreHook
3570: 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 {graph} {..# Giv
3580: 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 e the user of th
3590: 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 e cycle breaker
35a0: 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 the opportunity
35b0: 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 to work..# with
35c0: 74 68 65 20 67 72 61 70 68 20 62 65 74 77 65 65 the graph betwee
35d0: 6e 20 73 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 n setup and cons
35e0: 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 ummation....::va
35f0: 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a riable myprecmd.
3600: 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 .if {![llength $
3610: 6d 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 myprecmd]} retur
3620: 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b n...uplevel #0 [
3630: 6c 69 6e 73 65 72 74 20 24 6d 79 70 72 65 63 6d linsert $myprecm
3640: 64 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d d end $graph]..M
3650: 61 72 6b 20 24 67 72 61 70 68 20 2d 70 72 65 2d ark $graph -pre-
3660: 64 6f 6e 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 done..return.
3670: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 6f }.. proc Pro
3680: 63 65 73 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 cessedHook {dg c
3690: 73 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 set pos} {..# Gi
36a0: 76 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 ve the user of t
36b0: 68 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 he cycle breaker
36c0: 20 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 the opportunity
36d0: 20 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 to work..# with
36e0: 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 62 the changeset b
36f0: 65 66 6f 72 65 20 69 74 20 69 73 20 72 65 6d 6f efore it is remo
3700: 76 65 64 20 66 72 6f 6d 20 74 68 65 20 67 72 61 ved from the gra
3710: 70 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 ph....::variable
3720: 20 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 20 7b mysavecmd..if {
3730: 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 ![llength $mysav
3740: 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 ecmd]} return...
3750: 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 uplevel #0 [lins
3760: 65 72 74 20 24 6d 79 73 61 76 65 63 6d 64 20 65 ert $mysavecmd e
3770: 6e 64 20 24 64 67 20 24 70 6f 73 20 24 63 73 65 nd $dg $pos $cse
3780: 74 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d t]..return. }
3790: 0a 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b .. proc Break
37a0: 43 79 63 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 CycleHook {graph
37b0: 7d 20 7b 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 } {..# Call out
37c0: 74 6f 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c to the chosen al
37d0: 67 6f 72 69 74 68 6d 20 66 6f 72 20 63 79 63 6c gorithm for cycl
37e0: 65 20 62 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 e breaking. Find
37f0: 69 6e 67 0a 09 23 20 61 20 63 79 63 6c 65 20 69 ing..# a cycle i
3800: 66 20 6e 6f 20 62 72 65 61 6b 65 72 20 77 61 73 f no breaker was
3810: 20 63 68 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 chosen is an er
3820: 72 6f 72 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c ror....::variabl
3830: 65 20 6d 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 e mybreakcmd..if
3840: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 {![llength $myb
3850: 72 65 61 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 reakcmd]} {..
3860: 20 74 72 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 trouble fatal "
3870: 46 6f 75 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 Found a cycle, e
3880: 78 70 65 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a xpecting none.".
3890: 09 20 20 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a . exit 1..}..
38a0: 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e .uplevel #0 [lin
38b0: 73 65 72 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 sert $mybreakcmd
38c0: 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 72 65 end $graph]..re
38d0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
38e0: 70 72 6f 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 proc ClearHooks
38f0: 7b 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 {} {..::variable
3900: 20 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 myprecmd {}..
3910: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 ::variable mysav
3920: 65 63 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 ecmd {}..::vari
3930: 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 able mybreakcmd
3940: 7b 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d {}..return. }
3950: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
3960: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
3970: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 #############..
3980: 20 20 20 70 72 6f 63 20 4d 61 72 6b 57 61 74 63 proc MarkWatc
3990: 68 20 7b 67 72 61 70 68 7d 20 7b 0a 09 3a 3a 76 h {graph} {..::v
39a0: 61 72 69 61 62 6c 65 20 6d 79 77 61 74 63 68 69 ariable mywatchi
39b0: 64 73 0a 09 73 65 74 20 77 61 74 63 68 65 64 20 ds..set watched
39c0: 5b 57 61 74 63 68 65 64 20 24 67 72 61 70 68 20 [Watched $graph
39d0: 24 6d 79 77 61 74 63 68 69 64 73 5d 0a 09 69 66 $mywatchids]..if
39e0: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 77 61 74 {![llength $wat
39f0: 63 68 65 64 5d 7d 20 72 65 74 75 72 6e 0a 09 73 ched]} return..s
3a00: 65 74 20 6e 65 69 67 68 62 6f 75 72 73 20 5b 65 et neighbours [e
3a10: 76 61 6c 20 5b 6c 69 6e 73 65 72 74 20 24 77 61 val [linsert $wa
3a20: 74 63 68 65 64 20 30 20 24 67 72 61 70 68 20 6e tched 0 $graph n
3a30: 6f 64 65 73 20 2d 61 64 6a 5d 5d 0a 09 23 66 6f odes -adj]]..#fo
3a40: 72 65 61 63 68 20 6e 20 24 6e 65 69 67 68 62 6f reach n $neighbo
3a50: 75 72 73 20 7b 20 6c 6f 67 20 77 72 69 74 65 20 urs { log write
3a60: 36 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 6 cyclebreaker "
3a70: 4e 65 69 67 68 62 6f 72 20 5b 24 6e 20 69 64 5d Neighbor [$n id]
3a80: 20 3d 3e 20 24 6e 22 20 7d 0a 09 4d 61 72 6b 20 => $n" }..Mark
3a90: 24 67 72 61 70 68 20 77 61 74 63 68 65 64 20 5b $graph watched [
3aa0: 63 6f 6e 63 61 74 20 24 77 61 74 63 68 65 64 20 concat $watched
3ab0: 24 6e 65 69 67 68 62 6f 75 72 73 5d 0a 09 72 65 $neighbours]..re
3ac0: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
3ad0: 70 72 6f 63 20 57 61 74 63 68 65 64 20 7b 67 72 proc Watched {gr
3ae0: 61 70 68 20 77 61 74 63 68 69 64 73 7d 20 7b 0a aph watchids} {.
3af0: 09 73 65 74 20 72 65 73 20 7b 7d 0a 09 66 6f 72 .set res {}..for
3b00: 65 61 63 68 20 69 64 20 24 77 61 74 63 68 69 64 each id $watchid
3b10: 73 20 7b 0a 09 20 20 20 20 73 65 74 20 6e 6c 20 s {.. set nl
3b20: 5b 24 67 72 61 70 68 20 6e 6f 64 65 73 20 2d 6b [$graph nodes -k
3b30: 65 79 20 5f 5f 69 64 5f 5f 20 2d 76 61 6c 75 65 ey __id__ -value
3b40: 20 24 69 64 5d 0a 09 20 20 20 20 69 66 20 7b 21 $id].. if {!
3b50: 5b 6c 6c 65 6e 67 74 68 20 24 6e 6c 5d 7d 20 63 [llength $nl]} c
3b60: 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 ontinue.. lap
3b70: 70 65 6e 64 20 72 65 73 20 24 6e 6c 0a 09 20 20 pend res $nl..
3b80: 20 20 23 6c 6f 67 20 77 72 69 74 65 20 36 20 62 #log write 6 b
3b90: 72 65 61 6b 72 63 79 63 6c 65 20 22 57 61 74 63 reakrcycle "Watc
3ba0: 68 69 6e 67 20 24 69 64 20 3d 3e 20 24 6e 6c 22 hing $id => $nl"
3bb0: 0a 09 20 20 20 20 24 67 72 61 70 68 20 6e 6f 64 .. $graph nod
3bc0: 65 20 73 65 74 20 24 6e 6c 20 66 6f 6e 74 63 6f e set $nl fontco
3bd0: 6c 6f 72 20 72 65 64 0a 09 7d 0a 09 72 65 74 75 lor red..}..retu
3be0: 72 6e 20 24 72 65 73 0a 20 20 20 20 7d 0a 0a 20 rn $res. }..
3bf0: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
3c00: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
3c10: 23 23 23 23 23 23 23 23 23 23 0a 0a 0a 20 20 20 ##########...
3c20: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3c30: 61 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f at 0 ; # Co
3c40: 75 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 unter for commit
3c50: 20 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 ids for the....
3c60: 20 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 # changes
3c70: 65 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 ets.. typevar
3c80: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b iable mybottom {
3c90: 7d 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 } ; # List of th
3ca0: 65 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 e candidate node
3cb0: 73 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 s for....
3cc0: 23 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 # committing...
3cd0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3ce0: 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 myprecmd {} ;
3cf0: 23 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e # Callback, chan
3d00: 67 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 ge graph before
3d10: 77 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 walk.. typeva
3d20: 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 riable mysavecmd
3d30: 20 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 {} ; # Callbac
3d40: 6b 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 k, for each proc
3d50: 65 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 essed node..
3d60: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 typevariable myb
3d70: 72 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 reakcmd {} ; # C
3d80: 61 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 allback, for eac
3d90: 68 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a h found cycle...
3da0: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
3db0: 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f mydotdestinatio
3dc0: 6e 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 n {} ; # Destina
3dd0: 74 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 tion directory f
3de0: 6f 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 or the.....
3df0: 20 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 # generated .d
3e00: 6f 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 ot files.. ty
3e10: 70 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 pevariable mydot
3e20: 70 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b prefix {} ;
3e30: 20 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f # Prefix for do
3e40: 74 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 t files when....
3e50: 09 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 . # export
3e60: 69 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a ing the graphs..
3e70: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
3e80: 20 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 mydotid
3e90: 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 0 ; # Counter
3ea0: 20 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 for dot file na
3eb0: 6d 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 me..... #
3ec0: 67 65 6e 65 72 61 74 69 6f 6e 2e 0a 20 20 20 20 generation..
3ed0: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 77 typevariable myw
3ee0: 61 74 63 68 69 64 73 20 20 20 20 20 20 20 7b 7d atchids {}
3ef0: 20 3b 20 23 20 43 68 61 6e 67 65 73 65 74 73 20 ; # Changesets
3f00: 74 6f 20 77 61 74 63 68 20 74 68 65 0a 09 09 09 to watch the....
3f10: 09 20 20 20 20 20 20 20 23 20 6e 65 69 67 68 62 . # neighb
3f20: 6f 75 72 68 6f 6f 64 20 6f 66 2e 0a 0a 20 20 20 ourhood of...
3f30: 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 # # ## ### ####
3f40: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
3f50: 23 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 ########. ##
3f60: 43 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 Configuration..
3f70: 20 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e pragma -hasin
3f80: 73 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 stances no ; #
3f90: 20 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 singleton. p
3fa0: 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e ragma -hastypein
3fb0: 66 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 fo no ; # no
3fc0: 69 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 introspection.
3fd0: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 pragma -hastyp
3fe0: 65 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 edestroy no ; #
3ff0: 69 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 immortal.. #
4000: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
4010: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
4020: 23 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 #####.}..namespa
4030: 63 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f ce eval ::vc::fo
4040: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
4050: 73 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 s {. namespac
4060: 65 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 e export cyclebr
4070: 65 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 eaker. namesp
4080: 61 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 ace eval cyclebr
4090: 65 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 eaker {..namespa
40a0: 63 65 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 ce eval project
40b0: 7b 0a 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 {.. namespace
40c0: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f import ::vc::fo
40d0: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
40e0: 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a s::project::rev.
40f0: 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 . namespace i
4100: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 mport ::vc::foss
4110: 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a il::import::cvs:
4120: 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e :project::revlin
4130: 6b 0a 09 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 k..}..namespace
4140: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
4150: 6c 73 3a 3a 6d 69 73 63 3a 3a 2a 0a 09 6e 61 6d ls::misc::*..nam
4160: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
4170: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 vc::tools::log..
4180: 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 namespace import
4190: 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 74 72 ::vc::tools::tr
41a0: 6f 75 62 6c 65 0a 09 6e 61 6d 65 73 70 61 63 65 ouble..namespace
41b0: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f import ::vc::to
41c0: 6f 6c 73 3a 3a 64 6f 74 0a 09 6c 6f 67 20 72 65 ols::dot..log re
41d0: 67 69 73 74 65 72 20 63 79 63 6c 65 62 72 65 61 gister cyclebrea
41e0: 6b 65 72 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 23 ker. }.}..# #
41f0: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
4200: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
4210: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
4220: 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 ##########.## Re
4230: 61 64 79 0a 0a 70 61 63 6b 61 67 65 20 70 72 6f ady..package pro
4240: 76 69 64 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a vide vc::fossil:
4250: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 :import::cvs::cy
4260: 63 6c 65 62 72 65 61 6b 65 72 20 31 2e 30 0a 72 clebreaker 1.0.r
4270: 65 74 75 72 6e 0a eturn.