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