Artifact af14f4e127b1e54cb417ddae43bd12287a60a2d0:
File
tools/cvs2fossil/lib/c2f_cyclebreaker.tcl
part of check-in
[2cf0462b82]
- Cycle breaker, API change. Routing the core cycle breaking through a callback so that users can choose their own algorithms. Updated passes 6 and 7. Moven changesets selection in pass 7 to separate command.
by
aku on
2007-11-21 04:05:53.
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 73 61 76 65 63 typemethod savec
06c0: 6d 64 20 7b 63 6d 64 7d 20 7b 0a 09 3a 3a 76 61 md {cmd} {..::va
06d0: 72 69 61 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 riable mysavecmd
06e0: 20 24 63 6d 64 0a 09 72 65 74 75 72 6e 0a 20 20 $cmd..return.
06f0: 20 20 7d 0a 20 0a 20 20 20 20 74 79 70 65 6d 65 }. . typeme
0700: 74 68 6f 64 20 62 72 65 61 6b 63 6d 64 20 7b 63 thod breakcmd {c
0710: 6d 64 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 6c md} {..::variabl
0720: 65 20 6d 79 62 72 65 61 6b 63 6d 64 20 24 63 6d e mybreakcmd $cm
0730: 64 0a 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a d..return. }.
0740: 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23 20 . # # ## ###
0750: 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20 23 ##### ######## #
0760: 23 23 23 23 23 23 23 23 23 23 23 23 0a 0a 20 20 ############..
0770: 20 20 74 79 70 65 6d 65 74 68 6f 64 20 64 6f 74 typemethod dot
0780: 73 74 6f 20 7b 70 61 74 68 7d 20 7b 0a 09 3a 3a sto {path} {..::
0790: 76 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 64 65 variable mydotde
07a0: 73 74 69 6e 61 74 69 6f 6e 20 24 70 61 74 68 0a stination $path.
07b0: 09 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 .return. }..
07c0: 20 20 20 74 79 70 65 6d 65 74 68 6f 64 20 64 6f typemethod do
07d0: 74 20 7b 6c 61 62 65 6c 20 63 68 61 6e 67 65 73 t {label changes
07e0: 65 74 73 7d 20 7b 0a 09 3a 3a 76 61 72 69 61 62 ets} {..::variab
07f0: 6c 65 20 6d 79 64 6f 74 70 72 65 66 69 78 20 24 le mydotprefix $
0800: 6c 61 62 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c label..::variabl
0810: 65 20 6d 79 64 6f 74 69 64 20 20 20 20 20 30 0a e mydotid 0.
0820: 0a 09 73 65 74 20 64 67 20 5b 53 65 74 75 70 20 ..set dg [Setup
0830: 24 63 68 61 6e 67 65 73 65 74 73 20 30 5d 0a 09 $changesets 0]..
0840: 4d 61 72 6b 20 24 64 67 0a 09 24 64 67 20 64 65 Mark $dg..$dg de
0850: 73 74 72 6f 79 0a 09 72 65 74 75 72 6e 0a 20 20 stroy..return.
0860: 20 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 }.. # # ##
0870: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 ### ##### ######
0880: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 ## #############
0890: 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f 64 .. typemethod
08a0: 20 72 75 6e 20 7b 6c 61 62 65 6c 20 63 68 61 6e run {label chan
08b0: 67 65 73 65 74 73 7d 20 7b 0a 09 3a 3a 76 61 72 gesets} {..::var
08c0: 69 61 62 6c 65 20 6d 79 61 74 20 20 20 20 20 20 iable myat
08d0: 20 20 30 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 0..::variable
08e0: 6d 79 64 6f 74 70 72 65 66 69 78 20 24 6c 61 62 mydotprefix $lab
08f0: 65 6c 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d el..::variable m
0900: 79 64 6f 74 69 64 20 20 20 20 20 30 0a 0a 09 23 ydotid 0...#
0910: 20 57 65 20 63 72 65 61 74 65 20 61 20 67 72 61 We create a gra
0920: 70 68 20 6f 66 20 74 68 65 20 72 65 76 69 73 69 ph of the revisi
0930: 6f 6e 20 63 68 61 6e 67 65 73 65 74 73 2c 20 75 on changesets, u
0940: 73 69 6e 67 20 74 68 65 20 66 69 6c 65 0a 09 23 sing the file..#
0950: 20 6c 65 76 65 6c 20 64 65 70 65 6e 64 65 6e 63 level dependenc
0960: 69 65 73 20 74 6f 20 63 6f 6e 73 74 72 75 63 74 ies to construct
0970: 20 61 20 66 69 72 73 74 20 61 70 70 72 6f 78 69 a first approxi
0980: 6d 61 74 69 6f 6e 20 6f 66 20 74 68 65 0a 09 23 mation of the..#
0990: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 74 dependencies at
09a0: 20 74 68 65 20 70 72 6f 6a 65 63 74 20 6c 65 76 the project lev
09b0: 65 6c 2e 20 54 68 65 6e 20 77 65 20 6c 6f 6f 6b el. Then we look
09c0: 20 66 6f 72 20 63 79 63 6c 65 73 0a 09 23 20 69 for cycles..# i
09d0: 6e 20 74 68 61 74 20 67 72 61 70 68 20 61 6e 64 n that graph and
09e0: 20 62 72 65 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 break them....#
09f0: 20 31 2e 20 43 72 65 61 74 65 20 6e 6f 64 65 73 1. Create nodes
0a00: 20 66 6f 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e for all relevan
0a10: 74 20 63 68 61 6e 67 65 73 65 74 73 20 61 6e 64 t changesets and
0a20: 20 61 20 6d 61 70 70 69 6e 67 0a 09 23 20 20 20 a mapping..#
0a30: 20 66 72 6f 6d 20 74 68 65 20 72 65 76 69 73 69 from the revisi
0a40: 6f 6e 73 20 74 6f 20 74 68 65 69 72 20 63 68 61 ons to their cha
0a50: 6e 67 65 73 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a ngesets/nodes...
0a60: 09 73 65 74 20 64 67 20 5b 53 65 74 75 70 20 24 .set dg [Setup $
0a70: 63 68 61 6e 67 65 73 65 74 73 5d 0a 0a 09 23 20 changesets]...#
0a80: 33 2e 20 4c 61 73 74 6c 79 20 77 65 20 69 74 65 3. Lastly we ite
0a90: 72 61 74 65 20 74 68 65 20 67 72 61 70 68 20 74 rate the graph t
0aa0: 6f 70 6f 6c 6f 67 69 63 61 6c 6c 79 2e 20 57 65 opologically. We
0ab0: 20 6d 61 72 6b 20 6f 66 66 0a 09 23 20 20 20 20 mark off..#
0ac0: 74 68 65 20 6e 6f 64 65 73 20 77 68 69 63 68 20 the nodes which
0ad0: 68 61 76 65 20 6e 6f 20 70 72 65 64 65 63 65 73 have no predeces
0ae0: 73 6f 72 73 2c 20 69 6e 20 6f 72 64 65 72 20 66 sors, in order f
0af0: 72 6f 6d 0a 09 23 20 20 20 20 6f 6c 64 65 73 74 rom..# oldest
0b00: 20 74 6f 20 79 6f 75 6e 67 65 73 74 2c 20 73 61 to youngest, sa
0b10: 76 69 6e 67 20 61 6e 64 20 72 65 6d 6f 76 69 6e ving and removin
0b20: 67 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 g dependencies.
0b30: 49 66 0a 09 23 20 20 20 20 77 65 20 66 69 6e 64 If..# we find
0b40: 20 6e 6f 20 6e 6f 64 65 73 20 77 69 74 68 6f 75 no nodes withou
0b50: 74 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 77 t predecessors w
0b60: 65 20 68 61 76 65 20 61 20 63 79 63 6c 65 2c 0a e have a cycle,.
0b70: 09 23 20 20 20 20 61 6e 64 20 77 6f 72 6b 20 6f .# and work o
0b80: 6e 20 62 72 65 61 6b 69 6e 67 20 69 74 2e 0a 0a n breaking it...
0b90: 09 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 .log write 3 cyc
0ba0: 6c 65 62 72 65 61 6b 65 72 20 7b 4e 6f 77 20 73 lebreaker {Now s
0bb0: 6f 72 74 69 6e 67 20 74 68 65 20 63 68 61 6e 67 orting the chang
0bc0: 65 73 65 74 73 2c 20 62 72 65 61 6b 69 6e 67 20 esets, breaking
0bd0: 63 79 63 6c 65 73 7d 0a 0a 09 49 6e 69 74 69 61 cycles}...Initia
0be0: 6c 69 7a 65 43 61 6e 64 69 64 61 74 65 73 20 24 lizeCandidates $
0bf0: 64 67 0a 09 77 68 69 6c 65 20 7b 31 7d 20 7b 0a dg..while {1} {.
0c00: 09 20 20 20 20 77 68 69 6c 65 20 7b 5b 57 69 74 . while {[Wit
0c10: 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 houtPredecessor
0c20: 24 64 67 20 6e 5d 7d 20 7b 0a 09 09 50 72 6f 63 $dg n]} {...Proc
0c30: 65 73 73 65 64 48 6f 6f 6b 20 24 6e 20 24 6d 79 essedHook $n $my
0c40: 61 74 0a 09 09 24 64 67 20 6e 6f 64 65 20 64 65 at...$dg node de
0c50: 6c 65 74 65 20 24 6e 0a 09 09 69 6e 63 72 20 6d lete $n...incr m
0c60: 79 61 74 0a 09 20 20 20 20 7d 0a 0a 09 20 20 20 yat.. }...
0c70: 20 69 66 20 7b 21 5b 6c 6c 65 6e 67 74 68 20 5b if {![llength [
0c80: 64 67 20 6e 6f 64 65 73 5d 5d 7d 20 62 72 65 61 dg nodes]]} brea
0c90: 6b 0a 0a 09 20 20 20 20 42 72 65 61 6b 43 79 63 k... BreakCyc
0ca0: 6c 65 48 6f 6f 6b 20 20 20 20 20 20 20 24 64 67 leHook $dg
0cb0: 0a 09 20 20 20 20 49 6e 69 74 69 61 6c 69 7a 65 .. Initialize
0cc0: 43 61 6e 64 69 64 61 74 65 73 20 24 64 67 0a 09 Candidates $dg..
0cd0: 7d 0a 0a 09 64 67 20 64 65 73 74 72 6f 79 0a 0a }...dg destroy..
0ce0: 09 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 .log write 3 cyc
0cf0: 6c 65 62 72 65 61 6b 65 72 20 44 6f 6e 65 2e 0a lebreaker Done..
0d00: 09 43 6c 65 61 72 48 6f 6f 6b 73 0a 09 72 65 74 .ClearHooks..ret
0d10: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 urn. }.. #
0d20: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
0d30: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
0d40: 23 23 23 23 23 23 0a 0a 20 20 20 20 74 79 70 65 ######.. type
0d50: 6d 65 74 68 6f 64 20 62 72 65 61 6b 20 7b 67 72 method break {gr
0d60: 61 70 68 7d 20 7b 0a 09 42 72 65 61 6b 43 79 63 aph} {..BreakCyc
0d70: 6c 65 20 24 67 72 61 70 68 20 5b 46 69 6e 64 43 le $graph [FindC
0d80: 79 63 6c 65 20 24 67 72 61 70 68 5d 0a 09 72 65 ycle $graph]..re
0d90: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
0da0: 23 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 # # ## ### #####
0db0: 20 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 ######## ######
0dc0: 23 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 49 #######. ## I
0dd0: 6e 74 65 72 6e 61 6c 20 6d 65 74 68 6f 64 73 0a nternal methods.
0de0: 0a 20 20 20 20 70 72 6f 63 20 53 65 74 75 70 20 . proc Setup
0df0: 7b 63 68 61 6e 67 65 73 65 74 73 20 7b 6c 6f 67 {changesets {log
0e00: 20 31 7d 7d 20 7b 0a 09 69 66 20 7b 24 6c 6f 67 1}} {..if {$log
0e10: 7d 20 7b 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 } {.. log wri
0e20: 74 65 20 33 20 63 79 63 6c 65 62 72 65 61 6b 65 te 3 cyclebreake
0e30: 72 20 22 43 72 65 61 74 69 6e 67 20 63 68 61 6e r "Creating chan
0e40: 67 65 73 65 74 20 67 72 61 70 68 2c 20 66 69 6c geset graph, fil
0e50: 6c 69 6e 67 20 77 69 74 68 20 6e 6f 64 65 73 22 ling with nodes"
0e60: 0a 09 20 20 20 20 6c 6f 67 20 77 72 69 74 65 20 .. log write
0e70: 33 20 63 79 63 6c 65 62 72 65 61 6b 65 72 20 22 3 cyclebreaker "
0e80: 41 64 64 69 6e 67 20 5b 6e 73 70 20 5b 6c 6c 65 Adding [nsp [lle
0e90: 6e 67 74 68 20 24 63 68 61 6e 67 65 73 65 74 73 ngth $changesets
0ea0: 5d 20 6e 6f 64 65 5d 22 0a 09 7d 0a 0a 09 73 65 ] node]"..}...se
0eb0: 74 20 64 67 20 5b 73 74 72 75 63 74 3a 3a 67 72 t dg [struct::gr
0ec0: 61 70 68 20 64 67 5d 0a 0a 09 66 6f 72 65 61 63 aph dg]...foreac
0ed0: 68 20 63 73 65 74 20 24 63 68 61 6e 67 65 73 65 h cset $changese
0ee0: 74 73 20 7b 0a 09 20 20 20 20 24 64 67 20 6e 6f ts {.. $dg no
0ef0: 64 65 20 69 6e 73 65 72 74 20 24 63 73 65 74 0a de insert $cset.
0f00: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 73 65 . $dg node se
0f10: 74 20 20 20 20 24 63 73 65 74 20 74 69 6d 65 72 t $cset timer
0f20: 61 6e 67 65 20 5b 24 63 73 65 74 20 74 69 6d 65 ange [$cset time
0f30: 72 61 6e 67 65 5d 0a 09 7d 0a 0a 09 23 20 32 2e range]..}...# 2.
0f40: 20 46 69 6e 64 20 66 6f 72 20 61 6c 6c 20 72 65 Find for all re
0f50: 6c 65 76 61 6e 74 20 63 68 61 6e 67 65 73 65 74 levant changeset
0f60: 20 74 68 65 69 72 20 72 65 76 69 73 69 6f 6e 73 their revisions
0f70: 20 61 6e 64 20 74 68 65 69 72 0a 09 23 20 20 20 and their..#
0f80: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 4d dependencies. M
0f90: 61 70 20 74 68 65 20 6c 61 74 74 65 72 20 62 61 ap the latter ba
0fa0: 63 6b 20 74 6f 20 63 68 61 6e 67 65 73 65 74 73 ck to changesets
0fb0: 20 61 6e 64 0a 09 23 20 20 20 20 63 6f 6e 73 74 and..# const
0fc0: 72 75 63 74 20 74 68 65 20 63 6f 72 72 65 73 70 ruct the corresp
0fd0: 6f 6e 64 69 6e 67 20 61 72 63 73 2e 0a 0a 09 69 onding arcs....i
0fe0: 66 20 7b 24 6c 6f 67 7d 20 7b 0a 09 20 20 20 20 f {$log} {..
0ff0: 6c 6f 67 20 77 72 69 74 65 20 33 20 63 79 63 6c log write 3 cycl
1000: 65 62 72 65 61 6b 65 72 20 7b 53 65 74 74 69 6e ebreaker {Settin
1010: 67 20 75 70 20 6e 6f 64 65 20 64 65 70 65 6e 64 g up node depend
1020: 65 6e 63 69 65 73 7d 0a 09 7d 0a 0a 09 66 6f 72 encies}..}...for
1030: 65 61 63 68 20 63 73 65 74 20 24 63 68 61 6e 67 each cset $chang
1040: 65 73 65 74 73 20 7b 0a 09 20 20 20 20 66 6f 72 esets {.. for
1050: 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 each succ [$cset
1060: 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 successors] {..
1070: 09 23 20 43 68 61 6e 67 65 73 65 74 73 20 6d 61 .# Changesets ma
1080: 79 20 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 y have dependenc
1090: 69 65 73 20 6f 75 74 73 69 64 65 20 6f 66 20 74 ies outside of t
10a0: 68 65 0a 09 09 23 20 63 68 6f 73 65 6e 20 73 65 he...# chosen se
10b0: 74 2e 20 54 68 65 73 65 20 61 72 65 20 69 67 6e t. These are ign
10c0: 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 ored...if {![$dg
10d0: 20 6e 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 node exists $su
10e0: 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 cc]} continue...
10f0: 24 64 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 $dg arc insert $
1100: 63 73 65 74 20 24 73 75 63 63 0a 09 20 20 20 20 cset $succ..
1110: 7d 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 24 64 }..}...return $d
1120: 67 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 49 g. }.. # I
1130: 6e 73 74 65 61 64 20 6f 66 20 73 65 61 72 63 68 nstead of search
1140: 69 6e 67 20 74 68 65 20 77 68 6f 6c 65 20 67 72 ing the whole gr
1150: 61 70 68 20 66 6f 72 20 74 68 65 20 64 65 67 72 aph for the degr
1160: 65 65 2d 30 20 6e 6f 64 65 73 20 69 6e 0a 20 20 ee-0 nodes in.
1170: 20 20 23 20 65 61 63 68 20 69 74 65 72 61 74 69 # each iterati
1180: 6f 6e 20 77 65 20 63 6f 6d 70 75 74 65 20 74 68 on we compute th
1190: 65 20 6c 69 73 74 20 6f 6e 63 65 20 74 6f 20 73 e list once to s
11a0: 74 61 72 74 2c 20 61 6e 64 20 74 68 65 6e 20 6f tart, and then o
11b0: 6e 6c 79 0a 20 20 20 20 23 20 75 70 64 61 74 65 nly. # update
11c0: 20 69 74 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c it incrementall
11d0: 79 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6f y based on the o
11e0: 75 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 utgoing neighbou
11f0: 72 73 20 6f 66 20 74 68 65 0a 20 20 20 20 23 20 rs of the. #
1200: 6e 6f 64 65 20 63 68 6f 73 65 6e 20 66 6f 72 20 node chosen for
1210: 63 6f 6d 6d 69 74 2e 0a 0a 20 20 20 20 70 72 6f commit... pro
1220: 63 20 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 c InitializeCand
1230: 69 64 61 74 65 73 20 7b 64 67 7d 20 7b 0a 09 23 idates {dg} {..#
1240: 20 62 6f 74 74 6f 6d 20 3d 20 6c 69 73 74 20 28 bottom = list (
1250: 6c 69 73 74 20 28 6e 6f 64 65 2c 20 72 61 6e 67 list (node, rang
1260: 65 20 6d 69 6e 2c 20 72 61 6e 67 65 20 6d 61 78 e min, range max
1270: 29 29 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d ))..::variable m
1280: 79 62 6f 74 74 6f 6d 0a 09 66 6f 72 65 61 63 68 ybottom..foreach
1290: 20 6e 20 5b 24 64 67 20 6e 6f 64 65 73 5d 20 7b n [$dg nodes] {
12a0: 0a 09 20 20 20 20 69 66 20 7b 5b 24 64 67 20 6e .. if {[$dg n
12b0: 6f 64 65 20 64 65 67 72 65 65 20 2d 69 6e 20 24 ode degree -in $
12c0: 6e 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 n]} continue..
12d0: 20 20 6c 61 70 70 65 6e 64 20 6d 79 62 6f 74 74 lappend mybott
12e0: 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24 64 67 om [linsert [$dg
12f0: 20 6e 6f 64 65 20 67 65 74 20 24 6e 20 74 69 6d node get $n tim
1300: 65 72 61 6e 67 65 5d 20 30 20 24 6e 5d 0a 09 7d erange] 0 $n]..}
1310: 0a 09 73 65 74 20 6d 79 62 6f 74 74 6f 6d 20 5b ..set mybottom [
1320: 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 31 20 2d lsort -index 1 -
1330: 69 6e 74 65 67 65 72 20 5b 6c 73 6f 72 74 20 2d integer [lsort -
1340: 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 67 65 72 index 2 -integer
1350: 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d 0a 09 72 65 $mybottom]]..re
1360: 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 turn. }..
1370: 70 72 6f 63 20 57 69 74 68 6f 75 74 50 72 65 64 proc WithoutPred
1380: 65 63 65 73 73 6f 72 20 7b 64 67 20 6e 76 7d 20 ecessor {dg nv}
1390: 7b 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 {..::variable my
13a0: 62 6f 74 74 6f 6d 0a 0a 09 75 70 76 61 72 20 31 bottom...upvar 1
13b0: 20 24 6e 76 20 6e 0a 09 69 66 20 7b 21 5b 6c 6c $nv n..if {![ll
13c0: 65 6e 67 74 68 20 24 6d 79 62 6f 74 74 6f 6d 5d ength $mybottom]
13d0: 7d 20 7b 20 72 65 74 75 72 6e 20 30 20 7d 0a 0a } { return 0 }..
13e0: 09 73 65 74 20 6e 20 5b 6c 69 6e 64 65 78 20 5b .set n [lindex [
13f0: 6c 69 6e 64 65 78 20 24 6d 79 62 6f 74 74 6f 6d lindex $mybottom
1400: 20 30 5d 20 30 5d 0a 09 73 65 74 20 6d 79 62 6f 0] 0]..set mybo
1410: 74 74 6f 6d 20 5b 6c 72 61 6e 67 65 20 24 6d 79 ttom [lrange $my
1420: 62 6f 74 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 bottom 1 end]..s
1430: 65 74 20 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 et changed 0...#
1440: 20 55 70 64 61 74 65 20 6c 69 73 74 20 6f 66 20 Update list of
1450: 6e 6f 64 65 73 20 77 69 74 68 6f 75 74 20 70 72 nodes without pr
1460: 65 64 65 63 65 73 73 6f 72 2c 20 62 61 73 65 64 edecessor, based
1470: 20 6f 6e 20 74 68 65 0a 09 23 20 6f 75 74 67 6f on the..# outgo
1480: 69 6e 67 20 6e 65 69 67 68 62 6f 75 72 73 20 6f ing neighbours o
1490: 66 20 74 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 f the chosen nod
14a0: 65 2e 20 54 68 69 73 20 73 68 6f 75 6c 64 20 62 e. This should b
14b0: 65 0a 09 23 20 66 61 73 74 65 72 20 74 68 61 6e e..# faster than
14c0: 20 69 74 65 72 61 74 69 6e 67 20 6f 66 20 74 68 iterating of th
14d0: 65 20 77 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e e whole set of n
14e0: 6f 64 65 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c odes, finding al
14f0: 6c 0a 09 23 20 77 69 74 68 6f 75 74 20 70 72 65 l..# without pre
1500: 64 65 63 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 decessors, sorti
1510: 6e 67 20 74 68 65 6d 20 62 79 20 74 69 6d 65 2c ng them by time,
1520: 20 65 74 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 etc. pp...forea
1530: 63 68 20 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 ch out [$dg node
1540: 73 20 2d 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 s -out $n] {..
1550: 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 if {[$dg node
1560: 64 65 67 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d degree -in $out]
1570: 20 3e 20 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 > 1} continue..
1580: 20 20 20 20 23 20 44 65 67 72 65 65 2d 31 20 6e # Degree-1 n
1590: 65 69 67 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 eighbour, will h
15a0: 61 76 65 20 6e 6f 20 70 72 65 64 65 63 65 73 73 ave no predecess
15b0: 6f 72 73 20 61 66 74 65 72 20 74 68 65 0a 09 20 ors after the..
15c0: 20 20 20 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 # removal of
15d0: 6e 2e 20 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 n. Put on the li
15e0: 73 74 2e 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 st... lappend
15f0: 20 6d 79 62 6f 74 74 6f 6d 20 5b 6c 69 6e 73 65 mybottom [linse
1600: 72 74 20 5b 24 64 67 20 6e 6f 64 65 20 67 65 74 rt [$dg node get
1610: 20 24 6f 75 74 20 74 69 6d 65 72 61 6e 67 65 5d $out timerange]
1620: 20 30 20 24 6f 75 74 5d 0a 09 20 20 20 20 73 65 0 $out].. se
1630: 74 20 63 68 61 6e 67 65 64 20 31 0a 09 7d 0a 09 t changed 1..}..
1640: 69 66 20 7b 24 63 68 61 6e 67 65 64 7d 20 7b 0a if {$changed} {.
1650: 09 20 20 20 20 73 65 74 20 6d 79 62 6f 74 74 6f . set mybotto
1660: 6d 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 m [lsort -index
1670: 31 20 2d 69 6e 74 65 67 65 72 20 5b 6c 73 6f 72 1 -integer [lsor
1680: 74 20 2d 69 6e 64 65 78 20 32 20 2d 69 6e 74 65 t -index 2 -inte
1690: 67 65 72 20 24 6d 79 62 6f 74 74 6f 6d 5d 5d 0a ger $mybottom]].
16a0: 09 7d 0a 0a 09 23 20 57 65 20 64 6f 20 6e 6f 74 .}...# We do not
16b0: 20 64 65 6c 65 74 65 20 74 68 65 20 6e 6f 64 65 delete the node
16c0: 20 69 6d 6d 65 64 69 61 74 65 6c 79 2c 20 74 6f immediately, to
16d0: 20 61 6c 6c 6f 77 20 74 68 65 20 53 61 76 65 0a allow the Save.
16e0: 09 23 20 70 72 6f 63 65 64 75 72 65 20 74 6f 20 .# procedure to
16f0: 73 61 76 65 20 74 68 65 20 64 65 70 65 6e 64 65 save the depende
1700: 6e 63 69 65 73 20 61 73 20 77 65 6c 6c 20 28 65 ncies as well (e
1710: 6e 63 6f 64 65 64 20 69 6e 20 74 68 65 0a 09 23 ncoded in the..#
1720: 20 61 72 63 73 29 2e 0a 09 72 65 74 75 72 6e 20 arcs)...return
1730: 31 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 1. }.. pro
1740: 63 20 46 69 6e 64 43 79 63 6c 65 20 7b 64 67 7d c FindCycle {dg}
1750: 20 7b 0a 09 23 20 54 68 69 73 20 70 72 6f 63 65 {..# This proce
1760: 64 75 72 65 20 69 73 20 72 75 6e 20 69 66 20 61 dure is run if a
1770: 6e 64 20 6f 6e 6c 79 20 74 68 65 20 67 72 61 70 nd only the grap
1780: 68 20 69 73 20 6e 6f 74 20 65 6d 70 74 79 20 61 h is not empty a
1790: 6e 64 0a 09 23 20 61 6c 6c 20 6e 6f 64 65 73 20 nd..# all nodes
17a0: 68 61 76 65 20 70 72 65 64 65 63 65 73 73 6f 72 have predecessor
17b0: 73 2e 20 54 68 69 73 20 6d 65 61 6e 73 20 74 68 s. This means th
17c0: 61 74 20 65 61 63 68 20 6e 6f 64 65 20 69 73 0a at each node is.
17d0: 09 23 20 65 69 74 68 65 72 20 70 61 72 74 20 6f .# either part o
17e0: 66 20 61 20 63 79 63 6c 65 20 6f 72 20 28 69 6e f a cycle or (in
17f0: 64 69 72 65 63 74 6c 79 29 20 64 65 70 65 6e 64 directly) depend
1800: 69 6e 67 20 6f 6e 20 61 20 6e 6f 64 65 0a 09 23 ing on a node..#
1810: 20 69 6e 20 61 20 63 79 63 6c 65 2e 20 57 65 20 in a cycle. We
1820: 63 61 6e 20 73 74 61 72 74 20 61 74 20 61 6e 20 can start at an
1830: 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65 2c 20 arbitrary node,
1840: 66 6f 6c 6c 6f 77 20 69 74 73 0a 09 23 20 69 6e follow its..# in
1850: 63 6f 6d 69 6e 67 20 65 64 67 65 73 20 74 6f 20 coming edges to
1860: 69 74 73 20 70 72 65 64 65 63 65 73 73 6f 72 73 its predecessors
1870: 20 75 6e 74 69 6c 20 77 65 20 73 65 65 20 61 20 until we see a
1880: 6e 6f 64 65 20 61 0a 09 23 20 73 65 63 6f 6e 64 node a..# second
1890: 20 74 69 6d 65 2e 20 54 68 61 74 20 6e 6f 64 65 time. That node
18a0: 20 63 6c 6f 73 65 73 20 74 68 65 20 63 79 63 6c closes the cycl
18b0: 65 20 61 6e 64 20 74 68 65 20 62 65 67 69 6e 6e e and the beginn
18c0: 69 6e 67 20 69 73 0a 09 23 20 69 74 73 20 66 69 ing is..# its fi
18d0: 72 73 74 20 6f 63 63 75 72 65 6e 63 65 2e 20 4e rst occurence. N
18e0: 6f 74 65 20 74 68 61 74 20 77 65 20 63 61 6e 20 ote that we can
18f0: 63 68 6f 6f 73 65 20 61 6e 20 61 72 62 69 74 72 choose an arbitr
1900: 61 72 79 0a 09 23 20 70 72 65 64 65 63 65 73 73 ary..# predecess
1910: 6f 72 20 6f 66 20 65 61 63 68 20 6e 6f 64 65 20 or of each node
1920: 61 73 20 77 65 6c 6c 2c 20 77 65 20 64 6f 20 6e as well, we do n
1930: 6f 74 20 68 61 76 65 20 74 6f 20 73 65 61 72 63 ot have to searc
1940: 68 2e 0a 0a 09 23 20 57 65 20 72 65 63 6f 72 64 h....# We record
1950: 20 66 6f 72 20 65 61 63 68 20 6e 6f 64 65 20 74 for each node t
1960: 68 65 20 69 6e 64 65 78 20 6f 66 20 74 68 65 20 he index of the
1970: 66 69 72 73 74 20 61 70 70 65 61 72 61 6e 63 65 first appearance
1980: 20 69 6e 0a 09 23 20 74 68 65 20 70 61 74 68 2c in..# the path,
1990: 20 6d 61 6b 69 6e 67 20 69 74 20 65 61 73 79 20 making it easy
19a0: 61 74 20 74 68 65 20 65 6e 64 20 74 6f 20 63 75 at the end to cu
19b0: 74 20 74 68 65 20 63 79 63 6c 65 20 66 72 6f 6d t the cycle from
19c0: 0a 09 23 20 69 74 2e 0a 0a 09 23 20 43 68 6f 6f ..# it....# Choo
19d0: 73 65 20 61 72 62 69 74 72 61 72 79 20 6e 6f 64 se arbitrary nod
19e0: 65 20 74 6f 20 73 74 61 72 74 20 6f 75 72 20 73 e to start our s
19f0: 65 61 72 63 68 20 61 74 2e 0a 09 73 65 74 20 73 earch at...set s
1a00: 74 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 64 tart [lindex [$d
1a10: 67 20 6e 6f 64 65 73 5d 20 30 5d 0a 0a 09 23 20 g nodes] 0]...#
1a20: 49 6e 69 74 69 61 6c 69 7a 65 20 73 74 61 74 65 Initialize state
1a30: 2c 20 70 61 74 68 20 6f 66 20 73 65 65 6e 20 6e , path of seen n
1a40: 6f 64 65 73 2c 20 61 6e 64 20 77 68 65 6e 20 73 odes, and when s
1a50: 65 65 6e 2e 0a 09 73 65 74 20 20 20 20 20 20 20 een...set
1a60: 70 61 74 68 20 7b 7d 0a 09 61 72 72 61 79 20 73 path {}..array s
1a70: 65 74 20 73 65 65 6e 20 7b 7d 0a 0a 09 77 68 69 et seen {}...whi
1a80: 6c 65 20 7b 31 7d 20 7b 0a 09 20 20 20 20 23 20 le {1} {.. #
1a90: 53 74 6f 70 20 73 65 61 72 63 68 69 6e 67 20 77 Stop searching w
1aa0: 68 65 6e 20 77 65 20 68 61 76 65 20 73 65 65 6e hen we have seen
1ab0: 20 74 68 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 the current nod
1ac0: 65 0a 09 20 20 20 20 23 20 61 6c 72 65 61 64 79 e.. # already
1ad0: 2c 20 74 68 65 20 63 69 72 63 6c 65 20 68 61 73 , the circle has
1ae0: 20 62 65 65 6e 20 63 6c 6f 73 65 64 2e 0a 09 20 been closed...
1af0: 20 20 20 69 66 20 7b 5b 69 6e 66 6f 20 65 78 69 if {[info exi
1b00: 73 74 73 20 73 65 65 6e 28 24 73 74 61 72 74 29 sts seen($start)
1b10: 5d 7d 20 62 72 65 61 6b 0a 09 20 20 20 20 6c 61 ]} break.. la
1b20: 70 70 65 6e 64 20 70 61 74 68 20 24 73 74 61 72 ppend path $star
1b30: 74 0a 09 20 20 20 20 73 65 74 20 73 65 65 6e 28 t.. set seen(
1b40: 24 73 74 61 72 74 29 20 5b 65 78 70 72 20 7b 5b $start) [expr {[
1b50: 6c 6c 65 6e 67 74 68 20 24 70 61 74 68 5d 2d 31 llength $path]-1
1b60: 7d 5d 0a 09 20 20 20 20 23 20 43 68 6f 6f 73 65 }].. # Choose
1b70: 20 61 72 62 69 74 72 61 72 79 20 70 72 65 64 65 arbitrary prede
1b80: 63 65 73 73 6f 72 0a 09 20 20 20 20 73 65 74 20 cessor.. set
1b90: 73 74 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b 24 start [lindex [$
1ba0: 64 67 20 6e 6f 64 65 73 20 2d 69 6e 20 24 73 74 dg nodes -in $st
1bb0: 61 72 74 5d 20 30 5d 0a 09 7d 0a 0a 09 72 65 74 art] 0]..}...ret
1bc0: 75 72 6e 20 5b 73 74 72 75 63 74 3a 3a 6c 69 73 urn [struct::lis
1bd0: 74 20 72 65 76 65 72 73 65 20 5b 6c 72 61 6e 67 t reverse [lrang
1be0: 65 20 24 70 61 74 68 20 24 73 65 65 6e 28 24 73 e $path $seen($s
1bf0: 74 61 72 74 29 20 65 6e 64 5d 5d 0a 20 20 20 20 tart) end]].
1c00: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 49 44 20 7b }.. proc ID {
1c10: 63 73 65 74 7d 20 7b 20 72 65 74 75 72 6e 20 22 cset} { return "
1c20: 3c 5b 24 63 73 65 74 20 69 64 5d 3e 22 20 7d 0a <[$cset id]>" }.
1c30: 0a 20 20 20 20 70 72 6f 63 20 42 72 65 61 6b 43 . proc BreakC
1c40: 79 63 6c 65 20 7b 64 67 20 63 79 63 6c 65 7d 20 ycle {dg cycle}
1c50: 7b 0a 09 23 20 54 68 65 20 63 79 63 6c 65 20 77 {..# The cycle w
1c60: 65 20 68 61 76 65 20 67 6f 74 74 65 6e 20 69 73 e have gotten is
1c70: 20 62 72 6f 6b 65 6e 20 62 79 20 62 72 65 61 6b broken by break
1c80: 69 6e 67 20 61 70 61 72 74 20 6f 6e 65 20 6f 72 ing apart one or
1c90: 0a 09 23 20 6d 6f 72 65 20 6f 66 20 74 68 65 20 ..# more of the
1ca0: 63 68 61 6e 67 65 73 65 74 73 20 69 6e 20 74 68 changesets in th
1cb0: 65 20 63 79 63 6c 65 2e 20 54 68 69 73 20 63 61 e cycle. This ca
1cc0: 75 73 65 73 20 75 73 20 74 6f 0a 09 23 20 63 72 uses us to..# cr
1cd0: 65 61 74 65 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 eate one or more
1ce0: 20 63 68 61 6e 67 65 73 65 74 73 20 77 68 69 63 changesets whic
1cf0: 68 20 61 72 65 20 74 6f 20 62 65 20 63 6f 6d 6d h are to be comm
1d00: 69 74 74 65 64 2c 0a 09 23 20 61 64 64 65 64 20 itted,..# added
1d10: 74 6f 20 74 68 65 20 67 72 61 70 68 2c 20 65 74 to the graph, et
1d20: 63 2e 20 70 70 2e 0a 0a 09 73 65 74 20 63 70 72 c. pp....set cpr
1d30: 69 6e 74 20 5b 6a 6f 69 6e 20 5b 73 74 72 75 63 int [join [struc
1d40: 74 3a 3a 6c 69 73 74 20 6d 61 70 20 24 63 79 63 t::list map $cyc
1d50: 6c 65 20 5b 6d 79 70 72 6f 63 20 49 44 5d 5d 20 le [myproc ID]]
1d60: 7b 20 7d 5d 0a 0a 09 6c 61 70 70 65 6e 64 20 63 { }]...lappend c
1d70: 79 63 6c 65 20 5b 6c 69 6e 64 65 78 20 24 63 79 ycle [lindex $cy
1d80: 63 6c 65 20 30 5d 20 5b 6c 69 6e 64 65 78 20 24 cle 0] [lindex $
1d90: 63 79 63 6c 65 20 31 5d 0a 09 73 65 74 20 62 65 cycle 1]..set be
1da0: 73 74 6c 69 6e 6b 20 7b 7d 0a 09 73 65 74 20 62 stlink {}..set b
1db0: 65 73 74 6e 6f 64 65 20 7b 7d 0a 0a 09 66 6f 72 estnode {}...for
1dc0: 65 61 63 68 20 5c 0a 09 20 20 20 20 70 72 65 76 each \.. prev
1dd0: 20 5b 6c 72 61 6e 67 65 20 24 63 79 63 6c 65 20 [lrange $cycle
1de0: 30 20 65 6e 64 2d 32 5d 20 5c 0a 09 20 20 20 20 0 end-2] \..
1df0: 63 73 65 74 20 5b 6c 72 61 6e 67 65 20 24 63 79 cset [lrange $cy
1e00: 63 6c 65 20 31 20 65 6e 64 2d 31 5d 20 5c 0a 09 cle 1 end-1] \..
1e10: 20 20 20 20 6e 65 78 74 20 5b 6c 72 61 6e 67 65 next [lrange
1e20: 20 24 63 79 63 6c 65 20 32 20 65 6e 64 5d 20 7b $cycle 2 end] {
1e30: 0a 0a 09 09 23 20 45 61 63 68 20 74 72 69 70 6c ....# Each tripl
1e40: 65 20 50 52 45 56 20 2d 3e 20 43 53 45 54 20 2d e PREV -> CSET -
1e50: 3e 20 4e 45 58 54 20 6f 66 20 63 68 61 6e 67 65 > NEXT of change
1e60: 73 65 74 73 2c 20 61 0a 09 09 23 20 27 6c 69 6e sets, a...# 'lin
1e70: 6b 27 20 69 6e 20 74 68 65 20 63 79 63 6c 65 2c k' in the cycle,
1e80: 20 69 73 20 61 6e 61 6c 79 73 65 64 20 61 6e 64 is analysed and
1e90: 20 74 68 65 20 62 65 73 74 0a 09 09 23 20 6c 6f the best...# lo
1ea0: 63 61 74 69 6f 6e 20 77 68 65 72 65 20 74 6f 20 cation where to
1eb0: 61 74 20 6c 65 61 73 74 20 77 65 61 6b 65 6e 20 at least weaken
1ec0: 74 68 65 20 63 79 63 6c 65 20 69 73 0a 09 09 23 the cycle is...#
1ed0: 20 63 68 6f 73 65 6e 20 66 6f 72 20 66 75 72 74 chosen for furt
1ee0: 68 65 72 20 70 72 6f 63 65 73 73 69 6e 67 2e 0a her processing..
1ef0: 0a 09 09 73 65 74 20 6c 69 6e 6b 20 5b 70 72 6f ...set link [pro
1f00: 6a 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 20 25 41 ject::revlink %A
1f10: 55 54 4f 25 20 24 70 72 65 76 20 24 63 73 65 74 UTO% $prev $cset
1f20: 20 24 6e 65 78 74 5d 0a 09 09 69 66 20 7b 24 62 $next]...if {$b
1f30: 65 73 74 6c 69 6e 6b 20 65 71 20 22 22 7d 20 7b estlink eq ""} {
1f40: 0a 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6c ... set bestl
1f50: 69 6e 6b 20 24 6c 69 6e 6b 0a 09 09 20 20 20 20 ink $link...
1f60: 73 65 74 20 62 65 73 74 6e 6f 64 65 20 24 63 73 set bestnode $cs
1f70: 65 74 0a 09 09 7d 20 65 6c 73 65 69 66 20 7b 5b et...} elseif {[
1f80: 24 6c 69 6e 6b 20 62 65 74 74 65 72 74 68 61 6e $link betterthan
1f90: 20 24 62 65 73 74 6c 69 6e 6b 5d 7d 20 7b 0a 09 $bestlink]} {..
1fa0: 09 20 20 20 20 24 62 65 73 74 6c 69 6e 6b 20 64 . $bestlink d
1fb0: 65 73 74 72 6f 79 0a 09 09 20 20 20 20 73 65 74 estroy... set
1fc0: 20 62 65 73 74 6c 69 6e 6b 20 24 6c 69 6e 6b 0a bestlink $link.
1fd0: 09 09 20 20 20 20 73 65 74 20 62 65 73 74 6e 6f .. set bestno
1fe0: 64 65 20 24 63 73 65 74 0a 09 09 7d 20 65 6c 73 de $cset...} els
1ff0: 65 20 7b 0a 09 09 20 20 20 20 24 6c 69 6e 6b 20 e {... $link
2000: 64 65 73 74 72 6f 79 0a 09 09 7d 0a 09 20 20 20 destroy...}..
2010: 20 7d 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20 35 }...log write 5
2020: 20 62 72 65 61 6b 72 63 79 63 6c 65 20 22 42 72 breakrcycle "Br
2030: 65 61 6b 69 6e 67 20 63 79 63 6c 65 20 28 24 63 eaking cycle ($c
2040: 70 72 69 6e 74 29 20 62 79 20 73 70 6c 69 74 74 print) by splitt
2050: 69 6e 67 20 63 68 61 6e 67 65 73 65 74 20 3c 5b ing changeset <[
2060: 24 62 65 73 74 6e 6f 64 65 20 69 64 5d 3e 22 0a $bestnode id]>".
2070: 09 73 65 74 20 49 44 20 5b 24 62 65 73 74 6e 6f .set ID [$bestno
2080: 64 65 20 69 64 5d 0a 09 4d 61 72 6b 20 24 64 67 de id]..Mark $dg
2090: 20 2d 24 7b 49 44 7d 2d 62 65 66 6f 72 65 0a 0a -${ID}-before..
20a0: 09 73 65 74 20 6e 65 77 63 73 65 74 73 20 5b 24 .set newcsets [$
20b0: 62 65 73 74 6c 69 6e 6b 20 62 72 65 61 6b 5d 0a bestlink break].
20c0: 09 24 62 65 73 74 6c 69 6e 6b 20 64 65 73 74 72 .$bestlink destr
20d0: 6f 79 0a 0a 20 20 20 20 20 20 20 20 23 20 41 74 oy.. # At
20e0: 20 74 68 69 73 20 70 6f 69 6e 74 20 74 68 65 20 this point the
20f0: 6f 6c 64 20 63 68 61 6e 67 65 73 65 74 20 28 42 old changeset (B
2100: 45 53 54 4e 4f 44 45 29 20 69 73 20 67 6f 6e 65 ESTNODE) is gone
2110: 0a 20 20 20 20 20 20 20 20 23 20 61 6c 72 65 61 . # alrea
2120: 64 79 2e 20 57 65 20 72 65 6d 6f 76 65 20 69 74 dy. We remove it
2130: 20 66 72 6f 6d 20 74 68 65 20 67 72 61 70 68 20 from the graph
2140: 61 73 20 77 65 6c 6c 20 61 6e 64 20 74 68 65 6e as well and then
2150: 20 65 6e 74 65 72 0a 20 20 20 20 20 20 20 20 23 enter. #
2160: 20 74 68 65 20 66 72 61 67 6d 65 6e 74 73 20 67 the fragments g
2170: 65 6e 65 72 61 74 65 64 20 66 6f 72 20 69 74 2e enerated for it.
2180: 0a 0a 09 23 20 4e 4f 54 45 2e 20 57 65 20 68 61 ...# NOTE. We ha
2190: 76 65 20 74 6f 20 67 65 74 20 74 68 65 20 6c 69 ve to get the li
21a0: 73 74 20 6f 66 20 69 6e 63 6f 6d 69 6e 67 20 6e st of incoming n
21b0: 65 69 67 68 62 6f 75 72 73 20 61 6e 64 0a 09 23 eighbours and..#
21c0: 20 72 65 63 6f 6d 70 75 74 65 20 74 68 65 69 72 recompute their
21d0: 20 73 75 63 63 65 73 73 6f 72 73 20 61 66 74 65 successors afte
21e0: 72 20 74 68 65 20 6e 65 77 20 6e 6f 64 65 73 20 r the new nodes
21f0: 68 61 76 65 20 62 65 65 6e 0a 09 23 20 69 6e 73 have been..# ins
2200: 65 72 74 65 64 2e 20 54 68 65 69 72 20 6f 75 74 erted. Their out
2210: 67 6f 69 6e 67 20 61 72 63 73 20 77 69 6c 6c 20 going arcs will
2220: 6e 6f 77 20 67 6f 20 74 6f 20 6f 6e 65 20 6f 72 now go to one or
2230: 20 62 6f 74 68 20 6f 66 0a 09 23 20 74 68 65 20 both of..# the
2240: 6e 65 77 20 6e 6f 64 65 73 2c 20 61 6e 64 20 6e new nodes, and n
2250: 6f 74 20 72 65 64 6f 69 6e 67 20 74 68 65 6d 20 ot redoing them
2260: 6d 61 79 20 63 61 75 73 65 20 75 73 20 74 6f 20 may cause us to
2270: 66 6f 72 67 65 74 0a 09 23 20 63 69 72 63 6c 65 forget..# circle
2280: 73 2c 20 6c 65 61 76 69 6e 67 20 74 68 65 6d 20 s, leaving them
2290: 69 6e 2c 20 75 6e 62 72 6f 6b 65 6e 2e 0a 0a 09 in, unbroken....
22a0: 73 65 74 20 70 72 65 20 5b 24 64 67 20 6e 6f 64 set pre [$dg nod
22b0: 65 73 20 2d 69 6e 20 24 62 65 73 74 6e 6f 64 65 es -in $bestnode
22c0: 5d 0a 0a 20 20 20 20 20 20 20 20 24 64 67 20 6e ].. $dg n
22d0: 6f 64 65 20 64 65 6c 65 74 65 20 24 62 65 73 74 ode delete $best
22e0: 6e 6f 64 65 0a 0a 09 66 6f 72 65 61 63 68 20 63 node...foreach c
22f0: 73 65 74 20 24 6e 65 77 63 73 65 74 73 20 7b 0a set $newcsets {.
2300: 09 20 20 20 20 24 64 67 20 6e 6f 64 65 20 69 6e . $dg node in
2310: 73 65 72 74 20 24 63 73 65 74 0a 09 20 20 20 20 sert $cset..
2320: 24 64 67 20 6e 6f 64 65 20 73 65 74 20 20 20 20 $dg node set
2330: 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 20 $cset timerange
2340: 5b 24 63 73 65 74 20 74 69 6d 65 72 61 6e 67 65 [$cset timerange
2350: 5d 0a 09 7d 0a 0a 09 66 6f 72 65 61 63 68 20 63 ]..}...foreach c
2360: 73 65 74 20 24 6e 65 77 63 73 65 74 73 20 7b 0a set $newcsets {.
2370: 09 20 20 20 20 66 6f 72 65 61 63 68 20 73 75 63 . foreach suc
2380: 63 20 5b 24 63 73 65 74 20 73 75 63 63 65 73 73 c [$cset success
2390: 6f 72 73 5d 20 7b 0a 09 09 23 20 54 68 65 20 6e ors] {...# The n
23a0: 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d 61 ew changesets ma
23b0: 79 20 68 61 76 65 20 64 65 70 65 6e 64 65 6e 63 y have dependenc
23c0: 69 65 73 20 6f 75 74 73 69 64 65 20 6f 66 0a 09 ies outside of..
23d0: 09 23 20 74 68 65 20 63 68 6f 73 65 6e 20 73 65 .# the chosen se
23e0: 74 2e 20 54 68 65 73 65 20 61 72 65 20 69 67 6e t. These are ign
23f0: 6f 72 65 64 0a 09 09 69 66 20 7b 21 5b 24 64 67 ored...if {![$dg
2400: 20 6e 6f 64 65 20 65 78 69 73 74 73 20 24 73 75 node exists $su
2410: 63 63 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 cc]} continue...
2420: 24 64 67 20 61 72 63 20 69 6e 73 65 72 74 20 24 $dg arc insert $
2430: 63 73 65 74 20 24 73 75 63 63 0a 09 20 20 20 20 cset $succ..
2440: 7d 0a 09 7d 0a 09 66 6f 72 65 61 63 68 20 63 73 }..}..foreach cs
2450: 65 74 20 24 70 72 65 20 7b 0a 09 20 20 20 20 66 et $pre {.. f
2460: 6f 72 65 61 63 68 20 73 75 63 63 20 5b 24 63 73 oreach succ [$cs
2470: 65 74 20 73 75 63 63 65 73 73 6f 72 73 5d 20 7b et successors] {
2480: 0a 09 09 23 20 4e 6f 74 65 20 74 68 61 74 20 74 ...# Note that t
2490: 68 65 20 61 72 63 20 6d 61 79 20 61 6c 72 65 61 he arc may alrea
24a0: 64 79 20 65 78 69 73 74 20 69 6e 20 74 68 65 20 dy exist in the
24b0: 67 72 61 70 68 2e 20 49 66 0a 09 09 23 20 73 6f graph. If...# so
24c0: 20 69 67 6e 6f 72 65 20 69 74 2e 20 54 68 65 20 ignore it. The
24d0: 6e 65 77 20 63 68 61 6e 67 65 73 65 74 73 20 6d new changesets m
24e0: 61 79 20 68 61 76 65 0a 09 09 23 20 64 65 70 65 ay have...# depe
24f0: 6e 64 65 6e 63 69 65 73 20 6f 75 74 73 69 64 65 ndencies outside
2500: 20 6f 66 20 74 68 65 20 63 68 6f 73 65 6e 20 73 of the chosen s
2510: 65 74 2e 20 54 68 65 73 65 20 61 72 65 0a 09 09 et. These are...
2520: 23 20 69 67 6e 6f 72 65 64 0a 09 09 69 66 20 7b # ignored...if {
2530: 21 5b 24 64 67 20 6e 6f 64 65 20 65 78 69 73 74 ![$dg node exist
2540: 73 20 24 73 75 63 63 5d 7d 20 63 6f 6e 74 69 6e s $succ]} contin
2550: 75 65 0a 09 09 69 66 20 7b 5b 48 61 73 41 72 63 ue...if {[HasArc
2560: 20 24 64 67 20 24 63 73 65 74 20 24 73 75 63 63 $dg $cset $succ
2570: 5d 7d 20 63 6f 6e 74 69 6e 75 65 3b 23 20 54 4f ]} continue;# TO
2580: 44 4f 20 73 68 6f 75 6c 64 20 62 65 20 67 72 61 DO should be gra
2590: 70 68 20 6d 65 74 68 6f 64 2e 0a 09 09 24 64 67 ph method....$dg
25a0: 20 61 72 63 20 69 6e 73 65 72 74 20 24 63 73 65 arc insert $cse
25b0: 74 20 24 73 75 63 63 0a 09 20 20 20 20 7d 0a 09 t $succ.. }..
25c0: 7d 0a 0a 09 4d 61 72 6b 20 24 64 67 20 2d 24 7b }...Mark $dg -${
25d0: 49 44 7d 2d 61 66 74 65 72 0a 09 72 65 74 75 72 ID}-after..retur
25e0: 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 20 54 n. }.. # T
25f0: 4f 44 4f 3a 20 54 68 69 73 20 73 68 6f 75 6c 64 ODO: This should
2600: 20 62 65 20 61 20 67 72 61 70 68 20 6d 65 74 68 be a graph meth
2610: 6f 64 2e 0a 20 20 20 20 70 72 6f 63 20 48 61 73 od.. proc Has
2620: 41 72 63 20 7b 64 67 20 61 20 62 7d 20 7b 0a 09 Arc {dg a b} {..
2630: 23 38 2e 35 3a 20 72 65 74 75 72 6e 20 5b 65 78 #8.5: return [ex
2640: 70 72 20 7b 24 62 20 69 6e 20 5b 24 64 67 20 6e pr {$b in [$dg n
2650: 6f 64 65 73 20 2d 6f 75 74 20 24 61 5d 7d 5d 0a odes -out $a]}].
2660: 09 69 66 20 7b 5b 6c 73 65 61 72 63 68 20 2d 65 .if {[lsearch -e
2670: 78 61 63 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 xact [$dg nodes
2680: 2d 6f 75 74 20 24 61 5d 20 24 62 5d 20 3c 20 30 -out $a] $b] < 0
2690: 7d 20 7b 20 72 65 74 75 72 6e 20 30 20 7d 0a 09 } { return 0 }..
26a0: 72 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a return 1. }..
26b0: 20 20 20 20 70 72 6f 63 20 4d 61 72 6b 20 7b 64 proc Mark {d
26c0: 67 20 7b 73 75 66 66 69 78 20 7b 7d 7d 7d 20 7b g {suffix {}}} {
26d0: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 64 ..::variable myd
26e0: 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 0a 09 69 otdestination..i
26f0: 66 20 7b 24 6d 79 64 6f 74 64 65 73 74 69 6e 61 f {$mydotdestina
2700: 74 69 6f 6e 20 65 71 20 22 22 7d 20 72 65 74 75 tion eq ""} retu
2710: 72 6e 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d rn..::variable m
2720: 79 64 6f 74 70 72 65 66 69 78 0a 09 3a 3a 76 61 ydotprefix..::va
2730: 72 69 61 62 6c 65 20 6d 79 64 6f 74 69 64 0a 09 riable mydotid..
2740: 73 65 74 20 66 6e 61 6d 65 20 24 6d 79 64 6f 74 set fname $mydot
2750: 64 65 73 74 69 6e 61 74 69 6f 6e 2f 24 7b 6d 79 destination/${my
2760: 64 6f 74 70 72 65 66 69 78 7d 24 7b 6d 79 64 6f dotprefix}${mydo
2770: 74 69 64 7d 24 7b 73 75 66 66 69 78 7d 2e 64 6f tid}${suffix}.do
2780: 74 0a 09 66 69 6c 65 20 6d 6b 64 69 72 20 5b 66 t..file mkdir [f
2790: 69 6c 65 20 64 69 72 6e 61 6d 65 20 24 66 6e 61 ile dirname $fna
27a0: 6d 65 5d 0a 09 64 6f 74 20 77 72 69 74 65 20 24 me]..dot write $
27b0: 64 67 20 24 6d 79 64 6f 74 70 72 65 66 69 78 24 dg $mydotprefix$
27c0: 73 75 66 66 69 78 20 24 66 6e 61 6d 65 0a 09 69 suffix $fname..i
27d0: 6e 63 72 20 6d 79 64 6f 74 69 64 0a 0a 09 6c 6f ncr mydotid...lo
27e0: 67 20 77 72 69 74 65 20 35 20 63 79 63 6c 65 62 g write 5 cycleb
27f0: 72 65 61 6b 65 72 20 22 2e 64 6f 74 20 65 78 70 reaker ".dot exp
2800: 6f 72 74 20 24 66 6e 61 6d 65 22 0a 09 72 65 74 ort $fname"..ret
2810: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 23 urn. }.. #
2820: 20 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 # ## ### #####
2830: 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 ######## #######
2840: 23 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 61 ######. ## Ca
2850: 6c 6c 62 61 63 6b 20 69 6e 76 6f 6b 61 74 69 6f llback invokatio
2860: 6e 20 2e 2e 2e 0a 0a 20 20 20 20 70 72 6f 63 20 n ..... proc
2870: 50 72 6f 63 65 73 73 65 64 48 6f 6f 6b 20 7b 63 ProcessedHook {c
2880: 73 65 74 20 70 6f 73 7d 20 7b 0a 09 23 20 47 69 set pos} {..# Gi
2890: 76 65 20 74 68 65 20 75 73 65 72 20 6f 66 20 74 ve the user of t
28a0: 68 65 20 63 79 63 6c 65 20 62 72 65 61 6b 65 72 he cycle breaker
28b0: 20 74 68 65 20 6f 70 70 6f 72 74 75 6e 69 74 79 the opportunity
28c0: 20 74 6f 20 77 6f 72 6b 0a 09 23 20 77 69 74 68 to work..# with
28d0: 20 74 68 65 20 63 68 61 6e 67 65 73 65 74 20 62 the changeset b
28e0: 65 66 6f 72 65 20 69 74 20 69 73 20 72 65 6d 6f efore it is remo
28f0: 76 65 64 20 66 72 6f 6d 20 74 68 65 20 67 72 61 ved from the gra
2900: 70 68 2e 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 ph....::variable
2910: 20 6d 79 73 61 76 65 63 6d 64 0a 09 69 66 20 7b mysavecmd..if {
2920: 21 5b 6c 6c 65 6e 67 74 68 20 24 6d 79 73 61 76 ![llength $mysav
2930: 65 63 6d 64 5d 7d 20 72 65 74 75 72 6e 0a 0a 09 ecmd]} return...
2940: 75 70 6c 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 uplevel #0 [lins
2950: 65 72 74 20 24 6d 79 73 61 76 65 63 6d 64 20 65 ert $mysavecmd e
2960: 6e 64 20 24 70 6f 73 20 24 63 73 65 74 5d 0a 09 nd $pos $cset]..
2970: 72 65 74 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 return. }..
2980: 20 20 70 72 6f 63 20 42 72 65 61 6b 43 79 63 6c proc BreakCycl
2990: 65 48 6f 6f 6b 20 7b 67 72 61 70 68 7d 20 7b 0a eHook {graph} {.
29a0: 09 23 20 43 61 6c 6c 20 6f 75 74 20 74 6f 20 74 .# Call out to t
29b0: 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 6f 72 69 he chosen algori
29c0: 74 68 6d 20 66 6f 72 20 63 79 63 6c 65 20 62 72 thm for cycle br
29d0: 65 61 6b 69 6e 67 2e 20 46 69 6e 64 69 6e 67 0a eaking. Finding.
29e0: 09 23 20 61 20 63 79 63 6c 65 20 69 66 20 6e 6f .# a cycle if no
29f0: 20 62 72 65 61 6b 65 72 20 77 61 73 20 63 68 6f breaker was cho
2a00: 73 65 6e 20 69 73 20 61 6e 20 65 72 72 6f 72 2e sen is an error.
2a10: 0a 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 ...::variable my
2a20: 62 72 65 61 6b 63 6d 64 0a 09 69 66 20 7b 21 5b breakcmd..if {![
2a30: 6c 6c 65 6e 67 74 68 20 24 6d 79 62 72 65 61 6b llength $mybreak
2a40: 63 6d 64 5d 7d 20 7b 0a 09 20 20 20 20 74 72 6f cmd]} {.. tro
2a50: 75 62 6c 65 20 66 61 74 61 6c 20 22 46 6f 75 6e uble fatal "Foun
2a60: 64 20 61 20 63 79 63 6c 65 2c 20 65 78 70 65 63 d a cycle, expec
2a70: 74 69 6e 67 20 6e 6f 6e 65 2e 22 0a 09 20 20 20 ting none."..
2a80: 20 65 78 69 74 20 31 0a 09 7d 0a 0a 09 75 70 6c exit 1..}...upl
2a90: 65 76 65 6c 20 23 30 20 5b 6c 69 6e 73 65 72 74 evel #0 [linsert
2aa0: 20 24 6d 79 62 72 65 61 6b 63 6d 64 20 65 6e 64 $mybreakcmd end
2ab0: 20 24 67 72 61 70 68 5d 0a 09 72 65 74 75 72 6e $graph]..return
2ac0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72 6f 63 . }.. proc
2ad0: 20 43 6c 65 61 72 48 6f 6f 6b 73 20 7b 7d 20 7b ClearHooks {} {
2ae0: 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 6d 79 73 ..::variable mys
2af0: 61 76 65 63 6d 64 20 20 7b 7d 0a 09 3a 3a 76 61 avecmd {}..::va
2b00: 72 69 61 62 6c 65 20 6d 79 62 72 65 61 6b 63 6d riable mybreakcm
2b10: 64 20 7b 7d 0a 09 72 65 74 75 72 6e 0a 20 20 20 d {}..return.
2b20: 20 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 }.. # # ## #
2b30: 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 ## ##### #######
2b40: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a # #############.
2b50: 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 62 6c . typevariabl
2b60: 65 20 6d 79 61 74 20 20 20 20 20 20 30 20 3b 20 e myat 0 ;
2b70: 23 20 43 6f 75 6e 74 65 72 20 66 6f 72 20 63 6f # Counter for co
2b80: 6d 6d 69 74 20 69 64 73 20 66 6f 72 20 74 68 65 mmit ids for the
2b90: 0a 09 09 09 20 20 20 20 20 20 20 23 20 63 68 61 .... # cha
2ba0: 6e 67 65 73 65 74 73 2e 0a 20 20 20 20 74 79 70 ngesets.. typ
2bb0: 65 76 61 72 69 61 62 6c 65 20 6d 79 62 6f 74 74 evariable mybott
2bc0: 6f 6d 20 7b 7d 20 3b 20 23 20 4c 69 73 74 20 6f om {} ; # List o
2bd0: 66 20 74 68 65 20 63 61 6e 64 69 64 61 74 65 20 f the candidate
2be0: 6e 6f 64 65 73 20 66 6f 72 0a 09 09 09 20 20 20 nodes for....
2bf0: 20 20 20 20 23 20 63 6f 6d 6d 69 74 74 69 6e 67 # committing
2c00: 2e 0a 0a 20 20 20 20 74 79 70 65 76 61 72 69 61 ... typevaria
2c10: 62 6c 65 20 6d 79 73 61 76 65 63 6d 64 20 20 7b ble mysavecmd {
2c20: 7d 20 3b 20 23 20 43 61 6c 6c 62 61 63 6b 2c 20 } ; # Callback,
2c30: 66 6f 72 20 65 61 63 68 20 70 72 6f 63 65 73 73 for each process
2c40: 65 64 20 6e 6f 64 65 2e 0a 20 20 20 20 74 79 70 ed node.. typ
2c50: 65 76 61 72 69 61 62 6c 65 20 6d 79 62 72 65 61 evariable mybrea
2c60: 6b 63 6d 64 20 7b 7d 20 3b 20 23 20 43 61 6c 6c kcmd {} ; # Call
2c70: 62 61 63 6b 2c 20 66 6f 72 20 65 61 63 68 20 66 back, for each f
2c80: 6f 75 6e 64 20 63 79 63 6c 65 2e 0a 0a 20 20 20 ound cycle...
2c90: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
2ca0: 64 6f 74 64 65 73 74 69 6e 61 74 69 6f 6e 20 7b dotdestination {
2cb0: 7d 20 3b 20 23 20 44 65 73 74 69 6e 61 74 69 6f } ; # Destinatio
2cc0: 6e 20 64 69 72 65 63 74 6f 72 79 20 66 6f 72 20 n directory for
2cd0: 74 68 65 0a 09 09 09 09 20 20 20 20 20 20 20 23 the..... #
2ce0: 20 67 65 6e 65 72 61 74 65 64 20 2e 64 6f 74 20 generated .dot
2cf0: 66 69 6c 65 73 2e 0a 20 20 20 20 74 79 70 65 76 files.. typev
2d00: 61 72 69 61 62 6c 65 20 6d 79 64 6f 74 70 72 65 ariable mydotpre
2d10: 66 69 78 20 20 20 20 20 20 7b 7d 20 3b 20 23 20 fix {} ; #
2d20: 50 72 65 66 69 78 20 66 6f 72 20 64 6f 74 20 66 Prefix for dot f
2d30: 69 6c 65 73 20 77 68 65 6e 0a 09 09 09 09 20 20 iles when.....
2d40: 20 20 20 20 20 23 20 65 78 70 6f 72 74 69 6e 67 # exporting
2d50: 20 74 68 65 20 67 72 61 70 68 73 2e 0a 20 20 20 the graphs..
2d60: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 6d 79 typevariable my
2d70: 64 6f 74 69 64 20 20 20 20 20 20 20 20 20 20 20 dotid
2d80: 30 20 3b 20 23 20 43 6f 75 6e 74 65 72 20 66 6f 0 ; # Counter fo
2d90: 72 20 64 6f 74 20 66 69 6c 65 20 6e 61 6d 65 0a r dot file name.
2da0: 09 09 09 09 20 20 20 20 20 20 20 23 20 67 65 6e .... # gen
2db0: 65 72 61 74 69 6f 6e 2e 0a 0a 20 20 20 20 23 20 eration... #
2dc0: 23 20 23 23 20 23 23 23 20 23 23 23 23 23 20 23 # ## ### ##### #
2dd0: 23 23 23 23 23 23 23 20 23 23 23 23 23 23 23 23 ####### ########
2de0: 23 23 23 23 23 0a 20 20 20 20 23 23 20 43 6f 6e #####. ## Con
2df0: 66 69 67 75 72 61 74 69 6f 6e 0a 0a 20 20 20 20 figuration..
2e00: 70 72 61 67 6d 61 20 2d 68 61 73 69 6e 73 74 61 pragma -hasinsta
2e10: 6e 63 65 73 20 20 20 6e 6f 20 3b 20 23 20 73 69 nces no ; # si
2e20: 6e 67 6c 65 74 6f 6e 0a 20 20 20 20 70 72 61 67 ngleton. prag
2e30: 6d 61 20 2d 68 61 73 74 79 70 65 69 6e 66 6f 20 ma -hastypeinfo
2e40: 20 20 20 6e 6f 20 3b 20 23 20 6e 6f 20 69 6e 74 no ; # no int
2e50: 72 6f 73 70 65 63 74 69 6f 6e 0a 20 20 20 20 70 rospection. p
2e60: 72 61 67 6d 61 20 2d 68 61 73 74 79 70 65 64 65 ragma -hastypede
2e70: 73 74 72 6f 79 20 6e 6f 20 3b 20 23 20 69 6d 6d stroy no ; # imm
2e80: 6f 72 74 61 6c 0a 0a 20 20 20 20 23 20 23 20 23 ortal.. # # #
2e90: 23 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 # ### ##### ####
2ea0: 23 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 #### ###########
2eb0: 23 23 0a 7d 0a 0a 6e 61 6d 65 73 70 61 63 65 20 ##.}..namespace
2ec0: 65 76 61 6c 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 eval ::vc::fossi
2ed0: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 20 7b l::import::cvs {
2ee0: 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 65 . namespace e
2ef0: 78 70 6f 72 74 20 63 79 63 6c 65 62 72 65 61 6b xport cyclebreak
2f00: 65 72 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 er. namespace
2f10: 20 65 76 61 6c 20 63 79 63 6c 65 62 72 65 61 6b eval cyclebreak
2f20: 65 72 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 20 er {..namespace
2f30: 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b 0a 09 eval project {..
2f40: 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d namespace im
2f50: 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 port ::vc::fossi
2f60: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a l::import::cvs::
2f70: 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a 09 20 20 project::rev..
2f80: 20 20 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 6f namespace impo
2f90: 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a rt ::vc::fossil:
2fa0: 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 72 :import::cvs::pr
2fb0: 6f 6a 65 63 74 3a 3a 72 65 76 6c 69 6e 6b 0a 09 oject::revlink..
2fc0: 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70 }..namespace imp
2fd0: 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a ort ::vc::tools:
2fe0: 3a 6d 69 73 63 3a 3a 2a 0a 09 6e 61 6d 65 73 70 :misc::*..namesp
2ff0: 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a 76 63 3a ace import ::vc:
3000: 3a 74 6f 6f 6c 73 3a 3a 6c 6f 67 0a 09 6e 61 6d :tools::log..nam
3010: 65 73 70 61 63 65 20 69 6d 70 6f 72 74 20 3a 3a espace import ::
3020: 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 74 72 6f 75 62 vc::tools::troub
3030: 6c 65 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d le..namespace im
3040: 70 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 port ::vc::tools
3050: 3a 3a 64 6f 74 0a 09 6c 6f 67 20 72 65 67 69 73 ::dot..log regis
3060: 74 65 72 20 63 79 63 6c 65 62 72 65 61 6b 65 72 ter cyclebreaker
3070: 0a 20 20 20 20 7d 0a 7d 0a 0a 23 20 23 20 23 23 . }.}..# # ##
3080: 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 ### ##### #####
3090: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 ### ############
30a0: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 23 # ##############
30b0: 23 23 23 23 23 23 23 0a 23 23 20 52 65 61 64 79 #######.## Ready
30c0: 0a 0a 70 61 63 6b 61 67 65 20 70 72 6f 76 69 64 ..package provid
30d0: 65 20 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d e vc::fossil::im
30e0: 70 6f 72 74 3a 3a 63 76 73 3a 3a 63 79 63 6c 65 port::cvs::cycle
30f0: 62 72 65 61 6b 65 72 20 31 2e 30 0a 72 65 74 75 breaker 1.0.retu
3100: 72 6e 0a rn.