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