single valued attribute conflict resolution : issue 609

gbellato

04.36.2007 dcc67378350418e11e50e72996c24b61f1ea8f81

single valued attribute conflict resolution : issue 609

The resolution procedure for single valued attribute needs to be slightly different
from the mult-valued attribute procedure :
- less historical information can be kept
- the procedure must take into account the fact that only one value is allowed
 at a given time.

This Change splits the AttrInfo class into 2 classes :
AttrInfoSingle and AttrInfoMultiple that both extends AttributeInfo.
The Historical class if also refactorized to become more generic, some code
was staying there but was indeed specific to multi-valued attribute.

This change also add a number of unit tests for single valued attribute, and enable
an old test from HistoricalTest.java that was previously disabled because
conflict resolution for single valued attribute was not yet implemented.

 opends/src/server/org/opends/server/messages/ReplicationMessages.java

@@ -395,6 +395,11 @@
  public static final int MSGID_DUPLICATE_REPLICATION_SERVER_ID =
    CATEGORY_MASK_SYNC | SEVERITY_MASK_SEVERE_ERROR | 55;

  /**
   * Some bad historical information was found in an entry.
   */
  public static final int MSGID_BAD_HISTORICAL =
    CATEGORY_MASK_SYNC | SEVERITY_MASK_SEVERE_ERROR | 56;


  /**
@@ -542,5 +547,8 @@
        "Received a Null Msg from %s");
    registerMessage(MSGID_READER_EXCEPTION,
        "Exception when reading messages from %s");
    registerMessage(MSGID_BAD_HISTORICAL,
        "Entry %s was containing some unknown historical information,"
        + " This may cause some inconsistency for this entry");
  }
}

 opends/src/server/org/opends/server/replication/plugin/AttrInfo.java

File was deleted

 opends/src/server/org/opends/server/replication/plugin/AttrInfoMultiple.java

New file
@@ -0,0 +1,653 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.replication.plugin;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

import org.opends.server.replication.common.ChangeNumber;
import org.opends.server.types.Attribute;
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.Entry;
import org.opends.server.types.Modification;
import org.opends.server.types.ModificationType;


/**
 * This classes is used to store historical information for multiple valued
 * attributes.
 * One object of this type is created for each attribute that was changed in
 * the entry.
 * It allows to record the last time a given value was added, the last
 * time a given value was deleted and the last time the whole attribute was
 * deleted.
 */
public class AttrInfoMultiple extends AttributeInfo
{
   private ChangeNumber deleteTime, // last time when the attribute was deleted
                        lastUpdateTime; // last time the attribute was modified
   private ArrayList<ValueInfo> valuesInfo; // creation or deletion time for
                                            // given values
  /**
    * create a new AttrInfo object.
    * @param deleteTime the deletion time
    * @param updateTime the update time
    * @param valuesInfo of Value Info
    */
   public AttrInfoMultiple(ChangeNumber deleteTime, ChangeNumber updateTime,
       ArrayList<ValueInfo> valuesInfo)
   {
     this.deleteTime = deleteTime;
     this.lastUpdateTime = updateTime;
     if (valuesInfo == null)
       this.valuesInfo = new ArrayList<ValueInfo>();
     else
       this.valuesInfo = valuesInfo;
   }

   /**
    * create a new empty AttrInfo object.
    */
   public AttrInfoMultiple()
   {
     this.deleteTime = null;
     this.lastUpdateTime = null;
     this.valuesInfo = new ArrayList<ValueInfo>();
   }

   /**
    * Returns the last time when the entry was updated.
    * @return the last time when the entry was updated
    */
   private ChangeNumber getLastUpdateTime()
   {
     return lastUpdateTime;
   }

   /**
    * Returns the last time when the attribute was deleted.
    *
    * @return the last time when the attribute was deleted
    */
   public ChangeNumber getDeleteTime()
   {
     return deleteTime;
   }

   /**
    * Duplicate an AttrInfo.
    * ChangeNumber are duplicated by references
    * @return the duplicated AttrInfo
    */
   AttrInfoMultiple duplicate()
   {
     AttrInfoMultiple dup =
       new AttrInfoMultiple(this.deleteTime, this.lastUpdateTime,
           this.valuesInfo);
     return dup;
   }

   /**
    * Delete all historical information that is older than
    * the provided ChangeNumber for this attribute type.
    * Add the delete attribute state information
    * @param CN time when the delete was done
    */
   protected void delete(ChangeNumber CN)
   {
     // iterate through the values in the valuesInfo
     // and suppress all the values that have not been added
     // after the date of this delete.
     Iterator<ValueInfo> it = this.valuesInfo.iterator();
     while (it.hasNext())
     {
       ValueInfo info = it.next();
       if (CN.newerOrEquals(info.getValueUpdateTime()))
         it.remove();
     }

     if (CN.newer(deleteTime))
     {
       deleteTime = CN;
     }

     if (CN.newer(lastUpdateTime))
     {
       lastUpdateTime = CN;
     }
   }

   /**
    * Change historical information after a delete value.
    * @param val value that was deleted
    * @param CN time when the delete was done
    */
   protected void delete(AttributeValue val, ChangeNumber CN)
   {
     ValueInfo info = new ValueInfo(val, null, CN);
     this.valuesInfo.remove(info);
     this.valuesInfo.add(info);
     if (CN.newer(lastUpdateTime))
     {
       lastUpdateTime = CN;
     }
   }

   /**
    * Change historical information after a delete of a set of values.
    *
    * @param values values that were deleted
    * @param CN time when the delete was done
    */
   protected void delete(LinkedHashSet<AttributeValue> values, ChangeNumber CN)
   {
     for (AttributeValue val : values)
     {
       ValueInfo info = new ValueInfo(val, null, CN);
       this.valuesInfo.remove(info);
       this.valuesInfo.add(info);
       if (CN.newer(lastUpdateTime))
       {
         lastUpdateTime = CN;
       }
     }
   }

   /**
    * Update the historical information when a value is added.
    *
    * @param val values that was added
    * @param CN time when the value was added
    */
   protected void add(AttributeValue val, ChangeNumber CN)
   {
     ValueInfo info = new ValueInfo(val, CN, null);
     this.valuesInfo.remove(info);
     valuesInfo.add(info);
     if (CN.newer(lastUpdateTime))
     {
       lastUpdateTime = CN;
     }
   }

   /**
    * Update the historical information when values are added.
    *
    * @param values the set of added values
    * @param CN time when the add is done
    */
   private void add(LinkedHashSet<AttributeValue> values,
            ChangeNumber CN)
   {
     for (AttributeValue val : values)
     {
       ValueInfo info = new ValueInfo(val, CN, null);
       this.valuesInfo.remove(info);
       valuesInfo.add(info);
       if (CN.newer(lastUpdateTime))
       {
         lastUpdateTime = CN;
       }
     }
   }

  /**
   * Get the List of ValueInfo for this attribute Info.
   *
   * @return the List of ValueInfo
   */
  public ArrayList<ValueInfo> getValuesInfo()
  {
    return valuesInfo;
  }

  /**
   * {@inheritDoc}
   */
  public boolean replayOperation(
      Iterator<Modification> modsIterator, ChangeNumber changeNumber,
      Entry modifiedEntry, Modification m)
  {
    // We are replaying an operation that was already done
    // on another master server and this operation has a potential
    // conflict
    // with some more recent operations on this same entry
    // we need to take the more complex path to solve them
    Attribute modAttr = m.getAttribute();
    AttributeType type = modAttr.getAttributeType();

    if (ChangeNumber.compare(changeNumber, getLastUpdateTime()) <= 0)
    {
      // the attribute was modified after this change -> conflict

      switch (m.getModificationType())
      {
      case DELETE:
        if (changeNumber.older(getDeleteTime()))
        {
          /* this delete is already obsoleted by a more recent delete
           * skip this mod
           */
          modsIterator.remove();
          break;
        }

        conflictDelete(changeNumber, type, m, modifiedEntry, modAttr);
        break;

      case ADD:
        conflictAdd(modsIterator, changeNumber,
                    modAttr.getValues(), modAttr.getOptions());
        break;

      case REPLACE:
        if (changeNumber.older(getDeleteTime()))
        {
          /* this replace is already obsoleted by a more recent delete
           * skip this mod
           */
          modsIterator.remove();
          break;
        }
        /* save the values that are added by the replace operation
         * into addedValues
         * first process the replace as a delete operation -> this generate
         * a list of values that should be kept
         * then process the addedValues as if they were coming from a add
         * -> this generate the list of values that needs to be added
         * concatenate the 2 generated lists into a replace
         */
        LinkedHashSet<AttributeValue> addedValues = modAttr.getValues();
        modAttr.setValues(new LinkedHashSet<AttributeValue>());

        this.conflictDelete(changeNumber, type, m, modifiedEntry, modAttr);

        LinkedHashSet<AttributeValue> keptValues = modAttr.getValues();
        this.conflictAdd(modsIterator, changeNumber, addedValues,
            modAttr.getOptions());
        keptValues.addAll(addedValues);
        break;

      case INCREMENT:
        // TODO : FILL ME
        break;
      }
      return true;
    }
    else
    {
      processLocalOrNonConflictModification(changeNumber, m);
      return false;// the attribute was not modified more recently
    }
  }

  /**
   * This method calculate the historical information and update the hist
   * attribute to store the historical information for modify operation that
   * does not conflict with previous operation.
   * This is the usual path and should therefore be optimized.
   *
   * It does not check if the operation to process is conflicting or not with
   * previous operations. The caller is responsible for this.
   *
   * @param changeNumber The changeNumber of the operation to process
   * @param mod The modify operation to process.
   */
  public void processLocalOrNonConflictModification(ChangeNumber changeNumber,
      Modification mod)
  {
    /*
     * The operation is either a non-conflicting operation or a local
     * operation so there is no need to check the historical information
     * for conflicts.
     * If this is a local operation, then this code is run after
     * the pre-operation phase.
     * If this is a non-conflicting replicated operation, this code is run
     * during the handleConflictResolution().
     */

    Attribute modAttr = mod.getAttribute();
    AttributeType type = modAttr.getAttributeType();

    switch (mod.getModificationType())
    {
    case DELETE:
      if (modAttr.getValues().isEmpty())
      {
        delete(changeNumber);
      }
      else
      {
        delete(modAttr.getValues(), changeNumber);
      }
      break;

    case ADD:
      if (type.isSingleValue())
      {
        delete(changeNumber);
      }
      add(modAttr.getValues(), changeNumber);
      break;

    case REPLACE:
      /* TODO : can we replace specific attribute values ????? */
      delete(changeNumber);
      add(modAttr.getValues(), changeNumber);
      break;

    case INCREMENT:
      /* FIXME : we should update ChangeNumber */
      break;
    }
  }

  /**
   * Process a delete attribute values that is conflicting with a previous
   * modification.
   *
   * @param changeNumber The changeNumber of the currently processed change
   * @param type attribute type
   * @param m the modification that is being processed
   * @param modifiedEntry the entry that is modified (before current mod)
   * @param attrInfo the historical info associated to the entry
   * @param modAttr the attribute modification
   * @return false if there is nothing to do
   */
  private boolean conflictDelete(ChangeNumber changeNumber,
                                AttributeType type, Modification m,
                                Entry modifiedEntry,
                                Attribute modAttr )
  {
    LinkedHashSet<AttributeValue> delValues;
    LinkedHashSet<AttributeValue> replValues;

    /*
     * We are processing a conflicting DELETE modification
     *
     * This code is written on the assumption that conflict are
     * rare. We therefore don't care much about the performance
     * However since it is rarely executed this code needs to be
     * as simple as possible to make sure that all paths are tested.
     * In this case the most simple seem to change the DELETE
     * in a REPLACE modification that keeps all values
     * more recent that the DELETE.
     * we are therefore going to change m into a REPLACE that will keep
     * all the values that have been updated after the DELETE time
     * If a value is present in the entry without any state information
     * it must be removed so we simply ignore them
     */



    delValues = modAttr.getValues();
    if ((delValues == null) || (delValues.isEmpty()))
    {
      /*
       * We are processing a DELETE attribute modification
       */
      m.setModificationType(ModificationType.REPLACE);
      replValues = new LinkedHashSet<AttributeValue>();

      for (Iterator it = getValuesInfo().iterator();
           it.hasNext();)
      {
        ValueInfo valInfo; valInfo = (ValueInfo) it.next();

        if (changeNumber.older(valInfo.getValueUpdateTime()))
        {
          /*
           * this value has been updated after this delete, therefore
           * this value must be kept
           */
          replValues.add(valInfo.getValue());
        }
        else
        {
          /*
           * this value is going to be deleted, remove it from historical
           * information unless it is a Deleted attribute value that is
           * more recent than this DELETE
           */
          if (changeNumber.newerOrEquals(valInfo.getValueDeleteTime()))
          {
            it.remove();
          }
        }
      }

      modAttr.setValues(replValues);
      if (changeNumber.newer(getDeleteTime()))
      {
        deleteTime = changeNumber;
      }
      if (changeNumber.newer(getLastUpdateTime()))
      {
        lastUpdateTime = changeNumber;
      }
    }
    else
    {
      /*
       * we are processing DELETE of some attribute values
       */
      ArrayList<ValueInfo> valuesInfo = getValuesInfo();

      for (Iterator<AttributeValue> delValIterator = delValues.iterator();
           delValIterator.hasNext();)
      {
        AttributeValue val = delValIterator.next();
        Boolean deleteIt = true;  // true if the delete must be done

        /* update historical information */
        ValueInfo valInfo = new ValueInfo(val, null, changeNumber);
        int index = valuesInfo.indexOf(valInfo);
        if (index != -1)
        {
          /* this value already exist in the historical information */
          ValueInfo oldValInfo  = valuesInfo.get(index);
          if (changeNumber.newer(oldValInfo.getValueDeleteTime()) &&
              changeNumber.newer(oldValInfo.getValueUpdateTime()))
          {
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          else if (oldValInfo.isUpdate())
          {
            deleteIt = false;
          }
        }
        else
        {
          valuesInfo.add(valInfo);
        }
        /* if the attribute value is not to be deleted
         * or if attribute value is not present suppress it from the
         * mod to make sure the delete is going to process again
         */
        modifiedEntry.getAttribute(type);
        if (!deleteIt
            || !modifiedEntry.hasValue(type, modAttr.getOptions(), val))
        {
          delValIterator.remove();
        }
      }
      if (changeNumber.newer(getLastUpdateTime()))
      {
        lastUpdateTime = changeNumber;
      }
    }
    return true;
  }

  /**
   * Process a add attribute values that is conflicting with a previous
   * modification.
   *
   * @param modsIterator iterator on the list of modification
   * @param changeNumber  the historical info associated to the entry
   * @param addValues the values that are added
   * @param options the options that are added
   * @return false if operation becomes empty and must not be processed
   */
  private boolean conflictAdd(Iterator modsIterator, ChangeNumber changeNumber,
                          LinkedHashSet<AttributeValue> addValues,
                          Set<String> options)
  {
    /* if historicalattributedelete is newer forget this mod
     *   else find attr value
     *     if does not exist
     *           add historicalvalueadded timestamp
     *           add real value in entry
     *     else if timestamp older and already was historicalvalueadded
     *        update historicalvalueadded
     *     else if timestamp older and was historicalvaluedeleted
     *        change historicalvaluedeleted into historicalvalueadded
     *        add value in real entry
     */

    if (changeNumber.older(getDeleteTime()))
    {
      /* A delete has been done more recently than this add
       * forget this MOD ADD
       */
      modsIterator.remove();
      return false;
    }

    for (Iterator<AttributeValue> valIterator = addValues.iterator();
         valIterator.hasNext();)
    {
      AttributeValue addVal= valIterator.next();
      ArrayList<ValueInfo> valuesInfo = getValuesInfo();
      ValueInfo valInfo = new ValueInfo(addVal, changeNumber, null);
      int index = valuesInfo.indexOf(valInfo);
      if (index == -1)
      {
        /* this values does not exist yet
         * add it in the historical information
         * let the operation process normally
         */
        valuesInfo.add(valInfo);
      }
      else
      {
        ValueInfo oldValueInfo = valuesInfo.get(index);
        if  (oldValueInfo.isUpdate())
        {
          /* if the value is already present
           * check if the updateTime must be updated
           * in all cases suppress this value from the value list
           * as it is already present in the entry
           */
          if (changeNumber.newer(oldValueInfo.getValueUpdateTime()))
          {
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          valIterator.remove();
        }
        else
        {
          /* this value is marked as a deleted value
           * check if this mod is more recent the this delete
           */
          if (changeNumber.newer(oldValueInfo.getValueDeleteTime()))
          {
            /* this add is more recent,
             * remove the old delete historical information
             * and add our more recent one
             * let the operation process
             */
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          else
          {
            /* the delete that is present in the historical information
             * is more recent so it must win,
             * remove this value from the list of values to add
             * don't update the historical information
             */
            valIterator.remove();
          }
        }
      }
    }
    if (addValues.isEmpty())
    {
      modsIterator.remove();
    }

    if (changeNumber.newer(getLastUpdateTime()))
    {
      lastUpdateTime = changeNumber;
    }
    return true;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void load(HistKey histKey, AttributeValue value, ChangeNumber cn)
  {
    switch (histKey)
    {
    case ADD:
      if (value != null)
      {
        add(value, cn);
      }
      break;

    case DEL:
      if (value != null)
      {
        delete(value, cn);
      }
      break;

    case REPL:
      delete(cn);
      if (value != null)
      {
        add(value, cn);
      }
      break;

    case DELATTR:
        delete(cn);
      break;
    }
  }
}



 opends/src/server/org/opends/server/replication/plugin/AttrInfoSingle.java

New file
@@ -0,0 +1,231 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2007 Sun Microsystems, Inc.
 */
package org.opends.server.replication.plugin;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;

import org.opends.server.replication.common.ChangeNumber;
import org.opends.server.types.Attribute;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.Entry;
import org.opends.server.types.Modification;
import org.opends.server.types.ModificationType;

/**
 * This classes is used to store historical information for single valued
 * attributes.
 * One object of this type is created for each attribute that was changed in
 * the entry.
 * It allows to record the last time a given value was added,
 * and the last time the whole attribute was deleted.
 */
public class AttrInfoSingle extends AttributeInfo
{
  private ChangeNumber deleteTime = null; // last time when the attribute was
                                          // deleted
  private ChangeNumber addTime = null;    // last time when a value was added
  private AttributeValue value = null;    // last added value

  /**
   * {@inheritDoc}
   */
  @Override
  public ChangeNumber getDeleteTime()
  {
    return deleteTime;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public ArrayList<ValueInfo> getValuesInfo()
  {
    if (addTime == null)
    {
      return new ArrayList<ValueInfo>();
    }
    else
    {
      ArrayList<ValueInfo> values = new ArrayList<ValueInfo>();
      values.add(new ValueInfo(value, addTime, null));
      return values;
    }
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void processLocalOrNonConflictModification(ChangeNumber changeNumber,
      Modification mod)
  {
    Attribute modAttr = mod.getAttribute();
    LinkedHashSet<AttributeValue> values = null;
    if (modAttr != null)
      values = modAttr.getValues();
    AttributeValue newValue = null;
    if (values.size() != 0)
      newValue = values.iterator().next();

    switch (mod.getModificationType())
    {
    case DELETE:
      deleteTime = changeNumber;
      value = newValue;
      break;

    case ADD:
      addTime = changeNumber;
      value = newValue;
      break;

    case REPLACE:
      deleteTime = addTime = changeNumber;
      value = newValue;
      break;

    case INCREMENT:
      /* FIXME : we should update ChangeNumber */
      break;
    }
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public boolean replayOperation(Iterator<Modification> modsIterator,
      ChangeNumber changeNumber, Entry modifiedEntry, Modification mod)
  {
    boolean conflict = false;

    Attribute modAttr = mod.getAttribute();
    LinkedHashSet<AttributeValue> values = null;
    if (modAttr != null)
      values = modAttr.getValues();
    AttributeValue newValue = null;
    if (values.size() != 0)
      newValue = values.iterator().next();

    switch (mod.getModificationType())
    {
    case DELETE:
      if ((changeNumber.newer(addTime)) &&
          ((newValue == null) || ((newValue != null)
                                  && (newValue.equals(value)))))
      {
        deleteTime = changeNumber;
      }
      else
      {
        conflict = true;
        modsIterator.remove();
      }
      break;

    case ADD:
      if (changeNumber.newerOrEquals(deleteTime) && changeNumber.older(addTime))
      {
        conflict = true;
        mod.setModificationType(ModificationType.REPLACE);
        addTime = changeNumber;
        value = newValue;
      }
      else
      {
        if (changeNumber.newerOrEquals(deleteTime)
            && ((addTime == null ) || addTime.older(deleteTime)))
        {
          // no conflict : don´t do anything beside setting the addTime
          addTime = changeNumber;
          value = newValue;
        }
        else
        {
          conflict = true;
          modsIterator.remove();
        }
      }

      break;

    case REPLACE:
      if ((changeNumber.older(deleteTime)) && (changeNumber.older(deleteTime)))
      {
        conflict = true;
        modsIterator.remove();
      }
      else
      {
        addTime = changeNumber;
        value = newValue;
        deleteTime = changeNumber;
      }
      break;

    case INCREMENT:
      /* FIXME : we should update ChangeNumber */
      break;
    }
    return conflict;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void load(HistKey histKey, AttributeValue value, ChangeNumber cn)
  {
    switch (histKey)
    {
    case ADD:
      addTime = cn;
      this.value = value;
      break;

    case DEL:
      deleteTime = cn;
      if (value != null)
        this.value = value;
      break;

    case REPL:
      addTime = deleteTime = cn;
      if (value != null)
        this.value = value;
      break;

    case DELATTR:
      deleteTime = cn;
      break;
    }
  }
}


 opends/src/server/org/opends/server/replication/plugin/AttrInfoWithOptions.java

@@ -36,14 +36,14 @@
 */
public class AttrInfoWithOptions
{
  private HashMap<Set<String> ,AttrInfo> attributesInfo;
  private HashMap<Set<String> ,AttributeInfo> attributesInfo;

  /**
   * creates a new AttrInfoWithOptions.
   */
  public AttrInfoWithOptions()
  {
    attributesInfo = new HashMap<Set<String> ,AttrInfo>();
    attributesInfo = new HashMap<Set<String> ,AttributeInfo>();
  }

  /**
@@ -52,7 +52,7 @@
   * @param options the options
   * @return the information
   */
  public AttrInfo get(Set<String> options)
  public AttributeInfo get(Set<String> options)
  {
    return attributesInfo.get(options);
  }
@@ -64,7 +64,7 @@
   * @param attrInfo the info to associate
   * @return the info to associate
   */
  public AttrInfo put(Set<String> options,AttrInfo attrInfo )
  public AttributeInfo put(Set<String> options, AttributeInfo attrInfo )
  {
    return attributesInfo.put(options, attrInfo);
  }
@@ -73,7 +73,7 @@
   * get the Attributes information associated to this object.
   * @return the set of informations
   */
  public HashMap<Set<String>, AttrInfo> getAttributesInfo()
  public HashMap<Set<String>, AttributeInfo> getAttributesInfo()
  {
    return attributesInfo;
  }

 opends/src/server/org/opends/server/replication/plugin/AttributeInfo.java

New file
@@ -0,0 +1,119 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.replication.plugin;

import java.util.ArrayList;
import java.util.Iterator;

import org.opends.server.replication.common.ChangeNumber;
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.Entry;
import org.opends.server.types.Modification;


/**
 * This classes is used to store historical information.
 * One object of this type is created for each attribute that was changed in
 * the entry.
 */
public abstract class AttributeInfo
{
  /**
   * This method will be called when replaying an operation.
   * It should use whatever historical information is stored in this class
   * to solve the conflict and modify the mod and the mods iterator accordingly
   *
   * @param modsIterator  The iterator on the mods from which the mod is\
   *                      extracted.
   * @param changeNumber  The changeNumber associated to the operation.
   * @param modifiedEntry The entry modified by this operation.
   * @param mod           The modification.
   *
   * @return a boolean indicating if a conflict was detected.
   */
  public abstract boolean replayOperation(
      Iterator<Modification> modsIterator, ChangeNumber changeNumber,
      Entry modifiedEntry, Modification mod);

  /**
   * This method calculate the historical information and update the hist
   * attribute to store the historical information for modify operation that
   * does not conflict with previous operation.
   * This is the usual path and should therefore be optimized.
   *
   * It does not check if the operation to process is conflicting or not with
   * previous operations. The caller is responsible for this.
   *
   * @param changeNumber The changeNumber of the operation to process
   * @param mod The modify operation to process.
   */
  public abstract void processLocalOrNonConflictModification(
      ChangeNumber changeNumber, Modification mod);

  /**
   * Create a new AttributeInfo object that will be used with the givene type.
   *
   * @param type the AttrbuteType with which the ATtributeInfo is going to be
   *             used.
   * @return a new AttributeInfo object.
   */
  public static AttributeInfo createAttributeInfo(AttributeType type)
  {
    if (type.isSingleValue())
      return new AttrInfoSingle();
    else
      return new AttrInfoMultiple();
  }

  /**
   * Get the List of ValueInfo for this attribute Info.
   *
   * @return the List of ValueInfo
   */
  public abstract ArrayList<ValueInfo> getValuesInfo();


  /**
   * Returns the last time when the attribute was deleted.
   *
   * @return the last time when the attribute was deleted
   */
  public abstract ChangeNumber getDeleteTime();

  /**
   * Load the provided information.
   *
   * @param histKey the key to load.
   * @param value   the associated value or null if there is no value;
   * @param cn      the associated ChangeNumber.
   */
  public abstract void load(
      HistKey histKey, AttributeValue value, ChangeNumber cn);

}


 opends/src/server/org/opends/server/replication/plugin/HistVal.java

@@ -70,6 +70,9 @@
     *  description:00000108b3a6cbb800000001:repl:new_value
     *  or
     *  description:00000108b3a6cbb800000001:delAttr
     *  or
     *  description:00000108b3a6554100000001:add
     *  or
     *
     *  so after split
     *  token[0] will contain the attribute name
@@ -104,8 +107,13 @@
    stringValue = null;
    if (histKey != HistKey.DELATTR)
    {
      stringValue = token[3];
      attributeValue = new AttributeValue(attrType, stringValue);
      if (token.length == 4)
      {
        stringValue = token[3];
        attributeValue = new AttributeValue(attrType, stringValue);
      }
      else
        attributeValue = null;
    }
    else
    {

 opends/src/server/org/opends/server/replication/plugin/Historical.java

@@ -26,7 +26,10 @@
 */
package org.opends.server.replication.plugin;

import java.util.ArrayList;
import static org.opends.server.loggers.ErrorLogger.logError;
import static org.opends.server.messages.MessageHandler.getMessage;
import static org.opends.server.messages.ReplicationMessages.*;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
@@ -45,6 +48,8 @@
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.Entry;
import org.opends.server.types.ErrorLogCategory;
import org.opends.server.types.ErrorLogSeverity;
import org.opends.server.types.Modification;
import org.opends.server.types.ModificationType;

@@ -84,11 +89,6 @@
  static final AttributeType entryuuidAttrType =
    DirectoryServer.getSchema().getAttributeType(ENTRYUIDNAME);

  /*
   * The last update seen on this entry, allows fast conflict detection.
   */
  private ChangeNumber moreRecentChangenumber =
                              new ChangeNumber(0,0,(short)0);

  /*
   * contains Historical information for each attribute sorted by attribute type
@@ -108,21 +108,6 @@
  }

  /**
   * Duplicates an Historical Object.
   * attributesInfo are nor duplicated but used as references.
   * @return The duplicate of the Historical Object
   */
  public Historical duplicate()
  {
    Historical dup = new Historical();

    dup.attributesInfo =
                new HashMap<AttributeType,AttrInfoWithOptions>(attributesInfo);
    dup.moreRecentChangenumber = this.moreRecentChangenumber;
    return dup;
  }

  /**
   * Process an operation.
   * This method is responsible for detecting and resolving conflict for
   * modifyOperation. This is done by using the historical information.
@@ -132,200 +117,33 @@
   * @return true if the replayed operation was in conflict
   */
  public boolean replayOperation(ModifyOperation modifyOperation,
                              Entry modifiedEntry)
                                 Entry modifiedEntry)
  {
    boolean bConflict = false;
    List<Modification> mods = modifyOperation.getModifications();
    ChangeNumber changeNumber =
      OperationContext.getChangeNumber(modifyOperation);

    for (Iterator modsIterator = mods.iterator(); modsIterator.hasNext();)
    for (Iterator<Modification> modsIterator = mods.iterator();
         modsIterator.hasNext(); )
    {
      Modification m = (Modification) modsIterator.next();
      Attribute modAttr = m.getAttribute();
      Set<String> options = modAttr.getOptions();
      AttributeType type = modAttr.getAttributeType();
      AttrInfoWithOptions attrInfoWithOptions =  attributesInfo.get(type);
      AttrInfo attrInfo = null;
      if (attrInfoWithOptions != null)
      Modification m = modsIterator.next();

      AttributeInfo attrInfo = getAttrInfo(m);

      if (attrInfo.replayOperation(modsIterator, changeNumber,
                                   modifiedEntry, m))
      {
        attrInfo = attrInfoWithOptions.get(options);
      }

      if (this.hasConflict(attrInfo, changeNumber))
      {
        // We are replaying an operation that was already done
        // on another master server and this operation has a potential
        // conflict
        // with some more recent operations on this same entry
        // we need to take the more complex path to solve them

        switch (m.getModificationType())
        {
          case DELETE:
            if (changeNumber.older(attrInfo.getDeleteTime()))
            {
              /* this delete is already obsoleted by a more recent delete
              * skip this mod
              */
              modsIterator.remove();
              break;
            }

            this.conflictDelete(changeNumber,
                                type, m, modifiedEntry, attrInfo, modAttr);
            break;

          case ADD:
            this.conflictAdd(modsIterator, changeNumber, attrInfo,
                             modAttr.getValues(), modAttr.getOptions());
            break;

          case REPLACE:
            if (changeNumber.older(attrInfo.getDeleteTime()))
            {
              /* this replace is already obsoleted by a more recent delete
              * skip this mod
              */
              modsIterator.remove();
              break;
            }
            /* save the values that are added by the replace operation
            * into addedValues
            * first process the replace as a delete operation -> this generate
            * a list of values that should be kept
            * then process the addedValues as if they were coming from a add
            * -> this generate the list of values that needs to be added
            * concatenate the 2 generated lists into a replace
            */
            LinkedHashSet<AttributeValue> addedValues = modAttr.getValues();
            modAttr.setValues(new LinkedHashSet<AttributeValue>());

            this.conflictDelete(changeNumber, type, m, modifiedEntry,
                                attrInfo, modAttr);

            LinkedHashSet<AttributeValue> keptValues = modAttr.getValues();
            this.conflictAdd(modsIterator, changeNumber, attrInfo, addedValues,
                             modAttr.getOptions());
            keptValues.addAll(addedValues);
            break;

          case INCREMENT:
            // TODO : FILL ME
            break;
        }
        bConflict = true;
      }
      else
      {
        processLocalOrNonConflictModification(changeNumber, m);
      }
    }

    // TODO : now purge old historical information

    if (moreRecentChangenumber == null ||
         moreRecentChangenumber.older(changeNumber))
    {
      moreRecentChangenumber = changeNumber;
    }
    return bConflict;
  }

  /**
   * This method calculate the historical information and update the hist
   * attribute to store the historical information for modify operation that
   * does not conflict with previous operation.
   * This is the usual path and should therefore be optimized.
   *
   * It does not check if the operation to process is conflicting or not with
   * previous operations. The caller is responsible for this.
   *
   * @param changeNumber The changeNumber of the operation to process
   * @param mod The modify operation to process.
   */
  private void processLocalOrNonConflictModification(ChangeNumber changeNumber,
      Modification mod)
  {
    /*
     * The operation is either a non-conflicting operation or a local
     * operation so there is no need to check the historical information
     * for conflicts.
     * If this is a local operation, the this code is run during
     * the pre-operation phase (TODO : should make sure that replication
     * is always run after all other plugins)
     * If this is a non-conflicting replicated operation, this code is run
     * during the handleConflictResolution().
     */

    Attribute modAttr = mod.getAttribute();
    if (modAttr.getAttributeType().equals(historicalAttrType))
    {
      return;
    }
    Set<String> options = modAttr.getOptions();
    AttributeType type = modAttr.getAttributeType();
    AttrInfoWithOptions attrInfoWithOptions =  attributesInfo.get(type);
    AttrInfo attrInfo;
    if (attrInfoWithOptions != null)
    {
      attrInfo = attrInfoWithOptions.get(options);
    }
    else
    {
      attrInfo = null;
    }

    /*
     * The following code only works for multi-valued attributes.
     * TODO : See impact of single valued attributes
     */
    if (attrInfo == null)
    {
      attrInfo = new AttrInfo();
      if (attrInfoWithOptions == null)
      {
        attrInfoWithOptions = new AttrInfoWithOptions();
      }
      attrInfoWithOptions.put(options, attrInfo);
      attributesInfo.put(type, attrInfoWithOptions);
    }
    switch (mod.getModificationType())
    {
    case DELETE:
      if (modAttr.getValues().isEmpty())
      {
        attrInfo.delete(changeNumber);
      }
      else
      {
        attrInfo.delete(modAttr.getValues(), changeNumber);
      }
      break;

    case ADD:
      if (type.isSingleValue())
      {
        attrInfo.delete(changeNumber);
      }
      attrInfo.add(modAttr.getValues(), changeNumber);
      break;

    case REPLACE:
      /* TODO : can we replace specific attribute values ????? */
      attrInfo.delete(changeNumber);
      attrInfo.add(modAttr.getValues(), changeNumber);
      break;

    case INCREMENT:
      /* FIXME : we should update ChangeNumber */
      break;
    }
  }


  /**
   * Append replacement of state information to a given modification.
   *
   * @param modifyOperation the modification.
   */
  public void generateState(ModifyOperation modifyOperation)
@@ -346,12 +164,9 @@
    {
      for (Modification mod : mods)
      {
        processLocalOrNonConflictModification(changeNumber, mod);
      }
      if (moreRecentChangenumber == null ||
           moreRecentChangenumber.older(changeNumber))
      {
        moreRecentChangenumber = changeNumber;
        AttributeInfo attrInfo = getAttrInfo(mod);
        if (attrInfo != null)
          attrInfo.processLocalOrNonConflictModification(changeNumber, mod);
      }
    }

@@ -364,6 +179,48 @@
  }

  /**
   * Get the AttrInfo for a given Modification.
   * The AttrInfo is the object that is used to store the historical
   * information of a given attribute type.
   * If there is no historical information for this attribute yet, a new
   * empty AttrInfo is created and returned.
   *
   * @param mod The Modification that must be used.
   * @return The AttrInfo corresponding to the given Modification.
   */
  private AttributeInfo getAttrInfo(Modification mod)
  {
    Attribute modAttr = mod.getAttribute();
    if (modAttr.getAttributeType().equals(Historical.historicalAttrType))
    {
      // Don´t keep historical information for the attribute that is
      // used to store the historical information.
      return null;
    }
    Set<String> options = modAttr.getOptions();
    AttributeType type = modAttr.getAttributeType();
    AttrInfoWithOptions attrInfoWithOptions =  attributesInfo.get(type);
    AttributeInfo attrInfo;
    if (attrInfoWithOptions != null)
    {
      attrInfo = attrInfoWithOptions.get(options);
    }
    else
    {
      attrInfoWithOptions = new AttrInfoWithOptions();
      attributesInfo.put(type, attrInfoWithOptions);
      attrInfo = null;
    }

    if (attrInfo == null)
    {
      attrInfo = AttributeInfo.createAttributeInfo(type);
      attrInfoWithOptions.put(options, attrInfo);
    }
    return attrInfo;
  }

  /**
   * Encode the historical information in an operational attribute.
   * @return The historical information encoded in an operational attribute.
   */
@@ -376,16 +233,17 @@

    {
      AttributeType type = entryWithOptions.getKey();
      HashMap<Set<String> , AttrInfo> attrwithoptions =
      HashMap<Set<String> , AttributeInfo> attrwithoptions =
                                entryWithOptions.getValue().getAttributesInfo();

      for (Map.Entry<Set<String>, AttrInfo> entry : attrwithoptions.entrySet())
      for (Map.Entry<Set<String>, AttributeInfo> entry :
           attrwithoptions.entrySet())
      {
        boolean delAttr = false;
        Set<String> options = entry.getKey();
        String optionsString = "";
        AttrInfo info = entry.getValue();
        ChangeNumber deleteTime = info.getDeleteTime();
        AttributeInfo info = entry.getValue();


        if (options != null)
        {
@@ -398,6 +256,7 @@
          optionsString = optionsBuilder.toString();
        }

        ChangeNumber deleteTime = info.getDeleteTime();
        /* generate the historical information for deleted attributes */
        if (deleteTime != null)
        {
@@ -428,9 +287,18 @@
            }
            else
            {
              strValue = type.getNormalizedPrimaryName() + optionsString + ":" +
              valInfo.getValueUpdateTime().toString() +
              ":add:" + valInfo.getValue().toString();
              if (valInfo.getValue() == null)
              {
                strValue = type.getNormalizedPrimaryName() + optionsString
                           + ":" + valInfo.getValueUpdateTime().toString() +
                           ":add";
              }
              else
              {
                strValue = type.getNormalizedPrimaryName() + optionsString
                           + ":" + valInfo.getValueUpdateTime().toString() +
                           ":add:" + valInfo.getValue().toString();
              }
            }

            AttributeValue val = new AttributeValue(historicalAttrType,
@@ -463,286 +331,6 @@
    return attr;
  }

  /**
   * Detect if a new change has a potential conflict with previous changes.
   * Must be blinding fast
   * @param info the historical information for the attribute that
   * was modified
   * @param newChange the ChangeNumber of the change for which we need to check
   *        for potential conflict
   * @return true if there is a potential conflict, false otherwise
   */
  private boolean hasConflict(AttrInfo info, ChangeNumber newChange)
  {
    // if I've already seen a change that is more recent than the one
    // that is currently being processed, then there is
    // a potential conflict
    if (ChangeNumber.compare(newChange, moreRecentChangenumber) <= 0)
    {
      if (info == null)
      {
        return false;   // the attribute was never modified -> no conflict
      }
      else if (ChangeNumber.compare(newChange, info.getLastUpdateTime()) <= 0)
      {
        return true; // the attribute was modified after this change -> conflict
      }
      else
      {
        return false;// the attribute was not modified more recently
      }
    }
    else
    {
      return false;
    }
  }

  /**
   * Process a delete attribute values that is conflicting with a previous
   * modification.
   *
   * @param changeNumber The changeNumber of the currently processed change
   * @param type attribute type
   * @param m the modification that is being processed
   * @param modifiedEntry the entry that is modified (before current mod)
   * @param attrInfo the historical info associated to the entry
   * @param modAttr the attribute modification
   * @return false if there is nothing to do
   */
  private boolean conflictDelete(ChangeNumber changeNumber,
                                AttributeType type, Modification m,
                                Entry modifiedEntry,
                                AttrInfo attrInfo, Attribute modAttr )
  {
    LinkedHashSet<AttributeValue> delValues;
    LinkedHashSet<AttributeValue> replValues;

    /*
     * We are processing a conflicting DELETE modification
     *
     * This code is written on the assumption that conflict are
     * rare. We therefore don't care much about the performance
     * However since it is rarely executed this code needs to be
     * as simple as possible to make sure that all paths are tested.
     * In this case the most simple seem to change the DELETE
     * in a REPLACE modification that keeps all values
     * more recent that the DELETE.
     * we are therefore going to change m into a REPLACE that will keep
     * all the values that have been updated after the DELETE time
     * If a value is present in the entry without any state information
     * it must be removed so we simply ignore them
     */



    delValues = modAttr.getValues();
    if ((delValues == null) || (delValues.isEmpty()))
    {
      /*
       * We are processing a DELETE attribute modification
       */
      m.setModificationType(ModificationType.REPLACE);
      replValues = new LinkedHashSet<AttributeValue>();

      for (Iterator it = attrInfo.getValuesInfo().iterator();
           it.hasNext();)
      {
        ValueInfo valInfo; valInfo = (ValueInfo) it.next();

        if (changeNumber.older(valInfo.getValueUpdateTime()))
        {
          /*
           * this value has been updated after this delete, therefore
           * this value must be kept
           */
          replValues.add(valInfo.getValue());
        }
        else
        {
          /*
           * this value is going to be deleted, remove it from historical
           * information unless it is a Deleted attribute value that is
           * more recent than this DELETE
           */
          if (changeNumber.newerOrEquals(valInfo.getValueDeleteTime()))
          {
            it.remove();
          }
        }
      }

      modAttr.setValues(replValues);
      if (changeNumber.newer(attrInfo.getDeleteTime()))
      {
        attrInfo.setDeleteTime(changeNumber);
      }
      if (changeNumber.newer(attrInfo.getLastUpdateTime()))
      {
        attrInfo.setLastUpdateTime(changeNumber);
      }
    }
    else
    {
      /*
       * we are processing DELETE of some attribute values
       */
      ArrayList<ValueInfo> valuesInfo = attrInfo.getValuesInfo();

      for (Iterator<AttributeValue> delValIterator = delValues.iterator();
           delValIterator.hasNext();)
      {
        AttributeValue val = delValIterator.next();
        Boolean deleteIt = true;  // true if the delete must be done

        /* update historical information */
        ValueInfo valInfo = new ValueInfo(val, null, changeNumber);
        int index = valuesInfo.indexOf(valInfo);
        if (index != -1)
        {
          /* this value already exist in the historical information */
          ValueInfo oldValInfo  = valuesInfo.get(index);
          if (changeNumber.newer(oldValInfo.getValueDeleteTime()) &&
              changeNumber.newer(oldValInfo.getValueUpdateTime()))
          {
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          else if (oldValInfo.isUpdate())
          {
            deleteIt = false;
          }
        }
        else
        {
          valuesInfo.add(valInfo);
        }
        /* if the attribute value is not to be deleted
         * or if attribute value is not present suppress it from the
         * mod to make sure the delete is going to process again
         */
        modifiedEntry.getAttribute(type);
        if (!deleteIt
            || !modifiedEntry.hasValue(type, modAttr.getOptions(), val))
        {
          delValIterator.remove();
        }
      }
      if (changeNumber.newer(attrInfo.getLastUpdateTime()))
      {
        attrInfo.setLastUpdateTime(changeNumber);
      }
    }
    return true;
  }

  /**
   * Process a add attribute values that is conflicting with a previous
   * modification.
   *
   * @param modsIterator iterator on the list of modification
   * @param changeNumber  the historical info associated to the entry
   * @param attrInfo the historical info associated to the entry
   * @param addValues the values that are added
   * @param options the options that are added
   * @return false if operation becomes empty and must not be processed
   */
  private boolean conflictAdd(Iterator modsIterator, ChangeNumber changeNumber,
                          AttrInfo attrInfo,
                          LinkedHashSet<AttributeValue> addValues,
                          Set<String> options)
  {
    /* if historicalattributedelete is newer forget this mod
     *   else find attr value
     *     if does not exist
     *           add historicalvalueadded timestamp
     *           add real value in entry
     *     else if timestamp older and already was historicalvalueadded
     *        update historicalvalueadded
     *     else if timestamp older and was historicalvaluedeleted
     *        change historicalvaluedeleted into historicalvalueadded
     *        add value in real entry
     */

    if (changeNumber.older(attrInfo.getDeleteTime()))
    {
      /* A delete has been done more recently than this add
       * forget this MOD ADD
       */
      modsIterator.remove();
      return false;
    }

    for (Iterator<AttributeValue> valIterator = addValues.iterator();
         valIterator.hasNext();)
    {
      AttributeValue addVal= valIterator.next();
      ArrayList<ValueInfo> valuesInfo = attrInfo.getValuesInfo();
      ValueInfo valInfo = new ValueInfo(addVal, changeNumber, null);
      int index = valuesInfo.indexOf(valInfo);
      if (index == -1)
      {
        /* this values does not exist yet
         * add it in the historical information
         * let the operation process normally
         */
        valuesInfo.add(valInfo);
      }
      else
      {
        ValueInfo oldValueInfo = valuesInfo.get(index);
        if  (oldValueInfo.isUpdate())
        {
          /* if the value is already present
           * check if the updateTime must be updated
           * in all cases suppress this value from the value list
           * as it is already present in the entry
           */
          if (changeNumber.newer(oldValueInfo.getValueUpdateTime()))
          {
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          valIterator.remove();
        }
        else
        {
          /* this value is marked as a deleted value
           * check if this mod is more recent the this delete
           */
          if (changeNumber.newer(oldValueInfo.getValueDeleteTime()))
          {
            /* this add is more recent,
             * remove the old delete historical information
             * and add our more recent one
             * let the operation process
             */
            valuesInfo.remove(index);
            valuesInfo.add(valInfo);
          }
          else
          {
            /* the delete that is present in the historical information
             * is more recent so it must win,
             * remove this value from the list of values to add
             * don't update the historical information
             */
            valIterator.remove();
          }
        }
      }
    }
    if (addValues.isEmpty())
    {
      modsIterator.remove();
    }

    if (changeNumber.newer(attrInfo.getLastUpdateTime()))
    {
      attrInfo.setLastUpdateTime(changeNumber);
    }
    return true;
  }

  /**
   * read the historical information from the entry attribute and
@@ -756,7 +344,7 @@
    Historical histObj = new Historical();
    AttributeType lastAttrType = null;
    Set<String> lastOptions = new HashSet<String>();
    AttrInfo attrInfo = null;
    AttributeInfo attrInfo = null;
    AttrInfoWithOptions attrInfoWithOptions = null;

    if (hist == null)
@@ -764,89 +352,70 @@
      return histObj;
    }

    for (Attribute attr : hist)
    try
    {
      for (AttributeValue val : attr.getValues())
      for (Attribute attr : hist)
      {
        HistVal histVal = new HistVal(val.getStringValue());
        AttributeType attrType = histVal.getAttrType();
        Set<String> options = histVal.getOptions();
        ChangeNumber cn = histVal.getCn();
        AttributeValue value = histVal.getAttributeValue();
        HistKey histKey = histVal.getHistKey();

        if (attrType == null)
        for (AttributeValue val : attr.getValues())
        {
          /*
           * This attribute is unknown from the schema
           * Just skip it, the modification will be processed but no
           * historical information is going to be kept.
           * TODO : recovery tool should deal with this, add some logging.
           */
          continue;
        }
          HistVal histVal = new HistVal(val.getStringValue());
          AttributeType attrType = histVal.getAttrType();
          Set<String> options = histVal.getOptions();
          ChangeNumber cn = histVal.getCn();
          AttributeValue value = histVal.getAttributeValue();
          HistKey histKey = histVal.getHistKey();

        /* if attribute type does not match we create new
         *   AttrInfoWithOptions and AttrInfo
         *   we also add old AttrInfoWithOptions into histObj.attributesInfo
         * if attribute type match but options does not match we create new
         *   AttrInfo that we add to AttrInfoWithOptions
         * if both match we keep everything
         */
        if (attrType != lastAttrType)
        {
          attrInfo = new AttrInfo();
          attrInfoWithOptions = new AttrInfoWithOptions();
          attrInfoWithOptions.put(options, attrInfo);
          histObj.attributesInfo.put(attrType, attrInfoWithOptions);

          lastAttrType = attrType;
          lastOptions = options;
        }
        else
        {
          if (!options.equals(lastOptions))
          if (attrType == null)
          {
            attrInfo = new AttrInfo();
            /*
             * This attribute is unknown from the schema
             * Just skip it, the modification will be processed but no
             * historical information is going to be kept.
             * TODO : REPAIR tool should deal with this, add some logging.
             */
            continue;
          }

          /* if attribute type does not match we create new
           *   AttrInfoWithOptions and AttrInfo
           *   we also add old AttrInfoWithOptions into histObj.attributesInfo
           * if attribute type match but options does not match we create new
           *   AttrInfo that we add to AttrInfoWithOptions
           * if both match we keep everything
           */
          if (attrType != lastAttrType)
          {
            attrInfo = AttributeInfo.createAttributeInfo(attrType);
            attrInfoWithOptions = new AttrInfoWithOptions();
            attrInfoWithOptions.put(options, attrInfo);
            histObj.attributesInfo.put(attrType, attrInfoWithOptions);

            lastAttrType = attrType;
            lastOptions = options;
          }
        }

        if (histObj.moreRecentChangenumber.older(cn))
        {
          histObj.moreRecentChangenumber = cn;
        }

        switch (histKey)
        {
        case ADD:
          if (value != null)
          else
          {
            attrInfo.add(value, cn);
            if (!options.equals(lastOptions))
            {
              attrInfo = AttributeInfo.createAttributeInfo(attrType);
              attrInfoWithOptions.put(options, attrInfo);
              lastOptions = options;
            }
          }
        break;

        case DEL:
          if (value != null)
          {
            attrInfo.delete(value, cn);
          }
        break;

        case REPL:
          attrInfo.delete(cn);
          if (value != null)
          {
            attrInfo.add(value, cn);
          }
        break;

        case DELATTR:
          attrInfo.delete(cn);
        break;
          attrInfo.load(histKey, value, cn);
        }
      }
    } catch (Exception e)
    {
      // Any exception happening here means that the coding of the hsitorical
      // information was wrong.
      // Log an error and continue with an empty historical.
      int    msgID   = MSGID_BAD_HISTORICAL;
      String message = getMessage(msgID, entry.getDN().toString());
      logError(ErrorLogCategory.SYNCHRONIZATION,
               ErrorLogSeverity.SEVERE_ERROR,
               message, msgID);
    }

    /* set the reference to the historical information in the entry */

 opends/tests/unit-tests-testng/src/server/org/opends/server/replication/plugin/AttrInfoTest.java

@@ -32,7 +32,7 @@
import org.opends.server.core.DirectoryServer;
import org.opends.server.replication.ReplicationTestCase;
import org.opends.server.replication.common.ChangeNumber;
import org.opends.server.replication.plugin.AttrInfo;
import org.opends.server.replication.plugin.AttrInfoMultiple;
import org.opends.server.replication.plugin.ValueInfo;
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
@@ -87,23 +87,7 @@
      throws Exception
  {
    // Create an empty AttrInfo
    AttrInfo attrInfo1 = new AttrInfo();

    // Check getLastUpdateTime setLastUpdateTime
    if (attrInfo1.getLastUpdateTime() != null)
    {
      assertTrue(false);
    }
    attrInfo1.setLastUpdateTime(updateTime);
    assertTrue(attrInfo1.getLastUpdateTime().compareTo(updateTime) == 0);

    // Check getDeleteTime setDeleteTime
    if (attrInfo1.getDeleteTime() != null)
    {
      assertTrue(false);
    }
    attrInfo1.setDeleteTime(deleteTime);
    assertTrue(attrInfo1.getDeleteTime().compareTo(deleteTime) == 0);
    AttrInfoMultiple attrInfo1 = new AttrInfoMultiple();

    // Check add(AttributeValue val, ChangeNumber CN)
    attrInfo1.add(att, updateTime);
@@ -116,15 +100,13 @@
    ValueInfo valueInfo2 = new ValueInfo(att, updateTime, deleteTime);
    ArrayList<ValueInfo> values = new ArrayList<ValueInfo>();
    values.add(valueInfo2);
    AttrInfo attrInfo2 = new AttrInfo(deleteTime, updateTime, values);
    AttrInfoMultiple attrInfo2 = new AttrInfoMultiple(deleteTime, updateTime, values);

    // Check equality
    assertTrue(attrInfo1.getLastUpdateTime().compareTo(
        attrInfo2.getLastUpdateTime()) == 0);
    assertTrue(attrInfo1.getDeleteTime().compareTo(attrInfo2.getDeleteTime())==0);
    //assertTrue(attrInfo1.getDeleteTime().compareTo(attrInfo2.getDeleteTime())==0);

    //  Check constructor with time parameter and not Value
    AttrInfo attrInfo3 = new AttrInfo(deleteTime, updateTime, null);
    AttrInfoMultiple attrInfo3 = new AttrInfoMultiple(deleteTime, updateTime, null);
    attrInfo3.add(att, updateTime);
    ArrayList<ValueInfo> values3 = attrInfo3.getValuesInfo();
    assertTrue(values3.size() == 1);
@@ -132,11 +114,9 @@
    assertTrue(values3.get(0).equals(valueInfo1));

    // Check duplicate
    AttrInfo attrInfo4 = attrInfo3.duplicate();
    AttrInfoMultiple attrInfo4 = attrInfo3.duplicate();
    ArrayList<ValueInfo> values4 = attrInfo4.getValuesInfo();
    assertTrue(attrInfo4.getDeleteTime().compareTo(attrInfo3.getDeleteTime())==0);
    assertTrue(attrInfo4.getLastUpdateTime().compareTo(
        attrInfo3.getLastUpdateTime()) == 0);
    assertEquals(values4.size(), values3.size());

    // Check delete(AttributeValue val, ChangeNumber CN)

 opends/tests/unit-tests-testng/src/server/org/opends/server/replication/plugin/HistoricalTest.java

@@ -195,7 +195,7 @@
   * second server on a different entry.  Confused yet?
   * @throws Exception If the test fails.
   */
  @Test(enabled=false, groups="slow")
  @Test(enabled=true, groups="slow")
  public void conflictSingleValue()
       throws Exception
  {

 opends/tests/unit-tests-testng/src/server/org/opends/server/replication/plugin/ModifyConflictTest.java

@@ -55,6 +55,7 @@
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.DN;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.Entry;
import org.opends.server.types.Modification;
import org.opends.server.types.ModificationType;
@@ -82,32 +83,7 @@
  @Test()
  public void replaceAndAdd() throws Exception
  {
    DN dn = DN.decode("dc=com");
    Map<ObjectClass, String> objectClasses = new HashMap<ObjectClass, String>();
    ObjectClass org = DirectoryServer.getObjectClass("organization");
    objectClasses.put(org, "organization");

    Entry entry = new Entry(dn, objectClasses, null, null);

    // Construct a new random UUID. and add it into the entry
    UUID uuid = UUID.randomUUID();

    // Create the att values list of uuid
    LinkedHashSet<AttributeValue> valuesUuid =
      new LinkedHashSet<AttributeValue>(1);
    valuesUuid.add(new AttributeValue(Historical.entryuuidAttrType,
        new ASN1OctetString(uuid.toString())));
    ArrayList<Attribute> uuidList = new ArrayList<Attribute>(1);
    Attribute uuidAttr = new Attribute(Historical.entryuuidAttrType,
        "entryUUID", valuesUuid);
    uuidList.add(uuidAttr);

    /*
     * Add the uuid in the entry
     */
    Map<AttributeType, List<Attribute>> operationalAttributes = entry
        .getOperationalAttributes();
    operationalAttributes.put(Historical.entryuuidAttrType, uuidList);
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);
@@ -143,38 +119,55 @@
  }
  
  /**
   * Test that conflict between a modify-replace and modify-add for
   * single-valued attributes are handled correctly.
   */
  @Test()
  public void replaceAndAddSingle() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a modify-replace done at time t10
     */
    testModify(entry, hist, "displayname", ModificationType.REPLACE,
               "init value", 10, true);

    /*
     * Now simulate an add at an earlier date that the previous replace
     * conflict resolution should remove it.
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
               "older value", 1, false);

    /*
     * Now simulate an add at an earlier date that the previous replace
     * conflict resolution should remove it. (a second time to make
     * sure...)
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
               "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous replace.
     * conflict resolution should remove it
     */
    testModify(entry, hist, "displayname", ModificationType.ADD, "new value",
               11, false);

  }

  /**
   * Test that conflict between modify-add and modify-replace for
   * multi-valued attributes are handled correctly.
   */
  @Test()
  public void addAndReplace() throws Exception
  {
    DN dn = DN.decode("dc=com");
    Map<ObjectClass, String> objectClasses = new HashMap<ObjectClass, String>();
    ObjectClass org = DirectoryServer.getObjectClass("organization");
    objectClasses.put(org, "organization");

    Entry entry = new Entry(dn, objectClasses, null, null);

    // Construct a new random UUID. and add it into the entry
    UUID uuid = UUID.randomUUID();

    // Create the att values list of uuid
    LinkedHashSet<AttributeValue> valuesUuid =
      new LinkedHashSet<AttributeValue>(1);
    valuesUuid.add(new AttributeValue(Historical.entryuuidAttrType,
        new ASN1OctetString(uuid.toString())));
    ArrayList<Attribute> uuidList = new ArrayList<Attribute>(1);
    Attribute uuidAttr = new Attribute(Historical.entryuuidAttrType,
        "entryUUID", valuesUuid);
    uuidList.add(uuidAttr);

    /*
     * Add the uuid in the entry
     */
    Map<AttributeType, List<Attribute>> operationalAttributes = entry
        .getOperationalAttributes();
    operationalAttributes.put(Historical.entryuuidAttrType, uuidList);
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);
@@ -208,6 +201,399 @@
        "new value", 11, true);

  }
  
  /**
   * Test that conflict between modify-add and modify-replace for
   * single-valued attributes are handled correctly.
   */
  @Test()
  public void addAndReplaceSingle() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a modify-add done at time 2
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "init value", 2, true);

    /*
     * Now simulate a replace at an earlier date that the previous replace
     * conflict resolution should keep it.
     */
    testModify(entry, hist, "displayname", ModificationType.REPLACE,
        "older value", 1, true);

    /*
     * Now simulate a replace at a later date.
     * Conflict resolution should keept it.
     */
    testModify(entry, hist, "displayname", ModificationType.REPLACE,
        "older value", 3, true);

  }

  /**
   * Test that conflict between a modify-delete-attribute and modify-add
   * for multi-valued attributes are handled correctly.
   */
  @Test()
  public void deleteAndAdd() throws Exception
  {
    Entry entry = initializeEntry();


    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a delete of the whole description attribute done at time
     * t10
     */
    testModify(entry, hist, "description", ModificationType.DELETE, null, 10,
        true);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored.
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 1, false);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored. (a
     * second time to make sure that historical information is kept...)
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous delete.
     * conflict resolution should keep it
     */
    testModify(entry, hist, "description", ModificationType.ADD, "new value",
        11, true);
  }
  
  /**
   * Test that conflict between a modify-delete-attribute and modify-add
   * for multi-valued attributes are handled correctly.
   */
  @Test()
  public void deleteAndAddSingle() throws Exception
  {
    Entry entry = initializeEntry();


    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a delete of the whole description attribute done at time
     * t2
     */
    testModify(entry, hist, "displayname", ModificationType.DELETE, null, 3,
        true);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored.
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "older value", 1, false);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored. (a
     * second time to make sure that historical information is kept...)
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous delete.
     * conflict resolution should keep it
     */
    testModify(entry, hist, "displayname", ModificationType.ADD, "new value",
        4, true);
  }
  
  /**
   * Test that conflict between a modify-delete-attribute and modify-add
   * for multi-valued attributes are handled correctly.
   */
  @Test()
  public void deleteAndReplace() throws Exception
  {
    Entry entry = initializeEntry();


    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a delete of the whole description attribute done at time
     * t4
     */
    testModify(entry, hist, "description", ModificationType.DELETE, null, 4,
        true);

    /*
     * Now simulate a replace at an earlier date that the previous delete. The
     * conflict resolution should detect that this replace must be ignored.
     */
    testModify(entry, hist, "description", ModificationType.REPLACE,
        "new value", 3, false);
  }
  
  /**
   * Test that conflict between a modify-delete-attribute and modify-add
   * for multi-valued attributes are handled correctly.
   */
  @Test()
  public void deleteAndReplaceSingle() throws Exception
  {
    Entry entry = initializeEntry();


    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a delete of the whole description attribute done at time
     * t4
     */
    testModify(entry, hist, "displayname", ModificationType.DELETE, null, 4,
        true);

    /*
     * Now simulate a replace at an earlier date that the previous delete. The
     * conflict resolution should detect that this replace must be ignored.
     */
    testModify(entry, hist, "displayname", ModificationType.REPLACE,
        "new value", 3, false);
  }

  /**
   * Test that conflict between a modify-add and modify-add for
   * multi-valued attributes are handled correctly.
   */
  @Test()
  public void addAndAdd() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a add of the description attribute done at time t10
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "init value", 10, true);
    /*
     * Now simulate an add at an earlier date that the previous add. The
     * conflict resolution should detect that this add must be kept.
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 1, true);

    /*
     * Now simulate an add with a value already existing.
     * The conflict resolution should remove this add.
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous add. conflict
     * resolution should keep it
     */
    testModify(entry, hist, "description", ModificationType.ADD, "new value",
        11, true);
  }

  /**
   * Test that conflict between a modify-add and modify-add for
   * multi-valued attributes are handled correctly.
   */
  @Test()
  public void addAndAddSingle() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a add of the description attribute done at time t10
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "init value", 10, true);
    /*
     * Now simulate an add at an earlier date that the previous add. The
     * conflict resolution should detect that this add must be kept.
     * and that the previous value must be discarded, and therefore 
     * turn the add into a replace.
     */
    Modification mod = buildMod("displayname", ModificationType.ADD,
        "older value");
    List<Modification> mods = replayModify(entry, hist, mod, 1);
    
    /*
     * After replay the mods should contain only one mod,
     * the mod should now be a replace with the older value. 
     */
    testMods(mods, 1, ModificationType.REPLACE, "older value");

    /*
     * Now simulate a new value at a later date.
     * The conflict modify code should detect that there is already a value
     * and skip this change.
     */
    mod = buildMod("displayname", ModificationType.ADD, "new value");
    mods = replayModify(entry, hist, mod, 2);
    assertTrue(mods.isEmpty());
  }
  
  /**
   * Test that conflict between add delete and add are handled correctly.
   */
  @Test()
  public void addDelAddSingle() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a add of the description attribute done at time t1
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "init value", 1, true);
    
    /*
     * simulate a del of the description attribute done at time t3
     * this should be processed normally
     */
    testModify(entry, hist, "displayname", ModificationType.DELETE,
        "init value", 3, true);
    
    /*
     * Now simulate another add, that would come from another master
     * and done at time t2 (between t1 and t2)
     * This add should not be processed.
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "second value", 2, false);
  }
  
  /**
   * Test that conflict between add, add and delete are handled correctly.
   * 
   * This test simulate the case where a simple add is done on a first server
   * and at a later date but before replication happens, a add followed by 
   * a delete of the second value is done on another server.
   * The test checks that the firs tvalue wins and stay in the entry.  
   */
  @Test()
  public void addAddDelSingle() throws Exception
  {
    Entry entry = initializeEntry();

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a add of the description attribute done at time t1
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "first value", 1, true);
    
    /*
     * simulate a add of the description attribute done at time t2
     * with a second value. This should not work because there is already
     * a value
     */
    testModify(entry, hist, "displayname", ModificationType.ADD,
        "second value", 2, false);
    
    /*
     * Now simulate a delete of the second value.
     * The delete should not be accepted because it is done on a value
     * that did not get into the entry.
     */
    testModify(entry, hist, "displayname", ModificationType.DELETE,
        "second value", 2, false);
  }

  /**
   * Check that the mods given as first parameter match the next parameters.
   * 
   * @param mods The mods that must be tested.
   * @param size the size that the mods must have.
   * @param modType the type of Modification that the first mod of the 
   *                mods should have.   
   * @param value the value that the first mod of the mods should have.  
   */
  private void testMods(
      List<Modification> mods, int size, ModificationType modType, String value)
  {
    assertEquals(size, mods.size());
    Modification newMod = mods.get(0);
    assertTrue(newMod.getModificationType().equals(modType));
    AttributeValue val = newMod.getAttribute().getValues().iterator().next();
    assertEquals(val.getStringValue(), value);
  }

  /**
   * Create an initialize an entry that can be used for modify conflict
   * resolution tests.
   */
  private Entry initializeEntry() throws DirectoryException
  {
    /*
     * Objectclass and DN do not have any impact on the modifty conflict
     * resolution for the description attribute. Always use the same values
     * for all these tests.
     */
    DN dn = DN.decode("dc=com");
    Map<ObjectClass, String> objectClasses = new HashMap<ObjectClass, String>();
    ObjectClass org = DirectoryServer.getObjectClass("organization");
    objectClasses.put(org, "organization");

    /*
     * start with a new entry with an empty attribute
     */
    Entry entry = new Entry(dn, objectClasses, null, null);

    // Construct a new random UUID. and add it into the entry
    UUID uuid = UUID.randomUUID();

    // Create the att values list
    LinkedHashSet<AttributeValue> values = new LinkedHashSet<AttributeValue>(
        1);
    values.add(new AttributeValue(Historical.entryuuidAttrType,
        new ASN1OctetString(uuid.toString())));
    ArrayList<Attribute> uuidList = new ArrayList<Attribute>(1);
    Attribute uuidAttr = new Attribute(Historical.entryuuidAttrType,
        "entryUUID", values);
    uuidList.add(uuidAttr);

    /*
     * Add the uuid in the entry
     */
    Map<AttributeType, List<Attribute>> operationalAttributes = entry
        .getOperationalAttributes();

    operationalAttributes.put(Historical.entryuuidAttrType, uuidList);
    return entry;
  }

  /*
   * helper function.
@@ -262,8 +648,100 @@
    }
  }

  /*
   * helper function.
  /**
   * 
   *
   */
  private void testModify(Entry entry,
      Historical hist, String attrName,
      ModificationType modType, String value,
      int date, boolean keepChangeResult)
  {
    Modification mod = buildMod(attrName, modType, value);
    List<Modification> mods = replayModify(entry, hist, mod, date);

    if (keepChangeResult)
    {
      /*
       * The last change should have been detected as newer and
       * should be kept by the conflict resolution code.
       */
      assertTrue(mods.contains(mod));
      assertEquals(1, mods.size());
    }
    else
    {
      /*
       * The last older change should have been detected as conflicting and
       * should be removed by the conflict resolution code.
       */
      assertFalse(mods.contains(mod));
      assertEquals(0, mods.size());
    }
  }

  /**
   * 
   */
  private List<Modification> replayModify(
      Entry entry, Historical hist, Modification mod, int date)
  {
    InternalClientConnection connection =
      InternalClientConnection.getRootConnection();
    ChangeNumber t = new ChangeNumber(date, (short) 0, (short) 0);

    List<Modification> mods = new ArrayList<Modification>();
    mods.add(mod);

    ModifyOperation modOp = new ModifyOperation(connection, 1, 1, null,
        entry.getDN(), mods);
    ModifyContext ctx = new ModifyContext(t, "uniqueId");
    modOp.setAttachment(SYNCHROCONTEXT, ctx);

    hist.replayOperation(modOp, entry);
    if (mod.getModificationType() == ModificationType.ADD)
    {
      AddOperation addOp = new AddOperation(connection, 1, 1, null, entry
          .getDN(), entry.getObjectClasses(), entry.getUserAttributes(),
          entry.getOperationalAttributes());
      testHistorical(hist, addOp);
    }
    else
    {
      testHistoricalAndFake(hist, entry);
    }

    /*
     * Check that the encoding decoding of historical information
     * works  by encoding decoding and checking that the result is the same
     * as the initial value.
     */
    entry.removeAttribute(Historical.historicalAttrType);
    entry.addAttribute(hist.encode(), null);
    Historical hist2 = Historical.load(entry);
    assertEquals(hist2.encode().toString(), hist.encode().toString());
    
    return mods;
  }

  private Modification buildMod(
      String attrName, ModificationType modType, String value)
  {
    /* create AttributeType that will be used for this test */
    AttributeType attrType =
      DirectoryServer.getAttributeType(attrName, true);

    LinkedHashSet<AttributeValue> values = new LinkedHashSet<AttributeValue>();
    if (value != null)
      values.add(new AttributeValue(attrType, value));
    Attribute attr = new Attribute(attrType, attrName, values);
    Modification mod = new Modification(modType, attr);
    
    return mod;
  }

  /**
   *
   */
  private void testHistorical(
      Historical hist, AddOperation addOp)
@@ -288,223 +766,4 @@
      }
    }
  }

  /**
   * Test that conflict between a modify-delete-attribute and modify-add
   * for multi-valued attributes are handled correctly.
   */
  @Test()
  public void deleteAndAdd() throws Exception
  {
    /*
     * Objectclass and DN do not have any impact on the modifty conflict
     * resolution for the description attribute. Always use the same values
     * for all these tests.
     */
    DN dn = DN.decode("dc=com");
    Map<ObjectClass, String> objectClasses = new HashMap<ObjectClass, String>();
    ObjectClass org = DirectoryServer.getObjectClass("organization");
    objectClasses.put(org, "organization");

    /*
     * start with a new entry with an empty description
     */
    Entry entry = new Entry(dn, objectClasses, null, null);

    // Construct a new random UUID. and add it into the entry
    UUID uuid = UUID.randomUUID();

    // Create the att values list
    LinkedHashSet<AttributeValue> values = new LinkedHashSet<AttributeValue>(
        1);
    values.add(new AttributeValue(Historical.entryuuidAttrType,
        new ASN1OctetString(uuid.toString())));
    ArrayList<Attribute> uuidList = new ArrayList<Attribute>(1);
    Attribute uuidAttr = new Attribute(Historical.entryuuidAttrType,
        "entryUUID", values);
    uuidList.add(uuidAttr);

    /*
     * Add the uuid in the entry
     */
    Map<AttributeType, List<Attribute>> operationalAttributes = entry
        .getOperationalAttributes();

    operationalAttributes.put(Historical.entryuuidAttrType, uuidList);


    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a delete of the whole description attribute done at time
     * t10
     */
    testModify(entry, hist, "description", ModificationType.DELETE, null, 10,
        true);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored.
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 1, false);

    /*
     * Now simulate an add at an earlier date that the previous delete. The
     * conflict resolution should detect that this add must be ignored. (a
     * second time to make sure that historical information is kept...)
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous delete.
     * conflict resolution should keep it
     */
    testModify(entry, hist, "description", ModificationType.ADD, "new value",
        11, true);
  }

  /**
   * Test that conflict between a modify-add and modify-add for
   * multi-valued attributes are handled correctly.
   */
  @Test()
  public void addAndAdd() throws Exception
  {
    /*
     * Objectclass and DN do not have any impact on the modifty conflict
     * resolution for the description attribute. Always use the same values
     * for all these tests.
     */
    DN dn = DN.decode("dc=com");
    Map<ObjectClass, String> objectClasses = new HashMap<ObjectClass, String>();
    ObjectClass org = DirectoryServer.getObjectClass("organization");
    objectClasses.put(org, "organization");

    /*
     * start with a new entry with an empty description
     */
    Entry entry = new Entry(dn, objectClasses, null, null);

    // Construct a new random UUID. and add it into the entry
    UUID uuid = UUID.randomUUID();

    // Create the att values list
    LinkedHashSet<AttributeValue> values = new LinkedHashSet<AttributeValue>(
        1);
    values.add(new AttributeValue(Historical.entryuuidAttrType,
        new ASN1OctetString(uuid.toString())));
    ArrayList<Attribute> uuidList = new ArrayList<Attribute>(1);
    Attribute uuidAttr = new Attribute(Historical.entryuuidAttrType,
        "entryUUID", values);
    uuidList.add(uuidAttr);

    /*
     * Add the uuid in the entry
     */
    Map<AttributeType, List<Attribute>> operationalAttributes = entry
        .getOperationalAttributes();

    operationalAttributes.put(Historical.entryuuidAttrType, uuidList);

    // load historical from the entry
    Historical hist = Historical.load(entry);

    /*
     * simulate a add of the description attribute done at time t10
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "init value", 10, true);
    /*
     * Now simulate an add at an earlier date that the previous add. The
     * conflict resolution should detect that this add must be kept.
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 1, true);

    /*
     * Now simulate an add at an earlier date that the previous add. The
     * conflict resolution should detect that this add must be kept. (a
     * second time to make sure that historical information is kept...)
     */
    testModify(entry, hist, "description", ModificationType.ADD,
        "older value", 2, false);

    /*
     * Now simulate an add at a later date that the previous add. conflict
     * resolution should keep it
     */
    testModify(entry, hist, "description", ModificationType.ADD, "new value",
        11, true);
  }

  /*
   * helper function.
   */
  private void testModify(Entry entry,
      Historical hist, String attrName,
      ModificationType modType, String value,
      int date, boolean keepChangeResult)
  {
    InternalClientConnection connection =
        InternalClientConnection.getRootConnection();
    ChangeNumber t = new ChangeNumber(date, (short) 0, (short) 0);

    /* create AttributeType description that will be used for this test */
    AttributeType attrType =
      DirectoryServer.getAttributeType(attrName, true);

    LinkedHashSet<AttributeValue> values = new LinkedHashSet<AttributeValue>();
    if (value != null)
      values.add(new AttributeValue(attrType, value));
    Attribute attr = new Attribute(attrType, attrName, values);
    List<Modification> mods = new ArrayList<Modification>();
    Modification mod = new Modification(modType, attr);
    mods.add(mod);

    ModifyOperation modOp = new ModifyOperation(connection, 1, 1, null,
        entry.getDN(), mods);
    ModifyContext ctx = new ModifyContext(t, "uniqueId");
    modOp.setAttachment(SYNCHROCONTEXT, ctx);

    hist.replayOperation(modOp, entry);
    if (modType == ModificationType.ADD)
    {
      AddOperation addOp = new AddOperation(connection, 1, 1, null, entry
          .getDN(), entry.getObjectClasses(), entry.getUserAttributes(),
          entry.getOperationalAttributes());
      testHistorical(hist, addOp);
    }
    else
    {
      testHistoricalAndFake(hist, entry);
    }
    
    /*
     * Check that the encoding decoding of historical information
     * works  by encoding decoding and checking that the result is the same
     * as the initial value.
     */
    entry.removeAttribute(Historical.historicalAttrType);
    entry.addAttribute(hist.encode(), null);
    Historical hist2 = Historical.load(entry);
    assertEquals(hist2.encode().toString(), hist.encode().toString());
    
    /*
     * The last older change should have been detected as conflicting and
     * should be removed by the conflict resolution code.
     */
    if (keepChangeResult)
    {
      assertTrue(mods.contains(mod));
      assertEquals(1, mods.size());
    }
    else
    {
      assertFalse(mods.contains(mod));
      assertEquals(0, mods.size());
    }
  }
}