Artifact 0d5836726f709e16e14949aa4497f29e31d4a0c5:

File tools/cvs2fossil/lib/c2f_pbreakrcycle.tcl part of check-in [85bd219d0b] - Continued work on pass 6. Completed creation of changeset graph (nodes, dependencies), started on topological iteration and breaking cycles. Basic iteration is complete, fiding a cycle ditto. Not yet done is to actually break a found cycle. Extended the changeset class with the necessary accessor methods (getting cset type, successors, time range). Note: Looking at my code it may be that my decision to save the cset order caused this pass to subsume the RevisionTopologicalSortPass of cvs2svn. Check again when I am done. Note 2: The test case (tcl repository, tcl project) had no cycles. by aku on 2007-11-13 07:22:35.

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 50 61 73  ########..## Pas
0200: 73 20 56 49 2e 20 54 68 69 73 20 70 61 73 73 20  s VI. This pass 
0210: 67 6f 65 73 20 6f 76 65 72 20 74 68 65 20 73 65  goes over the se
0220: 74 20 6f 66 20 72 65 76 69 73 69 6f 6e 20 62 61  t of revision ba
0230: 73 65 64 20 63 68 61 6e 67 65 73 65 74 73 0a 23  sed changesets.#
0240: 23 20 61 6e 64 20 62 72 65 61 6b 73 20 61 6c 6c  # and breaks all
0250: 20 64 65 70 65 6e 64 65 6e 63 79 20 63 79 63 6c   dependency cycl
0260: 65 73 20 74 68 65 79 20 6d 61 79 20 62 65 20 69  es they may be i
0270: 6e 2e 20 57 65 20 6e 65 65 64 20 61 0a 23 23 20  n. We need a.## 
0280: 64 65 70 65 6e 64 65 6e 63 79 20 74 72 65 65 2e  dependency tree.
0290: 0a 0a 23 20 23 20 23 23 20 23 23 23 20 23 23 23  ..# # ## ### ###
02a0: 23 23 20 23 23 23 23 23 23 23 23 20 23 23 23 23  ## ######## ####
02b0: 23 23 23 23 23 23 23 23 23 20 23 23 23 23 23 23  ######### ######
02c0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 0a  ###############.
02d0: 23 23 20 52 65 71 75 69 72 65 6d 65 6e 74 73 0a  ## Requirements.
02e0: 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 65  .package require
02f0: 20 54 63 6c 20 38 2e 34 20 20 20 20 20 20 20 20   Tcl 8.4        
0300: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0310: 20 20 20 20 20 20 20 3b 20 23 20 52 65 71 75 69         ; # Requi
0320: 72 65 64 20 72 75 6e 74 69 6d 65 2e 0a 70 61 63  red runtime..pac
0330: 6b 61 67 65 20 72 65 71 75 69 72 65 20 73 6e 69  kage require sni
0340: 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t               
0350: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0360: 20 20 20 3b 20 23 20 4f 4f 20 73 79 73 74 65 6d     ; # OO system
0370: 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75 69 72  ..package requir
0380: 65 20 73 74 72 75 63 74 3a 3a 67 72 61 70 68 20  e struct::graph 
0390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
03a0: 20 20 20 20 20 20 20 20 3b 20 23 20 47 72 61 70          ; # Grap
03b0: 68 20 68 61 6e 64 6c 69 6e 67 2e 0a 70 61 63 6b  h handling..pack
03c0: 61 67 65 20 72 65 71 75 69 72 65 20 73 74 72 75  age require stru
03d0: 63 74 3a 3a 6c 69 73 74 20 20 20 20 20 20 20 20  ct::list        
03e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
03f0: 20 20 3b 20 23 20 48 69 67 68 65 72 20 6f 72 64    ; # Higher ord
0400: 65 72 20 6c 69 73 74 20 6f 70 65 72 61 74 69 6f  er list operatio
0410: 6e 73 2e 0a 70 61 63 6b 61 67 65 20 72 65 71 75  ns..package requ
0420: 69 72 65 20 76 63 3a 3a 74 6f 6f 6c 73 3a 3a 6c  ire vc::tools::l
0430: 6f 67 20 20 20 20 20 20 20 20 20 20 20 20 20 20  og              
0440: 20 20 20 20 20 20 20 20 20 20 3b 20 23 20 55 73            ; # Us
0450: 65 72 20 66 65 65 64 62 61 63 6b 2e 0a 70 61 63  er feedback..pac
0460: 6b 61 67 65 20 72 65 71 75 69 72 65 20 76 63 3a  kage require vc:
0470: 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a  :fossil::import:
0480: 3a 63 76 73 3a 3a 73 74 61 74 65 20 20 20 20 20  :cvs::state     
0490: 20 20 20 3b 20 23 20 53 74 61 74 65 20 73 74 6f     ; # State sto
04a0: 72 61 67 65 2e 0a 70 61 63 6b 61 67 65 20 72 65  rage..package re
04b0: 71 75 69 72 65 20 76 63 3a 3a 66 6f 73 73 69 6c  quire vc::fossil
04c0: 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a 70  ::import::cvs::p
04d0: 72 6f 6a 65 63 74 3a 3a 72 65 76 20 3b 20 23 20  roject::rev ; # 
04e0: 50 72 6f 6a 65 63 74 20 6c 65 76 65 6c 20 63 68  Project level ch
04f0: 61 6e 67 65 73 65 74 73 0a 0a 23 20 23 20 23 23  angesets..# # ##
0500: 20 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23   ### ##### #####
0510: 23 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23  ### ############
0520: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 23  # ##############
0530: 23 23 23 23 23 23 23 0a 23 23 20 52 65 67 69 73  #######.## Regis
0540: 74 65 72 20 74 68 65 20 70 61 73 73 20 77 69 74  ter the pass wit
0550: 68 20 74 68 65 20 6d 61 6e 61 67 65 6d 65 6e 74  h the management
0560: 0a 0a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d  ..vc::fossil::im
0570: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 61 73 73 20  port::cvs::pass 
0580: 64 65 66 69 6e 65 20 5c 0a 20 20 20 20 42 72 65  define \.    Bre
0590: 61 6b 52 65 76 43 73 65 74 43 79 63 6c 65 73 20  akRevCsetCycles 
05a0: 5c 0a 20 20 20 20 7b 42 72 65 61 6b 20 52 65 76  \.    {Break Rev
05b0: 69 73 69 6f 6e 20 43 68 61 6e 67 65 53 65 74 20  ision ChangeSet 
05c0: 44 65 70 65 6e 64 65 6e 63 79 20 43 79 63 6c 65  Dependency Cycle
05d0: 73 7d 20 5c 0a 20 20 20 20 3a 3a 76 63 3a 3a 66  s} \.    ::vc::f
05e0: 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63  ossil::import::c
05f0: 76 73 3a 3a 70 61 73 73 3a 3a 62 72 65 61 6b 72  vs::pass::breakr
0600: 63 79 63 6c 65 0a 0a 23 20 23 20 23 23 20 23 23  cycle..# # ## ##
0610: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23  # ##### ########
0620: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 20 23   ############# #
0630: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23  ################
0640: 23 23 23 23 0a 23 23 20 0a 0a 73 6e 69 74 3a 3a  ####.## ..snit::
0650: 74 79 70 65 20 3a 3a 76 63 3a 3a 66 6f 73 73 69  type ::vc::fossi
0660: 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a 3a  l::import::cvs::
0670: 70 61 73 73 3a 3a 62 72 65 61 6b 72 63 79 63 6c  pass::breakrcycl
0680: 65 20 7b 0a 20 20 20 20 23 20 23 20 23 23 20 23  e {.    # # ## #
0690: 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23  ## ##### #######
06a0: 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a  # #############.
06b0: 20 20 20 20 23 23 20 50 75 62 6c 69 63 20 41 50      ## Public AP
06c0: 49 0a 0a 20 20 20 20 74 79 70 65 6d 65 74 68 6f  I..    typemetho
06d0: 64 20 73 65 74 75 70 20 7b 7d 20 7b 0a 09 23 20  d setup {} {..# 
06e0: 44 65 66 69 6e 65 20 74 68 65 20 6e 61 6d 65 73  Define the names
06f0: 20 61 6e 64 20 73 74 72 75 63 74 75 72 65 20 6f   and structure o
0700: 66 20 74 68 65 20 70 65 72 73 69 73 74 65 6e 74  f the persistent
0710: 20 73 74 61 74 65 20 6f 66 0a 09 23 20 74 68 69   state of..# thi
0720: 73 20 70 61 73 73 2e 0a 0a 09 73 74 61 74 65 20  s pass....state 
0730: 77 72 69 74 69 6e 67 20 63 73 6f 72 64 65 72 20  writing csorder 
0740: 7b 0a 09 20 20 20 20 2d 2d 20 43 6f 6d 6d 69 74  {..    -- Commit
0750: 20 6f 72 64 65 72 20 6f 66 20 63 68 61 6e 67 65   order of change
0760: 73 65 74 73 20 62 61 73 65 64 20 6f 6e 20 74 68  sets based on th
0770: 65 69 72 20 64 65 70 65 6e 64 65 6e 63 69 65 73  eir dependencies
0780: 0a 09 20 20 20 20 63 69 64 20 49 4e 54 45 47 45  ..    cid INTEGE
0790: 52 20 20 4e 4f 54 20 4e 55 4c 4c 20 20 52 45 46  R  NOT NULL  REF
07a0: 45 52 45 4e 43 45 53 20 63 68 61 6e 67 65 73 65  ERENCES changese
07b0: 74 2c 0a 09 20 20 20 20 70 6f 73 20 49 4e 54 45  t,..    pos INTE
07c0: 47 45 52 20 20 4e 4f 54 20 4e 55 4c 4c 2c 0a 09  GER  NOT NULL,..
07d0: 20 20 20 20 55 4e 49 51 55 45 20 28 63 69 64 29      UNIQUE (cid)
07e0: 2c 0a 09 20 20 20 20 55 4e 49 51 55 45 20 28 70  ,..    UNIQUE (p
07f0: 6f 73 29 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 0a  os)..}...return.
0800: 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d      }..    typem
0810: 65 74 68 6f 64 20 6c 6f 61 64 20 7b 7d 20 7b 0a  ethod load {} {.
0820: 09 23 20 50 61 73 73 20 6d 61 6e 61 67 65 72 20  .# Pass manager 
0830: 69 6e 74 65 72 66 61 63 65 2e 20 45 78 65 63 75  interface. Execu
0840: 74 65 64 20 74 6f 20 6c 6f 61 64 20 64 61 74 61  ted to load data
0850: 20 63 6f 6d 70 75 74 65 64 20 62 79 0a 09 23 20   computed by..# 
0860: 74 68 69 73 20 70 61 73 73 20 69 6e 74 6f 20 6d  this pass into m
0870: 65 6d 6f 72 79 20 77 68 65 6e 20 74 68 69 73 20  emory when this 
0880: 70 61 73 73 20 69 73 20 73 6b 69 70 70 65 64 20  pass is skipped 
0890: 69 6e 73 74 65 61 64 20 6f 66 0a 09 23 20 65 78  instead of..# ex
08a0: 65 63 75 74 65 64 2e 0a 09 72 65 74 75 72 6e 0a  ecuted...return.
08b0: 20 20 20 20 7d 0a 0a 20 20 20 20 74 79 70 65 6d      }..    typem
08c0: 65 74 68 6f 64 20 72 75 6e 20 7b 7d 20 7b 0a 09  ethod run {} {..
08d0: 23 20 50 61 73 73 20 6d 61 6e 61 67 65 72 20 69  # Pass manager i
08e0: 6e 74 65 72 66 61 63 65 2e 20 45 78 65 63 75 74  nterface. Execut
08f0: 65 64 20 74 6f 20 70 65 72 66 6f 72 6d 20 74 68  ed to perform th
0900: 65 0a 09 23 20 66 75 6e 63 74 69 6f 6e 61 6c 69  e..# functionali
0910: 74 79 20 6f 66 20 74 68 65 20 70 61 73 73 2e 0a  ty of the pass..
0920: 0a 09 73 74 61 74 65 20 72 65 61 64 69 6e 67 20  ..state reading 
0930: 72 65 76 69 73 69 6f 6e 0a 0a 09 23 20 57 65 20  revision...# We 
0940: 63 72 65 61 74 65 20 61 20 67 72 61 70 68 20 6f  create a graph o
0950: 66 20 74 68 65 20 72 65 76 69 73 69 6f 6e 20 63  f the revision c
0960: 68 61 6e 67 65 73 65 74 73 2c 20 75 73 69 6e 67  hangesets, using
0970: 20 74 68 65 20 66 69 6c 65 0a 09 23 20 6c 65 76   the file..# lev
0980: 65 6c 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20  el dependencies 
0990: 74 6f 20 63 6f 6e 73 74 72 75 63 74 20 61 20 66  to construct a f
09a0: 69 72 73 74 20 61 70 70 72 6f 78 69 6d 61 74 69  irst approximati
09b0: 6f 6e 20 6f 66 0a 09 23 20 74 68 65 6d 20 61 74  on of..# them at
09c0: 20 74 68 65 20 70 72 6f 6a 65 63 74 20 6c 65 76   the project lev
09d0: 65 6c 2e 20 54 68 65 6e 20 6c 6f 6f 6b 20 66 6f  el. Then look fo
09e0: 72 20 63 79 63 6c 65 73 20 69 6e 20 74 68 61 74  r cycles in that
09f0: 0a 09 23 20 67 72 61 70 68 20 61 6e 64 20 62 72  ..# graph and br
0a00: 65 61 6b 20 74 68 65 6d 2e 0a 0a 09 23 20 31 2e  eak them....# 1.
0a10: 20 43 72 65 61 74 65 20 6e 6f 64 65 73 20 66 6f   Create nodes fo
0a20: 72 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63  r all relevant c
0a30: 68 61 6e 67 65 73 65 74 73 20 61 6e 64 20 61 20  hangesets and a 
0a40: 6d 61 70 70 69 6e 67 0a 09 23 20 20 20 20 66 72  mapping..#    fr
0a50: 6f 6d 20 74 68 65 20 72 65 76 69 73 69 6f 6e 73  om the revisions
0a60: 20 74 6f 20 74 68 65 69 72 20 63 68 61 6e 67 65   to their change
0a70: 73 65 74 73 2f 6e 6f 64 65 73 2e 0a 0a 09 6c 6f  sets/nodes....lo
0a80: 67 20 77 72 69 74 65 20 33 20 62 72 6b 72 63 79  g write 3 brkrcy
0a90: 63 6c 65 20 7b 43 72 65 61 74 69 6e 67 20 63 68  cle {Creating ch
0aa0: 61 6e 67 65 73 65 74 20 67 72 61 70 68 2c 20 66  angeset graph, f
0ab0: 69 6c 6c 69 6e 67 20 77 69 74 68 20 6e 6f 64 65  illing with node
0ac0: 73 7d 0a 0a 09 73 65 74 20 64 67 20 5b 73 74 72  s}...set dg [str
0ad0: 75 63 74 3a 3a 67 72 61 70 68 20 64 67 5d 0a 0a  uct::graph dg]..
0ae0: 09 73 74 61 74 65 20 74 72 61 6e 73 61 63 74 69  .state transacti
0af0: 6f 6e 20 7b 0a 09 20 20 20 20 66 6f 72 65 61 63  on {..    foreac
0b00: 68 20 63 73 65 74 20 5b 70 72 6f 6a 65 63 74 3a  h cset [project:
0b10: 3a 72 65 76 20 61 6c 6c 5d 20 7b 0a 09 09 69 66  :rev all] {...if
0b20: 20 7b 5b 24 63 73 65 74 20 62 79 73 79 6d 62 6f   {[$cset bysymbo
0b30: 6c 5d 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 09 64  l]} continue...d
0b40: 67 20 6e 6f 64 65 20 69 6e 73 65 72 74 20 24 63  g node insert $c
0b50: 73 65 74 0a 09 09 64 67 20 6e 6f 64 65 20 73 65  set...dg node se
0b60: 74 20 20 20 20 24 63 73 65 74 20 74 69 6d 65 72  t    $cset timer
0b70: 61 6e 67 65 20 5b 24 63 73 65 74 20 74 69 6d 65  ange [$cset time
0b80: 72 61 6e 67 65 5d 0a 09 20 20 20 20 7d 0a 09 7d  range]..    }..}
0b90: 0a 0a 09 23 20 32 2e 20 46 69 6e 64 20 66 6f 72  ...# 2. Find for
0ba0: 20 61 6c 6c 20 72 65 6c 65 76 61 6e 74 20 63 68   all relevant ch
0bb0: 61 6e 67 65 73 65 74 20 74 68 65 69 72 20 72 65  angeset their re
0bc0: 76 69 73 69 6f 6e 73 20 61 6e 64 20 74 68 65 69  visions and thei
0bd0: 72 0a 09 23 20 20 20 20 64 65 70 65 6e 64 65 6e  r..#    dependen
0be0: 63 69 65 73 2e 20 4d 61 70 20 74 68 65 20 6c 61  cies. Map the la
0bf0: 74 74 65 72 20 62 61 63 6b 20 74 6f 20 63 68 61  tter back to cha
0c00: 6e 67 65 73 65 74 73 20 61 6e 64 0a 09 23 20 20  ngesets and..#  
0c10: 20 20 63 6f 6e 73 74 72 75 63 74 20 74 68 65 20    construct the 
0c20: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 61 72  corresponding ar
0c30: 63 73 2e 0a 0a 09 6c 6f 67 20 77 72 69 74 65 20  cs....log write 
0c40: 33 20 62 72 6b 72 63 79 63 6c 65 20 7b 53 65 74  3 brkrcycle {Set
0c50: 74 69 6e 67 20 75 70 20 6e 6f 64 65 20 64 65 70  ting up node dep
0c60: 65 6e 64 65 6e 63 69 65 73 7d 0a 0a 09 73 74 61  endencies}...sta
0c70: 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 7b  te transaction {
0c80: 0a 09 20 20 20 20 66 6f 72 65 61 63 68 20 63 73  ..    foreach cs
0c90: 65 74 20 5b 70 72 6f 6a 65 63 74 3a 3a 72 65 76  et [project::rev
0ca0: 20 61 6c 6c 5d 20 7b 0a 09 09 69 66 20 7b 5b 24   all] {...if {[$
0cb0: 63 73 65 74 20 62 79 73 79 6d 62 6f 6c 5d 7d 20  cset bysymbol]} 
0cc0: 63 6f 6e 74 69 6e 75 65 0a 09 09 66 6f 72 65 61  continue...forea
0cd0: 63 68 20 73 75 63 63 20 5b 24 63 73 65 74 20 73  ch succ [$cset s
0ce0: 75 63 63 65 73 73 6f 72 73 5d 20 7b 0a 09 09 20  uccessors] {... 
0cf0: 20 20 20 64 67 20 61 72 63 20 69 6e 73 65 72 74     dg arc insert
0d00: 20 24 63 73 65 74 20 24 73 75 63 63 0a 09 09 7d   $cset $succ...}
0d10: 0a 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 23 20 33  ..    }..}...# 3
0d20: 2e 20 4c 61 73 74 6c 79 20 77 65 20 69 74 65 72  . Lastly we iter
0d30: 61 74 65 20 74 68 65 20 67 72 61 70 68 20 74 6f  ate the graph to
0d40: 70 6f 6c 6f 67 69 63 61 6c 6c 79 2e 20 57 65 20  pologically. We 
0d50: 6d 61 72 6b 20 6f 66 66 0a 09 23 20 20 20 20 74  mark off..#    t
0d60: 68 65 20 6e 6f 64 65 73 20 77 68 69 63 68 20 68  he nodes which h
0d70: 61 76 65 20 6e 6f 20 70 72 65 64 65 63 65 73 73  ave no predecess
0d80: 6f 72 73 2c 20 69 6e 20 6f 72 64 65 72 20 66 72  ors, in order fr
0d90: 6f 6d 0a 09 23 20 20 20 20 6f 6c 64 65 73 74 20  om..#    oldest 
0da0: 74 6f 20 79 6f 75 6e 67 65 73 74 2c 20 73 61 76  to youngest, sav
0db0: 69 6e 67 20 61 6e 64 20 72 65 6d 6f 76 69 6e 67  ing and removing
0dc0: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 2e 20 49   dependencies. I
0dd0: 66 0a 09 23 20 20 20 20 77 65 20 66 69 6e 64 20  f..#    we find 
0de0: 6e 6f 20 6e 6f 64 65 73 20 77 69 74 68 6f 75 74  no nodes without
0df0: 20 70 72 65 64 65 63 65 73 73 6f 72 73 20 77 65   predecessors we
0e00: 20 68 61 76 65 20 61 20 63 79 63 6c 65 2c 0a 09   have a cycle,..
0e10: 23 20 20 20 20 61 6e 64 20 77 6f 72 6b 20 6f 6e  #    and work on
0e20: 20 62 72 65 61 6b 69 6e 67 20 69 74 2e 0a 0a 09   breaking it....
0e30: 6c 6f 67 20 77 72 69 74 65 20 33 20 62 72 6b 72  log write 3 brkr
0e40: 63 79 63 6c 65 20 7b 43 6f 6d 70 75 74 69 6e 67  cycle {Computing
0e50: 20 63 68 61 6e 67 65 73 65 74 20 6f 72 64 65 72   changeset order
0e60: 2c 20 62 72 65 61 6b 69 6e 67 20 63 79 63 6c 65  , breaking cycle
0e70: 73 7d 0a 0a 09 49 6e 69 74 69 61 6c 69 7a 65 43  s}...InitializeC
0e80: 61 6e 64 69 64 61 74 65 73 20 24 64 67 0a 09 73  andidates $dg..s
0e90: 74 61 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e  tate transaction
0ea0: 20 7b 0a 09 20 20 20 20 77 68 69 6c 65 20 7b 31   {..    while {1
0eb0: 7d 20 7b 0a 09 09 77 68 69 6c 65 20 7b 5b 57 69  } {...while {[Wi
0ec0: 74 68 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72  thoutPredecessor
0ed0: 20 24 64 67 20 6e 5d 7d 20 7b 0a 09 09 20 20 20   $dg n]} {...   
0ee0: 20 53 61 76 65 41 6e 64 52 65 6d 6f 76 65 20 24   SaveAndRemove $
0ef0: 64 67 20 24 6e 0a 09 09 7d 0a 09 09 69 66 20 7b  dg $n...}...if {
0f00: 21 5b 6c 6c 65 6e 67 74 68 20 5b 64 67 20 6e 6f  ![llength [dg no
0f10: 64 65 73 5d 5d 7d 20 62 72 65 61 6b 0a 09 09 73  des]]} break...s
0f20: 65 74 20 63 79 63 6c 65 20 5b 46 69 6e 64 43 79  et cycle [FindCy
0f30: 63 6c 65 20 24 64 67 5d 0a 09 09 42 72 65 61 6b  cle $dg]...Break
0f40: 43 79 63 6c 65 20 24 64 67 20 24 63 79 63 6c 65  Cycle $dg $cycle
0f50: 0a 09 20 20 20 20 7d 0a 09 7d 0a 0a 09 72 65 74  ..    }..}...ret
0f60: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 74  urn.    }..    t
0f70: 79 70 65 6d 65 74 68 6f 64 20 64 69 73 63 61 72  ypemethod discar
0f80: 64 20 7b 7d 20 7b 0a 09 23 20 50 61 73 73 20 6d  d {} {..# Pass m
0f90: 61 6e 61 67 65 72 20 69 6e 74 65 72 66 61 63 65  anager interface
0fa0: 2e 20 45 78 65 63 75 74 65 64 20 66 6f 72 20 61  . Executed for a
0fb0: 6c 6c 20 70 61 73 73 65 73 20 61 66 74 65 72 20  ll passes after 
0fc0: 74 68 65 0a 09 23 20 72 75 6e 20 70 61 73 73 65  the..# run passe
0fd0: 73 2c 20 74 6f 20 72 65 6d 6f 76 65 20 61 6c 6c  s, to remove all
0fe0: 20 64 61 74 61 20 6f 66 20 74 68 69 73 20 70 61   data of this pa
0ff0: 73 73 20 66 72 6f 6d 20 74 68 65 20 73 74 61 74  ss from the stat
1000: 65 2c 0a 09 23 20 61 73 20 62 65 69 6e 67 20 6f  e,..# as being o
1010: 75 74 20 6f 66 20 64 61 74 65 2e 0a 0a 09 73 74  ut of date....st
1020: 61 74 65 20 64 69 73 63 61 72 64 20 63 73 6f 72  ate discard csor
1030: 64 65 72 0a 09 72 65 74 75 72 6e 0a 20 20 20 20  der..return.    
1040: 7d 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23  }..    # # ## ##
1050: 23 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23  # ##### ########
1060: 20 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 20   #############. 
1070: 20 20 20 23 23 20 49 6e 74 65 72 6e 61 6c 20 6d     ## Internal m
1080: 65 74 68 6f 64 73 0a 0a 20 20 20 20 23 20 49 6e  ethods..    # In
1090: 73 74 65 61 64 20 6f 66 20 73 65 61 72 63 68 69  stead of searchi
10a0: 6e 67 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61  ng the whole gra
10b0: 70 68 20 66 6f 72 20 74 68 65 20 64 65 67 72 65  ph for the degre
10c0: 65 2d 30 20 6e 6f 64 65 73 20 69 6e 0a 20 20 20  e-0 nodes in.   
10d0: 20 23 20 65 61 63 68 20 69 74 65 72 61 74 69 6f   # each iteratio
10e0: 6e 20 77 65 20 63 6f 6d 70 75 74 65 20 74 68 65  n we compute the
10f0: 20 6c 69 73 74 20 6f 6e 63 65 20 74 6f 20 73 74   list once to st
1100: 61 72 74 2c 20 61 6e 64 20 74 68 65 6e 20 6f 6e  art, and then on
1110: 6c 79 0a 20 20 20 20 23 20 75 70 64 61 74 65 20  ly.    # update 
1120: 69 74 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c 79  it incrementally
1130: 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 6f 75   based on the ou
1140: 74 67 6f 69 6e 67 20 6e 65 69 67 68 62 6f 75 72  tgoing neighbour
1150: 73 20 6f 66 20 74 68 65 0a 20 20 20 20 23 20 6e  s of the.    # n
1160: 6f 64 65 20 63 68 6f 73 65 6e 20 66 6f 72 20 63  ode chosen for c
1170: 6f 6d 6d 69 74 2e 0a 0a 20 20 20 20 70 72 6f 63  ommit...    proc
1180: 20 49 6e 69 74 69 61 6c 69 7a 65 43 61 6e 64 69   InitializeCandi
1190: 64 61 74 65 73 20 7b 64 67 7d 20 7b 0a 09 23 20  dates {dg} {..# 
11a0: 62 6f 74 74 6f 6d 20 3d 20 6c 69 73 74 20 28 6c  bottom = list (l
11b0: 69 73 74 20 28 6e 6f 64 65 2c 20 72 61 6e 67 65  ist (node, range
11c0: 20 6d 69 6e 2c 20 72 61 6e 67 65 20 6d 61 78 29   min, range max)
11d0: 29 0a 09 3a 3a 76 61 72 69 61 62 6c 65 20 62 6f  )..::variable bo
11e0: 74 74 6f 6d 0a 09 66 6f 72 65 61 63 68 20 6e 20  ttom..foreach n 
11f0: 5b 24 64 67 20 6e 6f 64 65 73 5d 20 7b 0a 09 20  [$dg nodes] {.. 
1200: 20 20 20 69 66 20 7b 5b 24 64 67 20 6e 6f 64 65     if {[$dg node
1210: 20 64 65 67 72 65 65 20 2d 69 6e 20 24 6e 5d 7d   degree -in $n]}
1220: 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20 20 6c   continue..    l
1230: 61 70 70 65 6e 64 20 62 6f 74 74 6f 6d 20 5b 6c  append bottom [l
1240: 69 6e 73 65 72 74 20 5b 24 64 67 20 6e 6f 64 65  insert [$dg node
1250: 20 67 65 74 20 24 6e 20 74 69 6d 65 72 61 6e 67   get $n timerang
1260: 65 5d 20 30 20 24 6e 5d 0a 09 7d 0a 09 73 65 74  e] 0 $n]..}..set
1270: 20 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72 74 20 2d   bottom [lsort -
1280: 69 6e 64 65 78 20 31 20 2d 69 6e 74 65 67 65 72  index 1 -integer
1290: 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65 78 20 32   [lsort -index 2
12a0: 20 2d 69 6e 74 65 67 65 72 20 24 62 6f 74 74 6f   -integer $botto
12b0: 6d 5d 5d 0a 09 72 65 74 75 72 6e 0a 20 20 20 20  m]]..return.    
12c0: 7d 0a 0a 20 20 20 20 70 72 6f 63 20 57 69 74 68  }..    proc With
12d0: 6f 75 74 50 72 65 64 65 63 65 73 73 6f 72 20 7b  outPredecessor {
12e0: 64 67 20 6e 76 7d 20 7b 0a 09 3a 3a 76 61 72 69  dg nv} {..::vari
12f0: 61 62 6c 65 20 62 6f 74 74 6f 6d 0a 0a 09 75 70  able bottom...up
1300: 76 61 72 20 31 20 24 6e 76 20 6e 0a 09 69 66 20  var 1 $nv n..if 
1310: 7b 21 5b 6c 6c 65 6e 67 74 68 20 24 62 6f 74 74  {![llength $bott
1320: 6f 6d 5d 7d 20 7b 20 72 65 74 75 72 6e 20 30 20  om]} { return 0 
1330: 7d 0a 0a 09 73 65 74 20 6e 20 5b 6c 69 6e 64 65  }...set n [linde
1340: 78 20 5b 6c 69 6e 64 65 78 20 24 62 6f 74 74 6f  x [lindex $botto
1350: 6d 20 30 5d 20 30 5d 0a 09 73 65 74 20 62 6f 74  m 0] 0]..set bot
1360: 74 6f 6d 20 5b 6c 72 61 6e 67 65 20 24 62 6f 74  tom [lrange $bot
1370: 74 6f 6d 20 31 20 65 6e 64 5d 0a 09 73 65 74 20  tom 1 end]..set 
1380: 63 68 61 6e 67 65 64 20 30 0a 0a 09 23 20 55 70  changed 0...# Up
1390: 64 61 74 65 20 6c 69 73 74 20 6f 66 20 6e 6f 64  date list of nod
13a0: 65 73 20 77 69 74 68 6f 75 74 20 70 72 65 64 65  es without prede
13b0: 63 65 73 73 6f 72 2c 20 62 61 73 65 64 20 6f 6e  cessor, based on
13c0: 20 74 68 65 0a 09 23 20 6f 75 74 67 6f 69 6e 67   the..# outgoing
13d0: 20 6e 65 69 67 68 62 6f 75 72 73 20 6f 66 20 74   neighbours of t
13e0: 68 65 20 63 68 6f 73 65 6e 20 6e 6f 64 65 2e 20  he chosen node. 
13f0: 54 68 69 73 20 73 68 6f 75 6c 64 20 62 65 0a 09  This should be..
1400: 23 20 66 61 73 74 65 72 20 74 68 61 6e 20 69 74  # faster than it
1410: 65 72 61 74 69 6e 67 20 6f 66 20 74 68 65 20 77  erating of the w
1420: 68 6f 6c 65 20 73 65 74 20 6f 66 20 6e 6f 64 65  hole set of node
1430: 73 2c 20 66 69 6e 64 69 6e 67 20 61 6c 6c 0a 09  s, finding all..
1440: 23 20 77 69 74 68 6f 75 74 20 70 72 65 64 65 63  # without predec
1450: 65 73 73 6f 72 73 2c 20 73 6f 72 74 69 6e 67 20  essors, sorting 
1460: 74 68 65 6d 20 62 79 20 74 69 6d 65 2c 20 65 74  them by time, et
1470: 63 2e 20 70 70 2e 0a 09 66 6f 72 65 61 63 68 20  c. pp...foreach 
1480: 6f 75 74 20 5b 24 64 67 20 6e 6f 64 65 73 20 2d  out [$dg nodes -
1490: 6f 75 74 20 24 6e 5d 20 7b 0a 09 20 20 20 20 69  out $n] {..    i
14a0: 66 20 7b 5b 24 64 67 20 6e 6f 64 65 20 64 65 67  f {[$dg node deg
14b0: 72 65 65 20 2d 69 6e 20 24 6f 75 74 5d 20 3e 20  ree -in $out] > 
14c0: 31 7d 20 63 6f 6e 74 69 6e 75 65 0a 09 20 20 20  1} continue..   
14d0: 20 23 20 44 65 67 72 65 65 2d 31 20 6e 65 69 67   # Degree-1 neig
14e0: 68 62 6f 75 72 2c 20 77 69 6c 6c 20 68 61 76 65  hbour, will have
14f0: 20 6e 6f 20 70 72 65 64 65 63 65 73 73 6f 72 73   no predecessors
1500: 20 61 66 74 65 72 20 74 68 65 0a 09 20 20 20 20   after the..    
1510: 23 20 72 65 6d 6f 76 61 6c 20 6f 66 20 6e 2e 20  # removal of n. 
1520: 50 75 74 20 6f 6e 20 74 68 65 20 6c 69 73 74 2e  Put on the list.
1530: 0a 09 20 20 20 20 6c 61 70 70 65 6e 64 20 62 6f  ..    lappend bo
1540: 74 74 6f 6d 20 5b 6c 69 6e 73 65 72 74 20 5b 24  ttom [linsert [$
1550: 64 67 20 6e 6f 64 65 20 67 65 74 20 24 6f 75 74  dg node get $out
1560: 20 74 69 6d 65 72 61 6e 67 65 5d 20 30 20 24 6f   timerange] 0 $o
1570: 75 74 5d 0a 09 20 20 20 20 73 65 74 20 63 68 61  ut]..    set cha
1580: 6e 67 65 64 20 31 0a 09 7d 0a 09 69 66 20 7b 24  nged 1..}..if {$
1590: 63 68 61 6e 67 65 64 7d 20 7b 0a 09 20 20 20 20  changed} {..    
15a0: 73 65 74 20 62 6f 74 74 6f 6d 20 5b 6c 73 6f 72  set bottom [lsor
15b0: 74 20 2d 69 6e 64 65 78 20 31 20 2d 69 6e 74 65  t -index 1 -inte
15c0: 67 65 72 20 5b 6c 73 6f 72 74 20 2d 69 6e 64 65  ger [lsort -inde
15d0: 78 20 32 20 2d 69 6e 74 65 67 65 72 20 24 62 6f  x 2 -integer $bo
15e0: 74 74 6f 6d 5d 5d 0a 09 7d 0a 0a 09 23 20 57 65  ttom]]..}...# We
15f0: 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 20 74   do not delete t
1600: 68 65 20 6e 6f 64 65 20 69 6d 6d 65 64 69 61 74  he node immediat
1610: 65 6c 79 2c 20 74 6f 20 61 6c 6c 6f 77 20 74 68  ely, to allow th
1620: 65 20 53 61 76 65 0a 09 23 20 70 72 6f 63 65 64  e Save..# proced
1630: 75 72 65 20 74 6f 20 73 61 76 65 20 74 68 65 20  ure to save the 
1640: 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 73 20  dependencies as 
1650: 77 65 6c 6c 20 28 65 6e 63 6f 64 65 64 20 69 6e  well (encoded in
1660: 20 74 68 65 0a 09 23 20 61 72 63 73 29 2e 0a 09   the..# arcs)...
1670: 72 65 74 75 72 6e 20 31 0a 20 20 20 20 7d 0a 0a  return 1.    }..
1680: 20 20 20 20 70 72 6f 63 20 53 61 76 65 41 6e 64      proc SaveAnd
1690: 52 65 6d 6f 76 65 20 7b 64 67 20 6e 7d 20 7b 0a  Remove {dg n} {.
16a0: 09 3a 3a 76 61 72 69 61 62 6c 65 20 61 74 0a 09  .::variable at..
16b0: 73 65 74 20 63 69 64 20 5b 24 6e 20 69 64 5d 0a  set cid [$n id].
16c0: 0a 09 6c 6f 67 20 77 72 69 74 65 20 34 20 62 72  ..log write 4 br
16d0: 65 61 6b 72 63 79 63 6c 65 20 22 43 6f 6d 69 74  eakrcycle "Comit
16e0: 74 69 6e 67 20 40 20 24 61 74 3a 20 3c 24 63 69  ting @ $at: <$ci
16f0: 64 3e 22 0a 09 73 74 61 74 65 20 72 75 6e 20 7b  d>"..state run {
1700: 0a 09 20 20 20 20 49 4e 53 45 52 54 20 49 4e 54  ..    INSERT INT
1710: 4f 20 63 73 6f 72 64 65 72 20 28 63 69 64 2c 20  O csorder (cid, 
1720: 20 70 6f 73 29 0a 09 20 20 20 20 56 41 4c 55 45   pos)..    VALUE
1730: 53 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28  S              (
1740: 24 63 69 64 2c 20 24 61 74 29 0a 09 7d 0a 09 23  $cid, $at)..}..#
1750: 20 54 4f 44 4f 3a 20 57 72 69 74 65 20 74 68 65   TODO: Write the
1760: 20 70 72 6f 6a 65 63 74 20 6c 65 76 65 6c 20 63   project level c
1770: 68 61 6e 67 65 73 65 74 20 64 65 70 65 6e 64 65  hangeset depende
1780: 6e 63 69 65 73 20 61 73 20 77 65 6c 6c 2e 0a 09  ncies as well...
1790: 69 6e 63 72 20 61 74 0a 09 24 64 67 20 6e 6f 64  incr at..$dg nod
17a0: 65 20 64 65 6c 65 74 65 20 24 6e 0a 09 72 65 74  e delete $n..ret
17b0: 75 72 6e 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70  urn.    }..    p
17c0: 72 6f 63 20 46 69 6e 64 43 79 63 6c 65 20 7b 64  roc FindCycle {d
17d0: 67 7d 20 7b 0a 09 23 20 54 68 69 73 20 70 72 6f  g} {..# This pro
17e0: 63 65 64 75 72 65 20 69 73 20 72 75 6e 20 69 66  cedure is run if
17f0: 20 61 6e 64 20 6f 6e 6c 79 20 74 68 65 20 67 72   and only the gr
1800: 61 70 68 20 69 73 20 6e 6f 74 20 65 6d 70 74 79  aph is not empty
1810: 20 61 6e 64 0a 09 23 20 61 6c 6c 20 6e 6f 64 65   and..# all node
1820: 73 20 68 61 76 65 20 70 72 65 64 65 63 65 73 73  s have predecess
1830: 6f 72 73 2e 20 54 68 69 73 20 6d 65 61 6e 73 20  ors. This means 
1840: 74 68 61 74 20 65 61 63 68 20 6e 6f 64 65 20 69  that each node i
1850: 73 0a 09 23 20 65 69 74 68 65 72 20 70 61 72 74  s..# either part
1860: 20 6f 66 20 61 20 63 79 63 6c 65 20 6f 72 20 28   of a cycle or (
1870: 69 6e 64 69 72 65 63 74 6c 79 29 20 64 65 70 65  indirectly) depe
1880: 6e 64 69 6e 67 20 6f 6e 20 61 20 6e 6f 64 65 0a  nding on a node.
1890: 09 23 20 69 6e 20 61 20 63 79 63 6c 65 2e 20 57  .# in a cycle. W
18a0: 65 20 63 61 6e 20 73 74 61 72 74 20 61 74 20 61  e can start at a
18b0: 6e 20 61 72 62 69 74 72 61 72 79 20 6e 6f 64 65  n arbitrary node
18c0: 2c 20 66 6f 6c 6c 6f 77 20 69 74 73 0a 09 23 20  , follow its..# 
18d0: 69 6e 63 6f 6d 69 6e 67 20 65 64 67 65 73 20 74  incoming edges t
18e0: 6f 20 69 74 73 20 70 72 65 64 65 63 65 73 73 6f  o its predecesso
18f0: 72 73 20 75 6e 74 69 6c 20 77 65 20 73 65 65 20  rs until we see 
1900: 61 20 6e 6f 64 65 20 61 0a 09 23 20 73 65 63 6f  a node a..# seco
1910: 6e 64 20 74 69 6d 65 2e 20 54 68 61 74 20 6e 6f  nd time. That no
1920: 64 65 20 63 6c 6f 73 65 73 20 74 68 65 20 63 79  de closes the cy
1930: 63 6c 65 20 61 6e 64 20 74 68 65 20 62 65 67 69  cle and the begi
1940: 6e 6e 69 6e 67 20 69 73 0a 09 23 20 69 74 73 20  nning is..# its 
1950: 66 69 72 73 74 20 6f 63 63 75 72 65 6e 63 65 2e  first occurence.
1960: 20 4e 6f 74 65 20 74 68 61 74 20 77 65 20 63 61   Note that we ca
1970: 6e 20 63 68 6f 6f 73 65 20 61 6e 20 61 72 62 69  n choose an arbi
1980: 74 72 61 72 79 0a 09 23 20 70 72 65 64 65 63 65  trary..# predece
1990: 73 73 6f 72 20 6f 66 20 65 61 63 68 20 6e 6f 64  ssor of each nod
19a0: 65 20 61 73 20 77 65 6c 6c 2c 20 77 65 20 64 6f  e as well, we do
19b0: 20 6e 6f 74 20 68 61 76 65 20 74 6f 20 73 65 61   not have to sea
19c0: 72 63 68 2e 0a 0a 09 23 20 57 65 20 72 65 63 6f  rch....# We reco
19d0: 72 64 20 66 6f 72 20 65 61 63 68 20 6e 6f 64 65  rd for each node
19e0: 20 74 68 65 20 69 6e 64 65 78 20 6f 66 20 74 68   the index of th
19f0: 65 20 66 69 72 73 74 20 61 70 70 65 61 72 61 6e  e first appearan
1a00: 63 65 20 69 6e 0a 09 23 20 74 68 65 20 70 61 74  ce in..# the pat
1a10: 68 2c 20 6d 61 6b 69 6e 67 20 69 74 20 65 61 73  h, making it eas
1a20: 79 20 61 74 20 74 68 65 20 65 6e 64 20 74 6f 20  y at the end to 
1a30: 63 75 74 20 74 68 65 20 63 79 63 6c 65 20 66 72  cut the cycle fr
1a40: 6f 6d 0a 09 23 20 69 74 2e 0a 0a 09 23 20 43 68  om..# it....# Ch
1a50: 6f 6f 73 65 20 61 72 62 69 74 72 61 72 79 20 6e  oose arbitrary n
1a60: 6f 64 65 20 74 6f 20 73 74 61 72 74 20 6f 75 72  ode to start our
1a70: 20 73 65 61 72 63 68 20 61 74 2e 0a 09 73 65 74   search at...set
1a80: 20 73 74 61 72 74 20 5b 6c 69 6e 64 65 78 20 5b   start [lindex [
1a90: 24 64 67 20 6e 6f 64 65 73 5d 20 30 5d 0a 0a 09  $dg nodes] 0]...
1aa0: 23 20 49 6e 69 74 69 61 6c 69 7a 65 20 73 74 61  # Initialize sta
1ab0: 74 65 2c 20 70 61 74 68 20 6f 66 20 73 65 65 6e  te, path of seen
1ac0: 20 6e 6f 64 65 73 2c 20 61 6e 64 20 77 68 65 6e   nodes, and when
1ad0: 20 73 65 65 6e 2e 0a 09 73 65 74 20 20 20 20 20   seen...set     
1ae0: 20 20 70 61 74 68 20 7b 7d 0a 09 61 72 72 61 79    path {}..array
1af0: 20 73 65 74 20 73 65 65 6e 20 7b 7d 0a 0a 09 77   set seen {}...w
1b00: 68 69 6c 65 20 7b 31 7d 20 7b 0a 09 20 20 20 20  hile {1} {..    
1b10: 23 20 53 74 6f 70 20 73 65 61 72 63 68 69 6e 67  # Stop searching
1b20: 20 77 68 65 6e 20 77 65 20 68 61 76 65 20 73 65   when we have se
1b30: 65 6e 20 74 68 65 20 63 75 72 72 65 6e 74 20 6e  en the current n
1b40: 6f 64 65 0a 09 20 20 20 20 23 20 61 6c 72 65 61  ode..    # alrea
1b50: 64 79 2c 20 74 68 65 20 63 69 72 63 6c 65 20 68  dy, the circle h
1b60: 61 73 20 62 65 65 6e 20 63 6c 6f 73 65 64 2e 0a  as been closed..
1b70: 09 20 20 20 20 69 66 20 7b 5b 69 6e 66 6f 20 65  .    if {[info e
1b80: 78 69 73 74 73 20 73 65 65 6e 28 24 73 74 61 72  xists seen($star
1b90: 74 29 5d 7d 20 62 72 65 61 6b 0a 09 20 20 20 20  t)]} break..    
1ba0: 6c 61 70 70 65 6e 64 20 70 61 74 68 20 24 73 74  lappend path $st
1bb0: 61 72 74 0a 09 20 20 20 20 73 65 74 20 73 65 65  art..    set see
1bc0: 6e 28 24 73 74 61 72 74 29 20 5b 6c 6c 65 6e 67  n($start) [lleng
1bd0: 74 68 20 24 70 61 74 68 5d 0a 09 20 20 20 20 23  th $path]..    #
1be0: 20 43 68 6f 6f 73 65 20 61 72 62 69 74 72 61 72   Choose arbitrar
1bf0: 79 20 70 72 65 64 65 63 65 73 73 6f 72 0a 09 20  y predecessor.. 
1c00: 20 20 20 73 65 74 20 73 74 61 72 74 20 5b 6c 69     set start [li
1c10: 6e 64 65 78 20 5b 24 64 67 20 6e 6f 64 65 73 20  ndex [$dg nodes 
1c20: 2d 69 6e 20 24 73 74 61 72 74 5d 20 30 5d 0a 09  -in $start] 0]..
1c30: 7d 0a 0a 09 72 65 74 75 72 6e 20 5b 73 74 72 75  }...return [stru
1c40: 63 74 3a 3a 6c 69 73 74 20 72 65 76 65 72 73 65  ct::list reverse
1c50: 20 5b 6c 72 61 6e 67 65 20 24 70 61 74 68 20 24   [lrange $path $
1c60: 73 65 65 6e 28 24 73 74 61 72 74 29 20 65 6e 64  seen($start) end
1c70: 5d 5d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 72  ]].    }..    pr
1c80: 6f 63 20 42 72 65 61 6b 43 79 63 6c 65 20 7b 64  oc BreakCycle {d
1c90: 67 20 63 79 63 6c 65 7d 20 7b 0a 09 74 72 6f 75  g cycle} {..trou
1ca0: 62 6c 65 20 69 6e 74 65 72 6e 61 6c 20 22 42 72  ble internal "Br
1cb0: 65 61 6b 20 63 79 63 6c 65 20 3c 24 63 79 63 6c  eak cycle <$cycl
1cc0: 65 3e 22 0a 09 72 65 74 75 72 6e 0a 20 20 20 20  e>"..return.    
1cd0: 7d 0a 0a 20 20 20 20 74 79 70 65 76 61 72 69 61  }..    typevaria
1ce0: 62 6c 65 20 61 74 20 20 20 20 20 20 30 20 3b 20  ble at      0 ; 
1cf0: 23 20 43 6f 75 6e 74 65 72 20 66 6f 72 20 63 6f  # Counter for co
1d00: 6d 6d 69 74 20 69 64 73 20 66 6f 72 20 74 68 65  mmit ids for the
1d10: 20 63 68 61 6e 67 65 73 65 74 73 2e 0a 20 20 20   changesets..   
1d20: 20 74 79 70 65 76 61 72 69 61 62 6c 65 20 62 6f   typevariable bo
1d30: 74 74 6f 6d 20 7b 7d 20 3b 20 23 20 4c 69 73 74  ttom {} ; # List
1d40: 20 6f 66 20 63 61 6e 64 69 64 61 74 65 20 6e 6f   of candidate no
1d50: 64 65 73 20 66 6f 72 20 63 6f 6d 6d 69 74 74 69  des for committi
1d60: 6e 67 2e 0a 0a 20 20 20 20 23 20 23 20 23 23 20  ng...    # # ## 
1d70: 23 23 23 20 23 23 23 23 23 20 23 23 23 23 23 23  ### ##### ######
1d80: 23 23 20 23 23 23 23 23 23 23 23 23 23 23 23 23  ## #############
1d90: 0a 20 20 20 20 23 23 20 43 6f 6e 66 69 67 75 72  .    ## Configur
1da0: 61 74 69 6f 6e 0a 0a 20 20 20 20 70 72 61 67 6d  ation..    pragm
1db0: 61 20 2d 68 61 73 69 6e 73 74 61 6e 63 65 73 20  a -hasinstances 
1dc0: 20 20 6e 6f 20 3b 20 23 20 73 69 6e 67 6c 65 74    no ; # singlet
1dd0: 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61 20 2d 68  on.    pragma -h
1de0: 61 73 74 79 70 65 69 6e 66 6f 20 20 20 20 6e 6f  astypeinfo    no
1df0: 20 3b 20 23 20 6e 6f 20 69 6e 74 72 6f 73 70 65   ; # no introspe
1e00: 63 74 69 6f 6e 0a 20 20 20 20 70 72 61 67 6d 61  ction.    pragma
1e10: 20 2d 68 61 73 74 79 70 65 64 65 73 74 72 6f 79   -hastypedestroy
1e20: 20 6e 6f 20 3b 20 23 20 69 6d 6d 6f 72 74 61 6c   no ; # immortal
1e30: 0a 0a 20 20 20 20 23 20 23 20 23 23 20 23 23 23  ..    # # ## ###
1e40: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20   ##### ######## 
1e50: 23 23 23 23 23 23 23 23 23 23 23 23 23 0a 7d 0a  #############.}.
1e60: 0a 6e 61 6d 65 73 70 61 63 65 20 65 76 61 6c 20  .namespace eval 
1e70: 3a 3a 76 63 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d  ::vc::fossil::im
1e80: 70 6f 72 74 3a 3a 63 76 73 3a 3a 70 61 73 73 20  port::cvs::pass 
1e90: 7b 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20  {.    namespace 
1ea0: 65 78 70 6f 72 74 20 62 72 65 61 6b 72 63 79 63  export breakrcyc
1eb0: 6c 65 0a 20 20 20 20 6e 61 6d 65 73 70 61 63 65  le.    namespace
1ec0: 20 65 76 61 6c 20 62 72 65 61 6b 72 63 79 63 6c   eval breakrcycl
1ed0: 65 20 7b 0a 09 6e 61 6d 65 73 70 61 63 65 20 69  e {..namespace i
1ee0: 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73 73  mport ::vc::foss
1ef0: 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73 3a  il::import::cvs:
1f00: 3a 73 74 61 74 65 0a 09 6e 61 6d 65 73 70 61 63  :state..namespac
1f10: 65 20 65 76 61 6c 20 70 72 6f 6a 65 63 74 20 7b  e eval project {
1f20: 0a 09 20 20 20 20 6e 61 6d 65 73 70 61 63 65 20  ..    namespace 
1f30: 69 6d 70 6f 72 74 20 3a 3a 76 63 3a 3a 66 6f 73  import ::vc::fos
1f40: 73 69 6c 3a 3a 69 6d 70 6f 72 74 3a 3a 63 76 73  sil::import::cvs
1f50: 3a 3a 70 72 6f 6a 65 63 74 3a 3a 72 65 76 0a 09  ::project::rev..
1f60: 7d 0a 09 6e 61 6d 65 73 70 61 63 65 20 69 6d 70  }..namespace imp
1f70: 6f 72 74 20 3a 3a 76 63 3a 3a 74 6f 6f 6c 73 3a  ort ::vc::tools:
1f80: 3a 6c 6f 67 0a 09 6c 6f 67 20 72 65 67 69 73 74  :log..log regist
1f90: 65 72 20 62 72 6b 72 63 79 63 6c 65 0a 20 20 20  er brkrcycle.   
1fa0: 20 7d 0a 7d 0a 0a 23 20 23 20 23 23 20 23 23 23   }.}..# # ## ###
1fb0: 20 23 23 23 23 23 20 23 23 23 23 23 23 23 23 20   ##### ######## 
1fc0: 23 23 23 23 23 23 23 23 23 23 23 23 23 20 23 23  ############# ##
1fd0: 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23  ################
1fe0: 23 23 23 0a 23 23 20 52 65 61 64 79 0a 0a 70 61  ###.## Ready..pa
1ff0: 63 6b 61 67 65 20 70 72 6f 76 69 64 65 20 76 63  ckage provide vc
2000: 3a 3a 66 6f 73 73 69 6c 3a 3a 69 6d 70 6f 72 74  ::fossil::import
2010: 3a 3a 63 76 73 3a 3a 70 61 73 73 3a 3a 62 72 65  ::cvs::pass::bre
2020: 61 6b 72 63 79 63 6c 65 20 31 2e 30 0a 72 65 74  akrcycle 1.0.ret
2030: 75 72 6e 0a                                      urn.