Artifact 999857d4f3483326b6bd38ae7b9fbdb9ef244c69:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[2a0ec504c5]
- Cycle breaker, API change. The changesets are now communicated via a retrieval callback instead of directly. Updated passes 6 and 7. This allowed us to move the start/done graph exports into the cyclebreaker as well. Changeset selection in pass 8 now in separate command too for this.
by
aku on
2007-11-21 04:36:13.
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: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
08c0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
08d0: 23 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 70 #######.. typ
08e0: 65 6d 65 74 68 6f 64 20 72 75 6e 20 7b 6c 61 62 emethod run {lab
08f0: 65 6c 20 63 68 61 6e 67 65 73 65 74 63 6d 64 7d el changesetcmd}
0900: 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d {..::variable m
0910: 79 61 74 20 20 20 20 20 20 20 20 30 0a 09 3a 3a yat 0..::
0920: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 variable mydotpr
0930: 65 66 69 78 20 24 6c 61 62 65 6c 0a 09 3a 3a 76 efix $label..::v
0940: 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 20 ariable mydotid
0950: 20 20 20 20 30 0a 0a 09 23 20 57 65 20 63 72 65 0...# We cre
0960: 61 74 65 20 61 20 67 72 61 70 68 20 6f 66 20 74 ate a graph of t
0970: 68 65 20 72 65 76 69 73 69 6f 6e 20 63 68 61 6e he revision chan
0980: 67 65 73 65 74 73 2c 20 75 73 69 6e 67 20 74 68 gesets, using th
0990: 65 20 66 69 6c 65 0a 09 23 20 6c 65 76 65 6c 20 e file..# level
09a0: 64 65 70 65 6e 64 65 6e 63 69 65 73 20 74 6f 20 dependencies to
09b0: 63 6f 6e 73 74 72 75 63 74 20 61 20 66 69 72 73 construct a firs
09c0: 74 20 61 70 70 72 6f 78 69 6d 61 74 69 6f 6e 20 t approximation
09d0: 6f 66 20 74 68 65 0a 09 23 20 64 65 70 65 6e 64 of the..# depend
09e0: 65 6e 63 69 65 73 20 61 74 20 74 68 65 20 70 72 encies at the pr
09f0: 6f 6a 65 63 74 20 6c 65 76 65 6c 2e 20 54 68 65 oject level. The
0a00: 6e 20 77 65 20 6c 6f 6f 6b 20 66 6f 72 20 63 79 n we look for cy
0a10: 63 6c 65 73 0a 09 23 20 69 6e 20 74 68 61 74 20 cles..# in that
0a20: 67 72 61 70 68 20 61 6e 64 20 62 72 65 61 6b 20 graph and break
0a30: 74 68 65 6d 2e 0a 0a 09 23 20 31 2e 20 43 72 65 them....# 1. Cre
0a40: 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 20 61 6c ate nodes for al
0a50: 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e 67 l relevant chang
0a60: 65 73 65 74 73 20 61 6e 64 20 61 20 6d 61 70 70 esets and a mapp
0a70: 69 6e 67 0a 09 23 20 20 20 20 66 72 6f 6d 20 74 ing..# from t
0a80: 68 65 20 72 65 76 69 73 69 6f 6e 73 20 74 6f 20 he revisions to
0a90: 74 68 65 69 72 20 63 68 61 6e 67 65 73 65 74 73 their changesets
0aa0: 2f 6e 6f 64 65 73 2e 0a 0a 09 73 65 74 20 63 68 /nodes....set ch
0ab0: 61 6e 67 65 73 65 74 73 20 5b 75 70 6c 65 76 65 angesets [upleve
0ac0: 6c 20 23 30 20 24 63 68 61 6e 67 65 73 65 74 63 l #0 $changesetc
0ad0: 6d 64 5d 0a 09 73 65 74 20 64 67 20 5b 53 65 74 md]..set dg [Set
0ae0: 75 70 20 24 63 68 61 6e 67 65 73 65 74 73 5d 0a up $changesets].
0af0: 0a 09 23 20 33 2e 20 4c 61 73 74 6c 79 20 77 65 ..# 3. Lastly we
0b00: 20 69 74 65 72 61 74 65 20 74 68 65 20 67 72 61 iterate the gra
0b10: 70 68 20 74 6f 70 6f 6c 6f 67 69 63 61 6c 6c 79 ph topologically
0b20: 2e 20 57 65 20 6d 61 72 6b 20 6f 66 66 0a 09 23 . We mark off..#
0b30: 20 20 20 20 74 68 65 20 6e 6f 64 65 73 20 77 68 the nodes wh
0b40: 69 63 68 20 68 61 76 65 20 6e 6f 20 70 72 65 64 ich have no pred
0b50: 65 63 65 73 73 6f 72 73 2c 20 69 6e 20 6f 72 64 ecessors, in ord
0b60: 65 72 20 66 72 6f 6d 0a 09 23 20 20 20 20 6f 6c er from..# ol
0b70: 64 65 73 74 20 74 6f 20 79 6f 75 6e 67 65 73 74 dest to youngest
0b80: 2c 20 73 61 76 69 6e 67 20 61 6e 64 20 72 65 6d , saving and rem
0b90: 6f 76 69 6e 67 20 64 65 70 65 6e 64 65 6e 63 69 oving dependenci
0ba0: 65 73 2e 20 49 66 0a 09 23 20 20 20 20 77 65 20 es. If..# we
0bb0: 66 69 6e 64 20 6e 6f 20 6e 6f 64 65 73 20 77 69 find no nodes wi
0bc0: 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f thout predecesso
0bd0: 72 73 20 77 65 20 68 61 76 65 20 61 20 63 79 63 rs we have a cyc
0be0: 6c 65 2c 0a 09 23 20 20 20 20 61 6e 64 20 77 6f le,..# and wo
0bf0: 72 6b 20 6f 6e 20 62 72 65 61 6b 69 6e 67 20 69 rk on breaking i
0c00: 74 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 33 t....log write 3
0c10: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 4e cyclebreaker {N
0c20: 6f 77 20 73 6f 72 74 69 6e 67 20 74 68 65 20 63 ow sorting the c
0c30: 68 61 6e 67 65 73 65 74 73 2c 20 62 72 65 61 6b hangesets, break
0c40: 69 6e 67 20 63 79 63 6c 65 73 7d 0a 0a 09 49 6e ing cycles}...In
0c50: 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 itializeCandidat
0c60: 65 73 20 24 64 67 0a 09 77 68 69 6c 65 20 7b 31 es $dg..while {1
0c70: 7d 20 7b 0a 09 20 20 20 20 77 68 69 6c 65 20 7b } {.. while {
0c80: 5b 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 [WithoutPredeces
0c90: 73 6f 72 20 24 64 67 20 6e 5d 7d 20 7b 0a 09 09 sor $dg n]} {...
0ca0: 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b 20 24 6e ProcessedHook $n
0cb0: 20 24 6d 79 61 74 0a 09 09 24 64 67 20 6e 6f 64 $myat...$dg nod
0cc0: 65 20 64 65 6c 65 74 65 20 24 6e 0a 09 09 69 6e e delete $n...in
0cd0: 63 72 20 6d 79 61 74 0a 09 20 20 20 20 7d 0a 0a cr myat.. }..
0ce0: 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c 65 6e 67 . if {![lleng
0cf0: 74 68 20 5b 64 67 20 6e 6f 64 65 73 5d 5d 7d 20 th [dg nodes]]}
0d00: 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 72 65 61 break... Brea
0d10: 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 20 20 20 kCycleHook
0d20: 20 24 64 67 0a 09 20 20 20 20 49 6e 69 74 69 61 $dg.. Initia
0d30: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 24 lizeCandidates $
0d40: 64 67 0a 09 7d 0a 0a 09 24 64 67 20 64 65 73 74 dg..}...$dg dest
0d50: 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 roy...log write
0d60: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 44 3 cyclebreaker D
0d70: 6f 6e 65 2e 0a 09 43 6c 65 61 72 48 6f 6f 6b 73 one...ClearHooks
0d80: 0a 0a 09 23 20 52 65 72 65 61 64 20 74 68 65 20 ...# Reread the
0d90: 67 72 61 70 68 20 61 6e 64 20 64 75 6d 70 20 69 graph and dump i
0da0: 74 73 20 66 69 6e 61 6c 20 66 6f 72 6d 2c 20 69 ts final form, i
0db0: 66 20 67 72 61 70 68 20 65 78 70 6f 72 74 0a 09 f graph export..
0dc0: 23 20 77 61 73 20 61 63 74 69 76 61 74 65 64 2e # was activated.
0dd0: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
0de0: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 dotdestination..
0df0: 69 66 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e if {$mydotdestin
0e00: 61 74 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 ation eq ""} ret
0e10: 75 72 6e 0a 0a 09 73 65 74 20 20 20 64 67 20 5b urn...set dg [
0e20: 53 65 74 75 70 20 5b 75 70 6c 65 76 65 6c 20 23 Setup [uplevel #
0e30: 30 20 24 63 68 61 6e 67 65 73 65 74 63 6d 64 5d 0 $changesetcmd]
0e40: 20 30 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 64 0]..Mark $dg -d
0e50: 6f 6e 65 0a 09 24 64 67 20 64 65 73 74 72 6f 79 one..$dg destroy
0e60: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
0e70: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
0e80: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
0e90: 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 ###########..
0ea0: 20 74 79 70 65 6d 65 74 68 6f 64 20 62 72 65 61 typemethod brea
0eb0: 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 42 72 65 k {graph} {..Bre
0ec0: 61 6b 43 79 63 6c 65 20 24 67 72 61 70 68 20 5b akCycle $graph [
0ed0: 46 69 6e 64 43 79 63 6c 65 20 24 67 72 61 70 68 FindCycle $graph
0ee0: 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a ]..return. }.
0ef0: 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 . # # ## ###
0f00: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
0f10: 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 20 20 ############.
0f20: 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d 65 74 ## Internal met
0f30: 68 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 20 53 hods.. proc S
0f40: 65 74 75 70 20 7b 63 68 61 6e 67 65 73 65 74 73 etup {changesets
0f50: 20 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 66 20 {log 1}} {..if
0f60: 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 6c 6f {$log} {.. lo
0f70: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
0f80: 72 65 61 6b 65 72 20 22 43 72 65 61 74 69 6e 67 reaker "Creating
0f90: 20 63 68 61 6e 67 65 73 65 74 20 67 72 61 70 68 changeset graph
0fa0: 2c 20 66 69 6c 6c 69 6e 67 20 77 69 74 68 20 6e , filling with n
0fb0: 6f 64 65 73 22 0a 09 20 20 20 20 6c 6f 67 20 77 odes".. log w
0fc0: 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 rite 3 cyclebrea
0fd0: 6b 65 72 20 22 41 64 64 69 6e 67 20 5b 6e 73 70 ker "Adding [nsp
0fe0: 20 5b 6c 6c 65 6e 67 74 68 20 24 63 68 61 6e 67 [llength $chang
0ff0: 65 73 65 74 73 5d 20 6e 6f 64 65 5d 22 0a 09 7d esets] node]"..}
1000: 0a 0a 09 73 65 74 20 64 67 20 5b 73 74 72 75 63 ...set dg [struc
1010: 74 3a 3a 67 72 61 70 68 20 64 67 5d 0a 0a 09 66 t::graph dg]...f
1020: 6f 72 65 61 63 68 20 63 73 65 74 20 24 63 68 61 oreach cset $cha
1030: 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 20 20 24 ngesets {.. $
1040: 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 dg node insert $
1050: 63 73 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f cset.. $dg no
1060: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
1070: 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 73 65 74 timerange [$cset
1080: 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a timerange]..}..
1090: 09 23 20 32 2e 20 46 69 6e 64 20 66 6f 72 20 61 .# 2. Find for a
10a0: 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 61 6e ll relevant chan
10b0: 67 65 73 65 74 20 74 68 65 69 72 20 72 65 76 69 geset their revi
10c0: 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 69 72 0a sions and their.
10d0: 09 23 20 20 20 20 64 65 70 65 6e 64 65 6e 63 69 .# dependenci
10e0: 65 73 2e 20 4d 61 70 20 74 68 65 20 6c 61 74 74 es. Map the latt
10f0: 65 72 20 62 61 63 6b 20 74 6f 20 63 68 61 6e 67 er back to chang
1100: 65 73 65 74 73 20 61 6e 64 0a 09 23 20 20 20 20 esets and..#
1110: 63 6f 6e 73 74 72 75 63 74 20 74 68 65 20 63 6f construct the co
1120: 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 72 63 73 rresponding arcs
1130: 2e 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a ....if {$log} {.
1140: 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 33 . log write 3
1150: 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 53 cyclebreaker {S
1160: 65 74 74 69 6e 67 20 75 70 20 6e 6f 64 65 20 64 etting up node d
1170: 65 70 65 6e 64 65 6e 63 69 65 73 7d 0a 09 7d 0a ependencies}..}.
1180: 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 ..foreach cset $
1190: 63 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 changesets {..
11a0: 20 20 66 6f 72 65 61 63 68 20 73 75 63 63 20 5b foreach succ [
11b0: 24 63 73 65 74 20 73 75 63 63 65 73 73 6f 72 73 $cset successors
11c0: 5d 20 7b 0a 09 09 23 20 43 68 61 6e 67 65 73 65 ] {...# Changese
11d0: 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 70 65 ts may have depe
11e0: 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 ndencies outside
11f0: 20 6f 66 20 74 68 65 0a 09 09 23 20 63 68 6f 73 of the...# chos
1200: 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 61 72 en set. These ar
1210: 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b e ignored...if {
1220: 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 ![$dg node exist
1230: 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e s $succ]} contin
1240: 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 ue...$dg arc ins
1250: 65 72 74 20 24 63 73 65 74 20 24 73 75 63 63 0a ert $cset $succ.
1260: 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 23 20 52 75 . }..}...# Ru
1270: 6e 20 74 68 65 20 75 73 65 72 20 68 6f 6f 6b 20 n the user hook
1280: 74 6f 20 6d 61 6e 69 70 75 6c 61 74 65 20 74 68 to manipulate th
1290: 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 0a 09 e graph before..
12a0: 23 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a # consummation..
12b0: 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b 20 4d 61 ..if {$log} { Ma
12c0: 72 6b 20 24 64 67 20 2d 73 74 61 72 74 20 7d 0a rk $dg -start }.
12d0: 09 50 72 65 48 6f 6f 6b 20 24 64 67 0a 09 72 65 .PreHook $dg..re
12e0: 74 75 72 6e 20 20 24 64 67 0a 20 20 20 20 7d 0a turn $dg. }.
12f0: 0a 20 20 20 20 23 20 49 6e 73 74 65 61 64 20 6f . # Instead o
1300: 66 20 73 65 61 72 63 68 69 6e 67 20 74 68 65 20 f searching the
1310: 77 68 6f 6c 65 20 67 72 61 70 68 20 66 6f 72 20 whole graph for
1320: 74 68 65 20 64 65 67 72 65 65 2d 30 20 6e 6f 64 the degree-0 nod
1330: 65 73 20 69 6e 0a 20 20 20 20 23 20 65 61 63 68 es in. # each
1340: 20 69 74 65 72 61 74 69 6f 6e 20 77 65 20 63 6f iteration we co
1350: 6d 70 75 74 65 20 74 68 65 20 6c 69 73 74 20 6f mpute the list o
1360: 6e 63 65 20 74 6f 20 73 74 61 72 74 2c 20 61 6e nce to start, an
1370: 64 20 74 68 65 6e 20 6f 6e 6c 79 0a 20 20 20 20 d then only.
1380: 23 20 75 70 64 61 74 65 20 69 74 20 69 6e 63 72 # update it incr
1390: 65 6d 65 6e 74 61 6c 6c 79 20 62 61 73 65 64 20 ementally based
13a0: 6f 6e 20 74 68 65 20 6f 75 74 67 6f 69 6e 67 20 on the outgoing
13b0: 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 neighbours of th
13c0: 65 0a 20 20 20 20 23 20 6e 6f 64 65 20 63 68 6f e. # node cho
13d0: 73 65 6e 20 66 6f 72 20 63 6f 6d 6d 69 74 2e 0a sen for commit..
13e0: 0a 20 20 20 20 70 72 6f 63 20 49 6e 69 74 69 61 . proc Initia
13f0: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 7b lizeCandidates {
1400: 64 67 7d 20 7b 0a 09 23 20 62 6f 74 74 6f 6d 20 dg} {..# bottom
1410: 3d 20 6c 69 73 74 20 28 6c 69 73 74 20 28 6e 6f = list (list (no
1420: 64 65 2c 20 72 61 6e 67 65 20 6d 69 6e 2c 20 72 de, range min, r
1430: 61 6e 67 65 20 6d 61 78 29 29 0a 09 3a 3a 76 61 ange max))..::va
1440: 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a riable mybottom.
1450: 09 66 6f 72 65 61 63 68 20 6e 20 5b 24 64 67 20 .foreach n [$dg
1460: 6e 6f 64 65 73 5d 20 7b 0a 09 20 20 20 20 69 66 nodes] {.. if
1470: 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 {[$dg node degr
1480: 65 65 20 2d 69 6e 20 24 6e 5d 7d 20 63 6f 6e 74 ee -in $n]} cont
1490: 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 65 6e inue.. lappen
14a0: 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 d mybottom [lins
14b0: 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 ert [$dg node ge
14c0: 74 20 24 6e 20 74 69 6d 65 72 61 6e 67 65 5d 20 t $n timerange]
14d0: 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74 20 6d 79 0 $n]..}..set my
14e0: 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d 69 bottom [lsort -i
14f0: 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72 20 ndex 1 -integer
1500: 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32 20 [lsort -index 2
1510: 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 74 74 -integer $mybott
1520: 6f 6d 5d 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 om]]..return.
1530: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 74 }.. proc Wit
1540: 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 houtPredecessor
1550: 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 72 {dg nv} {..::var
1560: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 0a iable mybottom..
1570: 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e 0a 09 .upvar 1 $nv n..
1580: 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d if {![llength $m
1590: 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 74 75 ybottom]} { retu
15a0: 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e 20 5b rn 0 }...set n [
15b0: 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 20 24 lindex [lindex $
15c0: 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d 0a 09 mybottom 0] 0]..
15d0: 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 72 set mybottom [lr
15e0: 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d 20 31 ange $mybottom 1
15f0: 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 6e 67 end]..set chang
1600: 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 65 20 ed 0...# Update
1610: 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 77 69 list of nodes wi
1620: 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f thout predecesso
1630: 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 65 0a r, based on the.
1640: 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 69 67 .# outgoing neig
1650: 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 63 68 hbours of the ch
1660: 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 73 20 osen node. This
1670: 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 61 73 should be..# fas
1680: 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 74 69 ter than iterati
1690: 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 20 ng of the whole
16a0: 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 66 69 set of nodes, fi
16b0: 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 69 74 nding all..# wit
16c0: 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 6f 72 hout predecessor
16d0: 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 6d 20 s, sorting them
16e0: 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 70 70 by time, etc. pp
16f0: 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 20 5b ...foreach out [
1700: 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 $dg nodes -out $
1710: 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b 5b 24 n] {.. if {[$
1720: 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 20 2d dg node degree -
1730: 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 63 6f in $out] > 1} co
1740: 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 44 65 ntinue.. # De
1750: 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f 75 72 gree-1 neighbour
1760: 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f 20 70 , will have no p
1770: 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 74 65 redecessors afte
1780: 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 65 6d r the.. # rem
1790: 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 20 6f oval of n. Put o
17a0: 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 20 20 n the list...
17b0: 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 6f lappend mybotto
17c0: 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 20 m [linsert [$dg
17d0: 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 74 69 node get $out ti
17e0: 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 74 5d merange] 0 $out]
17f0: 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e 67 65 .. set change
1800: 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 68 61 d 1..}..if {$cha
1810: 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 73 65 74 nged} {.. set
1820: 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 mybottom [lsort
1830: 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 -index 1 -integ
1840: 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 er [lsort -index
1850: 20 32 20 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 2 -integer $myb
1860: 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 20 57 ottom]]..}...# W
1870: 65 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 20 e do not delete
1880: 74 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 69 61 the node immedia
1890: 74 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 tely, to allow t
18a0: 68 65 20 53 61 76 65 0a 09 23 20 70 72 6f 63 65 he Save..# proce
18b0: 64 75 72 65 20 74 6f 20 73 61 76 65 20 74 68 65 dure to save the
18c0: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 73 dependencies as
18d0: 20 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 20 69 well (encoded i
18e0: 6e 20 74 68 65 0a 09 23 20 61 72 63 73 29 2e 0a n the..# arcs)..
18f0: 09 72 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a .return 1. }.
1900: 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 43 79 . proc FindCy
1910: 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 54 68 cle {dg} {..# Th
1920: 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 20 is procedure is
1930: 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c 79 20 run if and only
1940: 74 68 65 20 67 72 61 70 68 20 69 73 20 6e 6f 74 the graph is not
1950: 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 61 6c empty and..# al
1960: 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 72 65 l nodes have pre
1970: 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 73 20 decessors. This
1980: 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 68 20 means that each
1990: 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 68 65 node is..# eithe
19a0: 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 63 6c r part of a cycl
19b0: 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 6c 79 e or (indirectly
19c0: 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 61 ) depending on a
19d0: 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 63 79 node..# in a cy
19e0: 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 61 72 cle. We can star
19f0: 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 61 72 t at an arbitrar
1a00: 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 20 69 y node, follow i
1a10: 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 20 65 ts..# incoming e
1a20: 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 65 64 dges to its pred
1a30: 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c 20 77 ecessors until w
1a40: 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 0a 09 e see a node a..
1a50: 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e 20 54 # second time. T
1a60: 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 73 20 hat node closes
1a70: 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 74 68 the cycle and th
1a80: 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 0a 09 e beginning is..
1a90: 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 63 75 # its first occu
1aa0: 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 61 74 rence. Note that
1ab0: 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 20 61 we can choose a
1ac0: 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 20 70 n arbitrary..# p
1ad0: 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 65 61 redecessor of ea
1ae0: 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c 6c 2c ch node as well,
1af0: 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 65 20 we do not have
1b00: 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 20 57 to search....# W
1b10: 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 61 63 e record for eac
1b20: 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 65 78 h node the index
1b30: 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 61 70 of the first ap
1b40: 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 20 74 pearance in..# t
1b50: 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e 67 20 he path, making
1b60: 69 74 20 65 61 73 79 20 61 74 20 74 68 65 20 65 it easy at the e
1b70: 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 63 79 nd to cut the cy
1b80: 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 2e 0a cle from..# it..
1b90: 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 ..# Choose arbit
1ba0: 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 74 61 rary node to sta
1bb0: 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 61 74 rt our search at
1bc0: 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b 6c 69 ...set start [li
1bd0: 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 5d ndex [$dg nodes]
1be0: 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 6c 69 0]...# Initiali
1bf0: 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 20 6f ze state, path o
1c00: 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 61 6e f seen nodes, an
1c10: 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 73 65 d when seen...se
1c20: 74 20 20 20 20 20 20 20 70 61 74 68 20 7b 7d 0a t path {}.
1c30: 09 61 72 72 61 79 20 73 65 74 20 73 65 65 6e 20 .array set seen
1c40: 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b {}...while {1} {
1c50: 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 65 61 .. # Stop sea
1c60: 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 20 68 rching when we h
1c70: 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 75 72 ave seen the cur
1c80: 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 20 23 rent node.. #
1c90: 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 63 69 already, the ci
1ca0: 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 63 6c rcle has been cl
1cb0: 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 7b 5b osed... if {[
1cc0: 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 65 6e info exists seen
1cd0: 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 61 6b ($start)]} break
1ce0: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 70 61 .. lappend pa
1cf0: 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 20 73 th $start.. s
1d00: 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 29 20 et seen($start)
1d10: 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 68 20 [expr {[llength
1d20: 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 20 20 $path]-1}]..
1d30: 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 # Choose arbitra
1d40: 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 ry predecessor..
1d50: 20 20 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c set start [l
1d60: 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 index [$dg nodes
1d70: 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a -in $start] 0].
1d80: 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 .}...return [str
1d90: 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 uct::list revers
1da0: 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 e [lrange $path
1db0: 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e $seen($start) en
1dc0: 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 d]]. }.. p
1dd0: 72 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 7b 20 roc ID {cset} {
1de0: 72 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 74 20 return "<[$cset
1df0: 69 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 72 6f id]>" }.. pro
1e00: 63 20 42 72 65 61 6b 43 79 63 6c 65 20 7b 64 67 c BreakCycle {dg
1e10: 20 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 68 65 cycle} {..# The
1e20: 20 63 79 63 6c 65 20 77 65 20 68 61 76 65 20 67 cycle we have g
1e30: 6f 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 6e 20 otten is broken
1e40: 62 79 20 62 72 65 61 6b 69 6e 67 20 61 70 61 72 by breaking apar
1e50: 74 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f 72 65 t one or..# more
1e60: 20 6f 66 20 74 68 65 20 63 68 61 6e 67 65 73 65 of the changese
1e70: 74 73 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2e ts in the cycle.
1e80: 20 54 68 69 73 20 63 61 75 73 65 73 20 75 73 20 This causes us
1e90: 74 6f 0a 09 23 20 63 72 65 61 74 65 20 6f 6e 65 to..# create one
1ea0: 20 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 65 73 or more changes
1eb0: 65 74 73 20 77 68 69 63 68 20 61 72 65 20 74 6f ets which are to
1ec0: 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c 0a 09 be committed,..
1ed0: 23 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 67 # added to the g
1ee0: 72 61 70 68 2c 20 65 74 63 2e 20 70 70 2e 0a 0a raph, etc. pp...
1ef0: 09 73 65 74 20 63 70 72 69 6e 74 20 5b 6a 6f 69 .set cprint [joi
1f00: 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 74 20 n [struct::list
1f10: 6d 61 70 20 24 63 79 63 6c 65 20 5b 6d 79 70 72 map $cycle [mypr
1f20: 6f 63 20 49 44 5d 5d 20 7b 20 7d 5d 0a 0a 09 6c oc ID]] { }]...l
1f30: 61 70 70 65 6e 64 20 63 79 63 6c 65 20 5b 6c 69 append cycle [li
1f40: 6e 64 65 78 20 24 63 79 63 6c 65 20 30 5d 20 5b ndex $cycle 0] [
1f50: 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 31 5d lindex $cycle 1]
1f60: 0a 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 7b ..set bestlink {
1f70: 7d 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 65 20 }..set bestnode
1f80: 7b 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c 0a 09 {}...foreach \..
1f90: 20 20 20 20 70 72 65 76 20 5b 6c 72 61 6e 67 65 prev [lrange
1fa0: 20 24 63 79 63 6c 65 20 30 20 65 6e 64 2d 32 5d $cycle 0 end-2]
1fb0: 20 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 6c 72 \.. cset [lr
1fc0: 61 6e 67 65 20 24 63 79 63 6c 65 20 31 20 65 6e ange $cycle 1 en
1fd0: 64 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 78 74 d-1] \.. next
1fe0: 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 [lrange $cycle
1ff0: 32 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 45 61 2 end] {....# Ea
2000: 63 68 20 74 72 69 70 6c 65 20 50 52 45 56 20 2d ch triple PREV -
2010: 3e 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 20 6f > CSET -> NEXT o
2020: 66 20 63 68 61 6e 67 65 73 65 74 73 2c 20 61 0a f changesets, a.
2030: 09 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 74 68 ..# 'link' in th
2040: 65 20 63 79 63 6c 65 2c 20 69 73 20 61 6e 61 6c e cycle, is anal
2050: 79 73 65 64 20 61 6e 64 20 74 68 65 20 62 65 73 ysed and the bes
2060: 74 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e 20 77 t...# location w
2070: 68 65 72 65 20 74 6f 20 61 74 20 6c 65 61 73 74 here to at least
2080: 20 77 65 61 6b 65 6e 20 74 68 65 20 63 79 63 6c weaken the cycl
2090: 65 20 69 73 0a 09 09 23 20 63 68 6f 73 65 6e 20 e is...# chosen
20a0: 66 6f 72 20 66 75 72 74 68 65 72 20 70 72 6f 63 for further proc
20b0: 65 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 20 6c essing.....set l
20c0: 69 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 ink [project::re
20d0: 76 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 70 72 vlink %AUTO% $pr
20e0: 65 76 20 24 63 73 65 74 20 24 6e 65 78 74 5d 0a ev $cset $next].
20f0: 09 09 69 66 20 7b 24 62 65 73 74 6c 69 6e 6b 20 ..if {$bestlink
2100: 65 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 20 73 eq ""} {... s
2110: 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c 69 6e et bestlink $lin
2120: 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 k... set best
2130: 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d 20 65 node $cset...} e
2140: 6c 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 62 65 lseif {[$link be
2150: 74 74 65 72 74 68 61 6e 20 24 62 65 73 74 6c 69 tterthan $bestli
2160: 6e 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 62 65 nk]} {... $be
2170: 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 09 stlink destroy..
2180: 09 20 20 20 20 73 65 74 20 62 65 73 74 6c 69 6e . set bestlin
2190: 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 73 65 k $link... se
21a0: 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 65 74 t bestnode $cset
21b0: 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 20 20 ...} else {...
21c0: 20 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a $link destroy.
21d0: 09 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c 6f 67 ..}.. }...log
21e0: 20 77 72 69 74 65 20 35 20 62 72 65 61 6b 72 63 write 5 breakrc
21f0: 79 63 6c 65 20 22 42 72 65 61 6b 69 6e 67 20 63 ycle "Breaking c
2200: 79 63 6c 65 20 28 24 63 70 72 69 6e 74 29 20 62 ycle ($cprint) b
2210: 79 20 73 70 6c 69 74 74 69 6e 67 20 63 68 61 6e y splitting chan
2220: 67 65 73 65 74 20 3c 5b 24 62 65 73 74 6e 6f 64 geset <[$bestnod
2230: 65 20 69 64 5d 3e 22 0a 09 73 65 74 20 49 44 20 e id]>"..set ID
2240: 5b 24 62 65 73 74 6e 6f 64 65 20 69 64 5d 0a 09 [$bestnode id]..
2250: 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d Mark $dg -${ID}-
2260: 62 65 66 6f 72 65 0a 0a 09 73 65 74 20 6e 65 77 before...set new
2270: 63 73 65 74 73 20 5b 24 62 65 73 74 6c 69 6e 6b csets [$bestlink
2280: 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 74 6c 69 break]..$bestli
2290: 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 20 20 20 nk destroy..
22a0: 20 20 20 20 23 20 41 74 20 74 68 69 73 20 70 6f # At this po
22b0: 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 68 61 6e int the old chan
22c0: 67 65 73 65 74 20 28 42 45 53 54 4e 4f 44 45 29 geset (BESTNODE)
22d0: 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 20 20 20 is gone.
22e0: 20 23 20 61 6c 72 65 61 64 79 2e 20 57 65 20 72 # already. We r
22f0: 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d 20 74 68 emove it from th
2300: 65 20 67 72 61 70 68 20 61 73 20 77 65 6c 6c 20 e graph as well
2310: 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 72 0a 20 and then enter.
2320: 20 20 20 20 20 20 20 23 20 74 68 65 20 66 72 61 # the fra
2330: 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 74 65 64 gments generated
2340: 20 66 6f 72 20 69 74 2e 0a 0a 09 23 20 4e 4f 54 for it....# NOT
2350: 45 2e 20 57 65 20 68 61 76 65 20 74 6f 20 67 65 E. We have to ge
2360: 74 20 74 68 65 20 6c 69 73 74 20 6f 66 20 69 6e t the list of in
2370: 63 6f 6d 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 coming neighbour
2380: 73 20 61 6e 64 0a 09 23 20 72 65 63 6f 6d 70 75 s and..# recompu
2390: 74 65 20 74 68 65 69 72 20 73 75 63 63 65 73 73 te their success
23a0: 6f 72 73 20 61 66 74 65 72 20 74 68 65 20 6e 65 ors after the ne
23b0: 77 20 6e 6f 64 65 73 20 68 61 76 65 20 62 65 65 w nodes have bee
23c0: 6e 0a 09 23 20 69 6e 73 65 72 74 65 64 2e 20 54 n..# inserted. T
23d0: 68 65 69 72 20 6f 75 74 67 6f 69 6e 67 20 61 72 heir outgoing ar
23e0: 63 73 20 77 69 6c 6c 20 6e 6f 77 20 67 6f 20 74 cs will now go t
23f0: 6f 20 6f 6e 65 20 6f 72 20 62 6f 74 68 20 6f 66 o one or both of
2400: 0a 09 23 20 74 68 65 20 6e 65 77 20 6e 6f 64 65 ..# the new node
2410: 73 2c 20 61 6e 64 20 6e 6f 74 20 72 65 64 6f 69 s, and not redoi
2420: 6e 67 20 74 68 65 6d 20 6d 61 79 20 63 61 75 73 ng them may caus
2430: 65 20 75 73 20 74 6f 20 66 6f 72 67 65 74 0a 09 e us to forget..
2440: 23 20 63 69 72 63 6c 65 73 2c 20 6c 65 61 76 69 # circles, leavi
2450: 6e 67 20 74 68 65 6d 20 69 6e 2c 20 75 6e 62 72 ng them in, unbr
2460: 6f 6b 65 6e 2e 0a 0a 09 73 65 74 20 70 72 65 20 oken....set pre
2470: 5b 24 64 67 20 6e 6f 64 65 73 20 2d 69 6e 20 24 [$dg nodes -in $
2480: 62 65 73 74 6e 6f 64 65 5d 0a 0a 20 20 20 20 20 bestnode]..
2490: 20 20 20 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 $dg node dele
24a0: 74 65 20 24 62 65 73 74 6e 6f 64 65 0a 0a 09 66 te $bestnode...f
24b0: 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e 65 77 oreach cset $new
24c0: 63 73 65 74 73 20 7b 0a 09 20 20 20 20 24 64 67 csets {.. $dg
24d0: 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63 73 node insert $cs
24e0: 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 et.. $dg node
24f0: 20 73 65 74 20 20 20 20 24 63 73 65 74 20 74 69 set $cset ti
2500: 6d 65 72 61 6e 67 65 20 5b 24 63 73 65 74 20 74 merange [$cset t
2510: 69 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a 09 66 imerange]..}...f
2520: 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e 65 77 oreach cset $new
2530: 63 73 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 csets {.. for
2540: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
2550: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
2560: 09 23 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 .# The new chang
2570: 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 esets may have d
2580: 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 ependencies outs
2590: 69 64 65 20 6f 66 0a 09 09 23 20 74 68 65 20 63 ide of...# the c
25a0: 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 hosen set. These
25b0: 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 are ignored...i
25c0: 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 f {![$dg node ex
25d0: 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e ists $succ]} con
25e0: 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 tinue...$dg arc
25f0: 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 insert $cset $su
2600: 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 66 6f cc.. }..}..fo
2610: 72 65 61 63 68 20 63 73 65 74 20 24 70 72 65 20 reach cset $pre
2620: 7b 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 {.. foreach s
2630: 75 63 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 ucc [$cset succe
2640: 73 73 6f 72 73 5d 20 7b 0a 09 09 23 20 4e 6f 74 ssors] {...# Not
2650: 65 20 74 68 61 74 20 74 68 65 20 61 72 63 20 6d e that the arc m
2660: 61 79 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 ay already exist
2670: 20 69 6e 20 74 68 65 20 67 72 61 70 68 2e 20 49 in the graph. I
2680: 66 0a 09 09 23 20 73 6f 20 69 67 6e 6f 72 65 20 f...# so ignore
2690: 69 74 2e 20 54 68 65 20 6e 65 77 20 63 68 61 6e it. The new chan
26a0: 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 0a gesets may have.
26b0: 09 09 23 20 64 65 70 65 6e 64 65 6e 63 69 65 73 ..# dependencies
26c0: 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 65 20 outside of the
26d0: 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 chosen set. Thes
26e0: 65 20 61 72 65 0a 09 09 23 20 69 67 6e 6f 72 65 e are...# ignore
26f0: 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f d...if {![$dg no
2700: 64 65 20 65 78 69 73 74 73 20 24 73 75 63 63 5d de exists $succ]
2710: 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 69 66 20 } continue...if
2720: 7b 5b 48 61 73 41 72 63 20 24 64 67 20 24 63 73 {[HasArc $dg $cs
2730: 65 74 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 et $succ]} conti
2740: 6e 75 65 3b 23 20 54 4f 44 4f 20 73 68 6f 75 6c nue;# TODO shoul
2750: 64 20 62 65 20 67 72 61 70 68 20 6d 65 74 68 6f d be graph metho
2760: 64 2e 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 d....$dg arc ins
2770: 65 72 74 20 24 63 73 65 74 20 24 73 75 63 63 0a ert $cset $succ.
2780: 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 4d 61 72 6b . }..}...Mark
2790: 20 24 64 67 20 2d 24 7b 49 44 7d 2d 61 66 74 65 $dg -${ID}-afte
27a0: 72 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a r..return. }.
27b0: 0a 20 20 20 20 23 20 54 4f 44 4f 3a 20 54 68 69 . # TODO: Thi
27c0: 73 20 73 68 6f 75 6c 64 20 62 65 20 61 20 67 72 s should be a gr
27d0: 61 70 68 20 6d 65 74 68 6f 64 2e 0a 20 20 20 20 aph method..
27e0: 70 72 6f 63 20 48 61 73 41 72 63 20 7b 64 67 20 proc HasArc {dg
27f0: 61 20 62 7d 20 7b 0a 09 23 38 2e 35 3a 20 72 65 a b} {..#8.5: re
2800: 74 75 72 6e 20 5b 65 78 70 72 20 7b 24 62 20 69 turn [expr {$b i
2810: 6e 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 n [$dg nodes -ou
2820: 74 20 24 61 5d 7d 5d 0a 09 69 66 20 7b 5b 6c 73 t $a]}]..if {[ls
2830: 65 61 72 63 68 20 2d 65 78 61 63 74 20 5b 24 64 earch -exact [$d
2840: 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 61 5d g nodes -out $a]
2850: 20 24 62 5d 20 3c 20 30 7d 20 7b 20 72 65 74 75 $b] < 0} { retu
2860: 72 6e 20 30 20 7d 0a 09 72 65 74 75 72 6e 20 31 rn 0 }..return 1
2870: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
2880: 20 4d 61 72 6b 20 7b 64 67 20 7b 73 75 66 66 69 Mark {dg {suffi
2890: 78 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 72 69 x {}}} {..::vari
28a0: 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 69 6e able mydotdestin
28b0: 61 74 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 64 6f ation..if {$mydo
28c0: 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 65 71 20 tdestination eq
28d0: 22 22 7d 20 72 65 74 75 72 6e 0a 09 3a 3a 76 61 ""} return..::va
28e0: 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 riable mydotpref
28f0: 69 78 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d ix..::variable m
2900: 79 64 6f 74 69 64 0a 09 73 65 74 20 66 6e 61 6d ydotid..set fnam
2910: 65 20 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 e $mydotdestinat
2920: 69 6f 6e 2f 24 7b 6d 79 64 6f 74 70 72 65 66 69 ion/${mydotprefi
2930: 78 7d 24 7b 6d 79 64 6f 74 69 64 7d 24 7b 73 75 x}${mydotid}${su
2940: 66 66 69 78 7d 2e 64 6f 74 0a 09 66 69 6c 65 20 ffix}.dot..file
2950: 6d 6b 64 69 72 20 5b 66 69 6c 65 20 64 69 72 6e mkdir [file dirn
2960: 61 6d 65 20 24 66 6e 61 6d 65 5d 0a 09 64 6f 74 ame $fname]..dot
2970: 20 77 72 69 74 65 20 24 64 67 20 24 6d 79 64 6f write $dg $mydo
2980: 74 70 72 65 66 69 78 24 73 75 66 66 69 78 20 24 tprefix$suffix $
2990: 66 6e 61 6d 65 0a 09 69 6e 63 72 20 6d 79 64 6f fname..incr mydo
29a0: 74 69 64 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 tid...log write
29b0: 35 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 5 cyclebreaker "
29c0: 2e 64 6f 74 20 65 78 70 6f 72 74 20 24 66 6e 61 .dot export $fna
29d0: 6d 65 22 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 me"..return.
29e0: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
29f0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
2a00: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
2a10: 20 20 20 23 23 20 43 61 6c 6c 62 61 63 6b 20 69 ## Callback i
2a20: 6e 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a 0a 20 nvokation .....
2a30: 20 20 20 70 72 6f 63 20 50 72 65 48 6f 6f 6b 20 proc PreHook
2a40: 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 69 76 {graph} {..# Giv
2a50: 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 e the user of th
2a60: 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 e cycle breaker
2a70: 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 the opportunity
2a80: 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 to work..# with
2a90: 74 68 65 20 67 72 61 70 68 20 62 65 74 77 65 65 the graph betwee
2aa0: 6e 20 73 65 74 75 70 20 61 6e 64 20 63 6f 6e 73 n setup and cons
2ab0: 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a 76 61 ummation....::va
2ac0: 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 0a riable myprecmd.
2ad0: 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 .if {![llength $
2ae0: 6d 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 75 72 myprecmd]} retur
2af0: 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b n...uplevel #0 [
2b00: 6c 69 6e 73 65 72 74 20 24 6d 79 70 72 65 63 6d linsert $myprecm
2b10: 64 20 65 6e 64 20 24 67 72 61 70 68 5d 0a 09 4d d end $graph]..M
2b20: 61 72 6b 20 24 67 72 61 70 68 20 2d 70 72 65 2d ark $graph -pre-
2b30: 64 6f 6e 65 0a 09 72 65 74 75 72 6e 0a 20 20 20 done..return.
2b40: 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 6f }.. proc Pro
2b50: 63 65 73 73 65 64 48 6f 6f 6b 20 7b 63 73 65 74 cessedHook {cset
2b60: 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 76 65 20 pos} {..# Give
2b70: 74 68 65 20 75 73 65 72 20 6f 66 20 74 68 65 20 the user of the
2b80: 63 79 63 6c 65 20 62 72 65 61 6b 65 72 20 74 68 cycle breaker th
2b90: 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 20 74 6f e opportunity to
2ba0: 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 20 74 68 work..# with th
2bb0: 65 20 63 68 61 6e 67 65 73 65 74 20 62 65 66 6f e changeset befo
2bc0: 72 65 20 69 74 20 69 73 20 72 65 6d 6f 76 65 64 re it is removed
2bd0: 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 68 2e from the graph.
2be0: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
2bf0: 73 61 76 65 63 6d 64 0a 09 69 66 20 7b 21 5b 6c savecmd..if {![l
2c00: 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 65 63 6d length $mysavecm
2c10: 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 75 70 6c d]} return...upl
2c20: 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 evel #0 [linsert
2c30: 20 24 6d 79 73 61 76 65 63 6d 64 20 65 6e 64 20 $mysavecmd end
2c40: 24 70 6f 73 20 24 63 73 65 74 5d 0a 09 72 65 74 $pos $cset]..ret
2c50: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 urn. }.. p
2c60: 72 6f 63 20 42 72 65 61 6b 43 79 63 6c 65 48 6f roc BreakCycleHo
2c70: 6f 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 ok {graph} {..#
2c80: 43 61 6c 6c 20 6f 75 74 20 74 6f 20 74 68 65 20 Call out to the
2c90: 63 68 6f 73 65 6e 20 61 6c 67 6f 72 69 74 68 6d chosen algorithm
2ca0: 20 66 6f 72 20 63 79 63 6c 65 20 62 72 65 61 6b for cycle break
2cb0: 69 6e 67 2e 20 46 69 6e 64 69 6e 67 0a 09 23 20 ing. Finding..#
2cc0: 61 20 63 79 63 6c 65 20 69 66 20 6e 6f 20 62 72 a cycle if no br
2cd0: 65 61 6b 65 72 20 77 61 73 20 63 68 6f 73 65 6e eaker was chosen
2ce0: 20 69 73 20 61 6e 20 65 72 72 6f 72 2e 0a 0a 09 is an error....
2cf0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 ::variable mybre
2d00: 61 6b 63 6d 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 akcmd..if {![lle
2d10: 6e 67 74 68 20 24 6d 79 62 72 65 61 6b 63 6d 64 ngth $mybreakcmd
2d20: 5d 7d 20 7b 0a 09 20 20 20 20 74 72 6f 75 62 6c ]} {.. troubl
2d30: 65 20 66 61 74 61 6c 20 22 46 6f 75 6e 64 20 61 e fatal "Found a
2d40: 20 63 79 63 6c 65 2c 20 65 78 70 65 63 74 69 6e cycle, expectin
2d50: 67 20 6e 6f 6e 65 2e 22 0a 09 20 20 20 20 65 78 g none.".. ex
2d60: 69 74 20 31 0a 09 7d 0a 0a 09 75 70 6c 65 76 65 it 1..}...upleve
2d70: 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 6d l #0 [linsert $m
2d80: 79 62 72 65 61 6b 63 6d 64 20 65 6e 64 20 24 67 ybreakcmd end $g
2d90: 72 61 70 68 5d 0a 09 72 65 74 75 72 6e 0a 20 20 raph]..return.
2da0: 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 43 6c }.. proc Cl
2db0: 65 61 72 48 6f 6f 6b 73 20 7b 7d 20 7b 0a 09 3a earHooks {} {..:
2dc0: 3a 76 61 72 69 61 62 6c 65 20 6d 79 70 72 65 63 :variable myprec
2dd0: 6d 64 20 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 md {}..::varia
2de0: 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 20 7b ble mysavecmd {
2df0: 7d 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 }..::variable my
2e00: 62 72 65 61 6b 63 6d 64 20 7b 7d 0a 09 72 65 74 breakcmd {}..ret
2e10: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 urn. }.. #
2e20: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
2e30: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
2e40: 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 70 65 ######.. type
2e50: 76 61 72 69 61 62 6c 65 20 6d 79 61 74 20 20 20 variable myat
2e60: 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 0 ; # Counter
2e70: 20 66 6f 72 20 63 6f 6d 6d 69 74 20 69 64 73 20 for commit ids
2e80: 66 6f 72 20 74 68 65 0a 09 09 09 20 20 20 20 20 for the....
2e90: 20 20 23 20 63 68 61 6e 67 65 73 65 74 73 2e 0a # changesets..
2ea0: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
2eb0: 20 6d 79 62 6f 74 74 6f 6d 20 7b 7d 20 3b 20 23 mybottom {} ; #
2ec0: 20 4c 69 73 74 20 6f 66 20 74 68 65 20 63 61 6e List of the can
2ed0: 64 69 64 61 74 65 20 6e 6f 64 65 73 20 66 6f 72 didate nodes for
2ee0: 0a 09 09 09 20 20 20 20 20 20 20 23 20 63 6f 6d .... # com
2ef0: 6d 69 74 74 69 6e 67 2e 0a 0a 20 20 20 20 74 79 mitting... ty
2f00: 70 65 76 61 72 69 61 62 6c 65 20 6d 79 70 72 65 pevariable mypre
2f10: 63 6d 64 20 20 20 7b 7d 20 3b 20 23 20 43 61 6c cmd {} ; # Cal
2f20: 6c 62 61 63 6b 2c 20 63 68 61 6e 67 65 20 67 72 lback, change gr
2f30: 61 70 68 20 62 65 66 6f 72 65 20 77 61 6c 6b 2e aph before walk.
2f40: 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c . typevariabl
2f50: 65 20 6d 79 73 61 76 65 63 6d 64 20 20 7b 7d 20 e mysavecmd {}
2f60: 3b 20 23 20 43 61 6c 6c 62 61 63 6b 2c 20 66 6f ; # Callback, fo
2f70: 72 20 65 61 63 68 20 70 72 6f 63 65 73 73 65 64 r each processed
2f80: 20 6e 6f 64 65 2e 0a 20 20 20 20 74 79 70 65 76 node.. typev
2f90: 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 ariable mybreakc
2fa0: 6d 64 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 md {} ; # Callba
2fb0: 63 6b 2c 20 66 6f 72 20 65 61 63 68 20 66 6f 75 ck, for each fou
2fc0: 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 20 20 20 74 nd cycle... t
2fd0: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f ypevariable mydo
2fe0: 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 7b 7d 20 tdestination {}
2ff0: 3b 20 23 20 44 65 73 74 69 6e 61 74 69 6f 6e 20 ; # Destination
3000: 64 69 72 65 63 74 6f 72 79 20 66 6f 72 20 74 68 directory for th
3010: 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 67 e..... # g
3020: 65 6e 65 72 61 74 65 64 20 2e 64 6f 74 20 66 69 enerated .dot fi
3030: 6c 65 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 les.. typevar
3040: 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 iable mydotprefi
3050: 78 20 20 20 20 20 20 7b 7d 20 3b 20 23 20 50 72 x {} ; # Pr
3060: 65 66 69 78 20 66 6f 72 20 64 6f 74 20 66 69 6c efix for dot fil
3070: 65 73 20 77 68 65 6e 0a 09 09 09 09 20 20 20 20 es when.....
3080: 20 20 20 23 20 65 78 70 6f 72 74 69 6e 67 20 74 # exporting t
3090: 68 65 20 67 72 61 70 68 73 2e 0a 20 20 20 20 74 he graphs.. t
30a0: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f ypevariable mydo
30b0: 74 69 64 20 20 20 20 20 20 20 20 20 20 20 30 20 tid 0
30c0: 3b 20 23 20 43 6f 75 6e 74 65 72 20 66 6f 72 20 ; # Counter for
30d0: 64 6f 74 20 66 69 6c 65 20 6e 61 6d 65 0a 09 09 dot file name...
30e0: 09 09 20 20 20 20 20 20 20 23 20 67 65 6e 65 72 .. # gener
30f0: 61 74 69 6f 6e 2e 0a 0a 20 20 20 20 23 20 23 20 ation... # #
3100: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
3110: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
3120: 23 23 23 0a 20 20 20 20 23 23 20 43 6f 6e 66 69 ###. ## Confi
3130: 67 75 72 61 74 69 6f 6e 0a 0a 20 20 20 20 70 72 guration.. pr
3140: 61 67 6d 61 20 2d 68 61 73 69 6e 73 74 61 6e 63 agma -hasinstanc
3150: 65 73 20 20 20 6e 6f 20 3b 20 23 20 73 69 6e 67 es no ; # sing
3160: 6c 65 74 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 leton. pragma
3170: 20 2d 68 61 73 74 79 70 65 69 6e 66 6f 20 20 20 -hastypeinfo
3180: 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 6e 74 72 6f no ; # no intro
3190: 73 70 65 63 74 69 6f 6e 0a 20 20 20 20 70 72 61 spection. pra
31a0: 67 6d 61 20 2d 68 61 73 74 79 70 65 64 65 73 74 gma -hastypedest
31b0: 72 6f 79 20 6e 6f 20 3b 20 23 20 69 6d 6d 6f 72 roy no ; # immor
31c0: 74 61 6c 0a 0a 20 20 20 20 23 20 23 20 23 23 20 tal.. # # ##
31d0: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
31e0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
31f0: 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 65 20 65 76 .}..namespace ev
3200: 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a al ::vc::fossil:
3210: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 20 7b 0a 20 :import::cvs {.
3220: 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 78 70 namespace exp
3230: 6f 72 74 20 63 79 63 6c 65 62 72 65 61 6b 65 72 ort cyclebreaker
3240: 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 . namespace e
3250: 76 61 6c 20 63 79 63 6c 65 62 72 65 61 6b 65 72 val cyclebreaker
3260: 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 20 65 76 {..namespace ev
3270: 61 6c 20 70 72 6f 6a 65 63 74 20 7b 0a 09 20 20 al project {..
3280: 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f namespace impo
3290: 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a rt ::vc::fossil:
32a0: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 :import::cvs::pr
32b0: 6f 6a 65 63 74 3a 3a 72 65 76 0a 09 20 20 20 20 oject::rev..
32c0: 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 namespace import
32d0: 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 ::vc::fossil::i
32e0: 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a mport::cvs::proj
32f0: 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 0a 09 7d 0a ect::revlink..}.
3300: 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 .namespace impor
3310: 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d t ::vc::tools::m
3320: 69 73 63 3a 3a 2a 0a 09 6e 61 6d 65 73 70 61 63 isc::*..namespac
3330: 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 e import ::vc::t
3340: 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 6e 61 6d 65 73 ools::log..names
3350: 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 pace import ::vc
3360: 3a 3a 74 6f 6f 6c 73 3a 3a 74 72 6f 75 62 6c 65 ::tools::trouble
3370: 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f ..namespace impo
3380: 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a rt ::vc::tools::
3390: 64 6f 74 0a 09 6c 6f 67 20 72 65 67 69 73 74 65 dot..log registe
33a0: 72 20 63 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 r cyclebreaker.
33b0: 20 20 20 7d 0a 7d 0a 0a 23 20 23 20 23 23 20 23 }.}..# # ## #
33c0: 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 ## ##### #######
33d0: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 20 # #############
33e0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
33f0: 23 23 23 23 23 0a 23 23 20 52 65 61 64 79 0a 0a #####.## Ready..
3400: 70 61 63 6b 61 67 65 20 70 72 6f 76 69 64 65 20 package provide
3410: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
3420: 72 74 3a 3a 63 76 73 3a 3a 63 79 63 6c 65 62 72 rt::cvs::cyclebr
3430: 65 61 6b 65 72 20 31 2e 30 0a 72 65 74 75 72 6e eaker 1.0.return
3440: 0a .