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); // NOSONAR 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}