Artifact a02d54b2ad4d502956c78cd4c04008fff65d5f44:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[eabaea870a]
- Added a number of assertions and must-not-happens with associated log output. Plus some small tweaks, and notes.
by
aku on
2007-11-24 04:15:46.
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 49 44 20 24 63 73 abel [ID $cs
1190: 65 74 5d 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 et].. $dg nod
11a0: 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 5f e set $cset _
11b0: 5f 69 64 5f 5f 20 20 20 20 5b 24 63 73 65 74 20 _id__ [$cset
11c0: 69 64 5d 0a 09 7d 0a 0a 09 23 20 32 2e 20 46 69 id]..}...# 2. Fi
11d0: 6e 64 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 nd for all relev
11e0: 61 6e 74 20 63 68 61 6e 67 65 73 65 74 20 74 68 ant changeset th
11f0: 65 69 72 20 72 65 76 69 73 69 6f 6e 73 20 61 6e eir revisions an
1200: 64 20 74 68 65 69 72 0a 09 23 20 20 20 20 64 65 d their..# de
1210: 70 65 6e 64 65 6e 63 69 65 73 2e 20 4d 61 70 20 pendencies. Map
1220: 74 68 65 20 6c 61 74 74 65 72 20 62 61 63 6b 20 the latter back
1230: 74 6f 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e to changesets an
1240: 64 0a 09 23 20 20 20 20 63 6f 6e 73 74 72 75 63 d..# construc
1250: 74 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 t the correspond
1260: 69 6e 67 20 61 72 63 73 2e 0a 0a 09 69 66 20 7b ing arcs....if {
1270: 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 $log} {.. log
1280: 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 write 3 cyclebr
1290: 65 61 6b 65 72 20 7b 53 65 74 74 69 6e 67 20 75 eaker {Setting u
12a0: 70 20 6e 6f 64 65 20 64 65 70 65 6e 64 65 6e 63 p node dependenc
12b0: 69 65 73 7d 0a 09 7d 0a 0a 09 66 6f 72 65 61 63 ies}..}...foreac
12c0: 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 73 65 h cset $changese
12d0: 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 63 ts {.. foreac
12e0: 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 75 h succ [$cset su
12f0: 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 20 ccessors] {...#
1300: 43 68 61 6e 67 65 73 65 74 73 20 6d 61 79 20 68 Changesets may h
1310: 61 76 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 ave dependencies
1320: 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 0a outside of the.
1330: 09 09 23 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 ..# chosen set.
1340: 54 68 65 73 65 20 61 72 65 20 69 67 6e 6f 72 65 These are ignore
1350: 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f d...if {![$dg no
1360: 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d de exists $succ]
1370: 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 } continue...$dg
1380: 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 arc insert $cse
1390: 74 20 24 73 75 63 63 0a 0a 09 09 23 20 43 68 65 t $succ....# Che
13a0: 63 6b 20 66 6f 72 20 63 68 61 6e 67 65 73 65 74 ck for changeset
13b0: 73 20 72 65 66 65 72 65 6e 63 69 6e 67 20 74 68 s referencing th
13c0: 65 6d 73 65 6c 76 65 73 2e 20 53 75 63 68 20 61 emselves. Such a
13d0: 0a 09 09 23 20 6c 6f 6f 70 20 73 68 6f 77 73 20 ...# loop shows
13e0: 74 68 61 74 20 74 68 65 20 63 68 61 6e 67 65 73 that the changes
13f0: 65 74 20 69 6e 20 71 75 65 73 74 69 6f 6e 20 68 et in question h
1400: 61 73 0a 09 09 23 20 69 6e 74 65 72 6e 61 6c 20 as...# internal
1410: 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 53 6f dependencies. So
1420: 6d 65 74 68 69 6e 67 20 77 68 69 63 68 20 69 73 mething which is
1430: 20 73 75 70 70 6f 73 65 64 0a 09 09 23 20 74 6f supposed...# to
1440: 20 62 65 20 6e 6f 74 20 70 6f 73 73 69 62 6c 65 be not possible
1450: 2c 20 61 73 20 70 61 73 73 20 35 20 28 49 6e 69 , as pass 5 (Ini
1460: 74 43 73 65 74 73 29 20 74 61 6b 65 73 20 63 61 tCsets) takes ca
1470: 72 65 0a 09 09 23 20 74 6f 20 74 72 61 6e 73 66 re...# to transf
1480: 6f 72 6d 20 69 6e 74 65 72 6e 61 6c 20 69 6e 74 orm internal int
1490: 6f 20 65 78 74 65 72 6e 61 6c 20 64 65 70 65 6e o external depen
14a0: 64 65 6e 63 69 65 73 20 62 79 0a 09 09 23 20 62 dencies by...# b
14b0: 72 65 61 6b 69 6e 67 20 74 68 65 20 72 65 6c 65 reaking the rele
14c0: 76 61 6e 74 20 63 68 61 6e 67 65 73 65 74 73 20 vant changesets
14d0: 61 70 61 72 74 2e 20 53 6f 20 68 61 76 69 6e 67 apart. So having
14e0: 0a 09 09 23 20 6f 6e 65 20 69 6e 64 69 63 61 74 ...# one indicat
14f0: 65 73 20 62 69 67 20 74 72 6f 75 62 6c 65 20 69 es big trouble i
1500: 6e 20 70 61 73 73 20 35 2e 20 57 65 20 72 65 70 n pass 5. We rep
1510: 6f 72 74 20 74 68 65 6d 0a 09 09 23 20 61 6e 64 ort them...# and
1520: 20 64 75 6d 70 20 69 6e 74 65 72 6e 61 6c 20 73 dump internal s
1530: 74 72 75 63 74 75 72 65 73 20 74 6f 20 6d 61 6b tructures to mak
1540: 65 20 69 74 20 65 61 73 69 65 72 20 74 6f 0a 09 e it easier to..
1550: 09 23 20 74 72 61 63 65 20 74 68 65 20 6c 69 6e .# trace the lin
1560: 6b 73 20 63 61 75 73 69 6e 67 20 74 68 65 20 70 ks causing the p
1570: 72 6f 62 6c 65 6d 2e 0a 09 09 69 66 20 7b 24 73 roblem....if {$s
1580: 75 63 63 20 65 71 20 24 63 73 65 74 7d 20 7b 0a ucc eq $cset} {.
1590: 09 09 20 20 20 20 74 72 6f 75 62 6c 65 20 66 61 .. trouble fa
15a0: 74 61 6c 20 22 53 65 6c 66 2d 72 65 66 65 72 65 tal "Self-refere
15b0: 6e 63 69 6e 67 20 63 68 61 6e 67 65 73 65 74 20 ncing changeset
15c0: 3c 5b 24 63 73 65 74 20 69 64 5d 3e 22 0a 09 09 <[$cset id]>"...
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 3c 5b 24 OP changeset <[$
1600: 63 73 65 74 20 69 64 5d 3e 20 5f 5f 5f 5f 5f 5f cset id]> ______
1610: 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 5f 22 0a 09 09 ____________"...
1620: 20 20 20 20 61 72 72 61 79 20 73 65 74 20 6e 6d array set nm
1630: 61 70 20 5b 24 63 73 65 74 20 6e 65 78 74 6d 61 ap [$cset nextma
1640: 70 5d 0a 09 09 20 20 20 20 66 6f 72 65 61 63 68 p]... foreach
1650: 20 72 20 5b 6c 73 6f 72 74 20 2d 64 69 63 74 20 r [lsort -dict
1660: 5b 61 72 72 61 79 20 6e 61 6d 65 73 20 6e 6d 61 [array names nma
1670: 70 5d 5d 20 7b 0a 09 09 09 66 6f 72 65 61 63 68 p]] {....foreach
1680: 20 73 75 63 63 72 65 76 20 24 6e 6d 61 70 28 24 succrev $nmap($
1690: 72 29 20 7b 0a 09 09 09 20 20 20 20 6c 6f 67 20 r) {.... log
16a0: 77 72 69 74 65 20 32 20 63 79 63 6c 65 62 72 65 write 2 cyclebre
16b0: 61 6b 65 72 20 5c 0a 09 09 09 09 22 4c 4f 4f 50 aker \....."LOOP
16c0: 20 2a 20 72 65 76 20 3c 24 72 3e 20 2d 2d 3e 20 * rev <$r> -->
16d0: 72 65 76 20 3c 24 73 75 63 63 72 65 76 3e 20 2d rev <$succrev> -
16e0: 2d 3e 20 63 73 20 5b 6a 6f 69 6e 20 5b 73 74 72 -> cs [join [str
16f0: 75 63 74 3a 3a 6c 69 73 74 20 6d 61 70 20 5b 70 uct::list map [p
1700: 72 6f 6a 65 63 74 3a 3a 72 65 76 20 6f 66 72 65 roject::rev ofre
1710: 76 20 24 73 75 63 63 72 65 76 5d 20 5b 6d 79 70 v $succrev] [myp
1720: 72 6f 63 20 49 44 5d 5d 20 7b 20 7d 5d 22 0a 09 roc ID]] { }]"..
1730: 09 09 7d 0a 09 09 20 20 20 20 7d 0a 09 09 7d 0a ..}... }...}.
1740: 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 23 20 52 75 . }..}...# Ru
1750: 6e 20 74 68 65 20 75 73 65 72 20 68 6f 6f 6b 20 n the user hook
1760: 74 6f 20 6d 61 6e 69 70 75 6c 61 74 65 20 74 68 to manipulate th
1770: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 0a 09 e graph before..
1780: 23 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a # consummation..
1790: 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 20 4d 61 ..if {$log} { Ma
17a0: 72 6b 20 24 64 67 20 2d 73 74 61 72 74 20 7d 0a rk $dg -start }.
17b0: 09 50 72 65 48 6f 6f 6b 20 24 64 67 0a 0a 09 23 .PreHook $dg...#
17c0: 20 54 68 69 73 20 6b 69 6c 6c 73 20 74 68 65 20 This kills the
17d0: 61 70 70 6c 69 63 61 74 69 6f 6e 20 69 66 20 6c application if l
17e0: 6f 6f 70 73 20 28 73 65 65 20 61 62 6f 76 65 29 oops (see above)
17f0: 20 77 65 72 65 20 66 6f 75 6e 64 2e 0a 09 74 72 were found...tr
1800: 6f 75 62 6c 65 20 61 62 6f 72 74 3f 0a 09 72 65 ouble abort?..re
1810: 74 75 72 6e 20 20 24 64 67 0a 20 20 20 20 7d 0a turn $dg. }.
1820: 0a 20 20 20 20 23 20 49 6e 73 74 65 61 64 20 6f . # Instead o
1830: 66 20 73 65 61 72 63 68 69 6e 67 20 74 68 65 20 f searching the
1840: 77 68 6f 6c 65 20 67 72 61 70 68 20 66 6f 72 20 whole graph for
1850: 74 68 65 20 64 65 67 72 65 65 2d 30 20 6e 6f 64 the degree-0 nod
1860: 65 73 20 69 6e 0a 20 20 20 20 23 20 65 61 63 68 es in. # each
1870: 20 69 74 65 72 61 74 69 6f 6e 20 77 65 20 63 6f iteration we co
1880: 6d 70 75 74 65 20 74 68 65 20 6c 69 73 74 20 6f mpute the list o
1890: 6e 63 65 20 74 6f 20 73 74 61 72 74 2c 20 61 6e nce to start, an
18a0: 64 20 74 68 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 d then only.
18b0: 23 20 75 70 64 61 74 65 20 69 74 20 69 6e 63 72 # update it incr
18c0: 65 6d 65 6e 74 61 6c 6c 79 20 62 61 73 65 64 20 ementally based
18d0: 6f 6e 20 74 68 65 20 6f 75 74 67 6f 69 6e 67 20 on the outgoing
18e0: 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 neighbours of th
18f0: 65 0a 20 20 20 20 23 20 6e 6f 64 65 20 63 68 6f e. # node cho
1900: 73 65 6e 20 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a sen for commit..
1910: 0a 20 20 20 20 70 72 6f 63 20 49 6e 69 74 69 61 . proc Initia
1920: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 7b lizeCandidates {
1930: 64 67 7d 20 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 dg} {..# bottom
1940: 3d 20 6c 69 73 74 20 28 6c 69 73 74 20 28 6e 6f = list (list (no
1950: 64 65 2c 20 72 61 6e 67 65 20 6d 69 6e 2c 20 72 de, range min, r
1960: 61 6e 67 65 20 6d 61 78 29 29 0a 09 3a 3a 76 61 ange max))..::va
1970: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
1980: 09 66 6f 72 65 61 63 68 20 6e 20 5b 24 64 67 20 .foreach n [$dg
1990: 6e 6f 64 65 73 5d 20 7b 0a 09 20 20 20 20 69 66 nodes] {.. if
19a0: 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 {[$dg node degr
19b0: 65 65 20 2d 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 ee -in $n]} cont
19c0: 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 65 6e inue.. lappen
19d0: 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 d mybottom [lins
19e0: 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 ert [$dg node ge
19f0: 74 20 24 6e 20 74 69 6d 65 72 61 6e 67 65 5d 20 t $n timerange]
1a00: 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74 20 6d 79 0 $n]..}..set my
1a10: 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 bottom [lsort -i
1a20: 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72 20 ndex 1 -integer
1a30: 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32 20 [lsort -index 2
1a40: 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 74 74 -integer $mybott
1a50: 6f 6d 5d 5d 0a 09 53 68 6f 77 50 65 6e 64 69 6e om]]..ShowPendin
1a60: 67 4e 6f 64 65 73 0a 09 72 65 74 75 72 6e 0a 20 gNodes..return.
1a70: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 }.. proc W
1a80: 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f ithoutPredecesso
1a90: 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 r {dg nv} {..::v
1aa0: 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d ariable mybottom
1ab0: 0a 0a 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e ...upvar 1 $nv n
1ac0: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
1ad0: 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 $mybottom]} { re
1ae0: 74 75 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e turn 0 }...set n
1af0: 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 [lindex [lindex
1b00: 20 24 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d $mybottom 0] 0]
1b10: 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b ..set mybottom [
1b20: 6c 72 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d lrange $mybottom
1b30: 20 31 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 1 end]..set cha
1b40: 6e 67 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 nged 0...# Updat
1b50: 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 e list of nodes
1b60: 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 without predeces
1b70: 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 sor, based on th
1b80: 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 e..# outgoing ne
1b90: 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 ighbours of the
1ba0: 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 chosen node. Thi
1bb0: 73 20 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 s should be..# f
1bc0: 61 73 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 aster than itera
1bd0: 74 69 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c ting of the whol
1be0: 65 20 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 e set of nodes,
1bf0: 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 finding all..# w
1c00: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
1c10: 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 ors, sorting the
1c20: 6d 20 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 m by time, etc.
1c30: 70 70 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 pp...foreach out
1c40: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
1c50: 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b $n] {.. if {
1c60: 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 [$dg node degree
1c70: 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 -in $out] > 1}
1c80: 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 continue.. #
1c90: 44 65 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f Degree-1 neighbo
1ca0: 75 72 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f ur, will have no
1cb0: 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 predecessors af
1cc0: 74 65 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 ter the.. # r
1cd0: 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 emoval of n. Put
1ce0: 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 on the list...
1cf0: 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 lappend mybot
1d00: 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 tom [linsert [$d
1d10: 67 20 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 g node get $out
1d20: 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 timerange] 0 $ou
1d30: 74 5d 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e t].. set chan
1d40: 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 ged 1..}..if {$c
1d50: 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 73 hanged} {.. s
1d60: 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f et mybottom [lso
1d70: 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 rt -index 1 -int
1d80: 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 eger [lsort -ind
1d90: 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 6d ex 2 -integer $m
1da0: 79 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 ybottom]]..}...#
1db0: 20 57 65 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 We do not delet
1dc0: 65 20 74 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 e the node immed
1dd0: 69 61 74 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 iately, to allow
1de0: 20 74 68 65 20 53 61 76 65 0a 09 23 20 70 72 6f the Save..# pro
1df0: 63 65 64 75 72 65 20 74 6f 20 73 61 76 65 20 74 cedure to save t
1e00: 68 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 he dependencies
1e10: 61 73 20 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 as well (encoded
1e20: 20 69 6e 20 74 68 65 0a 09 23 20 61 72 63 73 29 in the..# arcs)
1e30: 2e 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 20 20 ...return 1.
1e40: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 53 68 6f 77 }.. proc Show
1e50: 50 65 6e 64 69 6e 67 4e 6f 64 65 73 20 7b 7d 20 PendingNodes {}
1e60: 7b 0a 09 69 66 20 7b 5b 6c 6f 67 20 76 65 72 62 {..if {[log verb
1e70: 6f 73 69 74 79 3f 5d 20 3c 20 31 30 7d 20 72 65 osity?] < 10} re
1e80: 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 62 6c 65 turn..::variable
1e90: 20 6d 79 62 6f 74 74 6f 6d 0a 09 6c 6f 67 20 77 mybottom..log w
1ea0: 72 69 74 65 20 31 30 20 63 79 63 6c 65 62 72 65 rite 10 cyclebre
1eb0: 61 6b 65 72 20 5c 0a 09 20 20 20 20 22 50 65 6e aker \.. "Pen
1ec0: 64 69 6e 67 3a 20 5b 73 74 72 75 63 74 3a 3a 6c ding: [struct::l
1ed0: 69 73 74 20 6d 61 70 20 24 6d 79 62 6f 74 74 6f ist map $mybotto
1ee0: 6d 20 5b 6d 79 70 72 6f 63 20 46 6f 72 6d 61 74 m [myproc Format
1ef0: 50 65 6e 64 69 6e 67 49 74 65 6d 5d 5d 22 0a 09 PendingItem]]"..
1f00: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
1f10: 20 20 70 72 6f 63 20 46 6f 72 6d 61 74 50 65 6e proc FormatPen
1f20: 64 69 6e 67 49 74 65 6d 20 7b 69 74 65 6d 7d 20 dingItem {item}
1f30: 7b 20 6c 72 65 70 6c 61 63 65 20 24 69 74 65 6d { lreplace $item
1f40: 20 30 20 30 20 3c 5b 5b 6c 69 6e 64 65 78 20 24 0 0 <[[lindex $
1f50: 69 74 65 6d 20 30 5d 20 69 64 5d 3e 20 7d 0a 0a item 0] id]> }..
1f60: 20 20 20 20 70 72 6f 63 20 46 69 6e 64 43 79 63 proc FindCyc
1f70: 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 68 69 le {dg} {..# Thi
1f80: 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 20 72 s procedure is r
1f90: 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 20 74 un if and only t
1fa0: 68 65 20 67 72 61 70 68 20 69 73 20 6e 6f 74 20 he graph is not
1fb0: 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 6c 6c empty and..# all
1fc0: 20 6e 6f 64 65 73 20 68 61 76 65 20 70 72 65 64 nodes have pred
1fd0: 65 63 65 73 73 6f 72 73 2e 20 54 68 69 73 20 6d ecessors. This m
1fe0: 65 61 6e 73 20 74 68 61 74 20 65 61 63 68 20 6e eans that each n
1ff0: 6f 64 65 20 69 73 0a 09 23 20 65 69 74 68 65 72 ode is..# either
2000: 20 70 61 72 74 20 6f 66 20 61 20 63 79 63 6c 65 part of a cycle
2010: 20 6f 72 20 28 69 6e 64 69 72 65 63 74 6c 79 29 or (indirectly)
2020: 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 61 20 depending on a
2030: 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 79 63 node..# in a cyc
2040: 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 61 72 74 le. We can start
2050: 20 61 74 20 61 6e 20 61 72 62 69 74 72 61 72 79 at an arbitrary
2060: 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 69 74 node, follow it
2070: 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 65 64 s..# incoming ed
2080: 67 65 73 20 74 6f 20 69 74 73 20 70 72 65 64 65 ges to its prede
2090: 63 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 77 65 cessors until we
20a0: 20 73 65 65 20 61 20 6e 6f 64 65 20 61 0a 09 23 see a node a..#
20b0: 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 54 68 second time. Th
20c0: 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 20 74 at node closes t
20d0: 68 65 20 63 79 63 6c 65 20 61 6e 64 20 74 68 65 he cycle and the
20e0: 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a 09 23 beginning is..#
20f0: 20 69 74 73 20 66 69 72 73 74 20 6f 63 63 75 72 its first occur
2100: 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 74 20 ence. Note that
2110: 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 61 6e we can choose an
2120: 20 61 72 62 69 74 72 61 72 79 0a 09 23 20 70 72 arbitrary..# pr
2130: 65 64 65 63 65 73 73 6f 72 20 6f 66 20 65 61 63 edecessor of eac
2140: 68 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c 2c 20 h node as well,
2150: 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 74 we do not have t
2160: 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 57 65 o search....# We
2170: 20 72 65 63 6f 72 64 20 66 6f 72 20 65 61 63 68 record for each
2180: 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 78 20 node the index
2190: 6f 66 20 74 68 65 20 66 69 72 73 74 20 61 70 70 of the first app
21a0: 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 74 68 earance in..# th
21b0: 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 20 69 e path, making i
21c0: 74 20 65 61 73 79 20 61 74 20 74 68 65 20 65 6e t easy at the en
21d0: 64 20 74 6f 20 63 75 74 20 74 68 65 20 63 79 63 d to cut the cyc
21e0: 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e 0a 0a le from..# it...
21f0: 09 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 .# Choose arbitr
2200: 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 61 72 ary node to star
2210: 74 20 6f 75 72 20 73 65 61 72 63 68 20 61 74 2e t our search at.
2220: 0a 09 73 65 74 20 73 74 61 72 74 20 5b 6c 69 6e ..set start [lin
2230: 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 dex [$dg nodes]
2240: 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c 69 7a 0]...# Initializ
2250: 65 20 73 74 61 74 65 2c 20 70 61 74 68 20 6f 66 e state, path of
2260: 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 6e 64 seen nodes, and
2270: 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 65 74 when seen...set
2280: 20 20 20 20 20 20 20 70 61 74 68 20 7b 7d 0a 09 path {}..
2290: 61 72 72 61 79 20 73 65 74 20 73 65 65 6e 20 7b array set seen {
22a0: 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a }...while {1} {.
22b0: 09 20 20 20 20 23 20 53 74 6f 70 20 73 65 61 72 . # Stop sear
22c0: 63 68 69 6e 67 20 77 68 65 6e 20 77 65 20 68 61 ching when we ha
22d0: 76 65 20 73 65 65 6e 20 74 68 65 20 63 75 72 72 ve seen the curr
22e0: 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 23 20 ent node.. #
22f0: 61 6c 72 65 61 64 79 2c 20 74 68 65 20 63 69 72 already, the cir
2300: 63 6c 65 20 68 61 73 20 62 65 65 6e 20 63 6c 6f cle has been clo
2310: 73 65 64 2e 0a 09 20 20 20 20 69 66 20 7b 5b 69 sed... if {[i
2320: 6e 66 6f 20 65 78 69 73 74 73 20 73 65 65 6e 28 nfo exists seen(
2330: 24 73 74 61 72 74 29 5d 7d 20 62 72 65 61 6b 0a $start)]} break.
2340: 09 20 20 20 20 6c 61 70 70 65 6e 64 20 70 61 74 . lappend pat
2350: 68 20 24 73 74 61 72 74 0a 09 20 20 20 20 73 65 h $start.. se
2360: 74 20 73 65 65 6e 28 24 73 74 61 72 74 29 20 5b t seen($start) [
2370: 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 20 24 expr {[llength $
2380: 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 20 23 path]-1}].. #
2390: 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 72 Choose arbitrar
23a0: 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 20 y predecessor..
23b0: 20 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c 69 set start [li
23c0: 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 20 ndex [$dg nodes
23d0: 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a 09 -in $start] 0]..
23e0: 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 75 }...return [stru
23f0: 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 65 ct::list reverse
2400: 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 24 [lrange $path $
2410: 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e 64 seen($start) end
2420: 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 ]]. }.. pr
2430: 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 7b 20 72 oc ID {cset} { r
2440: 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 74 20 69 eturn "<[$cset i
2450: 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 72 6f 63 d]>" }.. proc
2460: 20 42 72 65 61 6b 43 79 63 6c 65 20 7b 64 67 20 BreakCycle {dg
2470: 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 68 65 20 cycle} {..# The
2480: 63 79 63 6c 65 20 77 65 20 68 61 76 65 20 67 6f cycle we have go
2490: 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 6e 20 62 tten is broken b
24a0: 79 20 62 72 65 61 6b 69 6e 67 20 61 70 61 72 74 y breaking apart
24b0: 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f 72 65 20 one or..# more
24c0: 6f 66 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 of the changeset
24d0: 73 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2e 20 s in the cycle.
24e0: 54 68 69 73 20 63 61 75 73 65 73 20 75 73 20 74 This causes us t
24f0: 6f 0a 09 23 20 63 72 65 61 74 65 20 6f 6e 65 20 o..# create one
2500: 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 65 73 65 or more changese
2510: 74 73 20 77 68 69 63 68 20 61 72 65 20 74 6f 20 ts which are to
2520: 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c 0a 09 23 be committed,..#
2530: 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 67 72 added to the gr
2540: 61 70 68 2c 20 65 74 63 2e 20 70 70 2e 0a 0a 09 aph, etc. pp....
2550: 23 20 4e 4f 54 45 2f 54 4f 44 4f 2e 20 4d 6f 76 # NOTE/TODO. Mov
2560: 65 20 74 68 69 73 20 6d 61 70 20 6f 70 65 72 61 e this map opera
2570: 74 69 6f 6e 20 74 6f 20 70 72 6f 6a 65 63 74 3a tion to project:
2580: 3a 72 65 76 2c 20 61 73 20 74 79 70 65 6d 65 74 :rev, as typemet
2590: 68 6f 64 2e 0a 09 73 65 74 20 63 70 72 69 6e 74 hod...set cprint
25a0: 20 5b 6a 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a [join [struct::
25b0: 6c 69 73 74 20 6d 61 70 20 24 63 79 63 6c 65 20 list map $cycle
25c0: 5b 6d 79 70 72 6f 63 20 49 44 5d 5d 20 7b 20 7d [myproc ID]] { }
25d0: 5d 0a 0a 09 6c 61 70 70 65 6e 64 20 63 79 63 6c ]...lappend cycl
25e0: 65 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 e [lindex $cycle
25f0: 20 30 5d 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 0] [lindex $cyc
2600: 6c 65 20 31 5d 0a 09 73 65 74 20 62 65 73 74 6c le 1]..set bestl
2610: 69 6e 6b 20 7b 7d 0a 09 73 65 74 20 62 65 73 74 ink {}..set best
2620: 6e 6f 64 65 20 7b 7d 0a 0a 09 66 6f 72 65 61 63 node {}...foreac
2630: 68 20 5c 0a 09 20 20 20 20 70 72 65 76 20 5b 6c h \.. prev [l
2640: 72 61 6e 67 65 20 24 63 79 63 6c 65 20 30 20 65 range $cycle 0 e
2650: 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 20 63 73 65 nd-2] \.. cse
2660: 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 t [lrange $cycle
2670: 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 20 1 end-1] \..
2680: 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 20 24 63 next [lrange $c
2690: 79 63 6c 65 20 32 20 65 6e 64 5d 20 7b 0a 0a 09 ycle 2 end] {...
26a0: 09 23 20 45 61 63 68 20 74 72 69 70 6c 65 20 50 .# Each triple P
26b0: 52 45 56 20 2d 3e 20 43 53 45 54 20 2d 3e 20 4e REV -> CSET -> N
26c0: 45 58 54 20 6f 66 20 63 68 61 6e 67 65 73 65 74 EXT of changeset
26d0: 73 2c 20 61 0a 09 09 23 20 27 6c 69 6e 6b 27 20 s, a...# 'link'
26e0: 69 6e 20 74 68 65 20 63 79 63 6c 65 2c 20 69 73 in the cycle, is
26f0: 20 61 6e 61 6c 79 73 65 64 20 61 6e 64 20 74 68 analysed and th
2700: 65 20 62 65 73 74 0a 09 09 23 20 6c 6f 63 61 74 e best...# locat
2710: 69 6f 6e 20 77 68 65 72 65 20 74 6f 20 61 74 20 ion where to at
2720: 6c 65 61 73 74 20 77 65 61 6b 65 6e 20 74 68 65 least weaken the
2730: 20 63 79 63 6c 65 20 69 73 0a 09 09 23 20 63 68 cycle is...# ch
2740: 6f 73 65 6e 20 66 6f 72 20 66 75 72 74 68 65 72 osen for further
2750: 20 70 72 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 09 processing.....
2760: 73 65 74 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 63 set link [projec
2770: 74 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 55 54 4f t::revlink %AUTO
2780: 25 20 24 70 72 65 76 20 24 63 73 65 74 20 24 6e % $prev $cset $n
2790: 65 78 74 5d 0a 09 09 69 66 20 7b 24 62 65 73 74 ext]...if {$best
27a0: 6c 69 6e 6b 20 65 71 20 22 22 7d 20 7b 0a 09 09 link eq ""} {...
27b0: 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e 6b set bestlink
27c0: 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 $link... set
27d0: 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 0a bestnode $cset.
27e0: 09 09 7d 20 65 6c 73 65 69 66 20 7b 5b 24 6c 69 ..} elseif {[$li
27f0: 6e 6b 20 62 65 74 74 65 72 74 68 61 6e 20 24 62 nk betterthan $b
2800: 65 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 20 estlink]} {...
2810: 20 20 24 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 $bestlink dest
2820: 72 6f 79 0a 09 09 20 20 20 20 73 65 74 20 62 65 roy... set be
2830: 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 stlink $link...
2840: 20 20 20 73 65 74 20 62 65 73 74 6e 6f 64 65 20 set bestnode
2850: 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 65 20 7b $cset...} else {
2860: 0a 09 09 20 20 20 20 24 6c 69 6e 6b 20 64 65 73 ... $link des
2870: 74 72 6f 79 0a 09 09 7d 0a 09 20 20 20 20 7d 0a troy...}.. }.
2880: 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 20 63 79 ..log write 5 cy
2890: 63 6c 65 62 72 65 61 6b 65 72 20 22 42 72 65 61 clebreaker "Brea
28a0: 6b 69 6e 67 20 63 79 63 6c 65 20 28 24 63 70 72 king cycle ($cpr
28b0: 69 6e 74 29 20 62 79 20 73 70 6c 69 74 74 69 6e int) by splittin
28c0: 67 20 63 68 61 6e 67 65 73 65 74 20 3c 5b 24 62 g changeset <[$b
28d0: 65 73 74 6e 6f 64 65 20 69 64 5d 3e 22 0a 09 73 estnode id]>"..s
28e0: 65 74 20 49 44 20 5b 24 62 65 73 74 6e 6f 64 65 et ID [$bestnode
28f0: 20 69 64 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d id]..Mark $dg -
2900: 24 7b 49 44 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 ${ID}-before...s
2910: 65 74 20 6e 65 77 63 73 65 74 73 20 5b 24 62 65 et newcsets [$be
2920: 73 74 6c 69 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 stlink break]..$
2930: 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 bestlink destroy
2940: 0a 0a 20 20 20 20 20 20 20 20 23 20 41 74 20 74 .. # At t
2950: 68 69 73 20 70 6f 69 6e 74 20 74 68 65 20 6f 6c his point the ol
2960: 64 20 63 68 61 6e 67 65 73 65 74 20 28 42 45 53 d changeset (BES
2970: 54 4e 4f 44 45 29 20 69 73 20 67 6f 6e 65 0a 20 TNODE) is gone.
2980: 20 20 20 20 20 20 20 23 20 61 6c 72 65 61 64 79 # already
2990: 2e 20 57 65 20 72 65 6d 6f 76 65 20 69 74 20 66 . We remove it f
29a0: 72 6f 6d 20 74 68 65 20 67 72 61 70 68 20 61 73 rom the graph as
29b0: 20 77 65 6c 6c 20 61 6e 64 20 74 68 65 6e 20 65 well and then e
29c0: 6e 74 65 72 0a 20 20 20 20 20 20 20 20 23 20 74 nter. # t
29d0: 68 65 20 66 72 61 67 6d 65 6e 74 73 20 67 65 6e he fragments gen
29e0: 65 72 61 74 65 64 20 66 6f 72 20 69 74 2e 0a 0a erated for it...
29f0: 09 52 65 70 6c 61 63 65 20 24 64 67 20 24 62 65 .Replace $dg $be
2a00: 73 74 6e 6f 64 65 20 24 6e 65 77 63 73 65 74 73 stnode $newcsets
2a10: 0a 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 ...Mark $dg -${I
2a20: 44 7d 2d 61 66 74 65 72 0a 09 72 65 74 75 72 6e D}-after..return
2a30: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 54 4f . }.. # TO
2a40: 44 4f 3a 20 54 68 69 73 20 73 68 6f 75 6c 64 20 DO: This should
2a50: 62 65 20 61 20 67 72 61 70 68 20 6d 65 74 68 6f be a graph metho
2a60: 64 2e 0a 20 20 20 20 70 72 6f 63 20 48 61 73 41 d.. proc HasA
2a70: 72 63 20 7b 64 67 20 61 20 62 7d 20 7b 0a 09 23 rc {dg a b} {..#
2a80: 38 2e 35 3a 20 72 65 74 75 72 6e 20 5b 65 78 70 8.5: return [exp
2a90: 72 20 7b 24 62 20 69 6e 20 5b 24 64 67 20 6e 6f r {$b in [$dg no
2aa0: 64 65 73 20 2d 6f 75 74 20 24 61 5d 7d 5d 0a 09 des -out $a]}]..
2ab0: 69 66 20 7b 5b 6c 73 65 61 72 63 68 20 2d 65 78 if {[lsearch -ex
2ac0: 61 63 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d act [$dg nodes -
2ad0: 6f 75 74 20 24 61 5d 20 24 62 5d 20 3c 20 30 7d out $a] $b] < 0}
2ae0: 20 7b 20 72 65 74 75 72 6e 20 30 20 7d 0a 09 72 { return 0 }..r
2af0: 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 eturn 1. }..
2b00: 20 20 20 70 72 6f 63 20 4d 61 72 6b 20 7b 64 67 proc Mark {dg
2b10: 20 7b 73 75 66 66 69 78 20 7b 7d 7d 20 7b 73 75 {suffix {}} {su
2b20: 62 67 72 61 70 68 20 7b 7d 7d 7d 20 7b 0a 09 3a bgraph {}}} {..:
2b30: 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 :variable mydotd
2b40: 65 73 74 69 6e 61 74 69 6f 6e 0a 09 69 66 20 7b estination..if {
2b50: 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f $mydotdestinatio
2b60: 6e 20 65 71 20 22 22 7d 20 72 65 74 75 72 6e 0a n eq ""} return.
2b70: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f .::variable mydo
2b80: 74 70 72 65 66 69 78 0a 09 3a 3a 76 61 72 69 61 tprefix..::varia
2b90: 62 6c 65 20 6d 79 64 6f 74 69 64 0a 09 73 65 74 ble mydotid..set
2ba0: 20 66 6e 61 6d 65 20 24 6d 79 64 6f 74 64 65 73 fname $mydotdes
2bb0: 74 69 6e 61 74 69 6f 6e 2f 24 7b 6d 79 64 6f 74 tination/${mydot
2bc0: 70 72 65 66 69 78 7d 24 7b 6d 79 64 6f 74 69 64 prefix}${mydotid
2bd0: 7d 24 7b 73 75 66 66 69 78 7d 2e 64 6f 74 0a 09 }${suffix}.dot..
2be0: 66 69 6c 65 20 6d 6b 64 69 72 20 5b 66 69 6c 65 file mkdir [file
2bf0: 20 64 69 72 6e 61 6d 65 20 24 66 6e 61 6d 65 5d dirname $fname]
2c00: 0a 09 64 6f 74 20 77 72 69 74 65 20 24 64 67 20 ..dot write $dg
2c10: 24 6d 79 64 6f 74 70 72 65 66 69 78 24 73 75 66 $mydotprefix$suf
2c20: 66 69 78 20 24 66 6e 61 6d 65 20 24 73 75 62 67 fix $fname $subg
2c30: 72 61 70 68 0a 09 69 6e 63 72 20 6d 79 64 6f 74 raph..incr mydot
2c40: 69 64 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 id...log write 5
2c50: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 2e cyclebreaker ".
2c60: 64 6f 74 20 65 78 70 6f 72 74 20 24 66 6e 61 6d dot export $fnam
2c70: 65 22 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d e"..return. }
2c80: 0a 0a 20 20 20 20 70 72 6f 63 20 52 65 70 6c 61 .. proc Repla
2c90: 63 65 20 7b 64 67 20 6e 20 72 65 70 6c 61 63 65 ce {dg n replace
2ca0: 6d 65 6e 74 73 7d 20 7b 0a 09 23 20 4e 4f 54 45 ments} {..# NOTE
2cb0: 2e 20 57 65 20 68 61 76 65 20 74 6f 20 67 65 74 . We have to get
2cc0: 20 74 68 65 20 6c 69 73 74 20 6f 66 20 69 6e 63 the list of inc
2cd0: 6f 6d 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 oming neighbours
2ce0: 20 61 6e 64 0a 09 23 20 72 65 63 6f 6d 70 75 74 and..# recomput
2cf0: 65 20 74 68 65 69 72 20 73 75 63 63 65 73 73 6f e their successo
2d00: 72 73 20 61 66 74 65 72 20 74 68 65 20 6e 65 77 rs after the new
2d10: 20 6e 6f 64 65 73 20 68 61 76 65 20 62 65 65 6e nodes have been
2d20: 0a 09 23 20 69 6e 73 65 72 74 65 64 2e 20 54 68 ..# inserted. Th
2d30: 65 69 72 20 6f 75 74 67 6f 69 6e 67 20 61 72 63 eir outgoing arc
2d40: 73 20 77 69 6c 6c 20 6e 6f 77 20 67 6f 20 74 6f s will now go to
2d50: 20 6f 6e 65 20 6f 72 20 62 6f 74 68 20 6f 66 0a one or both of.
2d60: 09 23 20 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 .# the new nodes
2d70: 2c 20 61 6e 64 20 6e 6f 74 20 72 65 64 6f 69 6e , and not redoin
2d80: 67 20 74 68 65 6d 20 6d 61 79 20 63 61 75 73 65 g them may cause
2d90: 20 75 73 20 74 6f 20 66 6f 72 67 65 74 0a 09 23 us to forget..#
2da0: 20 63 69 72 63 6c 65 73 2c 20 6c 65 61 76 69 6e circles, leavin
2db0: 67 20 74 68 65 6d 20 69 6e 2c 20 75 6e 62 72 6f g them in, unbro
2dc0: 6b 65 6e 2e 0a 0a 09 73 65 74 20 70 72 65 20 5b ken....set pre [
2dd0: 24 64 67 20 6e 6f 64 65 73 20 2d 69 6e 20 24 6e $dg nodes -in $n
2de0: 5d 0a 0a 20 20 20 20 20 20 20 20 24 64 67 20 6e ].. $dg n
2df0: 6f 64 65 20 64 65 6c 65 74 65 20 24 6e 0a 0a 09 ode delete $n...
2e00: 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 72 65 foreach cset $re
2e10: 70 6c 61 63 65 6d 65 6e 74 73 20 7b 0a 09 20 20 placements {..
2e20: 20 20 24 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 $dg node inser
2e30: 74 20 24 63 73 65 74 0a 09 20 20 20 20 24 64 67 t $cset.. $dg
2e40: 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 node set $cs
2e50: 65 74 20 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 et timerange [$c
2e60: 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 set timerange]..
2e70: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
2e80: 20 20 20 20 24 63 73 65 74 20 6c 61 62 65 6c 20 $cset label
2e90: 20 20 20 20 5b 49 44 20 24 63 73 65 74 5d 0a 09 [ID $cset]..
2ea0: 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 $dg node set
2eb0: 20 20 20 20 24 63 73 65 74 20 5f 5f 69 64 5f 5f $cset __id__
2ec0: 20 20 20 20 5b 24 63 73 65 74 20 69 64 5d 0a 09 [$cset id]..
2ed0: 7d 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 }...foreach cset
2ee0: 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 73 20 7b $replacements {
2ef0: 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 .. foreach su
2f00: 63 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 cc [$cset succes
2f10: 73 6f 72 73 5d 20 7b 0a 09 09 23 20 54 68 65 20 sors] {...# The
2f20: 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d new changesets m
2f30: 61 79 20 68 61 76 65 20 64 65 70 65 6e 64 65 6e ay have dependen
2f40: 63 69 65 73 20 6f 75 74 73 69 64 65 20 6f 66 0a cies outside of.
2f50: 09 09 23 20 74 68 65 20 63 68 6f 73 65 6e 20 73 ..# the chosen s
2f60: 65 74 2e 20 54 68 65 73 65 20 61 72 65 20 69 67 et. These are ig
2f70: 6e 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 nored...if {![$d
2f80: 67 20 6e 6f 64 65 20 65 78 69 73 74 73 20 24 73 g node exists $s
2f90: 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 ucc]} continue..
2fa0: 09 24 64 67 20 61 72 63 20 69 6e 73 65 72 74 20 .$dg arc insert
2fb0: 24 63 73 65 74 20 24 73 75 63 63 0a 09 09 69 66 $cset $succ...if
2fc0: 20 7b 24 73 75 63 63 20 65 71 20 24 63 73 65 74 {$succ eq $cset
2fd0: 7d 20 7b 0a 09 09 20 20 20 20 74 72 6f 75 62 6c } {... troubl
2fe0: 65 20 69 6e 74 65 72 6e 61 6c 20 22 53 65 6c 66 e internal "Self
2ff0: 2d 72 65 66 65 72 65 6e 63 69 6e 67 20 63 68 61 -referencing cha
3000: 6e 67 65 73 65 74 20 3c 5b 24 63 73 65 74 20 69 ngeset <[$cset i
3010: 64 5d 3e 22 0a 09 09 7d 0a 09 20 20 20 20 7d 0a d]>"...}.. }.
3020: 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 .}..foreach cset
3030: 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 6f 72 $pre {.. for
3040: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
3050: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
3060: 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 68 65 .# Note that the
3070: 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 64 79 arc may already
3080: 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 67 72 exist in the gr
3090: 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f 20 69 aph. If...# so i
30a0: 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 6e 65 gnore it. The ne
30b0: 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d 61 79 w changesets may
30c0: 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 6e 64 have...# depend
30d0: 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 20 6f encies outside o
30e0: 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 65 74 f the chosen set
30f0: 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 23 20 . These are...#
3100: 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b ignored...if {![
3110: 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 73 20 $dg node exists
3120: 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 $succ]} continue
3130: 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 20 24 ...if {[HasArc $
3140: 64 67 20 24 63 73 65 74 20 24 73 75 63 63 5d 7d dg $cset $succ]}
3150: 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f 44 4f continue;# TODO
3160: 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 70 68 should be graph
3170: 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 20 61 method....$dg a
3180: 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 rc insert $cset
3190: 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a $succ.. }..}.
31a0: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
31b0: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
31c0: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
31d0: 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 20 ###########.
31e0: 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 6e 76 6f ## Callback invo
31f0: 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 20 20 20 kation .....
3200: 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 7b 67 72 proc PreHook {gr
3210: 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 65 20 74 aph} {..# Give t
3220: 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 63 he user of the c
3230: 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 65 ycle breaker the
3240: 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f 20 opportunity to
3250: 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 65 work..# with the
3260: 20 67 72 61 70 68 20 62 65 74 77 65 65 6e 20 73 graph between s
3270: 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 75 6d 6d etup and consumm
3280: 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 72 69 61 ation....::varia
3290: 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a 09 69 66 ble myprecmd..if
32a0: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 70 {![llength $myp
32b0: 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a recmd]} return..
32c0: 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e .uplevel #0 [lin
32d0: 73 65 72 74 20 24 6d 79 70 72 65 63 6d 64 20 65 sert $myprecmd e
32e0: 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d 61 72 6b nd $graph]..Mark
32f0: 20 24 67 72 61 70 68 20 2d 70 72 65 2d 64 6f 6e $graph -pre-don
3300: 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a e..return. }.
3310: 0a 20 20 20 20 70 72 6f 63 20 50 72 6f 63 65 73 . proc Proces
3320: 73 65 64 48 6f 6f 6b 20 7b 64 67 20 63 73 65 74 sedHook {dg cset
3330: 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 76 65 20 pos} {..# Give
3340: 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 the user of the
3350: 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 cycle breaker th
3360: 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f e opportunity to
3370: 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 work..# with th
3380: 65 20 63 68 61 6e 67 65 73 65 74 20 62 65 66 6f e changeset befo
3390: 72 65 20 69 74 20 69 73 20 72 65 6d 6f 76 65 64 re it is removed
33a0: 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 68 2e from the graph.
33b0: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
33c0: 73 61 76 65 63 6d 64 0a 09 69 66 20 7b 21 5b 6c savecmd..if {![l
33d0: 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 65 63 6d length $mysavecm
33e0: 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 75 70 6c d]} return...upl
33f0: 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 evel #0 [linsert
3400: 20 24 6d 79 73 61 76 65 63 6d 64 20 65 6e 64 20 $mysavecmd end
3410: 24 64 67 20 24 70 6f 73 20 24 63 73 65 74 5d 0a $dg $pos $cset].
3420: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
3430: 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 79 63 proc BreakCyc
3440: 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 7b leHook {graph} {
3450: 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 6f 20 ..# Call out to
3460: 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 6f 72 the chosen algor
3470: 69 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 20 62 ithm for cycle b
3480: 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 6e 67 reaking. Finding
3490: 0a 09 23 20 61 20 63 79 63 6c 65 20 69 66 20 6e ..# a cycle if n
34a0: 6f 20 62 72 65 61 6b 65 72 20 77 61 73 20 63 68 o breaker was ch
34b0: 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 72 6f 72 osen is an error
34c0: 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d ....::variable m
34d0: 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 7b 21 ybreakcmd..if {!
34e0: 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 65 61 [llength $mybrea
34f0: 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 74 72 kcmd]} {.. tr
3500: 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 46 6f 75 ouble fatal "Fou
3510: 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 78 70 65 nd a cycle, expe
3520: 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 20 20 cting none."..
3530: 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 75 70 exit 1..}...up
3540: 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 level #0 [linser
3550: 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 65 6e t $mybreakcmd en
3560: 64 20 24 67 72 61 70 68 5d 0a 09 72 65 74 75 72 d $graph]..retur
3570: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
3580: 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b 7d 20 c ClearHooks {}
3590: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 {..::variable my
35a0: 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 3a 3a 76 precmd {}..::v
35b0: 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d ariable mysavecm
35c0: 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 62 6c d {}..::variabl
35d0: 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b 7d 0a e mybreakcmd {}.
35e0: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
35f0: 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 23 # # ## ### ##
3600: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
3610: 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 20 ##########..
3620: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 61 typevariable mya
3630: 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f 75 t 0 ; # Cou
3640: 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 20 nter for commit
3650: 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 20 ids for the....
3660: 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 65 # changese
3670: 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 ts.. typevari
3680: 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b 7d able mybottom {}
3690: 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 65 ; # List of the
36a0: 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 73 candidate nodes
36b0: 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 23 for.... #
36c0: 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 20 committing...
36d0: 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d typevariable m
36e0: 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 23 yprecmd {} ; #
36f0: 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e 67 Callback, chang
3700: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 77 e graph before w
3710: 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 72 alk.. typevar
3720: 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 iable mysavecmd
3730: 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b {} ; # Callback
3740: 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 , for each proce
3750: 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 74 ssed node.. t
3760: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 72 ypevariable mybr
3770: 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 61 eakcmd {} ; # Ca
3780: 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 68 llback, for each
3790: 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 found cycle...
37a0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
37b0: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
37c0: 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 74 {} ; # Destinat
37d0: 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 6f ion directory fo
37e0: 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 20 r the.....
37f0: 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 6f # generated .do
3800: 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 70 t files.. typ
3810: 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 evariable mydotp
3820: 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b 20 refix {} ;
3830: 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f 74 # Prefix for dot
3840: 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 09 files when.....
3850: 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 69 # exporti
3860: 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a 20 ng the graphs..
3870: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3880: 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 20 mydotid
3890: 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 0 ; # Counter
38a0: 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 6d for dot file nam
38b0: 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 67 e..... # g
38c0: 65 6e 65 72 61 74 69 6f 6e 2e 0a 0a 20 20 20 20 eneration...
38d0: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
38e0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
38f0: 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 #######. ## C
3900: 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 onfiguration..
3910: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 pragma -hasins
3920: 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 tances no ; #
3930: 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 singleton. pr
3940: 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 agma -hastypeinf
3950: 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 o no ; # no i
3960: 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 ntrospection.
3970: 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 pragma -hastype
3980: 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 destroy no ; # i
3990: 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 mmortal.. # #
39a0: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
39b0: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
39c0: 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 ####.}..namespac
39d0: 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 e eval ::vc::fos
39e0: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
39f0: 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 {. namespace
3a00: 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 export cyclebre
3a10: 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 aker. namespa
3a20: 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 ce eval cyclebre
3a30: 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 aker {..namespac
3a40: 65 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b e eval project {
3a50: 0a 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 .. namespace
3a60: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 import ::vc::fos
3a70: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 sil::import::cvs
3a80: 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a 09 ::project::rev..
3a90: 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d namespace im
3aa0: 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 port ::vc::fossi
3ab0: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a l::import::cvs::
3ac0: 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e 6b project::revlink
3ad0: 0a 09 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 ..}..namespace i
3ae0: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c mport ::vc::tool
3af0: 73 3a 3a 6d 69 73 63 3a 3a 2a 0a 09 6e 61 6d 65 s::misc::*..name
3b00: 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 space import ::v
3b10: 63 3a 3a 74 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 6e c::tools::log..n
3b20: 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 amespace import
3b30: 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 74 72 6f ::vc::tools::tro
3b40: 75 62 6c 65 0a 09 6e 61 6d 65 73 70 61 63 65 20 uble..namespace
3b50: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
3b60: 6c 73 3a 3a 64 6f 74 0a 09 6c 6f 67 20 72 65 67 ls::dot..log reg
3b70: 69 73 74 65 72 20 63 79 63 6c 65 62 72 65 61 6b ister cyclebreak
3b80: 65 72 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 23 20 er. }.}..# #
3b90: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
3ba0: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
3bb0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
3bc0: 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 61 #########.## Rea
3bd0: 64 79 0a 0a 70 61 63 6b 61 67 65 20 70 72 6f 76 dy..package prov
3be0: 69 64 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a ide vc::fossil::
3bf0: 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 63 import::cvs::cyc
3c00: 6c 65 62 72 65 61 6b 65 72 20 31 2e 30 0a 72 65 lebreaker 1.0.re
3c10: 74 75 72 6e 0a turn.