Artifact 674bdc4eb4a7f56bf3e807349ce37514b2a6e99a:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[1e177a4c91]
- Cycle breaker, API extension. Added a hook to process the graph between setup and regular consummation. This will be used by pass 8.
by
aku on
2007-11-21 04:11:59.
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 73 7d 20 7b el changesets} {
0900: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 61 ..::variable mya
0910: 74 20 20 20 20 20 20 20 20 30 0a 09 3a 3a 76 61 t 0..::va
0920: 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 66 riable mydotpref
0930: 69 78 20 24 6c 61 62 65 6c 0a 09 3a 3a 76 61 72 ix $label..::var
0940: 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 20 20 20 iable mydotid
0950: 20 20 30 0a 0a 09 23 20 57 65 20 63 72 65 61 74 0...# We creat
0960: 65 20 61 20 67 72 61 70 68 20 6f 66 20 74 68 65 e a graph of the
0970: 20 72 65 76 69 73 69 6f 6e 20 63 68 61 6e 67 65 revision change
0980: 73 65 74 73 2c 20 75 73 69 6e 67 20 74 68 65 20 sets, using the
0990: 66 69 6c 65 0a 09 23 20 6c 65 76 65 6c 20 64 65 file..# level de
09a0: 70 65 6e 64 65 6e 63 69 65 73 20 74 6f 20 63 6f pendencies to co
09b0: 6e 73 74 72 75 63 74 20 61 20 66 69 72 73 74 20 nstruct a first
09c0: 61 70 70 72 6f 78 69 6d 61 74 69 6f 6e 20 6f 66 approximation of
09d0: 20 74 68 65 0a 09 23 20 64 65 70 65 6e 64 65 6e the..# dependen
09e0: 63 69 65 73 20 61 74 20 74 68 65 20 70 72 6f 6a cies at the proj
09f0: 65 63 74 20 6c 65 76 65 6c 2e 20 54 68 65 6e 20 ect level. Then
0a00: 77 65 20 6c 6f 6f 6b 20 66 6f 72 20 63 79 63 6c we look for cycl
0a10: 65 73 0a 09 23 20 69 6e 20 74 68 61 74 20 67 72 es..# in that gr
0a20: 61 70 68 20 61 6e 64 20 62 72 65 61 6b 20 74 68 aph and break th
0a30: 65 6d 2e 0a 0a 09 23 20 31 2e 20 43 72 65 61 74 em....# 1. Creat
0a40: 65 20 6e 6f 64 65 73 20 66 6f 72 20 61 6c 6c 20 e nodes for all
0a50: 72 65 6c 65 76 61 6e 74 20 63 68 61 6e 67 65 73 relevant changes
0a60: 65 74 73 20 61 6e 64 20 61 20 6d 61 70 70 69 6e ets and a mappin
0a70: 67 0a 09 23 20 20 20 20 66 72 6f 6d 20 74 68 65 g..# from the
0a80: 20 72 65 76 69 73 69 6f 6e 73 20 74 6f 20 74 68 revisions to th
0a90: 65 69 72 20 63 68 61 6e 67 65 73 65 74 73 2f 6e eir changesets/n
0aa0: 6f 64 65 73 2e 0a 0a 09 73 65 74 20 64 67 20 5b odes....set dg [
0ab0: 53 65 74 75 70 20 24 63 68 61 6e 67 65 73 65 74 Setup $changeset
0ac0: 73 5d 0a 0a 09 23 20 33 2e 20 4c 61 73 74 6c 79 s]...# 3. Lastly
0ad0: 20 77 65 20 69 74 65 72 61 74 65 20 74 68 65 20 we iterate the
0ae0: 67 72 61 70 68 20 74 6f 70 6f 6c 6f 67 69 63 61 graph topologica
0af0: 6c 6c 79 2e 20 57 65 20 6d 61 72 6b 20 6f 66 66 lly. We mark off
0b00: 0a 09 23 20 20 20 20 74 68 65 20 6e 6f 64 65 73 ..# the nodes
0b10: 20 77 68 69 63 68 20 68 61 76 65 20 6e 6f 20 70 which have no p
0b20: 72 65 64 65 63 65 73 73 6f 72 73 2c 20 69 6e 20 redecessors, in
0b30: 6f 72 64 65 72 20 66 72 6f 6d 0a 09 23 20 20 20 order from..#
0b40: 20 6f 6c 64 65 73 74 20 74 6f 20 79 6f 75 6e 67 oldest to young
0b50: 65 73 74 2c 20 73 61 76 69 6e 67 20 61 6e 64 20 est, saving and
0b60: 72 65 6d 6f 76 69 6e 67 20 64 65 70 65 6e 64 65 removing depende
0b70: 6e 63 69 65 73 2e 20 49 66 0a 09 23 20 20 20 20 ncies. If..#
0b80: 77 65 20 66 69 6e 64 20 6e 6f 20 6e 6f 64 65 73 we find no nodes
0b90: 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 without predece
0ba0: 73 73 6f 72 73 20 77 65 20 68 61 76 65 20 61 20 ssors we have a
0bb0: 63 79 63 6c 65 2c 0a 09 23 20 20 20 20 61 6e 64 cycle,..# and
0bc0: 20 77 6f 72 6b 20 6f 6e 20 62 72 65 61 6b 69 6e work on breakin
0bd0: 67 20 69 74 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 g it....log writ
0be0: 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 3 cyclebreaker
0bf0: 20 7b 4e 6f 77 20 73 6f 72 74 69 6e 67 20 74 68 {Now sorting th
0c00: 65 20 63 68 61 6e 67 65 73 65 74 73 2c 20 62 72 e changesets, br
0c10: 65 61 6b 69 6e 67 20 63 79 63 6c 65 73 7d 0a 0a eaking cycles}..
0c20: 09 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69 .InitializeCandi
0c30: 64 61 74 65 73 20 24 64 67 0a 09 77 68 69 6c 65 dates $dg..while
0c40: 20 7b 31 7d 20 7b 0a 09 20 20 20 20 77 68 69 6c {1} {.. whil
0c50: 65 20 7b 5b 57 69 74 68 6f 75 74 50 72 65 64 65 e {[WithoutPrede
0c60: 63 65 73 73 6f 72 20 24 64 67 20 6e 5d 7d 20 7b cessor $dg n]} {
0c70: 0a 09 09 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b ...ProcessedHook
0c80: 20 24 6e 20 24 6d 79 61 74 0a 09 09 24 64 67 20 $n $myat...$dg
0c90: 6e 6f 64 65 20 64 65 6c 65 74 65 20 24 6e 0a 09 node delete $n..
0ca0: 09 69 6e 63 72 20 6d 79 61 74 0a 09 20 20 20 20 .incr myat..
0cb0: 7d 0a 0a 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c }... if {![ll
0cc0: 65 6e 67 74 68 20 5b 64 67 20 6e 6f 64 65 73 5d ength [dg nodes]
0cd0: 5d 7d 20 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 ]} break... B
0ce0: 72 65 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 reakCycleHook
0cf0: 20 20 20 20 24 64 67 0a 09 20 20 20 20 49 6e 69 $dg.. Ini
0d00: 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 tializeCandidate
0d10: 73 20 24 64 67 0a 09 7d 0a 0a 09 64 67 20 64 65 s $dg..}...dg de
0d20: 73 74 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 74 stroy...log writ
0d30: 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 3 cyclebreaker
0d40: 20 44 6f 6e 65 2e 0a 09 43 6c 65 61 72 48 6f 6f Done...ClearHoo
0d50: 6b 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d ks..return. }
0d60: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 .. # # ## ###
0d70: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 ##### ########
0d80: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 #############..
0d90: 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 62 72 typemethod br
0da0: 65 61 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 42 eak {graph} {..B
0db0: 72 65 61 6b 43 79 63 6c 65 20 24 67 72 61 70 68 reakCycle $graph
0dc0: 20 5b 46 69 6e 64 43 79 63 6c 65 20 24 67 72 61 [FindCycle $gra
0dd0: 70 68 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 ph]..return.
0de0: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
0df0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
0e00: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
0e10: 20 20 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d ## Internal m
0e20: 65 74 68 6f 64 73 0a 0a 20 20 20 20 70 72 6f 63 ethods.. proc
0e30: 20 53 65 74 75 70 20 7b 63 68 61 6e 67 65 73 65 Setup {changese
0e40: 74 73 20 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 69 ts {log 1}} {..i
0e50: 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 f {$log} {..
0e60: 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 6c log write 3 cycl
0e70: 65 62 72 65 61 6b 65 72 20 22 43 72 65 61 74 69 ebreaker "Creati
0e80: 6e 67 20 63 68 61 6e 67 65 73 65 74 20 67 72 61 ng changeset gra
0e90: 70 68 2c 20 66 69 6c 6c 69 6e 67 20 77 69 74 68 ph, filling with
0ea0: 20 6e 6f 64 65 73 22 0a 09 20 20 20 20 6c 6f 67 nodes".. log
0eb0: 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 72 write 3 cyclebr
0ec0: 65 61 6b 65 72 20 22 41 64 64 69 6e 67 20 5b 6e eaker "Adding [n
0ed0: 73 70 20 5b 6c 6c 65 6e 67 74 68 20 24 63 68 61 sp [llength $cha
0ee0: 6e 67 65 73 65 74 73 5d 20 6e 6f 64 65 5d 22 0a ngesets] node]".
0ef0: 09 7d 0a 0a 09 73 65 74 20 64 67 20 5b 73 74 72 .}...set dg [str
0f00: 75 63 74 3a 3a 67 72 61 70 68 20 64 67 5d 0a 0a uct::graph dg]..
0f10: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 63 .foreach cset $c
0f20: 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 20 hangesets {..
0f30: 20 24 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 $dg node insert
0f40: 20 24 63 73 65 74 0a 09 20 20 20 20 24 64 67 20 $cset.. $dg
0f50: 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 65 node set $cse
0f60: 74 20 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 73 t timerange [$cs
0f70: 65 74 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 7d et timerange]..}
0f80: 0a 0a 09 23 20 32 2e 20 46 69 6e 64 20 66 6f 72 ...# 2. Find for
0f90: 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68 all relevant ch
0fa0: 61 6e 67 65 73 65 74 20 74 68 65 69 72 20 72 65 angeset their re
0fb0: 76 69 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 69 visions and thei
0fc0: 72 0a 09 23 20 20 20 20 64 65 70 65 6e 64 65 6e r..# dependen
0fd0: 63 69 65 73 2e 20 4d 61 70 20 74 68 65 20 6c 61 cies. Map the la
0fe0: 74 74 65 72 20 62 61 63 6b 20 74 6f 20 63 68 61 tter back to cha
0ff0: 6e 67 65 73 65 74 73 20 61 6e 64 0a 09 23 20 20 ngesets and..#
1000: 20 20 63 6f 6e 73 74 72 75 63 74 20 74 68 65 20 construct the
1010: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 72 corresponding ar
1020: 63 73 2e 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 cs....if {$log}
1030: 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 {.. log write
1040: 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 3 cyclebreaker
1050: 7b 53 65 74 74 69 6e 67 20 75 70 20 6e 6f 64 65 {Setting up node
1060: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 7d 0a 09 dependencies}..
1070: 7d 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 }...foreach cset
1080: 20 24 63 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 $changesets {..
1090: 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 63 foreach succ
10a0: 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 6f [$cset successo
10b0: 72 73 5d 20 7b 0a 09 09 23 20 43 68 61 6e 67 65 rs] {...# Change
10c0: 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 sets may have de
10d0: 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 pendencies outsi
10e0: 64 65 20 6f 66 20 74 68 65 0a 09 09 23 20 63 68 de of the...# ch
10f0: 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 osen set. These
1100: 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 are ignored...if
1110: 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 {![$dg node exi
1120: 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 sts $succ]} cont
1130: 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 inue...$dg arc i
1140: 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 63 nsert $cset $suc
1150: 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 23 20 c.. }..}...#
1160: 52 75 6e 20 74 68 65 20 75 73 65 72 20 68 6f 6f Run the user hoo
1170: 6b 20 74 6f 20 6d 61 6e 69 70 75 6c 61 74 65 20 k to manipulate
1180: 74 68 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 the graph before
1190: 0a 09 23 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e ..# consummation
11a0: 2e 0a 0a 09 50 72 65 48 6f 6f 6b 20 24 64 67 0a ....PreHook $dg.
11b0: 09 72 65 74 75 72 6e 20 24 64 67 0a 20 20 20 20 .return $dg.
11c0: 7d 0a 0a 20 20 20 20 23 20 49 6e 73 74 65 61 64 }.. # Instead
11d0: 20 6f 66 20 73 65 61 72 63 68 69 6e 67 20 74 68 of searching th
11e0: 65 20 77 68 6f 6c 65 20 67 72 61 70 68 20 66 6f e whole graph fo
11f0: 72 20 74 68 65 20 64 65 67 72 65 65 2d 30 20 6e r the degree-0 n
1200: 6f 64 65 73 20 69 6e 0a 20 20 20 20 23 20 65 61 odes in. # ea
1210: 63 68 20 69 74 65 72 61 74 69 6f 6e 20 77 65 20 ch iteration we
1220: 63 6f 6d 70 75 74 65 20 74 68 65 20 6c 69 73 74 compute the list
1230: 20 6f 6e 63 65 20 74 6f 20 73 74 61 72 74 2c 20 once to start,
1240: 61 6e 64 20 74 68 65 6e 20 6f 6e 6c 79 0a 20 20 and then only.
1250: 20 20 23 20 75 70 64 61 74 65 20 69 74 20 69 6e # update it in
1260: 63 72 65 6d 65 6e 74 61 6c 6c 79 20 62 61 73 65 crementally base
1270: 64 20 6f 6e 20 74 68 65 20 6f 75 74 67 6f 69 6e d on the outgoin
1280: 67 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 g neighbours of
1290: 74 68 65 0a 20 20 20 20 23 20 6e 6f 64 65 20 63 the. # node c
12a0: 68 6f 73 65 6e 20 66 6f 72 20 63 6f 6d 6d 69 74 hosen for commit
12b0: 2e 0a 0a 20 20 20 20 70 72 6f 63 20 49 6e 69 74 ... proc Init
12c0: 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 ializeCandidates
12d0: 20 7b 64 67 7d 20 7b 0a 09 23 20 62 6f 74 74 6f {dg} {..# botto
12e0: 6d 20 3d 20 6c 69 73 74 20 28 6c 69 73 74 20 28 m = list (list (
12f0: 6e 6f 64 65 2c 20 72 61 6e 67 65 20 6d 69 6e 2c node, range min,
1300: 20 72 61 6e 67 65 20 6d 61 78 29 29 0a 09 3a 3a range max))..::
1310: 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f variable mybotto
1320: 6d 0a 09 66 6f 72 65 61 63 68 20 6e 20 5b 24 64 m..foreach n [$d
1330: 67 20 6e 6f 64 65 73 5d 20 7b 0a 09 20 20 20 20 g nodes] {..
1340: 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 if {[$dg node de
1350: 67 72 65 65 20 2d 69 6e 20 24 6e 5d 7d 20 63 6f gree -in $n]} co
1360: 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 70 ntinue.. lapp
1370: 65 6e 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 69 end mybottom [li
1380: 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 nsert [$dg node
1390: 67 65 74 20 24 6e 20 74 69 6d 65 72 61 6e 67 65 get $n timerange
13a0: 5d 20 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74 20 ] 0 $n]..}..set
13b0: 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 mybottom [lsort
13c0: 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 -index 1 -intege
13d0: 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 r [lsort -index
13e0: 32 20 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 6f 2 -integer $mybo
13f0: 74 74 6f 6d 5d 5d 0a 09 72 65 74 75 72 6e 0a 20 ttom]]..return.
1400: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 }.. proc W
1410: 69 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f ithoutPredecesso
1420: 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 r {dg nv} {..::v
1430: 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d ariable mybottom
1440: 0a 0a 09 75 70 76 61 72 20 31 20 24 6e 76 20 6e ...upvar 1 $nv n
1450: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
1460: 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b 20 72 65 $mybottom]} { re
1470: 74 75 72 6e 20 30 20 7d 0a 0a 09 73 65 74 20 6e turn 0 }...set n
1480: 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e 64 65 78 [lindex [lindex
1490: 20 24 6d 79 62 6f 74 74 6f 6d 20 30 5d 20 30 5d $mybottom 0] 0]
14a0: 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b ..set mybottom [
14b0: 6c 72 61 6e 67 65 20 24 6d 79 62 6f 74 74 6f 6d lrange $mybottom
14c0: 20 31 20 65 6e 64 5d 0a 09 73 65 74 20 63 68 61 1 end]..set cha
14d0: 6e 67 65 64 20 30 0a 0a 09 23 20 55 70 64 61 74 nged 0...# Updat
14e0: 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 e list of nodes
14f0: 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 without predeces
1500: 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e 20 74 68 sor, based on th
1510: 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67 20 6e 65 e..# outgoing ne
1520: 69 67 68 62 6f 75 72 73 20 6f 66 20 74 68 65 20 ighbours of the
1530: 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 54 68 69 chosen node. Thi
1540: 73 20 73 68 6f 75 6c 64 20 62 65 0a 09 23 20 66 s should be..# f
1550: 61 73 74 65 72 20 74 68 61 6e 20 69 74 65 72 61 aster than itera
1560: 74 69 6e 67 20 6f 66 20 74 68 65 20 77 68 6f 6c ting of the whol
1570: 65 20 73 65 74 20 6f 66 20 6e 6f 64 65 73 2c 20 e set of nodes,
1580: 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 23 20 77 finding all..# w
1590: 69 74 68 6f 75 74 20 70 72 65 64 65 63 65 73 73 ithout predecess
15a0: 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20 74 68 65 ors, sorting the
15b0: 6d 20 62 79 20 74 69 6d 65 2c 20 65 74 63 2e 20 m by time, etc.
15c0: 70 70 2e 0a 09 66 6f 72 65 61 63 68 20 6f 75 74 pp...foreach out
15d0: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
15e0: 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69 66 20 7b $n] {.. if {
15f0: 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 72 65 65 [$dg node degree
1600: 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 31 7d 20 -in $out] > 1}
1610: 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 23 20 continue.. #
1620: 44 65 67 72 65 65 2d 31 20 6e 65 69 67 68 62 6f Degree-1 neighbo
1630: 75 72 2c 20 77 69 6c 6c 20 68 61 76 65 20 6e 6f ur, will have no
1640: 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 61 66 predecessors af
1650: 74 65 72 20 74 68 65 0a 09 20 20 20 20 23 20 72 ter the.. # r
1660: 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 50 75 74 emoval of n. Put
1670: 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e 0a 09 20 on the list...
1680: 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 lappend mybot
1690: 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 tom [linsert [$d
16a0: 67 20 6e 6f 64 65 20 67 65 74 20 24 6f 75 74 20 g node get $out
16b0: 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f 75 timerange] 0 $ou
16c0: 74 5d 0a 09 20 20 20 20 73 65 74 20 63 68 61 6e t].. set chan
16d0: 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24 63 ged 1..}..if {$c
16e0: 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20 73 hanged} {.. s
16f0: 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f et mybottom [lso
1700: 72 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 rt -index 1 -int
1710: 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 eger [lsort -ind
1720: 65 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 6d ex 2 -integer $m
1730: 79 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 ybottom]]..}...#
1740: 20 57 65 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 We do not delet
1750: 65 20 74 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 e the node immed
1760: 69 61 74 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 iately, to allow
1770: 20 74 68 65 20 53 61 76 65 0a 09 23 20 70 72 6f the Save..# pro
1780: 63 65 64 75 72 65 20 74 6f 20 73 61 76 65 20 74 cedure to save t
1790: 68 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 he dependencies
17a0: 61 73 20 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 as well (encoded
17b0: 20 69 6e 20 74 68 65 0a 09 23 20 61 72 63 73 29 in the..# arcs)
17c0: 2e 0a 09 72 65 74 75 72 6e 20 31 0a 20 20 20 20 ...return 1.
17d0: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 }.. proc Find
17e0: 43 79 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 Cycle {dg} {..#
17f0: 54 68 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 This procedure i
1800: 73 20 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c s run if and onl
1810: 79 20 74 68 65 20 67 72 61 70 68 20 69 73 20 6e y the graph is n
1820: 6f 74 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 ot empty and..#
1830: 61 6c 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 all nodes have p
1840: 72 65 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 redecessors. Thi
1850: 73 20 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 s means that eac
1860: 68 20 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 h node is..# eit
1870: 68 65 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 her part of a cy
1880: 63 6c 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 cle or (indirect
1890: 6c 79 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e ly) depending on
18a0: 20 61 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 a node..# in a
18b0: 63 79 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 cycle. We can st
18c0: 61 72 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 art at an arbitr
18d0: 61 72 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 ary node, follow
18e0: 20 69 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 its..# incoming
18f0: 20 65 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 edges to its pr
1900: 65 64 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c edecessors until
1910: 20 77 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 we see a node a
1920: 0a 09 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e ..# second time.
1930: 20 54 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 That node close
1940: 73 20 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 s the cycle and
1950: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 the beginning is
1960: 0a 09 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 ..# its first oc
1970: 63 75 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 curence. Note th
1980: 61 74 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 at we can choose
1990: 20 61 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 an arbitrary..#
19a0: 20 70 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 predecessor of
19b0: 65 61 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c each node as wel
19c0: 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 l, we do not hav
19d0: 65 20 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 e to search....#
19e0: 20 57 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 We record for e
19f0: 61 63 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 ach node the ind
1a00: 65 78 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 ex of the first
1a10: 61 70 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 appearance in..#
1a20: 20 74 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e the path, makin
1a30: 67 20 69 74 20 65 61 73 79 20 61 74 20 74 68 65 g it easy at the
1a40: 20 65 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 end to cut the
1a50: 63 79 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 cycle from..# it
1a60: 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 ....# Choose arb
1a70: 69 74 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 itrary node to s
1a80: 74 61 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 tart our search
1a90: 61 74 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b at...set start [
1aa0: 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 lindex [$dg node
1ab0: 73 5d 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 s] 0]...# Initia
1ac0: 6c 69 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 lize state, path
1ad0: 20 6f 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 of seen nodes,
1ae0: 61 6e 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 and when seen...
1af0: 73 65 74 20 20 20 20 20 20 20 70 61 74 68 20 7b set path {
1b00: 7d 0a 09 61 72 72 61 79 20 73 65 74 20 73 65 65 }..array set see
1b10: 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d n {}...while {1}
1b20: 20 7b 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 {.. # Stop s
1b30: 65 61 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 earching when we
1b40: 20 68 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 have seen the c
1b50: 75 72 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 urrent node..
1b60: 20 23 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 # already, the
1b70: 63 69 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 circle has been
1b80: 63 6c 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 closed... if
1b90: 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 {[info exists se
1ba0: 65 6e 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 en($start)]} bre
1bb0: 61 6b 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 ak.. lappend
1bc0: 70 61 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 path $start..
1bd0: 20 73 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 set seen($start
1be0: 29 20 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 ) [expr {[llengt
1bf0: 68 20 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 h $path]-1}]..
1c00: 20 20 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 # Choose arbit
1c10: 72 61 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 rary predecessor
1c20: 0a 09 20 20 20 20 73 65 74 20 73 74 61 72 74 20 .. set start
1c30: 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 [lindex [$dg nod
1c40: 65 73 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 es -in $start] 0
1c50: 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 ]..}...return [s
1c60: 74 72 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 truct::list reve
1c70: 72 73 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 rse [lrange $pat
1c80: 68 20 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 h $seen($start)
1c90: 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 end]]. }..
1ca0: 20 70 72 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 proc ID {cset}
1cb0: 7b 20 72 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 { return "<[$cse
1cc0: 74 20 69 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 t id]>" }.. p
1cd0: 72 6f 63 20 42 72 65 61 6b 43 79 63 6c 65 20 7b roc BreakCycle {
1ce0: 64 67 20 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 dg cycle} {..# T
1cf0: 68 65 20 63 79 63 6c 65 20 77 65 20 68 61 76 65 he cycle we have
1d00: 20 67 6f 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 gotten is broke
1d10: 6e 20 62 79 20 62 72 65 61 6b 69 6e 67 20 61 70 n by breaking ap
1d20: 61 72 74 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f art one or..# mo
1d30: 72 65 20 6f 66 20 74 68 65 20 63 68 61 6e 67 65 re of the change
1d40: 73 65 74 73 20 69 6e 20 74 68 65 20 63 79 63 6c sets in the cycl
1d50: 65 2e 20 54 68 69 73 20 63 61 75 73 65 73 20 75 e. This causes u
1d60: 73 20 74 6f 0a 09 23 20 63 72 65 61 74 65 20 6f s to..# create o
1d70: 6e 65 20 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 ne or more chang
1d80: 65 73 65 74 73 20 77 68 69 63 68 20 61 72 65 20 esets which are
1d90: 74 6f 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c to be committed,
1da0: 0a 09 23 20 61 64 64 65 64 20 74 6f 20 74 68 65 ..# added to the
1db0: 20 67 72 61 70 68 2c 20 65 74 63 2e 20 70 70 2e graph, etc. pp.
1dc0: 0a 0a 09 73 65 74 20 63 70 72 69 6e 74 20 5b 6a ...set cprint [j
1dd0: 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 oin [struct::lis
1de0: 74 20 6d 61 70 20 24 63 79 63 6c 65 20 5b 6d 79 t map $cycle [my
1df0: 70 72 6f 63 20 49 44 5d 5d 20 7b 20 7d 5d 0a 0a proc ID]] { }]..
1e00: 09 6c 61 70 70 65 6e 64 20 63 79 63 6c 65 20 5b .lappend cycle [
1e10: 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 30 5d lindex $cycle 0]
1e20: 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 [lindex $cycle
1e30: 31 5d 0a 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 1]..set bestlink
1e40: 20 7b 7d 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 {}..set bestnod
1e50: 65 20 7b 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c e {}...foreach \
1e60: 0a 09 20 20 20 20 70 72 65 76 20 5b 6c 72 61 6e .. prev [lran
1e70: 67 65 20 24 63 79 63 6c 65 20 30 20 65 6e 64 2d ge $cycle 0 end-
1e80: 32 5d 20 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 2] \.. cset [
1e90: 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 31 20 lrange $cycle 1
1ea0: 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 end-1] \.. ne
1eb0: 78 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c xt [lrange $cycl
1ec0: 65 20 32 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 e 2 end] {....#
1ed0: 45 61 63 68 20 74 72 69 70 6c 65 20 50 52 45 56 Each triple PREV
1ee0: 20 2d 3e 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 -> CSET -> NEXT
1ef0: 20 6f 66 20 63 68 61 6e 67 65 73 65 74 73 2c 20 of changesets,
1f00: 61 0a 09 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 a...# 'link' in
1f10: 74 68 65 20 63 79 63 6c 65 2c 20 69 73 20 61 6e the cycle, is an
1f20: 61 6c 79 73 65 64 20 61 6e 64 20 74 68 65 20 62 alysed and the b
1f30: 65 73 74 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e est...# location
1f40: 20 77 68 65 72 65 20 74 6f 20 61 74 20 6c 65 61 where to at lea
1f50: 73 74 20 77 65 61 6b 65 6e 20 74 68 65 20 63 79 st weaken the cy
1f60: 63 6c 65 20 69 73 0a 09 09 23 20 63 68 6f 73 65 cle is...# chose
1f70: 6e 20 66 6f 72 20 66 75 72 74 68 65 72 20 70 72 n for further pr
1f80: 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 ocessing.....set
1f90: 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a link [project::
1fa0: 72 65 76 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 revlink %AUTO% $
1fb0: 70 72 65 76 20 24 63 73 65 74 20 24 6e 65 78 74 prev $cset $next
1fc0: 5d 0a 09 09 69 66 20 7b 24 62 65 73 74 6c 69 6e ]...if {$bestlin
1fd0: 6b 20 65 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 k eq ""} {...
1fe0: 20 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c set bestlink $l
1ff0: 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 ink... set be
2000: 73 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d stnode $cset...}
2010: 20 65 6c 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 elseif {[$link
2020: 62 65 74 74 65 72 74 68 61 6e 20 24 62 65 73 74 betterthan $best
2030: 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 link]} {... $
2040: 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 bestlink destroy
2050: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6c ... set bestl
2060: 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 ink $link...
2070: 73 65 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 set bestnode $cs
2080: 65 74 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 et...} else {...
2090: 20 20 20 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f $link destro
20a0: 79 0a 09 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c y...}.. }...l
20b0: 6f 67 20 77 72 69 74 65 20 35 20 62 72 65 61 6b og write 5 break
20c0: 72 63 79 63 6c 65 20 22 42 72 65 61 6b 69 6e 67 rcycle "Breaking
20d0: 20 63 79 63 6c 65 20 28 24 63 70 72 69 6e 74 29 cycle ($cprint)
20e0: 20 62 79 20 73 70 6c 69 74 74 69 6e 67 20 63 68 by splitting ch
20f0: 61 6e 67 65 73 65 74 20 3c 5b 24 62 65 73 74 6e angeset <[$bestn
2100: 6f 64 65 20 69 64 5d 3e 22 0a 09 73 65 74 20 49 ode id]>"..set I
2110: 44 20 5b 24 62 65 73 74 6e 6f 64 65 20 69 64 5d D [$bestnode id]
2120: 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 ..Mark $dg -${ID
2130: 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 65 74 20 6e }-before...set n
2140: 65 77 63 73 65 74 73 20 5b 24 62 65 73 74 6c 69 ewcsets [$bestli
2150: 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 74 nk break]..$best
2160: 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 20 link destroy..
2170: 20 20 20 20 20 20 23 20 41 74 20 74 68 69 73 20 # At this
2180: 70 6f 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 68 point the old ch
2190: 61 6e 67 65 73 65 74 20 28 42 45 53 54 4e 4f 44 angeset (BESTNOD
21a0: 45 29 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 20 E) is gone.
21b0: 20 20 20 23 20 61 6c 72 65 61 64 79 2e 20 57 65 # already. We
21c0: 20 72 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d 20 remove it from
21d0: 74 68 65 20 67 72 61 70 68 20 61 73 20 77 65 6c the graph as wel
21e0: 6c 20 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 72 l and then enter
21f0: 0a 20 20 20 20 20 20 20 20 23 20 74 68 65 20 66 . # the f
2200: 72 61 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 74 ragments generat
2210: 65 64 20 66 6f 72 20 69 74 2e 0a 0a 09 23 20 4e ed for it....# N
2220: 4f 54 45 2e 20 57 65 20 68 61 76 65 20 74 6f 20 OTE. We have to
2230: 67 65 74 20 74 68 65 20 6c 69 73 74 20 6f 66 20 get the list of
2240: 69 6e 63 6f 6d 69 6e 67 20 6e 65 69 67 68 62 6f incoming neighbo
2250: 75 72 73 20 61 6e 64 0a 09 23 20 72 65 63 6f 6d urs and..# recom
2260: 70 75 74 65 20 74 68 65 69 72 20 73 75 63 63 65 pute their succe
2270: 73 73 6f 72 73 20 61 66 74 65 72 20 74 68 65 20 ssors after the
2280: 6e 65 77 20 6e 6f 64 65 73 20 68 61 76 65 20 62 new nodes have b
2290: 65 65 6e 0a 09 23 20 69 6e 73 65 72 74 65 64 2e een..# inserted.
22a0: 20 54 68 65 69 72 20 6f 75 74 67 6f 69 6e 67 20 Their outgoing
22b0: 61 72 63 73 20 77 69 6c 6c 20 6e 6f 77 20 67 6f arcs will now go
22c0: 20 74 6f 20 6f 6e 65 20 6f 72 20 62 6f 74 68 20 to one or both
22d0: 6f 66 0a 09 23 20 74 68 65 20 6e 65 77 20 6e 6f of..# the new no
22e0: 64 65 73 2c 20 61 6e 64 20 6e 6f 74 20 72 65 64 des, and not red
22f0: 6f 69 6e 67 20 74 68 65 6d 20 6d 61 79 20 63 61 oing them may ca
2300: 75 73 65 20 75 73 20 74 6f 20 66 6f 72 67 65 74 use us to forget
2310: 0a 09 23 20 63 69 72 63 6c 65 73 2c 20 6c 65 61 ..# circles, lea
2320: 76 69 6e 67 20 74 68 65 6d 20 69 6e 2c 20 75 6e ving them in, un
2330: 62 72 6f 6b 65 6e 2e 0a 0a 09 73 65 74 20 70 72 broken....set pr
2340: 65 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 69 6e e [$dg nodes -in
2350: 20 24 62 65 73 74 6e 6f 64 65 5d 0a 0a 20 20 20 $bestnode]..
2360: 20 20 20 20 20 24 64 67 20 6e 6f 64 65 20 64 65 $dg node de
2370: 6c 65 74 65 20 24 62 65 73 74 6e 6f 64 65 0a 0a lete $bestnode..
2380: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e .foreach cset $n
2390: 65 77 63 73 65 74 73 20 7b 0a 09 20 20 20 20 24 ewcsets {.. $
23a0: 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 dg node insert $
23b0: 63 73 65 74 0a 09 20 20 20 20 24 64 67 20 6e 6f cset.. $dg no
23c0: 64 65 20 73 65 74 20 20 20 20 24 63 73 65 74 20 de set $cset
23d0: 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 73 65 74 timerange [$cset
23e0: 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 7d 0a 0a timerange]..}..
23f0: 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 6e .foreach cset $n
2400: 65 77 63 73 65 74 73 20 7b 0a 09 20 20 20 20 66 ewcsets {.. f
2410: 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 oreach succ [$cs
2420: 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b et successors] {
2430: 0a 09 09 23 20 54 68 65 20 6e 65 77 20 63 68 61 ...# The new cha
2440: 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 ngesets may have
2450: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 dependencies ou
2460: 74 73 69 64 65 20 6f 66 0a 09 09 23 20 74 68 65 tside of...# the
2470: 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 chosen set. The
2480: 73 65 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 se are ignored..
2490: 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 .if {![$dg node
24a0: 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 exists $succ]} c
24b0: 6f 6e 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 ontinue...$dg ar
24c0: 63 20 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 c insert $cset $
24d0: 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 succ.. }..}..
24e0: 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 70 72 foreach cset $pr
24f0: 65 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 63 68 e {.. foreach
2500: 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 75 63 succ [$cset suc
2510: 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 20 4e cessors] {...# N
2520: 6f 74 65 20 74 68 61 74 20 74 68 65 20 61 72 63 ote that the arc
2530: 20 6d 61 79 20 61 6c 72 65 61 64 79 20 65 78 69 may already exi
2540: 73 74 20 69 6e 20 74 68 65 20 67 72 61 70 68 2e st in the graph.
2550: 20 49 66 0a 09 09 23 20 73 6f 20 69 67 6e 6f 72 If...# so ignor
2560: 65 20 69 74 2e 20 54 68 65 20 6e 65 77 20 63 68 e it. The new ch
2570: 61 6e 67 65 73 65 74 73 20 6d 61 79 20 68 61 76 angesets may hav
2580: 65 0a 09 09 23 20 64 65 70 65 6e 64 65 6e 63 69 e...# dependenci
2590: 65 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 68 es outside of th
25a0: 65 20 63 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 e chosen set. Th
25b0: 65 73 65 20 61 72 65 0a 09 09 23 20 69 67 6e 6f ese are...# igno
25c0: 72 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 20 red...if {![$dg
25d0: 6e 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 63 node exists $suc
25e0: 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 69 c]} continue...i
25f0: 66 20 7b 5b 48 61 73 41 72 63 20 24 64 67 20 24 f {[HasArc $dg $
2600: 63 73 65 74 20 24 73 75 63 63 5d 7d 20 63 6f 6e cset $succ]} con
2610: 74 69 6e 75 65 3b 23 20 54 4f 44 4f 20 73 68 6f tinue;# TODO sho
2620: 75 6c 64 20 62 65 20 67 72 61 70 68 20 6d 65 74 uld be graph met
2630: 68 6f 64 2e 0a 09 09 24 64 67 20 61 72 63 20 69 hod....$dg arc i
2640: 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 63 nsert $cset $suc
2650: 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 4d 61 c.. }..}...Ma
2660: 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d 61 66 rk $dg -${ID}-af
2670: 74 65 72 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 ter..return.
2680: 7d 0a 0a 20 20 20 20 23 20 54 4f 44 4f 3a 20 54 }.. # TODO: T
2690: 68 69 73 20 73 68 6f 75 6c 64 20 62 65 20 61 20 his should be a
26a0: 67 72 61 70 68 20 6d 65 74 68 6f 64 2e 0a 20 20 graph method..
26b0: 20 20 70 72 6f 63 20 48 61 73 41 72 63 20 7b 64 proc HasArc {d
26c0: 67 20 61 20 62 7d 20 7b 0a 09 23 38 2e 35 3a 20 g a b} {..#8.5:
26d0: 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b 24 62 return [expr {$b
26e0: 20 69 6e 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d in [$dg nodes -
26f0: 6f 75 74 20 24 61 5d 7d 5d 0a 09 69 66 20 7b 5b out $a]}]..if {[
2700: 6c 73 65 61 72 63 68 20 2d 65 78 61 63 74 20 5b lsearch -exact [
2710: 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 20 24 $dg nodes -out $
2720: 61 5d 20 24 62 5d 20 3c 20 30 7d 20 7b 20 72 65 a] $b] < 0} { re
2730: 74 75 72 6e 20 30 20 7d 0a 09 72 65 74 75 72 6e turn 0 }..return
2740: 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 1. }.. pr
2750: 6f 63 20 4d 61 72 6b 20 7b 64 67 20 7b 73 75 66 oc Mark {dg {suf
2760: 66 69 78 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a 76 61 fix {}}} {..::va
2770: 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 riable mydotdest
2780: 69 6e 61 74 69 6f 6e 0a 09 69 66 20 7b 24 6d 79 ination..if {$my
2790: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 65 dotdestination e
27a0: 71 20 22 22 7d 20 72 65 74 75 72 6e 0a 09 3a 3a q ""} return..::
27b0: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 variable mydotpr
27c0: 65 66 69 78 0a 09 3a 3a 76 61 72 69 61 62 6c 65 efix..::variable
27d0: 20 6d 79 64 6f 74 69 64 0a 09 73 65 74 20 66 6e mydotid..set fn
27e0: 61 6d 65 20 24 6d 79 64 6f 74 64 65 73 74 69 6e ame $mydotdestin
27f0: 61 74 69 6f 6e 2f 24 7b 6d 79 64 6f 74 70 72 65 ation/${mydotpre
2800: 66 69 78 7d 24 7b 6d 79 64 6f 74 69 64 7d 24 7b fix}${mydotid}${
2810: 73 75 66 66 69 78 7d 2e 64 6f 74 0a 09 66 69 6c suffix}.dot..fil
2820: 65 20 6d 6b 64 69 72 20 5b 66 69 6c 65 20 64 69 e mkdir [file di
2830: 72 6e 61 6d 65 20 24 66 6e 61 6d 65 5d 0a 09 64 rname $fname]..d
2840: 6f 74 20 77 72 69 74 65 20 24 64 67 20 24 6d 79 ot write $dg $my
2850: 64 6f 74 70 72 65 66 69 78 24 73 75 66 66 69 78 dotprefix$suffix
2860: 20 24 66 6e 61 6d 65 0a 09 69 6e 63 72 20 6d 79 $fname..incr my
2870: 64 6f 74 69 64 0a 0a 09 6c 6f 67 20 77 72 69 74 dotid...log writ
2880: 65 20 35 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 5 cyclebreaker
2890: 20 22 2e 64 6f 74 20 65 78 70 6f 72 74 20 24 66 ".dot export $f
28a0: 6e 61 6d 65 22 0a 09 72 65 74 75 72 6e 0a 20 20 name"..return.
28b0: 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 }.. # # ##
28c0: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
28d0: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
28e0: 0a 20 20 20 20 23 23 20 43 61 6c 6c 62 61 63 6b . ## Callback
28f0: 20 69 6e 76 6f 6b 61 74 69 6f 6e 20 2e 2e 2e 0a invokation ....
2900: 0a 20 20 20 20 70 72 6f 63 20 50 72 65 48 6f 6f . proc PreHoo
2910: 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 23 20 47 k {graph} {..# G
2920: 69 76 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 ive the user of
2930: 74 68 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 the cycle breake
2940: 72 20 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 r the opportunit
2950: 79 20 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 y to work..# wit
2960: 68 20 74 68 65 20 67 72 61 70 68 20 62 65 74 77 h the graph betw
2970: 65 65 6e 20 73 65 74 75 70 20 61 6e 64 20 63 6f een setup and co
2980: 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a 0a 09 3a 3a nsummation....::
2990: 76 61 72 69 61 62 6c 65 20 6d 79 70 72 65 63 6d variable myprecm
29a0: 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 d..if {![llength
29b0: 20 24 6d 79 70 72 65 63 6d 64 5d 7d 20 72 65 74 $myprecmd]} ret
29c0: 75 72 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 urn...uplevel #0
29d0: 20 5b 6c 69 6e 73 65 72 74 20 24 6d 79 70 72 65 [linsert $mypre
29e0: 63 6d 64 20 65 6e 64 20 24 67 72 61 70 68 5d 0a cmd end $graph].
29f0: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
2a00: 20 20 20 70 72 6f 63 20 50 72 6f 63 65 73 73 65 proc Processe
2a10: 64 48 6f 6f 6b 20 7b 63 73 65 74 20 70 6f 73 7d dHook {cset pos}
2a20: 20 7b 0a 09 23 20 47 69 76 65 20 74 68 65 20 75 {..# Give the u
2a30: 73 65 72 20 6f 66 20 74 68 65 20 63 79 63 6c 65 ser of the cycle
2a40: 20 62 72 65 61 6b 65 72 20 74 68 65 20 6f 70 70 breaker the opp
2a50: 6f 72 74 75 6e 69 74 79 20 74 6f 20 77 6f 72 6b ortunity to work
2a60: 0a 09 23 20 77 69 74 68 20 74 68 65 20 63 68 61 ..# with the cha
2a70: 6e 67 65 73 65 74 20 62 65 66 6f 72 65 20 69 74 ngeset before it
2a80: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d is removed from
2a90: 20 74 68 65 20 67 72 61 70 68 2e 0a 0a 09 3a 3a the graph....::
2aa0: 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 variable mysavec
2ab0: 6d 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 md..if {![llengt
2ac0: 68 20 24 6d 79 73 61 76 65 63 6d 64 5d 7d 20 72 h $mysavecmd]} r
2ad0: 65 74 75 72 6e 0a 0a 09 75 70 6c 65 76 65 6c 20 eturn...uplevel
2ae0: 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 6d 79 73 #0 [linsert $mys
2af0: 61 76 65 63 6d 64 20 65 6e 64 20 24 70 6f 73 20 avecmd end $pos
2b00: 24 63 73 65 74 5d 0a 09 72 65 74 75 72 6e 0a 20 $cset]..return.
2b10: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 42 }.. proc B
2b20: 72 65 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 7b 67 reakCycleHook {g
2b30: 72 61 70 68 7d 20 7b 0a 09 23 20 43 61 6c 6c 20 raph} {..# Call
2b40: 6f 75 74 20 74 6f 20 74 68 65 20 63 68 6f 73 65 out to the chose
2b50: 6e 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72 20 n algorithm for
2b60: 63 79 63 6c 65 20 62 72 65 61 6b 69 6e 67 2e 20 cycle breaking.
2b70: 46 69 6e 64 69 6e 67 0a 09 23 20 61 20 63 79 63 Finding..# a cyc
2b80: 6c 65 20 69 66 20 6e 6f 20 62 72 65 61 6b 65 72 le if no breaker
2b90: 20 77 61 73 20 63 68 6f 73 65 6e 20 69 73 20 61 was chosen is a
2ba0: 6e 20 65 72 72 6f 72 2e 0a 0a 09 3a 3a 76 61 72 n error....::var
2bb0: 69 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 iable mybreakcmd
2bc0: 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 ..if {![llength
2bd0: 24 6d 79 62 72 65 61 6b 63 6d 64 5d 7d 20 7b 0a $mybreakcmd]} {.
2be0: 09 20 20 20 20 74 72 6f 75 62 6c 65 20 66 61 74 . trouble fat
2bf0: 61 6c 20 22 46 6f 75 6e 64 20 61 20 63 79 63 6c al "Found a cycl
2c00: 65 2c 20 65 78 70 65 63 74 69 6e 67 20 6e 6f 6e e, expecting non
2c10: 65 2e 22 0a 09 20 20 20 20 65 78 69 74 20 31 0a e.".. exit 1.
2c20: 09 7d 0a 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 .}...uplevel #0
2c30: 5b 6c 69 6e 73 65 72 74 20 24 6d 79 62 72 65 61 [linsert $mybrea
2c40: 6b 63 6d 64 20 65 6e 64 20 24 67 72 61 70 68 5d kcmd end $graph]
2c50: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
2c60: 20 20 20 20 70 72 6f 63 20 43 6c 65 61 72 48 6f proc ClearHo
2c70: 6f 6b 73 20 7b 7d 20 7b 0a 09 3a 3a 76 61 72 69 oks {} {..::vari
2c80: 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 20 20 20 able myprecmd
2c90: 7b 7d 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d {}..::variable m
2ca0: 79 73 61 76 65 63 6d 64 20 20 7b 7d 0a 09 3a 3a ysavecmd {}..::
2cb0: 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 6b variable mybreak
2cc0: 63 6d 64 20 7b 7d 0a 09 72 65 74 75 72 6e 0a 20 cmd {}..return.
2cd0: 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 }.. # # ##
2ce0: 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 ### ##### #####
2cf0: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
2d00: 23 0a 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 #.. typevaria
2d10: 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 30 20 ble myat 0
2d20: 3b 20 23 20 43 6f 75 6e 74 65 72 20 66 6f 72 20 ; # Counter for
2d30: 63 6f 6d 6d 69 74 20 69 64 73 20 66 6f 72 20 74 commit ids for t
2d40: 68 65 0a 09 09 09 20 20 20 20 20 20 20 23 20 63 he.... # c
2d50: 68 61 6e 67 65 73 65 74 73 2e 0a 20 20 20 20 74 hangesets.. t
2d60: 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 6f ypevariable mybo
2d70: 74 74 6f 6d 20 7b 7d 20 3b 20 23 20 4c 69 73 74 ttom {} ; # List
2d80: 20 6f 66 20 74 68 65 20 63 61 6e 64 69 64 61 74 of the candidat
2d90: 65 20 6e 6f 64 65 73 20 66 6f 72 0a 09 09 09 20 e nodes for....
2da0: 20 20 20 20 20 20 23 20 63 6f 6d 6d 69 74 74 69 # committi
2db0: 6e 67 2e 0a 0a 20 20 20 20 74 79 70 65 76 61 72 ng... typevar
2dc0: 69 61 62 6c 65 20 6d 79 70 72 65 63 6d 64 20 20 iable myprecmd
2dd0: 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b {} ; # Callback
2de0: 2c 20 63 68 61 6e 67 65 20 67 72 61 70 68 20 62 , change graph b
2df0: 65 66 6f 72 65 20 77 61 6c 6b 2e 0a 20 20 20 20 efore walk..
2e00: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 73 typevariable mys
2e10: 61 76 65 63 6d 64 20 20 7b 7d 20 3b 20 23 20 43 avecmd {} ; # C
2e20: 61 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 allback, for eac
2e30: 68 20 70 72 6f 63 65 73 73 65 64 20 6e 6f 64 65 h processed node
2e40: 2e 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 62 .. typevariab
2e50: 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b 7d le mybreakcmd {}
2e60: 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b 2c 20 66 ; # Callback, f
2e70: 6f 72 20 65 61 63 68 20 66 6f 75 6e 64 20 63 79 or each found cy
2e80: 63 6c 65 2e 0a 0a 20 20 20 20 74 79 70 65 76 61 cle... typeva
2e90: 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 73 74 riable mydotdest
2ea0: 69 6e 61 74 69 6f 6e 20 7b 7d 20 3b 20 23 20 44 ination {} ; # D
2eb0: 65 73 74 69 6e 61 74 69 6f 6e 20 64 69 72 65 63 estination direc
2ec0: 74 6f 72 79 20 66 6f 72 20 74 68 65 0a 09 09 09 tory for the....
2ed0: 09 20 20 20 20 20 20 20 23 20 67 65 6e 65 72 61 . # genera
2ee0: 74 65 64 20 2e 64 6f 74 20 66 69 6c 65 73 2e 0a ted .dot files..
2ef0: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
2f00: 20 6d 79 64 6f 74 70 72 65 66 69 78 20 20 20 20 mydotprefix
2f10: 20 20 7b 7d 20 3b 20 23 20 50 72 65 66 69 78 20 {} ; # Prefix
2f20: 66 6f 72 20 64 6f 74 20 66 69 6c 65 73 20 77 68 for dot files wh
2f30: 65 6e 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 en..... #
2f40: 65 78 70 6f 72 74 69 6e 67 20 74 68 65 20 67 72 exporting the gr
2f50: 61 70 68 73 2e 0a 20 20 20 20 74 79 70 65 76 61 aphs.. typeva
2f60: 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 20 20 riable mydotid
2f70: 20 20 20 20 20 20 20 20 20 30 20 3b 20 23 20 43 0 ; # C
2f80: 6f 75 6e 74 65 72 20 66 6f 72 20 64 6f 74 20 66 ounter for dot f
2f90: 69 6c 65 20 6e 61 6d 65 0a 09 09 09 09 20 20 20 ile name.....
2fa0: 20 20 20 20 23 20 67 65 6e 65 72 61 74 69 6f 6e # generation
2fb0: 2e 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 ... # # ## ##
2fc0: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
2fd0: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20 #############.
2fe0: 20 20 20 23 23 20 43 6f 6e 66 69 67 75 72 61 74 ## Configurat
2ff0: 69 6f 6e 0a 0a 20 20 20 20 70 72 61 67 6d 61 20 ion.. pragma
3000: 2d 68 61 73 69 6e 73 74 61 6e 63 65 73 20 20 20 -hasinstances
3010: 6e 6f 20 3b 20 23 20 73 69 6e 67 6c 65 74 6f 6e no ; # singleton
3020: 0a 20 20 20 20 70 72 61 67 6d 61 20 2d 68 61 73 . pragma -has
3030: 74 79 70 65 69 6e 66 6f 20 20 20 20 6e 6f 20 3b typeinfo no ;
3040: 20 23 20 6e 6f 20 69 6e 74 72 6f 73 70 65 63 74 # no introspect
3050: 69 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 20 2d ion. pragma -
3060: 68 61 73 74 79 70 65 64 65 73 74 72 6f 79 20 6e hastypedestroy n
3070: 6f 20 3b 20 23 20 69 6d 6d 6f 72 74 61 6c 0a 0a o ; # immortal..
3080: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
3090: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
30a0: 23 23 23 23 23 23 23 23 23 23 23 0a 7d 0a 0a 6e ###########.}..n
30b0: 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 3a 3a amespace eval ::
30c0: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
30d0: 72 74 3a 3a 63 76 73 20 7b 0a 20 20 20 20 6e 61 rt::cvs {. na
30e0: 6d 65 73 70 61 63 65 20 65 78 70 6f 72 74 20 63 mespace export c
30f0: 79 63 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 yclebreaker.
3100: 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 63 namespace eval c
3110: 79 63 6c 65 62 72 65 61 6b 65 72 20 7b 0a 09 6e yclebreaker {..n
3120: 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20 70 72 amespace eval pr
3130: 6f 6a 65 63 74 20 7b 0a 09 20 20 20 20 6e 61 6d oject {.. nam
3140: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3150: 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f vc::fossil::impo
3160: 72 74 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 rt::cvs::project
3170: 3a 3a 72 65 76 0a 09 20 20 20 20 6e 61 6d 65 73 ::rev.. names
3180: 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 pace import ::vc
3190: 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 ::fossil::import
31a0: 3a 3a 63 76 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a ::cvs::project::
31b0: 72 65 76 6c 69 6e 6b 0a 09 7d 0a 09 6e 61 6d 65 revlink..}..name
31c0: 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 space import ::v
31d0: 63 3a 3a 74 6f 6f 6c 73 3a 3a 6d 69 73 63 3a 3a c::tools::misc::
31e0: 2a 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 *..namespace imp
31f0: 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a ort ::vc::tools:
3200: 3a 6c 6f 67 0a 09 6e 61 6d 65 73 70 61 63 65 20 :log..namespace
3210: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
3220: 6c 73 3a 3a 74 72 6f 75 62 6c 65 0a 09 6e 61 6d ls::trouble..nam
3230: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3240: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 64 6f 74 0a 09 vc::tools::dot..
3250: 6c 6f 67 20 72 65 67 69 73 74 65 72 20 63 79 63 log register cyc
3260: 6c 65 62 72 65 61 6b 65 72 0a 20 20 20 20 7d 0a lebreaker. }.
3270: 7d 0a 0a 23 20 23 20 23 23 20 23 23 23 20 23 23 }..# # ## ### ##
3280: 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 ### ######## ###
3290: 23 23 23 23 23 23 23 23 23 23 20 23 23 23 23 23 ########## #####
32a0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 ################
32b0: 0a 23 23 20 52 65 61 64 79 0a 0a 70 61 63 6b 61 .## Ready..packa
32c0: 67 65 20 70 72 6f 76 69 64 65 20 76 63 3a 3a 66 ge provide vc::f
32d0: 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 ossil::import::c
32e0: 76 73 3a 3a 63 79 63 6c 65 62 72 65 61 6b 65 72 vs::cyclebreaker
32f0: 20 31 2e 30 0a 72 65 74 75 72 6e 0a 1.0.return.