Source code

001/*
002 * (C) Copyright 2014-2019 Nuxeo (http://nuxeo.com/) and others.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 *
016 * Contributors:
017 *     Florent Guillaume
018 */
019package org.nuxeo.ecm.core.storage;
020
021import static org.nuxeo.ecm.core.storage.State.NOP;
022
023import java.io.Serializable;
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Calendar;
027import java.util.Collections;
028import java.util.HashSet;
029import java.util.Iterator;
030import java.util.List;
031import java.util.Objects;
032import java.util.Set;
033import java.util.Map.Entry;
034import java.util.concurrent.CopyOnWriteArrayList;
035
036import org.nuxeo.ecm.core.api.model.Delta;
037import org.nuxeo.ecm.core.storage.State.ListDiff;
038import org.nuxeo.ecm.core.storage.State.StateDiff;
039import org.nuxeo.runtime.api.Framework;
040
041/**
042 * Helpers for deep copy and deep diff of {@link State} objects.
043 */
044public class StateHelper {
045
046    private static final String DISABLED_DELTA_PROP = "org.nuxeo.core.delta.disabled";
047
048    /** Utility class. */
049    private StateHelper() {
050    }
051
052    /**
053     * Checks if we have a base type compatible with {@link State} helper processing.
054     */
055    public static boolean isScalar(Object value) {
056        return value instanceof String //
057                || value instanceof Boolean //
058                || value instanceof Long //
059                || value instanceof Double //
060                || value instanceof Calendar //
061                || value instanceof Delta;
062    }
063
064    /**
065     * Compares two values.
066     */
067    public static boolean equalsStrict(Object a, Object b) {
068        if (a == b) {
069            return true;
070        } else if (a == null || b == null) {
071            return false;
072        } else if (a instanceof State && b instanceof State) {
073            return equalsStrict((State) a, (State) b);
074        } else if (a instanceof List && b instanceof List) {
075            @SuppressWarnings("unchecked")
076            List<Serializable> la = (List<Serializable>) a;
077            @SuppressWarnings("unchecked")
078            List<Serializable> lb = (List<Serializable>) b;
079            return equalsStrict(la, lb);
080        } else if (a instanceof Object[] && b instanceof Object[]) {
081            return equalsStrict((Object[]) a, (Object[]) b);
082        } else if (a instanceof ListDiff && b instanceof ListDiff) {
083            ListDiff lda = (ListDiff) a;
084            ListDiff ldb = (ListDiff) b;
085            return lda.isArray == ldb.isArray //
086                    && equalsStrict(lda.diff, ldb.diff) //
087                    && equalsStrict(lda.rpush, ldb.rpush) //
088                    && equalsStrict(lda.pull, ldb.pull);
089        } else if (isScalar(a) && isScalar(b)) {
090            return a.equals(b);
091        } else {
092            return false;
093        }
094    }
095
096    /**
097     * Compares two {@link State}s.
098     */
099    public static boolean equalsStrict(State a, State b) {
100        if (a == b) {
101            return true;
102        }
103        if (a == null || b == null) {
104            return false;
105        }
106        if (a.size() != b.size()) {
107            return false;
108        }
109        if (!a.keySet().equals(b.keySet())) {
110            return false;
111        }
112        for (Entry<String, Serializable> en : a.entrySet()) {
113            String key = en.getKey();
114            Serializable va = en.getValue();
115            Serializable vb = b.get(key);
116            if (!equalsStrict(va, vb)) {
117                return false;
118            }
119        }
120        return true;
121    }
122
123    /**
124     * Compares two arrays of scalars.
125     */
126    public static boolean equalsStrict(Object[] a, Object[] b) {
127        // we have scalars, Arrays.equals() is enough
128        return Arrays.equals(a, b);
129    }
130
131    /**
132     * Compares two {@link List}s.
133     */
134    public static boolean equalsStrict(List<Serializable> a, List<Serializable> b) {
135        if (a == b) {
136            return true;
137        }
138        if (a == null || b == null) {
139            return false;
140        }
141        if (a.size() != b.size()) {
142            return false;
143        }
144        for (Iterator<Serializable> ita = a.iterator(), itb = b.iterator(); ita.hasNext();) {
145            if (!equalsStrict(ita.next(), itb.next())) {
146                return false;
147            }
148        }
149        return true;
150    }
151
152    /**
153     * Compares two values.
154     * <p>
155     * A {@code null} value or an empty array or {@code List} is equivalent to an absent value. A {@code null}
156     * {@link State} is equivalent to an empty {@link State} (or a {@link State} containing only absent values).
157     */
158    public static boolean equalsLoose(Object a, Object b) {
159        if (a == b) {
160            return true;
161        } else if (a instanceof State && b instanceof State //
162                || a instanceof State && b == null //
163                || a == null && b instanceof State) {
164            return equalsLoose((State) a, (State) b);
165        } else if (a instanceof List && b instanceof List //
166                || a instanceof List && b == null //
167                || a == null && b instanceof List) {
168            @SuppressWarnings("unchecked")
169            List<Serializable> la = (List<Serializable>) a;
170            @SuppressWarnings("unchecked")
171            List<Serializable> lb = (List<Serializable>) b;
172            return equalsLoose(la, lb);
173        } else if (a instanceof Object[] && b instanceof Object[] //
174                || a instanceof Object[] && b == null //
175                || a == null && b instanceof Object[]) {
176            return equalsLoose((Object[]) a, (Object[]) b);
177        } else if (a instanceof ListDiff && b instanceof ListDiff) {
178            ListDiff lda = (ListDiff) a;
179            ListDiff ldb = (ListDiff) b;
180            return lda.isArray == ldb.isArray && equalsLoose(lda.diff, ldb.diff) && equalsLoose(lda.rpush, ldb.rpush);
181        } else if (isScalar(a) && isScalar(b)) {
182            return a.equals(b); // NOSONAR
183        } else {
184            return false;
185        }
186    }
187
188    /**
189     * Compares two {@link State}s.
190     * <p>
191     * A {@code null} value or an empty array or {@code List} is equivalent to an absent value. A {@code null}
192     * {@link State} is equivalent to an empty {@link State} (or a {@link State} containing only absent values).
193     */
194    public static boolean equalsLoose(State a, State b) {
195        if (a == null) {
196            a = State.EMPTY;
197        }
198        if (b == null) {
199            b = State.EMPTY;
200        }
201        for (Entry<String, Serializable> en : a.entrySet()) {
202            Serializable va = en.getValue();
203            if (va == null) {
204                // checked by loop on b
205                continue;
206            }
207            String key = en.getKey();
208            Serializable vb = b.get(key);
209            if (!equalsLoose(va, vb)) {
210                return false;
211            }
212        }
213        for (Entry<String, Serializable> en : b.entrySet()) {
214            String key = en.getKey();
215            Serializable va = a.get(key);
216            if (va != null) {
217                // already checked by loop on a
218                continue;
219            }
220            Serializable vb = en.getValue();
221            if (!equalsLoose(null, vb)) {
222                return false;
223            }
224        }
225        return true;
226    }
227
228    /**
229     * Compares two arrays of scalars.
230     * <p>
231     * {@code null} values are equivalent to empty arrays.
232     */
233    public static boolean equalsLoose(Object[] a, Object[] b) {
234        if (a != null && a.length == 0) {
235            a = null;
236        }
237        if (b != null && b.length == 0) {
238            b = null;
239        }
240        // we have scalars, Arrays.equals() is enough
241        return Arrays.equals(a, b);
242    }
243
244    /**
245     * Compares two {@link List}s.
246     * <p>
247     * {@code null} values are equivalent to empty lists.
248     */
249    public static boolean equalsLoose(List<Serializable> a, List<Serializable> b) {
250        if (a != null && a.isEmpty()) {
251            a = null;
252        }
253        if (b != null && b.isEmpty()) {
254            b = null;
255        }
256        if (a == b) {
257            return true;
258        }
259        if (a == null || b == null) {
260            return false;
261        }
262        if (a.size() != b.size()) {
263            return false;
264        }
265        for (Iterator<Serializable> ita = a.iterator(), itb = b.iterator(); ita.hasNext();) {
266            if (!equalsLoose(ita.next(), itb.next())) {
267                return false;
268            }
269        }
270        return true;
271    }
272
273    /**
274     * Makes a deep copy of a value.
275     */
276    public static Serializable deepCopy(Object value) {
277        return deepCopy(value, false);
278    }
279
280    /**
281     * Makes a deep copy of a value, optionally thread-safe.
282     *
283     * @param threadSafe if {@code true}, then thread-safe datastructures are used
284     */
285    public static Serializable deepCopy(Object value, boolean threadSafe) {
286        if (value == null) {
287            return (Serializable) value;
288        } else if (value instanceof State) {
289            return deepCopy((State) value, threadSafe);
290        } else if (value instanceof List) {
291            @SuppressWarnings("unchecked")
292            List<Serializable> list = (List<Serializable>) value;
293            return (Serializable) deepCopy(list, threadSafe);
294        } else if (value instanceof Object[]) {
295            // array values are supposed to be scalars
296            return ((Object[]) value).clone();
297        }
298        // else scalar value -- check anyway (debug)
299        else if (!isScalar(value)) {
300            throw new UnsupportedOperationException("Cannot deep copy: " + value.getClass().getName());
301        }
302        return (Serializable) value;
303    }
304
305    /**
306     * Makes a deep copy of a {@link State} map.
307     */
308    public static State deepCopy(State state) {
309        return deepCopy(state, false);
310    }
311
312    /**
313     * Makes a deep copy of a {@link State} map, optionally thread-safe.
314     *
315     * @param threadSafe if {@code true}, then thread-safe datastructures are used
316     */
317    public static State deepCopy(State state, boolean threadSafe) {
318        State copy = new State(state.size(), threadSafe);
319        for (Entry<String, Serializable> en : state.entrySet()) {
320            copy.put(en.getKey(), deepCopy(en.getValue(), threadSafe));
321        }
322        return copy;
323    }
324
325    /**
326     * Makes a deep copy of a {@link List}.
327     */
328    public static List<Serializable> deepCopy(List<Serializable> list) {
329        return deepCopy(list, false);
330    }
331
332    /**
333     * Makes a deep copy of a {@link List}, optionally thread-safe.
334     *
335     * @param threadSafe if {@code true}, then thread-safe datastructures are used
336     */
337    public static List<Serializable> deepCopy(List<Serializable> list, boolean threadSafe) {
338        List<Serializable> copy = threadSafe ? new CopyOnWriteArrayList<>() : new ArrayList<>(
339                list.size());
340        for (Serializable v : list) {
341            copy.add(deepCopy(v, threadSafe));
342        }
343        return copy;
344    }
345
346    /**
347     * Does a diff of two values.
348     *
349     * @return a {@link StateDiff}, a {@link ListDiff}, {@link State#NOP}, or an actual value (including {@code null})
350     */
351    public static Serializable diff(Object a, Object b) {
352        if (equalsLoose(a, b)) {
353            return NOP;
354        }
355        if ((a == null || a instanceof Object[]) && (b == null || b instanceof Object[])) {
356            return diff((Object[]) a, (Object[]) b);
357        }
358        if ((a == null || a instanceof List) && (b == null || b instanceof List)) {
359            @SuppressWarnings("unchecked")
360            List<Object> la = (List<Object>) a;
361            @SuppressWarnings("unchecked")
362            List<Object> lb = (List<Object>) b;
363            return diff(la, lb);
364        }
365        if (a instanceof State && b instanceof State) {
366            StateDiff diff = diff((State) a, (State) b);
367            return diff.isEmpty() ? NOP : diff;
368        }
369        return (Serializable) b;
370    }
371
372    public static Serializable diff(Object[] a, Object[] b) {
373        List<Object> la = a == null ? null : Arrays.asList(a);
374        List<Object> lb = b == null ? null : Arrays.asList(b);
375        Serializable diff = diff(la, lb);
376        if (diff instanceof List) {
377            return b;
378        }
379        ListDiff listDiff = (ListDiff) diff;
380        listDiff.isArray = true;
381        return listDiff;
382    }
383
384    public static Serializable diff(List<Object> a, List<Object> b) {
385        ListDiff listDiff = new ListDiff();
386        if (a == null) {
387            a = Collections.emptyList();
388        }
389        if (b == null) {
390            b = Collections.emptyList();
391        }
392        List<Object> pull = findPull(a, b);
393        if (pull != null) {
394            listDiff.pull = pull;
395            return listDiff;
396        }
397        int aSize = a.size();
398        int bSize = b.size();
399        boolean doRPush = aSize < bSize;
400        // we can use a list diff if lists are the same size,
401        // or we have a rpush
402        boolean doDiff = aSize == bSize || doRPush;
403        if (!doDiff) {
404            return (Serializable) b;
405        }
406        int len = Math.min(aSize, bSize);
407        List<Object> diff = new ArrayList<>(len);
408        int nops = 0;
409        int diffs = 0;
410        for (int i = 0; i < len; i++) {
411            Serializable elemDiff = diff(a.get(i), b.get(i));
412            if (elemDiff == NOP) {
413                nops++;
414            } else if (elemDiff instanceof StateDiff) {
415                diffs++;
416            }
417            // TODO if the individual element diffs are big StateDiffs,
418            // do a full State replacement instead
419            diff.add(elemDiff);
420        }
421        if (nops == len) {
422            // only nops
423            diff = null;
424        } else if (diffs == 0) {
425            // only setting elements or nops
426            // TODO use a higher ratio than 0% of diffs
427            return (Serializable) b;
428        }
429        listDiff.diff = diff;
430        if (doRPush) {
431            List<Object> rpush = new ArrayList<>(bSize - aSize);
432            for (int i = aSize; i < bSize; i++) {
433                rpush.add(b.get(i));
434            }
435            listDiff.rpush = rpush;
436        }
437        return listDiff;
438    }
439
440    /** @since 11.5 */
441    public static List<Object> findPull(List<Object> a, List<Object> b) {
442        // check that list size decreased
443        if (a.size() <= b.size()) {
444            return null;
445        }
446        // check that we have scalar element types (complex not supported)
447        Object value = a.get(0);
448        if (!isScalar(value)) {
449            return null;
450        }
451        // get the set difference
452        Set<Object> set = new HashSet<>(a);
453        set.removeAll(b);
454        if (set.isEmpty()) {
455            return null;
456        }
457        // check that it's really a pull operation (all candidates are removed)
458        List<Object> list = new ArrayList<>(a);
459        List<Object> pull = new ArrayList<>(set);
460        list.removeAll(pull);
461        if (!equalsLoose(list, b)) {
462            return null;
463        }
464        return pull;
465    }
466
467    /**
468     * Makes a diff copy of two {@link State} maps.
469     * <p>
470     * The returned diff state contains only the key/values that changed. {@code null} values are equivalent to absent
471     * values.
472     * <p>
473     * For values set to null or removed, the value is null.
474     * <p>
475     * When setting a delta, the old value is checked to know if the delta should be kept or if a full value should be
476     * set instead.
477     * <p>
478     * For sub-documents, a recursive diff is returned.
479     *
480     * @return a {@link StateDiff} which, when applied to a, gives b.
481     */
482    public static StateDiff diff(State a, State b) {
483        StateDiff diff = new StateDiff();
484        for (Entry<String, Serializable> en : a.entrySet()) {
485            Serializable va = en.getValue();
486            if (va == null) {
487                // checked by loop on b
488                continue;
489            }
490            String key = en.getKey();
491            Serializable vb = b.get(key);
492            if (vb == null) {
493                // value must be cleared
494                diff.put(key, null);
495            } else {
496                // compare values
497                Serializable elemDiff = diff(va, vb);
498                if (elemDiff != NOP) {
499                    if (elemDiff instanceof Delta) {
500                        Delta delta = (Delta) elemDiff;
501                        Serializable deltaBase = delta.getBase();
502                        if (!Objects.equals(va, deltaBase)) {
503                            // delta's base is not the old value
504                            // -> set a new value, don't use a delta update
505                            elemDiff = delta.getFullValue();
506                        }
507                        // else delta's base is the in-database value
508                        // because base is consistent with old value, assume the delta is already properly computed
509                    }
510                    diff.put(key, elemDiff);
511                }
512            }
513        }
514        for (Entry<String, Serializable> en : b.entrySet()) {
515            String key = en.getKey();
516            Serializable va = a.get(key);
517            if (va != null) {
518                // already checked by loop on a
519                continue;
520            }
521            Serializable vb = en.getValue();
522            if (!equalsLoose(null, vb)) {
523                // value must be set or rpushed
524                diff.put(key, rpushOrValue(vb));
525            }
526        }
527        return diff;
528    }
529
530    /**
531     * Returns a pure rpush ListDiff for the value if it's an array/list.
532     *
533     * @param value the value
534     * @return a pure rpush ListDiff for the value, if possible
535     * @since 11.4
536     */
537    public static Serializable rpushOrValue(Serializable value) {
538        if (value instanceof Object[]) {
539            ListDiff listDiff = new ListDiff();
540            listDiff.isArray = true;
541            listDiff.rpush = Arrays.asList((Object[]) value);
542            return listDiff;
543        } else if (value instanceof List) {
544            ListDiff listDiff = new ListDiff();
545            @SuppressWarnings("unchecked")
546            List<Object> list = (List<Object>) value;
547            listDiff.rpush = list;
548            return listDiff;
549        } else {
550            return value;
551        }
552    }
553
554    /**
555     * Changes the deltas stored into actual full values.
556     *
557     * @since 6.0
558     */
559    public static void resetDeltas(State state) {
560        if (Boolean.parseBoolean(Framework.getProperty(DISABLED_DELTA_PROP, "false"))) {
561            return;
562        }
563        for (Entry<String, Serializable> en : state.entrySet()) {
564            Serializable value = en.getValue();
565            if (value instanceof State) {
566                resetDeltas((State) value);
567            } else if (value instanceof Delta) {
568                state.put(en.getKey(), ((Delta) value).getFullValue());
569            }
570        }
571    }
572
573}