001/*
002 * The contents of this file are subject to the terms of the Common Development and
003 * Distribution License (the License). You may not use this file except in compliance with the
004 * License.
005 *
006 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
007 * specific language governing permission and limitations under the License.
008 *
009 * When distributing Covered Software, include this CDDL Header Notice in each file and include
010 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
011 * Header, with the fields enclosed by brackets [] replaced by your own identifying
012 * information: "Portions Copyright [year] [name of copyright owner]".
013 *
014 * Copyright 2006-2010 Sun Microsystems, Inc.
015 * Portions Copyright 2011-2017 ForgeRock AS.
016 */
017package org.opends.server.replication.plugin;
018
019import java.util.Iterator;
020import java.util.Set;
021
022import org.forgerock.opendj.ldap.ByteString;
023import org.forgerock.opendj.ldap.ModificationType;
024import org.forgerock.opendj.ldap.schema.AttributeType;
025import org.opends.server.replication.common.CSN;
026import org.opends.server.types.Attribute;
027import org.opends.server.types.AttributeBuilder;
028import org.opends.server.types.Entry;
029import org.opends.server.types.Modification;
030
031import com.forgerock.opendj.util.SmallSet;
032
033/**
034 * This class is used to store historical information for multiple valued attributes.
035 * One object of this type is created for each attribute that was changed in the entry.
036 * It allows to record the last time a given value was added,the last
037 * time a given value was deleted and the last time the whole attribute was deleted.
038 */
039public class AttrHistoricalMultiple extends AttrHistorical
040{
041  /** Last time when the attribute was deleted. */
042  private CSN deleteTime;
043  /** Last time the attribute was modified. */
044  private CSN lastUpdateTime;
045  /** Change history for the values of this attribute. */
046  private final SmallSet<AttrValueHistorical> valuesHist = new SmallSet<>();
047
048   /**
049    * Create a new object from the provided information.
050    * @param deleteTime the last time this attribute was deleted
051    * @param updateTime the last time this attribute was updated
052    * @param valuesHist the new attribute values when updated.
053    */
054   AttrHistoricalMultiple(CSN deleteTime, CSN updateTime, Set<AttrValueHistorical> valuesHist)
055   {
056     this.deleteTime = deleteTime;
057     this.lastUpdateTime = updateTime;
058     if (valuesHist != null)
059     {
060      this.valuesHist.addAll(valuesHist);
061     }
062   }
063
064   /** Creates a new object. */
065   public AttrHistoricalMultiple()
066   {
067     this.deleteTime = null;
068     this.lastUpdateTime = null;
069   }
070
071   /**
072    * Returns the last time when the attribute was updated.
073    * @return the last time when the attribute was updated
074    */
075   CSN getLastUpdateTime()
076   {
077     return lastUpdateTime;
078   }
079
080   @Override
081   public CSN getDeleteTime()
082   {
083     return deleteTime;
084   }
085
086   /**
087    * Delete all historical information that is older than the provided CSN for
088    * this attribute type.
089    * Add the delete attribute state information
090    * @param csn time when the delete was done
091    */
092   void delete(CSN csn)
093   {
094     // iterate through the values in the valuesInfo and suppress all the values
095     // that have not been added after the date of this delete.
096     for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();)
097     {
098       AttrValueHistorical info = it.next();
099       if (csn.isNewerThanOrEqualTo(info.getValueUpdateTime()) &&
100           csn.isNewerThanOrEqualTo(info.getValueDeleteTime()))
101      {
102        it.remove();
103      }
104     }
105
106     if (csn.isNewerThan(deleteTime))
107     {
108       deleteTime = csn;
109     }
110
111     if (csn.isNewerThan(lastUpdateTime))
112     {
113       lastUpdateTime = csn;
114     }
115   }
116
117  /**
118   * Update the historical of this attribute after deleting a set of values.
119   *
120   * @param attr
121   *          the attribute containing the set of values that were deleted
122   * @param csn
123   *          time when the delete was done
124   */
125  void delete(Attribute attr, CSN csn)
126  {
127    AttributeType attrType = attr.getAttributeDescription().getAttributeType();
128    for (ByteString val : attr)
129    {
130      delete(val, attrType, csn);
131    }
132  }
133
134   /**
135   * Update the historical of this attribute after a delete value.
136   *
137   * @param val
138   *          value that was deleted
139   * @param attrType
140   * @param csn
141   *          time when the delete was done
142   */
143  void delete(ByteString val, AttributeType attrType, CSN csn)
144   {
145     update(csn, new AttrValueHistorical(val, attrType, null, csn));
146   }
147
148  /**
149   * Update the historical information when values are added.
150   *
151   * @param attr
152   *          the attribute containing the set of added values
153   * @param csn
154   *          time when the add is done
155   */
156  private void add(Attribute attr, CSN csn)
157  {
158    AttributeType attrType = attr.getAttributeDescription().getAttributeType();
159    for (ByteString val : attr)
160    {
161      add(val, attrType, csn);
162    }
163  }
164
165  /**
166   * Update the historical information when a value is added.
167   *
168   * @param addedValue
169   *          the added value
170   * @param attrType
171   *          the attribute type of the added value
172   * @param csn
173   *          time when the value was added
174   */
175  void add(ByteString addedValue, AttributeType attrType, CSN csn)
176  {
177    update(csn, new AttrValueHistorical(addedValue, attrType, csn, null));
178  }
179
180  private void update(CSN csn, AttrValueHistorical valInfo)
181  {
182    valuesHist.addOrReplace(valInfo);
183    if (csn.isNewerThan(lastUpdateTime))
184    {
185      lastUpdateTime = csn;
186    }
187  }
188
189  @Override
190  public Set<AttrValueHistorical> getValuesHistorical()
191  {
192    return valuesHist;
193  }
194
195  @Override
196  public boolean replayOperation(Iterator<Modification> modsIterator, CSN csn,
197      Entry modifiedEntry, Modification m)
198  {
199    if (csn.isNewerThanOrEqualTo(getLastUpdateTime())
200        && m.getModificationType() == ModificationType.REPLACE)
201    {
202      processLocalOrNonConflictModification(csn, m);
203      return false;// the attribute was not modified more recently
204    }
205    // We are replaying an operation that was already done
206    // on another master server and this operation has a potential
207    // conflict with some more recent operations on this same entry
208    // we need to take the more complex path to solve them
209    return replayPotentialConflictModification(modsIterator, csn, modifiedEntry, m);
210  }
211
212  private boolean replayPotentialConflictModification(Iterator<Modification> modsIterator, CSN csn,
213      Entry modifiedEntry, Modification m)
214  {
215    // the attribute was modified after this change -> conflict
216    switch (m.getModificationType().asEnum())
217    {
218    case DELETE:
219      if (csn.isOlderThan(getDeleteTime()))
220      {
221        /* this delete is already obsoleted by a more recent delete
222         * skip this mod
223         */
224        modsIterator.remove();
225        return true;
226      }
227
228      if (!processDeleteConflict(csn, m, modifiedEntry))
229      {
230        modsIterator.remove();
231        return true;
232      }
233      return false;
234
235    case ADD:
236      if (!processAddConflict(csn, m))
237      {
238        modsIterator.remove();
239        return true;
240      }
241      return false;
242
243    case REPLACE:
244      if (csn.isOlderThan(getDeleteTime()))
245      {
246        /* this replace is already obsoleted by a more recent delete
247         * skip this mod
248         */
249        modsIterator.remove();
250        return true;
251      }
252
253      /* save the values that are added by the replace operation into addedValues
254       * first process the replace as a delete operation
255       * -> this generates a list of values that should be kept
256       * then process the addedValues as if they were coming from an add
257       * -> this generates the list of values that needs to be added
258       * concatenate the 2 generated lists into a replace
259       */
260      boolean conflict = false;
261      Attribute addedValues = m.getAttribute();
262      m.setAttribute(new AttributeBuilder(addedValues.getAttributeDescription()).toAttribute());
263
264      processDeleteConflict(csn, m, modifiedEntry);
265      Attribute keptValues = m.getAttribute();
266
267      m.setAttribute(addedValues);
268      if (!processAddConflict(csn, m))
269      {
270        modsIterator.remove();
271        conflict = true;
272      }
273
274      AttributeBuilder builder = new AttributeBuilder(keptValues);
275      builder.addAll(m.getAttribute());
276      m.setAttribute(builder.toAttribute());
277      return conflict;
278
279    case INCREMENT:
280      // TODO : FILL ME
281      return false;
282
283    default:
284      return false;
285    }
286  }
287
288  @Override
289  public void processLocalOrNonConflictModification(CSN csn, Modification mod)
290  {
291    /*
292     * The operation is either a non-conflicting operation or a local operation
293     * so there is no need to check the historical information for conflicts.
294     * If this is a local operation, then this code is run after
295     * the pre-operation phase.
296     * If this is a non-conflicting replicated operation, this code is run
297     * during the handleConflictResolution().
298     */
299
300    Attribute modAttr = mod.getAttribute();
301    AttributeType type = modAttr.getAttributeDescription().getAttributeType();
302
303    switch (mod.getModificationType().asEnum())
304    {
305    case DELETE:
306      if (modAttr.isEmpty())
307      {
308        delete(csn);
309      }
310      else
311      {
312        delete(modAttr, csn);
313      }
314      break;
315
316    case ADD:
317      if (type.isSingleValue())
318      {
319        delete(csn);
320      }
321      add(modAttr, csn);
322      break;
323
324    case REPLACE:
325      /* TODO : can we replace specific attribute values ????? */
326      delete(csn);
327      add(modAttr, csn);
328      break;
329
330    case INCREMENT:
331      /* FIXME : we should update CSN */
332      break;
333    }
334  }
335
336  /**
337   * Process a delete attribute values that is conflicting with a previous modification.
338   *
339   * @param csn The CSN of the currently processed change
340   * @param m the modification that is being processed
341   * @param modifiedEntry the entry that is modified (before current mod)
342   * @return {@code true} if no conflict was detected, {@code false} otherwise.
343   */
344  private boolean processDeleteConflict(CSN csn, Modification m, Entry modifiedEntry)
345  {
346    /*
347     * We are processing a conflicting DELETE modification
348     *
349     * This code is written on the assumption that conflict are
350     * rare. We therefore don't care much about the performance
351     * However since it is rarely executed this code needs to be
352     * as simple as possible to make sure that all paths are tested.
353     * In this case the most simple seem to change the DELETE
354     * in a REPLACE modification that keeps all values
355     * more recent that the DELETE.
356     * we are therefore going to change m into a REPLACE that will keep
357     * all the values that have been updated after the DELETE time
358     * If a value is present in the entry without any state information
359     * it must be removed so we simply ignore them
360     */
361
362    Attribute modAttr = m.getAttribute();
363    if (modAttr.isEmpty())
364    {
365      // We are processing a DELETE attribute modification
366      m.setModificationType(ModificationType.REPLACE);
367      AttributeBuilder builder = new AttributeBuilder(modAttr.getAttributeDescription());
368
369      for (Iterator<AttrValueHistorical> it = valuesHist.iterator(); it.hasNext();)
370      {
371        AttrValueHistorical valInfo = it.next();
372
373        if (csn.isOlderThan(valInfo.getValueUpdateTime()))
374        {
375          // this value has been updated after this delete,
376          // therefore this value must be kept
377          builder.add(valInfo.getAttributeValue());
378        }
379        else if (csn.isNewerThanOrEqualTo(valInfo.getValueDeleteTime()))
380        {
381          /*
382           * this value is going to be deleted, remove it from historical
383           * information unless it is a Deleted attribute value that is
384           * more recent than this DELETE
385           */
386          it.remove();
387        }
388      }
389
390      m.setAttribute(builder.toAttribute());
391
392      if (csn.isNewerThan(getDeleteTime()))
393      {
394        deleteTime = csn;
395      }
396      if (csn.isNewerThan(getLastUpdateTime()))
397      {
398        lastUpdateTime = csn;
399      }
400    }
401    else
402    {
403      // we are processing DELETE of some attribute values
404      AttributeBuilder builder = new AttributeBuilder(modAttr);
405
406      AttributeType attrType = modAttr.getAttributeDescription().getAttributeType();
407      for (ByteString val : modAttr)
408      {
409        boolean deleteIt = true;  // true if the delete must be done
410        boolean addedInCurrentOp = false;
411
412        // update historical information
413        AttrValueHistorical valInfo = new AttrValueHistorical(val, attrType, null, csn);
414        AttrValueHistorical oldValInfo = valuesHist.get(valInfo);
415        if (oldValInfo == null)
416        {
417          valuesHist.add(valInfo);
418        }
419        else
420        {
421          // this value already exist in the historical information
422          if (csn.equals(oldValInfo.getValueUpdateTime()))
423          {
424            // This value was added earlier in the same operation
425            // we need to keep the delete.
426            addedInCurrentOp = true;
427          }
428          if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime()) &&
429              csn.isNewerThanOrEqualTo(oldValInfo.getValueUpdateTime()))
430          {
431            valuesHist.addOrReplace(valInfo);
432          }
433          else if (oldValInfo.isUpdate())
434          {
435            deleteIt = false;
436          }
437        }
438
439        /* if the attribute value is not to be deleted
440         * or if attribute value is not present suppress it from the
441         * MOD to make sure the delete is going to succeed
442         */
443        if (!deleteIt
444            || (!modifiedEntry.hasValue(modAttr.getAttributeDescription(), val) && ! addedInCurrentOp))
445        {
446          // this value was already deleted before and therefore
447          // this should not be replayed.
448          builder.remove(val);
449          if (builder.isEmpty())
450          {
451            // This was the last values in the set of values to be deleted.
452            // this MOD must therefore be skipped.
453            return false;
454          }
455        }
456      }
457
458      m.setAttribute(builder.toAttribute());
459
460      if (csn.isNewerThan(getLastUpdateTime()))
461      {
462        lastUpdateTime = csn;
463      }
464    }
465
466    return true;
467  }
468
469  /**
470   * Process a add attribute values that is conflicting with a previous modification.
471   *
472   * @param csn
473   *          the historical info associated to the entry
474   * @param m
475   *          the modification that is being processed
476   * @return {@code true} if no conflict was detected, {@code false} otherwise.
477   */
478  private boolean processAddConflict(CSN csn, Modification m)
479  {
480    /*
481     * if historicalattributedelete is newer forget this mod else find
482     * attr value if does not exist add historicalvalueadded timestamp
483     * add real value in entry else if timestamp older and already was
484     * historicalvalueadded update historicalvalueadded else if
485     * timestamp older and was historicalvaluedeleted change
486     * historicalvaluedeleted into historicalvalueadded add value in
487     * real entry
488     */
489
490    if (csn.isOlderThan(getDeleteTime()))
491    {
492      /* A delete has been done more recently than this add
493       * forget this MOD ADD
494       */
495      return false;
496    }
497
498    Attribute attribute = m.getAttribute();
499    AttributeBuilder builder = new AttributeBuilder(attribute);
500    AttributeType attrType = attribute.getAttributeDescription().getAttributeType();
501    for (ByteString addVal : attribute)
502    {
503      AttrValueHistorical valInfo = new AttrValueHistorical(addVal, attrType, csn, null);
504      AttrValueHistorical oldValInfo = valuesHist.get(valInfo);
505      if (oldValInfo == null)
506      {
507        /* this value does not exist yet
508         * add it in the historical information
509         * let the operation process normally
510         */
511        valuesHist.add(valInfo);
512      }
513      else
514      {
515        if  (oldValInfo.isUpdate())
516        {
517          // if the value is already present check if the updateTime must be updated
518          if (csn.isNewerThan(oldValInfo.getValueUpdateTime()))
519          {
520            // replay the new value even though it is semantically the same as the value that's already in
521            // the entry. This is to handle cases where the client changes the case of a case ignore string,
522            // etc. The modify will succeed because we use the permissive modify control
523            valuesHist.addOrReplace(valInfo);
524          }
525          else
526          {
527            // don't replay the new value because it is older than the current value
528            builder.remove(addVal);
529          }
530        }
531        else
532        { // it is a delete
533          /* this value is marked as a deleted value
534           * check if this mod is more recent the this delete
535           */
536          if (csn.isNewerThanOrEqualTo(oldValInfo.getValueDeleteTime()))
537          {
538            valuesHist.addOrReplace(valInfo);
539          }
540          else
541          {
542            /* the delete that is present in the historical information
543             * is more recent so it must win,
544             * remove this value from the list of values to add
545             * don't update the historical information
546             */
547            builder.remove(addVal);
548          }
549        }
550      }
551    }
552
553    Attribute attr = builder.toAttribute();
554    m.setAttribute(attr);
555
556    if (attr.isEmpty())
557    {
558      return false;
559    }
560
561    if (csn.isNewerThan(getLastUpdateTime()))
562    {
563      lastUpdateTime = csn;
564    }
565    return true;
566  }
567
568  @Override
569  public void assign(HistAttrModificationKey histKey, AttributeType attrType, ByteString value, CSN csn)
570  {
571    switch (histKey)
572    {
573    case ADD:
574      if (value != null)
575      {
576        add(value, attrType, csn);
577      }
578      break;
579
580    case DEL:
581      if (value != null)
582      {
583        delete(value, attrType, csn);
584      }
585      break;
586
587    case REPL:
588      delete(csn);
589      if (value != null)
590      {
591        add(value, attrType, csn);
592      }
593      break;
594
595    case ATTRDEL:
596      delete(csn);
597      break;
598    }
599  }
600
601  @Override
602  public String toString()
603  {
604    final StringBuilder sb = new StringBuilder();
605    sb.append(getClass().getSimpleName()).append("(");
606    boolean deleteAppended = false;
607    if (deleteTime != null)
608    {
609      deleteAppended = true;
610      sb.append("deleteTime=").append(deleteTime);
611    }
612    if (lastUpdateTime != null)
613    {
614      if (deleteAppended)
615      {
616        sb.append(", ");
617      }
618      sb.append("lastUpdateTime=").append(lastUpdateTime);
619    }
620    sb.append(", valuesHist=").append(valuesHist);
621    sb.append(")");
622    return sb.toString();
623  }
624}