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