libcwal  Hex Artifact Content

Artifact 20c5241c870a1f9aa93ed9bb9e5af23cbe026491:

Wiki page [cwal_gc] by stephan 2014-08-04 20:44:38.
0000: 44 20 32 30 31 34 2d 30 38 2d 30 34 54 32 30 3a  D 2014-08-04T20:
0010: 34 34 3a 33 38 2e 35 39 32 0a 4c 20 63 77 61 6c  44:38.592.L cwal
0020: 5f 67 63 0a 50 20 32 39 39 36 37 36 38 30 64 30  _gc.P 29967680d0
0030: 62 31 66 62 65 35 64 32 33 66 30 66 36 33 35 62  b1fbe5d23f0f635b
0040: 32 33 62 39 65 31 31 34 62 66 61 66 65 35 0a 55  23b9e114bfafe5.U
0050: 20 73 74 65 70 68 61 6e 0a 57 20 39 33 31 32 0a   stephan.W 9312.
0060: 53 65 65 20 61 6c 73 6f 3a 20 5b 44 61 74 61 54  See also: [DataT
0070: 79 70 65 73 5d 2c 20 5b 4d 65 6d 6f 72 79 4d 6f  ypes], [MemoryMo
0080: 64 65 6c 5d 0d 0a 0d 0a 4e 6f 74 65 73 20 61 62  del]....Notes ab
0090: 6f 75 74 20 68 6f 77 20 67 61 72 62 61 67 65 20  out how garbage 
00a0: 63 6f 6c 6c 65 63 74 69 6f 6e 20 77 6f 72 6b 73  collection works
00b0: 20 69 6e 20 63 77 61 6c 2e 2e 2e 0d 0a 0d 0a 41   in cwal.......A
00c0: 20 63 6f 72 65 20 72 65 71 75 69 72 65 6d 65 6e   core requiremen
00d0: 74 20 66 6f 72 20 6d 65 20 69 6e 20 61 20 22 70  t for me in a "p
00e0: 65 72 73 6f 6e 61 6c 20 73 63 72 69 70 74 69 6e  ersonal scriptin
00f0: 67 20 65 6e 67 69 6e 65 22 20 69 73 20 64 65 74  g engine" is det
0100: 65 72 6d 69 6e 69 73 74 69 63 20 64 65 73 74 72  erministic destr
0110: 75 63 74 69 6f 6e 20 28 74 68 6f 75 67 68 20 74  uction (though t
0120: 68 65 20 6f 72 64 65 72 69 6e 67 20 6e 65 65 64  he ordering need
0130: 20 6e 6f 74 20 61 6c 77 61 79 73 20 62 65 20 77   not always be w
0140: 65 6c 6c 2d 64 65 66 69 6e 65 64 29 2c 20 73 74  ell-defined), st
0150: 72 6f 6e 67 6c 79 20 6c 65 61 6e 69 6e 67 20 74  rongly leaning t
0160: 6f 77 61 72 64 73 20 43 2b 2b 2d 73 74 79 6c 65  owards C++-style
0170: 20 73 63 6f 70 69 6e 67 20 72 75 6c 65 73 2e 20   scoping rules. 
0180: 49 64 65 61 6c 6c 79 2c 20 74 68 69 73 20 77 6f  Ideally, this wo
0190: 75 6c 64 20 61 6c 73 6f 20 67 75 61 72 61 6e 74  uld also guarant
01a0: 79 20 20 74 68 61 74 20 76 61 6c 75 65 73 20 67  y  that values g
01b0: 65 74 20 66 69 6e 61 6c 69 7a 65 64 20 69 6e 20  et finalized in 
01c0: 74 68 65 20 6f 70 70 6f 73 69 74 65 20 6f 72 64  the opposite ord
01d0: 65 72 20 6f 66 20 74 68 65 69 72 20 63 72 65 61  er of their crea
01e0: 74 69 6f 6e 2c 20 62 75 74 20 69 74 20 74 75 72  tion, but it tur
01f0: 6e 73 20 6f 75 74 20 74 68 61 74 20 64 6f 69 6e  ns out that doin
0200: 67 20 73 6f 20 77 6f 75 6c 64 20 72 65 71 75 69  g so would requi
0210: 72 65 20 6d 6f 72 65 20 69 6e 66 72 61 73 74 72  re more infrastr
0220: 75 63 74 75 72 65 20 74 68 61 6e 20 69 27 64 20  ucture than i'd 
0230: 6c 69 6b 65 20 74 6f 20 70 61 79 20 66 6f 72 2e  like to pay for.
0240: 0d 0a 0d 0a 3c 73 74 72 6f 6e 67 3e 46 69 72 73  ....<strong>Firs
0250: 74 2c 20 61 6e 20 6f 76 65 72 76 69 65 77 20 6f  t, an overview o
0260: 66 20 74 68 65 20 64 61 74 61 20 6d 6f 64 65 6c  f the data model
0270: 3a 3c 2f 73 74 72 6f 6e 67 3e 20 22 56 61 6c 75  :</strong> "Valu
0280: 65 73 22 20 61 72 65 20 6f 70 61 71 75 65 20 68  es" are opaque h
0290: 61 6e 64 6c 65 73 20 77 68 69 63 68 20 72 65 66  andles which ref
02a0: 65 72 20 74 6f 20 76 61 72 69 6f 75 73 20 63 6f  er to various co
02b0: 6e 63 72 65 74 65 20 74 79 70 65 73 20 6c 69 6b  ncrete types lik
02c0: 65 20 6e 75 6d 62 65 72 73 2c 20 6f 62 6a 65 63  e numbers, objec
02d0: 74 73 2c 20 61 72 72 61 79 73 2c 20 73 74 72 69  ts, arrays, stri
02e0: 6e 67 73 2c 20 65 74 63 2e 20 49 74 20 69 73 20  ngs, etc. It is 
02f0: 73 74 72 6f 6e 67 6c 79 20 6d 6f 64 65 6c 65 64  strongly modeled
0300: 20 61 66 74 65 72 20 4a 53 4f 4e 2f 45 43 4d 41   after JSON/ECMA
0310: 53 63 72 69 70 74 20 74 79 70 65 73 20 28 61 6e  Script types (an
0320: 64 20 69 6e 20 66 61 63 74 20 6f 72 69 67 69 6e  d in fact origin
0330: 61 74 65 64 20 61 73 20 61 20 66 6f 72 6b 20 6f  ated as a fork o
0340: 66 20 74 68 65 20 5b 68 74 74 70 3a 2f 2f 66 6f  f the [http://fo
0350: 73 73 69 6c 2e 77 61 6e 64 65 72 69 6e 67 68 6f  ssil.wanderingho
0360: 72 73 65 2e 6e 65 74 2f 77 69 6b 69 73 2f 63 73  rse.net/wikis/cs
0370: 6f 6e 2f 7c 63 73 6f 6e 20 4a 53 4f 4e 20 6c 69  on/|cson JSON li
0380: 62 72 61 72 79 5d 29 2e 20 43 6c 69 65 6e 74 73  brary]). Clients
0390: 20 63 61 6e 20 61 73 6b 20 61 20 76 61 6c 75 65   can ask a value
03a0: 20 77 68 61 74 20 74 79 70 65 20 69 74 20 69 73   what type it is
03b0: 20 61 6e 64 20 70 65 72 66 6f 72 6d 20 6f 74 68   and perform oth
03c0: 65 72 20 6f 70 65 72 61 74 69 6f 6e 73 2e 20 53  er operations. S
03d0: 6f 6d 65 20 74 79 70 65 73 20 68 61 76 65 20 61  ome types have a
03e0: 20 68 69 67 68 65 72 2d 6c 65 76 65 6c 20 72 65   higher-level re
03f0: 70 72 65 73 65 6e 74 61 74 69 6f 6e 20 28 73 74  presentation (st
0400: 72 69 6e 67 73 2c 20 6f 62 6a 65 63 74 73 2c 20  rings, objects, 
0410: 61 6e 64 20 61 72 72 61 79 73 29 20 61 6e 64 20  and arrays) and 
0420: 73 75 63 68 20 61 20 76 61 6c 75 65 20 68 61 6e  such a value han
0430: 64 6c 65 20 63 61 6e 20 62 65 20 63 6f 6e 76 65  dle can be conve
0440: 72 74 65 64 20 66 72 65 65 6c 79 20 62 65 74 77  rted freely betw
0450: 65 65 6e 20 69 74 73 20 6f 70 61 71 75 65 20 63  een its opaque c
0460: 6f 6e 63 72 65 74 65 20 68 61 6e 64 6c 65 20 74  oncrete handle t
0470: 79 70 65 2e 20 41 73 20 66 61 72 20 61 73 20 74  ype. As far as t
0480: 68 65 20 65 6e 67 69 6e 65 20 69 73 20 70 72 69  he engine is pri
0490: 6d 61 72 69 6c 79 20 63 6f 6e 63 65 72 6e 65 64  marily concerned
04a0: 2c 20 68 6f 77 65 76 65 72 2c 20 74 68 65 79 20  , however, they 
04b0: 61 72 65 20 61 6c 6c 20 67 65 6e 65 72 69 63 20  are all generic 
04c0: 56 61 6c 75 65 73 2e 20 49 6e 74 65 72 6e 61 6c  Values. Internal
04d0: 6c 79 20 74 68 65 20 65 6e 67 69 6e 65 20 74 65  ly the engine te
04e0: 6e 64 73 20 74 6f 20 73 65 70 61 72 61 74 65 20  nds to separate 
04f0: 76 61 6c 75 65 73 20 69 6e 74 6f 20 22 61 74 6f  values into "ato
0500: 6d 73 22 20 61 6e 64 20 22 63 6f 6e 74 61 69 6e  ms" and "contain
0510: 65 72 73 2e 22 20 54 68 65 20 66 6f 72 6d 65 72  ers." The former
0520: 20 69 73 20 61 6e 79 20 74 79 70 65 20 77 68 69   is any type whi
0530: 63 68 20 63 61 6e 6e 6f 74 20 63 6f 6e 74 61 69  ch cannot contai
0540: 6e 20 63 68 69 6c 64 20 76 61 6c 75 65 73 20 61  n child values a
0550: 6e 64 20 74 68 65 20 6c 61 74 74 65 72 20 69 6e  nd the latter in
0560: 63 6c 75 64 65 73 20 61 72 72 61 79 73 20 61 6e  cludes arrays an
0570: 64 20 6f 62 6a 65 63 74 73 2e 20 4d 6f 72 65 20  d objects. More 
0580: 64 65 74 61 69 6c 73 20 61 62 6f 75 74 20 74 68  details about th
0590: 65 20 56 61 6c 75 65 20 73 79 73 74 65 6d 20 63  e Value system c
05a0: 61 6e 20 62 65 20 66 6f 75 6e 64 20 69 6e 20 74  an be found in t
05b0: 68 65 20 5b 4d 65 6d 6f 72 79 4d 6f 64 65 6c 5d  he [MemoryModel]
05c0: 20 61 6e 64 20 5b 44 61 74 61 54 79 70 65 73 5d   and [DataTypes]
05d0: 20 70 61 67 65 73 2e 0d 0a 0d 0a 57 68 65 6e 20   pages.....When 
05e0: 61 20 76 61 6c 75 65 20 69 73 20 63 72 65 61 74  a value is creat
05f0: 65 64 20 28 76 69 61 20 63 6f 6e 63 72 65 74 65  ed (via concrete
0600: 2d 74 79 70 65 2d 73 70 65 63 69 66 69 63 20 66  -type-specific f
0610: 61 63 74 6f 72 79 20 66 75 6e 63 74 69 6f 6e 73  actory functions
0620: 29 20 69 74 20 69 6e 69 74 69 61 6c 6c 79 20 62  ) it initially b
0630: 65 6c 6f 6e 67 73 20 74 6f 20 74 68 65 20 73 63  elongs to the sc
0640: 6f 70 65 20 77 68 69 63 68 20 69 73 20 61 63 74  ope which is act
0650: 69 76 65 20 77 68 65 6e 20 69 74 20 69 73 20 69  ive when it is i
0660: 6e 73 74 61 6e 74 69 61 74 65 64 2e 20 22 42 65  nstantiated. "Be
0670: 6c 6f 6e 67 73 20 74 6f 22 20 69 6e 20 74 68 69  longs to" in thi
0680: 73 20 73 65 6e 73 65 20 69 73 20 61 20 62 69 74  s sense is a bit
0690: 20 6d 69 73 6c 65 61 64 69 6e 67 2c 20 62 75 74   misleading, but
06a0: 20 69 73 20 61 6c 73 6f 20 6e 6f 74 20 65 6e 74   is also not ent
06b0: 69 72 65 6c 79 20 69 6e 63 6f 72 72 65 63 74 2c  irely incorrect,
06c0: 20 73 6f 20 77 65 27 6c 6c 20 73 69 6d 70 6c 69   so we'll simpli
06d0: 66 79 20 68 65 72 65 20 66 6f 72 20 63 6c 61 72  fy here for clar
06e0: 69 74 79 2e 0d 0a 0d 0a 54 68 65 20 66 69 72 73  ity.....The firs
06f0: 74 20 74 6f 6f 6c 20 63 77 61 6c 20 75 73 65 73  t tool cwal uses
0700: 20 66 6f 72 20 66 69 67 75 72 69 6e 67 20 6f 75   for figuring ou
0710: 74 20 77 68 65 6e 20 74 6f 20 64 65 73 74 72 6f  t when to destro
0720: 79 20 61 20 76 61 6c 75 65 20 69 73 20 61 20 63  y a value is a c
0730: 6f 6e 76 65 6e 74 69 6f 6e 61 6c 20 72 65 66 65  onventional refe
0740: 72 65 6e 63 65 20 63 6f 75 6e 74 2e 20 52 65 66  rence count. Ref
0750: 65 72 65 6e 63 65 20 63 6f 75 6e 74 69 6e 67 20  erence counting 
0760: 69 73 20 65 61 73 79 20 74 6f 20 69 6d 70 6c 65  is easy to imple
0770: 6d 65 6e 74 2c 20 77 6f 72 6b 73 20 77 65 6c 6c  ment, works well
0780: 2c 20 61 6e 64 20 61 6c 6c 6f 77 73 20 6d 61 6e  , and allows man
0790: 79 20 6f 70 65 72 61 74 69 6f 6e 73 20 74 6f 20  y operations to 
07a0: 70 65 72 66 6f 72 6d 20 6d 6f 72 65 20 65 66 66  perform more eff
07b0: 69 63 69 65 6e 74 6c 79 20 62 79 20 72 65 71 75  iciently by requ
07c0: 69 72 69 6e 67 20 66 65 77 65 72 20 61 6c 6c 6f  iring fewer allo
07d0: 63 61 74 69 6f 6e 73 2e 20 41 73 20 61 6e 79 6f  cations. As anyo
07e0: 6e 65 20 66 61 6d 69 6c 69 61 72 20 77 69 74 68  ne familiar with
07f0: 20 74 68 65 20 70 72 6f 62 6c 65 6d 20 64 6f 6d   the problem dom
0800: 61 69 6e 20 70 72 6f 62 61 62 6c 79 20 6b 6e 6f  ain probably kno
0810: 77 73 2c 20 72 65 66 65 72 65 6e 63 65 20 63 6f  ws, reference co
0820: 75 6e 74 69 6e 67 20 62 72 65 61 6b 73 20 64 6f  unting breaks do
0830: 77 6e 20 73 6f 6d 65 77 68 61 74 20 77 68 65 6e  wn somewhat when
0840: 20 69 74 20 63 6f 6d 65 73 20 74 6f 20 3c 65 6d   it comes to <em
0850: 3e 67 72 61 70 68 73 3c 2f 65 6d 3e 20 2d 20 64  >graphs</em> - d
0860: 61 74 61 20 73 74 72 75 63 74 75 72 65 73 20 77  ata structures w
0870: 68 69 63 68 20 63 61 6e 20 66 6f 72 6d 20 65 6e  hich can form en
0880: 64 6c 65 73 73 20 6c 6f 6f 70 73 20 76 69 61 20  dless loops via 
0890: 72 65 66 65 72 65 6e 63 65 73 20 77 68 69 63 68  references which
08a0: 20 6c 65 61 64 20 62 61 63 6b 20 74 6f 20 74 68   lead back to th
08b0: 65 20 73 61 6d 65 20 63 6f 6e 74 61 69 6e 65 72  e same container
08c0: 2e 0d 0a 0d 0a 63 77 61 6c 20 68 61 73 20 65 78  .....cwal has ex
08d0: 70 65 72 69 6d 65 6e 74 65 64 20 77 69 74 68 20  perimented with 
08e0: 74 77 6f 20 73 6f 6c 75 74 69 6f 6e 73 20 66 6f  two solutions fo
08f0: 72 20 63 61 74 63 68 69 6e 67 2f 62 72 65 61 6b  r catching/break
0900: 69 6e 67 20 63 79 63 6c 65 73 20 64 75 72 69 6e  ing cycles durin
0910: 67 20 64 65 73 74 72 75 63 74 69 6f 6e 2e 20 54  g destruction. T
0920: 68 65 20 66 69 72 73 74 20 6f 6e 65 20 75 73 65  he first one use
0930: 64 20 73 6f 6d 65 20 74 72 69 63 6b 65 72 79 20  d some trickery 
0940: 6f 66 20 72 65 66 65 72 65 6e 63 65 20 63 6f 75  of reference cou
0950: 6e 74 69 6e 67 20 73 6f 20 74 68 61 74 20 6f 6e  nting so that on
0960: 65 20 69 6e 73 74 61 6e 63 65 20 77 6f 75 6c 64  e instance would
0970: 20 66 6f 6f 6c 20 63 6f 6e 73 65 63 75 74 69 76   fool consecutiv
0980: 65 20 64 65 73 74 72 75 63 74 69 6f 6e 73 20 28  e destructions (
0990: 76 69 61 20 63 79 63 6c 65 73 29 20 69 6e 74 6f  via cycles) into
09a0: 20 64 6f 69 6e 67 20 6e 6f 74 68 69 6e 67 2c 20   doing nothing, 
09b0: 61 6c 6c 20 74 68 65 20 77 68 69 6c 65 20 66 75  all the while fu
09c0: 64 67 69 6e 67 20 68 69 73 20 72 65 66 65 72 65  dging his refere
09d0: 6e 63 65 20 63 6f 75 6e 74 20 74 6f 20 6d 61 6b  nce count to mak
09e0: 65 20 73 75 72 65 20 74 68 61 74 20 68 65 20 77  e sure that he w
09f0: 61 73 20 74 68 65 20 6f 6e 65 20 69 6e 20 63 6f  as the one in co
0a00: 6e 74 72 6f 6c 20 6f 66 20 74 68 65 20 66 69 6e  ntrol of the fin
0a10: 61 6c 20 64 65 73 74 72 75 63 74 69 6f 6e 2e 20  al destruction. 
0a20: 54 68 69 73 20 77 61 73 20 72 65 6c 61 74 69 76  This was relativ
0a30: 65 6c 79 20 63 68 65 61 70 20 74 6f 20 69 6d 70  ely cheap to imp
0a40: 6c 65 6d 65 6e 74 20 61 6e 64 20 70 65 72 66 6f  lement and perfo
0a50: 72 6d 65 64 20 72 65 61 73 6f 6e 61 62 6c 79 20  rmed reasonably 
0a60: 77 65 6c 6c 2c 20 62 75 74 20 69 74 20 6f 6e 6c  well, but it onl
0a70: 79 20 77 6f 72 6b 65 64 20 69 6e 20 6c 69 6d 69  y worked in limi
0a80: 74 65 64 20 63 69 72 63 75 6d 73 74 61 6e 63 65  ted circumstance
0a90: 73 20 61 6e 64 20 77 68 65 6e 20 74 68 65 20 63  s and when the c
0aa0: 6c 69 65 6e 74 20 70 61 72 74 69 63 69 70 61 74  lient participat
0ab0: 65 64 20 62 79 20 61 73 6b 69 6e 67 20 61 20 76  ed by asking a v
0ac0: 61 6c 75 65 20 74 6f 20 63 68 65 63 6b 20 69 74  alue to check it
0ad0: 73 65 6c 66 20 66 6f 72 20 63 79 63 6c 65 73 20  self for cycles 
0ae0: 62 65 66 6f 72 65 20 64 65 73 74 72 6f 79 69 6e  before destroyin
0af0: 67 20 69 74 2e 0d 0a 0d 0a 53 6f 20 6f 6e 20 74  g it.....So on t
0b00: 6f 20 70 6c 61 6e 20 42 2e 2e 2e 0d 0a 0d 0a 69  o plan B.......i
0b10: 27 76 65 20 68 61 64 20 74 68 69 73 20 69 64 65  've had this ide
0b20: 61 20 66 6f 72 20 61 20 63 6f 75 70 6c 65 20 79  a for a couple y
0b30: 65 61 72 73 20 74 68 61 74 20 77 65 20 63 61 6e  ears that we can
0b40: 20 62 79 70 61 73 73 20 61 20 6c 6f 74 20 6f 66   bypass a lot of
0b50: 20 74 68 69 73 20 6d 65 73 73 20 75 73 69 6e 67   this mess using
0b60: 20 61 20 73 69 6d 70 6c 65 20 6d 65 63 68 61 6e   a simple mechan
0b70: 69 73 6d 3a 20 77 68 65 6e 20 61 20 76 61 6c 75  ism: when a valu
0b80: 65 20 69 73 20 63 72 65 61 74 65 64 2c 20 69 74  e is created, it
0b90: 20 62 65 6c 6f 6e 67 73 20 74 6f 20 74 68 65 20   belongs to the 
0ba0: 63 75 72 72 65 6e 74 6c 79 20 61 63 74 69 76 65  currently active
0bb0: 20 73 63 6f 70 65 2e 20 49 66 20 74 68 65 20 76   scope. If the v
0bc0: 61 6c 75 65 20 69 73 20 6c 61 74 65 72 20 72 65  alue is later re
0bd0: 66 65 72 65 6e 63 65 64 20 66 72 6f 6d 20 61 20  ferenced from a 
0be0: 68 69 67 68 65 72 20 28 6f 6c 64 65 72 29 20 73  higher (older) s
0bf0: 63 6f 70 65 2c 20 69 74 20 69 73 20 6d 6f 76 65  cope, it is move
0c00: 64 20 69 6e 74 6f 20 74 68 61 74 20 73 63 6f 70  d into that scop
0c10: 65 20 66 6f 72 20 70 61 72 65 6e 74 69 6e 67 20  e for parenting 
0c20: 70 75 72 70 6f 73 65 73 2e 20 41 20 76 61 6c 75  purposes. A valu
0c30: 65 20 69 73 20 6e 65 76 65 72 20 22 64 6f 77 6e  e is never "down
0c40: 2d 73 63 6f 70 65 64 22 20 28 6d 6f 76 65 64 20  -scoped" (moved 
0c50: 74 6f 20 61 20 6e 65 77 65 72 2f 6c 6f 77 65 72  to a newer/lower
0c60: 2d 6c 65 76 65 6c 20 73 63 6f 70 65 29 2c 20 6f  -level scope), o
0c70: 6e 6c 79 20 75 70 2d 73 63 6f 70 65 64 20 28 74  nly up-scoped (t
0c80: 6f 20 61 6e 20 6f 6c 64 65 72 2f 68 69 67 68 65  o an older/highe
0c90: 72 2d 6c 65 76 65 6c 20 73 63 6f 70 65 29 2e 20  r-level scope). 
0ca0: 41 73 20 76 61 72 69 61 62 6c 65 73 20 61 72 65  As variables are
0cb0: 20 61 73 73 69 67 6e 65 64 2c 20 76 61 6c 75 65   assigned, value
0cc0: 73 20 61 72 65 20 69 6e 73 65 72 74 65 64 20 69  s are inserted i
0cd0: 6e 74 6f 20 63 6f 6e 74 61 69 6e 65 72 73 2c 20  nto containers, 
0ce0: 65 74 63 2e 2c 20 61 20 76 61 6c 75 65 27 73 20  etc., a value's 
0cf0: 6f 77 6e 65 72 73 68 69 70 20 63 6f 75 6c 64 20  ownership could 
0d00: 61 6c 77 61 79 73 20 6d 69 67 72 61 74 65 20 74  always migrate t
0d10: 6f 20 74 68 65 20 68 69 67 68 65 73 74 2d 6c 65  o the highest-le
0d20: 76 65 6c 20 73 63 6f 70 65 20 66 72 6f 6d 20 77  vel scope from w
0d30: 68 69 63 68 20 69 74 20 69 73 20 65 76 65 72 20  hich it is ever 
0d40: 72 65 66 65 72 65 6e 63 65 64 20 28 22 72 65 66  referenced ("ref
0d50: 65 72 65 6e 63 65 64 22 20 3d 20 22 69 6e 63 72  erenced" = "incr
0d60: 65 6d 65 6e 74 20 74 68 65 20 72 65 66 65 72 65  ement the refere
0d70: 6e 63 65 20 63 6f 75 6e 74 20 6f 66 20 69 74 20  nce count of it 
0d80: 6f 72 20 6f 6e 65 20 6f 66 20 69 74 73 20 63 6f  or one of its co
0d90: 6e 74 61 69 6e 65 72 20 70 61 72 65 6e 74 73 22  ntainer parents"
0da0: 29 2e 20 57 68 65 6e 20 69 74 20 63 6f 6d 65 73  ). When it comes
0db0: 20 74 69 6d 65 20 74 6f 20 63 6c 65 61 6e 20 75   time to clean u
0dc0: 70 2c 20 69 66 20 6e 6f 20 63 6f 6e 74 61 69 6e  p, if no contain
0dd0: 65 72 20 65 6e 64 73 20 75 70 20 63 6c 65 61 6e  er ends up clean
0de0: 69 6e 67 20 74 68 65 20 76 61 6c 75 65 2c 20 69  ing the value, i
0df0: 74 73 20 6f 77 6e 69 6e 67 20 73 63 6f 70 65 20  ts owning scope 
0e00: 77 69 6c 6c 20 63 6c 65 61 6e 20 69 74 20 75 70  will clean it up
0e10: 2e 0d 0a 0d 0a 50 6c 61 6e 20 42 20 63 6f 73 74  .....Plan B cost
0e20: 73 20 6d 65 20 61 20 73 63 6f 70 65 20 70 6f 69  s me a scope poi
0e30: 6e 74 65 72 20 70 65 72 20 76 61 6c 75 65 2c 20  nter per value, 
0e40: 77 68 69 63 68 20 69 20 72 65 61 6c 6c 79 20 68  which i really h
0e50: 61 74 65 20 28 61 6e 64 20 69 73 20 74 68 65 20  ate (and is the 
0e60: 72 65 61 73 6f 6e 20 69 20 64 69 64 6e 27 74 20  reason i didn't 
0e70: 74 72 79 20 69 74 20 66 69 72 73 74 29 2e 20 42  try it first). B
0e80: 75 74 2e 2e 2e 20 68 61 76 69 6e 67 20 74 68 65  ut... having the
0e90: 20 73 63 6f 70 65 20 69 6e 20 74 68 65 20 62 61   scope in the ba
0ea0: 73 65 20 76 61 6c 75 65 20 69 6e 74 65 72 66 61  se value interfa
0eb0: 63 65 20 61 6c 6c 6f 77 65 64 20 75 73 20 74 6f  ce allowed us to
0ec0: 20 72 65 6d 6f 76 65 2f 63 6f 6e 73 6f 6c 69 64   remove/consolid
0ed0: 61 74 65 20 73 6f 6d 65 20 63 6f 64 65 20 77 68  ate some code wh
0ee0: 69 63 68 20 6f 74 68 65 72 77 69 73 65 20 68 61  ich otherwise ha
0ef0: 73 20 74 6f 20 64 69 73 74 69 6e 67 75 69 73 68  s to distinguish
0f00: 20 62 65 74 77 65 65 6e 20 63 6f 6e 74 61 69 6e   between contain
0f10: 65 72 73 20 61 6e 64 20 61 74 6f 6d 73 2e 20 49  ers and atoms. I
0f20: 74 20 61 6c 73 6f 20 28 69 74 20 74 75 72 6e 73  t also (it turns
0f30: 20 6f 75 74 29 20 63 6f 73 74 73 20 6c 65 73 73   out) costs less
0f40: 20 6d 65 6d 6f 72 79 20 74 68 61 6e 20 74 68 65   memory than the
0f50: 20 61 72 72 61 79 73 20 77 65 20 68 61 64 20 62   arrays we had b
0f60: 65 65 6e 20 75 73 69 6e 67 20 74 6f 20 74 72 61  een using to tra
0f70: 63 6b 20 6f 77 6e 65 72 73 68 69 70 2c 20 61 6e  ck ownership, an
0f80: 64 20 69 6e 68 65 72 65 6e 74 6c 79 20 72 65 6d  d inherently rem
0f90: 6f 76 65 64 20 73 65 76 65 72 61 6c 20 6f 75 74  oved several out
0fa0: 2d 6f 66 2d 6d 65 6d 6f 72 79 20 63 6f 72 6e 65  -of-memory corne
0fb0: 72 73 20 66 72 6f 6d 20 77 68 69 63 68 20 77 65  rs from which we
0fc0: 20 68 61 64 20 6e 6f 20 72 65 63 6f 76 65 72 79   had no recovery
0fd0: 20 73 74 72 61 74 65 67 79 2e 20 53 6f 20 69 74   strategy. So it
0fe0: 20 77 61 73 20 61 20 77 69 6e 20 6f 76 65 72 61   was a win overa
0ff0: 6c 6c 2e 0d 0a 0d 0a 57 68 65 6e 20 61 20 73 63  ll.....When a sc
1000: 6f 70 65 20 63 6c 65 61 6e 73 20 75 70 2c 20 69  ope cleans up, i
1010: 74 20 77 6f 72 6b 73 20 6c 69 6b 65 20 74 68 69  t works like thi
1020: 73 3a 0d 0a 0d 0a 54 72 61 76 65 72 73 65 20 69  s:....Traverse i
1030: 74 73 20 6c 69 73 74 20 6f 66 20 6f 77 6e 65 64  ts list of owned
1040: 20 76 61 6c 75 65 73 20 61 6e 64 20 72 65 64 75   values and redu
1050: 63 65 20 74 68 65 69 72 20 72 65 66 63 6f 75 6e  ce their refcoun
1060: 74 20 62 79 20 31 2e 20 44 6f 69 6e 67 20 73 6f  t by 1. Doing so
1070: 20 77 69 6c 6c 2c 20 69 66 20 74 68 65 20 72 65   will, if the re
1080: 66 63 6f 75 6e 74 20 64 72 6f 70 73 20 74 6f 20  fcount drops to 
1090: 30 20 28 6f 72 20 69 73 20 61 6c 72 65 61 64 79  0 (or is already
10a0: 20 30 2c 20 77 68 69 63 68 20 69 73 20 74 68 65   0, which is the
10b0: 20 63 61 73 65 20 66 6f 72 20 6e 65 77 2c 20 61   case for new, a
10c0: 73 2d 79 65 74 2d 75 6e 72 65 66 65 72 65 6e 63  s-yet-unreferenc
10d0: 65 64 20 76 61 6c 75 65 73 20 28 6b 6e 6f 77 6e  ed values (known
10e0: 20 61 73 20 22 70 72 6f 62 61 74 69 6f 6e 61 72   as "probationar
10f0: 79 22 20 76 61 6c 75 65 73 29 29 2c 20 69 6e 64  y" values)), ind
1100: 69 72 65 63 74 6c 79 20 72 65 6d 6f 76 65 20 74  irectly remove t
1110: 68 65 20 76 61 6c 75 65 20 66 72 6f 6d 20 74 68  he value from th
1120: 65 20 73 63 6f 70 65 27 73 20 6c 69 73 74 20 28  e scope's list (
1130: 61 6e 20 4f 28 31 29 20 6f 70 65 72 61 74 69 6f  an O(1) operatio
1140: 6e 29 2e 20 49 66 20 74 68 61 74 20 76 61 6c 75  n). If that valu
1150: 65 20 69 73 20 61 20 63 6f 6e 74 61 69 6e 65 72  e is a container
1160: 2c 20 69 74 20 6d 69 67 68 74 20 63 6c 65 61 6e  , it might clean
1170: 20 75 70 20 6f 74 68 65 72 20 76 61 6c 75 65 73   up other values
1180: 2c 20 61 20 73 69 64 65 2d 65 66 66 65 63 74 20  , a side-effect 
1190: 6f 66 20 77 68 69 63 68 20 69 73 20 74 68 61 74  of which is that
11a0: 20 74 68 65 20 76 61 6c 75 65 73 20 61 72 65 20   the values are 
11b0: 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65  removed from the
11c0: 69 72 20 70 61 72 65 6e 74 20 73 63 6f 70 65 20  ir parent scope 
11d0: 28 6d 6f 73 74 20 6c 69 6b 65 6c 79 20 74 68 65  (most likely the
11e0: 20 6f 6e 65 20 62 65 69 6e 67 20 63 6c 65 61 6e   one being clean
11f0: 65 64 20 75 70 20 6e 6f 77 29 2e 20 49 66 2c 20  ed up now). If, 
1200: 61 74 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68  at the end of th
1210: 65 20 6c 6f 6f 70 2c 20 74 68 65 20 6c 69 73 74  e loop, the list
1220: 20 73 74 69 6c 6c 20 68 61 73 20 65 6e 74 72 69   still has entri
1230: 65 73 2c 20 72 65 70 65 61 74 20 74 68 69 73 20  es, repeat this 
1240: 70 72 6f 63 65 73 73 2e 2e 2e 20 61 67 61 69 6e  process... again
1250: 20 61 6e 64 20 61 67 61 69 6e 2c 20 75 6e 74 69   and again, unti
1260: 6c 20 69 74 20 68 61 73 20 6e 6f 20 6d 6f 72 65  l it has no more
1270: 20 65 6e 74 72 69 65 73 2e 0d 0a 0d 0a 57 68 61   entries.....Wha
1280: 74 20 74 68 69 73 20 64 6f 65 73 20 69 73 20 69  t this does is i
1290: 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 20 66 72 65  ncrementally fre
12a0: 65 20 75 70 20 65 6e 74 72 69 65 73 20 61 6e 64  e up entries and
12b0: 20 61 6e 79 20 63 79 63 6c 65 73 20 74 68 65 79   any cycles they
12c0: 20 70 61 72 74 69 63 69 70 61 74 65 20 69 6e 2e   participate in.
12d0: 20 54 68 65 20 73 63 6f 70 65 2d 66 6f 6c 6c 6f   The scope-follo
12e0: 77 69 6e 67 20 6d 65 63 68 61 6e 69 73 6d 20 65  wing mechanism e
12f0: 6e 73 75 72 65 73 20 74 68 61 74 20 69 66 20 61  nsures that if a
1300: 20 76 61 6c 75 65 20 69 73 20 62 65 69 6e 67 20   value is being 
1310: 63 6c 65 61 6e 65 64 20 75 70 20 62 79 20 61 20  cleaned up by a 
1320: 73 63 6f 70 65 20 74 68 65 6e 20 74 68 65 72 65  scope then there
1330: 20 63 61 6e 20 62 65 20 6e 6f 20 6f 74 68 65 72   can be no other
1340: 20 72 65 66 65 72 65 6e 63 65 20 74 6f 20 69 74   reference to it
1350: 20 69 6e 20 61 20 68 69 67 68 65 72 2d 6c 65 76   in a higher-lev
1360: 65 6c 20 73 63 6f 70 65 20 28 61 6e 64 20 61 6c  el scope (and al
1370: 6c 20 6c 6f 77 65 72 2d 6c 65 76 65 6c 20 73 63  l lower-level sc
1380: 6f 70 65 73 20 68 61 76 65 20 62 65 65 6e 20 64  opes have been d
1390: 65 73 74 72 6f 79 65 64 20 62 79 20 74 68 69 73  estroyed by this
13a0: 20 70 6f 69 6e 74 29 2e 20 42 79 20 74 72 61 76   point). By trav
13b0: 65 72 73 69 6e 67 20 74 68 65 20 6c 69 73 74 20  ersing the list 
13c0: 72 65 70 65 61 74 65 64 6c 79 2c 20 77 65 20 65  repeatedly, we e
13d0: 6e 64 20 75 70 20 77 65 65 64 69 6e 67 20 6f 75  nd up weeding ou
13e0: 74 20 63 79 63 6c 65 73 20 61 20 6c 61 79 65 72  t cycles a layer
13f0: 20 61 74 20 61 20 74 69 6d 65 2e 20 54 68 65 20   at a time. The 
1400: 63 6f 72 65 2d 6d 6f 73 74 20 76 61 6c 75 65 2d  core-most value-
1410: 66 69 6e 61 6c 69 7a 65 72 20 66 75 6e 63 74 69  finalizer functi
1420: 6f 6e 20 63 61 74 63 68 65 73 20 6e 65 73 74 65  on catches neste
1430: 64 20 66 69 6e 61 6c 69 7a 61 74 69 6f 6e 73 20  d finalizations 
1440: 63 61 75 73 65 64 20 62 79 20 63 79 63 6c 65 73  caused by cycles
1450: 20 61 6e 64 20 44 6f 65 73 20 74 68 65 20 52 69   and Does the Ri
1460: 67 68 74 20 54 68 69 6e 67 28 73 29 20 74 6f 20  ght Thing(s) to 
1470: 61 76 6f 69 64 20 66 72 65 65 69 6e 67 20 61 20  avoid freeing a 
1480: 76 61 6c 75 65 20 6d 6f 72 65 20 74 68 61 6e 20  value more than 
1490: 6f 6e 63 65 2e 20 57 65 20 61 6c 73 6f 20 75 73  once. We also us
14a0: 65 20 61 20 64 65 6c 61 79 65 64 20 64 65 73 74  e a delayed dest
14b0: 72 75 63 74 69 6f 6e 20 6d 65 63 68 61 6e 69 73  ruction mechanis
14c0: 6d 20 68 65 72 65 20 74 6f 20 61 76 6f 69 64 20  m here to avoid 
14d0: 74 68 61 74 20 73 75 63 68 20 61 20 63 79 63 6c  that such a cycl
14e0: 65 20 73 74 65 70 73 20 6f 6e 20 61 20 6a 75 73  e steps on a jus
14f0: 74 2d 66 72 65 65 64 20 63 79 63 6c 65 20 67 61  t-freed cycle ga
1500: 6e 67 20 6d 65 6d 62 65 72 20 28 77 68 69 63 68  ng member (which
1510: 20 64 6f 65 73 20 68 61 70 70 65 6e 2c 20 62 75   does happen, bu
1520: 74 20 69 73 20 68 61 72 6d 6c 65 73 73 20 62 65  t is harmless be
1530: 63 61 75 73 65 20 6f 66 20 74 68 65 20 64 65 6c  cause of the del
1540: 61 79 65 64 2d 67 63 20 71 75 65 75 65 29 2e 0d  ayed-gc queue)..
1550: 0a 0d 0a 54 72 69 76 69 61 3a 20 62 65 63 61 75  ...Trivia: becau
1560: 73 65 20 63 6c 65 61 6e 69 6e 67 20 75 70 20 61  se cleaning up a
1570: 20 76 61 6c 75 65 20 72 65 6d 6f 76 65 73 20 69   value removes i
1580: 74 20 66 72 6f 6d 20 69 74 73 20 73 63 6f 70 65  t from its scope
1590: 20 6c 69 73 74 2c 20 74 68 65 20 69 74 65 72 61   list, the itera
15a0: 74 69 6f 6e 20 64 65 73 63 72 69 62 65 64 20 61  tion described a
15b0: 62 6f 76 65 20 69 73 20 6e 6f 74 20 70 6f 73 73  bove is not poss
15c0: 69 62 6c 65 20 28 77 65 20 63 61 6e 20 65 6e 64  ible (we can end
15d0: 20 75 70 20 74 72 61 76 65 72 73 69 6e 67 20 74   up traversing t
15e0: 68 65 20 6c 69 73 74 20 69 6e 74 6f 20 74 68 65  he list into the
15f0: 20 72 65 63 79 63 6c 65 20 62 69 6e 20 6f 72 20   recycle bin or 
1600: 67 63 20 71 75 65 75 65 29 2e 20 54 68 65 20 61  gc queue). The a
1610: 6c 67 6f 72 69 74 68 6d 20 3c 65 6d 3e 61 63 74  lgorithm <em>act
1620: 75 61 6c 6c 79 3c 2f 65 6d 3e 20 73 69 6d 70 6c  ually</em> simpl
1630: 79 20 75 6e 72 65 66 73 20 74 68 65 20 3c 65 6d  y unrefs the <em
1640: 3e 68 65 61 64 3c 2f 65 6d 3e 20 6f 66 20 74 68  >head</em> of th
1650: 65 20 6c 69 73 74 20 63 6f 6e 74 69 6e 75 61 6c  e list continual
1660: 6c 79 20 75 6e 74 69 6c 20 69 74 73 20 6c 69 73  ly until its lis
1670: 74 20 68 61 73 20 6e 6f 20 68 65 61 64 2e 20 55  t has no head. U
1680: 6e 72 65 66 65 72 65 6e 63 69 6e 67 20 63 61 6e  nreferencing can
1690: 20 6d 6f 64 69 66 79 20 6f 72 20 72 65 6d 6f 76   modify or remov
16a0: 65 20 74 68 65 20 68 65 61 64 20 6f 66 20 74 68  e the head of th
16b0: 65 20 6c 69 73 74 2c 20 73 6f 20 77 65 20 68 61  e list, so we ha
16c0: 76 65 20 74 6f 20 6a 75 73 74 20 6b 65 65 70 20  ve to just keep 
16d0: 75 6e 72 65 66 27 69 6e 67 20 74 68 65 20 68 65  unref'ing the he
16e0: 61 64 20 75 6e 74 69 6c 20 74 68 65 72 65 20 69  ad until there i
16f0: 73 20 6e 6f 20 6d 6f 72 65 20 68 65 61 64 2e 0d  s no more head..
1700: 0a 0d 0a 41 73 73 75 6d 69 6e 67 20 69 20 63 61  ...Assuming i ca
1710: 6e 20 67 65 74 20 74 68 65 20 76 61 6c 75 65 2d  n get the value-
1720: 73 63 6f 70 65 20 70 61 72 65 6e 74 2f 63 68 69  scope parent/chi
1730: 6c 64 20 72 65 6c 61 74 69 6f 6e 73 68 69 70 73  ld relationships
1740: 20 63 6f 72 72 65 63 74 2c 20 69 20 62 65 6c 69   correct, i beli
1750: 65 76 65 20 74 68 69 73 20 61 70 70 72 6f 61 63  eve this approac
1760: 68 20 63 61 6e 20 68 61 6e 64 6c 65 20 66 61 69  h can handle fai
1770: 72 6c 79 20 69 6e 73 61 6e 65 20 67 72 61 70 68  rly insane graph
1780: 73 20 66 6f 72 20 74 68 65 20 6c 6f 77 2c 20 6c  s for the low, l
1790: 6f 77 20 63 6f 73 74 20 6f 66 20 61 20 73 6c 6f  ow cost of a slo
17a0: 77 2d 62 75 74 2d 73 75 72 65 20 61 6c 67 6f 72  w-but-sure algor
17b0: 69 74 68 6d 2e 20 28 41 6e 64 20 69 74 27 73 20  ithm. (And it's 
17c0: 6e 6f 74 20 3c 65 6d 3e 74 68 61 74 3c 2f 65 6d  not <em>that</em
17d0: 3e 20 73 6c 6f 77 20 73 69 6e 63 65 20 69 74 73  > slow since its
17e0: 20 6c 69 73 74 20 6d 61 6e 69 70 75 6c 61 74 69   list manipulati
17f0: 6f 6e 20 68 61 6e 64 6c 69 6e 67 20 63 68 61 6e  on handling chan
1800: 67 65 64 20 66 72 6f 6d 20 61 72 72 61 79 73 20  ged from arrays 
1810: 74 6f 20 6c 69 6e 6b 65 64 20 6c 69 73 74 73 2e  to linked lists.
1820: 20 54 68 65 20 61 6c 67 6f 73 20 61 72 65 20 6e   The algos are n
1830: 6f 77 20 4f 28 31 29 20 61 6e 64 20 68 61 76 65  ow O(1) and have
1840: 20 6e 6f 20 65 78 74 72 61 20 6d 65 6d 6f 72 79   no extra memory
1850: 20 63 6f 73 74 73 2e 29 20 54 65 73 74 69 6e 67   costs.) Testing
1860: 20 68 61 73 20 70 72 6f 76 65 6e 20 69 74 20 74   has proven it t
1870: 6f 20 77 6f 72 6b 20 73 6f 20 66 61 72 20 3a 29  o work so far :)
1880: 2e 0d 0a 0d 0a 54 68 65 72 65 20 61 72 65 20 63  .....There are c
1890: 61 73 65 73 20 77 68 65 72 65 20 61 20 76 61 6c  ases where a val
18a0: 75 65 20 6d 69 67 68 74 20 67 65 74 20 22 73 74  ue might get "st
18b0: 72 61 6e 64 65 64 22 20 66 6f 72 20 75 6e 64 75  randed" for undu
18c0: 6c 79 20 6c 6f 6e 67 20 69 6e 20 61 20 68 69 67  ly long in a hig
18d0: 68 2d 6c 65 76 65 6c 20 73 63 6f 70 65 2c 20 62  h-level scope, b
18e0: 75 74 20 74 68 61 74 20 63 61 73 65 20 63 61 6e  ut that case can
18f0: 20 63 65 72 74 61 69 6e 6c 79 20 62 65 20 68 61   certainly be ha
1900: 6e 64 6c 65 64 20 6f 6e 63 65 20 74 68 65 20 6c  ndled once the l
1910: 69 62 72 61 72 79 20 69 73 20 66 61 72 20 65 6e  ibrary is far en
1920: 6f 75 67 68 20 61 6c 6f 6e 67 20 74 6f 20 74 65  ough along to te
1930: 73 74 20 74 68 69 73 20 6d 6f 72 65 2e 20 54 68  st this more. Th
1940: 65 20 69 6d 70 6f 72 74 61 6e 74 20 74 68 69 6e  e important thin
1950: 67 20 66 6f 72 20 6d 65 2c 20 68 6f 77 65 76 65  g for me, howeve
1960: 72 2c 20 69 73 20 74 68 61 74 20 65 76 65 72 79  r, is that every
1970: 74 68 69 6e 67 20 67 65 74 73 20 63 6c 65 61 6e  thing gets clean
1980: 65 64 20 77 68 65 6e 20 74 68 65 20 61 70 70 72  ed when the appr
1990: 6f 70 72 69 61 74 65 20 73 63 6f 70 65 20 69 73  opriate scope is
19a0: 20 70 6f 70 70 65 64 2e 20 69 2e 65 2e 20 64 65   popped. i.e. de
19b0: 74 65 72 6d 69 6e 69 73 74 69 63 20 66 69 6e 61  terministic fina
19c0: 6c 69 7a 61 74 69 6f 6e 20 28 74 68 6f 75 67 68  lization (though
19d0: 20 74 68 65 20 65 78 61 63 74 20 6f 72 64 65 72   the exact order
19e0: 20 6f 66 20 66 69 6e 61 6c 69 7a 61 74 69 6f 6e   of finalization
19f0: 20 63 61 6e 6e 6f 74 20 62 65 20 73 74 72 69 63   cannot be stric
1a00: 74 6c 79 20 64 65 66 69 6e 65 64 20 66 6f 72 20  tly defined for 
1a10: 73 6f 6d 65 20 63 61 73 65 73 29 2e 20 69 20 77  some cases). i w
1a20: 6f 75 6c 64 20 61 6c 73 6f 20 6c 69 6b 65 20 74  ould also like t
1a30: 68 65 20 6f 70 74 69 6f 6e 20 6f 66 20 6d 61 6e  he option of man
1a40: 75 61 6c 20 6d 61 6e 61 67 65 6d 65 6e 74 2c 20  ual management, 
1a50: 77 68 65 72 65 20 74 68 65 72 65 20 69 73 20 6e  where there is n
1a60: 6f 20 73 63 6f 70 65 20 28 6f 72 20 76 61 6c 75  o scope (or valu
1a70: 65 73 20 61 72 65 20 68 61 6e 64 6c 65 64 20 6f  es are handled o
1a80: 75 74 73 69 64 65 20 6f 66 20 61 6e 79 20 73 63  utside of any sc
1a90: 6f 70 65 29 2c 20 62 75 74 20 74 68 61 74 20 69  ope), but that i
1aa0: 73 20 6f 66 20 73 65 63 6f 6e 64 61 72 79 20 63  s of secondary c
1ab0: 6f 6e 63 65 72 6e 20 28 61 6e 64 20 6e 6f 74 20  oncern (and not 
1ac0: 79 65 74 20 68 61 6e 64 6c 65 64 20 62 79 20 74  yet handled by t
1ad0: 68 65 20 41 50 49 29 2e 0d 0a 0d 0a 48 6f 77 20  he API).....How 
1ae0: 77 65 6c 6c 20 64 6f 65 73 20 74 68 69 73 20 61  well does this a
1af0: 63 74 75 61 6c 6c 79 20 77 6f 72 6b 3f 20 53 6f  ctually work? So
1b00: 20 66 61 72 2c 20 73 6f 20 67 6f 6f 64 2c 20 62   far, so good, b
1b10: 75 74 20 6d 75 63 68 20 6d 6f 72 65 20 65 78 70  ut much more exp
1b20: 65 72 69 6d 65 6e 74 61 74 69 6f 6e 20 69 73 20  erimentation is 
1b30: 6e 65 65 64 65 64 20 62 65 66 6f 72 65 20 69 20  needed before i 
1b40: 63 61 6e 20 63 6c 61 69 6d 20 61 6e 79 20 73 6f  can claim any so
1b50: 72 74 20 6f 66 20 76 69 63 74 6f 72 79 20 6f 76  rt of victory ov
1b60: 65 72 20 63 79 63 6c 65 73 2e 20 49 74 20 68 61  er cycles. It ha
1b70: 73 20 62 65 65 6e 20 73 68 6f 77 6e 20 74 6f 20  s been shown to 
1b80: 68 61 6e 64 6c 65 20 73 65 76 65 72 61 6c 20 6c  handle several l
1b90: 65 76 65 6c 73 20 6f 66 20 73 63 6f 70 65 20 64  evels of scope d
1ba0: 69 72 65 63 74 69 6f 6e 20 62 65 74 77 65 65 6e  irection between
1bb0: 20 6f 62 6a 65 63 74 73 2c 20 77 69 74 68 20 72   objects, with r
1bc0: 65 66 65 72 65 6e 63 65 73 20 67 6f 69 6e 67 20  eferences going 
1bd0: 69 6e 20 62 6f 74 68 20 64 69 72 65 63 74 69 6f  in both directio
1be0: 6e 73 20 61 6e 64 20 65 6e 74 72 69 65 73 20 63  ns and entries c
1bf0: 72 69 73 73 2d 63 72 6f 73 73 69 6e 67 20 61 6c  riss-crossing al
1c00: 6f 6e 67 20 74 68 65 20 77 61 79 2e 20 46 6f 72  ong the way. For
1c10: 20 65 78 61 6d 70 6c 65 2c 20 74 68 65 20 63 61   example, the ca
1c20: 73 65 20 6f 66 20 61 6e 20 4f 62 6a 65 63 74 20  se of an Object 
1c30: 77 68 69 63 68 20 63 6f 6e 74 61 69 6e 73 20 61  which contains a
1c40: 20 73 69 6e 67 6c 65 20 6b 65 79 2f 76 61 6c 75   single key/valu
1c50: 65 20 70 61 69 72 20 28 70 72 6f 70 65 72 74 79  e pair (property
1c60: 29 3a 20 28 69 74 73 65 6c 66 2c 20 69 74 73 65  ): (itself, itse
1c70: 6c 66 29 2e 20 48 6f 77 20 74 6f 20 63 6c 65 61  lf). How to clea
1c80: 6e 20 74 68 61 74 20 75 70 20 70 72 6f 70 65 72  n that up proper
1c90: 6c 79 20 69 73 20 61 6e 20 69 6e 74 65 72 65 73  ly is an interes
1ca0: 74 69 6e 67 20 65 78 65 72 63 69 73 65 2c 20 61  ting exercise, a
1cb0: 6e 64 20 63 77 61 6c 20 68 61 6e 64 6c 65 73 20  nd cwal handles 
1cc0: 69 74 20 63 6f 72 72 65 63 74 6c 79 2e 0d 0a 0d  it correctly....
1cd0: 0a 4f 6e 65 20 6f 66 20 74 68 65 20 74 72 69 63  .One of the tric
1ce0: 6b 73 20 77 65 20 75 73 65 20 74 6f 20 61 76 6f  ks we use to avo
1cf0: 69 64 20 73 74 6f 6d 70 69 6e 67 20 61 20 64 65  id stomping a de
1d00: 73 74 72 6f 79 65 64 2f 75 6e 64 65 72 2d 64 65  stroyed/under-de
1d10: 73 74 72 75 63 74 69 6f 6e 20 6f 62 6a 65 63 74  struction object
1d20: 20 77 68 65 6e 20 77 65 20 65 6e 63 6f 75 6e 74   when we encount
1d30: 65 72 20 63 79 63 6c 65 73 20 69 73 20 74 6f 20  er cycles is to 
1d40: 74 65 6d 70 6f 72 61 72 69 6c 79 20 22 66 61 6b  temporarily "fak
1d50: 65 22 20 74 68 65 20 64 65 73 74 72 75 63 74 69  e" the destructi
1d60: 6f 6e 20 6f 66 20 63 6f 6e 74 61 69 6e 65 72 73  on of containers
1d70: 20 69 66 20 74 68 65 79 20 61 72 65 20 64 65 73   if they are des
1d80: 74 72 6f 79 65 64 20 64 75 72 69 6e 67 20 61 20  troyed during a 
1d90: 73 63 6f 70 65 2d 70 6f 70 2e 20 41 20 66 72 65  scope-pop. A fre
1da0: 65 27 64 20 63 6f 6e 74 61 69 6e 65 72 20 77 69  e'd container wi
1db0: 6c 6c 2c 20 69 6e 73 74 65 61 64 20 6f 66 20 67  ll, instead of g
1dc0: 6f 69 6e 67 20 69 6e 74 6f 20 74 68 65 20 72 65  oing into the re
1dd0: 63 79 63 6c 65 20 62 69 6e 20 6f 72 20 62 65 20  cycle bin or be 
1de0: 69 6d 6d 65 64 69 61 74 65 6c 79 20 66 72 65 65  immediately free
1df0: 64 2c 20 67 6f 20 69 6e 74 6f 20 61 20 64 65 6c  d, go into a del
1e00: 61 79 65 64 2d 64 65 73 74 72 75 63 74 69 6f 6e  ayed-destruction
1e10: 20 71 75 65 75 65 2e 20 54 68 69 73 20 61 6c 6c   queue. This all
1e20: 6f 77 73 20 69 73 20 74 6f 20 62 65 20 73 61 66  ows is to be saf
1e30: 65 6c 79 20 72 65 66 65 72 65 6e 63 65 64 20 28  ely referenced (
1e40: 64 65 73 70 69 74 65 20 69 74 73 20 72 65 66 63  despite its refc
1e50: 6f 75 6e 74 20 6f 66 20 30 29 20 74 68 72 6f 75  ount of 0) throu
1e60: 67 68 6f 75 74 20 74 68 65 20 64 65 73 74 72 75  ghout the destru
1e70: 63 74 69 6f 6e 20 72 75 6e 2e 20 57 68 65 6e 20  ction run. When 
1e80: 74 68 65 20 73 63 6f 70 65 20 68 61 73 20 66 69  the scope has fi
1e90: 6e 69 73 68 65 64 20 70 6f 70 70 69 6e 67 2c 20  nished popping, 
1ea0: 74 68 65 20 66 72 65 65 2d 71 75 65 75 65 20 69  the free-queue i
1eb0: 73 20 70 75 73 68 65 64 20 69 6e 74 6f 20 74 68  s pushed into th
1ec0: 65 20 72 65 63 79 63 6c 69 6e 67 20 62 69 6e 20  e recycling bin 
1ed0: 6f 72 20 28 69 66 20 74 68 61 74 27 73 20 66 75  or (if that's fu
1ee0: 6c 6c 20 6f 72 20 74 75 72 6e 65 64 20 6f 66 66  ll or turned off
1ef0: 29 20 69 74 20 69 73 20 66 72 65 65 64 2e 20 4e  ) it is freed. N
1f00: 6f 6e 2d 63 6f 6e 74 61 69 6e 65 72 73 20 64 6f  on-containers do
1f10: 20 6e 6f 74 20 6e 65 65 64 20 74 6f 20 68 61 6e   not need to han
1f20: 64 6c 65 20 74 68 65 20 70 6f 73 74 2d 64 65 61  dle the post-dea
1f30: 74 68 2d 74 6f 75 63 68 69 6e 67 20 63 61 73 65  th-touching case
1f40: 2c 20 73 69 6e 63 65 20 74 68 65 79 20 63 61 6e  , since they can
1f50: 6e 6f 74 20 70 61 72 74 69 63 69 70 61 74 65 20  not participate 
1f60: 69 6e 20 63 79 63 6c 65 73 2e 20 54 68 69 73 20  in cycles. This 
1f70: 71 75 65 75 65 20 69 73 20 6d 61 6e 61 67 65 64  queue is managed
1f80: 20 75 73 69 6e 67 20 74 68 65 20 6c 69 6e 6b 65   using the linke
1f90: 64 2d 6c 69 73 74 20 77 68 69 63 68 20 56 61 6c  d-list which Val
1fa0: 75 65 73 20 70 72 6f 76 69 64 65 2c 20 73 6f 20  ues provide, so 
1fb0: 69 74 20 63 6f 73 74 73 20 75 73 20 6e 6f 20 61  it costs us no a
1fc0: 64 64 69 74 69 6f 6e 61 6c 20 6d 65 6d 6f 72 79  dditional memory
1fd0: 20 61 6e 64 20 69 6e 73 65 72 74 69 6f 6e 20 6f   and insertion o
1fe0: 66 20 6e 65 77 20 65 6e 74 72 69 65 73 20 69 73  f new entries is
1ff0: 20 4f 28 31 29 2e 20 69 2e 65 2e 20 74 68 69 73   O(1). i.e. this
2000: 20 63 6f 73 74 73 20 75 73 20 6e 6f 20 65 78 74   costs us no ext
2010: 72 61 20 6d 65 6d 6f 72 79 2c 20 76 65 72 79 20  ra memory, very 
2020: 6c 69 74 74 6c 65 20 74 69 6d 65 2c 20 61 6e 64  little time, and
2030: 20 73 63 61 6c 65 73 20 74 6f 20 61 6e 20 61 72   scales to an ar
2040: 62 69 74 72 61 72 79 20 6e 75 6d 62 65 72 20 6f  bitrary number o
2050: 66 20 76 61 6c 75 65 73 20 77 69 74 68 20 6e 6f  f values with no
2060: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 68 69 74   performance hit
2070: 20 6f 6e 20 74 68 65 20 63 6f 72 65 20 6c 69 73   on the core lis
2080: 74 20 6f 70 73 2e 0d 0a 0d 0a 52 65 67 61 72 64  t ops.....Regard
2090: 69 6e 67 20 72 65 66 65 72 65 6e 63 65 20 63 6f  ing reference co
20a0: 75 6e 74 69 6e 67 3a 0d 0a 0d 0a 57 68 65 6e 20  unting:....When 
20b0: 61 20 6e 65 77 20 56 61 6c 75 65 20 69 73 20 63  a new Value is c
20c0: 72 65 61 74 65 64 2c 20 69 74 73 20 69 6e 69 74  reated, its init
20d0: 69 61 6c 20 72 65 66 65 72 65 6e 63 65 20 63 6f  ial reference co
20e0: 75 6e 74 20 69 73 20 30 2c 20 6e 6f 74 20 31 2e  unt is 0, not 1.
20f0: 20 41 20 76 61 6c 75 65 20 77 69 74 68 20 61 20   A value with a 
2100: 72 65 66 63 6f 75 6e 74 20 6f 66 20 30 20 69 73  refcount of 0 is
2110: 20 63 61 6c 6c 65 64 20 22 70 72 6f 62 61 74 69   called "probati
2120: 6f 6e 61 72 79 22 2c 20 61 6e 64 20 6d 61 79 20  onary", and may 
2130: 62 65 20 63 6c 65 61 6e 65 64 20 75 70 20 61 74  be cleaned up at
2140: 20 6e 65 61 72 6c 79 20 61 6e 79 20 61 72 62 69   nearly any arbi
2150: 74 72 61 72 79 20 74 69 6d 65 20 62 79 20 74 68  trary time by th
2160: 65 20 63 77 61 6c 20 65 6e 67 69 6e 65 2e 20 54  e cwal engine. T
2170: 68 65 20 63 75 72 72 65 6e 74 20 72 75 6c 65 20  he current rule 
2180: 69 73 3a 20 61 6e 79 20 63 61 6c 6c 20 69 6e 74  is: any call int
2190: 6f 20 74 68 65 20 41 50 49 20 77 68 69 63 68 20  o the API which 
21a0: 74 61 6b 65 73 20 61 20 3c 74 74 3e 63 77 61 6c  takes a <tt>cwal
21b0: 5f 65 6e 67 69 6e 65 3c 2f 74 74 3e 20 70 6f 69  _engine</tt> poi
21c0: 6e 74 65 72 20 61 72 67 75 6d 65 6e 74 20 68 61  nter argument ha
21d0: 73 20 74 68 65 20 3c 65 6d 3e 70 6f 74 65 6e 74  s the <em>potent
21e0: 69 61 6c 2f 70 65 72 6d 69 73 73 69 6f 6e 3c 2f  ial/permission</
21f0: 65 6d 3e 20 74 6f 20 63 6c 65 61 6e 20 75 70 20  em> to clean up 
2200: 70 72 6f 62 61 74 69 6f 6e 61 72 79 20 76 61 6c  probationary val
2210: 75 65 73 2e 20 56 61 6c 75 65 73 20 77 68 69 63  ues. Values whic
2220: 68 20 61 72 65 20 72 65 66 65 72 65 6e 63 65 64  h are referenced
2230: 20 6f 6e 63 65 2c 20 65 69 74 68 65 72 20 76 69   once, either vi
2240: 61 20 61 20 63 61 6c 6c 20 74 6f 20 3c 74 74 3e  a a call to <tt>
2250: 63 77 61 6c 5f 76 61 6c 75 65 5f 72 65 66 28 29  cwal_value_ref()
2260: 3c 2f 74 74 3e 20 6f 72 20 62 79 20 69 6e 73 65  </tt> or by inse
2270: 72 74 69 6e 67 20 74 68 65 20 76 61 6c 75 65 20  rting the value 
2280: 69 6e 74 6f 20 61 20 63 6f 6e 74 61 69 6e 65 72  into a container
2290: 20 28 77 68 69 63 68 20 69 74 73 65 6c 66 20 6d   (which itself m
22a0: 61 79 20 62 65 20 70 72 6f 62 61 74 69 6f 6e 61  ay be probationa
22b0: 72 79 21 29 2c 20 74 68 65 79 20 61 72 65 20 6d  ry!), they are m
22c0: 6f 76 65 64 20 6f 75 74 20 6f 66 20 70 72 6f 62  oved out of prob
22d0: 61 74 69 6f 6e 61 72 79 20 73 74 61 74 75 73 20  ationary status 
22e0: 61 6e 64 20 6e 6f 74 20 73 75 62 6a 65 63 74 20  and not subject 
22f0: 74 6f 20 61 72 62 69 74 72 61 72 79 20 73 77 65  to arbitrary swe
2300: 65 70 69 6e 67 2e 20 54 68 65 20 22 73 77 65 65  eping. The "swee
2310: 70 22 20 6f 70 65 72 61 74 69 6f 6e 20 63 61 6e  p" operation can
2320: 20 62 65 20 74 72 69 67 67 65 72 65 64 20 62 79   be triggered by
2330: 20 74 68 65 20 63 6c 69 65 6e 74 20 61 6e 64 20   the client and 
2340: 77 69 6c 6c 20 69 6d 6d 65 64 69 61 74 65 6c 79  will immediately
2350: 20 63 6c 65 61 6e 20 75 70 20 61 6e 79 20 70 72   clean up any pr
2360: 6f 62 61 74 69 6f 6e 61 72 79 20 76 61 6c 75 65  obationary value
2370: 73 20 69 6e 20 74 68 65 20 63 75 72 72 65 6e 74  s in the current
2380: 20 73 63 6f 70 65 2e 20 50 72 6f 62 61 74 69 6f   scope. Probatio
2390: 6e 61 72 79 20 76 61 6c 75 65 73 20 61 72 65 20  nary values are 
23a0: 6b 65 70 74 20 69 6e 20 61 20 73 65 70 61 72 61  kept in a separa
23b0: 74 65 20 6c 69 73 74 20 66 72 6f 6d 20 22 6e 6f  te list from "no
23c0: 72 6d 61 6c 22 20 76 61 6c 75 65 73 2c 20 73 6f  rmal" values, so
23d0: 20 63 6c 65 61 6e 75 70 20 69 73 20 61 20 73 69   cleanup is a si
23e0: 6d 70 6c 65 20 4f 28 4e 29 20 6f 70 65 72 61 74  mple O(N) operat
23f0: 69 6f 6e 2c 20 77 68 65 72 65 20 4e 20 69 73 20  ion, where N is 
2400: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 70 72  the number of pr
2410: 6f 62 61 74 69 6f 6e 61 72 79 20 76 61 6c 75 65  obationary value
2420: 73 2e 20 57 68 65 6e 20 61 20 76 61 6c 75 65 27  s. When a value'
2430: 73 20 72 65 66 65 72 65 6e 63 65 20 63 6f 75 6e  s reference coun
2440: 74 20 72 65 61 63 68 65 73 20 31 20 66 6f 72 20  t reaches 1 for 
2450: 74 68 65 20 66 69 72 73 74 20 74 69 6d 65 2c 20  the first time, 
2460: 69 74 20 69 73 20 6d 6f 76 65 64 20 6f 75 74 20  it is moved out 
2470: 6f 66 20 74 68 65 20 70 72 6f 62 61 74 69 6f 6e  of the probation
2480: 61 72 79 20 73 74 61 74 65 20 61 6e 64 20 69 6e  ary state and in
2490: 74 6f 20 61 20 22 6c 6f 6e 67 65 72 20 6c 69 76  to a "longer liv
24a0: 65 64 22 20 73 74 61 74 75 73 20 28 61 6e 64 20  ed" status (and 
24b0: 61 6e 6f 74 68 65 72 20 6c 69 73 74 29 2e 0d 0a  another list)...
24c0: 0a 5a 20 30 64 39 36 35 39 61 66 32 35 65 64 64  .Z 0d9659af25edd
24d0: 32 34 30 64 31 31 34 33 64 63 30 64 66 33 62 33  240d1143dc0df3b3
24e0: 66 65 64 0a                                      fed.