Artifact 0fd2ab8302d759ce79baa4391f6e7424e43cb4e8:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[ad7d5c2d10]
- Reworked the cycle breaker internals, moving the code handling the replacement of a changset (= node) with its fragments into a separate command. Extended the API, exposing the replacement operation, for use by passes. Added debugging code showing the set of consumable nodes for each iteration.
by
aku on
2007-11-22 03:03:44.
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 09 53 68 6f 77 50 65 cr myat...ShowPe
0ce0: 6e 64 69 6e 67 4e 6f 64 65 73 0a 09 20 20 20 20 ndingNodes..
0cf0: 7d 0a 0a 09 20 20 20 20 69 66 20 7b 21 5b 6c 6c }... if {![ll
0d00: 65 6e 67 74 68 20 5b 64 67 20 6e 6f 64 65 73 5d ength [dg nodes]
0d10: 5d 7d 20 62 72 65 61 6b 0a 0a 09 20 20 20 20 42 ]} break... B
0d20: 72 65 61 6b 43 79 63 6c 65 48 6f 6f 6b 20 20 20 reakCycleHook
0d30: 20 20 20 20 24 64 67 0a 09 20 20 20 20 49 6e 69 $dg.. Ini
0d40: 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 tializeCandidate
0d50: 73 20 24 64 67 0a 09 7d 0a 0a 09 24 64 67 20 64 s $dg..}...$dg d
0d60: 65 73 74 72 6f 79 0a 0a 09 6c 6f 67 20 77 72 69 estroy...log wri
0d70: 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 te 3 cyclebreake
0d80: 72 20 44 6f 6e 65 2e 0a 09 43 6c 65 61 72 48 6f r Done...ClearHo
0d90: 6f 6b 73 0a 0a 09 23 20 52 65 72 65 61 64 20 74 oks...# Reread t
0da0: 68 65 20 67 72 61 70 68 20 61 6e 64 20 64 75 6d he graph and dum
0db0: 70 20 69 74 73 20 66 69 6e 61 6c 20 66 6f 72 6d p its final form
0dc0: 2c 20 69 66 20 67 72 61 70 68 20 65 78 70 6f 72 , if graph expor
0dd0: 74 0a 09 23 20 77 61 73 20 61 63 74 69 76 61 74 t..# was activat
0de0: 65 64 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 ed....::variable
0df0: 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f mydotdestinatio
0e00: 6e 0a 09 69 66 20 7b 24 6d 79 64 6f 74 64 65 73 n..if {$mydotdes
0e10: 74 69 6e 61 74 69 6f 6e 20 65 71 20 22 22 7d 20 tination eq ""}
0e20: 72 65 74 75 72 6e 0a 0a 09 73 65 74 20 20 20 64 return...set d
0e30: 67 20 5b 53 65 74 75 70 20 5b 75 70 6c 65 76 65 g [Setup [upleve
0e40: 6c 20 23 30 20 24 63 68 61 6e 67 65 73 65 74 63 l #0 $changesetc
0e50: 6d 64 5d 20 30 5d 0a 09 4d 61 72 6b 20 24 64 67 md] 0]..Mark $dg
0e60: 20 2d 64 6f 6e 65 0a 09 24 64 67 20 64 65 73 74 -done..$dg dest
0e70: 72 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 roy..return.
0e80: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 }.. # # ## ##
0e90: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 # ##### ########
0ea0: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a #############..
0eb0: 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 62 typemethod b
0ec0: 72 65 61 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 reak {graph} {..
0ed0: 42 72 65 61 6b 43 79 63 6c 65 20 24 67 72 61 70 BreakCycle $grap
0ee0: 68 20 5b 46 69 6e 64 43 79 63 6c 65 20 24 67 72 h [FindCycle $gr
0ef0: 61 70 68 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 aph]..return.
0f00: 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 }.. typemeth
0f10: 6f 64 20 72 65 70 6c 61 63 65 20 7b 67 72 61 70 od replace {grap
0f20: 68 20 6e 20 72 65 70 6c 61 63 65 6d 65 6e 74 73 h n replacements
0f30: 7d 20 7b 0a 09 52 65 70 6c 61 63 65 20 24 67 72 } {..Replace $gr
0f40: 61 70 68 20 24 6e 20 24 72 65 70 6c 61 63 65 6d aph $n $replacem
0f50: 65 6e 74 73 0a 09 72 65 74 75 72 6e 0a 20 20 20 ents..return.
0f60: 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 }.. # # ## #
0f70: 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 ## ##### #######
0f80: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a # #############.
0f90: 20 20 20 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 ## Internal
0fa0: 6d 65 74 68 6f 64 73 0a 0a 20 20 20 20 70 72 6f methods.. pro
0fb0: 63 20 53 65 74 75 70 20 7b 63 68 61 6e 67 65 73 c Setup {changes
0fc0: 65 74 73 20 7b 6c 6f 67 20 31 7d 7d 20 7b 0a 09 ets {log 1}} {..
0fd0: 69 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 if {$log} {..
0fe0: 20 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 log write 3 cyc
0ff0: 6c 65 62 72 65 61 6b 65 72 20 22 43 72 65 61 74 lebreaker "Creat
1000: 69 6e 67 20 63 68 61 6e 67 65 73 65 74 20 67 72 ing changeset gr
1010: 61 70 68 2c 20 66 69 6c 6c 69 6e 67 20 77 69 74 aph, filling wit
1020: 68 20 6e 6f 64 65 73 22 0a 09 20 20 20 20 6c 6f h nodes".. lo
1030: 67 20 77 72 69 74 65 20 33 20 63 79 63 6c 65 62 g write 3 cycleb
1040: 72 65 61 6b 65 72 20 22 41 64 64 69 6e 67 20 5b reaker "Adding [
1050: 6e 73 70 20 5b 6c 6c 65 6e 67 74 68 20 24 63 68 nsp [llength $ch
1060: 61 6e 67 65 73 65 74 73 5d 20 6e 6f 64 65 5d 22 angesets] node]"
1070: 0a 09 7d 0a 0a 09 73 65 74 20 64 67 20 5b 73 74 ..}...set dg [st
1080: 72 75 63 74 3a 3a 67 72 61 70 68 20 64 67 5d 0a ruct::graph dg].
1090: 0a 09 66 6f 72 65 61 63 68 20 63 73 65 74 20 24 ..foreach cset $
10a0: 63 68 61 6e 67 65 73 65 74 73 20 7b 0a 09 20 20 changesets {..
10b0: 20 20 24 64 67 20 6e 6f 64 65 20 69 6e 73 65 72 $dg node inser
10c0: 74 20 24 63 73 65 74 0a 09 20 20 20 20 24 64 67 t $cset.. $dg
10d0: 20 6e 6f 64 65 20 73 65 74 20 20 20 20 24 63 73 node set $cs
10e0: 65 74 20 74 69 6d 65 72 61 6e 67 65 20 5b 24 63 et timerange [$c
10f0: 73 65 74 20 74 69 6d 65 72 61 6e 67 65 5d 0a 09 set timerange]..
1100: 7d 0a 0a 09 23 20 32 2e 20 46 69 6e 64 20 66 6f }...# 2. Find fo
1110: 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 r all relevant c
1120: 68 61 6e 67 65 73 65 74 20 74 68 65 69 72 20 72 hangeset their r
1130: 65 76 69 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 evisions and the
1140: 69 72 0a 09 23 20 20 20 20 64 65 70 65 6e 64 65 ir..# depende
1150: 6e 63 69 65 73 2e 20 4d 61 70 20 74 68 65 20 6c ncies. Map the l
1160: 61 74 74 65 72 20 62 61 63 6b 20 74 6f 20 63 68 atter back to ch
1170: 61 6e 67 65 73 65 74 73 20 61 6e 64 0a 09 23 20 angesets and..#
1180: 20 20 20 63 6f 6e 73 74 72 75 63 74 20 74 68 65 construct the
1190: 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 corresponding a
11a0: 72 63 73 2e 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d rcs....if {$log}
11b0: 20 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 {.. log writ
11c0: 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 e 3 cyclebreaker
11d0: 20 7b 53 65 74 74 69 6e 67 20 75 70 20 6e 6f 64 {Setting up nod
11e0: 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 7d 0a e dependencies}.
11f0: 09 7d 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 .}...foreach cse
1200: 74 20 24 63 68 61 6e 67 65 73 65 74 73 20 7b 0a t $changesets {.
1210: 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 . foreach suc
1220: 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 c [$cset success
1230: 6f 72 73 5d 20 7b 0a 09 09 23 20 43 68 61 6e 67 ors] {...# Chang
1240: 65 73 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 esets may have d
1250: 65 70 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 ependencies outs
1260: 69 64 65 20 6f 66 20 74 68 65 0a 09 09 23 20 63 ide of the...# c
1270: 68 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 hosen set. These
1280: 20 61 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 are ignored...i
1290: 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 f {![$dg node ex
12a0: 69 73 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e ists $succ]} con
12b0: 74 69 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 tinue...$dg arc
12c0: 69 6e 73 65 72 74 20 24 63 73 65 74 20 24 73 75 insert $cset $su
12d0: 63 63 0a 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 23 cc.. }..}...#
12e0: 20 52 75 6e 20 74 68 65 20 75 73 65 72 20 68 6f Run the user ho
12f0: 6f 6b 20 74 6f 20 6d 61 6e 69 70 75 6c 61 74 65 ok to manipulate
1300: 20 74 68 65 20 67 72 61 70 68 20 62 65 66 6f 72 the graph befor
1310: 65 0a 09 23 20 63 6f 6e 73 75 6d 6d 61 74 69 6f e..# consummatio
1320: 6e 2e 0a 0a 09 69 66 20 7b 24 6c 6f 67 7d 20 7b n....if {$log} {
1330: 20 4d 61 72 6b 20 24 64 67 20 2d 73 74 61 72 74 Mark $dg -start
1340: 20 7d 0a 09 50 72 65 48 6f 6f 6b 20 24 64 67 0a }..PreHook $dg.
1350: 09 72 65 74 75 72 6e 20 20 24 64 67 0a 20 20 20 .return $dg.
1360: 20 7d 0a 0a 20 20 20 20 23 20 49 6e 73 74 65 61 }.. # Instea
1370: 64 20 6f 66 20 73 65 61 72 63 68 69 6e 67 20 74 d of searching t
1380: 68 65 20 77 68 6f 6c 65 20 67 72 61 70 68 20 66 he whole graph f
1390: 6f 72 20 74 68 65 20 64 65 67 72 65 65 2d 30 20 or the degree-0
13a0: 6e 6f 64 65 73 20 69 6e 0a 20 20 20 20 23 20 65 nodes in. # e
13b0: 61 63 68 20 69 74 65 72 61 74 69 6f 6e 20 77 65 ach iteration we
13c0: 20 63 6f 6d 70 75 74 65 20 74 68 65 20 6c 69 73 compute the lis
13d0: 74 20 6f 6e 63 65 20 74 6f 20 73 74 61 72 74 2c t once to start,
13e0: 20 61 6e 64 20 74 68 65 6e 20 6f 6e 6c 79 0a 20 and then only.
13f0: 20 20 20 23 20 75 70 64 61 74 65 20 69 74 20 69 # update it i
1400: 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 20 62 61 73 ncrementally bas
1410: 65 64 20 6f 6e 20 74 68 65 20 6f 75 74 67 6f 69 ed on the outgoi
1420: 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 ng neighbours of
1430: 20 74 68 65 0a 20 20 20 20 23 20 6e 6f 64 65 20 the. # node
1440: 63 68 6f 73 65 6e 20 66 6f 72 20 63 6f 6d 6d 69 chosen for commi
1450: 74 2e 0a 0a 20 20 20 20 70 72 6f 63 20 49 6e 69 t... proc Ini
1460: 74 69 61 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 tializeCandidate
1470: 73 20 7b 64 67 7d 20 7b 0a 09 23 20 62 6f 74 74 s {dg} {..# bott
1480: 6f 6d 20 3d 20 6c 69 73 74 20 28 6c 69 73 74 20 om = list (list
1490: 28 6e 6f 64 65 2c 20 72 61 6e 67 65 20 6d 69 6e (node, range min
14a0: 2c 20 72 61 6e 67 65 20 6d 61 78 29 29 0a 09 3a , range max))..:
14b0: 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 :variable mybott
14c0: 6f 6d 0a 09 66 6f 72 65 61 63 68 20 6e 20 5b 24 om..foreach n [$
14d0: 64 67 20 6e 6f 64 65 73 5d 20 7b 0a 09 20 20 20 dg nodes] {..
14e0: 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 if {[$dg node d
14f0: 65 67 72 65 65 20 2d 69 6e 20 24 6e 5d 7d 20 63 egree -in $n]} c
1500: 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c 61 70 ontinue.. lap
1510: 70 65 6e 64 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c pend mybottom [l
1520: 69 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f 64 65 insert [$dg node
1530: 20 67 65 74 20 24 6e 20 74 69 6d 65 72 61 6e 67 get $n timerang
1540: 65 5d 20 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74 e] 0 $n]..}..set
1550: 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 mybottom [lsort
1560: 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 -index 1 -integ
1570: 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 er [lsort -index
1580: 20 32 20 2d 69 6e 74 65 67 65 72 20 24 6d 79 62 2 -integer $myb
1590: 6f 74 74 6f 6d 5d 5d 0a 09 53 68 6f 77 50 65 6e ottom]]..ShowPen
15a0: 64 69 6e 67 4e 6f 64 65 73 0a 09 72 65 74 75 72 dingNodes..retur
15b0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
15c0: 63 20 57 69 74 68 6f 75 74 50 72 65 64 65 63 65 c WithoutPredece
15d0: 73 73 6f 72 20 7b 64 67 20 6e 76 7d 20 7b 0a 09 ssor {dg nv} {..
15e0: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 ::variable mybot
15f0: 74 6f 6d 0a 0a 09 75 70 76 61 72 20 31 20 24 6e tom...upvar 1 $n
1600: 76 20 6e 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e 67 v n..if {![lleng
1610: 74 68 20 24 6d 79 62 6f 74 74 6f 6d 5d 7d 20 7b th $mybottom]} {
1620: 20 72 65 74 75 72 6e 20 30 20 7d 0a 0a 09 73 65 return 0 }...se
1630: 74 20 6e 20 5b 6c 69 6e 64 65 78 20 5b 6c 69 6e t n [lindex [lin
1640: 64 65 78 20 24 6d 79 62 6f 74 74 6f 6d 20 30 5d dex $mybottom 0]
1650: 20 30 5d 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 0]..set mybotto
1660: 6d 20 5b 6c 72 61 6e 67 65 20 24 6d 79 62 6f 74 m [lrange $mybot
1670: 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 65 74 20 tom 1 end]..set
1680: 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 20 55 70 changed 0...# Up
1690: 64 61 74 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64 date list of nod
16a0: 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 es without prede
16b0: 63 65 73 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e cessor, based on
16c0: 20 74 68 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67 the..# outgoing
16d0: 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74 neighbours of t
16e0: 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20 he chosen node.
16f0: 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 0a 09 This should be..
1700: 23 20 66 61 73 74 65 72 20 74 68 61 6e 20 69 74 # faster than it
1710: 65 72 61 74 69 6e 67 20 6f 66 20 74 68 65 20 77 erating of the w
1720: 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e 6f 64 65 hole set of node
1730: 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09 s, finding all..
1740: 23 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 63 # without predec
1750: 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20 essors, sorting
1760: 74 68 65 6d 20 62 79 20 74 69 6d 65 2c 20 65 74 them by time, et
1770: 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 63 68 20 c. pp...foreach
1780: 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d out [$dg nodes -
1790: 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69 out $n] {.. i
17a0: 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67 f {[$dg node deg
17b0: 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20 ree -in $out] >
17c0: 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 1} continue..
17d0: 20 23 20 44 65 67 72 65 65 2d 31 20 6e 65 69 67 # Degree-1 neig
17e0: 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 61 76 65 hbour, will have
17f0: 20 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 73 no predecessors
1800: 20 61 66 74 65 72 20 74 68 65 0a 09 20 20 20 20 after the..
1810: 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20 # removal of n.
1820: 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e Put on the list.
1830: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 6d 79 .. lappend my
1840: 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 bottom [linsert
1850: 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6f [$dg node get $o
1860: 75 74 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 ut timerange] 0
1870: 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 74 20 63 $out].. set c
1880: 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 hanged 1..}..if
1890: 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 {$changed} {..
18a0: 20 20 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b set mybottom [
18b0: 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d lsort -index 1 -
18c0: 69 6e 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d integer [lsort -
18d0: 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 67 65 72 index 2 -integer
18e0: 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d 0a 09 7d 0a $mybottom]]..}.
18f0: 0a 09 23 20 57 65 20 64 6f 20 6e 6f 74 20 64 65 ..# We do not de
1900: 6c 65 74 65 20 74 68 65 20 6e 6f 64 65 20 69 6d lete the node im
1910: 6d 65 64 69 61 74 65 6c 79 2c 20 74 6f 20 61 6c mediately, to al
1920: 6c 6f 77 20 74 68 65 20 53 61 76 65 0a 09 23 20 low the Save..#
1930: 70 72 6f 63 65 64 75 72 65 20 74 6f 20 73 61 76 procedure to sav
1940: 65 20 74 68 65 20 64 65 70 65 6e 64 65 6e 63 69 e the dependenci
1950: 65 73 20 61 73 20 77 65 6c 6c 20 28 65 6e 63 6f es as well (enco
1960: 64 65 64 20 69 6e 20 74 68 65 0a 09 23 20 61 72 ded in the..# ar
1970: 63 73 29 2e 0a 09 72 65 74 75 72 6e 20 31 0a 20 cs)...return 1.
1980: 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 53 }.. proc S
1990: 68 6f 77 50 65 6e 64 69 6e 67 4e 6f 64 65 73 20 howPendingNodes
19a0: 7b 7d 20 7b 0a 09 69 66 20 7b 5b 6c 6f 67 20 76 {} {..if {[log v
19b0: 65 72 62 6f 73 69 74 79 3f 5d 20 3c 20 31 30 7d erbosity?] < 10}
19c0: 20 72 65 74 75 72 6e 0a 09 3a 3a 76 61 72 69 61 return..::varia
19d0: 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 0a 09 6c 6f ble mybottom..lo
19e0: 67 20 77 72 69 74 65 20 31 30 20 63 79 63 6c 65 g write 10 cycle
19f0: 62 72 65 61 6b 65 72 20 5c 0a 09 20 20 20 20 22 breaker \.. "
1a00: 50 65 6e 64 69 6e 67 3a 20 5b 73 74 72 75 63 74 Pending: [struct
1a10: 3a 3a 6c 69 73 74 20 6d 61 70 20 24 6d 79 62 6f ::list map $mybo
1a20: 74 74 6f 6d 20 5b 6d 79 70 72 6f 63 20 46 6f 72 ttom [myproc For
1a30: 6d 61 74 50 65 6e 64 69 6e 67 49 74 65 6d 5d 5d matPendingItem]]
1a40: 22 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a "..return. }.
1a50: 0a 20 20 20 20 70 72 6f 63 20 46 6f 72 6d 61 74 . proc Format
1a60: 50 65 6e 64 69 6e 67 49 74 65 6d 20 7b 69 74 65 PendingItem {ite
1a70: 6d 7d 20 7b 20 6c 72 65 70 6c 61 63 65 20 24 69 m} { lreplace $i
1a80: 74 65 6d 20 30 20 30 20 3c 5b 5b 6c 69 6e 64 65 tem 0 0 <[[linde
1a90: 78 20 24 69 74 65 6d 20 30 5d 20 69 64 5d 3e 20 x $item 0] id]>
1aa0: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 46 69 6e 64 }.. proc Find
1ab0: 43 79 63 6c 65 20 7b 64 67 7d 20 7b 0a 09 23 20 Cycle {dg} {..#
1ac0: 54 68 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 This procedure i
1ad0: 73 20 72 75 6e 20 69 66 20 61 6e 64 20 6f 6e 6c s run if and onl
1ae0: 79 20 74 68 65 20 67 72 61 70 68 20 69 73 20 6e y the graph is n
1af0: 6f 74 20 65 6d 70 74 79 20 61 6e 64 0a 09 23 20 ot empty and..#
1b00: 61 6c 6c 20 6e 6f 64 65 73 20 68 61 76 65 20 70 all nodes have p
1b10: 72 65 64 65 63 65 73 73 6f 72 73 2e 20 54 68 69 redecessors. Thi
1b20: 73 20 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 s means that eac
1b30: 68 20 6e 6f 64 65 20 69 73 0a 09 23 20 65 69 74 h node is..# eit
1b40: 68 65 72 20 70 61 72 74 20 6f 66 20 61 20 63 79 her part of a cy
1b50: 63 6c 65 20 6f 72 20 28 69 6e 64 69 72 65 63 74 cle or (indirect
1b60: 6c 79 29 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e ly) depending on
1b70: 20 61 20 6e 6f 64 65 0a 09 23 20 69 6e 20 61 20 a node..# in a
1b80: 63 79 63 6c 65 2e 20 57 65 20 63 61 6e 20 73 74 cycle. We can st
1b90: 61 72 74 20 61 74 20 61 6e 20 61 72 62 69 74 72 art at an arbitr
1ba0: 61 72 79 20 6e 6f 64 65 2c 20 66 6f 6c 6c 6f 77 ary node, follow
1bb0: 20 69 74 73 0a 09 23 20 69 6e 63 6f 6d 69 6e 67 its..# incoming
1bc0: 20 65 64 67 65 73 20 74 6f 20 69 74 73 20 70 72 edges to its pr
1bd0: 65 64 65 63 65 73 73 6f 72 73 20 75 6e 74 69 6c edecessors until
1be0: 20 77 65 20 73 65 65 20 61 20 6e 6f 64 65 20 61 we see a node a
1bf0: 0a 09 23 20 73 65 63 6f 6e 64 20 74 69 6d 65 2e ..# second time.
1c00: 20 54 68 61 74 20 6e 6f 64 65 20 63 6c 6f 73 65 That node close
1c10: 73 20 74 68 65 20 63 79 63 6c 65 20 61 6e 64 20 s the cycle and
1c20: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 69 73 the beginning is
1c30: 0a 09 23 20 69 74 73 20 66 69 72 73 74 20 6f 63 ..# its first oc
1c40: 63 75 72 65 6e 63 65 2e 20 4e 6f 74 65 20 74 68 curence. Note th
1c50: 61 74 20 77 65 20 63 61 6e 20 63 68 6f 6f 73 65 at we can choose
1c60: 20 61 6e 20 61 72 62 69 74 72 61 72 79 0a 09 23 an arbitrary..#
1c70: 20 70 72 65 64 65 63 65 73 73 6f 72 20 6f 66 20 predecessor of
1c80: 65 61 63 68 20 6e 6f 64 65 20 61 73 20 77 65 6c each node as wel
1c90: 6c 2c 20 77 65 20 64 6f 20 6e 6f 74 20 68 61 76 l, we do not hav
1ca0: 65 20 74 6f 20 73 65 61 72 63 68 2e 0a 0a 09 23 e to search....#
1cb0: 20 57 65 20 72 65 63 6f 72 64 20 66 6f 72 20 65 We record for e
1cc0: 61 63 68 20 6e 6f 64 65 20 74 68 65 20 69 6e 64 ach node the ind
1cd0: 65 78 20 6f 66 20 74 68 65 20 66 69 72 73 74 20 ex of the first
1ce0: 61 70 70 65 61 72 61 6e 63 65 20 69 6e 0a 09 23 appearance in..#
1cf0: 20 74 68 65 20 70 61 74 68 2c 20 6d 61 6b 69 6e the path, makin
1d00: 67 20 69 74 20 65 61 73 79 20 61 74 20 74 68 65 g it easy at the
1d10: 20 65 6e 64 20 74 6f 20 63 75 74 20 74 68 65 20 end to cut the
1d20: 63 79 63 6c 65 20 66 72 6f 6d 0a 09 23 20 69 74 cycle from..# it
1d30: 2e 0a 0a 09 23 20 43 68 6f 6f 73 65 20 61 72 62 ....# Choose arb
1d40: 69 74 72 61 72 79 20 6e 6f 64 65 20 74 6f 20 73 itrary node to s
1d50: 74 61 72 74 20 6f 75 72 20 73 65 61 72 63 68 20 tart our search
1d60: 61 74 2e 0a 09 73 65 74 20 73 74 61 72 74 20 5b at...set start [
1d70: 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 lindex [$dg node
1d80: 73 5d 20 30 5d 0a 0a 09 23 20 49 6e 69 74 69 61 s] 0]...# Initia
1d90: 6c 69 7a 65 20 73 74 61 74 65 2c 20 70 61 74 68 lize state, path
1da0: 20 6f 66 20 73 65 65 6e 20 6e 6f 64 65 73 2c 20 of seen nodes,
1db0: 61 6e 64 20 77 68 65 6e 20 73 65 65 6e 2e 0a 09 and when seen...
1dc0: 73 65 74 20 20 20 20 20 20 20 70 61 74 68 20 7b set path {
1dd0: 7d 0a 09 61 72 72 61 79 20 73 65 74 20 73 65 65 }..array set see
1de0: 6e 20 7b 7d 0a 0a 09 77 68 69 6c 65 20 7b 31 7d n {}...while {1}
1df0: 20 7b 0a 09 20 20 20 20 23 20 53 74 6f 70 20 73 {.. # Stop s
1e00: 65 61 72 63 68 69 6e 67 20 77 68 65 6e 20 77 65 earching when we
1e10: 20 68 61 76 65 20 73 65 65 6e 20 74 68 65 20 63 have seen the c
1e20: 75 72 72 65 6e 74 20 6e 6f 64 65 0a 09 20 20 20 urrent node..
1e30: 20 23 20 61 6c 72 65 61 64 79 2c 20 74 68 65 20 # already, the
1e40: 63 69 72 63 6c 65 20 68 61 73 20 62 65 65 6e 20 circle has been
1e50: 63 6c 6f 73 65 64 2e 0a 09 20 20 20 20 69 66 20 closed... if
1e60: 7b 5b 69 6e 66 6f 20 65 78 69 73 74 73 20 73 65 {[info exists se
1e70: 65 6e 28 24 73 74 61 72 74 29 5d 7d 20 62 72 65 en($start)]} bre
1e80: 61 6b 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 ak.. lappend
1e90: 70 61 74 68 20 24 73 74 61 72 74 0a 09 20 20 20 path $start..
1ea0: 20 73 65 74 20 73 65 65 6e 28 24 73 74 61 72 74 set seen($start
1eb0: 29 20 5b 65 78 70 72 20 7b 5b 6c 6c 65 6e 67 74 ) [expr {[llengt
1ec0: 68 20 24 70 61 74 68 5d 2d 31 7d 5d 0a 09 20 20 h $path]-1}]..
1ed0: 20 20 23 20 43 68 6f 6f 73 65 20 61 72 62 69 74 # Choose arbit
1ee0: 72 61 72 79 20 70 72 65 64 65 63 65 73 73 6f 72 rary predecessor
1ef0: 0a 09 20 20 20 20 73 65 74 20 73 74 61 72 74 20 .. set start
1f00: 5b 6c 69 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 [lindex [$dg nod
1f10: 65 73 20 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 es -in $start] 0
1f20: 5d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 ]..}...return [s
1f30: 74 72 75 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 truct::list reve
1f40: 72 73 65 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 rse [lrange $pat
1f50: 68 20 24 73 65 65 6e 28 24 73 74 61 72 74 29 20 h $seen($start)
1f60: 65 6e 64 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 end]]. }..
1f70: 20 70 72 6f 63 20 49 44 20 7b 63 73 65 74 7d 20 proc ID {cset}
1f80: 7b 20 72 65 74 75 72 6e 20 22 3c 5b 24 63 73 65 { return "<[$cse
1f90: 74 20 69 64 5d 3e 22 20 7d 0a 0a 20 20 20 20 70 t id]>" }.. p
1fa0: 72 6f 63 20 42 72 65 61 6b 43 79 63 6c 65 20 7b roc BreakCycle {
1fb0: 64 67 20 63 79 63 6c 65 7d 20 7b 0a 09 23 20 54 dg cycle} {..# T
1fc0: 68 65 20 63 79 63 6c 65 20 77 65 20 68 61 76 65 he cycle we have
1fd0: 20 67 6f 74 74 65 6e 20 69 73 20 62 72 6f 6b 65 gotten is broke
1fe0: 6e 20 62 79 20 62 72 65 61 6b 69 6e 67 20 61 70 n by breaking ap
1ff0: 61 72 74 20 6f 6e 65 20 6f 72 0a 09 23 20 6d 6f art one or..# mo
2000: 72 65 20 6f 66 20 74 68 65 20 63 68 61 6e 67 65 re of the change
2010: 73 65 74 73 20 69 6e 20 74 68 65 20 63 79 63 6c sets in the cycl
2020: 65 2e 20 54 68 69 73 20 63 61 75 73 65 73 20 75 e. This causes u
2030: 73 20 74 6f 0a 09 23 20 63 72 65 61 74 65 20 6f s to..# create o
2040: 6e 65 20 6f 72 20 6d 6f 72 65 20 63 68 61 6e 67 ne or more chang
2050: 65 73 65 74 73 20 77 68 69 63 68 20 61 72 65 20 esets which are
2060: 74 6f 20 62 65 20 63 6f 6d 6d 69 74 74 65 64 2c to be committed,
2070: 0a 09 23 20 61 64 64 65 64 20 74 6f 20 74 68 65 ..# added to the
2080: 20 67 72 61 70 68 2c 20 65 74 63 2e 20 70 70 2e graph, etc. pp.
2090: 0a 0a 09 73 65 74 20 63 70 72 69 6e 74 20 5b 6a ...set cprint [j
20a0: 6f 69 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 oin [struct::lis
20b0: 74 20 6d 61 70 20 24 63 79 63 6c 65 20 5b 6d 79 t map $cycle [my
20c0: 70 72 6f 63 20 49 44 5d 5d 20 7b 20 7d 5d 0a 0a proc ID]] { }]..
20d0: 09 6c 61 70 70 65 6e 64 20 63 79 63 6c 65 20 5b .lappend cycle [
20e0: 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 30 5d lindex $cycle 0]
20f0: 20 5b 6c 69 6e 64 65 78 20 24 63 79 63 6c 65 20 [lindex $cycle
2100: 31 5d 0a 09 73 65 74 20 62 65 73 74 6c 69 6e 6b 1]..set bestlink
2110: 20 7b 7d 0a 09 73 65 74 20 62 65 73 74 6e 6f 64 {}..set bestnod
2120: 65 20 7b 7d 0a 0a 09 66 6f 72 65 61 63 68 20 5c e {}...foreach \
2130: 0a 09 20 20 20 20 70 72 65 76 20 5b 6c 72 61 6e .. prev [lran
2140: 67 65 20 24 63 79 63 6c 65 20 30 20 65 6e 64 2d ge $cycle 0 end-
2150: 32 5d 20 5c 0a 09 20 20 20 20 63 73 65 74 20 5b 2] \.. cset [
2160: 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 31 20 lrange $cycle 1
2170: 65 6e 64 2d 31 5d 20 5c 0a 09 20 20 20 20 6e 65 end-1] \.. ne
2180: 78 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c xt [lrange $cycl
2190: 65 20 32 20 65 6e 64 5d 20 7b 0a 0a 09 09 23 20 e 2 end] {....#
21a0: 45 61 63 68 20 74 72 69 70 6c 65 20 50 52 45 56 Each triple PREV
21b0: 20 2d 3e 20 43 53 45 54 20 2d 3e 20 4e 45 58 54 -> CSET -> NEXT
21c0: 20 6f 66 20 63 68 61 6e 67 65 73 65 74 73 2c 20 of changesets,
21d0: 61 0a 09 09 23 20 27 6c 69 6e 6b 27 20 69 6e 20 a...# 'link' in
21e0: 74 68 65 20 63 79 63 6c 65 2c 20 69 73 20 61 6e the cycle, is an
21f0: 61 6c 79 73 65 64 20 61 6e 64 20 74 68 65 20 62 alysed and the b
2200: 65 73 74 0a 09 09 23 20 6c 6f 63 61 74 69 6f 6e est...# location
2210: 20 77 68 65 72 65 20 74 6f 20 61 74 20 6c 65 61 where to at lea
2220: 73 74 20 77 65 61 6b 65 6e 20 74 68 65 20 63 79 st weaken the cy
2230: 63 6c 65 20 69 73 0a 09 09 23 20 63 68 6f 73 65 cle is...# chose
2240: 6e 20 66 6f 72 20 66 75 72 74 68 65 72 20 70 72 n for further pr
2250: 6f 63 65 73 73 69 6e 67 2e 0a 0a 09 09 73 65 74 ocessing.....set
2260: 20 6c 69 6e 6b 20 5b 70 72 6f 6a 65 63 74 3a 3a link [project::
2270: 72 65 76 6c 69 6e 6b 20 25 41 55 54 4f 25 20 24 revlink %AUTO% $
2280: 70 72 65 76 20 24 63 73 65 74 20 24 6e 65 78 74 prev $cset $next
2290: 5d 0a 09 09 69 66 20 7b 24 62 65 73 74 6c 69 6e ]...if {$bestlin
22a0: 6b 20 65 71 20 22 22 7d 20 7b 0a 09 09 20 20 20 k eq ""} {...
22b0: 20 73 65 74 20 62 65 73 74 6c 69 6e 6b 20 24 6c set bestlink $l
22c0: 69 6e 6b 0a 09 09 20 20 20 20 73 65 74 20 62 65 ink... set be
22d0: 73 74 6e 6f 64 65 20 24 63 73 65 74 0a 09 09 7d stnode $cset...}
22e0: 20 65 6c 73 65 69 66 20 7b 5b 24 6c 69 6e 6b 20 elseif {[$link
22f0: 62 65 74 74 65 72 74 68 61 6e 20 24 62 65 73 74 betterthan $best
2300: 6c 69 6e 6b 5d 7d 20 7b 0a 09 09 20 20 20 20 24 link]} {... $
2310: 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 bestlink destroy
2320: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6c ... set bestl
2330: 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 ink $link...
2340: 73 65 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 set bestnode $cs
2350: 65 74 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 et...} else {...
2360: 20 20 20 20 24 6c 69 6e 6b 20 64 65 73 74 72 6f $link destro
2370: 79 0a 09 09 7d 0a 09 20 20 20 20 7d 0a 0a 09 6c y...}.. }...l
2380: 6f 67 20 77 72 69 74 65 20 35 20 63 79 63 6c 65 og write 5 cycle
2390: 62 72 65 61 6b 65 72 20 22 42 72 65 61 6b 69 6e breaker "Breakin
23a0: 67 20 63 79 63 6c 65 20 28 24 63 70 72 69 6e 74 g cycle ($cprint
23b0: 29 20 62 79 20 73 70 6c 69 74 74 69 6e 67 20 63 ) by splitting c
23c0: 68 61 6e 67 65 73 65 74 20 3c 5b 24 62 65 73 74 hangeset <[$best
23d0: 6e 6f 64 65 20 69 64 5d 3e 22 0a 09 73 65 74 20 node id]>"..set
23e0: 49 44 20 5b 24 62 65 73 74 6e 6f 64 65 20 69 64 ID [$bestnode id
23f0: 5d 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 ]..Mark $dg -${I
2400: 44 7d 2d 62 65 66 6f 72 65 0a 0a 09 73 65 74 20 D}-before...set
2410: 6e 65 77 63 73 65 74 73 20 5b 24 62 65 73 74 6c newcsets [$bestl
2420: 69 6e 6b 20 62 72 65 61 6b 5d 0a 09 24 62 65 73 ink break]..$bes
2430: 74 6c 69 6e 6b 20 64 65 73 74 72 6f 79 0a 0a 20 tlink destroy..
2440: 20 20 20 20 20 20 20 23 20 41 74 20 74 68 69 73 # At this
2450: 20 70 6f 69 6e 74 20 74 68 65 20 6f 6c 64 20 63 point the old c
2460: 68 61 6e 67 65 73 65 74 20 28 42 45 53 54 4e 4f hangeset (BESTNO
2470: 44 45 29 20 69 73 20 67 6f 6e 65 0a 20 20 20 20 DE) is gone.
2480: 20 20 20 20 23 20 61 6c 72 65 61 64 79 2e 20 57 # already. W
2490: 65 20 72 65 6d 6f 76 65 20 69 74 20 66 72 6f 6d e remove it from
24a0: 20 74 68 65 20 67 72 61 70 68 20 61 73 20 77 65 the graph as we
24b0: 6c 6c 20 61 6e 64 20 74 68 65 6e 20 65 6e 74 65 ll and then ente
24c0: 72 0a 20 20 20 20 20 20 20 20 23 20 74 68 65 20 r. # the
24d0: 66 72 61 67 6d 65 6e 74 73 20 67 65 6e 65 72 61 fragments genera
24e0: 74 65 64 20 66 6f 72 20 69 74 2e 0a 0a 09 52 65 ted for it....Re
24f0: 70 6c 61 63 65 20 24 64 67 20 24 62 65 73 74 6e place $dg $bestn
2500: 6f 64 65 20 24 6e 65 77 63 73 65 74 73 0a 0a 09 ode $newcsets...
2510: 4d 61 72 6b 20 24 64 67 20 2d 24 7b 49 44 7d 2d Mark $dg -${ID}-
2520: 61 66 74 65 72 0a 09 72 65 74 75 72 6e 0a 20 20 after..return.
2530: 20 20 7d 0a 0a 20 20 20 20 23 20 54 4f 44 4f 3a }.. # TODO:
2540: 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 20 This should be
2550: 61 20 67 72 61 70 68 20 6d 65 74 68 6f 64 2e 0a a graph method..
2560: 20 20 20 20 70 72 6f 63 20 48 61 73 41 72 63 20 proc HasArc
2570: 7b 64 67 20 61 20 62 7d 20 7b 0a 09 23 38 2e 35 {dg a b} {..#8.5
2580: 3a 20 72 65 74 75 72 6e 20 5b 65 78 70 72 20 7b : return [expr {
2590: 24 62 20 69 6e 20 5b 24 64 67 20 6e 6f 64 65 73 $b in [$dg nodes
25a0: 20 2d 6f 75 74 20 24 61 5d 7d 5d 0a 09 69 66 20 -out $a]}]..if
25b0: 7b 5b 6c 73 65 61 72 63 68 20 2d 65 78 61 63 74 {[lsearch -exact
25c0: 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d 6f 75 74 [$dg nodes -out
25d0: 20 24 61 5d 20 24 62 5d 20 3c 20 30 7d 20 7b 20 $a] $b] < 0} {
25e0: 72 65 74 75 72 6e 20 30 20 7d 0a 09 72 65 74 75 return 0 }..retu
25f0: 72 6e 20 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 rn 1. }..
2600: 70 72 6f 63 20 4d 61 72 6b 20 7b 64 67 20 7b 73 proc Mark {dg {s
2610: 75 66 66 69 78 20 7b 7d 7d 7d 20 7b 0a 09 3a 3a uffix {}}} {..::
2620: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 variable mydotde
2630: 73 74 69 6e 61 74 69 6f 6e 0a 09 69 66 20 7b 24 stination..if {$
2640: 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e mydotdestination
2650: 20 65 71 20 22 22 7d 20 72 65 74 75 72 6e 0a 09 eq ""} return..
2660: 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 ::variable mydot
2670: 70 72 65 66 69 78 0a 09 3a 3a 76 61 72 69 61 62 prefix..::variab
2680: 6c 65 20 6d 79 64 6f 74 69 64 0a 09 73 65 74 20 le mydotid..set
2690: 66 6e 61 6d 65 20 24 6d 79 64 6f 74 64 65 73 74 fname $mydotdest
26a0: 69 6e 61 74 69 6f 6e 2f 24 7b 6d 79 64 6f 74 70 ination/${mydotp
26b0: 72 65 66 69 78 7d 24 7b 6d 79 64 6f 74 69 64 7d refix}${mydotid}
26c0: 24 7b 73 75 66 66 69 78 7d 2e 64 6f 74 0a 09 66 ${suffix}.dot..f
26d0: 69 6c 65 20 6d 6b 64 69 72 20 5b 66 69 6c 65 20 ile mkdir [file
26e0: 64 69 72 6e 61 6d 65 20 24 66 6e 61 6d 65 5d 0a dirname $fname].
26f0: 09 64 6f 74 20 77 72 69 74 65 20 24 64 67 20 24 .dot write $dg $
2700: 6d 79 64 6f 74 70 72 65 66 69 78 24 73 75 66 66 mydotprefix$suff
2710: 69 78 20 24 66 6e 61 6d 65 0a 09 69 6e 63 72 20 ix $fname..incr
2720: 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f 67 20 77 72 mydotid...log wr
2730: 69 74 65 20 35 20 63 79 63 6c 65 62 72 65 61 6b ite 5 cyclebreak
2740: 65 72 20 22 2e 64 6f 74 20 65 78 70 6f 72 74 20 er ".dot export
2750: 24 66 6e 61 6d 65 22 0a 09 72 65 74 75 72 6e 0a $fname"..return.
2760: 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 20 }.. proc
2770: 52 65 70 6c 61 63 65 20 7b 64 67 20 6e 20 72 65 Replace {dg n re
2780: 70 6c 61 63 65 6d 65 6e 74 73 7d 20 7b 0a 09 23 placements} {..#
2790: 20 4e 4f 54 45 2e 20 57 65 20 68 61 76 65 20 74 NOTE. We have t
27a0: 6f 20 67 65 74 20 74 68 65 20 6c 69 73 74 20 6f o get the list o
27b0: 66 20 69 6e 63 6f 6d 69 6e 67 20 6e 65 69 67 68 f incoming neigh
27c0: 62 6f 75 72 73 20 61 6e 64 0a 09 23 20 72 65 63 bours and..# rec
27d0: 6f 6d 70 75 74 65 20 74 68 65 69 72 20 73 75 63 ompute their suc
27e0: 63 65 73 73 6f 72 73 20 61 66 74 65 72 20 74 68 cessors after th
27f0: 65 20 6e 65 77 20 6e 6f 64 65 73 20 68 61 76 65 e new nodes have
2800: 20 62 65 65 6e 0a 09 23 20 69 6e 73 65 72 74 65 been..# inserte
2810: 64 2e 20 54 68 65 69 72 20 6f 75 74 67 6f 69 6e d. Their outgoin
2820: 67 20 61 72 63 73 20 77 69 6c 6c 20 6e 6f 77 20 g arcs will now
2830: 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 20 62 6f 74 go to one or bot
2840: 68 20 6f 66 0a 09 23 20 74 68 65 20 6e 65 77 20 h of..# the new
2850: 6e 6f 64 65 73 2c 20 61 6e 64 20 6e 6f 74 20 72 nodes, and not r
2860: 65 64 6f 69 6e 67 20 74 68 65 6d 20 6d 61 79 20 edoing them may
2870: 63 61 75 73 65 20 75 73 20 74 6f 20 66 6f 72 67 cause us to forg
2880: 65 74 0a 09 23 20 63 69 72 63 6c 65 73 2c 20 6c et..# circles, l
2890: 65 61 76 69 6e 67 20 74 68 65 6d 20 69 6e 2c 20 eaving them in,
28a0: 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 73 65 74 20 unbroken....set
28b0: 70 72 65 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d pre [$dg nodes -
28c0: 69 6e 20 24 6e 5d 0a 0a 20 20 20 20 20 20 20 20 in $n]..
28d0: 24 64 67 20 6e 6f 64 65 20 64 65 6c 65 74 65 20 $dg node delete
28e0: 24 6e 0a 0a 09 66 6f 72 65 61 63 68 20 63 73 65 $n...foreach cse
28f0: 74 20 24 72 65 70 6c 61 63 65 6d 65 6e 74 73 20 t $replacements
2900: 7b 0a 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 {.. $dg node
2910: 69 6e 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 insert $cset..
2920: 20 20 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 $dg node set
2930: 20 20 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 $cset timerang
2940: 65 20 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e e [$cset timeran
2950: 67 65 5d 0a 09 7d 0a 0a 09 66 6f 72 65 61 63 68 ge]..}...foreach
2960: 20 63 73 65 74 20 24 72 65 70 6c 61 63 65 6d 65 cset $replaceme
2970: 6e 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 nts {.. forea
2980: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73 ch succ [$cset s
2990: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 23 uccessors] {...#
29a0: 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 65 73 The new changes
29b0: 65 74 73 20 6d 61 79 20 68 61 76 65 20 64 65 70 ets may have dep
29c0: 65 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 endencies outsid
29d0: 65 20 6f 66 0a 09 09 23 20 74 68 65 20 63 68 6f e of...# the cho
29e0: 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 61 sen set. These a
29f0: 72 65 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 re ignored...if
2a00: 7b 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 {![$dg node exis
2a10: 74 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 ts $succ]} conti
2a20: 6e 75 65 0a 09 09 24 64 67 20 61 72 63 20 69 6e nue...$dg arc in
2a30: 73 65 72 74 20 24 63 73 65 74 20 24 73 75 63 63 sert $cset $succ
2a40: 0a 09 20 20 20 20 7d 0a 09 7d 0a 09 66 6f 72 65 .. }..}..fore
2a50: 61 63 68 20 63 73 65 74 20 24 70 72 65 20 7b 0a ach cset $pre {.
2a60: 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 . foreach suc
2a70: 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 c [$cset success
2a80: 6f 72 73 5d 20 7b 0a 09 09 23 20 4e 6f 74 65 20 ors] {...# Note
2a90: 74 68 61 74 20 74 68 65 20 61 72 63 20 6d 61 79 that the arc may
2aa0: 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 20 69 already exist i
2ab0: 6e 20 74 68 65 20 67 72 61 70 68 2e 20 49 66 0a n the graph. If.
2ac0: 09 09 23 20 73 6f 20 69 67 6e 6f 72 65 20 69 74 ..# so ignore it
2ad0: 2e 20 54 68 65 20 6e 65 77 20 63 68 61 6e 67 65 . The new change
2ae0: 73 65 74 73 20 6d 61 79 20 68 61 76 65 0a 09 09 sets may have...
2af0: 23 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 6f # dependencies o
2b00: 75 74 73 69 64 65 20 6f 66 20 74 68 65 20 63 68 utside of the ch
2b10: 6f 73 65 6e 20 73 65 74 2e 20 54 68 65 73 65 20 osen set. These
2b20: 61 72 65 0a 09 09 23 20 69 67 6e 6f 72 65 64 0a are...# ignored.
2b30: 09 09 69 66 20 7b 21 5b 24 64 67 20 6e 6f 64 65 ..if {![$dg node
2b40: 20 65 78 69 73 74 73 20 24 73 75 63 63 5d 7d 20 exists $succ]}
2b50: 63 6f 6e 74 69 6e 75 65 0a 09 09 69 66 20 7b 5b continue...if {[
2b60: 48 61 73 41 72 63 20 24 64 67 20 24 63 73 65 74 HasArc $dg $cset
2b70: 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 $succ]} continu
2b80: 65 3b 23 20 54 4f 44 4f 20 73 68 6f 75 6c 64 20 e;# TODO should
2b90: 62 65 20 67 72 61 70 68 20 6d 65 74 68 6f 64 2e be graph method.
2ba0: 0a 09 09 24 64 67 20 61 72 63 20 69 6e 73 65 72 ...$dg arc inser
2bb0: 74 20 24 63 73 65 74 20 24 73 75 63 63 0a 09 20 t $cset $succ..
2bc0: 20 20 20 7d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e }..}...return
2bd0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 . }.. # #
2be0: 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 ## ### ##### ###
2bf0: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 ##### ##########
2c00: 23 23 23 0a 20 20 20 20 23 23 20 43 61 6c 6c 62 ###. ## Callb
2c10: 61 63 6b 20 69 6e 76 6f 6b 61 74 69 6f 6e 20 2e ack invokation .
2c20: 2e 2e 0a 0a 20 20 20 20 70 72 6f 63 20 50 72 65 .... proc Pre
2c30: 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 7b 0a 09 Hook {graph} {..
2c40: 23 20 47 69 76 65 20 74 68 65 20 75 73 65 72 20 # Give the user
2c50: 6f 66 20 74 68 65 20 63 79 63 6c 65 20 62 72 65 of the cycle bre
2c60: 61 6b 65 72 20 74 68 65 20 6f 70 70 6f 72 74 75 aker the opportu
2c70: 6e 69 74 79 20 74 6f 20 77 6f 72 6b 0a 09 23 20 nity to work..#
2c80: 77 69 74 68 20 74 68 65 20 67 72 61 70 68 20 62 with the graph b
2c90: 65 74 77 65 65 6e 20 73 65 74 75 70 20 61 6e 64 etween setup and
2ca0: 20 63 6f 6e 73 75 6d 6d 61 74 69 6f 6e 2e 0a 0a consummation...
2cb0: 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 70 72 .::variable mypr
2cc0: 65 63 6d 64 0a 09 69 66 20 7b 21 5b 6c 6c 65 6e ecmd..if {![llen
2cd0: 67 74 68 20 24 6d 79 70 72 65 63 6d 64 5d 7d 20 gth $myprecmd]}
2ce0: 72 65 74 75 72 6e 0a 0a 09 75 70 6c 65 76 65 6c return...uplevel
2cf0: 20 23 30 20 5b 6c 69 6e 73 65 72 74 20 24 6d 79 #0 [linsert $my
2d00: 70 72 65 63 6d 64 20 65 6e 64 20 24 67 72 61 70 precmd end $grap
2d10: 68 5d 0a 09 4d 61 72 6b 20 24 67 72 61 70 68 20 h]..Mark $graph
2d20: 2d 70 72 65 2d 64 6f 6e 65 0a 09 72 65 74 75 72 -pre-done..retur
2d30: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f n. }.. pro
2d40: 63 20 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b 20 c ProcessedHook
2d50: 7b 63 73 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 {cset pos} {..#
2d60: 47 69 76 65 20 74 68 65 20 75 73 65 72 20 6f 66 Give the user of
2d70: 20 74 68 65 20 63 79 63 6c 65 20 62 72 65 61 6b the cycle break
2d80: 65 72 20 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 er the opportuni
2d90: 74 79 20 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 ty to work..# wi
2da0: 74 68 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 th the changeset
2db0: 20 62 65 66 6f 72 65 20 69 74 20 69 73 20 72 65 before it is re
2dc0: 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 67 moved from the g
2dd0: 72 61 70 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 raph....::variab
2de0: 6c 65 20 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 le mysavecmd..if
2df0: 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 {![llength $mys
2e00: 61 76 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a avecmd]} return.
2e10: 0a 09 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 ..uplevel #0 [li
2e20: 6e 73 65 72 74 20 24 6d 79 73 61 76 65 63 6d 64 nsert $mysavecmd
2e30: 20 65 6e 64 20 24 70 6f 73 20 24 63 73 65 74 5d end $pos $cset]
2e40: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
2e50: 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 79 proc BreakCy
2e60: 63 6c 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 cleHook {graph}
2e70: 7b 0a 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 6f {..# Call out to
2e80: 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 6f the chosen algo
2e90: 72 69 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 20 rithm for cycle
2ea0: 62 72 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 6e breaking. Findin
2eb0: 67 0a 09 23 20 61 20 63 79 63 6c 65 20 69 66 20 g..# a cycle if
2ec0: 6e 6f 20 62 72 65 61 6b 65 72 20 77 61 73 20 63 no breaker was c
2ed0: 68 6f 73 65 6e 20 69 73 20 61 6e 20 65 72 72 6f hosen is an erro
2ee0: 72 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 r....::variable
2ef0: 6d 79 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 7b mybreakcmd..if {
2f00: 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 65 ![llength $mybre
2f10: 61 6b 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 74 akcmd]} {.. t
2f20: 72 6f 75 62 6c 65 20 66 61 74 61 6c 20 22 46 6f rouble fatal "Fo
2f30: 75 6e 64 20 61 20 63 79 63 6c 65 2c 20 65 78 70 und a cycle, exp
2f40: 65 63 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 20 ecting none."..
2f50: 20 20 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 75 exit 1..}...u
2f60: 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 plevel #0 [linse
2f70: 72 74 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 65 rt $mybreakcmd e
2f80: 6e 64 20 24 67 72 61 70 68 5d 0a 09 72 65 74 75 nd $graph]..retu
2f90: 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 rn. }.. pr
2fa0: 6f 63 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b 7d oc ClearHooks {}
2fb0: 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d {..::variable m
2fc0: 79 70 72 65 63 6d 64 20 20 20 7b 7d 0a 09 3a 3a yprecmd {}..::
2fd0: 76 61 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 variable mysavec
2fe0: 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 72 69 61 62 md {}..::variab
2ff0: 6c 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 7b 7d le mybreakcmd {}
3000: 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a ..return. }..
3010: 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 23 # # ## ### #
3020: 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 23 #### ######## ##
3030: 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 20 ###########..
3040: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
3050: 61 74 20 20 20 20 20 20 30 20 3b 20 23 20 43 6f at 0 ; # Co
3060: 75 6e 74 65 72 20 66 6f 72 20 63 6f 6d 6d 69 74 unter for commit
3070: 20 69 64 73 20 66 6f 72 20 74 68 65 0a 09 09 09 ids for the....
3080: 20 20 20 20 20 20 20 23 20 63 68 61 6e 67 65 73 # changes
3090: 65 74 73 2e 0a 20 20 20 20 74 79 70 65 76 61 72 ets.. typevar
30a0: 69 61 62 6c 65 20 6d 79 62 6f 74 74 6f 6d 20 7b iable mybottom {
30b0: 7d 20 3b 20 23 20 4c 69 73 74 20 6f 66 20 74 68 } ; # List of th
30c0: 65 20 63 61 6e 64 69 64 61 74 65 20 6e 6f 64 65 e candidate node
30d0: 73 20 66 6f 72 0a 09 09 09 20 20 20 20 20 20 20 s for....
30e0: 23 20 63 6f 6d 6d 69 74 74 69 6e 67 2e 0a 0a 20 # committing...
30f0: 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 typevariable
3100: 6d 79 70 72 65 63 6d 64 20 20 20 7b 7d 20 3b 20 myprecmd {} ;
3110: 23 20 43 61 6c 6c 62 61 63 6b 2c 20 63 68 61 6e # Callback, chan
3120: 67 65 20 67 72 61 70 68 20 62 65 66 6f 72 65 20 ge graph before
3130: 77 61 6c 6b 2e 0a 20 20 20 20 74 79 70 65 76 61 walk.. typeva
3140: 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 riable mysavecmd
3150: 20 20 7b 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 {} ; # Callbac
3160: 6b 2c 20 66 6f 72 20 65 61 63 68 20 70 72 6f 63 k, for each proc
3170: 65 73 73 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 essed node..
3180: 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 62 typevariable myb
3190: 72 65 61 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 reakcmd {} ; # C
31a0: 61 6c 6c 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 allback, for eac
31b0: 68 20 66 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a h found cycle...
31c0: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
31d0: 20 6d 79 64 6f 74 64 65 73 74 69 6e 61 74 69 6f mydotdestinatio
31e0: 6e 20 7b 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 n {} ; # Destina
31f0: 74 69 6f 6e 20 64 69 72 65 63 74 6f 72 79 20 66 tion directory f
3200: 6f 72 20 74 68 65 0a 09 09 09 09 20 20 20 20 20 or the.....
3210: 20 20 23 20 67 65 6e 65 72 61 74 65 64 20 2e 64 # generated .d
3220: 6f 74 20 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 ot files.. ty
3230: 70 65 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 pevariable mydot
3240: 70 72 65 66 69 78 20 20 20 20 20 20 7b 7d 20 3b prefix {} ;
3250: 20 23 20 50 72 65 66 69 78 20 66 6f 72 20 64 6f # Prefix for do
3260: 74 20 66 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 t files when....
3270: 09 20 20 20 20 20 20 20 23 20 65 78 70 6f 72 74 . # export
3280: 69 6e 67 20 74 68 65 20 67 72 61 70 68 73 2e 0a ing the graphs..
3290: 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c 65 typevariable
32a0: 20 6d 79 64 6f 74 69 64 20 20 20 20 20 20 20 20 mydotid
32b0: 20 20 20 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 0 ; # Counter
32c0: 20 66 6f 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 for dot file na
32d0: 6d 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 20 me..... #
32e0: 67 65 6e 65 72 61 74 69 6f 6e 2e 0a 0a 20 20 20 generation...
32f0: 20 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 # # ## ### ####
3300: 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 # ######## #####
3310: 23 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 ########. ##
3320: 43 6f 6e 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 Configuration..
3330: 20 20 20 70 72 61 67 6d 61 20 2d 68 61 73 69 6e pragma -hasin
3340: 73 74 61 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 stances no ; #
3350: 20 73 69 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 singleton. p
3360: 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 69 6e ragma -hastypein
3370: 66 6f 20 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 fo no ; # no
3380: 69 6e 74 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 introspection.
3390: 20 20 70 72 61 67 6d 61 20 2d 68 61 73 74 79 70 pragma -hastyp
33a0: 65 64 65 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 edestroy no ; #
33b0: 69 6d 6d 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 immortal.. #
33c0: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
33d0: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
33e0: 23 23 23 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 #####.}..namespa
33f0: 63 65 20 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f ce eval ::vc::fo
3400: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
3410: 73 20 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 s {. namespac
3420: 65 20 65 78 70 6f 72 74 20 63 79 63 6c 65 62 72 e export cyclebr
3430: 65 61 6b 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 eaker. namesp
3440: 61 63 65 20 65 76 61 6c 20 63 79 63 6c 65 62 72 ace eval cyclebr
3450: 65 61 6b 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 eaker {..namespa
3460: 63 65 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 ce eval project
3470: 7b 0a 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 {.. namespace
3480: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f import ::vc::fo
3490: 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 ssil::import::cv
34a0: 73 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a s::project::rev.
34b0: 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 . namespace i
34c0: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 mport ::vc::foss
34d0: 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a il::import::cvs:
34e0: 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e :project::revlin
34f0: 6b 0a 09 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 k..}..namespace
3500: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f import ::vc::too
3510: 6c 73 3a 3a 6d 69 73 63 3a 3a 2a 0a 09 6e 61 6d ls::misc::*..nam
3520: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3530: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 vc::tools::log..
3540: 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f 72 74 namespace import
3550: 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 74 72 ::vc::tools::tr
3560: 6f 75 62 6c 65 0a 09 6e 61 6d 65 73 70 61 63 65 ouble..namespace
3570: 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f import ::vc::to
3580: 6f 6c 73 3a 3a 64 6f 74 0a 09 6c 6f 67 20 72 65 ols::dot..log re
3590: 67 69 73 74 65 72 20 63 79 63 6c 65 62 72 65 61 gister cyclebrea
35a0: 6b 65 72 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 23 ker. }.}..# #
35b0: 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 23 ## ### ##### ##
35c0: 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 23 ###### #########
35d0: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
35e0: 23 23 23 23 23 23 23 23 23 23 0a 23 23 20 52 65 ##########.## Re
35f0: 61 64 79 0a 0a 70 61 63 6b 61 67 65 20 70 72 6f ady..package pro
3600: 76 69 64 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a vide vc::fossil:
3610: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 :import::cvs::cy
3620: 63 6c 65 62 72 65 61 6b 65 72 20 31 2e 30 0a 72 clebreaker 1.0.r
3630: 65 74 75 72 6e 0a eturn.