Changeset 7080


Ignore:
Timestamp:
Feb 25, 2016, 12:27:33 PM (6 years ago)
Author:
Nicklas Nordborg
Message:

References #1148: Removing items from trashcan when circular references exists

The trashcan implementation can now detect items that have circulare references. It doesn't yet know how to to break them though.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/core/net/sf/basedb/core/Trashcan.java

    r7034 r7080  
    3636import java.util.Collection;
    3737import java.util.Collections;
     38import java.util.HashSet;
    3839import java.util.Iterator;
     40import java.util.LinkedList;
    3941import java.util.List;
    4042import java.util.Set;
     
    297299          if (dc != null) dc.close();
    298300        }
     301       
     302        if (removedInTransaction == 0 && itemsToRemove.size() > 0)
     303        {
     304          // Not all items could be removed, try to break circular references
     305          // Note that as a (desired) side-effect non-removable items will be
     306          // removed from 'itemsToRemove'
     307          removedInTransaction = breakCircularReferences(sc2, itemsToRemove);
     308          if (isDebug)
     309          {
     310            log.debug("Removed " + removedInTransaction + " circular references; " +
     311              itemsToRemove.size() + " remains in list");
     312          }
     313        }
     314
    299315      } while (removedInTransaction > 0 && itemsToRemove.size() > 0);
    300316    }
     
    354370  }
    355371 
     372  private static int breakCircularReferences(SessionControl sc, Set<Identifiable> itemsToRemove)
     373  {
     374    if (isDebug) log.debug("Trying to break circular references: " + itemsToRemove);
     375   
     376    DbControl dc = sc.newDbControl();
     377    int circularRefsBroken = 0;
     378    try
     379    {
     380
     381      // Prepare by loading the using-items for all itemsToRemove
     382      List<CircularRefInfo> cRef = new LinkedList<CircularRefInfo>();
     383      // The proxies will speed up the checks
     384      Set<ItemProxy> itemsToRemoveProxy = new HashSet<ItemProxy>();
     385      for (Identifiable item : itemsToRemove)
     386      {
     387        CircularRefInfo c = new CircularRefInfo(dc, item);
     388        cRef.add(c);
     389        itemsToRemoveProxy.add(c.proxy);
     390      }
     391     
     392      // The strategy is to check which items in the itemsToRemove collection
     393      // that can never be removed since they have references to items that are
     394      // not in the itemsToRemove collection.
     395      // Such items are removed from the itemsToRemove collection
     396      // We need to to iterate until the itemsToRemove collection is stable
     397      // All remaining items are items that only have references to other items
     398      // in the itemsToRemove.... We have found the ones with circular references!!
     399      int numUnremovable;
     400      do
     401      {
     402        numUnremovable = 0;
     403        Iterator<CircularRefInfo> it = cRef.iterator();
     404        while (it.hasNext())
     405        {
     406          CircularRefInfo c = it.next();
     407          // For a given item 'c.item', if it has any using-item that is not
     408          // found among itemsToRemove 'c.item' can't be removed
     409          if (c.isUsingNonRemovableItem(itemsToRemoveProxy))
     410          {
     411            // 3. Remove 'c' from itemsToRemove and other collections
     412            itemsToRemove.remove(c.item);
     413            itemsToRemoveProxy.remove(c.proxy);
     414            it.remove();
     415            numUnremovable++;
     416          }
     417        }
     418       
     419      } while(itemsToRemove.size() > 0 && numUnremovable > 0);
     420      // Repeat until no more items are removed from itemsToRemove
     421     
     422      // The remaining items in itemsToRemove are those with possible circular references
     423      if (isDebug) log.debug(itemsToRemove.size() + " remaining items with circular ref: " + itemsToRemove);
     424     
     425      // Break circular references
     426      for (CircularRefInfo c : cRef)
     427      {
     428        circularRefsBroken += c.breakReferences(dc, itemsToRemove);
     429      }
     430     
     431      dc.commit();
     432         
     433    }
     434    finally
     435    {
     436      if (dc != null) dc.close();
     437    }
     438    return circularRefsBroken;
     439  }
     440
     441  /**
     442    Helper class for holding information about a single
     443    item, other items using it and other information that is
     444    relevant for resolving circular references.
     445    @since 3.8
     446  */
     447  static class CircularRefInfo
     448  {
     449    final Identifiable item;
     450    final ItemProxy proxy;
     451    final Set<ItemProxy> usingItems;
     452   
     453    public CircularRefInfo(DbControl dc, Identifiable item)
     454    {
     455      this.item = item;
     456      this.proxy = new ItemProxy(item.getId(), item.getType());
     457      this.usingItems = proxy.getItem(dc).getUsingItems();
     458    }
     459   
     460    /**
     461      Check if all using items of the main items is found among the
     462      'itemsToRemove'. If not, this item can't be removed even
     463      if circular references are broken.
     464      @return True if this item is using a non-removable item, false otherwise
     465    */
     466    boolean isUsingNonRemovableItem(Set<ItemProxy> itemsToRemove)
     467    {
     468      for (ItemProxy p : usingItems)
     469      {
     470        if (itemsToRemove.contains(p))
     471        {
     472          if (isDebug) log.debug(item+" has possible circular ref to: "+p);
     473        }
     474        else
     475        {
     476          if (isDebug) log.debug(item+" has ref to non-removable item: "+p);
     477          return true;
     478        }
     479      }
     480      return false;
     481    }
     482   
     483    /**
     484      Break all references from this item to the items in itemsToRemove.
     485      @return The number of references broken
     486    */
     487    int breakReferences(DbControl dc, Set<Identifiable> itemsToRemove)
     488    {
     489      // TODO
     490      return 0;
     491    }
     492   
     493   
     494  }
     495 
    356496}
Note: See TracChangeset for help on using the changeset viewer.