Re: module GC bug

[Marius Vollmer]

Han-Wen Nienhuys <address@hidden> writes:

>> I think the right fix is to change the weak hashtable marking
>> algorithm to properly cope with circular references like this.  I will
>> try this and then come back to you.  
>
> Interesting. How would you go about doing that?

The marking would would rougly look like this (some special cases are
not considered, like improper alists):

    mark OBJ:
      if mark of OBJ is set:
        return
      set mark of OBJ
      if OBJ is a weak vector
        put it on POSTPONED_OBJECTS
      else
        mark references of OBJ

    gc:
      POSTPONED_OBJECTS = '()
      mark all root references
      while POSTPONED_OBJECTS not empty
        OBJS = POSTPONED_OBJECTS
        POSTPONED_OBJECTS = '()
        mark_weak_vector all OBJS
      sweep   

    mark_weak_vector OBJ:
      for all elements ELT of OBJ:
        for all pairs P on list ELT:
          if P is marked, break
          ITEM = car of P
          if ITEM is a pair:
            if (OBJ has weak keys and car of ITEM is unmarked)
            or (OBJ has weak values and cdr of ITEM is unmarked)
              remove P from ELT
            else:
              mark ITEM (recursively)
              set mark of P

The non-trivial stuff is to integrate this properly with the abstract
hashtables (but I have basically done this already as well).

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405