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